Contents

Beyond Parallel Sampling:
Diverse Query Initialization for Agentic Search

Sidhaarth Murali1, João Coelho1,2, Jingjie Ning1, João Magalhães3, Bruno Martins2, Chenyan Xiong1
1Language Technologies Institute, Carnegie Mellon University    2IST Lisboa / INESC-ID    3Universidade Nova de Lisboa
arXiv Paper Code
DivInit overview: standard parallel sampling collapses onto near-identical queries; DivInit enforces diversity at initialization.

More parallel threads should mean better coverage. In practice, they all issue the same first query — retrieve the same evidence — and fail together. We call this anchor collapse, and fix it with one training-free intervention: DivInit.

🔍 Introduction

Parallel agentic search runs k independent ReAct-style threads and aggregates their answers via pass@k. At temperature > 0, you would expect the threads to explore different regions of the evidence space. Instead, they issue near-identical turn-1 queries, retrieve overlapping documents, and arrive at correlated conclusions. Scaling the thread count amplifies this redundancy rather than resolving it.

We introduce DivInit — a single-intervention fix that requires no training, no reward model, and no additional search budget. One shared LLM call generates a pool of n candidate queries; greedy max-min Jaccard selection picks k maximally diverse seeds; each thread starts from its own seed. Everything from turn 2 onward is unchanged.

Across five open-weight models and eight benchmarks, DivInit improves pass@4 by +5–7 points on multi-hop QA at matched compute. Gains are consistent across models and scale with model capacity, pointing to a capability floor below which models cannot productively act on varied initializations.

🪝 Anchor Collapse

We measure turn-1 diversity using QPD (Query Pairwise Distance) — mean token-level Jaccard distance across all pairs of thread-1 queries. Standard parallel sampling consistently clusters at QPD ≈ 0.2 regardless of temperature. The distribution barely shifts as T increases: the problem is structural, not stochastic.

QPD density: standard threads cluster at low diversity; DivInit shifts distribution right.

Query diversity at turn 1. Standard parallel sampling (blue) concentrates at low QPD across all temperatures. DivInit (orange) shifts the distribution toward high diversity. Temperature tuning does not close the gap.

Turn-1 imprint: turn-1 QPD strongly predicts full-trajectory QPD.

Turn-1 diversity predicts full-trajectory diversity (ρ = 0.42 / 0.35). The first query is not one step among many — it imprints the entire trajectory. Standard threads cluster at low QPD throughout; DivInit separates them permanently.

Low turn-1 QPD is not cosmetic: it means threads retrieve the same documents at turn 1, reason over the same evidence, and fail for the same reasons. Correlated failures are irreducible by adding more threads — they are reduced only by breaking the correlation at its source.

⚡ DivInit

One intervention, at turn 1 only. No training, no reward model, no embeddings required.

1
Generate a pool of n candidate queries in a single shared LLM call. This is the only additional overhead DivInit introduces relative to a standard single-thread run.
2
Select k diverse seeds via greedy max-min Jaccard (MMR with λ = 0). Iteratively pick the candidate with the largest minimum Jaccard distance to the already-selected set. No model calls, no embeddings — milliseconds of token arithmetic.
3
Launch one thread per seed. Each thread issues its assigned seed as its turn-1 search query. From turn 2 onward, all threads run standard ReAct — DivInit is not involved again.
Standard: k × T  calls  (k independent turn-1 calls)
DivInit:  1 + k(T−1)  calls  (one shared pool call; k−1 fewer total)

With k = 4 threads and T = 8 turns, DivInit makes 29 LLM calls vs. 32 for standard parallel sampling. DivInit is strictly cheaper at matched thread count, not just competitively priced.

We compared greedy Jaccard against dense sentence-embedding selection (all-MiniLM-L6-v2) across pool sizes 8–64. Jaccard matches or outperforms dense selection at every pool size — for short, keyword-rich search queries, token overlap is a well-calibrated proxy for semantic similarity, and it requires no embedding model.

📊 Results

We evaluate pass@4 across five open-weight models (Qwen3-1.7B/4B/8B, Gemma3-4B/12B) and eight benchmarks: five multi-hop QA tasks (HotpotQA, MuSiQue, 2WikiMultihopQA, Bamboogle, FRAMES) and three open-web tasks (GAIA, HLE, WebWalker). All runs use k = 4 threads, pool size n = 16, and 8 turns per thread.

pass@k sweep: DivInit widens the gap as k increases.

pass@k vs. thread count. The gap widens as k grows — more threads amplify the benefit of diverse initialization.

Gain vs. model size: larger models benefit more from DivInit.

Gain scales with model capacity. Absolute pass@4 improvement (DivInit − Standard) per Qwen3 model size. Near-zero at 1.7B; largest at 8B.

DivInit improves pass@4 by +5–7 points on multi-hop QA at matched compute across all five models. Open-web gains are smaller but consistent. The capacity scaling pattern suggests a capability floor: small models may lack the reasoning depth to productively diverge from distinct starting points.

pass@4 (%) — Standard → DivInit

Multi-hop QA Open-Web
Model HpQA MuSi 2Wiki Bambo FRAMES Avg GAIA HLE WebWalker Avg
Qwen3-1.7B 42.9 → 43.8 14.5 → 15.6 37.6 → 41.5 16.8 → 24.3 13.1 → 13.6 25.0 → 27.8 — — — —
Qwen3-4B 41.9 → 53.2 15.9 → 19.7 41.9 → 49.0 32.5 → 40.8 15.5 → 20.4 29.5 → 36.6 22.7 → 27.8 9.7 → 14.3 38.7 → 44.9 23.7 → 29.0
Qwen3-8B 50.4 → 57.0 23.9 → 29.7 46.3 → 55.1 47.7 → 57.6 24.8 → 30.8 38.6 → 46.0 26.0 → 30.2 10.0 → 14.1 41.6 → 46.8 25.2 → 28.2
Gemma3-4B 40.0 → 49.2 17.2 → 16.1 42.8 → 52.2 27.7 → 37.9 12.3 → 14.7 28.0 → 34.0 — — — —
Gemma3-12B 54.9 → 59.1 31.6 → 36.1 52.0 → 53.9 55.7 → 64.3 31.0 → 37.5 45.0 → 50.2 34.0 → 35.0 12.7 → 14.8 38.0 → 45.2 28.2 → 31.6

Green = improvement; red = regression. Dashes: model not evaluated on open-web benchmarks (hardware constraints).

📄 BibTeX

If you find this work useful, please cite: 

@article{murali2026divinit,
  title     = {Beyond Parallel Sampling: Diverse Query Initialization
               for Agentic Search},
  author    = {Murali, Sidhaarth and Coelho, Jo{\~a}o and Ning, Jingjie
               and Magalh{\~a}es, Jo{\~a}o and Martins, Bruno
               and Xiong, Chenyan},
  year      = {2026},
  url       = {https://arxiv.org/abs/2606.17209},
  note      = {Preprint}
}