Exact Scaling Laws for a Random-Features Bigram Model
Julian Enoch, Elvis Dohmatob
cs.LG
2026-10-14
Random-feature bigrams yield an exact regret law in width N, vocabulary d, and Zipf α. On WikiText-2 and OpenWebText2, sublinear width leaves a floor near α=0.94.
Kaplan et al. (2020) write language-model loss as a power law in parameters, data, and compute, and training budgets follow that fit. A similar decay can come from too few samples, a representation that cannot hold the predictor, or optimization that stops short. One training run does not separate the three.
Kunstner and Bach (2025) study an unconstrained bigram: one next-token distribution per context, so the parameter count is d squared. The knob is the number of gradient steps. For a Zipf exponent α>1, normalized regret falls about as steps to the power -(1-1/α). That exponent matches Hutter (2021) on sample size, but the resource is optimization steps. Neither paper has a width independent of d, so neither prices the error from compressing the transition table.
Real embeddings are much narrower than the vocabulary. This paper measures that capacity gap alone, and reads off how a Zipf tail charges width for storing predictive information.
Rank-i frequency follows Zipf, proportional to i to the -α. For every context, the sum of squared next-token probabilities equals the same constant A. A closer to 1 means a sharper next-token distribution. The loss is squared Frobenius norm: a linear map sends the current one-hot token to the next one.
Unconstrained W is d by d. The bottleneck sets W=ΩΘ. Ω is a fixed d by N random matrix with independent entries of mean 0 and variance 1/d. Θ is N by d and the only trained factor, so the trainable count drops from d squared to Nd. Θ is optimized inside the bottleneck, and the remaining regret has no optimization residual.
Normalized regret is the excess loss over the unconstrained empirical optimum, divided by the gap from zero weights to that optimum. In a large sample the denominator is about A.
Conditioned on the empirical counts, expected regret is bias plus variance. Bias is B=AN ν, with ν defined by N equal to the sum of p̂/(p̂+ν) over contexts. Width assigned to a context scales as frequency over frequency plus ν, so common contexts are fit first and the tail sets ν. Variance is (1-A) times the positive part of (S-N), divided by n. S is the number of contexts that actually occur, and the term is nonzero only for N<S. Once N is at least S and Ω has full rank on those rows, both terms vanish and the empirical transitions can be copied row by row. If N stays fixed below d, more samples do not remove the bias.
Theorem 2 also needs n much larger than d to the α times the Zipf partial sum. For α<1 that sum grows like log d, so superlinear n is enough, and both full corpora qualify. Variance is then about d/n when N is of lower order than d, and about (1-N/d)d/n when N scales linearly with d.
If α<1 and N is of lower order than d, bias tends to A. If α=1 and N equals γ times d to the β with β<1, the floor is about A(1-β) plus (1-A)d/n, and γ is absent from that leading term. For β=1 the expression becomes A/(q log d) plus (1-A)(1-γ)d/n. If α>1, bias scales as Cα times N to the -(α-1), the same exponent Cabannes et al. (2024) derived for associative memory. The corpora have α of 0.9354 and 0.9443, close to critical from below, outside that power law.
| Setup | Quantity | Value |
| WikiText-2, full | vocab / tokens / α | 33277 / 2051910 / 0.9354 |
| OpenWebText2, full | vocab / tokens / α | 50257 / 2110824721 / 0.9443 |
| Bottleneck vs full bigram | trainable parameters | Nd versus d squared |
| α>1 | bias vs width | proportional to N to the -(α-1) |
| α=1 and β<1 | leading regret | A(1-β)+(1-A)d/n |
| Experiment, β=1, γ=1 | normalized regret | falls to 0 |
| Experiment, β<1 | normalized regret | a floor remains and flattens as γ grows |
Synthetic Zipf draws are included with WikiText-2 and OpenWebText2; Table 1 labels the second corpus OpenWebText. Width is γ times d to the β, with β in {0.5, 0.65, 0.8, 1} and γ in {0.5, 1, 2}, and the horizontal axis runs to about 2. The two scales are vocabulary 10^3 with 10^5 tokens, and vocabulary 10^4 with 10^6 tokens, so d/n is 0.01 in both, trained to convergence. Solid curves average random projections. Dashed curves are Theorem 2.
On WikiText-2 the dashed curves track the solid ones. At β=1 and γ=1, N equals the vocabulary and regret hits 0. For β<1 a floor remains. OpenWebText2 departs from an ideal Zipf law in the head and the tail, and the curves still track the prediction. Raising γ in the sublinear regime buys less and the curves flatten, because the d/n term survives whenever width grows slower than the vocabulary.
No numeric error between the curves is reported. The match is read off the figure. There is no direct comparison with Transformer training loss.
Heavy-tailed frequencies plus an explicit width still leave a regret that depends on N, d, and α after the fit inside the bottleneck is optimal. At α=1 with β<1, the leading floor is A(1-β), and raising γ does not move it. The two corpora sit near α=0.94, close to that case. Strictly below α=1, with lower-order width, the leading term is the constant A. In the plots, regret hits 0 when N equals the vocabulary.
This is not a training budget. Squared loss, a bigram, and a frozen embedding measure how much of the empirical transition table rank N can store. A model whose embedding is far narrower than its vocabulary predicts with longer context, not by storing that full table. The usable role is a baseline: swap in learned embeddings, longer context, or a finite step budget, and see whether the same Zipf tail still controls the curve.
Against the step-count laws, the resource here is width, and the representation is already optimal inside the bottleneck. Against Cabannes et al., the α>1 exponent agrees. The addition is keeping d in the formula and scoring squared regret on conditional next-token probabilities. Only α at most 1 covers these two corpora.
Three extensions are left open: learned embeddings, dependencies past a bigram, and a finite optimization budget. The constant A forces every context to be equally peaked. The metric is empirical squared regret, not population cross-entropy.
The figures cover the toy. Vocabularies are 10^3 and 10^4, not the full 33277 and 50257, and not a language model. At α≈0.94 the crude subcritical statement says bias tends to A when width is of lower order than d. The plots split by β and the dashed lines still track, so they follow the general fixed point, not that constant leading term. The paper describes these regimes as closer to the functional form in Kaplan et al. (2020). It does not turn the formula into a power of parameter count, and it supplies no external exponent to check.
The title says exact. The scaling statements are large-sample asymptotics: n must be much larger than d to the α times the partial sum. On the experimental subsets n/d equals 100, and nothing in the paper breaks that condition and reports the damage.