Sense-Partitioned Inverted Indexes: Allocating Facets by Ambiguity, Not Frequency

Search systems first pull a short list of candidates from millions of documents and only then apply an expensive model to rank them. Anything missed in that first step is lost for good. Two cheap first-step tools dominate. Keyword indexes such as BM25 miss documents that use different words for the same idea. Single-vector neural retrievers compress each word or passage into one point, so an ambiguous word like "bank" settles at a compromise between its meanings. Token-level neural indexes, which store one contextual vector for every word occurrence, avoid both failures, but their indexes can be up to 200x larger than standard ones (ESPN). We propose a middle option. Each vocabulary term gets a small set of "facet" vectors, roughly its senses, learned from contextual embeddings. Every word occurrence in the corpus is then stored as just a (term, facet) pair, so the index stays close to inverted-index size while posting lists are split by meaning.

The question that makes this a research problem rather than an engineering exercise is how to share a fixed facet budget across a Zipfian vocabulary. The frequency-aware embedding literature gives frequent items more capacity and squeezes rare ones (Adaptive Input Representations). Polysemy is a different property. A frequent word can have a single meaning, and a rare word can have several. We claim that, at a fixed index size, giving facets to terms according to how much their contextual embeddings actually spread out, weighted by how much each term matters for retrieval, raises first-stage recall more than giving them out by frequency. We further claim that the gain concentrates on queries containing ambiguous terms.

Core Claim

Building the index has three steps. First, run a contextual encoder over the corpus. Second, for each term $w$, cluster its occurrence embeddings into $K_w$ centroids. Third, store each occurrence as the ID of its nearest centroid. Let $D_w(K)$ be the average loss in max-similarity score when an occurrence of $w$ is replaced by its nearest of $K$ centroids. Let $a_w$ be a retrieval-importance weight, defined as the share of query-to-relevant-document token matches on training queries that land on occurrences of $w$. We choose the allocation by solving

$$\min_{\{K_w\}} \sum_w a_w\, D_w(K_w) \quad \text{subject to} \quad \sum_w K_w \le B,\; K_w \ge 1,$$

where $B$ is the total number of facet vectors. The solver is greedy: each additional centroid goes to the term with the largest weighted marginal drop $a_w\,(D_w(K_w) - D_w(K_w+1))$. This greedy rule is optimal whenever each $D_w$ shows diminishing returns, which is the classical result for this kind of marginal allocation.

Frequency affects $D_w$ only indirectly, through how many occurrences are being clustered. Ambiguity enters directly. A frequent but single-sense term ends up with $K_w=1$. A mid-frequency term with several meanings gets several facets. The allocation tells us which of the two is happening, and that addresses an open tension in the file. Adaptive Input shows that shrinking rare items acts as regularization, while Word2Box finds that rare words benefit from more geometric capacity. Neither paper says which effect governs retrieval indexes.

At query time the query is encoded contextually, which is a single cheap forward pass. Each query token searches the $B$ facet centroids with approximate nearest-neighbor search. The top facets point to (term, facet) posting lists, and documents are scored by a sum over query tokens of the best matching facet. When a query token's facet is not found in a document, we fill in a similarity bound, borrowing the missing-similarity imputation of XTR. Because query tokens can reach facets of other terms, synonyms are matched without any extra mechanism. Because "bank" has separate river and finance postings, a query about river erosion does not fill its candidate pool with finance documents. The second effect is the one InteractComp shows breaks search agents: they guess one sense and reach 13.73% accuracy, against 71.50% when the context is disambiguated.

Relation to Prior Work

Three lines of work motivate the design. Frequency-aware allocation, including Adaptive Input, the compression survey of Experimental Analysis of Large-scale Learnable Vector Storage Compression, and MPD dimension selection, varies the size of one vector per entity according to frequency. We vary the number of vectors per term, and we set it by measured dispersion rather than frequency. Multi-facet embeddings such as PolyDW show that splitting an entity into $K$ facets helps a great deal: Pinterest link-prediction AUC rises from 0.703 to 0.919. PolyDW uses the same $K$ for every node, has never been used as a retrieval index, and its uniform $K$ is exactly the ablation we run. Probing work (Putting Words in Context) shows that contextual models keep a strong static-identity component, with a cosine of 0.84 to the static embedding at layer 1. This suggests contextual token vectors cluster tightly around a few per-term modes, which is the premise that makes per-term codebooks plausible. Measuring how much each term's vectors spread is our first experiment.

The candidate-generation literature supplies both the method pieces and the constraints. XTR changes how a token-level model is trained so that the retrieved tokens alone can score documents, but it still stores one 128-dimensional vector per token. ESPN reduces the memory such an index needs by streaming it from SSD, but leaves the index the same size. We shrink the index itself, replacing stored vectors with small facet IDs. Single global codebooks for compressing token vectors are common practice. What we add is a per-term codebook whose size is chosen per term, together with an inverted index keyed on (term, facet). The negative result from Improving Candidate Generation for Low-resource Cross-lingual Entity Linking also constrains us: heavy contextual encoders overfit in low-data regimes. For that reason the facets are derived from an existing pretrained encoder and are not learned end to end.

Research Program

The first stage is a measurement study. Using the encoder of an existing token-level retriever, we compute the distortion curves $D_w(K)$ for the MS MARCO vocabulary and ask three things. How do curve shapes relate to frequency? How do they relate to an external count of word senses? Do these curves stay stable when the corpus is split in half? The split-half check plays the same role as the split-corpus invariance used in MPD.

The second stage builds the index. We implement greedy allocation, per-term clustering, and posting lists keyed by facet, with each occurrence stored as a term ID plus a 1-byte facet ID. Facet search runs over the $B$ centroids with a standard approximate nearest-neighbor library.

The third stage settles the tension identified above. We plot the allocated $K_w$ against frequency and check whether tail terms receive more facets than a frequency rule would give them. If they do, the "overcrowding" account wins over the "overfitting" account for retrieval indexes.

The fourth stage tests whether better facets can be learned. A light fine-tuning step adjusts the centroids under a contrastive retrieval loss while keeping the allocation fixed, and we measure whether this gains anything over pure clustering.

Baselines

The naive reference points are BM25 and a single-vector dense retriever. On MS MARCO, CoRT reports BM25 at 85.7% Recall@1000. Our index adds a neural encoder over BM25, so it must clearly exceed that number to justify the extra cost.

The strongest cheap competitor is the hybrid of BM25 and a dense retriever. CoRT interleaves BM25 with a dual encoder trained on BM25's false positives and reports 94.9% Recall@1000 on MS MARCO. A BERT re-ranker saturates at 64 candidates with this pool, against 256 with BM25 alone. This is the baseline to beat on the cost–recall trade-off, since its index is a BM25 index plus one vector per passage. We will train our own CoRT-style dual encoder on the same MS MARCO training data and give it the same tuning budget. We will report Recall@100 and Recall@1000 at matched index bytes and matched latency. Beating it means higher Recall@100 at no more than twice its index size, or equal recall with a clear gain on the ambiguous-query slice.

The strongest quality reference is full token-level retrieval in the ColBERT/XTR style, using the same encoder our facets are derived from. XTR reports +2.8 nDCG@10 on BEIR over earlier multi-vector baselines, and CoRT reports ColBERT at 36.0 MRR@10 with 458 ms latency. We found no reported result on Lacuna for ColBERT or XTR Recall@1000 on MS MARCO. We will therefore measure it ourselves with the same encoder. Here we do not expect to win on raw recall. Success means keeping at least 90% of its Recall@100 while using an index an order of magnitude smaller.

Document expansion is the other strong cheap option. IDST reports NDCG@10 of 0.764 on TREC 2019 passages, and BEIR finds that docT5query beats BM25 on 11 of 18 datasets. We will run docT5query-style expansion over the same corpus with a BM25 index.

The ablations that isolate the key ingredient all hold $B$ and the encoder fixed and change only the allocation rule. The first gives every term the same $K$, as in PolyDW. The second sets $K_w$ by frequency tier, mimicking Adaptive Input. The third sets $K_w$ from dispersion alone, without the importance weight $a_w$. A fourth ablation uses a single global codebook with no per-term structure.

Why not just…?

Why not just run BM25 plus a dense retriever and take the union? This is the most serious threat. CoRT's 94.9% Recall@1000 leaves little headroom at depth 1000. We therefore center the evaluation on Recall@50 and Recall@100, where the pool fed to the re-ranker is decided, and on a slice of queries containing ambiguous terms. On that slice both components of the hybrid collapse a word to its dominant sense, for different reasons. If the hybrid matches us on that slice, the polysemy argument fails, and we will say so.

Why not just allocate facets by frequency, which is simpler and correlates with polysemy anyway? It might work nearly as well, because frequent words do tend to be more ambiguous. The frequency-tier ablation at equal $B$ is the decisive test. Our claim requires dispersion-based allocation to win on the ambiguous slice, and the measurement study to show substantial variation in $K_w$ among terms of the same frequency. If neither holds, the contribution reduces to "frequency-tiered facet indexes," which is still a useful but smaller result.

Why not just compress a full token-level index with a global codebook, or stream it from SSD as ESPN does? ESPN keeps the index size and moves it to disk, while a global codebook spends centroids on whatever regions of embedding space are densest. The global-codebook ablation tests whether per-term structure matters. Per-term codebooks also yield exact inverted postings, which a global codebook does not. We will compare at equal bytes per occurrence.

Why not just expand documents with generated queries? IDST observed that expansion hurt Average Precision and Recall@100 on passages while raising NDCG@10. Expansion also cannot help when the query itself is ambiguous. We include docT5query as a direct baseline and report Recall@100 to check whether that trade-off reappears.

Proposed Experiments

The main benchmarks are MS MARCO passage retrieval (Recall@50, Recall@100, Recall@1000, and MRR@10 after a fixed cross-encoder re-ranks the top 100) and zero-shot BEIR (nDCG@10 and Recall@100). For every system we report index bytes and query latency. To build the ambiguous slice, we select MS MARCO and BEIR queries containing terms with several senses in an external lexicon. We use the external lexicon rather than our own dispersion estimate so the slice is not defined circularly. We also run the 210 InteractComp questions through a fixed retrieve-then-answer pipeline as a small stress test of single-shot sense coverage.

The decisive checks are as follows. The first plots recall against index size for the allocation ablations at several values of $B$; the dispersion-plus-importance rule should dominate uniform and frequency-tier allocation, with the largest margin on the ambiguous slice. The second plots $K_w$ against frequency to settle the regularization-versus-expressivity question. The third measures Recall@100 against the CoRT-style hybrid at matched bytes. The fourth checks whether facets derived from MS MARCO transfer to BEIR domains or need to be re-clustered per corpus, which is cheap because clustering requires no training.

The result that would sink the proposal is frequency-tier allocation matching ours at every budget, together with the hybrid matching us on the ambiguous slice. In that case the honest conclusion is that ambiguity in first-stage retrieval is already handled well enough by cheap means.