Abstract
Large Language Model (LLM)-based search agents have shown remarkable capabilities in solving complex tasks by dynamically decomposing problems and addressing them through interleaved reasoning and retrieval. However, this interleaved paradigm introduces substantial efficiency bottlenecks. First, we observe that both highly accurate and overly approximate retrieval methods degrade system efficiency: exact search incurs significant retrieval overhead, while coarse retrieval requires additional reasoning steps during generation. Second, we identify inefficiencies in system design, including improper scheduling and frequent retrieval stalls, which lead to cascading latency -- where even minor delays in retrieval amplify end-to-end inference time. To address these challenges, we introduce SearchAgent-X, a high-efficiency inference framework for LLM-based search agents. SearchAgent-X leverages high-recall approximate retrieval and incorporates two key techniques: priority-aware scheduling and non-stall retrieval. Extensive experiments demonstrate that SearchAgent-X consistently outperforms state-of-the-art systems such as vLLM and HNSW-based retrieval across diverse tasks, achieving up to 3.4$\times$ higher throughput and 5$\times$ lower latency, without compromising generation quality.
1. Introduction: The Efficiency Bottlenecks of Search Agents
Traditional Retrieval-Augmented Generation (RAG) follows a linear "retrieve-then-generate" path. However, the field is moving toward Search Agents (RAG 2.0), where LLMs dynamically decide when and what to search for during the reasoning process. While this "interleaved" approach produces higher-quality answers for complex questions, it introduces significant efficiency challenges.
1.1 The Retrieval Accuracy Paradox
A key observation is that system efficiency is degraded by both overly precise and overly coarse retrieval. Exact search is computationally expensive, leading to high retrieval overhead. Conversely, very coarse approximate search results in poor data quality, forcing the LLM to perform more reasoning steps (retrieval counts) to compensate, which also slows down the system.
1.2 Systemic Latency Magnification
Current systems suffer from "cascading" latency, where minor retrieval delays are amplified into substantial end-to-end inference delays. This is primarily due to two systemic inefficiencies:
- Improper Scheduling: Standard First-Come-First-Served (FCFS) scheduling often allows new, short requests to preempt long-running agents waiting for search results. This causes the agent's large Key-Value (KV) cache to be evicted, necessitating expensive recomputations.
- Retrieval Stalls: LLM generation often stalls while waiting for search results that may only offer marginal improvements in quality.
2. SearchAgent-X: Optimizing the Agent-Search Interface
To address these bottlenecks, we propose SearchAgent-X, which introduces two core innovations:
- Priority-Aware Hierarchical Scheduling: SearchAgent-X prioritizes requests that have already undergone multiple retrieval steps. These "long-running" requests typically have the largest KV-caches. By finishing them first, the system maximizes cache reuse and prevents the eviction of valuable data, significantly improving throughput.
- Non-Stall Retrieval (Adaptive Termination): Instead of running searches for a fixed duration, SearchAgent-X monitors search result "maturity" in real-time. If the search reaches a point of diminishing returns and the LLM is ready to generate the next token, the system terminates the search early. This eliminates unproductive waiting periods.
3. Experimental Evaluation
We evaluated SearchAgent-X on six complex reasoning and multi-hop QA datasets, including Musique, NQ, 2WikiMultihopQA, HotpotQA, Bamboogle, and StrategyQA, using a Wikipedia-based knowledge base of ~21 million segments.
3.1 Key Results
- Throughput & Latency: SearchAgent-X achieved 1.3× to 3.4× higher throughput and up to 5× lower latency compared to baselines like vLLM with HNSW-based retrieval.
- Cache Efficiency: The framework improved KV-cache utilization from 0.07 to 0.65 in high-traffic scenarios, drastically reducing redundant computations.
- Quality Preservation: Generation accuracy remained virtually identical to systems using slow, exact retrieval, demonstrating that aggressive optimization does not compromise output quality.
4. Discussion and Future Work
Our findings highlight that for search agents, maximizing retrieval recall is not always optimal; a "sweet spot" exists where high-recall approximate search balances speed and reasoning quality. Furthermore, standard FCFS scheduling is ill-suited for the interleaved nature of search agents.
Future work includes extending SearchAgent-X to support hybrid (sparse and dense) retrieval strategies and optimizing the latency of text encoders. These techniques also hold potential for broader agentic workflows involving tool-use or multi-agent collaboration.
Summary updated