Generative Retrieval: The Model as the Index

Retrieval by a sequence-to-sequence model that writes the identifier of a relevant document, so that the index is the model's parameters. The differentiable search index of Tay et al. (2022) is set out with its atomic, naive and semantic identifiers; for semantic identifiers from hierarchical k-means it is proved that prefixes are clusters, that small leaves make them prefix-free, and how long they must be. Constrained beam search over a prefix trie is proved to return only real documents, an example shows it can miss the best one, and best-first search is proved exact. Generated queries for indexing (DSI-QG, NCI), GENRE's entity names and the language-model-as-knowledge-base idea follow, and, as of November 2026, the published results on adding documents (DSI++) and on scaling to 8.8 million passages. A small DSI trained on Cranfield with t5-small and no Cranfield query, three seeds per design, reached a median nDCG@10 of 0.233 with semantic identifiers, 0.118 with atomic and 0.087 with naive ones, against 0.368 for BM25 and 0.382 for a dense retriever, and forgot almost all it had memorized of 1,300 abstracts (indexing accuracy 0.565 to 0.025) when 100 new ones were indexed. Five worked problems cover identifiers by hand, beam against best-first search, the cost of atomic identifiers, length-normalized scores and query 185.

Cranfield query 185 asks for experimental studies on panel flutter. An inverted index answers it by reading the postings of panel and flutter and adding up weights; a dense retriever answers it by comparing one vector for the query with 1,400 stored vectors, one per abstract. Suppose instead that a language model has been trained until, given the query, it simply writes down the number of a relevant abstract, digit by digit, from what its parameters hold, with no postings and no stored vectors. Can a network's parameters serve as the index, and what does that cost? On the evidence below, at the scale of this collection and a 60-million-parameter model, they can serve, poorly: trained on generated questions about each abstract, the best of three identifier designs reaches an nDCG@10 of 0.233 on Cranfield's 225 queries, against 0.368 for BM25 and 0.382 for a pretrained dense retriever, and adding 100 abstracts by further training made an atomic index forget almost all it had memorized of the other 1,300.

Generative retrieval is retrieval in which a sequence-to-sequence model, given a query, generates the identifier of a relevant document, token by token, and a ranking is read from the model's probabilities for the identifiers. The collection is stored in the model by training: indexing a document means teaching the model to map the document's text, or queries about it, to the document's identifier. The system that established the approach for document retrieval is the differentiable search index, DSI, of Tay et al. (2022), in which, in their words, "all information of the corpus is encoded within the parameters of the Transformer language model".

Here is the route. First we state the model and its two training tasks, and set it beside the inverted index and the dense retriever. Then we take the three kinds of identifier in turn, and derive the structure of the semantic ones: why their prefixes are clusters, when they are prefix-free, and how long they must be. Next comes decoding: a prefix trie and beam search, with a proof that constrained beam search returns only real documents, an example showing it can miss the best one, and an exact best-first search with its proof. Then indexing: what DSI found about how to teach the association, the mismatch between documents and queries, and generated queries as the remedy. GENRE and the language-model-as-knowledge-base idea come next as the approach's neighbors. Our experiment trains a small DSI on Cranfield with all three identifiers and compares it with BM25 and the dense retriever of Text Embeddings and Dense Retrieval. Finally we set out what generative retrieval costs and what is known about its failures. The article assumes the bi-encoder of Sentence and Passage Encoders and Dense Passage Retrieval, k-means from the course, and a transformer encoder-decoder; Language Models from Scratch builds the decoder half step by step. The numbers are computed by tools/experiments/knowledge-stores/generative-retrieval.py and its module dsi.py.

From looking up to writing down

The idea in plain words. Every retrieval system in this collection's earlier units keeps two things apart: a store of the documents, in some indexed form, and a procedure that searches the store. An inverted index stores postings and the ranking function walks them; a dense retriever stores one vector per passage and a vector search finds the nearest. A generative retriever stores nothing outside the network. It is trained until, given a document's text, it can write that document's identifier, and given a query, it writes the identifier of a document that answers the query. Retrieval becomes generation, and building the index becomes training.

The formal version. Let the collection be $D = \{d_1, \dots, d_N\}$. Each document $d$ is given an identifier $y_d = (y_{d,1}, \dots, y_{d,L_d})$, a short sequence of tokens from an output vocabulary $V$, distinct documents getting distinct sequences. A sequence-to-sequence model with parameters $\theta$ reads an input text $x$ and defines, one token at a time, a probability for every output sequence:

$$P_\theta(y \mid x) = \prod_{t=1}^{L} P_\theta(y_t \mid y_1, \dots, y_{t-1}, x) .$$

Each factor is a softmax over $V$ computed by the decoder from the encoder's reading of $x$ and the tokens already written. The score of a document for a query $q$ is the log-probability of its identifier,

$$s(q, d) = \log P_\theta(y_d \mid q) = \sum_{t=1}^{L_d} \log P_\theta(y_{d,t} \mid y_{d,<t}, q) ,$$

and retrieval returns the $k$ documents of highest score. This is the scoring rule of GENRE (De Cao et al., 2021, Section 3) and of DSI's string identifiers (Tay et al., 2022, Section 3.2); the atomic identifiers below are the case $L_d = 1$.

Training has two kinds of example, which Tay et al. (2022, Section 1) call indexing and retrieval:

  • an indexing example pairs a representation of document $d$ (in DSI, its first $L$ tokens) with $y_d$;
  • a retrieval example pairs a query $q$ with the identifier of a document relevant to it.

Both are trained with the ordinary sequence-to-sequence loss, the negative log-likelihood of the target with the true previous tokens fed in (teacher forcing). For a set $T$ of input-target pairs,

$$\mathcal{L}(\theta) = -\sum_{(x, d) \in T} \log P_\theta(y_d \mid x) .$$

Tay et al.'s Table 1 sets the three designs side by side, and the comparison can be stated in their terms:

Inverted index with BM25 Dual encoder Differentiable search index
What is stored per document a sparse vector of term weights, as postings a dense vector nothing outside the parameters
Indexing build postings lists encode every document train the model to map $d$ to $y_d$
Retrieval of the top document sparse dot products over postings (approximate) maximum inner product search decode $\arg\max_y P_\theta(y \mid q)$ over valid identifiers

The table hides the point that most of this article is about. In the first two designs, adding a document is a write to a data structure. In the third it is a change to the parameters, which every other document's retrieval depends on.

Example (what "the index is in the parameters" does and does not mean). It is tempting to read the third column as "the model has memorized the collection's text". It has not, and it need not. The training objective only asks the model to emit $y_d$ when it reads something about $d$. The model never has to reproduce a word of the document, and in DSI-QG's variant it never reads the document at all, only queries generated from it. What is stored is an association from inputs to identifiers. The article's experiment measures how well that association is learned (the indexing accuracy) separately from how well it serves new queries.

Identifiers: what the model writes

The model can only write what its output vocabulary can spell, so the first design decision is the identifier. Tay et al. (2022, Section 3.2) tried three, and the later systems described here use one of them or a variant.

Atomic identifiers

Give each document its own new output token. The decoder's output layer, a matrix $W_{\text{tokens}} \in \mathbb{R}^{d_{\text{model}} \times |V|}$ that scores the vocabulary, is extended by one column per document:

$$O = \operatorname{softmax}\bigl([W_{\text{tokens}}; W_{\text{docs}}]^{\top} h_{\text{last}}\bigr), \qquad W_{\text{docs}} \in \mathbb{R}^{d_{\text{model}} \times N},$$

where $h_{\text{last}}$ is the decoder's last hidden state at the first output position (their notation). Retrieval is one decoding step: sort the $N$ document logits. The ranking is exact and complete, every document is scored, and no search is involved. The paper notes that this resembles listwise learning to rank, all documents being considered at once.

The cost is $d_{\text{model}} \cdot N$ new parameters, one embedding per document. For t5-small ($d_{\text{model}} = 512$) on Cranfield's 1,400 abstracts that is 716,800, about 1.2% of the model's 60,506,624. For the 8,841,823 passages of MS MARCO at T5-Base's 768 dimensions it is $8{,}841{,}823 \times 768 = 6{,}790{,}520{,}064$, about 6.8 billion. Pradeep et al. (2023, Table 4) list their T5-Base model with atomic identifiers on that collection at 7.0B parameters, which matches this count added to the base model's 220M. A matrix of one vector per document is also what a dense retriever stores. An atomic generative retriever differs in that its vectors are learned jointly with the network that reads the query, not computed from each document's text by an encoder; it does not escape the storage.

Naive string identifiers

Take an arbitrary unique integer for each document and write it as a decimal string, split into tokens by the model's own tokenizer. Tay et al. call this "ostensibly absurd": the digits carry no information about the document, yet the model must produce them one token at a time. It adds no parameters, and a ranking of $k$ documents needs a search over the space of strings, which they did with beam search.

On Cranfield, t5-small's tokenizer splits the numbers 0 to 1399 into one or two tokens: "1234" becomes ▁12 and 34, and "7" becomes ▁7. Of the 1,400 identifiers, 88 are one token and 1,312 are two. A detail of this collection affects the design. Cranfield's own document numbers are not arbitrary: neighboring abstracts often share a subject (the panel flutter abstracts relevant to query 185 include numbers 856, 857 and 858). Using them would give the naive design some of the structure of the semantic one. Our naive identifiers are therefore a random permutation of 0 to 1399, drawn from each run's seed.

Semantically structured identifiers

The third design makes the identifier describe the document. The aim, in Tay et al.'s words, is that "semantically similar documents share identifier prefixes", so that each decoding step narrows the search to a region of related documents.

The construction (their Algorithm 1). Compute a vector for every document. Cluster the vectors into $k$ groups by k-means and give each document the number of its group, $0$ to $k - 1$, as the first digit. A group of more than $c$ documents is clustered again in the same way, and the result is appended as the next digits. A group of at most $c$ documents is not split: its members get the numbers $0$ to $(\text{size} - 1)$, in arbitrary order, as their last digits. Tay et al. used $k = 10$ and $c = 100$, with vectors from an 8-layer BERT and scikit-learn's k-means. Wang et al. (2022) used $k = c = 30$ in NCI. The first level is the same kind of k-means partition that an inverted file index makes of a vector collection, and the recursion is a top-down hierarchical clustering, close to the bisecting k-means of Hierarchical Clustering with $k$ parts in place of two. We use $k = 10$ and $c = 10$, so that every digit of every identifier is a single token, and the vectors of the dense retriever used throughout this collection. In what follows, labels are written as decimal digits and concatenated, as in Tay et al.'s algorithm, and we take $k \le 10$, so that every cluster number is one digit. With $k > 10$ that reading breaks down: under NCI's $k = 30$ the string 12 could be cluster 12 or cluster 1 followed by 2. NCI avoids this by treating each label as one decoding step, one child of a node of the prefix tree (Wang et al., 2022, Algorithm 2); with that convention the propositions below hold for any $k$, with "digit" read as "label".

The construction defines a tree. Its root is the whole collection. Each internal node is a set of more than $c$ documents, and its children are its nonempty clusters, labelled by their cluster numbers. Each leaf node is a set of at most $c$ documents, whose members are labelled by their positions. A document's identifier is the sequence of labels on the path from the root to its leaf node, followed by its position there. Three properties follow, and the decoding section relies on all of them.

Proposition 1 (prefixes are clusters). Let $\sigma$ be a sequence of digits that labels a path from the root to a node $S_\sigma$ of the tree, internal or leaf. Then the documents whose identifiers begin with $\sigma$ are exactly the documents in $S_\sigma$.

Proof. By induction on the length $\ell$ of $\sigma$. For $\ell = 0$, $\sigma$ is empty, every identifier begins with it, and $S_\sigma$ is the root, the whole collection. Suppose the claim holds for $\sigma$ of length $\ell$, with $S_\sigma$ an internal node, and let $\sigma g$ label its child, the cluster numbered $g$. A document in $S_{\sigma g}$ is in $S_\sigma$, so by the hypothesis its identifier begins with $\sigma$. The algorithm then appends the cluster number of the cluster it falls into at $S_\sigma$, which is $g$, so its identifier begins with $\sigma g$. Conversely, a document whose identifier begins with $\sigma g$ begins with $\sigma$, so it lies in $S_\sigma$, and the digit after $\sigma$ in its identifier is its cluster number at $S_\sigma$ (that position holds a cluster number because $S_\sigma$ is internal), so the cluster is $g$ and the document is in $S_{\sigma g}$. $\square$

Proposition 2 (unique and prefix-free when $k \le 10$ and $c \le 10$). If $k \le 10$ and $c \le 10$, so that every cluster number and every position in a leaf node is a single digit, then distinct documents have distinct identifiers, and no identifier is a proper prefix of another.

Proof. Let $d$ have identifier $\sigma j$, where $\sigma$ labels its leaf node $S_\sigma$ and $j$ is its position. Suppose another document $d'$ has an identifier that begins with $\sigma j$. By Proposition 1, $d'$ is in $S_\sigma$. Since $S_\sigma$ is a leaf, the digit after $\sigma$ in the identifier of $d'$ is its position, a single digit, and the identifier ends there. So that identifier is exactly $\sigma j'$ with $j'$ the position of $d'$, and $j' = j$ forces $d' = d$, because positions in a leaf are distinct. An identifier that begins with $\sigma j$ is therefore $\sigma j$ itself and belongs to $d$. Taking $d' \ne d$ shows that no other identifier equals $\sigma j$ (uniqueness) and none extends it (prefix-freeness). $\square$

The condition matters. With Tay et al.'s $c = 100$, positions run from 0 to 99 and each position's "digits are appended to the existing identifier", so the document at position 7 of a leaf gets $\sigma 7$ and the one at position 70 gets $\sigma 70$: one identifier is a prefix of the other. Uniqueness survives, and an end-of-sequence token after every identifier keeps the two apart in decoding, which is how the trie below treats every design.

Proposition 3 (length). Let $\ell_{\max}$ be the length of the longest identifier.

  1. $\ell_{\max} \ge 1 + \lceil \log_k (N / c) \rceil$ whenever $N > c$.
  2. If every split produces at least two nonempty clusters, the construction ends. If also $c \le 10$ (with $k \le 10$, as above), $\ell_{\max} \le N - c + 1$.

Proof. (1) A tree in which every path has at most $\ell_{\max} - 1$ internal nodes and every internal node at most $k$ children has at most $k^{\ell_{\max} - 1}$ leaf nodes, each holding at most $c$ documents. So $N \le c\,k^{\ell_{\max} - 1}$, that is, $\ell_{\max} - 1 \ge \log_k(N/c)$, and since $\ell_{\max}$ is a whole number, $\ell_{\max} - 1 \ge \lceil \log_k (N/c) \rceil$. (2) If each split yields at least two nonempty clusters, each child of an internal node is a proper subset of it and so has at least one document fewer. Along a path from the root, the sizes of the internal nodes are therefore strictly decreasing whole numbers, all greater than $c$ and at most $N$, so there are at most $N - c$ of them. Every path is finite, so the recursion ends. With $c \le 10$ the identifier has one digit per internal node and one for the position, at most $N - c + 1$ digits. $\square$

Counted in labels (one per internal node and one for the position), the same argument gives at most $N - c + 1$ labels for any $c$. Counted in decimal digits with Tay et al.'s $c = 100$ it does not: a position can take two digits, and with $N = 101$, a first split into groups of 100 and 1, the document at position 50 of the large group gets 050, three digits, while $N - c + 1 = 2$. For $c \ge 2$ the digit count is at most $N - c + \lceil \log_{10} c \rceil$.

The upper bound is weak, and it can be attained only by very unbalanced clusterings; it is there to show that the recursion ends. The condition in (2) is not automatic: a group of more than $c$ documents with identical vectors (exact duplicates) cannot be split by any clustering, and the algorithm as written would recurse forever on it. Our script checks the condition at every split.

Example (Cranfield). With $N = 1{,}400$, $k = 10$ and $c = 10$, part (1) gives $\ell_{\max} \ge 1 + \lceil \log_{10} 140 \rceil = 1 + 3 = 4$, since $10^2 < 140 \le 10^3$. A perfectly balanced tree would make every identifier four digits long. The clustering of seed 0 gives 265 identifiers of three digits, 1,108 of four and 27 of five, a mean of 3.83 digits and a longest of five. k-means does not in general produce clusters of equal size, so some identifiers are shorter and some longer than four.

Decoding inside a trie

A trained model assigns a probability to every sequence of tokens, most of which are not identifiers. Two questions follow: how to make the model produce only valid identifiers, and how to find the $k$ most probable ones without scoring all $N$.

The prefix trie

A prefix tree, or trie, of a set of token sequences has one node per distinct prefix of the sequences, the empty prefix at the root, and an edge labelled $t$ from the node of prefix $p$ to the node of $p\,t$. To mark where an identifier ends, every identifier is followed by the end-of-sequence token, written ⟨/s⟩, so that the sequences stored are $y_d$⟨/s⟩. The node reached by a whole stored sequence is a leaf and records its document. Two facts about the trie are immediate from the construction:

  • the children of the node of a prefix $p$ are exactly the tokens that continue $p$ toward some identifier;
  • every node has at least one leaf below it, since every node lies on some stored sequence.

GENRE stores Wikipedia's titles this way. De Cao et al. (2021, Section 3.1) report that the BART tokenizer's spellings of 6M titles give a trie with 6M leaves and 17M internal nodes, which occupied 600MB on disk. Cranfield's semantic identifiers of seed 0 give a trie of 3,531 nodes; the naive identifiers, 2,802.

Constrained decoding restricts each decoding step to the children of the current node: the probabilities of all other tokens are set to zero. De Cao et al. note a choice of detail: they set the log-probabilities of invalid tokens to $-\infty$ after the softmax, and do not renormalize over the valid ones. A hypothesis's score is then the model's own probability of producing that identifier, $\log P_\theta(y_d \mid q)$, the score $s(q, d)$ defined above. We do the same.

Finding $\arg\max_d s(q, d)$ exactly would mean scoring every identifier. Beam search is the standard approximation. It keeps a set, the beam, of at most $B$ partial sequences, called hypotheses, each with its score so far.

  1. Start with one hypothesis, the empty sequence, with score 0.
  2. Replace every unfinished hypothesis $p$ by its extensions $p\,t$, one for each allowed next token $t$, with score $\text{score}(p) + \log P_\theta(t \mid p, q)$. A hypothesis whose last token is ⟨/s⟩ is finished; it is not extended and keeps its score.
  3. Of all hypotheses now present, finished and unfinished, keep the $B$ with the highest scores.
  4. Stop when every kept hypothesis is finished, and return them in order of score.

Each round adds one token to the unfinished hypotheses, so the number of rounds is at most the length of the longest identifier plus one. Unconstrained beam search allows every token of $V$ at step 2; constrained beam search allows only the children of the hypothesis's trie node. Ties are broken in our implementation by the token sequence, so the procedure is deterministic.

Theorem 1 (constrained beam search returns documents). With a trie of the identifiers of $N$ documents and a beam of $B$, constrained beam search returns exactly $\min(B, N)$ hypotheses, each the full identifier of a document followed by ⟨/s⟩, no two for the same document.

Proof. Every hypothesis is a path in the trie. This holds for the empty hypothesis, which is the root. A hypothesis is only ever extended by a child of its node, so an extension is again the label sequence of a path from the root. A hypothesis is finished only when its last token is ⟨/s⟩, and in the trie ⟨/s⟩ leads only to leaves, so a finished hypothesis is a whole stored sequence $y_d$⟨/s⟩, which belongs to exactly one document.

No document appears twice. At the start the beam has one hypothesis. Extensions of distinct hypotheses are distinct sequences (they differ in their first $\lvert p \rvert$ tokens or in their last), and extensions of one hypothesis by distinct tokens are distinct. Finished hypotheses carried over are not extended, so they are not duplicated. By induction the beam never holds the same sequence twice, and distinct whole sequences belong to distinct documents.

The count. Every unfinished hypothesis is a node with at least one child, so step 2 replaces it by at least one hypothesis, and the pool after step 2 is at least as large as the beam before it. Hence the beam's size never decreases. A discard at step 3 leaves exactly $B$ hypotheses, after which the size stays $B$; so if at the end the beam held fewer than $B$, step 3 never discarded anything, so the beam would contain every extension ever made: every path of the trie would have been followed to its end, and the finished hypotheses would be all $N$ documents. So the final beam holds $B$ hypotheses if $N \ge B$, and all $N$ otherwise. $\square$

Without the constraint none of this holds. An unconstrained decoder may write a sequence that no document has, and Tay et al. say plainly that DSI did not constrain its decoding: "It would be feasible to constrain DSI generation outputs to be valid docids. Although we do not use this technique, the degree to which this might improve performance is a worthwhile question." Later papers measured it. NCI's ablation (Wang et al., 2022, Table 3) removes the constraint and loses 0.21 points of Recall@1 on NQ320k, 65.86 to 65.65. Pradeep et al. (2023, Section 5.2) found that constrained decoding "only provides marginal value and generally is not worth the added complexity" at their scales. The experiment below counts how many of an unconstrained beam's outputs are not identifiers at all on Cranfield.

Beam search is not exact

Theorem 1 says the outputs are valid; it does not say they are the best. A beam discards a prefix as soon as $B$ others score higher, and a prefix that looks poor can lead to the best identifier.

Example (a beam of one misses the best identifier). Take a trie whose root has two children $a$ and $b$, with $P(a) = 3/5$ and $P(b) = 2/5$ for some query. After $a$ the model splits evenly between two identifiers, $P(a_1 \mid a) = P(a_2 \mid a) = 1/2$; after $b$ it is nearly sure, $P(b_1 \mid b) = 9/10$. The identifiers' probabilities are $3/10$ for $a_1$ and for $a_2$, and $9/25 = 0.36$ for $b_1$. A beam of one keeps $a$ at the first step, since $3/5 > 2/5$, and returns an identifier of probability $0.3$; the best, $b_1$ with $0.36$, was discarded with its prefix. A beam of two keeps both prefixes and finds $b_1$. Worked problem 2 runs both searches on this trie and on the exact search below.

Theorem 2 (exact top $k$ by best-first search). Keep a priority queue of hypotheses ordered by score, starting with the empty hypothesis. Repeatedly remove the hypothesis of highest score. If it is finished, output it; otherwise insert all its extensions by trie children. Stop after $k$ outputs. The outputs are the $k$ identifiers of highest probability, in order.

Proof. The key fact is that scores never increase along a path: an extension adds $\log P_\theta(t \mid p, q) \le 0$. So every identifier that extends a hypothesis $p$ has a score at most $\text{score}(p)$.

Consider the moment the search outputs a finished hypothesis $h$, and let $g$ be any identifier not yet output. The trie path of $g$ starts at the root, which was in the queue at the start. Removing an unfinished hypothesis inserts all its children, so at every moment some prefix of $g$ is in the queue: initially the root, and whenever the prefix in the queue is removed, its child on $g$'s path is inserted. (If $g$ itself is the finished hypothesis in the queue, the prefix is $g$.) Let $p$ be that prefix at the moment $h$ is removed. The queue releases its highest score first, so $\text{score}(h) \ge \text{score}(p) \ge \text{score}(g)$. Hence every output scores at least as high as every identifier not yet output, which is the claim. $\square$

The price is that the number of hypotheses expanded is not bounded by $B$ times the length: when the model's probabilities are spread over many prefixes, the search must expand every prefix that scores higher than the $k$-th best identifier before it can output that identifier. Beam search fixes the cost and gives up exactness; best-first search fixes exactness and gives up a bound on the cost. NCI divides each finished hypothesis's log-probability by its length (Wang et al., 2022, Algorithm 2), which changes the order among identifiers of different lengths, and with that change the bound in the proof no longer holds: a longer identifier's average can exceed its prefix's. The conclusion fails too. Let the root have children $a$ with probability 0.55 and $b$ with 0.45; after $a$ the model writes ⟨/s⟩ with probability 1, and after $b$ it writes $c$, $d$ and ⟨/s⟩, each with probability 1. Identifier $a$⟨/s⟩ has mean log-probability $\ln 0.55 / 2 = -0.299$ and identifier $b\,c\,d$⟨/s⟩ has $\ln 0.45 / 4 = -0.200$, so the second is first under the mean. Best-first search ordered by the mean expands the root, then $a$ (mean $-0.598$ against $b$'s $-0.799$), then removes the finished $a$⟨/s⟩ at $-0.299$, still above $b$'s $-0.799$, and outputs it first, which is wrong under the mean. Dividing only finished hypotheses by their length, as NCI's Algorithm 2 does, gives the same outcome. Under the sum, $a$⟨/s⟩ ($\ln 0.55 = -0.598$) rightly comes before $b\,c\,d$⟨/s⟩ ($-0.799$). We use the plain sum throughout. Worked problem 4 shows the two orders disagreeing.

What decoding costs

For atomic identifiers, retrieval is one decoder step and a softmax over $|V| + N$ outputs. For sequential identifiers it is up to $\ell_{\max} + 1$ steps, each on $B$ hypotheses. Wang et al. (2022, Section 3.4) state the cost of constrained beam search as $O(LBF)$ for identifiers of length $L$, beam $B$ and a largest fan-out $F$, and $O(B \log N)$ for a balanced tree. Pradeep et al. (2023, Section 6.2) compare inference costs on MS MARCO: the T5-Base model with atomic identifiers needed 9.7% of the inference FLOPs of T5-XL with naive identifiers, for 90% of its retrieval quality, because one large softmax ranks the whole collection while sequential identifiers need one decoding step per token of the identifier for each of $k$ beams ($k = 40$ in their experiments).

Indexing by memorization, and the queries it never sees

A valid identifier is not yet a relevant one. The model has to learn which identifier goes with which content, and the content it learns from at indexing is not the content it reads at retrieval.

What DSI found. Tay et al. (2022, Sections 3.1 and 4.2) compared several ways of teaching the association, on subsets of Natural Questions (NQ) of 10K, 100K and 320K question-document pairs, and with T5 models from Base (250M parameters in their table) to XXL (11B).

  • What to index. "Direct indexing", the first $L$ tokens of the document as input and the identifier as target, worked best, with $L = 32$ in the main results. Performance "seems to substantially dip beyond 64 tokens". Removing stop words or repeated terms gave no advantage. Mapping random contiguous chunks to the identifier (their "inverted index" variant) was hard to train.
  • Which direction. Inputs-to-targets (document tokens in, identifier out) and a bidirectional variant worked. Generating the document from its identifier, or span corruption with the identifier mixed into the text, gave 0% Hits@1. Without the indexing task at all, the model also scored 0%: retrieval examples alone give the identifiers no meaning for documents that no training query points to.
  • When to train which. Indexing first and retrieval afterward "results in mediocre performance". Training both together in one multi-task mixture worked, with a ratio of 32 indexing examples to each retrieval example performing well (their Figure 4).

The main results (their Table 2) are Hits@1 and Hits@10, the share of questions whose one relevant document is ranked first or in the top ten. On NQ320K, T5-Base with semantic identifiers reached 27.4 and 56.6, against 11.6 and 34.4 for BM25 and 20.5 and 58.3 for a T5-Base dual encoder trained on the same pairs; T5-XXL with semantic identifiers reached 40.4 and 70.3. In the "zero-shot" setting (their Table 3), with indexing examples only and no labelled queries, the best results on NQ100K and NQ320K came from atomic identifiers.

The mismatch. Zhuang et al. (2022) named the difficulty behind these findings. At indexing the model reads the first 32 tokens of a document; at retrieval it reads a question of a few words, phrased differently. Labelled queries close the gap for the documents they point to, and most documents have none. Their remedy, DSI-QG, is to represent each document at indexing by queries generated from it:

  1. a query generator, a sequence-to-sequence model fine-tuned to produce a question from a passage (a docT5query checkpoint, in their words "an existing docT5query query generation model checkpoint" (their Section 4.4; for docT5query they cite Nogueira and Lin, 2019); docT5query is the T5 successor of the doc2query model of Nogueira et al. (2019), and both are described in Learned Sparse Retrieval), writes $n$ queries for each document by top-$k$ sampling with $k = 10$, which they chose for diversity over beam search;
  2. a cross-encoder ranks the $n$ queries by their relevance to the document, and the top $r$ are kept;
  3. the DSI model is trained on (generated query, identifier) pairs in place of the document's own text, so that it "only observes short queries as input data during both indexing and retrieval".

With $n = 100$ and $r = 50$, on NQ320k with string identifiers (their Table 1), DSI-QG with T5-Base reached Hits@1 63.49 and Hits@10 82.36, against 27.40 and 56.60 for the original DSI with T5-Base. Those are relative gains of 132% and 46%, the figures the paper states. NCI (Wang et al., 2022) used generated queries too, 15 per document from DocT5Query, together with semantic identifiers from hierarchical k-means ($k = c = 30$), constrained beam search, a decoder whose output weights depend on the prefix (their "prefix-aware weight-adaptive" decoder) and a consistency regularizer. In its ablation (their Table 3) removing the generated queries cost the most, Recall@1 falling from 65.86 to 60.23 on NQ320k; removing the semantic identifiers cost 3.11 points, and removing the constraint 0.21.

Example (the generated queries of one abstract). Abstract 856 of Cranfield is relevant to query 185. Its title is some experimental studies of panel flutter at mach 1.3. The pinned generator, a T5 model fine-tuned on web search questions (MS MARCO), wrote these five queries for it, sampled with the seed 20261122 plus the abstract's position in the collection:

  • what material does flutter
  • what was the process of folding panel flutter
  • how many processes are used to find the effect of flutter in the panel?
  • what is panel flutter
  • how to test a panel flutter

They are short, phrased as questions and mostly about the right subject, and some are not good questions ("what material does flutter"). They are the inputs the model is trained on in our experiment, together with the abstract's first 32 tokens. The generator never saw Cranfield, and nothing from the Cranfield queries enters training.

Two neighbors: generating names, and reading facts from parameters

Generative retrieval has two ancestors that the DSI paper itself cites.

GENRE (De Cao et al., 2021) retrieves entities by generating their names. Its collection is the set of Wikipedia articles, each identified by its unique title, so the identifier is not an arbitrary code but a short, meaningful string: "Wikipedia titles have 6 BPE tokens on average". A fine-tuned BART model reads a context (a sentence with a marked mention, or a question) and writes a title, and constrained beam search over the trie of all titles makes every output a real entity. The paper reports three advantages of generating over the usual bi-encoder that classifies among entity vectors: the decoder reads the context and the name together, as a cross-encoder would; the model's size grows with the vocabulary and not with the number of entities (GENRE "occupied 14 times less memory than BLINK and 34 times less memory than DPR"); and the softmax over the next token is exact, with no sampled negatives. It also shows the limit of names as identifiers in a small test (their Section 4.2): of 50 Wikipedia articles created in 2020 and added to the knowledge base with nothing but their names, the 19 whose mention matched the title exactly were all retrieved, and 14 of the other 31 (45.2%) were. The model's preference for copying the mention, the authors conclude, is what helps on unseen data. Entity disambiguation of this kind is the subject of Entity Linking, where the candidate entities are pages of this site.

The difference that matters for retrieval, which Tay et al. (2022, Section 2) draw themselves: GENRE retrieves "a document whose title is the answer", while DSI retrieves "a document containing the answer", and DSI's targets may be "arbitrary docids". An arbitrary document has no name that a query is likely to echo, which is why the identifier must be learned. The same section sets DSI against retrieval-augmented generation, which uses retrieval to help a model write, as in RAG-Sequence and RAG-Token or the datastore of Nearest Neighbor Language Models: "Here we use generation to replace a retrieval process, rather than using retrieval to augment a generation process."

Language models as knowledge bases. Petroni et al. (2019) asked how much relational knowledge a pretrained language model holds with no fine-tuning, by turning facts into cloze sentences (their example: "Dante was born in [Mask] in the year 1265.") and reading the model's prediction for the blank. Their abstract reports that BERT "contains relational knowledge competitive with traditional NLP methods that have some access to oracle knowledge". The probe, its numbers and the later criticism of it are in the reading note Language Models as Knowledge Bases?. The connection to this article is the idea that parameters can serve as a store to be queried. Their probe, LAMA, asks what pretraining has put there; a DSI puts a collection there deliberately, and is queried for pointers to documents, not for facts.

An experiment: a small DSI on Cranfield

The DSI paper trained T5 models of 250M parameters and more for up to a million steps on 64 to 256 TPU chips. What a laptop processor can do is train the smallest T5 for 1,584 steps on Cranfield's 1,400 abstracts, against the paper's 10K to 320K documents, and the experiment should be read as that: a small-scale observation with one model and one collection.

Setup

  • Collection and queries. Cranfield's 1,400 abstracts and 225 queries with graded judgments, as in Dense Passage Retrieval: nDCG@10 with gain $5 - \text{grade}$, recall at 10 and 20 counting any judged abstract as relevant, and success at 1 and 10 (the share of queries with a relevant abstract at the first rank, or in the top ten), which is the Hits@$k$ of the DSI papers.
  • Model. google-t5/t5-small at revision df1b051c49625cf57a3d0d8d3863ed4d13564fe4, 60,506,624 parameters, with $d_{\text{model}} = 512$ (Raffel et al., 2020, Section 3.7). It is about a quarter the size of the smallest model in Tay et al.'s Table 2.
  • Identifiers. The three designs. Atomic: 1,400 new output rows, initialized at random. Naive: a random permutation of 0 to 1399 per seed, in T5's own tokens. Semantic: hierarchical k-means with $k = 10$ and $c = 10$ over the vectors of the encoder pinned in Text Embeddings and Dense Retrieval (sentence-transformers/all-MiniLM-L6-v2, the vectors of the dense baseline), scikit-learn's k-means with the run's seed, one token per digit.
  • Indexing data, the same for every design. Each abstract's first 32 T5 tokens (title, then text), mapped to its identifier, as in DSI's direct indexing; and five queries per abstract written by the pinned generator doc2query/msmarco-t5-small-v1 (revision eb04306040c87ff35caa4c87078dfd94a6b7b64e, a T5 fine-tuned on MS MARCO query-passage pairs, per its model card), by top-$k$ sampling with $k = 10$, each mapped to the abstract's identifier, as in DSI-QG. That makes 8,400 training pairs. No Cranfield query or judgment is used in training, so the model is evaluated on all 225 queries, in Tay et al.'s zero-shot setting with generated queries added. The generated queries are not filtered by a cross-encoder, as DSI-QG's were.
  • Training. 12 epochs of the 8,400 pairs in batches of 64 (1,584 steps), AdamW at a learning rate of $10^{-3}$ with 200 warm-up steps and linear decay, four processor threads. A run took between 41 and 73 minutes. Three seeds per design (0, 1, 2), each setting the order of the data, dropout, the naive permutation and the k-means. The 1,400 new atomic rows are initialized identically in every run (from a fixed torch seed, 12345), so the three atomic runs differ only in data order and dropout. The site's usual 30 seeds would have taken some days of processor time, so the intervals below are over three runs and say little; we report every run.
  • Retrieval. Constrained beam search with a beam of 20 for the string designs, the 20 finished hypotheses being the ranking; for atomic identifiers, the full ranking by the 1,400 logits, cut at 20 for comparison.
  • Baselines. The collection's BM25 ($k_1 = 1.2$, $b = 0.75$) and dense retriever, exactly as in Dense Passage Retrieval, cut at 20.

Results

Medians over the three seeds, with the interquartile range in parentheses (computed from three values, so it says little); BM25 and the dense retriever are deterministic:

Ranker nDCG@10 Recall@10 Recall@20 Success@1 Success@10
BM25 0.368 0.397 0.503 0.324 0.858
Dense 0.382 0.416 0.530 0.351 0.867
DSI, atomic 0.118 (0.111 to 0.118) 0.119 (0.112 to 0.121) 0.148 (0.146 to 0.157) 0.169 (0.167 to 0.178) 0.400 (0.400 to 0.418)
DSI, naive 0.087 (0.085 to 0.093) 0.095 (0.092 to 0.101) 0.125 (0.124 to 0.131) 0.129 (0.127 to 0.136) 0.369 (0.367 to 0.384)
DSI, semantic 0.233 (0.226 to 0.234) 0.269 (0.263 to 0.276) 0.376 (0.370 to 0.383) 0.240 (0.229 to 0.247) 0.653 (0.629 to 0.660)

Every run:

Design Seed nDCG@10 Success@10 Indexing accuracy Final training loss Minutes
Atomic 0 0.103 0.400 0.558 4.84 56
Atomic 1 0.118 0.436 0.560 4.90 55
Atomic 2 0.119 0.400 0.576 4.82 41
Naive 0 0.082 0.369 0.365 1.88 63
Naive 1 0.087 0.364 0.556 1.50 52
Naive 2 0.098 0.400 0.648 1.40 44
Semantic 0 0.233 0.667 0.391 0.82 73
Semantic 1 0.219 0.604 0.408 0.83 59
Semantic 2 0.236 0.653 0.471 0.81 62

The training loss is the mean over the last epoch of the per-token loss, so it is not comparable across designs: an atomic target is one token out of 1,400 new ones, a semantic target three to five digit tokens and the end token, each predicted under a softmax over the full vocabulary of 32,128 tokens. The minutes vary with the load of other jobs on the shared machine.

The semantic design is the only one that retrieves much. Its median nDCG@10 of 0.233 is about twice the atomic design's 0.118 and more than two and a half times the naive design's 0.087, and every semantic run is above every run of the other two. Averaging each query's nDCG@10 over the three seeds and pairing the designs query by query, the semantic design is ahead of the atomic one by 0.116 ($t = 9.71$ on 224 degrees of freedom; better on 157 queries, worse on 34) and of the naive one by 0.140 ($t = 13.32$); the atomic design is ahead of the naive one by 0.024 ($t = 2.80$, $p = 0.006$). Paired randomization tests over queries, flipping the sign of each query's difference, agree, with $p < 0.01$ for all three pairs. These tests treat the 225 queries as the sample and the three trained models of each design as fixed, so they show that these models differ, not how much training runs vary. Across training runs the evidence is the ordering: every semantic run is above every other run, and with three runs per design that ordering has probability $1/\binom{6}{3} = 1/20$ if the designs did not differ; the same holds for atomic against naive.

Every design is far below the two baselines. The semantic design trails BM25 by 0.139 in nDCG@10 ($t = -9.03$; better on 60 queries, worse on 149) and the dense retriever by 0.153 ($t = -10.49$). At success@10, the share of queries with a relevant abstract somewhere in the top ten, it reaches 0.653 against BM25's 0.858. These differences are far outside what the spread of three seeds could explain. They are what one small model, trained for 12 passes over 8,400 pairs, learned on a collection of technical abstracts it had never read, against rankers that need no training on it.

The ordering of the designs agrees with Tay et al.'s NQ320K results for T5-Base (Hits@1 of 27.4 for semantic, 20.7 for atomic and 6.7 for naive identifiers, their Table 2) and differs from their zero-shot table and from Pradeep et al.'s small-corpus finding that atomic identifiers were "consistently the best". Our atomic runs were plainly undertrained (below), so this is a statement about this budget, not about the designs.

What the model learned, and what it did not

The indexing accuracy asks the narrowest question: given the first 32 tokens of an abstract, the very input it was trained on, does the model put that abstract's identifier first? The medians are 0.560 for the atomic design, 0.556 for the naive design and 0.408 for the semantic design, with a wide spread for the naive runs (0.365 to 0.648). So even on its own training inputs the model has not memorized the collection after 12 epochs. Tay et al. (2022, Table 5) report indexing accuracies between 76.3% and 92.7% for their models, Base to XXL, after up to a million training steps; theirs is measured on the NQ validation documents only, ours on all 1,400 abstracts.

Example (memorizing is not retrieving). It is natural to expect the design that memorizes best to retrieve best. Here it does not. By median indexing accuracy, the atomic and naive models put the right identifier first for more of their own training documents than the semantic models did (one naive run, seed 0, is below all three semantic runs), and they retrieve far worse for queries they have not seen: naive seed 2 has the highest indexing accuracy of all nine runs, 0.648, and an nDCG@10 of 0.098. A likely reason, which the experiment does not isolate: an atomic row, or an arbitrary number, has to be learned from nothing for each document, from six training inputs, and nothing connects the identifiers of related documents. A semantic identifier's first digit is shared by some 140 documents on average, on related subjects, so every training input of every abstract in a node teaches the same first steps, and a new query about panel flutter can reach the right node even when the model cannot single out the right abstract within it.

The learning curves of seed 0, read from checkpoints after 4, 8 and 12 epochs (each a point on the same 12-epoch schedule, not a separate shorter run):

Epochs Atomic nDCG@10 Atomic indexing Semantic nDCG@10 Semantic indexing
4 0.038 0.083 0.105 0.037
8 0.084 0.409 0.200 0.226
12 0.103 0.558 0.233 0.391

Both were still improving when training stopped, and the atomic model's training loss was still falling (from 7.29 in the first epoch, about $\ln 1400 = 7.24$, the loss of a uniform guess over the documents, to 4.84 in the twelfth). The experiment does not say where either would stop, or whether the atomic design would overtake the semantic one with more training, as it does in some of the papers' settings; Tay et al. report that atomic identifiers were hard to optimize and that "these docids might also run into intermittent non-convergence".

Decoding checks

Two checks on the seed-0 models of the string designs, on all 225 queries.

Is the beam finding the most probable identifiers? Best-first search (Theorem 2) gives the exact top ten under the model, and beam search with $B = 10$ can be compared with it. For the semantic model the two agree on the first result for all 225 queries and on the whole set of ten for 179; over all queries the beam missed 68 of the 2,250 identifiers in the exact top tens. For the naive model they agree on the first result for 211 queries and on the set of ten for 132, and the beam missed 200. The exact search was cheap at this scale: it expanded a median of 24 hypotheses per query, at most 46 (semantic) and 34 (naive), comparable to the work of the beam, which scores up to ten hypotheses at each of four or five steps. Our reading of the difference, which the check does not test: a naive identifier's first token (▁12, ▁7) carries no meaning, so the model's probability for it is a poor guide to what follows, the situation of the example in "Beam search is not exact".

Does the constraint matter? Unconstrained beam search with $B = 10$, every token allowed at every step, produced sequences that are not identifiers in 132 of its 2,250 outputs for the semantic model and 11 for the naive model, and the top-ranked output was not an identifier for 2 queries (semantic) and none (naive). A likely reason for the difference: most strings of one or two number tokens that the model writes readily are integers below 1,400, so a plausible number is usually a valid one, while a semantic identifier must follow a path that exists in the tree. In line with the small effects that NCI and Pradeep et al. report for the constraint, the trained models here rarely put an invalid identifier first; the invalid outputs fall lower in the list, where without the constraint they would take places in the top ten.

Query 185

The running query shows what the semantic tree does to a search. Query 185 has nine relevant abstracts. In the clustering of seed 0, six of them (285, 856, 857, 859, 894 and 1008) have identifiers that begin with 11, a node of 12 abstracts, most of them on panel flutter; two (766 and 858, on the flutter of panels under thermal stress) begin with 30, a node of four; and one (15) begins with 62. The semantic model's top ten for the query are ten of the twelve abstracts under 11:

Rank Abstract Identifier Probability Title (shortened) Judged
1 856 1100 0.341 some experimental studies of panel flutter at mach 1.3 grade 3
2 658 1110 0.141 review of panel flutter and effects of aerodynamic noise no
3 285 1140 0.069 on the flutter of panels at high mach numbers grade 4
4 859 1130 0.064 flutter of aerodynamically heated aluminium-alloy and stainless steel panels grade 2
5 857 1101 0.060 experimental studies of flutter of buckled rectangular panels grade 2
6 627 1120 0.055 flutter analysis of circular panels no
7 1008 1150 0.048 free-flight measurements of the static and dynamic grade 3
8 894 1170 0.041 flutter of a two dimensional simply supported buckled panel grade 4
9 864 1160 0.035 status of flutter of flat and curved panels no
10 390 1190 0.031 some panel-flutter studies using piston theory no

The probability is $P_\theta(y_d \mid q)$, the exponential of the score. Cranfield's grades run from 1 (most relevant) to 4, so grade 4 is the weakest relevance.

Its nDCG@10 for the query is 0.586, against 0.256 for the atomic model, 0.132 for the naive model and 0.807 for BM25 (as computed in Dense Passage Retrieval). The best hypotheses went down one branch: all ten begin with 11, and by Proposition 1 that node holds exactly the 12 abstracts whose identifiers begin with 11. That is the intended effect of semantic identifiers, a decoding step that narrows the search to a region of related documents, and it is a bet on the cluster hypothesis, that documents close together are relevant to the same queries. The example shows the bet's other side. The relevant abstracts that k-means put in other nodes are not in the model's list of 20 at all. Two of them, 766 and 858, on panel flutter under thermal stress, lie under 30, and BM25 ranks them 3rd and 5th. The third, 15 (on two-dimensional panel flutter), lies under 62. A lexical ranker scores each abstract on its own words. The decoder reaches an abstract only through its prefixes, and here the paths to these three were pruned from the beam before they reached them.

Adding documents

The last run tests the first failure in the next section on a small scale. An atomic index was trained, with the recipe above and seed 0, on 1,300 of the abstracts; the other 100, drawn at random, were held back, and their output rows, present from the start, never served as targets. Then the 100 were added by continuing the training for 12 epochs on their indexing data alone, 600 examples (each abstract's first tokens and its five generated queries). A second continuation from the same starting point mixed in 600 generated queries of old abstracts, drawn at random once, so that the old documents were rehearsed while the new ones were learned, in the manner of DSI++'s generative memory.

State of the index Indexing accuracy, old 1,300 Indexing accuracy, new 100 nDCG@10, 225 queries
Before adding 0.565 0.000 0.092
After training on the new abstracts only 0.025 0.190 0.023
After training on the new abstracts with replay 0.316 0.400 0.075

Training on the new abstracts alone erased the old ones: the share of old abstracts whose own first tokens decode to their own identifier fell from 0.565 to 0.025, and retrieval over the whole collection fell to a quarter. Replaying old queries kept a little over half of the old accuracy, 0.316, and the new abstracts were learned better too. Retrieval still fell, from 0.092 to 0.075. An inverted index or a dense index would have added the 100 abstracts without touching the other 1,300. This is one seed on one small collection, with a starting model that had itself not finished learning, and the sizes of the drops say nothing about larger systems; the direction of the effect is the one DSI++ measured.

What generative retrieval costs, and what is known about its failures

The claims in this section are the published results of named papers, as of November 2026; the subject is young, and later work may change them.

Adding a document means training

An inverted index adds a document by appending to postings lists, and a dense index by encoding one passage and inserting one vector. A generative index adds a document by training the model on it, and training changes parameters that every other document's retrieval uses. Tay et al. (2022, Section 5) named "how such models can be updated for dynamic corpora" as an important direction. Their own appendix shows the problem inside an ordinary training run (Section 7.2.2): the indexing examples were fed through a shuffle buffer of 5,000, smaller than the validation split, so the validation documents were seen in bursts, and "a DSI model experiences forgetting of previously indexed batches as it indexes new batches". Validation scores rose and fell with the cycle. Their Table 6 gives NQ320K results at the peak and at the trough: for T5-Base with semantic identifiers, Hits@1 of 27.4 at minimum forgetting and 12.0 at maximum, an average of 19.7. The 27.4 of the main table is the peak, because the checkpoint was chosen for its validation score.

Mehta et al. (2023), in DSI++, made the continual case the subject. A model indexes an initial corpus $D_0$ of 50K documents with queries for some of them, then five further corpora of 10K documents each, for which no queries exist. Continuing to train on the indexing examples of the new documents caused what they call catastrophic forgetting: for T5-Base with atomic identifiers on NQ, indexing accuracy on $D_0$ fell by about 25 points and Hits@1 by about 20, and the forgetting grew as indexing continued: after the fifth new corpus, their forgetting measure for indexing accuracy reached 75. Even without new documents, "approx. 88%" of documents went from correctly to incorrectly decoded at some point during ordinary memorization (their "forgetting events"). Two remedies reduced the damage: an optimizer that seeks flat minima (sharpness-aware minimization), with which the model "stably memorizes more documents (+12%)", and a "generative memory", a query generator that produces pseudo-queries for the old documents so that they are rehearsed while the new ones are indexed. The generative memory improved average Hits@10 by 21.1% over the competing baselines on NQ, and average Hits@1 by 25.0% on MS MARCO; the authors' solution required "6 times fewer model updates compared to retraining the DSI model" for indexing the five corpora in sequence.

Identifiers add a second difficulty, which follows from the constructions above rather than from a measurement. An atomic identifier needs a new output row for the new document, initialized from nothing. A semantic identifier was fixed by a clustering of the old collection, and a new document must be placed in that tree, either at the end of an existing leaf node, which may break the bound $c$, or by re-clustering, which changes old identifiers and so invalidates what the model learned. GENRE's names avoid this for entities, since a new entity's title is known; its cold-start test above is the only measurement of that case we read.

Scaling to millions of passages

The early papers worked at 10K to 320K documents. Pradeep et al. (2023) took the methods to the full MS MARCO passage collection, 8.8M passages, with models up to 11B parameters, and measured MRR@10 on its 6,980 development questions. Their findings, from their Tables 3 and 4 and their conclusion:

  • Quality falls with the collection's size. With generated queries as the only indexing input and atomic identifiers on T5-Base, MRR@10 was 80.3 on a 100K-passage subset, 55.8 on 1M passages and 24.2 on all 8.8M. On the full collection BM25 scored 18.4, BM25 over passages expanded with doc2query-T5 queries 27.2, and a dense retriever, GTR-Base, 34.8.
  • Generated queries are the one technique that kept working. In their words, "the use of synthetic queries as a document representation strategy is the only approach that remained effective, and necessary, as we scaled up the corpus size". The original DSI recipe (document tokens and labelled queries) scored 7.5 with naive identifiers on the full collection.
  • The refinements did not survive the comparison at equal cost. NCI's decoder and semantic identifiers, its consistency loss and constrained decoding gave little or nothing once parameters and compute were held fixed. At about 700M parameters, the prefix-aware decoder with semantic identifiers trailed a plainly larger T5 with naive identifiers by about four points.
  • More parameters helped up to a point. The best result, 26.7, came from T5-XL (2.8B parameters in their table) with naive identifiers trained on generated queries only. T5-XXL (11B) in the same setting scored 24.3. T5-Base with atomic identifiers reached 24.2 with 7.0B parameters, most of them the identifier rows, and needed 7 days of training on 64 TPUv4 chips where the XL model needed 14 days.

Their summary is that generative retrieval "is competitive with state-of-the-art dual encoders on small corpora", while "scaling to millions of passages remains an important and unsolved challenge". The best generative result on the full collection was below the dense retriever and close to BM25 with document expansion.

Comparisons between papers need care

The baselines differ from paper to paper even on one dataset. BM25 on NQ320K is reported with Hits@1 and Hits@10 of 11.6 and 34.4 by Tay et al. (2022, Table 2), 29.27 and 60.15 by Zhuang et al. (2022, Table 1), and Recall@1 and Recall@10 of 15.11 and 32.48 by Wang et al. (2022, Table 1). Zhuang et al. note that they reconstructed the dataset from the descriptions, since the original construction code was not available, and each paper used a different BM25 implementation. A difference between two papers' systems is therefore safest read within one paper's table.

What is proved here, what is cited, and what the experiment shows

Proved on the page. For the semantic identifiers of hierarchical k-means: their prefixes are exactly the clusters (Proposition 1); with at most ten branches and leaves of at most ten documents they are unique and prefix-free, and with Tay et al.'s $c = 100$ they need not be prefix-free (Proposition 2); the longest is at least $1 + \lceil \log_k(N/c) \rceil$ digits, and the construction ends when every split has two nonempty clusters, with at most $N - c + 1$ digits when $c \le 10$ (Proposition 3). All three assume $k \le 10$ with labels written as digits, or one token per label. Constrained beam search returns $\min(B, N)$ distinct documents and nothing else (Theorem 1). Beam search can miss the most probable identifier (an example), and best-first search over the trie finds the exact top $k$ under the sum of log-probabilities (Theorem 2), a guarantee that the length-normalized score does not have (a counterexample follows the theorem). The parameter count of atomic identifiers, and the worked problems.

Cited. The designs and every published number: DSI's identifiers, indexing methods, training findings and Tables 2, 3 and 6 (Tay et al., 2022); DSI-QG's generated queries and its Table 1 (Zhuang et al., 2022); NCI's design and its Tables 1 and 3 (Wang et al., 2022); GENRE's names as identifiers, its trie and its cold-start test (De Cao et al., 2021); the knowledge-probe framing (Petroni et al., 2019); the continual-indexing results of DSI++ (Mehta et al., 2023); the scaling results on MS MARCO (Pradeep et al., 2023). These are each paper's own results, on Natural Questions, TriviaQA, XOR QA or MS MARCO, with T5 or BART models of 220M parameters and more, as of November 2026.

Shown by the experiment. On Cranfield, with t5-small trained for 12 epochs on each abstract's first 32 tokens and five generated queries, and no Cranfield query: semantic identifiers retrieved clearly better than atomic or naive ones (median nDCG@10 0.233, 0.118 and 0.087), and all three were far below BM25 (0.368) and the pretrained dense retriever (0.382). Memorizing the training inputs and retrieving for new queries came apart: by median indexing accuracy, the atomic and naive designs memorized more than the semantic one and retrieved far worse. Both learning curves were still rising when training stopped. Beam search found the exact top result for every query with semantic identifiers, and the exact top ten for 179 of 225; unconstrained decoding produced invalid identifiers mostly below the first rank. On query 185 the semantic model's ten best results all came from one node of 12 abstracts, and the relevant abstracts in other nodes were not retrieved. Adding 100 abstracts to an atomic index by training on them alone cut the indexing accuracy of the other 1,300 from 0.565 to 0.025; replaying generated queries of the old abstracts kept 0.316. These are observations on one small collection with one small model, three seeds per design and a fixed training budget; they do not show how the designs compare at scale, and the papers above report the comparison at scale with results that differ.

Worked problems

These problems are posed on small exact cases and on this article's Cranfield runs; the unit has no course assignments. The script checks each one under "Worked problems".

Problem 1 (semantic identifiers by hand). Nine documents $a, \dots, i$ are given identifiers with $k = 3$ branches and leaves of at most $c = 2$ documents. The first clustering gives the groups $\{a, b, c, d, e\}$, $\{f, g, h\}$ and $\{i\}$, numbered 0, 1, 2. The first group is split into $\{a, b\}$, $\{c, d\}$, $\{e\}$ and the second into $\{f, g\}$, $\{h\}$, numbered in that order. Within a leaf, documents are numbered in alphabetical order. Write down the identifiers, check Propositions 1 to 3, and count the nodes of the trie when each identifier is followed by ⟨/s⟩.

Solution. Group 0 has five documents, more than $c$, so it is split; its subgroups have at most two and are leaves. So $a = 000$, $b = 001$, $c = 010$, $d = 011$, $e = 020$. Group 1 has three, more than $c$, and is split: $f = 100$, $g = 101$, $h = 110$. Group 2 has one document, a leaf at the first level: $i = 20$. Proposition 1: the identifiers that begin with 0 are those of $a$ to $e$, the first group, and those beginning with 01 are $c$ and $d$, the subgroup numbered 1. Proposition 2 ($c = 2 \le 10$): the nine strings are distinct, and none is a prefix of another; in particular $20$ is not a prefix of any identifier, since no other identifier begins with 2. Proposition 3: $1 + \lceil \log_3 (9/2) \rceil = 1 + \lceil 1.37 \rceil = 3$, and the longest identifiers have exactly three digits; $i$'s has two, which the bound allows because it is a bound on the longest. The trie has the root; the distinct prefixes of length 1 (0, 1, 2), of length 2 (00, 01, 02, 10, 11, 20) and of length 3 (the eight three-digit identifiers); and one ⟨/s⟩ leaf for each of the nine identifiers. That is $1 + 3 + 6 + 8 + 9 = 27$ nodes.

Problem 2 (beam search and best-first search on one trie). Use the trie of the example in "Beam search is not exact": $P(a) = 3/5$, $P(b) = 2/5$; after $a$, $a_1$ and $a_2$ with $1/2$ each; after $b$, $b_1$ with $9/10$ and $b_2$ with $1/10$. Treat the second token as completing the identifier. Run beam search with $B = 1$ and $B = 2$, and best-first search for the top two, counting the hypotheses it expands.

Solution. The four identifiers have probabilities $P(a\,a_1) = P(a\,a_2) = 3/10$, $P(b\,b_1) = 9/25$ and $P(b\,b_2) = 1/25$; the best two are $b\,b_1$ ($0.36$), then a tie at $0.3$, which our tie rule resolves in token order to $a\,a_1$. With $B = 1$ the first step keeps $a$ ($3/5$ against $2/5$), the second extends it to $a\,a_1$ and $a\,a_2$, and the tie keeps $a\,a_1$: one identifier, of probability $0.3$, not the best. With $B = 2$ the first step keeps $a$ and $b$; the second has the four candidates above and keeps $b\,b_1$ and $a\,a_1$, which are the true top two. Best-first search starts with the root in the queue and expands it, inserting $a$ ($0.6$) and $b$ ($0.4$). It expands $a$, inserting $a\,a_1$ and $a\,a_2$ at $0.3$. The highest in the queue is now $b$ at $0.4$, which it expands, inserting $b\,b_1$ ($0.36$) and $b\,b_2$ ($0.04$). The highest is $b\,b_1$, a finished identifier, so it is output; next is $a\,a_1$ at $0.3$, also finished, and output. Three hypotheses were expanded (the root, $a$, $b$) and the outputs are the exact top two, as Theorem 2 guarantees. The beam of one went wrong because it judged $b$ by its first token's probability, $0.4$, while the best identifier lies under $b$ because the model is nearly certain of $b$'s continuation.

Problem 3 (what atomic identifiers cost). How many parameters do atomic identifiers add to t5-small for Cranfield, and to T5-Base for the full MS MARCO passage collection? How does the second compare with the stored vectors of a dense retriever with 768 dimensions?

Solution. One row of $d_{\text{model}}$ numbers per document. Cranfield with t5-small: $1{,}400 \times 512 = 716{,}800$, which is $716{,}800 / 60{,}506{,}624 = 1.2\%$ of the model. MS MARCO with T5-Base: $8{,}841{,}823 \times 768 = 6{,}790{,}520{,}064$, about 6.8 billion, some 31 times the 220M of the base model; Pradeep et al. list the total as 7.0B. A dense retriever with 768-dimensional vectors stores exactly the same count of numbers, one vector per passage. The two differ in how the numbers are obtained (an encoder applied to each passage, against rows learned by training on that passage), not in how many there are. Compared with sequential identifiers, what the atomic design saves is the decoding search: one matrix product with the decoder's state scores every passage. Compared with a dense retriever it saves nothing, neither in storage nor in the cost of scoring every passage exhaustively, which is also one matrix product.

Problem 4 (the sum of log-probabilities against the mean). Identifier $A$ has two tokens, each predicted with probability $1/2$. Identifier $B$ has four, predicted with probabilities $1/2$, $3/4$, $3/4$ and $3/4$. Which ranks first by the sum of log-probabilities, and which by the mean, as in NCI's Algorithm 2?

Solution. $P(A) = 1/4 = 0.25$ and $P(B) = \tfrac12 \cdot \left(\tfrac34\right)^3 = 27/128 = 0.211$. The sum of log-probabilities is the log of these, so $A$ ranks first. The means are $\ln(1/2) = -0.693$ for $A$ and $\bigl(\ln \tfrac12 + 3 \ln \tfrac34\bigr)/4 = -0.389$ for $B$, so the mean puts $B$ first. Dividing by length rewards long identifiers whose later tokens are predicted confidently, and in a semantic tree the later tokens are often the easy ones, once the cluster is fixed. The two rules answer different questions: the sum is the model's probability of writing the identifier, the quantity Theorem 2 finds exactly; the mean is a per-token confidence. A mean can rise as an identifier lengthens, which is why best-first search with the mean has no guarantee: Theorem 2's proof used the fact that adding a token can only lower the score.

Problem 5 (what the semantic tree allowed on query 185). The semantic model's top ten for query 185 is in the table of the experiment. With Cranfield's gain $5 - \text{grade}$ for a judged abstract and 0 otherwise, compute its nDCG@10. Then compute the largest nDCG@10 that any list drawn only from the 12 abstracts under the prefix 11 could reach.

Solution. The gains down the list are $2, 0, 1, 3, 3, 0, 2, 1, 0, 0$ (856 has grade 3, 285 grade 4, 859 and 857 grade 2, 1008 grade 3, 894 grade 4). DCG@10 is $\sum_r g_r / \log_2(r + 1)$:

$$\frac{2}{1} + \frac{1}{\log_2 4} + \frac{3}{\log_2 5} + \frac{3}{\log_2 6} + \frac{2}{\log_2 8} + \frac{1}{\log_2 9} = 2 + 0.5 + 1.292 + 1.161 + 0.667 + 0.315 = 5.935 .$$

The nine relevant abstracts have gains $3, 3, 3, 3, 2, 2, 1, 1, 1$, whose ideal DCG@10 is 10.121, so nDCG@10 is $5.935 / 10.121 = 0.586$. Under the prefix 11 lie six relevant abstracts, with gains $3, 3, 2, 2, 1, 1$ (859 and 857 of grade 2, 856 and 1008 of grade 3, 285 and 894 of grade 4). The best list from that node puts them first in that order, for a DCG of 7.497, and the ideal is unchanged, since it is computed over all nine; the largest reachable nDCG@10 is $7.497 / 10.121 = 0.741$. The two missing abstracts of gain 3, 766 and 858, are under 30. So even a perfect ordering inside the node the decoder chose loses a quarter of the attainable score on this query; the model's own ordering lost a further 0.154.

What we have learned

A generative retriever stores a collection in its parameters: it is trained to write a document's identifier when it reads the document or a query about it, and it retrieves by decoding. The identifier is the central design choice. Atomic identifiers give an exact ranking in one step at the cost of one row of parameters per document. Naive strings cost nothing and carry no meaning. Semantic identifiers from hierarchical k-means make every prefix a cluster, so that decoding narrows the search one level at a time; with small leaves they are unique and prefix-free, and their length is at least logarithmic in the collection's size. Constrained beam search over a trie of the identifiers returns only real documents, and is not exact; best-first search is exact, at a cost the beam does not bound. The published results show the approach competitive with dual encoders on collections of up to a few hundred thousand documents, made much stronger by indexing with generated queries, and well behind a dense retriever on 8.8 million passages, with adding documents a standing problem that rehearsal reduces and does not remove. Our small run on Cranfield, with t5-small and no Cranfield query in training, showed the same ordering of identifiers as DSI's own comparison with semantic identifiers first, all three far below BM25 and a pretrained dense retriever at this scale and budget, and the forgetting that makes adding documents hard.

The approach treats the model's parameters as a store that is written by training and read by generation, with no separate record of what was written where. Memory for Language-Model Agents takes up the opposite design, an explicit store of text that a model writes to and retrieves from while it works, where adding a memory is a write to the store and leaves the model's parameters as they were. The unit's overview sets the two side by side with the structured stores of Knowledge Graphs.

References

  • De Cao, N., Izacard, G., Riedel, S., and Petroni, F. (2021). Autoregressive entity retrieval. In International Conference on Learning Representations (ICLR 2021). arXiv:2010.00904. record
  • doc2query (n.d.). doc2query/msmarco-t5-small-v1. Model card at revision eb04306040c87ff35caa4c87078dfd94a6b7b64e. https://huggingface.co/doc2query/msmarco-t5-small-v1 (accessed 22 November 2026). record
  • Mehta, S. V., Gupta, J., Tay, Y., Dehghani, M., Tran, V. Q., Rao, J., Najork, M., Strubell, E., and Metzler, D. (2023). DSI++: Updating transformer memory with new documents. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 8198–8213. https://doi.org/10.18653/v1/2023.emnlp-main.510 record
  • Nogueira, R., and Lin, J. (2019). From doc2query to docTTTTTquery. Technical report, University of Waterloo. https://cs.uwaterloo.ca/~jimmylin/publications/Nogueira_Lin_2019_docTTTTTquery-v2.pdf record · 2 pages
  • Nogueira, R., Yang, W., Lin, J., and Cho, K. (2019). Document expansion by query prediction. arXiv:1904.08375. record · 3 pages
  • Petroni, F., Rocktäschel, T., Lewis, P., Bakhtin, A., Wu, Y., Miller, A. H., and Riedel, S. (2019). Language models as knowledge bases? In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), 2463–2473. https://doi.org/10.18653/v1/D19-1250 record · 2 pages
  • Pradeep, R., Hui, K., Gupta, J., Lelkes, A. D., Zhuang, H., Lin, J., Metzler, D., and Tran, V. Q. (2023). How does generative retrieval scale to millions of passages? In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 1305–1321. https://doi.org/10.18653/v1/2023.emnlp-main.83 record
  • Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. (2020). Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140), 1–67. record · 2 pages
  • Tay, Y., Tran, V. Q., Dehghani, M., Ni, J., Bahri, D., Mehta, H., Qin, Z., Hui, K., Zhao, Z., Gupta, J., Schuster, T., Cohen, W. W., and Metzler, D. (2022). Transformer memory as a differentiable search index. In Advances in Neural Information Processing Systems 35 (NeurIPS 2022), 21831–21843. arXiv:2202.06991. record
  • Wang, Y., Hou, Y., Wang, H., Miao, Z., Wu, S., Sun, H., Chen, Q., Xia, Y., Chi, C., Zhao, G., Liu, Z., Xie, X., Sun, H. A., Deng, W., Zhang, Q., and Yang, M. (2022). A neural corpus indexer for document retrieval. In Advances in Neural Information Processing Systems 35 (NeurIPS 2022), 25600–25614. arXiv:2206.02743. record
  • Zhuang, S., Ren, H., Shou, L., Pei, J., Gong, M., Zuccon, G., and Jiang, D. (2022). Bridging the gap between indexing and retrieval for differentiable search index with query generation. arXiv:2206.10128 (version 3 appeared at the Gen-IR workshop at SIGIR 2023). record