Generative retrieval trains one sequence model to read a query and spell out the identifier of the relevant document, one token at a time. The best-known version, the Differentiable Search Index, gets much of its strength from how those identifiers are built. Documents are grouped by recursive $K$-means over their embeddings, so related documents share an identifier prefix. The model then only has to pick the right branch at each level of this tree. That tree, however, reflects how documents resemble each other. The retrieval error that matters most is different: a query worded in the "wrong" vocabulary (lay terms against a technical corpus, a paraphrase against the literal text) sends the decoder down the wrong branch at the very first token. Beam search, which keeps only a few partial identifiers alive at each step, rarely recovers from a wrong first token. Vocabulary mismatch therefore shows up in generative retrieval as early branching errors in a tree that was never built with queries in mind.
We propose building the top levels of the identifier tree from a query-confusability graph rather than from document similarity. Two documents get a heavy edge when realistic queries written for one of them, especially queries that share few words with it, also pull up the other under standard retrievers. The top of the tree is then chosen to keep heavily confusable documents on the same side, which defers the hard decision to deep levels where the model has document-specific tokens to work with. The lower levels are still built by fast $K$-means on document embeddings. The construction is a hybrid hierarchical clustering scheme. A cheap partitional pass compresses the corpus into small groups, a graph-based partition decides the top of the tree, and ordinary clustering fills in the bottom. The core claim is testable. Most of the gain from semantic identifiers on mismatched queries is decided at the first one or two tokens, and a tree that cuts less confusability mass at the top will raise first-token accuracy and Hits@1. The improvement should be concentrated on queries that share few words with their target document.
Why this is the right place to intervene
Three pieces of prior work motivate the proposal. Transformer Memory as a Differentiable Search Index showed that hierarchical semantic IDs matter a great deal: 48.5% Hits@1 on NQ10K against 22.1% for a dual encoder, and 40.4% on NQ320K with an 11-billion-parameter model against 24.3%. Its tree, though, is plain recursive $K$-means on static document embeddings, with no notion of which documents queries fail to separate. WikiQA quantifies the mismatch regime: 20.3% of correct answer sentences share no content word with the question. Such queries are exactly the ones for which a document-side tree offers no lexical foothold at the first branch.
The theory of hierarchical clustering supplies the key structural insight. Bisect and Conquer studies the Moseley-Wang objective, a score that rewards a tree for keeping similar pairs together until late splits. It shows that the top split dominates this objective, and obtains a 0.4246 approximation by solving the top split as a balanced "keep similar items together" bisection and finishing with average linkage. Hierarchical Clustering: A 0.585 Revenue Approximation pushes this further. It shows that a single good top bisection captures at least half of an optimal tree's value, even with random splits below it.
We borrow the intuition, not the guarantee. If the top split carries most of the value, then its similarity graph deserves the most care. In generative retrieval, the top split is also where decoding errors are unrecoverable. Those random lower splits are useless for telling individual documents apart, so we replace them with embedding-based clustering, which that paper's limitation invites. We make no claim to inherit the 0.585 bound at the scale of 320K documents. Our partitioner is a scalable heuristic.
Several approaches differ from ours in where they apply query information. Understanding Differential Search Index for Text Retrieval adds filtered pseudo-queries and distillation from a ranked list. Multiview Identifiers Enhanced Generative Retrieval uses pseudo-queries as one kind of identifier. Both use query-side signals to train the decoder or to add views, never to decide the shape of the identifier tree. Learning to Tokenize for Generative Retrieval learns identifier tokens through document reconstruction, with balanced reassignment of documents to tokens. Its objective is to reconstruct the document, not to avoid query confusions. SEATER builds balanced trees over fixed item embeddings for recommendation. GLEN abandons trees for keyword identifiers and resolves collisions using the decoder's scores. Our proposal changes only the tree, which makes it compatible with the training improvements of these methods.
Core Mechanism
For each document $i$ we generate $m$ pseudo-queries, short queries a model predicts users might type for that document. We keep only those a dense retriever maps back to $i$, following the filtering of DSI-QG-Multi. Each kept query is weighted to favor low word overlap with $i$. For each such query $q$, we run BM25 and a dense retriever and record which other documents enter their top-$k$. The confusability weight is
$$ w_{ij} = \sum_{q \in Q_i} \alpha(q, i)\,\big[\mathbb{1}(j \in \mathrm{Top}_k^{\mathrm{BM25}}(q)) + \mathbb{1}(j \in \mathrm{Top}_k^{\mathrm{dense}}(q))\big], $$
where $Q_i$ is the set of kept pseudo-queries for document $i$, and $\alpha(q,i) = 1 - \mathrm{overlap}(q,i)$ is one minus the fraction of the query's content words that appear in $i$. The graph has at most $N m k$ nonzero edges, so it is sparse.
The graph is at document level, but partitioning it directly is costly. We therefore first compress the corpus into a few thousand micro-clusters with $K$-means on document embeddings, in the spirit of the partition-then-merge cascade of A Unified Framework for Model-based Clustering. We then sum edge weights between micro-clusters. For the top $L$ levels (we expect $L$ of one or two), we recursively split the micro-cluster graph into $b$ balanced parts. Each split maximizes the total weight kept within parts, which is the multi-way analogue of the balanced bisection above. At the top level this is small enough for a low-rank semidefinite relaxation of that bisection problem. Below level $L$, each branch is subdivided by recursive $K$-means on document embeddings, exactly as in DSI, so fine-grained purity at the leaves is unchanged.
The resulting identifiers have the same length and branching factor as DSI's, so they drop into any existing generative retriever. We will also report the fraction of confusability mass cut at each level. This is an inexpensive diagnostic that we predict tracks first-token accuracy.
Research Program
We will build three things. The first is the graph and tree construction pipeline. The second is a fixed generative retriever: T5-base, trained identically for every identifier scheme on the same pseudo-query data, because pseudo-queries alone produce large gains and must not be confounded with tree shape. The third is a per-level error analysis. The error analysis records, for each test query, the first level at which the gold identifier falls out of the beam. We then split test queries into overlap quantiles by the fraction of query content words present in the gold document. Our hypothesis predicts gains concentrated at level one and in the lowest-overlap quantile, with little change for high-overlap queries.
Baselines
The naive reference point is BM25 over the same corpus. BM25 is the "do nothing about mismatch" system, and BEIR shows it is hard to beat out of domain. Next to it we run BM25 with docT5query document expansion. BEIR reports that expansion beats plain BM25 on 11 of 18 datasets, which makes it the strongest cheap lexical fix. Both run with default parameters on identical passages.
The primary competitor is DSI with semantic identifiers from recursive $K$-means (Transformer Memory as a Differentiable Search Index). It reports 40.4% Hits@1 on NQ320K at 11B parameters, but we cannot afford that scale. We therefore re-run it at T5-base with the same filtered pseudo-query training as our system. The identifier tree is then the only difference between the two, and beating it means a statistically significant Hits@1 gain at matched model size, beam width, and training steps.
We also compare against DSI-QG-Multi (Understanding Differential Search Index for Text Retrieval), which reports 0.6711 Hits@1 on MS MARCO 100k. Its ranked-list distillation is orthogonal to tree shape, so we test our tree both with and without it. For learned identifiers we include GenRet (Learning to Tokenize for Generative Retrieval); for NQ320K the file gives only a 14% relative Recall@1 gain on unseen queries, and no reported absolute number found on Lacuna for GenRet. For context on full-scale lexical identifiers we report GLEN's 20.1 MRR@10 on full MS MARCO against 17.4 for NCI (GLEN), and MINDER's Hits@5 of 65.8 on NQ (MINDER). These are reference points, not matched comparisons. A dense dual encoder with an approximate nearest-neighbor index, trained on the same pseudo-queries, is also run because it is the practical default.
Two ablations isolate the key ingredient. The first uses our exact partitioner on a document-similarity graph (cosine k-nearest-neighbors on document embeddings) instead of the confusability graph, which separates "better graph" from "better algorithm." The second runs recursive $K$-means on the mean pseudo-query embedding of each document, which tests whether putting documents in query space is enough without pairwise confusion signals. We further vary the depth $L$ at which graph partitioning hands off to $K$-means, and remove the low-overlap weighting by setting $\alpha = 1$.
Why not just…?
Why not just cluster documents by their pseudo-query embeddings with ordinary $K$-means? This is the most serious threat. If it matches our tree, the contribution shrinks to "build the tree in query space." Our argument is that confusability is a pairwise property of retriever failures. Two documents can have distant embeddings yet both be returned for the same lay query, and averaged query embeddings blur exactly those cases. The second ablation settles the question directly. If it closes most of the gap on the low-overlap quantile, we will report that result as the finding rather than defend the graph.
Why not just widen the beam so early mistakes are recovered? A wider beam trades latency for recall. GenRet already reports top-100 latency of 0.16s against 0.32s for DSI, and MINDER is 1.2x slower than SEAL, so decoding cost is a live constraint. We will sweep beam width for both trees and plot Hits@1 against latency. Our claim holds only if our tree dominates the whole curve, not just at one beam setting.
Why not just use BM25 with document expansion, or a dense retriever, and skip generative identifiers entirely? For many deployments this is the right answer, and BEIR shows how robust BM25 is. Our question is narrower. We ask whether the known advantage of hierarchical identifiers (48.5% vs 22.1% on NQ10K in the DSI paper) can be extended to mismatched queries. We therefore report these systems in the same table and on the same overlap quantiles, so a reader can see whether generative retrieval with our tree earns its cost in the mismatch regime.
Why not just learn the identifiers end to end, as GenRet does? Learned tokens optimize document reconstruction, and nothing in that objective targets query confusions. They are also harder to train, since they require progressive multi-stage training. Our tree could even initialize such learning. We compare against GenRet directly and also test GenRet initialized from our top levels.
Proposed Experiments
The main benchmark is NQ320K, reporting Hits@1, Hits@10, and first-token accuracy. We add the MS MARCO 100k subset used by DSI-QG-Multi (Hits@1, MRR@10) and TREC DL19 (NDCG@10, where DSI-QG-Multi reports 0.7920 and TCT-ColBERT 0.7977). As a zero-shot check, we build trees on a few BEIR corpora with pseudo-queries only and no labeled queries, since the confusability graph needs no human labels. WikiQA's questions serve as a diagnostic for zero-overlap queries against Wikipedia sentences.
Four checks decide the outcome. First, at matched model and beam settings, our tree should raise first-token accuracy on NQ320K, with the gain in Hits@1 concentrated in the lowest-overlap quantile. If the gain is uniform across quantiles, the mismatch explanation is wrong even if the tree helps. Second, across all tree variants, including ablations and different depths $L$, the fraction of confusability mass cut at level one should predict Hits@1 better than standard clustering quality measures of the tree. Third, the same-partitioner-on-document-graph ablation should underperform, showing the signal comes from the queries and not from balanced graph partitioning. Fourth, the advantage should survive the beam-width sweep and the addition of ranked-list distillation. Failing any of the first three would falsify the core claim.
References
- Transformer Memory as a Differentiable Search Index
- WikiQA: A Challenge Dataset for Open-Domain Question Answering
- Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
- Hierarchical Clustering: A 0.585 Revenue Approximation
- Understanding Differential Search Index for Text Retrieval
- Multiview Identifiers Enhanced Generative Retrieval
- Learning to Tokenize for Generative Retrieval
- Generative Retrieval with Semantic Tree-Structured Identifiers and Contrastive Learning
- GLEN: Generative Retrieval via Lexical Index Learning
- A Unified Framework for Model-based Clustering
- BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models