TRACE: Trajectory Selection for Parallel Scaling of Search Agents

Qisheng Zhou; Zhen Xiong; Qiaoyu Tan

cs.LGSep 30, 2026

TRACE: Trajectory Selection for Parallel Scaling of Search Agents

Authors: Qisheng Zhou, Zhen Xiong, Qiaoyu Tan

Organizations: New York University Shanghai · New York University

Abstract

Parallel search may generate a correct answer that final-answer voting fails to select. We formulate this consolidation stage as trajectory selection and introduce TRACE (Trajectory Ranking with Aggregated Cross-Rollout Evidence), a lightweight learned selector that ranks completed trajectories using the search evidence behind their answers. TRACE preserves individual query and evidence occurrences, connects rollouts through shared content or document identity, and propagates information across these relations. Each candidate answer then reads the updated states of its own trajectory, preserving retrieval provenance while incorporating evidence from related rollouts. Trained with answer-level supervision over frozen text embeddings, TRACE returns an existing answer without additional search or autoregressive aggregation. One selector per search setting transfers across rollout policies and agent backbones without agent-specific fine-tuning, improving over voting across six WebQA policies and six long-horizon dataset-backbone combinations at $K=16$ . On Qwen2.5-14B Base/SFT WebQA pools, TRACE achieves 45.2/49.2% EM, compared with 43.9/48.0% for the strongest Qwen3-32B generative aggregators. On long-horizon FRAMES, GAIA, and BrowseComp, it reaches 78.6% average accuracy, exceeding majority voting by 3.1 percentage points. On Base WebQA pools, TRACE with only 8 rollouts comes within 0.4 points of majority voting over 64. TRACE also achieves at least $10\times$ higher processing throughput than SolAgg, SummAgg, and AggAgent across all seven WebQA benchmarks. These results show that reusing cross-rollout search evidence provides an effective and efficient alternative to heavyweight generative aggregation for parallel search. Code is available at https://github.com/Jaasssoooonnnnn/TRACE.

Figures & tables

Figure 1: TRACE selects one answer from

K

completed search trajectories. It first constructs an occurrence-preserving query–evidence graph, connecting trajectories through identical chunks in WebQA or shared documents in long-horizon browsing. A relation-specific GNN propagates information across these links. Each candidate answer then queries the updated Subquery/Evidence states of its own trajectory through a shared answer-conditioned QFormer and receives a selection score. The highest-scoring existing answer is returned without additional search or autoregressive generation. Graphs are schematic; WebQA’s Query node and some within-rollout edges are omitted for clarity.

	NQ		HotpotQA		TriviaQA		PopQA		2Wiki		MuSiQue		Bamboogle		Overall
Method	Base	SFT	Base	SFT	Base	SFT	Base	SFT	Base	SFT	Base	SFT	Base	SFT	Base	SFT
Single rollout	29.4	41.4	27.6	36.8	49.6	64.2	35.2	38.6	24.6	31.4	10.4	18.4	31.2	45.6	29.5	38.8
Majority Voting	44.6	46.6	40.4	46.8	63.8	72.2	46.0	46.2	40.8	46.2	18.4	22.4	48.8	59.2	42.6	47.2
Weighted Voting	44.4	46.6	40.6	47.2	64.8	72.6	46.0	46.2	41.6	45.6	19.0	22.4	48.8	60.0	43.0	47.3
Fewest Tools	36.0	45.0	30.2	42.6	58.2	71.2	39.4	43.4	26.0	41.0	9.6	20.2	32.8	57.6	33.2	44.4
SolAgg	43.2	43.4	42.6	49.0	65.0	72.4	45.0	46.4	45.8	48.6	19.6	25.0	52.8	60.8	43.9	48.0

Table 1: WebQA EM (%) at

K=16

with Qwen2.5-14B Base and SFT rollouts. SolAgg, SummAgg, and AggAgent use Qwen3-32B. Overall is question-weighted within each rollout policy. Bold marks the best result in each column.

	BrowseComp-Plus		FRAMES		GAIA
Method	OR	OSS	OR	OSS	OR	OSS	Avg.
Single rollout	38.3	45.2	73.1	84.9	55.4	61.7	59.7
Majority Voting	64.5	66.0	88.4	90.4	66.0	77.7	75.5
Weighted Voting	64.5	70.2	88.4	90.6	67.0	79.6	76.7
Fewest Tools	64.6	72.7	86.0	89.0	51.5	76.7	73.4
SolAgg	67.0	71.4	88.6	89.0	66.0	77.7	76.6

Table 2: Long-horizon accuracy (%). Single rollout reports mean Pass@1 over 16 samples; other rows use

K=16

. OR and OSS denote OpenResearcher-30B-A3B and gpt-oss-120B rollouts. All generative aggregators use Qwen3-32B. Bold marks the best result in each column.

Configuration	WebQA	Long-horizon avg.
Full TRACE	45.2	78.6
w/o cross-rollout communication	43.9	72.7
w/o GNN	43.7	75.5
Fixed-query readout	44.7	75.6

Table 3: Mechanism ablations at

K=16

. WebQA reports EM (%).

Figure 2: Final-answer performance with fixed TRACE checkpoints as the rollout budget increases. (a) 2Wiki EM with Qwen2.5-14B Base rollouts. (b) BrowseComp-Plus accuracy with gpt-oss-120B rollouts. Dashed curves show majority voting; brackets mark TRACE gains at

K=16

Method	GPU-hours $\downarrow$	Relative cost
TRACE	0.271	$1\times$
SolAgg	3.28	$12\times$
SummAgg	32.96	$122\times$
AggAgent	69.93	$258\times$

Table 4: Post-rollout runtime on the 3,125-question SFT WebQA pool. All LLM aggregators use Qwen3-32B. GPU-hours use H20s; relative cost is normalized to TRACE.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Task	Matching rule	Groups	Occurrence pairs			Graphs (%)
		Mean	Mean	Median	P90
WebQA	Identical chunk	7.6	243.6	228	430	99.9
Browsing	Identical evidence	15.4	462.0	314	1,080	99.0
Browsing	Same document	6.5	1,797.6	1,142.5	4,224	99.0

Appendix

Table A.1: Cross-rollout sharing at

K=16

. Groups and occurrence pairs are counted within each question graph. “Graphs” is the percentage containing at least one such pair.

Occurrence representation
Configuration	WebQA	Long-horizon avg.
Full TRACE	45.2	78.6
Merge identical evidence occurrences	44.1	77.1
Merge identical answers	44.9	76.3
Merge both	44.4	76.4
Answer readout and training

Appendix

Table B.1: Additional design comparisons at

K=16

. Columns report WebQA EM and long-horizon average accuracy (%), using the same aggregation as Table 3 . Dashes denote unevaluated comparisons.

	WebQA		Long-horizon avg.
$K$	EM	F1	TRACE	Majority	Pass@ $K$
1	28.5	36.4	59.7	59.7	59.7
2	35.2	43.9	67.8	65.5	72.2
4	40.2	48.8	71.5	69.7	80.1
8	43.3	51.8	75.3	73.8	86.1
16	45.2	53.4	78.6	75.5	90.9

Appendix

Table C.1: Budget-scaling results (%). WebQA: TRACE EM/F1 on Qwen2.5-14B Base rollouts through

K=32

. Long-horizon: accuracy through

K=16

Policy	1	2	4	8	16	32	64
Q2.5-7B Base	24.9	35.3	44.8	52.6	58.6	63.4	67.4
Q2.5-14B	30.5	40.1	48.0	54.3	59.3	63.6	67.3
SearchR1 RL	43.7	46.5	48.8	50.6	52.1	53.3	54.2
Q2.5-32B	30.5	39.7	47.6	54.2	59.4	63.6	67.4
Q3-32B	36.1	43.8	50.0	54.7	58.5	61.7	64.2
SFT (7B)	36.3	43.4	49.4	54.4	58.5	62.1	65.3

Appendix

Table D.1: Question-weighted Pass@

K

(%) for the policies in the parallel-search study.

	Qwen2.5-7B rollouts			Qwen2.5-14B rollouts
Method	Base	SFT	RL	Base	SFT	RL
Single rollout	24.6	36.6	44.0	29.5	38.8	46.9
Majority Voting	38.1	46.0	45.1	42.6	47.2	47.6
Weighted Voting	38.5	46.1	45.3	43.0	47.3	47.7
Fewest Tools	27.2	42.0	45.3	33.2	44.4	47.1
SolAgg	42.4	48.1	46.5	43.9	48.0	48.5

Appendix

Table E.1: WebQA EM (%) at

K=16

across six rollout policies, weighted by question count over the seven datasets. SolAgg, SummAgg, and AggAgent use Qwen3-32B. Bold marks the best result in each column.

	NQ		HotpotQA		TriviaQA		PopQA		2Wiki		MuSiQue		Bamboogle		Overall
Method	Base	SFT	Base	SFT	Base	SFT	Base	SFT	Base	SFT	Base	SFT	Base	SFT	Base	SFT
Single rollout	29.4	41.4	27.6	36.8	49.6	64.2	35.2	38.6	24.6	31.4	10.4	18.4	31.2	45.6	29.5	38.8
Majority Voting	44.6	46.6	40.4	46.8	63.8	72.2	46.0	46.2	40.8	46.2	18.4	22.4	48.8	59.2	42.6	47.2
Weighted Voting	44.4	46.6	40.6	47.2	64.8	72.6	46.0	46.2	41.6	45.6	19.0	22.4	48.8	60.0	43.0	47.3
Fewest Tools	36.0	45.0	30.2	42.6	58.2	71.2	39.4	43.4	26.0	41.0	9.6	20.2	32.8	57.6	33.2	44.4
SolAgg	43.2	43.4	42.6	49.0	65.0	72.4	45.0	46.4	45.8	48.6	19.6	25.0	52.8	60.8	43.9	48.0

Appendix

Table F.1: WebQA EM (%) with Qwen3-32B generative aggregation at

K=16

with Qwen2.5-14B Base and SFT rollouts. SolAgg, SummAgg, and AggAgent use Qwen3-32B. Overall is question-weighted within each rollout policy. Bold marks the best result in each column.

Stage	Seconds
Read and parse candidate texts	23.6
Fresh text encoding	905.2
Assemble tensors and construct graphs	38.2
Score and extract answers	7.2
Total	974.2

Appendix

Table H.1: Measured TRACE runtime on one H20 for the full 3,125-question pool. Text embeddings are recomputed, not loaded from a previous run.

Explore similar work

Jun 15, 2026cs.AI

Beyond Parallel Sampling: Diverse Query Initialization for Agentic Search

Test-time scaling for agentic search typically increases depth (i.e., more turns and tokens per trajectory) or breadth (i.e., more parallel rollouts). Here we focus on breadth scaling, showing that standard parallel sampling yields diminishing returns, tracing this to query redundancy at the first turn. When models issue similar first queries across rollouts, the threads retrieve overlapping evidence, and subsequent turns are conditioned on this shared retrieval. We address this limitation with DivInit, a training-free intervention at the first turn. Rather than sampling k independent first queries, DivInit draws n candidates from a single call, picks k < n diverse seeds, and runs them as parallel trajectories. Across five open-weight models and eight benchmarks, DivInit consistently improves over standard parallel sampling, with average gains of five to seven points on multi-hop QA at matched compute. Code available at https://github.com/cxcscmu/diverse-query-initialization

Sidhaarth Murali, João Coelho, Jingjie Ning +3

Carnegie Mellon University, United States · Instituto Superior Técnico and INESC-ID, University of Lisbon, Portugal · NOVA LINCS, NOVA School of Science and Technology, Portugal

Agentic Search Queries Agentic

Ask PDF

May 15, 2026cs.CL

Argus: Evidence Assembly for Scalable Deep Research Agents

Deep research agents have achieved remarkable progress on complex information seeking tasks. Even long ReAct style rollouts explore only a single trajectory, while recent state of the art systems scale inference time compute via parallel search and aggregation. Yet deep research answers are composed of complementary pieces of evidence, which parallel rollouts often duplicate rather than complete, yielding diminishing returns while pushing the aggregation context toward the model's limit. We propose Argus, an agentic system in which a Searcher and a Navigator cooperate to treat deep research as assembling a jigsaw from complementary evidence pieces, rather than brute forcing the whole answer in parallel. The Searcher collects evidence traces for a given sub-query through ReAct-style interaction. The Navigator maintains a shared evidence graph, verifying which pieces are still missing, dispatching Searchers to gather them, and reasoning over the completed graph to produce a source-traced final answer. We train the Navigator with reinforcement learning to verify, dispatch, and synthesize, while independently training the Searcher to remain a standard ReAct agent. The resulting Navigator supports rollouts with a single Searcher or many in parallel without retraining. With both Searcher and Navigator built on a 35B-A3B MoE backbone, Argus gains 5.5 points with a single Searcher and 12.7 points with 8 parallel Searchers, averaged over eight benchmarks. With 64 Searchers it reaches 86.2 on BrowseComp, surpassing every proprietary agent we benchmark, while the Navigator's reasoning context stays under 21.5K tokens.

Zhen Zhang, Liangcai Su, Zhuo Chen +7

MiroMind AI

Deep Research

Ask PDF

Sep 11, 2026cs.CL

SearchAtlas: Analyzing Agentic Search Strategies via Evidential Query Graphs

LLM search agents are often evaluated on final-answer accuracy, overlooking the process. Analyzing a search strategy requires understanding how credible evidence is retrieved to address question constraints. This valuable information is buried in raw search trajectories that are long and difficult to parse. We introduce SearchAtlas, a framework that converts search trajectories into structured graphs whose edges represent how evidence is propagated across the reasoning trace, from the query that retrieves it to the final answer. Our automated parsing pipeline achieves a mean edge F1 of 86.0% against human-annotated graphs and remains consistent across repeated runs. We analyze five search agents on three benchmarks, revealing systematic differences in search scale and evidence aggregation. SearchAtlas exposes fragmented answer support, question constraints that do not reach the answer, and unverified parametric knowledge entering the response. These process failures are strongly associated with incorrect answers, even more so than an LLM judge given either the raw trajectory or the ordered query list, suggesting that the constructed graphs provide useful interpretability. Moreover, an audit of cases in which process-diagnostic scores disagree with final-answer correctness shows that they capture information not reducible to answer accuracy.

Jiacheng Sang, Mengyuan Li, Sanxing Chen +3

Duke University · University of Pennsylvania

Agentic Search Queries Answer Atlas

Ask PDF