From "the" to the Tail: Prefix-Indexed Adam States Under Zipf's Law

PrefixAdam stores the vocabulary optimizer state in up to 17.8× less memory than AdamW (up to 9.0× less than Adam-mini) and attains the lowest rare-token loss in all three benchmarks, with lower overall loss than every baseline in two of them (all six baselines, 8/8 seeds, on a real-text V = 8192 model), backed by five new exact theorems checked by thirteen verification scripts. In a standard English language-model run, the token "the" appears roughly once every sixteen words, while four-fifths of the vocabulary appears only a handful of times per epoch. AdamW allocates the same 2d state scalars to "the" and to a word seen twice, whereas factored and block methods (Adafactor, Adam-mini) keep one second-moment scalar per row and discard row-specific curvature on frequent tokens. We replace uniform V×d optimizer state with a flat signed lookup table inspired by table-driven Huffman decoders: each token j carries one signed 64-bit header hdr[j]; hdr[j] > 0 indexes a small dense pool Pool[K_hot, d] (K_hot ≪ V), and hdr[j] ≤ 0 is a self-contained terminal leaf holding 63 bits of scalar sufficient statistics with no R^d state vectors. The resulting optimizer is PrefixAdam. Five exact results justify the construction: Anisotropic sparse features and momentum. Building on the exact finite-(d,B,η,β) second-moment theory of Paiva (2026, doi:10.5281/zenodo.24074237), feature conditioning accelerates frequent tokens up to √κfeat× under momentum, yet on rare tokens (Bqj ≪ 1) the per-step decay rate is independent of β1 to leading order, with marginal momentum slope equal to twice a spectral variance. With label noise, at a matched loss floor the tail gain vanishes exactly above a unique crossover floor, stays below 2×, and approaches 2 as 2 − 4√((dd+2)δ/dcond). Silent monoid. Silent evolution under arbitrary learning-rate and weight-decay schedules forms a subtraction-free associative monoid evaluated in O(1) time, so pool slots can be evicted after Δcut silent steps within float32 precision. Empirical-Bayes leaves. By an exact Fay–Herriot L2 decomposition, a zero-vector 64-bit leaf has strictly lower second-moment estimation error than d-float AdamW on every token with fewer than n☆ hits; threshold promotion is the exact Lagrangian optimum, and under Zipf(α) the memory–risk frontier is explicit (pool size grows as N1/α, residual leaf excess decays as K1−α for α > 1). Hit-arrival law. The conditional stationary second moment of dense AdamW at active hits equals ((1−β2)+β2pj)θj, removing √((1−β2)t) first-hit step spikes. Softmax calibration. On Softmax readout layers, same-step denominators give rare tokens the stationary calibration pj☆/qj → (1 − (1−β2)/(2πj))+, collapsing once a token appears in fewer than a fraction (1−β2)/2 of batches, whereas predictable leaf denominators restore exact calibration; an exact three-regime phase transition at β2,sil = αs prevents unseen-token repulsion runaway. In three small controlled benchmarks (anisotropic Zipfian regression, a real-text log-bilinear model with V = 8192, and a two-layer causal Transformer), PrefixAdam uses 4.9×–17.8× less vocabulary state than AdamW and 2.5×–9.0× less than Adam-mini and attains the lowest rare-tail loss in all three. It also has the lowest overall loss in the first two, but not in the Transformer, where tuned dense and factored baselines (including Ember) are better on frequent tokens and overall. Thirteen verification scripts reproduce every theorem numerically.