Query Decomposition for RAG: Balancing Exploration-Exploitation

Roxana Petcu, Kenton Murray, Daniel Khashabi, Evangelos Kanoulas, Maarten de Rijke, Dawn Lawrie, Kevin Duh · 2025

Read Query Decomposition for RAG: Balancing Exploration-Exploitation by Roxana Petcu, Kenton Murray, Daniel Khashabi, Evangelos Kanoulas, Maarten de Rijke, Dawn Lawrie, Kevin Duh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-18633.txt.

Introduction

Roxana Petcu and her six co-authors improve evidence gathering for hard questions. Their target is retrieval-augmented generation systems. Such systems split a request into sub-questions. They fetch documents for each one. They then merge the results into an answer. Fetch too broadly, and noise and cost pile up. Fetch too narrowly, and key material is missed. The authors frame that tension as a balance. One side explores new sub-questions. The other exploits ones already proving useful.

Framed so, the task becomes a bandit learning problem. Each fetched document updates a belief about a sub-question's value. That belief guides the next choice. Several bandit methods were tested. Judging relevance from rank data and human judgments worked best. Document-level precision rose by about thirty-five percent. A ranking quality measure rose by about fifteen percent. Long-form answers downstream improved as well.

Catalog record

CREATORRoxana Petcu, Kenton Murray, Daniel Khashabi, Evangelos Kanoulas, Maarten de Rijke, Dawn Lawrie, Kevin Duh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-18633

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Query Decomposition for RAG: Balancing Exploration-Exploitation Roxana Petcu, Kenton Murray, Daniel Khashabi, Evangelos Kanoulas, Maarten de Rijke, Dawn Lawrie, Kevin Duh Abstract Retrieval-augmented generation (RAG) systems address complex user requests by decomposing them into subqueries, retrieving potentially relevant documents for each, and then aggregating them to generate an answer. Efficiently selecting informative documents requires balancing a key trade-off: (i) retrieving broadly enough to capture all the relevant material, and (ii) limiting retrieval to avoid excessive noise and computational cost. We formulate query decomposition and document retrieval in an exploitation-exploration setting, where retrieving one document at a time builds a belief about the utility of a given sub-query and informs the decision to continue exploiting or exploring an alternative. We experiment with a variety of bandit learning methods and demonstrate their effectiveness in dynamically selecting the most informative sub-queries. Our main finding is that estimating document relevance using rank information and human judgments yields a 35% gain in document-level precision, 15% increase in α ​ -nDCG \alpha\text{-nDCG} , and better performance on the downstream task of long-form generation. Code is available on GitHub. 1 1 1 https://anonymous.4open.science/r/query-decomposition-bandits-2A0D 1 Introduction Complex user queries usually involve discourse operators such as the exclusion of information Zhang et al. 2025 , negation Petcu et al. 2025 ; Weller et al. 2024 ; van den Elsen et al. 2025 , or missing entities Qi et al. 2019 ; Bhargav et al. 2022 , and often require retrieving evidence found in multiple documents. One way to handle them is to decompose the request into atomic sub-queries Khot et al. 2023 , as shown in Figure 1 . Retrieving documents independently for each sub-query leads to coverage of complex information needs by maximizing recall. However, it may result in a large number of documents, of which many are irrelevant Kim et al. 2025 . This is problematic in two ways. First, too many documents cannot fit in the context window of an LLM, without being arbitrarily truncated, potentially removing vital information. Second, including a large proportion of irrelevant documents introduces noise in the generation Jin et al. 2024 . Mitigating these problems involves filtering by either human annotators or LLM agents. This motivates our core question: how to efficiently identify which sub-queries are likely to retrieve relevant information and what constitutes an appropriate retrieval depth for each sub-query ? Figure 1: A user request is first decomposed into sub-queries. Bandit learning iteratively selects a sub-query (arm), retrieves a document down its ranked list, observes its relevance, and updates the sub-query posterior belief over time. The selected documents across iterations are then used as evidence in a RAG setting to generate a grounded answer, balancing exploration (more sub-queries) and exploitation (more documents per sub-query). Existing approaches to sub-query decomposition and document retrieval lack a principled mechanism for allocating documents, with most methods retrieving a fixed number of documents regardless of sub-query utility. Meanwhile, we want to study a method that adaptively decides, under a fixed budget, whether to continue retrieving documents from an observed, promising sub-query or to explore alternatives that may yield more relevant evidence, while avoiding irrelevant overlap. A multi-armed bandit framework naturally captures this process: each sub-query is treated as an arm, for which each observed document provides evidence of its utility. Framing query decomposition and document selection as a bandit problem addresses two core challenges of complex information needs. First, retrieval is inherently sequential and budget-constrained, as it is impossible to verify all documents. Second, the relevance of a sub-query is initially uncertain, while our belief of its relevance builds with each retrieved document. Figure 1 illustrates our setting. We estimate the utility of each sub-query, modeled as an arm, by observing the relevance of one document at a time. The choice of assessment directly influences the cost. By estimating utility under a fixed budget, i.e., at each step the system makes a choice between going down the ranked list of a certain sub-query or retrieving from a new one, the process becomes considerably more efficient. This perspective is complementary to recent approaches on efficient selection under computational constraints, such as compute-efficient re-ranking ( Podolak et al. 2025 ) and training data selection ( Petcu and Maji 2024 ) . In the example shown in Figure 1 we assume access to a user request, its decomposition, document relevance (assessed by either LLM judges or human annotators), and a search engine We aim to answer the following research questions: (RQ1) How can query selection be framed as a multi-armed bandit problem? Does bandit learning outperform full exploitation and full exploration strategies? What strategies best balance exploration with exploitation? (RQ2) Does document selection using multi-armed bandits improve evaluation metrics on the downstream task of report generation? (RQ3) Can bandit learning be used to guide hierarchical sub-query decomposition? For answering RQ1, we model query decomposition and document retrieval in an efficient way using reinforcement learning (RL) policies in a multi-armed bandit setting, demonstrating that estimating Bernoulli distributions boosts relevance estimates by 17\% compared to simply going down the ranked list. With RQ2, we look into the performance of using an optimal subset of documents for report generation, in which we improve on evaluation metrics such as nugget coverage and sentence support. With RQ3, we examine the use of hierarchical, multi-level sub-query decomposition, which yields a 30\% precision gain over selecting all documents from a single-level decomposition. 2 Related Work RAG systems. RAG systems extend language models with access to external knowledge from retrieved evidence Lewis et al. 2021 ; Asai et al. 2020 ; Soudani et al. 2024 . While this approach brings advantages in grounding the generation into real information Askari et al. 2025 , it treats the query as a unitary piece of information. There are variants of RAG systems that handle complex queries, such as multi-step RAG systems which perform iterative retrieval Gu et al. 2025 , or feedback-based retrieval implemented with RLHF or model-estimated policies for re-generating the query until a satisfying answer can be composed by the system Deng et al. 2022 ; Rafailov et al. 2024 ; Jin et al. 2025 . This line of work follows earlier efforts in RL-based query reformulation Buck et al. 2018 , which have been extended to multi-modal and retrieval tasks Odijk et al. 2015 . Query decomposition . Research in discourse phenomena such as exclusion Zhang et al. 2025 , negation Weller et al. 2024 ; Petcu et al. 2025 , and compositions of logic operators Zhang et al. 2024 shows that such formulations are difficult to encode by retrieval models Krasakis et al. 2025 . These cases often benefit from decomposing the original request into simpler, unitary sub-queries Yao et al. 2023 . Query decomposition can be performed semantically using external models Khot et al. 2023 . However, naively splitting a complex query and retrieving documents for each sub-query does not necessarily improve results: longer contexts can degrade downstream performance Shao et al. 2025 . To address this, we propose an adaptive allocation of retrieval budgets across sub-queries. Research gap . We position our work at the intersection of query decomposition, using LLMs for unitary information needs, and efficient retrieval of documents by observing

Read the complete text