# W03 Lecture Notes — Discovery, Indexing, and Retrieval

## 1. The opening distinction: eligible is not retrieved

Suppose a public page returns a successful HTTP response, appears in a sitemap, and allows an identified crawler under the applicable policy. Has the page become visible in a generated answer? No. We have several observations about possible acquisition, but no observation of index membership, query matching, candidate rank, context inclusion, attribution, or answer use. The scientific task in W03 is to keep those events separate.

A useful stage vocabulary is: **discover**, **fetch**, **parse and represent**, **index**, **retrieve**, **rerank or select**, and **generate or attribute**. These labels are an analytical decomposition, not a claim that every production system implements the same modules. An open sandbox may expose every transition. A closed answer product may expose only a request and rendered response. Between those endpoints, the correct value for an unobserved candidate count is `unknown`, not a number inferred from the final answer.

This distinction changes the research question. “Why is our page invisible?” is too broad because it has no stage, comparator, query distribution, observation window, or event definition. A bounded question might be: “In the frozen ten-document teaching corpus, under the declared tokenizer and BM25 parameters, does document D-010 enter the top three for topic T-03, and what labeled-relevant fraction is recovered?” The bounded version is less glamorous and more answerable.

**Checkpoint A.** A page is fetched once by an owned test crawler. Name two conclusions supported by that record and four later-stage conclusions it cannot support.

## 2. A funnel whose denominators are not interchangeable

Let a declared source population contain 1,000 URLs. An owned crawler discovers 760 under a frozen protocol, requests 700, receives 650 usable responses, parses 610 representations, and admits 570 to an index. For one query, the retriever returns 100 candidates and a downstream selector uses 8 passages. Each ratio answers a different question.

- Discovery coverage may use 760/1,000, if the 1,000-URL population is itself justified.
- Fetch success may use 650/700, not 650/1,000, when the estimand is conditional on attempted requests.
- Index admission may use 570/610 if the policy decision applies to parsed representations.
- Candidate exposure for one query may use membership in the retrieved 100; it is not a corpus-wide percentage.
- Context inclusion may use 8/100 only for that candidate set and selector budget.

Changing a denominator changes the statement. If the 1,000 URLs were compiled after seeing what the crawler found, discovery coverage is circular. If a source appears as several passages, a document denominator and a passage denominator diverge. If robots rules or authorization prohibit a request, “not fetched” must not be silently grouped with network failure. A funnel is therefore a provenance table, not only a narrowing picture.

The most important closed-system discipline is to resist filling the funnel from surface outputs. Observing that one source is cited does not reveal how many sources were indexed, how many candidates were considered, whether the source came from retrieval, or whether a separate citation layer added the link. Repeated observations can characterize the visible response distribution under recorded conditions. They do not, by themselves, identify the hidden denominator.

**Checkpoint B.** Why is “8 selected passages out of 570 indexed documents” generally a poor estimate of selection rate? State the missing conditioning information.

## 3. Discovery, fetching, representation, and index membership

Discovery is obtaining an address or source identity that could be considered for acquisition. Links, submitted maps, feeds, curated lists, repositories, and prior crawls can support discovery. A discovery signal is not a command to fetch and not proof that an external crawler saw it. Fetching is an attempted retrieval of bytes under an identity, time, request configuration, policy, and authorization boundary. A status code alone is incomplete: redirects, content negotiation, authentication, locale, user agent, cache state, and rendered versus raw content can change the obtained representation.

Parsing and representation transform acquired material into indexable units. HTML may become visible text, fields, passages, metadata, link edges, or structured records. A client-rendered section may be absent from a raw response but present after an authorized rendering step. Canonicalization may consolidate representations. Language detection, segmentation, boilerplate removal, field weighting, and truncation can alter which evidence survives. These operations are observable only when we control or instrument them; a public interface does not reveal a closed product’s representation choices.

An index is a data structure and a policy boundary. “Index eligible” means a representation satisfies declared conditions for possible admission. “Indexed” means it is present in a particular index snapshot under a particular identity. “Retrievable” means a query and retrieval configuration can produce it, often within a cutoff. None of these is permanent. An index can be stale, sharded, filtered, language-specific, or rebuilt. The same public page can yield multiple stored representations.

For empirical work, freeze the smallest adequate identity record: source identifier, source version or capture time, acquisition method, rights, content hash, parser version, tokenization, document or passage identity, index build time, and exclusion reason. In a course fixture, all of these can be explicit. On an outside platform, record only what is observable and state the gap.

**Checkpoint C.** Classify each item as a discovery signal, fetch observation, representation decision, index observation, or unknown closed-platform event: sitemap entry; HTTP 200 captured by your crawler; removing navigation boilerplate; local index manifest lists D-007; public answer omits the page.

## 4. The inverted index as an inspectable candidate mechanism

A small lexical retriever can be understood through an inverted index. Instead of scanning every document for every query, the system maps each token to a postings list of document identities and, often, term frequencies or positions. For a corpus with documents A, B, and C, the postings for `retrieval` might be `[(A,2),(C,1)]`. The document frequency is two because the term appears in two documents, regardless of how often it repeats inside A.

Tokenization is part of the method. Lowercasing, punctuation splitting, Unicode normalization, stemming, stop-word handling, numbers, hyphens, Chinese segmentation, and field boundaries can all change postings. Therefore an “exact keyword” is not exact until the tokenizer is named. The L03 route uses a deliberately simple lowercase English-oriented tokenization. That makes the computation inspectable, not linguistically universal.

At query time, postings identify documents containing query terms. A scoring function combines evidence such as term rarity, within-document frequency, and document length. A lexical candidate miss can arise because the relevant concept uses different wording, the relevant representation was truncated, the tokenizer split terms unexpectedly, the document was never indexed, or the cutoff was too shallow. These are different failure classes. Looking only at the final score conceals them.

An inverted index is especially valuable pedagogically because a learner can trace every contributing term. That trace should not be overextended. A commercial or research system may combine fields, links, recency, learned representations, filters, or multiple retrieval passes. W03 uses an inverted index to teach candidate mechanics and diagnostics, not to reverse-engineer a closed product.

## 5. BM25: a reproducible lexical baseline

BM25 is a family of lexical scoring conventions. For the positive-IDF convention used in the Core Notes bridge and L03, let the corpus contain `N` documents. For query term `t` and document `d`, let `f(t,d)` be term frequency, `|d|` document length, `avgdl` mean document length, and `n_t` the number of documents containing the term. Then:

\[
IDF(t)=\log\left(1+\frac{N-n_t+0.5}{n_t+0.5}\right)
\]

and

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

The factor involving `f(t,d)` saturates: a fourth repetition normally adds less than the first. Parameter `k1` controls that saturation. Parameter `b` controls how strongly document length changes the denominator. With `b=0`, the formula does not normalize by length; with larger `b`, a term occurrence in a short document may receive more weight than the same count in a long document, all else equal.

Use the Core Notes micro-example. There are three documents, mean length 100, and a term appears in two documents. The positive IDF is approximately 0.470. With `k1=1.2` and `b=0.75`, document A has length 100 and three occurrences; document B has length 50 and one occurrence. The term contribution is approximately 0.738 for A and 0.591 for B. A ranks higher under this exact convention. The calculation does not establish that A is truer, more authoritative, easier to cite, or more likely to appear in a generated answer.

Several implementation choices belong in the manifest: log base and IDF form, treatment of absent or repeated query terms, field weights, tokenizer, average-length scope, index snapshot, `k1`, `b`, tie policy, cutoff, and score precision. Scores should normally be compared within one query and one locked index. Different queries activate terms with different document frequencies, so a raw score is not an absolute relevance probability.

BM25 is included because it creates an interpretable error surface. It can reveal rare entity names, exact dates, or query wording that a learned representation may treat differently. It can also miss paraphrases. “Baseline” means a reference under a protocol, not an inferior system and not a production recommendation.

**Checkpoint D.** If `n_t` increases while the corpus size remains fixed, what happens to the stated IDF? Why does that not mean the term became less important in the world?

## 6. Qrels, Recall@k, and the candidate ceiling

A qrel is a query–document judgment record, usually with a relevance value. It is not ground truth without qualification. The assessor population, instruction, unit, pooling method, adjudication, date, and incompleteness all matter. In the closed L03 fixture, unlisted topic–document pairs are treated as gain zero for the exercise. That policy is acceptable only because it is declared and the corpus is tiny. In open evaluation, unjudged often means unknown rather than irrelevant.

For query `q`, let `Rel(q)` be the declared relevant set and `R_k(q)` the top-k retrieved set. Binary Recall@k is:

\[
Recall@k(q)=\frac{|R_k(q)\cap Rel(q)|}{|Rel(q)|}.
\]

If T-03 has three relevant documents—D-005, D-006, and D-010—and BM25 top three are D-005, D-006, and D-008, then Recall@3 is 2/3. D-010 is a candidate miss at cutoff three. D-008 occupying rank three is not automatically “bad” in the world; it is nonrelevant under this fixture’s declared qrels.

Candidate recall creates a ceiling for later stages operating only on that set. A reranker restricted to the three BM25 candidates cannot promote D-010 because D-010 is absent. It can reorder D-005, D-006, and D-008, but the relevant-set coverage stays at most 2/3. A deeper candidate set may include D-010, allowing a fixed-set reranker to surface it. That is why every claim needs the candidate depth.

Recall ignores ordering among recovered relevant documents. NDCG adds graded relevance and position under a declared gain and discount convention. W04 develops ranking and context-selection consequences further. In W03, the key diagnostic is whether the relevant representation was eligible for the next stage at all.

Macro recall averages topic values, giving each topic equal weight. Micro aggregation may weight topics by their numbers of relevant documents. Neither is universally correct. Report the aggregation rule and inspect topic-level rows before celebrating the mean. A gain on two easy topics can hide a complete miss on a critical stratum.

**Checkpoint E.** A reranker improves NDCG@3 but Recall@3 is unchanged. What stage changed, and what did not become possible?

## 7. Dense and hybrid retrieval without invented identities

Dense retrieval represents queries and candidates as vectors and scores their geometry. It can recover semantic relations with little exact-term overlap, but its behavior depends on model identity, checkpoint, training data, pooling, text window, normalization, language, domain, and index build. Similarity is not entailment or source quality.

The L03 `frozen_dense_run.tsv` is intentionally more constrained: its values are authored synthetic scores. Metadata explicitly states `model_identity: none`. Therefore it is correct to say, “the supplied opaque run retrieves D-010 for T-03 at rank two.” It is incorrect to say, “a dense encoder outperforms BM25,” because no encoder was run. The fixture teaches how to analyze a second score stream under a claim ceiling.

Hybrid retrieval combines streams. Raw addition can be meaningless when scales differ. L03 performs per-topic min–max normalization and interpolates with declared `hybrid_alpha=0.55`. Other systems may calibrate scores, learn fusion, or fuse ranks. Reciprocal-rank fusion is another inspectable method because it uses ranks rather than pretending raw scores share units. Every fusion rule can fail; overlap between lists is not independent evidence when documents or sources derive from one another.

In the standard L03 run at `k=3`, the frozen opaque and hybrid methods recover all three T-03 relevant documents. Macro Recall@3 rises from BM25’s 0.8889 to 1.0000. Hybrid macro NDCG@3 is about 0.8884 versus BM25’s 0.8560. These values describe three topics and ten synthetic documents. They do not rank retriever families or predict any platform. More importantly, hybrid T-02 still places D-009 first, an unsupported promotional record labeled nonrelevant, producing NDCG@3 about 0.6653. Aggregate improvement has not removed a topic-level ordering problem.

## 8. Open-sandbox observations versus closed-platform inference

An open sandbox supports strong statements about its own execution: which bytes were inputs, how they were tokenized, which documents were indexed, what parameters were used, which candidates were returned, how metrics were calculated, and whether a second run reproduced the hashes. Those statements can be independently checked if the bundle is complete.

A closed platform permits a narrower observation: under a recorded surface, locale, account state, time, and exact query, the rendered response contained or omitted a source, claim, or citation. Repetition can estimate variability of that visible event for the sampled protocol. It cannot reveal the complete indexed universe or prove why an omission occurred. Alternative explanations include acquisition delay, representation differences, query rewrite, candidate cutoff, ranking, context budget, generation, citation-interface behavior, experimentation, personalization, or ordinary stochastic variation.

Do not treat an open proxy as a hidden-system measurement. If an owned BM25 index retrieves a page, the defensible conclusion is that the representation is lexically retrievable in the owned index under the query and protocol. The result can motivate a hypothesis about wording or representation. It does not prove inclusion in another index or causal influence on another answer surface.

This is not a reason to abandon measurement. It is a reason to align claims with observation. Open-system experiments can test mechanisms under controlled conditions. Closed-surface panels can characterize observable outcomes. The two designs become informative together when their bridge assumptions are explicit rather than smuggled into a single “visibility score.”

## 9. Failure diagnosis by stage

Use a stage-first error table:

| Failure class | Evidence needed | Valid next test | Invalid shortcut |
|---|---|---|---|
| Corpus absence | frozen corpus identity and document search | audit acquisition and representation | repeat the same query and blame ranking |
| Representation mismatch | source bytes, parsed fields, tokenizer trace | compare lawful representations under one changed factor | infer a closed parser from a screenshot |
| Candidate miss | qrels, full candidate list, cutoff | deepen or alter first-stage retrieval under a frozen task | rerank a set that lacks the item |
| Ordering error | fixed candidate set and relevance labels | rerank while proving set invariance | change retrieval and reranking together |
| Judgment gap | assessor record and unjudged items | adjudicate under a preregistered rule | relabel after seeing metric movement |
| Downstream omission | fixed ranking and selector trace | test context selection in an open system | call it a retrieval failure without trace |

For T-03 in L03, D-010 is relevant but outside BM25’s top three. At cutoff three, that is a candidate miss. For T-02, BM25 and hybrid both recover D-003 and D-004, so Recall@3 is one. Yet D-009 ranks first and the graded ordering score is lower. That is an ordering problem under the qrels, not a candidate-coverage problem. Calling both “retrieval quality” loses the actionable distinction.

Preserve negative and null results. A hybrid list can worsen because normalization, fusion weight, shallow component lists, domain mismatch, or noise changes ordering. The correct response is topic-level diagnosis, not changing qrels or hiding the delta. If the method identity is opaque, the interpretation remains correspondingly bounded.

## 10. A defensible W03 conclusion

A high-quality conclusion has four clauses:

1. **Scope:** name corpus, topics, index or run identities, time, parameters, cutoff, and judgment policy.
2. **Observation:** report per-topic and aggregate results without converting scores into probabilities.
3. **Diagnosis:** locate at least one difference at candidate generation or ordering, and identify what was held fixed.
4. **Boundary:** name later stages and external systems not evaluated.

For example: “In the immutable L03 ten-document synthetic corpus, with three declared topics, positive-IDF BM25 (`k1=1.2`, `b=0.75`), and unlisted pairs treated as gain zero, BM25 recovered 2/3 labeled-relevant T-03 documents at cutoff three. The supplied opaque run included D-010 and achieved 3/3 for that topic; because its scores are authored and have no model identity, the difference supports a candidate-set exercise only. Crawling, production indexing, context selection, generation, citation, absorption, and user outcomes were not evaluated.”

That paragraph is useful precisely because it refuses several tempting conclusions. It does not say dense retrieval is generally better, the page necessarily receives a citation, or a platform should behave similarly. It makes the experimental object reconstructable and leaves W04 with the right question: once a source is in the candidate set, why does its ordering and selection change?

## 11. Discussion prompts, summary, and exit test

1. When is a successful fetch a relevant denominator, and when is it merely an implementation trace?
2. Could a document have a high BM25 score and be poor evidence? Give two mechanisms.
3. Why can Recall@k increase while NDCG@k decreases?
4. What extra information would turn an unjudged document from “unknown” into an admissible relevance label?
5. Design one open-sandbox experiment and one closed-surface observation that address related questions without pretending they estimate the same stage.
6. Which tokenization choices are most consequential for a multilingual GEO study?

The central W03 lesson is short: **candidate access is a sequence of conditional events, and each event needs its own evidence and denominator**. Discovery is not fetching. Fetching is not index membership. Index membership is not top-k retrieval. Retrieval is not context inclusion. Context inclusion is not faithful use or attribution. BM25 supplies an inspectable lexical baseline under one frozen corpus; qrels and Recall@k expose candidate coverage; dense and hybrid routes introduce complementary retrieval evidence only under named identities and fusion rules.

**Exit test.** Write two sentences. Sentence one must state one result you can defend from the L03 sandbox, including cutoff and denominator. Sentence two must name the strongest closed-platform or downstream claim that the result does not establish. If either sentence uses “visibility” without an event definition, revise it.