1 Introduction↩︎

Retrieval-augmented generation (RAG) has emerged as a standard paradigm for grounding large language models (LLMs) in external knowledge sources. By retrieving documents from a corpus and conditioning generation on the retrieved evidence, RAG can improve factual accuracy and reduce hallucinations across a range of tasks, including open-domain QA and knowledge-intensive dialogue [1]–[3]. In this setup, a retriever maps a user query to a ranked list of documents, and the LLM produces an answer conditioned on both the query and the retrieved context. Despite substantial progress on retrieval models and architectures, the current practice in RAG systems is overwhelmingly to select a single retriever (and a single set of hyperparameters) and deploy it uniformly for all queries.

However, the query distributions faced by RAG systems are highly heterogeneous. Some questions are simple factoid queries that can be answered from a single, lexically similar passage, while others require multi-hop reasoning over multiple documents, aggregation of semantically diverse evidence, or domain-specific terminology. Therefore, different retrieval configurations tend to specialize in different regimes [4], [5]. Even for a fixed retriever, recent work shows that it can be beneficial to adapt its hyperparameters at inference time to better suit each query [6]. As a result, there is growing evidence that no single retriever is optimal for all queries, and that fixing a single retrieval strategy can leave substantial performance on the table across diverse information needs [7].

To address this limitation several recent works explicitly aim to adapt their retrieval strategy to the query. Adaptive-RAG [5] trains a classifier to predict the “complexity level” of the given query and then chooses among a small, fixed menu of strategies (no retrieval, single-step retrieval, or iterative multi-hop retrieval) based on this prediction. Vendi-RAG [6] instead focuses on a parametric retriever and iteratively tunes its hyperparameter at inference time: for each query, it generates candidate answers under different settings and employs an LLM judge to steer the retriever towards a better relevance–diversity trade-off. While these approaches validate the benefits of adapting retrieval, they either operate over a very small, hand-designed set of strategies or perform expensive per-query search in a hyperparameter space.

In contrast, we propose a principled approach for selecting a small portfolio of retrievers with complementary behavior, from a large candidate pool, that is provably near-optimal for the underlying query distribution.

We tackle this problem by explicitly modeling the fact that different retrievers may be best for different questions. We view each query \(q\) as a sample from an underlying distribution, and each retriever \(r\) (including its architecture and hyperparameters) as a candidate tool for answering that query. For every query-retriever pair \((q,r)\), we define a score \(s(q,r)\) that measures how suitable \(r\) is for \(q\), for example in terms of retrieval quality or end-to-end answer correctness. Rather than searching for a single retriever that performs best on average, we instead choose a small set \(S\) of \(k\) retrievers and evaluate this set by asking: for a random query \(q\), how good is the best retriever in \(S\)? Formally, we measure the quality of \(S\) by the expected “best-of-\(k\)” score \(\mathbb{E}_{q}[\max_{r \in S} s(q,r)]\) over the query distribution. This objective encourages portfolios whose members specialize on different regions of the query space, since redundant retrievers that behave similarly contribute little to the maximum. In the rest of the paper we analyze this objective and design algorithms that, given a finite sample of queries and a large candidate pool of retrievers, efficiently construct small portfolios with provable guarantees and strong empirical performance.

1.0.0.1 Our contributions

We introduce the new problem, RAG portfolio optimization, and analyze it theoretically and practically. More formally:

• Formulation & Theory. Given a large pool of candidate retrievers, we formalize an expected best-of-\(k\) objective over the query distribution that measures how well a portfolio of \(k\) retrievers covers heterogeneous information needs. Furthermore, we prove that one can efficiently obtain a near-optimal portfolio of retrievers.

• Methods. We propose a pipeline that learns a static portfolio of complementary retrievers offline (Algorithm 3) and trains a lightweight router to dynamically select the best retriever per query (Figure 2). This approach amortizes the cost of adaptation, avoiding expensive iterative search at inference time.

• Empirical evaluation. We evaluate our approach on diverse open-domain and multi-hop QA benchmarks (HotpotQA, 2WikiMultihopQA, TriviaQA, and MusiQue). Our method consistently yields better retrieval recall and answer accuracy compared to single-retriever baselines and inference-time tuning methods like Vendi-RAG, while significantly reducing latency and token usage.

1.0.0.2 Related Work

There are three main areas that are closely related to our work: retrieval augmented generation, adaptive retrieval approaches (including mixture of retrievers and routing pipelines) and portfolio optimization.

Retrieval Augmented Generation. Retrieval-augmented generation (RAG) has become a standard approach for grounding large language models (LLMs) in external knowledge. Instead of relying solely on parametric memory, a RAG system retrieves a small set of relevant documents from a large corpus and conditions generation on both the query and the retrieved context, which improves factual accuracy and knowledge coverage on open-domain and knowledge-intensive tasks [1]–[3]. Early work combined neural retrievers with sequence-to-sequence generators for open-domain QA [1], [4], and subsequent work has extended this paradigm to more complex settings, including multi-hop reasoning and conversational agents [3]. Across these systems, the retriever is a key component: it is usually chosen once, tuned on a development set, and then fixed for all queries, despite the diversity of retrieval behaviors that different questions may require.

Adaptive Retrieval. Recent work challenges the "one-size-fits-all" retrieval paradigm. Approaches like Adaptive-RAG [5] classify query complexity to select among fixed strategies (e.g., no retrieval vs. multi-step retrieval). Vendi-RAG [6] adopts a more granular approach, iteratively tuning a diversity-relevance hyperparameter at inference time to optimize the retrieved set. Other methods, such as Self-RAG [8], introduce retrieval tokens to dynamically decide when to retrieve or critique retrieved passages. Unlike these methods, which often incur high inference latency through iterative generation or search, our approach shifts the optimization burden offline by learning a fixed portfolio of complementary retrievers that can be routed to efficiently.

Mixtures of Retrievers and Query Routing. Recent work exploits complementary retrieval signals either by mixing retrievers or routing queries to different experts. MoR [9] proposes a zero-shot mixture of retrievers that assigns per-query weights to heterogeneous retrievers using pre- and post-retrieval signals, then fuses their scores to produce a single ranked list. While MoR validates the benefits of leveraging multiple retrieval signals, it focuses on score-level fusion over a given set of retrievers. In contrast, our goal is to select a small retriever portfolio from a large candidate pool with provable near-optimal coverage under an expected best-of-\(k\) objective, and to route each query to only a small number of portfolio members, enabling predictable and parallelizable inference cost when downstream LLM calls are expensive.

On the routing side, RouterDC [10] studies query-based routing for assembling multiple expert LLMs via dual contrastive learning, explicitly handling cases where multiple experts perform well for the same query. Our setting is analogous, we route queries to retrievers rather than generators, but our main contribution lies in the portfolio construction problem and its guarantees; RouterDC-style router training is complementary and can be incorporated into our pipeline.

Algorithm Selection and Solution Portfolios. Arising from catalog optimization and data mining, portfolio optimization has been studied extensively in algorithmic literature. In the Segmentation Problems, initially introduced by Kleinberg, Papadimitriou and Raghavan [11], for any combinatorial optimization problem and a set \(S\) of different cost vectors for this problem, the segmentation problem asks to partition the set \(S\) into several segments and pick a separate solution for each segment, so that the total cost is minimized. In an alternative version of this problem Gupta, Moondra and Singh [12] studied a variant where the objective is to identify a small set of solutions that guarantees a good approximation for each one of the cost vectors of interest. In portfolio optimization [13], one is given a combinatorial problem, a set of value functions over the solutions of the problem, and a distribution over the value, and the goal is to select \(k\) solutions that maximize or minimize the expected value of the best of those solutions. Our work instantiates this theoretical framework for RAG, treating retrievers as candidate algorithms and queries as problem instances.

2 Problem Formulation↩︎

We formalize the retrieval process in RAG as a portfolio selection problem. At a high level, we are given a large pool of candidate retrievers and a distribution over queries. Our goal is to select a small subset (a portfolio) such that, in expectation, performance is high when, for each query, we are allowed to use the best-performing retriever from the portfolio.

2.1 Setting and Notation↩︎

Let \(\mathcal{Q}\) denote the set of questions, and let \(\mathcal{D}\) be an unknown distribution over \(\mathcal{Q}\). Let also \(\mathcal{R} = \{ r_1, r_2, \dots, r_m \}\) be the set of candidate retrievers. Each retriever \(r \in \mathcal{R}\) is a black-box procedure that, given a query \(q \in \mathcal{Q}\), returns a ranked list of documents. We do not assume any particular retrieval algorithm or parameterization; different retrievers may correspond to different models, strategies, or hyperparameters.

We equip the space of query–retriever pairs with a bounded score function \[s : \mathcal{Q} \times \mathcal{R} \to [0, 1],\] where \(s(q, r)\) quantifies how suitable retriever \(r\) is for answering query \(q\) within a given RAG pipeline. The definition of \(s(q, r)\) is intentionally abstract here; in later sections we instantiate it with retrieval metrics and end-to-end answer quality.

2.2 Portfolio Objective↩︎

A portfolio is a subset \(S \subseteq \mathcal{R}\) of retrievers. We fix a budget \(k \in \mathbb{N}\) and restrict our attention to portfolios with \(|S| \le k\). Intuitively, \(k\) captures the maximum number of distinct retrievers one is willing to maintain and potentially deploy in a system.

Given a portfolio \(S\) and a query \(q\), we define the score of the portfolio on \(q\) as the score of its best retriever: \[\mathrm{score}(q, S) \;=\; \max_{r \in S} s(q, r).\] In words, a portfolio performs well on a query if at least one of its members does.

The quality of a portfolio \(S\) with respect to the query distribution \(\mathcal{D}\) is then measured by the following objective \[F(S) \;=\; \mathbb{E}_{q \sim \mathcal{D}} \big[ \max_{r \in S} s(q, r) \big] \;=\; \mathbb{E}_{q \sim \mathcal{D}} \big[ \mathrm{score}(q, S) \big].\] The function \(F(S)\) is the expected score of the portfolio on a random query. A portfolio is good when, for most queries sampled from \(\mathcal{D}\), at least one retriever in \(S\) performs well; in other words, \(F(S)\) captures how well \(S\) covers the heterogeneous behaviors required across the query distribution.

Our goal is to find a portfolio of size at most \(k\) that maximizes \(F\): \[\max_{S \subseteq \mathcal{R} : |S| \le k} F(S).\] This is exactly a data-driven solution portfolio problem [13], and closely related to the catalogue problem [11], with retrievers playing the role of candidate solutions and queries acting as problem instances.

3 Selecting Retriever Portfolios from Data↩︎

In this section we present an algorithm (3) for computing a near-optimal portfolio, given access to a distribution of queries.

Recall from Section 2 that, given a candidate pool of retrievers \(\mathcal{R}\) and a query distribution \(\mathcal{D}\), we seek a portfolio \(S\subseteq \mathcal{R}\) of size at most \(k\) maximizing the distributional best-of-\(k\) objective \[\label{eq:pop95objective} F(S)\;:=\;\mathbb{E}_{q\sim\mathcal{D}}\Big[\max_{r\in S} s(q,r)\Big],\tag{1}\] where \(s(q,r)\in[0,1]\) denotes the quality of retriever \(r\) on query \(q\).

Algorithm 3 implements a sample-based greedy procedure. It first draws \(N\) i.i.d.queries \(Q=\{q_1,\dots,q_N\}\sim\mathcal{D}^N\) and replaces the population objective 1 with the empirical estimate \[\label{eq:emp95objective} \widehat F_Q(S)\;:=\;\frac{1}{N}\sum_{q\in Q}\max_{r\in S} s(q,r).\tag{2}\] The algorithm then constructs \(S\) iteratively: at each step it chooses the retriever \(r\) that maximizes the empirical marginal gain \(\widehat F_Q(S\cup\{r\})-\widehat F_Q(S)\) and adds it to the portfolio.

To compute marginal gains efficiently, the algorithm maintains a memoized vector \(V[q]=\max_{r'\in S}s(q,r')\) over sampled queries. The marginal gain of adding \(r\) can then be written as \[\widehat F_Q(S\cup\{r\})-\widehat F_Q(S) =\frac{1}{N}\sum_{q\in Q}\max\!\bigl(0,\;s(q,r)-V[q]\bigr),\] so we only need to compare each candidate against the current best score per query.

3.0.0.1 Running time.

Overall, the implementation runs in \(\mathcal{O}(k\,|\mathcal{R}|\,N) = \mathcal{O}\left(k\,|\mathcal{R}|\cdot \frac{k \log |\mathcal{R}| + \log(1/\delta)}{\epsilon^2}\right)\) score evaluations (given access to \(s(q,r)\)) and \(\mathcal{O}(N)\) additional memory. It is important to note that this is independent of the support/complexity of the query distribution which may be very large.

3.0.0.2 Approximation guarantee.

The function \(S\mapsto \max_{r\in S}s(q,r)\) is non-negative, monotone and submodular for every fixed \(q\), and therefore both \(F(\cdot)\) and \(\widehat F_Q(\cdot)\) are non-negative monotone submodular set functions (this was similarly observed in the theoretical studies [11], [13])¹. As a consequence, the classical greedy algorithm achieves a \((1-1/e)\)-approximation to the empirical optimum under a cardinality constraint [14].

It remains to relate the empirical objective 2 to the population objective 1 . There are at most \(\binom{|\mathcal{R}|}{k}\) portfolios of size \(k\) (and at most \(\sum_{j=0}^k\binom{|\mathcal{R}|}{j}\) of size \(\le k\)). By Hoeffding/Chernoff bounds and a union bound over this family, it suffices to take \[\label{eq:sample95complexity} N=\mathcal{O}\!\left(\frac{k\log|\mathcal{R}|+\log(1/\delta)}{\epsilon^2}\right)\tag{3}\] samples to ensure uniform concentration of \(\widehat F_Q(S)\) around \(F(S)\) for all \(|S|\le k\) with probability at least \(1-\delta\).

Putting these pieces together (see 8 for detailed arguments) yields the following near-optimality guarantee (where we assume score evaluations take time \(\mathcal{O}(1)\)):

In words, Algorithm 3 attains the approximation guarantee of \((1-1/e)\) up to an additional \(\epsilon\) statistical error term. We remark that the \((1-1/e)\) guarantee is tight, as with no further assumptions, our model can express any coverage function: it is well-known that, for coverage functions, the \(1-1/e\) guarantee is tight for polynomial-time algorithms both in the value-oracle model [15] and if \(\mathrm{P} \neq \mathrm{NP}\) [16].

4 Pipeline & Experimental Setup↩︎

We evaluate retriever portfolios on four open-domain QA benchmarks and report both retrieval-only coverage metrics and end-to-end answer accuracy. All experiments are run locally on NVIDIA A100 80GB GPUs. Additional implementation details (exact hyperparameter grids, retriever pseudocode, router training settings, and prompt templates) are provided in 7.

4.1 Routing and inference-time selection↩︎

At inference time, a learned contrastive router represents the query \(\mathbf{q}\) using its raw text together with cached MPNet and E5 query embeddings. A frozen Flan-T5-Large encoder [17] produces a contextual text representation, which is fused with the two backbone-specific dense embeddings (see 7.9 for more details). The router scores each of the \(k\) portfolio retrievers by similarity to a learned retriever embedding and executes the top-\(\ell\) of the portfolio. This pipeline is visualized in Figure 2. The router is trained from retrieval supervision with a multi-positive contrastive objective, following the approach of [10], where positives are the retrievers that achieve the best Recall@\(k\) for each training query. The router training details (loss, tie handling, optimization schedule, and hyperparameters) are deferred to 7.9.

4.2 Answer and judge models↩︎

We use open-weight instruction-tuned LLMs as answerers in the RAG pipeline and as selectors for selecting among candidate answers. In our main experiments, we report end-to-end results with Gemma-3-27B-It [18] and Llama-3.1-70B-Instruct [19] as answer models. For fairness, we keep the answer-generating procedure fixed across all portfolio and baseline methods and use the same prompt formats for all evaluated retrievers. Prompt templates are provided in 7.7.

4.3 Datasets↩︎

We follow the benchmark suite used by Adaptive-RAG [5] and evaluate on: HotpotQA [20], 2WikiMultiHopQA [21], TriviaQA [22], and MusiQue [23]. These datasets span factoid and multi-hop questions and include gold supporting documents for retrieval evaluation. Table 1 summarizes the train/test sizes and corpus statistics.

3pt

4.4 Corpus processing and dense indexing↩︎

All retrieval methods operate over a shared chunked corpus, but dense retrieval artifacts are maintained separately for each embedding backbone. We split each corpus document into overlapping text chunks (512 tokens with 50-token overlap) and treat each chunk as a retrieval unit. We build one dense index per dataset and backbone. For MPNet-based retrievers we use the MPNet chunk/query embeddings; for E5-based retrievers we use the corresponding E5 embeddings. All embeddings are \(\ell_2\)-normalized, so inner product corresponds to cosine similarity, and each dense index is implemented as a FAISS inner-product index [24].

To make evaluation over large retriever pools tractable, we use cached candidate generation. For each query and dense backbone we first prefilter a fixed candidate set of \(M\) text chunks via the matching FAISS index (we use \(M=1000\) in all main experiments). Dense candidate retrievers then re-rank / re-select from this backbone-specific candidate set and output a fixed number of chunks \(n\) (we use \(n=4\)) that are passed to the answer model. Candidate retrieval outputs are cached per backbone and reused across all retriever configurations; see 7.1.

4.5 Candidate retriever pools↩︎

We instantiate the abstract candidate set \(\mathcal{R}\) as a heterogeneous union of multiple retriever families and multiple embedding backbones. Each family/backbone/hyperparameter configuration is treated as a distinct candidate retriever in the portfolio-selection problem. The portfolio objective and 3 are retriever-agnostic: they only require the training-query score matrix over candidates.

4.5.0.1 Dense baselines.

For each dense backbone, we include the standard top-\(n\) dense retriever that simply returns the highest-scoring FAISS neighbors with no diversification. In our implementation this is the DS configuration with hyperparameters \(\gamma=0\) and \(r=1\), so the dense baselines participate directly in the same candidate pool as the diversified DS variants.

4.5.0.2 DiscountedSimilarity (DS).

The DS retriever begins by ranking the backbone-specific candidate chunks according to their similarity scores with the question. It then iteratively selects \(n\) chunks while down-weighting candidates that are too similar to already-selected chunks. It is parameterized by a discount strength parameter \(\gamma\) and a similarity threshold \(r\). For each of MPNet and E5, the DS pool contains \(140\) \((\gamma,r)\) settings plus the dense baseline, giving \(141\) candidates per backbone embedding. In 7.2 we provide a pseudocode implementation of the DS retriever as well as the exact hyperparameter pool and other implementation details.

4.5.0.3 Vendi retriever.

Vendi [6] selects chunks by trading off query relevance and intra-set diversity using a Vendi-score-based objective, with trade-off parameter \(s\in[0,1]\). We instantiate Vendi separately over MPNet and E5 and sweep \(s\) in increments of \(0.05\) (21 configurations per backbone). In 7.3 we provide a pseudocode implementation of the Vendi retriever and other implementation details.

4.5.0.4 Graph-dense retrievers.

We also include graph-based dense retrieval variants, inspired by [25]. For each dataset, we build an entity-chunk graph from the chunked corpus, by identifying the entities that exist in a specific document chunk. The indexed graph is simply a bipartite graph where an entity has an edge with a chunk if it appears in that chunk. At query time, we identify the entities of the query and do a breadth-first search on the indexed graph to gather related document chunks. The fetched chunks are then reranked with MPNet or E5 dense similarity. The graph-dense pool sweeps the re-ranking backbone, the maximum number of graph-expansion hops, the maximum entity document frequency, and maximum graph candidates (see 7.5), yielding \(36\) graph-based candidates.

Overall, all the retriever pools contain \(360\) retrievers together: DS (including dense baselines) over MPNet/E5, Vendi over MPNet/E5, and graph-dense variants over MPNet/E5.

4.6 Portfolio construction↩︎

Portfolios are constructed offline using Algorithm 3 with the best-of-\(k\) objective. Concretely, we compute a score matrix \(s(q,r)\) which represents the performance of all candidate retrievers across a representative sample of training queries. The score function \(s(q,r)\) is instantiated to retrieval Recall@\(k\) and is calculated using the supporting documents of each question in the training set. For the all-pool experiment, we concatenate the score matrices for all family/backbone pools along the retriever dimension and run the greedy objective over the resulting union. This computation is accelerated by per-backbone caches and batched retriever implementations (for more details see 7.6).

Given the score matrix, we greedily select a portfolio \(S\) of size \(k\) maximizing \(\mathbb{E}_{q}[\max_{r\in S} s(q,r)]\). Our main portfolio is union-trained: we pool training queries across all datasets and select from the full heterogeneous candidate set. We compare this portfolio against average-best retriever selection, which chooses candidates by their mean training score, and against controls that retrieve more documents with a single retriever.

4.7 Metrics↩︎

We evaluate retrieval quality via Support Recall@\(k\) and F1@\(k\) based on ground-truth documents of the datasets. Downstream QA is assessed using Exact Match (EM) scores alongside generation token counts and wall-clock latency to characterize efficiency-accuracy trade-offs. We additionally report “retrieve more documents” controls to distinguish portfolio complementarity from simply increasing the context budget. See 7.8 for formal definitions, normalization procedures, and efficiency benchmarking details.

5 Results↩︎

We evaluate retriever portfolios on four QA benchmarks (HotpotQA, 2WikiMultiHopQA, TriviaQA, and MusiQue) using two answer models (Gemma-3-27B-It and Llama-3.1-70B-Instruct). Our results address three questions: (1) do learned portfolios provide better retrieval coverage as the portfolio size \(k\) grows (2) do these retrieval gains translate into end-to-end QA improvements beyond “retrieving more documents,” and (3) how do fixed portfolios compare to inference-time adaptation in terms of accuracy–cost trade-offs.

5.1 Portfolios improve retrieval coverage↩︎

We first measure retrieval performance in isolation, independent of the answer model. Following our formulation, we evaluate a size-\(k\) portfolio by its best-of-\(k\) retrieval score: for each query, we take the maximum support-document score achieved by any member of the portfolio. This isolates portfolio coverage from the downstream router and answer model, which are evaluated in the next subsection. Figure 4 reports support recall and support F1 for various portfolio sizes selected from the full heterogeneous candidate pool: DS and Vendi retrievers with MPNet and E5 backbones, together with GraphDense retrievers, for 360 candidates in total. The portfolio is trained once on the pooled training queries from all four benchmarks and then evaluated on the corresponding test sets.

2pt

5.1.0.1 Portfolio selection is not equivalent to picking the best retrievers on average.

A natural alternative to portfolio optimization is to perform a grid search over retriever configurations, rank candidates by their average training performance, and keep the top \(k\). Figure 4 evaluates exactly this baseline by taking the best-of-\(k\) score over the top-\(k\) candidates by average training score. The baseline is nearly flat: at \(k=5\), it reaches only 0.492 support recall and 0.432 support F1, while the learned portfolio reaches 0.594 and 0.500, respectively. The reason is visible in the selected portfolio. After the strongest average retriever, the greedy objective adds lower-average but complementary Vendi and GraphDense variants (Table 2) because they cover queries missed by earlier members. In contrast, the top-\(k\) average list is dominated by closely related GraphDense/E5 configurations, so additional members add little new coverage.

5.1.0.2 Gains are not explained by retrieving more documents.

Another possible explanation for the improved recall scores could be that a portfolio simply fetches more context. The \(k\times\) document baselines in Figure 4 test this directly: they run the single best retriever from each family while increasing the number of returned documents from \(4\) to \(4\cdot k\). As we can see, a portfolio with \(2\) members significantly outperforms even fetching \(20\) documents with the single best retriever. Inflating the number of fetched documents can increase recall, but does so by admitting many more non-support documents. Their support F1 therefore drops sharply as \(k\) grows (for DS and Vendi, from about 0.32 at \(k=1\) to about 0.11 at \(k=5\); for GraphDense, from 0.43 to 0.37). The pool portfolio shows the opposite pattern: support recall rises from 0.491 to 0.594, and support F1 rises from 0.431 to 0.500. Thus the gains come from selecting retrievers with complementary failure modes, not merely from increasing the number of retrieved passages.

5.1.0.3 The portfolio captures most of the available support signal.

The red horizontal line in Figure 4 is the recall of a method that picks the best retriever in the full candidate pool for every query. It is, of course, not a deployable method, since it assumes knowing which retriever will work for each query, but it indicates the maximum support score available in the pool. By \(k=5\), the learned portfolio closes most of this gap on both metrics, while using only five fixed retriever configurations that can be routed or run under a bounded inference budget.

5.2 End-to-end QA accuracy with routed portfolios↩︎

2.8pt

We now evaluate end-to-end Exact Match (EM), where a retrieved context is fed to the answer LLM. Table [tab:em] summarizes EM for no retrieval, nearest-neighbor retrieval, the best single retriever from each family, Vendi-RAG inference-time adaptation, a Vendi-only routed portfolio, and routed all-pool portfolios. The single-family rows choose the best configuration by average performance. For the routed portfolio rows, we report average-best operating points from their sweeps: Vendi-only \((k{=}5,\ell{=}2)\), and all-pool \((k{=}4,\ell{=}2)\) and \((k{=}4,\ell{=}3)\).

5.2.0.1 All-pool portfolios dominate the fixed-budget comparison.

The strongest entry in every dataset/model column comes from a full-pool portfolio. For Gemma-3-27B-It, the all-pool \((k{=}4,\ell{=}3)\) configuration has the best average EM, \(0.464\), while \((k{=}4,\ell{=}2)\) is close at \(0.456\). Both exceed the best single-family retrievers selected by average performance (DS: \(0.423\), Vendi: \(0.424\), GraphDense: \(0.397\)) and nearest-neighbor retrieval (\(0.356\)). For Llama-3.1-70B-Instruct, the same pattern holds: all-pool \((k{=}4,\ell{=}3)\) reaches average EM \(0.474\), with \((k{=}4,\ell{=}2)\) essentially tied at \(0.473\), above nearest-neighbor retrieval (\(0.403\)) and Vendi-RAG with \(T=20\) (\(0.421\)).

5.2.0.2 Heterogeneity matters.

The family-best DS, Vendi, and GraphDense baselines are strong single-retriever controls: each selects the best configuration within a retriever family by average EM. However, their performance varies substantially across datasets and answer models, so no single retriever family provides the best choice for all queries. The all-pool portfolio is designed to exploit this variation by selecting from the union of dense, diversity-based, and graph-based retrievers and routing each query to a small subset of portfolio members. Its consistent average gains over the family-best rows are therefore consistent with cross-family complementarity rather than merely better tuning within one family. This mirrors the retrieval-only result in Figure 4: average-best retriever selection identifies strong individual configurations, while the portfolio objective favors candidates that cover different query subpopulations.

5.2.0.3 Routing budget is a cost-accuracy knob.

The two reported all-pool rows differ only in the number of routed portfolio members executed per query. Increasing from \(\ell=2\) to \(\ell=3\) gives the best average EM for both answer models, especially on MusiQue and 2WikiMultiHopQA, while \(\ell=2\) is competitive and wins some columns such as TriviaQA. In deployment, this exposes a simple trade-off: \((k{=}4,\ell{=}3)\) is the highest-accuracy operating point in the table, while \((k{=}4,\ell{=}2)\) preserves most of the gain with fewer answer generations and judge comparisons.

5.3 Efficiency-accuracy trade-offs↩︎

Accuracy alone is insufficient for deployable RAG systems; adaptation must also be efficient. For this comparison, we intentionally do not use the heterogeneous all-pool portfolios from Figure 4. Instead, to make the comparison with Vendi-RAG as direct as possible, we isolate a single embedding backbone (MPNet) and a single retriever family (Vendi). The portfolio pool contains only Vendi retrievers that differ in the diversity parameter \(s\). This is exactly the one-dimensional hyperparameter that Vendi-RAG attempts to tune adaptively at inference time. Thus Figure 5 should be read as an apples-to-apples comparison between two ways of using the same Vendi search space: selecting a small fixed portfolio of \(s\) values offline versus searching over \(s\) sequentially at inference time. It is not intended as a full comparison between Vendi-RAG and our largest heterogeneous portfolios.

5.3.0.1 Offline Vendi portfolios are more efficient in the controlled comparison.

Under this restricted MPNet/Vendi setting, fixed Vendi portfolios occupy a better region of the cost-accuracy space: they achieve comparable EM to Vendi-RAG in the low-to-moderate cost regime while using substantially fewer tokens and lower wall-clock time (Figure 5). On Gemma, the portfolio is strictly preferable in this comparison, achieving higher EM at lower cost. On Llama, Vendi-RAG can reach slightly higher EM, but only after paying a large increase in tokens and latency.

5.3.0.2 Why portfolios are cheaper.

The search space is the same in this comparison; the difference is when and how it is searched. Vendi-RAG performs sequential per-query search over \(s\): it iterates retrieval, generation and judging, and each step depends on the previous step’s judged output. In contrast, portfolio learning amortizes the search offline by choosing a small set of complementary \(s\) values. At inference time, routing over the fixed Vendi portfolio requires only a bounded number of retrievals and LLM calls, and these calls can be parallelized across the selected portfolio members. This yields more predictable serving costs and enables practical deployment under latency/token constraints.

5.3.0.3 Summary.

Taken together, Figure 4 shows that portfolio learning yields complementary retrievers that better cover heterogeneous queries, Table [tab:em] shows that these gains translate into improved end-to-end QA (especially for Gemma), and Figure 5 shows that, in the controlled Vendi-only setting, offline portfolios provide a substantially better cost–accuracy trade-off than inference-time tuning over the same \(s\) grid.

Impact Statement↩︎

This work presents a principled framework for query-adaptive information retrieval, advancing the field of Retrieval-Augmented Generation (RAG). No specific malicious use of this technology is expected beyond the general risks associated with the deployment of large-scale generative models.

Acknowledgements↩︎

Miltiadis Stouras and Ola Svensson are supported by the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB22.00054.

6 Router Ablations↩︎

We ablate the learned router on the all-pool portfolio by comparing its ranked predictions against three references: a random portfolio member, the first portfolio member, and the oracle maximum over the portfolio. The first member is the size-one portfolio selected by the greedy objective, and therefore corresponds to the strongest single-retriever operating point within this portfolio prefix. The recall curve is shared across answer models; the EM curves use the corresponding answer model.

The router clearly improves over random selection from the portfolio. In the recall panel, random selection becomes worse as the portfolio grows because it often chooses a member that is not suitable for the current query. The learned router avoids this failure mode: even its top-1 prediction stays well above the random-member baseline for all nontrivial portfolio sizes, and the same pattern appears in both EM panels.

The top-1 router prediction also consistently improves over the single best retriever once \(k>1\). This shows that the router is not merely defaulting to the best average member. It uses the query to select different retrievers for different instances, yielding higher support recall and higher downstream EM than always using the first portfolio member.

Finally, the top-2 and top-3 curves are close to the oracle maximum over the portfolio. This indicates that the router often assigns high mass to the retrievers that are correct for the query, even when its first prediction is not the best one. This motivates the final selection layer: by executing the top \(\ell\) routed members and using the selector LLM to choose among their answers, the pipeline can exploit the router’s calibrated short list rather than relying only on a single argmax decision.

7 Implementation Details↩︎

This appendix provides additional implementation details needed to reproduce our retriever-portfolio experiments (Section 4). Unless stated otherwise, all experiments use dot-product similarity on \(\ell_2\)-normalized embeddings, so dot product coincides with cosine similarity.

7.1 Corpus preprocessing and FAISS indexing↩︎

7.1.0.1 Chunking.

For each dataset, we build a retrieval corpus by collecting all documents available in the dataset release (typically the union of train and test contexts). We split each document into overlapping chunks (“text units”) using a token-based sliding window with chunk size \(512\) and overlap \(50\) tokens. Each text unit stores its doc_id, chunk id, and text; dense embeddings are attached when building the corresponding backbone-specific index.

7.1.0.2 Embeddings.

We use two dense embedding backbones: MPNet (sentence-transformers/all-mpnet-base-v2) and E5 (intfloat/e5-large-v2). For each backbone, we embed both text units and queries with the corresponding SentenceTransformers encoder and \(\ell_2\)-normalize their embeddings. For E5, we use the standard role prefixes: query: for questions and passage: for chunks.

7.1.0.3 FAISS indices.

We build one FAISS IndexFlatIP [24] (exact maximum inner-product search) per dataset and dense backbone. For MPNet-based retrievers we search the MPNet index with MPNet query embeddings; for E5-based retrievers we search the E5 index with E5 query embeddings. Given a query/backbone pair, we first retrieve a prefiltered candidate set of size \(M\) (we use \(M=1000\) in all main experiments), then apply the retriever-specific selection rule over these candidates to return the final top \(K\) chunks (we use \(K=4\) throughout).

7.1.0.4 Graph sidecar.

Graph-dense retrievers are a simple graph-retriever variant inspired by [25]. They use the same chunk identifiers as the dense indices, but candidate generation is driven by a dataset-level entity–chunk graph rather than by FAISS prefiltering. The graph sidecar stores entity-to-chunk and chunk-to-entity adjacency lists and can attach chunk embeddings from either dense backbone for final dense reranking.

7.1.0.5 Caching.

To amortize evaluation over large retriever pools, we cache: (i) query embeddings separately for each split and backbone, (ii) for each query/backbone pair, its top-\(M\) FAISS candidates (including the candidate embeddings), and (iii) graph query-entity lists for graph-dense retrieval. Candidate retrieval outputs and score matrices are cached per family/backbone pool and reused across all retriever configurations.

7.2 DiscountedSimilarity retriever↩︎

DiscountedSimilarity (DS) is a greedy diversification heuristic that starts from standard query-chunk similarity, but down-weights candidates that are too similar to already-selected chunks. We instantiate DS separately for each dense backbone; the query embedding, candidate embeddings, and prefiltered candidate set always come from the same backbone-specific cache.

Let \(\mathcal{C}=\{x_1,\dots,x_M\}\) be the prefiltered candidate embeddings for a query \(q\), and let initial scores be \(s_i \leftarrow q^\top x_i\). DS iteratively constructs a set \(S\) of size \(k\). After selecting a chunk \(x_{i^\star}\), it computes similarities \(\sigma_j \leftarrow x_j^\top x_{i^\star}\) for remaining candidates and applies a multiplicative discount to those above a threshold \(r\): \[s_j \;\leftarrow\; s_j \cdot \exp(-\gamma \, \sigma_j) \quad\text{for all } j \text{ with } \sigma_j \ge r,\] where \(\gamma \ge 0\) controls discount strength and \(r \in [0,1]\) controls which candidates are considered “too similar”.

7.2.0.1 Naive baseline.

For each backbone, the DS pool includes a “naive” configuration \((\gamma=0, r=1)\), which reduces to standard top-\(k\) dense retrieval by similarity (no discounting in practice).

7.3 Vendi retriever↩︎

The Vendi retriever trades off query relevance with intra-set diversity via a Vendi-score objective [6]. Given a set of \(n\) selected normalized embeddings \(X_S \in \mathbb{R}^{n \times d}\), define the kernel \(K_S = X_S X_S^\top\) and let \(\lambda_1,\dots,\lambda_n\) be eigenvalues of \(K_S/n\). Define normalized weights \(w_i = \lambda_i / \sum_j \lambda_j\) and their entropy \(H(w) = -\sum_i w_i \log w_i\). The Vendi score is \[\textrm{Vendi}(S) \;=\; \textrm{exp}(H(w)).\] Intuitively, \(\textrm{Vendi}(S)\) behaves like an “effective number of distinct items”, ranging from \(1\) (highly redundant) to \(|S|\) (maximally diverse).

7.3.0.1 Greedy selection with trade-off \(s\).

For a query \(q\) and trade-off parameter \(s\in[0,1]\), we greedily construct \(S\) by selecting, at each step, the candidate that maximizes: \[\text{obj}(x) \;=\; s \cdot \textrm{Vendi}(S \cup \{x\}) \;+\; (1-s)\cdot \sum_{y\in S\cup\{x\}} q^\top y.\] Thus larger \(s\) emphasizes diversity, while smaller \(s\) emphasizes dense relevance. In our batched implementation (Section 7.6), the first choice is the most relevant item because \(\textrm{Vendi}(\{x\})\) is constant over singleton sets and the prefiltered candidate order is relevance-sorted. Subsequent steps follow the objective above.

7.4 Graph-dense retriever↩︎

The graph-dense retriever is a simple graph-retriever variant inspired by [25]. It uses a dataset-level entity–chunk graph for candidate generation and a dense encoder only for the final reranking step.

7.4.0.1 Graph construction.

For each dataset, we run entity extraction on document titles and corpus chunks. Entities are normalized by lowercasing, collapsing whitespace, and stripping surrounding punctuation. The graph sidecar stores two adjacency maps: (i) entity_to_chunk_keys, which maps each normalized entity to the ordered list of chunks that mention it, and (ii) chunk_to_entities, which maps each chunk key \((\texttt{doc\_id},\texttt{chunk\_id})\) to its normalized entities. Title entities are merged into every chunk from the same document. The sidecar also stores MPNet and E5 chunk-embedding matrices aligned to the same chunk-key order.

7.4.0.2 Query-time retrieval.

For each train/test split, query entities are extracted once and cached in question order. At retrieval time, the graph-dense retriever starts from the cached query entities, alternates entity and chunk frontiers, filters overly frequent entities, caps the number of graph candidates, and reranks the resulting chunks by dense similarity under the selected backbone.

7.4.0.3 Hyperparameters.

The graph-dense family has four hyperparameters: embedder selects the dense reranking backbone, either MPNet or E5; max_hops (\(H\)) is the graph-expansion depth, where odd hops add chunks from the current entity frontier and even hops discover new entities from the current chunk frontier; max_entity_df (\(D\)) is a document-frequency filter that skips entities appearing in more than \(D\) chunks; and max_candidates (\(C\)) is the maximum number of graph candidate chunks kept before dense reranking. If no query entities or no graph candidates are available, the retriever returns no chunks in our graph-dense pool evaluation.

7.5 Candidate retriever pools↩︎

We form structured candidate pools by sweeping hyperparameters and embedding backbones. The main all-pool portfolio concatenates the catalogued pools ds@mpnet, ds@e5, vendi@mpnet, vendi@e5, and graph_dense@mixed.

7.5.0.1 DS pools.

For each of MPNet and E5, we sweep \(\gamma \in \{0.2,0.4,0.6,0.8,1.0,1.2,1.4,1.6,1.8,2.0,4,6,8,10\}\) and \(r \in \{0.0,0.1,\dots,0.9\}\), yielding \(14\times 10=140\) diversified DS configurations. We add the naive setting \((0,1)\) for each backbone, for a total of \(141\) DS retrievers per backbone.

7.5.0.2 Vendi pools.

For each of MPNet and E5, we sweep \(s \in \{0.0, 0.05, 0.10, \dots, 0.95, 1.0\}\), giving \(21\) Vendi retrievers per backbone.

7.5.0.3 Graph-dense pool.

Graph-dense candidates use the retriever in 7.4. We sweep the reranking backbone in \(\{\text{MPNet},\text{E5}\}\), \[\texttt{max\_hops}\in\{1,3,5\},\qquad \texttt{max\_entity\_df}\in\{100,300,500\},\qquad \texttt{max\_candidates}\in\{1000,2000\}.\] This gives \(2\times 3\times 3\times 2=36\) graph-dense variants. The pool is stored under a mixed graph-dense artifact key because one graph family contains both MPNet-reranked and E5-reranked variants. Individual variants are named {embedder}_h{max_hops}_df{max_entity_df}_c{max_candidates}.

Altogether, the all-pool candidate set contains \(360\) retrievers.

7.6 Efficient batched evaluation over retriever pools↩︎

Evaluating all retriever configurations for all queries can be dominated by repeated reranking and greedy selection. We therefore batch computation within each family/backbone pool and reuse cached artifacts whenever possible.

7.6.0.1 Backbone-specific prefiltering.

For each query and dense backbone, we run FAISS once to obtain top-\(M\) candidates and reuse this fixed set across all DS and Vendi configurations that use that backbone. This eliminates repeated nearest-neighbor search when sweeping hyperparameters while keeping MPNet and E5 artifacts separate.

7.6.0.2 BatchDiscountedSimilarity.

Given a fixed candidate set, we precompute the candidate embedding matrix \(X\in\mathbb{R}^{M\times d}\) and the base similarity vector \(a=Xq\) once. For a batch of \(B\) DS configurations \(\{(\gamma_b,r_b)\}_{b=1}^B\), we maintain a score matrix \(S\in\mathbb{R}^{B\times M}\) initialized as \(S_{b,i}=a_i\), and update all \(B\) rows in parallel when discounting around each selected item. These matrix operations are highly parallelizable and can be significantly accelerated via GPU kernels, providing a large speedup when \(B\) is large (e.g., 141 DS configurations per backbone).

7.6.0.3 BatchVendiRetriever.

For a batch of \(B\) Vendi configurations (different \(s\) values), we share: (i) relevance scores \(a_i = q^\top x_i\), and (ii) the candidate-candidate similarity kernel \(K = XX^\top\). Since \(k\) is small (\(M=1000\)) and we only ever compute the Vendi score on subsets of size up to \(k=4\), the incremental cost is dominated by eigendecompositions of \(3\times 3\) and \(4\times 4\) matrices, which is negligible compared to FAISS and LLM calls.

7.6.0.4 BatchGraphDenseRetriever.

For graph-dense retrieval, we cache query entities and expand the graph once per query up to the maximum hop, entity-frequency, and candidate-count limits used by the pool. Each graph-dense hyperparameter setting is then evaluated by filtering this shared expansion context and reranking its candidate chunks with the requested dense backbone. When both MPNet and E5 variants are present, the query embeddings are loaded as a dictionary keyed by backbone and the same graph candidate set is reranked with the matching chunk-embedding matrix.

7.7 LLM prompting and answer selection↩︎

We use the same prompt templates across methods to ensure fair comparison.

7.7.0.1 Answer prompt (Answer LLM).

Given a question and the retrieved passages, the answerer is instructed to be evidence-first and to output a short final answer inside an <answer>...</answer> tag, along with a brief structured explanation indicating whether the answer is supported by the passages (mode=evidence) or a fallback guess (mode=guess). This structured output is used by the judge during selection.

The exact system & user prompts that we are using are the following.

7.7.0.2 Selection prompt (Selector LLM).

When we evaluate multiple retrievers per query (\(\ell>1\)), we run the answerer once per retriever and then prompt a judge model with only the question and the candidate answers (including their structured explanations). The judge selects the single most trustworthy candidate and outputs the chosen answer in a <judge>...</judge> tag.

The exact system and user prompts that we used are the following.

7.8 Evaluation metrics↩︎

7.8.0.1 Retrieval Metrics

We evaluate retrieval performance against a set of reference supporting documents that are provided for each question in the datasets. Since retrieval operates at the chunk level, a retrieved chunk is considered a “hit” if its document ID matches one of the reference document identifiers. We report document-level performance using the following metrics at a fixed budget of \(n\) retrieved items:

• Support Recall@\(k\): The fraction of reference documents successfully identified within the top \(k\) retrieved results.

• Support F1@\(k\): The harmonic mean of precision and recall at budget \(k\). This provides a balanced measure that accounts for both the accuracy (precision) of the retrieved chunks and the completeness (recall) of the retrieved support set.

7.8.0.2 End-to-end QA.

We report Exact Match (EM) scores for the final selected answer. A prediction is considered correct if, after standard normalization (lowercasing, stripping punctuation and articles), it exactly matches any of the reference ground-truth answers. To characterize the efficiency-accuracy trade-offs of our approach, we further measure the total tokens generated and the end-to-end wall-clock latency of the routed pipeline.

7.8.0.3 Retrieve-more controls.

To separate portfolio complementarity from simply increasing context length, we also evaluate single-retriever controls that retrieve a larger number of documents under the same answer-generation prompt format. These controls use one retriever configuration rather than a portfolio and therefore do not benefit from best-of-\(k\) coverage across complementary retrieval behaviors.

7.9 Router model and training↩︎

We train a query router that maps each question \(q\) to a ranking over the \(k\) retrievers in a learned portfolio.

7.9.0.1 Inputs.

Each question \(q\) is represented by: (i) its raw text (tokenized for a T5 encoder), (ii) a dense MPNet query embedding \(e_{\text{mp}}(q)\in\mathbb{R}^{d_{\text{mp}}}\), and (iii) a dense E5 query embedding \(e_{\text{e5}}(q)\in\mathbb{R}^{d_{\text{e5}}}\). The dense query embeddings are loaded from the same per-backbone caches used by retrieval. The router also carries binary masks for the dense modalities so a missing embedding can be zeroed after projection.

7.9.0.2 Architecture.

Let \(h_{\text{t5}}(q)\in\mathbb{R}^{d_{\text{t5}}}\) denote the pooled Flan-T5-large encoder output. We pool by averaging the encoder hidden states across tokens using the attention mask. The T5 encoder is frozen throughout router training.

We project the text representation and both dense embeddings to a common dimension \(d=256\): \[\tilde{h}(q) = \phi_h\!\left(W_h\,h_{\text{t5}}(q)\right),\qquad \tilde{m}(q) = m_{\text{mp}}\phi_{\text{mp}}\!\left(W_{\text{mp}}\,e_{\text{mp}}(q)\right),\qquad \tilde{e}(q) = m_{\text{e5}}\phi_{\text{e5}}\!\left(W_{\text{e5}}\,e_{\text{e5}}(q)\right),\] where each \(\phi(\cdot)\) is a linear layer followed by ReLU, dropout, and LayerNorm, and \(m_{\text{mp}},m_{\text{e5}}\in\{0,1\}\) are modality masks.

We fuse the three projected vectors with a small MLP and LayerNorm: \[z(q)=\mathrm{LayerNorm}\!\Big(\mathrm{MLP}\big([\tilde{h}(q);\tilde{m}(q);\tilde{e}(q)]\big)\Big)\in\mathbb{R}^{256}, \qquad \hat{z}(q)=\frac{z(q)}{\|z(q)\|_2}.\]

The router learns one trainable prototype vector per retriever in the portfolio, \(\{v(r)\in\mathbb{R}^{256}\}_{r=1}^k\), and uses cosine similarity scores: \[\textrm{sim}(q,r)=\cos\!\big(\hat{z}(q), \hat{v}(r)\big) \quad\text{where}\quad \hat{v}(r)=\frac{v(r)}{\|v(r)\|_2}.\] At inference time, the router ranks retrievers by \(\textrm{sim}(q,r)\) and executes either the argmax retriever or the top-\(\ell\) retrievers, depending on the evaluation budget.

7.9.0.3 Training supervision from retrieval recall.

For each training question \(q\), we precompute a vector of retrieval scores \(\mathrm{Rec}@K(q)\in\mathbb{R}^k\), one value per portfolio member, where \(K\) is the number of documents retrieved for evaluation. We define the winner set as the set of retrievers achieving the maximum recall on that instance: \[W(q)=\Big\{r:\mathrm{Rec}@K(q,r)=\max_{r'}\mathrm{Rec}@K(q,r')\Big\}.\] Questions for which \(\max_r \mathrm{Rec}@K(q,r)=0\) provide no routing signal; we exclude them from training/evaluation. To avoid unstable supervision from very large ties, we additionally ignore questions with \(|W(q)|>T\) (default \(T=3\)).

7.9.0.4 Contrastive argmax objective (multi-positive).

Let \(p(r\mid q)=\mathrm{softmax}_r\big(s(q,r)\big)\) be the distribution induced by the cosine scores. We minimize a multi-positive contrastive argmax loss that concentrates probability mass on the winner set: \[\mathcal{L}(q) = -\frac{1}{|W(q)|}\sum_{r\in W(q)}\log p(r\mid q).\] This treats all tied-best retrievers as positives and encourages the router to assign them high likelihood.

7.9.0.5 Balanced batching.

To reduce dominance of frequent single-winner cases, we bin training questions by their winner structure (e.g., “\(R_i\)-unique” when retriever \(i\) is the unique winner, and optional tie bins such as tie2/tie3), and sample batches in a round-robin manner across non-empty bins.

7.9.0.6 Optimization and schedule.

We keep the T5 encoder frozen and optimize only the dense projection heads, fusion MLP, and retriever prototype vectors. Checkpoints store only non-T5 weights. We optimize with AdamW using a single learning rate for all trainable parameters. Model selection is performed by highest dev recall@K under \(\arg\max_r s(q,r)\) routing.

7.9.0.7 Default hyperparameters.

Unless otherwise stated, we use:

• Epochs: \(10\).

• Batch size: \(64\); gradient accumulation: \(1\) step; gradient clipping: \(1.0\).

• Learning rate: \(3\times 10^{-4}\) for all trainable non-T5 parameters.

• Max input length: \(256\) tokens.

• Max tie size: \(T=3\) (ignore questions \(q\) with \(|W(q)|>T\)).

7.10 Vendi-RAG baseline details↩︎

For the Vendi-RAG baseline [6], our implementation follows the one described in [6]. We implement a \(T\)-step adaptive loop over the Vendi trade-off parameter \(s\): starting from an initial \(s_0 = 0.8\), we repeatedly (i) retrieve with Vendi at \(s_t\), (ii) answer with the same answer LLM used elsewhere, (iii) score the answer with a judge LLM, and (iv) update \(s\) for the next iteration. Our update rule maps the judge score (clamped to \([0,10]\)) to \(s_{t+1}=1-\text{score}/10\), i.e., lower judged answer quality increases \(s\) and shifts subsequent retrieval toward more diverse evidence. The final answer is the step with the best judge score.

8 Detailed proofs and explanations of 3↩︎

We give a detailed analysis of 3, and, in particular, we prove 1. The running time is immediate from the explanations and the pseudocode in 3. We thus focus on the approximation guarantee and the sample complexity \(N\), which follows from that the function is monotone and submodular, and a simple uniform convergence bound (via Hoeffding’s inequality and a union bound).

Recall that a set function \(f:2^V\to\mathbb{R}\) is normalized if \(f(\emptyset)=0\). It is monotone if \(f(A)\le f(B)\) for all \(A\subseteq B\subseteq V\). It is submodular if it satisfies the diminishing returns property, i.e., for all \(A\subseteq B\subseteq V\) and \(x\in V\setminus B\), \[f(A\cup\{x\})-f(A)\ge f(B\cup\{x\})-f(B).\] Further note that a normalized, monotone set function is non-negative.

8.1 Submodularity of the best-of-\(k\) objective↩︎

For a fixed query \(q\), define \(f_q(S):=\max_{r\in S}s(q,r)\) with \(f_q(\emptyset)=0\). Recall \(s(q,r)\in[0,1]\).

Given \(Q=\{q_1,\dots,q_N\}\sim\mathcal{D}^N\), define the empirical objective \[\widehat F_Q(S):=\frac{1}{N}\sum_{i=1}^N f_{q_i}(S) =\frac{1}{N}\sum_{i=1}^N\max_{r\in S}s(q_i,r).\]

8.2 Uniform convergence from finitely many query samples↩︎

8.3 End-to-end population guarantee↩︎

The following theorem implies the stated guarantee of 1.

References↩︎

---

1. A set function \(f:2^V\to\mathbb{R}\) is non-negative if \(f(S)\geq 0\). It is monotone if \(f(A)\le f(B)\) for all \(A\subseteq B\subseteq V\). It is submodular if it satisfies the diminishing returns property, i.e., for all \(A\subseteq B\subseteq V\) and \(x\in V\setminus B\), \(f(A\cup\{x\})-f(A)\ge f(B\cup\{x\})-f(B).\)↩︎