Polarity-Marked Sparse Indexes for Negation-Aware Candidate Generation

Search systems first pull a few hundred candidates out of millions of documents with a fast index, then sort them with a slow, accurate model. Anything the fast stage misses is lost for good. The fast stages in use today score a document by adding up weights for words it shares with the query, so "hotel without a pool" and "hotel with a pool, without a gym" look nearly identical to them. On a benchmark built for exactly this case, these first stages rank negated pairs correctly only 2–10% of the time, below the 25% expected from random ranking (NevIR). The slow reranker could often fix the ordering, but only if the right document reaches it.

We propose to change what a word weight is attached to. Learned sparse retrievers such as SPLADE and DeepCT give each vocabulary word one positive, context-dependent weight. We would instead let the encoder write each word under one of two index keys: a plain key ("pool") or a negated key ("¬pool"), chosen from the word's context. Queries may also place a negative weight on a plain key, which lets a query penalize documents that assert a concept it excludes. Scoring remains an additive dot product over sparse keys, so the method runs on an ordinary inverted index at first-stage cost. Because the negated key is predicted and expanded rather than produced by rules, "lacks a pool" on the document side and "without pool" on the query side can land on the same key.

Core Claim

A sparse first stage whose index keys are words in polarity scope, rather than words alone, can recover most of the candidate-recall loss on negated and exclusionary queries. It can do so without the collapse in general retrieval quality that hurts dense models fine-tuned on negation. The scoring function is

$$s(q,d)=\sum_{t\in V\cup \bar V} w_q(t)\,w_d(t),\qquad w_d(t)\ge 0,\; w_q(t)\in\mathbb{R},$$

where $V$ is the ordinary word-piece vocabulary, $\bar V$ is a copy of it whose keys mean "this concept, under negation or exclusion," $w_d$ are the document weights stored in posting lists, and $w_q$ are the query weights, which may be negative.

The result is still a bag, but a bag of scoped keys. "X" and "not X" no longer share a key. We do not claim to solve word order in general. Directional roles ("from Florida" vs. "to Florida") are tested only as a stretch extension of the same key-marking idea.

Why This Gap, and Not a Neighbor

The literature in the file motivates the problem from three sides.

The first concerns how words are weighted. Classic frequency weighting down-weights exactly the short, common words that flip meaning. A Simple but Tough-to-Beat Baseline for Sentence Embeddings and Going Beyond Sentence Embeddings note that corpus-level inverse frequency penalizes negations. DeepCT and SPLADE learn context-aware weights, but a high weight on "not" only matches documents that contain "not" somewhere. A scalar weight carries no information about which concept is negated.

The second concerns lexical overlap. SemAntoNeg finds general-purpose sentence encoders below chance on "not [antonym]" paraphrases (all-MiniLM-L6-v2 at 1.9% against 33.3% random). PAWS shows high-overlap word swaps drive models from over 90% to 33–40%.

The third concerns order. Multi-vector late interaction keeps per-token vectors, but it sums independent best matches, a commutative operation. ColBERT reaches only 19.7% on NevIR and about 25% after fine-tuning (NevIR).

Other work constrains the design. Reproducing NevIR shows that fine-tuning multi-qa-mpnet on NevIR lifts it to 50.1% but drops MS MARCO MRR@10 from 0.20 to 0.06. Models tuned on NevIR also show "almost no improvement" on ExcluIR. Any method that learns negation must therefore protect general matching and be tested for transfer. The same paper also reports an early-stopped model at 48.9% on NevIR that keeps MRR@10 at 0.20. So the "cost of learning" trap is not absolute, and that model is a competitor we must beat rather than a straw man.

Work that routes around the first stage, namely reranker-guided graph search, the bi-metric framework and ADACUR, still depends on a cheap proxy whose neighborhoods are built from word overlap. We read this as complementary. A polarity-aware proxy should help those graphs too, but we do not build on them here.

Two papers supply the method. SPLADE gives the masked-language-model head that projects each token onto vocabulary weights, the log-saturation of those weights, and the regularizer that keeps them sparse. The idea of complementary training in CoRT, which trains against the negatives a lexical retriever prefers, motivates mining the negated twin as the hard negative.

Research Program

We would build the model on a SPLADE encoder with a second output head of the same vocabulary size, producing weights over $\bar V$. A small per-token gate decides, for each token, how its expansion mass splits between $V$ and $\bar V$. On queries a third, signed head may assign negative weight to keys in $V$. Document weights stay non-negative so that posting lists and index compression are unchanged.

Negative query terms break the upper-bound pruning that fast index traversal relies on. We would therefore first score with the non-negative query terms and then subtract the negative contributions over the retrieved pool. We will report how much latency this adds.

Training has two streams.

The plain channel is trained on MS MARCO exactly as in SPLADE. It is also anchored to a reproduced SPLADE checkpoint by distilling its plain-vocabulary weights. This anchoring is our answer to the trap documented in Reproducing NevIR: the negation signal has no path to rewrite general term matching.

The marked channel and the signed query head are trained on minimal pairs, each with the twin as the hard negative. The pairs come from three sources:

  • the NevIR training split, whose pairs are built from CondaQA;
  • negation and exclusion edits of MS MARCO passages generated by an LLM and filtered by a cross-encoder;
  • the matching queries for those edits.

A sparsity penalty applies to $\bar V$, so that for passages with no negation the marked channel stays almost empty and the index barely grows. We will report index-size overhead and the fraction of postings in $\bar V$ as first-class results.

The analysis then asks two questions. Where does the gate fire? We would compare its firings against crowd-annotated negation cues in CondaQA, including affixal negation such as "unhappy" and implicit negation such as "lacks". Does the marked key for a concept form one cluster across different surface phrasings of its negation? The stretch extension replaces the binary polarity marker with a handful of role markers (source, destination, agent, patient). It is tested on queries derived from PAWS word swaps.

Baselines

The naive reference point is BM25 on the same corpora. On NevIR, the file reports TF-IDF below 2% and bi-encoders and sparse models in the 5–10% range (NevIR). On MS MARCO, the SPLADE paper reports BM25 at MRR@10 0.184 (SPLADE).

The strongest sparse competitor is SPLADE itself, which reports MRR@10 0.322 and Recall@1000 0.955 on MS MARCO. It is the right comparison because it is the system we modify: it already learns context-aware weights and vocabulary expansion, and it runs on the same index. We will retrain it from the same initialization with the same MS MARCO data, the same regularization sweep and the same GPU budget. We will also give it the same negation minimal pairs as extra hard negatives, so that only the key change differs.

The strongest dense competitor is the early-stopped multi-qa-mpnet. It is reported at 48.9% NevIR pairwise accuracy while keeping MRR@10 0.20 (Reproducing NevIR). We will reproduce it with its published stopping rule. We also report fine-tuned ColBERT (about 25% on NevIR) as the multi-vector reference.

As an upper reference for the reranking stage, we use MonoT5-3B, reported at 50.6% pairwise accuracy on NevIR, and RankGPT with o3-mini, reported at 77.3%. These are not first-stage competitors. They are what we put downstream to measure end-to-end gains.

Beating the baselines means three things together:

  1. NevIR pairwise accuracy above 48.9% at the first stage.
  2. MS MARCO MRR@10 within 0.01 of our reproduced SPLADE, and Recall@1000 within one point of it.
  3. Clearly lower rates of the wrong twin being retrieved in the haystack setting described below.

The improvement must also appear on ExcluIR. For that benchmark the file contains only the qualitative report of "almost no improvement" from NevIR-tuned models and no exact number. Our bar there is therefore a measurable gain over our own reproduced SPLADE and early-stopped baselines.

Three ablations isolate the key ingredient:

  • SPLADE trained on the identical negation data with no $\bar V$ channel. This separates "new keys" from "more data."
  • The full model without signed query weights.
  • The full model with $\bar V$ restricted to tokens literally present in the text, with no expansion into the marked space. This isolates the learned mapping across different phrasings of a negation.

Why not just…?

Why not just retrieve a deeper pool and let a strong reranker sort it out? The reranker can only fix what it receives. Tsukuba at TREC 2023 found that GPT-4 reranking does not make up for a weak first stage. Reranker-guided search documents a correct target buried at rank 2,812. CoRT shows cross-encoder gains flatten as the pool grows while cost grows linearly. Our experiment settles this directly: we plot end-to-end accuracy against pool depth for SPLADE plus MonoT5 versus our model plus MonoT5. If SPLADE at depth 1000 matches our model at depth 100, the method is merely a cost saving, and we will report it as such.

Why not just tag negation scope with rules and index tagged tokens, or use phrase and proximity matching? This is the most serious threat, so it is run as a baseline. We apply a rule-based scope tagger (negation cue plus a following window, or a dependency-scope heuristic) to both queries and documents and index the tagged tokens with BM25 and with SPLADE. Rules cannot map "without a pool" in a query onto "has no swimming facilities" in a document. Proximity matching rewards "not" near "guilty" but misses scope across a clause. Our "no expansion" ablation is close to this baseline with learned tagging. If rules match the full model on NevIR and ExcluIR, the contribution reduces to the signed query weights, and we would narrow the claim to that.

Why not just fine-tune a dense bi-encoder on negation with early stopping? The 48.9% / 0.20 result shows this is viable. But 0.20 MRR@10 is far below SPLADE's 0.322, and NevIR-tuned models barely transfer to ExcluIR (Reproducing NevIR). A single vector also has to fold the concept and its polarity into one point; Blacoe et al. describe the broader problem that commutative composition erases structure. Our comparison holds MS MARCO quality fixed and asks which approach is more negation-aware and transfers further. If a dense model trained on our minimal-pair data matches us at equal MS MARCO quality, the sparse design loses its justification.

Why not just use late interaction with fine-tuning? Summing independent token matches leaves the bag intact, and the reported ColBERT numbers stay at or below chance on NevIR (NevIR). We include it for completeness rather than as a likely winner.

Proposed Experiments and Decisive Checks

The first evaluation is NevIR pairwise accuracy at the first stage, scoring both twins under both queries with each retriever alone. The second guards against the cost of learning: MS MARCO dev MRR@10 and Recall@1000, plus TREC Deep Learning 2019 and 2020 nDCG@10. ExcluIR tests transfer to exclusionary phrasing. SemAntoNeg, scored by sparse dot product, serves as a diagnostic.

NevIR measures isolated pairs, not retrieval from a large corpus. We therefore build a haystack: all NevIR documents are inserted into the 8.8M MS MARCO passages. For each query we measure three things: whether the correct document appears in the top 100 and top 1000; how often its negated twin outranks it; and accuracy after MonoT5-3B reranking of the top 100. No reported result exists on Lacuna for this setting, so all systems will be run fresh.

The decisive check is the joint one, read off a single plot of NevIR accuracy against MS MARCO MRR@10 that traces each system's trade-off. The method succeeds only if it beats the early-stopped dense model on negation while staying at SPLADE's general quality. It must also beat SPLADE trained on the same negation pairs. That comparison shows the gain comes from the scoped keys and not from the training data.

The secondary checks are three. The marked channel should stay sparse on passages without negation, keeping the index-size increase in single-digit percent. Latency overhead from the negative query terms should be small next to reranking cost. Haystack gains should survive reranking, so that end-to-end accuracy rises rather than just first-stage recall.