Exact Scaling Laws for a Random-Features Bigram Model

1. Introduction

• Zipfian token frequencies raise the question of whether accurate bigram prediction requires a separate next-token distribution for every context or can use a smaller representation.The broader aim is to connect the cost of compressing predictive information to the power-law structure of language.Source: §1 · p. 1

1.1. Contributions

• A fixed random embedding imposes a width-N bottleneck with dN trainable parameters, isolating limited-capacity regret from optimization error.The model extends the unrestricted bigram setting of Kunstner and Bach (2025) and complements their analysis of optimization steps.Source: §1.1 · p. 2
• Exact regret laws track vocabulary size, sample size, embedding dimension, and Zipf exponent, distinguishing sublinear and linear capacity regimes.The laws include vocabulary-occupancy and empirical-transition variability effects, and recover the functional form of classical neural scaling laws in an appropriate regime.Source: §1.1 · p. 2
• Experiments on WikiText-2 and OpenWebText2 support the predicted scaling curves across vocabulary sizes, sample sizes, and embedding dimensions.They examine regret decay under sublinear capacity and its approach to zero as the bottleneck widens sufficiently.Source: §1.1 · p. 2

1.2. Related work

• Prior analyses address sample-size or optimization scaling but do not characterize approximation error from an independently variable embedding-width budget.The paper distinguishes this capacity axis from optimization-time scaling in Kunstner and Bach (2025) and from associative-memory retrieval error in Cabannes et al. (2024).Source: §1.2 · pp. 2–3
• The contribution is a discrete Zipfian next-token setting with explicit random-embedding capacity, not the general introduction of capacity into scaling-law theory.It also differs from spectral random-feature theories and models based on separately acquired language skills or attention dependencies.Source: §1.2 · pp. 3–4

2. Theoretical Setup

• Each word has an index in a vocabulary of size d, context frequency p_i, and conditional next-word frequency π_j|i, defining a distribution over word pairs.The distribution is assumed to have Zipf marginals and constant collision probability, with α and A entering the theory.Source: §2 · p. 4

2.1. Unconstrained Bigram Model

• The unconstrained model fits next-token outputs from an i.i.d. sample of n context/next-word pairs by minimizing squared loss over W.For fitted W, the predictor selects the highest-scoring next token; performance can also be assessed by top-k accuracy.Source: §2.1 · p. 5
• Prior gradient-descent analyses vary optimization horizon, whereas this study retains vocabulary size and sample size and adds independently adjustable embedding width.The earlier results describe optimization-time scaling under idealized Zipfian assumptions and do not explicitly track finite-sample fluctuations.Source: §2.1 · p. 6

2.2. A Capacity-Constrained Biagram Model

• Factoring W through an embedding matrix Ω and learnable Θ reduces trainable parameters from d² to Nd, with N ≤ d.The embedding entries are i.i.d. with zero mean, variance 1/d, and Gaussian concentration; the analysis focuses on expected normalized regret of the fitted predictor.Source: §2.2 · pp. 6–7

3.1. Bias-Variance Decomposition

• The conditional expected regret splits into a bottleneck bias B and a finite-sample variance V, with ν = 0 when N ≥ S.For N < S, B depends on the empirical context-frequency profile and decreases with embedding width; with fixed N < d, more observations need not eliminate it.Source: §3.1 · pp. 7–8

3.2. Sketch of Proof of Proposition 1

• The proof conditions on empirical counts, uses transition-matrix concentration, then applies random matrix theory to estimate projection terms and obtain the decomposition.The projection estimate is h_k ≃ c_k/(c_k + Nν).Source: §3.2 · pp. 8–9

3.3. Explicit Scaling Laws

• Regret is approximated by B + V, with B = A N^ν; V captures finite-sample variability and vanishes when N ≥ S.The decomposition conditions on observed context counts; the unconstrained model has N = d ≥ S, so V = 0.Source: §3.1 · pp. 7–8, §3.3 · p. 9
• For α > 1, the capacity term scales as B ≃ C_α N^−(α−1); in sub-critical and critical regimes, the derived laws better match observed Kaplan et al. (2020) scaling forms.The explicit laws assume n ≫ d^α H_{d,α}; for α < 1, this condition is satisfied by language datasets with α < 1 when sample size grows super-linearly with vocabulary size.Source: §3.3 · p. 10

3.4. A Canonical Scaling for the Embedding Dimension

• For α = 1 and n ≫ d log d, the canonical width N = γd^β yields distinct regret expressions for β < 1 and β = 1.For β < 1 the expression is A(1−β) + (1−A)ϕ; for β = 1 it is A/(q log d) + (1−A)(1−γ)ϕ.Source: §3.4 · p. 10

4.1. Experimental Setup

• The experiments optimize a rank-N random-projection bigram model to convergence and measure normalized excess risk against the unconstrained empirical optimum.Width is parameterized as N = γd^β, with sweeps probing linear (β = 1) and sublinear (β < 1) regimes.Source: §4.1 · pp. 10–11

4.3. Results

• Across datasets, empirical excess risk aligns with theoretical predictions, and OpenWebText2 supports robustness to realistic corpus artifacts.On WikiText-2, regret reaches zero at γ = 1 when β = 1 but retains a nonzero floor when β < 1; on OpenWebText2, predictions remain accurate despite noisier token frequencies.Source: Figure 1 · p. 11, Figure 2 · p. 12, §4.3 · p. 13

4.2. Datasets

• Experiments cover Zipf-generated synthetic data, WikiText-2, and OpenWebText2, estimating real-corpus vocabulary size, token count, and Zipf exponent from each full dataset.Source: §4.2 · p. 12

4.3. Results

• In the sublinear-width regime, regret improvements diminish as γ rises, consistent with a finite-sample variance term that persists when width grows too slowly relative to vocabulary size.Source: §4.3 · p. 13

• The results isolate representational capacity as a source of scaling, complementing explanations based on optimization dynamics.Source: §5 · p. 13
• Keeping vocabulary size explicit distinguishes increasing capacity for a fixed prediction problem from enlarging the problem itself.Source: §5 · p. 13
• The framework provides a quantitative benchmark for capacity-driven scaling, while extensions could examine learned embeddings, longer contexts, and finite optimization budgets.Source: §5 · p. 14

• Generative AI was used for spell-checking and reformulating portions of the introduction.Source: AI use statement · p. 14
• AI also assisted with tedious verification and sanity-checking of some proofs.Source: AI use statement · p. 14
• The authors report no other AI use and take responsibility for the final content.Source: AI use statement · p. 14

• The proof first defines empirical transition rows and uses them to express the regret of any student relative to the unconstrained empirical minimizer.Source: §A.1 · p. 16
• It then restricts students to W = ΩΘ and represents the optimal student through the projection onto the restricted random-embedding subspace.Source: §A.1 · pp. 16–17
• Sign-flip symmetry of the random projection makes the expected projection matrix diagonal; the proof relates its diagonal entries to leverage-score-like quantities.Source: §A.1 · pp. 17–18
• Random matrix theory approximates each leverage score as h_k ≃ c_k/(c_k + μ), yielding the corresponding residual factor 1 − h_k ≃ μ/(c_k + μ).Source: §A.1 · pp. 18–19

A.2. Proof of Theorem 2

• For 0 ≤ α < 1, sublinear width gives B ∼ A, while proportional width gives B ∼ A(1 − α) ψ ρ(α, ψ).These laws follow from the small-ρ integral limit and the normalization H_d,α ∼ d^(1−α)/(1 − α).Source: §A.2 · p. 20
• At α = 1, the proof evaluates the integral explicitly and uses the discrete fixed point for proportional width.It defines q from H_d,1 and ν, then distinguishes the sample-dependent fixed point from its population counterpart.Source: §A.2 · pp. 19–21
• For α > 1 and sublinear width, the integral constant is π/[α sin(π/α)]; proportional width instead gives B ∼ A ζ(α)d^(1−α) ψ ρ(α, ψ).The proportional-width dependence remains proportional to N^−(α−1), with a prefactor that also depends on ψ.Source: §A.2 · pp. 21–22
• Concavity of the fixed-point solution and Jensen’s inequality support relative L1 convergence of the empirical solution to its population counterpart.The proof controls an aggregate rather than requiring uniform concentration of all empirical frequencies.Source: §A.2 · pp. 22–23
• The two main regret terms equal B + V + o_L1(B + V), yielding the stated approximation when E|ε(c)| = o(B + V).The sample-size assumption ensures even the least frequent context has a diverging expected count.Source: §A.2 · pp. 22–24
• The proportional-width proof assumes ψ0 < 1; at N = d, the separate interpolation branch makes both contributions vanish.When N/d approaches one, the occupancy estimate may not give a relative approximation because d − N can be too small.Source: §A.2 · p. 24