Zur Theorie der GesellschaftsspieleJohn von Neumann#
1928·Mathematische Annalen
Contribution
Proved the minimax theorem for two-person zero-sum games, showing that a mixed strategy equilibrium always exists.
Emile Borel had posed the two-person zero-sum problem a few years earlier and conjectured that no general solution existed. Von Neumann, then twenty-four, proved the opposite, showing that allowing randomized strategies always produces a value. The paper sat largely unread until he expanded it with Morgenstern sixteen years later.
1930s
Grundbegriffe der WahrscheinlichkeitsrechnungAndrey Kolmogorov#
1933·Springer
Contribution
Axiomatized probability on measure-theoretic foundations, giving a single framework in which all of probability and statistics could be stated.
Hilbert's sixth problem had asked for an axiomatic treatment of probability, and by the early 1930s the subject still rested on intuitions about frequency and symmetry. Kolmogorov's answer was that probability is a measure of total mass one, which imports the whole apparatus of Lebesgue integration at no cost. The monograph runs under seventy pages and settled the question.
On the Problem of the Most Efficient Tests of Statistical HypothesesJerzy Neyman and Egon Pearson#
1933·Philosophical Transactions of the Royal Society A
Contribution
Formulated hypothesis testing as a decision between two distributions and proved the lemma giving the most powerful test at any given size.
Fisher's significance tests asked whether data were surprising under a null hypothesis and said nothing about what else might be true. Neyman and Pearson argued that a test only becomes a decision once an alternative is named, and that the two ways of being wrong must be traded against each other explicitly. Fisher rejected the framing for the rest of his life.
Proved that any smooth manifold of dimension n can be embedded in Euclidean space of dimension 2n+1, establishing the foundational embedding theorem for differential topology.
Manifolds had been defined as subsets of Euclidean space, which leaves it unclear whether an abstractly specified manifold is the same kind of object. Whitney proved that any such manifold embeds in a Euclidean space of roughly twice its dimension, which settles the question. The paper also fixes the modern definition in terms of charts and transition maps.
On Computable Numbers, with an Application to the EntscheidungsproblemAlan Turing#
1936·Proceedings of the London Mathematical Society
Contribution
Defined a universal computing machine and proved that no algorithm decides whether an arbitrary program halts.
Hilbert had asked for a procedure that decides whether any given statement follows from a set of axioms. Turing answered by defining what a procedure is, in terms of a machine reading and writing symbols on a tape, and then showing no such machine can decide whether an arbitrary machine halts. Church had reached the same conclusion months earlier by a different route, but Turing's model was the one people found convincing.
1940s
A Mathematical Theory of CommunicationClaude Shannon#
1948·Bell System Technical Journal
Contribution
Defined entropy as the measure of information and proved the limits on lossless compression and on reliable transmission over a noisy channel.
Shannon had spent the war on cryptography at Bell Labs, where the question of how much a message reveals is the same question as how much it contains. The paper defines information as reduction in uncertainty, separates the source from the channel, and proves that a noisy channel has an exact capacity below which error can be made arbitrarily small. It appeared in two parts in the Bell System Technical Journal and created the field entire.
1950s
A Difficulty in the Concept of Social WelfareKenneth Arrow#
1950·Journal of Political Economy
Contribution
Proved that no ranked voting system over three or more alternatives can satisfy a small set of fairness axioms simultaneously.
Arrow was at RAND, where the question arose of whether a nation could be assigned a utility function so that game theory could treat it as a player. He tried to construct one from individual preferences and found that a short list of reasonable requirements admits no solution at all beyond dictatorship. The negative result became his dissertation and eventually the Nobel citation.
Proposed the imitation game as a test for machine intelligence and addressed nine categories of objections to the possibility of thinking machines.
Turing opens by declaring the question of whether machines can think too meaningless to discuss and replaces it with a game about whether an interrogator can tell which correspondent is human. Most of the paper is a systematic answer to nine objections he anticipated, including the theological one. It appeared in the philosophy journal Mind rather than a technical venue.
1950·Proceedings of the National Academy of Sciences
Contribution
Proved that every finite game has at least one mixed-strategy equilibrium, extending the minimax result to n players.
Von Neumann's minimax theorem covered only two players with strictly opposed interests, which excludes nearly every situation of interest. Nash's note, barely a page in the Proceedings of the National Academy of Sciences, proves that any finite game has an equilibrium once mixed strategies are allowed. Von Neumann is said to have called it a trivial consequence of a fixed point theorem.
A Stochastic Approximation MethodHerbert Robbins and Sutton Monro#
1951·Annals of Mathematical Statistics
Contribution
Proved that a noisy iterative procedure converges to the root of an equation under a decreasing step-size schedule, founding stochastic optimization.
The problem came from bioassay, where the dose producing a target response must be found and each measurement is a noisy binary outcome. Robbins and Monro showed that a sequence of decreasing steps in the direction of the observed error converges to the root, and gave conditions on the step sizes that guarantee it. Those conditions are the reason learning rate schedules look the way they do.
On Information and SufficiencySolomon Kullback and Richard Leibler#
1951·Annals of Mathematical Statistics
Contribution
Defined the divergence between two probability distributions that became the loss function for maximum-likelihood training.
Kullback and Leibler were cryptanalysts, and the question of how much one intercepted distribution differs from another was operational rather than abstract. Their measure counts the extra bits spent when a code built for one distribution is used for the other. It is not symmetric, which turns out to be the right property rather than a defect.
A Method for the Construction of Minimum-Redundancy CodesDavid Huffman#
1952·Proceedings of the IRE
Contribution
Gave a greedy algorithm that constructs the optimal prefix-free code for a known symbol distribution.
Robert Fano offered his information theory class at MIT a choice between a final exam and a term paper on finding the optimal prefix code, without mentioning that he and Shannon had both failed at it. Huffman had nearly given up when he saw that building the tree upward from the least frequent symbols, rather than splitting downward, gives the optimum. The algorithm is still in use seventy years later.
Formulated portfolio choice as a tradeoff between expected return and variance, making diversification a solvable optimization rather than a maxim.
Markowitz was reading Williams on valuing a stock by its discounted dividends when he noticed the theory implied putting everything in whichever stock had the highest expected value. Since nobody actually does that, something was missing, and the missing thing was variance. Treating covariance as the mechanism made diversification a computation rather than a maxim.
Stochastic Estimation of the Maximum of a Regression FunctionJack Kiefer and Jacob Wolfowitz#
1952·Annals of Mathematical Statistics
Contribution
Gave a finite-difference variant of stochastic approximation for finding the maximum of a function observed only through noisy evaluations.
Robbins and Monro had solved the root-finding problem the previous year, but many applications need the maximum of a function rather than a zero. Kiefer and Wolfowitz supplied the extension by estimating the gradient from finite differences of noisy evaluations. The scheme is the ancestor of derivative-free stochastic optimization.
Equation of State Calculations by Fast Computing MachinesMetropolis, Rosenbluth, Rosenbluth, Teller and Teller#
1953·Journal of Chemical Physics
Contribution
Introduced the sampling method that became Markov chain Monte Carlo, drawing from a distribution known only up to a constant.
The Los Alamos group needed the equation of state for a system of hard spheres, where the integral runs over a space too large to sample uniformly. Their solution was to walk through configuration space accepting moves that lower the energy always and moves that raise it sometimes, with a probability that makes the walk settle at the right distribution. Marshall Rosenbluth later said Metropolis contributed nothing but computer time, though the name stuck.
Derived subjective probability and expected utility from axioms on preferences, giving Bayesian decision theory its foundation.
Savage set out to derive probability from preference rather than assume it, asking what consistency requirements a person's choices among uncertain prospects must satisfy. The answer is that anyone obeying them acts as if maximizing expected utility against some probability distribution, which need not be shared with anyone else. This is the technical foundation of the subjective Bayesian position.
Inadmissibility of the Usual Estimator for the Mean of a Multivariate Normal DistributionCharles Stein#
1956·Proceedings of the Third Berkeley Symposium
Contribution
Proved that the sample mean of a multivariate normal in three or more dimensions is inadmissible, showing that a biased shrinkage estimator dominates it.
Estimating several means at once was assumed to decompose into separate problems, since the observations are independent and each sample mean is optimal on its own. Stein showed that in three or more dimensions the collection of sample means is beaten by shrinking them toward a common point, even when the quantities are unrelated. The result was so unwelcome that it took a decade to be absorbed.
Proved that the maximum flow through a network equals the capacity of its minimum cut, and gave an algorithm that finds both.
The study was commissioned to analyze the Soviet rail network in Eastern Europe, and the question of where to cut it is the dual of how much can flow through it. Ford and Fulkerson proved that the maximum flow equals the minimum cut and gave an augmenting-path method to find both. The classified companion report on interdiction was declassified decades later.
The Imbedding Problem for Riemannian ManifoldsJohn Nash#
1956·Annals of Mathematics
Contribution
Proved that any Riemannian manifold can be isometrically embedded in Euclidean space, showing that intrinsic geometry is always realizable as extrinsic geometry.
Whitney's theorem embeds a manifold while distorting distances, so it says nothing about whether an abstract geometry can be realized concretely. Nash proved that it can, with distances preserved exactly, using an iteration that corrects errors faster than they accumulate. The technique became a general tool for solving nonlinear problems where ordinary approximation fails.
1960s
A New Approach to Linear Filtering and Prediction ProblemsRudolf Kalman#
1960·Journal of Basic Engineering
Contribution
Gave a recursive algorithm for optimal state estimation in linear systems with Gaussian noise, replacing batch solutions with a single-pass filter.
Wiener's filter required stationarity and worked in the frequency domain, which made it unusable for a vehicle whose dynamics change over time. Kalman recast the problem in state space, so that estimation becomes a recursion carrying only the current estimate and its covariance. The paper met resistance from the control community and was taken up first by NASA Ames for the Apollo navigation computer.
Optimal Policies for a Multi-Echelon Inventory ProblemClark and Scarf#
1960·Management Science
Contribution
Showed that a serial multi-stage inventory system decomposes into single-stage problems, making the optimal policy computable stage by stage.
Inventory theory had treated each stocking location in isolation, which is wrong when a warehouse supplies retailers whose demands it must anticipate. Clark and Scarf showed that under linear costs the multi-stage problem decomposes if inventory is measured cumulatively from the customer backward. That reformulation is why echelon stock, rather than local stock, is the quantity supply chains track.
Showed that with zero transaction costs, bargaining between parties reaches an efficient allocation regardless of the initial assignment of property rights.
Pigou had argued that a factory imposing costs on its neighbors should be taxed by the amount of the harm. Coase pointed out that the harm is reciprocal, that the parties can bargain if rights are defined and transaction costs are low, and that the efficient outcome then does not depend on who holds the right. The argument is usually cited for the frictionless case, which Coase considered the least interesting part.
A Proof for the Queuing Formula: L = λWJohn D. C. Little#
1961·Operations Research
Contribution
Proved that the average number in a queueing system equals the arrival rate times the average time in system, independent of the arrival and service distributions.
Practitioners had used the relation between queue length, arrival rate and waiting time for years on the strength of examples. Little supplied the proof and, more importantly, showed how little it assumes: no distributional form, no service discipline, no independence. That generality is why it applies to systems whose internals are unknown.
Counterspeculation, Auctions, and Competitive Sealed TendersWilliam Vickrey#
1961·Journal of Finance
Contribution
Introduced the second-price sealed-bid auction and showed that it is incentive-compatible, making truthful bidding a dominant strategy.
In a first-price sealed auction every bidder must guess how much to shade below their true value, which wastes effort and produces unpredictable outcomes. Vickrey showed that charging the winner the second-highest bid removes the guessing entirely, since bidding your value becomes dominant. The design was ignored in practice for thirty years and later inspired the second-price auctions used in online advertising, much of which has since moved to first-price formats.
A Dynamic Programming Approach to Sequencing ProblemsHeld and Karp#
1962·Journal of the Society for Industrial and Applied Mathematics
Contribution
Gave a dynamic program solving the traveling salesman problem in time exponential in the number of cities but far below enumerating all tours.
Enumerating tours over n cities is factorial, which is hopeless past about a dozen. Held and Karp observed that a partial tour need only be remembered by which cities it has visited and where it currently is, which collapses the count to n squared times two to the n. It remains the fastest exact algorithm known for the general case.
Capital Asset Prices: A Theory of Market Equilibrium under Conditions of RiskWilliam Sharpe#
1964·Journal of Finance
Contribution
Derived the capital asset pricing model, relating expected return to systematic risk through a single market factor.
Markowitz described what a single investor should hold, and Sharpe asked what prices must obtain if everyone holds such a portfolio. The answer is that diversifiable risk earns nothing, so a security's expected return depends only on its covariance with the market. The Journal of Finance rejected the paper before accepting it under a different editor.
Some Methods for Classification and Analysis of Multivariate ObservationsJames MacQueen#
1967·Berkeley Symposium on Mathematical Statistics and Probability
Contribution
Formalized the k-means clustering algorithm and proved convergence of the iterative assignment-update procedure.
MacQueen gave the procedure the name k-means and analyzed a sequential version of it, in the proceedings of the Berkeley symposium. Stuart Lloyd had described essentially the same algorithm at Bell Labs a decade earlier for pulse-code modulation, but that work was internal and did not appear until 1982. The method is now standard partly because it is the simplest thing that works.
1970s
Efficient Capital Markets: A Review of Theory and Empirical WorkEugene Fama#
1970·Journal of Finance
Contribution
Formalized the efficient market hypothesis and classified its weak, semi-strong, and strong forms against the available empirical evidence.
Fama organized two decades of scattered evidence on price predictability into a single framework and drew the distinction between weak, semi-strong and strong forms of efficiency. The framing made the hypothesis testable by specifying exactly which information set is at issue. It also made explicit that any test of efficiency is a joint test of efficiency and an asset pricing model, which is the objection that has proved hardest to answer.
Space/Time Trade-offs in Hash Coding with Allowable ErrorsBurton H. Bloom#
1970·Communications of the ACM
Contribution
Introduced the Bloom filter, a probabilistic data structure that tests set membership with no false negatives and a controllable false positive rate.
Bloom was working on hyphenation, where most words follow rules and a dictionary lookup for the exceptions is too large to keep in memory. He observed that a test allowed to say yes occasionally when the answer is no can use a small fraction of the space. The filter is now used wherever a cheap negative check precedes an expensive lookup.
The Market for 'Lemons': Quality Uncertainty and the Market MechanismGeorge Akerlof#
1970·Quarterly Journal of Economics
Contribution
Showed that asymmetric information about quality can collapse a market to its worst goods, even when gains from trade exist.
Akerlof asked why a car loses so much value the moment it is driven off the lot, and found that the answer generalizes. If sellers know quality and buyers do not, the price reflects the average, good sellers withdraw, and the average falls again until the market can unravel entirely. Three journals rejected the paper, two on the grounds that it was trivial and one that it was too general to be true.
On the Uniform Convergence of Relative Frequencies of Events to Their ProbabilitiesVladimir Vapnik and Alexey Chervonenkis#
1971·Theory of Probability and Its Applications
Contribution
Proved uniform convergence bounds that depend on the combinatorial dimension of a function class, founding statistical learning theory.
Empirical error converges to true error for any fixed classifier, which says nothing useful once the classifier is chosen by looking at the data. Vapnik and Chervonenkis asked when convergence holds uniformly over a whole class, and answered it with a combinatorial measure of how many labelings the class can produce. The bound requires no assumption about the underlying distribution.
The Complexity of Theorem-Proving ProceduresStephen Cook#
1971·STOC
Contribution
Defined the class NP and proved that Boolean satisfiability is NP-complete, giving the first problem against which all others in NP could be reduced.
Cook was asking whether propositional satisfiability is fundamentally harder than the problems reducible to it. The paper shows that any problem solvable by a nondeterministic machine in polynomial time reduces to satisfiability, which makes one concrete problem a stand-in for an entire class. Levin proved essentially the same thing in the Soviet Union at the same time and neither knew of the other.
Organization and Maintenance of Large Ordered IndexesBayer and McCreight#
1972·Acta Informatica
Contribution
Introduced the B-tree, which keeps the tree balanced and packs many keys per node to minimize disk seeks in large indexes.
Binary trees are optimal when comparisons dominate and terrible when the data is on disk, since each level is a separate seek. Bayer and McCreight made nodes wide enough to fill a disk page, so the tree is shallow and each level costs one read. Essentially every relational database and filesystem index is a variant of this structure.
Reducibility Among Combinatorial ProblemsRichard Karp#
1972·Complexity of Computer Computations
Contribution
Showed that 21 natural combinatorial problems are NP-complete by a chain of polynomial reductions from satisfiability.
Cook's theorem identified one hard problem, and it was not obvious whether it was an isolated curiosity. Karp exhibited twenty-one problems from scheduling, graph theory and logic that all reduce to it and to each other, so that any one of them being easy would make all of them easy. The list is what convinced the field that the question mattered.
Modeled education as a costly signal of unobservable ability, showing how informed agents can credibly communicate private information.
Spence asked why employers pay more for a degree whose content has nothing to do with the work. If education costs less for able candidates than for others, then acquiring it is credible evidence of ability regardless of what is learned. The model separates signaling from human capital as explanations for the wage premium, which are observationally similar and imply different policy.
The Pricing of Options and Corporate LiabilitiesFischer Black and Myron Scholes#
1973·Journal of Political Economy
Contribution
Derived a closed-form price for a European option by constructing a riskless hedge and solving the resulting partial differential equation.
Black and Scholes noticed that a position combining the option and the underlying can be made instantaneously riskless, and that arbitrage then pins the price without any reference to expected return or risk preference. Two journals rejected the paper before Merton Miller and Eugene Fama intervened on its behalf. The Chicago Board Options Exchange opened for trading one month before it appeared.
Theory of Rational Option PricingRobert C. Merton#
1973·Bell Journal of Economics and Management Science
Contribution
Extended option pricing to dividends and American exercise, and placed the no-arbitrage argument on a continuous-time stochastic calculus foundation.
Merton reached the same formula through continuous-time stochastic control rather than the hedging argument, which made the assumptions explicit and the result more general. He derived a set of bounds that hold for any option regardless of the pricing model, then showed where the specific formula sits inside them. He deliberately delayed publication so that Black and Scholes would appear first.
Efficiency of a Good But Not Linear Set Union AlgorithmRobert Endre Tarjan#
1975·Journal of the ACM
Contribution
Analyzed the union-find data structure with path compression and union by rank, showing its amortized cost is an inverse Ackermann function of the number of operations.
Union-find with path compression and union by rank was known to be fast and its exact cost was unknown. Tarjan proved the amortized cost per operation is the inverse Ackermann function, which is below five for any input that could physically exist, and later showed the bound is tight. It is a rare case of a natural algorithm whose complexity is almost but not quite constant.
New Directions in CryptographyWhitfield Diffie and Martin Hellman#
1976·IEEE Transactions on Information Theory
Contribution
Introduced public-key cryptography and a key-exchange protocol whose security rests on the difficulty of discrete logarithms.
Key distribution had been the unsolved problem in cryptography for as long as it had existed, since two parties who have never met cannot agree on a secret over a channel an adversary is reading. Diffie and Hellman showed they can, using exponentiation in a group where the inverse is hard, and proposed digital signatures in the same paper. GCHQ had reached similar conclusions years earlier under classification and could not say so.
Maximum Likelihood from Incomplete Data via the EM AlgorithmDempster, Laird and Rubin#
1977·Journal of the Royal Statistical Society, Series B
Contribution
Unified a family of iterative procedures for maximum-likelihood estimation in the presence of missing or latent data.
Half a dozen fields had independently discovered the same alternation between filling in missing values and re-estimating parameters, each under its own name. Dempster, Laird and Rubin recognized them as one algorithm, gave it a name, and proved that the likelihood cannot decrease. The convergence proof in the paper contained an error that Wu corrected six years later.
A Method for Obtaining Digital Signatures and Public-Key CryptosystemsRivest, Shamir and Adleman#
1978·Communications of the ACM
Contribution
Constructed a practical public-key cryptosystem and digital signature scheme based on the difficulty of factoring large integers.
Diffie and Hellman had argued that a public-key system should exist without producing one. Rivest, Shamir and Adleman spent a year proposing candidates and breaking them, until one built on the difficulty of factoring survived. Martin Gardner described it in Scientific American before the technical paper appeared, which is how most people first heard of it.
A Theory of Type Polymorphism in ProgrammingRobin Milner#
1978·Journal of Computer and System Sciences
Contribution
Gave the theory behind polymorphic type inference, showing that the principal type of an expression in a polymorphic language can be computed without annotations.
Static typing required annotating every declaration, which is verbose, while dynamic typing defers all errors to runtime. Milner showed that the most general type of an expression can be inferred with no annotations at all, and that a program passing inference cannot fail with a type error at runtime. The algorithm underlies ML, Haskell, OCaml and the inference in most modern languages.
Time, Clocks, and the Ordering of Events in a Distributed SystemLeslie Lamport#
1978·Communications of the ACM
Contribution
Defined the happened-before partial order and gave a logical clock that assigns consistent timestamps without a physical time source.
Lamport was reading a paper on replicated databases and noticed its protocol was wrong, because it assumed events have a well-defined order that no distributed system can supply. He recognized the situation as the one in special relativity, where simultaneity is not absolute, and defined ordering by causality instead. The logical clock construction that follows is three pages and underlies most of the field.
Bootstrap Methods: Another Look at the JackknifeBradley Efron#
1979·Annals of Statistics
Contribution
Showed that resampling from the observed data with replacement yields confidence intervals without distributional assumptions.
Standard errors were available only for statistics whose sampling distribution someone had worked out analytically, which excludes most quantities people actually care about. Efron proposed resampling the observed data with replacement and treating the spread of the recomputed statistic as the answer. The name refers to the apparent impossibility of it working.
Prospect Theory: An Analysis of Decision under RiskDaniel Kahneman and Amos Tversky#
1979·Econometrica
Contribution
Documented systematic violations of expected utility theory and proposed a descriptive model with reference dependence and loss aversion.
Kahneman and Tversky had accumulated a decade of experiments in which people violate expected utility in consistent directions. The model replaces wealth with gains and losses from a reference point, makes the loss side steeper, and overweights small probabilities. They placed it in Econometrica deliberately, on the reasoning that psychologists would not change economics from a psychology journal.
1980s
A Method for Solving a Convex Programming Problem with Convergence Rate O(1/k^2)Yurii Nesterov#
1983·Soviet Mathematics Doklady
Contribution
Introduced momentum-based acceleration for gradient descent, achieving the optimal convergence rate for smooth convex functions.
Gradient descent on a smooth convex function reduces the gap in proportion to one over the iteration count, and lower bounds show a first-order method could in principle do better. Nesterov exhibited a method that attains the better rate by evaluating the gradient at an extrapolated point rather than the current one. The scheme is not a heuristic acceleration but the provably optimal one for this class.
A new polynomial-time algorithm for linear programmingNarendra Karmarkar#
1984·Combinatorica
Contribution
Gave an interior-point method solving linear programs in polynomial time, and the first such method that was competitive with the simplex method in practice.
Khachiyan had shown in 1979 that linear programs are solvable in polynomial time, but the ellipsoid method was far slower in practice than the exponential-worst-case simplex method. Karmarkar's method moves through the interior of the feasible region rather than along its edges, and was fast in theory and in practice at once. AT&T patented it, which set off a long argument about whether algorithms should be patentable.
Defined probably approximately correct learning and proved that Boolean conjunctions are learnable in polynomial time under this model.
Machine learning had procedures that worked on examples and no way to say what working means. Valiant proposed asking for a hypothesis that is probably approximately correct, with sample size and running time bounded polynomially in the accuracy and confidence demanded. Naming the tolerances turned learning into a subject with theorems.
Classification and Regression TreesBreiman, Friedman, Olshen and Stone#
1984·Wadsworth, reissued by Routledge 2017
Contribution
Formalized recursive binary splitting of feature space into a decision tree with pruning, giving the CART algorithm.
Recursive partitioning had been tried repeatedly and kept failing, because a tree grown until the training data is exhausted fits noise. The monograph's contribution is to grow the tree deliberately too large and then prune it back using a complexity penalty tuned by cross-validation.
End-to-End Arguments in System DesignSaltzer, Reed and Clark#
1984·ACM Transactions on Computer Systems
Contribution
Argued that a function needing the application's knowledge can be implemented completely and correctly only at the endpoints, and that a partial version lower in the system can still be useful as a performance enhancement.
Reliable packet delivery still leaves failures in host software, storage and gateway buffers outside the checked path. Saltzer, Reed and Clark used careful file transfer and delivery acknowledgments to explain why applications still need their own checks and completion protocol.
Graphical Perception: Theory, Experimentation, and Application to the Development of Graphical MethodsCleveland and McGill#
1984·Journal of the American Statistical Association
Contribution
Ranked the elementary perceptual tasks used to read a chart by measured accuracy, establishing that position along a common scale is judged more accurately than length, angle, area or color.
Chart design advice rested on taste and precedent, with no measurements of what readers can actually extract. Cleveland and McGill ran experiments ranking the elementary perceptual tasks by accuracy, finding position along a common scale most accurate and area, angle, and color saturation progressively worse. This is the empirical basis for preferring bars to pies.
Impossibility of Distributed Consensus with One Faulty ProcessFischer, Lynch and Paterson#
1985·Journal of the ACM
Contribution
Proved that a deterministic protocol satisfying consensus agreement and validity cannot guarantee termination in a fully asynchronous system with even one possible crash fault.
With unbounded message delay, a process cannot distinguish a crashed peer from one whose messages have not arrived. Fischer, Lynch and Paterson showed that a deterministic protocol preserving agreement and validity can have an admissible execution that never decides. Additional timing or failure-detector assumptions, or appropriate randomized guarantees, change the model; a timeout alone does not prove that an asynchronous peer has failed.
Learning Representations by Back-propagating ErrorsRumelhart, Hinton and Williams#
1986·Nature
Contribution
Showed that gradients computed by the chain rule train multilayer networks to build useful internal representations.
Multilayer networks were known to be more expressive than perceptrons and there was no accepted way to train them. The four-page Nature paper shows that the chain rule gives the gradient for every weight in one backward sweep, and that the hidden units then discover features nobody specified. Linnainmaa had described the same computation years earlier without reference to neural networks, and Werbos had proposed using it to train them, though without demonstrating learned internal representations.
Formalized the assignment of probabilities to logical sentences and gave entailment rules for probabilistic knowledge bases.
Logical inference gives conclusions that follow with certainty from premises, which excludes nearly everything an agent actually knows. Nilsson showed how to treat a set of sentences with attached probabilities as constraints on a distribution over possible worlds, so that entailment becomes a linear program. The formulation clarified why probabilistic reasoning is expensive and set up the search for structure that makes it tractable.
How to Play Any Mental GameGoldreich, Micali and Wigderson#
1987·STOC
Contribution
Proved that any function can be computed by multiple parties without any party learning more than what the output reveals, assuming trapdoor permutations exist.
Yao had shown two parties can compute a function of their private inputs without revealing them, for specific functions. Goldreich, Micali and Wigderson proved the general case: any function that could be computed with a trusted intermediary can be computed without one. The result establishes that secure multiparty computation is a matter of cost rather than possibility.
Learning to Predict by the Methods of Temporal DifferencesRichard Sutton#
1988·Machine Learning
Contribution
Introduced temporal-difference learning, which updates value estimates from successive predictions without waiting for a final outcome.
Supervised learning of a prediction requires waiting for the outcome, which in a long episode means waiting a long time and learning nothing in between. Sutton showed that a prediction can be updated toward the next prediction instead, so learning happens at every step. The method was already implicit in Samuel's checkers program from the 1950s and this paper gave it a proof.
Probabilistic Reasoning in Intelligent SystemsJudea Pearl#
1988·Morgan Kaufmann
Contribution
Unified probabilistic inference using directed graphical models and message-passing algorithms over Bayesian networks.
Exact probabilistic inference over many variables was considered infeasible because the joint distribution grows exponentially. Pearl's book shows that conditional independence, read off a directed graph, factors the joint into local pieces and makes inference tractable on the structures that occur in practice. It also gave the standard account of belief propagation, which later reappeared as the decoding algorithm for modern error-correcting codes.
The Design Philosophy of the DARPA Internet ProtocolsDavid D. Clark#
1988·SIGCOMM
Contribution
Explained the Internet architecture through its ranked design goals, including fate-sharing: essential connection state is kept at the end hosts, so losing a gateway does not erase a live connection.
The DARPA protocols had to join existing networks and keep communication going when networks or gateways failed. Clark described how these goals led to stateless packet switches between hosts that retain the state transport reliability needs.
The Knowledge Complexity of Interactive Proof SystemsGoldwasser, Micali and Rackoff#
1989·SIAM Journal on Computing
Contribution
Defined zero-knowledge proofs and showed that a prover can convince a verifier of a statement without revealing anything beyond its truth.
A proof normally convinces by exhibiting the reason, which means the verifier learns the reason. Goldwasser, Micali and Rackoff asked whether one can convince without teaching, and defined knowledge leaked as whatever the verifier could not have simulated alone. The paper was rejected three times before publication and the notion is now the foundation of a large part of applied cryptography.
1990s
A Statistical Approach to Machine TranslationPeter Brown et al.#
1990·Computational Linguistics
Contribution
Modeled translation as a noisy channel and estimated word-alignment probabilities from parallel corpora, founding statistical machine translation.
Machine translation had been a grammar-writing enterprise for thirty years with disappointing results. The IBM group treated translation as decoding a noisy channel, estimating word correspondences directly from the bilingual proceedings of the Canadian parliament with no linguistic rules at all. The approach was resented by the linguistics community and it worked.
Sampling-Based Approaches to Calculating Marginal DensitiesAlan Gelfand and Adrian Smith#
1990·Journal of the American Statistical Association
Contribution
Showed that Gibbs sampling and related MCMC methods make Bayesian posterior inference practical for models where analytic solutions do not exist.
Bayesian analysis was limited to models where the posterior had a closed form, which is a small and unrepresentative class. Gelfand and Smith showed that iteratively sampling each parameter from its conditional distribution produces draws from the joint posterior, using machinery already known in image processing. The paper is usually credited with making applied Bayesian statistics practical.
Skip Lists: A Probabilistic Alternative to Balanced TreesWilliam Pugh#
1990·Communications of the ACM
Contribution
Introduced skip lists, which achieve expected logarithmic search, insert, and delete times using randomized tower heights instead of explicit rebalancing.
Balanced trees achieve logarithmic operations through rebalancing rules that are correct and unpleasant to implement, especially under concurrency. Pugh replaced the rebalancing with randomization, giving each element a random number of forward pointers so that expected search cost is logarithmic. The structure is far simpler to implement and to make concurrent, which is why several databases use it.
Proved that any weak learner can be boosted to arbitrary accuracy, answering the open question that motivated the boosting framework.
Kearns and Valiant had asked whether a learner barely better than chance implies the existence of one that is arbitrarily accurate, and the answer was not obvious. Schapire proved that it does, by constructing a procedure that trains later learners on the examples earlier ones get wrong. The construction was impractical and led directly to AdaBoost five years later.
Adaptive Mixtures of Local ExpertsJacobs, Jordan, Nowlan and Hinton#
1991·Neural Computation
Contribution
Introduced the mixture-of-experts architecture, training a gating network and several expert networks together so that experts specialize on different regions of the input space.
A single network trained on a heterogeneous task must find one set of weights that serves all of it, and the subtasks interfere. Jacobs, Jordan, Nowlan and Hinton trained several networks alongside a gate that decides which to trust for each input, with an error function that encourages specialization rather than cooperation. The idea sat mostly unused until model sizes made conditional computation attractive.
Efficiently Computing Static Single Assignment Form and the Control Dependence GraphCytron et al.#
1991·ACM TOPLAS
Contribution
Gave an efficient algorithm, linear in practice, for converting a program to SSA form, making def-use analysis trivial and enabling most modern compiler optimizations.
Optimizing compilers need to know which definition of a variable reaches which use, and computing that repeatedly is expensive. Assigning each variable exactly once makes the answer syntactic, and the difficulty is placing merge nodes where control flow joins. Cytron and colleagues showed the correct placement is given by the dominance frontier and can be computed efficiently, which made this the standard intermediate representation.
ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead LoggingMohan et al.#
1992·ACM Transactions on Database Systems
Contribution
Described a write-ahead-logging recovery method that permits steal and no-force buffer policies by repeating history on restart, redoing every missing update before rolling back the transactions that never committed.
ARIES combined record-level locking, partial rollbacks and write-ahead logging in one recovery method. On restart it repeats history, redoing every missing update, including those of transactions that will be rolled back, and only then undoes the losers, logging each undo step as a redo-only compensation record so that logging stays bounded even when failures repeat during restart. The paper reports implementations, to varying degrees, in IBM's DB2, Starburst and QuickSilver, among others, and in the University of Wisconsin's EXODUS and Gamma.
Proved that an off-policy temporal-difference update converges to the optimal action-value function under standard stochastic approximation conditions.
Temporal difference methods learned the value of following a fixed policy, which does not directly say what to do instead. Watkins's thesis result, presented here with Dayan's convergence proof, learns the value of each action and converges to the optimal policy even while the agent behaves suboptimally to explore. Learning about one policy while following another is what makes the method usable.
Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement LearningRonald Williams#
1992·Machine Learning
Contribution
Derived the REINFORCE algorithm, showing that the gradient of expected reward can be estimated from sampled trajectories without a model of the environment.
When the action is sampled from a distribution, the reward is not a differentiable function of the parameters, so backpropagation does not apply. Williams showed that the gradient of expected reward can still be estimated from samples by weighting the log-probability of the action taken by the reward received. Every policy gradient method in use descends from this identity.
Multilayer Feedforward Networks with a Nonpolynomial Activation Function Can Approximate Any FunctionMoshe Leshno, Vladimir Ya. Lin, Allan Pinkus and Shimon Schocken#
1993·Neural Networks
Contribution
Proved that feedforward networks with a single hidden layer of non-polynomial activation functions can approximate any continuous function on a compact set.
Cybenko and Hornik had proved universal approximation for sigmoidal activations, leaving open how much the specific shape mattered. Leshno and colleagues showed the condition is exactly that the activation not be a polynomial, which is close to no condition at all. The result also clarifies that universality is not the interesting property, since it says nothing about how many units are needed.
Algorithms for Quantum Computation: Discrete Logarithms and FactoringPeter Shor#
1994·FOCS
Contribution
Gave polynomial-time quantum algorithms for integer factoring and discrete logarithms, breaking RSA and Diffie-Hellman on a fault-tolerant quantum computer.
Quantum computing had been a theoretical curiosity with no problem it clearly solved faster. Shor observed that factoring reduces to finding the period of a function, and that a quantum Fourier transform extracts periods in polynomial time. Since the security of deployed public-key cryptography rests on factoring and discrete logarithms being hard, the field acquired funding almost immediately.
Controlling the False Discovery Rate: A Practical and Powerful Approach to Multiple TestingYoav Benjamini and Yosef Hochberg#
1995·Journal of the Royal Statistical Society, Series B
Contribution
Defined the false discovery rate and gave a step-up procedure that controls it for independent tests, replacing the Bonferroni correction in high-dimensional testing.
Bonferroni correction controls the chance of any false positive, which is so conservative that with thousands of tests nothing survives. Benjamini and Hochberg proposed controlling the expected fraction of discoveries that are false instead, which is the quantity a screening study actually cares about. The procedure arrived just as genomics began producing tests by the thousand.
Support-Vector NetworksCorinna Cortes and Vladimir Vapnik#
1995·Machine Learning
Contribution
Introduced the soft-margin support vector machine, maximizing the classification margin while tolerating a controlled amount of misclassification.
Vapnik's theory said generalization depends on the capacity of the hypothesis class rather than its parameter count, which suggested choosing the maximum-margin separator. Cortes and Vapnik added slack variables for non-separable data and combined them with the kernel trick of Boser, Guyon and Vapnik for nonlinear boundaries, so the method computes in the original space while separating in a much larger one. It was the strongest general-purpose classifier for roughly the next decade.
A Fast Quantum Mechanical Algorithm for Database SearchLov Grover#
1996·STOC
Contribution
Gave a quantum algorithm that searches an unstructured database of N items in O(sqrt(N)) queries, which is provably optimal.
Shor's algorithm exploited the specific structure of periodicity, and it was unclear whether quantum computers helped on problems with no structure at all. Grover showed that an unstructured search of n items takes only the square root of n queries, by repeatedly rotating the state toward the marked item. The speedup is provably optimal and is quadratic rather than exponential, which is why symmetric cryptography survives by doubling key lengths.
Emergence of Simple-Cell Receptive Field Properties by Learning a Sparse Code for Natural ImagesOlshausen and Field#
1996·Nature
Contribution
Showed that imposing a sparsity penalty on a learned overcomplete basis for natural images yields localized, oriented, bandpass filters, which is the origin of the dictionary learning later applied to interpretability.
Neurophysiology had cataloged the oriented, localized, bandpass receptive fields in primary visual cortex without explaining why those and not others. Olshausen and Field imposed only two requirements, that natural images be reconstructable and that few units be active at once, and the same receptive fields emerged. The result is one of the strongest arguments that cortical structure reflects the statistics of the input.
The Log-Structured Merge-Tree (LSM-Tree)O'Neil et al.#
1996·Acta Informatica
Contribution
Introduced a write-optimized index structure that batches writes in memory and merges sorted runs on disk, trading read amplification for write throughput.
B-trees update in place, which turns a write-heavy workload into random disk writes and destroys throughput. O'Neil and colleagues buffer writes in memory and flush them as sorted runs that are later merged, converting random writes into sequential ones. Reads cost more, which is the trade every write-optimized store since has taken.
Introduced consistent hashing, which distributes keys across nodes so that adding or removing a node moves only a fraction of keys proportional to 1/n.
Distributing keys across servers by hashing modulo the server count remaps nearly everything whenever a server is added or removed. Karger and colleagues placed servers and keys on the same circular hash space, so a change moves only the keys in one arc. The technique came out of web caching and is now standard in distributed storage.
Long Short-Term MemorySepp Hochreiter and Jürgen Schmidhuber#
1997·Neural Computation
Contribution
Introduced gated memory cells that let recurrent networks learn dependencies over hundreds of time steps without vanishing gradients.
Hochreiter had shown in his 1991 thesis that gradients through a recurrent network either vanish or explode over long sequences, which caps the dependencies such a network can learn. The remedy is a cell with a linear self-connection and multiplicative gates controlling what enters and leaves (a gate for what persists was added in 2000), so the gradient has a path that neither shrinks nor grows. The architecture dominated sequence modeling until attention replaced it.
No Free Lunch Theorems for OptimizationDavid Wolpert and William Macready#
1997·IEEE Transactions on Evolutionary Computation
Contribution
Proved that averaged over all possible objective functions, no optimization algorithm outperforms any other, so performance gains require problem structure.
Practitioners regularly claimed that one search heuristic was generally better than another. Wolpert and Macready proved that averaged over all possible objective functions every algorithm performs identically, so any advantage must come from assumptions about which functions arise. The theorem is often overread, since real problems are drawn from a narrow and highly structured subset.
Gradient-Based Learning Applied to Document RecognitionLeCun, Bottou, Bengio and Haffner#
1998·Proceedings of the IEEE
Contribution
Demonstrated that convolutional networks trained end-to-end with backpropagation read handwritten digits at production accuracy.
LeCun's group had been building convolutional networks for handwritten digits since the late 1980s, and this paper is the consolidated account. Beyond the architecture it argues that the whole pipeline, including segmentation, should be trained end to end rather than assembled from separately tuned pieces. The resulting system read a large share of the checks processed in the United States.
Proof Verification and the Hardness of Approximation ProblemsArora et al.#
1998·Journal of the ACM
Contribution
Proved that NP membership has verifiers using logarithmically many random bits and constantly many proof-bit queries, with perfect completeness and soundness error at most one half.
Hardness of exact optimization does not by itself establish hardness of approximation. Arora and colleagues gave verifiers that use logarithmic randomness but inspect only constantly many proof bits: a true instance has a proof accepted with probability one, while every purported proof of a false instance is rejected with probability at least one half. These guarantees concern the instance being proved, not detection of every altered bit in a proof of a true statement, and they yield hardness-of-approximation results.
Described Paxos, whose quorum rules preserve agreement despite asynchronous delays and crash faults, with additional communication and leadership conditions needed for progress.
Lamport presented the consensus algorithm as an archaeological report on the legislative procedures of a fictional Greek island. Agreement safety does not guarantee that a new value will be chosen: progress needs a stable proposer and a responding majority with sufficiently timely message delivery. Crash recovery must preserve the protocol state on which the safety argument depends.
The PageRank Citation Ranking: Bringing Order to the WebLawrence Page et al.#
1999·Stanford InfoLab
Contribution
Defined a web page importance score as the stationary distribution of a random walk on the link graph, with a damping factor to handle sinks.
Web search in the mid-1990s ranked pages by keyword frequency, which is trivially gamed by repeating words. Page and Brin proposed ranking by a recursive notion of importance, where a page matters if pages that matter link to it, computed as the stationary distribution of a random walk. The idea came from academic citation counting and became the basis of Google.
2000s
Greedy Function Approximation: A Gradient Boosting MachineJerome Friedman#
2001·Annals of Statistics
Contribution
Cast boosting as gradient descent in function space, fitting each weak learner to the negative gradient of the loss.
Boosting had been explained as a margin-maximizing procedure specific to classification, which did not say how to extend it. Friedman reframed it as gradient descent in function space, where each new tree fits the negative gradient of whatever loss is chosen. That reframing made boosting available for regression, ranking, and any differentiable objective, and it remains among the strongest methods for tabular data.
Restated the Paxos consensus algorithm in plain English and showed how a replicated state machine runs a sequence of separate Paxos instances, one per command, with an elected leader as the only proposer.
Paxos had been regarded as difficult to understand, which Lamport attributes to its original presentation being Greek to many readers. This short column derives the single-decree algorithm step by step from the requirements of consensus, then builds a state machine from a sequence of instances, the structure that DynamoDB's 2022 paper, citing this column, calls Multi-Paxos.
Showed that bagging decorrelated decision trees with random feature subsets yields an ensemble with low variance and competitive accuracy.
Bagging reduces variance by averaging trees fit to resampled data, but the trees stay correlated because they all split on the same dominant features. Breiman added a second randomization, restricting each split to a random subset of variables, which decorrelates the trees and improves the average further. The paper also shows the generalization error converges rather than diverging as trees are added, so the method does not overfit with size.
The control of the false discovery rate in multiple testing under dependencyYoav Benjamini and Daniel Yekutieli#
2001·Annals of Statistics
Contribution
Proved that the Benjamini-Hochberg procedure still controls the false discovery rate under positive regression dependence among the test statistics, and gave a conservative modification that controls it under any dependence.
The 1995 false discovery rate procedure was proved for independent tests, while tests in fields such as genomics and imaging are often correlated. Benjamini and Yekutieli showed that a common form of positive dependence leaves the guarantee intact, and that a more conservative version of the procedure restores it under any dependence, at a cost in power.
Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web ServicesGilbert and Lynch#
2002·ACM SIGACT News
Contribution
Proved the CAP theorem, showing that a distributed system cannot simultaneously provide linearizability and availability when a network partition occurs.
Brewer had conjectured in a conference talk that a distributed system cannot have consistency, availability, and partition tolerance at once. Gilbert and Lynch supplied a formal model and a proof, which also clarified that the trade is only forced during an actual partition. The theorem is widely cited in a looser form than what was proved.
Topological Persistence and SimplificationEdelsbrunner, Letscher and Zomorodian#
2002·Discrete & Computational Geometry
Contribution
Formalized persistent homology by tracking when topological features appear and disappear in a filtration, distinguishing structure from noise by lifetime.
Topological features of a sampled space depend on the scale at which it is examined, and there was no principled way to pick the scale. Edelsbrunner, Letscher and Zomorodian track features across all scales at once and record where each appears and disappears, so that long-lived features can be separated from noise. This made topology into a data analysis method with a computable output.
Introduced a generative probabilistic model for collections of discrete data that discovers latent topic structure via variational inference.
Earlier topic models assigned each document a fixed mixture with no generative story above the document level, which meant they could not assign probability to a document they had not seen. Blei, Ng and Jordan placed a Dirichlet prior over the mixtures, which makes the model properly generative and regularizes the per-document estimates. It became the standard tool for unsupervised structure in text corpora.
The Google File SystemGhemawat, Gobioff and Leung#
2003·SOSP
Contribution
Described a distributed file system designed for large streaming reads on commodity hardware, with single-master metadata and replicated chunks.
Google needed to store data across thousands of cheap machines where disk failure is a daily event rather than an exception. The design abandons POSIX semantics, assumes files are huge and mostly appended to, and puts all metadata on a single master while data flows directly between clients and chunk servers. Nearly every distributed file system built since borrows from it.
Introduced a hash table with worst-case constant lookup time by using two hash functions and moving existing keys on collision.
Open addressing gives fast lookups on average with no bound on the worst case, since a probe sequence can run long. Pagh and Rodler used two tables and two hash functions, with each key in one of exactly two positions and insertions displacing whatever they find. Lookup then touches at most two locations, which makes the worst case constant.
LLVM: A Compilation Framework for Lifelong Program Analysis and TransformationLattner and Adve#
2004·CGO
Contribution
Introduced a typed, low-level intermediate representation and modular compiler infrastructure that decouples front ends from back ends and optimization passes.
Compilers were monolithic, so a new language meant writing a backend for every target and a new target meant modifying every compiler. Lattner and Adve defined a typed low-level intermediate representation stable enough to serve as the interface between them, with optimization operating on it independently of both ends. Clang, Rust, Swift and most GPU compilers are built on it.
MapReduce: Simplified Data Processing on Large ClustersJeffrey Dean and Sanjay Ghemawat#
2004·OSDI, reprinted in Communications of the ACM 2008
Contribution
Showed that a two-phase functional abstraction over partitioned data lets non-specialists write programs that run on thousands of machines.
Google engineers kept writing the same distribution, scheduling, and fault tolerance code around otherwise simple computations. Dean and Ghemawat noticed the computations almost always fit a per-record transformation followed by a grouped aggregation, and that fixing that shape lets the framework handle everything else. The restriction is what makes automatic recovery from machine failure possible.
Causal Inference Using Potential Outcomes: Design, Modeling, DecisionsDonald Rubin#
2005·Journal of the American Statistical Association
Contribution
Formalized the potential outcomes framework for causal inference and showed how randomization, matching, and propensity scores fit within it.
Rubin's framework had been developed over three decades in scattered papers and was often applied without its design discipline. This account insists that the assignment mechanism be specified before any outcome is examined, so that an observational study is analyzed as an approximation to an experiment. The separation of design from analysis is the paper's practical contribution.
Defined a mathematical guarantee bounding how much any single record can affect the output of a query, giving a composable privacy notion.
Anonymized data releases kept being reidentified, and each fix addressed the specific attack rather than the underlying problem. Dwork proposed a guarantee about the mechanism instead of the data: the output distribution must barely change when any single record is added or removed. That makes the promise hold against an adversary with arbitrary side information, which no earlier definition did.
Gaussian Processes for Machine LearningCarl Rasmussen and Christopher Williams#
2006·MIT Press
Contribution
Presented a unified treatment of Gaussian process regression and classification with exact and approximate inference methods.
Kernel methods gave point predictions with no principled account of uncertainty, which matters when a prediction drives a decision. The book develops the view that a prior over functions with a covariance kernel yields a posterior in closed form, giving both a prediction and its variance. The cubic cost in sample size is the reason the method stayed confined to small data and to Bayesian optimization.
Dynamo: Amazon's Highly Available Key-value StoreDeCandia et al.#
2007·SOSP
Contribution
Described a key-value store that sacrifices strong consistency for availability and partition tolerance, using consistent hashing and vector clocks.
Amazon found that for the shopping cart, refusing a write during a network partition costs more than serving stale data. Dynamo therefore accepts writes always, allows replicas to diverge, and reconciles at read time using vector clocks and application-supplied merge logic. The paper is the practical statement of choosing availability over consistency and launched the systems that followed it.
Visualizing Data using t-SNEvan der Maaten and Hinton#
2008·JMLR
Contribution
Introduced a nonlinear dimensionality reduction method that preserves local neighborhood structure, making cluster structure visible in two-dimensional projections.
Earlier embedding methods preserved large distances well and crowded everything else into the middle, since in high dimensions most pairs are far apart. Van der Maaten and Hinton used a heavy-tailed distribution in the low-dimensional space, which gives distant points room and lets nearby structure separate. The method reveals cluster structure clearly and the distances between clusters should not be interpreted.
Large-Scale Deep Unsupervised Learning Using Graphics ProcessorsRaina, Madhavan and Ng#
2009·ICML
Contribution
Demonstrated that sparse coding and deep belief networks train an order of magnitude faster on a GPU than on a CPU, motivating GPU adoption for deep learning.
Training deep models was limited by processor speed, and graphics hardware offered far more arithmetic throughput than anyone in machine learning was using. Raina, Madhavan and Ng mapped the matrix operations of deep belief networks onto the GPU and reported speedups above an order of magnitude. The paper made the hardware argument three years before the result that convinced everyone.
The Probabilistic Relevance Framework: BM25 and BeyondStephen Robertson and Hugo Zaragoza#
2009·Foundations and Trends in Information Retrieval
Contribution
Gave a unified account of term-weighting models from TF-IDF through BM25, deriving each from probabilistic relevance assumptions.
BM25 was in wide use as a scoring formula carrying tuning constants whose justification was spread across two decades of separate papers. Robertson and Zaragoza assemble the probabilistic relevance framework in one place and show which modeling assumption produces each term of the formula. The account matters because the constants are routinely tuned as free parameters by people who do not know what the derivation assumes about them.
2010s
Conflict-Free Replicated Data TypesShapiro et al.#
2011·SSS
Contribution
Defined data types whose concurrent operations commute by construction, guaranteeing eventual convergence without coordination.
Replicas that accept writes independently will diverge, and reconciling them usually means coordination or a human deciding which version wins. Shapiro and colleagues identified data types whose merge operation is commutative, associative, and idempotent, so replicas converge automatically regardless of message order or duplication. Collaborative editors and offline-capable applications are built on this.
Distributed Optimization and Statistical Learning via the Alternating Direction Method of MultipliersBoyd et al.#
2011·Foundations and Trends in Machine Learning
Contribution
Unified ADMM as a decomposition method for large-scale convex optimization, splitting a hard problem into easier subproblems solved in alternation.
ADMM dates to the 1970s and had been largely forgotten by the time datasets grew past single machines. Boyd and colleagues showed the method splits a problem into pieces that can be solved on separate machines with only a small vector exchanged between them, which is exactly what distributed learning needs. The monograph is a revival rather than an invention and is cited far more than the original work.
Product Quantization for Nearest Neighbor SearchJegou, Douze and Schmid#
2011·IEEE Transactions on Pattern Analysis and Machine Intelligence
Contribution
Decomposed high-dimensional vectors into subspaces and quantized each independently, compressing a vector to a short code while enabling fast approximate distance computation.
Exact nearest neighbor search in high dimensions degenerates to scanning everything, and storing the vectors themselves exhausts memory before the scan becomes the bottleneck. Jegou and colleagues split each vector into subvectors, quantize each independently, and compute approximate distances from a small lookup table. The compression is aggressive enough that billion-scale search fits on one machine.
ImageNet Classification with Deep Convolutional Neural NetworksKrizhevsky, Sutskever and Hinton#
2012·NeurIPS, reprinted in Communications of the ACM 2017
Contribution
Won the ImageNet challenge by a wide margin using a deep convolutional network trained on GPUs, restarting industrial interest in neural networks.
Convolutional networks had worked on small images for two decades without scaling, and the ImageNet competition supplied a million labeled photographs. Krizhevsky wrote the convolution kernels for two GPUs by hand and combined depth with rectified linear units and dropout. The error rate fell by roughly ten points below the next entry, and computer vision abandoned hand-designed features within a year.
Poisoning Attacks against Support Vector MachinesBiggio, Nelson and Laskov#
2012·ICML
Contribution
Showed that injecting a small number of crafted training points shifts the SVM decision boundary enough to degrade test accuracy.
Adversarial work had focused on evading a trained classifier at test time, leaving the training phase assumed to be safe. Biggio and colleagues showed an attacker who can insert a small number of crafted training points can move the decision boundary substantially, using the gradient of test error with respect to the injected point. The paper opened the study of attacks on the data supply rather than the model.
Efficient Estimation of Word Representations in Vector SpaceMikolov et al.#
2013·ICLR Workshop
Contribution
Showed that simple log-bilinear models trained on large corpora produce word vectors whose arithmetic captures semantic and syntactic regularities.
Neural language models produced useful word vectors as a byproduct, at a training cost that limited them to small vocabularies. Mikolov's group stripped the hidden layer entirely, leaving a shallow model that trains on billions of words in a day. The resulting vectors turned out to encode analogies as offsets, which was not designed and drove most of the paper's attention.
On the Importance of Initialization and Momentum in Deep LearningSutskever et al.#
2013·ICML
Contribution
Showed that carefully tuned Nesterov momentum matches or exceeds more complex adaptive methods on deep learning benchmarks.
Deep networks were widely believed to require second-order methods or layerwise pretraining, since plain stochastic gradient descent was thought to stall. Sutskever and colleagues showed that careful initialization combined with a well-tuned momentum schedule matches those methods, and explained the connection between classical momentum and Nesterov's variant. The practical conclusion was that the optimizer was never the obstacle.
Playing Atari with Deep Reinforcement LearningMnih et al.#
2013·NeurIPS Workshop
Contribution
Showed that a convolutional network trained with Q-learning from raw pixels learns to play Atari games, outperforming previous approaches on six of seven games and a human expert on three.
Reinforcement learning with function approximation was known to diverge, and combining it with a deep network was considered unwise. The DeepMind group stabilized it with a replay buffer that breaks the correlation between consecutive samples. One architecture then learned seven games from raw pixels with no per-game tuning.
Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging SchemesShamir and Zhang#
2013·ICML
Contribution
Proved that the last iterate of stochastic gradient descent with step sizes proportional to one over the square root of the step count has expected suboptimality O(log(T)/sqrt(T)) after T steps on non-smooth convex problems.
Stochastic gradient descent had been analyzed for decades, but the classical analysis usually assumed a smooth objective, which excludes non-smooth losses such as the hinge loss of a support vector machine. Shamir and Zhang analyzed the non-smooth case directly, bounded the final iterate rather than an average of the trajectory, and gave a running-average scheme that reaches the optimal rate.
Showed that in a service fanning out to many machines, overall latency is governed by the slowest responses rather than the average, and gave techniques that bound tail latency without reducing per-machine variability.
A service that calls a hundred backends returns only when the slowest returns, so a rare slow response becomes the common case at the top level. Dean and Barroso quantified this and described the techniques Google uses against it, including hedged requests, micropartitioning, and selective replication. The paper reframed latency as a distribution to be shaped rather than an average to be reduced.
A Fast, Minimal Memory, Consistent Hash AlgorithmJohn Lamping and Eric Veach#
2014·arXiv preprint
Contribution
Introduced jump consistent hash, which needs no stored lookup table and runs in expected logarithmic time, for buckets numbered consecutively from zero.
Ring-based consistent hashing stores many points per server to spread keys evenly. Lamping and Veach considered data stores whose shard identifiers fill a consecutive range, which let them replace the ring with a reproducible sequence of jumps computed from the key.
Auto-Encoding Variational BayesDiederik Kingma and Max Welling#
2014·ICLR
Contribution
Introduced a reparameterization trick that makes the variational bound on a latent-variable model differentiable and trainable by stochastic gradient descent.
Variational inference required a tractable expectation, which rules out any approximate posterior parameterized by a neural network. Kingma and Welling supplied the reparameterization trick, writing the sample as a deterministic function of the parameters and independent noise so gradients pass through it. That single change made variational inference compatible with backpropagation and gave rise to the variational autoencoder.
Dropout: A Simple Way to Prevent Neural Networks from OverfittingSrivastava et al.#
2014·JMLR
Contribution
Showed that randomly zeroing hidden units during training acts as an implicit ensemble and reduces overfitting across architectures.
Averaging many networks reduces overfitting reliably and costs many times the training budget. Hinton's group observed that randomly deleting units during each training step approximates that average within a single model, since each step trains a different thinned network sharing weights. The interpretation offered is that units cannot rely on specific collaborators and must be individually useful.
Showed that a generator trained against a discriminator converges to the data distribution at the Nash equilibrium of a minimax game.
Generative models were trained by maximizing likelihood, which requires a tractable normalizing constant and tends to produce blurred samples. Goodfellow proposed replacing the likelihood with a second network trained to distinguish real samples from generated ones, so the objective is supplied by an adversary rather than written down. The formulation gives sharp samples and a training process that is notoriously unstable.
In Search of an Understandable Consensus AlgorithmDiego Ongaro and John Ousterhout#
2014·USENIX ATC
Contribution
Redesigned Paxos into a decomposed protocol with a strong leader, achieving equivalent safety guarantees with a structure that practitioners implement correctly.
Paxos was the standard consensus algorithm and almost nobody could implement it correctly from the paper, so every real system used an undescribed variant. Ongaro and Ousterhout treated understandability as the design constraint and decomposed the problem into leader election, log replication and a safety argument. They evaluated the result by testing whether students who read it could answer questions about it.
Intriguing Properties of Neural NetworksSzegedy et al.#
2014·ICLR
Contribution
Showed that imperceptible perturbations to images cause high-confidence misclassification, revealing that neural network decision boundaries sit close to data points.
Networks that classified images better than any prior method were assumed to have learned something robust about visual structure. Szegedy and colleagues found that an imperceptible perturbation, computed by optimizing against the model, flips the prediction with high confidence, and that the same perturbation often transfers to other models. The finding is still not fully explained.
Majority is not Enough: Bitcoin Mining is VulnerableEyal and Sirer#
2014·Financial Cryptography
Contribution
Showed that strategic block withholding could give a minority Bitcoin mining pool a reward share above its hash-rate share.
Bitcoin's double-spending analysis assumed that most hash power followed the protocol. Eyal and Sirer asked whether miners seeking more revenue had an incentive to follow its block-publication rules, and found that a pool withholding blocks could profit, with a threshold that falls to zero when honest miners favor the pool's blocks in ties.
Sequence to Sequence Learning with Neural NetworksSutskever, Vinyals and Le#
2014·NeurIPS
Contribution
Demonstrated that an encoder-decoder pair of LSTMs translates between languages at competitive quality with no task-specific features.
Translation systems combined a learned language model with separately estimated alignment and phrase tables. Sutskever, Vinyals and Le showed one recurrent network can read a sentence into a fixed vector and another can write the translation out, with no alignment machinery at all. They found reversing the source sentence improved results markedly, a hint that the fixed vector was the bottleneck attention would soon remove.
Adam: A Method for Stochastic OptimizationKingma and Ba#
2015·ICLR
Contribution
Combined per-parameter adaptive step sizes with momentum and bias correction into the optimizer that became the default.
Adaptive methods before Adam either accumulated squared gradients forever, so the effective step size decayed to zero, or ignored the gradient's mean. Kingma and Ba combined exponentially decaying estimates of both first and second moments with a bias correction for the early steps. The method needs almost no tuning, which is why it became the default despite known convergence gaps.
Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate ShiftSergey Ioffe and Christian Szegedy#
2015·ICML
Contribution
Showed that normalizing layer inputs per mini-batch allows higher learning rates and reduces sensitivity to initialization.
Deep networks trained slowly because each layer must adapt to a distribution of inputs that shifts as the layers below it change. Ioffe and Szegedy normalized each layer's activations using the statistics of the current mini-batch, with learned scale and shift so nothing is lost. The stated explanation has since been contested, while the empirical effect on trainable depth is not in dispute.
Distilling the Knowledge in a Neural NetworkHinton, Vinyals and Dean#
2015·NeurIPS 2014 Deep Learning Workshop
Contribution
Showed that training a small network to match the soft output distribution of a large network transfers most of its performance.
An ensemble outperforms any single model and costs proportionally more to serve, which is a problem when serving dominates the budget. Hinton, Vinyals and Dean showed a small network trained on the ensemble's full output distribution, rather than the hard labels, recovers much of the accuracy. The relative probabilities assigned to wrong classes carry the information, which is why softening them helps.
Explaining and Harnessing Adversarial ExamplesGoodfellow, Shlens and Szegedy#
2015·ICLR
Contribution
Showed that small perturbations aligned with the gradient of the loss reliably fool neural networks, and proposed adversarial training as a defense.
The first adversarial examples paper left the cause open, with speculation that they were rare pockets in a highly nonlinear function. Goodfellow, Shlens and Szegedy argued the opposite: the models are too linear, and in high dimensions many small aligned perturbations sum to a large change in the output. The linear view yields a one-step attack cheap enough to use during training.
Human-Level Control through Deep Reinforcement LearningMnih et al.#
2015·Nature
Contribution
Stabilized deep Q-learning with a target network and experience replay, achieving human-level play on 49 Atari games from raw pixels.
The Atari result from two years earlier was a workshop paper covering seven games with limited analysis. This version extends to forty-nine games with the same architecture and hyperparameters throughout, comparing against a professional human tester on each. Holding the configuration fixed across games is the claim, since per-game tuning would make the generality meaningless.
Neural Machine Translation by Jointly Learning to Align and TranslateBahdanau, Cho and Bengio#
2015·ICLR
Contribution
Introduced an attention mechanism that lets a decoder attend to different parts of the source sentence at each step, removing the fixed-length bottleneck.
Encoding an entire sentence into one fixed vector degrades badly as sentences lengthen, which the reversal trick in earlier work had only partly masked. Bahdanau, Cho and Bengio let the decoder compute a weighted sum over all encoder states at each output step, learning the weights jointly. The alignments the model produced were interpretable, and the mechanism became the basis of the transformer.
The Ladder: A Reliable Leaderboard for Machine Learning CompetitionsBlum and Hardt#
2015·ICML
Contribution
Introduced the Ladder leaderboard mechanism and proved accuracy guarantees for a hidden holdout set that participants query adaptively through repeated submissions.
Competition leaderboards score each submission on a hidden holdout, and every score returned leaks a little of that holdout back to the participants, who then overfit it. Existing safeguards were heuristics such as limiting resubmissions and rounding the reported score. Blum and Hardt defined leaderboard accuracy formally and gave a mechanism that stays reliable under adaptive submissions.
Derived a policy-improvement bound and proposed a practical trust-region algorithm based on approximations to the theoretically justified scheme.
A small parameter update can change a policy substantially, motivating a bound expressed in policy distributions rather than parameter distance. Schulman and colleagues derived a monotonic-improvement scheme and approximated it to obtain TRPO. The sampled objective, practical divergence constraint, and approximate optimization do not inherit an unconditional guarantee that every update improves expected return.
Variational Inference with Normalizing FlowsRezende and Mohamed#
2015·ICML
Contribution
Showed that composing a sequence of invertible transformations lets variational inference use arbitrarily flexible posterior approximations.
Variational posteriors were nearly always taken to be fully factorized Gaussians, which cannot represent correlation or multiple modes no matter how much data is available. Rezende and Mohamed apply a sequence of invertible transformations to a simple distribution, tracking the density exactly through the change of variables formula. The construction trades a restrictive family for a computational constraint that each transformation have a cheap Jacobian determinant.
Very Deep Convolutional Networks for Large-Scale Image RecognitionKaren Simonyan and Andrew Zisserman#
2015·ICLR
Contribution
Showed that stacking many 3x3 convolutional layers to 16-19 depth improves image classification over shallower architectures with larger filters.
Architectures at the time mixed filter sizes and layer types in ways that made it hard to attribute performance to any one choice. Simonyan and Zisserman fixed every convolution at three by three and varied only depth, showing that a stack of small filters matches a larger receptive field with fewer parameters and more nonlinearity. The resulting networks were widely reused as feature extractors long after they stopped being competitive.
Asynchronous Methods for Deep Reinforcement LearningMnih et al.#
2016·ICML
Contribution
Showed that running multiple agents in parallel on CPUs stabilizes training without experience replay, matching GPU-trained DQN at lower cost.
Deep Q-learning needed a large replay buffer to decorrelate samples, which restricts it to off-policy methods and consumes memory. Mnih and colleagues ran many actors in parallel on separate copies of the environment, which decorrelates the updates by construction rather than by storage. The result trained faster on a single multicore CPU than the earlier method did on a GPU.
Cataloged five categories of failure in reinforcement learning agents deployed in the real world, including reward hacking and distributional shift.
Safety discussion at the time was dominated by long-range speculation that gave engineers nothing to work on. Amodei and colleagues restated the concerns as five research problems in accident risk, including reward gaming, safe exploration and distributional shift, each with a concrete experimental setting. The paper is largely responsible for safety becoming an empirical subfield.
Deep Residual Learning for Image RecognitionHe, Zhang, Ren and Sun#
2016·CVPR
Contribution
Showed that identity shortcut connections let networks of far greater depth train without degradation.
Adding layers past a certain depth made training error worse, which cannot be an overfitting problem since a deeper network can always represent a shallower one by learning identity maps. He and colleagues concluded that the optimizer cannot find those identity maps, and added them to the architecture as skip connections. Networks jumped from tens of layers to over a hundred immediately.
Normalized activations across the feature dimension within each example, removing the batch dependence that made batch normalization unsuitable for recurrent and variable-length architectures.
Batch normalization computes statistics across the mini-batch, which fails when the batch is small and has no clean definition for a recurrent network whose sequence lengths vary. Ba, Kiros and Hinton normalize across the features of a single example instead, making the computation independent of batch size and identical at training and inference. Transformers use it, or its RMSNorm simplification, for exactly these reasons.
Mastering the Game of Go with Deep Neural Networks and Tree SearchSilver et al.#
2016·Nature
Contribution
Defeated a professional Go player by combining convolutional policy and value networks with Monte Carlo tree search.
Go had resisted the search techniques that produced superhuman chess play because the branching factor is an order of magnitude larger and no good evaluation function was known. Silver's group learned the evaluation function and a move prior from data and self-play, then used them to focus a Monte Carlo tree search. The system beat Lee Sedol in 2016.
Neural Machine Translation of Rare Words with Subword UnitsSennrich, Haddow and Birch#
2016·ACL
Contribution
Introduced byte pair encoding for neural machine translation, allowing open-vocabulary generation by segmenting words into frequent subword units.
Neural translation systems used a fixed vocabulary and replaced everything outside it with an unknown token, which fails on names, compounds, and morphologically rich languages. Sennrich, Haddow and Birch adapted byte pair encoding, a compression scheme, to merge frequent character pairs into a vocabulary of subwords. Every large language model still tokenizes this way.
TensorFlow: A System for Large-Scale Machine LearningAbadi et al.#
2016·OSDI
Contribution
Described a dataflow system that compiles computation graphs to heterogeneous hardware, becoming the first widely adopted framework for distributed training.
Its predecessor at Google scaled well but hard-coded the layered structure of neural networks, which made new architectures awkward. TensorFlow represents the computation as a dataflow graph of stateful operations, so that the same description runs on one machine or a cluster and differentiates automatically. The static graph gave good distribution and a poor debugging experience, which is the tradeoff PyTorch later reversed.
XGBoost: A Scalable Tree Boosting SystemTianqi Chen and Carlos Guestrin#
2016·KDD
Contribution
Introduced sparsity-aware split finding and column-block compression that made gradient boosting scale to billions of examples on a single machine.
Gradient boosting was well understood in theory and every implementation was slow enough to limit the problems it could touch. Chen and Guestrin contributed a sparsity-aware split finder, a quantile sketch for approximate splits, and a cache-conscious data layout. The system won a large fraction of tabular competitions for several years and remains a strong baseline.
A Deep Reinforcement Learning Framework for the Financial Portfolio Management ProblemJiang, Xu, and Liang#
2017·arXiv preprint
Contribution
Formulated portfolio allocation as a reinforcement learning problem and showed that a policy-gradient agent outperformed traditional methods on cryptocurrency markets.
Applying reinforcement learning to trading normally means discretizing the action space, which does not fit a continuous allocation across assets. Jiang, Xu and Liang designed a network that outputs portfolio weights directly, with an identical sub-network applied per asset so the model does not depend on asset ordering or count. The results are on cryptocurrency data over short backtests and should be read as a framework rather than a strategy.
Argued that datacenter hardware and software handle nanosecond and millisecond events well but not microsecond ones, and showed software overheads turning a 2-microsecond network round trip into nearly 100.
Processors hide nanosecond stalls with prefetching and out-of-order execution, and operating systems hide millisecond disk waits by switching threads. Fast datacenter networks and flash storage created events in between, where neither technique works. Barroso and colleagues named the gap and measured how quickly software overheads waste fast hardware.
Showed that a model built only from attention and feedforward layers matched recurrent translation systems while parallelizing across sequence positions.
Attention had been added to recurrent networks as an improvement, and recurrence forced sequential computation that no amount of hardware could parallelize. Vaswani and seven co-authors removed the recurrence and kept only the attention, adding positional encodings to restore order information. Training became parallel across sequence positions, which is the reason models could then grow by orders of magnitude.
Bringing the Web up to Speed with WebAssemblyHaas et al.#
2017·PLDI
Contribution
Presented a portable, validated stack-machine format with a bounds-checked linear memory for running low-level code in a sandbox.
C and C++ applications needed a portable browser target that kept unsafe memory operations away from the host. Haas and colleagues designed WebAssembly around a compact instruction format and an isolated linear memory in which every access is checked against the memory size, so a buggy or exploited program can corrupt only its own data.
Deep Reinforcement Learning from Human PreferencesChristiano et al.#
2017·NeurIPS
Contribution
Showed that a reward model trained on human comparisons can guide a reinforcement learning agent without a hand-specified reward function.
Many tasks have no reward function anyone can write down, and hand-specified proxies get gamed. Christiano and colleagues showed that asking humans to compare short trajectory segments, rather than score them, gives enough signal to fit a reward model, and that about 700 comparisons suffice for simulated locomotion tasks and a few thousand for Atari games. This is the procedure later scaled up to align language models.
Kolmogorov Complexity and Algorithmic RandomnessAlexander Shen, Vladimir Uspensky and Nikolai Vereshchagin#
2017·American Mathematical Society
Contribution
Gave a comprehensive treatment of Kolmogorov complexity as an incomputable but foundational measure of the information content of individual objects.
Algorithmic information theory had accumulated results across four decades in papers written in several languages and notational conventions. This book gives a unified treatment of complexity, randomness deficiency and their relations to information theory and computability. It is the standard reference for the claim that randomness means incompressibility.
Neural Architecture Search with Reinforcement LearningZoph and Le#
2017·ICLR
Contribution
Used a recurrent controller trained with reinforcement learning to generate network descriptions, producing a CIFAR-10 architecture that matched the best hand-designed ones at 3.65 percent test error.
Architectures were designed by researchers trying variations by hand, a process that is slow and hard to describe as science. Zoph and Le trained a recurrent controller to emit architecture descriptions and rewarded it with the validation accuracy of the trained result. The discovered networks matched hand-designed ones at a compute cost measured in thousands of GPU-days, which set off the search for cheaper methods.
Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts LayerShazeer et al.#
2017·ICLR
Contribution
Introduced a trainable gating network that routes each token to a subset of expert networks, scaling model capacity without proportional compute cost.
Model quality improves with parameter count and so does the cost of every forward pass, which ties capacity to compute. Shazeer and colleagues inserted a layer holding thousands of expert subnetworks with a gate that activates only a few per token, so capacity grows while per-token cost stays roughly fixed. Making the routing balanced and trainable was the hard part and needed an explicit load-balancing loss.
Poincaré Embeddings for Learning Hierarchical RepresentationsNickel and Kiela#
2017·NeurIPS
Contribution
Showed that embedding in hyperbolic space rather than Euclidean space captures hierarchical structure with far fewer dimensions.
Embedding a tree in Euclidean space requires dimension growing with depth, because the number of nodes grows exponentially and the available volume does not. Nickel and Kiela used hyperbolic space, where volume grows exponentially with radius, so a hierarchy fits in very few dimensions. Five-dimensional hyperbolic embeddings outperformed Euclidean ones with two hundred.
Proximal Policy Optimization AlgorithmsSchulman et al.#
2017·arXiv preprint
Contribution
Introduced a clipped surrogate objective that discourages large policy updates without computing second-order information, becoming the default on-policy method.
Trust region policy optimization worked but required a constrained optimization with second-order information at every update, which is complicated and expensive. Schulman and colleagues replaced the hard constraint with a clipped objective that simply removes the incentive to move too far, computable with ordinary first-order methods. It became the default policy gradient algorithm, including for reinforcement learning from human feedback.
Replaced the Jensen-Shannon divergence in GAN training with the Wasserstein distance, giving a loss that correlates with sample quality and stabilizes training.
Adversarial training failed in ways nobody could diagnose, since the loss carried no information about sample quality and the gradient vanished when the discriminator got too good. Arjovsky, Chintala and Bottou traced this to the divergence being minimized and substituted the earth mover distance, which stays informative when the distributions do not overlap. The critic loss then correlates with sample quality, which made debugging possible for the first time.
A General Reinforcement Learning Algorithm that Masters Chess, Shogi, and Go through Self-PlaySilver et al.#
2018·Science
Contribution
Showed that a single neural-network architecture trained from self-play alone, with no domain knowledge beyond the rules, masters chess, shogi, and Go.
AlphaGo used human game records, Go-specific input features and handcrafted rollouts, so it was unclear how much came from the method and how much from the domain. AlphaZero removed all of it, learning from self-play alone with only the rules supplied. The same algorithm and hyperparameters then reached superhuman play in three different games.
Improving Language Understanding by Generative Pre-TrainingRadford et al.#
2018·OpenAI technical report
Contribution
Showed that unsupervised pre-training of a transformer decoder on a large corpus followed by supervised fine-tuning transfers to diverse NLP tasks.
Transfer learning in language had been limited to word embeddings, with the rest of each model trained from scratch per task. Radford and colleagues pretrained a transformer decoder on unlabeled text with a next-token objective, then fine-tuned the whole model with a task-specific head. The recipe of general pretraining followed by cheap adaptation is the one the field still uses.
Demonstrated mixed-precision training with FP16 computations, FP32 master weights, and loss scaling while preserving model accuracy on the evaluated tasks.
Half-precision tensor values occupy two bytes instead of four, but FP32 master weights add another parameter copy. An FP16 weight plus its FP32 master requires six bytes, compared with four for one FP32 weight; this parameter-only count excludes gradients, activations, and optimizer state. Total training memory and speed depend on the workload and hardware, rather than following a universal factor of two.
UMAP: Uniform Manifold Approximation and Projection for Dimension ReductionMcInnes, Healy and Melville#
2018·arXiv preprint
Contribution
Derived a dimension reduction algorithm from Riemannian geometry and fuzzy topology that preserves both local and global structure faster than t-SNE.
The dominant nonlinear embedding method was slow on large datasets and had no theory saying what it preserves. McInnes, Healy and Melville derived their method from a Riemannian and category-theoretic argument, arriving at an algorithm that runs much faster and retains more global structure. It became the default in single-cell biology within about two years.
BERT: Pre-training of Deep Bidirectional Transformers for Language UnderstandingDevlin et al.#
2019·NAACL
Contribution
Showed that masked language modeling over both directions yields representations that, after fine-tuning, advance the state of the art on eleven NLP benchmarks.
Language model pretraining was left to right, so each token's representation could not use the words that follow it, which is a real handicap for understanding tasks. Devlin and colleagues masked a fraction of the tokens and trained the model to recover them, which permits attention in both directions. Fine-tuning the result advanced eleven benchmarks at once and made pretraining standard practice.
Deep Double Descent: Where Bigger Models and More Data HurtNakkiran et al.#
2019·ICLR 2020
Contribution
Documented the double-descent curve where test error rises then falls again as model capacity increases past the interpolation threshold.
Classical theory says test error rises once a model can fit the training data exactly, and practitioners were routinely training far past that point with good results. Nakkiran and colleagues showed error rises to a peak at the interpolation threshold and then falls again, and that the same non-monotonicity appears in training time and dataset size. More data can hurt in a specific regime, which is not something the standard account permits.
Generating Long Sequences with Sparse TransformersChild et al.#
2019·Venue not recorded
Contribution
Introduced sparse factorizations of the attention matrix that reduce the cost from quadratic to O(n sqrt(n)), enabling generation of longer sequences.
Attention costs grow with the square of sequence length, which caps context at a few thousand tokens regardless of available memory. Child and colleagues restrict each position to attend to a structured subset chosen so that any two positions connect within a few hops. The paper is the origin of the long line of work on sparse and linear attention.
Language Models Are Unsupervised Multitask LearnersRadford et al.#
2019·OpenAI technical report
Contribution
Showed that a billion-parameter-scale transformer trained on web text performs a range of NLP tasks in a zero-shot setting without any task-specific training.
The prevailing recipe pretrained once and then fine-tuned per task with labeled data. Radford and colleagues observed that a large enough model trained only to predict the next token performs several tasks when the task is described in the prompt, with no gradient updates. OpenAI initially withheld the largest model, which was the first public argument about staged release.
Proposed a structured reporting format for trained models that states intended use, performance across subgroups, and limitations.
Models were released with aggregate accuracy figures that concealed how differently they behave across groups, and there was no convention for saying more. Mitchell and colleagues proposed a short standardized document reporting intended use, out-of-scope use and disaggregated performance. The format is now widely used on model repositories and anticipates the documentation duties of the EU AI Act.
PyTorch: An Imperative Style, High-Performance Deep Learning LibraryPaszke et al.#
2019·NeurIPS
Contribution
Showed that an eager-mode, tape-based autodiff system can match the performance of graph-compiled frameworks while providing a standard Python debugging experience.
Frameworks built on static graphs were fast and awkward, since the model had to be fully specified before it could be run or inspected. PyTorch builds the graph as the code executes, so ordinary control flow and debuggers work, and the paper's contribution is showing this costs little performance. Research adoption moved almost entirely within about two years.
Root Mean Square Layer NormalizationZhang and Sennrich#
2019·NeurIPS
Contribution
Showed that normalizing by the root mean square alone, without the mean subtraction of layer normalization, gave comparable quality while cutting running time by 7 to 64 percent across the models tested.
Layer normalization stabilized training, but its computational overhead slowed the underlying network, recurrent networks in particular. Zhang and Sennrich hypothesized that its re-centering invariance was dispensable and kept only the re-scaling, and the simpler form was later adopted widely in large language models.
The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural NetworksFrankle and Carbin#
2019·ICLR
Contribution
Showed that a randomly initialized dense network contains a sparse subnetwork that, trained in isolation from the same initialization, reaches comparable accuracy in comparable time.
Networks can be pruned to a small fraction of their weights after training, and the same sparse architecture trained from scratch fails. Frankle and Carbin found that it succeeds if the surviving weights are reset to their original random values rather than reinitialized, suggesting the dense network contains a subnetwork that was well positioned from the start. Whether this holds at large scale is still contested.
2020s
Denoising Diffusion Probabilistic ModelsHo, Jain and Abbeel#
2020·NeurIPS
Contribution
Showed that iteratively denoising a sample from Gaussian noise following a learned reverse process generates images competitive with GANs.
Diffusion models had been proposed in 2015 and produced samples well short of adversarial methods. Ho, Jain and Abbeel reparameterized the objective so the network predicts the added noise rather than the denoised image, which turns training into a simple regression. Sample quality became competitive with GANs without the training instability, and the approach now dominates image generation.
Dense Passage Retrieval for Open-Domain Question AnsweringKarpukhin et al.#
2020·EMNLP
Contribution
Showed that a dual-encoder trained on question-passage pairs retrieves passages more accurately than BM25 for open-domain question answering.
Retrieval for question answering relied on term overlap, which fails when the question and the passage use different words for the same thing. Karpukhin and colleagues trained separate encoders for questions and passages so that matching pairs land near each other, using in-batch negatives to make training efficient. Dense retrieval beat the term-frequency baseline decisively and became the standard first stage.
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World GraphsYury Malkov and Dmitry Yashunin#
2020·IEEE Transactions on Pattern Analysis and Machine Intelligence
Contribution
Gave a graph-based index for approximate nearest neighbor search that achieves sub-linear query time while maintaining high recall at billion scale.
Tree and hash based indexes degrade toward brute force as dimension rises, and earlier graph methods had no way to make long jumps early in a search. Malkov and Yashunin stack proximity graphs at several scales so search descends from coarse to fine, giving logarithmic behavior in practice. The index underlies most production vector databases.
Language Models are Few-Shot LearnersBrown et al.#
2020·NeurIPS
Contribution
Showed that a 175-billion-parameter autoregressive model performs tasks from a few examples placed in the prompt, without gradient updates.
The previous model had hinted that scale alone produces task generality, on evidence too thin to settle the question. This paper trains a model roughly a hundred times larger and evaluates it on dozens of tasks given only a task description and a handful of examples in the prompt. Performance improves smoothly with scale on most tasks and discontinuously on a few, which set off the argument about emergent abilities.
Mastering Atari, Go, Chess and Shogi by Planning with a Learned ModelSchrittwieser et al.#
2020·Nature
Contribution
Showed that learning a dynamics model from interaction alone, without access to the game rules, matches the performance of algorithms given the true model.
Planning methods needed a simulator of the environment, which exists for board games and not for most problems. Schrittwieser and colleagues learn a model in a latent space trained only to predict reward, value, and policy, discarding any requirement that it reconstruct observations. Planning with a model that cannot render the world still works, because it only needs to be accurate about what planning uses.
Retrieval-Augmented Generation for Knowledge-Intensive NLP TasksLewis et al.#
2020·NeurIPS
Contribution
Combined a dense retriever with a seq2seq generator trained end-to-end, letting the model condition on documents retrieved at inference time.
Facts stored in a model's weights cannot be updated without retraining and cannot be attributed to a source. Lewis and colleagues attached a dense retriever to a generator and trained them jointly, so the model conditions on documents fetched at inference time. Knowledge becomes an editable index rather than a parameter, which is the architecture most production systems now use.
Scaling Laws for Neural Language ModelsKaplan et al.#
2020·Venue not recorded
Contribution
Found power-law relationships between test loss and model size, dataset size, and compute, with model size yielding the steepest returns.
Whether a larger model was worth training was decided by intuition and by whatever budget was available. Kaplan and colleagues varied model size, dataset size and compute over several orders of magnitude and found loss falls as a power law in each, with the exponents stable enough to extrapolate. Turning capability into a forecastable quantity changed how laboratories plan.
Later qualified
Hoffmann et al. 2022 found the original prescription undertrained on data relative to parameters, shifting the optimal allocation toward more tokens. Pearce and Song 2024 and Porian et al. 2024 traced the gap to counting only non-embedding parameters at small scale, uncounted output-layer compute, a fixed warmup too long for small models and untuned optimizer settings, rather than chiefly to the learning rate decay Hoffmann et al. suspected.
Specification Gaming: The Flip Side of AI IngenuityKrakovna et al.#
2020·DeepMind blog
Contribution
Collected and categorized dozens of examples in which reinforcement learning agents exploit reward specifications in unintended ways.
Reward functions written by careful people were repeatedly being satisfied in ways nobody intended, and each case was treated as an isolated bug. Krakovna and colleagues collected dozens of instances and argued they share a cause: the objective is a proxy, and optimization pressure finds the gap between the proxy and the intent. The list is maintained publicly and continues to grow.
The Next Decade in AI: Four Steps Towards Robust Artificial IntelligenceGary Marcus#
2020·Venue not recorded
Contribution
Argued that current deep learning lacks compositional generalization and proposed hybrid neuro-symbolic architectures as a path to robustness.
Marcus has argued for two decades that scaling statistical learning will not produce reliable reasoning, and this is the constructive version of the argument. He proposes hybrid systems with explicit symbolic structure, causal models and knowledge representation, rather than only criticizing what exists. The paper is worth reading as the strongest statement of a position the field has largely bet against.
ZeRO: Memory Optimizations Toward Training Trillion Parameter ModelsRajbhandari et al.#
2020·SC
Contribution
Showed that data-parallel training can partition optimizer states and gradients across devices instead of replicating them, cutting per-device model-state memory with no increase in communication volume.
Data parallelism kept a full copy of the optimizer states, gradients and parameters on every device, and model parallelism, which splits the model instead, lost efficiency quickly beyond a single node. Rajbhandari and colleagues partitioned the optimizer states and gradients across the data-parallel group at no extra communication volume, and analyzed a third stage that partitions the parameters too, for half again the volume. The implementation covered the first two stages plus fixes for activation memory, temporary buffers and fragmentation, and it trained models of up to 13 billion parameters without model parallelism and, combined with it, models of up to 170 billion on 400 GPUs.
A Mathematical Framework for Transformer CircuitsElhage et al.#
2021·Anthropic research
Contribution
Showed that attention heads in small attention-only transformers compose into interpretable circuits that perform specific algorithmic operations.
Interpretability work had mostly examined individual neurons and attention maps, which does not compose into an account of how a computation is performed. Elhage and colleagues rewrote small attention-only transformers in a form where paths through the residual stream can be read off algebraically, which makes specific circuits identifiable. Induction heads, the mechanism behind in-context learning, were found this way.
An Image Is Worth 16x16 Words: Transformers for Image Recognition at ScaleDosovitskiy et al.#
2021·ICLR
Contribution
Showed that a pure transformer applied to sequences of image patches matches or exceeds convolutional networks on image classification when pre-trained on large data.
Convolution encodes locality and translation equivariance, which was assumed to be necessary for vision rather than merely helpful. Dosovitskiy and colleagues cut images into patches and fed them to a plain transformer with no visual inductive bias at all. It underperforms convolutional networks on medium datasets and overtakes them given enough data, which is the paper's actual finding.
Proposed a standardized documentation template for datasets that records motivation, composition, collection, and intended use.
Datasets circulated with a name, a download link and a citation, so downstream users could not tell how the data was collected or who is in it. Gebru and colleagues borrowed the datasheet convention from electronic components and proposed a standard questionnaire covering motivation, composition, collection, and recommended uses.
Decision Transformer: Reinforcement Learning via Sequence ModelingChen et al.#
2021·NeurIPS
Contribution
Cast offline reinforcement learning as autoregressive sequence prediction over states, actions, and returns, matching or exceeding purpose-built offline RL methods.
Offline reinforcement learning struggles because value estimates on actions absent from the data are unconstrained and tend to be wildly optimistic. Chen and colleagues sidestep the value function entirely, treating trajectories as sequences and training a transformer to predict the next action given a desired return. Conditioning on a high return at inference time then produces high-return behavior, with no dynamic programming anywhere.
Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LMNarayanan et al.#
2021·SC
Contribution
Showed that tensor parallelism works best inside one multi-GPU server and pipeline parallelism across servers, and combined the two with data parallelism to run training iterations of a trillion-parameter GPT model on 3,072 GPUs at 52 percent of theoretical peak per GPU.
Language models had outgrown the memory of one multi-GPU server, and naive use of tensor and pipeline parallelism scaled poorly to thousands of GPUs: the all-reduce that tensor parallelism needs had to cross links between servers slower than NVLink, and pipeline parallelism left devices idle in the pipeline bubble. Narayanan and colleagues kept tensor parallelism inside a server, spread pipeline stages across servers, and added an interleaved pipeline schedule that could raise throughput by 10 percent or more. They found that poor combinations of the two could halve throughput, even with a fast network between servers.
Highly Accurate Protein Structure Prediction with AlphaFoldJumper et al.#
2021·Nature
Contribution
Predicted protein structures from amino acid sequence at experimental accuracy, removing the crystallography bottleneck that had gated structural biology.
Predicting a protein's shape from its sequence had been a defining open problem in biology for fifty years, with slow progress measured by a biennial competition. AlphaFold combined evolutionary couplings from related sequences with a structure module that reasons directly in three-dimensional space, reaching accuracy comparable to experimental methods for most targets. The predicted structures for essentially every known protein were released publicly.
Learning Transferable Visual Models from Natural Language SupervisionRadford et al.#
2021·ICML
Contribution
Showed that contrastive pre-training on 400 million image-text pairs produces a visual representation that transfers to downstream tasks without any task-specific training.
Image classifiers were trained on fixed label sets, so recognizing a new category required new labeled data. Radford and colleagues trained on image and caption pairs collected from the web, learning a shared space where matching pairs align. Classification then becomes a comparison against text descriptions, which allows categories the model was never trained on.
Measuring Massive Multitask Language UnderstandingHendrycks et al.#
2021·ICLR
Contribution
Introduced a benchmark of 57 subjects from STEM to humanities that measures knowledge and reasoning across a broad range of difficulty.
Existing benchmarks were being saturated within months of release, which made them useless for tracking progress. Hendrycks and colleagues assembled examination questions across fifty-seven subjects from elementary through professional level, testing knowledge that cannot be acquired from surface patterns. It became the standard headline number and has since been substantially saturated in turn.
MLIR: A Compiler Infrastructure for the End of Moore's LawLattner et al.#
2021·CGO
Contribution
Introduced a multi-level intermediate representation with user-defined dialects, allowing domain-specific optimizations at the abstraction level where the relevant structure is visible.
Machine learning frameworks each built their own compiler stack, and the gap between a tensor graph and machine code was too wide for one intermediate representation to span. MLIR allows multiple dialects to coexist and be lowered progressively, so domain-specific optimization happens at the level where the information exists. It is now the backbone of TensorFlow, JAX and several accelerator toolchains.
On the Dangers of Stochastic Parrots: Can Language Models Be Too Big?Bender et al.#
2021·FAccT
Contribution
Documented the environmental and social risks of scaling language models, including the costs of compute, the biases in training data, and the gap between fluency and understanding.
The prevailing direction was to train on more web text with more parameters, on evidence that loss keeps falling. Bender and colleagues cataloged the costs on the other side: environmental burden, the concentration of dominant viewpoints in scraped data, and the risk of fluent text with no grounding being taken as understanding. Google's attempt to suppress the paper led to the departure of two of its authors and made it far more widely read.
RoFormer: Enhanced Transformer with Rotary Position EmbeddingSu et al.#
2021·arXiv preprint
Contribution
Introduced rotary position embedding, which encodes absolute position by rotating query and key vectors so that attention scores depend only on relative position.
Absolute position embeddings do not extrapolate past the training length and learned relative schemes add cost to every attention computation. Su and colleagues encode position as a rotation applied inside attention, chosen so the dot product between a query and a key depends only on their separation. The encoding is applied without extra parameters and is now standard in large language models.
The Pile: An 800GB Dataset of Diverse Text for Language ModelingGao et al.#
2021·Venue not recorded
Contribution
Assembled and documented a large open pretraining corpus from 22 named sources, making the composition of training data inspectable rather than proprietary.
Training corpora at the frontier were proprietary, so nobody outside those laboratories could reproduce or audit a result. Gao and colleagues assembled twenty-two documented sources spanning code, legal filings, papers, and dialogue, deliberately weighting toward diversity rather than raw web scale. It was the standard open corpus for several years and its copyright status has since been litigated.
Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database ServiceElhemali et al.#
2022·USENIX ATC
Contribution
Described how DynamoDB partitions tables, replicates each partition through a Multi-Paxos replication group, and changed over a decade of operation to keep performance predictable at any scale.
Dynamo, Amazon's first NoSQL database, was single-tenant, and each team that used it ran its own installation, so Amazon engineers came to prefer managed services such as S3 and SimpleDB even where Dynamo fit their needs better. DynamoDB, launched in 2012, combined Dynamo's incremental scalability and predictable performance with SimpleDB's ease of administration, consistency and table-based data model. The paper reports a peak of 89.2 million requests per second during the 66-hour Prime Day event in 2021.
BLOOM: A 176B-Parameter Open-Access Multilingual Language ModelLe Scao et al.#
2022·Venue not recorded
Contribution
Trained and released a 176-billion-parameter multilingual model together with its data pipeline and governance process, showing that a frontier-scale run could be conducted as an open collaboration.
Frontier models were English-centric and released, if at all, behind an API. BLOOM was built by roughly a thousand researchers coordinating in the open over a year, covering forty-six natural languages, with the data governance and the training decisions documented as they were made. The process is as much the contribution as the model.
Chain-of-Thought Prompting Elicits Reasoning in Large Language ModelsWei et al.#
2022·NeurIPS
Contribution
Showed that prompting a model to produce intermediate reasoning steps before answering improves performance on arithmetic, commonsense, and symbolic tasks.
Large models failed at multi-step arithmetic and logic in ways that scale alone was not fixing. Wei and colleagues found that including worked reasoning in the few-shot examples, so the model writes out intermediate steps before answering, produces large gains that appear only above a certain model size. The prompting change costs nothing and revealed capability that was already present.
Compute Trends Across Three Eras of Machine LearningSevilla et al.#
2022·Venue not recorded
Contribution
Measured training compute for 123 milestone systems and identified distinct growth regimes, separating the pre-2010 trend from the deep learning era that followed.
Claims about compute doubling times were circulating with a single often-cited figure and little underlying data. Sevilla and colleagues estimated training compute for 123 milestone systems across seventy years and identified distinct regimes, with a sharp break around 2010 and a separate faster-growing frontier of large-scale models. The dataset is public, which is most of the paper's value.
Constitutional AI: Harmlessness from AI FeedbackBai et al.#
2022·Venue not recorded
Contribution
Separated supervised learning on model-revised responses from reinforcement learning on AI-generated harmlessness preferences, while keeping human labels for helpfulness.
Reinforcement learning from human feedback requires people to read and rank harmful outputs, which does not scale and is unpleasant work. Anthropic had the model critique and revise its own responses against a written set of principles and fine-tuned on the final revisions, then had a model compare response pairs against those principles to produce harmlessness preference labels. Those labels were mixed with human helpfulness labels to train the preference model used as the reward. The constitution is inspectable and editable, which makes the value judgments explicit rather than buried in annotator behavior.
Deduplicating Training Data Makes Language Models BetterLee et al.#
2022·ACL
Contribution
Showed that removing near-duplicate documents from training corpora reduces memorization and improves downstream performance per training token.
Web corpora contain the same passages many times over, and the effect of that on training had not been measured. Lee and colleagues found duplication substantial, showed that removing it lowers memorized verbatim output by roughly an order of magnitude, and demonstrated that undeduplicated test sets overlap training data enough to inflate reported scores. Deduplication is now a standard preprocessing step.
Discovering Faster Matrix Multiplication Algorithms with Reinforcement LearningFawzi et al.#
2022·Nature
Contribution
Used reinforcement learning to find matrix multiplication algorithms that improve on known results for specific matrix sizes.
Strassen's algorithm from 1969 had not been improved for four by four matrices in fifty years, and the search space of possible decompositions is enormous. Fawzi and colleagues cast the search as a single-player game and applied the AlphaZero machinery to it, finding a decomposition of 4 by 4 matrices in arithmetic modulo 2 using fewer multiplications than the best known. The result is modest in practical terms and notable as machine discovery of a mathematical object.
Efficiently Scaling Transformer InferencePope et al.#
2022·arXiv preprint
Contribution
Gave an analytical model for choosing how to partition a large transformer across chips, setting a new Pareto frontier on latency against model FLOPS utilization.
Training a large model is a solved engineering problem compared with serving it, where latency, throughput, and cost pull in different directions. Pope and colleagues give an analytic model of how partitioning strategies interact with chip interconnect, and derive which layout is optimal in which regime. It is the reference account of why serving configurations look the way they do.
FlashAttention: Fast and Memory-Efficient Exact Attention with IO-AwarenessTri Dao et al.#
2022·NeurIPS
Contribution
Reordered the attention computation to minimize HBM reads by tiling into SRAM, computing exact attention faster than approximate methods.
Work on attention cost had focused on reducing arithmetic through approximation, while the actual bottleneck was moving the attention matrix between levels of GPU memory. Dao and colleagues tile the computation so the matrix is never written out in full, computing the softmax incrementally instead. The result is exact rather than approximate, several times faster, and linear rather than quadratic in memory.
LoRA: Low-Rank Adaptation of Large Language ModelsHu et al.#
2022·ICLR
Contribution
Showed that injecting trainable low-rank matrices into frozen transformer layers matches full fine-tuning quality at a fraction of the parameter cost.
Fine-tuning every parameter of a large model requires optimizer state several times the model size and produces a full copy per task. Hu and colleagues freeze the base weights and learn a low-rank update, on the observation that the change induced by adaptation has low intrinsic rank. Trainable parameters drop by orders of magnitude and the adapter can be merged at inference with no added latency.
Orca: A Distributed Serving System for Transformer-Based Generative ModelsYu et al.#
2022·OSDI
Contribution
Introduced iteration-level scheduling, which runs one model iteration at a time so that finished requests leave and new ones join between steps, and reported 36.9 times the throughput of NVIDIA FasterTransformer at the same latency on GPT-3 175B.
Serving systems scheduled a whole request at a time, so a request that finished early could not return until its batch did, and a new arrival waited for the entire batch to finish. Yu and colleagues scheduled one model iteration at a time instead, and batched every operation except attention, whose inputs differ in shape from request to request. The same idea is what serving engines now call continuous batching.
ST-MoE: Designing Stable and Transferable Sparse Expert ModelsZoph et al.#
2022·arXiv preprint
Contribution
Introduced the router z-loss, a penalty on large router logits that stabilized sparse expert models without the quality loss of other fixes, and scaled a sparse model to 269 billion parameters with state-of-the-art transfer results.
Mixture-of-experts models and Switch Transformers offered an energy-efficient path to larger language models, but training instabilities and uncertain quality after fine-tuning held them back. Zoph and colleagues found that many stability fixes worked only at the expense of quality, while a penalty on large router logits did not, and wrote their results up as a design guide. Their 269-billion-parameter model, at about the compute of a 32-billion-parameter dense one, was the first sparse model to reach state-of-the-art performance in transfer learning.
Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient SparsityFedus, Zoph and Shazeer#
2022·JMLR
Contribution
Simplified mixture-of-experts routing to a single top-1 gate, reducing communication cost and scaling a transformer to a trillion parameters.
Mixture-of-experts routing sent each token to several experts, which complicated the implementation and made training unstable at scale. Fedus, Zoph and Shazeer route to exactly one, which simplifies everything, and address the resulting instability with selective precision and a tighter initialization. Parameter counts reached the trillions at constant per-token compute.
Demonstrated in controlled settings that neural networks represent more features than they have dimensions by superposing them, explaining why individual neurons are polysemantic.
Networks appear to represent more distinct features than they have neurons, and it was unclear whether that was real or an artifact of how features were being counted. Elhage and colleagues built small models where the true features are known by construction and showed that when features are sparse, the network packs them into overlapping directions at the cost of interference. This explains why single neurons are polysemantic and motivates sparse dictionary methods.
Training Compute-Optimal Large Language ModelsHoffmann et al.#
2022·NeurIPS
Contribution
Showed that earlier scaling-law work had undertrained on data relative to parameters and that compute-optimal training requires scaling tokens and parameters roughly equally.
The earlier scaling work had been read as saying that model size should absorb most of any compute increase, and the field had been building very large models on comparatively little data. Hoffmann and colleagues trained over four hundred models and found parameters and tokens should scale roughly in proportion, meaning existing frontier models were substantially undertrained. Their smaller model trained longer beat much larger ones, and training budgets shifted accordingly.
Training Language Models to Follow Instructions with Human FeedbackOuyang et al.#
2022·NeurIPS
Contribution
Demonstrated that fine-tuning a language model with RLHF on human preference data produces outputs humans prefer to those of a much larger base model.
A model trained to predict the next token continues text, which is not what a person asking a question wants. Ouyang and colleagues collected demonstrations, fine-tuned on them, then fit a reward model to human rankings and optimized against it. A model with a hundred times fewer parameters was preferred to the raw base model, and the pipeline became the standard way to make a language model usable.
AWQ: Activation-aware Weight Quantization for LLM Compression and AccelerationLin et al.#
2023·arXiv preprint
Contribution
Protected salient weights identified by activation magnitude during quantization, achieving 4-bit models with minimal quality loss.
Quantization methods treated all weights as equally important, and the resulting accuracy loss at low precision was attributed to the format. Lin and colleagues observed that a small fraction of weights, identifiable from activation magnitudes rather than the weights themselves, account for most of the damage. Scaling those channels before quantizing preserves accuracy without mixed precision or retraining.
Can ChatGPT Forecast Stock Price Movements? Return Predictability and Large Language ModelsLopez-Lira and Tang#
2023·arXiv preprint
Contribution
Found that GPT sentiment scores on news headlines predicted next-day stock returns, with the effect concentrated in smaller and less-covered firms.
Sentiment scoring of financial news had relied on word lists and small supervised classifiers that miss context and negation. Lopez-Lira and Tang prompted a language model to judge whether a headline is good or bad for the stock and found the scores predict next-day returns, more strongly among small caps and after bad news. The out-of-sample window is short and the model's training cutoff makes lookahead a live concern, both of which the authors address.
Direct Preference Optimization: Your Language Model Is Secretly a Reward ModelRafailov et al.#
2023·NeurIPS
Contribution
Showed that the RLHF objective can be reparameterized into a classification loss on preference pairs, eliminating the need for a separate reward model.
Aligning with human feedback required fitting a separate reward model and then running reinforcement learning against it, a two-stage process with substantial tuning burden. Rafailov and colleagues showed the optimal policy under the standard objective has a closed form in terms of the reward, which can be inverted to express the reward in terms of the policy. The preference data can then be optimized directly with a classification loss and no reinforcement learning at all.
Efficient Memory Management for Large Language Model Serving with PagedAttentionKwon et al.#
2023·SOSP
Contribution
Applied virtual memory paging to the KV cache, eliminating fragmentation and increasing serving throughput by 2-4x over contiguous allocation.
Serving systems preallocated contiguous memory for each request's maximum possible length, wasting most of it and capping how many requests could run at once. Kwon and colleagues applied virtual memory paging to the key-value cache, storing it in non-contiguous blocks with an indirection table. Throughput improved by several times, and the resulting system became the standard open serving stack.
Fast Inference from Transformers via Speculative DecodingLeviathan, Kalman and Matias#
2023·ICML
Contribution
Showed that drafting tokens with a smaller model and verifying them in parallel with the target model speeds up autoregressive generation without changing the output distribution.
Generation is sequential and each token requires a full forward pass, so latency is bounded by model depth regardless of available parallelism. Leviathan and colleagues let a small fast model propose several tokens and have the large model verify them in one batched pass, accepting the prefix that matches. The accepted output is distributed identically to what the large model alone would produce, so nothing is given up.
Full Stack Optimization of Transformer Inference: a SurveyKim et al.#
2023·arXiv preprint
Contribution
Cataloged optimization techniques across the inference stack from hardware to serving systems and measured their interactions.
Inference optimization work was spread across compilers, kernels, quantization, architecture search and hardware design, with little contact between the communities. Kim and colleagues profile where the time actually goes and then survey each layer against those measurements. The value is in showing which optimizations interact and which are independent.
Generative Agents: Interactive Simulacra of Human BehaviorPark et al.#
2023·UIST
Contribution
Populated a sandbox environment with language-model agents that maintained memory, formed plans, and exhibited emergent social behaviors over extended simulation.
Language models respond to a prompt and forget, which makes sustained believable behavior over days of simulated time impossible. Park and colleagues added a memory stream scored by recency, importance, and relevance, plus periodic reflection that synthesizes higher-level conclusions from it. Twenty-five agents in a sandbox town produced coordinated behavior nobody scripted, including organizing a party by word of mouth.
Formalized generative flow networks as samplers that learn a policy whose terminal state distribution matches a given unnormalized reward, connecting MCMC and RL.
Reinforcement learning finds the highest-reward outcome, which is wrong when the goal is a diverse set of good candidates, as in drug or material design. Bengio and colleagues train a policy to sample terminal states with probability proportional to reward rather than to maximize it, using a flow-conservation condition over the construction graph. The formalism connects to variational inference and to energy-based models.
GPTQ: Accurate Post-Training Quantization for Generative Pre-Trained TransformersFrantar et al.#
2023·ICLR
Contribution
Quantized large language models to 3-4 bits per weight with negligible accuracy loss by using approximate second-order information layer by layer.
Quantizing a large model to low precision without retraining had produced unacceptable accuracy loss below eight bits. Frantar and colleagues quantize weights one column at a time while updating the remaining columns to compensate, using second-order information from a small calibration set. Models with hundreds of billions of parameters run at three or four bits with modest degradation, which puts them on single GPUs.
GQA: Training Generalized Multi-Query Transformer Models from Multi-Head CheckpointsAinslie et al.#
2023·EMNLP
Contribution
Introduced grouped-query attention, which shares each key and value head across a group of query heads to reduce key-value cache storage and bandwidth.
Multi-query attention, which uses a single key and value head for all query heads, speeds up decoder inference but can degrade quality. Ainslie and colleagues proposed an intermediate number of key-value heads, and a recipe for converting an existing multi-head checkpoint with about 5 percent of the original pretraining compute. The converted models came close to multi-head quality at a speed comparable to multi-query attention.
Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 smallWang et al.#
2023·ICLR
Contribution
Reverse-engineered a complete circuit in GPT-2 small that performs indirect object identification, showing that mechanistic interpretability scales to nontrivial behaviors.
Circuit-level explanations had been demonstrated on toy models, leaving open whether the method survives contact with a real trained network. Wang and colleagues reverse-engineered the algorithm GPT-2 small uses for a specific grammatical task, identifying twenty-six attention heads in seven functional groups and validating each by ablation. It remains the most complete circuit description of a natural behavior in a real model.
Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code GenerationLiu et al.#
2023·NeurIPS
Contribution
Extended the HumanEval coding tests about 80-fold, caught wrong code the original tests had accepted from 26 models, and showed that the original tests had misranked some of them.
Code benchmarks such as HumanEval judged a generated program correct if it passed a handful of hand-written tests, so a program could be scored correct while failing on inputs nobody had written. Liu and colleagues had ChatGPT write seed inputs aimed at corner cases, multiplied them by type-aware mutation, and compared each program with the reference solution on every input. On the extended suite, HumanEval+, two fine-tuned CodeLlama models overtook ChatGPT, which neither had done on the original tests.
Llama 2: Open Foundation and Fine-Tuned Chat ModelsTouvron et al.#
2023·Venue not recorded
Contribution
Released pretrained and chat-tuned models with published weights under a license permitting commercial use, which moved the open-weight frontier close to the closed one.
Open models lagged the closed frontier and, more importantly, came with no account of how the alignment work was done. Meta released weights along with a long description of the supervised fine-tuning and reinforcement learning from human feedback pipeline, including the separate helpfulness and safety reward models. The license permits commercial use with restrictions, which is what made it the base for most subsequent open work.
MegaBlocks: Efficient Sparse Training with Mixture-of-ExpertsGale et al.#
2023·MLSys
Contribution
Reformulated mixture-of-experts computation as block-sparse matrix operations so that no tokens are dropped, training up to 40 percent faster than MoEs trained with the Tutel library and 2.4 times faster than dense networks trained with Megatron-LM.
Frameworks of the time fitted mixture-of-experts routing into fixed-size expert buffers, so users had to choose between dropping the tokens that overflowed, which cost quality, and padding the buffers, which wasted computation and memory. Gale and colleagues wrote block-sparse GPU kernels that handle any number of tokens per expert, removing the trade-off.
Microscaling Data Formats for Deep LearningRouhani et al.#
2023·arXiv preprint
Contribution
Evaluated the MX formats, in which each block of 32 values shares an 8-bit power-of-two scale, and showed on over two dozen benchmarks that they could replace FP32 for inference and training, including training generative language models with sub-8-bit weights, activations and gradients at minimal accuracy loss.
One scale per tensor had proved insufficient for formats narrower than 8 bits, whose dynamic range is too small. Engineers from Microsoft, AMD, Intel, Meta, NVIDIA and Qualcomm published block-scaled formats as an Open Compute Project specification, and this paper reports their evaluation. Nvidia's Blackwell GPUs support MXFP4 alongside NVFP4.
ReAct: Synergizing Reasoning and Acting in Language ModelsYao et al.#
2023·ICLR
Contribution
Interleaved reasoning traces with actions in a language model loop, showing that explicit reasoning improves task completion on knowledge and decision tasks.
Chain-of-thought reasons without checking anything against the world, and tool-using agents act without visible deliberation, so each fails in a characteristic way. Yao and colleagues interleave the two, letting the model write a thought, take an action, observe the result and continue. Grounding the reasoning in retrieved observations cut hallucination substantially, and the loop is the template most agent frameworks follow.
Reflexion: Language Agents with Verbal Reinforcement LearningShinn et al.#
2023·NeurIPS
Contribution
Had agents reflect on failures in natural language and store the reflection in an episodic memory, improving success rates on coding and reasoning tasks without weight updates.
Improving an agent from its failures normally means updating weights, which is expensive and impossible behind an API. Shinn and colleagues have the model write a verbal critique of its own failed attempt and carry that text into the next attempt as context. Learning happens in the prompt rather than the parameters, which is unusual and works well enough to matter on coding and reasoning benchmarks.
Representation Engineering: A Top-Down Approach to AI TransparencyZou et al.#
2023·arXiv preprint
Contribution
Showed that reading and writing to internal representations can identify and control high-level concepts like honesty and harmlessness without fine-tuning.
Mechanistic interpretability works upward from individual weights and attention heads, which is slow and has not yet reached most behaviors of interest. Zou and colleagues start from the concept instead, locating directions in activation space that correspond to properties like honesty or harmfulness by contrasting paired stimuli. Those directions can then be read as monitors or added as interventions.
Scaling Laws for Reward Model OveroptimizationGao, Schulman and Hilton#
2023·ICML
Contribution
Quantified how optimizing too hard against a learned reward model causes the true reward to decrease, giving scaling laws for overoptimization.
A reward model is a fitted approximation to human preference, and optimizing hard against any approximation eventually diverges from what it approximates. Gao and colleagues measured this by using a large reward model as a stand-in for ground truth, and fit the shape of the gap as a function of optimization pressure and reward model size. Goodhart's law becomes a curve that can be located rather than a warning.
SGLang: Efficient Execution of Structured Language Model ProgramsZheng et al.#
2023·Venue not recorded
Contribution
Introduced a runtime for programs that make multiple language model calls, with radix-tree reuse of cached prefixes across calls and faster decoding of constrained output.
Applications increasingly chain several generation calls with control flow and structured output, and serving systems had no efficient way to execute such programs. Zheng and colleagues paired a frontend language for writing them with a runtime built around cache reuse and structured decoding, and reported up to 6.4 times the throughput of existing inference systems on their workloads.
The Curse of Recursion: Training on Generated Data Makes Models ForgetShumailov et al.#
2023·arXiv preprint
Contribution
Showed that training each generation of a model on data generated by the previous one erases the tails of the original distribution, with degraded language models even when 10 percent of the original data was retained.
As model-generated text spreads online, future models will be trained partly on the output of earlier ones. Shumailov and colleagues repeated that loop with Gaussian mixture models, variational autoencoders and language models, and named the resulting loss of rare events model collapse.
Later qualified
Gerstgrasser et al. 2024 found that keeping the original data and adding each synthetic generation to it, instead of replacing it, avoided collapse in their experiments.
Toolformer: Language Models Can Teach Themselves to Use ToolsSchick et al.#
2023·NeurIPS
Contribution
Showed that a language model could teach itself when to call external tools by keeping only the API calls it had inserted into text whose results lowered its loss on the following tokens, then fine-tuning on the kept examples.
Tool use in language models depended on large amounts of human annotation or on task-specific setups. Schick and colleagues had a model annotate web text with candidate calls to a calculator, a question-answering system, a search engine, a translation system and a calendar, kept the calls whose results made the next tokens easier to predict, and fine-tuned the 6.7-billion-parameter GPT-J on the result.
Towards Monosemanticity: Decomposing Language Models with Dictionary LearningBricken et al.#
2023·Anthropic research
Contribution
Showed that sparse autoencoders applied to transformer activations recover interpretable, monosemantic features from a superposition of concepts.
Individual neurons respond to unrelated concepts, which makes them useless as units of explanation, and superposition explains why: models pack more features than they have dimensions. Bricken and colleagues trained a sparse autoencoder to expand activations into a much wider, sparsely active basis, and found the resulting directions largely interpretable. This is currently the main practical tool in mechanistic interpretability.
"Give Me BF16 or Give Me Death"? Accuracy-Performance Trade-Offs in LLM QuantizationKurtic et al.#
2024·ACL 2025
Contribution
Benchmarked quantized serving in vLLM and found 4-bit weight-only quantization most cost-efficient for synchronous deployments and 8-bit weights and activations best under asynchronous continuous batching.
The accuracy and performance trade-offs between quantization formats were unclear. Kurtic and colleagues ran over 500,000 evaluations of FP8, INT8 and INT4 formats across the Llama-3.1 model family, finding FP8 effectively lossless and well-tuned INT8 within 1 to 3 percent of the original accuracy, and then measured serving performance for each format in vLLM.
A Careful Examination of Large Language Model Performance on Grade School ArithmeticZhang et al.#
2024·NeurIPS Datasets and Benchmarks
Contribution
Introduced GSM1k, a fresh set matched to GSM8k, and measured accuracy drops of up to 8 percentage points, with the largest gaps in models more likely to reproduce GSM8k examples.
High scores on grade-school math could mean the models reason or that they had seen the test. The authors commissioned new problems matched to GSM8k in style and difficulty, then compared each model on the two sets and against its likelihood of generating GSM8k items. Many frontier models showed little gap, which is what separates an overfit model from a capable one.
Adding Error Bars to Evals: A Statistical Approach to Language Model EvaluationsEvan Miller#
2024·arXiv preprint
Contribution
Set out how to report a language-model evaluation as an estimate with a standard error, including clustered errors for related questions and paired comparisons between models on the same items.
Benchmark scores were published as bare percentages, so readers could not tell a real lead from sampling noise. Miller treated the questions as a sample from an unseen population of possible questions and brought over the standard tools of experiment analysis, which let a team state how many items a comparison needs before it runs.
DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language ModelDeepSeek-AI#
2024·Venue not recorded
Contribution
Introduced multi-head latent attention, which caches a compressed key-value vector and a separate rotary key per token instead of full keys and values.
During generation, the key-value cache of standard multi-head attention becomes the bottleneck that limits inference efficiency. DeepSeek-V2, a mixture-of-experts model with 236 billion total parameters and 21 billion active per token, compressed that cache into a latent vector and reported a cache 93.3 percent smaller than that of the dense DeepSeek 67B model.
Trained a mixture-of-experts model with 671 billion total and 37 billion active parameters per token that balanced expert load mainly through a per-expert routing bias instead of an auxiliary loss, and dropped no tokens in training or inference.
Auxiliary losses keep mixture-of-experts routing balanced, but too large a loss impairs model quality. DeepSeek-AI added to each expert's routing score a bias used only to select experts and adjusted after every training step according to that expert's load, and trained the model with FP8 mixed precision in 2.788 million H800 GPU hours.
DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language ModelsShao et al.#
2024·arXiv preprint
Contribution
Introduced group relative policy optimization, a PPO variant that takes its baseline from the mean reward of answers sampled for the same question instead of from a learned value model, and used it to bring a 7B model to 51.7 percent on the competition-level MATH benchmark.
Open models trailed GPT-4 and Gemini-Ultra on competition mathematics, and the value model that PPO trains alongside the policy is typically about as large as the policy, a substantial memory and compute cost. Shao and colleagues continued pretraining a 7B code model on 120 billion math tokens filtered from Common Crawl, then replaced the value model with a baseline computed from a group of sampled answers. The reinforcement learning stage raised MATH accuracy from 46.8 to 51.7 percent while using fewer training resources than PPO.
DeepSeekMoE: Towards Ultimate Expert Specialization in Mixture-of-Experts Language ModelsDai et al.#
2024·ACL
Contribution
Showed that splitting experts into many smaller ones, activated in proportionally larger numbers at equal compute, and isolating a few shared experts that every token uses improved expert specialization, with a 2-billion-parameter model matching GShard at 2.9 billion.
Conventional mixture-of-experts layers such as GShard route each token to the top few of a modest number of large experts, which makes it hard for each expert to acquire non-overlapping, focused knowledge and leaves several experts relearning the same common knowledge. Dai and colleagues at DeepSeek-AI segmented the experts more finely and set aside shared experts to capture common knowledge, and the design became the feed-forward architecture of later DeepSeek models, including DeepSeek-V3.
DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model ServingZhong et al.#
2024·OSDI
Contribution
Showed that running prefill and decoding on separate GPUs, each with its own allocation and parallelism plan, raised the request rate a GPU could serve while a target share of requests met both the time-to-first-token and time-per-output-token objectives.
Serving systems batched prefill and decoding together on the same GPUs and maximized total throughput, so a long prefill delayed every decoding step batched with it and both phases shared one resource plan. Zhong and colleagues measured capacity instead as per-GPU goodput, the highest request rate a GPU sustains while a target share of requests meets both latency objectives, and gave each phase its own GPUs, placed by cluster bandwidth to limit the cost of moving key-value caches between them.
FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precisionShah et al.#
2024·NeurIPS
Contribution
Reached up to 740 FP16 teraflops for attention on the H100, 75 percent of peak and 1.5 to 2 times FlashAttention-2, by overlapping matrix multiplies with softmax through warp specialization and asynchronous data movement, with an FP8 path near 1.2 petaflops.
FlashAttention-2 reached only 35 percent utilization on the H100, in part because it did not use the asynchronous tensor cores and data movement that Hopper added. Shah and colleagues rebuilt the kernel around those features and added block quantization for FP8. The paper shows how close attention can come to a GPU's peak once the kernel is written for the hardware.
Is Model Collapse Inevitable? Breaking the Curse of Recursion by Accumulating Real and Synthetic DataGerstgrasser et al.#
2024·arXiv preprint
Contribution
Reported that keeping the original real data and accumulating successive synthetic generations alongside it avoided model collapse across the model sizes, architectures and hyperparameters tested.
Model collapse had been shown under a protocol in which each generation's synthetic data replaced the data before it. Gerstgrasser and colleagues compared replacement with accumulation, where real data is kept and synthetic data is added, which they argue is the more realistic assumption about how training data builds up over time.
KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV CacheLiu et al.#
2024·ICML
Contribution
Developed a tuning-free 2-bit key-value cache quantizer that groups keys per channel and values per token to match their different distributions.
Batching many requests lowers the cost of serving, but the key-value cache then dominates memory and becomes the bottleneck in speed. Liu and colleagues studied how cached elements are distributed in popular models, found that keys and values need different grouping, and reported almost unchanged quality with 2.6 times less peak memory, weights included.
KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache QuantizationHooper et al.#
2024·NeurIPS
Contribution
Quantized the key-value cache to 3 bits with a perplexity increase below 0.1 on Wikitext-2 and C4 for the LLaMA, Llama-2, Llama-3 and Mistral models tested.
With long context windows the key-value cache becomes the dominant use of inference memory, and existing quantizers could not represent it accurately below 4 bits. Hooper and colleagues combined per-channel key quantization, quantizing keys before the rotary embedding, non-uniform levels and separate handling of outliers in each vector, and reported serving LLaMA-7B with up to 1 million tokens of context on a single A100-80GB GPU.
Mamba: Linear-Time Sequence Modeling with Selective State SpacesGu and Dao#
2024·COLM
Contribution
Introduced a selective state-space model with input-dependent gating that matches transformer quality at linear time in sequence length.
State space models scale linearly in sequence length but had a fixed transition that cannot decide what to keep, so they underperformed attention on language. Gu and Dao made the state transition depend on the input, which restores content-based selection at the cost of the convolutional form that made them fast. A hardware-aware scan recovers the speed, and the model matches transformers of comparable size.
Mathematical Discoveries from Program Search with Large Language ModelsRomera-Paredes et al.#
2024·Nature
Contribution
Used a large language model to search over programs and found new constructions for the cap set problem that improve on known bounds.
Language models produce plausible mathematics that is frequently wrong, which makes them unusable for discovery on their own. Romera-Paredes and colleagues had the model write programs rather than proofs, evaluated each against an exact verifier, and fed the surviving ones back as prompts. The loop found a construction improving the known bound for the cap set problem, a genuine advance in combinatorics.
Showed that an open-weight sparse model routing each token to two of eight experts in every layer, using 13 billion of its 47 billion parameters per token, could outperform or match Llama 2 70B and GPT-3.5 across the benchmarks evaluated.
Mistral AI built Mixtral 8x7B on the Mistral 7B architecture, replacing each feed-forward block with eight experts and a router that selects two of them for every token at every layer, so different tokens can use different experts. Both the base model and an instruction-tuned version were released under the Apache 2.0 license.
OLMo: Accelerating the Science of Language ModelsGroeneveld et al.#
2024·Venue not recorded
Contribution
Released weights together with training data, training code, and intermediate checkpoints, making the full training trajectory reproducible rather than only the final model.
Open weights allow a model to be used and not studied, since the data, the intermediate checkpoints and the training code stay private. The Allen Institute released all of it, so questions about how a capability arises during training can be investigated rather than speculated about. This is the fullest available answer to the reproducibility complaint.
QServe: W4A8KV4 Quantization and System Co-design for Efficient LLM ServingLin et al.#
2024·MLSys 2025
Contribution
Combined 4-bit weights, 8-bit activations and a 4-bit key-value cache with serving kernels designed to keep dequantization cheap, raising measured serving throughput over TensorRT-LLM.
Existing 4-bit quantization sped up small-batch inference on edge devices but not large-batch serving in the cloud, because dequantizing weights or partial sums on GPUs added 20 to 90 percent runtime overhead. Lin and colleagues designed the quantization algorithm and the serving system together to remove that overhead.
QuantAgent: Seeking Holy Grail in Trading by Self-Improving Large Language ModelWang et al.#
2024·arXiv preprint
Contribution
Built a two-layer agent loop in which the inner loop answers from a knowledge base and the outer loop tests those answers against the market, writing what it learns back into the base.
Language models proposing trading signals have no way to tell a real edge from a story that sounds plausible. Wang and colleagues build a two-loop system where an inner loop refines against a knowledge base and an outer loop tests against market data and writes the outcome back. The paper is best read as an architecture for closing the feedback loop, since the reported performance rests on limited data.
Reconciling Kaplan and Chinchilla Scaling LawsPearce and Song#
2024·TMLR
Contribution
Attributed much of the gap between the Kaplan and Chinchilla compute-optimal exponents to Kaplan counting non-embedding rather than total parameters at small scale, since simulating the Chinchilla study under those conditions gave coefficients close to Kaplan's.
The Kaplan and Chinchilla scaling laws prescribed very different splits of a compute budget, with optimal model size growing as compute to the 0.73 and to the 0.50. Pearce and Song reran the Chinchilla analysis under Kaplan's counting convention and model range and recovered a biased exponent close to Kaplan's, which reaffirmed Chinchilla's coefficients and led them to recommend that scaling studies count total parameters and compute.
Resolving Discrepancies in Compute-Optimal Scaling of Language ModelsPorian et al.#
2024·NeurIPS
Contribution
Traced the Kaplan and Chinchilla discrepancy to uncounted output-layer compute, a warmup too long for small models and optimizer settings not tuned per model size, and recovered the Chinchilla exponent with a constant learning rate, showing that careful learning rate decay is not essential to it.
The Chinchilla authors had conjectured that Kaplan's learning rate decay was a main cause of the two groups' different compute-optimal allocations. Porian and colleagues reproduced the Kaplan law in their own setup and removed its differences from Chinchilla one at a time, finding that matching learning rate decay to each budget changed the exponent little while compute accounting, warmup length and per-size tuning of learning rate, batch size and AdamW β2 closed the gap.
Scaling and evaluating sparse autoencodersGao et al.#
2024·arXiv preprint
Contribution
Trained sparse autoencoders at scale on GPT-4 and showed that the number of interpretable features recovered grows predictably with autoencoder size.
Sparse autoencoders for interpretability had been demonstrated on small models with hand-tuned sparsity penalties and no agreed way to compare them. Gao and colleagues used a top-k activation to fix sparsity directly, trained autoencoders up to sixteen million features on a frontier model, and proposed metrics for feature quality. The paper turns the technique into something with scaling laws of its own.
Self-Play Fine-Tuning Converts Weak Language Models to Strong Language ModelsChen et al.#
2024·ICML
Contribution
Showed that iterating self-play, in which a model learns to distinguish its own generations from human-written demonstrations, improves alignment without additional human annotation.
Fine-tuning is limited by the supply of human-written demonstrations, which is expensive and finite. Chen and colleagues have the model generate responses and train to distinguish them from the human data, so it improves against its own previous version without new annotation. Gains hold for several rounds before the process saturates.
Solving Olympiad Geometry without Human DemonstrationsTrinh et al.#
2024·Nature
Contribution
Combined a neural language model with a symbolic deduction engine to solve Olympiad geometry problems at a level approaching the gold-medal threshold.
Olympiad geometry has almost no machine-readable proof corpus, so supervised learning has nothing to learn from. Trinh and colleagues generated a hundred million synthetic theorems and proofs from random diagrams, then paired a language model that proposes auxiliary constructions with a symbolic engine that closes the deductions. The system solved twenty-five of thirty recent olympiad problems, near gold medal standard.
Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-ServeAgrawal et al.#
2024·OSDI
Contribution
Showed that capping the prompt tokens processed per iteration, and admitting new requests without pausing the decodes already running, raised serving capacity under tail-latency limits over vLLM.
Iteration-level batching had raised throughput, but schedulers that ran each new prompt eagerly made every ongoing decode wait for it, trading steady token delivery for batch size. Agrawal and colleagues had shown in 2023 that decodes can ride along with a chunk of prefill work at little extra cost. Sarathi-Serve built a scheduler around a fixed per-iteration token budget, and vLLM later made chunked prefill its default.
vAttention: Dynamic Memory Management for Serving LLMs without PagedAttentionPrabhu et al.#
2024·ASPLOS 2025
Contribution
Kept the key-value cache contiguous in virtual memory while allocating physical memory on demand, and measured up to 1.23 times the serving throughput of paged attention kernels.
PagedAttention removed cache fragmentation by allocating physical memory at runtime, but it also made the cache non-contiguous in virtual memory, which adds programming and performance overhead to every attention kernel. Prabhu and colleagues used CUDA virtual memory management to separate virtual from physical allocation, so existing attention kernels run unmodified.
Corporate Discount RatesNiels Joachim Gormsen and Kilian Huber#
2025·American Economic Review
Contribution
Showed from corporate conference calls that firms apply discount rates averaging 15.7 percent against a perceived cost of capital averaging 8.4 percent, and that discount rates absorbed the falling cost of capital only slowly, so the average US wedge widened by about 2.5 percentage points between 2002 and 2021.
Pretrained a trillion-parameter mixture-of-experts model, with 32 billion parameters active per token, on 15.5 trillion tokens using MuonClip, a Muon variant that caps attention logits, and reported no loss spike over the run.
The Kimi team wanted Muon's greater learning signal per token, since high-quality training data was limited, but in its experiments Muon let attention logits explode more often than AdamW, which destabilized training. Its QK-Clip rescales a head's query and key projection weights after an update whenever that head's largest attention logit passes a threshold, and with it the team pretrained K2 before a post-training stage built on synthetic agentic data and joint reinforcement learning.
Showed that the Muon optimizer scales to large language models once weight decay is added and each matrix's update is scaled to match AdamW's, needing about 52 percent of AdamW's training compute in compute-optimal scaling-law experiments.
Muon, which updates weight matrices with orthogonalized momentum, had done well on small language models, but whether it held up for billions of parameters and trillions of tokens was untested. Liu and colleagues at Moonshot AI found that without weight decay the weights and layer outputs grew beyond the range bfloat16 represents precisely, so they added decay and matched the update size to AdamW, which let Muon reuse AdamW settings. They then trained Moonlight, a mixture-of-experts model with 16 billion total and 3 billion active parameters, on 5.7 trillion tokens.
OLMoE: Open Mixture-of-Experts Language ModelsMuennighoff et al.#
2025·ICLR
Contribution
Released a mixture-of-experts language model with 7 billion parameters, 1 billion of them active per token, pretrained on 5 trillion tokens, together with its weights, training data, code and logs.
Frontier models such as Gemini 1.5 used mixture-of-experts layers, but most such models were closed, and those with public weights said little about their data, code or recipes. Muennighoff and colleagues released every part of a small sparse model and reported experiments on how to train one, finding for instance that the router z-loss reduced loss spikes and lowered loss for about 2 percent of throughput.
Quantum Error Correction below the Surface Code ThresholdAcharya et al.#
2025·Nature
Contribution
Demonstrated surface code memories operating below threshold, with the logical error rate falling by a factor of 2.14 for each increase of two in code distance and a 101-qubit distance-7 memory outliving its best physical qubit by a factor of 2.4.
Error correction suppresses logical errors exponentially as qubits are added, but only when the physical error rate sits below a critical threshold. Acharya and colleagues ran distance-5 and distance-7 surface code memories, one with a real-time decoder, and measured the suppression directly. Repetition-code runs up to distance 29 then showed performance limited by rare correlated errors arriving about once an hour.
Building Production-Ready Probes For GeminiKramár et al.#
2026·arXiv preprint
Contribution
Reported that activation probes for misuse detection informed deployments in user-facing Gemini, after new probe architectures addressed the shift from short to long inputs.
Screening every prompt with another language model is expensive, and earlier probes failed to generalize under production distribution shifts, especially from short-context to long-context inputs. Kramár and colleagues proposed probe architectures for long contexts, evaluated them on cyber-offensive prompts including multi-turn conversations and adaptive red teaming, and paired probes with prompted classifiers for accuracy at low cost.
Verbalizable Representations Form a Global Workspace in Language ModelsGurnee et al.#
2026·Transformer Circuits Thread
Contribution
Introduced the Jacobian lens, which reads internal concepts available for verbal report at layers where the logit lens is unreadable.
The logit lens reads intermediate activations as if every layer used the output head's coordinates, which fails in early layers. Gurnee and colleagues averaged, over a large corpus of contexts, the linearized effect of each layer's activation on the likelihood of producing a token now or later, correcting for how representations change across layers. They described the resulting readout as imperfect and incomplete, and the basic method only finds concepts that correspond to single tokens.
Selection rests on a contribution used in the encyclopedia: a result, method, model, or synthesis.
The catalog includes primary research alongside selected surveys, position papers, technical reports, and other explanatory records. Citation count alone is not an inclusion rule.
These records carry different kinds of evidence. A theorem depends on its assumptions and proof; an experiment on its methods, data, and comparison; a system report on what its authors actually measured. A survey can organize earlier results without originating them, and a position paper can make an argument without establishing it experimentally. The contribution field should preserve those distinctions. Inclusion does not certify independent review or replication.
Each entry records an arXiv identifier or a digital object identifier wherever one exists, so the claim on this page can be checked against the source in one step. Where a paper predates those systems, the venue and year are given instead. The site treats an unverifiable citation as worse than no citation, because it borrows authority it has not earned.
Grouping runs by decade rather than by branch because sequence is the thing a primary literature page can show that a topic page cannot. What had to exist before the next result could be stated is visible in a chronology and invisible in a taxonomy. A branch grouping would split the dependency chain across mathematics, theory, and application before a reader could see it.
The first question for an unfamiliar paper is not whether the result is true. It is which independent checks have already happened.
A venue stamp can mean indexing, moderation, public review, confidential review, editorial selection, or only a durable pointer. Those are different claims. Confusing them makes a preprint look reviewed, a proceedings paper look merely provisional, or a DOI look like endorsement.
arXiv is a preprint server, not a journal. Its moderation policy says submissions are checked for fit with arXiv’s subject areas, scholarly form, and basic archival interest, and arXiv states that moderation is not peer review. An arXiv posting does not certify that a referee checked the theorem, reran the experiment, inspected the data, or judged the method against alternatives. It also does not establish that no review occurred elsewhere: check the paper’s conference, journal, and version records.
That distinction matters because machine learning often treats the arXiv copy as the working copy even after a conference or journal version exists. arXiv identifiers carry versions: v1, v2, and so on. A replacement or withdrawal creates a new version, and the abstract page without a version suffix shows the latest one. Cite the exact version when a proof, table, or claim changed. A withdrawn arXiv paper remains in the record: the withdrawn version becomes the default view, the reason appears in the comments field, and earlier versions usually remain reachable through the version history. Withdrawal is therefore a warning label, not erasure.
OpenReview is a review and publishing platform whose value is the record attached to the paper. Venue organizers choose the openness policy, so the stamp differs by conference. For NeurIPS 2024, accepted papers made reviews, meta-reviews, and discussion with the authors public, while identities of reviewers and area chairs remained anonymous. OpenReview itself describes open discussion as hosting accepted papers with their reviews and comments, with chairs controlling read and write permissions.
For a reader, that record is often more informative than the final PDF. Reviews name the objection the authors had to answer: missing baseline, weak ablation, unclear novelty, insufficient theory, or a measurement problem. The area chair’s meta-review tells which objections moved the decision. OpenReview certifies the existence of a review process and exposes much of its reasoning when the venue makes the record public. It does not certify that the reviewers were right, that the authors fixed every weakness, or that rejected objections were unimportant. Read the reviews as structured adversarial notes, not as a truth label.
In machine learning, conference proceedings at NeurIPS, ICML, and ICLR carry the status that journals carry in physics, biology, or economics. A main-conference acceptance means the paper passed a time-bounded peer-review process run by program chairs, area chairs, and reviewers, usually with author rebuttal and discussion. NeurIPS, for example, requires anonymized submissions, assigns reviewers and area chairs, asks authors to respond to initial reviews, and publishes accepted camera-ready papers in the conference record.
The stamp certifies competitive review for novelty, technical soundness, clarity, and fit with the conference. It does not certify journal-style replication, long editorial iteration, or an exhaustive check of every appendix. Acceptance rates measure scarcity in a particular year’s review process, not a universal probability that a result is correct. A spotlight or oral label usually means the program committee selected the paper for scarce presentation time because reviewers or chairs expected broad interest. It is not a separate methodological audit. Treat proceedings status as stronger than a preprint and weaker than independent reproduction.
An NBER working paper is a National Bureau of Economic Research working-paper series item, not a peer-reviewed journal article. NBER describes the series as new research by NBER affiliates, circulated before peer review for discussion and comment. The stamp certifies that an NBER-affiliated author placed the work into that circulation channel and that it passed the bureau’s series rules, including NBER’s rule against policy recommendations and normative policy judgments in working papers. It does not certify that journal referees accepted the identification strategy, the standard errors, the data construction, or the welfare interpretation.
Economics nevertheless runs on working papers because journal publication is slow and seminar circulation is part of the discipline’s error-correction system. A working paper may be the object everyone cites for years. When a journal version appears, compare it to the working-paper version rather than assuming identity. The model, sample, appendix, and even the main conclusion can move between the circulating version and the version of record.
Nature and Science are peer-reviewed general-science journals, but their editorial filter differs from a field journal’s filter. Nature says its research Articles must report original scientific research of outstanding scientific importance and interest to an interdisciplinary readership. Science tells authors that it seeks influential papers that substantially advance scientific understanding and present novel, broadly important data, syntheses, or concepts. The stamp certifies both peer review and editorial selection for breadth.
A strong field journal asks a narrower question: whether specialists think the methods, evidence, and contribution meet the standards of that field. Neither stamp dominates. A general-science venue can expose a result to readers far outside the specialty and demand a shorter, clearer claim. That same breadth can reward findings whose scope, novelty, or surprise is easier to state than their fragility. Fang and Casadevall’s retraction-index study found that retractions are rare overall but that retraction frequency correlated strongly with journal impact factor. The mechanism is selection pressure, not moral ranking: high-profile journals attract unusually important work, unusually competitive authors, unusually compressed presentations, and unusually intense scrutiny after publication.
A digital object identifier is a persistent identifier, not a venue stamp. https://doi.org/10.xxxx/... sends the identifier to the DOI resolver, which redirects to the current URL registered for the object. The DOI Foundation describes persistence as a social and technical system: registration agencies, metadata, policies, and the Handle System keep the identifier useful even when a publisher changes platforms. The stamp certifies that a registrant created and maintains a record for that object. It does not certify peer review, availability, correctness, or free access.
When a DOI resolves to a paywall, do not stop at the publisher page. Search the title with the author’s name, then check the author’s home page, the institutional repository, and the preprint server. The arXiv version may differ from the DOI version, so compare dates, version numbers, and journal references before quoting a claim. If no legal copy appears, email the corresponding author with the citation and the specific use. Authors often send a copy because they want the work read and because a private scholarly request is ordinary academic practice.
The order that reaches a judgment fastest, which is not the order the paper is printed in.
Read the abstract, then go straight to the figures and tables, then to the experimental setup, and only then to the body. The introduction is written to persuade a reviewer that the work matters, and it is the section least constrained by what the authors actually did. The tables carry the claim. If the numbers do not support the story, no amount of prose in the introduction repairs that, and finding the gap takes two minutes from the tables and twenty from the narrative.
Check the baseline before you check the result. The interesting comparison is against the strongest available alternative, and the common substitute is a comparison against the authors’ own previous system or against a version of the alternative that nobody tuned. A method that wins by three points against an untuned baseline and loses to a tuned one has told you about hyperparameter search rather than about architecture. Look for a sentence stating that both systems received equal tuning budget, and treat its absence as informative.
A result that changes the architecture, the data, and the optimizer at once cannot attribute its gain to any of them, and the ablation table is where the authors either do that attribution or decline to. An ablation that removes one component and reports a small drop is evidence about that component. A paper with no ablation at all is reporting that a pipeline works, which is a weaker and often still useful claim, but not the claim the title usually makes.
Most published results are the surviving members of a search over methods, seeds, and evaluation choices, and the search is rarely described. A single-seed result with no variance reported is weak evidence in any setting where reruns differ, which covers most of deep learning. Where a paper reports means over several seeds with intervals, it has given you something you can reason about, and that alone separates a careful paper from a lucky one.
In a well-written paper the limitations section is the most honest page. Authors who state clearly where the method fails are describing the boundary of a real contribution. Where the limitations section is absent or consists of a promise to scale further in future work, the boundary has not been established and you should assume it is closer than the abstract suggests.
A correction is the field working rather than failing, and a reader who cites the original without the correction is citing something the literature has moved past.
Qualification takes a few recognizable forms and they carry different weight.
Form
What happens to the original claim
Narrowed
It still holds, under stricter conditions than first stated.
Fails to replicate
Challenges reproducibility or generality. Whether it undermines the original result depends on the replication design, uncertainty, and cause of the discrepancy.
Superseded by measurement
A constant or an exponent is re-estimated. This is the ordinary progress of an empirical science and says nothing bad about the first estimate.
Explanation replaced
The effect survives and the mechanism in the abstract does not. This is the form most often misread, because the finding stays citable.
A “Later qualified” box identifies a recorded qualification. Other caveats appear in the background paragraphs. Before relying on an original claim, locate the qualifying work and compare which assumptions, results, or explanations changed.
Absence of a qualification on an entry means none has been recorded here, and it does not mean none exists. The literature qualifying a widely used result is frequently scattered across venues that do not cite each other, and there is no registry to consult. Treat the boxed fields as a floor on the corrections that apply rather than as a complete accounting, and check the citing literature before you rest an argument on any single paper.