Research map / Optimization / Implicit bias and generalization
Implicit Optimization Bias of Next-token Prediction in Linear Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical analysis of implicit optimization bias of next-token prediction (cross-entropy over distinct contexts with sparse next-token distributions) for linear decoders with fixed context embeddings, showing GD splits into a finite data-subspace component and a max-margin (NTP-SVM) direction in the orthogonal subspace.
Problem
Which solutions gradient-based optimizers select among the many minimizers of the next-token prediction (NTP) cross-entropy objective, when the conditional next-token distributions are sparse and contexts are repeated across the training set.
Approach
Frames NTP as cross-entropy over distinct contexts with sparse empirical next-token distributions, introduces NTP-separability and NTP-compatibility conditions that allow reaching the entropy lower bound, and shows GD in linear models decomposes into a finite data-subspace solution plus a divergent component aligned with an NTP-specific max-margin direction.
Key results
- GD iterates' norm diverges while CE converges to the empirical conditional entropy (H≈1.445 nats in the synthetic setup), with direction aligning to the NTP-SVM solution (cosine →1).
- The data-subspace component of GD iterates converges to a unique finite solution W* satisfying NTP-compatibility equations.
- Overparameterization d>m with full-rank embeddings is shown to be a sufficient condition for NTP-separability and compatibility.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use normalized gradient descent (NGD) instead of GD | Linear NTP model on synthetic overparameterized data · Synthetic NTP data (n=5000, m=50, d=60, V=10) | convergence speed | Helped |
| Use Adam instead of GD | Linear NTP model on synthetic overparameterized data · Synthetic NTP data (n=5000, m=50, d=60, V=10) | convergence speed | Helped |
| Use Adam instead of NGD | Linear NTP model on synthetic overparameterized data · Synthetic NTP data (n=5000, m=50, d=60, V=10) | convergence speed | Helped |
Limitations
- Analysis restricted to linear decoders with fixed context embeddings and convex CE objective.
- Sufficient overparameterization condition (d>m) is not tight; exact NTP-separability thresholds unknown.
- Experiments are small synthetic settings only; no real language model experiments.
Experimental setup
Metrics: cross-entropy loss vs entropy lower bound parameter norm growth cosine alignment with NTP-SVM direction convergence of data-subspace component
Baselines: gradient descent normalized gradient descent Adam
Builds on: implicit bias of gradient descent on separable data one-hot classification implicit bias (non-separable binary data) Kesler's construction
Closest papers by meaning
- On the Generalization Ability of Next-Token-Prediction Pretraining (ICML 2025 · similarity 0.90)
- Reinforced Fast Weights via Next-Sequence Prediction (NeurIPS 2026 · similarity 0.88)
- Towards Auto-Regressive Next-Token Prediction: In-context Learning Emerges from Generalization (ICLR 2025 · similarity 0.88)
- Learning In-context $n$-grams with Transformers: Sub-$n$-grams Are Near-Stationary Points (ICML 2025 · similarity 0.87)
- Correlation and Navigation in the Vocabulary Key Representation Space of Language Models (ICLR 2025 · similarity 0.87)
- Tokens-per-Parameter Coverage Is Critical for Robust LLM Scaling Law Extrapolation (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.