Efficiency, Scaling, and Deployment Trade-Offs

Classical algorithms move work among fitting, memory, inference, updates, and explanation.

The reference-based end of that range has been measured rather than guessed. In February 2017 Facebook AI Research published its billion-scale similarity search work, with the numbers attached. The k-selection design runs “at up to 55% of theoretical peak performance”. The nearest-neighbour implementation is 8.5x faster than the prior GPU state of the art. What that buys is the last sentence of the abstract: “Our implementation enables the construction of a high accuracy k-NN graph on 95 million images from the Yfcc100M dataset in 35 minutes, and of a graph connecting 1 billion vectors in less than 12 hours on 4 Maxwell Titan X GPUs.” Facebook's own announcement of the Faiss library, a month later, repeats those benchmarks and adds the per-request side. On Deep1B, “getting a 1-recall@1 of 40 percent has a query time of less than 2 ms per vector”, against 20 ms for the prior published result at 45 percent.

Those are the numbers a neighbour-based model actually ships with. Not a parameter file and a function call. An index, a build budget in GPU-hours, and a recall setting that trades against milliseconds per vector.

A model can be efficient in one dimension. It can be expensive in another.

The dimension most often left out of a benchmark is also the largest one. Google engineers reported it from production in 2015, in a paper on hidden technical debt in machine learning systems. Their section on anti-patterns opens with the finding: “It may be surprising to the academic community to know that only a tiny fraction of the code in many ML systems is actually devoted to learning or prediction”. Then they put a proportion on it: “a mature system might end up being (at most) 5% machine learning code and (at least) 95% glue code”. Their central figure says the same thing as a picture — “Only a small fraction of real-world ML systems is composed of the ML code, as shown by the small black box in the middle. The required surrounding infrastructure is vast and complex.”

The shipped artifact measures the same way. A later study of deployed ML containers found that bloat “accounts for up to 80% of machine learning container sizes, increasing container provisioning times by up to 370% and exacerbating vulnerabilities by up to 99%”. Four of the cards below price what the estimator does. The fifth prices the other 95%.

The same predictive metric can hide very different live-system requirements.

For kernel methods the reference dependence is provable, not merely observed. There is a lower bound on how much of the training set a support vector machine must keep, and Ingo Steinwart proved it in 2003. The informal form of his first main result reads: “With probability tending to 1 when n → ∞ the fraction of support vectors is essentially greater than the Bayes risk R_P”. The operational consequence he draws from it is blunt. “When a noisy classification problem is learned we should expect that the number of support vectors increases linearly in the sample size.” For differentiable losses the bound is worse still. That is why he notes that L2-SVMs “can produce decision functions that are far from being sparse”.

A second pair of researchers states the same result with the constant attached. Léon Bottou and Chih-Jen Lin, writing on support vector machine solvers in 2007, record that the number of bounded support vectors scales at least linearly with the number of examples. Then, under the heading “Sparsity”: “When the hyperparameter C follows the right scaling laws, Steinwart (2004) has shown that the total number of support vectors is asymptotically equivalent to 2Bn. Noisy problems do not lead to very sparse SVMs.” B is the best error achievable by a linear decision boundary in the chosen feature space. Put a problem with 10% irreducible error into 2Bn and the fitted machine keeps roughly one training example in five. A kernel machine on noisy data does not compress its training set. It keeps a fixed share of it, and pays for that share on every request.

The matrix-based node has a ceiling of its own, and it is low. Rasmussen and Williams, in the 2006 textbook on Gaussian processes, give the cost of exact GP regression as “the computational complexity is n3/6 for the Cholesky decomposition”, with n2/2 for the triangular solves. At 44,484 training cases they already find it “computationally expensive to make use of all” of them “due to the O(n3) scaling of the basic algorithm”. Where that leaves ordinary practice is written into a 2019 abstract: “However, computational constraints with standard inference procedures have limited exact GPs to problems with fewer than about ten thousand training points, necessitating approximations for larger datasets.” Its authors break the ceiling only with conjugate gradients on 8 NVIDIA Tesla V100 GPUs, training on the HouseElectric dataset of n = 1,311,539 in less than 2 hours. Exact matrix operations limiting scale is not a phrase. It is about 10,000 points on the standard route, and eight V100s to go past it.

A million-column sparse matrix can be manageable when each row has a few nonzeros, while accidental centering can make it impossible, and dense arrays can exploit optimized linear algebra but pay for every entry.

A public benchmark makes both halves of that visible. The RCV1-v2 text collection, published in 2004, contains 804,414 documents represented over 47,236 stemmed-word features. The average document uses only 75.7 unique terms. That is about 0.16% of the columns nonzero, so a dense encoding of one row would be roughly 620 times larger than the sparse one. LIBSVM's dataset page lists rcv1.binary with the same 47,236 features, split 20,242 training and 677,399 testing instances, and news20.binary with 1,355,191 features. A million logical columns is not the problem. The 75.7 is what makes the matrix affordable.

Subtract a column mean from that representation and every stored zero becomes a stored number. The library will not do it. scikit-learn describes the with_mean parameter of StandardScaler in these words: “If True, center the data before scaling. This does not work (and will raise an exception) when attempted on sparse matrices, because centering them entails building a dense matrix which in common use cases is likely to be too large to fit in memory.” The exception is not a limitation of the tool. It is the tool refusing to build the 620-times-larger object on your behalf.

Measure actual matrix density, data type, copies, and solver compatibility rather than reasoning from logical column count alone.

Algorithms with partial-fit or sufficient-statistic updates can process streams without full retraining, but they still need a schedule, ordering policy, drift response, and rollback plan.

Updating on recent labels can amplify feedback loops or silently forget older but still relevant populations.

Performance testing should use realistic serialization, hardware, concurrency, and input shapes.

An industry benchmark already encodes step 1 and step 3, with the percentiles written down. MLPerf Inference was built by more than 30 organisations and 200 practitioners, and it refuses to score inference as a mean. It defines four scenarios: single-stream, multistream, server and offline. The single-stream metric is the query stream's 90th-percentile latency. The server scenario sets a benchmark-specific latency bound of 15 to 250 milliseconds, then rules on the tail: “No more than 1% of queries may exceed the latency bound for the vision tasks and no more than 3% may do so for translation.”

This is not a proposal that went nowhere. The first call for submissions, in October 2019, “garnered more than 600 reproducible inference-performance measurements from 14 organizations, representing over 30 systems”. MLCommons' current published rules still score the Server scenario at the 99% tail latency percentile, and Single-stream at a “90%-ile early-stopping latency estimate”. A service target written as a mean over a warm loop is not a weaker version of this. It is a different measurement, and the six steps below exist to close that gap.

Reducing tree count, pruning, quantizing coefficients, approximating kernels, or shrinking indexes may improve cost, but they can alter rare-case behavior, calibration, and explanation stability even when average metrics barely move.

Treat compression as a model change. It needs its own validation and version.

The paper that named the technique treats it as one too. Bucilă, Caruana and Niculescu-Mizil presented model compression in 2006, aimed at ensembles of “hundreds or thousands of base-level classifiers”, whose storage and run time “prohibits their use in applications where test sets are large (e.g. Google), where storage space is at a premium (e.g. PDAs), and where computational power is limited (e.g. hearing aids)”. The method trains a neural network to mimic the ensemble on data the ensemble itself has labelled, manufacturing synthetic cases with a procedure the authors call MUNGE where unlabelled data is scarce. Their introduction closes with the result: “Using MUNGE, we are able to train neural nets that are a thousand times smaller and faster than ensemble selection ensembles, but which have nearly the same performance as the far more complex ensembles.”

Nearly is the operative word, and the gap it hides has since been counted. Geoffrey Hinton and colleagues published the distillation paper in March 2015, credited that 2006 work with the idea, and reported the residual disagreement. On MNIST a large regularised net made 67 test errors, an unregularised small net 146, and the same small net distilled from the large one 74. On a Google acoustic model of about 85M parameters trained on ~2000 hours of speech, the baseline scored 58.9% frame accuracy and 10.9% WER, a 10-model ensemble 61.1% and 10.7%, and the distilled single model 60.8% and 10.7%. Distillation recovered most of 146 to 74. It did not reach 67, and 61.1% is not 60.8%. What ships is a different function that agrees with the old one on most inputs. Which is exactly why it needs its own version and its own evaluation.

A one-point metric gain may not justify tenfold latency, difficult deletion, or fragile dependencies; conversely, an expensive model may be worthwhile when it prevents high-cost errors or enables calibrated uncertainty.

Difficult deletion is not a hypothetical clause in that list. In January 2021 the FTC settled with Everalbum, Inc., and the proposed consent order set out what had to go: “Part III of the proposed order requires Respondent to delete (A) photos and videos of Ever app Users who requested deactivation of their accounts, (B) face recognition data that it created without obtaining Users’ affirmative express consent, and (C) models and algorithms it developed in whole or in part using images from Users’ photos.” The FTC's own press release states clause (C) in one line: the company had to delete “any facial recognition models or algorithms developed with Ever users' photos or videos”.

The order did not stop at the rows. It reached the trained artifact, because of how the training data had been obtained. A model family whose state is a compressed parameter set and one whose state is the training examples themselves are not equally easy to unwind under that kind of order. That difference belongs in the selection decision, not in a later incident.

Make trade-offs explicit in a decision memo rather than hiding them behind one score.