Research map / Large language models / Language, safety and interpretability
Understanding Transformers via N-Gram Statistics
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.
Shows that transformer next-token predictions on TinyStories and Wikipedia can be approximated by N-gram rulesets built from training-data statistics, and uses this lens to study approximability, curriculum-like learning dynamics, and an overfitting detector without a holdout set.
Problem
Understanding how transformer LLMs use their context when predicting the next token, by describing their predictions as simple template functions (N-gram rules) derived from training data statistics.
Approach
Defines families of regex-style N-gram rules (suffix, subgram, all) formed by keeping, dropping, or marginalizing context tokens, and measures per-context how close transformer predictions are to the best such rule; low model variance across runs predicts good rule approximation.
Key results
- Optimal N-gram rule from the all-rules ruleset with max context 7 matches the 160M model's top-1 prediction 78% of the time on TinyStories (79% with L-infinity distance), versus 56.7% for stupid backoff.
- On Wikipedia with a 1.4B model, optimal rules reach 67.7% top-1 agreement versus 54.9% top-1 accuracy of the model against ground truth.
- Tracking limited-context models shows train and validation loss curves track closely, giving an early stopping signal that needs no holdout set.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase maximum rule context length from 1 to 7 using all rule types | Optimal rules approximating the 160M transformer · TinyStories validation stories | top-1 accuracy (%): 30.0 -> 78.0 | Helped |
| Use all rule types rather than suffix rules at M=7 | Optimal rules approximating the 160M transformer · TinyStories validation stories | top-1 accuracy (%): 65.6 -> 78.0 | Helped |
| Use all rule types rather than backoff at M=7 | Optimal rules approximating the 160M transformer · TinyStories validation stories | top-1 accuracy (%): 56.7 -> 78.0 | Helped |
| Increase maximum rule context length from 1 to 7 using all rule types | Optimal rules approximating the 1.4B transformer · Wikipedia holdout sequences | top-1 accuracy (%): 24.3 -> 67.7 | Helped |
| Scale the transformer from 160M to 1.4B | Transformer · TinyStories holdout | eval loss: 1.43 -> 1.22 | Helped |
| Scale the transformer from 160M to 1.4B | Transformer · Wikipedia holdout | eval loss: 2.63 -> 2.26 | Helped |
| Scale the transformer from 160M to 1.4B | Optimal all-rule approximation · TinyStories holdout | top-1 accuracy (%) at context length 7: 77.9 -> 78.2 | No clear effect |
Surprising findings
- Optimal rule top-1 agreement with the LLM (78%) exceeds the LLM's own top-1 accuracy against ground truth (69.6%).
Limitations
- Descriptive rather than explanatory: rules describe post-hoc but do not predict which rule applies.
- Evaluated only on simple datasets (TinyStories, Wikipedia) with models up to 1.4B; LLM-level behavior beyond N-gram rules not captured.
- Variational distance and L-infinity distance results differ and each has failure modes for high-entropy distributions.
Experimental setup
Datasets: TinyStories MassiveText Wikipedia
Benchmarks: TinyStories validation (100 stories) Wikipedia holdout (10 chunks)
Metrics: top-1 accuracy variational distance L-infinity distance cross-entropy loss
Baselines: stupid backoff
Builds on: stupid backoff Chinchilla infini-gram
Closest papers by meaning
- Trainable Transformer in Transformer (ICML 2024 · similarity 0.90)
- Bigram Subnetworks: Mapping to Next Tokens in Transformer Language Models (NeurIPS 2025 · similarity 0.89)
- Transformer Block Coupling and its Correlation with Generalization in LLMs (ICLR 2025 · similarity 0.89)
- How Do Nonlinear Transformers Learn and Generalize in In-Context Learning? (ICML 2024 · similarity 0.88)
- Do Efficient Transformers Really Save Computation? (ICML 2024 · similarity 0.88)
- Understanding Scaling Laws with Statistical and Approximation Theory for Transformer Neural Networks on Intrinsically Low-dimensional Data (NeurIPS 2024 · similarity 0.88)
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.