Research map / Large language models / Language, safety and interpretability
Non-Vacuous Generalization Bounds for Large Language 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.
Derives the first non-vacuous PAC-style compression generalization bounds for pretrained-from-scratch GPT-2 style LLMs on OpenWebText, using prediction smoothing for unbounded NLL, subsampled empirical risk, and a nonlinear SubLoRA parameterization.
Problem
Whether large language models generalize beyond their training data rather than memorizing it; existing PAC-Bayes and compression bounds are vacuous for LLMs because the NLL is unbounded, token predictions are not independent, and models have huge parameter counts.
Approach
Combine a finite-hypothesis compression bound (prior from code length) with prediction smoothing to bound the unbounded BPD, a subsampling bound to cheaply estimate empirical risk, and SubLoRA (LoRA applied to a random-subspace-projected parameter vector) to reach extreme compression while keeping expressivity.
Key results
- SubLoRA yields a document-level BPD bound of 12.12 for GPT-2 small (124M) versus 13.09 for LoRA only, 14.59 for subspace only, and 70.76 for the original model, with top-1 error bound 96.41%.
- Scaling SubLoRA to 849M parameters gives a non-vacuous BPD bound of 12.01 and top-100 error bound of 58.89%, with bounds not worsening as model size grows.
- Subsampling 10,000 documents cuts bound computation time to about 45 minutes on one GPU versus 3 days on 8 GPUs for OpenWebText.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| combine LoRA with subspace compression rather than using LoRA alone (ablation) | GPT-2 small · OpenWebText document-level | Top-1 Error Bound (%): 100 -> 96.41 | Helped |
| combine LoRA with subspace compression rather than using subspace training alone (ablation) | GPT-2 small · OpenWebText document-level | Top-1 Error Bound (%): 96.52 -> 96.41 | Helped |
| combine LoRA with subspace compression rather than using LoRA alone (ablation) | GPT-2 small · OpenWebText document-level | Bits per Dimension Bound: 13.09 -> 12.12 | Helped |
| combine LoRA with subspace compression rather than using subspace training alone (ablation) | GPT-2 small · OpenWebText document-level | Bits per Dimension Bound: 14.59 -> 12.12 | Helped |
| increase GPT-2 model size from 124M to 354M | SubLoRA · OpenWebText document-level | Bits per Dimension Bound: 12.12 -> 11.96 | Helped |
| increase GPT-2 model size from 124M to 458M | SubLoRA · OpenWebText document-level | Bits per Dimension Bound: 12.12 -> 11.95 | Helped |
| increase GPT-2 model size from 124M to 773M | SubLoRA · OpenWebText document-level | Bits per Dimension Bound: 12.12 -> 12.10 | Helped |
| increase GPT-2 model size from 124M to 849M | SubLoRA · OpenWebText document-level | Bits per Dimension Bound: 12.12 -> 12.01 | Helped |
| shuffle token order within each training sequence | GPT-2 language model · OpenWebText | Top-1 Error Bound | Hurt |
| apply LoRA to other linear layers in addition to attention and the last linear layer (ablation) | SubLoRA pretraining · OpenWebText | pretraining performance | No clear effect |
| fine-tune pretrained rather than randomly initialized GPT-2 with SubLoRA | GPT-2 · QQP | Error Bound (%): 71.72 -> 35.27 | Helped |
| fine-tune pretrained rather than randomly initialized GPT-2 with SubLoRA | GPT-2 · CoLA | Error Bound (%): 53.42 -> 38.89 | Helped |
Surprising findings
- The original uncompressed GPT-2 achieves the best validation BPD (4.35) yet gives vacuous bounds (70.76 BPD bound) due to its parameter count.
- Larger GPT-2 variants obtain better (tighter) BPD bounds than the 124M model, contrary to naive expectations that larger models generalize worse.
Limitations
- Larger models (354M to 849M) were trained with only a limited hyperparameter sweep, so their bounds are likely loose relative to achievable values.
- SubLoRA-pretrained models produce largely ungrammatical text, so the compressed models are poor generators.
- Bounds require training models from scratch through the SubLoRA parameterization; they do not directly certify already-trained models; document-level i.i.d. assumption ignores token-level dependence.
Experimental setup
Datasets: OpenWebText GLUE QQP GLUE CoLA
Benchmarks: OpenWebText GLUE QQP GLUE CoLA
Metrics: BPD generalization bound Top-1/Top-10/Top-100 error bound validation BPD validation NLL classification error bound
Baselines: LoRA only subspace training only original (uncompressed) model
Builds on: PAC-Bayes compression bounds (Lotfi et al. 2022) intrinsic dimension subspace training LoRA Solomonoff prior / Kolmogorov complexity bounds nanoGPT
Closest papers by meaning
- Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models (NeurIPS 2024 · similarity 0.95)
- Compute-Optimal LLMs Provably Generalize Better with Scale (ICLR 2025 · similarity 0.91)
- A Probabilistic Perspective on Unlearning and Alignment for Large Language Models (ICLR 2025 · similarity 0.89)
- Constrained Entropic Unlearning: A Primal-Dual Framework for Large Language Models (NeurIPS 2025 · similarity 0.88)
- Compressing LLMs: The Truth is Rarely Pure and Never Simple (ICLR 2024 · similarity 0.88)
- Data-Constrained Language Model Pretraining: Improved Regularization and Scaling Laws (NeurIPS 2026 · 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.