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

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.