Algorithmic improvement

1 What is held fixed

• Q1: for a fixed task at a fixed performance level, how much cheaper has it become?
• Q2: for a fixed budget, how much better is the result?
• Q3: which tasks went from infeasible to feasible?
• Only Q1 has a clean operationalization. The literature measures Q1 and then argues about whether the answer transfers to Q2 and Q3.
• Q3 is probably where most of the value lies, and a cost ratio cannot measure it. Either the old method never reaches the target, so its cost is infinite, or the comparison is made at a level where both methods fail.
• “Fixed task” is the ambiguous term. It has five readings, from strictest to loosest.

The five levels in Gaussian-process regression.

• L0: inv(X) @ B against a Cholesky solve that never forms the inverse. Same answer to machine precision, about \(3\times\) fewer operations, much better conditioning. The asymptotic complexity is unchanged, so (Sherry and Thompson 2021) count this as no improvement.
• L1: Cholesky against a randomized sketch (Halko, Martinsson, and Tropp 2011). The answer is now \(\epsilon\)-approximate with a probabilistic guarantee. (Sherry and Thompson 2021) exclude approximate algorithms from their survey.
• L2: exact GP against an inducing-point GP. A different estimator that we hope has about the same predictive risk.
• L2 or L3: GP against a neural network that predicts as well at cost linear rather than cubic in \(n\). The linear-algebra problem is gone. This is L2 if we could hold true predictive risk fixed, and L3 in practice, because what gets checked is a benchmark score.

Consequences.

• Each move to a looser level yields a one-off speedup that comes from the loosening itself, not from any new algorithm. It is a step, not a rate. A trend fitted across such a step overstates the rate.
• Statistical and ML tasks have the most room to loosen, because the answer never needs to be more accurate than the noise in the data. Part of what gets counted as algorithmic progress is discovering how much accuracy can be discarded.
• (Thompson et al. 2022)’s \(\Omega(P^4)\) bound is the same statistical fact used as a floor. The \(1/\sqrt{n}\) rate says halving the error needs \(4\times\) the data, and an overparameterized model’s training compute grows as \(n^2\), so \(16\times\) the compute.
• A benchmark declares two different outputs to be the same answer when they score the same. L3 measurement needs that declaration; without it, two different models have no common target.
• The declaration can be wrong. Shortcut learning is the standing example: a model scores well without doing the task (Geirhos et al. 2020).
• L2 versus L3 is the adaptive-overfitting problem. A field that reuses one test set raises benchmark scores faster than it improves true accuracy.
• Which loosenings pay off depends on the hardware. Randomized linear algebra wins partly because it replaces a sequential factorization with large dense matrix products, which GPUs run well. (Hooker 2020)’s hardware lottery applies to approximations, not only to architectures.
• Loosened far enough, “same task” admits methods so different that one of them cannot reach the target at any budget. The Q1 ratio is then infinite, and the question was a Q3 question all along. This usually goes unremarked.

2 Changing the question

• The largest wins come from changing the problem while keeping its purpose: a different output, a different success criterion, or a different set of instances.
• A ratio can still be computed, because the substitute problem has its own cost curve.
• That ratio no longer measures “faster on the same problem”, because “same problem” has been relaxed to “same purpose”.

Two directions of substitution.

• Output side: weaken what must be produced. These are the strictness levels above.
• Input side: shrink the set of instances that must be handled, from the worst case toward the instances that actually arise.

The input side.

• (Sherry and Thompson 2021) use worst-case complexity because “it does not require assumptions about the distribution of inputs”. The price is that every gain which depends on the instances that arise being easier than the worst case is invisible to them.
• SAT is NP-complete, and industrial instances with millions of variables solve in seconds. The success of conflict-driven clause learning is a fact about which instances arise, not about the complexity class.
• MILP likewise: (Koch et al. 2022) measure \(50\times\) on the instances both generations of solver can finish, and 149 of the 240 MIPLIB 2017 instances can only be finished by the new ones.
• A speedup on a curated benchmark set is therefore partly a measurement of how the curators sampled.
• This axis has its own literature, mostly disconnected from the progress literature: (Rice 1976)’s algorithm selection problem, and instance space analysis (Smith-Miles and Muñoz 2023), which projects a benchmark suite into a feature space and maps which algorithm wins where.
• In those terms, “algorithm \(j\) is \(k\times\) faster than \(i\)” holds on some region of instance space, and a progress rate is an average over a distribution on that space that nobody states.

3 The reduced form nearly everyone uses

A1, factor-augmenting algorithms.

\[C_{\text{eff}}(t) = A(t)\, C_{\text{phys}}(t)\]

• \(C_{\text{phys}}\) is FLOP actually executed, \(A\) is algorithmic efficiency (dimensionless, normalized to 1 at a reference year), \(C_{\text{eff}}\) is effective compute.
• Software acts as a pure multiplier on physical compute, so performance depends on the pair only through the product.

A1 lumps algorithmic work together with systems efficiency. The cost of reaching a fixed target \(q\) involves three factors, not two.

\[C(q,t) \approx \frac{W(q,t)}{P_{\text{HW}}(t)\; U_{\text{sys}}(t)}\]

• \(W\) is algorithmic work: the nominal FLOP, tokens or steps needed to reach \(q\). \(1/A\) measures this.
• \(P_{\text{HW}}\) is raw hardware capability per dollar or joule. \(U_{\text{sys}}\) is the fraction of that capability we achieve (kernels, compiler, collectives, data loading, batching, precision).
• Nearly every published “algorithmic efficiency” number focuses on \(W\) alone. Nearly every claim of “we made it \(3\times\) faster” refers to \(U_{\text{sys}}\) on one stack.
• \(W\) carries across hardware generations; \(U_{\text{sys}}\) does not.

A2, exponential software.

\[A(t) = e^{g_A t}\]

A3, power-law returns, with \(E\) the irreducible loss and \(\alpha\) the scaling exponent.

\[L(C_{\text{eff}}) = E + \kappa\, C_{\text{eff}}^{-\alpha}\]

Consequences.

• Reducible loss falls at rate \(\alpha (g_A + g_C)\), for \(g_C = \mathrm{d}\log C_{\text{phys}}/\mathrm{d}t\).
• Hardware and algorithms are then perfect substitutes in log space. That is what makes “what share of progress” a well-posed question, and the algorithmic share is \(g_A / (g_A + g_C)\).
• A1 carries the whole argument. Every entry under “why the decomposition is not clean” is a case where A1 fails.

The same identity, split to show where money enters (Hernandez and Brown 2020).

\[C_{\text{eff}} = \underbrace{A}_{\text{algorithms}} \times \underbrace{(\mathrm{FLOP}/\$)}_{\text{hardware}} \times \underbrace{\$_{\text{spend}}}_{\text{investment}}\]

• Growth rates add: \(g(C_{\text{eff}}) = g(A) + g(\mathrm{FLOP}/\$) + g(\$)\).
• Their 2012–2018 arithmetic: \(7.5 \times 10^6 = 37{,}500 \times 8 \times 25\), for spending, parallelization, Moore’s law, and algorithms.
• Davidson’s compute-centric takeoff model is built on this identity with all three terms endogenous.

4 Measures that fix the output

Strictness L0. A speedup only reduces the operation count.

5 Measures that fix a benchmark number

Strictness L3. A speedup may change anything except the benchmark score, which is why these measures report the largest numbers. They inherit every problem with the benchmark itself; see ML benchmarks.

• A fixed-threshold measure needs headroom above the threshold and a benchmark still being worked on. A saturated benchmark can no longer be used this way. (Ott et al. 2022) map benchmark creation and saturation across the field.
• The measured rate is therefore partly a property of the benchmark’s life cycle, not of the algorithms.

6 Measures that fix the deployed workload

These measures bundle every layer together on purpose. That is what a buyer needs and the opposite of what a decomposition needs.

7 Measured rates, hardware and money

• The hardware baseline is contested and the choice changes the answer. Transistor density, SPECint (used by (Sherry and Thompson 2021) and (Leiserson et al. 2020)), FLOP/s, FLOP/$ and FLOP/joule diverge once Dennard scaling ends around 2005.
• Specialization does much of the recent work and is not Moore’s law in any sense. Accelerators are co-designed with the algorithms, which is (Hooker 2020)’s point.
• The last two rows are the \(\$_{\text{spend}}\) term rather than hardware, and they are the largest term in the identity.

8 Measured rates, algorithms

• (Grace 2013) across six domains: algorithmic gains are 50–100% as large as hardware gains, incremental and smooth on the scale of years; the fusion-simulation series shows roughly equal shares.
• Frontier-ML doubling times cluster at 4–17 months and classical-CS ones at 1–6 years. The gap reflects, at least in part, how much money is chasing each.
• Every ML row is measured at L3 and every classical row at L0, so the two halves of the table are not comparable. The ML numbers are larger partly because the measure permits more to change.

9 Why the decomposition is not clean

Each entry is a case where A1 fails, with a measurement behind it.

• Problem-size dependence. Whether algorithms beat hardware is a function of \(n\), crossing over near \(n \approx 10^{12}\) for the median family, so the question has no scalar answer (Sherry and Thompson 2021).
• Scale dependence, the same effect in ML. LSTM-to-transformer is a change of exponent, not a multiplier: \(6\times\) at \(10^{15}\) FLOP, over \(100\times\) at \(10^{23}\) (Gundlach et al. 2025).
• Reference dependence. The same sequence of frontier models shows 63%/year CEG growth against a compute-optimal LSTM baseline and 0%/year against a dense transformer. At \(10^{18}\) FLOP a decade of algorithmic progress is worth \(\approx 20\times\), below Moore’s \(\approx 32\times\); at frontier scale the same decade is worth \(\approx 6{,}930\times\). Small and large actors are not in the same regime (Gundlach et al. 2025).
• Compute-dependent advances. Innovations whose benefit appears only at scale may account for ~99% of cumulative CEG, making algorithms and compute complements rather than substitutes in the regime that matters (Sanderson et al. 2025).
• The hardware lottery. Which algorithms look good depends on which hardware exists, so \(A\) and FLOP/$ are not independent factors (Hooker 2020).
• Substitution is unmeasured. Per “changing the question” above, the first demonstration of a capability gives an unbounded ratio (Hernandez and Brown 2020).
• Component gains do not multiply, in either direction. Solver features reinforce each other (“the sum is more than its parts”); transformer innovations fail to compound (3.43 predicted, 1.33 measured).
• Selection and censoring. Benchmarks collect hard instances, easy instances get retired, the time limit is a free parameter that changes the answer, and Bixby’s MIP benchmark was built and analysed by the CEO of Gurobi.
• Adaptivity to the test set. A community that reuses one held-out set is running an adaptive estimation procedure, so some fraction of any L3 trend is overfitting to the instrument rather than progress. (Blum and Hardt 2015) give the mechanism and a leaderboard that resists it; (Arora and Zhang 2021) bound the damage.
• Some of it does not survive fair comparison. A decade of claimed metric-learning gains mostly disappears under matched tuning and evaluation (Musgrave, Belongie, and Lim 2020), and recent language-model reasoning gains shrink under controlled reproduction (Hochlehnert et al. 2025).
• How results are averaged. Normalized benchmark ratios can be summarized in ways that reverse the ranking (Fleming and Wallace 1986), and the three headline measures use three different estimators: shifted geometric mean (Koch et al. 2022), median over families (Sherry and Thompson 2021), frontier minimum (Hernandez and Brown 2020). Systems measurement has its own biases, where link order or environment size moves the result (Mytkowicz et al. 2009).
• Training-run cost is not development cost. Architecture search inflates development compute relative to the final run, and hyperparameter robustness makes training cheaper in ways FLOP-counting misses (Hernandez and Brown 2020).

10 The growth-theory layer

To derive \(g_A\) instead of fitting it, from (Bloom et al. 2020).

\[\frac{\dot A_t}{A_t} = \alpha S_t, \qquad \text{research productivity} := \frac{\dot A_t / A_t}{S_t}\]

Semi-endogenous version with dynamic diminishing returns.

\[\frac{\dot A_t}{A_t} = \alpha A_t^{-\beta} S_t \quad \Longrightarrow \quad g_A = \frac{g_S}{\beta}\]

• \(S_t\) represents effective researchers, or R&D spend deflated by the wage; \(\beta\) is the ideas-get-harder elasticity.
• Constant exponential progress requires exponentially growing research effort.
• US aggregate research productivity falls 5.3%/year, a 13-year half-life. Moore’s law needs \(18\times\) more researchers than in the early 1970s for the same 2-year doubling.
• Davidson’s fit provides the hardware analogue: each doubling of cumulative hardware R&D spend buys \(\approx 5\) doublings of FLOP/$.
• (Hernandez and Brown 2020) note the confound the other way: AI investment rose \(\approx 5\times\) over 2012–2018, so observed \(g_A\) is partly rising \(S\) rather than constant productivity.

11 Adjacent axes

• Data. (Erdil and Besiroglu 2023) split this out and find data-augmenting progress small and not significant. Training data has doubled every 9–10 months since 2010.
• Inference-time compute. A third input with its own scaling law and efficiency trend, unmeasured in every decomposition above.
• Schlep. Scale, schlep, and systems argues scaffolding, tools, prompting and fine-tuning are a distinct fast-moving factor; (Davidson et al. 2023) quantify this as CEG.
• Diffusion. (Pilz, Heim, and Brown 2024) separate the access effect (a given performance costs less) from the performance effect (a given spend buys more). In their notation performance is \(p = f_c(i)\) for investment \(i\), with \(f_c = f_a \circ f_h\): \(f_h\) turns investment into compute and \(f_a\) turns compute into performance.
• Performance ceilings damp the performance effect and let laggards catch up. MNIST has been above 99% since the early 2000s.
• Numerical precision, half hardware and half algorithm. FP16 and BF16 each took 3–4 years to become the default; FP8 is mid-adoption.

12 Sub-areas to follow up

• Numerical linear algebra is the best-documented long run: FFT \(O(N^2) \to O(N \log N)\), fast multipole \(O(N^2) \to O(N)\), Krylov against direct \(O(N^3)\), then the randomized generation (Halko, Martinsson, and Tropp 2011). One field moving from L0 to L1 over fifty years.
• (Dongarra and Sullivan 2000)’s top ten sort into three kinds of gain: asymptotic wins (FFT, fast multipole, quicksort), tractability wins (simplex, Krylov, Metropolis), and one piece of pure software infrastructure (the Fortran optimizing compiler).
• Monte Carlo variance reduction, where the saving is counted in samples rather than FLOP (Luengo et al. 2020).
• Factoring, where the algorithmic story is subexponential against exponential and the hardware share is unclear (Grace 2013).
• “Is there secret sauce in LLM development?” (Mertens, Fischl-Lanzoni, and Thompson 2026)] Shapley-decomposes \(R^2\) into scale, shared algorithmic progress, and firm-specific factors. The natural next question after (Ho et al. 2024).

13 Open threads

• The defensible claim is probably that at frontier scale over the last decade the two are within a factor of a few of each other, compute slightly ahead, while at small scale algorithms lose badly. Both halves rest on the scale-dependence result.
• Whether the cost-ratio framing survives Q3. The interesting events are complexity-class transitions, capability firsts and substitutions, and the ratio measures none of them.
• Feedback loops: compute buys the experiments that find the compute-dependent algorithms, and the algorithms justify the next capex round.
• Whether there is an algorithmic Moore’s law, meaning a self-sustaining trend, or only a line fitted through a period when the findings happened to be easy.
• Whether the one-off gain from loosening strictness can be quantified. That would say where measured progress has to slow.

14 Incoming

• Scale, schlep, and systems
• Neural scaling laws
• ML benchmarks

15 References