mlsanityData to 14 Oct 2026

Non-vacuous Generalization Bounds for Reinforcement Learning with Verifiable Rewards

arXiv 2607.14506 ↗First posted 16 Jul 2026cs.LG cs.AIcited by 1

On the map: LLM reasoning → Reinforcement learning for reasoning

Abstract (arXiv)

While reinforcement learning with verifiable rewards (RLVR) is widely used to improve the reasoning capabilities of large language models (LLMs), the generalizability of the resulting models remains poorly understood. In this work, we establish the first non-vacuous generalization bounds for parameter-efficient RLVR fine-tuning at the billion-parameter scale. Our approach adapts PAC-Bayes compression bounds to this setting, and addresses the inherent stochasticity of token generation by applying the Gumbel-max reparameterization trick. To operationalize these bounds, we propose the Progressive RLVR framework, which integrates RLVR with on-policy distillation, TinyLoRA, and model quantization. Progressive RLVR empirically retains 84-97% performance of standard LoRA fine-tuning while producing models that are 14,796x more compressible. We show that this framework yields non-vacuous generalization bounds in four domains: mathematical problem-solving, programming, general-knowledge reasoning, and Text-to-SQL. Our bounds exceed the accuracy of the base model by 9-51% and lie within 6-11% of the accuracy of the fine-tuned models.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning. Builds on 54 of its 74 references that are in the map. First posted on arXiv 16 Jul 2026.

Builds on

54 of 74 references.

Closest ancestors · 9

Same direction, newest first

  1. 2025Soft Adaptive Policy Optimization25 Nov
  2. 2025The Reasoning Boundary Paradox: How Reinforcement Learning Constrains Language Models2 Oct
  3. 2025General-Reasoner: Advancing LLM Reasoning Across All Domains20 May
  4. 2025Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?18 Apr
  5. 2025Understanding R1-Zero-Like Training: A Critical Perspective26 Mar
  6. 2025DAPO: An Open-Source LLM Reinforcement Learning System at Scale18 Mar
  7. 2025SWE-RL: Advancing LLM Reasoning via Reinforcement Learning on Open Software Evolution25 Feb
  8. 2025Process Reinforcement through Implicit Rewards3 Feb
  9. 2025SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training28 Jan

Other references · 45

  1. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  2. 2025Qwen3 Technical Reportcited by 8,820
  3. 2020Measuring Massive Multitask Language Understandingcited by 7,963
  4. 2018Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challengecited by 4,886
  5. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,720
  6. 2016Categorical Reparameterization with Gumbel-Softmaxcited by 2,739
  7. 2015Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Codingcited by 2,329
  8. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  9. 2020What Disease does this Patient Have? A Large-scale Open Domain Question Answering Dataset from Medical Examscited by 1,356
  10. 2023On-Policy Distillation of Language Models: Learning from Self-Generated Mistakescited by 939
  11. 2020Aligning AI With Shared Human Valuescited by 723
  12. 2023C-Eval: A Multi-Level Multi-Discipline Chinese Evaluation Suite for Foundation Modelscited by 708
33 more
  1. 2024Parameter-Efficient Fine-Tuning for Large Models: A Comprehensive Surveycited by 656
  2. 2015Policy Distillationcited by 440
  3. 2023LegalBench: A Collaboratively Built Benchmark for Measuring Legal Reasoning in Large Language Modelscited by 336
  4. 2018Stronger generalization bounds for deep nets via a compression approachcited by 307
  5. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  6. 2017Size-Independent Sample Complexity of Neural Networkscited by 290
  7. 2025MiniMax-M1: Scaling Test-Time Compute Efficiently with Lightning Attentioncited by 263
  8. 2021User-friendly introduction to PAC-Bayes boundscited by 239
  9. 2021CUAD: An Expert-Annotated NLP Dataset for Legal Contract Reviewcited by 236
  10. 2023Parameter-Efficient Fine-Tuning Methods for Pretrained Language Models: A Critical Review and Assessmentcited by 230
  11. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 224
  12. 2021When Does Pretraining Help? Assessing Self-Supervised Learning for Law and the CaseHOLD Datasetcited by 201
  13. 2023LoftQ: LoRA-Fine-Tuning-Aware Quantization for Large Language Modelscited by 196
  14. 2023QA-LoRA: Quantization-Aware Low-Rank Adaptation of Large Language Modelscited by 155
  15. 2021ContractNLI: A Dataset for Document-level Natural Language Inference for Contractscited by 148
  16. 2025KodCode: A Diverse, Challenging, and Verifiable Synthetic Dataset for Codingcited by 119
  17. 2025OmniSQL: Synthesizing High-quality Text-to-SQL Data at Scalecited by 91
  18. 2026OpenClaw-RL: Train Any Agent Simply by Talkingcited by 90
  19. 2022PAC-Bayes Compression Bounds So Tight That They Can Explain Generalizationcited by 76
  20. 2024LoRA-XS: Low-Rank Adaptation with Extremely Small Number of Parameterscited by 76
  21. 2018CLAUDETTE: an Automated Detector of Potentially Unfair Clauses in Online Terms of Servicecited by 73
  22. 2019Question Answering for Privacy Policies: Combining Computational and Legal Perspectivescited by 67
  23. 2023Non-Vacuous Generalization Bounds for Large Language Modelscited by 53
  24. 2024Parameter-Efficient Fine-Tuning in Large Models: A Survey of Methodologiescited by 47
  25. 2023MAUD: An Expert-Annotated Legal NLP Dataset for Merger Agreement Understandingcited by 33
  26. 2019On the Generalization Gap in Reparameterizable Reinforcement Learningcited by 22
  27. 2021Factoring Statutory Reasoning as Language Understanding Challengescited by 20
  28. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  29. 2025PLoP: Precise LoRA Placement for Efficient Finetuning of Large Modelscited by 14
  30. 2026Learning to Reason in 13 Parameterscited by 14
  31. 2017A Tight Excess Risk Bound via a Unified PAC-Bayesian-Rademacher-Shtarkov-MDL Complexitycited by 7
  32. 2025Uni-LoRA: One Vector is All You Needcited by 7
  33. 2025PiCa: Parameter-Efficient Fine-Tuning with Column Space Projectioncited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Certification Frontiers for Gaussian LoRA: Independent Priors, Posterior Risk, and Prediction-Preserving Balancingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Limits of Generalization in RLVR: Two Case Studies in Mathematical Reasoning
  2. 2025Generalization of RLVR Using Causal Reasoning as a Testbed
  3. 2025RLPR: Extrapolating RLVR to General Domains without Verifiers
  4. 2025Extending RLVR to Open-Ended Tasks via Verifiable Multiple-Choice Reformulation
  5. 2025Evaluating Parameter Efficient Methods for RLVR
  6. 2026Boosting LLM Exploration via Weak-Model Guidance in RLVR
  7. 2025Position: The Hidden Costs and Measurement Gaps of Reinforcement Learning with Verifiable Rewards
  8. 2026Resource-Efficient Reinforcement for Reasoning Large Language Models via Dynamic One-Shot Policy Refinement