Search papers, labs, and topics across Lattice.
CMU MLNOVA LINCSNOVA School of Science and TechnologyUniversity of LisbonJun 15, 2026arXiv:2606.17209This paper investigates the limitations of standard parallel sampling in agentic search, particularly its diminishing returns due to query redundancy at the initial turn. The authors introduce DivInit, a novel approach that generates diverse initial queries from a single model call, allowing for more effective parallel rollouts. Their experiments across multiple models and benchmarks demonstrate that DivInit significantly enhances performance in multi-hop question answering, achieving average improvements of five to seven points while maintaining computational efficiency.
Diminishing returns in parallel sampling can be overcome by generating diverse initial queries, leading to substantial performance gains in multi-hop question answering.
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
