acceptodds
Under review as a conference paper at ICLR 2027

Learning to Allocate: Critic Training for Test-Time Agent Search

Abstract

Test-time search for LLM agents requires deciding which partial trajectories deserve further computation. Standard critic training supervises each prefix independently using continuation outcomes, although the resulting scores jointly determine how a shared search budget is allocated. We introduce RATE (Relative Allocation Training), a framework that combines pointwise continuation-value learning with relative supervision across competing prefixes. Both forms of supervision use the same sampled continuations. The joint objective preserves the ideal continuation-potential target while emphasizing relative score errors that affect allocation. At test time, the trained critic guides the allocation of continuation slots while the actor remains fixed. Across four agent environments, RATE improves mean candidate reward over Best-of-N (BoN) by 3.95–8.90 percentage points under a fixed continuation budget. The gains also extend from fixed-frontier evaluation to repeated budget allocation during online search.

Primary area:
reinforcement learning
Keywords:
LLM agents, test-time search, compute allocation, process reward models, test-time compute

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_eXeZOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors propose RATE, a framework for training critics to use at inference time. The critic is trained to decide which prefixes to allocate compute to in a particle search inference setup using a pointwise potential loss combined with a weighted cross-entropy loss over prefixes. Experiments on a set of RL environments and Qwen3 models show that RATE improves over baselines, even taking into account extra compute budget (through fixed-compute evaluations). Using RATE for SFT data generation also appears to improve performance.

Critical strengths
  1. The problem is interesting (how to train a critic well for allocation), and the method is well-justified. Experiments are described in thorough detail, with confidence intervals provided in most cases.
  2. Experimental design is strong, with fixed-compute and time-based comparisons.
Critical weaknesses
  1. Noisy evaluation: Based on Figure 3, RATE’s performance is within noise compared to most baselines, especially Norm-CE. Similarly, the reward curves in Figure 5 look especially noisy, with RATE oscillating quite wildly across training steps.
  2. It would be good to compare to baselines like Agentic Monte Carlo and contrastive twist learning, both of which are identified in the related work. As it is, the online results are a bit thin and seem fairly noisy as well (large error bars in Figure 4).
  3. The choice of a small lambda in all experiments might mean the proposed setup boils down to a return regression plus a relative error penalty, as explained by the authors themselves in Appendix A.7. This may make the method quite close to the Return-MSE + RankNet baseline.

Nit: BoN feels like a bit of a misleading name for the baseline: it’s uniform allocation over prefixes, not selecting the best single prefix to continue based on a critic.

edit: the authors addressed my concerns in the rebuttal phase and so I accordingly raised my score.

Questions for authors
  1. Do you have any results from hyperparameter sweeps, especially over lambda and gamma? How were the existing hyperparameters chosen?
3 comments

Thank you for carefully reviewing our paper. We truly appreciate your time and effort, as well as your constructive, insightful, and friendly feedback. Your suggestions helped us further examine the reliability of our results. We have added online search comparisons and hyperparameter sweeps, with detailed responses below.

1. Evaluation Noise and Training Curves

Thank you for suggesting that we further examine the reliability of our results. In the matched-training fixed-frontier evaluation on ALFWorld, after selecting checkpoints by validation reward, RATE achieves a mean candidate reward of 75.70 compared to 72.64 for Return-MSE, a gain of 3.06 with a 95% bootstrap confidence interval of [1.07, 5.29].

We also checked whether this gain holds at the fixed end of training. At that point, RATE improves over Return-MSE by 2.24 [0.35, 4.34] and over Pointwise CGF by 1.96 [0.21, 3.92], with both intervals strictly above zero. This supports the benefit of adding frontier supervision in this experiment.

Regarding the training dynamics plot (Figure 6 in the paper), the curves show unsmoothed validation rewards. Because allocation involves discrete choices, small shifts in predicted scores can cause jumps in reward.

In addition, Norm-CE also includes relative frontier supervision, only replacing the sample-dependent weight with a fixed weight. Comparing it with RATE therefore tests the added contribution of the weighting mechanism, whereas comparing with Pointwise CGF directly tests the effect of frontier supervision. We will distinguish these two takeaways more clearly in the revision.

2. Comparisons with AMC and Contrastive Twist Learning

We added adapted comparisons for AMC and CTL in our environments, sharing the same actor, critic architecture, and training data. AMC-MSE directly uses the Return-MSE critic, with the core difference being that it switches to AMC incremental-weight resampling. The weighted MSE variant uses exp⁡(return)\exp(\text{return})-weighted regression. CTL trains on the continuation bank to approximate the forward marginal KL objective, pairing the same trained critic with either our allocation rule or incremental twist resampling. Thus, RATE versus Return-MSE compares training objectives, while the AMC variants compare full search configurations.

The table below reports online search mean candidate reward on TextCraft. All methods share the same search width, horizon, and compute budget cap, which includes all scoring overhead.

MethodAllocation RuleMean Candidate Reward
RATEOurs71.60
Return-MSEOurs69.60
AMC-MSE (adapted)AMC resampling65.20
AMC Weighted-MSE (adapted)AMC resampling64.00
CTL-bank (adapted)Ours66.60
CTL-bank (adapted)Twist resampling63.40

3. Small λ\lambda and the Difference from Return-MSE + RankNet

Your observation regarding the small-λ\lambda approximation is spot on. In this regime, RATE approximates return regression plus a relative error penalty. For frontiers consisting entirely of nonterminal prefixes, the coefficient on the relative-error variance term in the scaled loss (Appendix A.7) is 1/γ1/\gamma, which remains 4 at our default γ=0.25\gamma=0.25 and does not vanish as λ\lambda decreases.

The key difference is that RATE calibrates numerical return differences, reaching minimal relative penalty when the predicted differences match the target differences. RankNet instead uses pairwise ordering labels, so even when the ranking is already correct, it still tends to push the score margins further apart.

4. Hyperparameter Sweeps and Selection

We swept λ∈{0.01,0.05,0.2,1}\lambda \in \{0.01, 0.05, 0.2, 1\} at fixed γ=0.25\gamma=0.25, and swept γ∈{0.0625,0.25,1,4}\gamma \in \{0.0625, 0.25, 1, 4\} at fixed λ=0.05\lambda=0.05. The table below lists all swept points for RATE using checkpoints selected by validation reward, reporting mean candidate reward on the fixed continuation bank (0–100 scale).

Methodλ\lambdaγ\gammaTextCraftWebShop
Return-MSE——73.3051.39
RATE0.010.2575.1351.64
RATE0.050.2575.9352.44
RATE0.20.2575.9351.61
RATE10.2573.9352.14
RATE0.050.062574.7551.81
RATE0.05175.1151.61
RATE0.05474.7551.31

5. Naming of BoN

Thank you for pointing out the ambiguity in this naming. After consideration, we have decided to adopt your suggestion and rename this baseline Uniform allocation, and we will incorporate this change throughout the revised manuscript.

Thank you again for your time and effort!

Hi, thank you for the response! I think you addressed all my concerns and so I am raising my score accordingly. I do agree with reviewer sjju that writing could be improved.

Thank you very much for your response and for taking the time to carefully consider our rebuttal. We sincerely appreciate your thoughtful feedback, constructive suggestions, and willingness to revisit your assessment. Your careful consideration and encouragement mean a great deal to us. We are truly grateful for the time and effort you have devoted to reviewing our work. Thank you again for your kindness and support throughout the review process.

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

The paper proposes RATE, a method for training critics that guide time allocation among competing agent trajectories. The method combines pointwise supervision with a frontier-level loss, accounting for relative scores. The authors show that the proposed objective preserves the ideal continuation-potential target while emphasizing errors that affect allocation decisions. Experiments on different benchmarks show improvements over standard value regression and ranking-based baselines.

Critical strengths
  1. The paper studies the interesting problem of critic predictions used joinlty to distribute a limited search budget. The objective is well motivated and justified.
  2. The analysis provide a connection between prediction errors and the quality of the allocation.
Critical weaknesses
  1. The theoretical analysis does not establish the advantage of frontier supervision over pointwise potential learning and I am not convinced that the theoretical results justify the new frontier loss. In the Proof of Prop. A2, the regret bound comes directly from the pointwise loss, while the frontier terms is used only through its non-negativity. A similar argument is used for CGF.
  2. To my understanting, the regret analysis consider the average reward of generated candidates in Eq. (13), not the reward of the best candidate found. It is unclear how the proposed guarantees translate to the quality of the final solution returned by the search.
Questions for authors
  1. See critical weakness 1. What does the new loss actually buy us theoretically?
  2. See critical weakness 2. Why is mean candidate reward used as the regret objective in (13)? Can we obtain a guarantee in terms of the best candidate as a target in the regret?
3 comments
AuthorsOpenReview ↗

Response to Reviewer Rzbh

Response to Reviewer Rzbh

Thank you very much for your careful review and for all the effort you put into evaluating our paper. We truly appreciate your thoughtful, encouraging, and constructive feedback. Below, we provide additional analysis and experiments to address your questions about the role of frontier supervision and the quality of the final returned solution.

1. What additional role does frontier supervision play?

Your observation about Proposition A2 is accurate, as that proof relies primarily on the pointwise term. However, while keeping the ideal potential target unchanged, the frontier term directly constrains the relative errors that actually determine allocation decisions. For a fixed frontier, let DFD_F denote its excess risk, and let p⋆p^\star and pθp_\theta denote the soft allocations induced by the ideal potential and the model predictions, respectively. They satisfy DF=CFDKL(p⋆∥pθ)D_F=C_F D_{\mathrm{KL}}(p^\star\Vert{}p_\theta), where CF=ZF/a(F)>0C_F=Z_F/a(F)>0.

Even when the regression MSE is identical, the resulting allocations can differ substantially. Shifting all predictions by a common constant leaves the soft allocation unchanged, whereas relative errors across prefixes can alter which prefixes receive computation. Locally, the KL divergence above is proportional to the weighted variance of the effective log-score errors, so the frontier term targets these relative errors while the pointwise term anchors the absolute potential level.

This connection can also be used directly to bound allocation regret. Under equal prior prefix weights and valid return predictions in [0,1][0,1], let rir_i be the prediction error in return units, NN be the frontier size, and AA be the set of eligible prefixes. We then have span⁡A(r)≤2λNeλDF/CF\operatorname{span}_A(r)\le\frac{2}{\lambda}\sqrt{N e^\lambda D_F/C_F}. Substituting this bound into the error span term of Equation (13) yields an allocation regret upper bound that depends explicitly on the excess risk of the frontier term.

Empirical verification. We ran a controlled comparison on ALFWorld using the exact same training configuration, comparing Pointwise CGF (pointwise loss only) against RATE (with the frontier term added). The table below reports mean candidate reward on fixed frontiers.

Checkpoint selectionPointwise CGFRATEGain and paired 95% CI
Selected by validation reward73.9775.70+1.73 [-0.42, 3.94]
Preset update 30074.8476.80+1.96 [0.21, 3.92]

2. How does the mean reward analysis relate to the best candidate and final solution?

The mean candidate reward JF(q)=∑iqiμiJ_F(q)=\sum_i q_i \mu_i directly captures the overall allocation quality on the current frontier, where qiq_i is the allocation probability and μi\mu_i is the expected continuation reward.

Connection to best-candidate quality. For binary success rewards, local regret in mean reward translates directly into regret on the best candidate. On a fixed frontier, suppose MM continuations are allocated in advance, so prefix ii receives MqiM q_i continuations in expectation, and outcomes are conditionally independent given the parent prefix. Let BMB_M be the probability of obtaining at least one successful candidate, and let μmax⁡\mu_{\max} be the highest success probability among eligible prefixes. The optimal fixed-frontier allocation achieves BM⋆=1−(1−μmax⁡)MB_M^\star=1-(1-\mu_{\max})^M, and we have 0≤BM⋆−BM≤min⁡{1,M[μmax⁡−JF(q)]}0\le B_M^\star-B_M\le\min\{1,M[\mu_{\max}-J_F(q)]\}.

This inequality follows directly from expanding the product of conditional failure probabilities, linking mean reward regret to best-candidate quality. Of course, the final solution returned to the user also depends on the final selector, so we measured the success rate of the actual returned solutions as well.

Online search evaluation. We added an online search experiment across all 134 ALFWorld tasks. Both methods use the same generator, search setup, and compute budget cap, where the budget accounting includes both scoring and final selection overhead. In the table below, rewards are reported on a 0 to 100 scale and success rates are in percentages.

Online search metricReturn-MSERATEGain
Mean candidate reward72.9577.24+4.29
At least one candidate succeeds (oracle)82.0987.31+5.22
Final selected and returned solution succeeds79.1085.07+5.97

On the final returned solutions, RATE succeeds on 114/134 tasks compared to 106/134 for Return-MSE, an improvement of 5.97 percentage points, with a task-paired bootstrap 95% confidence interval of [0.75, 11.19].

Thank you again for your valuable suggestions and for your time!

Thank you for the clarification and additional results. While they address some of my concerns, I will maintain my original score.

Thank you very much for taking the time to thoroughly review our manuscript and share such thoughtful feedback. We genuinely appreciate the care you put into evaluating our work, and your detailed comments have been invaluable in helping us clarify our arguments and strengthen the paper.

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

The paper’s central contribution appears to be a new modelling objective aimed at improving the performance of particle search, and the improvement seems potentially novel and valuable. As I understand it, the point is that existing approaches to reward-tilted particle search employ ‘pointwise’ critics (learning based on each trajectory independently) and that augmenting the critic loss with a batch-dependent softmax modelling term improves training quality without changing the modelling target.

Critical strengths

The proposed design seems logical, intuitive (training a critic specifically for the allocation decisions it informs), and potentially novel.

Critical weaknesses

First, the paper’s exposition is needlessly confusing. I do not believe the paper’s exposition is clear enough to confidently review this paper, and as such, on that alone, I recommend rejection.

There seems to be a large mismatch between the complexity of the idea and contribution (which appear relatively simple) and the complexity of exposition (which I found complex). For example, the paper dedicates a paragraph to the simple observation that the expectation of an exponential of a random variable does not, in general, equal the exponential of an expectation of that variable. This is a trivial observation—at the level of high school probability theory, but the associated exposition (lines 130-134) is bizarre (including an irrelevant reference to Jensen's inequality) and seems a potential AI artifact.

The idea itself is also poorly explained. The fundamental contribution appears to be a modelling objective, as written in lines 35-36: “our focus is how to train the critic for the allocation decisions its scores induce,” and yet the paper presents RATE as a “framework” and it is not clear to me what the authors mean by that word, or how they situate their contribution. This is one of many strange and misleading exposition choices, such as describing a softmax distribution modelling target as being a ‘soft reference’ (line 107) which is the kind of non-standard and actively un-informative figurative language that AI often employs.

Second, the paper's emphasis on its baselines seems inappropriate to the contribution it claims, with the headline comparison to Best-of-N (BoN) search actively misleading. The paper’s contribution is not the idea of particle search, which is, as they reference, an established field. Rather, the paper’s contribution is instead, a new modelling objective that can be used as part of particle search. Looking at the paired-task bootstrap intervals in Figure 3, RATE’s reward gain compared to the particle search controls of MSE, CGF, and Norm-CE each includes zero on three of the four environments. This comparison is central to their paper, yet the authors' own statistical analysis fails to establish statistically significant improvements in three of the four environments. In this context, the abstract emphasising the improvement over BoN seems misleading and irrelevant to the claims of the paper (that RATE’s modelling objective improves particle search). This claim evidence mismatch is incompatible with good scientific communication, and as such, I view this as a second major barrier to publication.

In my view, while the ideas may have potential merit, the paper requires such substantial revision that it should be completely rewritten and resubmitted to a future conference.

Questions for authors

What do you mean by the use of the word framework? Does RATE do more than change the critic loss?

Could you elaborate on the extent of AI assistance? The AI-use statement indicates that AI tools assisted with writing, developing and checking mathematical derivations. Was the resulting exposition critically reviewed for mathematical clarity, relevance, and coherence?

Comments on the paper

2 comments

You do not seem to be reading or engaging with my points. For example, my point regarding the paper inclusion of Jensen’s inequality was that it is not required (and is in fact tellingly inappropriately) for supporting the claim that, for a general random variable XX, E(eX)E(e^X) is not necessarily equal to eE(X)e^{E(X)}. I also directly asked whether the human authors had reviewed and understood the (ir)relevance of the inequality and for elaboration on the use of AI.

I have received no clarification, instead I have received the same irrelevant statement reasserted.

Finally, I will also note that the entirety of your response appears to be AI generated.

In the above context, I feel my current score of strong reject is entirely appropriate.

We cite Jensen's inequality to prove that exponentiating the conditional mean return yields a lower bound on the expected weight (Appendix A.1). This rebuttal was completed manually, and then polished with AI. In the rebuttal, we present the source of our motivation, particularly the inspiration from GRPO that only the authors know, and our logical flow. Regarding the use of AI in the paper, generally speaking, please refer to our AI Use Statement. It was mainly for language polishing or elaboration. Thank you.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.