POQD: Performance-Oriented Query Decomposer for Multi-vector retrieval
Authors: Yaoyang Liu
Junlin Li
Yinjun Wu
zhen chen
Venue: ICML 2025 poster (2025)
Keywords: information retrieval
retrieval-augmented generation
Primary area: applications

Abstract: Although Multi-Vector Retrieval (MVR) has achieved the state of the art on many information retrieval (IR) tasks, its performance highly depends on how to decompose queries into smaller pieces, say phrases or tokens. However, optimizing query decomposition for MVR performance is not end-to-end differentiable. Even worse, jointly solving this problem and training the downstream retrieval-based systems, say RAG systems could be highly inefficient. To overcome these challenges, we propose Performance-Oriented Query Decomposer (POQD), a novel query decomposition framework for MVR. POQD leverages one LLM for query decomposition and searches the optimal prompt with an LLM-based optimizer. We further propose an end-to-end training algorithm to alternatively optimize the prompt for query decomposition and the downstream models. This algorithm can achieve superior MVR performance at a reasonable training cost as our theoretical analysis suggests. POQD can be integrated seamlessly into arbitrary retrieval-based systems such as Retrieval-Augmented Generation (RAG) systems. Extensive empirical studies on representative RAG-based QA tasks show that POQD outperforms existing query decomposition strategies in both retrieval performance and end-to-end QA accuracy. POQD is available at https://github.com/PKU-SDS-lab/POQD-ICML25.

POQD: Performance-Oriented Query Decomposer for Multi-vector retrieval
Yaoyang Liu'
Junlin Li
Yinjun Wu?
Zhen Chen
Abstract
Callan, 2021; Zhao al., 2024c). It underpins many sys- tems, in particular, retrieval-angmenned generation (RAG) frameworks (Karpukhin et al., 2020), where retrieval accu- racy is paramount. Vectii Retrieval (MVR) enhances retrieval accuracy by leveraging multiple representations for finer- sner-grained matching (Khattab & Zaharia, 2020). MVR methods, e.g., ColBERT (Khattab Zaharia, 2020), decom- pose queries and documents into smaller units, say tokens. For each query token, we identify the most similar doc- ument piece to it and calculate their similarity, which is referred to as the MaxSim operation in (Khattab & Zaharia, 2020). Such scores are then aggregated across all query to- kens as the overall query-document similarity. Compared to standard dense retrieval solutions, this strategy more effec- tively captures the fine-grained similarities between queries and documents, enhancing performance in information re- trieval (IR) tasks (Khattab & Zaharia, 2020; Santhanam et al., 2022b) and et al., 2024).
Although Multi-Vector Retrieval (MVR) has achieved the state of the art on many information retrieval (IR) tasks, its performance highly de- pends on how to decompose queries into smaller pieces, say phrases tokens. However, optimiz- ing query decomposition for MVR performance is not end-to-end differentiable. Even worse, jointly solving this problem and training the downstream retrieval- based systems, say RAG systems could highly inefficient. To overcome these chal- lenges, we propose Performance-Orient Decomposer (POQD), novel query decomposi- tion framework for MVR. POQD leverages one LLM for query decomposition and searches the optimal prompt with an LLM-based optimizer. We further propose an end-to-end training algo- rithm to alternatively optimize the prompt for query decomposition and the downstream mod- els. This algorithm can achieve superior MVR performance reasonable training cost as theoretical analysis suggests. POQD can be inte- grated seamlessly into arbitrary retrieval-based systems such as Retrieval-Augmenter Genera- tion (RAG) systems. Extensive empirical stud- ies on representative RAG-based QA tasks show that POQD outperforms existing query decom- position strategies in both retrieval performance and end-to-end QA accuracy. POQD is available at https:://// / /ggtttb...b/g/////g////gg.b..t com/PKU-SSS-aab TCM.25.
Query
systems like RAG (Xu
In this paper, we aim to develop a new MVR strategy to enhance the performance of arbitrary retrieval-based sys- tems, with particular focus on RAG systems. Note that traditional MVR approaches, in particular, ColBERT (Khat- tab & Zaharia, 2020), decompose queries at the token level. However, as revealed in Section 2, decomposing queries into slightly more coarse-grained units, such as phrases, can yield better results for tasks like retrieval- auggmenedd generation (RAG). Furthermore, we observe that the perfor- mance of these tasks highly depends on how we decompose queries. Considering that the space of all possible decom- posed sub sub-queries is exponentially large, this thus raises one critical question, i.e., how can we effectively generate sub- queries of arbitrary granularity to optimize the performance of downstream serieval-bassed systems?
1. Introduction
Dense retrieval retrieves documents by evaluating their sim- ilarity scores with user queries (Mitra et al., 2018; Gao &
Query decomposition has been widely studied in question answering (QA), especially in multi-hop QA. aims to break down complicated questions into simpler components, allowing Large Language Models (LLMs) to reason step by step, thereby enhancing QA accuracy. Various question de- composition strategies exist, such as (L.i et al., 2024), which prompts LLMs with manually crafted prompts for query decomposition. However, as shown in Figure 1, applying the resulting sub-queries MVR could retrieve an incor- rect image, ultimately generating wrong answer in the
'School of Infomation, Renmin University "School of Computer Science. Peking University 'Fundamental Indus- try Training Center, Tsinghua University. Correspon- dence to: Yinjun Wu <wuyinjun@@ pku.edu.en>, Zhen Chen <zhenchen seainghaa.cdu.cn....
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

POQD: Performance-Orientee Query Decomposer for Multi-vector retricval
Query decomposition
Multi-vector retrieval
Retrieved Image
ColBERT
Viciona
Hong
Kong
Image
Answer
Decompase
has
many
what
Generater x
tokens
bype
of
buildings
Maxhim
X
Apti
Query
Image 2
Victoria Hong Kong
Victoria Kong many what type of buildings?
Manual prompting
MaxSim
Generator Y+
Tai X
buildings
MosSSin
type
AMD
Image
Optimized prompting by POQD
Victoria Hong Kong
Generator g
Skyecrapers
buildings
Figure 1. Motivating example from ManyModalQA dataset (Hamnan et al., 2020). We aim to answer the question "Victoria Hong Kong has many what type of buildings?" using eetrivaa--uummente generation (RAG). To enhance the retrieval accuracy and thus ensure the answer correctness, employ Multi-Vector Retrieval (MVR), which decomposes the query into sub-queries and embeds them. MaxSim operations (as defined in (Khattab & Zaharia, 2020)) are then applied to compute similarity scores for retrieval. Traditional query decomposition strategies, which are primarily based heuristics, such as decomposing by tokens (Khattab & Zaharia, 2020) or by prompting LLMs with manually crafted prompts (Li et al., 2024), often retrieve irrelevant images, thus resulting in incorrect answers. In contrast, we optimize LLM prompts to generate more effective sub-queries, improving QA accuracy. This approach enables MVR retrieve images of Victoria Harbour with skyscrapers, leading to the correct answer: ""kkyscapers"..
RAG-based QA tasks.
We further perform extensive empirical studies to evaluate the effectiveness of POQD on variety of RAG-based QA tasks, covering both image and text QA tasks. The empirical studies suggest that POQD can outperform the state-of-the. art in both retrieval and QA accuracy by a large margin.
To address this issue, it would be ideal to train a model for searching the decomposed sub-queries that can opti- mize the downstream performance. However, two critical technical challenges arise. First, the search process is non- differentiable, sub-queries cannot propagate gradients from the downstream performance score. Second, evalu- ating candidate sub-queries requires training downstream RAG models, which is computationally expensive.
Our contributions can be summarized follows:
1. We introduce POQD, novel query decomposition frame- work that can perform query decomposition for optimiz- ing multi-vector retrieval performance.
To tackle these two challenges, we proposed Performance- Oriented Query Decomposer (POQD for abbreviation), a query decomposition framework. To address the non-differentiabiliiy issue, we first prompt one L.M generate decomposed sub-queries for one input query, which can be iteratively refined by an LLM-based optimizer (Yang et al., 2024) to enhance downstream perfor- mance. But evaluating a candidate prompt requires train- ing the downstream model, O, with its induced sub-queries. Hence, we propose a training algorithm to alternatively re- fine the prompt p while only training the model θ for few epochs. Our theoretical analysis confirms the effec- tiveness of this approach with appropriate hyper-parameter configurations.
2. We design a training algorithm, which alternates between training the downstream RAG models and refining the prompt used for query decomposition. Theoretical anal- ysis demonstrates the effectiveness of this training algo- rithm with appropriate hyper-paramettr configurations. 3. We perform extensive experiments on RAG-based QA tasks, covering both image QA and text QA, which sug- gests that POQD can outperform the state-of-the-an in both retrieval and QA accuracy by a large margin.
novel performance-diee
2. Motivation
We conduct an in-depth analysis of the motivating example shown in Figure to further motivate our method.
Note that such performance optimization process con- ducted in weakly-superrvised manner since the downstream RAG performance rather than the intermediate retrieval per- formance is optimized. This strategy is even effective in applications such Multi-hop QA (Yang al., 2018), in which the queries are dynamically generated during the reasoning process.
2.1. Why does ColBERT fail?
To understand why ColBERT fails in the example shown in Figure 1, we perform MVR with mini-query "Hong Kong". For this query, ColBERT tokenizes it into two individual tokens, "Hong" and "Kong". For each image, we then per- form the Max operation between these two tokens and
2

---

POQD: Performance-Oriented Query Decomposer for Multi-vector retricval
Problem definition Given one query Q
hong
kong
(2,,,o,.....56 .. composed of m tokens, we aim to decompose it into n sub-queries { in which each qi is composed of tokens from {c1, 22,..,,., Cm The goal of performing this query decomposition is to maximize the performance of downstream retrieval-based systems.
0.2368
0.2101
0.4469
Greater than
X
0.2372
0.1911
0.4283
3. Preliminary
3.1. Multi-vector retrieval
Figure 2. Further analysis on the motivating example: the token "kong" is relevant to the photo of a black gorilla- wriilla-like monster, which is mostly black. Coincidentally, in the photo of Lee Kuan Yew. the patch identified as the most relevant to the token 'kong' also mostly black.
To evaluate the similarity score between a query Q, and a document or image D. Multi-vector retrieval first decom- poses Q and D into fine-grained pieces, denoted by (q: )= and (d, )= applies MaxSim operation to identify the most similar dj to each qi and then aggregates these similarity scores across all gi with the following formula:
the fine-grained image patches, i.e., determine the similarity score between one token and its most similar image patch. Such similarity scores are subsequently aggregated across all tokens to obtain the overall query-documen document similarity score. As depicted in Figure 2, a surprising result emerges: despite its visual irrelevance to Hong Kong, the photo of Lee Kuan Yew, the 1st Prime Minister of Singapore exhibits higher similarity to the mini-query "Hong Kong" than the ground-truth image. A deep investigation suggests that the token "kong" could refer to black gorilla-like monster, thus yields unrealistically high similarity to the image patch highlighted with a green bounding box since both this patch and the figure of " "Kon" are mostly black. This coincidence thus leads a higher ranking of the Lee Kuan Yew's image than the ground truth. In contrast, by treating "Hong Kong" as a unified phrase and evaluating its similar- ity to each image, the ground-trute image achieves higher similarity score than other images. This example thus un- derscores the necessity of decomposing queries at a slightly coarser-grained level, rather than the token level for MVR.
SIM, (Q, = K >x
max Ea(4:) Eo(d)) (1)
As mentioned in Section 2, we primarily study how to optimize the query decomposition process. But how to de- compose documents or images may also matter. Therefore, to ensure a fair comparison between different query decom- position strategies, we decompose documents or images in the same way across all baseline methods and POQD. One exception is ColBERT for text retrieval, which is configured to decompose documents into tokens.
3.2. Augmentee Generation (RAG)
As introduced in Section 1, we primarily study the effec- tiveness of POQD on RAG tasks. For this task, aim to optimize the following objective function:
(()) = - log! Σ DDDDK PolaQQ, (DI1),,
(2)
in which θ (), and DR represents the set of Top-K' most relevant documents to a query Q according to the sim- ilarity score defined in Equation (1). Additionally, Po rep- resents the likelihood of the ground-trutt answer a, which is parameterized by the generator model parameter 9. Note that this objective function relies on the similarity function defined in Equation (1) determine the Top-K most rele- vant documents, thus implicitly dependent on how queries are decomposed. Also, we follow prior studies such as (Barnett et al., 2024), to only train 0 while maintaining the retrieval model, 3, in RAG systems fixed to ensure training efficiency. This is because updating retrieval models usually requires rebuilding indexes and re-embedding corpus, which could be highly time-consuming.
2.2. Why essential to optimize query decomposition?
As mentioned in Figure we can manually craft prompts for I.LMs so that they can generate decomposed sub-queries (Li et al., 2024). These sub-queries include critical phrases such as "Victoria Hong Kong" and "building". However, performing MVR with these sub-queries still incorrectly retrieves a less relevant image (see the second row of Figure I). In comparison to the optimal sub-queries discovered by our solutions, this method generates one extra sub-query "type". This extra sub-query is less informative than the other two sub-queries. Thus incorporating this sub-query into MVR may lead to inaccurate similarity scoring. There- fore, optimizing the query decomposition process by climi- nating non non-essential sub-queries, such as "type," is crucial for improving retrieval accuracy. Hence, the problem to be addressed is formally defined as follows.
4. Methodology
This section starts with the framework overview in Section 4.1, which is followed by illustrating how to generate opti- mal sub-queries with POQD in Section 4.2 and describing
3

---

POQD: Performance-Drientel Query Decomposer for Multi-vector retricval
our end-to-end training algorithm in Section 4.3. We con- clude this section with a theoretical analysis of the training algorithm in Section 4.4.
following two steps. The goals of these two steps are to generate candidate prompt for the Query Decomposer by invoking the Prompt Optimizer, and to evaluate the quality of the prompt with the training loss [(O:p) p) respectively.
4.1. Framework overview
Step I: By following (Yang et al., 2024), the Prompt Op- timizer aims to produce a prompt prefix po. say, "Design a query decomposition framework that..." as shown in Figure 3, which is then concatenated with fixed prompt template, including the description of the query decomposition task and one input query Q, to construct a complete prompt p for the Query Decomposer. Hence, searching optimal p is equivalent to searching optimal prompt prefix Po- The generation of one candidate prompt prefix pu is conducted by prompting the Prompt Optimizer with two pieces of meta-prompts and dynamically constructed solution-score pair list (see Figure 3). This list is initially empty and then gradually populated with the pairs of the prompt prefix Po produced by the Prompt Optimizer and the corresponding training loss p(::p) as Algorithm 1 is executed. Intuitively speaking, Po is regarded as the solution to this optimizer while L(O: p) is viewed as the score of this solution.
Given query Q, we aim to perform query decomposition by prompting one LLM (referred to as the Query Decomposer) with a prompt p. Those sub-queries are then employed to perform multi-vector retrieval. Therefore, the quality of the sub-queries produced by the Query Decomposer highly depends on the prompt p. In light of this, we propose to adopt an LLM- based optimizer (referred to as the Prompr Optimizer) to generate p and iteratively refine it for opti- mizing the downstream performance (see Section 4.2). The pipeline of generating prompt p and producing decomposed sub-queries with this prompt is visualized in Figure 3.
As mentioned in Section I, the performance to be optimized in our setup would not only depend on O but also depend on the decomposed sub-queries. which is further dependent on the prompt p. Hence, the loss function defined in (2) is reformulated as p): To optimize this loss function, we proposed an end-to-end training algorithm to jointly optimize and + (see Section 4.3).
Step 2: To construct the above solution-score pairs, in par- ticular, attaining the training loss L(O;p) for one candidate prompt p. we thus prompt the Query Decomposer with p to generate the decomposed sub-queries for each query in the training set. These sub-queries are then used to perform MVR in the downstream sttreval--aase system and evalu- ate the training loss L(O:p) on all training queries. Then the pair (p, L(O: p)) is appended the solution-score pair list as shown in Line 6.
In Section 4.4, we further provide a theoretical analysis of this end-to-end training algorithm. It suggests that with appropriate hyper-parameter configurations, this algorithm can effectively optimize the prompt p and minimize the loss L(O:p) at reasonable training cost.
4.2. Optimize query decomposition with fixed C
According to (Yang et al., 2024), as more solution-score pairs are included from prior iterations of Algorithm 1, the Prompt Optimizer can gradually refine the prompt for the Query Decomposer which may produce smaller training loss. In the end, Algorithm terminates if the training loss with the updated prompt, L(O: p). is at least smaller than that with the initial prompt pold by or the while loop is repeated for k iterations (see Line 7 in Algorithm 1).
Algorithm 1 Optimize query decomposition
1: Input: A set of training queries: Quain, retricval--asse sys- tom parameterized by e, the old prompt old
2: Initialize the solution-score pairs LS = [(pr)) ((O:p")))
3: while not converge do
4: Prompt the Prompt Optimizer by leveraging LS to generate a new prompt p with Step 1 of Section 4.2.
5: Execute Step 2 to decompose each query in Qunin by prompting the Query Decomposer with p.
Note that the Query Decomposer may hallucinate, in par- ticular, the generated sub-queries may contain tokens that do not exist in the input query. To mitigate this, we filter out irrelevant tokens in these sub-queries. The effect of this filtering step is empirically evaluated in Appendix D.3.
6: Evaluate the training loss, p(O:p), over Qitiin and add (p. p)): to I.
7: if L(O: [(O; (d I a repeated for iterations
then
8: Break
9: end if
10:
end while
4.3. End-to-end training algorithm
11: return p and decomposed sub sub-queries
Note that in Section 4.2, we optimize the prompt with a fixed O Indeed, the sub-queries produced by Algorithm I impact the input θ thus motivating the need to further update O As a consequence, we propose an end-to-end training algorithm outlined in Algorithm 2. This algorithm aims to alternatively optimize the prompt for the query
Given a retrieval-based system with a fixed parameter O we elaborate on how to search optimal decomposed sub- queries in this section. Recall that solving this optimization problem is not differentiable, we overcome this challenge by leveraging Algorithm 1, which iteratively executes the
4

---

POQD: Performance-Drientee Query Decomposer for Multi-vector retricval
meta-prompt
prompt prefix
Your task generate the instruction <INS>. Below are some previous instructions with their scores, The score ranges from 0 to 100.
Design query decomposition framework that seamlessly integrates logical soundness...
# solution-score pairs
Prompt Optimizer
task decription
Query Decomposer
text:
Decompose query Q Into a set of semantically connected...
query below, split it semannically aligned sub- queries, separated by and only output the sub-queries. Do not include any other information or explanation.
<INS>
score:45
text:
You are query decomposition assistant.....
Score: 46
'columns Southampton buildings color"
input query
What color the columns on Southampton buildings?
# mmta--prompt
Generate an instruction that different from the instructions <INS> above, and has higher score than all the instructions <INS> above.....
Figure 3. The pipeline of generating decomposed sub-queries. This pipeline primarily consists of two LLMs, one serving as the Prompt Optimizer while other one serving as the Query Decomposer. The prompt optimizer first takes two pieces mela-prompts as well solution-score pairs collected during the execution of Algorithm as input and produces the optimized solution, which is an essential prompt prefix for the Query Decomposer. In addition, the query decomposer further incorporates the description of the query decomposition task and one input query in the prompts. The decomposed sub-queries (separated by vertical lines 'I') are then generated by the Query Decomposer.
Algorithm 2 Training POQD
more. In the end, we optimize the loss L(O; with fixed until convergence, resulting in an optimized parameter O (p) (see Line 11 of Algorithm 2). We use the notation (p) to denote its dependency on the prompt p.
1: Input: set training queries: Q" a retrieval- baase sys- tem parameterized by e.
2: Initialize one random pd
3: while not converge do
4: Invoke Algorithm by inputting pale obtain new prompt
Note that in Algorithm I, the training loss gets reduced by when the prompt is updated from pull to prew However, this may not necessarily guarantee decreased training loss at convergence, i.e., L( ; > I(O"(p (p"""); pPw), which is critical to ensure the optimality of the derived prompt peew. Otherwise, it would be meaningless to update this prompt. Hence, in Section 4.4, we provide a rigorous theoretical analysis show that the above inequality holds with appropriate and without hurting training efficiency.
p= and optimized sub-queries.
5: pf" == oid then
6: Break
7: end if
Train for J iterations with optimized sub-queries by minimizing ((0:p"*) with nnw fixed.
9: pall new
10: end while
11: Train O until convergence with optimized sub-queries by min-
imizing L(O:p"y with new fixed.
4.4. Theoretical analysis
decomposer and train θ until convergence.
In this sub-section, before formally presenting the theoreti- cal results, list some essential assumptions below.
Note that at each iteration of Algorithm 2, we could option- ally train O until convergence given sub-queries produced by Algorithm I. However, in many retrieval-based systems such RAG systems, performing full training on Ô could be highly expensive. For instance, training the RAG model with large image QA dataset takes up hour per epoch as revealed in Section 5, which usually needs at least 5 epochs to converge. Hence, in Algorithm 2, we alternatively optimize the prompt and sub-queries Line 4 and update for iterations with the optimized sub-queries in Line This repeated until the prompt cannot be updated any-
Assumption 4.1 (μ-PL* condition and L-smoothness). C(O: p) satisfies the condition (Liu et al., 2022) and L-smoothness for any θ with a given p. i.e..:
star (μ-PL**)
[[L((:))] pC():p)
(PL* condition)
L
((0xp) < (()pp) veL(Or:) 11) 110 0
(L-smoothness)
Indeed, according to recent theoretical results (Liu et al.),
5

---

POQD: Performance-Driented Query Decomposer for Multi-vector retricval
for pre-trained over-parameteriize large language models, if they are fine-tuned with the state-of-the-ar optimization method, GaLore (Zhao et al., 2024b), their training loss satisfies the above PL* condition.
to generate decomposed sub-questions for each question. We follow (Zhou et al., 2022; Zhu et al., 2023; Guo et al., 2022; Wu et al., 2024a) to fine-tune Llama3. 1-8B with StrategyQA dataset (Geva et al.. 2021b) which contains human-annotated sub-queries. Unsupervised Query Decomposition (U-QD for short); This aims to train query decomposition model in an un- supervised manner. The representative method is OUNS (Perez et al., 2020) which aims to identify sub-queries that are similar to original questions but also diverse enough. Query Decomposition
Assumption 4.2 (Bounded loss). For arbitrary O and p, the loss ((:;p) p) is upper bounded by a constant M, i.c.:
[(O; p) S M.
Assumption 4.3 (Gradient Descent updates). Suppose up- dating θ in p) with a fixed p is performed through gradient descent, i.e.,
In-Context Learning-
(ICL-QD for short): Some recent works (Li ct al., 2024; Pereira et al., 2023; Niu et al., 2023; Ye et al., 2023; Xue et al.; Wu et al., 2024b; Chen et al., 2024; Bhattacharya et al., 2023) prompt LLMs to perform in-context learning for query decompositions with manually crafted prompts.
= 0 - -
(3)
in which 1y is the learning rate.
Given the above assumptions, the following theorem holds.
These prompts are included in Appendix D.
Theorem 4.4, Suppose the prompt Td is updated to prew in Line 4 of Algorithm 2, then the following inequality holds:
In-Context Learning with Feedback for Query Decom- position (ICLF-QD): Some recent works (Qi et al.; Gao et al., 2024; Sidhoum et al., 2024) improve ICL-QD B-D by providing feedback to LLMs regarding the quality of the decomposed sub-queries. In particular, we follow (Qi et al.) to evaluate whether sub-query is relevant to the re- trieved document or not. This is for determining whether to further decompose this sub-query. The prompts used in this method are included in Appendix D.1.
fL )M, C(e"() ( C(O (p""";;"""" a-
2T
in which L(O' (p and C(O (pptt);; ) denote the converged training loss when the prompt is fixed to ypld and yoow respectively.
In the above theorem, the term (1 (1-4) 21) is a constant be- tween 0 and 1. Therefore, we can configure t such that M M is a positive value, e.g. ja by setting a a- - 2I
Datasets and models We employ Web Questions (We- bQA) (Berant et al., 2013; Chang et al., 2021), Multi- ModalQA (Talmor et al.), ManyModalQA (Hannan et al., 2020) and StrategyQA (Geva et al., 2021a) dataset for ex- periments. Among these datasets, the former three include questions requiring retrieval from multi-modal data. We focus two baGeb QA tasks throughout the experi- ments, i.e., image QA and text QA. For image QA, we select only questions requiring image retrieval from WebQA, Mul- tiModalQA, and ManyModalQA. For text QA, we select only questions requiring text documents from all of these four datasets. Notably, Strategy QA is used for multi-hop QA, while the others only support single-hop QA.
T == log1 $ figure as by default which strikes a balance between the training efficiency and performance empirically verified by Section 5.
).
). As mentioned in Section 4.3, we con-
This theorem states that with appropriate r and a, Algorithm 2 can effectively optimize the prompt p for decomposing sub-queries at a reasonable training cost, thus achieving superior downstream performance than that by employing other query decomposition strategies. The complete proof of this theorem is provided in Appendix A.
5. Experiments
Regarding the retrieval process, it is critical to determine which embedding model to use. For text QA, we employ the Sentence- Bert model (Reimers, 2019) by default for encoding sub-queries and corpus for other baseline meth- ods as well as POQD. On the other hand, for image QA, the CLIP model (Radford et al., 2021) is employed as the default model for embedding text queries and image corpus. In Section 5.3, we further perform ablation studies on the retrieval model. But note that ColBERT and its counterpart for image retrieval, ColPali (Faysse et al., 2024), have their own encoding models. Hence, we report the results of two versions of ColBERT, one taking its own embedding model (denoted by ColBERT-orig) while the other leverages the
5.1. Experimental setup
Baseline We compare POQD against the following query decomposition methods from prior studies:
Conventional dense retrieval encodes each query and document with one single embedding.
ColBERT (Khattab & Zaharia, 2020) which decomposes queries into individual tokens.
Supervised Query Decomposition (S-QD for short): A series of works (Xue et al., 2024; Yang & Zhu, 2021; Zhou et al., 2022; Zhu et al., 2023; Guo et al., 2022) train a peuuence-to-sequene model in supervised manner
6

---

POQD: Performance-Drientel Query Decomposer for Multi-vector retricval
As Table 1 and Table 2 suggest, POQD outperforms all baseline methods in both the retrieval performance and end- to-end QA accuracy by large margin across all datasets. Notably, the retrieval accuracy is increased by up to 5.28% (see the last column in Table 1) while POQD) boosts QA accuracy by up to 12.61% (see the MultiModalQA column under Image QA in Table 2). This thus indicates that per- forming multi-vector retrieval with the sub-queries derived by POQD, can enhance the retrieval performance, and con- sequently the QA accuracy. Note that POQD consistently beats both ColBERT and ColBERT-orig. thus indicating the poor performance of ColBERT regardless of the underlying embedding model.
Invoke Algorithm
Training Time (s)
40000
Train
30000
20000
10000
WebQA (image)
ManyMMoaaQQA (image)
MultiModalQA (image)
WebQA (text)
ManyModalQA (text)
MultiModalQA (text)
Figure 4. Overall training time of Algorithm 2
Time analysis We further analyze both the training time and inference time of POQD for the RAG-based QA pipeline. First, regarding the training time, we record the overall running time of Algorithm 2 on all datasets except StrategyQA. StrategyQA is excluded since, as noted earlier, the generator model is not fine-tuned for this multi-hop QA dataset. The results, presented in Figure 4, also decompose the total running time into two components: the time for invoking Algorithm to optimize the prompt in [(O)p) p) and that for training the parameter O As illustrated by this figure, the dominant training overhead is from the generator training phase, while optimizing the prompt adds negligible training cost. Considering that POQD also yields significant performance gains as Table 2 shows, these findings thus highlight both the effectiveness and efficiency of POQD.
same default embedding model as others.
For the generator models, we leverage Llama3.1-8) (Dubey et al., 2024) and Llava-y1.5-78 (Liu et al., 2024) as genera- tors for single-hop text QA and image QA, respectively. In the experiments, only these generator models fine-tuned while keeping the retrieval models frozen. On the other hand, regarding multi-hop text QA, i.c., Strategy dataset, we follow the state-of-the-arr (Xu et al., 2024) to utilize the frozen GPT-4 (Achiam et al., 2023) model and merely replace its default retrieval method with baseline methods and POQD.
Throughout the experiments, the default values of a, t and are configured as 0.02, and 5, respectively. Regarding the configuration for the retrieval process, retrieve the Top-1 most relevant images and the Top-2 most relevant documents in the image QA and text QA tasks, respec- tively. More details on experimental setup are provided in Appendix B, which include how to decompose and embed documents or images.
We also report the inference time of POQD in Figure 5. Similar to the breakdown in Figure 4, the total inference time is decomposed into three components, including the generator model inference time, retrieval time, and the time spent decomposing queries. As illustrated in Figure 5, the model inference time contributes the largest portion of the overall inference overhead, significantly exceeding the query decomposition time. This finding indicates that in- corporating query decomposition does not adversely impact the overall inference speed.
5.2. Quantitative results
Performance analysis We perform end-to-end RAG train- ing on the QA datasets introduced in Section 5.1. For this experiment, we not only report the end-to-end QA accu- racy in Table 2 but also compare the ground-truth relevant documents or images against the retrieved ones by POQD and baseline methods in Table 1. Regarding the retrieval accuracy metric, we report Hit@1 and @ (see the for- mal definition in (Croft et al., 2010) for image QA and text QA, respectively, since the Top-1 relevant image and Top-2 relevant text documents are retrieved in these two tasks, re- spectively. Note that since StrategyQA is primarily used for multi-hop QA in which the queries for retrieving documents are dynamically generated during the reasoning process, the ground-trure relevant documents are thus not available for this dataset. Hence, we do not report the retrieval accuracy for this dataset.
5.3. Ablation studies
We also perform a series of ablation studies to evaluate the effect of the hyperparameters and the superiority of POQD under various configurations with the WebQA dataset in the text QA task.
Effect of a We also vary the value of a in Algorithm I to evaluate its effect on the training loss, which produces Figure 6. In this figure, the prompt used for decomposing queries is updated three times by Algorithm I (indicated by the inverted triangle symbols). As this Figure suggests, if is too large (say a=005)) POQD would struggle to find a suitable new in Algorithm 1, thus causing the underfitting
7

---

POQD: Performancc--riennte Query Decomposer for Multi-vector retricval
Image QA MultiModallQ
Text QA
Dataset
WebQA
ManyModalQA
WchQA
MultiModalQA
ManyModalQA
Hit@1
Hit@
Hit@1
Hit@2
Hit@2
Hit@2
Dense retrieval
41.38
50.00
27.38
43.52
66.44
49.25
ColBERT
11.98
25.22
16,30
50.72
40.92
40.37
ColBERT-orig
38.95
36.96
21.05
52.16
79.89
87.07
S-QD
40.93
52.61
28.15
48.56
56.17
68.07
U-QD
33.89
51.74
26.86
46.04
45.21
67.89
ICL-QD
39.39
54.34
27.76
41.37
71.43
85.14
ICLF-QD
41.69
51.74
27.89
51.80
69.76
66.49
POQD
42.33
58.26
28.67
53.24
80.58
92.35
Table 1. Retrieval Accuracy on QA datasets
Image QA
Text QA
Dataset
WehQA
MultiModalQA
ManyModalQQ
WebQA
MultiModalQA
ModyModalQA
Strategy QA
w/o RAG
80,31
16.52
30.98
56.47
40.36
32.28
58.76
Dense retrieval
81.43
46.09
34.12
59.35
59.36
41.25
61.43
ColBERT
82. 14
42.61
29.80
60.79
53.95
22.08
62.45
ColBERT-orig
81.96
49.13
32.29
61.14
61.73
77.66
65,50
S-QD
81.73
48.70
35.82
58.99
54.92
62.62
73.33
U-QD
82.26
47.73
33.73
60.79
49.24
60.95
71.11
ICL-QD
82.37
46.78
34.70
58.63
61.86
76.69
60.70
ICLF-QD
81.54
46.55
34.77
60.42
63.52
60.07
72.34
POQD(r=3) 82.83
61.74
37.92
62.22
68.10
81.27
75.55
Table End-to-End QA (Exact Match) Accuracy. We bold best underline second best accuracy number respectively
Generator Time Retrieval Time Query Decomposition Time
3000
0.50
Time (s)
0.48
2000
Loss
1000
0.42
StrategyQA WebQA (image)
Manaaaa (image)
(image)
WebQA (text)
ManyModalQA d (text)
MultiModalQA (text)
0.40
Invake Algrithm c 0.01
0.38
Invoke Algritimm c- 0.02
ManyMo
25
50
75
100
125
150
175
200
Number of iterations
Figure 5. Overall inference time of POQD
issue. In contrast, if a is too small (say a=0.01), POQD con- verges much slower than our default with a=0.02. Hence, the default configuration of a, i.e., 0.02, can balance the con- vergence speed and the final performance. In addition, with o=0.02, the training loss decreases smoothly throughout the training process, exhibiting no abrupt spikes.
Figure 6, Effect of on the training loss on the WebQA dataset in text QA
formance. As this figure suggests, configuring as 3 is reasonable choice since it balances the training efficiency and performance well.
Effect of We measure the training loss L(O;p) and the total training time by varying between 0 to 5, which is plotted in Figure hibited in this figure matches the analysis in Section 4.4, ie., larger leading to longer training time but better per-
Effect of using varied LLMs for decomposing queries Unlike other methods, ICL-QD, ICLF-QD, and POQD rely on one LLM for generating decomposed sub-queries. Hence, we also compare their performance with alternative L.MMs
Notably, the performance trend ex-
8

---

POQD: Performancc-Oriented Query Decomposer for Multi-vector retricval
Decomposed sub-queries
0.75
70000
S-QD
["What Victoria, Hong Kong". "type buildings"]
0.70
Score
U-QD
["Victoria", ""bulidings""
60000
ICL-QD
("Victoria Hong Kong", "buildings", "type"l
Time (s)
0.65
ICLF-QD
["buildings Victoria, Hong Kong"]
50000
0.60
2003 (orr)
POQD
("Victoria Hong "ong"."buildings""
40000
0.55
30000
Table 4. Performance on the WebQA dataset in text QA by using the Roberta model as the embedding model for retrieval
0.50
20000
10000
0.45
1
2
3
4
5
6. Related work
T
Multi- Retrieval Multi-Vector Retrieval (MVR), first introduced by ColBERT (Khattab & Zaharia, 2020), employs a late-interaction mechanism to evaluate query- document similarity. This approach can overcome the repre- sentational limitations of dense retrieval methods that use single embeddings for queries and documents. Subsequent works have focused on accelerating retrieval (Santhanam et al., 2022b:a; Gao et al., 2021; Li et al., 2023) or im- proving score aggregation strategies (Qian et al.). Notably, most solutions decompose queries into individual tokens, leaving the optimization of query decomposition for MVR underexplored.
Figure? 7. Training time of POQD with varied values of
for query decomposition. Specifically, this experiment is conducted by leveraging the GPT-4 model (Achiam et al., 2023) and D3 (DeepSeek Team, 2024) the query decomposer, which leads to the results in Table 3. As this table shows, with varied LLMs used for query de- composition, POQD consistently outperforms ICL-QD and ICLF-QD.
Top-2 retrieval accuracy DeepSeek
QA accuracy DeepSeek
GPT-4
GPT-4
ICL-QD
56.83
55.40
57.91
58.27
L.M--based optimizer (Yang et al., 2024; Pryzant et al.; Wang et al.) have shown the potential of large language models (LLMs) as generic optimizer, which aims to search the prompts for a given LLM based on a history of a history of past instructions and performance scores on the training set. Later on, this strategy is further extended for optimizing the configurations of LLM agents (Zhang et al.; Zhao et al., 2024a). This strategy is highly effective since it is free of gradient computation (Lin et al., 2024).
ICLF-QD
49.28
48.92
56.47
57.55
POQD
58.99
55.40
59.71
60.43
Table 3. Performance on the WehQA dataset in text QA with varied LLMs for query decomposition
Additional ablation studies Due to space limit, other ablation studies are reported Appendix D.3, including the study the effect of the varied number of retrieved items, the filtering step, the varied generator models, and the varied embedding models for retrieval.
Due to the space limit, we discuss other relevant related works in Appendix C.
7. Conclusion
5.4. Qualitative studies
In this paper, we studied how decompose queries into sub- queries for multi-vector retrieval such that the performance of retrieval-based systems, in particular, RAG systems is optimized. To solve this problem, we propose to prompt an LLM to decompose queries into sub-queries and opti- mize its prompt with an LLM-based optimizer. We further propose an efficient end-to-end training algorithm. Exten- sive experiments on variety of RAG-based QA benchmark datasets demonstrate the effeectiveness and efficiency of our method.
We expand the example shown in Figure to show the dif- ferences between the baseline methods and POQD. Specifi- cally, we report the decomposed sub-queries generated by other baseline methods in Table 4. In comparison to POQD, these baseline methods produce sub-queries that either con- tain irrelevant information, say the word "what" and "type" generated by S-QD, miss key information, say "Hong Kong" by U-QD. As a consequence, the most relevant im- ages retrieved with those sub-queries (shown in Appendix D.4) do not match the ground-truth image shown in Figure These retrieval errors can thus be attributed to the un- reasonable aub-queries produced by the baseline methods.
9

---

POQD: Performaace--riennte Query Decomposer for Multi-vector retricval
Acknowledgements
Croft, W. B., Metzler, D., and Strohman, T. Search engines: Information refrieval in practice, volume 520. Addison- Wesley Reading, 2010.
This work supported by "The Fundamental Research Funds for the Central Universities, Peking University". We are grateful to the GPU Cluster support with AIBD platform from Fundamental Industry Training Center of Tsinghua University.
DeepSeek Team. Deepseek-v3: Technical report. Tech- nical report, DeepSeek, 2024. URL https: httpp:://www.. deepseek. com.
Devlin, J. Bert: Pre-training of deep bidirectional trans-
Impact Statement
formers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
This paper presents work whose goal is to enhance the end- to-end performance of the retrieval-based systems, in partic- ular, the Retrieval-Augmentted Generation (RAG) systems, through optimizing their retrieval process. This is achieved by utilizing multiple-vecton retrieval and optimizing the way of decomposing queries into sub-queries. We believe that the proposed method could be seamlessly employed to enhance the performance of arbitrary RAG systems in a lightweight manner, but without imposing any negative impacts.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The llama 3 herd of models. arXiv preprint arXiv: 2tli::2400.21220 2024.
Faysse, M., Sibille, H., Wu, T., Omrani, B., Viaud, G., Hudelot, C.,, and Colombo, P. Colpali: Efficient document retrieval with vision language models. In The Thirteenth International Conference on Learning Representations, 2024.
References
Gandhi, M., Gul, M. O., Prakash, E.,, Grunde-MeLaughhe M., Krishna, R., and Agrawala, M. Measuring compo- sitional consistency for video question answering, In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5046-5055, 2022.
Achanta, R., Shaji, A., Smith, K., Lucchi, A., Fua, P., and Süsstrunk, S. Slic superpixels. 2010.
Achiam, J., Adler, S., Agarwal, S., Ahmad, I.., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
Gao, L. and Callan, J. Condenser: pre-trainn vre-training architecture for dense retrieval. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 981-993, 2021.
Barnett, S., Kurniawan, S., Thudumu, S., Brannelly, Z., and Abdelrazek, M. Seven failure points when engineering retrieval augmented generation system. In Proceedings of the IEEE/ACM 3rd International Conference on Al Engineering Soofrerr Engineering for Al, pp. 194-199, 2024.
Gao, L., Dai, Z., and Callan, J. Coil: Revisit exact lex- ical match in information retrieval with contextualized inverted list. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technologies, pp. 3030-3042 2021.
Berant, J., Chou, A., Frostig, R., and Liang, P. Semantic parsing on freebase from question- question-answer answer pairs. In Pro- ceedings of the 2013 conference on empirical methods in natural language processing, pp. 1533-1544, 2013.
Gao, Y., Zhu, Y., Cao, Y., Zhou, Y., Wu, Z., Chen, Y., Wu, S., Hu, H., and Dai, X. Dr3: Ask large language models not give off-topic answers in open domain multi-hop question answering. arXiv preprint urXiv:2403. 12393. 2024.
Bhattacharya, S., Anand, A., et al. In-context ability transfer for question decomposition in complex qa. arXiv preprint 1rXiv:2310.18331 2023.
Geva, M., Khashabi, D., Segal, E., Khot, T., Roth, D., and Berant, J. Did aristotle use a laptop? question answering benchmark with implicit reasoning strategies. Transac- tions of the Association for Computational Linguistics, 9: 346-361, 2021a.
Chang, Y., Narang, M., Suzuki, H., Cao, G., Gao, J., and Bisk, Y. WebQA: Multihop and Multimodal QA. 2021. URL
org/ abs / 2109 00590.
Chen, J., Kim, G., Sriram, A., Durrett, G., and Choi, E. Complex claim verification with evidence retrieved in the wild. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies ( (Volume 1: Long Papers), pp. 3569-3587, 2024.
Geva, M., Khashabi, D., Segal, E., Khot, T., Roth, D., and Berant, J. Did Aristotle Use a Laptop? A Question An- swering Benchmark with Implicit Reasoning Strategies. Transactions of the Association for Computational Lin- guistics (TACL.) 2021b.
10

---

POQD: Performancc-Driented Query Decomposer for Multi-vector retricval
Guo, X.-Y., Li, Y.-F,, and Haffari, G. Complex reading comprehension through question decomposition. In Pro- ceedings of the 20th Annual Workshop of the Australasian Language Technology Association, pp. 31-40, 2022.
and atomic retrieval. In Findings of the Association for Computational Linguistics: EMNLP 2024, pp- 1 11472- 11485, 2024.
Liao, Z., Li, J., Niu, L.,, and Zhang. L. Align and aggre- gate: Compositional reasoning with video alignment and answer aggregation for video question-answering In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13395- 13404, 2024.
Hannan, D., Jain, A., and Bansal, M. Manymodalqa: Modal- ity disambiguation and qu over diverse inputs. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7879-7886, 2020.
Huang, X., Qi, J., Sun, Y., and Zhang, R. Latent reasoning for low-resource question generation. Findings of the Association for Computational Linguistics: ACL-ICNLP 2021, pp. 3008-3022, 2021.
Lin, M., Sheng. J., Zhao, A., Wang, S., Yue, Y., Wu, Y., Liu, H., Liu, J., Huang, G., and Liu, Y.-J. Llm-based optimization of compound ai systems: A survey. arXiv preprint arXiv:2410. /6392, 2024.
Jiang, Z., Araki, J., Ding, H., and Neubig, G. Understanding and improving zero-shot multi-hop reasoning in gener- ative question answering. In Proceedings of the 29th International Conference on Computational Linguistics, pp. 1765-1775, 2022.
Liu, C., Zhu, L.,, and Belkin, M. Loss landscapes and opti- mization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85-1166 2022.
Liu, H., Li, C.,, Wu, Q. and Lee, Y.J. Visual instruction tun- ing, Advances in neural information processing systems, 36, 2024.
Karpukhin, V., Oguz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W.-t. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 6769-6781, 2020.
Liu, X.-H., Du, Y., Wang. J., and Yu, Y. On the optimiza- tion landscape of low rank adaptation methods for large language models. In The Thirteenth International Con- ference on Learning Representations.
Khattab, O. and Zaharia, M. Colbert: Efficient and effective passage search via contextualized late interaction over bert. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pp. 39-48, 2020.
Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., and Stoyanov, Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: /907. 1692, 2019.
Khot, T., Trivedi, H., Finlayson, M., Fu, Y., Richardson, K., Clark, P., and Sabharwal, A. Decomposed prompting: A modular approach for solving complex tasks. In The Eleventh International Conference on Learning Repre- sentations.
Ma, X., Gong, Y., He, P., Zhao, H., and Duan, N. Query rewriting in rettieval-uugmented large language mod- els. In Proceedings of the 2023 Conference on Empiri- cal Methods in Natural Language Processing, pp. 5303- 5315, 2023.
Khot, T., Khashabi, D., Richardson, K., Clark, P., and Sab- harwal, A. Text modular networks: Learning to decom- pose tasks in the language of existing models. In Pro- ceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 1264-1279, 2021.
Mitra, B., Craswell, N., et al. An introduction to neural information retrieval. Foundations and Trends@ in Infor- mation Retrieval, 13(1):1-126, 2018
Nguyen, T., Rosenberg. M., Song, X., Gao, J., Tiwary, S., Majumder, R., and Deng, L. Ms marco: A human- generated machine reading comprehension dataset. 2016.
Li, M., Lin, S.-C., Oguz, B., Ghoshal, A., Lin, J., Mehdad, Y., Yih, W.-t., and Chen, X. Citadel: Conditional token interaction via dynamic lexical routing for efficient and effective multi-vector retrieval. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 11891-11907, 2023.
Niu, Y., Huang, F., Liu, W., Cui, J., Wang, B., and Huang, M. Bridging the gap between synthetic and natural questions via sentence decomposition for semantic parsing. Trans- actions of the Association for Computational Linguistics, 11:367-383, 2023.
Pereira, J., Fidalgo, R., Lotufo, R., and Nogueira, R. Vis- conde: Multi-document qa with gpt-3 and neural rerank- ing. In European Conference on Information Retrieval, pp. $34-543, Springer, 2023.
Li, Y., Song, D., Zhou, C., Tian, Y., Wang, H., Yang, Z., and Zhang, S. A framework of knowledge graph graph-enhanced large language model based on question decomposition

---

POQD: Performance-Drientel Query Decomposer for Multi-vector retricval
Perez, E., Lewis, P., Yih, W.-., Cho, K., and Kiela, D. Unsu- pervised question decomposition for question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), Pp.
Talmor, A., Yoran, O., Catav, A., Lahav, D., Wang, Y., Asai, A., Ilharco, G., Hajishirzi, H., and Berant, J. Multi- modalqa: complex question answering over text, tables and images. In International Conference on Learning Representations.
3864-8880, 2020.
Press, O., Zhang, M., Min, S., Schmidt, L.,, Smith, N. A., and Lewis, M. Measuring and narrowing the composi- tionality gap in language models. In Findings of the As- sociation for Computational Linguistics: EMNLP 2023, pp. 511556887711 2022.
Wang, X., Li, C., Wang, Z., Bai, F., Luo, H., Zhang. J., Jojic, N., Xing, E., and Hu, Z. Promptagent: Strategic plan- ning with language models enables expert-level prompt optimization. In The Twelfth International Conference on Learning Representations.
Pryzant, R., Iter, D., Li. J., Lee, Y. T., Zhu, C., and Zeng, M. Automatic prompt optimization with" gradient descent" and beam search. In The 2023 Conference on Empirical Methods in Natural Language Processing.
Wu, J., Yang, L.., Ji, Y., Huang, W., Karlsson, B. F., and Okumura, M. Gendec: A robust generative question- decomposition method for multi-hop reasoning, arXiv preprint 2rXiv:2402.11166 2024a.
Wu, Z., Bai, H., Zhang, A., Gu. J., Vydiswaran, V., Jaitly, N., and Zhang, Y. Divide-or-conquer! which part should you distill your Ilm? arXiv preprint arXiv:2402. 2024b.
Qi, J., Xu, Z., Shen, Y., Liu, M., Jin, D., Wang, Q., and Huang, L. The art of socratic questioning: Recursive thinking with large language models. In The 2023 Con- ference on Empirical Methods in Natural Language Pro- cessing.
Xu, J., Guo, Z.,, He, J., Hu, H., He, T., Bai, S., Chen, K., Wang, J., Fan, Y., Dang, K., al. Qwen2. 5-omni techni- cal report. arXiv preprint arXiv:2503.20211 2025.
Qian, Y., Lee, J., Duddu, K., Dai, Z., Lei, T., Brahma, S.,
Naim, I., and Zhao, V. Y. Multi-vector retrieval as sparse alignment.
Xu, S., Pang, L.,, Shen, H., Cheng, X., and Chua, T.-S. Search-in senech-in-thh-chie thethhhhchin Interactively enhancing large lan- guage models with search for knowledge-intensivee intensive tasks. In Proceedings of the ACM on Web Conference 2024, pp. 1362-1373, 2024.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pp. 8748 8763. PMLR, 2021.
Xue, S., Huang, Z., Liu, J., Lin, X., Ning, Y., Jin, B., Li, X., and Liu, Q. Decompose, analyze and rethink: Solving in- tricate problems with human- like reasoning cycle. The Tiirth- Annual Conference on Neural Information Processing Systems.
Reimers, N. Sentence-bert: Sentence embeddings using siamese bert-networks. arXiv preprint arXiv:1908. 10084, 2019.
Santhanam, K., Khattab, O., Potts, C., and Zaharia, M. Plaid: efficient engine for late interaction retrieval. In Proceedings of the 31st ACM International Conference Information & Knowledge Management, pp. 1747-1756, 2022a.
Xue, S., Huang, Z., Lin, X., Liu, J., Qin, L.,, Su, T., Liu, H., and Liu, Q Enhancing the completeness of rationales for multi-step question answering. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pp. 2763, 2024.
Santhanam, K., Khattab, O., Saad-Falcon, J., Potts, C., and Zaharia, M. Colbertv2: Effective and efficient retrieval via lightweight late interaction. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lan- guage Technologies, pp. 3715-3734, 2022b.
Yang, C., Wang, X., Lu, Y., Liu, H., Le, Q V., Zhou, D., and Chen, X. Large language models as optimizers. In The Twelfth International Conference on Learning Represen- tations, 2024. URL https: / openrevieweeeeeee//e net/ forum?
Yang, L., Kong, Q., Yang, H.-K., Kehl, W., Sato, Y., and Kobori, N. Deco: Decomposition and reconstruction for compositional temporal grounding via coarse-to-fine contrastive ranking. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 23130-23 40, 2023.
Sidhoum, A. H., Mataoui, M., Sebbak, F., Hosni, A. I. E., and Smaili, K. Scoring multi-hop question decomposition using masked language models. ACM Transactions on Asian and Low- Resource Language Information Process- ing, 23(7):1-21 2024.
12

---

POQD: Performance-Orientee Query Decomposer for Multi-vector retricval
Yang, X. and Zhu, X. Exploring decomposition for table- based fact verification. In Findings of the Association for Computational Linguisties: EMNLP 2021, pp. 1045- 1052, 2021.
Yang, Z., Qi, P., Zhang, S., Bengio, Y., Cohen, W., Salakhut- dinov, R., and Manning, C. D. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 Conference on Empirical Meth- ods in Natural Language Processing, pp. 2369-2380, 2018.
Ye, Y., Hui, B., Yang, M., Li, B., Huang, F., and Li, Y. Large language models are versatile decomposers: Decompos- ing evidence and questions for table-based reasoning. In Proceedings of the 46th International ACM SIGIR Con- ference on Research and Development in Information Retrieval, pp. 174-184, 2023.
Zhang, S., Zhang, J., Liu, J., Song, L., Wang, C., Krishna, R., and Wu, Q. Offline training of language model agents with functions as learnable weights. In Forty-first Inter- national Conference on Machine Learning.
Zhang, X., Wang, M., Yang, X., Wang, D., Feng, S., and Zhang, Y. Hierarchical retrieval- -agmeettd generation model with rethink for multi-hop question answering. arXiv preprint arXiv:2408.1 /875, 2024.
Zhao. H. Ma, C., Wang, G., Su, J., Kong, L., Xu, J., Deng, Z.-H., and Yang, H. Empowering large language model agents through action learning. arXiv preprint arXiv:2402. 15809, 2024a.
Zhao, J.. Zhang, Z., Chen, B., Wang, Z., Anandkumar, A., and Tian, Y. Galore: Memory-efficien I1m training by gradient low-rank projection. In International Conference on Machine Learning, pp. 61121-61143 PMLR, 2024b.
Zhao, W. X., Liu, J., Ren, R., and Wen, J.-R. Dense text retrieval based on pretrained language models: A survey. ACM Transactions on Information Systems, 42(4):1-60, 2024c.
Zhou, B., Richardson, K., Yu, X., and Roth, D. Learn- ing to decompose: Hypothetical question decomposition based on comparable texts. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 2223-222222222 2235, 2022.
Zhu, W., Thomason, J., and Jia, R. Chain-of-questions training with latent answers for robust multistep question answering. In Proceedings of the 2023 Conference on Empirical Methods Natural Language Processing, pp. 8845-8860, 2023.
13

---

POQD: Performance-Drientee Query Decomposer for Multi-vector retricval
A. Theoretical analysis
The proof of Theorem 4.4 depends on the following essential Lemma from prior studies.
Lemma A.1 (Linear convergence), For a model parameterized by θ satisfying the p-PL* condition and the L-smoothness, suppose is trained with the grudient descent method and converges O' then the following inequality defined the loss function (()) holds for the model parameter at the keh iteration (denoted by ②²):
((Or) -00))-((0"">) S
2L (C((b)) - L(0")).
The above inequality indicates that the model θ converges at linear rate.
Proof. First, according the y-PL condition shown in Assumption 4.1, i..,, (I (u((e) the following inequality holds:
||C().) 2 pC(0.) 2
(4)
Then according the smoothness property of [(O,), the following formula holds:
L [(0++1) S ((O,) + VL(O, -0) + 10:41 10:11-910 0.112
According to Formula (3), 0x+1 - θ in the above formula can be substituted by -n((()), leading to:
[(0++1) - ((0,) - nlI + Ln7
- [VVL(,))
-())) (1 - L1j² -n
According to Equation (4), the above formula can be transformed to:
[(0++1) S ((e.) - 7ll Ln
2 [[V
= -(O)) (n 2
2
Lnj
< L(e,) (1 p(((O,) ((0r)
Then by subtracting L(0*) on both sides of the above formula, we can obtain:
-(0,41) - ((e)) v ((e,) - C(0") - (n Ln² u(C(O,) - ((e)))
LM [C((e))) - L(("))
[1 1n11
Then by setting 7) = 4, 1 pnn(1
Lg)
= and thus the above formula is bounded by:
27.
1 (C(O,) - L()*))
$ (1 21
Recall that according to Assumption 4.1, the training loss satisfies the fa-PI.* condition and T-smoothness with arbitrary fixed p. Hence, by substituting L(0) with p(O;p), the following inequality holds for L(O:p) when θ is updated with gradient descent:
[(Ox:p) ((0":)) < (1 11
C(0t:))))
(5)
2L
Then we formally provide the proof Theorem 4.4 as follows.
14

---

POQD: Performancc-Drientel Query Decomposer for Multi-vector retricval
Proof. With a fixed prompt yoرd (or yeew resp.), suppose the model parameter the ly iteration of the training process shown in Line 4 of Algorithm is 0 (or Ope resp.). By representing A = 2r Equation (3) be rewritten
L(O - C( (p p:t = _( : - Gold < A :p : L(O"(( (p= );10 olu)] A ('((00 : Gald];
in which use Gold represent L( (poll); poli) and substitute the ratio 1 27. with constant A(0 < A < 1)
Then when t T, the above formula is transformed into:
C(O : Gold A" (C(60)) p Gola)
(6)
Recall that when pold updated to prew, the training loss is reduced by a. Therefore, the following formula holds:
[( : - C(O, p new) 2 a.
which can be integrated into Formula (6), resulting in:
L(0 )=e)) + a Gold = L pTeM) + Gold S AT( poll) Gola).
(7)
By subtracting Gola and adding Gnew on the left side of the above formula, we can obtain:
1(00% ; )==) - Gnew + Gnew Gold + a S ("( : - Gola).
Since Gnew minimizes L(O; Pnew) for any O, this means that L(O)ew pm poww)- Gnew 2 0. This thus can be leveraged to lower bound the left side the above formula, leading to:
Gnew
Gold + a S ; - Gola)-
By leveraging the fact that L(Oghd ) S M and Gold 0, then the above formula is further bounded by:
Gold Gnew 2 A.M.
B. Additional experimental setups
Datasets and models As introduced in Section 1, we primarily conduct experiments on RAG-based QA tasks covering both image QA and text QA tasks, which we evaluate both the retrieval performance and end-to-end QA accuracy, Specifically, we employ Web Questions (WebQA) (Berant al., 2013; Chang et al., 2021). MultiModalQA (Talmor et al.), ManyModalQA (Hannan et al., 2020) and Strategy (Geva al., 2021a) dataset for experiments. The WebQA dataset consists of Image QA dataset (Chang al., 2021) and Text QA dataset (Berant et al., 2013), Among these datasets, WebQA, MultiModalQA and Moda-Moda contain questions that may require retrieving data from different modalities. Hence, for image QA, in particular, for WebQA, MultiModalQA and ManyModalQA. dataset, we only select questions requiring retrieving images while for text QA, we only select questions requiring text documents as input. Among these datasets, Strategy QA employed for multi-hop QA while others are used for single-hop QA.
Regarding the retrieval model for text QA, we employ the pre-trained model developed by (Santhanam et al., 2022b) for ColBERT, which fine-tunes the Bert model (Devlin, 2018) the MSMARCO dataset (Nguyen al., 2016). Since COlBERT decomposes queries at the token level, which may not be suitable for decomposed sub-queries, we thus employ the Sentence- Bert model (Reimers, 2019) for encoding sub-queries and corpus for other baseline methods as well POQD. On the other hand, for image QA, the CLIP model (Radford et al., 2021) is employed to embed text queries and images.
For the generator models, we leverage Llama3.1-88 (Dubey et al., 2024) and Llava-v1.5-77 (Liu et al., 2024) as generators for single-hop text QA and image QA respectively. In the experiments for these tasks, only the generator models are
15

---

POQD: Performance-Driented Query Decomposer for Multi-vector retricval
fine-tuned in our experiments for baseline methods while POQD jointly fine-tunes the generator model and optimizes the prompt for query decomposition. On the other hand, regarding multi-hop text QA, i.e., StrategyQA dataset, we follow the state-of-the-art (Xu et al., 2024) to utilize frozen GPT-4 (Achiam et al., 2023) model and merely replace its default retrieval model, i.e., ColBERT, with other baseline and POQD.
Also, to facilitate multi-vector retrieval, it is essential to construct multiple vectors appropriately for each document or image in the corpus. Since queries are decomposed into sub-queries composed of multiple tokens, it is thus not appropriate to follow (Khattab Zaharia, 2020) to embed individual tokens documents, which is even impossible for images in the context of image QA. Hence, for text QA, except ColBERT, we embed individual sentences for other baseline methods and POQD while for image QA, we segment each image into superpixels with existing image segmentation tools, say, SLIC (Achanta et al., 2010), and embed these superpixels with CLIP model.
C. Additional related work
Question decomposition in Question Answering How to decompose queries or questions has been extensively studied in the Question-Answering (QA) literature but from a different perspective. Specifically, various strategies have been devised decompose complex questions into multiple sub-questions facilitate multi-hop QA. Indeed, these strategies could be adapted for decomposing queries for multi-vector retrieval. For instance, series of works (Xue et al., 2024; Yang & Zhu, 2021; Zhou et al., 2022; Zhu et al., 2023; Guo et al., 2022; Wu et al., 2024a; Geva et al., 2021b; Khot et al., 2021) train a sequence-to-sequeene model in a supervised manner over a set of training queries with human-annotated sub-queries such that this model can generate decomposed sub-queries directly. Considering the lack of human annotations for sub-queries in most data, one can either train a query decomposition model in an unsupervised way (Perez et al., 2020) or employ heuristies (Jiang et al., 2022; Gandhi al.. 2022; Yang et al., 2023) (say syntax rules (Yang al., 2023)), or perform in-context learning with LLMs (Li al., 2024; Pereira et al., 2023: Niu al., 2023; Ye et al., 2023; Xue al.; Wu et al., 2024b; Chen et al., 2024; Bhattacharya et al., 2023; Liao al., 2024; Khot et al.; Press et al., 2023; Zhang et al., 2024) for query decomposition. To further enhance the decomposition performance, one can optionally collect feedback on the decomposed sub-queries and incorporate it into the above in- in-context learning-basee methods. Typical feedback includes confidence scores (Qi et al.), quality scores provided by a powerful enough L.MM (Gao et al., 2024), or relevance scores between the generated answers and an expected topic (Sidhoum et al., 2024). Some other works even model the target sub-queries latent variables (Huang et al., 2021: Zhu et al., 2023). However, to our knowledge, none of these solutions determine sub-queries for optimizing the downstream retrieval-based task performance.
D. A Aditional experimental results
D.I. Prompts used for ICL-QD, ICLF-QD and POQD
We present the prompts used for query decomposition in ICL-QD and ICLF-QD in Figure 8 and Figure 9, respectively. For the latter one, we reuse the prompt from (Qi et al.).
Regarding the prompts used for query decomposition in POQD, we present what prompts are used as the input for the LLM optimizer and that for the LLM-based query decomposer in Figure 10, which also displays how these prompts evolve the first four iterations of Algorithm 1.
You are a query decomposition assistant. Please decompose one query Q into semantically coherent sub-queries.
Figure The prompt used for query decomposition in ICL-QD
D.2. Comparison against the query rewrite strategy
There is an emerging trend in the literature for rewriting user queries to maximize the RAG performance. Considering that both POQD and this line of work aim to manipulate the user queries for performance enhancement, we thus also compare POQD against one of such representative work (Ma et al., 2023). This experiment is conducted on the WebQA dataset in
16

---

POQD: Performancc--riinnted Query Decomposer for Multi-vector retricval
Imagine that you are thoughtful and logical problem solver. You will get a question. However, this question is too complex or lacking information to answer. You need break down the original question into several simpler subquestions to help the information retrieval system retrieve the relevant information. Important: Do not use pronouns indefinite pronoun phrases in generated questions. The questions asked must be self-contained questions. Each question can contain only one parameter. Don't just ask yes/no questions." "For example, Question: Could the Great Wall of China connect the Dodgers to the White Sox? Note: The raised question has be self-contained question. Do not use pronouns or indefinite pronoun phrases the generated questions. Copy context from the original question if needed. Deep Questions: 1. What is the most commonly cited figure for the total length of the Great Wall? 2. What is the straight-line distance between Chicago, Illinois, and Los Angeles, California?
Figure 9. The prompt used for query decomposition in ICLF-QD
text QA, which produces results in Table 5. Note that since the query rewrite method still relies the traditional dense retrieval strategy to retrieve relevant items, it thus suffers from poor retrieval performance, which eventually underperforms POQD by a large margin concerning the end-to-end QA accuracy.
Top-2 retrieval accuracy
End-to-end QA accuracy
Query rewrite POQD
28.42
52.16
53.96
61.87
Table 5. Comparison between POQD and query rewrite strategy
D.3. Additional ablation studies
We include additional ablation studies in this section. Considering the generally poor performance of ColBERT compared ColBERT-orig reported in Section 5, we ignore the results of ColBERT below.
Effect of the varied number of retrieved items We varied the number of retrieved Top-K K relevant items in the retrieval process between and 5 on the WebQA dataset in text QA, which leads to the results in Table 6. These results again show that with varied numbers of relevant items, POQD consistently beat other methods regarding the QA accuracy numbers.
2
w/o RAG
56.47
56.47
56.47
Dense retrieval
58.63
59.35
61.51
ColBERT-orig
59.70
61.14
63.66
S-QD
58.99
58.99
62.23
U-QD
58.27
60.79
62.23
ICL-QD
57.91
58.63
59.35
ICLF-QD
59.71
60.42
62.58
POQD
61.15
62.22
64.03
Table End-to-end QA accuracy on WebQA dataset text QA by varying the number of retrieved relevant documents in the retrieval process
Effect of the filtering step Considering that LLMs may produce irrelevant tokens during the query decomposition process, POQD filters out these irrelevant tokens in the generated sub-queries. We therefore further evaluate how this filtering step influences the performance of POQD as well as baseline methods.
Effect of varied generator models We repeat the text QA experiments on the WebQA dataset by replacing its default generator model, 1lama3.1-8B, with Qwen2.5 (Xu et al., 2025). The resulting end-to-end QA accuracy is reported in Table 8, which suggests that POQD outperforms the baseline methods regardless of the generator model used.
17

---

POQD: Performance-Orientte Query Decomposer for Multi-vector retricval
Without filtering step
With filtering step
Top-2 retrieval accuracy
End-to-end QA accuracy
Top-2 retrieval accuracy
End-to-end QA accuracy
S-QD
41.37
58
48.56
58.99
U-QD
39.20
57.91
46.04
60.79
ICL-QD
35.97
57.55
41.37
58.63
ICLF-QD
41.01
58.27
51.80
60.42
POQD
52.51
61.87
53.24
62.22
Table 7. Performance on the WebQA dataset text QA with VS without the filtering step
Llama3. 1--BB
Qwen2.5
w/o RAG
56.47
54.32
Dense retrieval
59,35
57.19
ColBERT-org
61.14
57.55
S-QD
58.99
51.44
U-QD
60.79
50.72
ICL-QD
58.63
57.91
ICLF-QD
60.42
56.47
POQD
62.22
59.35
Table 8. End-to-End QA Accuracy with varied generator models on the WebQA dataset the text QA task
Effect of varied embedding models for retrieval We also compare POQD against baseline methods by using the RoBERTa model (Liu et al., 2019) rather than the Sentence-Ben model as the embedding model for retrieval. The results of this experiment are summarized in Table 9, which again indicate the performance advantage of POQD compared to other methods.
Top-2 retrieval accuracy
QA accuracy
w/o RAG Dense retrieval
54.32
22.29
58.63
ColBERT-orig
43.53
60.43
S-QD
22.30
58,99
U-QD
20.86
$7.91
ICL-QD
39.57
59.71
ICLF-QD
34.89
60.07
POQD
43.88
61.51
Table 9. Performance on the WebQA dataset in text QA by using the RoBERTa model as the embedding model for retrieval
D.4. Additional details on qualitative studies
As mentioned in Section 5.4, we decompose the query appearing in Figure using POQD and baseline methods and retrieve images with the decomposed sub-queries. The retrieved images by these methods are shown Figure 11, which suggests that those images do not match the buildings in Victoria, Hong Kong. Hence, this misalignment between these retrieved images and the ground-truth indicates that the decomposed sub-queries by baseline methods (shown in Table 4) are not reasonable.
18

---

POQD: Performaacce-riennte Query Decomposer for Multi-vector retricval
meta-prompt
prompt prefix
generate instruction <INS>, provious
Prompt Optimizer
You are query optimization assistant. Please analyze given query and generate a set of refined sub quertes that maximize clarity, relevance, and efficiency retriving the desired information.
instructins soones. The scora ranges 100.
solution-score pairs
<N
meta promptt
Generate
instructioee <INS> above,
and has higher soore than the instructions <INSS above...
Score:
(a) Iteration 0 of Algorithm
meta-prompt
Your teek is to generate the instruction <INS> Below are some previous Instructions with their scoee. The score from to 100.
prompt profix
You query optimization assistant Analyze the given query Q and generato sot of refined sub quen-ueees that maximize clanty, relevance, officincyy in ratreving the destred information.
solution-sen sccoe pairs
Prompt Optimizer
You a query optimization assistant, Please analyno the given query Q and generate a set of rafined sub-querias that maxinize clarity, relevance, and efficiency in retriewing the desired information. 0.75
Text:
meta-prompt
Generato an Instruction that cifferent from all the instructions <INS> above, and has a higher score than all the instructions <INS> above....
Score: 0.74
Iteration of Algorithm
meta-prompt
#
prompt prefix
generate instruction <INS>, Below some previous instructions with their scores. The score ranges from to 100.
You are query optimizetion decomposition
solutton-scooee pairs
assietant. Analyze the given query Q and generate set of refined, logically independent autt-queries that onhance clartly. relevance, and officiency. ensuring sub-querry semantically coherent and can be processed independently while preserving original query's intent.
Text: You optimization assistant. Please anelyze the given query dariiyy, relevance,
Prompt Optimizer
generate refined sub-queries and efficiency retrieving the desired information.
Score: 0.75
KINS
query optimization assistant, Analyze the given query generate sot of rofined sub sub-qquries that maximze clantyy, relevance, and afficiency retrieving desired Information. Score:
# meta-prompt
Genarata an instruction that is difforent from all the instructions <INS> above, and has higher score than the instructions <INS> above
Score: 0.73
(c) Iteration of Algorithm
meta-prompt
Your lask is ta generate the instruction <INS>. Below are some previous Instructions with their scoree. The
from 0 100.
solution-score pairs
Text: You are query opéimccttion assisiani. Please analyze the given query Q and generate sel of refined sub-queries that masimize darll. relevance, and efficiency netrieving the desined information. Score: 0.75
prompt prefix
You assistant, Please analyze
optimization
Text: You are query optimization assistent. Analyze the given query and generate a sel of refined eub-queriee that masimize darity, relevance, and afficlency in netr lerieiing the desired information. Score: 0.74
given query Q and generate a set refined sub queries that improve dlaniy. efficiency. and relevance meintaining semantic coherence.
Prompt Optimizer
<INS>
Text: You are query optimization and decompastion assistant. Analyze the
given query Q and generate set of refined, logically independent sub- queries that enhance derity, relevance, and efficency. ensuring eech sub- query semantically
Indapandently while
Score: 0.72
preserving original quary's intent. Score: 0.73
meta-prompt
Gonerato an instruction that is difforant from al the instructions <INS> above. has higher than the instructions <INS> above
(d) Iteration 3 of Algorithm 1
Figure 10. Prompts produced in the first four iterations by Algorithm
19

---

POQD: Performance-Driented Query Decomposer for Multi-vector retricval
(a) S-QD
(b) U-QD
(c) ICL-QD
(d) ICLF-QD
Figure 11, Retrieved images by using decomposed sub-queries produced by baseline methods
20


Reviews:
[{"review_id": "hIaj2yleeR", "reviewer": "Reviewer_Nopx", "summary": "The paper tackles an important problem of jointly optimizing the query decomposition and retreival model for downstream generation task. The query decomposition and embedding model are trained alternatively. \n\nGiven an embedding model, the query decomposition is performed using a LLM with the optimization space restricted to prompts. To navigate this space, they use existing ideas from Yang 2024 to have LLM generate better and better prompts. \n\nGiven a prompt, the model is trained for some iterations using standard optimization. (e.g. gradient descent)\n\nThe authors find that this acheives superior RAG performance on downstream QA tasks -- specifically, the performance is starkly improved on MultiModal data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would thank your comments. You can find our responses to your comments below:\n\n+ Regarding the retrieval results in Table 1:\n\nWe admit that these results look confusing. Indeed, the discrepancy between Table 1 and Table 2 can arise from the fact that we report Top-20 and Top-100 retrieval accuracy while we only retrieve the most relevant image for image QA and the two most relevant documents for text QA. Hence, if we report Top-1 and Top-2 retrieval accuracy instead (as shown below), we can see that our method always performs better than the state-of-the-art: \n\n|Top-1 retrieval accuracy  | ManyModalQA (image) |\n|---|------------------------|\n| Dense retrieval | 27.38 |\n| Colbert |16.30|\n|S-QD|28.15|\n|U-QD|26.86|\n|ICL-QD|27.76|\n|ICLF-QD|27.89|\n|POQD|**28.67**|\n\n|Top-2 retrieval accuracy  | WebQA (text) |\n|---|------------------------|\n| Dense retrieval |52.96|\n| Colbert |52.16|\n|S-QD|48.56|\n|U-QD|46.04|\n|ICL-QD|41.37|\n|ICLF-QD|51.80|\n|POQD|**53.24**|\n\n \n+ Regarding the theoretical analysis:\n\nWe agree that proving the convergence of POQD is trivial. However, the main message that we want to deliver in Theorem 4.4 (and the following explanations between line 290 and 297) is to analyze under what conditions $p^{new}$ would lead to a better training loss at convergence than that of $p^{old}$. This is crucial in demonstrating that the loss $L(\\theta;p)$ is indeed optimized with respect to $p$. Otherwise, it is likely that with the finally derived prompt $p^*$ by Algorithm 2, the converged training loss $L(\\theta^*(p^*); p^*)$ is even worse than that with the initial random prompt $L(\\theta^*(p^{init}); p^{init})$. This thus invalidates the optimality of $p^*$ derived by Algorithm 2. So to guarantee that this solution is optimal, we thus need to make sure that updating $p^{old}$ to $p^{new}$ can lead to sufficiently large training loss reduction (by $\\alpha$) within 5 iterations in Algorithm 1 (which will be clarified in the description of Algorithm 2 in the revision). Otherwise, we terminate updating the prompt.  \n\n+ Regarding the possibly unstable training issue: \n\nWe agree that without identifying a $p^{new}$ that can reduce the training loss by $\\alpha$, the training process can be unstable. So as long as we cannot find such a $p^{new}$ within 5 iterations in Algorithm 1, which will be further clarified near line 254 to 257 in the revision, we break the while loop in Algorithm 1 and stop updating $p$ any more. The empirical results in Section 5 indeed demonstrate the performance advantage of our method with this strategy. We would love to elaborate more on this point in the revision. \n\n+ Regarding the relationship between the prompt scores and loss:\n\nAs we point out in line 180 in the right column, the training loss $L(Θ; p)$ is viewed as the score \n\n+ Regarding the plots of training loss:\n\nWe included the plot of training loss in this [link](https://anonymous.4open.science/r/Training-Loss/Training_loss.jpg), which shows no spike during the entire training process of Algorithm 2 (including the prompt update process). As mentioned above, we only update $p^{old}$ to $p^{new}$ if the training loss is reduced by at least $\\alpha$ within 5 steps (as explained in the response to reviewer PnGe). Otherwise, we terminate the training process. This can thus guarantee the smooth reduction of training loss.", "claims_and_evidence": "A few claims that i was not convinced about are\n1. \n\nThe prompt decomposition trained the way proposed in the paper achieves superior retreival resutls -- this does not seem to be true generally. Specifically, the Table 1, retreival accuracy (which measures if correct document is retrieved), shows that PQQD does not improve retreival across the board. It has phenomenal improvemenets in MultiModalQA. But it can be quite suboptimal when it comes to TextQA when compared to ColBERT.  It is interesting that despite this, POQD has consistent improvement over all baselines in the downstream task. I believe that the optimization considers if the LLM generating answer with the retrieved documents can generate the correct answer from the correct document or not -- and that seems to tip the scales in favor of POQD. Am i understanding this correctly?\n\n2. \n\nThe purpose of theoretical analysis section is unclear to me. On the face of it, it seems like a statement is being made about convergence of the POQD training. However, one most complex pieces of training -- prompt generation is abstracted out in the proof by simply assuming that p_new has lower loss than p_old by amount of $\\alpha$ (line 674). Once you assume something like this, along with strong convexity, it is not surprising that the result shows convergence.  \nHowever, the loss(p_new) begin less than loss(p_old) is the most tricky part imo. I understand that this is hard to even begin analysing this. But section 4.4 needs to highlight this issue that potentially, POQD can have unstable training where you never get p_new that has lower loss because LLM generating prompt may not satisfactorily navigate the prompt space.", "methods_and_evaluation_criteria": "I am not well versed with this area of research. The method and evaluation seem reasonable to me based on broader understanding of the field.", "theoretical_claims": "I did not check the correctness. But the result seems okay. Some discussion needs to be added though (see the claims section)", "experimental_designs_or_analyses": "I am not well versed with this area of research. The method and evaluation seem reasonable to me based on broader understanding of the field.", "relation_to_broader_scientific_literature": "I am not well versed with this area of research.", "essential_references_not_discussed": "I am not well versed with this area of research.", "other_strengths_and_weaknesses": "[strength]\n1. The paper is well written with good examples. \n\n[weakness]\n1. The retreival results in table 1 seem contradictory.", "other_comments_or_suggestions": "1. Line 160. n-sub queries ( do you mean k sub queries)\n2. Can you provide more empirical details on training . A few things that might help \n     -- how well does prompt scores align with loss. \n     -- Can you show us the plots of training loss. I suspect, we can see some unexpected spikes on the prompt update step.", "questions_for_authors": "Please see my concerns above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KZrjfjuGb3", "reviewer": "Reviewer_EhPc", "summary": "The paper presents Performance-Oriented Query Decomposer (POQD), a framework for optimizing query decomposition in retrieval-augmented generation (RAG) tasks, particularly in multi-vector retrieval (MVR). POQD leverages an LLM-driven iterative optimization strategy to generate sub-queries that enhance downstream question-answering (QA) performance. Extensive experiments on RAG-based QA tasks, covering both image QA and text QA have been reported to demonstrate the effectiveness of the proposed framework.\n\n##update after rebuttal\nThe authors have addressed most of my concerns satisfactorily, I am therefore updating my recommendation to a weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments. Our responses are below:\n\n+ About the contribution of the paper:\n\nWhile we don't propose a novel LLM-based optimization method, our key contribution is recognizing the need to optimize query decomposition for multi-vector retrieval—a critical factor in improving retrieval-based systems. To address this, we adapt an LLM-based optimization strategy for query decomposition and jointly train it with the generator model. We believe this work fits the scope of ICML's application track.\n\n+ About the training algorithm:\n\nWhile our alternative training algorithm may seem straightforward, it could incur higher training overhead compared to optimizing only the RAG generators—a concern for practical applications. However, our theoretical analysis (lines 281-297) shows that with proper hyper-parameters, the added overhead is minimal without compromising optimality, as empirically confirmed in Figure 4. Thus, our algorithm effectively balances efficiency and effectiveness, as highlighted in Contribution 2.\n \n+ About the theoretical analysis:\n\nWhile our theoretical analysis assumes strong convexity, it also holds under the weaker Polyak-Łojasiewicz star (PL*) condition [2]. Prior work [1] suggests that pre-trained, over-parameterized LLMs fine-tuned with GaLore, a variant of LoRA, likely satisfy the PL* condition. Since the model $\\Theta$ in the paper is a pre-trained LLM fine-tuned with GaLore, the analysis in [1] applies.\nAssuming the loss function $L(\\Theta;p)$ satisfies the $\\mu$-PL* condition (instead of $\\mu$-strong convexity), a variant of Lemma A.1 yields:\n$L(Θ_k; p) − L(Θ^∗; p) <= (1-\\mu/L)^k(L(Θ_0; p) − L(Θ^∗; p))$.\nSimilarly, a modified Theorem 4.4 gives:\n$L(Θ^*(p^{old}); p^{old}) − L(Θ^*(p^{new}); p^{new}) >= \\alpha - (1-\\mu/L)^{\\tau} M$.\nThese adjustments preserve our conclusion that Algorithm 2 balances efficiency and effectiveness with proper hyper-parameters. We will include this refined analysis.\n \n+ About the inconsistent retrieval results:\n\nSee our response to reviewer Nopx (Regarding the retrieval results in Table 1)\n\n+ About the text QA results:\n\nIndeed, we report both image QA and text QA results for WebQA in Table 1,2. The text QA results on MultiModalQA and ManyModalQA below show that our method consistently outperforms baselines:\n\n|Top-2 retrieval acc.|MultiModalQA|ManyModalQA|\n|-|-|-|\n|Dense retrieval|66.44|49.25|\n|Colbert|79.89| 87.07|\n|S-QD|56.17|68.07|\n|U-QD|45.21|67.89|\n|ICL-QD|71.43|85.14|\n|ICLF-QD|69.76|66.49|\n|POQD|**80.58**|**92.35**|\n\n|QA acc.|MultiModalQA|ManyModalQA|\n|-|-|-|\n|without RAG|40.36|32.28|\n|Dense retrieval|59.36|41.25|\n|Colbert|61.73|77.66|\n|S-QD|54.92|62.62|\n|U-QD|49.24|60.95|\n|ICL-QD|61.86|76.69|\n|ICLF-QD|63.52|60.07|\n|POQD|**68.10**|**81.27**|\n\n+ About implementation details:\n\n1. U-QD: We reuse the code from (Perez et al., 2020).\n2. ICL-QD & ICLF-QD: Both follow straightforward principles—ICL-QD uses manual prompts for in-context learning, while ICLF-QD adds relevance scores to retrieved documents (see Section 5.1). These prompts will be included in the revision.\n3. We used the GPT-4 as the prompt optimizer and query decomposer (details in revision).\n4. Parameters: Default $\\alpha=0.02$; retrieved items set to 1 (image QA) and 2 (text QA).\n \n+ Ablation studies on WebQA (text):\n\nWe first varied the value of alpha and tracked its effect on the training loss is varied across the training process, which is visualized [here](https://anonymous.4open.science/r/Training-Loss/alpha_ablation_study.jpg). If alpha is too large (say alpha=0.05), POQD struggles to find a suitable $p^{new}$ in Algorithm 1, thus causing the underfitting issue. In contrast, if alpha is too small (say alpha=0.01), POQD converges much slower than our default with alpha=0.02. Hence, alpha=0.02 can balance the convergence speed and the final performance. \n\nAblation on the generator model (from Llama to Qwen2.5):\n|||\n|-|-|\n|Dense retrieval|57.19|\n|Colbert|57.55|\n|S-QD|51.44|\n|U-QD|50.72|\n|ICL-QD|57.91|\n|ICLF-QD|56.47|\n|POQD| **59.35**|\n\nAblation on the query decomposer (from Llama to GPT4). \n|||\n|-|-|\n|ICL-QD|55.40|\n|ICLF-QD|48.92|\n|POQD|**55.40**|\n\nAblation on the retrieval model (from sentence-bert to Roberta): \n||Top-2 retrieval acc.|QA acc.|\n|-|-|-|\n|Dense retrieval|22.29|58.63|\n|Colbert|43.53|60.43|\n|S-QD|22.30|58.99|\n|U-QD|20.86|57.91|\n|ICL-QD|39.57|59.71|\n|ICLF-QD|34.89|60.07|\n|POQD|**43.88**|**61.51**|\n\nAblation on the number of retrieved items:\n|\\# of items|1|5|\n|-|-|-|\n|Dense retrieval|56.31|62.41|\n|Colbert|62.41|69.21|\n|S-QD|51.60|54.23|\n|U-QD|50.49|55.48|\n|ICL-QD|61.58|66.85|\n|ICLF-QD|57.56|60.75|\n|POQD| **62.97**|**69.63**|\n\nThese results show the superiority of POQD under various conditions. \n\n[1] Liu, X. H. et al. \"On the Optimization Landscape of Low Rank Adaptation Methods for Large Language Models.\" ICLR 2023.\n[2] Liu, C. et al. \"Loss Landscapes and Optimization in Over-Parameterized Non-Linear Systems and Neural Networks.\" Appl. Comput. Harmon. Anal.", "claims_and_evidence": "1. The second contribution of the paper, which pertains to the proposed training algorithm, lacks significant novelty. First, the authors adopt the optimization approach introduced in LLMs as Optimizers for query decomposition, rather than proposing a fundamentally new algorithm. This reliance on existing techniques diminishes the originality of their contribution. Second, the end-to-end training framework is essentially an alternative optimization approach, which is a straightforward and intuitive strategy rather than an innovative methodological advancement. Third, the theoretical analysis presented in the paper is based on critical assumptions that are questionable. Notably, the assumption that the training loss function is strongly convex is highly unrealistic, particularly in the context of complex neural networks, where loss landscapes are typically non-convex and may contain multiple local minima and saddle points. Such an assumption weakens the theoretical foundation of the proposed approach.\n\n2. Furthermore, the third claimed contribution, which concerns the empirical performance of the proposed POQD method, also presents notable issues. While the authors argue that POQD outperforms existing methods, a closer examination of the reported results reveals inconsistencies. Specifically, POQD does not consistently achieve the highest retrieval accuracy across all benchmark comparisons, raising questions about the robustness and generalizability of the approach. The lack of consistent superiority over baselines suggests that the empirical results may not fully substantiate the claimed advantages of POQD.", "methods_and_evaluation_criteria": "The experimental evaluation covers both image-based question answering (image QA) and text-based question answering (text QA) scenarios. The evaluation was conducted using four benchmark datasets: WebQA, MultiModalQA, ManyModalQA, and StrategyQA. Among these, WebQA, MultiModalQA, and ManyModalQA include questions that require retrieval from multiple modalities. However, the paper presents image QA results for all three multimodal datasets while reporting text QA results exclusively for WebQA, without providing a clear rationale for this selective reporting. This omission raises concerns regarding the completeness and consistency of the experimental setup, as it remains unclear why text QA was not evaluated across all relevant datasets.", "theoretical_claims": "I have carefully reviewed the proof. Based on my analysis, given those rigor assumptions, the logical progression and mathematical reasoning appear to be technically sound.", "experimental_designs_or_analyses": "1. The experimental section of this paper lacks critical implementation details, making it difficult to fully understand and reproduce the proposed approach. Specifically, the implementation of U-QD, ICL-QD, and ICLF-QD is not clearly described. It remains unclear which large language model (LLM) is utilized for both the prompt optimizer and the query decomposer. Additionally, key hyperparameters such as the value of alpha and the number of retrieved items used in the retrieval-augmented generation (RAG) system are not explicitly stated.\n\n2. Moreover, the analysis section lacks an ablation study on the hyperparameter alpha, which is essential for understanding its impact on the overall performance of the proposed method. \n\n3. Furthermore, the experiments do not include an evaluation of the framework’s robustness and generalization ability across different settings. Specifically, there is no empirical analysis demonstrating the performance variations when using different LLMs, retrieval models, or generator models.", "relation_to_broader_scientific_literature": "The idea of optimizing query decomposition with respect to the final downstream performance might be interesting to broader scientific literature.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "The strengths and weaknesses have been listed above.", "other_comments_or_suggestions": "1. In Assumption 4.3, located on line 274 of page 5, the symbol F(\\theta;p) may have been incorrectly represented and should potentially be L(\\theta;p). \n\n2. In the Time Analysis section on page 7, the sentence starting with \"the generator model is not fine-tuned for this multi-hop QA dataset The results,\" in line 337 appears to be missing a period.", "questions_for_authors": "1. The proposed training algorithm builds upon LLM-based optimization for query decomposition. Could you clarify what specific methodological innovations distinguish your approach from prior work?\n\n\n2. Could you provide additional insights into the conditions under which POQD performs best and where it struggles? Additionally, have you tested POQD with different LLMs, retrieval models, or generator models to test its robustness? Demonstrating consistent improvements across diverse settings would strengthen the empirical claims.\n\n3. The paper provides image-based QA results on all three multimodal datasets but reports text-based QA results only for WebQA. What was the rationale behind this selective reporting? Would including text QA results for MultiModalQA and ManyModalQA provide additional insights into POQD’s effectiveness across modalities? \n\n4. The impact of the hyperparameter alpha on overall performance is not analyzed in the paper. \n\n5. The paper lacks details regarding the implementation of U-QD, ICL-QD, and ICLF-QD. Could you provide more information on the specific LLMs used for query decomposition and prompt optimizer, as well as key hyperparameters such as the value of alpha and the number of retrieved items in RAG?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "z3oJPeYLrQ", "reviewer": "Reviewer_sd7s", "summary": "The paper proposes an approach to decompose a query into sub-queries, and the decomposition is optimized to obtain better performance in the end task. The decomposition is performed by using meta-prompting to an LLM. It is expected that the LLM is able to iteratively generate better prompts when the performance measure is provided as feedback. The proposed approach is tested on several datasets, showing generally better performance measures than the baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would thank your comments. Our responses are below:\n+ About qualitative examples:\n\nThanks for pointing out this issue. Indeed, in figure 1, we leverage one example to show the differences between ColBERT, ICL-QD and POQD. We further expand it by reporting the decomposed sub-queries (both before and after filtering step) generated by other baseline methods as follows (the retrieved figures are shown in this [link](https://anonymous.4open.science/r/Example-9717)). \n\n| | before filtering | after filtering |\n|-|-|-|\n|S-QD| ['What is Victoria, Hong Kong known for having in abundance at its waterfront', 'Is  a type of building'] |[\"What Victoria, Hong Kong\", \"type buildings\"] |\n|U-QD | ['where is Victoria' ,'what is in front of the buliding'] |['Victoria' ,'bulidings'] |\n|ICL-QD| [\"historical significance of Victoria Hong Kong\", \"buildings\", \"type\"] | [\"Victoria Hong Kong\", \"buildings\", \"type\"] | \n|ICLF-QD| [ 'What is the historical significance of colonial buildings in Victoria, Hong Kong ', 'What are the different architectural styles found in Victoria, Hong Kong'] |[\"buildings Victoria, Hong Kong\"] | \n\nBefore filtering, the sub-queries from baselines contain many irrelevant tokens, as analyzed below:\n1. S-QD: Trained on StrategyQA with human-annotated sub-queries. However, when applied to other datasets, distribution shifts introduce irrelevant tokens.\n2. U-QD: Its candidate sub-queries are collected from datasets (e.g., SQuAD), leading to irrelevant tokens in generated sub-queries.\n3. ICL-QD/ICLF-QD: Their LLM-generated sub-queries may contain hallucinated irrelevant tokens.\n\nUnlike our method, baselines lack iterative refinement using downstream feedback, causing them to either miss key tokens (e.g., U-QD drops \"Hong Kong\") or retain unimportant ones (e.g., S-QD keeps \"type\" and \"what\"). This leads to incorrect image retrieval and answers. We will add this analysis in the revision.\n\n+ About the prompts produced by POQD:\n\nWe run Algorithm 1 for four steps and show the prompts and generated prefixes at each step are included in this [link](https://anonymous.4open.science/r/Training-Loss/opt_iter). The LLM optimizer indeed produces variations of query decomposition instructions, searching for variants that minimize the retrieval system’s training loss.\n\n+ About the filtering step:\n\nAs noted in lines 198-201, we only filter irrelevant tokens to ensure query decomposition correctness. For LLM-based methods (ICL-QD, ICLF-QD), retrieval and QA accuracy remain nearly identical with or without POQD's filtering, as shown in our ManyModalQA (image) ablation studies below.\n\n|Top-1 retrieval accuracy | w/o filtering | w/ filtering|\n|-|-|-|\n|S-QD|  28.15| 27.05|\n|U-QD| 26.86|26.54|\n|ICL-QD| 27.76| 27.51|\n|ICLF-QD| 27.89| 28.37|\n\n|QA score | w/o filtering | w/ filtering|\n|-|-|-|\n|S-QD| 35.82|35.42 |\n|U-QD| 33.73|33.46 |\n|ICL-QD| 34.70|36.37 |\n|ICLF-QD| 34.77| 35.56|\n\nWe also removed the filtering step from our method and retested on ManyModalQA (image). The results are shown below, which show that both retrieval and QA accuracy get reduced by 2%-5%, but still higher than baseline methods.\n\n||Top-1 retrieval accuracy|QA accuracy|\n|-|-|-| \n|POQD (w/o filtering) |28.15 | 36.12|\n|POQD| 28.67 | 37.92 |\n\n+ About the theoretical analysis:\n\nSee our response to reviewer EhPc (About the theoretical analysis). \n\n+ About the example in Section 2.1:\n\nAs explained in Appendix B, image retrieval in image QA involves segmenting images into patches and encoding each of them. Due to the maxsim operation, the similarity between a sub-query and an image depends on the most similar patch to this sub-query. In Section 2.1’s example, CLIP considers Patch A [black-filled](https://anonymous.4open.science/r/Training-Loss/kong.png) most similar to \"kong,\" while the ground-truth image’s Patch B [buildings](https://anonymous.4open.science/r/Training-Loss/kong2.png) is less similar. Since \"kong\" refers to a gorilla-like monster (see [Wiki](https://en.wikipedia.org/wiki/King_Kong)), the Patch A yields unrealistically high similarity, ranking Lee Kuan Yew’s image above the ground truth. We will clarify this in the revision.\n\n+ About query and document encodings:\nYes, we encode sub-queries using pre-trained models like Sentence-BERT. For documents, we encode each sentence similarly for all methods except ColBERT to ensure fair comparison (lines 311-321). ColBERT inherently tokenizes queries and documents, so we use its default setup. But we also test it on WebQA by processing documents like other methods. The top-2 retrieval accuracy (48.92) and QA score (59.71) under this setup are worse than ColBERT's default (61.15 and 60.79 resp.).\n\n+ About the retrieval time in Figure 6:\nThe retrieval time on WedQA is much smaller than the generator time. You may mean the longer retrieval time on StrategyQA, which as noted in lines 307-311, is due to multi-hop QA requiring repeated reasoning and retrieval per question. We will add this explanation to Section 5.2.", "claims_and_evidence": "The main idea of the paper is to iteratively improve the prompt to LLM to generate sub-queries. To this end, an iterative process is designed. Under some conditions, the paper shows that the decomposition improves. This idea sounds very interesting. The experiments provide evidence to show the utility of the process.", "methods_and_evaluation_criteria": "The main idea is attractive. The use of meta-prompt to generate prompts for query decomposition is innovative. The idea sounds intuitive.\nHowever, the paper does not provide sufficient information on what prompts the process may produce. It is unclear that the iterative process will converge. At the end of the iterative process, what type of prompt for query decomposition is generated? Does it correspond to some specific form of prompt? or some pattern for the prompt? If some examples are provided, and better,some analysis about what the iterative process will produce, one can better understand the approach.\n\nThe experiments show some advantages of the proposed method over the existing baselines. However, the comparison is mainly quantitative. It is unclear why the proposed method can produce better decompositions. Some analysis about the different behaviors of different approaches would help.\n\nThe proposed approach also include a step of filtering of sub-queries with irrelevant tokens. How is this done? How do you determine that a token is irrelevant? How does this filtering important in the whole method? Would part of the gain for the method be generated by this filtering? If this is the case, then the superior performance of your method is not produced solely by the optimized decomposition process. Would a similar filtering process be applicable to other baseline methods? This should be discussed in the paper.\n\nOverall, the evaluation demonstrates the superiority of the proposed method, but there is not sufficient qualitative analysis to allow for better understanding of the reasons.", "theoretical_claims": "The paper contains some theoretical results, showing that under some conditions, the iterative optimization process can improve. As recognized by the authors, the conditions will not be satisfied in practice, making the utility of the theoretical results less strong. Despite this, the results are informative.", "experimental_designs_or_analyses": "The experiments are performed on several datasets. The general design of the experiments are correct.\nThere is a lack of discussion about the reasons that better performance is obtained with the proposed method, and its differences with the existing baselines, especially on the sub-queries that can be generated.", "relation_to_broader_scientific_literature": "The key contribution of the paper is to rely on LLM to decompose queries into sub-queries. The performance-aware optimization is believed to produce a better decomposition than the existing methods. This idea sounds interesting. However, there is a lack of explanation about the process to be fully convinced that the algorithm can indeed produce better decompositions.\nThe main related methods in the literature are cited.", "essential_references_not_discussed": "The main references are cited. They are correctly described.\nHowever, the comparison with them is superficial.", "other_strengths_and_weaknesses": "Some statements need further support.\n- \"Notably, the similarity score between the token “Kong” and the photo of Lee Kuan Yew is exceptionally high,\": It is difficult to understand why this is produced. Can you provide a plausible reason for it? This may help understand the nature of the problem.\n- The theoretical parts of the paper are more difficult to understand. This is partly due to the fact that some concepts are used without explanation. For example, μ-strongly convex and L-smooth are not explained.\n- Sentence BERT is used to encode sub-queries and the corpus: \"We thus employ the Sentence-Bert model (Reimers, 2019) for encoding sub-queries and corpus for other baseline methods as well as POQD.\". How is this done? Do you consider each sub-query as a sentence and ask sentence-BERT to encode it? How about for the documents? Do you encode each sentence wit it?\n- In Fig. 6, why is there a so large retrieval time for WebQA (image)?", "other_comments_or_suggestions": "General suggestion: perform more details about the decomposition that can be obtained, more analysis about the experimental results and more qualitative comparisons with the baselines.", "questions_for_authors": "see the questions above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wPh2GkZcgE", "reviewer": "Reviewer_PnGe", "summary": "The paper introduces POQD, a framework for optimizing multi-vector retrieval (MVR) for retrieval-augmented generation (RAG) systems. The key idea is to improve retrieval performance by decomposing a query into sub-queries. POQD uses an LLM in two roles: one acts as a Query Decomposer that splits the input query into candidate sub-queries, and the other functions as a Prompt Optimizer that iteratively refines the prompt guiding the decomposition. It proposes an alternating training algorithm that alternates between optimizing the prompt and training the downstream retrieval model. The paper supports its contributions with experiments across image and text-based QA tasks.\n\n### Update after rebuttal\nThe rebuttal helped clarify some of my doubts about the experiments, I am raising my score to 3 in light of this. The results in the current manuscript are presented in a confusing manner, and can greatly benefit from a clear presentation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank for your comments. Our responses are below:\n\n+ About the additional training data:\n\nIndeed, in our experiments, we did not include additional training data to train POQD throughout the paper. During the training process, we train POQD using the same set of training samples as those baseline methods.\n \n+ About the baseline method:\n\nAs explained in Section 5.1, for S-QD, it aims to train a sequence-to-sequence model to generate decomposed sub-queries. Such training process has been used in many prior works such as  (Zhou et al., 2022; Zhu et al., 2023; Guo et al., 2022; Wu et al., 2024). We thus reuse the code from these papers to train this query decomposition model. For U-QD, we directly use the released unsupervised model for performing query decomposition. For ICL-QD, since it performs query decomposition by prompting LLMs. We thus leverage the prompts from prior works to decompose queries through in-context learning. For ICLF-QD, we follow (Qi et al.) to add retrieval scores as feedback in the prompts for in-context learning.  \nThe experimental results of these baseline methods are not taken from prior papers. As explained in Appendix C, S-QD, U-QD, ICL-QD and ICLF-QD haven’t been evaluated for decomposing queries for retrieval in the context of RAG. We thus implement these methods in our experiments and obtain these numbers by ourselves.  \n\n+ About the theoretical analysis:\n\nSee our response to reviewer EhPc (About the theoretical analysis)\n\n+ About the contribution of the paper:\n\nSee our response to reviewer EhPc (About the contribution of the paper)\n \n+ About the image retrieval performance of ColBert:\n\nYes, as mentioned in line 319-321, in the image QA experiments, we leverage the pre-trained CLIP model as the underlying image retrieval model for all methods including ColBert. The reason why Colbert performs worse is that the original version of Colbert has not been applied in image retrieval yet. To mitigate this, we further included the results of Colpali [1] below, which is a variant of ColBert adapted for image retrieval. The results indicate that our method still outperforms Colpali although it is adapted for image retrieval. \n\n|ManyModalQA |Top-1 retrieval acc.| QA accuracy|\n|-|-|-|\n|Colbert| 16.30| 29.80|\n|ColPali| 21.05| 32.29|\n|POQD| **28.67**|**37.92**|\n\n|MultiModalQA |Top-1 retrieval acc.| QA accuracy|\n|-|-|-|\n|Colbert|16.53 |42.61|\n|ColPali|36.96|49.13 |\n|POQD|**48.56**|**61.74**|\n\n+ About ColBert text QA results:\n\nSee our response to reviewer Nopx (Regarding the retrieval results in Table 1)\n \n+ About the number of iterations for step 1:\n\nWe configure the number of iterations as 5 by default. If we can find a prompt $p^{new}$ which can lead a training loss smaller than that with $p^{new}$ by up to $\\alpha$ within 5 iterations, then we terminate this loop early. Otherwise, we terminate the entire process of updating prompts in Algorithm 2.\n \n+ About Algorithm 1:\n\nSome details of this algorithm, particularly the while loop's convergence condition, are deferred to Section 4.3. The loop terminates if the loss with an updated prompt is at least $\\alpha$ lower than the initial loss (best\\_L in Algorithm 2, equivalent to Algorithm 1's initial loss) within 5 iterations. In other words, convergence occurs when any updated prompt reduces the loss by at least \n$\\alpha$ compared to the initial training loss. We will clarify this later.\n\n+ About the comparison against the query rewrite strategy:\n\nWe further compare POQD against the strategy of performing query rewrite (we follow [2]) on WebQA (text). The following results again show better performance of POQD:\n||Top 2 retrieval acc.|QA acc.|\n|-|-|-|\n|query rewrite|28.42|52.16|\n|POQD|**53.96**|**61.87**|\n\n[1] Manuel et al. \"Colpali: Efficient document retrieval with vision language models.\"ICLR 2024.\n\n[2] Ma et al, Query Rewriting for Retrieval-Augmented Large Language Models, arxiv", "claims_and_evidence": "The central claim of the paper is that better query decomposition leads to significant improvements in multi-vector retrieval performance, it is compared against multiple query decomposition techniques and the simple token-based query decomposition (colbert) but the proposed model uses additional training data which is not clear whether the baselines have access to or not, there are other questions around the experiments which needs further clarification (see Questions below).", "methods_and_evaluation_criteria": "See\"Experimental Designs Or Analyses\" comments.", "theoretical_claims": "Partially.", "experimental_designs_or_analyses": "Experiments are performed on QA tasks which is a sound choice for the evaluation of contributed techniques. A better description of the baselines can help in gauging the quality of the baselines used.", "relation_to_broader_scientific_literature": "Query understanding is an important step in performing information retrieval, better query decomposition which is the focus of this paper, is one way to understand a query better which can help the subsequent retrieval pipeline.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "### Strengths\n- Paper is well motivated\n- Results show significant improvements on ImageQA tasks (although I'm not convinced of the quality of the baselines)\n\n### Weakness\n- Limited contributions - the paper's main algorithm is to do an alternate minimization of prompt optimization and retriever training, both of them by themselves are well known techniques, moreover, the theoretical reasoning is very basic assuming very strong assumptions which do not seem fair to make in this setting\n- The paper writing can be significantly improved, it's easy to read till motivation section but the presentation can be improved in the method and experiment section", "other_comments_or_suggestions": "- Algorithm 1 is hard to understand, many of its details are deferred to later section which makes a linear read of the paper confusing\n- Appendix C link in section 6 is not correct\n- Figure 5 differs in formatting from the rest of the figures", "questions_for_authors": "1. What are the exact baseline methods in Table 1 & 2 (the baseline description cites multiple works)? Also, are these numbers directly taken from their respective papers? are these baselines also trained on the respective datasets or off the shelf?\n2. Why is Colbert much worse than dense retrieval baseline for ImageQA accuracy? Is it because the underlying encoder not trained on image data, in that case underlying encoder should be a capable image retrieval model?\n3. Also on TextQA how is it possible that the retrieval accuracy for Colbert is quite high but the final end-to-end accuracy is not?\n4. How many iterations does it take on an average to finish the step 1 (prompt optimization for a given retrieval model)?\n5. How does query decomposition compare with simple query rewriting?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work addresses the problem of query decomposition in multi-vector retrieval (MVR) systems. It argues that the performance of MVR systems is highly dependent on the decomposition of the query into smaller units such as phrases and words. As end-to-end optimization of MVR systems by joint optimization of query decomposer and downstream retrieval-based task is impractical, the work proposes to address the challenge by alternative optimization of the prompt for query decomposition and the downstream models. The work employs the proposed optimization on RAG-based QA tasks and compares the end-to-end task performance with baselines that employ alternative ways of decomposing the query.

While the problem addressed by the work is important, the proposed solution is interesting and the experimental results provide some evidence about the effectiveness of the proposed solution, there are some concerns:

1. The novelty of POQD is limited as it makes a straight forward adaptation of LLM-based
optimizer (Yang et al., 2024) for prompt optimization and a straight forward application of alternative optimization for end-to-end optimization.
2. Some of the experimental results are problematic as noted by reviewer Nopx. 
3. Though the theoretical analysis is interesting, it is based on strong assumptions that are not satisfied in practice.
4. Though the experimental results evaluate the effectiveness of the proposed approach, no insights are given on why the proposed solution produces better decompositions as claimed. There is no qualitative analysis that provides deeper insight into specific forms and patterns in the produced prompts.
Decision: Accept (poster)