What must survive corpus design, ranking, and approximation before a useful passage can become evidence?
# The Shape of a Search
*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](https://openreview.net/forum?id=fUtxNAKpdV) showed the power of image-to-markup parsing for scientific documents, while the 2026 study [When Good OCR Is Not Enough](https://aclanthology.org/2026.acl-industry.60/) 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](https://doi.org/10.1108/eb026526) 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](https://doi.org/10.1145/361219.361220) 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](https://doi.org/10.1002/asi.4630270302)).
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](https://pages.nist.gov/trec-browser/trec3/proceedings/). 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](https://arxiv.org/abs/1410.3916) placed statements in
addressable slots and made one or more hard reads before answering.
[End-To-End Memory Networks](https://proceedings.neurips.cc/paper/2015/hash/8fb21ee7a2207526da55a679f0332de2-Abstract.html)
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](https://aclanthology.org/P17-1171/) 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](https://aclanthology.org/P19-1612/) 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](https://aclanthology.org/2020.emnlp-main.550/) 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](https://aclanthology.org/2022.naacl-main.272/)
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.