PaperlayerView exact revision on arXiv

Source-linked AI summary

The Coverage Principle: How Pre-Training Enables Post-Training

Fan Chen, Audrey Huang, Noah Golowich, Sadhika Malladi, Adam Block, Jordan T. Ash, Akshay Krishnamurthy, Dylan J. Foster

arXiv:2510.15020v2stat.MLcs.AIcs.CLcs.LGmath.STstat.TH

TL;DR

The paper asks why pre-training quality measured by cross-entropy does not reliably predict downstream performance. It analyzes coverage as the missing link, showing that coverage is tied to Best-of-N success and that next-token prediction implicitly optimizes it while avoiding cross-entropy’s sequence-length dependence.

  • Problem

    The relationship between next-token prediction loss and downstream performance is poorly understood, and cross-entropy can fail to predict post-training success.

    Source: §1 · pp. 1–2

  • Method

    The paper develops a theoretical coverage framework and studies maximum likelihood, SGD, model selection, gradient normalization, and decoding interventions.

    Source: §1 · p. 2, §6.3 · p. 14

  • Results

    Coverage is necessary and sufficient for Best-of-N success, predicts downstream performance better than cross-entropy in the highlighted comparison, and generalizes faster without spurious sequence-length dependence.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Coverage offers a theoretical lens for understanding and improving when pre-training enables effective post-training and test-time scaling.

    Source: §7 · p. 15

    Sequence-level cross-entropy and KL-based scaling laws can grow with sequence length and cannot hold under only bounded token-level cross-entropy.

    Source: §3 · pp. 5–6

Abstract

from arXiv · show

Language models demonstrate remarkable abilities when pre-trained on large text corpora and fine-tuned for specific tasks, but how and why pre-training shapes the success of the final model remains poorly understood. Notably, although pre-training success is often quantified by cross-entropy loss, cross-entropy can be a poor predictor of downstream performance. Instead, we provide a theoretical perspective on this relationship through the lens of \emph{coverage}, which quantifies the probability mass the pre-trained model places on high-quality responses and which is necessary and sufficient for post-training and test-time scaling methods such as Best-of-N to succeed. Our main results develop an understanding of \emph{the coverage principle}, a phenomenon whereby next-token prediction (more generally, maximum likelihood) implicitly optimizes toward a model with good coverage. In particular, we uncover a mechanism that explains the power of coverage in predicting downstream performance: \emph{coverage generalizes faster than cross-entropy}, avoiding spurious dependence on problem-dependent parameters such as the sequence length. We also study practical algorithmic interventions with provable benefits for improving coverage, including (i) model/checkpoint selection procedures, (ii) gradient normalization schemes, and (iii) test-time decoding strategies.

1 Introduction

The paper studies why stronger next-token prediction does not reliably yield stronger downstream performance, proposing coverage as the missing link. It develops the coverage principle and theoretical and algorithmic tools for improving coverage.

1 Introduction

  • Coverage quantifies probability mass on high-quality responses and is necessary and sufficient for Best-of-N to succeed, while cross-entropy can be poorly correlated with downstream performance.The paper highlights coverage as a refinement of cross-entropy that captures rare but high-quality responses.Source: §1 · p. 2

1.1 Contributions

  • Next-token prediction implicitly optimizes toward models with good coverage, inheriting the training corpus’s coverage over tasks of interest.The analysis provides a fine-grained view of maximum likelihood through coverage.Source: §1.1 · pp. 2–3
  • Cross-entropy scaling laws can become vacuous because they depend on sequence length and other problem parameters, motivating coverage-based analysis.The paper frames this limitation as a reason to seek metrics that more directly predict downstream success.Source: §1.1 · p. 2
  • Coverage generalizes faster than cross-entropy, avoiding spurious dependence on sequence length and improving further as the Best-of-N tail parameter N increases.This mechanism explains why coverage can better predict downstream success than cross-entropy.Source: §1.1 · p. 2
  • In overparameterized autoregressive linear models, one-pass SGD optimizes coverage but has suboptimal sequence-length dependence; gradient normalization removes that dependence and improves coverage.A further normalization scheme improves coverage in expert distillation, where teacher token logits are available.Source: §1.1 · p. 3
  • Test-time training-inspired decoding provably improves coverage for standard token-level SGD.This is one of the paper’s proposed interventions beyond standard next-token prediction.Source: §1.1 · p. 3
  • Tournament procedures for selecting among a small number of models or checkpoints achieve better coverage, especially in the tail parameter N, than cross-entropy validation.The paper also studies additional coverage properties, including low coverage under severe misspecification and faster generalization under convexity.Source: §1.1 · p. 3

2 Problem Setup

The paper formalizes pre-training and post-training through coverage, then characterizes when maximum likelihood yields models whose probability mass supports successful downstream scaling. It also distinguishes coverage from cross-entropy by its finer tail sensitivity, practical estimability limits, and reduced dependence on sequence length.

2 Problem Setup

  • Maximum likelihood is formulated over prompt-response distributions, with autoregressive next-token prediction as the sequence-valued special case.The estimator maximizes empirical log likelihood over a realizable model class, and autoregressive probabilities factor across response tokens.Source: §2 · p. 3
  • Best-of-N succeeds when the pre-trained model has good coverage for a downstream comparator policy, with reward gap scaling as CovN(πT ∥bπ).The setup treats coverage as sufficient for high reward and notes that some post-training methods are also believed to require it.Source: §2 · p. 4
  • The data distribution must itself assign nontrivial probability to high-reward responses; coverage then transfers to the downstream optimal policy through transitivity.For example, 10% data-distribution success combined with CovN/10(πD ∥bπ) = ε yields 10ε error.Source: §2 · p. 4
  • The analysis uses autoregressive linear models with bounded parameters and features, while noting that frozen-feature models can still represent complex non-Markovian dependencies.These assumptions provide the paper’s running model class and regularity conditions.Source: §2 · p. 4

2.1 Properties of the Coverage Profile

  • Coverage is a budget-sensitive refinement of cross-entropy: it is the CDF of log density ratios, whereas KL divergence captures only their mean and can miss tail behavior.This explains why coverage can differ substantially from KL across inference scales.Source: §2.1 · p. 4
  • Coverage and KL are generally not estimable because they depend on the unknown data density, so cross-entropy serves as an estimable KL upper bound and proxies can support model selection.Expert distillation is an exception because teacher log-probabilities are available; Figure 2 illustrates coverage’s weaker sequence-length dependence than KL.Source: §2.1 · p. 4, Figure 2 · p. 5

3 Cross-Entropy and Coverage: Scaling Laws and Limitations

Cross-entropy can relate to coverage through sequence-level KL divergence, but its dependence on sequence length and missing mass limits downstream predictions. The section motivates coverage as a more reliable lens for Best-of-N performance, including cases where cross-entropy is large or infinite.

Cross-Entropy and Coverage

  • Cross-entropy fails to provide predictive finite-sample guarantees for downstream performance despite converging asymptotically under maximum likelihood.The section uses this insufficiency to motivate direct analysis of coverage rather than relying on cross-entropy alone.Source: §3 · p. 5

A simple scaling law for cross-entropy

  • Coverage can be bounded by sequence-level KL divergence, yielding a Best-of-N test-time compute scaling law under suitable data coverage assumptions.For N ≥ e, Cov_N(π_D ∥ b_π) ≤ D_KL(π_D ∥ b_π), and combining this bound with downstream coverage assumptions gives a sufficient compute budget for target sub-optimality.Source: §3 · p. 5

Insufficiency of cross-entropy

  • Sequence-level cross-entropy and KL divergence can grow with sequence length, predicting exponential test-time scaling in length even when token-level cross-entropy is modest.Such a prediction cannot hold from bounded token-level cross-entropy alone, exposing a problem-dependent dependence in the scaling law.Source: §3 · pp. 5–6
  • Worst-case constructions show that sequence-level KL divergence can scale linearly with sequence length, including for autoregressive linear models.This establishes that the length dependence is not merely an artifact of a loose analysis.Source: §3 · p. 6

Case study in Bernoulli models

  • In a graph reasoning case study, next-token prediction achieves good coverage and successful Best-of-N across sequence lengths despite large cross-entropy or KL divergence.The result suggests that the next-token objective’s inductive bias, rather than low sequence-level cross-entropy alone, may explain the observed coverage.Source: §3 · p. 6

A glimmer of hope: Case study in Bernoulli models

  • The Bernoulli example shows that maximum likelihood can have infinite expected KL divergence while retaining well-behaved coverage, with coverage controlled differently across sample-size regimes.When n ≳ log(δ^-1)/p⋆, a binomial tail bound gives b_p ≥ p⋆; when n ≲ log(δ^-1)/p⋆, missing mass yields Cov_N(π_D ∥ b_π) ≤ p⋆ ≲ log(δ^-1)/n.Source: §3 · p. 6

Insufficiency of cross-entropy

  • Missing mass can make KL divergence and cross-entropy large through log W_max contributions, especially when prompts are heterogeneous or the sequence length is large.The underlying issue is that a learner may fail to cover responses lacking enough information for generalization or extrapolation.Source: §3 · p. 6

4 Next-Token Prediction Implicitly Optimizes Coverage

Maximum likelihood implicitly favors models with good coverage: its coverage profile can generalize faster than cross-entropy, avoiding explicit sequence-length dependence under the paper’s assumptions.

4 Next-Token Prediction Implicitly Optimizes Coverage

  • Theorem 4.1 shows that maximum likelihood learns models whose coverage profile generalizes faster than cross-entropy, with no explicit sequence-length dependence in the fine-grained term.The rate improves with larger N through a 1/log N factor, reflecting the logarithmic loss’s implicit bias.Source: §4 · pp. 6–7
  • Coverage can remain well controlled under misspecification through the best-in-class coverage profile, and tournament estimators extend this guarantee to arbitrary model classes.The maximum-likelihood guarantee may depend on approximation error, whereas tournament procedures scale with the best available coverage even for non-convex classes.Source: §4 · p. 7, §4.3 · p. 10

4.1 Examples

  • For autoregressive linear models, inherent variance acts as an effective sequence length, and next-token prediction achieves nearly horizon-independent coverage when this variance is smaller than worst-case B^2H.The bound is tight: in the overparameterized regime, n ≥ H can be necessary when σ⋆^2 ≍ H.Source: §4.1 · p. 8

4.2 Proof Sketch

  • The proof uses one-sided concentration: models with large coverage incur sufficiently low empirical log-likelihood to be excluded by maximum likelihood.This one-sided argument avoids paying for density-ratio ranges or sequence length in the same way as two-sided cross-entropy control.Source: §4.2 · pp. 8–9

4.3 Tightness of Theorem 4.1

  • Both coarse- and fine-grained terms in Theorem 4.1 are tight, so their covering-number dependence cannot generally be removed or replaced by only coarse-scale complexity.These are algorithm-specific lower bounds, and Section 6 shows that coverage-designed algorithms can improve over maximum likelihood.Source: §4.3 · p. 10

5 Stochastic Gradient Descent Through the Lens of Coverage

In autoregressive linear models, one-pass SGD can achieve suboptimal coverage because heterogeneous gradient scales create conflicting learning-rate requirements, while normalized SGD removes the sequence-length dependence.

5 Stochastic Gradient Descent Through the Lens of Coverage

  • The analysis studies stochastic gradient descent on autoregressive linear models in the single-pass, compute-optimal regime rather than only analyzing an empirical maximum-likelihood solution.This setup models contemporary training that uses one or fewer passes over the corpus.Source: §5 · p. 10, §5.1 · p. 11

5.1 Stochastic Gradient Descent has Suboptimal Coverage

  • One-pass SGD converges in KL divergence but yields a coverage bound with an unfavorable sequence-length dependence, and a matching lower bound shows this degradation is real.Some prompts require η ≲ 1/(HB) to avoid divergence, while others need η ≫ 1/(HB) for fast convergence.Source: §5.1 · pp. 10–11

5.2 Gradient Normalization Improves Coverage

  • Gradient normalization achieves a horizon-independent coverage bound for mini-batched SGD under suitable choices of η and λ.The guarantee has a qualitatively similar rate to next-token prediction, although its dependence on the target coverage level ε is worse.Source: §5.2 · p. 11
  • Mini-batching is necessary to control bias introduced by gradient normalization, but mini-batching alone does not provide the result.The proposed update is related to SignSGD, while Adam becomes a similar per-coordinate normalization when certain mechanisms are disabled.Source: §5.2 · pp. 11–12

6 Interventions for Better Coverage

The paper proposes coverage-driven interventions across test-time training, distillation, and model selection, each with provable improvements over conventional procedures under stated assumptions.

6.1 Improving Coverage at Test Time

  • Token-level test-time SGD removes the sequence-length dependence of standard SGD’s lower bound and achieves a horizon-independent coverage guarantee.Its guarantee matches and slightly improves the next-token-prediction bound, with leading terms improved by factors of 1/√log N and 1/log N.Source: §6.1 · p. 12

6.2 SGD: Improved Gradient Normalization for Distillation

  • In the distillation setting, truncated gradient normalization matches the maximum-likelihood coverage rate by stopping token-level updates when cumulative teacher–student KL becomes too large.The method exploits access to the teacher’s next-token probabilities and keeps the accumulated token-level divergence normalized.Source: §6.2 · p. 13

6.3 Selecting for Coverage

  • Coverage-based tournament procedures can select checkpoints or hyperparameters with better coverage than cross-entropy selection and need not assume that the data distribution lies in the model class.They are intended for downstream RL fine-tuning or test-time scaling, where poor coverage can limit later performance.Source: §6.3 · p. 13
  • For infinite model classes, tournament estimators can improve over maximum likelihood by retaining only coarse-grained complexity dependence, including in well-specified settings.The estimators can be instantiated on a covering of the class.Source: §6.3 · pp. 13–14
  • The basic tournament is nearly as good as the best candidate but incurs an additive 1/N^(1−a) term, while an on-policy variant removes that term.The improved estimator requires a stronger closeness condition on the best-in-class model and is more complex to implement.Source: §6.3 · p. 14

7 Discussion and Future Work

The discussion frames coverage as a lens for explaining why pre-training supports post-training, while identifying formulation assumptions and directions for extending the theory.

7.1 Simplifications in the Problem Formulation

  • The formulation simplifies language-model pre-training by treating sequences as prompt–response pairs, though the authors expect the insights to extend to variable-length sequences without this split.Source: §7.1 · p. 15
  • The analysis largely assumes realizability, while Appendix E suggests coverage is more tolerant of misspecification than KL-divergence and leaves deeper study open.Source: §7.1 · p. 15
  • The prompt distribution is assumed identical during pre-training and post-training; relaxing this requires an additional coverage or distribution-shift coefficient.Source: §7.1 · p. 15
  • The paper establishes coverage as necessary for Best-of-N success, but does not identify the minimal conditions required for reinforcement learning.Source: §7.1 · p. 15
  • For reasoning tasks, the sequence-level analysis can be weakened to answer-level coverage when only the final answer matters, although answer-level coverage may be strictly smaller than sequence-level coverage.Source: §7.1 · p. 15

7.2 Future Work

  • Future work includes coverage-guided optimizer and checkpoint design, restructuring language-model training around coverage, and semantic coverage that accounts for learned representations.Source: §7.2 · p. 15

A Related Work

  • The related-work discussion positions the paper as theoretical support for coverage assumptions in post-training, while distinguishing its model-based coverage profile from offline-dataset coverage and Pass@N terminology.Source: A Related Work · p. 23

B Comparison to Classical Generalization Bounds for MLE

This block contrasts coverage-based generalization with classical KL and Hellinger analyses, then describes graph-reasoning experiments used to evaluate the paper’s predictions.

B Comparison to Classical Generalization Bounds for MLE

  • KL-based bounds can become uninformative for large N because CovN(bπ) = 0 for N ≥ Wmax, preventing meaningful improvement as Best-of-N scales.Source: B Comparison to Classical… · p. 24
  • Hellinger-based conversion yields non-trivial coverage bounds for constant N but provides no further improvement as N increases.Source: B Comparison to Classical… · p. 24
  • Classical bounds may avoid explicit sequence-length dependence only after a burn-in cost that can itself scale with problem-dependent quantities such as log Wmax.Source: B Comparison to Classical… · p. 24

C.1 Graph Reasoning Task

  • The experiments use layered-DAG graph-search tasks, converting graph prompts and sampled paths into autoregressive sequence-modeling problems.Source: §C.1 · p. 25, §C.1.1 · pp. 25–26

C.1.1 Graph Search Task Description

  • Graph tasks separate locally valid paths from globally selected expert paths, making imitation of the data-collection policy harder than learning path validity alone.Source: §C.1.1 · p. 26

C.1.2 Model Details

  • The transformer experiments train GPT2-like causal models with cross-entropy and Adam, using hyperparameter grids summarized in Table 1.Source: §C.1.2 · p. 26, Table 1 · p. 27

C.2 Experiment Details for Figure 1

The experiments construct heterogeneous graph-reasoning tasks to test whether coverage better tracks downstream performance than cross-entropy across training checkpoints and sequence horizons.

C.2 Experiment Details for Figure 1

  • Cross-entropy reduction can worsen coverage when finite representation and sample constraints force a model to favor a better-represented graph class.Source: §C.2 · p. 27
  • The best-coverage checkpoint occurs midway through training, when both graph classes are covered, before later cross-entropy improvements sacrifice coverage on the less-represented class.Source: §C.2 · p. 27
  • Despite imperfect supervised learning, the model can sample a correct path with N = O(1) Best-of-N attempts and achieve optimal test-time-scaling performance.Source: §C.2 · p. 27

C.2.1 Task Description

  • The Figure 1 setup uses two fine-tuning graph classes with different global path-selection rules, while pre-training adds a third class whose policy samples uniformly among valid paths.Source: §C.2.1 · p. 27, §C.2.2 · p. 28

C.3 Experiment Details for Figure 2

  • Figure 2 varies the number of intermediate layers to expose cross-entropy’s horizon sensitivity, while difficult examples inflate KL-divergence without affecting coverage.Source: §C.3 · p. 28, §C.3.1 · p. 29

C.3.2 Task-Specific Implementation Details

  • The experiments evaluate checkpoints on per-class validation sets, average metrics using class probabilities, and report medians across 16 seeds with quantile-based shading.Source: §C.3.2 · p. 29

D.1 Properties of the Coverage Profile

  • The supporting results establish conversion and chain-rule properties for coverage, including KL- and Hellinger-based relationships and tightness examples.Source: §D.1 · pp. 30–31

D.2 Analysis of Best-of-N Sampling under a Good Coverage Profile

The appendix establishes when Best-of-N succeeds or fails under coverage, then relates maximum-likelihood convergence and autoregressive coverage to bounded divergence measures.

D.2 Analysis of Best-of-N Sampling under a Good Coverage Profile

  • Best-of-N is guaranteed to succeed when the base model has sufficiently low coverage error at scale M and N is large enough.Proposition D.6 assumes N ≥ 2M log(ε^-1) and Cov_M(πT ∥ bπ) ≤ 1/2.Source: §D.2 · p. 32
  • Coverage is necessary for Best-of-N because an adversarial binary reward can select responses outside the base model’s covered set.The construction uses rT(x, y) = I{y ∈ Sx}.Source: §D.2 · p. 32

D.3 Properties of Maximum Likelihood

  • Maximum likelihood admits high-probability convergence bounds for coverage through standard Hellinger- and KL-based guarantees under realizability and boundedness assumptions.The KL analysis assumes πD ∈ Π and uniformly bounded likelihood ratios, while the Hellinger result applies for all M ≥ 2.Source: §D.3 · pp. 32–33
  • The KL bound can retain a log(Wmax) factor, and the appendix notes that this dependence can be tight for the considered model classes.The accompanying example relates the result to covering-number behavior.Source: §D.3 · p. 33

D.4 Autoregressive Models: Coverage and Stopped KL-Divergence

  • For autoregressive models, coverage is related to stopped KL-divergence, which remains bounded even when ordinary KL-divergence may diverge.A converse lower-bounds coverage using the tail behavior of sums of step-wise Hellinger distances.Source: §D.4 · pp. 33–34

E.1 Maximum Likelihood: Better Coverage for Convex Classes

The appendix shows that maximum likelihood can obtain faster coverage convergence for convex model classes, while misspecification can fundamentally obstruct coverage; standard concentration and information-theoretic lemmas support these results.

E.1 Maximum Likelihood: Better Coverage for Convex Classes

  • For convex model classes, maximum likelihood achieves a faster coverage convergence rate and tolerates misspecification through comparison with the best KL approximator.In the well-specified case, the bound simplifies relative to the general coverage result.Source: §E.1 · p. 35

E.2 Lower Bound for Maximum Likelihood under Misspecification

  • Under misspecification, maximum likelihood can have coverage scaling with the inverse log model-size factor even when another model in the class has zero coverage error.The lower-bound construction uses a two-model class and permits arbitrarily small per-example log-likelihood discrepancy up to α.Source: §E.2 · p. 35

F.1 Concentration Inequalities

  • The technical development uses Freedman-type concentration, covering-number uniform convergence, and related concentration tools for bounded adapted random variables.These results provide the probabilistic control used by the appendix’s maximum-likelihood analyses.Source: §F.1 · p. 37

F.2 Information-Theoretic Inequalities

  • The information-theoretic toolkit bounds expectation differences and vector-valued deviations using KL divergence and exponential-family inequalities.The lemmas cover bounded scalar functions, vector-valued functions, and log-linear distributions.Source: §F.2 · p. 38

G Proofs from Section 3

These proofs construct hard autoregressive instances showing that data can be uninformative about rare contexts, allowing maximum likelihood to select models with poor coverage despite favorable divergence behavior.

G Proofs from Section 3

  • The lower-bound construction hides parameter-dependent behavior in a rare context, so samples often contain only an uninformative context.The event that all observed inputs equal zero has high probability under the construction.Source: G Proofs from Section 3 · p. 39
  • On the common context, the induced output distribution does not depend on the parameter, preventing the data from reliably distinguishing candidate models.The proof expresses the KL divergence through the rare context and shows the relevant objective is minimized at the neutral parameter.Source: G Proofs from Section 3 · p. 39
  • The construction can make KL convergence slow even when the inherent variance is small, demonstrating a separation between KL behavior and the coverage-relevant quantity.The appendix states this holds when B is sufficiently large relative to log H.Source: G Proofs from Section 3 · p. 39

H.1 Proof of Theorem 4.1 (Coverage for MLE)

The proofs derive the main coverage guarantee for approximate maximum likelihood, extend it to convex classes, establish supporting lower bounds, and connect autoregressive coverage to sequence-level divergence.

H.1 Proof of Theorem 4.1 (Coverage for MLE)

  • Theorem 4.1 follows by bounding clipped log loss uniformly over the model class and relating the resulting quantity to coverage.The proof uses covering numbers, concentration, and the fact that the clipped-loss lower bound controls Cov_N(π) when log N exceeds the clipping threshold.Source: §H.1 · pp. 39–40

H.2 Proof of Theorem E.1 (Coverage for MLE with Convex Classes)

  • For convex classes, concavity makes the population and empirical maximum-likelihood problems amenable to comparison with the best-in-class model.The proof derives a coverage bound by combining this comparison with uniform concentration.Source: §H.2 · p. 42

H.3 Proofs for Supporting Results

  • Supporting constructions prove lower bounds by creating unseen or weakly observed outcomes that force maximum likelihood toward models retaining nontrivial coverage error.The proof explicitly obtains Cov_N(bπ) ≥ p in the constructed instance.Source: §H.3 · pp. 43–44

I.1 Organization

  • The autoregressive analysis uses the sequence divergence Dseq,N and Proposition D.10 to upper-bound coverage by a logarithmic factor times this stopped sequence-level quantity.The appendix states Cov_N(πθ) ≤ 2 log N−1 Dseq,N(πD ∥ πθ).Source: §I.1 · p. 45

I.2 Proof of Theorem 4.2 (Coverage for MLE for Autoregressive Linear Models)

This section proves coverage guarantees for maximum-likelihood estimation in autoregressive linear models and extends the analysis to vanilla SGD. The proof uses fractional coverings and concentration arguments to control conditional divergences and coverage.

I.2 Proof of Theorem 4.2 (Coverage for MLE for Autoregressive Linear Models)

  • Theorem I.1 states that, under Assumption 2.2, the MLE bπ achieves a bound containing n + B2 log N.This holds for any parameter N ≥2, with divergence Dseq,N(· ∥·) defined in Proposition D.10.Source: §I.2 · p. 46
  • The MLE analysis first bounds the expected sum of per-step conditional KL divergences, without implying a sequence-level KL bound because the fitted parameter depends on the data.The expected quantity is bounded by 2σ⋆√n.Source: §I.2 · p. 46
  • A Gaussian fractional cover concentrates the truncated error around its expectation and avoids the dimension-dependent symmetrization required by classical covering arguments.The cover is sampled independently of the dataset, while its error depends only on the ground-truth variance σ⋆²∆².Source: §I.2 · pp. 46–47

I.2.1 Proofs for Supporting Lemmas

  • The supporting lemmas construct weighted conditional-divergence controls and analyze Gaussian parameter perturbations through log-likelihood ratios and feature differences.The proof uses a weight function α and applies a fractional-covering lemma to distributions induced by target and observed prefixes.Source: §I.2.1 · pp. 49–50

I.3 Proof of Proposition 5.1 (Vanilla SGD: Coverage Upper Bound)

  • For vanilla projected SGD, the analysis combines a standard projection inequality with concavity and smoothness of the log-likelihood to obtain a coverage upper bound.The result holds when η ≤ 1/(2HB²).Source: §I.3 · pp. 52–53

I.4 Proof of Proposition 5.1 (Vanilla SGD: Coverage Lower Bound)

The appendix develops proofs for coverage bounds and related algorithmic results, spanning vanilla and normalized SGD, test-time training, gradient-normalized distillation, and simple-tournament guarantees. It also establishes a high-dimensional lower bound illustrating unavoidable variance dependence under specified conditions.

I.4 Proof of Proposition 5.1 (Vanilla SGD: Coverage Lower Bound)

  • Vanilla SGD has an instance with variance σ⋆≤1 where, with probability at least 0.5, Cov_N(π_θt) ≥ 1−1/(2T) for all t ∈[T].The proof is completed by combining Lemma I.6 and Lemma I.7.Source: §I.4 · p. 54
  • The vanilla-SGD construction establishes the first regime by showing iterates alternate near v_−1 and v_1, where Claim 5 gives Cov_N(π_θ) ≥ 1−1/(2T).This holds when B is sufficiently large and log N ≤ HB/8, using the transition and concentration claims in the constructed instance.Source: §I.4 · p. 55

I.5 Proof of Theorem 5.1 (Coverage for Normalized SGD)

  • For normalized SGD, coverage is bounded through stopped KL divergences and controlled under λ ≥ 8BM, with the proof reducing the result to bounds on normalized-gradient terms.The update is written as a projected step using the normalized gradient, and the final parameter choices require η ≤ 1/(128B) and λ = M/(16η).Source: §I.5 · pp. 57–58

I.6 Proof of Theorem 6.1 (Test-Time Training)

  • The test-time training proof specializes a lemma to token-level SGD, combines concavity and smoothness inequalities, and requires η ≤ 1/(2B2).The argument takes expectations over the learning process and uses the chain rule for KL divergence.Source: §I.6 · pp. 61–63

I.7 Proof of Theorem 6.2 (Gradient Normalization for Distillation)

  • The gradient-normalization proof controls the estimator’s gradient error using stopped-KL bounds, a gradient-error lemma, and a stepsize condition η ≤ 1/[2(32A+1)B2].Here A = log N, and the proof combines inequalities controlling the normalized estimator and its expected squared norm.Source: §I.7 · pp. 63–64

I.8 Necessity of Variance Dependence in High Dimension

  • Under log N ≤ c min{H, B2}, a worst-case autoregressive linear model shows variance dependence is generally necessary for bounds that avoid explicit H-scaling.The construction uses d = H, a bounded feature map, and a parameter set Θ = B2(1).Source: §I.8 · p. 65

J Proofs from Section 6

  • The proof of the Section 6 results concludes with the desired lower bound.The supplied passage provides the proof conclusion but not the lower-bound expression itself.Source: J Proofs from Section 6 · p. 66

J.1 Proof of Theorem 6.3 (Simple Tournament)

  • The simple-tournament proof derives its claimed bound by combining success-event inequalities and setting α = c log N and N′ = N^a.The argument conditions on the success events from the preceding bounds before applying these parameter choices.Source: §J.1 · p. 66

J.2 Proof of Theorem 6.4 (Offset Tournament)

This section proves generalization guarantees for the offset tournament estimator using an offset divergence and empirical concentration. The resulting bounds relate tournament coverage to approximation and statistical errors.

J.2 Proof of Theorem 6.4 (Offset Tournament)

  • Theorem 6.4′ gives a general guarantee for the offset tournament estimator when N ≥8γ².The theorem is stated for arbitrary N and γ satisfying this condition.Source: §J.2 · p. 67
  • The offset divergence is zero whenever the log-probability difference between πD and π is at most log γ pointwise.Theorem 6.4 follows by setting γ = N^a.Source: §J.2 · p. 67
  • Lemma J.1 uniformly relates empirical offset-tournament probabilities to population probabilities, with deviations controlled by εstat.The simultaneous bounds apply under both the population and empirical context distributions.Source: §J.2 · p. 68
  • The proof bounds the empirical tournament event by approximation and statistical errors, yielding bPn(CN(π, bπ)) ≤ 5εstat + 2ε′apx.This uses N ≥8γ² together with the empirical concentration bound.Source: §J.2 · p. 68
  • Transferring the empirical event bound to the population gives N(π ∥ bπ) ≤ 12εstat + 4ε′apx.The argument applies the population concentration inequality after bounding the empirical tournament probability.Source: §J.2 · p. 68
  • The approximation term is itself controlled by the offset divergence through 2γ(πD ∥ π) = Cov2γ(π) ≤ εapx.This connects the tournament guarantee to the best available approximation error in the class.Source: §J.2 · p. 68

Related papers

Loading 2510.15020v2…