- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies search agents under an unknown inference budget: in practice, an agent’s computation may be interrupted at any point, so it should give a correct answer whenever it is stopped while still benefiting from additional search. The paper propose AnySearcher, a single policy trained with the AnyBudget objective. The proposed objective scores answer correctness at multiple interruption points along the trajectory, and the budget is measured as the number of tool calls. They decompose this objective into first-success utility and correctness regression, and use it as the reward in GRPO training. An adaptive weighting shifts the reward toward terminal correctness for queries the policy rarely solves, to reduce noisy training signals. Experiments with Qwen3-4B on four deep-search benchmarks show that AnySearcher achieves better results compared to other baselines.
Critical strengths
- Clear and well-motivated research question. The paper targets a practical gap: in real deployments, an agent’s computation may be interrupted at an unknown point.
- Clear writing and presentation. The paper is easy to follow. Figure 1 illustrates the problem with a concrete example; key quantities are defined right before they are used, with intuitive illustrations (Fig. 2); and the experiments follow the structure of the method.
- Sensible and simple method. The AnyBudget objective directly scores correctness at multiple interruption points along the same trajectory, so a single policy can be trained without conditioning on a known budget. Decomposing it into first-success utility and correctness regression gives an intuitive reading too.
Critical weaknesses
-
Evaluation protocols favor the proposed method. The AUC metric is essentially the AnyBudget training objective with uniform weights, so AnySearcher is optimized directly for the evaluation metric while the baselines are not. The interruption checkpoints and weights used in training are also not reported.
-
Limited insight into when early success and correctness regression occur. The paper is motivated by two behaviors: (a) the agent often has enough evidence to answer early, and (b) continued search can overturn a correct answer. However, it never analyzes in which cases these happen, e.g., kind of misleading evidence, and provides no case studies of negative flips.
-
The core objective closely follows AnytimeReasoner (Qi et al., NeurIPS 2025), which already truncates reasoning at budgets sampled from a prior and optimizes the expected reward over budgets. AnySearcher mainly transfers this idea from token budgets to tool-call budgets. The paper cites this work only briefly and neither discusses the differences nor compares against an adapted version.
-
Limited scope of the empirical evidence. All results use a single model (Qwen3-4B). Results on additional models (e.g., different sizes or model families) would strengthen the claim that the method benefits anytime search.
Questions for authors
-
Baselines for the anytime setting. Most baselines assume the budget is known in advance. Could the authors compare against any methods designed for interruption at an unknown point?
-
Training checkpoints. Which interruption checkpoints and weights are used in training? How sensitive are the results to this choice, and does performance hold when the evaluation budget distribution differs from the training one?
-
Relation to AnytimeReasoner. Beyond the change from token budgets to tool-call budgets, what are the key differences from AnytimeReasoner? Why was a single trajectory-level reward chosen over dense, checkpoint-level credit assignment?
6 comments
Response to Reviewer NEQj (2/2)
Q4:Training checkpoints, sensitivity, and distribution mismatch.
We thank the reviewer for pointing out these missing details. Below, we provide more details on our training and evaluation settings, along with additional results on generalization to unseen budgets and shifts in interruption distributions.
(1) Training checkpoints and weights.
We use 10 training checkpoints: . Based on the first 200 training trajectories, we observed a maximum length of 66 tool calls and a median length of 11 tool calls. we allocate checkpoints more densely at smaller budgets, where most search trajectories are active, and more sparsely at larger budgets to improve sampling efficiency. The training budget prior remains uniform over .
(2) Generalization to unseen budgets.
Our evaluation uses 17 budget checkpoints: . All 17 checkpoints were included in the original Fig. 3, although only 10 were labeled on the x-axis for visual clarity previously. We have now revised Fig. 3 to explicitly label all 17 checkpoints. Notably, 9 of the 16 positive evaluation budgets are unseen during training: , directly evaluating generalization to unseen budgets.
(3) Generalization to shifted interruption distributions.
To assess robustness to distribution mismatch, we evaluate distribution-weighted AUC under three test-time budget distributions over :
p_{\mathrm{small}}(B)=\frac{2(M-B)}{M^2},\quad p_{\mathrm{large}}(B)=\frac{2B}{M^2}.$$ We define weighted AUC as: $$\mathrm{AUC}_{p}@M=\int_0^M \mathrm{Acc}(B)p(B)\,dB.$$ We integrate the piecewise-linear accuracy curves against each distribution. Results for $M=50$ are shown below: | Benchmark | Method | Uniform | Small-budget skew | Large-budget skew | |---|---|---:|---:|---:| | FRAMES | **AnySearcher** | **61.50** | **59.78** | 63.22 | | | GRPO | 60.92 | 57.71 | **64.13** | | BrowseComp-Plus | **AnySearcher** | **23.82** | **22.99** | **24.64** | | | GRPO | 22.35 | 20.11 | 24.59 | AnySearcher achieves particularly large gains under small-budget skew. However, changes in interruption distributions can affect relative performance, as GRPO slightly outperforms AnySearcher under large-budget skew on FRAMES. These results demonstrate generalization beyond the uniform training prior while highlighting the trade-offs associated with distribution mismatch. In practice, aligning the training budget prior with users' expected inference-budget preferences would be preferable for optimizing performance under their deployment conditions. **Q5:Why trajectory-level rewards instead of dense checkpoint-level credit assignment?** Thank you for this thoughtful question. We explored dense checkpoint-level credit assignment during method development. However, intermediate correctness signals in tool-augmented search can be noisy and non-monotonic, making fine-grained credit assignment challenging. In our preliminary experiments, dense rewards did not improve performance over our trajectory-level approach, while introducing additional computational overhead. We therefore favor trajectory-level rewards for their simplicity and efficiency. Nevertheless, developing more effective fine-grained credit assignment for tool-augmented search remains a promising direction, which we plan to explore in future work. **Q6:AUC normalization formula.** Thank you for pointing this out. We compute AUC@5, AUC@10, and AUC@50 by integrating accuracy under a uniform budget distribution: $$\mathrm{AUC}@M=\frac{1}{M}\int_0^M \mathrm{Acc}(B)\,dB, \qquad M\in\{5,10,50\}.$$ The integral is evaluated using the trapezoidal rule over the evaluation checkpoints, accounting for their unequal spacing. **Q7: Generalization across model sizes and families.** We thank the reviewer for the feedback. Agentic RL training requires substantial computational resources and long training cycles. Conducting additional full training runs across different model sizes and families is therefore not feasible within the limited rebuttal period. Our current experiments focus on Qwen3-4B, a model at a commonly used scale in LLM-based search agent research, allowing us to conduct systematic comparisons across multiple baselines under a consistent computational budget. We appreciate the reviewer's understanding of these practical constraints and acknowledge broader cross-model evaluation as an important direction for future work. --- **We hope that our responses and additional results have addressed your concerns. Should you have any further questions or comments, we would be happy to continue the discussion.**Dear authors,
Thanks for the detailed response and the additional work, especially on quantitative and qualitative analysis for early success and correctness regression. And most of my concerns are addressed.
However, I do think training and evaluating on Qwen3-4B only is not enough. I deeply understand that Agentic RL training requires substantial computational resources. But I'd expect that at least one another model should be trained and evaluated on the proposed method and some baselines.
The authors are doing a great job on the rest of the paper, and if the authors could provide the extra result on another model, I would be happy to raise my score.
Response to Reviewer NEQj (1/2)
Thank you for your careful review. We appreciate your valuable feedback. Below, we address each of your comments point by point.
Q1:Evaluation fairness and baselines for unknown interruption budgets. Thank you for pointing this out. We consider AUC to be the most natural choice to capture how well a model performs across arbitrary interruption budgets. Based on this, we evaluate all methods using the same protocol. We also want to clarify that not all our baselines assume a known budget. The Base Model, Standard GRPO, and Length Penalty also do not require budget information in advance. To further extend our comparison, we now additionally evaluate AnyReasoner(BRPO). AnySearcher outperforms BRPO on both FRAMES (AUC@5: 45.89 vs. 39.84, AUC@10: 54.20 vs. 49.76, AUC: 61.50 vs. 58.82) and BrowseComp-Plus (16.30 vs. 13.43, 20.20 vs. 17.53, 23.82 vs. 22.39). This shows that our gains are not limited to comparisons with baselines that assume a known budget.
Q2: Early success and correctness regression: quantitative and qualitative analysis.
We thank the reviewer for this valuable suggestion. While Section 4.2 examines correctness preservation through negative flip rates, we have further extended our analysis in Appendix A.5 and A.6. We provide quantitative results on early success, negative flips, and additional tool calls (Appendix A.7), along with two qualitative examples illustrating why these behaviors occur (Appendix A.8).
Q3: Relationship to AnytimeReasoner and methodological novelty.
We thank the reviewer for highlighting this connection. We agree that AnytimeReasoner and AnySearcher share the general idea of an any-time objective, which is commonly used in the broader setting of budget-aware reasoning. However, the two methods differ in several important aspects. Below, we first provide a direct empirical comparison, and then followed by an explanation of the key differences in methodology and policy optimization.
Empirical comparison. We adapted BRPO (AnytimeReasoner) to the tool-augmented search setting and evaluated it under the same conditions as AnySearcher. As shown below, AnySearcher consistently outperforms BRPO on both FRAMES and BrowseComp-Plus, with particularly large improvements at smaller inference budgets (AUC@5,10).
Beyond the empirical results, we further clarify how the two approaches differ in both methodology and policy optimization.
Methodological differences. AnytimeReasoner uses rewards from multiple interruption budgets to estimate token-level advantages, combining historical rewards and group-level baselines to improve credit assignment and reduce gradient variance. AnySearcher instead aggregates intermediate rewards at the trajectory level, characterizes anytime performance through first-success and correctness-regression components, and uses capability-adaptive weighting to balance terminal correctness and anytime rewards according to query solvability.
In addition, the two approaches address different challenges. AnytimeReasoner focuses on improving the stability of gradient estimation, making better use of intermediate rewards. AnySearcher focuses on how much emphasis should be placed on anytime supervision at different levels of model capability. When the model struggles to solve a query, sparse intermediate successes can introduce noisy learning signals. Capability-adaptive weighting therefore prioritizes terminal correctness on difficult queries and gradually increases the emphasis on anytime performance as the model becomes more capable.