acceptodds
Under review as a conference paper at ICLR 2027

Learning Stratified Policies for Inference-Time Objectives

Abstract

Inference-time scaling improves the performance of large language models by sampling multiple responses and evaluating their collective utility. However, many existing approaches obtain these samples by repeatedly sampling from a single policy. In this work, we study if the sample budget at inference time can instead be allocated across a population of policies. We introduce stratified policies, where each of learned policies contributes one response to a -sample inference-time objective. We realize this policy population using separate LoRA adapters on a shared language model backbone and optimize it for pass@. We theoretically motivate the approach by analyzing the linear setting; a population of LoRAs can achieve zero best-of- approximation error in settings where every single LoRA has strictly positive prediction error. Empirically, we demonstrate that stratified policies consistently improve pass@ over a single-policy baseline across multiple reasoning tasks. Overall, our results highlight how distributing samples across complementary policies can be a more effective use of sample budget than repeated i.i.d. sampling from a single policy at inference time.

Primary area:
reinforcement learning
Keywords:
RL, inference-time compute, pass@k, reasoning

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_E7vEOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

In this paper, the authors propose a fine-tuning method optimized for inference time methods such as Best-of-n or Pass-at-k. They highlight a limitation in sampling each n/k samples from the same distribution, and propose an approach, inspired by stratified sampling, to jointly train a population of policies for better performance on inference time sampling strategies. They implement this strategy with LoRA adapters, and provide theoretical results in linear settings highlighting the necessity of different policies to achieve zero error on specific target functions. Through experiments, they highlight the efficacy of their approach across a variety of reasoning tasks and model scales.

Critical strengths
  • The method is intuitive and well-motivated.
  • The experiments are very compelling, I really appreciated the Mixture baseline as providing more context for the efficacy of the method: sampling from each policy is necessary to leverage a diversity of policies that can subsequently specialize, otherwise in the Mixture setting there is no guarantee that the LoRA "expert" for a given problem will be invoked.
Critical weaknesses
  • You say your goal isn't to improve Pass@k. Why is this? Aren't you explicitly optimizing for this and trying to improve inference time methods?
  • Presentation: You have some hanging 1/2 line phrases, such as "Unlike LOO, this modification does not give an unbiased estimate of the best-of-k policy gradient." at the end of your pages. They're slightly jarring and would probably save you space if you were to merge them with the paragraphs above them.
  • The normalized color bars in Fig. 4 do not visualize problems which are solved by more than 1 policy, they just communicate the distribution of unique problems. I would be interested to see unnormalized forms to see proportion of problems that are not uniquely solved, otherwise its hard to understand what this is communicating, and potentially misleading readers into thinking that it is providing evidence towards individual policy specialization (which Fig. 6 shows does not always happen).
Questions for authors

I am curious about the bimodal pattern you observed in the Jaccard similarity plots. Do you think this indicates that, for certain tasks, fewer than 5 total policies are required to solve the task, leading to redundant policies?

3 comments

We thank the reviewer for carefully reviewing our paper! We greatly appreciate the feedback. Please see below our responses to the comments.

We have also updated the paper by adding additional experiments and analysis in the appendices based on the feedback (updated text in lavender).


1. You say your goal isn't to improve Pass@k. Why is this? Aren't you explicitly optimizing for this and trying to improve inference time methods?

We would like to clarify that our goal is indeed to improve pass@kk. Lines 108-112 on page 3 emphasize that we do not aim to design a state-of-the-art method for pass@kk. Instead, we view using stratified policies as a complementary approach that could also benefit other pass@kk optimization methods.


2. ... You have some hanging 1/2 line phrases... at the end of your pages.

We thank the reviewer for noting this. We have merged these sentences with the preceding paragraphs.


3. The normalized color bars in Fig. 4 do not visualize problems which are solved by more than 1 policy... I would be interested to see unnormalized forms to see proportion of problems that are not uniquely solved...

Based on the reviewer's suggestion, we have revised Fig. 6 to show each adapter’s contribution to problems solved by exactly one, two, three, four, or five policies. The heights of the bars show the percentage of solved problems at each count. Colors show the contribution of each policy (e.g., if exactly mm policies solve a problem, each is considered to have contributed equally).


4. I am curious about the bimodal pattern you observed in the Jaccard similarity plots. Do you think this indicates that, for certain tasks, fewer than 5 total policies are required to solve the task, leading to redundant policies?

Although the bimodal pattern in the Jaccard similarity heatmap for Knights-&-Knaves shows that some policies solve similar sets of problems, it does not necessarily imply that two policies are sufficient. Based on the reviewer's suggestion, to make this more concrete, we evaluate the sets of solved problems for every subset of the five policies on Knights-&-Knaves using greedy decoding, and report below the best subset's coverage (how many problems are solved) for each subset size, along with the gap w.r.t. using the full population:

Subset SizeCoverage of Best SubsetGap
274.674.6\\%19.019.0
384.684.6\\%9.09.0
490.890.8\\%2.82.8
593.693.6\\%00

Even the best pair of adapters (selected in hindsight) is severely suboptimal compared to using the full population.


We hope that our responses address your concerns and are helpful in improving your rating. If you have any other comments or feedback, please let us know! We are looking forward to hearing back from you! Thank you again for the review.

Reviewer_E7vEOpenReview ↗

Reviewer Response

Thank you for clarifying things! I appreciate the last experiment (point 4) and the effort put in to responding and updating the paper. Maybe this last result could go in the Appendix of the paper.

I think this paper deserves an acceptance at the conference!

Thank you for your positive feedback! Based on your suggestion, we have added the analysis of the bimodal pattern in Knights-&-Knaves to Appendix H, Table 5. We would appreciate it if you could consider increasing your rating, if you feel the additional experiments and analysis have strengthened the paper. Please let us know if you have additional comments or feedback. Thanks!

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

This paper replaces repeated sampling from a single language-model policy with one sample from each member of a jointly trained policy population. The implementation uses separate LoRA adapters on a shared frozen backbone and a winner-only update motivated by pass@k. A linear expressivity result establishes a separation between a population evaluated by its best prediction and a single linear predictor. Experiments on four reasoning tasks report improved pass@5, with controls for adapter parameter count, independent training, and sampling from a mixture of the same adapters.

Critical strengths
  1. The paper studies a relevant question: how to allocate a limited response budget across multiple policies. Comparing stratified sampling with sampling from a mixture of the same adapters helps isolate the benefit of the sampling strategy.

  2. The empirical study includes meaningful controls for adapter parameter count and independent-population training cost, with results across four tasks and three seeds. These controls and the consistent gains provide a credible empirical contribution, even though the underlying population-optimization idea builds on prior work. The transparent reporting of update bias and the pass@1 trade-off further supports my weak-accept assessment.

Critical weaknesses
  1. The main area where I would welcome a stronger case is novelty. The paper explicitly relates its objective to the binary-reward case of population RL in Grinsztajn et al. (2023) and to stochastic multiple choice learning. The linear expressivity theorem illustrates the benefit of a best-of-K collection, but does not establish a corresponding result for stochastic nonlinear LLM policies. The methodological novelty appears moderate, and a clearer explanation of the additional insight would improve the positioning.

  2. The evidence for a broader scaling interpretation would benefit from a modest extension beyond the current configuration. The main results fix k=5, and Appendix G shows that the Sudoku gain changes from 6.1 points with the group-mean update to 2.5 with leave-one-out. The existing comparison remains meaningful. A small extension of this ablation, or a narrower statement of the scaling claim, would help establish the scope of the observed benefit.

Questions for authors
  1. Could you clarify the specific methodological or empirical insight beyond the population objectives and winner-based optimization discussed in the related work? This would be particularly helpful for assessing the contribution.

  2. Is there evidence that the advantage persists at another population size or under leave-one-out on another task? Such evidence would help establish whether the contribution extends beyond the reported configuration.

2 comments

We thank the reviewer for carefully reviewing our paper! We greatly appreciate the feedback. Please see below our responses to the comments.

We have also updated the paper by adding additional experiments and analysis in the appendices based on the feedback (updated text in lavender).


1. The main area where I would welcome a stronger case is novelty... Could you clarify the specific methodological or empirical insight beyond the population objectives and winner-based optimization discussed in the related work?

We would like to emphasize that our work studies stratification for general kk-sample inference-time objectives, and we instantiate our framework with pass@kk for the experiments. As stated in our related work section, the pass@kk objective in our work recovers the binary-reward special case of Grinsztajn et al. (2023). We discuss our additional contributions below.

First, we study sample allocation across policies for a general k-sample utility, which allows us to separate the choice of training objective from the structure of the population. Our experiments show that stratification improves pass@kk under both LOO and group-mean training. In Appendix J, we analyze the different utility optimized by group-mean and show its connection to Maximum Likelihood Reinforcement Learning (MaxRL) [Tajwar et al., 2026].

Second, we provide a practical implementation for LLM post-training using separate LoRA adapters on a shared (frozen) LLM backbone. This allows us to jointly train the population without maintaining separate copies of the full language model. In contrast to supervised winner-based training in LoRA-MCL [Letzelter et al., 2026], we jointly train the LLM policies through reinforcement learning, where the updates are determined by the rewards from the sampled set of responses.

Third, our experiments separate the benefit of sample allocation from differences in the trained policies. Stratified and Mixture use exactly the same trained adapters and budget of responses. However, they differ in how this budget is allocated across adapters. Therefore, the gap in performance between these methods helps us measure the benefit of sampling once from each policy in the population while keeping the policies and their individual accuracies fixed.

Overall, our results show how stratified populations can improve LLM reasoning under a fixed budget of responses.


2. The linear expressivity theorem illustrates the benefit of a best-of-K collection, but does not establish a corresponding result for stochastic nonlinear LLM policies.

We would like to clarify that our contribution is primarily empirical, and Theorem 1 provides theoretical motivation by showing that a LoRA population can be more expressive than a single linear predictor. The theorem does not cover stochastic policies. Extending the analysis to stochastic nonlinear policies is an interesting direction for future work.


3. Is there evidence that the advantage persists at another population size or under leave-one-out on another task?

Based on the reviewer's suggestion, we evaluated Single and Stratified on Sudoku with varying population size k∈{3,5,8}k\in\{3,5,8\}, and trained using the group-mean advantage. Appendix I, Fig. 11 shows that Stratified beats Single at all three population sizes (+6.2+6.2, +6.1+6.1, and +2.2+2.2 improvement in pass@kk, respectively). Further, the improvement is positive on every seed at each value of kk.

We have also updated Table 3 to include results for Knights-&-Knaves. It compares the group-mean baseline with the leave-one-out baseline, and the results show two things. First, the group-mean baseline improves Stratified on every seed of both tasks (+4.3+4.3 on average on Sudoku, +4.7+4.7 on Knights-&-Knaves). Second, Stratified outperforms Single on all seeds under both baselines.

The table below reports the gains in pass@55 from Stratified over Single, averaged across three seeds.

BaselineGain on SudokuGain on Knights-&-Knaves
LOO+2.5+2.5+1.9+1.9
Group-Mean+6.1+6.1+2.6+2.6

We provide full results in Appendix G, Table 3.


[Grinsztajn et al., 2023] Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization. NeurIPS 2023.

[Tajwar et al., 2026] Maximum Likelihood Reinforcement Learning. ICML 2026.

[Letzelter et al., 2026] Multiple Choice Learning of Low-Rank Adapters for Language Modeling, ICML 2026.


We hope that our responses address your concerns and are helpful in improving your rating. If you have any other comments or feedback, please let us know! We are looking forward to hearing back from you! Thank you again for the review.

Dear Reviewer zxaT,

Since the Author/Reviewer Discussion period concludes on Nov. 18, we would be happy to address any remaining concerns or questions.

Thanks!

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

This paper proposes stratified policy populations to improve pass@k under a fixed response budget. The method samples one response from each policy, using separate LoRA adapters on a shared frozen backbone in the language-model experiments. Joint training assigns a winner-only group-relative update, making each policy's learning signal depend on the full response set. A piecewise-linear analysis illustrates how multiple adapters can cover target mappings that one linear predictor cannot fit.

Critical strengths
  1. The idea is interesting. Allocating one sample to each jointly trained adapter provides a simple way to encourage complementary coverage without a separate diversity reward.
  2. The paper is well-written and easy to follow. The figures and tables are visually appealing and clearly presented.
Critical weaknesses
  1. Eq. (6) reinforces successful responses even when another population member already solves the prompt. After averaging the random tie-breaking, its unclipped sequence-level gradient corresponds to a count-based surrogate whose reward increment for the m-th success is $ \frac{1}{m} - \frac{1}{k} $. This rewards additional successes beyond the first, unlike pass@k. The acknowledged bias therefore changes what the population learns, rather than merely reducing gradient variance. In Appendix G, changing the estimator increases the stratification advantage on Sudoku from 2.5 to 6.1 points. The interpretation of the main gains needs to separate this surrogate's effect from optimizing complementary coverage under the stated objective.
  2. Theorem 1 compares a population evaluated by an oracle minimum with a single deterministic linear predictor. Repeating the latter produces identical predictions, so the theorem does not represent the central comparator of k independent samples from a stochastic policy. It establishes an expressivity separation for multiple predictors, but does not explain how much of the practical advantage comes from sample allocation rather than the chosen function class. A connection to the finite-budget stochastic setting is missing from the theoretical motivation.
Questions for authors
  1. How do the complementarity measurements change under the temperature-1 sampling used for pass@5, after accounting for each adapter's marginal accuracy? Figures 5 and 6 use greedy decoding, and lower individual accuracy can itself reduce overlap between solved-item sets.
  2. How are the population members initialized from the shared warm-start adapter, and what breaks their initial symmetry? Does early winner selection create persistent differences in update counts or leave some adapters contributing very little?
5 comments
AuthorsOpenReview ↗

Rebuttal [Part 1 of 2]

We thank the reviewer for carefully reviewing our paper! We greatly appreciate the feedback. Please see below our responses to the comments.

We have also updated the paper by adding additional experiments and analysis in the appendices based on the feedback (updated text in lavender).


1. Eq. (6)... changes what the population learns, rather than merely reducing gradient variance…

We agree that Eq. 6 changes the training objective. Based on the reviewer's suggestion, in Appendix J, we formalize this objective and prove its connection to Maximum Likelihood Reinforcement Learning (MaxRL) [Tajwar et al., 2026]. More concretely, the group-mean advantage optimizes the expected utility FGM=∑m=1K(1m−1k)F_{\mathrm{GM}}=\sum_{m=1}^{K}\left(\frac{1}{m}-\frac{1}{k}\right), where KK is the number of successful responses. Therefore, additional successes are rewarded with decreasing returns.

In the single-policy setting, we show that ∇θJGM(θ)=∇θEx∼ρ[∑j=2k1jpass⁡@j(x)]\nabla_\theta J_{\mathrm{GM}}(\theta)=\nabla_\theta\mathbb{E}_{x\sim\rho}\left[\sum_{j=2}^{k}\frac{1}{j}\operatorname{pass}@j(x)\right], whereas the truncated MaxRL objective has gradient ∇θJMaxRL(k)(θ)=∇θEx∼ρ[∑j=1k1jpass⁡@j(x)]\nabla_\theta J_{\mathrm{MaxRL}}^{(k)}(\theta)=\nabla_\theta\mathbb{E}_{x\sim\rho}\left[\sum_{j=1}^{k}\frac{1}{j}\operatorname{pass}@j(x)\right]. This shows that the updates using the group-mean baseline remove the pass@11 term in this setting. Tajwar et al. (2026) empirically show that MaxRL beats pass@kk optimization. This is consistent with our experiments in Appendix G, where the group-mean baseline achieves higher mean pass@kk (across three seeds) than the leave-one-out baseline (LOO), even though LOO directly optimizes pass@kk:

TaskMethodLOO pass@5Group-Mean pass@5
SudokuSingle73.473.474.274.2
SudokuStratified75.975.980.380.3
Knights-&-KnavesSingle86.586.590.690.6
Knights-&-KnavesStratified88.588.593.293.2

We provide full results in Appendix G, Table 3.

A useful analogy is classification. Although accuracy corresponds to the 0–1 loss, training typically uses a surrogate such as cross-entropy, which provides non-zero gradients even when all training examples are correctly classified.


2. The interpretation of the main gains needs to separate this surrogate's effect from optimizing complementary coverage under the stated objective.

To separate the benefit of using stratified policies from the choice of baseline, we also compare Stratified and Single under LOO on both Sudoku and Knights-&-Knaves, and report the gains in pass@55 due to stratification (averaged across three seeds) below:

BaselineGain on SudokuGain on Knights-&-Knaves
LOO+2.5+2.5+1.9+1.9
Group-Mean+6.1+6.1+2.6+2.6

We provide full results in Appendix G, Table 3.

Stratified outperforms Single on every seed under both baselines, including LOO, which directly optimizes pass@kk. Therefore, stratified policies improve performance under both baselines, but the magnitude of improvement varies.


3. Theorem 1… establishes an expressivity separation for multiple predictors, but does not explain how much of the practical advantage comes from sample allocation rather than the chosen function class.

We would like to clarify that our contribution is primarily empirical, and Theorem 1 provides theoretical motivation by showing that a LoRA population can be more expressive than a single linear predictor. The theorem does not cover stochastic policies. Extending the analysis to stochastic nonlinear policies is an interesting direction for future work. We address the sample allocation question through the comparison between Stratified and Mixture in Point 4 of our response.

AuthorsOpenReview ↗

Rebuttal [Part 2 of 2]

4. How do the complementarity measurements change under the temperature-1 sampling used for pass@5…

Based on the reviewer's suggestion, in Appendix H, we analyze complementarity under the temperature-1 sampling used for pass@55.

Let pi(x)p_i(x) denote the probability that a response sampled from policy πθi(⋅∣x)\pi_{\theta_i}(\cdot\mid x) is correct. Stratified independently samples one response from each of the kk policies. In contrast, Mixture samples kk responses independently from the uniform mixture πˉ(⋅∣x)=1k∑i=1kπθi(⋅∣x)\bar\pi(\cdot\mid x)=\frac{1}{k}\sum_{i=1}^{k}\pi_{\theta_i}(\cdot\mid x). Define pˉ(x)=1k∑i=1kpi(x)\bar p(x)=\frac{1}{k}\sum_{i=1}^{k}p_i(x). The probabilities that at least one of kk responses is correct are PStratified(x)=1−∏i=1k(1−pi(x))P_{\mathrm{Stratified}}(x)=1-\prod_{i=1}^{k}(1-p_i(x)) and PMixture(x)=1−(1−pˉ(x))kP_{\mathrm{Mixture}}(x)=1-(1-\bar p(x))^k.

By the AM–GM inequality, PStratified(x)≥PMixture(x)P_{\mathrm{Stratified}}(x)\geq P_{\mathrm{Mixture}}(x). The gap is zero iff all the policies have the same success probability on xx. Appendix H, Fig. 10 shows its expectation over the prompt distribution as a measure of complementarity:

BaselineStratified − Mixture on SudokuStratified − Mixture on Knights-&-Knaves
LOO+8.4+8.4+6.3+6.3
Group-Mean+10.1+10.1+7.5+7.5

The results are averaged across three seeds. There is a substantial gap between Stratified and Mixture on both tasks under both estimators. Both of these methods use the same set of trained adapters (i.e., the per-adapter accuracy is the same across the methods), so this experiment isolates the benefit of sampling once from each adapter.

To further analyze if a single policy in the population is responsible for Stratified's performance, we evaluate the pass@55 accuracy of each adapter individually, using five independent samples from that adapter. Appendix H, Table 4 shows that even the best adapter (selected in hindsight) underperforms both Single and Stratified on every seed of both tasks.


5. How are the population members initialized from the shared warm-start adapter, and what breaks their initial symmetry?

In our experiments, we initialize all LoRA adapters in the population with the same adapter weights. Their initial symmetry is broken because responses are sampled independently at any step in training and only the winner (ties broken randomly) is updated.


6. Does early winner selection create persistent differences in update counts or leave some adapters contributing very little?

Based on the reviewer's suggestion, we additionally show in Appendix G, Fig. 9 that all adapters continue receiving gradient updates throughout training. The group-mean baseline also provides a denser learning signal (more updates for every adapter) than LOO, and the updates are also spread relatively evenly across adapters.


[Tajwar et al., 2026] Maximum Likelihood Reinforcement Learning. ICML 2026.


We hope that our responses address your concerns and are helpful in improving your rating. If you have any other comments or feedback, please let us know! We are looking forward to hearing back from you! Thank you again for the review.

Dear Reviewer wHAn,

Since the Author/Reviewer Discussion period concludes on Nov. 18, we would be happy to address any remaining concerns or questions.

Thanks!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.