Store Only What the Hybrid Cannot Derive: Grammar-Style Compaction for Multi-Vector Retrieval

Search systems that give each document several embedding vectors find long documents better than systems that squeeze each document into one vector. The cost is a much larger index. Most of these extra vectors are probably wasted, because the single document vector, or plain keyword matching, already finds the document for whatever those vectors cover. Grammar compaction faced the same problem decades ago. A rule extracted from a treebank is redundant if the remaining rules can already produce it, and a large multi-word fragment is worth keeping only if it occurs more often than its smaller parts predict. We propose to apply that principle to retrieval indexes. A document's phrase-level vector stays in the index only when the cheaper hybrid of keyword matching plus one document vector fails to retrieve the document for queries about that phrase. Everything else is treated as "derivable" and discarded.

The opportunity is concrete. Sparse, Dense, and Attentional Representations for Text Retrieval proves that a fixed-length vector loses its ability to separate a relevant long document from competitors as the document grows. Their fix, ME-BERT, stores the first $m$ token embeddings of every document, which inflates the index 3x to 8x and spends the same budget on every document, whether it needs it or not. The bet of this proposal is that a compacted index can match ME-HYBRID's accuracy at a fraction of its size. The index would hold one document vector, one keyword index, and a small, unevenly distributed set of "exception" vectors for the phrases the hybrid would otherwise miss. We expect those phrases to be mostly rare entities and non-compositional expressions.

Core Claim

The claim is that index entries should be chosen by a corpus-level redundancy test borrowed from grammar compaction, not by position, by a local classifier, or by surface collocation statistics. Two results from grammar reduction supply the method and its constraint. The first is Compacting the Penn Treebank Grammar. It removes a rule when the remaining grammar can parse its right-hand side. Done purely symbolically, this cut 93% of rules but wrecked precision and recall. With probability thresholds it achieved a 58% reduction with no loss. We take both halves of that result: derivability is the right test, but it must be graded and probabilistic, not all-or-nothing. The second is Parsimonious Data-Oriented Parsing. Its Push-n-Pull procedure compares a fragment's observed frequency with the frequency a simpler baseline grammar predicts. It keeps over-represented fragments and pushes the rest down to general rules, cutting 1.4 million rules to 11,411 with no accuracy loss on OVIS. In our setting the "baseline grammar" is the cheap hybrid scorer. The "observed" quantity is how well a constituent's own vector retrieves its document. A constituent is kept only where the two disagree.

Formally, let $s_B(q,d)=\alpha\,\mathrm{BM25}(q,d)+\beta\, \mathbf{q}^\top \mathbf{v}_d$ be the baseline hybrid score, where $\mathbf{v}_d$ is the single document vector. For a candidate constituent $c$ of document $d$, let $Q_c$ be a few pseudo-queries generated from $c$, and let $N(q)$ be the hard negatives for query $q$. The baseline's margin is $\mu_B(q,d)=s_B(q,d)-\max_{d'\in N(q)} s_B(q,d')$. The gain from storing $c$ is

$$\Delta(c)=\sum_{q\in Q_c}\Big[\max\big(\mu_B(q,d),\ \mu_c(q,d)\big)-\mu_B(q,d)\Big]_{\text{clipped at }\tau},$$

Here $\mu_c$ is the margin when $d$ may also be scored by $\mathbf{q}^\top\mathbf{v}_c$, and $\tau$ caps credit once a query is already safely won. The index keeps the set $S$ of constituents that maximizes $\sum_{c\in S}\Delta(c)-\lambda|S|$ under a global budget. This is a description-length tradeoff in the spirit of The Generalized Smallest Grammar Problem: each stored vector has a cost and has to pay for itself in retrieval margin. Because the budget is global rather than per document, long or entity-dense documents receive many vectors and short generic ones receive none. That allocation is exactly what Luan et al.'s length–capacity analysis says is needed.

Relation to Prior Work

Two hybrid-retrieval papers motivate the selection rule from opposite sides. On Complementarity Objectives for Hybrid Retrieval trains the dense model to be orthogonal to the sparse one, so that it stops duplicating easy keyword matches. Salient Phrase Aware Dense Retrieval instead trains a dense model to imitate BM25 on salient phrases, doubling the MS MARCO index from 26 GB to 52 GB. These look contradictory. Our rule reconciles them at the index level rather than in training. Phrase information is stored only when it is not already covered by keyword matching or the document vector. That is complementarity enforced by selection, and it keeps salient phrases without paying for all of them.

Three papers constrain the design. Hybrid Inverted Index Is a Robust Accelerator for Dense Retrieval already selects salient terms per document, so it is the natural heuristic competitor. Bridging the Training-Inference Gap for Dense Phrase Retrieval shows that discarding over 70% of phrase-index tokens can improve accuracy, which tells us pruning need not hurt. Its filter, however, judges each token in isolation; it does not ask whether the token is redundant given what else is stored. Real-Time Open-Domain Question Answering with Dense-Sparse Phrase Index still needed 1.2 TB after quantization. That result warns that compression alone does not fix uncontrolled enumeration.

We deliberately do not target the phrase-QA indexes themselves as the main testbed. DENSPI already factors phrase scores into start and end token vectors, so there is no explicit phrase dictionary to compact. Multi-vector document retrieval is where an explicit set of stored units exists and can be shrunk.

Hybrid First-stage Retrieval Models for Biomedical Literature supplies the synthetic-query machinery: it generated 103 million PubMed query–document pairs. It also shows how badly pure dense models fail on entity matching, with a BioASQ batch MAP of 0.1173 for the dense encoder against 0.2718 for BM25.

Research Program

We will build three components. The first is a candidate generator that proposes units within each document. Our default is syntactic constituents from an off-the-shelf parser, with fixed token windows and sentences as alternatives. The span encoder can start from SpanBERT (facebookresearch/SpanBERT). The second is a pseudo-query generator, trained as in Ma et al., that produces a few queries per candidate unit. The third is the compaction pass. It computes $\Delta(c)$ against the baseline hybrid and then greedily keeps units in order of gain per byte until the budget is spent. As in Push-n-Pull, it re-estimates gains after each round, because storing one constituent can make a sibling redundant.

At query time, a document's score is the maximum of the baseline hybrid score and its best stored-constituent score. Both live in one approximate-nearest-neighbour index alongside the BM25 postings.

The analysis asks three questions. Which units survive compaction: are they disproportionately rare entities and multi-word names, as P-DOP's retained subtrees such as "New York Stock Exchange" suggest? How does the number of stored vectors per document scale with document length, and is it close to linear as Luan et al.'s bound predicts? Finally, by analogy with Krotov et al.'s 93% versus 58% contrast, does a hard derivability threshold over-prune compared with the clipped, graded gain?

Baselines

The naive reference point is BM25 linearly interpolated with a single-vector BERT dual encoder. This is exactly our baseline scorer $s_B$ with no stored constituents. It sets the floor and the minimum index size, and any exception vector must improve on it.

The strongest directly comparable competitor is ME-HYBRID from Sparse, Dense, and Attentional Representations for Text Retrieval. It reports MRR@10 of 0.343 on MS MARCO Passage, against 0.302 for the single-vector dual encoder and 0.334 for ME-BERT, at a 3x to 8x index cost. We will retrain it with the same encoder checkpoint, training data, and negatives as our system. We will sweep $m$ so that each of its configurations is matched by ours at equal stored bytes. Beating it means equal or higher MRR@10 at no more than half the index bytes, or clearly higher MRR@10 at equal bytes. On MS MARCO Document we found no reported result on Lacuna for ME-HYBRID's exact number; the file only says gains there were "even more pronounced". We will therefore establish that number ourselves.

The strongest accuracy reference on MS MARCO Passage is the complementarity-trained hybrid of On Complementarity Objectives for Hybrid Retrieval, which reports MRR@10 of 38.63. It is a training-side method and orthogonal to ours. The fair test is therefore to apply our compaction on top of its encoder and check whether exception vectors still add accuracy per byte.

The heuristic selection competitor keeps the same per-corpus budget but chooses units by salience instead of derivability. Units are ranked either by maximum term IDF, in the style of the salient-term lists of Hybrid Inverted Index Is a Robust Accelerator for Dense Retrieval, or by a learned per-unit keep/drop classifier in the style of Kim et al.

Two ablations isolate the key ingredients. The first ablation swaps candidate units: constituents versus fixed windows versus sentences, with the derivability criterion held fixed. This tells us whether the grammar's units matter or only the compaction principle does. The second ablation swaps the selection criterion: graded clipped gain versus a hard derivable/not-derivable threshold versus gain computed against the dense vector alone, ignoring BM25. The last comparison tests whether complementarity with the sparse side is what makes the selection work.

Why not just…?

Why not just give every document the first $m$ token vectors and quantize harder? Quantization and selection are complementary, and we will quantize both systems identically. The question is whether uniform allocation wastes vectors. Zhang et al. show that compression alone costs recall: IVF-OPQ reaches 0.796 Recall@100 on MS MARCO against 0.927 for flat search. DENSPI still occupied 1.2 TB after int8 and pointer tricks. The equal-bytes sweep against ME-HYBRID settles this directly.

Why not just expand documents with the generated pseudo-queries and index them in BM25? This is a serious threat, because it uses the same synthetic queries with no extra vectors at all. We include it as a baseline with identical pseudo-queries. If keyword expansion matches our accuracy, the pseudo-queries are doing the work, not the stored vectors. If our system wins mainly on paraphrased queries, the dense exceptions are earning their place. We will report that result whichever way it falls.

Why not just pick phrases by collocation statistics such as pointwise mutual information? Push-n-Pull looks superficially like a collocation test. The difference is the baseline. Collocation compares a phrase with its words' frequencies, whereas our gain compares retrieval with the phrase against retrieval through the existing hybrid. A frequent collocation that BM25 already matches exactly should be dropped. A PMI-ranked selection at equal budget will be run as part of the heuristic baseline. Our explicit prediction is that it wastes budget on exactly those keyword-covered phrases.

Why not just train a better single vector with complementarity objectives? Lee et al.'s objective improves the dense side but cannot escape Luan et al.'s length bound, which concerns a fixed dimension, not training. The MS MARCO Document comparison, stratified by document length, will show whether the gap to our system widens with length, as the bound predicts.

Proposed Experiments

The main experiment plots accuracy against index size on MS MARCO Passage (MRR@10, Recall@100) and MS MARCO Document. Every system appears as a curve over its budget parameter. The decisive check is whether our curve dominates ME-HYBRID's and the heuristic-selection curve in the regime of 1.5x to 3x the single-vector index size.

Zero-shot transfer to BEIR and to Natural Questions (Recall@100, where Lee et al. report 90.13%) tests a separate question. It asks whether pseudo-query-driven selection overfits to the generator's query style. We will also report SPAR's BEIR comparison for context, since it beat BM25 and Contriever on 11 of 14 datasets.

BioASQ 8 MAP is the stress test for entity-heavy text. There Ma et al. report 0.4056 for HybridRerank. If compaction behaves as hypothesized, retained units there should be dominated by gene and chemical names.

Two diagnostics determine whether the grammar story is real. The first is the length-scaling plot of stored vectors per document. The second is the constituent-versus-window ablation at matched budgets. If windows match constituents, the contribution reduces to compaction-by-derivability without syntax. We would report the result that way.