# Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models

arXiv: https://arxiv.org/abs/2407.18158 · HTML: https://mlsanity.com/paper/2407.18158/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 48 references that are in the map.
- First posted on arXiv 25 Jul 2024.

## Builds on (most cited first, 26 of 26)

- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [QLoRA: Efficient Finetuning of Quantized LLMs](https://mlsanity.com/paper/2305.14314/) (2023)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [QuIP: 2-Bit Quantization of Large Language Models With Guarantees](https://mlsanity.com/paper/2307.13304/) (2023)
- [QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks](https://mlsanity.com/paper/2402.04396/) (2024)
- [LLM-QAT: Data-Free Quantization Aware Training for Large Language Models](https://mlsanity.com/paper/2305.17888/) (2023)
- [Transformers as Algorithms: Generalization and Stability in In-context Learning](https://mlsanity.com/paper/2301.07067/) (2023)
- [KronA: Parameter Efficient Tuning with Kronecker Adapter](https://mlsanity.com/paper/2212.10650/) (2022)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [LUT-GEMM: Quantized Matrix Multiplication based on LUTs for Efficient Inference in Large-Scale Generative Language Models](https://mlsanity.com/paper/2206.09557/) (2022)
- [Memory-Efficient Fine-Tuning of Compressed Large Language Models via sub-4-bit Integer Quantization](https://mlsanity.com/paper/2305.14152/) (2023)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [On the role of data in PAC-Bayes bounds](https://mlsanity.com/paper/2006.10929/) (2020)
- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [Non-Vacuous Generalization Bounds for Large Language Models](https://mlsanity.com/paper/2312.17173/) (2023)
- [On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities](https://mlsanity.com/paper/1510.03925/) (2015)
- [A unified recipe for deriving (time-uniform) PAC-Bayes bounds](https://mlsanity.com/paper/2302.03421/) (2023)
- [Understanding prompt engineering may not require rethinking generalization](https://mlsanity.com/paper/2310.03957/) (2023)
- [The Cost of Down-Scaling Language Models: Fact Recall Deteriorates before In-Context Learning](https://mlsanity.com/paper/2310.04680/) (2023)
- [Generalization bounds for learning under graph-dependence: A survey](https://mlsanity.com/paper/2203.13534/) (2022)
- [Probabilistic fine-tuning of pruning masks and PAC-Bayes self-bounded learning](https://mlsanity.com/paper/2110.11804/) (2021)

## Built on by (most cited first, 25 of 25)

- [Deep Learning is Not So Mysterious or Different](https://mlsanity.com/paper/2503.02113/) (2025)
- [Large Language Models as Markov Chains](https://mlsanity.com/paper/2410.02724/) (2024)
- [Not All LLM Reasoners Are Created Equal](https://mlsanity.com/paper/2410.01748/) (2024)
- [A Little Help Goes a Long Way: Efficient LLM Training by Leveraging Small LMs](https://mlsanity.com/paper/2410.18779/) (2024)
- [Quantized Reasoning Models Think They Need to Think Longer, but They Do Not](https://mlsanity.com/paper/2606.00206/) (2026)
- [From Low Intrinsic Dimensionality to Non-Vacuous Generalization Bounds in Deep Multi-Task Learning](https://mlsanity.com/paper/2501.19067/) (2025)
- [Generalization Error Analysis for Selective State-Space Models Through the Lens of Attention](https://mlsanity.com/paper/2502.01473/) (2025)
- [Compute-Optimal LLMs Provably Generalize Better With Scale](https://mlsanity.com/paper/2504.15208/) (2025)
- [Investigating Social Bias Changes in Quantized Language Models](https://mlsanity.com/paper/2602.06181/) (2026)
- [Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses](https://mlsanity.com/paper/2409.17932/) (2024)
- [Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks](https://mlsanity.com/paper/2410.13577/) (2024)
- [Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained models](https://mlsanity.com/paper/2503.07325/) (2025)
- [Fast Rate Bounds for Multi-Task and Meta-Learning with Different Sample Sizes](https://mlsanity.com/paper/2505.15496/) (2025)
- [Bound to Disagree: Generalization Bounds via Certifiable Surrogates](https://mlsanity.com/paper/2602.23128/) (2026)
- [Towards Mitigation of Hallucination for LLM-empowered Agents: Progressive Generalization Bound Exploration and Watchdog Monitor](https://mlsanity.com/paper/2507.15903/) (2025)
- [WinFLoRA: Incentivizing Client-Adaptive Aggregation in Federated LoRA under Privacy Heterogeneity](https://mlsanity.com/paper/2602.01126/) (2026)
- [Position: A Three-Layer Probabilistic Assume-Guarantee Architecture Is Structurally Required for Safe LLM Agent Deployment](https://mlsanity.com/paper/2605.18672/) (2026)
- [Requential Coding: Pushing the Limits of Model Compression with Self-Generated Training Data](https://mlsanity.com/paper/2607.11883/) (2026)
- [Customizing the Inductive Biases of Softmax Attention using Structured Matrices](https://mlsanity.com/paper/2509.07963/) (2025)
- [Sparse Semantic Dimension as a Generalization Certificate for LLMs](https://mlsanity.com/paper/2602.11388/) (2026)
- [Can Generative Artificial Intelligence Survive Data Contamination? Theoretical Guarantees under Contaminated Recursive Training](https://mlsanity.com/paper/2602.16065/) (2026)
- [When Can We Trust the Sparse Lens? A Certification Framework for SAE Faithfulness](https://mlsanity.com/paper/2606.18383/) (2026)
- [Certification Frontiers for Gaussian LoRA: Independent Priors, Posterior Risk, and Prediction-Preserving Balancing](https://mlsanity.com/paper/2609.32271/) (2026)
- [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026)
- [Information-Theoretic Analysis of Next-Token Prediction under Markovian Data](https://mlsanity.com/paper/2609.34731/) (2026)

## Abstract (arXiv)

Large language models (LLMs) with billions of parameters excel at predicting the next token in a sequence. Recent work computes non-vacuous compression-based generalization bounds for LLMs, but these bounds are vacuous for large models at the billion-parameter scale. Moreover, these bounds are obtained through restrictive compression techniques, bounding compressed models that generate low-quality text. Additionally, the tightness of these existing bounds depends on the number of IID documents in a training set rather than the much larger number of non-IID constituent tokens, leaving untapped potential for tighter bounds. In this work, we instead use properties of martingales to derive generalization bounds that benefit from the vast number of tokens in LLM training sets. Since a dataset contains far more tokens than documents, our generalization bounds not only tolerate but actually benefit from far less restrictive compression schemes. With Monarch matrices, Kronecker factorizations, and post-training quantization, we achieve non-vacuous generalization bounds for LLMs as large as LLaMA2-70B. Unlike previous approaches, our work achieves the first non-vacuous bounds for models that are deployed in practice and generate high-quality text.