acceptodds
Under review as a conference paper at ICLR 2027

Non-vacuous Generalization Bounds for Reinforcement Learning with Verifiable Rewards

Abstract

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 obtain non-vacuous bounds, we develop Progressive RLVR, a pipeline combining RLVR with on-policy distillation, TinyLoRA, and quantization, which achieves high empirical accuracy and high compressibility. Progressive RLVR retains 84–97% performance of standard LoRA fine-tuning while producing learned weight updates that are 14,796× more compressible. We show that this framework yields non-vacuous generalization bounds in four domains: math, 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.

Primary area:
reinforcement learning
Keywords:
generalization bound, reinforcement learning with verifiable rewards

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_bKpoOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The manuscript shows a generalization bound for machine learning model fine-tuning. In this manuscript's setting, a base model and a problem distribution are fixed in advance. The model is then fine-tuned using samples from the distribution. Such fine-tuning can be of any form, including SFT, OPD, or RLVR. After fine-tuning, an estimate of the model's average reward in the problem distribution can be obtained by evaluating on the training set. The main result of the paper bounds the difference between the actual average reward in the problem distribution and this estimate, using the maximum difference in reward, the size of the training set, and importantly, the amount of information required to reconstruct the fine-tuned model from the base model. This generalization bound evaluates to a non-vacuous one in the authors' experiment setting. The authors fine-tune Qwen3.5-4B in verifiable tasks including math, coding, text-to-sql, and knowledge QA. They use TinyLoRA and quantization to ensure the parameter difference from the base model is small in information, and a large training set. As a result, the computed bounds for generalization are not vacuous and can meaningfully distinguish between the base model and the fine-tuned models. According to the authors, this is the first generalization bound that was able to do so when the model has billions of parameters. Moreover, under the authors' peft and quantization fine-tuning scheme, to be able to match the performance of normal LoRA fine-tuning, the authors proposed progressive RLVR, which is a training recipe that retains most of the performance of normal LoRA fine-tuning for Qwen3.5-4B in the settings that the authors consider.

Critical strengths
  • As the authors claimed, this is the first generalization bound that evaluates to empirically meaningful values in settings that are relavant to modern billion-parameter language model post-training. I found it very impressive that this is possible.
  • The experiments convincingly shows that the bounds really evaluate to meaningful numbers that carries information, across multiple domains.
Critical weaknesses
  • This result, although already meaningful in some empirical settings, is not likely to guide how people really evaluate generalization when doing post-training in practice. For the bounds to evaluate to meaningful numbers, one has to keep the number of tunable parameters very small with low precision, which sacrifices performance notably.
Questions for authors
  • Q1: Feel free to respond to the weakness raised.
  • Q2: In the theorem, it feels the term (1+1n)\left(1 + \frac{1}{\sqrt{n}}\right) can be bounded with a constant 22, which seems to convey the message better and simplify the setting. Is there a reason why you choose not to do so?
2 comments

We thank the reviewer for their comments. We addressed them below and revised the paper with changes highlighted in blue.

W/Q1: This result, although already meaningful in some empirical settings, is not likely to guide how people really evaluate generalization when doing post-training in practice. For the bounds to evaluate to meaningful numbers, one has to keep the number of tunable parameters very small with low precision, which sacrifices performance notably.

Held-out sets or benchmarks are widely used in practice to evaluate generalization and do not sacrifice performance. However, PAC-Bayes generalization bounds provide additional properties and enable additional applications, compared to held-out testing.

  • Scope of the guarantee. A held-out bound only covers the hypothesis fixed before the held-out set is examined, while a PAC-Bayes bound holds simultaneously for all hypotheses.

  • No reserved data. A PAC-Bayes bound uses only the training data and requires nothing held out. Therefore, PAC-Bayes bounds are particularly valuable when data are scarce or expensive. For example, constructing SWE-Bench Pro V2 required 404 hours from 23 professional engineers [3], while solving each task in FrontierMath took expert mathematicians multiple hours to multiple days [4].

  • Bound optimization. A held-out bound becomes invalid when we adaptively use it to improve training without addressing the multiple comparisons problem [1, 2]. In contrast, we can improve training to minimize a PAC-Bayes bound computed on training data, while the bound stays valid.

  • Explanation of generalization: A PAC-Bayes generalization bound explains why a model generalizes and enables the developer to compare training algorithms qualitatively. In contrast, a held-out set is a black-box test that does not explain generalization.

In the revised paper, we discussed benefits of PAC-Bayes generalization bound in Section 6.

Q2: In the theorem, it feels the term (1+1/n)(1 + 1 / \sqrt{n}) can be bounded with a constant 2, which seems to convey the message better and simplify the setting. Is there a reason why you choose not to do so?

We keep the factor (1+1/n)(1+1/\sqrt{n}) because it is close to 1 for the nn used in our experiments (1.1251.125 for n=64n=64). Compared to a constant of 2, this reduces the PAC-Bayes penalty by 44%. In the revision, we added a paragraph in Section 3.1 to note the simplified form for readers who prefer it.


[1] Blum, Avrim and Hardt, Moritz. “The ladder: A reliable leaderboard for machine learning competitions” ICML (2015).

[2] Cawley, Gavin and Talbot, Nicola. “On over-fitting in model selection and subsequent selection bias in performance evaluation” JMLR (2010).

[3] Dan, Soham, et al. "SWE-Bench Pro V2: A Cleaner, Harder-to-Game Coding Benchmark." arXiv:2610.24206 (2026).

[4] Glazer, Elliot, et al. "FrontierMath: A benchmark for evaluating advanced mathematical reasoning in ai." arXiv:2411.04872 (2024).

I thank the authors for the detailed response. I agree that PAC-Bayes generalization bounds that the authors develop has these values. I think my point that "it s not likely to guide how people really evaluate generalization when doing post-training in practice" also still holds. Overall, I think my recommendation of this paper remains weak acceptance.

Reviewer_fvbwOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper develops compression-based certificates for expected verifier rewards. It uses Gumbel-max reparameterization to separate prompt and generation randomness. Progressive RLVR trains a LoRA teacher, distills it on-policy into a TinyLoRA student, and quantizes the update. Experiments with Qwen3.5-4B report informative accuracy bounds on mathematics, programming, general knowledge, and multi-turn SQL.

Critical strengths
  1. The paper reports non-vacuous accuracy bounds for compressed students across four domains. This provides empirical evidence that compression-based certificates can be informative in these RLVR settings.

  2. The ablations examine how distillation, adapter choice, and quantization affect the resulting bounds. These comparisons help identify which parts of the pipeline contribute to the reported results.

Critical weaknesses
  1. I do not see why stochastic decoding prevents a direct application of standard compression bounds, as suggested in the introduction (p. 1, lines 44–51). Under Theorem 1's assumptions, applying Hoeffding to the bounded per-prompt rollout averages and taking a prior-weighted union bound gives, simultaneously for all hh with probability at least 1−δ1-\delta, $ R(h)\geq\widehat R_{m,n}(h)-\Delta\sqrt{\frac{\log(1/P(h))+\log(1/\delta)}{2m}}. $

    Using Appendix B.2's description-length substitution removes Theorem 1's 1+1/n1+1/\sqrt n factor and confidence split. This comparison concerns the full-data estimator. The numerical demonstration remains useful, but the theoretical contribution beyond this argument is unclear.

  2. The deployment motivation in §6 would benefit from a comparison with ordinary held-out certification. For a model fixed independently of 4,096 i.i.d. held-out prompts, the one-sided 95% Hoeffding penalty on per-prompt mean binary rewards is log⁡(20)/(2⋅4096)≈0.0191\sqrt{\log(20)/(2\cdot4096)}\approx0.0191, or 1.91 percentage points. Reserving such a set would allow direct teacher certification without distillation or quantization. Reusing training data is an advantage of compression bounds, but the paper gives little guidance on when it outweighs the added training stages and accuracy losses shown in Figure 3.

Questions for authors
  1. Could you clarify how the direct bound above compares with Theorem 1 under the same assumptions and C(h),m,n,δC(h),m,n,\delta? This would help me understand the role of the proposed decomposition.

  2. Could you discuss how the pipeline compares with direct teacher certification on 4,096 prompts reserved before training and model selection, using the same generations per prompt? It would be helpful to understand the settings where reusing training data is particularly valuable.

  3. Could you describe the sequence of model selection and certification, including whether the certification rewards informed checkpoint or quantization choices? The evaluator and sample count after any exclusions would also help clarify the application of Corollary 1. I also noticed that scripts/run_pipeline/06_compute_bounds.py uses log⁡(2/δ)\log(2/\delta) where the corollary gives log⁡(3/δ)\log(3/\delta); could you confirm which expression was used for the reported bounds? The numerical difference is about 0.11 percentage points for the stated binary-reward settings.

6 comments

We thank the reviewer for their insightful feedback. We concisely addressed them below and accordingly revised the paper with changes highlighted in blue.

W1/Q1: Why stochastic decoding prevents a direct application of standard compression bounds? Could you clarify how the direct bound above compares with Theorem 1? This would help me understand the role of the proposed decomposition.

We thank the reviewer for pointing out this comparison. Here, we clarify why stochastic decoding prevents a direct application of standard compression bounds, how we address it, and what our error decomposition adds. In the revised paper, we added the corresponding explanation and discussion in Sections 1, 2.2, and 3.1 and Appendix B.2.

What stochastic decoding prevents. Standard compression bounds require the following two conditions [1].

  1. a sample S={zi}i=1mS=\{z_i\}_{i=1}^m drawn i.i.d. from a distribution that does not depend on the hypothesis.
  2. a deterministic, bounded, efficiently computable loss ℓ(h,z)\ell(h,z).

For the RLVR objective, Ex∼P0[Ey∼πθ(h)(⋅∣x)[r(x,y)]]\mathbb{E}_{x\sim\mathcal{P}_0}\left[\mathbb{E}_{y\sim\pi_{\theta(h)}(\cdot\mid x)}\left[r(x,y)\right]\right], there are two direct ways to instantiate the standard bound. However, neither satisfies both conditions.

  1. z=(x,y)z=(x,y) with y∼πθ(h)(⋅∣x)y\sim\pi_{\theta(h)}(\cdot\mid x) and ℓ=r(x,y)\ell=r(x,y). The loss is efficiently computable. However, the sampling distribution P0⊗πθ(h)\mathcal{P}_0\otimes\pi_{\theta(h)} depends on hh, which violates condition 1.

  2. z=xz=x with ℓ(h,x)=Ey∼πθ(h)(⋅∣x)[r(x,y)]\ell(h,x)=\mathbb{E}_{y\sim\pi_{\theta(h)}(\cdot\mid x)}[r(x,y)]. This satisfies condition 1. However, computing the loss exactly requires summing over vocabularylen(sequence)\text{vocabulary}^{len(sequence)} sequences. For Qwen3.5-4B, with a vocabulary of 248,320 tokens and a maximum generation length of 4,096, this approach requires summing over about 102209810^{22098} sequences per prompt.

Therefore, standard compression bounds are not directly applicable to RLVR without implausibly large amounts of computation.

Addressing stochastic decoding with reparameterization. We applied the Gumbel-max trick to reparameterize the stochastic decoding y∼πθ(h)(⋅∣x)y\sim\pi_{\theta(h)}(\cdot\mid x) with random noise ξi,j\xi_{i,j} that is independent of the hypothesis. The proposed bound already includes this reparameterization to compute R^m,n(h)\hat{R}_{m,n}(h). Without the reparameterization, the per-prompt rollout averages fall under the first instantiation above, whose sampling distribution depends on hh.

Comparison of bounds. The proposed bound does not consider the two sources of randomness with separate concentration arguments. Instead, it treats each prompt and its noise vectors as one i.i.d. sample. Hence, the proposed bound requires noise vectors to be independent across prompts. However, noise vectors shared across prompts do occur in practice (e.g., vLLM broadcasts seed across a batch of prompts [2]). In this setting, the proposed bound becomes invalid, while our error decomposition framework can address the effect of shared noise vectors with the intrinsic error (Appendix B.2).

[1] Lotfi, et al. “Non-Vacuous Generalization Bounds for Large Language Models” ICML (2024).

[2] tolleybot. “[Bug]: Broadcasting one seeded SamplingParams across a batch gives every prompt the same noise vector” https://github.com/vllm-project/vllm/issues/50440.

W2/Q2: Could you discuss how the pipeline compares with direct teacher certification on 4,096 prompts reserved before training and model selection, using the same generations per prompt?

We agree that a sufficiently large held-out test can often give a tighter bound than ours. However, held-out testing bounds and PAC-Bayes bounds differ in what they guarantee and how they can be used. We added a paragraph in Section 6 to discuss this. We summarize the key points here.

  • Scope of the guarantee. A held-out bound only covers the hypothesis fixed before the held-out set is examined, while a PAC-Bayes bound holds simultaneously for all hypotheses.

  • No reserved data. A PAC-Bayes bound uses only the training data and requires nothing held out. Therefore, PAC-Bayes bounds are particularly valuable when data are scarce or expensive. For example, constructing SWE-Bench Pro V2 required 404 hours from 23 professional engineers [5], while solving each task in FrontierMath took expert mathematicians multiple hours to multiple days [6].

  • Bound optimization. A held-out bound becomes invalid when we adaptively use it to improve training without addressing the multiple comparisons problem [3, 4]. In contrast, we can improve training to minimize a PAC-Bayes bound computed on training data, while the bound stays valid.

  • Explanation of generalization: A PAC-Bayes generalization bound explains why a model generalizes and enables the developer to compare training algorithms qualitatively. In contrast, a held-out set is a black-box test that does not explain generalization.

Q3.1: Could you describe the sequence of model selection and certification, including whether the certification rewards informed checkpoint or quantization choices? The evaluator and sample count after any exclusions would also help clarify the application of Corollary 1.

Sequence of model selection and certification. We clarify that the certification rewards did not inform checkpoint or quantization choices. This is required to ensure the validity of the subsample bound in Corollary 1. In the revised paper, we discussed the selection process in Section 4 and described the selection we performed in experiments in Section 5.1.

  1. Checkpoint: In each experiment, we saved a checkpoint every 5 training steps and selected the one that achieved the highest reward on a validation set of 1,000 prompts.

  2. Number of quantization levels: Before training, we fixed a candidate set for the number of quantization levels, inspired by prior work [1]. For the selected checkpoint, we then computed the bound for each candidate using the empirical reward on the validation set and selected the candidate with the highest bound.

Neither selection affects the validity of our bounds because the validation set, the candidate set, and the selection procedure were fixed before examining the 4096 subsample used for Corollary 1.

Evaluator and sample count. For each domain, we compute the reward on the 4096 subsample with the verifier described in Section 5.1. The reported 4096 is the number of prompts used for Corollary 1 after any exclusions.

Q3.2: Could you confirm which expression was used for the reported bounds?

We confirm that the reported bounds use 3/δ3/\delta as in Corollary 1. The 2/δ2/\delta in scripts/run_pipeline/06_compute_bounds.py was an error in the artifact that was supposed to calculate the full-data bound. We have corrected it in the revised supplementary material.


[3] Blum, Avrim and Hardt, Moritz. “The ladder: A reliable leaderboard for machine learning competitions” ICML (2015).

[4] Cawley, Gavin and Talbot, Nicola. “On over-fitting in model selection and subsequent selection bias in performance evaluation” JMLR (2010).

[5] Dan, Soham, et al. "SWE-Bench Pro V2: A Cleaner, Harder-to-Game Coding Benchmark." arXiv:2610.24206 (2026).

[6] Glazer, Elliot, et al. "Frontiermath: A benchmark for evaluating advanced mathematical reasoning in ai." arXiv:2411.04872 (2024).

Thank you for the response and revisions. The new shared-noise proposition and proof are sound and clarify the role of the error decomposition under correlated noise. The added details on model selection and certification largely address my earlier questions.

However, my concerns about the main theoretical contribution remain. Under Theorem 1’s independent-noise assumption, using the paper’s reparameterization, each prompt together with its decoding noise can be treated as an independent sample. Applying Hoeffding’s inequality and a prior-weighted union bound directly to the bounded per-prompt average rewards yields a tighter bound, without the 1+1/n1+1/\sqrt n factor or the associated confidence-budget split. The shared-noise extension broadens applicability but does not change this comparison. Can you distinguish the independent-noise result from the shared-noise extension?

I appreciate that compression bounds allow training-data reuse and model selection with guarantees. The revision also appropriately acknowledges that directly certifying the teacher typically yields tighter bounds when sufficient independent test data can be reserved. However, the paper still does not establish when these benefits outweigh the additional distillation and quantization steps and their accuracy costs.

I value the non-vacuous certification results, but still have reservations about the theoretical advance and practical advantages over held-out certification. I therefore maintain my weak reject rating for now.

Reviewer_XLFwOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper develops compression-based PAC-Bayes bounds for expected RLVR rewards, using Gumbel-max reparameterization to separate uncertainty from prompt sampling and stochastic generation. It also derives a subsampling bound to reduce the cost of estimating empirical rewards. To obtain useful guarantees, Progressive RLVR trains a LoRA teacher, distills it on-policy into a TinyLoRA student, and quantizes the learned update. On Qwen3.5-4B across math, programming, general knowledge, and text-to-SQL, the resulting accuracy lower bounds lie 6–11% below the student's empirical accuracy.

Critical strengths
  1. The good point of this is that Theorem 1 and Corollary 1 yield positive lower bounds for a 4B-parameter model across four rather different tasks. The paper reports the numerical bounds alongside student and teacher accuracy, and decomposes the penalties. This goes beyond presenting a formal bound that cannot be evaluated in practice.

  2. Experimental results of this paper show that on-policy distillation, TinyLoRA, and quantization affect the accuracy–description-length tradeoff in distinct ways, while standard rank-1 LoRA gives vacuous bounds in the tested 4B configurations. This helps explain why the pipeline is consequential.

Critical weaknesses

Theorem 1 treats the frozen checkpoint, SVD bases, random projections, adapter layout, decoding settings, and code as a hypothesis-independent decoder. The paper should clarify whether the final checkpoint and quantization level were fixed before inspecting the 4096 prompt evaluation subsample, and account for any selection using that subsample.

Questions for authors

Were the five quantization levels fixed independently of the 4096 prompt subsample used for Corollary 1? If any were chosen after inspecting that subsample, how is selection reflected in the confidence bound?

1 comment

We thank the reviewer for their comments. We addressed them below and revised the paper with changes highlighted in blue.

Were the five quantization levels fixed independently of the 4096 prompt subsample used for Corollary 1? If any were chosen after inspecting that subsample, how is selection reflected in the confidence bound?

The final checkpoint and the choice of five quantization levels were selected without using the 4,096-prompt subsample in Corollary 1. This is required to ensure the validity of the subsample bound in Corollary 1. In the revised paper, we clarified the selection process in Section 4 and explained the selection we performed in experiments in Section 5.1. We summarize our selection procedure briefly as follows:

  1. Checkpoint: In each experiment, we saved a checkpoint every 5 training steps and selected the one that achieved the highest reward on a validation set of 1,000 prompts.

  2. Number of quantization levels: Before training, we fixed a candidate set for the number of quantization levels, inspired by prior work [1]. For the selected checkpoint, we then computed the bound for each candidate using the empirical reward on the validation set and selected the candidate with the tightest bound.

We completed both selections without inspecting the 4,096-prompt subsample. We then used that subsample solely to compute the empirical reward entering the reported Corollary 1 bound. Therefore, no additional correction for the confidence bound is needed.

[1] Lotfi, et al., “Non-Vacuous Generalization Bounds for Large Language Models” ICML (2024).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.