Chapter 23: Generative Retrieval

00-START-HERE · 01-READING-ROUTES · 22_reranking · 24_query_reformulation This chapter explains when a model can retrieve by generating document identifiers, what that relocation costs, why updates remain hard, and how recitation can complement Retrieval-Augmented Generation (RAG).

TL;DR

• Generating a document identifier relocates part of retrieval into model decoding, but valid-ID constraints and the ID-to-content store remain external structures.
• An atomic output head has $N$ learned rows. The exhaustive baseline scores them all; an ANN approximation can accelerate inner-product ranking if one accepts a conventional index again.
• Semantic identifiers can shorten the output alphabet. Tree balance, identifier assignment, constrained decoding and beam pruning determine achieved behavior; a trie provides validity, not relevance or exact global top-k search.
• Fixed-length identifiers need at least $\lceil\log_V N\rceil$ symbols, but this is not a universal achieved latency law. Model compute, memory traffic, beam work and auxiliary structures matter.
• Stored model bits divided by corpus size are a useful footprint comparison, not a mathematical retrieval-quality ceiling or a necessary prototype-rejection threshold.
• Updates need explicit freshness and preservation tests. A frozen learned base with a mutable conventional delta is one design, not the only possible local-update architecture.
• Recitation can supply unverified context, including on some retrieval misses. Clean-continuation decay and voting improvements depend on stated probability assumptions. Prefer retained sources for freshness, privacy controls and attributable evidence.

The story

Imagine a library with an extraordinary librarian. In a normal library, the librarian searches a catalog. The catalog is the runtime index. It stores one addressable record for every book. Generative retrieval trains the librarian to say a call number such as $629.2$ directly after hearing a question. The call number is the document identifier, a short token sequence that names one document. The catalog did not disappear. Part of it moved into the librarian’s memory, and part became the system used to organize call numbers. Giving every book one unique spoken word is the atomic identifier design. It sounds simple, but the librarian must choose among every book in one step. That choice recreates a full shelf-sized catalog inside the final scoring layer. A better design gives books hierarchical call numbers. The first digit chooses a broad wing, the next chooses an aisle, and later digits choose a shelf and book. These are semantically structured identifiers, which means nearby topics share early digits. The librarian now makes several small coarse-to-fine choices. A prefix trie acts like a floor plan that lists every legal partial call number. If no book begins with 3 5, the floor plan closes that branch before it wastes a candidate slot. The librarian can carry several possible call numbers at once. That is beam search, a decoding method that keeps a fixed number of live prefixes. In a balanced fixed-length identifier design, a larger collection may require another symbol when alphabet capacity is exhausted. That gives a staircase in decode depth, not constant query cost or a guarantee that an unbalanced semantic tree has the minimum depth. The model has finite stored weights, but dividing their bytes equally among documents does not measure the information it actually learned. Related documents can share structure, while even a large model can learn a poor query-to-identifier mapping. Comparing model bytes with catalog-record bytes is useful bookkeeping, not a theorem predicting which retriever wins. A conventional catalog has addressable records. A shared learned mapping can change older associations during training, but it is too strong to say every insertion must rewrite every parameter. A new atomic row, an adapter or another update policy has different preservation and query-cost trade-offs; each needs tests beyond the training examples. The practical library therefore freezes the librarian’s learned catalog. It puts new books into a small mutable side catalog, searches both, and periodically retrains the librarian during compaction. A second route asks the model to recite a passage before answering. Exact continuation from a remembered beginning can drift as it grows. That describes this recitation procedure, not a theorem that an autoregressive model cannot answer a fact directly from a suitable question. An externally retrieved passage instead supplies an addressable source, though retrieval and extraction can still fail. The two routes therefore cooperate. The catalog supplies private, recent, and citable books. The librarian’s recitation can cover a vocabulary-mismatched zero-hit question. Both routes produce passages for the same final answer writer. The system keeps their provenance labels separate so a remembered imitation never receives a false citation.

Decoder table

Core mechanics

Mathematical conventions

Storage uses decimal units: $1\,\mathrm{MB}=10^6\,\mathrm B$, $1\,\mathrm{GB}=10^9\,\mathrm B$ and $1\,\mathrm{TB}=10^{12}\,\mathrm B$. Count a multiply-accumulate as two FLOPs. Keep full precision until reporting. Percentages are fractions scaled by one hundred; percentage-point changes are absolute differences. Use $b_w$ for stored bits per parameter and $\beta$ for beam width, avoiding the source's overloaded letter. $L_{\mathrm{id}}$ counts identifier tokens; $L_{\mathrm{roll}}$ counts generated passage tokens in the recitation toy. Fixed-length identifier calculations omit extra end/formatting tokens. A branching factor does not guarantee a balanced tree, and an alphabet-size lower bound is not an achieved path length for every identifier design. The examples deliberately use different resource assumptions: the identifier comparison uses $F_{\mathrm{id}}=1.25\times10^{14}\,\mathrm{FLOP\,s^{-1}}$ and $B_{\mathrm{id}}=2.0\times10^{12}\,\mathrm{B\,s^{-1}}$; the later decoder-stream example uses $1.6\times10^{12}\,\mathrm{B\,s^{-1}}$ and the PQ scan assumes $10^9$ code lookups per core-second. For this recalculation the identifier scenario fixes the summary's approximately $125\,\mathrm{TFLOP/s}$ as the stated rate rather than inferring a different rate from rounded times. Training assumes eight devices at $1.5\times10^{14}\,\mathrm{FLOP/s}$ each, perfect aggregation and a price $\$2$ per device-hour. The recitation/prefill example separately assumes $2.0\,\mathrm{TB/s}$ and $3.4\times10^{14}\,\mathrm{FLOP/s}$. These are planning inputs, not reproduced hardware measurements. Work divided by a sustained rate and bytes divided by bandwidth are resource-time components, not measured latency, invoices or p99 bounds. For a compute/memory roofline use the larger component, not their sum, before adding dependent stages. Actual kernels, attention, caches, trie traversal, selection, transfer, queues and deployment overhead can change the result. Model memory comparisons exclude the identifier trie, mapping back to documents, source text and other metadata unless explicitly included. Generating an identifier is not fetching the identified passage. The quantity $b_wP/N$ is a nominal stored-bit budget per document, not learned information, a guaranteed capacity allocation or a retrieval-quality bound. It cannot be equated to PQ record bits to prove necessary starvation. The retraining formula $6PT_{\mathrm{work}}$ is a simplified token-work proxy: applying all model parameters to encoder and decoder positions is not a faithful encoder-decoder operation count. Updated examples count declared target positions as well as inputs and still exclude pseudo-query generation, attention overhead and evaluation. Recitation equations describe a specified clean entry/continuation/extraction path. Equal conditional continuation probabilities yield a power; marginal per-token accuracy alone does not. Voting examples additionally assume IID correctness indicators, a single canonical correct answer and a declared tie rule. Concentrated wrong-answer identity is different from statistical correlation between samples.

23.1 Generating document IDs instead of searching

Classical search keeps the corpus on the query path

• Classical scoring defines $\hat d\in\mathop{\mathrm{arg\,max}}_{d\in D}s(q,d)$, with a declared tie policy. Approximate search need not return that exact maximizer.
• Inverted lists, IVF and HNSW reduce evaluated records under their own assumptions; corpus vectors, postings or other index data remain in the retrieval path.
• Full materialization, sharding and replication are deployment choices, not a mathematical requirement that all source text be resident on one machine. The worked payload comparison explicitly excludes several serving structures.

Generative retrieval turns retrieval into decoding

Assign an injective identifier $i(d)=(t_1,\ldots,t_{L_{\mathrm{id}}})$ from an alphabet of size $V$. The autoregressive factorization is

The ID-generation stage can consult weights and a constraint structure rather than scanning document vectors. Returning a passage still requires an identifier-to-document mapping and content access. Training and constraint storage do not disappear, and variable-length schemes need explicit termination semantics.

DSI trains memorization and generalization together

• What: Tay et al. (2022) train an indexing task from document text to its docid and a retrieval task from query to docid. Metzler et al. (2021) frame the program as replacing the index with parameters.
• Why: The indexing task teaches the corpus. The retrieval task teaches the mapping used in production.
• Without it: Document-only training does not match query-only serving.
• Cost: Training needs examples for both tasks. Generated queries cover documents that lack real query logs.

Atomic identifiers rebuild the index inside the softmax

In the exhaustive atomic baseline, one document receives one output class, so the added head has $N$ rows of width $d_{\mathrm{model}}$. At $N=8.8\times10^6,d_{\mathrm{model}}=768$, its fp32 payload is

The stipulated $220\times10^6$-parameter backbone is $880\,\mathrm{MB}$ in fp32, so that added table is exactly $30.72$ times the backbone payload. The total is $27.9136\,\mathrm{GB}$ under this additive, non-shared-table accounting. Exhaustive output scoring is maximum-inner-product ranking. It is not intrinsically impossible to index those rows with ANN for approximate top results; doing so reintroduces a conventional search structure. Full softmax normalization and exact class probabilities have additional requirements.

Semantic hierarchy spends the identifier space differently

The source uses hierarchical clustering with branching factor ten and leaf capacity one hundred. At least $\lceil8.8\times10^6/100\rceil=88{,}000$ leaves are necessary. A sufficiently balanced ten-way tree can use five tree digits and two within-leaf digits, giving seven-token IDs; the leaf-count calculation alone does not guarantee that depth for recursive k-means. Unbalanced splits or unsuccessful clustering termination require another policy. Semantic prefixes may help learning, but do not prove more accurate decisions than arbitrary prefixes. In a balanced first split, committing to one wrong branch retains about one tenth of documents and discards about nine tenths, including the gold branch. Beam search can retain alternatives. The ten-symbol fp32 head is $10(768)(4)=30{,}720\,\mathrm B=30.72\,\mathrm{kB}$, excluding other vocabulary rows, special tokens and tree storage. The source reports semantic identifiers strongest among its compared schemes at the tested scale; that is not a universal result.

The hierarchy resembles an autoregressive IVF probe

The coarse-to-fine path resembles successive IVF choices, but ordinary IVF ranks coarse centroids once and may probe several lists; it is not simply making statistically independent decisions. Autoregressive prefixes allow later scores to depend on earlier choices. At fixed per-step work and beam policy, decode work grows with $L_{\mathrm{id}}$, while prefix pruning can lose the globally best full identifier.

Constrained decoding provides validity, not relevance

A prefix trie masks children not present in the registered identifier set. With correct terminal handling, a complete accepted path names a registered item; truncation, stale mappings and output parsing still need checks. This is validity, not relevance. In the fixed seven-digit example there are $10^7$ strings and $1.2\times10^6$ unused strings, or $12\%$ of the code space. That unused-space fraction is not the trained decoder's invalid-output probability. The chapter cites GENRE for title-trie decoding and SEAL for corpus-substring constraints using an FM-index. A legal substring can occur in multiple documents, so substring-to-document aggregation is not automatically a unique docid mapping. Constraint memory and updates belong in the serving budget.

Beam width is retrieval depth

For a final-beam-only implementation, width $\beta$ retains at most $\beta$ active hypotheses and returns at most that many final IDs before deduplication/filtering. Algorithms that accumulate completed hypotheses or run extra searches can return a different number. Approximate beam search does not guarantee the globally highest-probability identifiers. A final beam of ten alone cannot supply twenty unique candidates. Wider beams can share weight reads within a decode step, but still increase arithmetic, KV-cache traffic, selection and active-prefix work. Post-filtering invalid results wastes slots; maintaining validity during search does not fix a bad relevance model.

Worked comparison at 8.8M passages

Configuration 1 uses dense vectors and HNSW.

• At the stated fp32 width, vector payload is $27.0336\,\mathrm{GB}$.
• Under the base-layer allocation convention $M=32$, up to $2M=64$ four-byte neighbor slots budget $256\,\mathrm{B/node}$ or $2.2528\,\mathrm{GB}$.
• Their sum is $29.2864\,\mathrm{GB}$; three such copies are $87.8592\,\mathrm{GB}$. Upper graph layers, identifiers, allocation overhead, source text and other metadata are excluded, so this is not complete resident memory.
• $e_{\mathrm{search}}=128$ does not mathematically imply exactly one thousand visited vectors. Stipulate one thousand for the traffic example: each payload is $3{,}072\,\mathrm B$, and dot work is $1{,}536{,}000$ FLOPs.
• A fully serialized thousand-fetch scenario at $100\,\mathrm{ns/fetch}$ sums to $0.1\,\mathrm{ms}$. Dependence, overlap, locality, graph work, selection and query encoding can change actual latency. This is not an independently measured HNSW benchmark. Configuration 2 uses atomic generative identifiers. The added atomic table streams $27.0336\,\mathrm{GB}$ in fp32, a $13.5168\,\mathrm{ms}$ bandwidth component at $2.0\,\mathrm{TB/s}$. At fp16 the corresponding table/read component is $13.5168\,\mathrm{GB}$ and $6.7584\,\mathrm{ms}$. Backbone forward work, query encoding and output selection are additional. These are not end-to-end latencies. The fp32 table-plus-backbone sum $27.9136\,\mathrm{GB}$ is actually below the scoped HNSW $29.2864\,\mathrm{GB}$ payload-plus-links estimate, so these numbers do not establish the source's “strictly dominated on both memory and speed” claim. Precision, quality, auxiliary data, devices and full costs must be matched. Configuration 3 uses hierarchical identifiers. For one explicit hierarchical scenario, divide the $220\times10^6$ stored parameters into two stipulated equal halves: encoder and decoder each $110\times10^6$. This is simplified accounting, not a measured T5 implementation profile. The fp16 total is $440\,\mathrm{MB}$; each half is $220\,\mathrm{MB}$. A thirty-two-position query uses linear work $2(110\times10^6)(32)=7.04\times10^9$ FLOPs, or $0.056320\,\mathrm{ms}$ at $F_{\mathrm{id}}$. A full encoder-half read costs $0.11\,\mathrm{ms}$ at $B_{\mathrm{id}}$. Seven decoder-half reads use $1.54\,\mathrm{GB}$, or $0.77\,\mathrm{ms}$. Beam ten adds linear decoder work $2(110\times10^6)(10)(7)=15.4\times10^9$ FLOPs, or $0.123200\,\mathrm{ms}$. The partial sequential roofline estimate is therefore

If instead every decode step reads the full backbone, seven reads use $3.08\,\mathrm{GB}$; the corresponding partial sum is $0.11+1.54=1.65\,\mathrm{ms}$. Neither byte sum is an upper bound on real latency. The earlier calculation mixed decoder parameter counts with full-model traffic and omitted the encoder read. Model-only versus HNSW payload-plus-base-links storage ratio is $29.2864/0.44=66.56$, not an all-in index ratio because the trie and ID mapping are omitted. Int8 vector payload is $6.7584\,\mathrm{GB}$; with the same graph-link budget it is $9.0112\,\mathrm{GB}$, ratio $20.48$. Quantization can change quality. The $0.88/0.1=8.8$ and $1.65/0.1=16.5$ partial-time ratios compare stipulated components, not controlled architecture benchmarks.

Scale checks and operating choices

• The source reports atomic-ID tests through $320{,}000$ documents. Their fp32 added table is $983.04\,\mathrm{MB}$, larger than the stipulated $880\,\mathrm{MB}$ backbone.
• Fixed-length unique IDs over a ten-symbol alphabet require $L_{\mathrm{id}}\ge\lceil\log_{10}N\rceil$. Seven is the lower bound at $8.8\times10^6$; achieving it with semantic clustering needs a suitable assignment. EOS and formatting are extra if used.
• At $10^5$ documents, the atomic table is $307.2\,\mathrm{MB}$. Strictly under one decimal GB allows up to $325{,}520$ rows; the source's roughly one-hundred-thousand recommendation is a heuristic, not the arithmetic one-GB boundary.
• One hundred symbols need at least four fixed-length tokens. Seven-to-four reduces only the fixed per-step decode component by $42.857143\%$; including one unchanged encoder-half read changes this partial model from eight to five equal reads, a $37.5\%$ reduction. The symbol head is tenfold wider; total softmax/model/runtime need not be tenfold.
• Tenfold growth to $8.8\times10^7$ requires at least eight decimal digits, a $14.285714\%$ step increase, or $12.5\%$ in the equal encoder-plus-decoder read scenario. Balance, beam work and model quality can also change.
• Preserve a stable ID policy or version migrations. Reclustering can rename old paths and force mapping/model updates.
• Compare structured, substring, atomic and conventional retrievers on matched quality, hardware, all-in footprint and freshness. Co-train document and query tasks and validate generated-query coverage; no single scheme is universally best.

23.2 Query scaling, stored budgets, and empirical quality limits

Query latency depends on the model and identifier

A stipulated batch-one decoder may be bandwidth-bound if weight reads dominate arithmetic and other traffic; this is not automatic for every model, beam or implementation. Reusing a read across beam hypotheses helps, but does not make hypotheses free. Under a fixed per-step regime, the weight-stream component is proportional to $L_{\mathrm{id}}$. For $N$ fixed-length unique IDs over $V$ symbols,

This is an identifier-space lower bound, not a universal achieved complexity. At minimum length, decimal IDs need six tokens at $320{,}000$, seven at $8.8\times10^6$ and nine at $10^9$ documents. Thousandfold growth adds three minimal decimal digits. Variable lengths, nonuniform IDs and unbalanced semantic trees need their own maximum/mean-length analysis.

Index cost still grows with the corpus

For IVF with $C$ coarse lists, exhaustive centroid selection evaluates $C$ centroid vectors. Under balanced-list or mean-size assumptions, probing $n_{\mathrm{probe}}$ lists scans about $n_{\mathrm{probe}}N/C$ document codes. At $C\approx\sqrt N$, their total number is approximately $(1+n_{\mathrm{probe}})\sqrt N$, but a centroid comparison and a PQ code scan are not equal-cost operations. With width $d$ and $m$ PQ subquantizers, price coarse inner products as $2dC$ FLOPs and code scans as $m n_{\mathrm{probe}}N/C$ lookups. A query lookup-table build with $256$ centroids per subspace adds roughly $2(256)d$ dot-product FLOPs. Query-selected lists need not equal the global average length. HNSW often has favorable empirical/logarithmic-like scaling, not a universal guaranteed logarithmic hop count. Resident versus disk-based indexes, sharding, caches and fan-out are design choices; maxima of shard timings must not be replaced by an identity involving individual p99 values.

Stored-bit parity is not a quality theorem

The model's stored payload is $b_wP$ bits. Dividing by the corpus size gives nominal budget $\kappa_{\mathrm{gen}}=b_wP/N$. A width-$768$ fp32 vector uses $24{,}576$ bits; a sixty-four-byte PQ code uses $512$ bits. Their byte-budget equality is

It is not a necessary quality bound, a guarantee of starvation above the crossing, or a guarantee of good retrieval below it. Model weights can share structure across documents; PQ codes store a particular representation, not the information-theoretic minimum for retrieval. Model payload also excludes the trie, mapping and source text. There is no justified inference that below five hundred twelve stored weight bits per document forces a model to lose. A genuine counting bound needs a declared function family. If all information for an arbitrary bijection from $N$ fixed labeled queries to $N$ document IDs must reside in quantized weights, distinguishing all $N!$ bijections requires $b_wP\ge\log_2(N!)$. At $8.8\times10^6$, this is about $21.626379$ bits per document, not $512$. This hypothetical counting requirement is not a sufficiency theorem for learning or natural-language retrieval, and external structures can carry information too.

If model size grows with the corpus

Keeping the nominal ratio $b_wP/N$ fixed means scaling $P$ linearly with $N$ at fixed precision. Under fixed hardware and full uncached per-step weight streaming, that makes each stream component linear in $N$; when minimal ID length also grows, the product is roughly $N\log_VN$, not merely linear overall. It does not prove that quality requires proportional model growth. Compression, routing, caching, learned structure and other algorithms change the premise. An atomic head instead incurs linear row payload immediately, but approximate head indexing or local-row updates remain possible design choices.

Worked latency and capacity comparison

Use $P=220\times10^6$ and $b_w=16$, totaling $3.52\times10^9$ stored bits. These are payload budgets, not measured learned information. Assume the decoder holds one half of the stored weights: $110\times10^6(2\,\mathrm B)=0.22\,\mathrm{GB}$. At the separate bandwidth $1.6\,\mathrm{TB/s}$, its stream component is $0.1375\,\mathrm{ms/step}$. One full encoder-half stream adds another $0.1375\,\mathrm{ms}$ per query in this simple memory-only comparison. For the IVF-PQ example choose integer $C=\lceil\sqrt N\rceil$, $d=768,m=64,n_{\mathrm{probe}}=32$, and a stipulated $10^9$ code-table lookups per core-second. Compute the code-scan lookup component separately from centroid scoring, table construction, query encoding, selection and other costs. The code-scan times below are not complete IVF-PQ latency or controlled same-hardware comparisons with the decoder. At $N = 320,000$ documents: At $N=320{,}000$, minimum decimal length is six. Decoder-half streaming is $0.825\,\mathrm{ms}$, or $0.9625\,\mathrm{ms}$ including the encoder-half stream. For $C=566$, coarse scoring costs $869{,}376$ dot-product FLOPs. Balanced-list code scans average $32N/C\approx18{,}091.872792$ records, or $1{,}157{,}879.858657$ table lookups and $1.157880\,\mathrm{ms}$ at the assumed lookup rate. These expected counts need not be integers; actual selected-list totals are integers. Stored model budget is $11{,}000$ bits per document, $21.484375$ times the PQ-code payload, not proven superior learned capacity. At $N = 8.8\mathrm{M}$ passages: At $N=8.8\times10^6$, minimum decimal length is seven. Decoder streaming is $0.9625\,\mathrm{ms}$, or $1.1\,\mathrm{ms}$ with the encoder stream. For $C=2{,}967$, coarse scoring costs $4{,}557{,}312$ FLOPs. Mean code scans are $94{,}910.684193$, giving $6{,}074{,}283.788338$ lookups and $6.074284\,\mathrm{ms}$ of lookup-rate resource time. A separate LUT build is approximately $393{,}216$ dot-product FLOPs in both examples. The corpus grew $27.5$-fold. Decoder-only stream time grew $16.666667\%$, encoder-plus-decoder stream time $14.285714\%$, and this particular code-scan component $424.603977\%$. Do not count all coarse comparisons as sixty-four PQ lookups or call these partial component ratios benchmarked speedups. The stored model budget is $400$ bits per document; its being below a $512$-bit code does not make retrieval-quality failure follow mathematically. The memory comparison has an important limit. Model weights are $440\,\mathrm{MB}$. PQ codes alone are $8.8\times10^6(64)=563.2\,\mathrm{MB}$, ratio $1.28$; the fp32 vector payload is $27.0336\,\mathrm{GB}$, ratio $61.44$. None is an all-in memory comparison: the model needs identifier constraints/mappings, and IVF-PQ needs centroids, codebooks, IDs, lists and serving data. Index quantization also changes its accuracy/cost trade-off.

Evidence checks and decision rules

• Against $512$-bit records, $N^\star=6{,}875{,}000$; $8.8\times10^6$ is $28\%$ beyond that stored-payload crossing, not necessarily beyond a quality boundary.
• The source reports that scaled generative systems in the cited comparison did not match a tuned dual encoder on the full corpus. This is empirical evidence in that setup, not proof that identifier assignment alone caused the gap.
• An $11\times10^9$-parameter fp16 model has $1.76\times10^{11}$ stored bits and parity $343{,}750{,}000$ against those codes. Poor quality below that number does not make parity a necessary condition; it shows only that byte counts do not predict the outcome.
• Source factor-two rejection and below-one-tenth preference rules are unvalidated screening heuristics. Do not treat them as mathematical prototype gates.
• At $20\times10^6$ documents the base model budget is $176$ stored bits per document. Halving code bytes doubles the payload crossing; neither change determines learned accuracy.
• Beam fifty still has the same number of token steps, but not the same arithmetic, KV or selection cost. In the simplified first example, linear beam work alone reaches the decoder-half read component near width $62.5$; other overhead can bind earlier.
• Keep conventional retrieval unless matched quality, total footprint, full latency and updates justify replacement. A generator chunk's $10.541176\,\mathrm{ms}$ linear prefill proxy can exceed the $6.074284\,\mathrm{ms}$ lookup component, but unlike partial costs do not prove one component irrelevant.
• Keep the same half-model convention for the large-model check: an $11$-billion total parameter model has $11\,\mathrm{GB}$ per decoder-half read, $6.875\,\mathrm{ms/step}$ at $1.6\,\mathrm{TB/s}$, and $48.125\,\mathrm{ms}$ for seven reads. Reading all $22\,\mathrm{GB}$ every step would instead give $96.25\,\mathrm{ms}$. Neither is total query latency.

23.3 Incremental indexing: the open wound

Fresh documents have zero recall

If a frozen valid-ID constraint excludes every newly registered document, that serving path has zero recall for those new IDs. Adding IDs to the constraint permits outputs but does not teach a useful query mapping. Once permitted, a new ID can have nonzero probability even without a targeted update, so universal zero recall then no longer follows. Prior exposure to the text and changed external inputs are separate questions.

Classical indexes have write locality

Appending postings requires work proportional to processed terms/postings under a chosen dictionary/storage design, often modeled as $O(\lvert d\rvert)$ plus lookup, allocation and durability costs. HNSW allocates a new node, searches for neighbors and may alter reciprocal neighbor lists. A frequently used $O(M\log N)$ description relies on graph/search assumptions; it is not a universal worst-case bound on rewritten edges. Indexes can support concurrent serving, but locking, versions, compaction and replication are implementation obligations. Local addressability does not mean cost is exactly independent of corpus size.

A learned index superposes every document

Shared learned mappings can interfere: updating one query-to-ID path can alter older scores. A softmax denominator couples probabilities within one decision, but it does not prove every parameter has a nonzero gradient or that every correct insertion must rewrite the entire parameter field. Frozen features plus a new atomic row, sparse or adapter updates and modular models are counterexamples to that absolute claim. They still need preservation tests and can have other serving costs. A missing preservation term provides no guarantee, not a theorem of inevitable forgetting.

Full retraining prices one refresh workflow, not every update method

The source prices a DSI-style retriever with $N = 10^{7}$ and $P = 2.2 \times 10^{8}$. The indexing input is $64$ positions plus ten pseudo-query inputs of sixteen positions: $224$ inputs per document and epoch. The original $6PT$ estimate counted only those inputs. This revised workload reserves fixed eight-digit identifiers for the update scenario, allowing growth beyond ten million without immediately exhausting seven-digit space. Eleven tasks per document therefore add $11(8)=88$ target positions, with no extra EOS in this declared proxy.

The earlier input-only $T=2.24\times10^{10}$ gives $2.9568\times10^{19}$ FLOPs and $6.844444$ hours under the same simplified rule. Neither is a measured encoder-decoder training runtime or a strict freshness floor: parameter participation differs by stage, attention and decoder memory projections are not modeled, and pseudo-query generation, evaluation, queues and release work are excluded. Count targets explicitly and benchmark the actual recipe instead of presenting the input-only value as a complete job estimate.

New-only fine-tuning forgets old mappings

The source reports continual-indexing forgetting and describes DSI++ using sharpness-aware minimization and generative-memory rehearsal. Its quoted average Hits-at-ten improvement is $21.1\%$ relative to its stated baselines, not automatically twenty-one-point-one absolute points. The reported sixfold reduction concerns model updates across five sequential corpora, not an externally reproduced cost ratio. New-only training lacks a direct old-example preservation objective, but does not necessarily damage every old mapping. Rehearsal covers only its sampled/generated distribution. LoRA restricts update parameters without making old and new outputs probabilistically disjoint or guaranteeing no forgetting. Evaluate old and new cohorts independently, with retrieval constraints and denominators documented.

IncDSI restores locality by restoring a flat layer

For frozen query features and atomic scores $s_i(q)=h(q)^\mathsf T w_i$, a new row $w_{N+1}$ is an addressable update. Older pairwise logits and odds can stay unchanged even though adding the new softmax class reduces their normalized probabilities. New rows can still outrank an old correct document, so constraints on finite training queries are not universal preservation guarantees. The chapter reports IncDSI insertions around $20$–$50\,\mathrm{ms}$ and competitive quality in its setup. This is reported implementation context, not a universal service SLA. Exhaustive evaluation of all rows has linear row traffic; ANN acceleration is possible but introduces a conventional index. Local row insertion does not require retraining all network parameters.

Frozen base plus mutable delta as one deployment option

One update design freezes a learned base, inserts new documents into a mutable ANN delta, searches both, merges scores with an explicit policy and periodically compacts. Measure score calibration, duplicate versions, delta growth, old/new recall and cutover correctness. A decode constraint, tombstone or serving filter can block registered IDs if every read enforces it, but stale caches, replicas and alternate paths still matter. Retrieval exclusion is not erasure from weights or all source copies, and it does not eliminate recitation exposure.

Worked updates with fifty thousand daily net additions

Initially there are $10^7$ documents and $50{,}000$ net additions per day, $0.5\%$ of the initial base. This is a fixed count, not a perpetually compounded half-percent growth rate. The update workload uses eight-digit IDs, ten epochs and the revised target-inclusive token-work proxy. An annualized initial-size budget and a growing-corpus forecast are different calculations. Each new vector has $d = 768$ fp32 dimensions. Configuration 1 retrains nightly. One initial-size refresh has proxy $4.1184\times10^{19}$ FLOPs, $9.533333$ idealized hours on eight devices and $76.266667$ device-hours. At $\$2$ per device-hour it costs $\$152.533333$. Repeating that same-size workload daily for $365$ days annualizes to $\$55{,}674.67$, excluding other costs. For net additions and a refresh after each day's arrivals, $N_j=10^7+50{,}000j$. Holding model, token counts, rates and epochs fixed, the corresponding annual proxy is $\sum_{j=1}^{365}(\$152.533333)N_j/10^7\approx\$106{,}616.99$, ending at $28.25\times10^6$ documents. The original flat annual number did not account for this growth. This is the work/price of the requested jobs, not a guarantee that an eight-device cluster can deliver each refresh nightly: this proxy first exceeds twenty-four hours on arrival day $304$, so the final part of that schedule needs extra capacity, fewer jobs or a longer freshness window. Job time is not ingest freshness. With one snapshot every twenty-four hours and a deterministic initial job duration, arrivals wait for the next eligible snapshot. Uniform arrival phases yield mean wait-plus-job $21.533333$ hours and supremum $33.533333$ hours, before queues and release checks. Later larger jobs take longer under this proxy. A replacement corpus held at fixed size would require an explicit retirement/deletion policy and a different growth interpretation. Configuration 2 inserts one IncDSI row per document. At stipulated row service time $50\,\mathrm{ms}$, fifty thousand rows sum to $2{,}500\,\mathrm s$ of device service. This is not fifty milliseconds of end-to-end freshness for every arrival. A simultaneous batch on one serial worker has last completion at $2{,}500\,\mathrm s$ and mean $1{,}250.025\,\mathrm s$, before preparation/publishing. At a uniform daily rate, arrivals average $0.578704\,\mathrm{s^{-1}}$ and nominal utilization is $2.893519\%$, but burstiness can still create queues. The $34{,}320/0.05=686{,}400$ job/service ratio is not an SLA speedup. The initial fp32 row payload is $30.72\,\mathrm{GB}$. Exhaustive scoring needs $1.536\times10^{10}$ dot-product FLOPs and a $15.058824\,\mathrm{ms}$ read component at $2.04\,\mathrm{TB/s}$, excluding query encoding, output selection and other serving work. This demonstrates a flat-read trade-off, not that every atomic design must use brute force. Configuration 3 uses an HNSW delta and weekly compaction. The HNSW delta uses $M=32,ef_{\mathrm{construction}}=200$. Their product does not determine actual visited distances; separately stipulate $6{,}400$ dot-product-equivalent distances per insertion. At $2d=1{,}536$ FLOPs each, graph-insertion work is $9{,}830{,}400$ FLOPs. At the stated $10^{10}\,\mathrm{FLOP/s}$ per core, that is $0.98304\,\mathrm{ms}$ per insertion and $49.152\,\mathrm s$ for the daily batch. These are arithmetic service proxies, not ingest or p99 freshness. Seven days add $350{,}000$ vectors: $3.5\%$ of the original base, or $3.381643\%$ of the resulting total. Their fp32 vector payload is $1.0752\,\mathrm{GB}$; base-layer links add up to $0.0896\,\mathrm{GB}$ under the same slot budget, sum $1.1648\,\mathrm{GB}$ before other overhead. An initial-size weekly refresh annualizes to $10.895238$ device-hours per day and $\$7{,}953.52$ per year. With net growth and fifty-two compactions after days seven through three hundred sixty-four, the same linear work proxy instead sums to $\$15{,}288.42$ for compaction, excluding delta serving, embedding, pseudo-queries and other costs. Daily graph insertion is $4.9152\times10^{11}$ FLOPs; the initial full refresh is $83{,}789{,}062.5$ times that graph-only work. Producing new vectors is not free: the separate $110\times10^6$-parameter, $256$-position encoder proxy adds $2.816\times10^{15}$ daily FLOPs, changing that scoped arithmetic ratio to about $14{,}622.447718$. These workloads have different learning goals and hardware costs, so neither ratio is an end-to-end price or latency speedup.

Sanity checks and decision rules

• The source reports Chinchilla $5.76\times10^{23}$ FLOPs; $6(7\times10^{10})(1.4\times10^{12})=5.88\times10^{23}$ is $2.083333\%$ above it. This decoder-training sanity check does not validate a sequence-to-sequence update estimate.
• Re-embedding all ten million documents with the stated encoder proxy costs $5.632\times10^{17}$ FLOPs, $469.333333\,\mathrm s$ or $7.822222$ minutes at the same idealized cluster throughput. The revised GenIR refresh is $73.125$ times that arithmetic. An unchanged document encoder can embed new documents only; a changed document encoder may require migration/re-embedding to keep one compatible index.
• Treat snapshot waiting, token preparation, evaluation, release and queues as part of freshness. A failed full-refresh SLA does not rule out every alternate update architecture.
• With two percent of the initial base added daily, a fortnight's delta is $28\%$ of that base, not a rival-sized full copy. With two percent compounded growth it is $31.947876\%$; reaching the original base size takes thirty-six whole days. The source's fortnight claim is incorrect under either interpretation.
• Frozen base/delta is one practical option. Validate merge quality, tombstones and compaction before choosing it over a conventional retriever or another continual-update method.
• New-only training offers no general preservation guarantee; rehearsal is a mitigation to evaluate, not proof of no forgetting. Atomic head indexing and semantic identifier stability have distinct costs.
• Measure p99 ingest-to-successful-retrieval under actual arrival bursts and queries. Never replace it with one insertion's arithmetic service time.
• Read-time ID blocking is logical exclusion, not deletion from model weights, logs, backups or every replica. Route revocable/private content according to actual retention and compliance requirements.

23.4 Recite-then-answer, and GenIR as RAG’s complement

Two stores can produce the same context object

An external datastore $D$ retains documents; weights $\theta$ encode learned behavior. A model that emits a docid still needs a content store to turn it into a retrieved passage. A reciter instead generates a passage-like string, which may be wrong or untraceable. Either can supply context set $C$ to a final generator, but they do not confer the same provenance. A smaller model plus external retrieval beating a larger model is a workload-dependent reported motivation, not a universal seven-billion-versus-seventy-billion substitution law.

Recitation converts continuation into temporary access

Autoregressive generation factorizes a string into next-token probabilities $p_\theta(x_t\mid x_{\lt t})$. A model can also directly answer a question from its prompt; it is not architecturally forced to reproduce all earlier tokens of a remembered source. The procedure analyzed here intentionally locates a passage beginning and generates forward. It is not a keyed database read, and its exact-continuation reliability is a property to measure rather than a certified source-access operation.

Recitation success has an exponential distance term

For a specified recitation-and-answer distribution, the law of total probability gives

Sampling recitations approximates expectations under that declared distribution; voting is a different aggregation rule, not exact marginalization. Locating a particular true passage start is event $G$, maintaining the chosen clean continuation to answer distance $L_{\mathrm{roll}}$ is $H$, and answering correctly after it is $J$. The path contribution obeys a conditional chain:

This is overall accuracy only under the further toy assumption that success on all other paths is zero. Correct answers can survive imperfect wording or arise without that entry path. A marginal average per-token accuracy does not by itself justify the power. At $\phi=0.995$, the clean factors are $0.995^{60}\approx0.740260958$ and $0.995^{200}\approx0.366957822$. Retrieval avoids generating every preceding token of a source, but has its own coverage, selection and extraction errors.

Retrieval and recitation cover different misses

Let $R$ and $S$ be retrieved-evidence and clean-recitation coverage events on the same query population. The exact union is

Only under independence does it reduce to $1-(1-R_1)(1-p_{\mathrm{loc}}\phi^{L_{\mathrm{roll}}})$. The marginal probabilities alone bound the union between $\max(\Pr R,\Pr S)$ and $\min(1,\Pr R+\Pr S)$. A fallback deployed only on retrieval misses needs measured $\Pr(S\mid R^c)$, not recitation accuracy averaged over all queries. Oracle zero-hit labels are not automatically available online; a no-evidence detector has its own errors. The source reports combining generated and retrieved documents in GenRead. That supports evaluating complementarity, not independence or a guaranteed union/answer gain. Adding noisy context can harm the final reader. Retained sources can supply fresh, private and attributable content when correctly indexed and controlled. A frozen model without new evidence offers no verified update channel; it can still infer or guess answers, so lack of freshness is not a blanket claim that every post-training fact is impossible to output. Keep origin labels and verify any cited source independently.

Worked recitation and retrieval comparison

These are constructed coverage and clean-answer scenarios, not reproduced Natural Questions measurements for a particular seven-billion-parameter model. Use $\phi=0.995,A=0.75$ and a separately reported DPR top-one-hundred hit rate $R_{100}=0.854$. The last number is not automatically the coverage of five passages in a final prompt. Configuration 1 is a head entity with recitation only. For the head example $p_{\mathrm{loc}}=0.70,L_{\mathrm{roll}}=60$, clean coverage is $0.70(0.995^{60})\approx0.518182670$ and the toy answer success is $0.388637003$, or $38.863700\%$. All later calculations use these unrounded inputs. Configuration 2 is a tail entity with recitation only. For the tail example $p_{\mathrm{loc}}=0.15,L_{\mathrm{roll}}=200$, clean coverage is $0.055043673$ and toy answer success $0.041282755$, or $4.128275\%$. The head/tail ratio is $9.414028$. Both location probability and distance changed, so this ratio is not an isolated distance or entity-popularity causal effect. Configuration 3 fuses retrieved and recited contexts. Using the head clean coverage and $R_{100}=0.854$ in the independence scenario gives union $0.929654670$, or $92.965467\%$, an absolute $7.565467$ percentage-point increase. Without an overlap estimate, the marginals permit anything from $85.4\%$ to $100\%$. This is coverage, not final exact match. For a five-item prompt chosen from one hundred, substitute $R_{\mathrm{context}}=R_{100}R_2(5\mid100)$, with conditional retention measured separately; the top-one-hundred number alone does not determine that union.

Voting depends on the error structure

Use five independent correctness indicators with common per-sample success $s=0.388637003$ from the unrounded head scenario. Then $K\sim\mathop{\mathrm{Binomial}}\nolimits(5,s)$. Suppose all correct outputs canonicalize to one answer. If every wrong answer is distinct, at least two correct copies form the unique plurality. With ties declared unsuccessful/abstained, success is

Uniformly breaking the five-way tie when exactly one sample is correct instead gives $0.697422098$. The tie rule therefore matters. If all incorrect samples name the same wrong alternative while correctness indicators remain IID, the correct answer needs a strict majority:

That is $9.063993$ percentage points below the single-sample success. This failure requires no correlation between correctness indicators: concentrated wrong labels suffice. With statistically correlated samples, the Binomial formulas no longer apply; perfectly shared successes/failures, for example, leave voting at single-sample accuracy. Measure aliases, abstention, ties, repeated wrong labels and dependence rather than asserting that correlation alone always makes voting harmful below one half.

Recitation is slower in the worked serving model

The separate serving proxy assumes one full fp16 seven-billion-parameter weight read, $14\,\mathrm{GB}$, for each generated token at $2.0\,\mathrm{TB/s}$. That stream component is $7\,\mathrm{ms/token}$: sixty sequential tokens give $420\,\mathrm{ms}$ and two hundred give $1{,}400\,\mathrm{ms}$. Batching, caches, arithmetic, KV traffic, input prefill and answer generation change actual cost; the stream number is not measured token latency. For another partial scenario, stipulate ANN service $10\,\mathrm{ms}$ and five retrieved chunks of $256$ positions. Their document-only prefill proxy is

The sum is $62.705882\,\mathrm{ms}$; $420/62.705882\approx6.697936$. This compares unlike partial context-production costs, not quality-matched measured request latencies. In particular, top-one-hundred DPR hit rate cannot be assigned to this five-chunk prompt without measuring truncation/reranking. Shared prompt/answer costs and reader behavior also need accounting.

Sanity checks and operating choices

• The source reports DPR Natural Questions exact match $41.5\%$. The constructed head example gives $38.863700\%$, numerically $2.636300$ points lower, but invented path probabilities and a different extraction assumption do not demonstrate competitive measured performance.
• $0.415/0.854\approx0.485948478$ is an effective ratio of the cited answer score to candidate coverage. It is not automatically a measured conditional clean-passage extraction rate: query populations, gold definitions, final-context retention and success without that gold matter.
• A catalog pasted into a prompt is not the same operation as generated-ID retrieval. Full attention can scale with that supplied context; caching and sparse attention change costs, so no universal linear per-request latency law follows.
• Use a validated no-evidence detector if routing recitation to misses. Test on the actual miss cohort, not only a head-heavy aggregate. Source availability and citation requirements still govern whether generated context is acceptable.
• The clean-path half-survival threshold is $L_{\mathrm{roll}}\le\ln(0.5)/\ln(0.995)\approx138.282573$, hence at most $138$ whole positions. It is not a theorem that half of all answers are wrong after that distance.
• Measure conditional continuation behavior on known source passages and test alternatives to a constant-probability model. Verify recited text against a retained source before making an attributable citation; do not invent citations from the recitation itself.
• Five recitations across two hundred queries is a source pilot heuristic, not a powered guarantee of benefit. Measure disagreement structure, canonicalization, tie handling and latency; keep one sample unless the intended aggregation shows benefit with uncertainty.
• In a fixed $400{,}000$-document population, $12{,}000$ revisions per week is $3\%$. Under independent uniform weekly hazards and no refresh, the expected fraction touched at least once after thirteen weeks is $1-0.97^{13}\approx32.697291\%$. Repeatedly changing the same documents or disjoint weekly sets gives different fractions; document revisions are not automatically the fraction of facts or queries answered incorrectly.
• For changing internal content, retain an updatable, access-controlled source system. Consider generated-context fallback only when its measured benefit and evidence limitations meet the use case.

Diagrams

Figure 23.1

Diagram description and source

flowchart TD
    q[query q]
    s0((0))
    s3((3))
    s7((7))
    s31((1))
    s38((8))
    s35((5))
    s314((4))
    s319((9))
    d314[doc 3 1 4]
    d319[doc 3 1 9]
    invalid[no document carries prefix 3 5]
    q -->|step 1, lower score| s0
    q ==>|step 1, beam keeps| s3
    q -->|step 1, lower score| s7
    s3 ==>|step 2, beam keeps| s31
    s3 -->|step 2, lower score| s38
    s3 -.->|trie has no child| s35
    s35 -.-> invalid
    s31 ==>|step 3, beam keeps| s314
    s31 -->|step 3, lower score| s319
    s314 --> d314
    s319 --> d319

Figure $23.1$: A trie masks unregistered continuations. The highlighted path illustrates one accepted identifier, not an exact global top-beam guarantee. For fixed-length IDs, $L_{\mathrm{id}}\ge\lceil\log_VN\rceil$; a balanced decimal assignment can reach seven at $N=8.8\times10^6$. A semantic tree may be deeper. This ID stage touches weights and external constraints; returning passage text still needs the mapping and content store.

Figure 23.2

The following are component models, not measured latency curves:

Figure $23.2$: Stored-bit parity compares footprints, not learned information or a retrieval-quality ceiling. The integer-list PQ lookup component excludes separately counted centroid work and LUT construction. The decoder stream includes neither complete query compute nor real service overhead. Devices and resource denominators differ. Identifier length grows in steps with the minimum fixed-length space; it is not flat in corpus size for all designs.

Figure 23.3

Figure $23.3$: Addressable index records make local updates possible, but graph traversal and storage overhead are not fixed by a symbolic complexity label. Shared learned updates can interfere with old behavior without touching every parameter. A frozen-base/delta system is one way to isolate serving changes; atomic rows and other modular designs provide different trade-offs. Validate freshness and preservation rather than claiming every generative insertion is necessarily global.

Figure 23.4

Diagram description and source

flowchart TD
    Q["Query"] --> R["Retrieve retained source passages"]
    Q --> S["Generate an unverified recitation"]
    R --> C["Context with explicit origin and access/provenance metadata"]
    S --> C
    C --> G["Answer and verify attributable claims against actual sources"]
    S --> V["Measure clean entry, continuation, extraction and failures outside that path"]

Figure $23.4$: Recitation is one context producer, not the only way an autoregressive model can express learned facts. Its specified clean-path contribution is $p_{\mathrm{loc}}\phi^{L_{\mathrm{roll}}}A$ only under equal conditional survival and extraction assumptions. The exact coverage union uses miss-conditional recitation success; independence is a special case. Union coverage does not guarantee improved final answers, and generated text alone is not attributable evidence.

Whiteboard pack

What to draw

1. Draw separate ID generation, ID-to-document mapping and passage fetch stages.
2. Contrast the added atomic head $N d_{\mathrm{model}}$ with structured identifiers and their external constraints.
3. Draw a trie mask and label it validity, not relevance or globally exact top-k.
4. Write $L_{\mathrm{id}}\ge\lceil\log_VN\rceil$ for fixed-length identifiers; state the balance/assignment assumptions behind equality.
5. Separate encoder work, decoder weight traffic, beam work, auxiliary memory and actual hardware capacity.
6. Compare stored-bit budgets $b_wP/N$ and $\kappa_{\mathrm{idx}}$, explicitly not a quality theorem.
7. Add a frozen base, mutable delta, merge policy and separately priced compaction as one update option.
8. Price inputs and identifier targets, then add snapshot waits, queues and deployment to freshness.
9. Draw a recitation branch with $p_{\mathrm{loc}}\phi^{L_{\mathrm{roll}}}A$ labeled clean-path model.
10. Use $\Pr(R)+(1-\Pr R)\Pr(S\mid R^c)$ for union coverage; annotate independence only when assumed.
11. Mark generated context unverified until checked against an actual source. Measure final answer quality and voting ties/dependence.

Spoken script

Generating IDs relocates part of search, not the document store or every index structure. Atomic heads are large flat classifiers; semantic IDs trade a smaller alphabet for sequential decisions and constraint storage. Minimum identifier length is not an achieved latency guarantee, and stored bytes do not prove a quality ceiling. Measure model quality, full footprint and update behavior together. Shared updates risk interference, but not every insertion must rewrite every parameter. A frozen base and mutable delta is one practical option. Recitation can produce extra context, particularly on some retrieval misses, but exact-continuation decay is a conditional model rather than a universal limit on answering. Preserve origin labels and ground citations in retained, verified sources.

Interview traps

1. Where did the index go when the model generates document IDs?

An exhaustive atomic head adds $N d_{\mathrm{model}}$ learned weights and scores every row; an ANN approximation can index those rows if desired. Structured identifiers distribute work across learned token decisions and an external constraint/mapping structure. Neither design eliminates the content store needed to fetch passages, and model-only byte counts omit that auxiliary footprint.

2. Why can generated IDs be invalid, and what does a trie actually guarantee?

There are $V^{L_{\mathrm{id}}}$ fixed-length strings but only the registered subset names documents. Correct trie masking plus termination can guarantee membership in that subset, not relevance, freshness, successful content fetch or globally exact top-k ranking. The unused-code fraction is not the decoder's measured error probability. Variable-length IDs and corpus substrings require their own stopping and document-aggregation rules.

3. Is generative retrieval constant time, and where does its quality ceiling come from?

Fixed-length identifiers need at least $\lceil\log_VN\rceil$ symbols, but semantic-tree balance and assignment determine actual depth. Compute, weights, KV traffic, beam work and constraints determine real query cost. The ratio $b_wP/N$ is nominal stored payload per document; its equality with a PQ code size is not a necessary or sufficient retrieval-quality condition. Report empirical scaling instead of converting byte parity into a rejection theorem.

4. What happens when new documents arrive?

New IDs excluded by the frozen constraint have zero recall on that path. Registering a new ID removes that structural exclusion but does not create reliable learned relevance. Shared updates can interfere without necessarily modifying every parameter or always forgetting. Frozen features plus atomic rows, rehearsal, modular methods and base/delta designs offer different trade-offs. Measure old/new quality, snapshot waits, queues and release freshness; one service-time number is not an ingest SLA.

5. When should recite-then-answer complement retrieval, and when should it not?

Evaluate generated-context fallback on the actual detected no-evidence cohort. A clean-continuation model can decay as $\phi^{L_{\mathrm{roll}}}$ under constant conditional faithfulness, but total answer accuracy need not obey it, and coverage events need not be independent. Retained sources support verified freshness, access control and citations. Recitation alone supplies none of those guarantees; if verified against an actual source, cite that source rather than an invented provenance trail. Voting benefit depends on wrong-answer identities, ties and sample dependence.

Key numbers