How to Determine the Time Complexity of Machine Learning Models for Prediction?

Question

I am used to calculating the time complexity of algorithms and data structures to understand how my code will perform in a production environment. However, when using machine learning (ML) and AI-based solutions, it becomes challenging to determine the asymptotic time complexity because the instructions are not explicitly written by me but instead learned from data. These learned models are often treated as a "black box," making it harder to analyze their computational requirements.

I want to focus specifically on the time complexity for prediction (inference), not training. For instance:

1. How can I determine the prediction time complexity of models such as k-Nearest Neighbors (k-NN)?
2. How can I evaluate the prediction time complexity for binary classification models based on deep learning (e.g., a simple feedforward neural network)?

Any detailed explanation or references to methodologies for analyzing the time complexity of ML models during prediction would be greatly appreciated.

Answer 1

Analyzing the time complexity of the prediction algorithm of an ML model depends on the algorithm and model. For example, in the case of neural networks, prediction starts with a forward pass, which is a series of matrix multiplications.

Here I explain how you can compute the time complexity of the forward pass of an FFNN, here the same for a CNN and here for an LSTM.

For other neural networks, you will need to perform a similar reasoning.

In general, neural networks perform matrix multiplications and a single matrix multiplication can be done in $O(n^3)$, although there are matrix multiplication algorithms with a better time complexity. See e.g. the Wikipedia article. If you multiply a matrix by a vector, that can be done in $O(n^2)$, assuming a square matrix.

You should keep in mind that, as opposed to traditional algorithms, here the time complexity depends not only on the input size but also on the model architecture.

Answer 2

Indeed if the ML model you employed is kept as a blackbox, you cannot estimate its theoretical time complexity for your input at inference time. So you need to have some knowledge about your model's inference mechanism to estimate, and the more exact knowledge you gain the more accurate your estimation will achieve.

For the example of common MLPs, it just has the forward pass mechanism at inference time which doesn't depend on the size of your input data (your input data is just represented by the input layer which is usually fixed in size) but instead on the modal parameters such as the number of total layers, the number of input neurons to a layer and the number of output neurons from the same layer.

However, for stacked-transformer models with $L$ total layers like GPT, though they're also neural networks, due to their inherent self-attention mechanism it's well known that the time complexity of your input sequence with length $n$ is $O(L(n^2d+nd^2))$ where $d$ is the dimension of the embedding space. Similarly for $K$-NNs, your input at inference time directly affects the time complexity because its inference mechanism involves computing distances between the input and all the $N$ training samples which depends on the number of features $d$ of your input in addition to the model's parameters such as $K$ and $N$.

Finally in practice you could use tools like TensorFlow or PyTorch's Profiler to measure time complexity empirically even with a blackbox ML model you're agnostic about.