Reward-Guided Tree Search for Efficient Agent Test-Time Scaling

Test-time scaling improves the performance of large language model agents by allocating additional computation during inference. However, independent best-of-$N$ sampling is costly on long-horizon tasks, as each new attempt repeats reasoning and environment interactions that could be shared across trajectories. Recent approaches address this inefficiency through trajectory reuse or intermediate guidance, but reuse based on completed attempts postpones branching until those attempts finish, while costly or unreliable intermediate evaluations can offset computational savings or misdirect search. We introduce SPAR, a reward-guided tree search framework that combines adaptive computation allocation with prefix reuse for efficient agent test-time scaling. During generation, a compact reward model periodically ranks active prefixes, guiding SPAR to branch from promising states and prune persistently low-ranked branches to reallocate available computation. Each new branch inherits its parent's interaction history and execution state, allowing alternative continuations to be explored without regenerating or re-executing their shared prefix. To support these decisions, the reward model is jointly trained with a confidence-weighted pairwise objective for comparing prefixes and candidate actions using sampled continuation success rates, and a listwise objective for selecting completed trajectories using verified outcomes, connecting search and selection within a single framework. Compared with best-of-16 sampling, SPAR achieves higher accuracy with 46.3% fewer generated tokens on SWE-bench Verified and 58.4% fewer on AIME 2024, where accuracy improves by 3.3 percentage points.