- 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
- Significant token savings, based on experimental data.
- A single 9B reward model is used for both intermediate pruning and final selection, making deployment relatively straightforward.
Critical weaknesses
- 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.
- 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
-
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?
-
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
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.
| Benchmark | SPAR (%) | BoN@16 (%) | Paired difference [95% CI] | Token reduction |
|---|---|---|---|---|
| MATH-500 | 87.2 ± 0.0 | 86.2 ± 0.4 | +1.0 [0.0, +2.0] | 32% |
| SWE-bench Verified | 71.6 ± 0.6 | 70.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.
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.
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.
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.