acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

Test-time scaling improves the performance of large language model agents by allocating additional computation during inference. However, independent best-of- 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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Test-time Scaling, LLM Agents, Reward Modeling, Tree Search

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_7F83OpenReview ↗
Rating
3(+1)
Confidence
2(−1)
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes SPAR for agent test-time scaling: starting from multiple independent trajectories, periodically ranking unfinished prefixes using a reward model (StarRM), branching (forking) new execution states from high-scoring prefixes, pruning branches that rank last in two consecutive evaluations, and finally selecting the answer via reward-weighted voting, with early stopping when multiple roots converge. StarRM is trained with confidence-weighted pairwise ranking based on MC-estimated continuation success rates, alongside a listwise objective.

Critical strengths
  1. Significant token savings, based on experimental data.
  2. A single 9B reward model is used for both intermediate pruning and final selection, making deployment relatively straightforward.
Critical weaknesses
  1. The method is mostly a combination of known ideas. Using a learned scorer to decide which partial attempts to continue, labeling partial attempts by how often their continuations succeed, voting over final answers, and stopping early when answers agree have all been done before. The paper puts these pieces together, but I could not find a new idea that goes beyond this combination.

2.It is not clear that the reward model is what makes the search work. The paper’s own results show that the reward model can barely tell good partial attempts from bad ones early in a run, and this is exactly when the method decides which branches to grow or stop. So the token savings may come from simpler things: stopping some branches, stopping early when answers agree, and reusing shared prefixes. The paper does not test this. A simple check would be to replace the reward model with random scores and see how much of the savings remain.

  1. The gains look larger than they are. Compared with best-of-16, accuracy goes up by only a few problems on each benchmark, with no variance reported. The final answer is also chosen by a different rule from the best-of-16 baseline, so part of the gain may come from that rule rather than from the search. On cost, the paper counts only the tokens generated by the agent. It leaves out the cost of running the reward model on every active branch and of copying the environment for each new branch. The results support “similar accuracy with fewer generated tokens,” not “better and cheaper.”
Questions for authors
  1. How much of the gain comes from the reward model? If the reward model is replaced with random scores for branching and pruning, while early stopping and prefix reuse are kept, how much of the token savings and accuracy remain?

  2. What are the real accuracy and cost gains? Can you report accuracy over several runs with variance, with best-of-16 using the same grouped voting rule as SPAR?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 7F83 (1/2)

We thank the reviewer for recognizing SPAR's token savings and the value of a unified reward model. We further clarify SPAR's technical contributions, reward-guided allocation, and efficiency benefits.

Response to Weakness 1

Thank you for this comment. Foundational techniques such as reward scoring, rollout-based supervision, and answer aggregation have been explored in prior work. However, SPAR's novelty lies in a new adaptive search algorithm for long-horizon agents and a unified reward model supporting its decisions, rather than in these foundational techniques.

1. Novel adaptive allocation across active agent trajectories. Existing methods operate differently: SWE-Replay reuses archived trajectories through heuristic branching, MCTS performs tree search, and AgentRM and QLASS guide step-level decisions. In contrast, SPAR dynamically reallocates computation across concurrently running trajectories. It compares unfinished trajectories, forks promising prefixes while inheriting their execution states, and releases resources from persistently weak branches. This enables exploration without regenerating or re-executing shared prefixes. To our knowledge, this combination of online cross-trajectory allocation, execution-state reuse, and reward-guided pruning has not been explored for long-horizon agents.

2. A lightweight, unified reward model supporting different search decisions. StarRM jointly evaluates trajectory prefixes, executed actions, and completed trajectories using a single compact 9B model. Its training combines confidence-weighted pairwise comparisons from continuation outcomes with listwise supervision over completed solutions (Section 3.4), enabling unified guidance for intermediate allocation and final selection. StarRM scores directly from next-token logits without autoregressive evaluation, avoiding costly LLM-as-a-judge API calls. It requires less than 20GB of GPU memory, making frequent evaluations practical. StarRM-9B achieves 72.3% average selection accuracy across five SWE generation models, outperforming larger domain-specific reward models (up to 32B, 69.8%) and evaluated LLM judges (up to 71.4%), while generalizing to unseen benchmarks (Table 3).

3. Empirical evidence beyond combining existing components. Our controlled ablations isolate the algorithm's contribution. With the same policy, reward model, and final-selection procedure, replacing reward-guided allocation with random allocation reduces accuracy by 2.4 points on MATH-500 and 3.2 points on SWE-bench Verified, despite comparable token consumption. SPAR also matches MCTS's 71.2% SWE accuracy with approximately 50% fewer generated tokens, demonstrating an advantage over existing search strategies.

We therefore respectfully disagree that the contribution is merely an assembly of established techniques. SPAR introduces a distinct approach to allocating and reusing computation during agent execution, while StarRM provides unified supervision and scoring for its search decisions.

Response to Weakness 2 and Question 1

Thank you for this valuable suggestion. We agree that isolating reward-guided allocation from prefix reuse and early stopping is important. We have conducted the proposed controlled experiment, replacing StarRM's intermediate scores with random scores for branching and pruning, while keeping the rollout policy, prefix reuse, early stopping, and StarRM-based final selection unchanged.

1. Random-score ablation.

MethodMATH Acc. (%)TokensSavingsSWE-bench Acc. (%)TokensSavings
SPAR87.219.1K32%71.2116K46%
SPAR with random scores84.821.1K25%68.0118K46%
BoN@16 (matched selection)86.428.2K—70.2217K—

The results highlight two complementary contributions: prefix reuse and early stopping provide token efficiency, while reward-guided allocation improves search quality. Random allocation retains substantial token savings (25% on MATH-500 and 46% on SWE), but reduces accuracy by 2.4 and 3.2 points, respectively, falling below BoN@16 on both benchmarks. In contrast, StarRM-guided SPAR achieves higher accuracy with fewer tokens, demonstrating that the reward model is essential for effectively allocating computation rather than merely reducing generation cost.

2. Robustness to noisy early scores. We acknowledge that Figure 3 shows weak prefix ranking early in SWE trajectories. SPAR is explicitly designed to avoid relying on a single uncertain prediction: branches are pruned only after ranking last at two consecutive checkpoints, while branching occurs in small batches so subsequent rankings can guide allocation. As more execution evidence becomes available, reward estimates become more informative. The controlled ablation demonstrates that this guidance provides meaningful benefits despite imperfect early scores.

AuthorsOpenReview ↗

Response to Reviewer 7F83 (2/2)

Response to Weakness 3 and Question 2

Thank you for these important questions. We would like to emphasize that SPAR consistently achieves higher accuracy than BoN@16 while substantially reducing inference computation. To further strengthen this finding, we conducted additional evaluations across multiple runs with matched final selection and profiled computational costs beyond completion tokens.

1. Matched selection and repeated-run accuracy. Both SPAR and BoN@16 use the same StarRM-9B reward model. While the original BoN baseline selects the highest-scoring trajectory, SPAR uses reward-weighted group selection. To isolate the contribution of the search strategy, we additionally evaluate BoN@16 using the same grouped selection rule as SPAR. We conduct three runs and compute 95% paired bootstrap confidence intervals over problems.

BenchmarkSPAR (%)BoN@16 (%)Paired difference [95% CI]Token reduction
MATH-50087.2 ± 0.086.2 ± 0.4+1.0 [0.0, +2.0]32%
SWE-bench Verified71.6 ± 0.670.2 ± 0.6+1.4 [−0.6, +3.2]46%

Accuracy is reported as mean ± standard deviation across three runs; differences and confidence intervals are in percentage points.

SPAR outperforms BoN@16 in all three runs on both benchmarks, even under identical final-selection rules. On MATH-500, SPAR consistently solves 436 of 500 problems across all three runs. While the confidence intervals quantify uncertainty in the accuracy differences, the results demonstrate a favorable accuracy–efficiency tradeoff: SPAR achieves consistently higher observed accuracy while reducing completion tokens by approximately 32% on MATH-500 and 46% on SWE.

2. Computational cost beyond completion tokens. To establish that SPAR's efficiency extends beyond generated tokens, we additionally profile policy input tokens, tool executions, generation time, reward-model inference, and environment-state reuse at the Figure 2 operating points.

On SWE-bench Verified, SPAR reduces policy input tokens by 45% (11.7M to 6.4M), output tokens by 46% (217K to 116K), and tool executions by 54% (754 to 350). Summed policy generation time decreases from 43 to 20 minutes. SPAR performs 34 reward-model evaluations per task versus 16 for BoN@16, requiring only 20.5s versus 10s of scoring time. Environment snapshots and forks add just 37s per task, without re-executing previous commands.

On MATH-500, policy input tokens decrease by 14%, and summed policy generation time decreases by 62% (493s to 188s). Reward-model scoring requires only 4s per task, while branching incurs negligible history-copying overhead.

Importantly, StarRM-9B produces scores directly from next-token logits without autoregressive evaluation, keeping reward-model overhead small relative to policy generation. These measurements demonstrate substantial savings across multiple computational dimensions, not merely completion tokens, while the additional scoring and state-reuse costs remain limited.

Overall, the additional evidence strengthens our central conclusion: SPAR achieves higher observed accuracy with substantially lower inference computation, even after controlling for final-selection differences and accounting for reward-model and environment-reuse overhead. The repeated-run results support the robustness of this accuracy–efficiency advantage, and the detailed cost profiling demonstrates that SPAR's benefits extend well beyond token-count reductions. We will incorporate these results into the revised paper.

AuthorsOpenReview ↗

Follow-up to Reviewer 7F83

Dear Reviewer,

We would like to kindly follow up on our rebuttal. We have carefully clarified SPAR's technical contributions and conducted additional experiments addressing your concerns, including random-score ablations, matched-selection comparisons, repeated-run evaluations, and detailed computational cost analyses. We believe these results provide stronger evidence for the effectiveness of reward-guided allocation and SPAR's efficiency benefits.

We would greatly appreciate it if you could revisit our responses and reconsider your assessment in light of this additional evidence. We would also be happy to clarify any remaining questions.

Thank you again for your time and consideration!

thanks for your additional experiments, it address my concerns about cost and the role of the reward model. But the token saving seems to come from pruning and early stopping, the novelty problem remains. I will raise my score.

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

The paper introduces SPAR, a test-time search framework for tool-using agents. A learned reward model periodically ranks active prefixes, guides branching and pruning, and selects the final output. Branches inherit the executed prefix and environment state. The reward model, StarRM, combines confidence-weighted pairwise training on terminal outcomes and rollout-estimated intermediate values with listwise training on completed trajectories. On SWE-bench Verified, MATH-500, and AIME 2024, SPAR reports higher accuracy than BoN@16 with 46.3%, 32.5%, and 58.4% fewer policy completion tokens, respectively. Separate experiments assess reward-model selection and transfer across generators and tasks.

Critical strengths
  1. The framework addresses a consequential source of waste in agent inference. Reusing an executed prefix while reallocating computation before attempts finish is a sensible design for long-horizon tasks. Figure 2 reports a useful tradeoff: on SWE-bench Verified, accuracy increases from 70.2% to 71.2% while policy completion tokens decrease by 46.3%. Comparisons with SWE-Replay and MCTS make the evaluation more informative than a comparison with independent sampling alone.

  2. The reward-model evaluation controls candidate availability and tests transfer. Evaluators score the same 16-trajectory pools. Across five SWE generators, StarRM-9B achieves 72.3% average selection accuracy versus 69.8% for OpenHands-32B (Table 1). This is meaningful evidence that a relatively small evaluator can support final selection beyond its training generator, although it does not by itself establish the value of intermediate search guidance.

Critical weaknesses
  1. The cost metric leaves the practical efficiency claim under-supported. Section 4.1 measures policy completion tokens, including pruned branches, but does not quantify reward-model inference, policy prefill, environment cloning, or tool execution. Avoiding evaluator decoding is helpful, but repeated forward passes over long histories still cost computation; math prefixes are evaluated every turn. Consequently, Figure 2 establishes savings in policy generation, while the end-to-end compute and latency advantage remains unclear. This matters because inexpensive intermediate guidance is a central motivation for SPAR.

  2. The experiments do not isolate the proposed mechanisms. There are no ablations separating reward-guided allocation from prefix reuse, pruning, agreement-based stopping, and group-based final selection, nor ablations of confidence weighting and listwise training. It is also unclear whether search baselines share the same evaluator and final-selection rule. This leaves open how much benefit comes from the proposed allocation and training choices. The issue is particularly relevant on SWE: prefix AUC is 0.495 at 25% progress in Figure 3, so effective guidance at the actual branching checkpoints needs stronger evidence. The small accuracy improvements also lack uncertainty estimates in the main TTS comparison; the 3.3-point AIME gain amounts to one additional solved problem on a 30-question evaluation.

Questions for authors
  1. Clarification and supporting measurement: What are the end-to-end latency and resource costs at the Figure 2 operating points, including reward scoring, policy prefill, environment-state cloning, and tools? How many reward evaluations are made per task? These measurements would determine whether the policy-token savings translate into practical efficiency.

  2. Assessment-changing controlled experiments: With the evaluator and final-selection rule fixed, how does SPAR compare with prefix reuse plus unguided allocation, and with agreement-based early stopping disabled? For StarRM, does removing confidence weighting or the listwise term materially change search performance? A small set of matched controls would help establish the contribution beyond reuse and selection.

  3. Clarification of selection: Does the implemented SWE grouping rule merge patches that touch the same lines but contain different edits? If so, how often does this trigger early stopping? Equation (2) also counts every descendant, while only the stopping threshold counts distinct roots. How sensitive are results to correlated descendants dominating group support?

  4. Clarification of reproducibility: Please specify R for each reported SPAR point, continuation counts used for intermediate supervision, and whether baselines use StarRM and the same selection procedure. How are histories exceeding the 8,192-token reward-model limit represented, and how is execution state copied without replaying the prefix?

  5. Clarification of reported results: What explains the GPT-5.4 BoN@16 difference between Table 1 (72.0%) and Figure 4 (54.4%)? Please identify any differences in task subsets, agent configuration, or selection. Repeated-run results or paired uncertainty estimates for the main TTS accuracy differences would also help assess whether the small gains are stable; Figure 3's AUC intervals do not answer that question.

5 comments
AuthorsOpenReview ↗

Response to Reviewer 1ZAc (1/3)

We thank the reviewer for recognizing the practical importance of reducing redundant computation in long-horizon agent inference and the effectiveness of StarRM across different generation models. We appreciate the detailed feedback and would like to clarify several aspects of SPAR that we believe address the reviewer's concerns. We also provide additional controlled experiments and implementation details to further substantiate our contributions.

Response to Weakness 1 and Question 1

Thank you for this valuable suggestion. To address this concern, we have conducted additional cost profiling at the Figure 2 operating points, covering policy input/output tokens, generation time, tool executions, reward-model evaluations, and environment-state cloning. The results demonstrate that SPAR's efficiency gains extend beyond completion-token savings, while the additional reward-model and state-reuse overhead remains modest.

Metric (per task)SWE: SPARSWE: BoN@16MATH: SPARMATH: BoN@16
Policy input tokens6.4M11.7M88K102K
Policy output tokens116K217K19.1K28.2K
Policy turns / tool executions3507544168
Policy generation time20 min43 min188s493s
Reward-model evaluations34164816
Reward-model scoring time20.5s10s4s1s
Environment-state cloning37s—Negligible—

1. Policy prefill and tool executions. SPAR reuses trajectory prefixes and execution states, reducing redundant computation and environment interactions. On SWE-bench Verified, policy input tokens decrease by 45% and tool executions by 54%; on MATH-500, the corresponding reductions are 14% and 40%.

2. Reward-model overhead. StarRM-9B requires less than 20GB of GPU memory in our serving setup and produces scalar scores directly from next-token logits, without autoregressive evaluator decoding. We explicitly measure its overhead: SPAR performs 34 reward evaluations per task on SWE (20.5s) and 48 on MATH (4s). Even with more frequent prefix scoring, the additional reward-model computation is small compared with policy generation time (20 minutes on SWE and 188s on MATH).

3. Environment-state cloning and scheduling. On SWE, forked branches inherit their parent's execution state through filesystem snapshots, avoiding the re-execution of previous commands. All snapshots and forks together take only 37 seconds per task. On MATH, each Python execution is self-contained, so branching only copies conversation history, with negligible overhead. Branch scheduling involves ranking at most 12 active prefixes per checkpoint, requiring minimal bookkeeping.

4. Generation time and practical efficiency. Summed policy generation time decreases by 53% on SWE-bench Verified and 62% on MATH-500. Since branches can execute concurrently, these measurements quantify aggregate policy generation time rather than end-to-end wall-clock latency. Nevertheless, the substantial reductions in policy prefill, generation time, and tool executions, together with the explicitly measured reward-model and cloning overhead, demonstrate that SPAR's efficiency improvements extend well beyond policy completion tokens.

We will incorporate these additional cost measurements and clarify the computational accounting in the revised paper.

AuthorsOpenReview ↗

Response to Reviewer 1ZAc (2/3)

Response to Weakness 2 and Question 2

Thank you for these constructive suggestions. Figure 2 already compares search strategies under the same rollout policy and decoding settings, using the same StarRM-9B checkpoint for reward-guided scoring where applicable. Each baseline retains its original search and selection mechanism. To further isolate the contributions of individual components, we have conducted additional controlled ablations, keeping the generation policy and evaluation settings fixed.

1. Search component ablations.

MethodMATH-500 Acc. (%)TokensSWE-bench Verified Acc. (%)Tokens
SPAR87.219.1K71.2116K
Prefix reuse + random allocation84.821.1K68.0118K
Without pruning85.420.4K69.0129K
Without agreement-based early stopping86.422.3K70.4143K
BoN@16 (matched scorer and selection)86.428.2K70.2217K

2. Reward-model training objective ablations.

Training objectiveMATH-500 Search Acc. (%)SWE-bench Verified Search Acc. (%)
Full objective (SPAR)87.271.2
Without listwise loss86.469.6
Without confidence weighting85.670.4

Reward-guided allocation and prefix quality. Replacing StarRM's scores with random scores reduces accuracy by 2.4 points on MATH-500 and 3.2 points on SWE, showing that prefix reuse alone is insufficient. For Figure 3's low early-stage prefix AUC, SPAR mitigates unreliable scores by pruning after two consecutive lowest-ranked checkpoints and expanding branches in small batches. The random-allocation ablation confirms the effectiveness of learned guidance despite noisy early predictions.

Pruning and early stopping. Disabling pruning reduces accuracy by 1.8 points on MATH-500 and 2.2 points on SWE. Agreement-based early stopping reduces completion tokens by about 14% on MATH-500 and 19% on SWE, while improving accuracy by 0.8 points on both benchmarks. On MATH-500, it triggers on approximately 47% of tasks.

Final selection and training objectives. BoN@16 and SPAR use the same StarRM evaluator, but the original BoN baseline uses maximum-reward selection. Applying SPAR's grouped selection rule to BoN@16 leaves SPAR ahead in accuracy and efficiency, confirming that its advantage is not solely attributable to final selection. Removing either the listwise loss or confidence weighting reduces search accuracy on both benchmarks, supporting the contribution of StarRM's training objectives.

Uncertainty and robustness. Across three runs, paired bootstrap comparisons show improvements of +1.0 point [0.0, +2.0] on MATH-500 and +1.4 points [−0.6, +3.2] on SWE, with about 32% and 46% fewer completion tokens. SPAR performs better in every run, although the intervals reflect uncertainty in the small gains. We acknowledge that AIME 2024's 3.3-point improvement corresponds to one problem; our primary conclusions rest on the larger MATH-500 and SWE evaluations.

Overall, these controlled results demonstrate that SPAR's benefits extend beyond prefix reuse and final selection alone, with reward-guided allocation, pruning, early stopping, and StarRM's training objectives contributing to effective and efficient search. We will include these ablations in the revision.

Response to Question 3

As described in Section 3.3, completed trajectories are grouped using a task-specific matching rule. In our SWE implementation, patches are grouped based on their per-file added and removed line contents, excluding diff headers and unchanged context. Patches that touch the same files or locations but make different edits are not merged. We will clarify this matching criterion in Section 3.3 to avoid ambiguity. Grouping alone does not trigger early stopping. SPAR requires all completed trajectories to belong to the same output group, with agreement spanning at least max⁡(2,⌈R/2⌉)\max(2,\lceil R/2\rceil) distinct initial roots. Descendants sharing a root count only once toward this threshold. Therefore, different edits cannot produce false agreement through grouping, and multiple correlated descendants from a single root cannot independently trigger early stopping. Moreover, identical patches are relatively uncommon on SWE: in our evaluated 16-candidate pools, the largest matching group contains only 1.5 trajectories on average.

Eq. (2) aggregates reward-weighted support rather than independent votes. Since SPAR deliberately allocates more computation to promising prefixes, allowing their descendants to contribute according to their reward scores is consistent with adaptive search. Moreover, the limited overlap among SWE patches reduces the influence of correlated descendants on final selection. Thus, the two criteria serve complementary purposes: final selection utilizes reward-weighted evidence from completed candidates, while early stopping requires agreement across distinct roots.

AuthorsOpenReview ↗

Response to Reviewer 1ZAc (3/3)

Response to Question 4

Thank you for these questions. For the starred points in Figure 2 (N=16N=16), we use R=6R=6 initial trajectories across all evaluation tasks, with at most L=12L=12 concurrent branches. We will also report the corresponding RR and NN values for the remaining budget points.

For intermediate supervision, we use 32 sampled continuations per mathematical candidate and 12 per SWE candidate, given the higher computational cost of SWE tasks. Their success counts are used to estimate continuation values and confidence-weighted preferences in Eqs. (6)–(8).

All methods use the same rollout policy and decoding settings, with the same StarRM-9B checkpoint for reward-based evaluation where applicable. Baselines retain their respective selection procedures. We additionally evaluate BoN@16 using SPAR's grouped selection rule to control for this difference, as described in our response to Weakness 2.

For histories exceeding the 8,192-token limit, we retain the task description, recent interaction history, and final answer or patch, where applicable. If further truncation is necessary, we preserve both the beginning and end of the input.

For execution-state reuse, SWE branches inherit their parent's filesystem snapshot and conversation history without re-executing previous commands. On mathematics tasks, Python calls are self-contained, so branching only requires copying the conversation history, with negligible overhead. We will include these details to improve reproducibility and clarify the fairness of our comparisons.

Response to Question 5

Thank you for pointing this out. We would like to clarify that the difference arises from the evaluation task subsets, rather than differences in the agent configuration or selection procedure.

Table 1 evaluates StarRM's BoN@16 selection accuracy on the full 500-task SWE-bench Verified benchmark, generating 16 independent GPT-5.4 trajectories per task and achieving 72.0% accuracy. In contrast, Figure 4 evaluates online test-time search on a difficulty-stratified subset, emphasizing tasks with mixed successful and unsuccessful attempts, where adaptive search has greater opportunity to improve the outcome. On this more challenging subset, the same GPT-5.4 agent and BoN@16 selection procedure achieve 54.4% accuracy. Therefore, the difference reflects the task distribution rather than an inconsistency in the evaluation. We will explicitly clarify the subset selection in Figure 4 and Section 5.3.

Regarding robustness, we additionally conducted three runs with paired bootstrap confidence intervals for the main TTS comparisons:

BenchmarkSPAR (%)BoN@16 (%)Paired difference [95% CI]Token reduction
MATH-50087.2 ± 0.086.2 ± 0.4+1.0 [0.0, +2.0]32%
SWE-bench Verified71.6 ± 0.670.2 ± 0.6+1.4 [−0.6, +3.2]46%

Accuracy is reported as mean ± standard deviation across three runs; differences and confidence intervals are in percentage points.

SPAR achieves higher accuracy than BoN@16 in all three runs on both benchmarks, while consistently reducing completion tokens by approximately 32% and 46%, respectively. Although the confidence intervals reflect uncertainty in the small absolute accuracy differences, these results reinforce our primary finding: SPAR maintains competitive or higher accuracy with substantially lower inference-generation cost.

Reviewer_r7tUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces SPAR, a test-time scaling framework that reuses trajectory prefixes and execution states, and uses reward scores to guide branching, pruning, and final solution selection. The authors also train StarRM to support both intermediate search decisions and final selection. Experiments on software engineering and mathematical reasoning benchmarks show competitive accuracy with fewer policy-generated completion tokens.

Critical strengths

The paper addresses a practically relevant problem with clear motivation. For long-horizon tasks involving tool use and environment interaction, independent best-of-N sampling can repeat similar exploration and continue spending computation on unsuccessful trajectories. Reusing existing progress, adapting computation allocation, and reliably selecting final solutions are therefore worthwhile research directions. The method offers some novel elements within a coherent design. SPAR combines prefix reuse, intermediate scoring, branching and pruning under a concurrency limit, and final solution selection. Pruning only after two consecutive lowest-ranked checkpoints, expanding in small batches, and requiring agreement across distinct initial roots for early stopping reflect consideration of scoring noise and search diversity. StarRM’s training objectives are also aligned with its roles in search and selection. The empirical results are valuable. The evaluation covers both software engineering and mathematical reasoning benchmarks and includes several search methods and reward models. The reported reductions in generated completion tokens are substantial. Although some accuracy gains are modest, maintaining comparable accuracy while substantially reducing completion tokens remains practically useful.

Critical weaknesses

Critical Weaknesses Comparisons across inference budgets are limited. Figure 2 includes MCTS, DVTS, CSO, beam search, and SWE-Replay, and the reported results support SPAR’s advantages over the evaluated configurations. However, the budget-scaling analysis focuses primarily on SPAR and BoN, while the other search methods are generally represented by a single point. Adding a few budget points for the most relevant or competitive baselines, along with details of configuration selection, would make the comparison more convincing. The cost evaluation is incomplete. Section 4.1 and Figure 2 primarily measure cost using policy-generated completion tokens, which is a reasonable measure of generation effort. However, SPAR also incurs costs from StarRM evaluations, input-context processing, execution-state reuse, and branch scheduling. These costs are not quantified in the main efficiency evaluation. Related work such as SWE-Replay reports both average input and output token usage. Reporting additional measures, such as input token consumption and end-to-end runtime, with a clear accounting of reward-model overhead, would strengthen the efficiency claims. The contribution of individual components remains unclear. The method introduces several interacting components, but the current analyses mainly examine reward-model size, prefix-ranking quality, and cross-task generalization. They do not isolate the contributions of the search strategy, reward-model training objectives, grouped final selection, and early stopping. A small set of targeted, controlled ablations would help establish which design choices account for the observed gains.

Questions for authors

In Section 3.3, early stopping counts distinct initial roots, while the group support in Eq. (2) sums contributions from all completed trajectories, including descendants sharing a prefix. How does this aggregation account for the dependence among such trajectories and the unequal allocation of branches across roots? Could the authors clarify the rationale? In Figure 2, most search baselines are represented by a single point. Is this due to the expense of running additional experiments, difficulty controlling their computational budgets, or limitations in adapting them to the evaluated tasks? Please clarify how these configurations were selected. The accuracy improvements over BoN@16 on MATH-500 and SWE-bench Verified are 0.6 and 1.0 percentage points, respectively. These results remain valuable given the substantial savings in completion tokens. Could the authors nevertheless provide results across repeated runs or confidence intervals, preferably for the paired accuracy differences, to assess the robustness of these gains?

4 comments
AuthorsOpenReview ↗

Response to Reviewer r7tU (1/3)

We thank the reviewer for the thoughtful and constructive feedback, and for recognizing the practical significance of SPAR's token savings, its consideration of reward uncertainty, and the effectiveness of the unified reward model. We appreciate the opportunity to further clarify the experimental design and provide additional evidence supporting the proposed framework.

Response to Weakness 1 and Question 2

The single-point comparisons were primarily due to the computational expense of running additional search configurations, rather than limitations in adapting the baselines. Unlike BoN, which samples independent completed trajectories, search methods dynamically allocate computation based on intermediate decisions. Changing their budgets can alter the search process, requiring additional generation runs to evaluate different configurations. Moreover, different methods control computation through different parameters, making nominal trajectory counts less directly comparable. Therefore, as described in Section 4.1, we use actual policy completion tokens, including tokens spent on pruned branches, as a consistent measure of generation cost across methods.

The original Figure 2 reported the best-performing evaluated configuration of each search baseline. Following the reviewer's suggestion, we have added additional budget points for the most competitive baselines, allowing comparisons with SPAR at comparable token budgets.

MATH-500:

MethodAccuracy (%)Tokens/problem
Beam search (8 branches)84.013.4K
DVTS (8 branches)84.413.2K
SPAR (comparable budget)85.814.3K
Beam search (16 branches)87.027.2K
DVTS (16 branches)86.226.3K
MCTS85.228.4K
BoN@1686.628.2K
SPAR87.219.1K

SWE-bench Verified:

MethodAccuracy (%)Tokens/task
SWE-Replay (5 patches)67.677K
CSO68.674K
SPAR (matched budget)70.074K
MCTS (half budget)69.6121K
DVTS (half budget)68.8158K
SWE-Replay (10 patches)68.6142K
MCTS71.2234K
DVTS70.2304K
BoN@1670.2217K
SPAR71.2116K

The additional results further support SPAR's favorable accuracy–cost tradeoff across different budgets. On MATH-500, SPAR outperforms both beam search and DVTS at comparable lower budgets, and achieves higher accuracy at the larger operating points while using approximately 28–30% fewer tokens. On SWE-bench Verified, SPAR achieves higher accuracy than CSO and SWE-Replay at comparable lower budgets, and matches MCTS's 71.2% accuracy with approximately half the generated tokens. Regarding configuration selection, all methods use the same rollout policy and decoding settings, with the same StarRM-9B checkpoint for reward-guided scoring where applicable. Each baseline retains its corresponding search and selection mechanisms.

Response to Weakness 2

Thank you for this suggestion. We would like to clarify that SPAR's efficiency gains extend beyond policy completion tokens. We additionally measured policy input tokens, generation time, tool executions, reward-model inference, and execution-state reuse overhead at the Figure 2 operating points. The results show substantial reductions in policy computation and environment interactions, with relatively small additional overhead from reward scoring and state reuse.

Metric per taskSWE: SPARSWE: BoN@16MATH: SPARMATH: BoN@16
Policy input tokens6.4M11.7M88K102K
Policy output tokens116K217K19.1K28.2K
Policy turns / tool executions3507544168
Policy generation time20 min43 min188s493s
Reward-model scored inputs34164816
Reward-model scoring time20.5s10s4s1s
Execution-state reuse37s—Negligible—

Policy computation and execution savings. On SWE-bench Verified, SPAR reduces policy input/output tokens by 45%/46% and tool executions by 54%. On MATH-500, input tokens decrease by 14% and policy generation time by 62% (493s -> 188s).

Reward-model overhead. StarRM-9B uses <20GB GPU memory and scores directly from next-token logits without generating rationales or LLM-judge API calls. Despite more evaluations than BoN@16, scoring takes only 20.5s versus 20min of policy generation on SWE, and 4s versus 188s on MATH. Independent serving also avoids policy GPU contention.

Execution-state reuse and scheduling. SWE branches reuse execution states via filesystem snapshots, with all snapshots and forks totaling just 37s per task. MATH requires only conversation-history copying, with negligible overhead. Scheduling ranks at most 12 prefixes per checkpoint.

Overall, SPAR substantially reduces policy computation and tool usage with modest additional overhead. We will include this breakdown in the revision.

AuthorsOpenReview ↗

Response to Reviewer r7tU (2/3)

Response to Weakness 3

Thank you for this suggestion. We would like to clarify that the paper already evaluates SPAR's components from complementary perspectives: Figure 2 compares our search strategy against five alternative methods, while Tables 1–4 and Figure 3 analyze reward-model quality, ranking ability, and generalization. To further isolate the contributions of individual components, we have conducted additional controlled ablations, keeping the generation policy, evaluation setting, and final-selection procedure fixed.

1. Search component ablations.

MethodMATH-500 Acc. (%)TokensSWE-bench Verified Acc. (%)Tokens
SPAR87.219.1K71.2116K
Random scores for branching/pruning84.821.1K68.0118K
Without early stopping86.422.3K70.4143K
BoN@16 (matched scorer and selection)86.428.2K70.2217K

2. Reward-model training objective ablations.

Training objectiveMATH-500 Search Acc. (%)SWE-bench Verified Search Acc. (%)
Full objective (SPAR)87.271.2
Without listwise loss86.469.6
Without confidence weighting85.670.4

The results demonstrate that reward-guided allocation is critical beyond prefix reuse alone. Replacing StarRM with random scores reduces accuracy by 2.4 points on MATH-500 and 3.2 points on SWE-bench Verified, despite slightly higher token consumption. Early stopping further improves efficiency, reducing completion tokens by approximately 14% on MATH-500 and 19% on SWE, while also improving accuracy by 0.8 points on both benchmarks. On MATH-500, early stopping triggers on approximately 47% of tasks.

We would like to clarify that BoN@16 and SPAR already use the same StarRM reward model for evaluating completed trajectories. While the original BoN baseline uses maximum-reward selection, SPAR employs reward-weighted group selection. To isolate the effect of final selection, we additionally apply the same grouped selection rule to BoN@16. SPAR continues to achieve higher accuracy with substantially fewer completion tokens, demonstrating that the improvements cannot be attributed solely to the final-selection procedure.

Finally, the reward-model ablations show that both training objectives contribute to search performance. Removing either the listwise loss or confidence weighting consistently reduces accuracy across both benchmarks, supporting the effectiveness of StarRM's unified training objective. We will incorporate these controlled ablations into Section 5 to make the contributions of the individual components more explicit.

Response to Question 1

Thank you for the careful reading. We would like to clarify that the two criteria are intentionally designed for different purposes and are fully consistent with SPAR's adaptive search strategy.

Early stopping terminates further exploration, so we adopt a conservative criterion requiring agreement across distinct initial roots. This prevents multiple correlated descendants from the same root from prematurely triggering termination. Final selection, in contrast, ranks the completed candidates rather than deciding whether to terminate exploration. Since SPAR deliberately allocates more computation to promising prefixes, allowing their descendants to contribute to the final selection is a natural consequence of reward-guided allocation. Eq. (2) aggregates these candidates using their learned reward scores rather than treating all trajectories as equally reliable. Thus, additional continuations contribute according to their estimated quality, while the search itself determines where additional computation is most valuable.

Eq. (2) is designed to aggregate reward-weighted support from the generated candidate pool, rather than estimate statistically independent votes. The different treatments of shared-prefix descendants therefore reflect the distinct objectives of final selection and early stopping, rather than an inconsistency in the method.

AuthorsOpenReview ↗

Response to Reviewer r7tU (3/3)

Response to Question 3

Thank you for this valuable suggestion. To assess the robustness of our results, we conducted additional evaluations across three random seeds and computed 95% paired bootstrap confidence intervals over problems. We use the same StarRM reward model for both methods and additionally apply SPAR's grouped final-selection rule to BoN@16 in this repeated-run comparison, controlling for differences in final selection.

BenchmarkSPAR (%)BoN@16 (%)Paired difference [95% CI]Token reduction
MATH-500 (3 runs)87.2 ± 0.086.2 ± 0.4+1.0 [0.0, +2.0]32%
SWE-bench Verified (3 runs)71.6 ± 0.670.2 ± 0.6+1.4 [−0.6, +3.2]46%

Accuracy is reported as mean ± standard deviation across runs; differences and confidence intervals are in percentage points.

The additional results demonstrate consistent accuracy and substantial efficiency gains across repeated runs. SPAR outperforms BoN@16 in all three runs on both benchmarks. Notably, on MATH-500, SPAR consistently solves 436 of the 500 problems across all three runs. Although the confidence intervals reflect uncertainty in the relatively small accuracy differences, SPAR maintains competitive or higher accuracy while reducing completion-token consumption by approximately 32% on MATH-500 and 46% on SWE-bench Verified. These findings reinforce our main conclusion: SPAR achieves a consistently more favorable accuracy–computation tradeoff, with substantial token savings that persist across different random seeds. We will include the repeated-run results and paired confidence intervals in the revised paper.

AuthorsOpenReview ↗

Follow-up to Reviewer r7tU

Dear Reviewer,

We would like to kindly follow up on our rebuttal. We have carefully addressed your concerns through additional budget-matched comparisons, detailed computational cost analyses, controlled ablations, and repeated-run evaluations. We believe these new results provide stronger empirical support for SPAR's effectiveness and efficiency.

We would greatly appreciate it if you could revisit our responses and reconsider your assessment in light of this additional evidence. We would also be happy to clarify any remaining questions.

Thank you again for your time and consideration!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.