Search systems fail most often when a query and a relevant document describe the same thing in different words. Named entities make this worse in both directions. Sometimes the entity string is the only thing linking a query to the right document, so rewriting it away is fatal. Sometimes the query's name for the entity (slang, a colloquial label, a rare alias) never appears in the corpus, so keeping it verbatim guarantees a miss. The right choice depends on the query. It also changes as users, domains and vocabulary drift, and today it is fixed once by a hand-written rule. We propose to learn this choice online. For each incoming query, a small policy picks one of a handful of cheap ways to treat its entity mentions: keep them, delete them, replace them with a type label, expand them with aliases, or send the query to a lexical or a dense retriever. It then observes only whether the chosen option retrieved something relevant.
The learning problem is a contextual bandit, meaning an online learner that picks one action per round and sees the outcome of that action alone. It has an unusual property that makes a specific family of algorithms the right tool. For most queries, some treatment retrieves a relevant document. So the best policy's cumulative failure count, written $L^*$, is small compared with the number of queries $T$. First-order or "small-loss" bandit algorithms are designed for exactly this regime: their regret, the extra failures relative to the best policy in hindsight, grows with $\sqrt{L^*}$ rather than $\sqrt{T}$. Entity masking enters a second time, and this is the part we think is most useful. The policy's own input is delexicalized, so what it learns about "queries shaped like [DRUG] dosage for [CONDITION]" transfers to entities it has never seen.
Core Claim
We claim that per-query choice of entity treatment, learned online with a log-loss first-order bandit over a delexicalized query representation, will beat three alternatives under domain shift: the best single fixed treatment, a square-loss bandit, and an offline-trained router. We further claim that the gain is concentrated where the small-loss theory predicts, on streams where the best policy's failure rate $L^*/T$ is low.
The claim is falsifiable at three points. If the per-query oracle is barely better than the best fixed treatment, adaptivity has nothing to buy. If SquareCB matches the first-order method, the theory is irrelevant here. If a lexicalized policy input does as well as the delexicalized one, the masking ingredient is decorative.
Relation to Prior Work
Three papers show that the treatment decision matters and is unresolved. On the Importance of Delexicalization for Fact Verification replaces entities with overlap-aware type tags (such as organization-c1) and WordNet super-sense tags. This lifts FEVER→FNC accuracy from 48.86% to 53.59% and FNC→FEVER from 41.16% to 51.77%. The same super-sense tags hurt on other domain pairs. That paper chooses one abstraction level per experiment by hand; we choose per query, online, and for retrieval rather than classification.
Covering Cracks in Content Moderation masks 46 seed drug terms so that its JEDIS classifier learns context. It finds over 100 jargon terms where a keyword filter finds 22. Its masking is static, and its "gray area" failures, where context alone cannot settle intent, are exactly the queries where keeping the entity should win.
Ontology-based Solution for Building an Intelligent Searching System on Traffic Law Documents maps colloquial terms to formal concepts through a hand-built ontology and reaches 75% success. We replace the manual mapping with a learned choice among cheap automatic treatments.
On the retrieval side, other papers motivate the problem or constrain the design. WikiQA shows that 20.3% of correct answer sentences share no content word with the question, which is why "always keep verbatim" cannot be enough. BEIR shows that dense retrievers fine-tuned in one domain often lose to BM25 zero-shot. This is the constraint that argues against a purely offline-trained router and for online adaptation. RaFe trains a query rewriter from reranker feedback, and InteR alternates LLM expansion with retrieval. Both generate open-ended rewrites, carry no regret guarantee, and in InteR's case pay multiple LLM calls per query. We deliberately restrict to a small, discrete, cheap action set, which is what makes a regret guarantee available at all.
The method comes from the bandit literature. Efficient First-Order Contextual Bandits proves that square-loss reductions like SquareCB cannot achieve first-order regret. It introduces FastCB, which uses a log-loss regression oracle and reweighted inverse-gap exploration, where arms predicted to be worse are tried less often and exploration shrinks as estimated losses shrink. It proves
$$\mathbb{E}[\mathrm{Reg}(T)] \le \tilde{O}\left(\sqrt{L^* \cdot A \cdot \mathrm{Reg}_{KL}(T)}\right),$$
where $A$ is the number of actions and $\mathrm{Reg}_{KL}(T)$ is the online log-loss regret of the oracle. Contextual Bandits with Online Neural Regression extends this to wide networks (NeuFastCB) with a $\tilde{O}(\sqrt{K L^*} + K)$ bound that does not depend on network size. Both were evaluated only on classification datasets converted to bandits. We reuse their algorithms unchanged; our contribution is the problem formulation, the delexicalized context, and the empirical test of whether retrieval actually lives in the small-$L^*$ regime.
The same bandit paper also constrains us. It notes that FastCB's constants are worse than SquareCB's when $L^*$ is large, so we expect, and will report, losses on hard streams.
Research Program
Action set. Each round is one query, and the action set has $A = 6$ arms. The arms are BM25 on the verbatim query; BM25 with entity mentions deleted; BM25 with each entity expanded by aliases from a knowledge base or embedding neighbors; a dense retriever on the verbatim query; a dense retriever on the type-masked query; and a fixed hybrid of BM25 and dense scores. Entity spans come from an off-the-shelf tagger. We treat tagger errors as part of the environment rather than hiding them, because that fragility is a documented limitation of delexicalization.
Loss. The loss is binary: 1 if no relevant document appears in the top 10, and 0 otherwise. In simulation, relevance comes from benchmark relevance judgments, standing in for a click or an answer acceptance. A second, noisier setting uses a cross-encoder reranker's judgment, to probe reranker-bias effects of the kind RaFe inherits.
Policy input. The policy sees an overlap-aware delexicalized query: entity spans are replaced by type plus a mention index, and the representation adds cheap statistics for each entity. These include its corpus document frequency, whether it is out of vocabulary for BM25, and its tagger confidence. The document-frequency feature keeps the policy able to recognise "this name does not occur in the index" without memorising the name itself.
Learner. The regression oracle is a small network trained online with log loss to predict each arm's failure probability, plugged into FastCB and NeuFastCB.
Analysis. Alongside the experiments we measure $L^*/T$ for each stream. This locates each benchmark on the axis where the theory predicts first-order methods should win or lose.
Baselines
The naive reference points are the six fixed arms run on every query. The strongest of these, chosen in hindsight on the test stream, is the "best fixed treatment", which is effectively what the delexicalization papers deploy. Beating it by a meaningful margin in top-10 failure rate, on at least the entity-heavy datasets, is the minimum bar. We will also report the per-query oracle, which picks the best arm with hindsight for each query, as a ceiling. The gap between the oracle and the best fixed treatment is the total prize available.
The strongest bandit competitor is SquareCB, the square-loss reduction analysed in Efficient First-Order Contextual Bandits. We also include epsilon-greedy. All bandit methods share the same network, the same context features, the same query order and the same hyperparameter budget, tuned on a held-out prefix stream from a different domain. FastCB beats SquareCB in that paper, most clearly on datasets with $L^* \le 0.2$, but the file gives no per-dataset numbers. We count a win as lower cumulative failures on low-$L^*$ streams, with SquareCB allowed to win on high-$L^*$ streams as the theory predicts.
The price of partial feedback is isolated by a full-information learner. This learner runs all six arms on every query and observes every loss, so it costs six times the retrieval compute. The bandit should close most of the gap to it.
The strongest external systems are LLM-based expansion methods. InteR reports 50.0 MAP on TREC DL'19, against 41.8 for HyDE and 30.1 for BM25. We do not expect a six-arm cheap policy to match InteR's absolute quality on DL'19. The comparison we care about is failure rate per unit of compute, with InteR's number cited and, where affordable, reproduced on our subsets. The offline alternative is a router trained with supervision on MS MARCO to predict the best arm, then frozen for the target streams.
The key ablation swaps the delexicalized policy input for the raw lexicalized query embedding, keeping everything else fixed. For the BEIR target datasets themselves, we found no reported result on Lacuna for per-dataset BM25 or dense scores, so our own runs of those systems serve as the reference.
Why not just…?
Why not just pick the best fixed treatment on a development set? If one treatment dominates, this is the right answer and our method is overhead. The delexicalization evidence says it does not dominate across domains, since super-sense tags help on one transfer pair and hurt on another. But that evidence comes from classification, not retrieval. The oracle-versus-best-fixed gap, measured first on every dataset, settles this directly. If the gap is under a couple of points of failure rate, we will report that and stop.
Why not just train a router offline and freeze it? This is a real threat when training and test domains are similar. BEIR's finding that MS MARCO-trained models degrade zero-shot on TREC-COVID, SciFact and BioASQ is the evidence that it breaks under shift. We test it directly with streams that switch domains partway through. We also run the fair hybrid, the offline router used as a warm start for the bandit. If warm-starting captures most of the gain, the honest conclusion is that online learning matters mainly after shifts.
Why not just use SquareCB, which is simpler? The first-order paper proves SquareCB cannot adapt to small $L^*$ and reports FastCB's largest gains exactly there. It also warns that FastCB is worse when losses are high. We therefore stratify results by measured $L^*/T$ rather than averaging them away. A result where SquareCB ties everywhere would falsify the part of our claim that concerns the theory.
Why not just let an LLM rewrite every query? InteR's DL'19 result shows this can be higher quality. But it needs multiple LLM calls per query and degrades beyond two iterations. RaFe reports 78 hours of LLM feedback generation against 0.67 hours for its small-model signal on 30,000 instances. We position our policy as a cheap first stage and report quality at matched latency. One LLM-rewrite arm can be added to the action set with a cost penalty, which lets the bandit itself decide when the expensive option is worth paying for.
Proposed Experiments
Streams. We build query streams from BEIR datasets with many entities or strong vocabulary gaps: TREC-COVID, SciFact, NQ, HotpotQA, DBPedia-Entity, FEVER and Climate-FEVER. We add WikiQA, recast as retrieving answer sentences, because of its documented zero-overlap fraction. Each stream is run in two orders: shuffled, and domain-blocked, where the domain switches abruptly. The primary metric is cumulative top-10 failures, reported as regret against the best fixed policy and against the per-query oracle. Secondary metrics are nDCG@10 and retrieval calls per query.
Decisive checks. We run four checks, in order, and each can falsify part of the claim. First, the oracle-versus-best-fixed gap for each dataset, which decides whether the problem exists at all. Second, the measured $L^*/T$ for each stream, plotted against the FastCB-minus-SquareCB difference in failures; the theory predicts a negative correlation, with FastCB winning at low $L^*/T$ and possibly losing at high. Third, the delexicalized-versus-lexicalized input ablation, evaluated specifically on queries whose entities never appeared earlier in the stream, where masking should matter most. Fourth, the reranker-feedback variant, which tells us whether noisy automatic feedback, the realistic deployment signal, inflates $L^*$ enough to erase the first-order advantage.
A slang-heavy slice built from the Reddit and Silk Road drug corpora of Covering Cracks in Content Moderation serves as a qualitative stress test of the keep-versus-mask trade-off. These corpora were built for classification, so no retrieval number exists there to compare against.
References
- On the Importance of Delexicalization for Fact Verification
- Covering Cracks in Content Moderation: Delexicalized Distant Supervision for Illicit Drug Jargon Detection
- Ontology-Based Solution for Building an Intelligent Searching System on Traffic Law Documents
- WikiQA: A Challenge Dataset for Open-Domain Question Answering
- BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models
- RaFe: Ranking Feedback Improves Query Rewriting for RAG
- Synergistic Interplay between Search and Large Language Models for Information Retrieval
- Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
- Contextual Bandits with Online Neural Regression