The Scheduler Is a Hidden Retriever: How Asynchrony Shapes Evidence Acquisition in Search Agents

Ruiyang Ren; Yuhao Wang; Yinan Zhang; Chunyan Miao

Figure 1. Arrival timing redirects retrieval. Two recorded runs receive the same six documents in different orders. Each executes one search after the second arrival (shaded prefix). The highlighted film page identifies K. Subash, whose biography is absent from the packet. Both runs eventually identify him, but only the upper run acquires his death date. The question asks which of two films, The Coca-Cola Kid or Ayul Kaithi, has the director who died earlier. Two arrival sequences contain the same six original documents. Each sequence shows numbered document arrivals from one to six, with shading over the first two documents available at the search decision and dashed outlines for the later arrivals. The Ayul Kaithi film page is highlighted at arrival two in the upper sequence and arrival six in the lower sequence. In each row, an arrow branches from immediately after the second arrival into a search while the remaining documents are still in flight. In the upper path, the agent already knows the director's name and searches for K. Subash's death date, retrieving his biography. In the lower path, the director is not yet known, so the agent searches for the film's director and misses the biography. After all original documents arrive, both runs identify K. Subash. Only the upper path has his death date and correctly answers Ayul Kaithi; the lower path incorrectly answers The Coca-Cola Kid.

Figure 2. Acquisition differences persist after input completion (DeepSeek V4). Batch reads documents in fixed order; Notes updates on arrival. Fractions count received documents. Circles compare what the agent searches for (target categories); squares compare returned documents (Jaccard distance). Dashed lines connect early Notes to its unexecuted probe (shaded, hollow). Zero marks same-order repeat variation; bars show 95% CIs. Early Batch reports sets only; MuSiQue has no target categories. Four DeepSeek V4 panels in one row show 2Wiki compositional, 2Wiki bridge comparison, HotpotQA bridge, and MuSiQue. Five categorical conditions are grouped into complete-input controls, early decisions, and a follow-up probe. Batch reads received documents together in fixed order; Notes updates working notes in arrival order. Fractions count received original documents. Blue circles compare what the agent searches for, measured by disagreement between target categories. Orange squares compare the returned documents using Jaccard distance; early Batch reports sets only. MuSiQue has no target categories. The four first-decision conditions are independent comparisons. Dashed lines connect only early Notes to its follow-up probe, which retains the early action, notes, and any search feedback after all original documents arrive. Shading and hollow markers distinguish probes, whose queries imply retrieval sets without executing a second search or adding feedback. Zero denotes same-order repeat variation; bars are question-bootstrap 95 percent confidence intervals. Complete-input controls lie near repeat variation; early decisions and their probes retain excess disagreement.

Task ( $n$ )	Search demand		Search direction
Comp. (200)	$14.7$	$[12.4,\,17.1]$	$2.0$	$[0.8,\,3.4]$
Bridge (200)	$8.2$	$[6.2,\,10.3]$	$1.3$	$[0.2,\,2.4]$
HotpotQA (100)	$8.6$	$[5.4,\,11.9]$	$4.3$	$[0.6,\,8.1]$
MuSiQue (100)	$3.2$	$[0.3,\,6.2]$	$6.2$	$[2.9,\,9.6]$

Table 1. Search demand and direction remain schedule-sensitive after delivery (DeepSeek V4). Excess disagreement above same-order repeats (pp [95% CI]). Demand compares search/answer choices; direction compares retrieval sets when both runs search. Comp./Bridge denote 2Wiki tasks; eligible pairs: Appendix A .

	Incremental reasoning				Batch reasoning
Task	Runs with search	Searches finding support	Answer accuracy		Answer accuracy
DeepSeek V4
2Wiki: bridge comparison	$-10.1$	$+80.9$	$+30.3$	$[26.6,\,34.2]$	$-2.5$	$[-5.7,\,0.6]$
2Wiki: compositional	$-13.1$	$+54.8$	$+17.4$	$[13.1,\,21.7]$	$-4.4$	$[-7.1,\,-1.8]$
HotpotQA	$-25.1$	$+35.0$	$+3.6$	$[-1.1,\,8.3]$	$-8.9$	$[-13.1,\,-5.1]$
MuSiQue	$-24.2$	$+15.0$	$-1.1$	$[-3.6,\,1.5]$	$-5.5$	$[-8.2,\,-3.0]$

Table 2. Waiting makes searches more selective. Differences are complete-input minus early commitment (pp). Support recovery is the fraction of searches finding the withheld document; brackets give paired 95% CIs for accuracy.

Figure 3. Stable requests can still yield different acquisitions. In this deterministic example, evidence identifies a director and an actor but omits their birthplaces. The rows reverse request completion order. With one search slot, first-ready retrieves different biographies; CEA fixes priority before delivery and retrieves the director’s biography in both orders. Panel a shows two independent subquestions seeking the birthplaces of a director and an actor. Each forms a fixed search request after receiving its complete local evidence, which identifies the person but omits the birthplace. Panel b compares two alternative request completion orders, shown as rows, under a budget of one search. The first and second columns identify which request finishes first and second; these are not sequential reasoning steps. The remaining columns show the document retrieved by each allocation rule. When the director request finishes first, both rules retrieve the director biography, and CEA searches immediately without waiting for the actor request. When the actor request finishes first, first-ready allocation retrieves the actor biography, whereas CEA waits for the priority director request and retrieves the director biography. The local requests are unchanged, but first-ready retrieves different evidence across the two orders. CEA retrieves the same evidence while preserving independent local reasoning.

Figure 4. CEA evaluation. Panels (a,b) use GPT-5.6. (a) Acquisition disagreement with question-only plans under early commitment (2/6 arrivals), complete-input shared history (6/6), and CEA. Zero marks same-order repeat variation. (b) Mean input-token cost per run and accuracy with matched reasoning calls. CEA keeps subtask notes separate; Shared combines them. (c) Time saved against the same program waiting for all initial evidence (20 DeepSeek V4 and 100 GPT-5.6 questions). Whiskers show 95% CIs, paired in (c). Three panels evaluate CEA. Panel a compares acquisition disagreement under early commitment after two of six arrivals, complete-input shared history, and CEA across three benchmarks. Zero marks same-order repeat variation. Panel b separates input-token cost and answer accuracy into aligned columns with common method rows. CEA maintains separate notes for each subtask; the control shares notes across all subtasks. CEA uses 6,877 mean input tokens versus 11,505 for shared notes, with accuracies of 87.3 and 86.0 percent. Both token and accuracy estimates have 95 percent confidence intervals. Panel c shows the paired time saved by local execution against the identical CEA program delayed until all evidence arrives. Positive values mean earlier completion. The first subtask decision finishes about eight seconds earlier, while the final response saves between about one and two seconds. Gray diamonds denote DeepSeek V4 and blue circles GPT-5.6.

Allocation	Acq. (pp)	Acc. (%)	$\Delta$ Acq. (pp)
(a) One missing support: low contention
Fixed priority	$0.6$	$86.7$	—
First-ready	$0.7$	$87.3$	$+0.1$	$[-2.1,\,2.4]$
(b) Two missing supports: high contention
Fixed priority	$-0.5$	$74.5$	—
First-ready	$21.1$	$74.1$	$+21.6$	$[18.3,\,24.8]$

Table 3. CEA allocation ablation on 100 2Wiki bridge-comparison questions (GPT-5.6; one search slot). Acq. denotes acquisition contrast and Acc. denotes accuracy.

\Delta

is first-ready minus fixed [paired 95% CI].

Task	Early	Shared	CEA	$\Delta$ vs. Early (pp)
2Wiki	$38.5$	$47.9$	$51.1$	$+12.6$	$[6.4,\,18.9]$
HotpotQA	$38.9$	$42.0$	$42.5$	$+3.6$	$[0.3,\,7.1]$
MuSiQue	$26.8$	$25.8$	$26.8$	$-0.1$	$[-3.6,\,3.5]$

Table 4. Accuracy (%) with question-only plans (

n=100

per task). Early commits after two arrivals; Shared uses complete-input shared history.

\Delta

is CEA minus Early [paired 95% CI].

DeepSeek V4 / Bridge comparison $n=200$
Strategy	Search	Rec./S	Rec./all	Acc.	Strict	No alias
native@2	$93.91$	$14.04$	$13.19$	$59.53$	$49.09$	$59.53$
native@6	$83.84$	$94.93$	$79.59$	$89.84$	$77.53$	$89.84$
wait_all@2	$63.78$	$5.44$	$3.47$	$68.97$	—	—
wait_all@6	$0.03$	$100.0$ †	$0.03$	$66.44$	—	—
CEA (Batch)	$42.16$	$90.96$	$38.34$	$67.22$	$57.91$	$67.22$

Table E1. Strategy outcomes (%) and answer disagreement. Rec./S and Rec./all report recovery per search and over all runs; † one search. Strict removes normalization; No alias removes aliases. Centered is cross-order minus same-order disagreement [95% CI], treating NULL as a category. Dashes mark unreported values. Matched GPT contrasts use the replication in Table E2 .

Arrival profile	Local (s)	Barrier (s)	Saved (s)		Local (s)	Barrier (s)	Saved (s)
	DeepSeek V4 ( $n=20$ )				GPT-5.6 ( $n=100$ )
Simultaneous	$22.7$	$22.7$	$-0.1$	$[-1.4,\,1.4]$	$12.4$	$12.4$	$\phantom{+}0.0$	$[-0.2,\,0.3]$
Priority domain first	$40.6$	$42.0$	$+1.5$	$[-0.5,\,3.4]$	$30.9$	$32.3$	$+1.4$	$[0.9,\,1.9]$
Priority domain last	$40.3$	$42.5$	$+2.2$	$[0.7,\,3.6]$	$31.5$	$32.3$	$+0.8$	$[0.5,\,1.2]$
Fragmented	$40.2$	$42.5$	$+2.3$	$[1.4,\,3.2]$	$31.1$	$32.3$	$+1.2$	$[0.8,\,1.6]$
All profiles	$36.0$	$37.4$	$+1.5$	$[0.7,\,2.2]$	$26.5$	$27.3$	$+0.8$	$[0.6,\,1.0]$

Table E2. Same-program timing and matched GPT-5.6 controls. Saved time is barrier minus local [paired 95% CI]. Recovery is over all runs; calls and input tokens are means. Lower panels are separate matched comparisons.

Fixed-packet acquisition contrasts (pp)
Task	Native@2	Native@6	Batch@2	Batch@6
HotpotQA	$12.7$	$3.3$	$12.5$	$1.2$
MuSiQue	$11.7$	$1.3$	$11.2$	$0.1$

Table E3. GPT-5.6 acquisition and accuracy comparisons (

n=100

per task). Acq. denotes acquisition contrast, Acc. accuracy, and Batch wait_all .

\Delta

is CEA minus Shared [paired 95% CI].

The Scheduler Is a Hidden Retriever: How Asynchrony Shapes Evidence Acquisition in Search Agents

Abstract

Figures & tables

LLM Inference Scheduling

Before Agents Act: Assurance-Aware Semantic Scheduling for Evidence Acquisition in Distributed Systems

Harness-Search: Guiding Long-Horizon Search through Multi-Agent Coordination

Argus: Evidence Assembly for Scalable Deep Research Agents

Abstract

LLM Inference Scheduling

Explore similar work

Before Agents Act: Assurance-Aware Semantic Scheduling for Evidence Acquisition in Distributed Systems

Harness-Search: Guiding Long-Horizon Search through Multi-Agent Coordination

Argus: Evidence Assembly for Scalable Deep Research Agents