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

• URL: http://arxiv.org/abs/2508.09303v1
• Date: Tue, 12 Aug 2025 19:38:21 GMT
• Title: ParallelSearch: Train your LLMs to Decompose Query and Search Sub-queries in Parallel with Reinforcement Learning
• Authors: Shu Zhao, Tan Yu, Anbang Xu, Japinder Singh, Aaditya Shukla, Rama Akkiraju,
• Abstract summary: Reasoning-augmented search agents such as Search-R1 demonstrate remarkable capabilities in multi-step information retrieval from external knowledge sources.<n>Existing approaches suffer from a fundamental architectural limitation: they process search queries strictly sequentially, even when handling inherently parallelizable and logically independent comparisons.<n>We propose ParallelSearch, a novel reinforcement learning framework that empowers large language models to recognize parallelizable query structures and execute multiple search operations concurrently.
• Score: 20.11646932754985
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• When should I search more: Adaptive Complex Query Optimization with Reinforcement Learning [26.489185170468062]
  We propose a novel RL framework called Adaptive Complex Query Optimization (ACQO)<n>Our framework is designed to adaptively determine when and how to expand the search process.<n>ACQO achieves state-of-the-art performance on three complex query benchmarks, significantly outperforming established baselines.
  arXiv  Detail & Related papers  (2026-01-29T03:16:53Z)
• Rethinking On-policy Optimization for Query Augmentation [49.87723664806526]
  We present the first systematic comparison of prompting-based and RL-based query augmentation across diverse benchmarks.<n>We introduce a novel hybrid method, On-policy Pseudo-document Query Expansion (OPQE), which learns to generate a pseudo-document that maximizes retrieval performance.
  arXiv  Detail & Related papers  (2025-10-20T04:16:28Z)
• Beyond the limitation of a single query: Train your LLM for query expansion with Reinforcement Learning [23.104182075898297]
  Reasoning-augmented search agents, such as Search-R1, are trained to reason, search, and generate the final answer iteratively.<n>We train an LLM-based search agent with the native capability of query expansion through reinforcement learning.<n>With the assistance of the squeezer model, we discover that even a small-scale 3B LLM can demonstrate a strong capability of query expansion.
  arXiv  Detail & Related papers  (2025-10-11T04:23:30Z)
• AceSearcher: Bootstrapping Reasoning and Search for LLMs via Reinforced Self-Play [45.02121903138421]
  AceSearcher trains a single large language model (LLM) to alternate between two roles: a decomposer that breaks down complex queries and a solver that integrates retrieved contexts for answer generation.<n>Experiments on three reasoning-intensive tasks across 10 datasets show that AceSearcher outperforms state-of-the-art baselines, achieving an average exact match improvement of 7.6%.
  arXiv  Detail & Related papers  (2025-09-29T02:14:30Z)
• Reasoning-enhanced Query Understanding through Decomposition and Interpretation [87.56450566014625]
  ReDI is a Reasoning-enhanced approach for query understanding through Decomposition and Interpretation.<n>We compiled a large-scale dataset of real-world complex queries from a major search engine.<n> Experiments on BRIGHT and BEIR demonstrate that ReDI consistently surpasses strong baselines in both sparse and dense retrieval paradigms.
  arXiv  Detail & Related papers  (2025-09-08T10:58:42Z)
• Hybrid Deep Searcher: Integrating Parallel and Sequential Search Reasoning [57.78245296980122]
  We introduce HDS-QA (Hybrid Deep Search QA), a dataset automatically generated from Natural Questions.<n>It comprises hybrid-hop questions that combine parallelizable independent subqueries (executable simultaneously) and sequentially dependent subqueries (requiring step-by-step resolution)<n>We name the model HybridDeepSearcher, which outperforms state-of-the-art baselines across multiple benchmarks.
  arXiv  Detail & Related papers  (2025-08-26T15:15:17Z)
• Reinforcement Fine-Tuning for Reasoning towards Multi-Step Multi-Source Search in Large Language Models [7.719379471690927]
  Reasoning-Search (R-Search) is a single-LLM search framework that unifies multi-step planning, multi-source search execution, and answer synthesis.<n>R-Search structure the output into four explicitly defined components, including reasoning steps that guide the search process.
  arXiv  Detail & Related papers  (2025-06-10T02:09:57Z)
• Iterative Self-Incentivization Empowers Large Language Models as Agentic Searchers [74.17516978246152]
  Large language models (LLMs) have been widely integrated into information retrieval to advance traditional techniques.<n>We propose EXSEARCH, an agentic search framework, where the LLM learns to retrieve useful information as the reasoning unfolds.<n>Experiments on four knowledge-intensive benchmarks show that EXSEARCH substantially outperforms baselines.
  arXiv  Detail & Related papers  (2025-05-26T15:27:55Z)
• Reinforcing Compositional Retrieval: Retrieving Step-by-Step for Composing Informative Contexts [67.67746334493302]
  Large Language Models (LLMs) have demonstrated remarkable capabilities across numerous tasks, yet they often rely on external context to handle complex tasks.<n>We propose a tri-encoder sequential retriever that models this process as a Markov Decision Process (MDP)<n>We show that our method consistently and significantly outperforms baselines, underscoring the importance of explicitly modeling inter-example dependencies.
  arXiv  Detail & Related papers  (2025-04-15T17:35:56Z)
• Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning [50.419872452397684]
  Search-R1 is an extension of reinforcement learning for reasoning frameworks.<n>It generates search queries during step-by-step reasoning with real-time retrieval.<n>It improves performance by 41% (Qwen2.5-7B) and 20% (Qwen2.5-3B) over various RAG baselines.
  arXiv  Detail & Related papers  (2025-03-12T16:26:39Z)
• LLM-assisted Vector Similarity Search [0.0]
  This paper explores a hybrid approach combining vector similarity search with Large Language Models (LLMs) to enhance search accuracy and relevance.<n> Experiments on structured datasets demonstrate that while vector similarity search alone performs well for straightforward queries, the LLM-assisted approach excels in processing complex queries involving constraints, negations, or conceptual requirements.
  arXiv  Detail & Related papers  (2024-12-25T08:17:37Z)
• Retrieval with Learned Similarities [2.729516456192901]
  State-of-the-art retrieval algorithms have migrated to learned similarities.<n>We show that Mixture-of-Logits (MoL) can be realized empirically to achieve superior performance on diverse retrieval scenarios.
  arXiv  Detail & Related papers  (2024-07-22T08:19:34Z)
• JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
  Join order selection (JOS) is the problem of ordering join operations to minimize total query execution cost. We present JoinGym, a query optimization environment for bushy reinforcement learning (RL) Under the hood, JoinGym simulates a query plan's cost by looking up intermediate result cardinalities from a pre-computed dataset.
  arXiv  Detail & Related papers  (2023-07-21T17:00:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.