- 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
-
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.
-
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
-
Clarification: Given Figure 4(a), what empirical conclusion about the benefit of adaptive allocation is supported on the original five-group setting?
-
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
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 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.
Authors' Rebuttal
We thank the reviewer for the constructive feedback. Please see our responses below.
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.
We used RMSE computed on a separate tuning split as an empirical estimate of the error-bound parameter εˉi for each domain i. 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 using 256 responses generated for each test prompt I. 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.