# ParallelSearch: Train your LLMs to Decompose Query and Search Sub-queries in Parallel with Reinforcement Learning

arXiv: https://arxiv.org/abs/2508.09303 · HTML: https://mlsanity.com/paper/2508.09303/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 43 references that are in the map.
- First posted on arXiv 12 Aug 2025.

## Builds on (most cited first, 30 of 37)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [Retrieval-Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2312.10997/) (2023)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [SimPO: Simple Preference Optimization with a Reference-Free Reward](https://mlsanity.com/paper/2405.14734/) (2024)
- [Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions](https://mlsanity.com/paper/2212.10509/) (2022)
- [MuSiQue: Multihop Questions via Single-hop Question Composition](https://mlsanity.com/paper/2108.00573/) (2021)
- [ORPO: Monolithic Preference Optimization without Reference Model](https://mlsanity.com/paper/2403.07691/) (2024)
- [A Survey of Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2312.14925/) (2023)
- [MultiHop-RAG: Benchmarking Retrieval-Augmented Generation for Multi-Hop Queries](https://mlsanity.com/paper/2401.15391/) (2024)
- [Iterative Reasoning Preference Optimization](https://mlsanity.com/paper/2404.19733/) (2024)
- [Large Language Models in Finance: A Survey](https://mlsanity.com/paper/2311.10723/) (2023)
- [Spurious Rewards: Rethinking Training Signals in RLVR](https://mlsanity.com/paper/2506.10947/) (2025)
- [ZeroSearch: Incentivize the Search Capability of LLMs without Searching](https://mlsanity.com/paper/2505.04588/) (2025)

## Built on by (most cited first, 26 of 26)

- [SKILL0: In-Context Agentic Reinforcement Learning for Skill Internalization](https://mlsanity.com/paper/2604.02268/) (2026)
- [Flash-Searcher: Fast and Effective Web Agents via DAG-Based Parallel Execution](https://mlsanity.com/paper/2509.25301/) (2025)
- [A Comprehensive Survey on Reinforcement Learning-based Agentic Search: Foundations, Roles, Optimizations, Evaluations, and Applications](https://mlsanity.com/paper/2510.16724/) (2025)
- [Native Parallel Reasoner: Reasoning in Parallelism via Self-Distilled Reinforcement Learning](https://mlsanity.com/paper/2512.07461/) (2025)
- [A Survey on Parallel Reasoning](https://mlsanity.com/paper/2510.12164/) (2025)
- [InfoFlow: Reinforcing Search Agent Via Reward Density Optimization](https://mlsanity.com/paper/2510.26575/) (2025)
- [HyperEyes: Dual-Grained Efficiency-Aware Reinforcement Learning for Parallel Multimodal Search Agents](https://mlsanity.com/paper/2605.07177/) (2026)
- [Erase to Improve: Erasable Reinforcement Learning for Search-Augmented LLMs](https://mlsanity.com/paper/2510.00861/) (2025)
- [Beyond the limitation of a single query: Train your LLM for query expansion with Reinforcement Learning](https://mlsanity.com/paper/2510.10009/) (2025)
- [GlobalRAG: Enhancing Global Reasoning in Multi-hop Question Answering via Reinforcement Learning](https://mlsanity.com/paper/2510.20548/) (2025)
- [Beyond Single Embeddings: Capturing Diverse Targets with Multi-Query Retrieval](https://mlsanity.com/paper/2511.02770/) (2025)
- [EvoFSM: Controllable Self-Evolution for Deep Research with Finite State Machines](https://mlsanity.com/paper/2601.09465/) (2026)
- [Hybrid Deep Searcher: Scalable Parallel and Sequential Search Reasoning](https://mlsanity.com/paper/2508.19113/) (2025)
- [Beyond Outcome Reward: Decoupling Search and Answering Improves LLM Agents](https://mlsanity.com/paper/2510.04695/) (2025)
- [MoRA: Missing Modality Low-Rank Adaptation for Visual Recognition](https://mlsanity.com/paper/2511.06225/) (2025)
- [Rethinking On-policy Optimization for Query Augmentation](https://mlsanity.com/paper/2510.17139/) (2025)
- [In-Context Reinforcement Learning for Tool Use in Large Language Models](https://mlsanity.com/paper/2603.08068/) (2026)
- [Planner-Centric Reinforcement Learning for Deep Research with Structure-Aware Reward](https://mlsanity.com/paper/2605.30824/) (2026)
- [Windsock is Dancing: Adaptive Multimodal Retrieval-Augmented Generation](https://mlsanity.com/paper/2510.22694/) (2025)
- [A Picture of Agentic Search](https://mlsanity.com/paper/2602.17518/) (2026)
- [Plan Before Search: Search Agents Need Plan](https://mlsanity.com/paper/2605.28354/) (2026)
- [SubSearch: Intermediate Rewards for Unsupervised Guided Reasoning in Complex Retrieval](https://mlsanity.com/paper/2604.07415/) (2026)
- [LatentRAG: Latent Reasoning and Retrieval for Efficient Agentic RAG](https://mlsanity.com/paper/2605.06285/) (2026)
- [CAS: Conformalized Agentic Search via Adaptive Retrieval and Policy Weighting](https://mlsanity.com/paper/2608.20771/) (2026)
- [The Value of Being Wrong: Self-Mined Visual In-Context Learning from Errors](https://mlsanity.com/paper/2610.16977/) (2026)
- [CASI: Credit Assignment via Set Intervention for Agentic Retrieval](https://mlsanity.com/paper/2610.20293/) (2026)

## Abstract (arXiv)

Reasoning-augmented search agents such as Search-R1, trained via reinforcement learning with verifiable rewards (RLVR), demonstrate remarkable capabilities in multi-step information retrieval from external knowledge sources. These agents address the limitations of their parametric memory by dynamically gathering relevant facts to address complex reasoning tasks. However, existing approaches suffer from a fundamental architectural limitation: they process search queries strictly sequentially, even when handling inherently parallelizable and logically independent comparisons. This sequential bottleneck significantly constrains computational efficiency, particularly for queries that require multiple entity comparisons. To address this critical limitation, we propose ParallelSearch, a novel reinforcement learning framework that empowers large language models (LLMs) to recognize parallelizable query structures and execute multiple search operations concurrently. Our approach introduces dedicated reward functions that incentivize the identification of independent query components while preserving answer accuracy through jointly considering correctness, query decomposition quality, and parallel execution benefits. Comprehensive experiments demonstrate that ParallelSearch outperforms state-of-the-art baselines by an average performance gain of 2.9% across seven question-answering benchmarks. Notably, on parallelizable questions, our method achieves a 12.7% performance improvement while requiring only 69.6% of the LLM calls compared to sequential approaches.