Elamur Research⌕
☰
home / papers / 2026 / Query Decomposition for RAG: Balancing Exploration-Exploitation

Query Decomposition for RAG: Balancing Exploration-Exploitation

Paper · 2026 · Roxana Petcu, Kenton Murray, Daniel Khashabi et al.

Summary

In RAG, complex requests are often split into sub-queries. Pulling a fixed number of documents for each one, however, floods the generator with irrelevant text and can overflow the context window. Petcu et al. treat the choice of which sub-query to read from, and how far down its ranked list to go, as a multi-armed bandit problem under a fixed document budget. Each sub-query is an arm, and the relevance of every inspected document updates a posterior belief about that arm's usefulness. The authors test Thompson sampling with Beta-Bernoulli rewards (binary relevance) and Gaussian rewards (score-based). They also try variants such as UCB, ϵ-greedy, rank-aware, top-k and diversity-oriented rewards, and extend the approach to hierarchical decompositions using correlated bandits. Experiments on NeuCLIR24 and ResearchyQuestions run offline, with relevance labels supplying the rewards. Combining rank information with human judgments works best: document-level precision rises by about 35%, α-nDCG by about 15%, and long-form report generation improves. The approach gives a principled way to spend a limited budget of relevance checks.

Key points

  • Formulation: sub-queries are arms, and each step reveals the next unseen document of the chosen arm. The budget b is smaller than N·K documents. Discrete rewards use Bernoulli distributions with flat Beta(1,1) priors, and continuous rewards use Gaussians.
  • Modeling Bernoulli rewards improves relevance estimates by about 17% over simply walking down the ranked list. Top-k Bernoulli variants (k = 3, 4, 5) beat the other reward types across budgets.
  • Hierarchical sub-query decomposition with correlated bandits gives roughly a 30% precision gain over taking all documents from a flat, single-level decomposition. In one reported comparison, Bernoulli top k = 5 gains 24% over the serialized setup, using n = 4, τ = 0.77 and λ = 0.91. These gains shrink as the budget increases.
  • In the downstream report-generation task, documents selected by the bandits improve nugget coverage and sentence support.
  • Limitations: rewards depend on the quality of the underlying retriever. Good budget choices depend on the dataset. NeuCLIR sub-queries are regenerated each time rather than fixed, which adds noise. Online use with clicks or LLM judges is left for future work.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Johns Hopkins UniversityBaltimore · United States240 works · 96,487 citations🎓University of AmsterdamAmsterdam · Netherlands144 works · 173,906 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksInformation Systems · 1,437 works

Cite

Cite as Roxana Petcu, Kenton Murray, Daniel Khashabi, Evangelos Kanoulas, Maarten de Rijke, Dawn Lawrie and Kevin Duh. 2026. Query Decomposition for RAG: Balancing Exploration-Exploitation. Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.eacl-long.322

@inproceedings{petcu2026query,
  title = {{Query Decomposition for RAG: Balancing Exploration-Exploitation}},
  author = {Roxana Petcu, Kenton Murray, Daniel Khashabi, Evangelos Kanoulas, Maarten {de Rijke}, Dawn Lawrie and Kevin Duh},
  booktitle = {Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.eacl-long.322},
  url = {https://doi.org/10.18653/v1/2026.eacl-long.322}
}

References

35 references, 7 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Akari Asai, Kazuma Hashimoto, Hannaneh Hajishirzi, Richard Socher, and Caiming Xiong. 2020. Learning to retrieve reasoning paths over wikipedia graph for question answering. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.n…
  2. Arian Askari, Roxana Petcu, Chuan Meng, Mohammad Aliannejadi, Amin Abolghasemi, Evangelos Kanoulas, and Suzan Verberne. 2025. Self-seeding and multi-intent self-instructing llms for generating intent-aware information-seeking dialogs. Preprint, arXiv:2402.11633. find
  3. Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, Binyuan Hui, Luo Ji, Mei Li, Junyang Lin, Runji Lin, Dayiheng Liu, Gao Liu, Chengqiang Lu, Keming Lu, and 29 others. 2023. Qwen technical report. Preprint, arXiv:2309.16609.
  4. Samarth Bhargav, Georgios Sidiropoulos, and Evangelos Kanoulas. 2022. ‘It’s on the tip of my tongue’: A new dataset for known-item retrieval. In WSDM ’22: The Fifteenth ACM International Conference on Web Search and Data Mining, Virtual Event / Tempe, AZ, USA, February 21 - 25, 2022, pages 48–56. AC… find
  5. Christian Buck, Jannis Bulian, Massimiliano Ciaramita, Wojciech Gajewski, Andrea Gesmundo, Neil Houlsby, and Wei Wang. 2018. Ask the right questions: Active question reformulation with reinforcement learning. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Cana… find
  6. Charles L.A. Clarke, Maheedhar Kolla, Gordon V. Cormack, Olga Vechtomova, Azin Ashkan, Stefan Büttcher, and Ian MacKinnon. 2008. Novelty and diversity in information retrieval evaluation. In Proceedings of the 31st Annual International ACM SI-GIR Conference on Research and Development in Information… find
  7. Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric P. Xing, and Zhiting Hu. 2022. Rlprompt: Optimizing discrete text prompts with reinforcement learning. Preprint, arXiv:2205.12548.
  8. Zhanzhong Gu, Wenjing Jia, Massimo Piccardi, and Ping Yu. 2025. Empowering large language models for automated clinical assessment with generation-augmented retrieval and hierarchical chain-of-thought. Artif. Intell. Medicine, 162:103078. find
  9. Bowen Jin, Jinsung Yoon, Jiawei Han, and Sercan O. Arik. 2024. Long-context llms meet rag: Overcoming challenges for long inputs in rag. Preprint, arXiv:2410.05983. — [arXiv:2410.05983](https://arxiv.org/abs/2410.05983) find
  10. Bowen Jin, Hansi Zeng, Zhenrui Yue, Jinsung Yoon, Sercan Arik, Dong Wang, Hamed Zamani, and Jiawei Han. 2025. Search-r1: Training llms to reason and leverage search engines with reinforcement learning. Preprint, arXiv:2503.09516.
  11. Jia-Huei Ju, Suzan Verberne, Maarten de Rijke, and Andrew Yates. 2026. Controlled retrieval-augmented context evaluation for long-form rag. Preprint, arXiv:2506.20051. find
  12. Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. 2023. Decomposed prompting: A modular approach for solving complex tasks. Preprint, arXiv:2210.02406. find
  13. Takyoung Kim, Kyungjae Lee, Young Rok Jang, Ji Yong Cho, Gangwoo Kim, Minseok Cho, and Moontae Lee. 2025. Learning to explore and select for coverage-conditioned retrieval-augmented generation. Preprint, arXiv:2407.01158. find
  14. Antonios Minas Krasakis, Andrew Yates, and Evangelos Kanoulas. 2025. Constructing set-compositional and negated representations for first-stage ranking. Preprint, arXiv:2501.07679. — [arXiv:2501.07679](https://arxiv.org/abs/2501.07679) find
  15. Dawn Lawrie, Sean MacAvaney, James Mayfield, Paul McNamee, Douglas W. Oard, Luca Soldaini, and Eugene Yang. 2025. Overview of the trec 2024 neuclir track. Preprint, arXiv:2509.14355. — [arXiv:2509.14355](https://arxiv.org/abs/2509.14355) find
  16. Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2021. Retrieval-augmented generation for knowledge-intensive nlp tasks. Preprint, arXiv:2005.11401.
  17. Dan Li and Evangelos Kanoulas. 2017. Active sampling for large-scale information retrieval evaluation. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM ’17, page 49–58. ACM. find
  18. Suraj Nair, Eugene Yang, Dawn Lawrie, Kevin Duh, Paul McNamee, Kenton Murray, James Mayfield, and Douglas W. Oard. 2022. Transfer learning approaches for building cross-language dense retrieval models. In Proceedings of the 44th European Conference on Information Retrieval (ECIR). find
  19. Thong Nguyen, Sean MacAvaney, and Andrew Yates. 2023. A unified framework for learned sparse retrieval. Preprint, arXiv:2303.13416. — [arXiv:2303.13416](https://arxiv.org/abs/2303.13416) find
  20. Daan Odijk, Edgar Meij, Isaac Sijaranamual, and Maarten de Rijke. 2015. Dynamic query modeling for related content finding. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, Santiago, Chile, August 9-13, 2015, pages 33–42. ACM. find
  21. Roxana Petcu, Samarth Bhargav, Maarten de Rijke, and Evangelos Kanoulas. 2025. A comprehensive taxonomy of negation for nlp and neural retrievers. Preprint, arXiv:2507.22337. find
  22. Roxana Petcu and Subhadeep Maji. 2024. Efficient data selection employing semantic similarity-based graph structures for model training. Preprint, arXiv:2402.14888. — [arXiv:2402.14888](https://arxiv.org/abs/2402.14888) find
  23. Jakub Podolak, Leon Perić, Mina Janićijević, and Roxana Petcu. 2025. Beyond reproducibility: Advancing zero-shot llm reranking efficiency with setwise insertion. In Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’25, page 320… find
  24. Peng Qi, Xiaowen Lin, Leo Mehr, Zijian Wang, and Christopher D. Manning. 2019. Answering complex open-domain questions through iterative query generation. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural L…
  25. Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. 2024. Direct preference optimization: Your language model is secretly a reward model. Preprint, arXiv:2305.18290.
  26. Md Mustafizur Rahman, Mucahid Kutlu, Tamer Elsayed, and Matthew Lease. 2020. Efficient test collection construction via active learning. In Proceedings of the 2020 ACM SIGIR on International Conference on Theory of Information Retrieval, ICTIR ’20, page 177–184. ACM. find
  27. Corby Rosset, Ho-Lam Chung, Guanghui Qin, Ethan C. Chau, Zhuo Feng, Ahmed Awadallah, Jennifer Neville, and Nikhil Rao. 2024. Researchy questions: A dataset of multi-perspective, decompositional questions for llm web agents. Preprint, arXiv:2402.17896. — [arXiv:2402.17896](https://arxiv.org/abs/2402.17896) find
  28. Rulin Shao, Rui Qiao, Varsha Kishore, Niklas Muennighoff, Xi Victoria Lin, Daniela Rus, Bryan Kian Hsiang Low, Sewon Min, Wen tau Yih, Pang Wei Koh, and Luke Zettlemoyer. 2025. Reasonir: Training retrievers for reasoning tasks. Preprint, arXiv:2504.20595. find
  29. Heydar Soudani, Roxana Petcu, Evangelos Kanoulas, and Faegheh Hasibi. 2024. A survey on recent advances in conversational data generation. Preprint, arXiv:2405.13003. — [arXiv:2405.13003](https://arxiv.org/abs/2405.13003) find
  30. Coen van den Elsen, Francien Barkhof, Thijmen Ni-jdam, Simon Lupart, and Mohammad Aliannejadi. 2025. Reproducing nevir: Negation in neural information retrieval. In Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2025, Padua, Ita… find
  31. Ellen M. Voorhees. 2018. On building fair and reusable test collections using bandit techniques. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM ’18, page 407–416, New York, NY, USA. Association for Computing Machinery. find
  32. William Walden, Marc Mason, Orion Weller, Laura Dietz, Hannah Recknor, Bryan Li, Gabrielle Kaili-May Liu, Yu Hou, James Mayfield, and Eugene Yang. 2025. Auto-argue: Llm-based report generation evaluation. Preprint, arXiv:2509.26184. — [arXiv:2509.26184](https://arxiv.org/abs/2509.26184) find
  33. Orion Weller, Dawn J. Lawrie, and Benjamin Van Durme. 2024. Nevir: Negation in neural information retrieval. In Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics, EACL 2024 - Volume 1: Long Papers, St. Julian’s, Malta, March 17-22, 2024, page… find
  34. An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, and 23 others. 2025. Qwen2.5 technical report. Preprint, arXiv:241… find
  35. Algorithm 2: Thompson Sampling in Continuous Space Input :Sub-queries S = {s 1 , . . . , s K } Input :Budget b Eugene Yang, Dawn Lawrie, James Mayfield, Douglas W. Oard, and Scott Miller. 2024. Translate-distill: Learning cross-language dense retrieval by translation and distillation. In Proceedings… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/petcu-2026-query-decomposition-rag-balancing-exploration/