acceptodds
Under review as a conference paper at ICLR 2027

AnySearcher: Learning to Search under Arbitrary Inference Budgets

Abstract

Language model agents increasingly use test-time computation to seek information, interact with tools, and iteratively refine their answers. Yet in real-world settings, an agent rarely operates under a fixed computational endpoint: user patience, latency requirements, tool availability, resource constraints, and task urgency may change while an agent is running. A desirable agent should therefore exhibit an **anytime property**, remaining reliable whenever its computation is interrupted while continuing to benefit from additional computation when it remains available. Existing approaches typically optimize agents for predefined inference budgets or terminal performance, making them less suited to such dynamic conditions. We introduce **AnySearcher**, a single search policy trained with an **AnyBudget objective** that optimizes expected task performance over possible interruption points along the search process. This encourages the agent to be correct at earlier interruption points and remain correct as additional search is performed. Across four challenging search benchmarks, AnySearcher achieves higher accuracy across inference budgets, reaches high performance with fewer tool interactions, and better preserves correctness as additional computation becomes available, demonstrating stronger anytime reliability throughout the process.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Search Agent, Anytime;Budget-aware

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_NEQjOpenReview ↗
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
  1. 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.
  2. 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.
  3. 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
  1. 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 BkB_k and weights wkw_k used in training are also not reported.

  2. 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.

  3. 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.

  4. 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
  1. 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?

  2. Training checkpoints. Which interruption checkpoints BkB_k and weights wkw_k 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?

  3. 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
AuthorsOpenReview ↗

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).

BenchmarkMethodAUC@5AUC@10AUC
FRAMESAnySearcher45.8954.2061.50
AnytimeReasoner (BRPO)39.8449.7658.82
BrowseComp-PlusAnySearcher16.3020.2023.82
AnytimeReasoner (BRPO)13.4317.5322.39

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.

AuthorsOpenReview ↗

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: 1,2,3,5,8,12,18,26,40,66{1,2,3,5,8,12,18,26,40,66}. 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 [0,66][0,66].

(2) Generalization to unseen budgets.

Our evaluation uses 17 budget checkpoints: {0,1,2,3,4,5,6,7,8,10,12,15,20,25,30,40,50}\{0,1,2,3,4,5,6,7,8,10,12,15,20,25,30,40,50\}. 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: {4,6,7,10,15,20,25,30,50}\{4,6,7,10,15,20,25,30,50\}, 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 [0,M][0,M]:

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.

Reviewer_mC1iOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper addresses the critical challenge of deploying Large Language Model (LLM) agents in real-world scenarios where inference budgets are dynamic and unpredictable. The authors introduce AnySearcher, a unified search strategy designed to maintain reliable performance at any interruption point while continuing to improve as computational resources increase. AnySearcher achieves competitive performance on several benchmarks with low cost.

Critical strengths
  1. The formulation of “anytime search” for LLM agents is highly relevant to real-world deployment. User patience, tool latency, and resource constraints are inherently stochastic; optimizing for a single fixed budget is often suboptimal. This work correctly identifies the need for a policy that is robust to arbitrary interruptions.
  2. Authors effectively mitigate the variance issue inherent in group normalization, allowing the model to learn meaningful signals even on hard instances without being overwhelmed by noisy intermediate rewards.
  3. The use of AUC and Budget@90% provides a much richer assessment than single-point accuracy. These metrics directly reflect the “anytime” property, showing not just if the model succeeds, but how efficiently it utilizes the budget to get there.
Critical weaknesses
  1. This paper lacks ablations that isolate the contribution of the two decomposed terms. Specifically, what happens if we train with only first-success utility or only correctness regression? Without this, it is unclear if the performance gain comes from the joint optimization or just one dominant term.
  2. The computational cost of training and inference is under-discussed. A comparison of training FLOPs/hours and inference latency overhead against standard GRPO would be necessary to evaluate the practical trade-offs.
Questions for authors
  1. Authors should add more comparison with new works.
3 comments

Thank you for your detailed feedback and support for our work! we'll answer your questions below:


Q1:Ablation of first-success utility and correctness regression.

Thank you for raising this point. We clarify that first-success utility and correctness regression are not two independently introduced loss functions, but an exact decomposition of the AnyBudget objective we describe in the method section.

Nevertheless we're happy to add a controlled ablations to help establish the empirical contribution of each term beyond this mathematical interpretation. We now ablate the corresponding term from the objective and report the results below. Removing the correctness regression term degrades performance across both benchmarks, with particularly drops at smaller budgets:

BenchmarkMethodAUC@5AUC@10AUC
FRAMESAnySearcher45.8954.2061.50
w/o correctness regression39.7051.1060.30
BrowseComp-PlusAnySearcher16.3020.2023.82
w/o correctness regression6.9812.8421.80

Q2: Training computational cost.

Thank you for your comment. Compare with GRPO, both methods share the same training procedure for the first 200 steps. After step 200, AnySearcher introduces intermediate answer probing, which initially adds about 9% per-step overhead. However, as training progresses, AnySearcher reduces unnecessary tool calls and shortens rollout generation, more than offsetting the probing overhead. Including the shared first 200 steps, the estimated total training time is approximately 0.61× that of standard GRPO, corresponding to a 39% reduction.

Q3:Inference latency and deployment overhead.

Thank you for your feedback. Compared with other baselines, AnySearcher uses the same model without introducing extra deployment or inference costs. When interrupted, the inference engine simply appends <answer> marker to the current context and generates the answer directly, without restarting the reasoning process, making additional tool calls, or recomputing the existing context (assuming KV caching). The only cost is generating a short answer, which other baselines also need to do. If no ineterruption occurs, no extra costs are incurred. Further, AnySearcher can reach correct answers at smaller budgets, enabling correct answers to be obtained earlier and potentially reducing time-to-answer latency.

Q4:Comparisons with recent methods.

Thank you for your suggestion. To strengthen the comparison with recent work, we additionally evaluate BRPO from AnytimeReasoner, which also optimizes performance under unknown interruption budgets. AnySearcher outperforms the adapted BRPO baseline 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)


We hope that our clarifications and additional results help address your concerns. We appreciate the constructive discussion and welcome any further questions or feedback.

Thanks for the authors' reply. My questions are resolved. I consider my score reasonable and will keep my rating unchanged.

Thank you for your time and support!

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

The paper studies the anytime property for tool-augmented search agents: because the available inference budget (number of tool calls) may be unknown when search begins, a user may interrupt, latency limits may change, or tools may become unavailable, a single policy should be correct at every possible interruption point and should preserve a correct answer as more computation becomes available.

Critical strengths
  1. Well-motivated and practically relevant framing. The distinction between budget-aware policies and true anytime policies (budget unknown at start) is clean and under-addressed for tool-using agents. The running examples are realistic for deployed search agents.

  2. The objective is simple and the right one for the setting. Expected correctness over an interruption distribution p(B), with a single unconditioned policy, is the classical anytime-algorithm formulation correctly ported to interactive search.

  3. The capability-adaptive weighting addresses a genuine optimization pathology. The argument that, on low-solvability queries, long trajectories accumulate more chance intermediate successes and therefore AnyBudget rewards inadvertently favor longer rollouts under group normalization (Section 3.3, Figure 5) is a non-obvious and plausible failure mode. Mixing terminal and AnyBudget rewards by the group pass rate p_q is a pragmatic fix.

Critical weaknesses
  1. The core training mechanism closely parallels AnytimeReasoner, which is cited in the references but never discussed in the body. AnytimeReasoner ("Optimizing Anytime Reasoning via Budget Relative Policy Optimization", NeurIPS 2026) already (i) truncates the full thinking process to fit sampled budgets from a prior distribution, (ii) compels the model to produce an answer from each truncated prefix for verification, (iii) inserts dense verifiable rewards over the budget distribution, and (iv) optimizes a single policy across all budgets under that distribution — precisely the AnyBudget procedure of Sections 3.2–3.3, with token budgets in place of tool-call budgets. The paper cites it (reference list) but the Related Work section (Section 2, "Budget Aware Reasoning") does not mention or differentiate it. The contribution must be repositioned: the genuinely new elements appear to be (a) the tool-interaction setting where prefixes end at tool-call boundaries and answers come from interleaved search state, (b) the explicit first-success/regression decomposition, and (c) capability-adaptive weighting. A direct comparison (or at least a clear mechanistic delta, plus discussion of BRPO's variance reduction vs. the p_q weighting) is required; as written, the paper risks being read as an application of a published recipe to search agents.

  2. The interruption/evaluation protocol is under-specified, yet it determines whether the measured "anytime" performance is deployable. The paper never states how the accuracy–budget curve Acc(B) is obtained at evaluation: (a) a fresh rollout hard-capped at B tool calls that must then answer, or (b) one full trajectory whose prefixes are post-hoc prompted for answers. These differ substantially, and neither fully matches a real interruptible deployment, which would require the agent to continuously expose a tentative answer after each tool call (with the token cost of doing so).

  3. I could not find the values of the K checkpoints B_1<…<B_K or the weights w_k used during training (evaluation uses {0,1,2,3,5,8,12,20,30,50}, but training checkpoints are never given). Results under p(B) are only meaningful relative to this distribution, and the central claim is "arbitrary budgets." There is no experiment testing mismatched interruption distributions (e.g., train uniform, test skewed toward small or large B, or test on checkpoints never seen in training), which is the direct test of "arbitrary." The AUC normalization formula (discrete points over [0,5]/[0,10]/[0,50]) is also not given.

Questions for authors

How does AnySearcher perform under a test interruption distribution that differs from training (skewed, or at unseen checkpoints)?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 6ULd (1/2)

Thank you for your careful review and for taking the time to help us improve our work. We've addressed your questions below:

Q1:Comparison with AnytimeReasoner

We thank the reviewer for highlighting this connection. AnytimeReasoner and AnySearcher indeed share the aim of traing for any-time availability, which is central to the broader setting of budget-aware reasoning. We have clarified our existing discussion of this connection in our related work further. 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 have now implemented the BRPO algorithm from AnytimeReasoner in our tool-augmented search setting and have now evaluated it under the same conditions as AnySearcher. We find that, as below, AnySearcher consistently outperforms BRPO on both FRAMES and BrowseComp-Plus, with particularly large improvements at smaller inference budgets (AUC@5,10).

BenchmarkMethodAUC@5AUC@10AUC
FRAMESAnySearcher45.8954.2061.50
AnytimeReasoner (BRPO)39.8449.7658.82
BrowseComp-PlusAnySearcher16.3020.2023.82
AnytimeReasoner (BRPO)13.4317.5322.39

Beyond these 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. Our proposed Capability-adaptive weighting therefore prioritizes terminal correctness on difficult queries and gradually increases the emphasis on anytime performance as the model becomes more capable.

Q2:Interruption and Evaluation Protocol

Thank you for your comment. In brief, in this paper, we use protocol (b) for evaluation. However we do want to clarify that our method fully supports interruptions in real-world deployment (this is the goal after all). At any ReAct checkpoint, the current best answer can be prompted by simply appending an <answer> marker to the existing context, without additional tool calls or a separate reasoning process, generating the answer immediately. AnyBudget training encourages the model to be ready to answer at each checkpoint in this way, without requiring it to generate and store tentative answers along the way. In practice, we only need to reserve a small token budget and generate an answer when an interruption occurs, adding no inference overhead if no interruption happens. We have clarified this in the revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer 6ULd (2/2)

Q3:Budget Distribution and Generalization to Unseen Budgets

We thank the reviewer for pointing out the interest for these additional details. Below, we provide additional 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: 1,2,3,5,8,12,18,26,40,66{1,2,3,5,8,12,18,26,40,66}. 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 [0,66][0,66].

(2) Generalization to unseen budgets.

Our evaluation uses 17 budget checkpoints: {0,1,2,3,4,5,6,7,8,10,12,15,20,25,30,40,50}\{0,1,2,3,4,5,6,7,8,10,12,15,20,25,30,40,50\}. 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: {4,6,7,10,15,20,25,30,50}\{4,6,7,10,15,20,25,30,50\}, 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 [0,M][0,M]:

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.** **Q4: AUC normalization formula.** 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 numerically evaluated using the trapezoidal rule over the evaluation checkpoints, accounting for their unequal spacing. We have included the complete training and evaluation details in the revised manuscript. --- **We hope that our clarifications have addressed your concerns. Please don’t hesitate to reach out with any further questions. We would be happy to discuss further.**

With the discussion period coming to a close, we would appreciate any further feedback. Please let us know whether our responses have sufficiently addressed your concerns. We would be happy to provide additional details or clarifications if needed.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.