Yash Sherry

Neil Thompson

September 1, 2021

Algorithms are one of the fundamental building blocks of computing. But current evidence about how fast algorithms improve is anecdotal, using small numbers of case studies to extrapolate. In this work, we gather data from 57 textbooks and more than 1,137 research papers to present the first systematic view of algorithm progress ever assembled. There is enormous variation. Around half of all algorithm families experience little or no improvement. At the other extreme, 13% experience transformative improvements, radically changing how and where they can be used. Overall, we find that, for moderate-sized problems, 30% to 45% of algorithmic families had improvements comparable or greater than those that users experienced from Moore's Law and other hardware advances

Paper Link

Cite this work

September 1, 2021

Yash Sherry, Neil Thompson (). How Fast do Algorithms Improve?. Published in Proceedings of the IEEE. Retrieved from https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9540991. Accessed .

Copied

@article{,
  title     = { How Fast do Algorithms Improve? },
  author    = { Yash Sherry, Neil Thompson },
  journal   = { Proceedings of the IEEE },
  year      = {  },
  url       = { https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9540991 }
}

Copied

Related Publications

Meek Models Shall Inherit the Earth

June 2025

Hans Gundlach, Jayson Lynch, Neil Thompson

The past decade has seen incredible scaling of AI systems by a few companies, leading to inequality in AI model performance. This paper argues that, contrary to prevailing intuition, the diminishing returns to compute scaling will lead to a convergence of AI model capabilities. In other words, meek models (those with limited computation budget) shall inherit the earth, approaching the performance level of the best models overall. We develop a model illustrating that under a fixed-distribution next-token objective, the marginal capability returns to raw compute shrink substantially. Given current scaling practices, we argue that these diminishing returns are strong enough that even companies that can scale their models exponentially faster than other organizations will eventually have little advantage in capabilities. As part of our argument, we give several reasons that proxies like training loss differences capture important capability measures using evidence from benchmark data and theoretical performance models. In addition, we analyze empirical data on the capability difference of AI models over time. Finally, in light of the increasing ability of meek models, we argue that AI strategy and policy require reexamination, and we outline the areas this shift will affect.

Introducing the Quantum Economic Advantage Online Calculator

August 2025

Frederick Mejia, Hans Gundlach, Jayson Lynch, Carl Dukatz, Andrew Lucas, Eleanor Crane, Prashant Shukla, Neil Thompson

We introduce an open-access web tool that estimates when quantum systems will outperform classical computers for specific algorithms on a cost‑equivalent basis. Built on the Choi–Moses–Thompson framework, it lets users vary assumptions about error correction, gate speeds, overheads, connectivity, hardware roadmaps, and classical baselines. We find that expected timing for advantage is robust for some algorithms (e.g., Shor's) but contingent for others (e.g., Grover's), depending on technical factors.

The Computational Limits of Deep Learning

July 2020

Neil C. Thompson, Kristjan Greenewald, Keeheon Lee, Gabriel F. Manso

Deep learning's recent history has been one of achievement: from triumphing over humans in the game of Go to world-leading performance in image classification, voice recognition, translation, and other tasks. But this progress has come with a voracious appetite for computing power. This article catalogs the extent of this dependency, showing that progress across a wide variety of applications is strongly reliant on increases in computing power. Extrapolating forward this reliance reveals that progress along current lines is rapidly becoming economically, technically, and environmentally unsustainable. Thus, continued progress in these applications will require dramatically more computationally-efficient methods, which will either have to come from changes to deep learning or from moving to other machine learning methods.

Quantum Deep Learning Still Needs a Quantum Leap

November 2025

Hans Gundlach, Hrvoje Kukina, Jayson Lynch, Neil Thompson

Quantum computing technology is advancing rapidly. Yet, even accounting for these trends, a quantum leap would be needed for quantum computers to meaningfully impact deep learning over the coming decade or two. We arrive at this conclusion based on a first-of-its-kind survey of quantum algorithms and how they match potential deep learning applications. This survey reveals three important areas where quantum computing could potentially accelerate deep learning, each of which faces a challenging roadblock to realizing its potential. First, quantum algorithms for matrix multiplication and other algorithms central to deep learning offer small theoretical improvements in the number of operations needed, but this advantage is overwhelmed on practical problem sizes by how slowly quantum computers do each operation. Second, some promising quantum algorithms depend on practical Quantum Random Access Memory (QRAM), which is underdeveloped. Finally, there are quantum algorithms that offer large theoretical advantages, but which are only applicable to special cases, limiting their practical benefits. In each of these areas, we support our arguments using quantitative forecasts of quantum advantage that build on the work by Choi et al. [2023] as well as new research on limitations and quantum hardware trends. Our analysis outlines the current scope of quantum deep learning and points to research directions that could lead to greater practical advances in the field.

How fast are algorithms reducing the demands on memory? A survey of progress in space complexity

November 2025

Hayden Rome, Jayson Lynch, Jeffery Li, Chirag Falor, Neil Thompson

Algorithm research focuses primarily on how many operations processors need to do (time complexity). But for many problems, both the runtime and energy used are dominated by memory accesses. In this paper, we present the first broad survey of how algorithmic progress has improved memory usage (space complexity). We analyze 118 of the most important algorithm problems in computer science, reviewing the 800+ algorithms used to solve them. Our results show that space complexity has become much more important in recent years as worries have arisen about memory access bottle-necking performance (the ``memory wall''). In 20% of cases we find that space complexity improvements for large problems (n=1 billion) outpaced improvements in DRAM access speed, suggesting that for these problems algorithmic progress played a larger role than hardware progress in minimizing memory access delays. Increasingly, we also see the emergence of algorithmic Pareto frontiers, where getting better asymptotic time complexity for a problem requires getting worse asymptotic space complexity, and vice-versa. This tension implies that programmers will increasingly need to consider multiple algorithmic options to understand which is best for their particular problem. To help theorists and practitioners alike consider these trade-offs, we have created a reference for them at this https URL.

The Price of Progress: Algorithmic Efficiency and the Falling Cost of AI Inference

November 2025

Hans Gundlach, Jayson Lynch, Matthias Mertens, Neil Thompson

Language models have seen enormous progress on advanced benchmarks in recent years, but much of this progress has only been possible by using more costly models. Benchmarks may therefore present a warped picture of progress in practical capabilities per dollar. To remedy this, we use data from Artificial Analysis and Epoch AI to form the largest dataset of current and historical prices to run benchmarks to date. We find that the price for a given level of benchmark performance has decreased remarkably fast, around to per year, for frontier models on knowledge, reasoning, math, and software engineering benchmarks. These reductions in the cost of AI inference are due to economic forces, hardware efficiency improvements, and algorithmic efficiency improvements. Isolating out open models to control for competition effects and dividing by hardware price declines, we estimate that algorithmic efficiency progress is around per year. Finally, we recommend that evaluators both publicize and take into account the price of benchmarking as an essential part of measuring the real-world impact of AI.