The Shape of a Search

What must survive corpus design, ranking, and approximation before a useful passage can become evidence?

Field notes on ranking, memory, and the making of evidence

Retrieval begins before the query arrives. It begins when someone decides what counts as a document, which boundaries will survive parsing, whether a title is part of the body, whether an identifier is a word, and which version of a page is allowed to answer a question. By the time a search box appears, most of the system's epistemology has already been built into its units and indexes.

That is easy to forget in the age of vector databases. A vector store looks like the center of a retrieval system because it is the component we can point at. Historically and technically, however, retrieval is a more interesting problem: given a finite budget, arrange imperfect candidates so that the evidence needed downstream is likely to survive. The index, the score, the chunk, the approximate search algorithm, and the final fusion rule all take part in that arrangement.

This chapter follows that arrangement from term statistics to dense and token-level representations, then outward into the machinery that makes those representations useful. The path is not a sequence in which each new technique abolishes the old one. It is a widening vocabulary of failure modes.

1. A collection acquires a memory

Before ranking can fail, the collection can fail to remember. A connector may never discover an attachment. Pagination may stop at the first thousand records. A crawler may preserve the navigation shell and discard the article. An incremental feed may deliver an update before the version it updates. A permission inherited from a parent folder may vanish while the text survives. Each of these becomes a retrieval miss later, but none can be repaired by changing an embedding.

The corpus should therefore be treated as a sequence of auditable states rather than a folder of convenient strings. A useful source record binds a stable logical identity to an exact upstream version and the bytes actually observed:

d=(id,source,source\_version,bytes\_hash,observed\_at, valid\_from,valid\_to,acl,license,parser\_version,content).

Those fields answer different questions. The logical ID tells us that two revisions belong to the same source. The source version, ETag, filing accession, commit, or content hash tells us which revision entered this index. Observed time tells us when the pipeline learned it; valid time tells us when its statements apply. An access policy says who may cross the boundary. License, retention, and data classification determine whether the source may be transformed, quoted, logged, used for evaluation, or sent to a remote embedding service. The parser version explains how raw bytes became evidence.

Immutable raw objects and a release manifest make that chain replayable. The manifest records connector watermarks, raw hashes, parser and OCR versions, normalization and deduplication policy, chunker, enrichment, embedding model and tokenizer, index algorithm and parameters, counts, ACL partitioning, parent release, and tombstones. A vector-store row is a derivative, not the surviving identity of the source. Chunks, embeddings, summaries, table rows, graph edges, and qrels should all point backward to the logical ID and exact source version from which they came.

Connectors deserve the same tests as retrieval. A full scan establishes the authoritative item count; an incremental watermark keeps it current; periodic reconciliation reveals silent omissions. Because exactly-once delivery is rare, processing should be idempotent under a key such as source identity, source version, and transformation version. Retries must not manufacture duplicate evidence. A malformed document belongs in a visible dead-letter queue with a reason and recovery path, not in a quiet hole in the knowledge base. Updates and deletions are not complete until raw storage, manifests, derived artifacts, indexes, caches, summaries, and graph edges agree.

Then bytes have to become structure. Plain text is the easy case. HTML carries headings, lists, links, tables, hidden nodes, and boilerplate; destroying the tree too early destroys context. PDF is not a stream of paragraphs but positioned glyphs and drawing commands. A robust path validates the file in isolation, compares native extraction with page rendering, invokes OCR where necessary, identifies regions, reconstructs reading order, recognizes headings, lists, tables, formulas, figures and captions, removes repeated furniture cautiously, and preserves page coordinates plus character offsets. Nougat showed the power of image-to-markup parsing for scientific documents, while the 2026 study When Good OCR Is Not Enough showed why low character error can still produce poor RAG when structural and semantic relations are broken.

The canonical evidence copy should remain conservative. Unicode may be normalized with an offset map, but punctuation, case, layout, units, negation, and identifiers should not disappear merely because a retrieval view prefers simpler text. A table should survive as headers, rows, cells, spans, units, footnotes, page region, and extraction confidence; row strings and summaries may be derived for retrieval. A figure should keep its original region, caption, nearby references, and any extracted data. A transcript should keep speakers and time ranges. Code should keep its commit, path, syntax boundaries, imports, references, and tests. Generated descriptions are useful derived evidence and dangerous substitutes for the original.

Deduplication also carries epistemic meaning. Byte-identical objects can usually collapse safely. Near duplicates might be harmless syndication, a later correction, independent corroboration, or an attacker repeating a poisoned claim until rank fusion mistakes frequency for authority. Preserve a cluster identity and the relation among versions rather than deleting similarity without explanation. The same care applies to source authority: ten copied pages do not become ten independent witnesses.

A deletion is the most revealing corpus test. The source may be gone while its chunk remains in an ANN segment, its sentence survives in a hierarchical summary, its entity persists in a graph, its answer sits in a semantic cache, or its text appears in an evaluation trace. Tombstones need stable identities, release semantics, and a measurable propagation SLO across every derivative. Access revocation is similarly temporal: authorization must be resolved before candidate material reaches a reranker, model provider, log, or cache, not applied cosmetically to the final answer.

Corpus evaluation begins before question answering. Sample connector completeness against authoritative counts. Measure ingestion lag and deletion backlog. Keep golden documents for reading order, headings, tables, footnotes, formulas, scans, multilingual text, and code. Compare parser versions at block and span level, then follow their effect into retrieval and claim-level answers. Record missing-source, parse-loss, structure-loss, permission-loss, and version-loss separately. Only then does “the retriever missed” mean the evidence was present in a form the retriever could actually find.

The corpus is the system's memory, but a memory without lineage cannot explain itself, and a memory without deletion cannot be governed.

2. Before semantics had an embedding

The classical foundations of information retrieval supplied three ideas that remain visible in modern RAG systems. Karen Spärck Jones's term-specificity account made rarity informative: a term occurring in only a few documents distinguishes those documents more sharply than a term appearing everywhere. The vector-space model made queries and documents comparable as weighted term vectors. Robertson and Spärck Jones then gave relevance weighting a probabilistic form, asking how the presence of a term changes the odds that a document is relevant (1976 paper).

With $N$ documents, $n_t$ containing term $t$ , $R$ documents judged relevant, and $r_t$ relevant documents containing the term, their weight can be written

\log \frac{(r_t+0.5)/(R-r_t+0.5)} {(n_t-r_t+0.5)/(N-n_t-R+r_t+0.5)}.

When relevance judgments are absent, the expression becomes an IDF-like prior: rarity stands in for discriminative power. This is not “mere keyword search.” It is a compact model of what a collection says about its own vocabulary.

The corresponding systems invention was the inverted index. Instead of scanning every document, the engine stores a postings list for each term: document identifiers, frequencies, positions, perhaps fields and impact scores. Phrase and proximity queries follow naturally. So do filters over dates, tenants, products, and access-control domains. Compressed postings and upper-bound algorithms such as WAND and Block-Max WAND allow the engine to skip candidates that cannot enter the current top set. A small teaching loop over every document may compute the same formula; it is not yet a search engine.

3. BM25, a disciplined compromise

BM25 grew from the Okapi experiments reported at TREC-3. In a common form,

\operatorname{BM25}(q,d)= \sum_{t\in q}\operatorname{IDF}(t) \frac{(k_1+1)f(t,d)} {f(t,d)+k_1(1-b+b|d|/\operatorname{avgdl})}.

The fraction encodes two practical judgments. First, term frequency should saturate: the tenth occurrence is not worth ten times the first. The parameter $k_1$ controls how quickly it saturates. Second, long documents create more opportunities for accidental matches. The parameter $b$ controls how strongly length is normalized against the collection average.

These judgments make BM25 unusually durable. It protects rare names, error codes, legal citations, chemical symbols, product versions, and quoted phrases that semantic encoders may blur. It can be inspected: one can see which terms contributed, which field they came from, and how length changed the score. It can also be updated incrementally without re-encoding an entire corpus.

BM25 is not one immutable recipe. A title, a support ticket, a table row, and a long policy section do not share a useful length distribution. Fielded BM25 keeps title and body statistics separate; variants alter the treatment of long documents or proximity. Tuning belongs to the retrieval unit, not to a folklore pair of $k_1$ and $b$ values.

Nor should the historical record be simplified into a clean “BM25 gain.” The original Okapi TREC-3 run combined weighting with passage retrieval, expansion, and routing changes. The experiment does not isolate a portable improvement that can be pasted onto a modern benchmark.

In practice, this makes ordinary BM25 more than a baseline to defeat. It is a diagnostic instrument. If a learned retriever loses queries containing exact identifiers, the lexical run shows the missing behavior. If a dense model gains recall only by returning many semantically similar duplicates, the postings run helps expose the difference between topicality and evidence coverage. If a chunking change alters document lengths, BM25 makes that distribution shift visible through a familiar scoring mechanism. Keep its analyzer, fields, parameters, corpus snapshot, and candidate depth fixed when comparing another component; otherwise the “baseline” moves while the experiment is being read.

This also explains why preprocessing is part of the model. Lowercasing may be harmless for prose and destructive for case-sensitive identifiers. Stemming can join useful variants and merge terms that the domain carefully distinguishes. Stopword removal can erase a negation or a phrase boundary. A fielded index can place title, heading, body, and identifier channels under different statistics without literally duplicating text. The transparent lexical system is valuable precisely because these choices remain inspectable.

query terms
    |
    v
postings lists  --->  upper bounds  --->  fully score survivors
   rare term           skip safely          BM25 top-k

The weakness is equally clear. Exact terms do not automatically bridge “physician” and “doctor,” a paraphrase and its source wording, or a question and an answer whose salient words do not overlap. Pseudo-relevance feedback can borrow vocabulary from top documents, but an ambiguous first retrieval can pull the query toward the wrong sense. Neural sparse systems later learned contextual term weights and vocabulary expansion while retaining inverted-index serving. SPLADE, for example, maps contextual token logits into sparse vocabulary weights and regularizes the number of activated terms. Its existence is a useful correction to a lazy history: the field did not simply walk from sparse to dense.

4. The document becomes a point

The neural-memory lineage supplied a different intuition. The original Memory Networks placed statements in addressable slots and made one or more hard reads before answering. End-To-End Memory Networks replaced hard selection with soft attention so the answer loss could train the reads. Those memories were small by search-engine standards, but they made an important conceptual move: evidence could be an external, repeatedly readable state rather than a fact compressed permanently into model parameters.

DrQA then treated Wikipedia as that external state at useful scale. Its retriever used hashed unigram and bigram TF-IDF over 5,075,182 articles from a December 2016 snapshot, returned five articles, and passed them to an extractive reader. On SQuAD, the reader alone reached 69.5 development exact match while the full open-domain system reached 27.1. The gap made the retrieval ceiling visible: a brilliant reader cannot extract an answer it never sees.

Dense retrieval changes the comparison space. A dual encoder produces one vector for a query and one for each passage,

u=E_q(q),\qquad v=E_d(d),\qquad s(q,d)=u^\top v,

and trains the positive passage to outrank negatives:

\mathcal L_i=-\log \frac{\exp(s(q_i,d_i^+)/\tau)} {\sum_{d\in D_i}\exp(s(q_i,d)/\tau)}.

The denominator is the curriculum. Random negatives are often too easy. In-batch negatives make every other positive in a batch do double duty. Lexical hard negatives teach the encoder not to mistake word overlap for answering the question. Neighbors mined from the current ANN index expose the model's own confusions. Change the negative distribution and one changes the task being learned.

ORQA showed how dense retrieval could be bootstrapped without question–passage labels. Its Inverse Cloze Task treated a sentence as a pseudo-query and its surrounding block as evidence, then fine-tuned through answer-string marginalization. It searched a little over 13 million Wikipedia blocks using 128-dimensional representations and an LSH maximum-inner-product index. The gains were revealing rather than universal: test exact match rose from a BM25+BERT baseline of 26.5 to 33.3 on Natural Questions, but fell from 33.2 to 20.2 on SQuAD. Dense similarity helped questions written as genuine information needs and struggled where dataset construction favored the source's exact language.

DPR made the dual-encoder recipe simpler and stronger: independent BERT-base towers, in-batch negatives, and a high-ranked BM25 passage without the answer as a hard negative. Its corpus was the 2018 Wikipedia split into exactly 21,015,324 non-overlapping 100-word passages, represented by 768-dimensional vectors and searched with FAISS/HNSW. DPR's top-20 answer-containing recall exceeded BM25 on Natural Questions, TriviaQA, WebQuestions, and CuratedTREC, but not on SQuAD, where 63.2 trailed 68.8. “Dense beats sparse” was never the result. “Dense supplies a powerful, complementary error surface” is closer.

The price of speed is compression. A long passage may contain several entities, relations, exceptions, and dates, yet a single vector must stand for all of them. Fine detail can be averaged away. Dot product also uses vector norm while cosine removes it; normalization, quantization, instruction prefixes, and dimension truncation can all change neighbor order. An embedding name is not a retrieval contract. The model revision, tokenizer, pooling, prefix, metric, precision, and chunk transform belong in the contract too.

5. Late interaction keeps the words in the room

A cross-encoder jointly reads query and document and can model negation and fine relationships, but it cannot economically score an entire large corpus. A dual encoder can search the corpus, but collapses each side too early. Late interaction occupies the ground between them.

ColBERT represents query and document tokens separately, then scores with MaxSim:

s(Q,D)=\sum_{i=1}^{m}\max_{j\in[1,n]}q_i^\top d_j.

Each query token finds its best document-token counterpart; document vectors remain precomputable. ColBERTv2 added denoised supervision and residual compression. Its centroid IDs and quantized residuals reduced token storage roughly six- to ten-fold from the original ColBERT, while the paper reported MS MARCO development MRR@10 of 0.397 and recall@1,000 of 0.984.

The bargain is explicit. A passage is no longer one point but many. Candidate generation, centroid routing, decompression, and exact MaxSim reranking become part of the system. Reporting only the embedding dimension conceals the real storage cost; one must report vectors and bytes per unit. Late interaction is often attractive as a reranker over a sparse–dense union, where its fine-grained matching is spent only on a manageable candidate set.

6. Approximation is inside the model boundary

Exact dense search computes every query–document score. It is valuable as an oracle on a representative slice, but its $O(Nm)$ cost per query becomes uncomfortable as $N$ grows. Approximate nearest-neighbor search buys latency and memory by accepting that some exact neighbors will be missed.

The major families embody different compromises. Inverted-file indexes cluster vectors and search only the nearest partitions; increasing the number of probed partitions improves recall and work together. Product quantization replaces subvectors with compact codebook entries, shrinking storage while distorting distances. HNSW constructs a layered navigable graph; larger connectivity and search breadth usually improve recall at greater memory, build time, and latency. DiskANN/Vamana and SPANN organize graph or posting structures around the realities of SSD access. ScaNN combines partitioning, anisotropic quantization for maximum inner product, and a final reordering stage.

None is “the vector index” in the abstract. Its parameters, filter behavior, cache warmth, deletion history, and hardware determine which evidence reaches the reader. A useful systems diagnostic is

\operatorname{ANNRecall@k}= \frac{|\operatorname{ANN}_k(q)\cap\operatorname{Exact}_k(q)|}{k}.

But even perfect ANN recall says only that approximation recovered the exact vector neighbors. It does not say those neighbors are relevant, sufficient, or true. Measure both ANN loss and task evidence recall, then inspect the effect on the answer.

Filters deserve their own benchmark. Pre-filtering may fragment graph connectivity; post-filtering may leave fewer than $k$ authorized results; iterated over-retrieval creates unpredictable tail latency. In a multitenant system, an inaccessible neighbor must not reach a reranker, a remote model, a cache, or even an observable result count.

7. A chunk is a theory of the future question

Before any index can succeed, the corpus must be cut into retrievable units. Fixed token windows are deterministic and inexpensive, but can separate a condition from its consequence or a table header from its row. Overlap repairs some boundary losses at the cost of storage and repeated prompt text, growing roughly by $w/(w-o)$ for window $w$ and overlap $o$ .

Structure-aware segmentation prefers sections, paragraphs, and sentences before falling back to tokens. It is a strong default when parsing is sound. Sentence-window retrieval indexes a precise center and expands to neighboring sentences for reading. Parent–child retrieval likewise searches small units but returns a larger containing section. Proposition indexing goes smaller still, which can sharpen claim matching and provenance while risking lost qualifiers and broken coreference. Contextual prefixes add titles or heading paths to otherwise ambiguous fragments; generated summaries can help, but must remain marked as derivatives rather than primary evidence.

There is no universally optimal chunk size because the evidence spans required by future questions are not yet known. The appropriate objective balances containment, retrievability, redundancy, and cost:

\max_U\; \alpha\,\operatorname{containment}(E,U) +\beta\,\operatorname{retrievability}(U) -\gamma\,\operatorname{redundancy}(U) -\delta\,\operatorname{cost}(U).

Evaluate chunkers on the corpus's real pathologies: definitions separated from exceptions, long lists, cross-section references, tables, code, scans, and multi-page evidence. Citation localization belongs in this evaluation. A chunk that retrieves well but cannot be mapped back to an exact source span has already spent some of the system's grounding budget.

8. Let unlike retrievers disagree

Sparse and dense retrieval fail differently. The sensible response is often to preserve both candidate lists, canonicalize their identities, collapse duplicate views, and fuse them.

Reciprocal-rank fusion avoids pretending that a BM25 score and a dot product share a scale:

\operatorname{RRF}(d)= \sum_r\frac{w_r}{K+\operatorname{rank}_r(d)}.

It is robust, not parameter-free. Retrieval depths, $K$ , weights, and near-duplicate flooding still matter. Score-level fusion requires declared normalization; min–max is sensitive to outliers, z-scores assume meaningful distributions, and a per-query softmax depends on temperature and pool depth. A learned router may shift budget toward lexical search for identifiers and toward dense search for paraphrases, but it should retain an exploration budget for routing mistakes.

                    +--> sparse postings ----+
question --> units -+--> dense ANN ----------+--> fuse --> rerank
                    +--> late interaction ---+              |
                                                             v
                                             deduplicate --> evidence set

Reranking then asks which candidates are individually relevant. Evidence selection asks the harder set question: do the survivors jointly cover the answer? Five paraphrases of one fact can occupy every top position while a second required hop disappears. Maximal marginal relevance introduces novelty; coverage objectives allocate a token budget across subquestions, source authority, and independence.

The useful diagnostic is not whether fusion improved an overall mean. Measure each retriever's unique relevant contribution, the oracle recall of their union, the duplicate rate, and what the reranker removed. If union recall rises but fused recall does not, the fusion rule is at fault. If the union itself adds nothing, the new retriever is merely an expensive echo.

Retrieval therefore ends not with the nearest passage, but with a deliberately constructed evidence set. Its members have identities, versions, spans, permissions, and scores whose meanings are kept separate. The next stage will decide whether the generator actually uses that set—or merely writes past it.