PaperlayerView exact revision on arXiv

Source-linked AI summary

On the origin of neural scaling laws: from random graphs to natural language

Maissam Barkeshli, Alberto Alfarano, Andrey Gromov

arXiv:2601.10684v1cs.LGcond-mat.dis-nncs.AIstat.ML

TL;DR

The paper asks whether neural scaling laws require power-law structure in the data and what determines their exponents. It studies transformers on graph random walks and systematically simplified language data, then revisits conventional language-model scaling fits. The results show scaling laws without power-law data correlations, monotonic exponent changes with complexity, and several language-scaling phenomena reproducible in small transformers.

  • Problem

    The origin of neural scaling laws and the factors determining their exponents remain unclear, especially beyond linear models and power-law data assumptions.

  • Method

    The paper trains transformers on random walks from graphs with tunable complexity, simplified language generators, and language-model settings, while comparing scaling-law fitting methods.

  • Results

    Neural scaling laws arise for random-graph walks without power-law data correlations, while scaling exponents change monotonically as language complexity increases.

  • Takeaways & Limitations

    Scaling laws are not established here as consequences solely of power-law structure in data, and their behavior can be studied through controlled complexity changes.

  • Takeaways & Limitations

    The paper leaves more controllable interpolation between language bigrams and natural language, including n-grams, skip n-grams, and hierarchical graphical structures, for future work.

Abstract

from arXiv · show

Scaling laws have played a major role in the modern AI revolution, providing practitioners predictive power over how the model performance will improve with increasing data, compute, and number of model parameters. This has spurred an intense interest in the origin of neural scaling laws, with a common suggestion being that they arise from power law structure already present in the data. In this paper we study scaling laws for transformers trained to predict random walks (bigrams) on graphs with tunable complexity. We demonstrate that this simplified setting already gives rise to neural scaling laws even in the absence of power law structure in the data correlations. We further consider dialing down the complexity of natural language systematically, by training on sequences sampled from increasingly simplified generative language models, from 4,2,1-layer transformer language models down to language bigrams, revealing a monotonic evolution of the scaling exponents. Our results also include scaling laws obtained from training on random walks on random graphs drawn from Erdös-Renyi and scale-free Barabási-Albert ensembles. Finally, we revisit conventional scaling laws for language modeling, demonstrating that several essential results can be reproduced using 2 layer transformers with context length of 50, provide a critical analysis of various fits used in prior literature, demonstrate an alternative method for obtaining compute optimal curves as compared with current practice in published literature, and provide preliminary evidence that maximal update parameterization may be more parameter efficient than standard parameterization.

1 Introduction

Neural scaling laws predictably relate test loss to model parameters, data, and compute, but their origin and exponents remain unclear. This paper studies whether scaling laws arise without power-law data structure and systematically varies sequence complexity to investigate their behavior.

  • Motivation: Neural scaling laws show predictable power-law decreases in test loss as model parameters, dataset size, and compute increase.These relationships have informed model and dataset scaling decisions and benchmarking of algorithmic improvements.
  • Open question: The paper asks why test loss follows power laws across N, D, and C and what determines their exponents.Understanding the exponents could clarify how the asymptotic efficiency of deep learning might vary.
  • Existing explanations: Prior explanations often attribute neural scaling laws to power-law structure already present in datasets, including Zipf-like word frequencies.Theoretical support for this idea largely comes from linear or kernel regression rather than autoregressive sequence modeling with cross-entropy loss.
  • Approach: The authors study transformers predicting random walks on graphs because graph walks can model n-gram language and provide datasets with tunable complexity.This framework enables comparisons across progressively simplified sequence-generation settings.
  • Contributions: Random-graph random walks exhibit neural scaling laws even when the input data has no power-law structure.This is presented as the first empirical example of scaling laws under data without power-law structures.
  • Contributions: The study measures scaling laws across progressively simpler language generators and revisits prior language-model scaling fits and compute-optimal methods.It also examines whether maximal update parameterization may be more parameter-efficient than standard parameterization.

2 Neural scaling laws

Neural scaling laws describe predictable decreases in test loss with model parameters and dataset size, but their fitting and compute-optimal extrapolation require careful choices. The paper emphasizes one-dimensional power-law fits with irreducible-loss offsets, compares them against exponential fits, and uses neural-network regression for unsampled compute settings.

  • Scaling-law setup: Test loss L(N, D) is commonly modeled as a function of model parameters N and dataset size D, with N sometimes excluding embedding parameters.The loss is defined as the optimum over a hyperparameter sweep, including choices such as learning rate, batch size, and weight decay.
  • Empirical scaling behavior: For unbiased random walks on an Erdös-Renyi graph without power-law structure, mean αD = 1.028 ± 0.129 and mean βN = 0.749 ± 0.014.The power-law fits also have lower average MSE than the best exponential fits for both parameter- and data-scaling curves.
  • Scaling-law setup: The standard one-dimensional fits are L(N)D = ED + ADN^−αD and L(D)N = EN + BND^−βN for sufficiently large N or D.All fitted parameters depend on which variable is held fixed.
  • Fitting choices: Omitting irreducible-loss offsets ED and EN can underestimate scaling exponents αD and βN by more than 2× in practice.The paper therefore includes the offsets when extracting scaling laws.
  • Fitting choices: The paper compares one-dimensional power-law fits with exponential fits because scaling-law accuracy matters when extrapolating test loss across orders of magnitude.It also critiques two-dimensional parametric formulas, noting that the 2d Chinchilla formula can fit substantially worse and lacks theoretical support.
  • Compute-optimal scaling: Compute-optimal curves are obtained by predicting unsampled loss values with a 3-layer fully connected neural network rather than using the common two-dimensional fits directly.Compute is approximately C ≈ 6ND for one-epoch training, and the optimal N and D minimize loss subject to fixed compute.

3 Random walks, n-grams, and random graphs

The paper represents bigram prediction as random walks on weighted graphs, then tests whether transformers exhibit scaling laws on graphs whose correlation structure can be tuned. Erdös-Renyi experiments show scaling-law behavior even without power-law structure, while biased walks improve power-law fit quality.

  • Random walks and n-grams: Random-walk next-token prediction on a directed weighted graph is equivalent to learning bigram transition probabilities.The graph’s stationary node distribution corresponds to unigram frequencies, while edge transitions correspond to bigram probabilities.
  • Erdös-Renyi graphs: Erdös-Renyi graphs have degree distributions and spectra without power laws, providing data with no power-law structure for the experiments.Their degree distribution is tightly concentrated around the expected degree.
  • Erdös-Renyi graphs: Neural scaling laws appear for sequence models trained on Erdös-Renyi random walks, independent of power-law structure in the input data.The experiments use maximal update parameterization with context length 50.
  • Biased random walks: dialing into power laws: For biased walks with κ = 1, the transition probabilities follow an exponential rank relationship and the data distributions become smoother without acquiring power laws.The authors report that power-law fit quality improves in this intermediate case.
  • Erdös-Renyi graphs: At 1K nodes and 5K edges, the mean exponents are αD = 0.665 and βN = 0.684, with power-law fits outperforming exponential fits by average MSE.The average MSEs are 2.41e −08 versus 1.96 × 10−7 for L(N)D, and 3.37 × 10−8 versus 1.97 × 10−6 for L(D)N.

4 Dialing up complexity: from random graphs to natural language

The paper dials language complexity from bigrams toward transformer-generated language and tracks how scaling exponents change. The exponents interpolate across this hierarchy, while entropy and fitting limitations constrain how the complexity ladder is evaluated.

  • Complexity hierarchy: The study treats language complexity as increasing from bigram models toward natural language and measures how scaling exponents vary across that progression.It uses sequence models ranging from language bigrams to transformer-generated language.
  • Complexity measure: Entropy is used as a rough complexity measure, and n-gram sequence entropy decreases monotonically as n increases.Lower entropy corresponds to stronger predictive signal from preceding tokens in the paper’s interpretation.
  • Complexity limitations: Entropy for TnL sequences is not feasible to compute directly because sampling requirements grow exponentially with sequence length, and natural language lacks an intrinsic generative distribution.The paper instead approximates entropy using asymptotic cross-entropy-loss fits.
  • Language bigrams: The language-bigram experiment uses a GPT-2 tokenizer with vocabulary size 50,257 and approximately 130M unique bigrams from Fineweb-edu-10B.The resulting bigram probability distribution has a broken power-law form.
  • Language bigrams: For language bigrams, the mean exponents are αD = 0.977 and βN = 0.547 under a 2-layer transformer with µP and context length 50.The αD values range from 0.84–1.2, while βN ranges from 0.47–0.60.
  • Dialing up language complexity: The mean αD exponents interpolate between language-bigram and natural-language results across the simplified language models.The T4L results were nearly identical to T2L and were omitted from presentation.

5 Revisiting scaling laws for natural language modeling

The paper revisits language-model scaling laws, finding that shallow transformers with short contexts reproduce major prior results while exposing weaknesses in common fitting methods. It also reports alternative compute-optimal fits and preliminary evidence that µP may improve parameter efficiency.

  • Methodological analysis: Power-law fits should retain irreducible-loss offsets because omitting them substantially underestimates exponents and worsens fit quality.The authors report nearly a factor-of-two exponent difference and almost an order-of-magnitude MSE difference when the offset is neglected.
  • Short-context transformers: Two-layer transformers with short contexts recover major language-scaling patterns, including the Kaplan–Chinchilla discrepancy through embedding-parameter treatment.The paper reports that changing the learning-rate schedule is unnecessary for recovering the discrepancy.
  • Methodological analysis: Neural-network and kernel regressions fit L(N, D) better than the 2d Chinchilla formula, with nearly 2× lower average validation MSE.The comparison uses 80/20 splits, Huber loss, and averages MSE across 20 random splits.
  • Methodological analysis: The interpretable 1d fit achieves MSE 7.76 × 10−5 versus 4.77 × 10−4 for the 2d fit.The 1d fit is reported as almost an order of magnitude better on the analyzed Chinchilla data.
  • Compute-optimal scaling: A neural-network regression produces compute-optimal exponents γ = 0.16, a = 0.482, and b = 0.504, close to the 2d Chinchilla values.The corresponding Chinchilla-fit values are γ = 0.178, a = 0.513, and b = 0.487.
  • Short-context transformers: Including embedding parameters gives a/b ≈0.94, whereas excluding them gives (a, b) = (0.742, 0.386), close to the OpenAI result (0.73, 0.27).The paper connects this distinction to the discrepancy between Chinchilla and OpenAI scaling laws.
  • Parameterization: µP yields mean αD ≈0.5 in 2- and 4-layer Fineweb-edu transformers, compared with αD ≈0.35 for standard parameterization.The paper interprets this as preliminary evidence that µP may be more parameter-efficient for compute-optimal training.

6 Additional related work

The related-work discussion places the paper among studies of random-walk learning, data-manifold explanations, superposition, resource-based theories, and parameterization-dependent scaling. It emphasizes that the paper’s random-walk setting targets scaling-law origins rather than general learnability.

  • Transformers and random walks: Random-walk studies often examine capability or learnability, whereas this work uses graph random walks to study neural scaling laws.
  • Neural scaling laws: Data-manifold explanations appear inapplicable to this work because its sequences consist of discrete tokens with no obvious data manifold.
  • Neural scaling laws: Other proposed mechanisms include superposition and resource-based theories, whose relationship to the observed random-walk scaling laws remains open.
  • Scaling laws with µP: Prior work reported that µP gives approximately 1% better loss and more robust scaling laws at fixed tokens per parameter.
  • Scaling laws with µP: The paper reports µP as more parameter-efficient than standard parameterization at relatively small scales, with larger αD and smaller a.
  • Scaling laws with µP: Figure 13 reports mean αD = 0.501 and mean βN = 0.408 for a 2-layer Fineweb-edu transformer using µP.The power-law fits have lower average MSE than the best exponential fits for both L(N)D and L(D)N.

7 Discussion

The discussion argues that neural scaling laws arise even without power-law data correlations and vary systematically with dataset complexity. It also identifies optimization, fit-window sensitivity, and unresolved interpolation mechanisms as important boundaries.

  • Across language bigrams, TnL, and natural language, increasing dataset complexity produces a monotonic decrease in αD.
  • The observed αD ≳ βN pattern suggests losses are generally more limited by data than architectural capacity in this one-epoch setting.
  • Power-law fits outperform exponential fits substantially, with L(D)N fits achieving 50–100× lower MSEs across studied cases.
  • Neural scaling laws arise empirically on unbiased Erdös-Renyi random walks whose data have no power-law correlations.
  • The paper leaves systematic interpolation between bigrams and natural language, and the role of power laws in internal activations, for future work.
  • Scaling-law robustness remains constrained because optimization choices and fit windows can substantially alter losses and fitted parameters.

A Experimental details

The experiments train small decoder-only transformers on synthetic random walks and language-derived graphs under controlled optimization settings. Datasets are generated from weighted transition matrices, with graph and language constructions defining the transition structure.

  • Transformer architectures: The models are 2- or 4-layer pre-normalization decoder-only transformers with rotary positional embeddings and embedding dimensions from 128 to 4096.
  • Optimization: Training uses AdamW, weight decay 0.01, a learning-rate sweep, warmup, cosine decay, and three random seeds per configuration.
  • Data generation: Each synthetic sequence begins from an initial-node distribution and then samples T−1 successive nodes using the transition probabilities W_uv.
  • Data generation: Walks may revisit nodes and traverse the same edge multiple times.
  • Graph datasets: Graph datasets use binary symmetric adjacency matrices, while biased walks assign edge weights from a power-law distribution controlled by κ.
  • Language datasets: Bigram graphs are built from filtered GPT-2-tokenized Fineweb-edu data, leaving approximately 33M unique bigrams.

B.1 L(N)D and L(D)N fits

The fitting procedure compares robust power-law models with exponential alternatives and uses bootstrap methods for uncertainty. The paper evaluates fit quality through MSE and uses several regression approaches for two-dimensional loss surfaces.

  • Power-law fits: The authors fit L(D)_N and L(N)_D power laws using Huber-robust least squares with an adaptively chosen cutoff δ.
  • Optimization: The nonlinear fit optimizes over E, log A, and log β with bounded β, using multiple initializations and retaining the lowest Huber objective.
  • Fit validation: Power-law and exponential fits are compared using their MSEs to test whether power-law scaling better describes the data.
  • Fit validation: L(D)_N power-law fits are 50–100× better in MSE than the best exponential fits across the studied datasets.
  • Confidence intervals: Parameter uncertainty is estimated with fixed-x wild bootstrap samples, BCa intervals, and 4,000 bootstrap replicates.
  • Two-dimensional fits: Two-dimensional L(N,D) fits compare a Chinchilla formula, neural network regression, and kernel ridge regression under Huber loss.

B.4 Fitting compute optimal scaling laws, Lopt, Nopt, Dopt

Compute-optimal curves are extracted from a fitted two-dimensional loss surface rather than directly from a fixed analytic form. The method uses grid-based minimization and then fits power laws to the resulting optimal quantities.

  • Compute-optimal curves: The neural-network fit estimates compute-optimal loss by minimizing L̂(N,C/6N) or L̂(C/6D,D) over sampled grids.
  • Compute-optimal curves: Optimal model size Nopt(C) and dataset size Dopt(C) are obtained from the fitted surface and regressed in log space to extract compute-optimal exponents.
  • Caveats: Boundary regions and optima outside the sampled grid require manual clipping because fitted quantities can become spurious there.
  • Model comparison: The authors report neural-network regression results because it usually produces more sensible compute-optimal curves than kernel regression.
  • Caveats: Fit parameters are sensitive to the selected fitting window, motivating further sensitivity analysis.
  • Model comparison: The 2d Chinchilla fit has MSE about 30–40× worse than the neural-network and kernel fits.

C Sample error baseline

The paper analyzes counting-based probability estimates as a baseline for data scaling laws. The estimator is formed from empirical frequencies, whose large-sample behavior follows from averaging independent indicator variables.

  • C Sample error baseline: The counting estimate assigns each outcome a probability based on its observed frequency in D samples.For outcome a, the count n_a determines its empirical probability estimate.
  • C Sample error baseline: The analysis extends prior counting-model results by deriving data scaling laws for mean-squared error and cross-entropy losses.The stated baseline is intended for comparison with the random-walk scaling-law results.
  • C Sample error baseline: Each empirical probability is the sample mean of an indicator variable for whether the sampled outcome equals a.The indicator has a Bernoulli distribution with the target probability π_a.
  • C Sample error baseline: In the large-D limit, the empirical probability is approximately Gaussian because it averages D independent binary variables.The variance is σ^2 = π_a(1 − π_a).

C.1 Mean squared error

For counting estimates, both mean-squared error and cross-entropy exhibit asymptotic population-loss scaling with exponent β = 1. The random-walk application uses node-specific effective sample sizes, with smoothing required for finite-sample cross-entropy.

  • C.1 Mean squared error: β = 1 is the asymptotic power-law exponent for population loss under both mean-squared error and cross-entropy.The result is stated for the counting model and can be checked empirically.
  • C.1 Mean squared error: For graph random walks, each node v has an effective dataset size Deff,v = p(v)D for learning p(u|v).The node frequency determines how many training tokens contribute to estimating its conditional distribution.
  • C.1 Mean squared error: The total random-walk cross-entropy averages the node-specific losses over the nodes.For an unbiased walk, p(u|v) = Auv/deg(v) and p(v) = deg(v)/2E.
  • C.1 Mean squared error: Finite-sample cross-entropy requires implicit smoothing when an empirical probability is zero although the true probability is nonzero.This qualification applies because the counting estimate can assign zero probability to observed-unseen outcomes.

D Additional scaling law results

Additional experiments report scaling-law fits for language and random-walk data on scale-free and Erdős-Rényi graphs. The reported power-law fits have lower mean-squared errors than the corresponding best exponential fits in the shown results.

  • D Additional scaling law results: Over 100 million language bigrams appear only a handful of times, producing a near-linear relationship on a log-log count plot.The figure describes a perfect linear fit on the log-log scale.
  • D Additional scaling law results: αD = 0.391 and βN = 0.550 for the 4-layer Fineweb-edu transformer with Standard Parameterization.The power-law fits have lower average MSE than the best exponential fits for both reported loss slices.
  • D Additional scaling law results: αD = 0.815 and βN = 0.735 for the scale-free Barabási-Albert graph with 8,192 nodes.The reported power-law fit errors are lower than the corresponding best exponential-fit errors.
  • D Additional scaling law results: α = 2.443 and β = 1.361 for the unbiased Erdős-Rényi graph, while biased sampling gives α = 2.169 and β = 0.847.For both sampling settings, the reported power-law fits have lower average MSE than the best exponential fits.
Loading 2601.10684v1…