PaperlayerView exact revision on arXiv

Source-linked AI summary

TRACE: Trajectory Selection for Parallel Scaling of Search Agents

Qisheng Zhou, Zhen Xiong, Qiaoyu Tan

arXiv:2609.39912v1cs.LGcs.AI

TL;DR

Parallel search can produce a correct answer that final-answer voting fails to select, leaving systems to consolidate completed rollouts. TRACE selects an existing trajectory using cross-rollout evidence while retaining retrieval provenance. Across WebQA and long-horizon search, it improves over voting and is competitive with or stronger than generative aggregation.

  • Problem

    Parallel search can yield successful trajectories, but consolidation must choose which of K completed rollouts to return.

    Source: §1 · p. 1

  • Method

    TRACE preserves query and evidence occurrences, propagates information across rollouts linked by shared evidence, and scores existing candidates using their own updated trajectory states.

    Source: §1 · p. 2

  • Results

    Across WebQA and long-horizon search, TRACE improves over voting and is competitive with or stronger than Qwen3-32B generative aggregation; it reaches 78.6% average accuracy, 3.1 points above majority voting.

    Source: §4.2 · p. 7, §5 · p. 10

  • Takeaways & Limitations

    Post-rollout consolidation can be decoupled from trajectory generation and handled by a lightweight, transferable selection module.

    Source: §5 · p. 10

Abstract

from arXiv · show

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.

1 INTRODUCTION

Parallel search can produce successful trajectories, but systems still need to choose which completed rollout to return. TRACE treats consolidation as trajectory selection, using shared search evidence while preserving each rollout’s retrieval context.

Motivation

  • Parallel scaling samples multiple completed trajectories, creating a consolidation problem: choosing which rollout to return when their queries, sources, reasoning paths, and answers differ.Search trajectories can share evidence retrieved through different subqueries, but merging repeated observations would erase their query and retrieval context.Source: §1 · pp. 1–2

Existing approaches

  • Voting uses final-answer agreement, verifiers often score candidates independently, and generative aggregators add another autoregressive reasoning stage after search.TRACE instead uses cross-rollout evidence while selecting an existing candidate.Source: §1 · pp. 1–2

Approach

  • TRACE preserves query and evidence occurrences, connects rollouts through shared chunks or documents, and scores each candidate using its own trajectory states updated by related searches.It returns an existing answer without additional search or autoregressive synthesis.Source: §1 · p. 2

Results

  • At K = 16, TRACE improves over voting across six WebQA policies and long-horizon search, reaching 78.6% average accuracy, 3.1 points above majority voting.On Qwen2.5-14B Base/SFT WebQA pools, TRACE achieves 45.2/49.2% EM versus 43.9/48.0% for the strongest generative aggregators.Source: §1 · p. 2

Transfer and efficiency

  • One selector per search setting transfers across rollout policies and agent backbones without generator-specific fine-tuning, and TRACE with 8 Base WebQA rollouts comes within 0.4 points of 64-rollout majority voting.The selector is trained with answer-level correctness supervision over frozen text embeddings and does not modify the search agent.Source: §1 · p. 2

2 RELATED WORK

Prior work scales search through parallel rollouts and consolidates their outputs through voting or generative aggregation. TRACE relates to this literature through its use of completed trajectories, candidate selection, and graph-structured evidence, while differing in how it connects rollouts and scores candidates.

Parallel scaling and trajectory aggregation

  • Parallel search extends test-time scaling to tool-augmented trajectories; consolidation includes answer-level voting and generative aggregation, while TRACE selects one existing candidate.AggAgent uses another language-model agent to synthesize an answer, and ParallelMuse reuses information across parallel search paths (Li et al., 2025).Source: §2 · pp. 2–3

Verification and candidate selection

  • Best-of-N methods and learned verifiers use outcome- or process-level supervision, but most score candidates independently from their answer or reasoning trace.TRACE instead makes trajectory quality relational, allowing one rollout’s score to depend on evidence encountered by others.Source: §2 · p. 3

Graph-structured evidence reasoning

  • Prior graphs organize evidence or reasoning dependencies in QA and LLM reasoning, whereas TRACE preserves query and evidence occurrences across completed search trajectories.It links rollouts through shared chunk or document identity for message passing without merging away retrieval provenance.Source: §2 · p. 3

3 TRACE: TRAJECTORY SELECTION WITH CROSS-ROLLOUT EVIDENCE

TRACE selects an existing trajectory by propagating information across shared evidence while retaining each search and evidence occurrence. It then reads the updated states of that trajectory and trains the selector using answer-level correctness supervision.

3.1 PROBLEM SETUP AND OVERVIEW

  • Given completed trajectories, TRACE selects one retained candidate rather than generating another answer, using cross-rollout evidence while preserving each occurrence’s query and retrieval context.A relational GNN propagates information across within-trajectory and shared-evidence relations; the final decision remains trajectory-specific.Source: §3.1 · p. 3

3.2 OCCURRENCE-PRESERVING QUERY–EVIDENCE GRAPH

  • The graph keeps repeated searches and observations as distinct nodes, linking identical WebQA chunks directly and long-horizon observations through shared document identities.In browsing, the Evidence–Doc–Evidence path shares information across observations without merging them.Source: §3.2 · pp. 3–4

3.3 CROSS-ROLLOUT EVIDENCE PROPAGATION

  • A relation-specific GraphSAGE encoder updates Subquery and Evidence states, propagating information independently of candidate answers.Matching WebQA chunks exchange information in one hop, while browsing observations communicate through a shared Doc node in two hops.Source: §3.3 · p. 5

3.4 ANSWER-CONDITIONED TRAJECTORY READOUT

  • Each candidate answer attends to updated process states from its own trajectory, which retain local retrieval provenance while carrying information from related rollouts.Candidate conditioning enters at the answer-conditioned readout, not during graph message passing.Source: §3.4 · p. 5

3.5 LEARNING TO SELECT

  • TRACE learns from answer-level correctness labels using candidate-level binary cross-entropy, a listwise objective, and a hard-ranking objective.Training updates the selector components while keeping the text embedding model and rollout-generating policy fixed, allowing use with different generators.Source: §3.5 · p. 6

4 EXPERIMENTS

The experiments evaluate TRACE across WebQA and long-horizon search, testing transfer, mechanism, rollout-budget scaling, and post-rollout cost. Across settings, TRACE improves on voting, while ablations and budget sweeps probe how its evidence-sharing design performs.

4.1 EXPERIMENTAL SETUP

  • The evaluation covers seven WebQA datasets and three long-horizon benchmarks, using six WebQA rollout policies and two long-horizon generators.Selectors are trained on mixed correct/incorrect candidate pools, with WebQA K = 16 training trajectories and existing 16-trajectory long-horizon pools.Source: §4.1 · pp. 6–7
  • Comparisons include voting heuristics, Fewest Tools, and Qwen3-32B generative aggregators; rollout policies and text embeddings remain frozen during selector training.The implementation trains for three epochs and selects one checkpoint by validation performance for rollout-budget sweeps.Source: §4.1 · p. 7

4.2 MAIN RESULTS: EFFECTIVE AND TRANSFERABLE TRAJECTORY SELECTION (RQ1, RQ2)

  • 78.6% average long-horizon accuracy and 45.2%/49.2% WebQA EM show TRACE’s gains across benchmarks and rollout policies.On WebQA, it exceeds majority voting by 2.6 points on Base pools and scores 49.2% versus 47.2% on SFT; on long-horizon search it is best, including ties, in five of six settings.Source: §4.2 · p. 7, Table 1 · p. 7, Table 2 · p. 8

4.3 MECHANISM ANALYSIS (RQ3)

  • Removing cross-rollout communication lowers WebQA EM from 45.2% to 43.9% and long-horizon accuracy from 78.6% to 72.7%, the largest drop among main ablations.The ablation holds pools, embeddings, supervision, and optimization budget fixed; other controls remove the GNN or replace the answer-conditioned query.Source: Table 3 · p. 8, §4.3 · p. 8

4.2 MAIN RESULTS: EFFECTIVE AND TRANSFERABLE TRAJECTORY SELECTION (RQ1, RQ2)

  • TRACE beats the strongest Qwen3-32B generative aggregator by 1.3/1.2 points on WebQA Base/SFT and 1.6 points on long-horizon search.TRACE selects an existing candidate, whereas the generative baselines synthesize a new response.Source: Table 1 · p. 7, §4.2 · p. 8, Table 2 · p. 8

4.3 MECHANISM ANALYSIS (RQ3)

  • Occurrence-merging controls score 44.1/77.1, 44.9/76.3, and 44.4/76.4 (WebQA/long-horizon), while evidence-link controls favor source identity for long-horizon passage connections.Doc links alone yield 78.6% long-horizon accuracy, versus 76.5% for content links alone, 76.9% for Doc plus content, and 71.1% with neither; removing content-identity links lowers WebQA EM to 43.8%.Source: §4.3 · pp. 8–9

4.4 SCALING AND EFFICIENCY (RQ4)

  • A fixed checkpoint stays above majority voting for every K ≥2; WebQA EM rises from 35.2% at K = 2 to 45.2% at K = 16 and 46.3% at K = 32.On Base pools, TRACE at K = 8 reaches 43.3% EM, close to majority voting’s 43.6% at K = 64.Source: §4.4 · p. 9, Figure 2 · p. 9
  • 0.271 H20 GPU-hours process all 3,125 SFT WebQA questions, versus 3.28 for SolAgg, 32.96 for SummAgg, and 69.93 for AggAgent.The comparison covers post-rollout processing, including fresh text encoding, graph construction, and trajectory selection.Source: Table 4 · p. 9, §4.4 · p. 9

5 CONCLUSION

The conclusion presents TRACE as a lightweight selector that uses cross-rollout graph propagation and answer-conditioned readout to choose an existing candidate. It reports consistent gains over voting across WebQA policies and long-horizon search evaluations.

5 CONCLUSION

  • TRACE combines cross-rollout graph propagation with answer-conditioned readout to select an existing candidate without additional search or autoregressive aggregation.It preserves retrieval occurrences and connects trajectories through shared evidence.Source: §5 · pp. 9–10
  • One selector per search setting improves over voting across six WebQA rollout policies and BrowseComp-Plus, FRAMES, and GAIA evaluations.The conclusion describes the selector as transferable and lightweight.Source: §5 · p. 10
  • The paper concludes that post-rollout consolidation can be decoupled from trajectory generation and handled by a selection module.Source: §5 · p. 10

AI USE STATEMENT

The authors report using ChatGPT and Codex to create and edit code and to edit the manuscript for readability.

AI USE STATEMENT

REPRODUCIBILITY STATEMENT

The reproducibility statement directs readers to the paper’s model, objectives, optimization settings, and supplementary implementation and evaluation details. It also identifies the public code repository.

REPRODUCIBILITY STATEMENT

A.1 CANDIDATE POOLS AND METRICS

The appendix specifies how candidate pools, baselines, shared-evidence statistics, and TRACE’s encoder and readout are constructed. It also defines the evaluation metrics and aggregation rules used across WebQA and long-horizon search.

A.1 CANDIDATE POOLS AND METRICS

  • WebQA retains trajectories with answers and retrieved evidence, while browsing retains nonempty responses; invalid samples are not replaced, and question sets stay fixed across evaluation conditions.WebQA EM and token F1 normalize answers and take the best reference-alias match; long-horizon accuracy uses saved Qwen3-32B judgments. Long-horizon aggregates equally weight dataset–backbone pairs.Source: §A.1 · p. 13

A.2 BASELINES

  • Generative baselines use Qwen3-32B to synthesize answers, while weighted voting groups normalized answers and weights them by model-estimated confidence.SolAgg integrates solution texts, SummAgg summarizes interactions, and AggAgent accesses candidates through solution, trajectory-search, and segment tools.Source: §A.2 · pp. 13–14

A.3 GRAPH STATISTICS AND COUNTING UNITS

  • Cross-rollout sharing counts unordered occurrence pairs from content or source identities present in at least two rollouts, with table summaries reported across question graphs.The “Graphs” column is the percentage containing at least one such pair; means include graphs with zero shared groups, alongside medians and 90th percentiles.Source: §A.3 · p. 14, Table A.1 · p. 14
  • Browsing uses 235.6 directed Evidence–Doc edges per graph, and 74.3% of cross-rollout same-document pairs have different content identities.Unlike WebQA’s identical-content links, document incidence provides two-hop paths between same-source observations without forming an Evidence clique.Source: §A.3 · p. 14

A.4 ENCODER AND READOUT DETAILS

  • TRACE propagates information with relation-specific GraphSAGE, then uses each answer as a query over its rollout’s Subquery and Evidence states.Cross-trajectory messages travel directly between matching WebQA chunks or through Evidence–Doc–Evidence paths in browsing; the loss combines candidate-level, listwise, and hard-ranking objectives.Source: §A.4 · pp. 14–15

B ADDITIONAL ABLATIONS

The ablations compare TRACE’s occurrence representation, evidence links, and readout/training choices against the full model. The appendix also identifies the scope and protocol of fixed-checkpoint rollout-budget results.

B ADDITIONAL ABLATIONS

  • The controls removing cross-rollout messages, bypassing the GNN, or using a fixed attention query retain answer-frequency features and local readout membership.The controls use the same K = 16 pools, question splits, frozen embeddings, correctness supervision, and optimization budget as the full model.Source: B ADDITIONAL ABLATIONS · p. 15
  • 77.1%, 76.3%, and 76.4% long-horizon accuracy follow process merging, answer merging, and both, respectively, versus 78.6% for Full TRACE.The corresponding WebQA results are 44.1%, 44.9%, and 44.4%, versus 45.2%; process merging combines identical-content occurrences and their retrieval connections.Source: B ADDITIONAL ABLATIONS · p. 16
  • 71.1% long-horizon average accuracy results when both Doc and content links are removed, 7.4 points below Full TRACE; Doc-based TRACE reaches 78.6%.Direct content links alone reach 76.5%, while combining Doc and content links reaches 76.9%; removing all content-identity links gives 43.8% WebQA EM.Source: B ADDITIONAL ABLATIONS · p. 16
  • 75.8% and 75.1% long-horizon averages for graph readout and two-stage training trail the jointly trained TRACE result of 78.6%.The reported gains are 2.7 and 3.4 points; the fixed-query control retains attention while changing its query.Source: B ADDITIONAL ABLATIONS · p. 16

C SELECTION UNDER DIFFERENT ROLLOUT BUDGETS

  • The fixed-checkpoint budget table covers Qwen2.5-14B Base WebQA through K = 32 and long-horizon accuracy through K = 16.Long-horizon results equally weight six dataset–backbone combinations and use the same 500-question FRAMES subset at every budget.Source: C SELECTION UNDER DIFFERENT ROLLOUT… · p. 16, Table C.1 · p. 16

D POLICY-SAMPLING RESULTS

The policy-sampling appendix defines Pass@K from pools of 64 trajectories and describes the policies and evaluation scope. It distinguishes this Pass@1 estimate from the single-rollout references used elsewhere.

D POLICY-SAMPLING RESULTS

  • Pass@K is estimated from 64 trajectories per question, with the numerator set to zero when fewer than K incorrect trajectories remain.Pass@1 averages correctness over all 64 samples per question, whereas WebQA single-rollout references evaluate sample 0.Source: D POLICY-SAMPLING RESULTS · pp. 16–17
  • The Qwen2.5-7B and Qwen2.5-14B SFT policies train for three epochs on 3,083 successful search trajectories and are evaluated on 64 samples for each of 3,125 WebQA questions.SFT coverage uses all generated samples before selector filtering, and normalized empty predictions count as incorrect.Source: D POLICY-SAMPLING RESULTS · p. 17

E ADDITIONAL WEBQA ROLLOUT POLICIES

TRACE improves over voting across six WebQA rollout policies, while candidate filtering can limit the pool available for selection. The accompanying analysis distinguishes candidate coverage from successful selection and explains how voting can miss correct answers.

E ADDITIONAL WEBQA ROLLOUT POLICIES

  • At K = 16, TRACE improves over majority and weighted voting across all six WebQA rollout policies, with EM weighted by question count across seven datasets.Table E.1 reports WebQA EM with Qwen3-32B generative aggregators.Source: E ADDITIONAL WEBQA ROLLOUT POLICIES · p. 17, Table E.1 · p. 17
  • Mean overlap reaches 0.87 and 0.83 for 7B and 14B RL, versus 0.36 and 0.50 Base and 0.56 and 0.60 SFT; RL voting gains are 0.7 and 0.3 points.The passage links repetitive evidence to fewer distinct evidence contexts and says this reduced complementarity is consistent with smaller gains over voting.Source: E ADDITIONAL WEBQA ROLLOUT POLICIES · p. 17
  • Filtering excludes 27.2% of 7B Base samples and reduces questions with a correct candidate from 59.0% to 56.5%, yet TRACE gains 3.0 points over majority voting in the smaller pool.The pool averages 11.6 candidates per question; zero-search trajectories account for 18.1% at 7B versus 6.0% at 14B.Source: E ADDITIONAL WEBQA ROLLOUT POLICIES · pp. 17–18

F QWEN3-32B AGGREGATION ON WEBQA

  • On SFT rollouts, TRACE reaches 49.2% Overall EM, retaining the highest score against Qwen3-32B generative aggregators.SolAgg rises from 33.9% to 48.0%, SummAgg from 17.7% to 46.7%, and AggAgent from 29.3% to 43.6% when replacing Qwen2.5-14B with Qwen3-32B.Source: Table F.1 · p. 18, F QWEN3-32B AGGREGATION ON WEBQA · p. 18

G.1 PARALLEL SEARCH AND EVALUATION

  • Final-answer accuracy separates candidate coverage from selection success conditional on a correct answer being available.On fixed candidate pools, oracle accuracy is the fraction of questions containing a correct candidate; comparisons to this oracle concern selection from those pools, not new answer generation.Source: §G.1 · p. 18

G.2 POLICY CHOICE UNDER PARALLEL SEARCH

  • Across seven WebQA datasets, policy ordering changes with sampling budget; selection is learned from completed rollouts while holding the generating policy fixed.The passage says coverage must be paired with successful selection.Source: §G.2 · p. 18

G.3 A PROBABILISTIC VIEW OF THE COVERAGE–VOTING GAP

  • With rollout probabilities (0.2, 0.5, 0.3) and only the first class correct, coverage tends to one while majority-voting accuracy tends to zero.Under the stated i.i.d. finite-answer-class assumption, voting converges to the most probable class even when that class is incorrect.Source: §G.3 · p. 19

H EFFICIENCY MEASUREMENTS

The efficiency measurements profile TRACE's post-rollout processing and compare its runtime with generative aggregation pipelines, excluding rollout generation and correctness judging.

H EFFICIENCY MEASUREMENTS

  • The runtime study covers 3,125 WebQA questions, with 35,503 retained candidates across 2,939 nonempty pools from the first 16 samples.All questions remain in the denominator; rollout generation and correctness judging are excluded.Source: H EFFICIENCY MEASUREMENTS · p. 19
  • TRACE encodes 68,664 distinct node texts once with Qwen3-Embedding-8B; the frozen encoder accounts for most inference time.A three-epoch selector fit on 101,323 training questions takes 4.17 minutes on one H20 with precomputed embeddings, or 6.42 minutes including loading and setup.Source: H EFFICIENCY MEASUREMENTS · p. 19
  • With graph tensors reused, batched selector inference takes a median of 1.09 seconds over three measurements, including batching and device transfer.Model initialization adds 52.8 seconds to the reported runtime.Source: H EFFICIENCY MEASUREMENTS · p. 19
  • The Qwen3-32B SummAgg pipeline takes 59,322 seconds (16.5 hours) across summary generation, final integration, confidence scoring, and client scheduling.The measurement uses two H20s with tensor parallelism and excludes rollout generation and correctness judging.Source: H EFFICIENCY MEASUREMENTS · p. 19
  • SolAgg takes approximately 98.5 minutes (3.28 GPU-hours), SummAgg 32.96 GPU-hours, and AggAgent an estimated 69.93 GPU-hours.The AggAgent deployment estimate includes restarts and abnormal waits, with two unfinished questions counted as failures.Source: H EFFICIENCY MEASUREMENTS · p. 19

Related papers

Loading 2609.39912v1…