Algorithmic improvement

1 The decomposition

Write \(T\) for the time (or dollars) needed to reach target \(q\), \(W_a(q)\) for the operations algorithm \(a\) needs to reach it, and \(S\) for the operations per second (or per dollar) our hardware delivers. Then \(T = W_a(q)/S\).

Moving from an old setup \((a_0, S_0, q_0)\) to a new one \((a_1, S_1, q_1)\), the speedup telescopes:

\[ \frac{T_0}{T_1} = \underbrace{\frac{S_1}{S_0}}_{\text{hardware}} \times \underbrace{\frac{W_{a_0}(q_0)}{W_{a_1}(q_0)}}_{\text{algorithm}} \times \underbrace{\frac{W_{a_1}(q_0)}{W_{a_1}(q_1)}}_{\text{loosening}} \]

This is an identity, so it always holds. In logs, the three terms add, and “what share of the progress is algorithmic?” looks like it has an answer. It only has one if the identity is also a production function, in which the factors do not depend on one another. Even as accounting, it has gaps. One is that the split depends on the order in which we apply the changes. Another is that some of the factors can be infinite. If the old method cannot reach the new target at any budget, or the new method only makes sense for a target the old problem never posed, the ratio is infinite or undefined. Infeasible-to-feasible transitions are arguably where most of the value lies, and a cost ratio cannot see them.

2 Example

Gaussian-process regression makes a handy worked example. The task is posterior predictive inference. With \(n\) training points, kernel matrix \(K\) and noise \(\sigma^2\), the predictive mean at a test point is \(k_*^\top (K + \sigma^2 I)^{-1} y\) and the predictive variance is \(k_{**} - k_*^\top (K + \sigma^2 I)^{-1} k_*\); fitting the hyperparameters also needs \(\log\det(K + \sigma^2 I)\). The cost of a prediction is dominated by an \(n \times n\) linear solve with respect to a symmetric matrix.

• Exact, naive: transcribe the equations, form \((K + \sigma^2 I)^{-1}\) explicitly and multiply. About \(2n^3\) operations and poor conditioning, i.e., numerically unstable. This is the cost of the base problem as written.
• Exact, competent: Cholesky \(LL^\top = K + \sigma^2 I\) at \(n^3/3\) operations, triangular solves at \(n^2\) per right-hand side, \(\log\det\) read off the diagonal of \(L\) for free. Same answer in principle but due to floating point shenanigans, much faster and more stable. Still \(O(n^3)\) but less awful. A pure algorithmic gain: same answer, fewer operations.
• Same answer to tolerance \(\epsilon\): the same posterior but we allow some error. Conjugate gradients for the solve and Lanczos methods for \(\log\det\) cost \(O(n^2)\) per iteration and stop at \(\epsilon\); randomized sketches (Halko, Martinsson, and Tropp 2011) give an \(\epsilon\)-approximate answer with a probabilistic guarantee. Admits more data at a known loss of precision, so now we have a tradeoff.
• Same predictive risk, different estimator: a variational posterior. Inducing-point methods summarize the data by \(m \ll n\) pseudo-inputs at \(O(nm^2)\) cost. The output is no longer the GP posterior per se; it is a different distribution we hope has about the same predictive risk, which in practice we assess by scoring on a held-out set.
• Same held-out score, different model class: a neural network that scores as well on the held-out set. There is no \(n \times n\) system to solve any more, so the cost of inference is \(O(n)\). There is also no posterior per se: the network returns a point prediction, or an uncertainty estimate of some other kind.

Only the second step leaves the target alone. Each later step is a looser contract about what counts as success: the output to tolerance, then the risk of the estimator, then a benchmark score, and at the far end, the task the benchmark was meant to stand in for.

3 As a production function

The multiplicative form treats hardware and algorithms as inputs to a production function in which only their product matters, the “effective compute” \(A \cdot C\) of the scaling-law literature. Its isoquants are hyperbolae, so it is Cobb-Douglas between the two, with elasticity of substitution \(\sigma = 1\) and no cross terms; in translog terms it is the first-order expansion with every \(b_{ij} = 0\). The hardware lottery (Hooker 2020) says the cross terms are not zero.

A cost function makes the structure easier to see. Hardware does not have a speed; it has a price for each kind of operation: FLOPs at each precision, bytes moved from memory, synchronizations, mispredicted branches. Write \(w(h)\) for that price vector on hardware \(h\). An algorithm \(a\) that reaches target \(q\) uses a bundle \(x(a, q)\) of those operations in fixed proportions, like a Leontief technique in activity analysis. The cost of reaching \(q\) is then

\[ C(h, q) = \min_{a \in \mathcal{A}(q)} w(h) \cdot x(a, q), \]

where \(\mathcal{A}(q)\) is the set of algorithms we know that reach \(q\). Algorithmic progress adds techniques to \(\mathcal{A}\); hardware progress changes \(w\).

Uniform hardware gains are exactly multiplicative. A cost function is homogeneous of degree one in prices, \(C(\lambda w, q) = \lambda C(w, q)\), whatever the algorithm. If every operation got cheaper by the same factor, the hardware factor would be well defined and independent of the algorithm. Clock-speed scaling up to about 2005 was the nearest thing we had, and even then memory latency fell behind.

Small uneven gains are multiplicative at the margin. By the envelope theorem, the first-order change in cost from a small change in prices is \(dC = x^* \cdot dw\), evaluated at the algorithm we already use; switching algorithms gains only at second order. So locally the multiplicative form is fine, and that is the sense in which hardware and algorithms are separable.

Large uneven gains are not. When relative prices tilt far enough, the cheapest algorithm changes. That is the hardware lottery restated as a change in relative prices. Since about 2005 tilting has been the norm: GPU FLOP/s double every 2.3 years against memory bandwidth every 4.1 (Hobbhahn, Heim, and Aydos 2023), and SIMD units and GPUs made regular, dense, branch-free operations far cheaper than irregular ones. FlashAttention (Dao et al. 2022) is a tidy example. It computes exact attention with more FLOPs than the standard implementation, and runs faster because it moves less data between memory levels. Counted in FLOPs it is negative algorithmic progress, and it pays only because of the price vector. The gain from switching algorithms after a large price change belongs to neither factor; it is the interaction term, and the order in which we price the factors decides which one gets it. Fichte, Hecher, and Szeider (2023) measured it directly: SAT solvers from 2003 built on clause learning solve 1.7 to 2.8 times as many instances on 2019 hardware as on 1999 hardware, while the older solvers barely gain.

There is a possible rescue at the aggregate level. Houthakker (1955) showed that aggregating many fixed-coefficient activities, with capacity Pareto-distributed over their input coefficients, gives a Cobb-Douglas industry production function, and Jones (2005) turned this into a theory of ideas: if techniques are discovered as draws from a Pareto distribution, the envelope over all discovered techniques, the global production function, is Cobb-Douglas, even though each technique has fixed proportions and the short-run production function substitutes poorly. Mapped onto this problem, the global cost function would be Cobb-Douglas in operation prices. An uneven hardware gain would then enter as a cost-share-weighted product of the per-operation price falls, and new algorithms would shift the constant in front. The multiplicative form would survive as a description of the frontier over many algorithm–hardware pairings, with kinks, even though no single pairing behaves that way. That would reconcile smooth trend lines with lumpy individual cases. Sherry and Thompson (2021)’s bimodal gains are at least heavy-tailed; whether they are Pareto enough for this to hold, I do not know.

The target \(q\) fits the frame worse, because it is not an input.

• Loosening changes the menu. \(\mathcal{A}(q)\) depends on \(q\): conjugate gradients is only an option once we accept a tolerance, and the neural network only once a held-out score is the criterion. The main effect of loosening is to enlarge the feasible set of techniques, and the “algorithm” factor is then measured over techniques that were not available before.
• Loosening interacts with hardware. Lower precision only pays where low-precision operations are cheap, and randomized linear algebra wins partly because it turns a sequential factorization into large dense matrix products. So there are three-way interactions as well.
• Loosening may not be a cost reduction at all. The output has several dimensions (accuracy, guarantees, calibrated uncertainty, which instances are covered), so we are on a multi-output transformation frontier rather than a production function. Whether a cheaper output counts as the same good depends on what the user wanted, that is, on the task. For someone who wants a held-out score, the neural network and the GP are the same good; for someone who needs a calibrated posterior variance, they are not. This is the quality-adjustment problem from price indices, as in the computing price series of Nordhaus (2007), and it means the loosening factor is set by demand as much as by production technology.

4 Measured progress

A measurement of algorithmic progress has to hold some target fixed, and it can only hold fixed a target it can check: the exact output, a tolerance, a benchmark score. Call that the measured target \(b\). What a user wants done, the task \(q^*\), is something else: a PDE solution accurate to the discretization error, say, or a classifier that works on the photos it will meet in deployment. A benchmark stands in for a task that is hard to measure directly, which is the construct-validity problem of Raji et al. (2021).

The measurement reports the algorithm factor at \(b\). Multiplying and dividing by each method’s cost at the task splits that into two factors:

\[ \underbrace{\frac{W_{a_0}(b)}{W_{a_1}(b)}}_{\text{measured}} = \underbrace{\frac{W_{a_0}(q^*)}{W_{a_1}(q^*)}}_{\text{progress on the task}} \times \underbrace{\frac{W_{a_1}(q^*) / W_{a_1}(b)}{W_{a_0}(q^*) / W_{a_0}(b)}}_{\text{mismatch}} \]

For each method, \(W_a(q^*)/W_a(b)\) is how much more it would cost that method to do the task than to reach the measured target. The second factor compares that gap for the new method against the old one. It is 1 when the measured target is the task, or when both methods find the two equally far apart, and in those cases the measurement is progress on the task. The table sorts the published measurements by their measured target.

The two halves of the table miss the task in different ways.

The classical rows hold a target stricter than the task. They fix the exact output, while most tasks only need it to some tolerance. Then \(W_a(q^*)/W_a(b) \le 1\), and it is smallest for the methods that can exploit the tolerance, so when the new method is one of those, the mismatch factor is below 1 and the measurement undercounts progress on the task. Sherry and Thompson (2021)’s exclusion of approximate algorithms is the extreme case: methods that only pay off at a tolerance are left out altogether.

The best-known chart of algorithms beating Moore’s law shows what changes when we measure against the task instead. Rüde et al. (2018) plot the cost of solving the Poisson equation on an \(n \times n \times n\) grid, from banded Gaussian elimination in 1947 at \(O(n^7)\) operations to Brandt’s multigrid in 1974 at \(O(n^3)\). At \(n = 64\) the ratio is \(64^4 = 2^{24}\), which they match to the 24 doublings of Moore’s law over the same period. Gaussian elimination solves the discretized system exactly, while multigrid’s \(O(n^3)\) is the cost of an iterative solve stopped once its error is down to the size of the discretization error. Against the exact solve, part of that speedup is loosening. Against the task, which never needed more than the discretization accuracy, all of it is algorithm, because Gaussian elimination has no way to stop early: \(W_{\text{GE}}(q^*) = W_{\text{GE}}(\text{exact})\). That is the order dependence of the Cholesky example, settled by taking the task as the reference target.

The ML rows hold a target that differs from the task in both directions. A benchmark score can be reached without doing the task, wherever the score fails to check something the task needs: robustness, calibration, the photos the model will meet in deployment. It can also demand things the task does not need, such as telling apart the hundred-odd dog breeds in ImageNet’s label set, or agreeing with labels that are themselves wrong; at least 6% of the ImageNet validation labels are (Northcutt, Athalye, and Mueller 2021). So each method’s gap \(W_a(q^*)/W_a(b)\) can sit on either side of 1, and nothing in the setup fixes the sign of the mismatch factor.

Selection fixes it, roughly. When a benchmark is new, nobody has optimized against it, so the first method to reach a given score has no special relationship to the benchmark’s quirks. Later methods are selected for reaching the score cheaply, that is, for a small \(W_{a_1}(b)\), and nobody selects them for a small \(W_{a_1}(q^*)\). Whichever way the benchmark differs from the task, that selection favours methods specialized to the benchmark: good at what it checks, whether or not the task needs it, and indifferent to what it does not check. So the mismatch factor drifts above 1, and the measurement overcounts. This is Goodhart’s law written into the identity: the benchmark measured the task well until it became the target. Shortcut learning is the limit, where a model reaches the score and cannot do the task at any budget, so \(W_{a_1}(q^*)\) is infinite (Geirhos et al. 2020).

There are two checks I know of on how large the overcount is, and they point in different directions. Recht et al. (2019) rebuilt the ImageNet test set by following the original collection process, and found that models lost 11–14 points of accuracy on it, but that gains on the original test set came with larger gains on the new one. That rules out one route to overcounting, reuse of the same test set, at least on ImageNet up to 2019. It cannot see the other routes, since a fresh test set built the same way shares the original’s quirks. Beyer et al. (2020) relabelled the ImageNet validation set with a more careful annotation procedure, and found the gains of recent classifiers substantially smaller on the new labels than on the original ones. That is the overcount from fitting the benchmark’s quirks, measured directly.

Three more details from these measurements feed into the inferences. The MILP figure covers only the instances both generations of solver could finish; 149 of the 240 MIPLIB 2017 instances were out of reach of every 2001 solver within 24 hours. Sherry and Thompson (2021) find algorithmic gains bimodal: just under half of algorithm families never improve, and a few jump by orders of magnitude, so the median family overtakes hardware only around \(n \approx 10^{12}\). And Gundlach et al. (2025) find that the LSTM-to-transformer gain is a change of scaling exponent rather than a constant multiplier: about \(6\times\) at \(10^{15}\) FLOP, over \(100\times\) at \(10^{23}\).

5 Minimal inferences

Where the target is held exact, algorithms and hardware are roughly even. Three different designs agree on this: solver binaries swapped across machines (Koch et al. 2022), the time-leap SAT experiment (Fichte, Hecher, and Szeider 2023), and Grace (2013)’s survey across six domains, which puts algorithmic gains at 50–100% of hardware gains. The algorithmic gains are lumpier, which matters for forecasting even when the averages match. An exact target is stricter than most tasks, so this undercounts algorithmic progress on the task by however much the approximate methods are worth. In the area I know best, Gaussian processes, approximate methods are what people mostly use; I do not know how big the undercount is elsewhere.

ML’s faster algorithmic rates are measured against a different target. An 8-month doubling against a 2-year hardware doubling makes algorithms look like the bigger term, but part of it may be mismatch between benchmark and task, which Goodhart’s law predicts will grow the longer a field optimizes against one benchmark. Since loosening is a one-off per task, I would not extrapolate those rates as if they were hardware-like trends. If this is right, a new task should show a burst of fast early “algorithmic” progress while people discover what can be thrown away, then slow down. That is at least consistent with how benchmarks tend to saturate, though I have not checked it.

Some hardware progress is loosening too. Epoch fits accelerator FLOP/s within one number format and reports the move to lower precision separately, as a one-off of roughly \(8\times\) for FP16 tensor cores and \(13\times\) for INT8 (Hobbhahn, Heim, and Aydos 2023). At a 2.3-year doubling time, those single steps are worth about 7 and 8.5 years of FP32 progress. Lower precision loosens the target, and gets booked as hardware.

At the frontier, the split is not well defined. This is the envelope problem, in the quantity of compute rather than the price of operations. If the transformer’s advantage grows with compute, then the “algorithmic” gain at frontier scale grew because frontier compute grew, and listing it beside compute as a separate factor counts that growth twice. At a fixed small scale the comparison is cleaner, and there Gundlach et al. (2025) put a decade of algorithms at around \(20\times\) at \(10^{18}\) FLOP, a bit less than the hardware gain over the same decade.

The most valuable progress is invisible to all of these. Infeasible-to-feasible transitions give infinite ratios, and loosening is the usual way they happen. So any account of “how much faster we got” built from cost ratios underweights loosening, and that is the factor I would most like a handle on.

🚧TODO🚧 Can we estimate in advance how far a task’s target can be loosened? For statistical tasks there is a floor: Thompson et al. (2022) argue compute must grow at least as performance to the fourth power, and measure something closer to the twelfth on ImageNet. The fourth power comes from two square laws: at the usual \(1/\sqrt{n}\) statistical rate, halving the error needs \(4\times\) the data, and training an overparameterized model costs about \(n^2\) in the data size, so \(16\times\) the compute. That gap looks like a candidate measure of how much loosening is left.

6 Incoming

• Neural scaling laws
• ML benchmarks
• Grammar induction
• Bloom et al. (2020) on why constant exponential progress needs exponentially growing research effort.
• Sanderson et al. (2025) on compute-dependent advances, which make algorithms and compute complements rather than substitutes.
• Pilz, Heim, and Brown (2024) on separating the falling cost of a given capability from the rising capability per dollar.

7 References