ReBOL: Retrieval via Bayesian Optimization with Batched LLM Relevance Observations and Query Reformulation

Anton Korikov; Scott Sanner

cs.IRMar 20, 2026

ReBOL: Retrieval via Bayesian Optimization with Batched LLM Relevance Observations and Query Reformulation

Authors: Anton Korikov, Scott Sanner

Organizations: University of Toronto

Abstract

LLM-reranking is limited by the top-k documents retrieved by vector similarity, which neither enables contextual query-document token interactions nor captures multimodal relevance distributions. While LLM query reformulation attempts to improve recall by generating improved or additional queries, it is still followed by vector similarity retrieval. We thus propose to address these top-k retrieval stage failures by introducing ReBOL, which 1) uses LLM query reformulations to initialize a multimodal Bayesian Optimization (BO) posterior over document relevance, and 2) iteratively acquires document batches for LLM query-document relevance scoring followed by posterior updates to optimize relevance. After exploring query reformulation and document batch diversification techniques, we evaluate ReBOL against LLM reranker baselines on five BEIR datasets and using two LLMs (Gemini-2.5-Flash-Lite, GPT-5.2). ReBOL consistently achieves higher recall and competitive rankings, for example compared to the best LLM reranker on the Robust04 dataset with 46.5% vs. 35.0% recall@100 and 63.6% vs. 61.2% NDCG@10. We also show that ReBOL can achieve comparable latency to LLM rerankers.

Figures & tables

Figure 1: a-b) LLM rankers rely on upstream vector similarity retrieval to reduce a large document collection to a top- $k$ candidate list. c) ReBOL-IQ ( I nitial Q uery) first initializes a GP prior with a high-relevance point at the query embedding (yellow square), then iteratively selects which document to judge next using an acquisition function (blue star), scores its relevance to the query using an LLM, and updates a multimodal GP posterior.

Figure 2: Given $q_{0}$ , an LLM generates query reformulations $q_{1}$ and $q_{2}$ . a) An example reformulate-retrieve-rerank pipeline, using each $q\in\{q_{0},q_{1},q_{2}\}$ for vector similarity retrieval before score averaging and batched top- $k$ LLM scoring b) ReBOL-QR ( Q uery R eformulation) initializes a multimodal GP posterior with peaks at query embeddings $\{z^{q_{0}},z^{q_{1}},$ $z^{q_{2}}\}$ followed by active document batch acquisition, batched LLM scoring, and posterior updating.

Dataset	#docs	#qs	#rel d/q
TREC-NEWS	595K	57	19.6
Robust04	528K	249	69.9
TREC-COVID	171K	50	493.5
SciFact	5K	300	1.1
NFCorpus	3.6K	323	38.2

Table 1: BEIR Thakur et al. (2021) dataset statistics for corpus size, # of queries, and mean # of relevant docs.

Method	nfcorpus		scifact		robust		covid		news
Method	R@100	N@10	R@100	N@10	R@100	N@10	R@100	N@10	R@100	N@10
BM25 Flat	24.6	32.2	92.5	67.9	37.5	40.7	10.9	59.5	44.7	39.5
BM25 MF	25.0	32.5	90.8	66.5	37.5	40.7	11.4	65.6	42.2	39.8
SPLADE	28.4	34.7	93.5	70.4	38.5	46.8	12.8	72.7	44.1	41.5
Dense (IQ)	30.8	31.6	92.8	64.9	32.7	40.5	9.5	51.8	42.3	38.2
PW (IQ)	30.8	37.7	92.8	70.4	32.7	59.8	9.5	71.3	42.3	45.8

Table 2: Recall(R)@100 and NDCG(N)@10 using Gemini-2.5-Flash-Lite for ReBOL with Top-

B

acquisition (

B=10

) versus LLM rerankers, including IQ (initial query) and QR (query reformulations added) variants. The best overall method is bold while the best absolute LLM scoring method (PW or ReBOL) is underlined . QR is generally helpful, and ReBOL with greedy or UCB acquisition consistently shows large improvements in recall and competitive rankings.

Method	Batch	covid				news
		Metric		Time (s)		Metric		Time (s)
		R@100	N@10	LLM	Total	R@100	N@10	LLM	Total
Dense (QR)	n/a	8.0	45.4	0.8	1.0	45.7	43.3	0.6	1.1
PW (QR)	1	8.0	65.9	38.2	38.4	45.9	44.7	37.3	38.0
ReBOL-QR-Greedy		15.6	79.6	39.4	42.9	51.3	48.4	37.6	41.9
ReBOL-QR-UCB		16.4	82.4	39.4	46.9	52.8	47.9	39.3	63.7

Table 3: Batch size

B=1

vs. 10 ablation for ReBOL-QR (Top-

B

) versus PW Reranking (QR) showing Recall(R)@100 and NDCG(N)@10, as well as mean time per query spent in LLM calls versus in total — both PW and ReBOL see large latency reductions due to batching. ReBOL performs noticeably better with

B=1

, showing the benefits of more interleaved LLM scoring and BO if time is available.

Method	Diversity	nfcorpus		scifact		robust		covid		news
Method	Diversity	R@100	N@10	R@100	N@10	R@100	N@10	R@100	N@10	R@100	N@10
Dense (QR)	n/a	30.8	31.6	92.8	64.9	32.7	40.5	9.5	51.8	42.3	38.2
	MMR 0.9	33.0	33.6	96.6	70.9	34.4	43.9	8.1	46.2	44.2	41.7
	MMR 0.7	29.2	30.8	94.9	71.1	30.0	40.7	7.8	41.6	36.0	34.8
	MMR 0.5	15.6	21.9	74.5	63.7	9.7	24.7	1.9	26.7	8.2	21.9
ReBOL-QR-Greedy	Top-B	36.1	40.1	96.7	73.5	45.6	63.6	15.6	76.8	49.9	45.1

Table 4: Effect of diversification methods, including MMR (

x=\lambda

), Kriging Believer, and Top-

B

(no diversity).

Method	Diversity	nfcorpus		scifact		robust		covid		news
		LLM	Total	LLM	Total	LLM	Total	LLM	Total	LLM	Total
Dense	n/a	0.0	0.1	0.0	0.1	0.0	0.4	0.0	0.2	0.0	0.4
Dense (QR)	n/a	0.9	0.9	0.8	0.9	1.1	1.4	0.8	1.0	0.6	1.1
PW (QR)	n/a	5.0	5.0	5.0	5.0	5.6	6.0	4.9	5.0	5.5	5.9
LW-one-call (QR)	n/a	4.1	4.1	4.3	4.3	4.4	4.8	2.7	2.8	4.5	5.0
LW-window (QR)	n/a	8.3	8.3	9.7	9.8	11.9	12.3	7.3	7.4	15.7	16.7

Table 5: Mean time (s) per query spent in LLM calls versus in total, with

B=10

for ReBOL and PW.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Listwise reranking prompt — real document IDs are simplified before prompting to ["d1" , $...$ , "dk"] for $k$ documents.

Method	GPT-5.2				Cross-Encoder
	covid		news		covid		news
	R@100	N@10	R@100	N@10	R@100	N@10	R@100	N@10
Dense (IQ)	9.5	51.8	42.3	38.2	9.5	51.8	42.3	38.2
PW (IQ)	9.5	73.8	42.3	45.9	9.5	74.0	42.3	45.6
LW-window (IQ)	9.5	78.0	42.3	52.4	n/a	n/a	n/a	n/a
Dense (QR)	8.0	45.4	45.7	43.3	8.0	45.4	45.7	43.3

Appendix

Table 6: LLM relevance observation model ablation with GPT-5.2 and a cross-encoder (ms-marco-MiniLM-L6-v2) showing Recall(R)@100 and NDCG(N)@10 for ReBOL (Top-

B

), with bold indicating the best overall method and underline the best absolute relevance scorer. In general, ReBOL continues to display strong performance though it is relatively weaker with the cross-encoder.

Method	nfcorpus		scifact		robust		covid		news
	R@50	N@10	R@50	N@10	R@50	N@10	R@50	N@10	R@50	N@10
Dense (IQ)	25.6	31.6	87.9	64.9	25.7	40.5	5.6	51.8	33.8	38.2
PW (IQ)	25.6	37.2	87.9	70.3	25.7	57.2	5.6	70.6	33.8	47.4
LW-one-call (IQ)	25.6	35.7	87.9	72.1	25.7	52.2	5.6	70.3	33.8	46.7
LW-window (IQ)	25.6	37.1	87.9	72.8	25.7	55.7	5.6	75.1	33.8	49.1
Dense (QR)	28.0	33.7	92.9	70.3	28.0	44.2	5.0	45.4	36.8	43.3

Appendix

Table 7: Ablation study with

k=50

and 50 observations for ReBOL (Top

B

)

Method	nfcorpus		scifact		robust		covid		news
	R@100	N@10	R@100	N@10	R@100	N@10	R@100	N@10	R@100	N@10
Dense (IQ)	30.8	31.6	92.8	64.9	32.7	40.5	9.5	51.8	42.3	38.2
PW (IQ)	32.3	38.3	95.2	69.9	38.0	61.0	11.6	72.0	46.7	44.8
LW-one-call (IQ)	30.7	33.6	93.1	69.2	33.3	48.7	10.1	72.8	42.3	41.4
LW-window (IQ)	32.3	37.3	95.2	76.0	35.8	58.5	10.4	81.5	44.6	48.3
Dense (QR)	33.3	34.7	95.8	71.0	35.0	44.4	8.3	46.3	46.1	42.2

Appendix

Table 8: Ablation study with

k=200

and 200 observations for ReBOL (Top

B

)

Information Retrieval

Information Retrieval studies how to find, rank, and organize relevant information in large collections of data.

See all 471 papers

A Reproducibility Study of LLM-Based Query Reformulation
Apr 30, 2026Amin Bigdeli, Radin Hamidi Rad, Hai Son Le +4LLM Evaluation LLM Prompting
University of Waterloo Waterloo, Ontario, Canada · Mila – Quebec AI Institute Montreal, Quebec, Canada · Toronto Metropolitan University Toronto, Ontario, Canada +2
Document Optimization for Black-Box Retrieval via Reinforcement Learning
Apr 6, 2026Omri Uzan, Ron Polonsky, Douwe Kiela +1RL for IR Large Language Model-Guided Optimization
Stanford University · ContextualAI
Optimizing RAG Rerankers with LLM Feedback via Reinforcement Learning
Apr 2, 2026Yuhang Wu, Xiangqing Shen, Fanfan Wang +4Retrieval-Augmented Generation Reinforcement Learning
School of Computer Science and Engineering, Nanjing University of Science and Technology, China · School of Intelligence Science and Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China

Apr 30, 2026J/K move · Enter open · S save

A Reproducibility Study of LLM-Based Query Reformulation

Amin Bigdeli, Radin Hamidi Rad, Hai Son Le, Mert Incesu+3

University of Waterloo Waterloo, Ontario, Canada · Mila – Quebec AI Institute Montreal, Quebec, Canada · Toronto Metropolitan University Toronto, Ontario, Canada+2

LLM Evaluation LLM Prompting IR Evaluation

Open paper AskPDF arXiv

Large Language Models (LLMs) are now widely used for query reformulation and expansion in Information Retrieval, with many studies reporting substantial effectiveness gains. However, these results are typically obtained under heterogeneous experimental conditions, making it difficult to assess which findings are reproducible and which depend on specific implementation choices. In this work, we present a systematic reproducibility and comparative study of ten representative LLM-based query reformulation methods under a unified and strictly controlled experimental framework. We evaluate methods across two architectural LLM families at two parameter scales, three retrieval paradigms (lexical, learned sparse, and dense), and nine benchmark datasets spanning TREC Deep Learning and BEIR. Our results show that reformulation gains are strongly conditioned on the retrieval paradigm, that improvements observed under lexical retrieval do not consistently transfer to neural retrievers, and that larger LLMs do not uniformly yield better downstream performance. These findings clarify the stability and limits of reported gains in prior work. To enable transparent replication and ongoing comparison, we release all prompts, configurations, evaluation scripts, and run files through QueryGym, an open-source reformulation toolkit with a public leaderboard.\footnote{https://leaderboard.querygym.com}

Abstract

Information Retrieval

Explore similar work

A Reproducibility Study of LLM-Based Query Reformulation

Document Optimization for Black-Box Retrieval via Reinforcement Learning

Optimizing RAG Rerankers with LLM Feedback via Reinforcement Learning