Demystifying and Enhancing the Efficiency of Large Language Model Based Search Agents
Authors: Tiannuo Yang
Zebin Yao
Bowen Jin
Lixiao Cui
Yusen Li
Gang Wang
xiaoguang Liu
Willie Neiswanger
Venue: ICLR 2026 Poster (2026)
Keywords: Large Language Models
Reasoning
Agents
System Efficiency
Information Retrieval
Primary area: infrastructure, software libraries, hardware, systems, etc.
TL;DR: This paper demystifies the key factors affecting the efficiency of LLM-based search agents and, based on these insights, designs SearchAgent-X to improve end-to-end efficiency without compromising generation quality.

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-induced 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× higher throughput and 5× lower latency, without compromising generation quality. Code is available at https://github.com/tiannuo-yang/SearchAgent-X.

Published as a conference paper at ICLR 2026
DEMYSTIFYING AND ENHANCING THE EFFICIENCY OF LARGE LANGUAGE MODEL BASED SEARCH AGENTS
Tiannuo Yangh.2, Zebin Yao²; Bowen Jin Lixiao Cui?, Yusen Li,, Gang Wang", Xiaoguang Liu?, Willie Neiswanger'
University of Southern California Nankai University UUniverstyy of Illinois Urbana- Champaann
ABSTRACT
Large Language Model (LLM)-based search agents have shown remarkable ca- pabilities solving complex tasks by dynamically decomposing problems and addressing them through interleaved reasoning and retrieval. However, this in- terleaved paradigm introduces substantial efficiency bottlenecks. First, we ob- serve that both highly accurate and overly approximate retrieval methods de- grade system efficiency: exact search incurs significant retrieval overhead, while coarse retrieval requires additional reasoning steps during generation. Second, we identify inefficiencies system design, including improper scheduling and frequent serrieval-induce 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: X, high-efficiency inference framework for LLM-based search agents. SearchAgent- leverages high-recall approxi- mate retrieval and incorporates two key techniques: priority- prwaret--wware 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.4x higher throughput and 5x lower latency, without compromising generation quality. Code is available https: thub. com www.tiinnooooooo////oo/.oooooooa wtt.c////aaaaaaoaaa/a/aaraaaeeee yang/SeerccAgeett>
INTRODUCTION
Traditional Retrieval-Augnee Augmented Generation (RAG) typically sequential retrieve-thor sheevve--hen-eeee teeengeenertte approach (Fan et al., 2024; Gao et al., 2024; Gupta et al., 2024; Huang & Huang, 2024; Wu et al., 2024; Yu et al., 2024; Zhao al., 2024a;b), which limits dynamic interaction with knowledge bases. Recent advancements have ushered RAG 2.0, known as Search Agents (Trivedi et al., 2022; Singh al., 2025; Li et al., 2025; Jin et al., 2025a: Chen al., 2025; Song et al., 2025; xAI, 2025; OpenAI, 2025). This paradigm leverages the strong reasoning capabilities of Large Language Models (LLMs), allowing for the dynamic and adaptive interleaving of reasoning steps with retrieval calls throughout the generation process. Instead of a fixed pipeline, search agents can decide when and what to retrieve based on LLM's ongoing reasoning, leading to significant improvements in the quality and depth of the generated responses. Leveraging post-training techniques similar to DeepSeek-RI 1 some pioncering models can even autonomously initiate retrieval actions during reasoning without intermediate supervision (Jin et al., 2025a; Chen et al., 2025; Song et al., 2025).
However, the improved generation quality achieved by search agents often comes at the cost of cffi- ciency-an overhead that is nontrivial in practical deployments. In reasoning- ceasoning-with-scarch scenarios, achieving low-latency responses critical for ensuring a seamless user experience (Ray et al., 2024; Jin et al., 2024). Moreover, during post-training of LLM- based search agents, efficient model rollouts over large-scale training corpora are essential to support scalable learning. While recent systems incorporate advanced inference optimizations-sute
sequence concatenation (Jin et al., 2025a; Chen et al., 2025; Song et al., 2025) and prefix caching (Jin et al., 2024; Kwon et al., 2023; Zheng
'Equal contribution
Corresponding authors: Tiannuo Yang (tiannuoy@use.edl edu), Lixiao Cui (cui 1x@nankai. edu. cn), and Willic Neiswanger (nei swangQuuss edu).

---

Published as a conference paper at ICLR 2026
et al., 2024) these techniques are not specifically designed to address the unique computational challenges posed by the tight interleaving of multi-step reasoning and dynamic retrieval.
To this end, first conduct systematic analysis of the efficiency factors governing LLM-based search agents, uncovering insights that diverge from the understanding of naive RAG. Our in- depth analysis reveals two key observations: First, we demonstrate mon-mmontoniic relationship between retrieval accuracy and end-to-end efficiency. Both excessively high (e.g., exact search) and excessively low retrieval recall degrade overall efficiency. While aiming for perfect recall incurs unnecessary computational overhead in the retrieval phase, low recall necessitates more retrieval iterations and longer reasoning paths by the LLM to compensate (as shown in Figure 1). This highlights that search agent systems benefit from supports reasoning without unnecessary retrieval costs. Second, we find that search agent systems are highly sensitive to retrieval latency. Unlike naive RAG where retrieval is largely amortized, even minor increases in retrieval time in the search agent system can cause a disproportionately large increase in end-to-end latency (Figure 2a). We attribute this magnification effect to two primary root causes: improper scheduling, where standard policies like FCFS fail to prioritize requests that would benefit most from KV-cache reuse (Figure 2b), and aatrieval-inducee stalls, where timing misalignments between asynchronous retrieval and token generation force requests to wait, leading to unnecessary recomputation (Figure 2c).
approximate search that effectively
Motivated by these findings, we propose SearchAgent-X X, an inference system dedicated for efficient search agents. SearchAgent-X is designed to optimize end-to-end system throughput and latency by smoothly coordinating the interleaving of sell-reasoning and retrieval. Since both overly low and high retrieval efforts lead to degraded efficiency, SearchAgent-X chooses build upon high-recall approximate retrieval method. To tackle the problem of improper scheduling, SearchAgent-> schedules requests with priority awareness through their real-time status to enhance KV-cache utilization. Moreover, in order to overcome frequent getrieval-induce stalls, SearchAgent-x proposes a non-stall retrieval mechanism through an adaptive strategy that allows generation to proceed without unnecessary waiting while ensuring sufficient retrieval quality.
Our extensive experiments demonstrate that SearchAgent-2 consistently and significantly outper- forms state-of-the-art baseline systems across various operational settings. In both offline and online inference scenarios, SearchAgent-- achieves substantial improvements in system performance (e.g.. 1.3-3.4x higher throughput) by improving LLM KV-cache utilization (from 0.07 to 0.65), all while maintaining the high generation quality characteristic of search agents with exact retrieval.
BACKGROUND AND MOTIVATION
2.1 PRELIMINARY: LLM--ASSE SEARCH AGENT SYSTEMS
LLM-bbsed search agent systems are designed tackle complex requests by decomposing problems into a series of interleaved, multi-turn reasoning and information retrieval steps. This allows the LLM to adaptively seek and integrate external knowledge throughout its reasoning process. Appendix A shows an example of the process of
search agent.
Supporting Multi- Turn Reasoning. Search agent systems often build on LLM inference frameworks like vLLM (Jin et al., 2025a). They use Sequence Concatenation for dynamic retrieval: during inference, the system monitors model output for retrieval signals. Upon such a signal, LLM decoding pauses, query is issued, and retrieved results are concatenated with previously generated tokens to form a new, extended Sequence. This is then re-injected into the LLM to resume reasoning.
To enhance efficiency, Prefix Cache is commonly leveraged (Jin et al., 2024; Zheng et al., 2024). This technique stores key-value (KV) pairs from the L.M'' s attention mechanism for prior tokens, allowing efficient reuse in subsequent generations. This is particularly advantagcous in search agents, as the concatenated sequence's prefix, excluding newly retrieved tokens, overlaps with the previous generation. Furthermore, shared system prompts across search agent requests be cached and reused. In our evaluation, enabling prefix caching saved over 24% of token recomputation costs.
Sequence Scheduling. Efficient scheduling is vital for high throughput. Modern LLM inference frameworks utilize Iteration- Scheduling, where GPU scheduling decisions occur at the gran- ularity of the single token generation step (Kwon et al., 2023; Zheng et al., 2024). Compared to
2

---

Published as a conference paper at ICLR 2026
sequence-level scheduling (NVIDIA, 2019; 2021), iteration-level scheduling avoids waiting for all sequences a batch to complete, thus preventing bubble problems and becoming a leading solution. Frameworks like vLLM typically employ Seess--Com-FFiit-Seeee (FCFS) scheduling policy.
Retrieval Mechanism. On the retrieval side, semantic search techniques efficiently locate relevant external knowledge. Queries usually encoded into dense vector representations for searching in vector space. The two primary approaches are exact nearest neighbor (ENN) search (Dasgupta & Sinha, 2013) and approximate nearest neighbor (ANN) search (Malkov & Yashunin, 2018; Guo et al., 2020). Graph-based ANN methods like HNSW (Malkov & Yashunin, 2018) offer a favorable speed/aceuracy trade-off, making them suitable for large knowledge bases.
2.2 KEY INSIGHTS: FACTORS GOVERNING EFFICIENCY
Despite significant progress high-performmnce LLM inference and retrieval, the LLM-based search agent's 's efficiency remains poorly understood. In this section, we analyze the influence of two key factors: 1) retrieval accuracy and retrieval latency, and examine how they contribute to severe inefficiencies in current solutions. For retrieval, we assume a local search with fixed dense encoder. Experiments in this section use Search-R1 on MuSiQue and the default vLLM configuration.
2.2.1 IMPACT OF RETRIEVAL ACCURACY
Both overly high and overly low retrieval recall degrade end-to-end efficiency. High recall increases retrieval overhead, while low recall leads to longer reasoning steps.
Insight 1:
We first investigate the impact different retrieval ac- curacies the system efficiency of search agents. In- tuitively, lower retrieval accuracy means lower retrieval overhead, thus higher system efficiency. However, observe a "less is more" phenomenon for LLM-based search agents. Low-recall retrievals may result in sub- optimal context, forcing the model to compensate by is- suing additional retrievals and extending the reasoning length. Figure 1 shows how varying the ANN search range affects throughput and average retrieval counts. When the search range is too small (e.g., 10), the model fails to retrieve useful documents, resulting longer reasoning steps and an average of 6.5 retrievals per re- quest. This reduces throughput to just above 2.1. As the search range increases 500, retrieval quality im- proves, and the model completes reasoning with fewer retrievals (around 5.7), boosting throughput over 3.2.
Throughput (Generalion error beyord 1%)
Throughout (Senaration accuray arror within 1%)
Avg. Counts
6.50
Throughou
3.0
5.75
10
50
500
5000
10000
20000
ANN Search Range
Figure 1: Impact of Retrieval Accuracy on Search Agent Efficiency. Higher ANN search range means higher-recall retrieval. Throughput marks the number requests completed per second (higher better). Re- trieval count indicates the number of re- trievals called per request. End-to-end gen- eration accuracy error is calculated by com- parison with an exact retrieval method.
However, further increasing the search range (e.g.. be- yond 10,000) yields diminishing returns. While average retrieval counts decrease slightly, throughput declines due to the higher cost of very high-recall ANN searches. This suggests that simply maximizing retrieval recall not the optimal strategy for search agent efficiency, Once retrieval quality sufficiently supports reasoning, additional search efforts offer marginal benefits and can even harm overall efficiency.
2.2.2 IMPACT OF RETRIEVAL LATENCY
Insight 2: Compared to naive RAG, search agents much more sensitive to retrieval latency due to ignoring inter-request priorities and retrieval-indus stalls.
For naive RAG, all requests are retrieved before generation. Retrieval latency (millisecond level) is negligible compared to the total request latency (second level), so it insensitive to retrieval latency. However, for search agents, retrieval occurs during self self-reasoning, where the time scale of a single token generation and retrieval latency are comparable. Minor retrieval latency can cause requests to be inserted into different token generation iterations, leading different system behaviors.
3

---

Published as a conference paper at ICLR 2026
Request (searched times)
Agentic
Moduler RAG
FCFS Scheduling: 12 > 11, #a waiting
t1
Aug. Eid-so-End Latency (6)
240
17x
LLM Engine
n
Prefil
Recompute for long req #ta
220
83x Latency Magnification
retrieval
Request #a (searched times)
Cache Hit
Cache Miss
200
KV Cache Space
Preftx #b
Increased Prefix of #b
180
Profix dia
(much larger)
Preftx of #a
evicted
Avg. Retrieval Latency (8)
Caused by
(b) Inefficiency Reason Improper scheduling.
Prefhx Ceche Hit Rats
0.30
Request #b (searched times)
Only #b is ready
generation, aa wailing
0.25
LLM Engine
4_1
d_n
Prefill for
KV Recompute for long reg Wa
0.20
retrieval
stalled
4
Request #a
(a) Minor retrieval delays lead to substantial system inefficiency.
(searched times)
(c) Inefficiency Reason #2: Retrleval-Induced stalls.
Figure 2: Impact of Retrieval Latency on Search Agent Efficiency. (a) Search agents exhibit significantly higher retrieval latency sensitivity than naive RAG (up 83 magnification), linked to lower prefix VV-cache hit rates. (b, c) Root causes include: (h) improper scheduling, where serving shorter requests first evicts cache for longer ones, causing recomputation; and (c) retrieval-induced stalls, where requests missing a scheduling point must wait, risking cache eviction.
Figure shows the average end-to-end latency of search agents and RAG under different retrieval latency (controlled by different search ranges), with request rate of requests/sccond and test duration of minutes. For fair comparison, we assume RAG generates the same length of tokens with search agent, and its end-to-end latency te2e is calculated as 182e + Fret Rrret with 182e as the token generation time without retrieval, Eret as the average retrieval time, and Nyet as the average retrieval counts per request. The results indicate that search agents suffer from drastic efficiency degradation under even minor retrieval delays. As average retrieval latency increases from 0.6s to 4.4s, the end-to-end latency of the search agent magnified by over 83x, while RAG remains largely stable. This severe magnification in search agent is strongly correlated with a sharp decrease in the prefix KV-cache hit rate, dropping from over 30% to under 21%, which forces frequent and costly KV recomputations (Figure 2a).
We identify two root causes for this observed behavior, both contributing to unnecessary KV recom- putation, particularly for longer, multi-turn requests: improper scheduling and retrieval-induced stalls. Figure illustrates the issue of improper scheduling. Consider request #a, which involves longer reasoning path with 6 retrievals, and request #b, which just completes a single retrieval. Even if request #a arrives first, if its retrieval completes slightly later than that of #b (t2 > t1), a standard FCFS scheduler may choose to serve #b first in the next iteration. As #b proceeds with its generation, occupies valuable KV-cache space, potentially leading to the eviction of the prefix KV-cache belonging to #a. When request #a eventually resumes, it encounters cache miss and must recompute its entire prefix from scratch, significantly increasing its latency. Our measurements highlight the high cost of such improper scheduling: 55.9% of tokens were unnecessarily recomputed in affected cases, leading to more than a 108% increase in computation time per request.
Even with improved scheduling, another significant inefficiency risk comes from reasoning stalls, depicted in Figure 2c. The asynchronous execution of retrieval and generation can lead to subtle timing misalignments. If long request like #a completes its retrieval only slightly after the deadline for inclusion in the next generation step, it misses the current scheduling batch and is forced to wait until the subsequent one. We term this unproductive waiting period "retrieval-induced stalls." During this stall, shorter requests (e.g., #b) that are ready can continue executing. Their execution may further displace #a's prefix from the KV-cache, once again resulting in costly recomputation upon
4

---

Published as a conference paper at ICLR 2026
<information> Doc 1.2.... <iinformaiinn>
One Generation Step
Retriever
Priority Scheduler
Prefix Match
Non-Stall Retrieval
QA Choice
Context length
Resume!
Retrieval counts
</search>
Ordered Requests
If
step
Step
Requests
Waiting time
2
now-1
Prefill
Reuse KV Cache
retrieval
Adaplive
Termination
Step
Next
Token Generation
Prefix #b
Or
Update
Prefix of Aa
Trtle
External
Decode
Prefill
Cache Space
Knowledge
ANN Graph
<answer> result <lanswer>
Asynchronoussy
3
<search> query </search>
SearchAgent-X's Architecture. Requests are scheduled with priorities. Reasoning and Figure 3:
retrieval are interleaved, with non-stall retrieval mechanism to avoid unnecessary waiting.
#a's eventual resumption. Our data shows that, on average, more than 25% of sequences experience such stalls after completing their retrieval across various scenarios.
Limitations of Existing Solutions. Our analysis highlights key limitations in current search agent systems. ENN retrieval, despite full recall, incurs prohibitive retrieval overhead. While high- recall ANN search more suitable, suffers from retrieval-induced stalls due to asynchronous exccution. Furthermore, prevalent FCFS scheduling LLM inference frameworks (Kwon al., 2023; Abhyankar et al., 2024) disregards the search agent's ' unique request priorities, leading to suboptimal cache utilization and costly recomputation.
DESIGN OF SEERCH
3.1 OVERALL ARCHITECTURE
Drawing upon the above insights, we propose SearchAgent-X, simple yet efficient inference system that is easy deploy, explicitly designed optimize end-to-end efficiency for search agent workloads by smoothly interleaving self-reasoning and retrieval. Figure 3 shows SearchAgent architecture, tightly integrated system processing search agent requests at the token generation level. At each LLM output step, the system checks for special tags that trigger the Retriever for an ANN-based search (e.g., <search>) or request completion (e.g.. <answer>), respectively.
To optimize GPU resource usage, SearchAgent- incorporates priority scheduler. It dynamically prioritizes concurrent requests using real-time collected metrics like retrieval count and waiting time, aiming enhance KV-cache reuse by processing higher-priority requests first. During prefill, prefix matching reuses existing KV pairs from cache, significantly reducing computational overhead; new KV states computed if caching is inapplicable asynchronously to enhance throughput. When retrieval triggered, the system queries a pre-built AÑN graph index. To proactively avoid retrieval-induced stalls, SearchAgent-2 employs non-stall retrieval with adaptive search termination, allowing generation to proceed without unnecessary waiting while ensuring sufficient retrieval quality.
miss occurs. Retrieval and generation operate
3.2 PRIORITY SCHEDULING
SearchAgent-X employs priority-based scheduling mechanism to efficiently and fairly manage
concurrent generation requests. As introduced earlier, each search agent request involves a list of generation sequences [si.o, $1,1,..., St.r.l where $1,0 is the initial sequence and $t (i > 0) represents a sequence resumed after the j-th retrieval. Let r; denote the current number retrievals performed for request i, and Si,r, be the sequence currently being processed.
As discussed earlier, requests that have undergone more retrieval steps (i.c., higher r.) benefit more significantly from prefix cache reuse due longer shared prefixes. Prioritizing such requests can
5

---

Published as a conference paper at ICLR 2026
therefore enhance overall cache efficiency and reduce redundant computation. However, scheduling solely based on retrieval count risks starving requests with fewer or no retrievals, leading to increased end-to-end latency and reduced faimess.
To mitigate these issues, SearchAgent- - utilizes a hierarchical scheduler that dynamically prioritizes requests based on combination of three key metrics associated with request é: (1) the number of
retrievals completed R₂ = ry: (2) the context length of the current sequence C; = Luequi and (3) the waiting time of the initial request W; know fa The first two metrics implicidy prioritize sequences with longer reusable prefixes, while the last ensures faimess by giving preference to
requests that have been waiting longer overall.
Instead of combining these diverse metrics into a single weighted score, which would require tedious and potentially task-specific tuning of weights, SearchAgent-X discretizes each metric into G distinct priority levels. For given metric M E (R, C), the threshold defining the lower bound for level & calculated as:
+ k
TM, = min(M)
G (max((M) - min(M)), 0 G
request is then assigned to the highest priority level for which at least one of its metric values (R,; W., C,) exceeds the corresponding threshold TM
A = max (j E [0, G-1] R, > TR,, W; Two V V > Tes}
Requests that do not meet any threshold are assigned to the base level 0.
Within each assigned priority level, active sequences are further sorted according to their current ((r)) queucing time, defined as W = fno ((r)) where 'urr is the time when the sequence Si,r, becomes ready for processing (e.g., after retrieval completes). Sorting by W in descending order ensures that among requests of similar priority level, those that have been waiting longest for their current step are processed first, mitigating the risk of K KV-cache eviction during extended waits.
Finally, SearchAgent -X determines the execution order by traversing the priority levels from highest to lowest and processing the sequences within each level based on their sorted W
3.3 NON-STALL RETRIEVAL
To mitigate inefficiencies from retrieval latency and prevent vetrieval-induced stalls (Section 2.2.2). SearchAgent-2 incorporates a flexible, non-stall early termination strategy for Approximate Nearest Neighbor (ANN) search. Unlike traditional ANN search that iteratively refines candidates until meeting pre-set criteria (e.g., explored nodes, list stability) and can thus cause pipeline stalls retrieval is slow, SearchAgent-- X adaptively concludes the search. This adaptive termination is based on two key conditions: the maturity of retrieval results and the readiness of the LLM engine, ensuring generation proceeds without unnecessary blocking.
At the core of this strategy is the concept a soft limil for the retrieval process. This soft limit repre- sents checkpoint where search results are likely to have achieved sufficient quality for the generation task. SearchAgent-X estimates retrieval maturity by monitoring returns in quality improvement during the ANN search. While retrieval quality generally improves with more explored neighbors, we find that the rate of improvement diminishes significantly after a certain point, exhibiting a "Knee" where newly found points contribute less to the overall quality. SearchAgent-X exploits this observation. A normalized metric RQ, is used to evaluate the quality of newly discovered candidates at step f, defined as: (d;- dbea)/ (dworss doea), where de is the new candidate's 's distance to the query, while drest and dworst are the distances of the best and worst candidates currently in ANN algorithm's 's list. high RQ, value suggests the new candidate offers little improvement over existing ones, indicating diminishing returns from further search (see details in Appendix B.2).
The maturity exit criterion is met when this smoothed quality signal (derived from RQ.) indicates plateau (i.e., exceeds threshold T) and the L.LM engine is ready for its next token generation operation. Upon meeting both conditions, SearchAgent halts the retrieval and provides the current, sufficiently mature results to the LLM; otherwise, retrievals stop naturally. This adaptive alignment of asynchronous retrieval and generation significantly reduces end-to-end latency without compromising the quality of the retrieved context, contrasting with traditional fixed stopping criteria that may not optimally synchronize with the dynamic state of the generation pipeline. SearchAgent- complete execution process and implementation details can be found in Appendix B.

---

Published as a conference paper at ICLR 2026
VLLM_ENN
VLLM ANN
LM ANN
SearchAgent-X
(frisshe req/see)
1.9-3.4x
End-to-End Lalency
1200
Throughput
1.3-3.7x
1.8-2.7x
1.5
1.8-2.2x
(sac)
0.5x0.6x
1.5-1.7x
0,4+0.5k 0.5kk
400
0 6
0.55x
1
2
4
Top K Retrieved
Top Retrieved
Figure 4: End-to-End Efficiency of Offline Inference. Left: Requests completed per second (higher better). Right: Average end-to-end latency (lower is better). SearchAgent-X is our proposed system, which consistently outperforms all baselines across different top-k values.
1.2
400.0
1.0
End-o-EEd Latenoy (Bec)
Pending Sequence Ratio
Thoughipe (reseed)
0.8
0.8
200.0
0.4
100.0
0.2
2
2
5
Roquest Rate
Request Rate
Request Rate
Figure 5: End-to-End Efficiency of Online Inference. Left: Throughput, Middle: Latency. Right:
Pending Sequence Ratio, the percentage of sequences initiated but not completed within the test period. Lower better, indicating reasonable workload scheduling.
4 EVALUATION
4.1 EXPERIMENTAL SETUP
different search agent models from Search-RI (Jin et al., 2025a) and ReCall (Chen et al., 2025). For retrieval, we adopt a chunked Wikipedia dataset as the knowledge base, using an ANN index constructed with HNSWlib (Malkov Yashunin). Note that our approach is model-agnostic and readily generalizes to other reasoning models/ANN methods.
Models and Datasets. We evaluate our method
Testbed. For the 7B model, we use single NVIDIA L20 GPU with 48GB memory. For the 14B model, we use two A100 GPUs with 40GB memory each, connected via PCIe 3.0. The retrieval system runs on 22 CPU cores with 120GB of RAM.
Baselines, We compare the performance of four methods: 1) vLLM ENN: the vanilla vLLM with exact retrieval. 2) vLLM ANN: vanilla vL.LM system (Kwon et al., 2023) with approximate retrieval. 3) CacheviLM_AND : vanilla vLL.M with approximate retrieval and prefix cache. 4) SearchAgent-XX our proposed system. Refer to Appendix B.3 for detailed setup.
4.2 END-To-ENT PERFORMANCE
We first evaluate the end-to-end performance different methods. For efficiency measurement, we use Musique (Jin et al., 2025b) and HotpotQA (Yang et al., 2018), two datasets of complex multi-hop queries. Two scenarios are tested: (1) offline inference, where all requests arrive the start; and (2) online inference, where requests arrive a fixed rate. In the offline setting, process 1000 requests and measure efficiency upon completion. In the online setting, requests arrive at rates from to 10-minute window. Results for the 7B Search-R1 model are shown in Figures 4 and 5; full results across all metrics and models are in Appendix C.1 and C.2.
In offline scenarios, SearchAgent- consistently outperforms all baselines in terms of system throughput and per-request latency. As shown in Figure 4, SearchAgent- achieves 1.3-3.4x higher throughput and only 0.2-0.6x the latency compared to the baselines across different top-k
7

---

Published as a conference paper at ICLR 2026
Table 1: Generation Quality of SearchAgent-X X and Exact Retrieval.
Dataset
Musique
NQ
2Wiki
HotpotQA
Bamboogle
StrategyQA
Avg.
Generation Accuracy
Exact Retrieval
0.203
0.316
0.371
0.429
0.472
0,788
0.430
SearchAgent-X 0.203
0.320
0.370
0.428
0.472
0.789
0,430
values. Even in the most challenging case of top-k=5, SearchAgent-X still beats the best baseline CacheviLM_AND LANN, with a significant margin (1.5x in throughput and 0.6x in latency). We attribute this improvement to the SearchAgent--2 - high-recall ANN, and the design of efficient scheduling and non-stall retrieval mechanisms. vLLM_ENN performs poorly in this scenario, as it incurs excessive retrieval overhead and hinders end-to-end reasoning efficiency. vLLM_ANN employs a high-recall ANN and performs obviously better than vLLM_ENN, but it still suffers from the inefficiencies of large amounts of recomputation due to the lack of prefix cache. CachevLLM ANN uses prefix cache to reduce recomputation, but it still fails wisely manage the scheduling of requests and avoid ectrieval-inducee stalls, leading to a significant performance gap compared to SearchAgent-X
We also find that the performance of all methods first increases then decreases with the increase of top-k values. This aligns well with our previous observation that both overly high and overly low retrieval quality degrade end-to-end efficiency. When the top-k value is too small, the model may fail to retrieve useful documents, leading to longer reasoning sequences and lower throughput. Conversely, when the top-k value too large, the concatenated sequence becomes too long, resulting in longer prefill time. However, we note that gearchtgent- consistently outperforms all baselines across all top-k values, indicating its robustness to different retrieval settings.
We also observe that SearchAgent-X often yields larger gains on harder tasks. As shown in Table 3 in Appendix C.I, the HotpotQA dataset (a easier dataset according the Search-RI analysis) yields lower benefits compared to the Musique dataset in our main experiments (e.g.. 1.52x of throughput improvement on easy dataset vs. 1.84x of throughput improvement on hard dataset, for top-k=3).
In online scenarios, SearchAgent- X utilizes computing resources more efficiently than baselines, completing more requests the same amount of time. As shown in Figure 5, SearchAgent completes at least 1.5x, and up to 3.5x more requests average than the baseline, within the request rate range of to 6. Further, we record the pending sequence ratio that measures the resource utility of the system, defined as the percentage of sequences that are initiated but not completed within the test period. As shown in Figure (right), SearchAgent- achieves stable, small pending sequence ratios (about 0.2), while the baselines experiences dramatic increases with higher request rates (more than 0.6), indicating the effectiveness of SearchAgent-22 -orpntttt'ss -X's scheduling.
SearchAgent-X achieves comparable generation quality to exact retrieval. We evaluate the generation quality of SearchAgent-X and exact retrieval (vLLM_ENN) on six representative datasets. We use the Exact Match metric as generation accuracy measure the correctness of the generated answers (Jin et al., 2025b). As shown in Table 1, SearchAgent-X achieves similar generation accuracy, retrieval counts and output length (see Appendix C.2 for details) as exact retrieval across all datasets, indicating that it does not compromise generation quality for efficiency. Another interesting finding is that SearchAgent-2 may even achieve higher generation accuracy on some datasets, such as NQ (0.320 0.316). The results could be attributed to two aspects. First, full ANN recall does not necessarily mean optimal generation accuracy; the correct answer document may not always be captured by semantic similarity. Second, the search agent model has the adaptability adjust the reasoning length. ANN might lead search agents to perform an extra reasoning step (e.g., 2.292 vs. 2.288 for NQ), adjusting the retrieval query, which in turn improves generation accuracy.
4.3 ABLATION STUDY
The priority scheduling and non-stall retrieval of SearchAgent-X help improve the prefix cache utility, thus enhancing end-to-end efficiency. In this section, we use Search-R1 7B model on Musique dataset. Figure 6 (left) shows the end-to-end performance of different techniques for offline inference with top-k = 5. We have several observations. First, the advantages of prefix cache are dininished in this challenging scenario. With top-k=5, it's only 1.01 that of vLLM ANN, compared to
8

---

Published as a conference paper at ICLR 2026
End-to-End Latency
Prefix Cache Hit Rate
Waitiin
Prefill Decode
Retrieval
1200
200
1000
0.8
160
Terminate Ratio
800
800
35.55%
6.31%
0.4
Time Breakdown
120
0.16s
0.156
400
Hit
0.36
200
40
81s
VLLM
Prefix
Non-Stall Scheduling
Priority
VLLM
VLLM
+ Prefix
+ Priority Non-Stall
Cache
Scheduling Retrieval
Figure 6: SearchAgent-X Technique Breakdown for End-to-End Performance (Left) and Per- Sequence Generation Time (Right). Each bar/scatter adds one technique over its left bar/scatter, with the leftmost being vanilla vLLM and the rightmost being the full SearchAgent-X.
1.91 x with top-k=1. This validates that the benefits of prefix cache still require appropriate scheduling and retrieval methods unleash its potential. Second, SearchAgent- X's priority scheduling reduces the end-to-end latency by 35.55% based on prefix cache. This is because the priority of requests is properly managed, maximizing the utilization of GPU resources. In addition, the prefix cache hit rate increases from 0.07 to 0.51, verifying the effectiveness of the technique. Third, SearchAgent -X's non-stall retrieval further improves the hit rate 0.65, leading to further 6.3% reduction in latency. This shows that the adaptive termination strategy fully utilizes the "free lunch" of asynchronous execution, timely recalling mature retrieval results, thereby improving system processing efficiency.
Figure 6 (right) further demonstrates the per-sequence generation time of different parts. We have more observations. First, for vLLM ENN, the retrieval time is the largest component, accounting for over 60% of the total time. Instead, its prefill time is the lowest across different techniques, since its reasoning requires waiting for long-time retrieval, thus reducing the pressure on token generation. Second, for priority scheduling, cache utilized), but also the decode time, showing a better system processing capability. This is because by improving KV-cache utilization, it avoids recomputation of long requests, freeing up GPU space earlier for better decode parallelism. Third, non-stall retrieval actually only reduces 0.01s of retrieval time (from 0.16s to 0.15s), with about 24% of the retrievals being early terminated, but significantly reduces the end-to-end latency (41s, the end-to-end latency shown in Figure (left)). This aligns well with our previous observation that minor retrieval latency can cause drastic efficiency degradation (as shown in Figure 2). Non-stall retrieval adaptively terminates only a small set of retrievals when necessary, yet yields the significant benefit of better cache utilization. More experiments can be found in Appendix C.3 to C.7.
note that it reduces not only the prefill time (due more prefix
RELATED WORK
Several recent systems optimize one- multi-round RAG pipelines, such as TELERAG (Lin et al., 2025), RAGO (Jiang et al., 2025), PATCHWORK (Hu et al., 2025), RAGServe (Ray et al., 2024), RAGCache (Jin et al., 2024), AquaPipe (Yu al., 2025). AutoRAG (Fu al., 2024), and PipeRAG (Jiang et al., 2024). These methods either prefetch or pipeline retrieval results, or tune retrieval/generation hy hyperparameters, but they still treat retrieval and generation as largely separated stages and do not analyze the root causes of inefficiency in the dynamically interleaved search-reasoning pattern targeted by SearchAgent-X.
Techniques that could change sequence prefix, such as context trimming, summarization, or token sparsification (Jiang et al., 2023) are also compatible with our design: as long as they are applied in a prefix-press prefexipeeerving fashion during decoding, prefix caching remains effective and scheduler can simply use the effective cached prefix length (after sparsification) as scheduling feature.
Meanwhile, broader agent workflow optimizations, such as auto-tuning (He et al., 2025), KV-cache management (Abhyankar et al., 2024), and partial tool execution (Xu et al., 2024), improve overall efficiency but overlook the specific challenges of retrieval accuracy and latency in search agents. In contrast, SearchAgent-X directly addresses these challenges by tightly coupling reasoning with non-stall retrieval, yielding improved efficiency. Notably, our approach is orthogonal

---

Published as a conference paper at ICLR 2026
to, and potentially be combined with, other RAG optimization techniques such context compression (Shi et al., 2024) and retrieval reranking (Glass et al., 2022).
CONCLUSION
LLM reasoning-driven search agents offer great potential for complex problems, but face severe, distinct efficiency challenges. This paper highlights the non-trivial impact of retrieval accuracy and the latency sensitivity caused by scheduling deficiencies and retrieval-induced stalls. Our proposed system, SearchAgent-X, X, designed based on these insights, demonstrates substantial improvement in system efficiency, all while maintaining high generation quality. This study provides important insights for practical deployments of high-efficiency LLM-based search agents, and the proposed solutions are easily adaptable to other ANN retrieval methods and LLM reasoning models.
REPRODUCIBILITY STATEMENT
We provide the complete source code SearchAgent-X in an anonymous repository at https:/ gi thub. com/ htt//iannnn tiannuo- caaiuuu-yang//a Seang/Sarchhgentt-re X. The repository is self-contained with instructions and scripts to replicate all experiments, along with dataset specifications and pre-trained model references.
ACKNOWLEDGMENTS
W.N. is supported by the National Science Foundation (NSF) under Award No. 2427856.
T.Y. thanks his friend Ke Cheng for the technical advice and discussion provided during the rebuttal.
REFERENCES
Reyna Abhyankar, Zijian He, Vikranth Srivatsa, Hao Zhang, and Yiying Zhang. InferCept: Efficient Intercept Support for Augmented Large Language Model Inference, May 2024. URL http: [cs].
//arxiv.ors /rgg abs/2402. 01869. arXiv:2402.00
Mingyang Chen, Tianpeng Li, Haoze Sun, Yijic Zhou, Chenzheng Zhu, Haofen Wang, Jeff Z. Pan, Wen Zhang. Huajun Chen, Fan Yang, Zenan Zhou, and Weipeng Chen. ReSearch: Learning to Reason with Search for LLMs via Reinforcement Learning, March 2025. URL http:://arxe
org/abs /2503. 19470. arXiv:2503. 19470 [cs].
Sanjoy Dasgupta and Kaushik Sinha. Randomized partition trees for exact nearest neighbor search. In Shai Shalev-Shwartz and Ingo Steinwart (eds.), Proceedings of the 26th Anmual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pp. 317-337, Princeton, NJ, USA, 12-14 Jun 2013. PMLR. URL https: httpp://pproceeding: .ml.eeddiinnm.........mm.m.reere mlr. colr.press/v33 Dasgupta13 html.
Wenqi Fan, Yujuan Ding, Liangbo Ning, Shijie Wang, Hengyun Li, Dawei Yin, Tat-Seng Chua, and Qing Li. A survey on meeting llms: Towards retrieval- augmented large language models. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp- 6491-6501, 2024.
Jia Fu, Xiaoting Qin, Fangkai Yang, Lu Wang, Jue Zhang, Qingwei Lin, Yubo Chen, Dongmei Zhang, Tuning Saravan Rajmohan, and Qi Zhang. AutoRAG-HP: Automatic Online (arg/abs//4000 19251. for Retrieval- Augmented Generation, June 2024. URL http://a/arrx arXiv:2406.11 19251 [cs].
Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, Meng Wang, and Haofen Wang. Retrieval-Augmmented Generation for Large Language Models: A Survey, March 2024. URL http:://aaaii.oorrbb//221122 10997. arXiv:2312.1099 [cs].
Michael Glass, Gaetano Rossiello, Md Faisal Mahbub Chowdhury, Ankita Rajaram Naik, Pengshan Cai, and Alfio Gliozzo. Re2g: Retrieve, rerank, generate. arXiv preprint arXiv:2207.063000 2022.
10

---

Published as a conference paper at ICLR 2026
Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Cher,, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning. pp. 3887-3896. PMLR, 2020.
Shailja Gupta, Rajesh Ranjan, and Surya Narayan Singh. A Comprehensive Survey of Retrieval- Augmented Generation (RAG): Evolution, Current Landscape and Future Directions, October 2024. URL http://arxiv wwg. http//b//22111 12837. arXiv:2410.1283: [cs].
Zijian He, Reyna Abhyankar, Vikranth Srivatsa, and Yiying Zhang. Cognify: Supercharging gen-ai workflows with hierarchical autotuning. arXiv preprint arXiv:2502.08055 2025.
Charles C. Holt. Forecasting seasonals and trends by exponentially weighted moving averages. International Journal of Forecasting. 20(1):5-10, 2004. ISSN 0169-2070. doi: https://doi.org 10. i00e 09.015. URL httph:ttp///tttt sci encedi wtt./oom//c///ee htmm//iicncearrrceee. p2i/$016920700300000
Bodun Hu, Luis Pabon, Saurabh Agarwal, and Aditya Akella. Patchwork: A unified framework for RAG serving. CoRR, abs/2505.07833, 2025. doi: (0,485500aXXiv2555.0783... URL https:
lwwaii.oorrree.. atrg/abs/25000 07833.
Yizheng Huang and Jimmy Huang. A Survey on Retrieval-Augmennte Text Generation for Large Lan- guage Models, August 2024. URL http://arxiv. wrgg/bs///0/.aa.o// attp://aaxx..rrrraas/244444 10981. arXiv:2404. 109888 10981
[cs].
Huiqiang Jiang, Qianhui Wu, Chin- Yew Lin, Yuqing Yang, and Lili Qiu. LLMLingua: Compressing prompts for accelerated inference of large language models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2023. doi: 44445550//XX..231000575333 URL https: //arvvv..vvvv///aa///a/ org/ hts///bs//2333 2313605736..... 05736.
Wenqi Jiang, Shuai Zhang, Boran Han, Jie Wang, Bernie Wang, and Tim Kraska. Piperag: Fast retrieval-augmented generation via algorithm-system co-design. arXiv preprint arXiv:2403.05676 2024.
Wenqi Jiang, Suvinay Subramanian, Cat Graves, Gustavo Alonso, Amir Yazdanbakhsh, and Vidushi Dadu. Rago: Systematic performance optimization for retrieval-augmentee generation serving. In Proceedings of the 52nd Annual International Symposium on Computer Architecture (ISCA '25), pp. 974-989. ACM, 2025. doi: 10. 10.11457395503333310093 URL 2503. 14649.
Bowen Jin, Hansi Zeng, Zhenrui Yue, Dong Wang, Hamed Zamani, and Jiawei Han. Search-RI1 Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning, March 2025a. URL httt:://ttpiiii org/ a250. 09516. arXiv:2503.099 16511 [cs].
Chao Jin, Zili Zhang, Xuanlin Jiang, Fangyue Liu, Xin Liu, Xuanzhe Liu, and Xin Jin. RAGCache: Efficient Knowledge Caching for Retrieval-Augmented Generation, April 2024. URL http: htbb//444 2204. 12457. arXiv:2404.1 114:24 [cs].
//arxiv. org. abs
Jiajie Jin, Yutao Zhu, Guanting Dong. Yuyao Zhang, Xinyu Yang, Chenghao Zhang, Tong Zhao, Zhao Yang, Zhicheng Dou, and Ji-Rong Wen. FlashRAG: A Modular Toolkit for Efficient Retrieval- Augmented Generation Research, February 2025b. URL arXiv:2405. 13576 [cs].
aa////bs////// 13576.
Jeff Johnson, Matthijs Douze, and Herve Jegou. Billion-scale similarity search with gpus. IEEE Transactions Big Data, pp. 535-547, Jul 2021. doi: 10. 10.11999tbaa..221.221177777 URL http::/dx.doi... dww..og/.......... t109/tbddtt.20000 2019. 2919.2921572.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pp. 61 611-626 2023.
11

---

Published as a conference paper at ICLR 2026
Conglong Li, Minjia Zhang, David G. Andersen, and Yuxiong He. Improving approximate nearest neighbor search through learned adaptive early termination. In Proceedings of the 2020 ACM SIGMOD International Conference Management of Data, SIGMOD '20, pp. 2539-2554, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 97814503611 450367356. doi: 1445/33188444338666611 URL https:t/s//doii.. wrg/10........ 1145/3318464 3380680.
Xiaoxi Li, Guanting Dong, Jiajie Jin, Yuyao Zhang, Yujia Zhou, Yutao Zhu, Peitian Zhang, and Zhicheng Dou. Search-ol: Agentic search-enhanced large reasoning models. arXiv preprint arXiv:2501.05366, 2025.
Chien-Xo Yu Lin, Keisuke Kamahori, Yiyu Liu, Xiaoxiang Shi, Madhav Mahesh Kashyap. Yile Gu, Rulin Shao, Zihao Ye, Kan Zhu, Stephanie Wang, Arvind Krishnamurthy, Rohan Kadekodi, Luis Ceze, and Baris Kasikci. Telerag: Efficient retrieval-augmented generation inference with lookahead retrieval. CoRR, abs/2502.20969, 2025.
doi: 10448550/rrx..22002.200 URL
https://arxiv. wtt.:/or//bbbb/22.22000
Yu. A. Malkov and D. A. Yashunin. Hnswlib fast approximate nearest neighbor search. https:
//gi www.ttt.....mu..eeeeeeee wtt.mmmmsllmiimmmmmmmmmmemmmaeee b/hnswlib. Accessed: 2025-05-15.
Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4):824-83) 2018.
Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45: 61-68, 2014. ISSN 0306-4379. doi: http::/800..or//100001///.220220
URL https:
//www. wwwencedirect..c..mm.....
NVIDIA. FasterTransformer. http::/gttttu.oooo///////aaatttt 2019. Ac-
cessed: 2025-05-14.
NVIDIA. Triton Inference Server: Dynamic Batching. https://docs.nvida.
deeplearning/triton infornnineeeeeeeeeee server/used httr//usrrguuid/ddeeeee http:///s//uuer.uiieeeeeeeeeeeee
configuration. hww.::ttmmmnncaaaaaaaeaa
2021.
Accessed: 2025-05-14.
OpenAI.
Introducing
deep research.
https://openai.com
introducing- -eep-inn-deee---ee researchs 2025.
Accessed: 2025-05-15.
Siddhant Ray, Rui Pan, Zhuohan Gu, Kuntai Du, Ganesh Ananthanarayanan, Ravi Netravali, and Junchen Jiang. RAGServe: Fast Quality-Awart RAG Systems with Configuration Adaptation, December 2024. URL http://arxiv..
http://axwi..gg/bb////a/aaa wwtp/og//////////// 10543. arXiv:2412.10043 [cs].
Nils Reimers and Iryna Gurevych. Sentence-bert. Sentence embeddings using siamese bert-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019. URL https: /ttp///axvvvv//a////v org/ abs/ 10084.
Z. Ren, K. Dockemeijer, Apparao, and A. Trivedi. Storage-based approximate nearest neighbor search: What are the performance, cost, and i/o characteristies? In 2025 IEEE International Symposium on Workload Characterization (ISWC)). IEEE, oct 2025.
Kaize Shi, Xueyao Sun, Qing Li, and Guandong Xu. Compressing long context for enhancing rag with amr-based concept distillation. arXiv preprint MXXiv2405.0000S 2024.
Aditi Singh, Abul Ehtesham, Saket Kumar, and Tala Talaei Khoei. Agentic Retrieval-Augmented Generation: A Survey on Agentic RAG, February 2025. URL 69136. arXiv:2501 .09136 [cs].
Huatong Song, Jinhao Jiang, Yinggian Min, Jie Chen, Zhipeng Chen, Wayne Xin Zhao, Lei Fang, and Ji-Rong Wen. RI-Searcher: Incentivizing the Search Capability LLMs via Reinforcement Learning, March 2025. URL URL www....ww.....///./a..... 005.5553..505.292 59592. arXiv:2503.055 05559 [cs].
12

---

Published as a conference paper at ICLR 2026
Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. Interleaving retrieval with of-in-oo-thhuuuh reasoning for knowledge-imtensive multi-step questions. arXiv preprint arXiv:2212.10509 2022.
M. Wang, X. Xu, Q. Yue, and Y. Wang. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proceedings of the VLDB Endowment, 14 / 10. 14778/
(11):1964-1978, 2021. doi: 00144778/347624.347772222 URL hwtph:tt//ooo org/ 3476249. 3476255.
Shangyu Wu, Ying Xiong, Yufei Cui, Haolun Wu, Can Chen, Ye Yuan, Lianming Huang, Xue Liu, Tei- Wei Kuo, Nan Guan, and Chun Jason Xue. Retrieval-Augmenned Generation for Nat- ural Language Processing: A Survey, July 2024. URL http arXiv:2407.33193 [cs].
13193.
XAI. Grok agents: Combining reasoning and tool use.
grok-age -ati--genttt--s combining-reasontiee
and- tool use, 2025.
Accessed: 2025-05-15.
Yechen Xu, Xinhao Kong. Tingjun Chen, and Danyang Zhuo Conveyor: Efficient tool-aware Ilm serving with tool partial execution. arXiv preprint arXiv:2406.00059, 2024.
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpoiQA: A dataset for diverse, explainable multi-hop question answering. In Conference Empirical Methods in Natural Language Processing (EMNLP), 2018.
Hao Yu, Aoran Gan, Kai Zhang, Shiwei Tong, Qi Liu, and Zhaofeng Liu. Evaluation of retrieval- augmented generation: A survey. In CCF Conference on Big Data, pp. 102-120. Springer, 2024.
Runjie Yu, http:///ridd.r///000909000000000
View Profile, Weizhou Huang, View Profile, Shuhan Bai, https://orcid.org/00000 0002-0842-7602, View Profile, Jian Zhou, http:://orcid.r///0000000000 010--0000--225-668.00 View ortp:0000000001-944---1000010
and View Profile. AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models. Proceedings of the ACM on Management of Data, 3(1):1-26, February 2025. doi: 10. 145/3709661 URL https://dlnext. acm. org/doi. 19..114/37996611111 Machinery.
Profile, Fei Wu,
Publisher: Association for Computing
Penghao Zhao, Hailin Zhang, Qinhan Yu, Zhengren Wang, Yunteng Geng, Fangcheng Fu, Ling Yang, Wentao Zhang, Jie Jiang, and Bin Cui. Retrieval-Augmmented Generation for Al-Generated Content: A Survey, June 2024a. URL http:://ta//teee http://wwwwv.......a//// / 19473. arXiv:2402. 19473 [cs].
Siyun Zhao, Yuqing Yang, Zilong Wang, Zhiyuan He, Luna K. Qiu, and Lili Qiu. Retrieval Augmented Generation (RAG) and Beyond: A Comprehensive Survey on How to Make your LLMs use External Data More Wisely, September 2024b. URL http://arxi: //wxiv///xivv////////// httg/bbs/24000 14924. arXiv:2409, 14944 [cs].
Lianmin Zheng. Liangsheng Yin, Zhiqiang Xie, Chuyue Livia Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E Gonzalez, al. Sglang: Efficient execution of structured language model programs. Advances in Neural Information Processing Systems, 37: 02557-62583 2024.
13

---

Published as a conference paper at ICLR 2026
APPENDIX
A AN ILLUSTRATION OF LLM-BASED SEARCH AGENTS
Figure 7 shows an example of a search agent process. Faced with a complex query ("Curious is a women's 's fragrance by a singer born in what city and state?"), the search agent first engages in preliminary reasoning ("I need to find out which city and state singer..."). Recognizing a knowledge gap regarding the "Curious fragrance," the model proactively decides to initiate a search (" ("search Curious fragrance information") ). Upon receiving the crucial information ("Curious is a women's fragrance by Britney Spears"), the model doesn't It conclude its process. Instead, it integrates this new knowledge into its subsequent thought process and reasoning. This triggers further searches, of which the retrieval result concatenated with previously generated tokens and re-injected into LLMs. Through this dynamic cycle of "think-search-rettinkk the model progressively assembles the necessary pieces of the knowledge puzzle required to answer the question fully, This culminates in high-quality answer that addresses all aspects of the initial query ("McComb, Mississippi"). This ability to autonomously plan retrieval actions and iteratively incorporate new information into its reasoning process allows the search agent tackle more complex questions and deliver better responses, moving beyond reliance solely pre-trained knowledge or a single retrieval.
<think> need to find out which city and state a singer ... </think> <search> Curious fragrance information </search>
Prompt
S User
Concatenation
<information> Curious fragrance by Britney Spears <iiffrmation>
Input Question
"Curious
28
LLM prefill
Curious la a fragrance by a singer born in what city and state?
decode
Multi-Turn
Search
Approsimate Nearest Neighbor
requeett
Noarest Neighbar Slow
High
nead to find
Search Agent
Output Answer
<answer> McComb, Mississippi <lanswer>
(1 End request
tum
sthink> I need to find out which city and state a singer. ... s/think>
"Curious fragrance information"
<search> Curious fragrance information </search>
<lanswer>
</search>
Figure 7: An illustration of reasoning and search interleaved L.LM-based search agents.
B IMPLEMENTATION DETAILS
B.1 SEARCHAGENT- EXECUTION
This section outlines the high-level execution flow of the SearchAgent-X system, as depicted in Algorithm 1, complementing the conceptual component descriptions in Section 3 of the main paper. SearchAgent-X orchestrates LLM inference (with prefix caching, Section 3.1), dynamic high-recall approximate retrieval, Priority Scheduling (Section 3.2), and Non-Stall Retrieval (Section 3.3) to achieve efficient search agents. The system initializes an LLM inference engine and manages incoming requests, active asynchronous search tasks, and their results.
The main execution loop begins by ingesting new user requests into the LLM engine's pool (line5-7). Concurrently, Non-Stall Retrieval active, SearchAgent-X consults an external signal to identify and expedite the completion of any ongoing retrieval tasks that have reached sufficient maturity or for which LLM engine readiness dictates early termination (line 10-11), thus preventing pipeline stalls. Upon completion of search (either normally via early termination). retrieved documents are concatenated with the original context, and the augmented request is resubmitted to the LLM engine (line 15-20).
14

---

Published as a conference paper at ICLR 2026
The of the processing loop involves LLM generation and the agentic control flow. Before each LLM generation step. SearchAgent-X's Priority Scheduling policy is applied to the queue of waiting requests. reordering them to optimize system throughput and KV-cache utilization (line 23). Following token generation by the L.M,, the output for each active sequence is parsed (line 25-28). If <search> tag is detected, indicating need for external knowledge, SearchAgent halts further generation for that sequence and launches an asynchronous high-recall ANN retrieval task (line 29-34). Conversely, a <answer> tag is identified the sequence naturally concludes, the request is finalized (line 35-38). This iterative and asynchronous process enables the dynamic interleaving of LLM reasoning, external knowledge retrieval, and intelligent scheduling, which is fundamental to SearchAgent -X's efficient handling of complex search agent workloads.
Algorithm SearchAgent X Main Execution Loop
1: Initialize LLM Engine, ArrivalQueue, ActiveSeerccTTasks. FinishedOutputs
2: Configure PriorityScheduling (enabled/type), NonStallRetrreval (enabled)
3: while LLM_Engine has unfinished requests or not ActiveSeeaccTTask is empty or not Ar- rivalQueue is empty do
4: // Step 1: Ingest new requests
5: for each request Rnew in ArrivalQueue ready for processing do
6: Add Rnew to LLM Engine's 's request pool
7: Remove Rnew from ArrivalQueue end for
8:
9:
// Step 2: Non-Stall Retrieval Check (if enabled)
if NonStallRettrivall enabled and ActiveSearchTasks not empty and LLM Engine has waiting requests then TerminatedSearchlIS: < ChecKExtenalNonSttlliinnoo // Queries for searches to terminate early
12:
13:
end if
14:
// Step 3: Process completed search tasks
15:
for each search task S, in ActiveSearchTaske that has completed do
16:
Rorig, wwwrreeeedddoee.. search ficurch_fnissttimee +- g.getssuul)( new context <- Concatenate (Rorie context, retrieved docs)
17:
18:
AddResumedRRquuste Rorig: new context, search finish time) LLM Engine Remove S. from ActiveSearch Tasks end for
19:
20:
21:
// Step 4: LLM Generation Step
if LLM Engine has unfinished requests then
23:
// Section 3.2
ApplyPiorriyycheediiggLLLL. Engine. waiting requests)
Engine.waiting
25:
I.LM__utpure Scheduler_Ingg +- W.L.M__ngine.ttte
26:
27:
for each output O, in LLM-Ouiputs do
28:
current text + O, geteenerttcdeex(() if DetectSearcTTaiccureee text) then
29:
30:
query + ExtraceSearchQueeyycurrntt text)
31:
LLM Etn.ggneebbborreuusss(((eeeeeeee
32:
S +- L-aaaddlsnneeerrrrlalaaaaa.,oo
current_text, query)
// High-recall ANN
34:
Add Snew to ActiveSearch Tasks
else (eeteetAnswerTaggcuum
text) or is.isiiis)edd)) then
36:
Add O, to FinishedQutputs
LLM LLM_ wwi.EnngieeabooRRuuet(((eeeeeee
38: end if
39:
end for
40:
end if
41:
end while
42: CleampRemaininggTaake
15

---

Published as a conference paper at ICLR 2026
1.0
Recall- 0.3
Number of Explored Candidates
40k
0.940
0.8
Metric Value
30k
0.8
0.6
0.6
Recall
20k
0.4
0.4
0.2
RQ
10k
EMA of RQ
Persi Maturit Exct
0.2
Maturtty Stop
Recall
0.0
Ok
0.0
10k
20k
Number Explored Candidates
Queries
Figure 8: EMA Signal of Retrieval Maturity, RQ means relative quality of newly explored candidates. EMA represents smoothed RQ. The vertical line marks maturity, where the improve- ment of recall and EMA decreases to about O.
Figure 9: Comparison of Maturity Exit and Natural Stop. The shadows represent the ber of candidates explored by two methods (showing similar trend). The curve represents the recall of maturity exit (consistently high).
B.2 RETRIEVAL MATURITY ESTIMATION
In practice, the raw RQ, signal described in Section 3.3 exhibits short-term fluctuations that may hinder robust maturity estimation. To address this, SearchAgent-X applies an exponential moving average (EMA) (Holt, 2004), with a window size of 500, to smooth the signal.
Selecting appropriate threshold for the EMA is critical to balancing retrieval quality and latency. To determine a suitable value, we sample queries from the Musique dataset and record the evolution of the EMA curve as the number of explored candidates increases. For each query, we identify the point where the EMA curve flattens-ia i.e. where marginal improvements approach zero- pero-indicating that newly explored candidates are far from the query and contribute little to quality. This point reflects the onset of retrieval maturity. As shown in Figure 8, the recall at this stage also stabilizes and reaches high level (around 0.98). We adopt the corresponding EMA value (r = 0.9) at this "knee" as the practical threshold in SearchAgent- X to reliably trigger maturity exit. We provide more analysis of this design to verify its effectiveness in Appendix C.3.
B.3 DETAILED EXPERIMENTAL SETUP
implement SearchAgent by building upon vLLM (Kwon et al., 2023), a state-of-the-art LLM inference engine to its efficient PagedAttention mechanism. For retrieval component, use knowledge base constructed from a chunked Wikipedia dataset, containing approximately 21 million text chunks. Each chunk is embedded into 384-dimensional vector using the all- Wil1-MiniLM-LL model (Reimers & Gurevych, 2019). An Approximate Nearest Neighbor (ANN) index is built offline over these embeddings using HNSWlib (Malkov & Yashunin), configured with parameters such as up to 32 neighbors per node and an efConstruction (candidate list size during build) of 500. This index serves as the foundation for all ANN-based retrieval methods in our experiments. For these ANN searches (employed by SearchAgent- X and approximate retrieval baselines), we generally the search range (e.g.. efSearch) 10,000 achieve high recall with acceptable computational overhead, based on empirical analysis. These HNSW ANN searches leverage inter-query parallelism with threads to optimize throughput while managing memory access contention.
Specific configurations for the different systems are as follows. For the exact retrieval baseline (VLLM_ENN) we adapt HNSWlib to perform exhaustive search more efficiently by enabling intra-query parallelism, utilizing 6 threads. For SearchAgent-2 beyond using the aforementioned high-recall
ANN setup, we set its unique parameters: the priority scheduling level G is configured to (we note that SearchAgent-X exhibits low sensitivity to this specific value, shown in ablation study in Appendix C.4). The threshold TEMA for estimating retrieval maturity in the non-stall mechanism set to 0.9, determined via offline profiling detailed in Appendix B.2. The approximate retrieval
16

---

Published as a conference paper at ICLR 2026
baselines (vLLM_ANN, CachevLLM also utilize the general ANN search settings described above, including the search range 10,000 and threads for inter-query parallelism.
C MORE RESULTS
C.I DETAILED OVERALL EFFICIENCY
We note that SearchAgent -x outperforms all baselines in different scenarios including model sizes, deployment methods (single GPU distributed GPUs), top-k values, and query datasets.
Different Model Sizes and Top-k Values Table 2 presents detailed results of overall efficiency across different methods for Search-R1 under 7B (on a single L.40 GPU) and 14B models (on two 40GB A 100 GPUs). The advantage of SearchAgent-XX is bigger in the 7B model and small top-k: values of the 14B model. This is due to two reasons. First, although the 14B model distributes model weights across two A 100s, its KV-cache space still smaller than the 7B model (because the model weights are larger, resulting in larger KV-cache for a single token). The 7B model has a larger available KV-cache space, thus yielding greater benefits from managing the prefix cache. Second, the 14B model we test calls retrievals more cautiously, while the 7B model calls more retrievals (e.g.. 4.9 of the model vs. 3.3 the 14B model when top- = for Musique dataset), resulting a greater distinction in request priority.
Different Datasets outperforms all baselines, achieving 1.47x to 2.55x higher throughput and 1.62x 2.81x lower latency compared to the strongest baseline, CachevLLM
Moreover, shown in Table 3, on the HotpotQA dataset, SearchAgent-X also
Different Search Agent Models To further demonstrate the generality of our method, we apply it different search agent architecture, ReCall (Chen et al., 2025). We observe that SearchAgent-X consistently delivers best efficiency. As shown in Table 4 below, when applied to ReCall's ss 7B model, SearchAgent-X attains 1.12x to 1.74x higher throughput, 1.31x to 1.81x lower latency, and 1.49x to 2.86x higher cache hit rate than baselines. The results demonstrate that SearchAgent-X still outperforms the most competitive baseline in this different search agent architecture, confirming the generality of SearchAgent-X..
C.2 DETAILED GENERATION QUALITY
Table 5 further shows the generation details beyond Table 1 of SearchAgent and exact retrieval (vLLM ENN) across different datasets. We note that SearchAgent- achieves similar generation length as exact retrieval across all datasets (6822 tokens vs. 6826 tokens), indicating that our non-stall retrieval does not lead to unusual search agent model/retriever behaviours, making SearchAgent-X possible for maintaining perfect generation quality.
C.3 ANALYSIS MATURITY EXIT MECHANISM
The maturity exit mechanism effectively halts unnecessary searches without compromising retrieval quality. To validate the effectiveness of non-stall retrieval, we analyze whether the maturity- based termination reliably halts unnecessary ANN iterations. We compare the retrieval traces of representative queries under two settings: maturity-basee early stop and standard natural stop. As shown in Figure we make several observations. First, query difficulty varies significantly across the dataset, resulting in different numbers of candidate nodes explored before natural convergence. This highlights the need for an adaptive termination strategy rather than relying on fixed exploration budget. Second, for queries of varying difficulty, the number of candidates explored by the maturity- based strategy closely matches the natural termination point of standard search, indicating our maturity exit accurately captures query difficulties. More importantly, the recall achieved by queries remains consistently high (0.963 on average). These results confirm that our ntn-stall retrieval effectively terminates redundant search iterations while preserving retrieval quality.
17

---

Published as a conference paper at ICLR 2026
Table 2: Comparison across seven key metrics and top-k values for different methods. Throughput and efficiency gains are marked by x multipliers. Lower values are better for metries marked with
Metric
Top-1
Top-2
Top-3
Top-4
Top-5
Top-1
Top-2
Top-3
Search-R1-7B
Search-RI-14B
Throughput
VLLMEENN
0.44
0.69
0.62
0.63
0.61
0.46
0.47
0.43
VLLM_ANN
0.62
1.04
0.76
0.73
0.68
0.77
0.61
CachevLLM
1.18
1.25
0.89
0.77
0.69
1.08
0.89
0.70
SearchAgent-X
1.59
2.36
1.64
1.39
1.01
1.40
1.09
0.76
Max Ratio
3.61x
3.42x
2.65x
2.20x
1.66x
3.04x
2.32x
1.77x
Min Ratio
1.35x
1.89x
1.84x
1.81x
1.46x
1.30x
1.22x
1.09x
Token Throughput
VLLM_ENN
69.90
90.85
86.12
97.79
84.26
156.35
127.28
111.21
vLLM_ANN
101.21
136.81
106.09
114.28
94.65
320.76
206.46
159.70
CachevLLM ANN
191.65
164.46
124.59
119.17
95.64
366.85
239.01
182.60
SearchAgent-X
259.94
309.73
229.96
216.21
139.25
472.76
292.13
199.14
Max Ratio
3.72x
3.41x
2.67
2.21x
1.65x
3.02x
2.30
1.79x
Min Ratio
1.36x
1.88x
1.85x
1.81
1.46x
1.29x
1.22x
1.09x
Latency
vLLM ENN
1300.56
1066.05
1089.37
1154.62
1205.16
1642.86
1567.85
1614.71
vLLM ANN
571.36
625.33
790.68
930.29
1020.46
767.46
923.74
1052.74
CachevLLMMANN
429.60
562,47
759.57
916.58
1026.91
673.35
805.60
980.35
SearchAgent-
238.00
266.50
347.14
466.78
620.07
502.10
690.20
939.42
Max Ratio
0.18x
0.25x
0.32x
0.40x
0.51
0.31x
0.44x
0.58x
Min Ratio
0.55x
0.47x
0.46
0.51
0.60
0.75x
0.86
0.96x
P99 Latency +
VELMLENN
1758.64
1441,18
1462.45
1569.80
1641.90
2205.26
2136.75
2237.55
vLLM
915.04
956.46
1160.86
1348.87
1459.13
1066.63
1334.67
1555,47
CachevLLX
609.70
797.46
1073.03
1296.03
1446.88
930.06
1159.02
1454.61
SearchAgent-2 X
373.20
421.32
566.28
716.88
993.98
732.16
958.78
1362.24
Max Ratio
0.21
x.29
0.39
0.46x
0.61
0.33x
0.45
0.61
Min Ratio
0.61x
0.53x
0.53
0.55
0.69
0.79x
0.83
0.94x
Table 3: Comparison of system efficiency under the HotpotQA dataset.
TopK
Method
Throughput
Latency
Token Throughput
Cache Hit Rate
3
VLLM ENN
0.78143
483.4094
106.0500
0.0000
MAchevLLMAAN
1.30926
282.9210
179.9000
0.3890
SearchAgent -X
1.99253
171.9478
271.8200
0.8890
4
VLLM ENN
0.74530
505.7417
102.6500
0.0000
CachevLLM 0.95950
375.9803
133.7800
0.3040
SearchAgent
1.57188
210.8670
217.4600
0.9100
VLLM_ENN
0.68400
543.9000
87,5970
0.0000
CachevLLM ANN
0.81700
443.1300
105.2410
0.1706
SearchAgent-x 1.20400
273.6900
154.8331
0.7340
18

---

Published as a conference paper at ICLR 2026
Table 4: Comparison of system efficiency under the ReCall search agent model.
TopK
Method
Throughput
Latency
Token Throughput
Cache Hit Rate
3
VLLM_ENN
0.6370
376.375
224.550
0.000
CachevLLM ANN
0.9861
273.360
342.490
0.570
SearchAgent-X
1.1035
207.920
391.898
0.849
vLLM
0.6200
423.070
205.630
0.000
CachevLLM
0.8242
342.870
276.810
0.383
SearchAgent-2
1.0780
234.390
364.066
0.804
5
VLLM_ENN
0.7180
393,390
220.810
0.000
CachevLLM ANN
0.7566
383.490
236.660
0.250
SearchAgent-X
0.9570
282.085
302.049
0.716
Table 5: Generation Quality of SearchAgent-X X and Exact Retrieval.
Dataset
Musique
NQ
2Wiki
HotpotQA
Bamboogle
StrategyQA
Avg.
Retrieval Counts
Exact Retrieval
3.247
2.288
3.126
2.702
2.440
2.496
2.717
SearchAgent-X
3.251
2.292
3.138
2.699
2.448
2,476
2.717
Output Length
Exact Retrieval
8125
5839
7575
6840
6152
6402
6822
SearchAgent-X
8134
5847
7600
6839
6151
6382
6826
Throughput (Reg/Sec)
Token Throughput (TokenolSac)
Latency
Prefix Cacha Rale
0.8
0.6
150
100
0.4
N/A 2
8
N/A
12
N/A
8
12
N/A 2
12
Prianty Schoduling Leval
Friority Scheduling Level
Prioniy Schaduling Level
Prionity Schaduling Level
Figure 10: Comparison of Different Priority Levels G on Musique dataset. The numbers on the X-axis represent different priority scheduling levels; N/A indicates that priority scheduling is used.
Throughpul (Reg/ec)
Throughout
Laterry (5)
Prefi
300
0.8
250
200
1.5
100
1.0
150
0.2
NIA
NIA
N6A Prionty
Priorty
Scheduling
Prtontt Scheolling Leva
Figure 11: Comparison of Different Priority Levels G on HotpotQA dataset. The numbers
the X-axis represent different priority scheduling levels; N/A indicates that priority scheduling is not used.
19

---

Published as a conference paper at ICLR 2026
Table 6: System performance under different concurrency for vL.LM and SearchAgent-
Concurrency
10
50
100
200
300
400
500
Cache Hit Rate
VLLMLANN
0.131
0.065
0.088
0.135
0.168
0.173
0.173
0.177
SearchAgent-X
0.999
0,920
0.920
0.920
0.920
0.589
0.555
0.495
End-to-End Latency
VLLM_ANN
2181.75
633.37
477.88
448.64
437.12
425.89
415.44
411.67
SearchAgent-X
1378.82
323.21
212.05
199.29
208.07
295.39
314.80
327.87
Throughput
vLLM ANN
0.190
0.604
0.782
0.843
0.853
0.865
0.862
0.865
SearchAgent-X
0.203
0.848
1.348
1.517
1.582
1.137
1.100
1.060
C.4
COMPARISON OF DIFFERENT PRIORITY LEVELS G
The performance of SearchAgent is insensitive its priority level setting. The priority level G' mentioned in Section 3.2 is an important hyperparameter of our method. In this section, we conduct an ablation study to evaluate the performance of SearchAgent-X with different priority levels G. The evaluation is performed on the Musique and HotpotQA datasets using the Search-RI RI 7B model in offline scenarios. We set G = 2, 4, 6, 8, 10, and 12, and compare them with the baseline without priority scheduling (N/A). The results are shown in Figure 10. We note that the performance of SearchAgent-XX is not sensitive to the choice of G. and all efficiency metrics (including throughput, token throughput, latency, and prefix cache hit rate) first improve and then stabilize after G This is expected because the average retrieval number of the 7B model is within 4 and 6, while the primary objective of priority scheduling is to distinguish requests with different retrieval numbers for effective management.
We further validate this observation on the HotpotQA dataset. As shown in Figure 11, the efficiency consistently improves as G' increases (e.g., up to 1.62 throughput gain), and stabilizes once G 2 6. This again confirms that the performance of SearchAgent is not sensitive to the choice of G, making it straightforward to tune across different settings.
C.5 COMPARISON OF DIFFERNET CONCURRENCY SETTINGS
SearchAgent-X consistently outperforms baselines across different concurrency levels. To explore the impact of concurrency levels on system performance, we conduct an analysis to validate the effecttivnness of SearchAgent-x under explicitly controlled request concurrency by tuning key parameters: iteration-level concurrency (maz num seq) in vLLM (Kwon et al., 2023). The evaluation is conducted on the Musique dataset using the Search-R1 7B model in offline scenarios.
As detailed in Table 6, when increasing concurrency from to 500, SearchAgent- maintains a high cache hit rate up around 200. Beyond that point, the cache hit rate drops more significantly. Meanwhile, system efficiency first increases then declines, showing a turning point: latency is minimized around concurrency 100, and throughput peaks at concurrency = 200. This suggests that the GPU becomes saturated or experiences resource contention when concurrency exceeds 300. In practice, we typically choose the default value 256, which yields performance close to the optimal. The results demonstrate that SearchAgent-2 consistently outperforms vLLM in both throughput and latency while exhibiting tradeoff between cache hit rate and concurrency. We also observe that vLLM consistently suffers from low cache hit rates and lower system efficiency compared to SearchAgent- across concurrency levels. This because suboptimal scheduling and retrieval under interleaved cessoning-eetrieval retrieval workloads, where cache for previous tokens is frequently evicted-ever even with relatively small concurrency- causing inefficient reuse.
C.6 COMPARISON WITH A NAIVE EARLY-STOPPING BASELINE
SearchAgent-2 X aligns stopping decisions with the LLM's prefill/decode progress, making the stop decision more timely and effective. In contrast, naive early-stopping approaches make halting
20

---

Published as a conference paper at ICLR 2026
Table 7: Performance comparison of vanilla early stop and SearchAgent-X's Non-Stall Retrieval.
Method
Throughput (req/sec)
Latency (sec)
Cache Hit Rate
Accuracy
Vanilla HNSW
0.7872
661.85
0.412
0.15
Early Stop
0.8050
634.77
0.564
0.15
SearchAgent-X X
0.9502
620.07
0.645
0.15
Table 8: Comparison of system efficiency under the NSW search engine.
TopK
Method
Throughput
Latency
Token Throughput
Cache Hit Rate
vLLM ENN
0.7880
395.040
97.640
0.000
CachevLLM
1.7401
173.026
216.970
0.666
SearchAgent-X
2.1270
129.862
265.690
0.891
4
VLLM_ENN
0.7196
578.940
99.487
0.000
CachevLLM
1.0706
285.390
147.590
0.350
SearchAgent-X
1.6560
172.340
227.730
0.864
5
vLLM ENN
0.6940
428.642
87.531
0,000
CachevLLM ANN
0.8959
333.206
115.081
0.281
SearchAgent-X
1.1402
241.234
146.360
0.690
decisions based exclusively on retrieval-side signals, such machine learning model that predicts the "maturity" of retrieval, while disregarding the state of LLM inference. To further validate the effectiveness of SearchAgent-X* non-stall retrieval, we conduct a comparison against a vanilla early-stop baseline that only relies on retrieval status to decide the stopping point. The evaluation conducted on the Musique dataset using the Search-RI 7B model with Top-5 retrieval in offline scenarios. Table 7 shows SearchAgent-> outperforms vanilla HNSW and the early-stop baseline. Early-stop baseline (Li et al., 2020) boosts throughput by 2.26% and cache hit rate by 0.152, cutting latency by 27.08 sec while keeping accuracy at 0.15. SearchAgent -X further increases throughput by 18.04% and cache hit rate by 0.081, reducing latency by 14.70 sec, with accuracy unchanged at 0.15. This confirms the efficiency gains of SearchAgent X's non-stall retrieval via aligned LLM scheduling and retrieval.
C.7 SCALABILITY TO OTHER RETRIEVAL METHODS
To further validate the generalizability of our method, we implemented and evaluated on an alternative retrieval backend, NSW (Malkov et al., 2014), which is another widely-used approximate search method. The experiments are conducted on Musique dataset in offline scenarios using Search-R1 7B model. As shown in Table 8, our method boosts the throughput of the NSW-base -bsdded system by up to 2.7x and the cache hit rate by 2.46x, while reducing latency by 3.04x. These results confirm that method is robust across retrieval strategies and design is compatible with any iterative retriever, including cluster- (e.g., IVF (Johnson et al., 2021)) 1) and graph-based (e.g., HNSW (Malkov & Yashunin, 2018)) methods.
D DISCUSSION
D.1 APPLICABILITY
Other Inference Engines Our implementation of SearchAgent-X is direct modification of vLLM. We therefore compare against yLLM-based baselines so that all systems share the same serving stack (PagedAttention,, batching logic, etc.), avoiding interference with the performance observations from unrelated optimizations. However, The proposed optimization techniques are not specific to vLL.. SeanchAgent-X only assumes: 1) token-level generation scheduling, and FCFS (or
21

---

Published as a conference paper at ICLR 2026
FCFS-likes base policy that can be overridden. SGLang also adopts token-level generation scheduling and an FCFS-style policy, so SearchAgent-X can be integrated into SGLang with minimal changes for system improvement.
Beyond Graph-Based ANN For non-graph indices such as IVF or PQ-based methods, we treat probing additional clusters codebook entries as units of search effort and apply the same maturity- based stopping rule; in large-scale industrial deployments it is common to tune these parameters to trade recall against latency (Wang al., 2021; Ren al., 2025), making SearchAgent-X readily applicable in such environments.
Search APIs
While non-stall retrieval assumes controllable local searches, is still possible to initiate concurrent requests to search APIs with multiple different search parameters, and do non-stall retrieval with an asynchronous manner as our compatible extension.
D.2 FUTURE EXTENSIONS
Our priority-award aware scheduling and non-stall retrieval mechanisms offer natural starting point for coordinating across agents, for example by: 1) introducing agent-level priorities or budgets, and 2) propagating these priorities to the shared SearchAgent-X scheduler.
Multi-Agents
The core ideas of SearchAgent-X, including balancing retrieval accuracy and system efficiency, priority- aware scheduling, and allocating "just enough" tool-use effort, can be applied broadly any scenario with multi-round, dynamically autonomous tool invocations.
Other Tools
E THE USE OF LARGE LANGUAGE MODELS
We the large language model for proofreading and language refinement for this paper. The LLM's contribution is confined to improving grammar and prose; all research concepts and results are the original work of the authors.
22


Reviews:
[{"review_id": "Sq0U9lo171", "reviewer": "Reviewer_3XfA", "summary": "This paper investigates efficiency bottlenecks in LLM-based search agents, which dynamically interleave reasoning and retrieval during generation. The authors identify that both exact and coarse retrieval hurt performance and the framework is highly sensitive to retrieval latency. To address this, the authors propose SearchAgent-X, which features high-recall approximate retrieval, priority-aware scheduling and non-stall retrieval.", "questions": "- Can the proposed non-stall retrieval mechanism degrade answer quality when retrieval terminates too early?\n- Could priority scheduling introduce starvation or fairness issues under high request concurrency?\n- How would the framework adapt to multi-agent environments, where multiple reasoning agents interact concurrently?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and easy to follow.\n- The paper shows the non-monotonic relationship between retrieval accuracy and efficiency.\n- Components (priority scheduling, non-stall retrieval) in SearchAgent-X are well-motivated.\n- Comprehensive ablation studies demonstrate robustness of the proposed method.", "weaknesses": "- The baselines do not include recent LLM serving framework like SGLang.\n- The priority discretization thresholds and non-stall retrieval maturity criterion involve heuristic settings without extensive sensitivity analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BJTEL7U2GF", "reviewer": "Reviewer_PMHy", "summary": "This paper systematically investigates the efficiency bottlenecks of LLM-based search agents and uncovers several insights: (1) retrieval accuracy exhibits a non-monotonic relationship with end-to-end efficiency; (2) search agents are extremely sensitive to retrieval latency, where minor delays can lead to an 83× latency magnification effect; and (3) traditional FCFS scheduling results in low KV-cache utilization. Based on these findings, the paper proposes SearchAgent-X, a system that optimizes search agents through high-recall approximate retrieval, priority-aware scheduling, and a non-stall retrieval mechanism. Experiments demonstrate that the system achieves up to 3.4× higher throughput and 5× lower latency while maintaining generation quality.", "questions": "1. The paper mentions that efSearch=500 may lead to unstable recall. What is the specific performance degradation across different benchmarks?\n2. How does SearchAgent-X perform on tasks of varying difficulty? What are the latency and throughput improvements over baselines across different tasks?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. With the rise of DeepResearch-related work, the paper systematically studies efficiency issues in this emerging scenario, offering significant practical significance and application value.\n2. Through empirical studies, the paper discovers many noteworthy phenomena. It provides a deep analysis of the root causes of search agent latency, supported by extensive experiments.\n3. Priority scheduling avoids complex weight tuning through discretization, while non-stall retrieval adaptively terminates based on retrieval maturity. Both techniques are easy to implement and model-agnostic.", "weaknesses": "1. The main improvements stem from the high reusability of KV-cache, which works for the Search-R1 pattern. However, some current search agents modify historical context to handle overly long retrieval trajectories (e.g., summarizing previous context or keeping only recent k rounds of retrieval results), which could render the priority-aware scheduling completely ineffective.\n2. Priority-aware scheduling cannot be applied to commercial models (e.g., GPT), and the non-stall retrieval mechanism cannot be used to retrieve APIs (e.g., Google). These limitations make the application scenarios quite restricted (local LLM, knowledge base retrieval, KV-cache constrained, Search-R1 pattern).\n3. Lack of generalization discussion across different knowledge bases and tasks. For more challenging tasks or models that require more retrieval iterations, many designs in this paper—such as concurrency levels, priority level G, and maturity thresholds—may require substantial adjustments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JOE41S4oHP", "reviewer": "Reviewer_eCQa", "summary": "This paper presents SearchAgent-X, an inference framework for Large Language Model (LLM)-based search agents that incorporate priority-aware scheduling and non-stall retrieval. The design is based on the observation that both excessively high and excessively low retrieval accuracy degrade efficiency. SearchAgent-X improves the throughput by 1.3-3.4x", "questions": "- In Section 2.2, what model and dataset did you use, and what was the configuration of the inference engine (e.g., batch size)?\n- In Figure 2a, I cannot see how the latency increases by 83x. I only observe the end-to-end latency rising from around 180s to 240s. Also, why are the data points so coarse-grained (e.g., no points between retrieval latencies of 1s and 4s)?\n- In Figure 2b, what is d_i​? How is the scheduling performed here (is it rescheduled after each retrieval step)? Also, how can a non-FCFS policy solve this issue? For example, even if we prioritize request a over request b, wouldn’t that still lead to a cache miss for request b?\n- In Figure 2c, what is the latency overhead caused by retrieval-induced stalls? If scheduling is done at the iteration level and chunked prefill is used, I think this overhead should be small.\n- Section 4.1 mentions using two models from Search-R1 and ReCall, but the figures do not specify which model was used.\n- In Section 4.3, it compares the advantages of prefix caching for top-k=5 and top-k=1, but where is the data for top-k=1?\n- Section 4.3 mentions that non-stall retrieval reduced end-to-end latency by 41s, but it is unclear which data this refers to.\n- It seems that most of the performance benefit comes from priority scheduling, and I think it is not limited to search-based agents. I wonder if this technique can be generalized to other types of LLM agents that use external tools.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The proposed method achieves good latency/throughput improvement while preserving the accuracy of search agents.", "weaknesses": "- No discussion about the previous efficiency optimization method for RAG with multiple rounds of retrievals, including [1-3]\n- The non-stall early termination strategy in Section 3.3 seems inconsistent with the retrieval-induced stalls in Section 2.2.2. It is unclear how this optimization resolves the stall caused by being late for the LLM generation steps.\n- The paper contains several unclear points. See the questions below.\n\n### References\n\n- [1] https://arxiv.org/abs/2502.20969\n- [2] https://arxiv.org/abs/2503.14649\n- [3] https://arxiv.org/abs/2505.07833", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rOPtud7VRj", "reviewer": "Reviewer_pjDb", "summary": "This paper addresses the significant system efficiency bottlenecks in LLM-based search agents, which operate by dynamically interleaving reasoning (generation) and retrieval. The authors first analyze the sources of inefficiency, demonstrating a non-monotonic relationship between retrieval accuracy and end-to-end efficiency. They find that both exact search (high retrieval overhead) and low-recall approximate search (high reasoning overhead) are suboptimal, showing high-recall approximate search is the best compromise.\n\nSecond, they diagnose a \"cascading latency\" problem in existing systems (like vLLM) caused by two primary factors: (1) Improper scheduling, where standard FCFS policies fail to optimize for search-agent workloads, leading to poor KV-cache utilization; and (2) Retrieval-induced stalls, where timing misalignments between asynchronous retrieval and generation steps force requests to wait, resulting in cache evictions and costly recomputation.\n\nTo address these challenges, the authors propose SearchAgent-X, a high-efficiency inference framework. SearchAgent-X introduces two main techniques: A priority-aware scheduler that replaces FCFS. It prioritizes requests based on context length, retrieval count, and waiting time to maximize KV-cache reuse. A non-stall retrieval mechanism, an adaptive early-termination strategy for ANN search. This strategy monitors retrieval \"maturity\" and synchronizes the search termination with the LLM engine's readiness, thus eliminating stalls.\n\nExperiments show that SearchAgent-X significantly outperforms baselines, achieving up to 3.4x higher throughput and 5x lower latency while maintaining the generation quality of exact-retrieval systems.", "questions": "see weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper tackles a critical and timely problem. As agentic systems that interact with external tools become more common, their inference efficiency is a major bottleneck. This is a strong systems-level contribution.\n- The analysis in Section 2.2 is a key contribution. The identification of the non-monotonic efficiency curve (Figure 1) is a clear insight. The decomposition of latency amplification into \"improper scheduling\" and \"retrieval-induced stalls\" (Figure 2) is clear, well-illustrated, and clearly motivates the solution.\n- The solutions are sound and well-motivated.\nThe priority-aware scheduler is a smart improvement over FCFS, as it explicitly models the value of a request's KV-cache prefix.\nThe non-stall retrieval mechanism is the most novel part. It's not just naive early stopping; it's a true co-design where the retrieval component's behavior is dynamically adapted based on the generation engine's state. This tight coupling is a key insight.\n- The experiments are comprehensive and convincing.\nThe system is benchmarked against strong baselines (vLLM with ENN, vLLM with ANN, and vLLM+Cache+ANN).\nThe evaluation covers both offline and online serving scenarios, showing it's robust.", "weaknesses": "- The priority scheduling mechanism (Section 3.2) feels a bit heuristic. It relies on discretizing three metrics ($R_i, C_i, W_i$) into $G$ levels and assigning priority based on whether any metric exceeds a threshold (Eq. 2). The logic seems sensitive to the thresholds $T_{M,k}$, and the logic for combining these metrics isn't deeply explored. \n\n\n- The non-stall retrieval mechanism (Section 3.3) depends on retrieval maturity and \"the readiness of the LLM engine.\" The implementation of this \"readiness\" signal is critical but vague. Algorithm 1 (line 9-11) abstractly mentions CheckExternalNonStallSignal() when the LLM Engine has waiting requests. How is this practically implemented?  \n\n- The non-stall retrieval mechanism is tested on HNSW and NSW, which are iterative, graph-based ANN methods. The \"retrieval maturity\" concept is tied to this iterative process. It's unclear how this would apply to other major ANN algorithms (e.g., PQ, IVF) that aren't iterative in the same way. I am curious what are the search solution in real-world industry like perplexity", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)