Paper deep dive
CompCQR: Compositional Query Generation for Training-Free Conversational Search
Yunah Jang, Kang-il Lee, Joongbo Shin, Kyomin Jung
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Multi-turn interactions with LLMs are becoming increasingly common in information-seeking scenarios. However, user queries are often ambiguous and context-dependent, making them ill-suited for direct use as retriever queries. Conversational query reformulation (CQR) addresses this issue by rewriting the current utterance into a stand-alone query grounded in the dialogue history. Recent LLM-based CQR approaches achieve strong performance; however, their repeated LLM invocations and misalignment with downstream retrievers remain challenges. In this work, we begin from the observation that retrievers are highly sensitive to content ordering: simply reordering the same content can lead to changes in retrieval coverage and performance. Based on this, we propose a novel training-free method that generates a very large number of queries with minimal LLM usage by compositionally combining a small set of atomic components. We further apply LLM reasoning to construct a high-quality document set that balances precision and recall while capturing the user's core intent. Our framework generalizes across both open- and closed-source LLMs as well as dense and sparse retrievers. It achieves strong performance on four widely used conversational benchmarks, with up to 22.5% relative MRR improvement over the previous state-of-the-art baseline with far fewer LLM calls.
Tags
Links
- Source: https://arxiv.org/abs/2609.14646v1
- Canonical: https://arxiv.org/abs/2609.14646v1
Trouble viewing inline? Open PDF directly →
Full Text
75,073 characters extracted from source content.
Expand or collapse full text
CompCQR: Compositional Query Generation for Training-Free Conversational Search Yunah Jang Affiliation: Dept. of ECE, Seoul National University Email: vn2209@snu.ac.kr Kang-il Lee Affiliation: Dept. of ECE, Seoul National University Email: 4bkang@snu.ac.kr Joongbo Shin Affiliation: LG AI Research Email: kjung@snu.ac.kr Kyomin Jung Affiliation: Dept. of ECE, Seoul National University Email: jb.shin@lgresearch.ai Abstract Multi-turn interactions with LLMs are becoming increasingly common in information-seeking scenarios. However, user queries are often ambiguous and context-dependent, making them ill-suited for direct use as retriever queries. Conversational query reformulation (CQR) addresses this issue by rewriting the current utterance into a stand-alone query grounded in the dialogue history. Recent LLM-based CQR approaches achieve strong performance; however, their repeated LLM invocations and misalignment with downstream retrievers remain challenges. In this work, we begin from the observation that retrievers are highly sensitive to content ordering: simply reordering the same content can lead to changes in retrieval coverage and performance. Based on this, we propose a novel training-free method that generates a very large number of queries with minimal LLM usage by compositionally combining a small set of atomic components. We further apply LLM reasoning to construct a high-quality document set that balances precision and recall while capturing the user’s core intent. Our framework generalizes across both open- and closed-source LLMs as well as dense and sparse retrievers. It achieves strong performance on four widely used conversational benchmarks, with up to 22.5% relative MRR improvement over the previous state-of-the-art baseline with far fewer LLM calls.∗ 22footnotetext: Corresponding author.11footnotetext: Code is available at https://github.com/YunahJang/CompCQR. 1 Introduction Large language models (LLMs) are increasingly becoming a common medium for information seeking Li et al. (2025); Zhang et al. (2025). When interacting with LLMs, users often engage in multi-turn exchanges to refine and clarify their information needs Laban et al. (2026); Wang et al. (2024); Guan et al. (2025). This makes conversational search—the task of retrieving relevant information throughout an ongoing dialogue while understanding user intent in context—a fundamental paradigm for modern information access Mo et al. (2025a); Mo et al. (2026). Figure 1: Comparison of MRR across different FLOPs. On TopiOCQA Adlakha et al. (2022), we conduct a comparison of two prompting-based CQR methods: CompCQR (ours) and LLM4CS Mao et al. (2023b). In conversational settings, user utterances are often short, ambiguous, and highly dependent on prior dialogue context Adlakha et al. (2022); Anantha et al. (2021); Dalton et al. (2020b). They frequently contain ellipsis, coreference, and underspecified intent, making them difficult to use directly for retrieval Jang et al. (2024); Mo et al. (2023). To address these challenges, conversational query rewriting (CQR) reformulates the current utterance into a stand-alone query grounded in the dialogue history, enabling downstream retrievers to better capture the user’s information need Yu et al. (2020); Wu et al. (2022). LLMs have recently emerged as a powerful tool for CQR, owing to their strong performance to infer missing context from dialogue history and produce coherent stand-alone queries Lai et al. (2025a); Mao et al. (2023b); Ye et al. (2023). Despite their strong ability, important challenges remain in making methods both computationally efficient and effective. In practice, as shown in Table 1, existing methods depend on multiple LLM calls or training models. Method # of Calls # of Query Query Agg. Train Free T5QR (2020) 0 1 ✗ ✗ ConvGQR (2023) 0 1 ✗ ✗ IterCQR (2024) 0 1 ✗ ✗ ConvSearch-R1 (2025) 1 1 ✗ ✗ AdaCQR (2025b) 1 1 ✗ ✗ CHIQ-Fusion (2024) 6 2 D ✗ AdaRewriter (2025a) 16 16 ✗ ✗ LLM4CS (2023b) 5 5 Q ✓ CompCQR (Ours) 3 325 D ✓ Table 1: Comparison of CQR methods. We compare the number of LLM calls, the number of query reformulations, the aggregation (agg.) strategy, and whether the method is training-free. Aggregation occurs either at the query level (Q), merging multiple queries into a single query embedding, or at the document level (D), retrieving with each query and aggregating the document sets. Instead of relying on expensive training or excessive LLM inference, we propose CompCQR, a training-free CQR framework. CompCQR generates diverse queries through lightweight compositional expansion with minimal LLM usage, enabling broader exploration of the retrieval space. It then aggregates the documents retrieved by these queries into a ranked list, improving coverage by retaining documents that may be missed by any single rewrite while preserving strong ranking signals from highly ranked results. Finally, it applies LLM-based reasoning to select a document based on answerability, which constructs a document set that better balances recall and precision while remaining faithful to the user’s intent. As shown in Figure 1, CompCQR yields substantially better retrieval performance than prompting-based baselines under a comparable computational cost. We conduct extensive experiments on four conversational search benchmarks and find that CompCQR achieves competitive or superior performance over training-based QR baselines with a more LLM-efficient pipeline. In particular, it outperforms the previous best-performing baseline by up to 22.5% on dense retrievers and 14.7% on sparse retrievers. These results highlight the strong performance and robustness of the proposed method across diverse retrieval settings. In summary, our contributions are as follows: • We propose CompCQR, a training-free method that generates a large number of compositional rewrites with minimal LLM calls. • We use document-level aggregation and an LLM-based reasoning step that provides both recall and precision improvements to the retrieved document set. • We demonstrate that CompCQR consistently performs well across multiple datasets, retrievers, and long conversational contexts. 2 Potential of Compositional Queries Several works explore test-time scaling for CQR by generating multiple rewritten queries, resulting in an expanded retrieval space and improved retrieval performance Mao et al. (2023b); Lai et al. (2025a). However, such approaches typically require multiple LLM calls, resulting in substantial computational cost. More broadly, recent work on query robustness has shown that even semantically equivalent query formulations can lead to substantially different retrieval behavior Jang et al. (2026), suggesting that diverse formulations can expose complementary retrieval results. Motivated by these observations, we propose a lightweight query generation method, compositional query generation. This method constructs multiple query variants solely by adding, removing, or reordering atomic components. Specifically, we extract four components using two LLM calls: a rewritten query–answer pair (qr,arq^r,a^r) and a follow-up query–answer pair (qf,afq^f,a^f). Together with the original query (q), this yields five components in total. We then enumerate all permutations of these components to construct 325 candidate queries.22 2 The total number of permutations from five components is ∑r=15Pr5=325 _r=1^5_5P_r=325. In this section, we show that compositional queries (i) yield diverse retrieval spaces, and (i) perform well compared to existing multiple-query rewriting methods. We employ the ANCE Xiong et al. (2020) retriever and TopiOCQA Adlakha et al. (2022) dataset. 2.1 Retrieval Coverage of Compositional Queries We first investigate whether compositional queries yield diverse retrieval results. Since compositional queries are formed by reordering the same set of components, many variants differ only in their ordering. We therefore compare queries with identical components but different orders, and measure the overlap of their top-k retrieved documents using Jaccard similarity. The average overlap is 0.72 at top-10 and 0.71 at top-100. These results indicate that, even with identical components, changing their order can result in a Jaccard distance of 28%, reflecting a substantial set-level difference in the retrieved documents. This suggests that compositional queries can improve retrieval coverage by exploiting the retriever’s sensitivity to query order. This trend is consistent across different dense retrievers, as shown in Appendix 16. Figure 2: Comparison of query rewriting methods. We compare the average and upper-bound retrieval performance across 325 query candidates generated by compositional and sampling-based query rewriting methods, where IID denotes independent sampling at different temperatures, Seq. sequential sampling, and Comp. compositional query rewriting. 2.2 Effectiveness of Compositional Queries We then investigate whether the retrieval diversity of compositional queries leads to higher CQR performance compared to existing methods. For existing multiple-query generation approaches, we adopt two LLM sampling strategies: IID sampling at three temperatures (0.7, 1.0, and 1.3), and sequential sampling with five calls, each generating 65 queries conditioned on previously generated outputs. For a fair comparison, all methods generate 325 queries per instance over 100 randomly sampled instances from TopiOCQA Adlakha et al. (2022). As shown in Figure 2, compositional query rewriting achieves the highest average and upper-bound MRR while requiring only two LLM calls per query, compared to 325 calls for IID sampling and 32.1× higher FLOPs for sequential generation. This result underscores a key insight: the goal of rewriting queries is not merely to produce uniformly strong candidates, but to discover reformulations that better align with the retriever and recover relevant documents missed by the original query. 3 Methodology Figure 3: CompCQR Framework Overview. CompCQR first extracts query components with two LLM calls, generates compositional query candidates, aggregates retrieved documents via RRF scoring, and finally performs LLM-based document selection. In this section, as illustrated in Figure 3, we introduce a three-stage framework designed to improve document relevance through complementary recall- and precision-oriented components. Specifically, the recall-oriented stages consist of compositional query generation and document ranking, while the precision-oriented stage is implemented through LLM-based document selection. 3.1 Task Formulation A conversational search task aims to retrieve documents that contain the necessary information to answer a user’s query in a conversational setting. At the current turn t, the user issues a query qtq_t, and the historical context Ht−1H_t-1 is defined as Ht−1=(qi,ai)i=1t−1,H_t-1=\(q_i,a_i)\_i=1^t-1, where qiq_i and aia_i denote the query and answer at turn i, respectively. Given the current query qtq_t and the historical context Ht−1H_t-1, a language model ℳM rewrites qtq_t into a standalone query: qt~=ℳ(qt,Ht−1). q_t=M(q_t,H_t-1). The rewritten query qt~ q_t is then fed into an off-the-shelf retriever ℛR, which returns a ranked list of documents: Dt=ℛ(qt~)=d1,d2,…,dk,D_t=R( q_t)=\d_1,d_2,…,d_k\, where DtD_t denotes the top-k retrieved documents. In later sections, we denote the history and current query as H and q, respectively. 3.2 Compositional Query Reformulation As discussed in Section 2, we employ compositional query reformulation to broaden retrieval coverage. For each instance, we first use dialogue history H and original query q to issue two LLM calls with different prompts, and then construct multiple compositional query variants from their outputs. Unlike prior work, which primarily considers rewrites and potential answers, we additionally generate a follow-up query and its corresponding answer, further increasing semantic diversity Samarinas and Zamani (2024); Meng et al. (2025). Specifically, using the query rewriting prompt PrewriteP_rewrite and the follow-up query generation prompt PfollowP_follow, we obtain four components: a rewritten query q~ q and its potential answer a~ a, and a follow-up query qfq^f and its corresponding answer afa^f: (q~,a~) ( q, a) =LLM(Prewrite,H,q), =LLM(P_rewrite,H,q), (1) (qf,af) (q^f,a^f) =LLM(Pfollow,H,q). =LLM(P_follow,H,q). (2) Together with the original query q, these outputs form five query-related components: =q,q~,a~,qf,af.C=\q,\ q,\ a,\ q^f,\ a^f\. (3) We then construct compositional query candidates by enumerating all possible ordered combinations of these five components. Specifically, for each length r∈1,2,3,4,5r∈\1,2,3,4,5\, we consider all permutations without repetition: ℰ=⋃r=15Perm(,r),|ℰ|=∑r=15Pr5=325.E= _r=1^5Perm(C,r), |E|= _r=1^5_5P_r=325. (4) where Perm(,r)Perm(C,r) denotes the set of all length-r ordered sequences formed from C.33 3 For BM25 retrieval, component order does not affect retrieval because queries are treated as bags of words. Therefore, the number of distinct query combinations is ∑r=15(5r)=31 _r=1^55 r=31. The prompts used in this step are provided in Appendix J. 3.3 Document Sorting by Retrieval Scores Using multiple queries to explore the query space has shown promise in prior work Lai et al. (2025a); Jang et al. (2024). Existing approaches typically combine query information at the query or embedding level Mao et al. (2023b); Kostric and Balog (2024), while Reciprocal Rank Fusion (RRF) is often used as a learning signal in retrieval pipelines Lai et al. (2025a); Lai et al. (2025b). In contrast, we apply RRF directly to document-set-level aggregation Mo et al. (2024); Lin et al. (2021b); Dhole et al. (2024). By aggregating documents retrieved from multiple queries using RRF Cormack et al. (2009) together with document frequency, our method preserves complementary evidence across queries and thereby improves document coverage. Method Model TF QReCC TopiOCQA MRR NDCG R@10 R@100 MRR NDCG R@10 R@100 Sparse (BM25) T5QR T5-base ✗ 33.4 30.2 53.8 86.1 11.3 9.8 22.1 44.7 ConQRR T5-base ✗ 38.3 - 60.1 88.9 - - - - ConvGQR T5-base ✗ 44.1 41.0 64.4 88.0 12.4 10.7 23.8 45.6 EdiRCS T5-base ✗ 42.1 - 65.6 85.3 - - - - IterCQR T5-base ✗ 46.7 44.1 64.4 85.5 16.5 14.9 29.3 54.1 ReTPO Llama-2-7B ✗ 50.0 47.3 69.5 89.5 28.3 26.5 48.3 73.1 ICR Llama2-7B ✗ 58.4 54.9 78.3 95.9 31.4 30.4 52.8 76.3 ConvSearch-R1 Llama-3.2-3B ✗ 55.9 54.3 77.2 89.0 37.8 36.2 59.6 80.1 ADACQR Llama-2-7B† ✗ 55.1 52.5 76.5 - 28.3 26.5 48.9 - CHIQ-Fusion Llama-2-7B† ✗ 54.3 51.9 78.5 - 25.6 23.5 44.7 - AdaRewriter Llama-3.1-8B† ✗ 56.2 53.8 78.8 - 30.7 28.8 51.3 - LLM-Aided GPT-3.5-turbo ✓ 49.4 46.5 67.1 - - - - - LLM4CS Llama-3.1-8B ✓ 49.7 46.9 73.8 - 24.5 22.6 42.1 - LLM4CS GPT-4.1-mini ✓ 54.4 52.0 78.9 94.7 31.3 29.6 52.7 74.9 CompCQR Llama-3.1-8B ✓ 55.7 54.0 75.8 94.1 29.3 28.4 49.3 73.7 CompCQR GPT-4.1-mini ✓ 67.0 64.4 83.4 96.1 41.3 40.4 60.3 80.2 Dense (ANCE) T5QR T5-base ✗ 34.5 31.8 53.1 72.8 23.0 22.2 37.6 54.4 ConvGQR T5-base ✗ 42.0 39.1 63.5 81.8 25.6 24.3 41.8 58.8 IterCQR T5-base ✗ 42.9 40.2 65.5 84.1 26.3 25.1 42.6 62.0 ReTPO Llama-2-7B ✗ 44.0 41.1 66.7 84.6 30.0 28.9 49.6 68.7 ICR Llama2-7B ✗ 49.5 46.8 73.2 88.3 42.1 40.4 64.3 78.3 ConvSearch-R1 Llama-3.2-3B ✗ 50.2 48.1 70.6 82.8 50.5 50.1 72.0 86.3 ADACQR Llama-2-7B† ✗ 45.8 42.9 67.3 - 38.5 37.6 58.4 - CHIQ-Fusion Llama-2-7B† ✗ 47.2 44.2 70.7 - 38.0 37.0 61.6 - AdaRewriter Llama-3.1-8B† ✗ 47.5 44.7 69.8 - 40.3 39.7 61.9 - LLM-Aided GPT-3.5-turbo ✓ 43.5 41.3 65.6 - - - - - LLM4CS Llama-3.1-8B ✓ 43.2 40.7 64.6 - 35.2 34.8 58.2 76.0 LLM4CS GPT-4.1-mini ✓ 47.4 44.6 70.6 87.4 41.9 40.9 63.7 78.7 CompCQR Llama-3.1-8B ✓ 50.8 48.3 67.8 86.2 42.3 41.5 62.2 80.2 CompCQR GPT-4.1-mini ✓ 61.5 58.6 74.6 88.0 48.7 47.7 67.5 83.5 Table 2: Main results on QReCC and TopiOCQA. We report our main results under sparse (BM25) and dense (ANCE) retrieval. We compare our proposed method, CompCQR, with prior conversational query rewriting approaches. Bold and underlined values denote the best and second-best results within each retriever setting. † denotes methods using fine-tuned LMs with LLM. TF stands for training-free. For a compositional query set ℰE, let ranke(d)rank_e(d) denote the rank of document d among the top 100 retrieved documents for query candidate e∈ℰe . We compute the RRF score of document d as RRF(d)=∑e∈ℰd1s+ranke(d),RRF(d)= _e _d 1s+rank_e(d), (5) where ℰd⊆ℰE_d denotes the subset of query candidates that retrieve d, and s is a smoothing hyperparameter. Documents are then ranked in descending order of RRF(d)RRF(d). Ties are broken using Freq(d)=|ℰd|Freq(d)=|E_d|, giving higher priority to documents retrieved by more query candidates. This aggregation favors documents that appear frequently and at high ranks across query candidates, capturing the user’s information need. By exposing the retriever to multiple views of the same need, it increases the likelihood of retrieving relevant documents missed by the original query. 3.4 Best Document Selection Finally, we refine the top-ranked result by leveraging the LLM’s document-grounded reasoning capabilities. Let D^100=(d1,d2,…,d100) D_100=(d_1,d_2,…,d_100) denote the top-100 documents ranked by RRF-based aggregation, and let D^k=(d1,…,dk) D_k=(d_1,…,d_k) denote its top-k prefix. The LLM then selects a single document d∗=ℳ(q,H,D^k),d^*=M(q,H, D_k), (6) where d∗∈D^kd^*∈ D_k is judged most likely to contain answer-supporting information. The final list D100finalD^final_100 is constructed by moving d∗d^* to rank 1 while preserving the relative order of the remaining documents in D^100 D_100. This list is used for evaluation. 4 Experiments 4.1 Experimental Setup Datasets. We evaluate our framework on four widely used conversational search datasets: QReCC Anantha et al. (2021), TopiOCQA Adlakha et al. (2022), CAsT19 Dalton et al. (2020b), and CAsT20 Dalton et al. (2020a). We evaluate baselines on the test set, considering only instances that contain gold annotations. Additional statistics are provided in Appendix A.3. Evaluation Metrics. We use the pytrec_eval toolkit to compute retrieval metrics Gysel and de Rijke (2018), including mean reciprocal rank (MRR), NDCG@3, Recall@10, and Recall@100, following previous studies Lai et al. (2025a); Jang et al. (2024); Mo et al. (2023). Implementation Details. We evaluate our framework using two types of models: Llama-3.1-8B-Instruct Grattafiori et al. (2024) and GPT-4.1-mini OpenAI (2025). Llama-3.1-8B has been widely used in prior baselines, often together with additional reward model training. ChatGPT has also been commonly adopted in prompting-based approaches; therefore, we use GPT-4.1-mini as a lightweight yet strong-performing model for comparison with these baselines. For RRF, we tune the hyperparameters on the validation set, setting s to 0 and choosing top-K values of 10 for Llama-3.1-8B and 40 for GPT-4.1-mini. Additional analyses of these hyperparameters are provided in Appendix A.2. For retrieval, we use both BM25 Robertson and Zaragoza (2009) and the ANCE Xiong et al. (2020) dense retriever, following previous work Lai et al. (2025b); Lai et al. (2025a); Yoon et al. (2025); Jang et al. (2024). Baselines. We compare our method against three types of baselines: training-based methods, hybrid methods that combine LLMs with trained smaller models, and training-free LLM-based methods. The training-based baselines include T5QR Lin et al. (2020), CONQRR Wu et al. (2022), ConvGQR Mo et al. (2023), EdiRCS Mao et al. (2023a), IterCQR Jang et al. (2024), RetPO Yoon et al. (2025), ICR Cao et al. (2025), and ConvSearch-R1 Zhu et al. (2025). Among hybrid methods, which combine trained language models such as T5-base or DeBERTa with LLMs, we include AdaCQR Lai et al. (2025b), CHIQ-Fusion Mo et al. (2024), and AdaRewriter Lai et al. (2025a). For the training-free setting most comparable to ours, we consider LLM-Aided Ye et al. (2023) and LLM4CS Mao et al. (2023b). Further baseline details are provided in Appendix I. Method CAsT-19 CAsT-20 MRR R@10 MRR R@10 LLM4CS∗ 73.3 13.9 77.2 17.8 AdaRewriter∘ - 13.0 63.0 21.6 CompCQR∘ 66.6 12.1 71.0 16.2 CompCQR∗ 75.8 13.2 78.3 16.7 Table 3: CAsT-19 and -20 results. We compare CompCQR against prior baselines under dense retrieval. ∘ denotes results using Llama-3.1-8B-Instruct, and ∗ denotes results using GPT-4.1-mini. 4.2 Main Results In Table 2, we evaluate TopiOCQA and QReCC using both dense (ANCE) and sparse (BM25) retrievers. Compared with training-based baselines that require human-rewritten queries or ground-truth documents, our method achieves comparable performance and, in some settings, outperforms them by up to 22.5% (+11.3 MRR) without using any training labels. It also outperforms all prior training-free LLM-based query rewriting methods by a large margin across all settings. We also evaluate on CAsT-19 and CAsT-20 (Table 3), where our approach outperforms existing prompting-based methods. Overall, these results show that CompCQR achieves strong performance without explicit training, outperforming previous baselines while reducing LLM inferences (see Appendix F). 5 Analysis 5.1 Ablation Studies Setting MRR NDCG R@10 CompCQR (Ours) 42.3 41.5 62.2 - w/o RRF (+Rel.) 35.7 34.4 51.5 - w/o RRF (+Mean) 39.4 38.9 57.9 - w/o LS 37.8 36.5 62.2 - w/o RRF (+Rel.) & LS 31.5 29.9 51.5 - w/o RRF (+Mean) & LS 36.8 35.8 57.9 Table 4: Ablation study. We evaluate the contribution of the two core components of CompCQR: LLM-based document selection (LS) and RRF-based document aggregation (RRF). For the setting w/o RRF, candidate passages are ranked either according to the retriever relevance score (Rel.) or using mean aggregation (Mean). #Q LS RRF Mean MRR NDCG MRR NDCG 5 ✗ 36.0 34.6 34.2 33.1 ✓ 39.6 (+3.6) 38.5 (+3.9) 38.1 (+3.9) 37.5 (+4.4) 325 ✗ 37.8 36.5 36.8 35.8 ✓ 42.3 (+4.5) 41.5 (+5.0) 39.4 (+2.6) 38.9 (+3.1) Table 5: Comparison with different aggregation strategies. We compare mean and RRF aggregation with and without the LLM selection (LS) setting on the TopiOCQA dataset. Each method is evaluated using 5 and 325 queries. The values in parentheses indicate the performance gain when LS is applied. We conduct an ablation study on TopiOCQA using Llama-3.1-8B-Instruct to assess the contribution of each component in CompCQR. It consists of two main components: an RRF-based document aggregation stage (RRF) and a final LLM-based document selection stage (LS). To examine the effect of removing the LLM-based selection module (w/o LS) we directly use the ranking produced by RRF aggregation. To examine the contribution of the RRF-based aggregation module, we further construct w/o RRF, which removes the RRF-based aggregation step. In this setting, documents are instead aggregated using either the retriever relevance score (Rel.) or query embedding mean aggregation (Mean). We note that query mean aggregation is also adopted in the strong baseline LLM4CS Mao et al. (2023b). The results in Table 4 show that both components contribute substantially to retrieval quality, with a 4.5-point drop when LS is removed. We further verify in Appendix 14 that this gain does not simply come from the additional LLM call, as applying the same selection step to LLM4CS yields a much smaller improvement than for CompCQR. Replacing top-1 selection with full reranking over the top-10 documents also degrades performance substantially (Appendix B.3), indicating that selecting the best supporting document is a more reliable decision for the LLM than ordering an entire list. 5.2 Aggregation Method under Scaling We further investigate the effect of aggregation strategies under different numbers of query candidates. Table 5 compares reciprocal rank fusion (RRF) and mean aggregation using 5 randomly sampled query candidates and the full set of 325 query candidates, both with and without LLM selection. Overall, RRF consistently outperforms mean aggregation across all settings. In particular, CompCQR with RRF improves by 3 points when scaling from 5 to 325 candidates in NDCG@3, whereas mean aggregation shows a smaller gain of 1.4 points. Moreover, at 325 candidates, incorporating LLM selection yields the largest gain of 5.0 NDCG@3 points over RRF aggregation alone. These results suggest that document-level aggregation benefits more from LLM-based document selection than query-embedding averaging, especially when a large and diverse set of compositional queries is used. 5.3 Computational Efficiency Method # Cands. End-to-End (s) MRR LLM4CS 5 4.05 34.6 LLM4CS 16 5.51 35.4 LLM4CS 325 29.90 40.5 CompCQR 5 15.67 40.9 CompCQR 325 17.41 42.3 Table 6: End-to-end wall-clock latency and MRR on TopiOCQA across different numbers of candidates. Step Description Time Fraction 0 Rewrite 2.93 s 17.0% 1 Follow-up Generation 1.80 s 10.3% 2 Variation Generation 0.19 ms ∼ 0.0% 3 Retrieval + Sorting 1.83 s 10.5% 4 LLM-based Selection 10.85 s 62.3% LLM Total 15.58 s 89.5% Retrieval Total 1.83 s 10.5% Overall 17.41 s 100.0% Table 7: End-to-end latency breakdown of CompCQR on TopiOCQA. We analyze the computational efficiency of CompCQR from two perspectives: end-to-end wall-clock latency, and the number of LLM calls and FLOPs per query. Latency is measured on TopiOCQA using one NVIDIA A6000 GPU with vLLM. Table 6 reports the average per-query latency together with MRR. CompCQR consistently achieves higher retrieval effectiveness than LLM4CS across candidate sizes. Notably, CompCQR with only 5 candidates achieves an MRR of 40.9, outperforming LLM4CS with 325 candidates (40.5) while being approximately 1.9× faster (15.67s vs. 29.90s). With 325 candidates, our main setting, CompCQR further improves MRR to 42.3. While CompCQR considers a large number of query candidates, the associated retrieval and sorting cost remains small. As shown in Table 7, the end-to-end latency grows only marginally with the number of candidates, since retrieval and sorting account for just 10.5% of the total runtime. CompCQR is also favorable in terms of LLM calls and FLOPs, requiring only three calls per query (Appendix F). These results show that CompCQR remains computationally efficient despite exploring a large candidate space. 5.4 Analysis on Different Retrievers Method Retriever MRR NDCG@3 LLM4CS GTR 42.6 41.7 CompCQR GTR 47.2 (+4.6) 45.9 (+4.2) LLM4CS Contriever 46.1 45.1 CompCQR Contriever 48.9 (+2.8) 47.6 (+2.5) Table 8: Results with additional dense retrievers. We report GTR and Contriever results on our framework. We conduct additional dense retriever experiments on TopiOCQA using two widely used dense retrievers, GTR Ni et al. (2022) and Contriever Izacard et al. (2021), with GPT-4.1-mini. As shown in Table 8, CompCQR consistently improves over LLM4CS in terms of MRR, with gains of +4.6 points using GTR and +2.8 points using Contriever. These results indicate that the effectiveness of CompCQR is not limited to ANCE, but generalizes to other dense retrievers. We additionally analyze their order sensitivity in Appendix 16. Figure 4: Per-turn performance comparison. We compare per-turn MRR with LLM4CS (2023b). 5.5 Long-conversation Performance Previous studies have shown that conversational search performance tends to decline in later turns Lai et al. (2025a); Wu et al. (2022). To evaluate the robustness of our framework in long conversations, we analyze performance by turn index. Figure 4 compares our method with the LLM-prompting-based baseline LLM4CS Mao et al. (2023b) on TopiOCQA using GPT-4.1-mini. The performance gap widens as the conversation progresses, indicating that our framework is more robust in long conversations and better preserves retrieval effectiveness in later turns. 6 Compositional Query Analysis In this section, we analyze our compositional query generation framework from three perspectives: (i) the relative contribution of each query component, (i) differences in preferred supporting components across retrievers, and (i) impact of component ordering on dense retrieval. Component Notation Dense (ϕφ) Sparse (ϕφ) Original Query q 1.13 0.41 Rewrite q~ q 9.98 6.27 Rewrite Answer a~ a 16.20 14.54 Followup Query qfq^f 5.13 3.86 Followup Answer afa^f 7.13 6.32 Table 9: Impact of components by Shapley value. Shapley value analysis under dense and sparse retrievers, where all values are scaled by 100. # Queries MRR NDCG@3 CompCQR (ours) 325 42.3 41.5 - without qf,afq^f,a^f 113 34.9 35.1 Table 10: Performance comparison without follow-up components. We compare the full model with the variant without the follow-up query qfq^f and answer afa^f. Answer components are important. Our framework uses five components: the original query (q), rewritten query (q~ q), rewritten answer (a~ a), follow-up query (qfq^f), and follow-up answer (afa^f). To quantify the contribution of each component, we compute its Shapley value on test-set MRR Ghorbani and Zou (2019); Rozemberczki et al. (2022), which measures the average marginal contribution of that component across all possible combinations. As shown in Table 9, for both ANCE and BM25, the rewritten answer a~ a is the most important component, with Shapley values of 16.2 and 14.54, respectively. This consistent pattern aligns with prior CQR studies showing that answer information is particularly useful for retrieval Mo et al. (2023); Jang et al. (2024). In Table 10, we additionally report the results after excluding qfq^f and afa^f. Removing these components leads to an overall MRR drop of 6.4 points. This shows that follow-up information expands the query space with complementary intent signals, leading to more effective retrieval. Different retrievers favor different components. The two retrievers differ, however, in their next most useful components. In ANCE, the rewritten query q~ q is the second most influential component (ϕ=9.98φ=9.98), whereas in BM25, the follow-up answer afa^f slightly surpasses q~ q (ϕ=6.32φ=6.32 vs. ϕ=6.27φ=6.27). This suggests that sparse and dense retrievers benefit from different supporting components and composition strategies. Figure 5: Position sensitivity of the a~ a component. We report the change in MRR relative to the mean performance of queries sharing the same component set, grouped by the position of a~ a in the query. Component ordering matters for dense retrieval. Consistent with Section 2, component order matters for dense retrieval. In ANCE, performance is generally higher when a~ a appears earlier in the sequence, as shown in Figure 5. This may reflect the encoding behavior of dense retrievers, where earlier tokens can have a stronger influence on the final query representation. Additional analyses on the number of queries are provided in Appendix C. Overall, these results suggest that effective retrieval depends not only on query content, but also on structurally diverse query variations. 7 Related Work In conversational search, the main challenge is to interpret the current query in light of the preceding dialogue context. To address this challenge, two main approaches have been explored: conversational dense retrieval (CDR) and conversational query reformulation (CQR). CDR methods encode conversational context directly for retrieval without an explicit query rewriting step Chen et al. (2024); Lin et al. (2021b); Mao et al. (2023c). Representative approaches include ConvDR, which learns contextualized dense embeddings via teacher–student distillation Yu et al. (2021), and Contextualized Query Embeddings, which develop a compact retriever for low-latency conversational passage retrieval Lin et al. (2021b). More recent work such as ConvAug improves generalization through LLM-based conversation augmentation Chen et al. (2024). A parallel line of work adapts sparse retrievers to the conversational setting: Conv-SPLADE fine-tunes SPLADE Formal et al. (2021) on conversational data. In contrast, CQR enables the use of off-the-shelf retrievers by reformulating the current query into a standalone form that can be directly processed by existing retrieval models Jang et al. (2024); Mao et al. (2023b); Zhu et al. (2025). Recent CQR research has increasingly been shaped by large language models (LLMs). IterCQR Jang et al. (2024) uses LLM-generated rewrites for initialization instead of human annotations. LLM4CS Mao et al. (2023b) applies direct prompting to generate multiple rewrites and hypothetical responses. LLM-aided informative query rewriting Ye et al. (2023) employs LLMs in a rewrite-then-edit framework. ConvSearch-R1 Zhu et al. (2025) further explores training LLM-based reformulation models through supervised fine-tuning and reinforcement learning. Our work shares this motivation and aims to fully leverage LLM capabilities for CQR while improving efficiency through compositional generation. 8 Conclusion In conclusion, we introduce CompCQR, a simple yet effective training-free CQR framework. Rather than relying on costly training or repeated LLM inference, our approach generates diverse compositional reformulations, aggregates retrieval results across candidates, and uses lightweight answerability-guided reasoning to select high-quality evidence. Our findings show that: (1) our framework outperforms existing training- and prompting-based methods without explicit training labels across both dense and sparse retrievers; (2) document-level aggregation via RRF increasingly outperforms query-level aggregation as the number of candidates grows; and (3) our framework remains robust in long conversations, where the performance gap over existing QR methods widens as the conversation progresses. Limitations Our work has several limitations. The current evaluation is limited to English benchmarks, so it remains unclear how well the framework transfers to other languages. Extending the approach to multilingual settings would therefore be an important direction for future work. In addition, while we consider a predefined set of compositional queries, we do not study how to identify the most effective subset for a given dataset or retriever. A more principled composition selection strategy could further improve both efficiency and retrieval effectiveness. Although our experiments show that the framework is already cost-effective in terms of both LLM calls and FLOPs, the current design still requires multiple retriever calls to explore compositional variants. Further improving retrieval efficiency, for example by reducing the number of retrieval calls while preserving coverage, could lower end-to-end latency and make the framework even more practical. Our current framework also considers only permutations without repetition. Exploring more flexible composition strategies, including those that intentionally repeat selected components, adding more future queries, could further enrich the space of query variants and potentially improve retrieval effectiveness. Finally, while we evaluate compact open-source and API-based models, it would also be interesting to examine how the framework performs with larger open-source LLMs, such as 70B-scale models. Acknowledgments This work was partly supported by the Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2022-I220184, Development and Study of AI Technologies to Inexpensively Conform to Evolving Policy on Ethics), and the Artificial Intelligence Graduate School Program (Seoul National University) (No. RS-2021-I212068)). K. Jung is with the Automation and Systems Research Institute (ASRI), Seoul National University, Seoul, Republic of Korea. References Adlakha et al. (2022) V. Adlakha, S. Dhuliawala, K. Suleman, H. de Vries, and S. Reddy TopiOCQA: open-domain conversational question answering with topic switching. Transactions of the Association for Computational Linguistics 10, p. 468–483. External Links: Link, Document Cited by: Figure 1, §1, §2.2, §2, §4.1. Anantha et al. (2021) R. Anantha, S. Vakulenko, Z. Tu, S. Longpre, S. Pulman, and S. Chappidi Open-domain question answering goes conversational via question rewriting. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, K. Toutanova, A. Rumshisky, L. Zettlemoyer, D. Hakkani-Tur, I. Beltagy, S. Bethard, R. Cotterell, T. Chakraborty, and Y. Zhou (Eds.), Online, p. 520–534. External Links: Link, Document Cited by: §1, §4.1. Cao et al. (2025) Z. Cao, P. Li, and Q. Zhu ICR: iterative clarification and rewriting for conversational search. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, C. Christodoulopoulos, T. Chakraborty, C. Rose, and V. Peng (Eds.), Suzhou, China, p. 9810–9824. External Links: Link, Document, ISBN 979-8-89176-332-6 Cited by: 7th item, §4.1. Chen et al. (2024) H. Chen, Z. Dou, K. Mao, J. Liu, and Z. Zhao Generalizing conversational dense retrieval via LLM-cognition data augmentation. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), L. Ku, A. Martins, and V. Srikumar (Eds.), Bangkok, Thailand, p. 2700–2718. External Links: Link, Document Cited by: Table 21, §7. Cormack et al. (2009) G. V. Cormack, C. L. A. Clarke, and S. Buettcher Reciprocal rank fusion outperforms condorcet and individual rank learning methods. In Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’09, New York, NY, USA, p. 758–759. External Links: ISBN 9781605584836, Link, Document Cited by: §3.3. Dalton et al. (2020a) J. Dalton, C. Xiong, and J. Callan CAsT 2020: the conversational assistance track overview. In Text Retrieval Conference, External Links: Link Cited by: §4.1. Dalton et al. (2020b) J. Dalton, C. Xiong, and J. Callan TREC cast 2019: the conversational assistance track overview. CoRR abs/2003.13624. External Links: Link, 2003.13624 Cited by: §1, §4.1. Dhole et al. (2024) K. D. Dhole, R. Chandradevan, and E. Agichtein Generative query reformulation using ensemble prompting, document fusion, and relevance feedback. External Links: 2405.17658, Link Cited by: §3.3. Formal et al. (2021) T. Formal, B. Piwowarski, and S. Clinchant SPLADE: sparse lexical and expansion model for first stage ranking. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’21, New York, NY, USA, p. 2288–2292. External Links: ISBN 9781450380379, Link, Document Cited by: Table 21, §7. Ghorbani and Zou (2019) A. Ghorbani and J. Zou Data shapley: equitable valuation of data for machine learning. In Proceedings of the 36th International Conference on Machine Learning, K. Chaudhuri and R. Salakhutdinov (Eds.), Proceedings of Machine Learning Research, Vol. 97, p. 2242–2251. External Links: Link Cited by: §6. Grattafiori et al. (2024) A. Grattafiori, A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Vaughan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783. Cited by: §4.1. Guan et al. (2025) S. Guan, H. Xiong, J. Wang, J. Bian, B. Zhu, and J. Lou Evaluating llm-based agents for multi-turn conversations: a survey. CoRR abs/2503.22458. External Links: Link Cited by: §1. Gysel and de Rijke (2018) C. V. Gysel and M. de Rijke Pytrec_eval: an extremely fast python interface to trec_eval. The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval. External Links: Link Cited by: §4.1. Izacard et al. (2021) G. Izacard, M. Caron, L. Hosseini, S. Riedel, P. Bojanowski, A. Joulin, and E. Grave Towards unsupervised dense information retrieval with contrastive learning. CoRR abs/2112.09118. External Links: Link, 2112.09118 Cited by: §A.1, §5.4. Jang et al. (2024) Y. Jang, K. Lee, H. Bae, H. Lee, and K. Jung IterCQR: iterative conversational query reformulation with retrieval guidance. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), K. Duh, H. Gomez, and S. Bethard (Eds.), Mexico City, Mexico, p. 8121–8138. External Links: Link, Document Cited by: §A.1, 5th item, Table 1, §1, §3.3, §4.1, §4.1, §4.1, §6, §7. Jang et al. (2026) Y. Jang, M. Sundriyal, K. Jung, and M. Cha How you ask matters! adaptive rag robustness to query variations. External Links: 2604.10745, Link Cited by: §2. Jin et al. (2023) Z. Jin, P. Cao, Y. Chen, K. Liu, and J. Zhao InstructoR: instructing unsupervised conversational dense retrieval with large language models. In Findings of the Association for Computational Linguistics: EMNLP 2023, H. Bouamor, J. Pino, and K. Bali (Eds.), Singapore, p. 6649–6675. External Links: Link, Document Cited by: Table 21. Johnson et al. (2017) J. Johnson, M. Douze, and H. Jégou Billion-scale similarity search with gpus. External Links: 1702.08734, Link Cited by: §A.1. Kostric and Balog (2024) I. Kostric and K. Balog A surprisingly simple yet effective multi-query rewriting method for conversational passage retrieval. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’24, New York, NY, USA, p. 2271–2275. External Links: ISBN 9798400704314, Link, Document Cited by: §3.3. Laban et al. (2026) P. Laban, H. Hayashi, Y. Zhou, and J. Neville LLMs get lost in multi-turn conversation. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: §1. Lai et al. (2025a) Y. Lai, J. Wu, Z. Wang, and D. Zhou AdaRewriter: unleashing the power of prompting-based conversational query reformulation via test-time adaptation. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, C. Christodoulopoulos, T. Chakraborty, C. Rose, and V. Peng (Eds.), Suzhou, China, p. 3889–3905. External Links: Link, Document, ISBN 979-8-89176-332-6 Cited by: §A.1, 11st item, Table 1, §1, §2, §3.3, §4.1, §4.1, §4.1, §5.5. Lai et al. (2025b) Y. Lai, J. Wu, C. Zhang, H. Sun, and D. Zhou AdaCQR: enhancing query reformulation for conversational search via sparse and dense retrieval alignment. In Proceedings of the 31st International Conference on Computational Linguistics, O. Rambow, L. Wanner, M. Apidianaki, H. Al-Khalifa, B. D. Eugenio, and S. Schockaert (Eds.), Abu Dhabi, UAE, p. 7698–7720. External Links: Link Cited by: §A.1, 9th item, Table 1, §3.3, §4.1, §4.1. Li et al. (2025) X. Li, G. Dong, J. Jin, Y. Zhang, Y. Zhou, Y. Zhu, P. Zhang, and Z. Dou Search-o1: agentic search-enhanced large reasoning models. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, C. Christodoulopoulos, T. Chakraborty, C. Rose, and V. Peng (Eds.), Suzhou, China, p. 5420–5438. External Links: Link, Document, ISBN 979-8-89176-332-6 Cited by: §1. Lin et al. (2021a) J. Lin, X. Ma, S. Lin, J. Yang, R. Pradeep, and R. Nogueira Pyserini: an easy-to-use python toolkit to support replicable IR research with sparse and dense representations. CoRR abs/2102.10073. External Links: Link, 2102.10073 Cited by: §A.1. Lin et al. (2021b) S. Lin, J. Yang, and J. Lin Contextualized query embeddings for conversational search. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, M. Moens, X. Huang, L. Specia, and S. W. Yih (Eds.), Online and Punta Cana, Dominican Republic, p. 1004–1015. External Links: Link, Document Cited by: §3.3, §7. Lin et al. (2020) S. Lin, J. Yang, R. Nogueira, M. Tsai, C. Wang, and J. Lin Conversational question reformulation via sequence-to-sequence architectures and pretrained language models. CoRR abs/2004.01909. External Links: Link, 2004.01909 Cited by: 1st item, Table 1, §4.1. Mao et al. (2024) K. Mao, C. Deng, H. Chen, F. Mo, Z. Liu, T. Sakai, and Z. Dou ChatRetriever: adapting large language models for generalized and robust conversational dense retrieval. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Y. Al-Onaizan, M. Bansal, and Y. Chen (Eds.), Miami, Florida, USA, p. 1227–1240. External Links: Link, Document Cited by: Table 21. Mao et al. (2023a) K. Mao, Z. Dou, B. Liu, H. Qian, F. Mo, X. Wu, X. Cheng, and Z. Cao Search-oriented conversational query editing. In Findings of the Association for Computational Linguistics: ACL 2023, A. Rogers, J. Boyd-Graber, and N. Okazaki (Eds.), Toronto, Canada, p. 4160–4172. External Links: Link, Document Cited by: 4th item, §4.1. Mao et al. (2023b) K. Mao, Z. Dou, F. Mo, J. Hou, H. Chen, and H. Qian Large language models know your contextual search intent: a prompting framework for conversational search. In Findings of the Association for Computational Linguistics: EMNLP 2023, H. Bouamor, J. Pino, and K. Bali (Eds.), Singapore, p. 1211–1225. External Links: Link, Document Cited by: §A.1, §J.1, §B.1, 13rd item, Figure 1, Table 1, §1, §2, §3.3, §4.1, Figure 4, §5.1, §5.5, §7. Mao et al. (2023c) K. Mao, H. Qian, F. Mo, Z. Dou, B. Liu, X. Cheng, and Z. Cao Learning denoised and interpretable session representation for conversational search. In Proceedings of the ACM Web Conference 2023, W ’23, New York, NY, USA, p. 3193–3202. External Links: ISBN 9781450394161, Link, Document Cited by: Table 21, §7. Meng et al. (2025) C. Meng, F. Tonolini, F. Mo, N. Aletras, E. Yilmaz, and G. Kazai Bridging the gap: from ad-hoc to proactive search in conversations. In Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’25, New York, NY, USA, p. 64–74. External Links: ISBN 9798400715921, Link, Document Cited by: §3.2. Mo et al. (2026) F. Mo, Y. Gao, S. Li, H. Zeng, X. Liu, Z. Tan, X. Li, J. Chen, D. Wang, and M. Jiang Agentic conversational search with contextualized reasoning via reinforcement learning. External Links: 2601.13115, Link Cited by: §1. Mo et al. (2024) F. Mo, A. Ghaddar, K. Mao, M. Rezagholizadeh, B. Chen, Q. Liu, and J. Nie CHIQ: contextual history enhancement for improving query rewriting in conversational search. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Y. Al-Onaizan, M. Bansal, and Y. Chen (Eds.), Miami, Florida, USA, p. 2253–2268. External Links: Link, Document Cited by: 10th item, Table 1, §3.3, §4.1. Mo et al. (2025a) F. Mo, K. Mao, Z. Zhao, H. Qian, H. Chen, Y. Cheng, X. Li, Y. Zhu, Z. Dou, and J. Nie A survey of conversational search. ACM Trans. Inf. Syst. 43 (6). External Links: ISSN 1046-8188, Link, Document Cited by: §1. Mo et al. (2023) F. Mo, K. Mao, Y. Zhu, Y. Wu, K. Huang, and J. Nie ConvGQR: generative query reformulation for conversational search. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), A. Rogers, J. Boyd-Graber, and N. Okazaki (Eds.), Toronto, Canada, p. 4998–5012. External Links: Link, Document Cited by: 3rd item, Table 1, §1, §4.1, §4.1, §6. Mo et al. (2025b) F. Mo, J. Zhang, Y. Hui, J. A. Sun, Z. Xu, Z. Su, and J. Nie ConvMix: a mixed-criteria data augmentation framework for conversational dense retrieval. External Links: 2508.04001, Link Cited by: Table 21. Ni et al. (2022) J. Ni, C. Qu, J. Lu, Z. Dai, G. Hernandez Abrego, J. Ma, V. Zhao, Y. Luan, K. Hall, M. Chang, and Y. Yang Large dual encoders are generalizable retrievers. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, Y. Goldberg, Z. Kozareva, and Y. Zhang (Eds.), Abu Dhabi, United Arab Emirates, p. 9844–9855. External Links: Link, Document Cited by: §A.1, §5.4. OpenAI (2025) OpenAI Introducing GPT-4.1 in the API. Note: https://openai.com/index/gpt-4-1/ Cited by: §4.1. Robertson and Zaragoza (2009) S. Robertson and H. Zaragoza The probabilistic relevance framework: bm25 and beyond. Foundations and Trends in Information Retrieval 3, p. 333–389. External Links: Document Cited by: §4.1. Rozemberczki et al. (2022) B. Rozemberczki, L. Watson, P. Bayer, H. Yang, O. Kiss, S. Nilsson, and R. Sarkar The shapley value in machine learning. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, L. D. Raedt (Ed.), p. 5572–5579. Note: Survey Track External Links: Document, Link Cited by: §6. Samarinas and Zamani (2024) C. Samarinas and H. Zamani ProCIS: a benchmark for proactive retrieval in conversations. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’24, New York, NY, USA, p. 830–840. External Links: ISBN 9798400704314, Link, Document Cited by: §3.2. Wang et al. (2024) X. Wang, Z. Wang, J. Liu, Y. Chen, L. Yuan, H. Peng, and H. Ji MINT: evaluating LLMs in multi-turn interaction with tools and language feedback. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §1. Wu et al. (2022) Z. Wu, Y. Luan, H. Rashkin, D. Reitter, H. Hajishirzi, M. Ostendorf, and G. S. Tomar CONQRR: conversational query rewriting for retrieval with reinforcement learning. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, Y. Goldberg, Z. Kozareva, and Y. Zhang (Eds.), Abu Dhabi, United Arab Emirates, p. 10000–10014. External Links: Link, Document Cited by: 2nd item, §1, §4.1, §5.5. Xiong et al. (2020) L. Xiong, C. Xiong, Y. Li, K. Tang, J. Liu, P. Bennett, J. Ahmed, and A. Overwijk Approximate nearest neighbor negative contrastive learning for dense text retrieval. External Links: 2007.00808, Link Cited by: §A.1, Table 21, Appendix H, §2, §4.1. Ye et al. (2023) F. Ye, M. Fang, S. Li, and E. Yilmaz Enhancing conversational search: large language model-aided informative query rewriting. In Findings of the Association for Computational Linguistics: EMNLP 2023, H. Bouamor, J. Pino, and K. Bali (Eds.), Singapore, p. 5985–6006. External Links: Link, Document Cited by: 12nd item, §1, §4.1, §7. Yoon et al. (2025) C. Yoon, G. Kim, B. Jeon, S. Kim, Y. Jo, and J. Kang Ask optimal questions: aligning large language models with retriever’s preference in conversation. In Findings of the Association for Computational Linguistics: NAACL 2025, L. Chiruzzo, A. Ritter, and L. Wang (Eds.), Albuquerque, New Mexico, p. 5914–5936. External Links: Link, Document, ISBN 979-8-89176-195-7 Cited by: 6th item, §4.1, §4.1. Yu et al. (2020) S. Yu, J. Liu, J. Yang, C. Xiong, P. Bennett, J. Gao, and Z. Liu Few-shot generative conversational query rewriting. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’20, New York, NY, USA, p. 1933–1936. External Links: ISBN 9781450380164, Link, Document Cited by: §1. Yu et al. (2021) S. Yu, Z. Liu, C. Xiong, T. Feng, and Z. Liu Few-shot conversational dense retrieval. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’21, New York, NY, USA, p. 829–838. External Links: ISBN 9781450380379, Link, Document Cited by: Table 21, §7. Zhang et al. (2025) W. Zhang, Y. Li, Y. Bei, J. Luo, G. Wan, L. Yang, C. Xie, Y. Yang, W. Huang, C. Miao, H. P. Zou, X. Luo, Y. Zhao, Y. Chen, C. Chan, P. Zhou, X. Zhang, C. Zhang, J. Shang, M. Zhang, Y. Song, I. King, and P. S. Yu From web search towards agentic deep research: incentivizing search with reasoning agents. External Links: 2506.18959, Link Cited by: §1. Zhu et al. (2025) C. Zhu, S. Wang, R. Feng, K. Song, and X. Qiu ConvSearch-r1: enhancing query reformulation for conversational search with reasoning via reinforcement learning. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, C. Christodoulopoulos, T. Chakraborty, C. Rose, and V. Peng (Eds.), Suzhou, China, p. 26547–26564. External Links: Link, Document, ISBN 979-8-89176-332-6 Cited by: 8th item, Table 1, §4.1, §7. Appendix A Experimental Setting A.1 Implementation Details All experiments are conducted using two NVIDIA A6000 GPUs. We implement the retrieval systems using Faiss Johnson et al. (2017) and Pyserini Lin et al. (2021a). For BM25, we follow previous work Jang et al. (2024); Lai et al. (2025b); Lai et al. (2025a). Specifically, we use k1=0.9k_1=0.9 and b=0.4b=0.4 for TopiOCQA, and k1=0.82k_1=0.82 and b=0.68b=0.68 for QReCC. For dense retrieval, we use ANCE Xiong et al. (2020), trained on MSMARCO, with maximum input lengths of 128 tokens for reformulated queries and 384 tokens for passages. Additionally, we report the results on GTR Ni et al. (2022), and Contriever Izacard et al. (2021) on TopiOCQA. Because the best document selection step may vary across runs due to LLM sampling, we additionally report multi-run statistics for this component in Appendix B.2, while the main results are reported from a single run. For all comparisons with LLM4CS Mao et al. (2023b), we implement the best-performing setting, Rewrite-and-Response (RAR), Mean Aggregation, and Chain-of-Thought (CoT). Since LLM4CS aggregates its generated queries by averaging query embeddings, it is not directly applicable to BM25. For sparse retrieval we therefore concatenate the rewrite and its response into a single query. Figure 6: RRF Softening s. We test the impact of softening parameter s on RRF ranking. A.2 Hyperparameters A.2.1 RRF Softening Hyperparameter For the RRF score softening hyperparameter s, we tested values from 0 to 100 on the validation set. As shown in Figure 6, varying the s value does not significantly affect the final MRR score, although s=0s=0 achieves the best performance. All results are therefore reported using s=0s=0. A.2.2 LLM Document Selection Model K Accuracy MRR R@5 GPT-4.1-mini 5 66.4% 41.5 49.7 10 56.1% 42.0 52.3 20 53.2% 44.3 54.6 30 49.9% 44.6 54.0 40 49.4% 45.1 54.6 50 47.2% 44.7 54.7 Llama-3.1-8B 5 54.0% 37.7 49.7 10 49.5% 39.7 51.0 20 39.9% 38.5 50.4 Table 11: LLM best document selection accuracy. We report the accuracy of LLMs on best document selection. QR Model Selection Model Accuracy MRR GPT-4.1-mini Llama-3.1-8B 48.3% 43.7 (-5.0) Llama-3.1-8B GPT-4.1-mini 52.1% 46.4 (+4.1) Table 12: Impact of selection models. We analyze the effects of the QR model and the document selection model by using different models for each component. The ++ and −- indicate the performance relative to using the original QR model as the selection model. In our framework, we use LLM reasoning to select the document that best answers a given question conditioned on its conversational history. To study the effect of the candidate set size, we vary the number of top-k retrieved documents provided to the LLM from 5 to 50 (20 for Llama). We evaluate this step using two metrics: (1) best-document accuracy, which measures how often the LLM selects the best document when it is included in the top-k candidates, and (2) the final retrieval performance measured by MRR. Table 11 shows that the best-document selection accuracy of both models decreases as the number of candidate documents increases. This trend suggests that document selection becomes more challenging as the LLM must reason over a larger candidate set. However, for GPT-4.1-mini, the final retrieval performance continues to improve as k increases, with MRR reaching its best value at k=40k=40. In contrast, Llama-3.1-8B shows substantially lower selection accuracy overall, and its performance becomes unstable when the number of candidate documents exceeds 20. This indicates that Llama-3.1-8B struggles to follow the selection instructions reliably in larger candidate sets. To further understand whether the lower performance of Llama-3.1-8B comes from weaker candidate generation or from the document selection step itself, we conduct an additional analysis in Table 12. When GPT-4.1-mini is replaced with Llama-3.1-8B as the selection model, the MRR drops by 5.0 points. Conversely, when GPT-4.1-mini is used as the selection model in the Llama-based setting, the MRR improves by 4.1 points. These results indicate that the final performance is influenced by both the quality of the query candidates and the effectiveness of the best-document selection model. Based on the validation results, we set the number of input documents in the document selection stage according to each model’s capacity. Specifically, GPT-4.1-mini performs best with the top 40 documents on MRR, whereas Llama-3.1-8B remains most stable when given the top 10 documents. A.3 Dataset QReCC TopiOCQA CAsT-19 CAsT-20 # Dialogues 2775 205 50 25 # Turns 8209 2514 479 208 # Collections 54M 25M 38M 38M Table 13: Statistics of conversational search test datasets: QReCC, TopiOCQA, CAsT-19, and CAsT-20. In Table 13, we summarize the statistics of the datasets used in our experiments. All four datasets provide test sets with gold document annotations for conversational queries. The reported numbers correspond to the test instances with valid gold documents. Additionally, for hyperparameter tuning, we randomly sample 700 turns from the TopiOCQA training set. Appendix B Analysis of LLM-based Document Selection B.1 Document Selection on Different Method Setting MRR NDCG@3 CompCQR (w/o LS) 37.8 36.5 CompCQR (ours - w/ LS) 42.3 (+4.5) 41.5 (+5.0) LLM4CS 35.2 34.8 LLM4CS (w/ LS) 36.4 (+1.2) 36.7 (+1.9) Table 14: LLM4CS with top-1 document selection. We report the results obtained by applying top-1 LLM document selection (LS) to the LLM4CS method. In this section, we further compare the performance of the baseline LLM4CS Mao et al. (2023b) with and without LLM-based best-document selection. We evaluate both settings on the TopiOCQA dataset using Llama-3.1-8B-Instruct. In Table 14, consistent with the results in Section 5.2, our method benefits substantially from LLM-based document selection, achieving gains of up to 4.5 MRR points, whereas LLM4CS shows only a small increase of 1.2 points. B.2 Multi-run Statistics for Best-document Selection To examine the stability of LLM-based document selection, we report multi-run statistics for the top-10 document selection setting. We focus on this setting because the stability of LLM decisions directly affects retrieval performance. We run the LLM-based best-document selection process three times under the same top-10 setting and report the mean and standard deviation for each metric. The results show consistent performance across runs, with an MRR of 42.2 ± 0.9 and nDCG of 41.3 ± 0.6. These results suggest that LLM-based selection in the top-10 setting is reasonably stable and that our main findings are unlikely to be driven by run-to-run randomness. MRR NDCG@3 R@5 RRF Aggregation 37.8 36.5 - + w/ LS (ours) 42.3 41.5 53.7 + w/ LR 26.7 24.1 43.7 Table 15: Performance comparison of LLM-based document selection and ranking. We compare RRF document aggregation with variants using LLM document selection (LS) and LLM document full reranking (LR). B.3 Comparison with Re-ranking We compare our top-1 document selection step with LLM-based reranking over the top 10 retrieved documents. We conduct the experiment on the TopiOCQA dataset using Llama-3.1-8B. As shown in Table 15, the results indicate that selecting a single top document is an easier task for the model, allowing it to identify the gold document more effectively. In contrast, reranking multiple documents is a more complex decision-making task that introduces additional noise, leading to substantially degraded performance. Appendix C Component Analysis C.1 Number of Queries and Components Figure 7: Upper-bound MRR with accumulated queries. We report upperbound of MRR on TopiOCQA. Figure 7 shows the upper-bound MRR on TopiOCQA with ANCE as the number of applied queries increases. Retrieval performance improves steadily as more candidates are included, but the gains begin to saturate around 250 queries. This suggests that broad compositional coverage is beneficial, while also indicating that selecting an optimal subset of queries could be a promising direction. Appendix D Generalization to Different Models D.1 Dense Retrievers Retriever Top-10 Jaccard Distance ANCE 28.0% GTR 22.6% Contriever 23.2% Table 16: Top-10 Jaccard Distance under query-component reordering. We also report the order sensitivity analysis from Section 2 using GTR and Contriever in Table 16. Although the change rates for GTR and Contriever are lower than that of ANCE, both retrievers still exhibit substantial changes in their top-10 retrieved documents under reordering components. This suggests that order sensitivity is a general property of dense retrievers rather than an artifact specific to ANCE. D.2 Large Open-source Models Method LLM MRR NDCG R@100 LLM4CS Qwen2.5-72B 43.4 42.2 82.2 CompCQR Qwen2.5-72B 47.4 46.6 83.4 LLM4CS Llama-3.3-70B 45.3 44.5 83.6 CompCQR Llama-3.3-70B 48.6 47.5 84.0 Table 17: Retrieval performance with large open-source LLMs. We report results on TopiOCQA using the ANCE retriever. We additionally evaluate CompCQR with two strong open-source LLMs, Qwen2.5-72B and Llama-3.3-70B, on TopiOCQA dataset with ANCE retriever. As shown in Table 17, CompCQR consistently outperforms LLM4CS-5 across all retrieval metrics for both models. With Qwen2.5-72B, CompCQR improves MRR from 43.4 to 47.4, corresponding to a 9.2% relative improvement. Similarly, with Llama-3.3-70B, CompCQR improves MRR from 45.3 to 48.6 (+7.3% relative), with consistent gains in nDCG@3 and R@100. These results demonstrate that the effectiveness of CompCQR is not limited to a specific proprietary LLM and generalizes well to strong open-source LLMs. Appendix E Topic Shift Performance Figure 8: Topic Shift Performance. We test the framework performance in topic-shift (TS) and topic-concentrated (TC) turns. We conduct an additional analysis on TopiOCQA by dividing the test instances according to whether the topic changes from the previous turn. Using the topic labels provided in the dataset, we define a turn as topic-shift (TS) when its topic differs from that of the preceding turn, and as topic-concentrated (TC) otherwise. In Figure 8, results show a clear difference across models. GPT-4.1-mini preserves its performance under topic shifts and even achieves better results in those cases, while LLaMA-3.1-8B suffers from a slight degradation. This discrepancy is likely attributable to differences in the underlying model capacity. More specifically, the findings indicate that the ability to correctly interpret conversational context plays a crucial role in handling topic transitions effectively. Appendix F LLM Calls and FLOPs Method LLM Calls TFLOPs MRR CHIQ-Fusion 6 - 38.0 LLM4CS (k=5) 5 69 34.6 LLM4CS (k=16) 16 114 35.4 CompCQR (w/o LS) 2 74 37.8 CompCQR 3 109 42.3 Table 18: Computational Cost. We compare the number of LLM calls, FLOPs per query, and corresponding TopiOCQA MRR across different methods. We report both CompCQR without LLM selection and the full framework. We compare the cost of CompCQR with prompting-based baselines in terms of LLM calls and FLOPs. As shown in Table 18, CompCQR achieves the best MRR with only three LLM calls, and the variant without LLM selection already surpasses LLM4CS (k=16) with two calls and fewer FLOPs. This indicates that the gain comes from compositional generation rather than from additional inference. We further note that although our framework processes more input tokens by conditioning on top-ranked documents during selection, this cost stems from longer input processing rather than repeated generation, which is typically cheaper in both latency and API pricing. Appendix G Case Study G.1 Mitigating Hard Negatives Original Query: Describe core, aggregator, and edge switches. Category Document LLM Passage Analysis RRF 1st-ranked “This makes a large core switch a logical way to handle traffic passing between … Top-of-rack switches are designed slightly differently from user edge switches …” Passage 1 describes core switches and their roles, including their switching capacity and position in the network. … with some details on data center use. LLM-selected (Rank: 3) “… an additional layer of switching, called the distribution layer, aggregates the edge switches. … The aggregation layer connects to the uplinks of the edge switches and is uplinked to the … network core.” Passage 3 explicitly describes the distribution and aggregation layers, explaining how aggregation layers connect edge switches and aggregate uplinks. … including the rationale behind the layers and design considerations. Reason for Selection Passage 3 provides a clear and direct explanation of core, aggregator (aggregation), and edge switches … making it the most suitable to answer the query comprehensively. Table 19: Case study of a hard negative in RRF top-1 ranking. Although the top-ranked RRF document is a hard negative, the LLM correctly identifies the relevant gold document that was originally ranked third. In Table 19, we present a case in which LLM document selection step successfully distinguishes a hard negative from retrieved documents. The top-ranked document under RRF is topically relevant but only partially addresses the query, whereas the document selected by the LLM provides a more complete explanation. This shows that LLM-based selection can recover a suitable document even when rank fusion places a hard negative at the top. G.2 Failure Analysis Component Content Rank Original Query Regarding the ancient kingdom above; was any innovation made that time? 6 Rewrite What innovations were made during the time of the ancient kingdom of Macedon? 1 Rewrite Answer …One notable innovation was the development of the phalanx formation, a tactical … 36 Follow-up Query What were some of the notable innovations and achievements …particularly during the reign of Alexander the Great? 7 Follow-up Answer …particularly during the reign of Alexander the Great, was known for several notable innovations and achievements … >100>100 CompCQR (RRF only) 8 Table 20: A failure case from TopiOCQA. We report the gold-passage rank for each component in the rightmost column. The generated components are truncated for readability. We provide a concrete failure case from TopiOCQA where CompCQR underperforms a single-rewrite method. Table 20 shows the generated components and their corresponding gold-passage ranks. In this example, the rewritten query retrieves the gold passage at rank 1. However, the auxiliary components introduce sub-topic drift: the rewrite answer focuses on military innovations such as the phalanx, while the follow-up components shift toward Alexander the Great’s broader achievements. Since the gold passage instead concerns agricultural and glass-related innovations, these partially off-topic signals dilute the strong rewrite signal under reciprocal rank fusion, moving the gold passage from rank 1 to rank 8. This suggests that while component diversification is beneficial on average, it can hurt when generated components retrieve plausible but mismatched evidence. Appendix H Comparison with CDR Method TopiOCQA QReCC Conv-ANCE Xiong et al. (2020) 20.5 45.6 ConvDR Yu et al. (2021) 26.4 35.7 Conv-SPLADE Formal et al. (2021) 29.5 46.6 InstructOR-ANCE Jin et al. (2023) 23.7 40.5 LeCoRE Mao et al. (2023c) 32.0 51.1 ConvAug Chen et al. (2024) 33.3 50.4 ChatRetriever Mao et al. (2024) 40.1 52.5 ConvMix Mo et al. (2025b) 36.6 50.7 CompCQR (ours) 47.7 58.6 Table 21: Comparison with CDR Methods. We report results on TopiOCQA, and QReCC with NDCG@3. In this section, we compare CompCQR with various CDR methods. As shown in Table 21, our method achieves the best performance, outperforming the second-best CDR method by 7.6 NDCG@3 points on TopiOCQA. We use the same dense retriever as the Conv-ANCE (2020) baseline. Appendix I Baseline details. We briefly summarize the baselines used in our experiments below. • T5QR Lin et al. (2020): A supervised T5-based query rewriting model fine-tuned to generate standalone rewrites for conversational search. • CONQRR Wu et al. (2022): A query rewriting model trained with reinforcement learning to directly optimize downstream retrieval performance for a fixed black-box retriever. • ConvGQR Mo et al. (2023): A trained generative reformulation framework that combines query rewriting with generated answer information for query expansion. • EdiRCS Mao et al. (2023a): A supervised text-editing-based conversational query rewriting model that copies most rewrite tokens from the dialogue context and generates only a small number of additional tokens. • IterCQR Jang et al. (2024): An iterative conversational query reformulation framework that optimizes the reformulation model using retrieval signals rather than relying solely on human rewrite annotations. • ReTPO Yoon et al. (2025): A retriever preference optimization framework that fine-tunes a query rewriting language model using retrieval feedback so that generated rewrites better align with the preferences of the target retriever. • ICR Cao et al. (2025): A trained iterative clarification-and-rewriting framework that improves reformulation quality by generating clarification signals before rewriting ambiguous conversational queries. • ConvSearch-R1 Zhu et al. (2025): A conversational reformulation framework trained with reinforcement learning to optimize query rewriting directly with retrieval-based rewards, without requiring rewrite supervision. • AdaCQR Lai et al. (2025b): A hybrid reformulation framework that combines a fine-tuned query rewriting model with LLM-based fusion to improve robustness across retrieval settings. • CHIQ-Fusion Mo et al. (2024): A hybrid method that combines a trained query rewriting model with LLM-based history enhancement and ambiguity resolution. • AdaRewriter Lai et al. (2025a): A prompting-based reformulation framework that uses test-time adaptation and a lightweight reward model to select the most effective rewrite candidate. • LLM-Aided Ye et al. (2023): A training-free query rewriting approach that uses an LLM to generate more informative rewrites without task-specific model training. • LLM4CS Mao et al. (2023b): A training-free prompting framework that uses an LLM to generate multiple rewrites and hypothetical responses for conversational search. Appendix J Prompt J.1 Rewrite Query and Answer Generation Prompt PrewriteP_rewrite rewrites the query and potential answer with given history context. We directly follow the prompts from LLM4CS RAR setting Mao et al. (2023b). J.2 Follow-up Query Generation Prompt PfollowP_follow generates the follow-up query and answer with given history context. Follow-up Query and Corresponding Answer Generate a follow-up query and its answer based on the previous query and answer. The follow-up query should be highly relevant to the topic and context of the conversation. (Closely related so that both questions are likely to be answered by a passage.) If no follow-up is needed, return an empty string. Please format your output exactly as follows: "followup_query": "Your highly related query here", "next_answer": "Your corresponding answer here" Context: History Context Current Query: Current Query J.3 LLM Best Doc Selection This prompt selects the best 1 document given top-k documents, that best answers the given question and history context. Best Document Selection You are an expert in question answering. Your task is to select the most relevant passage from the given passages based on the query. I will provide you with k passages, each with a passage number. Select the passage based on their relevance to the search query: question. Dialogue History: formatted_context Search Query: oq Passages: passage_text Please follow the steps below: Step 1: List up the information required to answer the search query and rewrite the query into a standalone and de-contextualized query. Step 2: Analyze whether each passage has the information required to answer the search query. Step 3: Choose the passage that mostly covers clear and diverse information to answer the query. The format of the final output should be as follows: "query analysis": "<step 1 output, your analysis of the query and the rewritten query>", "passage analysis": "<step 2 output, analysis>", "reason for selection": "<step 3 output, reason for selecting the passage>", "selected_passage_number": "<the number of the selected passage, chosen from 1 to TOP_K>" J.4 LLM Doc Full Reranking In Section B.3, we compare the performance of LLM-based document selection and full reranking over the top-10 documents. The prompt below corresponds to the latter setting, in which all top-k documents are ranked according to their relevance to the given question and dialogue history. LLM Document Ranking You are an expert in information retrieval and passage ranking. Your task is to rank the given passages by their relevance to the query. I will provide you with TOP_K passages, each indicated by a passage number from 1 to TOP_K. Rank all passages based on their relevance to the search query. Dialogue History: context Search Query: query Passages: passage_text Please follow the steps below: Step 1: Analyze the search query in the context of the dialogue history and rewrite it into a standalone query. Step 2: Evaluate each passage’s relevance to the search query. Step 3: Rank all TOP_K passages from most relevant to least relevant. The format of the final output should be as follows: "query_analysis": "<step 1 output, your analysis and rewritten query>", "passage_analysis": "<step 2 output, brief relevance analysis of each passage>", "ranking": [<step 3 output, comma-separated passage numbers from most to least relevant, e.g., 3, 1, 5, 2, 4, 7, 6, 8, 10, 9>] Appendix K Usage of GenAI AI-assisted coding tools were used to support data analysis and visualization, including drafting and debugging scripts for figure/table generation. All code and results were subsequently reviewed and validated by the authors.