Search queries often say what the user does not want: "sci-fi films from 2019 besides Endgame," "treatments that did not require surgery." Retrieval systems handle these badly. Systems that compress a query into one vector rank the excluded item near the top, because its name is the strongest word in the query. The usual remedy for a different problem makes this worse. When the user's words differ from the document's words (the vocabulary mismatch or lexical gap), the standard fix is query expansion: add synonyms and related terms to the query. Expansion cannot tell which clause a word belongs to, so expanding "without violence" adds "guns" and "blood" as positive matching signals. Plain string filtering has the opposite flaw. It removes documents that say "Endgame" but keeps those that call it "the Avengers finale."
We propose to borrow a principle from database theory. There, unrestricted negation makes query answering intractable or even undecidable. Restricting every negated condition to the records already picked out by a positive condition, called guarded negation, makes it tractable again. In retrieval, this means three things. The query is split into its positive and negated parts. Only the positive part is allowed to retrieve and to be expanded. The negated part is checked document by document inside that positive candidate set, by an entailment model that asks "does this passage assert the excluded thing?" rather than "is this passage similar to it?" Because each part is matched in the right place, the lexical gap can be bridged on both parts without one contaminating the other. Queries without negation pass through unchanged.
Core Claim
Negation and vocabulary mismatch interact. Most failures of negation-aware retrieval come from this interaction, not from either problem alone. Expansion helps the positive clause and hurts the negated one. Geometric or string-based negation handles the negated clause but discards relevant material. We claim that separating polarity first and evaluating negation in a guarded way fixes both problems at once. Concretely, the system expands only the positive part, retrieves a candidate set, and then applies a small entailment check of the negated concept to each candidate. We expect this to outperform both unconstrained expansion and end-to-end negation fine-tuning on negation benchmarks. Because non-negated queries are untouched, it also cannot pay the general-retrieval cost that fine-tuning pays.
For a query $q$ split into a positive part $q^+$ and a negated concept $c^-$, the guarded score of a document $d$ is
$$s(d) = s^+(d \mid \tilde q^+) - \lambda \, P_{\text{ent}}(d \Rightarrow c^-), \quad d \in G_K(\tilde q^+),$$
where $\tilde q^+$ is the expanded positive part and $G_K(\tilde q^+)$ is the top-$K$ "guard set" retrieved by it. The term $s^+$ is the first-stage retrieval score, $P_{\text{ent}}$ is the entailment model's probability that the passage asserts $c^-$, and $\lambda$ sets how strongly the negated concept is penalized. Documents outside the guard set are never scored against the negation. This mirrors the requirement in Queries with Guarded Negation that a negated subformula's variables must co-occur in a positive atom. As in that work, the payoff is bounded cost. The negated part is checked against $K$ documents rather than being proven absent across the whole corpus.
Position Relative to Prior Work
The database-theory results motivate the design. They show what goes wrong without a guard. Under open-world semantics, negation pushes probabilistic query evaluation to $\text{NP}^{\text{PP}}$ (Open World Probabilistic Databases (Extended Abstract)). Path negation over ontologies becomes undecidable (XPath for DL Ontologies). The guarded fragment GNFO recovers $\text{coNP}$ or $\text{PTime}$ data complexity (Queries with Guarded Negation). That work also reports, qualitatively, that real SQL workloads mostly use negation in guarded form. We do not claim a complexity theorem for neural retrieval. We use the guardedness discipline as a design constraint, and we test the hypothesis that natural-language negated queries, like SQL, are mostly guarded.
The open-world/closed-world distinction from the same literature becomes a concrete design choice. A three-way entailment model can say a passage asserts $c^-$, denies it, or is silent about it. Treating "silent" as passing the negation is closed-world reasoning inside the guard set. Requiring an explicit denial is open-world reasoning. We test both, because exclusion queries and sentential-negation queries plausibly want different semantics.
Five lines of IR work bear on the design, each in a different role. Orthogonal Negation in Vector Spaces for Modelling Word-Meanings and Document Retrieval subtracts the negated term's direction from the query vector. This removed up to 76% of the negated term's semantic neighbours but cut retrieval of the positive term by about 25%. That paper constrains our design. Any method that modifies the query representation itself risks this collateral damage, which is why we leave the positive representation untouched.
The diagnostic papers supply the evidence for the gap. NevIR: Negation in Neural Information Retrieval built contrastive document pairs that differ by a negation and found bi-encoders at 5–10% pairwise accuracy. ExcluIR: Exclusionary Neural Information Retrieval showed the excluded entity's words dominate single-vector queries, with off-the-shelf models at 53–58% Right Rank. Reproducing NevIR found that fine-tuning on negation drops MS MARCO MRR@10 from 0.20 to 0.06, and that it does not transfer to ExcluIR. None of these papers varies vocabulary mismatch on either clause, and none separates query polarity before retrieval. Those are the two things we add.
A Comprehensive Taxonomy of Negation for NLP and Neural Retrievers supplies a labelling scheme. It sorts negation into types: sentential, exclusion, affixal, implicit verbs, and antonyms. It also shows ExcluIR is 81% exclusion. We use this taxonomy to stratify results and to train the polarity splitter.
Bridging Knowledge Gaps in Neural Entailment via Symbolic Models supplies the method precedent. It decomposed hypotheses into sub-facts and routed each to an entailment model, reaching 77.9% versus 74.3% on SciTail. That gain came from bridging a lexical gap, which is why we pick entailment rather than similarity for the negated part. That work did classification only. We move the decomposition into ranking.
Finally, the query-rewriting work supplies the expansion component. Query Expansion by Prompting Large Language Models and RaFe both expand or rewrite the whole query with no notion of which clause a term serves. Our change is to apply the same expansion to $q^+$ only.
Research Program
The system has three pieces. First, a small polarity splitter, a fine-tuned seq2seq model of a few hundred million parameters. It maps a query to $(q^+, c^-, \text{type})$, or to "no negation." It is trained on synthetic splits labelled with the taxonomy's categories, and audited on held-out human-written NevIR and ExcluIR queries.
Second, expansion is applied to $q^+$ alone, using chain-of-thought expansion with BM25 and, separately, a dense retriever. A light alias expansion is also applied to $c^-$, but only as additional hypotheses for the entailment checker, never as retrieval terms.
Third, a guarded checker scores each document in $G_K$ against $c^-$ and its aliases. We use an off-the-shelf three-way entailment model, optionally adapted on taxonomy-balanced data. Training touches only the splitter and the checker. The first-stage retriever is frozen, so MS MARCO behaviour on queries routed as "no negation" is unchanged by construction. The only residual risk is the splitter falsely firing on such queries, which we measure directly.
The analysis question is when guarding is enough. Guarding fails in two cases. One is when the negated concept defines the information need: "documents not about X" with no positive part. The other is when the excluded item is absent from $G_K$ because the positive part is too vague. We will measure how often natural queries fall into these unguarded cases, which is the retrieval analogue of the TPC-H guardedness audit.
Baselines
The naive reference point is the first-stage retriever on the raw query, both BM25 and a dense bi-encoder, with no negation handling. On NevIR, TF-IDF scores below 2% and bi-encoders 5–10% pairwise accuracy (NevIR). On ExcluIR, off-the-shelf models reach 53–58% Right Rank (ExcluIR). Beating this baseline is necessary but not informative.
The strongest lexical-gap baseline is whole-query chain-of-thought expansion feeding BM25, which reports 90.61 Recall@1K on MS MARCO against BM25's 87.82 (Query Expansion by Prompting Large Language Models). We run it with the same generator and prompt as our positive-only expansion. Any difference between the two then isolates polarity separation. Beating it means higher pairwise accuracy and Right Rank at equal or better Recall@1K on non-negated queries.
The strongest fine-tuning baseline is the early-stopped multi-qa-mpnet of Reproducing NevIR. It reports 48.9% NevIR pairwise accuracy while keeping MS MARCO MRR@10 at 0.20. We also add a version trained with MS MARCO examples mixed into the negation data, under the same number of training steps as our checker. To beat it, we must exceed 48.9% on NevIR with MRR@10 not below 0.20, and also improve on ExcluIR, where that model barely moved.
The strongest accuracy baselines are rerankers applied to the same top-$K$ candidates. MonoT5-3B reports 50.6% NevIR pairwise accuracy (NevIR). RankGPT with o3-mini reports 77.3% (Reproducing NevIR). For ExcluIR, the reported generative-retrieval reference is SEAL fine-tuned, which gains 18% Right Rank (ExcluIR). We do not expect a small checker to beat o3-mini outright. The comparison that matters is at matched inference cost: same $K$, and a reranker of comparable size to our checker. We also report accuracy per thousand queries per GPU-second, with the o3-mini ceiling shown as a reference.
Two ablations isolate the key ingredients. The first replaces entailment with similarity: score $c^-$ by maximum similarity in the dense space, or by Widdows-style orthogonal projection of the query vector. The second removes the guard: apply the negation penalty as a global query modification rather than within $G_K$.
Why not just…?
Why not just retrieve and apply a Boolean NOT filter? String filtering fails exactly where the lexical gap bites. It keeps documents that name the excluded concept by an alias, as Widdows' "internet" versus "broadband" examples show (Orthogonal Negation). It also cannot read sentential negation inside documents, which is the whole of NevIR. Our alias-perturbed benchmark (below) makes this measurable: filtering should be competitive when excluded entities appear verbatim and collapse when they appear as aliases.
Why not just fine-tune the bi-encoder, but mix in general retrieval data to avoid forgetting? This is a real threat, and the reproduction study did not try data mixing, only early stopping. We include it as a baseline at matched training budget. Our expectation that it falls short rests on the reported lack of transfer from NevIR to ExcluIR (Reproducing NevIR). That pattern suggests single-vector training learns dataset-specific shortcuts. If the mixed model matches us on all three benchmarks and on the alias variants, our contribution reduces to the efficiency and interpretability of an explicit split, and we will say so.
Why not just rerank the top-$K$ with a cross-encoder or LLM? This is the most serious alternative, because our guard set is a top-$K$ list too. The difference is in which documents enter that list and what the second stage computes. A reranker over a raw-query or whole-query-expanded list inherits a candidate set already crowded with the excluded entity's documents and missing the alias-phrased positives. We separate these effects with a 2×2 design: first stage (raw versus positive-only expansion) crossed with second stage (MonoT5 versus our checker). If MonoT5 on our guard set equals our checker, the finding is "polarity-separated retrieval plus any good reranker," which is still new, and we will report it that way.
Why not just expand the whole query with an LLM? We predict whole-query expansion helps on non-negated queries and hurts on negated ones, by injecting the negated concept's neighbours as positive terms. The matched comparison against positive-only expansion is precisely the experiment that confirms or refutes this prediction.
Proposed Experiments
We evaluate on NevIR (pairwise accuracy), ExcluIR (Right Rank, plus Recall@100 of the positive document), and MS MARCO dev (MRR@10, Recall@1K). The taxonomy's Free and Controlled Generation sets are used for per-type breakdowns.
The decisive new resource is a lexical-gap stress version of ExcluIR and NevIR. Using an LLM with human verification on a sample, we rewrite documents along two independent axes. One axis paraphrases the excluded entity or negated predicate into an alias or jargon. The other paraphrases the positive constraint. This gives four conditions. There is no reported result found on Lacuna for any system under such alias perturbation. We also build an ExcluIR open-corpus setting that retrieves from the full HotpotQA document pool rather than only the pair, so that guard-set recall matters.
The central prediction is a crossover. Whole-query expansion should beat raw retrieval only when the gap is on the positive part. Similarity-based negation and Widdows-style projection should degrade when the gap is on the negated part. The guarded entailment system should be the only method that holds across all four cells.
Three further checks are decisive. The first is the splitter's false-positive rate on MS MARCO queries, with MRR@10 required to stay at the unmodified retriever's value within noise. The second is guard-set recall: the fraction of queries whose relevant document lies in $G_K$. This bounds what any guarded method can achieve and quantifies the unguarded failure mode. The third compares closed-world against open-world treatment of the checker's "neutral" verdict, broken down by negation type. We expect closed-world to win on exclusion and open-world to win on sentential negation. A failure on the first check, or a guard-set recall that leaves most of the gain to the second stage, would show that the guarding idea, not just its implementation, is wrong.
References
- Queries with Guarded Negation
- Open World Probabilistic Databases (Extended Abstract)
- XPath for DL Ontologies
- Orthogonal Negation in Vector Spaces for Modelling Word-Meanings and Document Retrieval
- NevIR: Negation in Neural Information Retrieval
- ExcluIR: Exclusionary Neural Information Retrieval
- Reproducing NevIR: Negation in Neural Information Retrieval
- A Comprehensive Taxonomy of Negation for NLP and Neural Retrievers
- Bridging Knowledge Gaps in Neural Entailment via Symbolic Models
- Query Expansion by Prompting Large Language Models
- RaFe: Ranking Feedback Improves Query Rewriting for RAG