ReBOL: Retrieval via Bayesian Optimization with Batched LLM Relevance Observations and Query Reformulation¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://anonymous.4open.science/r/ReBOL-5D56/README.md
Area: Information Retrieval & RAG
Keywords: Bayesian Optimization, Large Language Models, Query Reformulation, Active Retrieval, Gaussian Processes
TL;DR¶
ReBOL reformulates the standard reformulate-retrieve-rerank pipeline into a Bayesian optimization framework, using LLM query reformulations to seed a multimodal Gaussian process posterior and actively acquiring diversified document batches for LLM relevance scoring to overcome vector retrieval recall bottlenecks.
Background & Motivation¶
Modern search and retrieval-augmented generation (RAG) pipelines predominantly rely on a two-stage cascade: first, a bi-encoder dense retriever retrieves a top-\(k\) candidate list based on vector similarity, and second, an LLM acts as a pointwise or listwise reranker to reorder the candidates. However, the downstream performance of this pipeline is fundamentally bounded by the initial retrieval recall. Bi-encoders map queries and documents into separate vector spaces and compute dot products or cosine similarities. This architectural separation precludes deep token-level cross-attention and imposes an inherently unimodal relevance assumption centered at the query embedding, whereas in practical retrieval tasks, relevant documents naturally reside across multiple diverse semantic clusters.
To alleviate poor retrieval recall, query reformulation (QR) techniques employ LLMs to generate one or more alternative formulations of the initial query. Yet, in typical pipelines, these reformulations are still fed into standard vector similarity retrievers, with candidates pooled through naive similarity averaging or ranked list fusion. When the underlying vector similarity search misses relevant clusters due to vocabulary mismatch or semantic drift, downstream LLM rerankers remain powerless because they cannot judge documents that were never retrieved in the top-\(k\) set.
This paper tackles this limitation by reframing the retrieval process as Bayesian optimization (BO) over a black-box document relevance function. Core idea: use an initial query and its LLM reformulations to initialize multiple relevance peaks in a multimodal Gaussian process posterior, and iteratively acquire diversified document batches for LLM relevance assessment to actively optimize retrieval across the entire corpus.
Method¶
Overall Architecture¶
ReBOL (Retrieval via Bayesian Optimization with Batched LLM Relevance Observations and Query Reformulation) models the query-document relevance function \(f: \mathbb{R}^m \to [0, s_{\max}]\) as an unknown black-box function over the embedding space of a dense text encoder, bounded between 0 (completely irrelevant) and \(s_{\max} = 3\) (highly relevant). Given a user query \(q_0\), ReBOL first prompts an LLM to generate \(Q\) distinct query reformulations \(\{q_1, \dots, q_Q\}\). The embeddings of both the original query and all reformulations are injected into a Gaussian process (GP) prior with maximal relevance observations to form an initial multimodal posterior. Subsequently, the system enters an iterative active retrieval loop: in each step, an acquisition function selects a batch of candidate documents across the unobserved corpus; an LLM scores the query-document relevance of this batch in a single call; and the GP posterior is analytically updated.
The end-to-end operational pipeline is depicted in the flowchart below, where each major processing stage directly aligns with the key designs:
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input Query q0 and Document Corpus"] --> B["LLM Query Reformulation & Multimodal Posterior Initialization<br/>Generate reformulations and seed relevance peaks in embedding space"]
B --> C["Diversified Document Batch Acquisition<br/>MMR / UCB balancing posterior mean and uncertainty"]
C --> D["Batched LLM Relevance Scoring<br/>UMBRELA 0-3 relevance scoring in single LLM prompt"]
D --> E["Gaussian Process Posterior Updating<br/>Closed-form predictive mean and variance update"]
E -->|Under observation budget B_max| C
E -->|Observation budget reached| F["Output Final Ranked Documents<br/>Sort candidates by descending GP posterior mean"]
Key Designs¶
1. LLM Query Reformulation & Multimodal Posterior Initialization: Breaking the Unimodal Inductive Bias Standard dense retrieval computes linear inner products, inducing a unimodal distribution of relevance scores centered around the query vector. ReBOL overcomes this limitation by placing a zero-mean Gaussian process prior over the latent relevance function \(f(z)\) using a non-linear Radial Basis Function (RBF) kernel: $\(k(z, z') = \sigma_s^2 \exp\left(-\frac{\|z - z'\|_2^2}{2\ell^2}\right)\)$ To capture the multifaceted nature of complex queries, ReBOL prompts an LLM to generate \(Q\) alternative query rewrites \(\{q_1, \dots, q_Q\}\). The initial query and each rewrite are incorporated into the GP prior as synthetic observations with maximal relevance: \((z_{q_i}, s_{\max})\) for \(i \in \{0, 1, \dots, Q\}\). Because the RBF kernel non-linearly decays with Euclidean distance, these observation points create multiple distinct relevance peaks in the latent space. Regions far from any query formulation naturally revert to the prior mean of 0, reflecting the prior belief that most documents in a large corpus are irrelevant, while providing multiple distinct seeds for global exploration.
2. Diversified Document Batch Acquisition: Balancing Exploration with Redundancy Reduction In each iteration \(t\), ReBOL must select a batch \(B_t\) of \(B\) documents from the unobserved collection \(\mathcal{X} \setminus \mathcal{D}_t\). A single-point acquisition function such as Upper Confidence Bound (UCB) balances exploitation and exploration: $\(\alpha(z_d | \mathcal{D}_t) = \mu[f(z_d)] + \sqrt{\beta}\,\sigma[f(z_d)]\)$ where the posterior mean \(\mu[f(z_d)]\) and standard deviation \(\sigma[f(z_d)]\) are computed analytically from the GP. However, taking the top-\(B\) candidates greedily often selects near-duplicate documents within the same local neighborhood, wasting LLM labeling budget. Rather than using Kriging Believer (KB)โwhich requires recomputing the full posterior \(B\) times per batchโReBOL introduces a novel Maximal Marginal Relevance (MMR) inspired batch acquisition function. After picking the first document \(d_t = \arg\max_{d} \alpha(z_d|\mathcal{D}_t)\), subsequent candidates are added sequentially by maximizing a penalized objective: $\(d_{t+i} = \arg\max_{d \in \mathcal{X} \setminus B_t} \left[ \lambda \alpha(z_d | \mathcal{D}_t) - (1 - \lambda) \max_{d' \in B_t} S(z_d, z_{d'}) \right]\)$ Here \(S(\cdot, \cdot)\) denotes cosine similarity and \(\lambda\) dictates the trade-off between acquisition value and batch diversity. This design evaluates the acquisition function only once per batch and uses fast vector dot products for diversity penalization, dramatically reducing computational overhead while ensuring diverse sample selection.
3. Batched LLM Relevance Scoring: Reducing Inference Latency and Exploiting Document Interactions Issuing individual LLM inference requests for every single document induces prohibitive latency and fails to exploit cross-document attention context. ReBOL groups the selected batch of \(B\) documents into a unified prompt, prompting the LLM to output absolute relevance scores \(\{s_{q_0, d}\}\) based on the 4-level UMBRELA rubric (\(0 = \text{irrelevant}\), \(1 = \text{related but non-answering}\), \(2 = \text{partially answering}\), \(3 = \text{dedicated and exact answer}\)). These scores are treated as noisy observations \(y \sim \mathcal{N}(f(z), \sigma_n^2)\). Using closed-form GP inference, the predictive posterior mean \(\mu[f(z')]\) and variance \(\sigma^2[f(z')]\) are updated across the document collection. Because document rankings are dynamically derived from \(\mu[f(z_d)]\), ReBOL functions as an anytime algorithm that can terminate at any observation budget and return a ranked candidate list with calibrated predictive scores.
Key Experimental Results¶
Main Results¶
The authors evaluate ReBOL across five diverse BEIR benchmark datasets (spanning news, biomedical research, and fact-checking) against lexical baselines, dense retrieval, and LLM rerankers using Gemini-2.5-Flash-Lite, with a budget of 100 document observations.
| Dataset | Metric | Dense (QR) + PW | LW-window (QR) | ReBOL-QR-Greedy | ReBOL-QR-UCB | Gain over Dense+PW |
|---|---|---|---|---|---|---|
| Robust04 | R@100 | 35.0 | 35.0 | 45.6* | 46.5* | +32.9% |
| Robust04 | NDCG@10 | 61.2 | 58.6 | 63.6 | 63.3 | +3.9% |
| TREC-COVID | R@100 | 8.0 | 8.0 | 15.6* | 15.6* | +95.0% |
| TREC-COVID | NDCG@10 | 66.5 | 72.6 | 76.8 | 75.4 | +15.5% |
| NFCorpus | R@100 | 33.7 | 33.7 | 36.1 | 37.7 | +11.9% |
| NFCorpus | NDCG@10 | 39.3 | 39.9 | 40.1 | 40.2 | +2.3% |
| SciFact | R@100 | 96.6 | 96.6 | 96.7 | 96.7 | +0.1% |
| SciFact | NDCG@10 | 71.0 | 76.7 | 73.5 | 73.5 | +3.5% |
| TREC-NEWS | R@100 | 45.7 | 45.7 | 49.9 | 52.7 | +15.3% |
| TREC-NEWS | NDCG@10 | 44.0 | 49.6 | 45.1 | 45.7 | +3.9% |
(Note: * indicates statistically significant improvement over baselines at \(p < 0.05\). PW = Pointwise scoring, LW = Listwise reranking.)
Ablation Study¶
Evaluation of batch diversification strategies (MMR, Kriging Believer, Top-B) and diversity parameter \(\lambda\) under ReBOL-QR-UCB (Table 4 of the paper):
| Batch Acquisition Strategy | Diversity Parameter \(\lambda\) | Robust04 R@100 | Robust04 NDCG@10 | TREC-COVID R@100 | TREC-COVID NDCG@10 | Note |
|---|---|---|---|---|---|---|
| Top-B (No Diversity) | - | 46.5* | 63.3 | 15.6* | 75.4 | Baseline non-diversified batching |
| Kriging Believer (KB) | - | 45.6* | 63.7 | 16.0* | 83.2 | High computational cost (\(B\times\) updates) |
| MMR | \(\lambda = 0.9\) | 46.7* | 64.6 | 15.9* | 77.3 | Mild diversity penalty, steady gains |
| MMR | \(\lambda = 0.7\) | 47.1* | 65.2 | 16.1* | 78.2 | Best empirical balance for recall and ranking |
| MMR | \(\lambda = 0.5\) | 44.7* | 63.8 | 16.1* | 83.2 | Over-exploration degrades exploitation |
Key Findings¶
- Substantial Recall Leaps: Unlike standard LLM rerankers whose recall is permanently capped by upstream dense retrieval (e.g., 35.0% on Robust04 and 8.0% on TREC-COVID), ReBOL actively searches the global space via Bayesian optimization, achieving 46.5% (+32.9%) and 15.6% (+95.0%) recall@100, demonstrating that active exploration effectively recovers documents missed by bi-encoders.
- Warm Start via Query Reformulation: Introducing LLM query reformulations (ReBOL-QR vs. ReBOL-IQ) provides immediate benefits, especially under constrained observation budgets (e.g., 50 observations) and for random acquisition, confirming that multiple query vectors seed effective multimodal anchors in the GP prior.
- Efficiency and Latency Profile: While serial Bayesian optimization (\(B=1\)) slightly improves ranking quality by incorporating the freshest feedback at each step, it incurs prohibitive per-query latencies (~40s). Batched acquisition with \(B=10\) slashes total latency to 5โ8 seconds, matching standard pointwise LLM rerankers because LLM inference heavily dominates the negligible GP inference overhead.
Highlights & Insights¶
- Reconceptualizing Retrieval as Active Search: ReBOL shifts the paradigm from passive, static "retrieve-then-rerank" cascades to an active exploration process where high-precision LLM judgments directly steer posterior updates and subsequent sampling locations.
- MMR-style Batch Diversification: Adapting classical IR maximal marginal relevance into GP batch acquisition eliminates the heavy computational burden of Kriging Believer while outperforming it empirically, offering an elegant blueprint for batched Bayesian active learning.
- Model Agnostic Versatility: Experiments with GPT-5.2 and cross-encoders confirm that ReBOL consistently outperforms standard rerankers across diverse scoring backbones, highlighting its general applicability to enterprise search and RAG architectures.
Limitations & Future Work¶
- Scalability on Massive Corpora: Computing GP predictive distributions across hundreds of thousands of candidate document embeddings requires matrix operations that, while parallelizable on GPU, pose scalability challenges on web-scale indices (tens of millions of documents) without clustering or hierarchical partitioning.
- Fixed Hyperparameter Setting: The GP kernel parameters (\(\sigma_s^2=1\), \(\sigma_n^2=1\), \(\ell=1\)) were kept fixed across all benchmarks rather than being tuned via online marginal likelihood maximization or adaptive length-scale estimation.
- Vulnerability to LLM Scoring Biases: Relying on LLM zero-shot absolute scoring can expose the Bayesian posterior to model hallucinations, social biases, or adversarial manipulation (e.g., prompt injections embedded within crawled web pages).
Related Work & Insights¶
- vs Dense Retrieval + LLM Reranking (Ma et al., 2023; Upadhyay et al., 2024): Existing pipelines passively rank an invariant top-\(k\) set retrieved by bi-encoders; ReBOL actively queries the corpus, utilizing LLM relevance signals to break the top-\(k\) recall ceiling.
- vs LLM Query Reformulation (Wang et al., 2023; Kostric & Balog, 2024): Previous methods treat reformulations as isolated queries and aggregate candidates via score averaging; ReBOL uses reformulations as joint observation seeds to form a multimodal GP posterior landscape.
- vs Active Learning with GPs (Kim et al., 2026; Liu et al., 2026): While prior work explored GP active learning with LLMs in serial single-point settings or recommendation tasks, ReBOL introduces multimodal query seeding and fast MMR-based batch diversification, achieving high recall and low latency on standard IR benchmarks.
Rating¶
- Novelty: โญโญโญโญโญ Seamlessly unifies LLM query reformulation, Bayesian optimization, and active batch acquisition to replace brittle multi-stage retrieval cascades.
- Experimental Thoroughness: โญโญโญโญโ Rigorous evaluation across five BEIR datasets, multiple LLM backbones, cross-encoders, and detailed batch/observation ablations.
- Writing Quality: โญโญโญโญโญ Exceptionally structured formulation with clear mathematical definitions, intuitive visualizations, and well-contextualized empirical analysis.
- Value: โญโญโญโญโญ Directly addresses the long-standing recall bottleneck of neural retrieval, providing an actionable paradigm for future RAG and conversational search systems.