Trace improves parallel search accuracy and speed using trajectory ranking
TRACE: Trajectory Selection for Parallel Scaling of Search Agents
Machine LearningArtificial Intelligence
Summary
When many AI agents search for answers in parallel, simply voting on their final answers can miss the best one. The authors introduce TRACE, a smart method that looks at all the search paths and evidence behind answers to pick the best one. TRACE learns to connect related searches and share proof without extra searching or slow processing. This helps it pick better answers faster than older voting or generating new summaries. It works well across different AI setups and types of questions.
What this means in practice
- •For search system engineers: Enhance answer selection in parallel AI search systems by ranking trajectories using shared evidence for better accuracy without extra computation.
- •For enterprise ai developers: Improve large-scale question answering services by incorporating cross-rollout evidence aggregation to quickly choose the best response among multiple search attempts.
Authors
Qisheng Zhou, Zhen Xiong, Qiaoyu Tan
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.