AnySearcher: Learning to Search under Arbitrary Inference Budgets

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.