PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithmic progress in language models

Anson Ho, Tamay Besiroglu, Ege Erdil, David Owen, Robi Rahman, Zifan Carl Guo, David Atkinson, Neil Thompson, Jaime Sevilla

arXiv:2403.05812v1cs.CLcs.AI

TL;DR

The paper asks how much language-model progress comes from pre-training algorithms versus scaling models and datasets. It fits augmented scaling laws to evaluation data and finds that compute needs fell rapidly, with scaling the predominant source of recent gains.

  • Problem

    The paper asks how much recent language-model progress came from pre-training algorithmic improvements versus scaling models and datasets.

    Source: §1 · p. 1

  • Method

    The authors fit an augmented neural scaling law to estimate algorithmic progress and use Shapley values to separate contributions from compute scaling and algorithms.

    Source: §2.1 · p. 4, §4.1 · p. 10

  • Results

    Compute required to reach a fixed language-model performance threshold halved approximately every 8 months, and compute scaling was the predominant source of recent gains.

    Source: §4.3 · p. 12

  • Takeaways & Limitations

    The analysis quantifies rapid language-model progress and identifies scale as dominant over algorithms for recent performance gains.

    Source: §4.3 · p. 12

    Sparse pre-2017 data and noisy benchmark evaluations widen doubling-time confidence intervals, while correlated algorithmic improvements and scaling complicate attribution.

    Source: §4.2 · pp. 10–11

Abstract

from arXiv · show

We investigate the rate at which algorithms for pre-training language models have improved since the advent of deep learning. Using a dataset of over 200 language model evaluations on Wikitext and Penn Treebank spanning 2012-2023, we find that the compute required to reach a set performance threshold has halved approximately every 8 months, with a 95% confidence interval of around 5 to 14 months, substantially faster than hardware gains per Moore's Law. We estimate augmented scaling laws, which enable us to quantify algorithmic progress and determine the relative contributions of scaling models versus innovations in training algorithms. Despite the rapid pace of algorithmic progress and the development of new architectures such as the transformer, our analysis reveals that the increase in compute made an even larger contribution to overall performance improvements over this time period. Though limited by noisy benchmark data, our analysis quantifies the rapid progress in language modeling, shedding light on the relative contributions from compute and algorithms.

1 Introduction

The paper asks how pre-training algorithmic improvements compare with model and dataset scaling as sources of language-model progress. It frames algorithmic progress as achieving the same benchmark performance with less compute, against a background of advances across computer science and machine learning.

1 Introduction

  • Using established WikiText and Penn Treebank benchmarks, the study compares pre-training compute savings with model and dataset scaling, excluding post-training enhancements.Source: §1 · pp. 1–2

1.1 Previous work

  • Across computer science, algorithmic progress often corresponds to doubling effective compute every 1–2 years, though rates vary substantially by domain and problem size.Source: §1.1 · p. 2

1.1.1 Algorithmic progress in computer science

  • LP studies report over 1000× CPLEX speedups from 1988–1995, while Koch et al. 2022 estimate algorithmic speedups of 9× for LPs and 50× for MILPs.Source: §1.1.1 · pp. 2–3
  • Modern SAT solvers on 1999 hardware solved a similar number of instances as early-2000s solvers on 2019 hardware; at n = 1 million, 30–43% of algorithms outpaced Moore’s law.Source: §1.1.1 · p. 3

1.1.2 Algorithmic progress in machine learning

  • In vision, ImageNet training compute fell 44× to match AlexNet, while modernized digit-recognition methods cut error 60% at fixed model size.Source: §1.1.2 · p. 3
  • Deep reinforcement-learning sample-efficiency doubling times range from 5 to 18 months across Atari, MuJoCo, and DeepMind Control Suite tasks.Dorner attributes progress to factors including off-policy learning, model-based methods, auxiliary objectives, and efficiency tuning.Source: §1.1.2 · p. 3
  • Erdil and Besiroglu (2022) estimate that algorithms explain 25–70% of gains, with physical compute scaling at 30–55% and data scaling at 10–30%.They estimate compute-augmenting algorithmic advances halve physical compute needs every 9 months.Source: §1.1.2 · p. 3
  • Applying Hoffmann et al. 2022’s scaling law yields a 2× to 4× reduction in compute to reach a given loss target at frontier-model scales.Source: §1.1.2 · p. 3

2 Methodology

The methodology augments neural scaling laws with time-varying effective model and data resources to estimate algorithmic progress. The authors select a model using cross-validation and fit it to a curated set of language-model evaluations.

2.1 Model definitions

  • The augmented scaling law relates loss to parameter count and dataset size, modeling algorithmic progress as exponential growth in effective model size and data over time.The authors use these effective quantities to define effective compute from effective parameters and data.Source: §2.1 · p. 4

2.2.1 Model selection

  • Leave-one-out cross-validation compared about 90 specifications and selected model 7, with benchmark-specific A and B coefficients and held-out R2 around 0.91.Source: §2.2.1 · p. 4
  • Alternative models allowing scaling exponents to vary performed similarly, and the core results remained broadly similar across tokenization and training-epoch choices.The alternative models typically achieved R2 between 0.88 and 0.91.Source: §2.2.1 · pp. 4–5

2.2.2 Data

  • The analysis uses about 231 of over 400 models, selected for perplexity, publication date, parameter count, and training-data size; Figure 2 shows perplexity across over eight compute orders of magnitude.Figure 2’s shape sizes are proportional to training compute.Source: §2.2.2 · p. 5, Figure 2 · p. 5
  • To limit possible autocorrelation from multiple models per paper, the main analysis includes at most three models per paper; an alternative correction yields consistent doubling-time estimates.Source: §2.2.2 · p. 5

3 Empirical results

Pre-training algorithmic progress rapidly reduced the compute needed for language-model performance, but physical compute scaling contributed more to overall modeled gains. The analysis also estimates a substantial transformer advantage while cautioning that long-range extrapolations and architecture comparisons have limits.

3.1 Models require 2× less compute roughly every eight months

  • 8.4 months [95% CI: 4.5 to 14.3 months] was the median doubling time for effective compute due to pre-training algorithmic progress in the preferred model.The estimates use the augmented scaling law and definitions of effective data, parameters, and compute.Source: §3.1 · pp. 5–6
  • The top ten cross-validation models had a median doubling time of 7.8 months [95% CI: 1.5 to 17.6 months], while a numerical alternative gave 8.6 months [95% CI: 4.5 to 14.5 months].Both estimates were reported as similar to the preferred model’s result.Source: §3.1 · pp. 6–7
  • Post-cutoff median doubling times were faster for every 2016–2020 cutoff, usually only marginally; the analysis found no strong evidence of a drastic speedup.The 2017 cutoff showed a pronounced difference, unlike most other cutoff choices.Source: §3.1 · p. 7, Figure 4 · p. 7

3.2 Most recent performance gains in next-token prediction have been from compute-scaling

  • From 2014–2023, physical compute grew about 1,000,000× versus roughly 22,000× performance-equivalent compute from algorithmic progress, with slightly under two-thirds of effective-compute growth attributed to physical compute.Figure 5 presents this as a stylized comparison.Source: §3.2 · p. 7, Figure 5 · p. 8
  • Long-range extrapolations lack direct observations of 10,000×-plus gains and ignore scale dependence; the authors say evidence does not establish that tiny models can match much larger ones.Some innovations may become less useful at larger scales, while recent innovations may fail to benefit much smaller models.Source: §3.2 · p. 8
  • Shapley analysis weakly supports compute scaling as more important than algorithmic progress in explaining performance improvements, while algorithmic progress’s relative contribution diminished over time.The authors describe this pattern for models historically close to the state of the art.Source: §3.2 · p. 8

3.3 The significance of the transformer architecture

  • The transformer’s estimated compute-equivalent gain compares the compute needed for a transformer and a non-transformer to reach the same loss.The study compares 103 transformer models with 127 non-transformer models, largely recurrent networks.Source: §3.3 · pp. 9–10
  • The transformer typically lowered reducible loss proportionally by 4.6% [95% CI: 3.0%, 7.0%], with a median compute-equivalent gain of 7.2× [95% CI: 3.3×, 45.7×].The compute-equivalent estimate corresponds to nearly two years of algorithmic progress; context length was not explicitly controlled, and longer-context evaluations may suggest a larger transformer improvement.Source: §3.3 · p. 10

4 Discussion and conclusion

From 2012 to 2023, compute required to reach fixed language-model performance halved about every 8–9 months, while compute scaling contributed more to performance gains than pre-training algorithms. The discussion also qualifies these estimates with limits in temporal resolution, data quality, and the scaling-law assumptions.

4.1 Summary of our findings

  • Compute required to reach fixed language-model performance halved every 8–9 months, while compute scaling accounted for 60–95% of gains and algorithms for 5–40%.The transformer’s introduction was a major algorithmic advance, with a 3x–46x compute-equivalent gain.Source: §4.1 · p. 10
  • The transformer’s 2017 introduction represented a 3x–46x compute-equivalent gain and more than 10% of algorithmic innovation in pretrained language models over the past decade.Source: §4.1 · p. 10

4.2 Limitations

  • The analysis cannot reliably estimate gains from specific innovations or progress over shorter timescales; experiments are better suited to innovation-specific efficiency estimates.Source: §4.2 · p. 10
  • Sparse historical data, missing model details, and inconsistent evaluation procedures add noise and potential bias, while concurrent scaling and algorithmic changes make their contributions hard to disentangle.Source: §4.2 · pp. 10–11
  • The analysis applies a Chinchilla scaling law derived for dense GPT-3-style transformers to other architectures, and cannot distinguish data-quality gains from improved data use.Source: §4.2 · p. 11

4.3 Conclusion

  • The study quantifies historical progress and finds scale dominant; extending the analysis to more benchmarks and examining data quality and specific innovations remain future work.Source: §4.3 · p. 12

A Observing improvements in the data

Direct comparisons suggest substantially less compute is needed over time to match earlier language models’ evaluated perplexity. The estimated halving rate varies with the reference model, and this approach has important limitations.

A Observing improvements in the data

  • Between 5-fold and 100-fold less compute per year in 2023 was needed to reach performance achieved between 2019 and 2023, corresponding to a 6-to-15-month halving time.Source: A Observing improvements in the data · p. 12
  • 14.9 months for Megatron-LM, 5.9 months for GPT-2, and 6.9 months for Gopher are the estimated effective-compute doubling times at matched evaluated perplexity.The estimates use least-squares regression over different cross-entropy ranges for each reference model.Source: Figure 7 · p. 12
  • The direct-comparison approach is sensitive to reference performance, can vary by a factor of 2.5, and is limited by sparse later-model compute data.The authors therefore use their core model for the main results.Source: A Observing improvements in the data · p. 12

B The gains from better scaling laws

The section estimates compute savings from adopting Chinchilla rather than Kaplan scaling laws. For dense autoregressive transformers, the estimated compute-equivalent multiplier ranges from 1.75-fold at GPT-2 scale to 4-fold at PaLM scale.

B The gains from better scaling laws

  • Compute-equivalent gain is the original compute budget divided by the compute needed under Chinchilla scaling to match the minimum loss under Kaplan scaling.The method defines loss functions for both scaling laws and minimizes them over model size and data at specified compute budgets.Source: B The gains from better scaling laws · pp. 12–13
  • GPT-3 and PaLM (540B) use around 1.7 and 1.44 tokens per parameter, respectively, close to what Kaplan scaling laws recommend.The passage notes this suggests Kaplan scaling was close to practice at the time.Source: Figure 8 · p. 13
  • 1.75-fold for GPT-2-scale models and 4-fold for PaLM-scale models are the estimated compute-equivalent multipliers from Chinchilla scaling.Source: B The gains from better scaling laws · p. 13

C Core model parameter estimates

The core model estimates benchmark-specific scaling parameters while keeping other parameters benchmark-agnostic. Its effective-compute doubling-time estimate is statistically significant despite individually non-significant year parameters; comparisons with earlier scaling laws are qualified by the compute range of the fitted data.

C Core model parameter estimates

  • The core model estimates A and B separately for each benchmark, while its other parameters are benchmark-agnostic.It normalizes N and D to minimum dataset values and reparameterizes A and B as exponentials.Source: C Core model parameter estimates · p. 13
  • Effective-compute doubling-time estimates are statistically significant even though the confidence intervals for α_year and β_year are not significant at the 5% level.The estimates for α_param and β_data are significant, while α_year and β_year are negatively correlated.Source: C Core model parameter estimates · p. 13

C.1 Comparing our estimates to earlier work

  • Around 80% of models with known training compute fall between approximately 4 × 10^17 and 10^22 FLOP, where the fitted data make the Kaplan and Hoffmann exponents hard to distinguish.The scaling-law slopes also appear more similar between these compute regimes, while diverging below and above them.Source: §C.1 · pp. 14–15
  • Adding an irreducible loss term yields scaling exponents very similar to the core model, weakening the proposed omitted-variable explanation for the discrepancy.Source: §C.1 · p. 15

D Significance of the transformer architecture

The section examines transformer contributions and measurement choices that affect estimates of language-model progress. Its analyses describe uncertainty in transformer estimates, benchmark and context-length considerations, and a tokenization adjustment that leaves the core result largely unchanged.

D Significance of the transformer architecture

E.1 Performance measure and dataset

  • The analysis uses token-level perplexity on WikiText-103, WikiText-2, and Penn Treebank, collecting 370 eligible models from 226 papers.Eligibility requires reported perplexity, parameter size, publication date, and dataset size.Source: §E.1 · p. 15

E.2 Perplexity

  • Perplexity is the exponential of test-set cross-entropy, and is chosen because it is commonly reported and relates simply to cross-entropy.Source: §E.2 · pp. 15–16

E.2.1 Context length

  • Perplexity comparisons may be affected by different context lengths; rough calculations put annual context-length loss reductions at 10–60% of algorithmic-progress reductions.The authors identify long-context task capabilities as a further avenue for investigation.Source: §E.2.1 · pp. 16–17

E.2.2 Tokenization

  • Adding a vocabulary-size term produces an 8.0-month median effective-compute doubling time, with a 95% confidence interval of 4.0 to 17.1 months.Cross-validation MSE is 0.0486 for both this model and the preferred model, and the authors judge the results consistent with their main findings.Source: §E.2.2 · p. 17
  • Typical vocabularies are roughly 10k tokens for PTB, 22k for WT2, and 268k for WT103; most vocabularies within each benchmark fall in the same histogram bin.The authors suggest benchmark-specific tokenization similarities limit the effect of including vocabulary size.Source: §E.2.2 · p. 17, Figure 11 · p. 17

E.2.3 Inconsistencies in perplexity evaluations

Perplexity evaluations contain unresolved procedural differences, but the authors judge these unlikely to explain the estimated annual reduction in perplexity. The appendices also document how training epochs and model sizes are recorded and which model families are excluded.

E.2.3 Inconsistencies in perplexity evaluations

  • Evaluation procedures were often incompletely documented, and differences in pretraining data, test-time adaptation, tokenization, strides, or preprocessing may change perplexity.The authors curated evaluations to be roughly comparable but could not verify every procedure.Source: §E.2.3 · p. 17
  • About 10%: the authors estimate that one year of pre-training algorithmic progress reduces perplexity by around 10%, more than plausible average year-to-year evaluation changes.They conclude that evaluation inconsistencies do not substantially undermine the results.Source: §E.2.3 · p. 17
  • The authors expect perplexity differences on these long-used benchmarks to broadly reflect genuine differences in model capabilities.Source: §E.2.3 · p. 18

E.3 Dataset Size & Epochs

  • When reported epoch counts are unavailable, the dataset records estimate epochs as context-length tokens multiplied by batch size and training steps.Dataset-size records generally include pre-training data and, for fine-tuned models, fine-tuning data.Source: §E.3 · p. 18

E.4 Parameter Size

  • Parameter counts use reported values when available; otherwise, they are inferred from known model counterparts, other papers, or manual architecture-based calculations.Source: §E.4 · p. 18

E.5 Inclusion and exclusion criteria

  • The analysis excludes models using retrieval, compression or pruning, neural architecture search, distillation, or cache mechanisms because their scaling behavior may differ substantially.These techniques can alter the parameter-to-data ratio that would optimally minimize loss under a compute budget.Source: §E.5 · p. 18

F Quantifying training data D

The appendix tests alternative definitions of training data and finds the core doubling-time estimates broadly robust. It also estimates doubling time using compute-optimal scaling as an alternative to a closed-form calculation.

F Quantifying training data D

  • Training data is considered as dataset size, total tokens seen, or tokens seen adjusted for diminishing returns from repeated exposure.The tokens-seen definition is approximately epochs multiplied by dataset size; the adjusted definition reflects evidence that loss-reduction benefits drop after more than four epochs.Source: F Quantifying training data D · p. 19
  • Across alternative training-data definitions, doubling-time model estimates are broadly consistent, with similar overall uncertainty; imputing unknown epochs as one yields results more similar to the core estimates.The authors therefore use dataset size for simplicity and report the results as robust to this choice.Source: F Quantifying training data D · p. 19

G Doubling times via optimal scaling

  • The alternative doubling-time analysis computes the loss reduction from doubling compute under compute-optimality, then finds the algorithmic-progress time needed to match that reduction.It addresses uncertainty about whether effective compute is optimally allocated between model size and data, including models with changing scale exponents.Source: G Doubling times via optimal scaling · pp. 19–20
  • 8.6 months: the compute-optimal approach estimates a median effective-compute doubling time, with a 95% confidence interval of 4.5 to 14.5 months.This is very similar to the estimate from the closed-form approach.Source: G Doubling times via optimal scaling · p. 20

H Irreducible loss

Adding an irreducible-loss term leaves the estimated compute-efficiency doubling time consistent with the primary estimate, although the authors caution against using their parameter estimates to determine compute-optimal model scaling. The appendix also describes a likelihood-based approach to within-paper autocorrelation.

H Irreducible loss

  • The primary model omits irreducible loss, and its parameter estimates are not reliable enough to strongly guide compute-optimal scaling of models.The authors say the omitted term does not affect their estimates of algorithmic-improvement rates, the paper's focus.Source: H Irreducible loss · p. 20
  • 8.8 months: with an irreducible-loss term, the estimated compute-efficiency doubling time has a 95% confidence interval of 4.2 to 18.7 months, consistent with the primary model.Source: H Irreducible loss · p. 20

I Autocorrelation

  • To address possible autocorrelation among models from the same paper, the alternative analysis estimates within-paper correlations and fits a multivariate-normal likelihood.The main analysis instead retained at most three models per paper.Source: I Autocorrelation · p. 21
  • The autocorrelation model uses a block-diagonal correlation structure: models from different papers are uncorrelated, while models from the same paper share correlation ρ.Its loss weights residuals using the inverse correlation matrix.Source: I Autocorrelation · pp. 21–22

I.1 Results

The clustered autocorrelation analysis produces a doubling-time estimate consistent with the core estimates. The appendix details matrix calculations for that likelihood and the leave-one-out cross-validation used to compare model specifications.

I.1 Results

  • 8.1 months: the clustered autocorrelation model estimates a median doubling time, with a 95% confidence interval of 2.9 to 13.8 months, consistent with core estimates.The estimated within-paper correlation ρ is typically around 0.45, which the authors describe as not very strong.Source: §I.1 · p. 22, Table 9 · p. 22

I.2 Determinant

  • For the determinant calculation, the block-diagonal correlation matrix lets the overall determinant be computed by multiplying the determinants of its individual blocks.The appendix reduces each block determinant through repeated row operations.Source: §I.2 · pp. 22–24

I.3 Inverse

  • For the inverse calculation, block diagonality reduces the work to inverting individual blocks, using the Sherman-Morrison formula for each block.The resulting inverse is used to calculate the residual quadratic form in the likelihood.Source: §I.3 · p. 24

J Cross validation for model choice

  • Leave-one-out cross-validation compares candidate specifications that vary benchmark-specific parameters, algorithmic progress across model size or data, regularization, and scaling exponents.The appendix describes 15 candidate model numbers and six regularization strengths; models 16–20 also support robustness checks.Source: J Cross validation for model choice · pp. 24–25

J.1 Compute-only model

The compute-only formulation is omitted from the core results because it appears misspecified and predicts poorly out of sample. Tests of changing scaling exponents suggest little contribution from that form of algorithmic progress, while cross-validation performance is assessed using average out-of-sample MSE.

J.1 Compute-only model

  • Equation 35 lets parameter scaling reach irreducible loss without data, unlike equation 34; Figure 12 shows N/D varying over five orders of magnitude across years.Source: §J.1 · p. 27, Figure 12 · p. 27
  • α=0.004 (95% CI [0.002, 0.012]) and 1–5-month effective compute doubling times accompany the compute-only model’s divergent scaling behavior, illustrated in Figure 13.Source: §J.1 · pp. 27–28, Figure 13 · p. 28
  • The compute-only model performs very poorly on out-of-sample prediction, far worse than the other models considered.Source: §J.1 · p. 28

J.2 Algorithmic progress through changes in the scale exponents αparam and βdata

  • Model 15 estimates that earlier-form progress dominates; model 14 validates roughly like no-progress models 16 and 17, with αrate and βrate around 0.001–0.01.Source: §J.2 · p. 28

J.3 Performance metrics

  • Cross-validation reports average out-of-sample MSE test loss for model-δ combinations, with δ denoting the L1 regularization term.Source: §J.3 · p. 28, Table 11 · p. 29
Loading 2403.05812v1…