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

Beyond Parallel Sampling: Diverse Query Initialization for Agentic Search
Jun 15, 2026Sidhaarth Murali, João Coelho, Jingjie Ning +3Agentic Search Queries
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
Argus: Evidence Assembly for Scalable Deep Research Agents
May 15, 2026Zhen Zhang, Liangcai Su, Zhuo Chen +7Deep Research
MiroMind AI
SearchAtlas: Analyzing Agentic Search Strategies via Evidential Query Graphs
Sep 11, 2026Jiacheng Sang, Mengyuan Li, Sanxing Chen +3Agentic Search Queries
Duke University · University of Pennsylvania

Jun 15, 2026, cs.AIJ/K move · Enter open · S save

Beyond Parallel Sampling: Diverse Query Initialization for Agentic Search

Sidhaarth Murali, João Coelho, Jingjie Ning, João Magalhães+2

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

Open paper AskPDF arXiv

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

Abstract

Explore similar work

Beyond Parallel Sampling: Diverse Query Initialization for Agentic Search

Argus: Evidence Assembly for Scalable Deep Research Agents

SearchAtlas: Analyzing Agentic Search Strategies via Evidential Query Graphs