acceptodds
Under review as a conference paper at ICLR 2027

Maximin Inference-Time Alignment with Diverse Rewards

Abstract

Inference-Time Alignment (ITA) improves a learned model’s output through sampling and search heuristics without modifying its underlying weights. While effective in guiding the model response, in reality a single model often serves a diverse group of users or is evaluated over multiple categories (e.g. accuracy, safety) with different reward models. This raises the question of how a shared and finite sampling budget should be allocated to ensure response quality across multiple groups of users or different evaluation criteria. We formulate this problem as a maximin budget allocation problem and study ITA under exact-reward and proxy reward settings. In the exact-reward setting, we upper bound the maximin regret of a greedy variant of Best-of-N algorithm (Greedy-BoN) and show that the regret goes to zero as the budget goes to infinity. However, in the proxy reward setting, the above approach fails even as the sampling budget goes to infinity. To overcome this, we develop Batched Greedy Pessimistic (BGP) algorithm that allocates each batch to the group using pessimistic response selection, and bound its maximin regret with respect to the proxy reward floor. Empirically, we evaluate Greedy-BoN and BGP on a dataset with five different domain (groups) and show that Greedy-BoN performs best with respect to the proxy reward, whereas BGP performs best when evaluated against an external judge, highlighting the importance of pessimism in inference-time alignment.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Inference Time Alignment, Maximin Allocation, Greedy Sampling

Reviews

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

The paper studies how to allocate a shared inference-time sampling budget across groups to maximize the minimum expected reward. It analyzes a greedy Best-of-N allocation rule under exact rewards and shows that proxy reward errors can cause persistent regret. It then proposes Batched Greedy Pessimistic, combining pessimistic response selection with adaptive allocation, and provides regret bounds under stated error and coverage assumptions. Experiments use five SHP domains with separate proxy and judge reward models.

Critical strengths

The paper gives a clear theoretical account of why allocation based on exact rewards can behave differently from allocation based on imperfect proxies. The counterexample and pessimistic formulation make reward-model error an explicit part of the allocation problem, rather than assuming proxy scores are reliable.

Critical weaknesses
  1. The empirical contribution of adaptive allocation is not convincingly isolated. Appendix F reports no consistent judge-reward improvement over Uniform-Pess-Auto on the original five groups. Thus, the gains over simpler baselines do not clearly establish an advantage from adaptive allocation beyond pessimistic selection and automatic regularization.

  2. The connection between the theoretical error assumption and its empirical estimate needs clarification. Appendix E estimates group error using tuning-set proxy–judge RMSE, which does not by itself establish the error upper bound required by the analysis. This limits how directly the theoretical guarantees support the implementation.

Questions for authors
  1. Clarification: Given Figure 4(a), what empirical conclusion about the benefit of adaptive allocation is supported on the original five-group setting?

  2. Clarification: How is the tuning-set RMSE related to the error upper bound assumed in the theory, and how sensitive are the results to underestimating that bound?

3 comments
AuthorsOpenReview ↗

Authors' Rebuttal

We thank the reviewer for the constructive feedback. Please see our responses below.

Weakness 1 & Question 1.

When reward model can reflect human preference accurately, the adaptive allocation in Greedy BoN and BGP are consistently better than the uniform-allocation version.

In the manuscript, we investigate that the similar performance between BGP and Uniform-Pess-Auto. One of the reason is because that the original five domains exhibit estimation errors in both directions, while the pessimistic index uses only the estimated error magnitude without distinguishing its sign. Figure 4 (b) shows that when proxy rewards consistently overestimate Judge rewards across domains, BGP achieves better performance than Uniform-Pess-Auto.

Weakness 2 & Question 2.

We used RMSE computed on a separate tuning split as an empirical estimate of the error-bound parameter εˉi\bar\varepsilon_i for each domain ii. Strictly matching the theoretical setting would require sampling responses in advance for the specific prompts to which ITA is applied. Under the limited sampling budgets considered in our setting, such additional sampling on test prompts would be impractical and would hurt the practical utility of our method.

As an additional experiment, we estimated prompt-level εˉi\bar \varepsilon_i using 256 responses generated for each test prompt II. The results below show that this finer-grained estimation improves both BGP and BGP-fixed relative to their original versions using tuning-split estimates. Moreover, prompt-level BGP consistently outperforms prompt-level BGP-fixed across all evaluated budgets.

Budget BBOriginal BGPPrompt-level BGPBGP-fixedPrompt-level BGP-fixed
650.2733880.2764190.2655900.269271
900.2748360.2779510.2678170.272169
1250.2753830.2782880.2666120.272404
1800.2770290.2791210.2692260.273498
2550.2760830.2781890.2681500.272942

Thanks for your response, somewhat addressed my concerns. But i wonder how could it extends to multi-turn situation, considering the practical application, I also find it hard to see a concrete application for this setup. How would it fit into current agent loops or harnesses?

Thanks for your follow-up questions.

Our problem is how to distribute a shared inference-time compute budget among groups with diverse preferences. It arises when a system improves its output quality by sampling several candidates in parallel and selecting one with a reward model. One application is the following agent harness: we split a task into several sub-tasks which are solved by sub-agents within a limited budget, and each task has its own verifier to judge its output quality. The final result is combined on these sub-agents' outputs, and is limited by the weakest sub-task response, which is exactly our maximin objective.

Our current formulation studies the response-level budget, in which there is a total number of BB responses to allocate. We appreciate your questions about multi-turn extension and practical application, and discuss two extensions below.

(1) Token-level budget. In practice the budget is often counted in tokens, so each response's cost is determined by its token length. Our greedy algorithm applies naturally: we allocate more tokens to the group that has the lowest response quality so far.

(2)Multi-turn responses. At each turn, the prompt is the full conversation history, and the budget is the total number of turns generated across groups. This is a sequential sampling problem, in contrast to the parallel sampling of our formulation. Our greedy algorithm can also be applied naturally, though we need a new analysis.

We believe our greedy allocation under exact rewards and pessimistic allocation under proxy rewards are the right building blocks for both extensions, and we will add this discussion to the revision.

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

The paper proposes a new maximin-based inference-time alignment approach, which targets when a single model serves multiple groups (multiple reward models) with a shared sampling budget. The main concept is to maximize the reward of the worst group. The paper tackles two different scenarios, 1) when the true rewards are known and 2) when only imperfect proxy reward models are available. For each case, the paper proposes different algorithms to maximize the worst group’s reward. Experiments are performed on five domains of the SHP dataset, and the main results show that Greedy-BoN achieves the best worst-group reward under the proxy reward models, while BGP achieves the best worst-group reward under a separate judge model.

Critical strengths

The paper has various strong aspects:

  • The main target problem, allocating a shared inference-time sampling budget across multiple groups with different reward models, is a timely and important topic. Also, the paper formulates it well as a maximin problem based on the Rawlsian principle.
  • The theoretical setup is generally clear, and the contrast between the exact-reward and proxy-reward settings is well presented.
  • The experimental results seem to be reported transparently (e.g., reporting results that do not favor the proposed method). Such transparency is great, but there are some other aspects that could be improved, as described below.
Critical weaknesses

The experiments could be improved in several aspects:

  • It is unclear whether the proposed framework can handle groups with conflicting preferences (if so, how the algorithm will result in such cases). The paper motivates the problem with different evaluation categories such as accuracy and safety, which often conflict for the same response. However, in the formulation, the groups interact only through the shared budget. Also, the five domains used in the experiments also differ mainly in topic, reward level, and reward model error, rather than in conflicting preferences. It would be helpful to experiment (or at least discuss) a setting where multiple, potentially conflicting reward models evaluate the same prompt and a single response must balance them (e.g., helpfulness vs. safety).

  • The experimental scale seems a bit limited. The experiments use one dataset with five domains and only small set evaluation prompts per domain. Also, all responses come from one base model (Qwen2.5-3B-Instruct). The baselines are also limited to uniform allocation and variants of the proposed methods, without comparison to more recent allocation approaches (e.g., Damani et al., 2025, Zuo & Zhu 2026, cited in the paper). The paper’s claim could be more convincing if it provides results with more datasets, larger models, and stronger baselines.

  • The evaluation setting might need more justification. In the experiments, the “true” reward seems to be a 7B Judge reward model trained similarly with the the 3B reward model, so their errors may be correlated. Also, the current setting does not necessarily reflect human preferences. Moreover, the error bounds used by Batched Greedy Pessimistic (BGP) are estimated from the discrepancy between the proxy and this Judge on the tuning split. This might be related to why BGP performs best under the Judge. It would be helpful to evaluate with human ratings or an independent judge (e.g., using different model families).

Questions for authors

The main questions are merged together in the above section.

2 comments
AuthorsOpenReview ↗

Authors' Rebuttal

We thank the reviewer for the constructive comments. Please see our responses below.

Weakness 1.

We would like to clarify that our problem is the allocation of a shared sampling budget across groups, not the aggregation of conflicting preferences into a shared response. In our formulation, each group (user) is specified by its own prompt and its own reward, and each group receives its own response, selected by its own reward model; a central designer decides the allocation of the budget among groups. Sharing a response across groups is a different problem (e.g., Maximin-RLHF by Chakraborty et al., 2024): the objective is to fine-tune a single model whose response is "fair" for all groups. That problem is less natural in our formulation since different users do not share a response; rather, each group's reward model selects its own. What's more, if groups share the candidate pool to a common prompt, every sample could be scored by every group's reward model, so all groups would use the full budget and no allocation problem would arise. It is an interesting problem, but not the focus of this paper.

Weakness 2.

We thank the reviewer for these helpful suggestions and we provide the following additional experiments:

  1. We implemented the two baselines suggested by the reviewer. We would also like to clarify that these baselines were not included in the original manuscript because they target different objectives. Our objective is to maximize the reward of the worst-off group, whereas [Damani et al. (2025)] maximize total expected reward across queries, and [Zuo and Zhu (2026)] maximize average query-level accuracy under a fixed compute budget.

  2. We use Mistral-7B as the base model to generate responses, Claude Haiku 5.5 as the proxy RM for algorithms and GPT-6.1-Sol as the judge RM for evaluation. The three models belong to different model families, and both RMs are commercial models. Their scoring prompts include examples from the corresponding domain as references.

  3. Except the SHP dataset we used in the manuscript, we add an experiment on another multi-domain dataset allenai/multipref.

The results are presented below.

  1. In the original Qwen-based experiments on SHP, we added the two baselines and included the Uniform BoN baseline for reference. BGP outperforms both newly added baselines across all evaluated budgets.
Budget BBBGP (ours)online-AdaBoK (Damani et al., 2025)Elim-RM (Zuo & Zhu, 2026)Uniform BoN
650.2733880.2621830.2657400.268356
900.2748360.2654820.2663830.268648
1250.2753830.2679990.2678240.264376
1800.2770290.2697480.2692890.266080
2550.2760830.2671730.2687980.266993
  1. With the stronger models on SHP, BGP continues to outperform all baselines, including the two newly added methods, across all evaluated budgets.
Budget BBBGP (ours)BGP-fixedonline-AdaBoKUniform-pess-fixedUniform BoNGreedy BoNElim-RM
650.413280.403490.404610.410660.404860.387660.39226
900.426000.404410.402440.400210.400570.372020.38597
1250.425750.404900.405880.398380.403290.376040.38484
1800.425520.409330.398400.397320.409820.377470.37212
2550.426210.408530.384930.389590.389640.380490.37203
  1. With the stronger models on the additional MultiPref dataset, BGP also outperforms all baselines, including the two newly added methods, across all evaluated budgets.
Budget BBBGP (ours)BGP-fixedonline-AdaBoKUniform-pess-fixedUniform BoNGreedy BoNElim-RM
650.339410.333780.327110.328910.325450.316380.31685
900.342790.331460.340650.331790.334780.317920.32180
1250.341290.332530.339200.330150.332040.315780.31990
1800.342720.338440.334740.336280.334170.322220.31978
2550.354530.349890.320340.339850.332320.318500.31778

Above results show that our BGP algorithm consistently keep advantages with different models, varied datasets and additional baselines.

Weakness 3.

Please refer the response for weakness 2. Since there are 64k responses included for tuning hyperparameters and for ITA samplings, it is not realistic to score them by human, we instead use GPT-6.1-sol as the Judge to reflect human preference more accurately. In additional experiments and with stronger Judge model, our BGP algorithm consistently outperforms all of baselines.

Dear Reviewer ciu9,

Thank you again for your thoughtful review of our paper. As the discussion period is approaching its end, we wanted to check whether you have any remaining concerns or would like us to clarify any part of our response. We would be happy to provide any additional clarification that may be helpful.

Best regards,

The Authors

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

This paper studies Inference-Time Alignment (ITA) under a shared and finite budget and interrogates the problem of maximum budget allocation with exact and proxy rewards. Given heterogeneous reward models, the authors take a regret minimisation perspective and seek a group-wise budget allocation that maximises the reward of the worst-off group. With exact rewards, they introduce Greedy-BoN which iteratively allocates a sample to the group with the lowest current reward and prove the optimality of this allocation and that the regret bound vanishes with growing budget. With imperfect proxy rewards, the authors point out the reward hacking pitfall of greedy selection and instead propose Batched Greedy Pessimistic (BGP), whose regret bound combines a budget-dependent term (decreases with more sampels) and a residual determined by reward error and coverage. Empirically testing on a 5-group dataset demonstrates that Greedy-BoN is best on proxy rewards, while GBP outperforms under separate judge models.

Critical strengths
  • S1. Approach of group-aware ITA. The paper does well in characterising the tradeoff bewteen a shared sampling budget and worst-group response quality. They consider algorithms for heterogeneous reward models and depart from the usual approach of optimising aggregate performance alone.
  • S2. Convincing results under exact rewards. The authors show that Greedy-BoN's pathwise optimality holds for arbitrary nondecreasing best-response value sequences; the regret analysis outines convergence through the rarity of near-optimal responses. This makes the allocation rule intuitive and ties it back to the properties of the base model.
  • S3. Treatment of imperfect rewards and BGP formulation. I found the arguments for imperfect rewards easy to follow, from the nonvanishing regret---despite increasing computation---of proxy-based greedy allocation, to then developing GBP with a guarantee that separates reward-error and coverage from budget-dependent statistical error. BGP seems well constructed: doubling batches allow for parallel response generation and separate judge evaluation mitigates over-optimisation on the proxy.
Critical weaknesses
  • W1. Limited evaluation. How much improvement do Greedy-BoN and BGP deliver within the restricted ITA policy class? The practical impact of these algorithms could be better contextualised by reporting gains over unselected base-model repsonses or changes in the induced (output) response distributions.

  • W2. Heterogeneity of group-wise preferences. The authors consider heterogeneous domains (groups) with disjoint sets of prompt-reponse pairs, rather than groups expressing conflicting preferences over shared responses. As such, it is hard to determine if evaluation primarily demonstrates balancing performance across domains or indeed about pluralistic alignment of heterogeneous preferences.

  • W3. Gap between assumption and empirical error estimates. BGP's guarantee requires an error upper bound for each prompt relative to true rewards, whereas experimentally, average domain-level disagreement with a learned judge is used instead. The domain average does not bound individual-prompt errors nor does it measure error agianst true rewards; this mismatch leaves undetermined the applicability of the guarantee and robustness to misspecified error estimates.

Questions for authors
  • Q1. How sensitive are the allocations and empirical fairness gains to reward normalisation? Independently normalising each domain to [0,1][0, 1] does not necessarily make group utilities comparable.
  • Q2. Have the authors investigated how group allocations change as the total budget grows? Do the reward tail and coverage assumptions play a role? Do allocation proportions stabilise at all and how is additional computation utilised?
  • Q3. Have the authors considered using randomisation in allocations? Although the present algorithms allocate adaptively, the main benchmark uses determinisitc fixed allocation. Could randomising over allocations improve the worst-group expected reward; could the proxy-reward guarantees extend to such benchmarks?
4 comments
AuthorsOpenReview ↗

Authors' Rebuttal (Part 1)

We thank the reviewer for the constructive feedback. Please see our responses below.

Weakness 1.

We agree with the reviewer that the gain should be contextualized, and we provide three baselines in the paper: Uniform-BoN, BGP-Fixed, Uniform-Pess-Fixed. Our algorithm aims to maximize the reward for the worst-off group at inference time, so un-selected response for each group may not fully capture this objective as the worst group could be varied for different trials. Instead, we rank groups by their empirical rewards within each trial and report the average reward at each rank across trials. This un-selected baseline uses the same number of N samples as BGP in each trial. The results below show that BGP achieves a higher average Judge reward at every group rank.

group rankAverage of N samplingBGP
Worst0.26200.2761
2nd worst0.31320.3290
3rd worst0.34830.3703
4th worst0.43070.4374
Best0.48310.5058

Weakness 2.

We would like to clarify that our problem is the allocation of a shared sampling budget across groups, not the aggregation of conflicting preferences into a shared response. In our formulation, each group (user) is specified by its own prompt and its own reward, and each group receives its own response, selected by its own reward model; there is a central designer to allocate the compute budget to each group. Therefore, whether preferences over responses conflict do not matter, since there is no common prompt and response pool is not shared between groups. In our problem, groups are heterogeneous since they differ in the quality of the base model’s responses, how much they benefit from additional samples, and the accuracy of their reward models.

Weakness 3.

In our experiments, we used RMSE computed on a separate tuning split as an empirical estimate of the error-bound parameter $\bar\varepsilon_i $ for each domain ii. Strictly matching the theoretical setting would require sampling responses in advance for the specific prompts to which ITA is applied. Under the limited sampling budgets considered in our setting, such additional sampling on test prompts would be impractical. As an additional experiment, we estimated prompt-level εˉi\bar \varepsilon_i using 256 responses generated for each test prompt ii. The results below show that this finer-grained estimation improves both BGP and BGP-fixed relative to their original versions using tuning-split estimates. Moreover, prompt-level BGP consistently outperforms prompt-level BGP-fixed across all evaluated budgets.

Budget BBOriginal BGPPrompt-level BGPBGP-fixedPrompt-level BGP-fixed
650.2733880.2764190.2655900.269271
900.2748360.2779510.2678170.272169
1250.2753830.2782880.2666120.272404
1800.2770290.2791210.2692260.273498
2550.2760830.2781890.2681500.272942

Question 1.

The normalization method in the manuscript is to min–max normalize rewards within each domain to [0,1]. In this case, improving worst-group reward thus raises the minimum relative performance across groups on these domain-specific scales. We additionally add three more normalization methods:

  1. Quantile min–max (1–99%): replaces the minimum and maximum with 1st- and 99th-percentile rewards in the domain. The central 98% of scores are mapped linearly to [0,1], while rewards outside this interval are clipped to 0/1.

  2. Empirical mid-CDF: Each reward is replaced by the proportion of rewards from the same domain that are lower than it. For example, a response with normalized reward 0.2 means its original reward is higher than 20% of responses.

  3. Z-score + sigmoid: Each reward is standardized by subtracting the mean of rewards from the same domain and dividing by the standard deviation. A sigmoid function then maps the standardized reward to a value between zero and one.

By testing different methods of normalization, we can see that our BGP method consistently outperforms other baselines under Judge evaluation. Please see our results in the next reply.

AuthorsOpenReview ↗

Authors' Rebuttal (Part 2)

NormalizationBBGPGreedy BoNUniform BoNBGP-fixedUniform-pess fixed
Domain min–max (ours)650.27340.25000.26840.26560.2675
900.27480.25080.26860.26780.2684
1250.27540.25620.26440.26660.2655
1800.27700.25780.26610.26920.2660
2550.27610.25980.26700.26810.2668
Quantile min–max (1–99%)650.37390.34550.34970.34170.3508
900.37960.35440.35810.36300.3590
1250.38190.36500.36740.36370.3686
1800.39470.36880.37210.37260.3761
2550.39550.36740.37010.37940.3816
Empirical mid-CDF650.24320.21620.20180.18610.1995
900.24890.22160.21250.19800.2158
1250.25350.21920.21290.20920.2132
1800.26290.21940.21020.20810.2141
2550.26660.23170.22730.21850.2289
Z-score + sigmoid650.31810.29740.28960.27680.2879
900.32360.30420.29950.28920.3008
1250.32500.31250.30150.29950.3029
1800.33240.31050.30030.30330.3014
2550.33500.31500.30980.31000.3088

Question 2.

Since the adaptive allocation is highly related to the proxy reward of each group, we firstly provide the average proxy reward for each domain in different number of samples. We can see that the average rewards are generally stable with different N.

DomainN=65N=90N=125N=180N=255
Academia0.46560.47420.48220.49490.5099
Culinary0.57270.57310.57490.57620.5789
Engineers0.47200.48240.48840.50050.5081
Science fiction0.58830.58850.58850.58880.5893
Change my view0.46350.48430.49650.51700.5299

The table below shows the proportion of allocations for each domain with different budgets. With a small budget, samples are distributed relatively evenly. As the budget increases, BGP allocates a larger proportion to domains with relatively low proxy rewards and gradually converge to stable proportions.

DomainB=65B=90B=125B=180B=255
Academia24.27%26.78%30.14%33.11%34.69%
Culinary15.58%11.50%9.16%6.89%5.80%
Engineers21.08%22.33%21.42%22.28%22.91%
Science fiction15.38%11.17%8.04%5.81%4.48%
Change my view23.69%28.22%31.24%31.92%32.12%

Question 3.

Our adaptive benchmark already accounts for randomization. In Appendix A.2 (referenced in footnote 1), we define the adaptive benchmark Vad⋆V_{ad}^\star (along with the adaptive regret RBad\mathcal{R}_B^{ad}) as the supreme over all adaptive allocation policies, where a policy can select the next group as a function of the sampling history.

Could randomising over allocations improve the worst-group expected reward

Yes. Consider two identical groups and B = 3: every deterministic allocation allocates one group with a single draw and another group with two draws, so V⋆=V(1)V^\star = V(1), while mixing the allocations (1,2) and (2,1) with equal probability gives each group (V(1)+V(2))/2>V(1)(V(1) + V(2))/2 > V(1). Our algorithms and the adaptive benchmark can cover such randomized allocations.

Could the proxy-reward guarantees extend to such benchmarks?

Yes. While we used the weaker deterministic benchmark in the main text for simplicity, Proposition 1 in Appendix A.2 shows that, under Assumption 1, Vad⋆−V⋆=O((k/B)γmin⁡)V_{ad}^\star-V^\star = O((k/B)^{\gamma_{\min}}), the same rate as in Theorem 1.

Dear Reviewer hnYk,

Thank you again for your thoughtful review of our paper. As the discussion period is approaching its end, we wanted to check whether you have any remaining concerns or would like us to clarify any part of our response. We would be happy to provide any additional clarification that may be helpful.

Best regards,

The Authors

Thank you for adding a comparison with unselected resposnes and testing BGP under different reward normalisations. That BGP achieves higher worst-group judge scores across all settings gives me more confidence in its practical value. Though some doubts remain about whether group rewards are comparable after normalisation, and whether theoretical assumptions (per-prompt bounds) are met in practice, I continue to think this paper is a good candidate for acceptance and maintain my score of 3.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.