INFS7410 Revision Hub

Information Retrieval · Weeks 1–13 · Practicals · Projects

A1 ZH
Complete review map

From term matching to evidence-grounded generation

The course forms one connected Information Retrieval (IR) pipeline: index documents, retrieve candidates, rerank them, evaluate and learn from feedback, then provide evidence to a generator. Study sequence: retrieval → reranking → evaluation → RAG → attribution.

Text → terms Terms → index Index → ranking Ranking → evaluation Sparse → dense semantics Dense → learned sparse Qrels → clicks Candidates → BERT / LLM reranking Evidence → RAG answer Claims → attribution Observation → next search Web graph → authority Ranked list → diverse intents Feedback → query reformulation Multiple runs → fused ranking Index → fast top-k
13connected weeks
30+key formulas
35+retrieval, ranking and RAG methods
Practicalscode exercises and projects
Weekly practical map

Lecture + practical, week by week

One course pipeline, with the code exercises next to the concepts they make concrete.

Week / LecturePracticalConcept bridge
Week 1Text analysis and indexingTokens, tf/df/cf, inverted indexes and Zipf
Week 2From runs to defensible comparisonsQrels, ranking measures and paired tests
Week 3Implementing lexical scoringTF-IDF, BM25 saturation and candidate limits
Week 4Follow the Transformer tensorsAttention, tensor shapes, pooling and prediction
Week 5Single-vector, multi-vector and decoder retrievalBi-encoders, late interaction and decoder embeddings
Week 6Inspect learned term weightsContextual weighting, exact matching and expansion
Week 7Learn from labels, then from clicksPointwise loss, clicks, interleaving and DBGD
Week 8Neural and LLM rerankingCross-encoding, answer-token scores and pairwise ranking
Week 9Build and test evidence-grounded RAGRAG, attribution, missing evidence and controlled prompts
Week 10From a retrieval call to a search–read loopPolicy, tools, observations, state and budgets
Week 11PageRank as a probability updateRandom surfer, stochastic matrices and convergence
Week 12Reformulate queries and fuse rankingsPRF, IDF-r, score normalisation and rank fusion

Source review: 20 October 2026. Weeks 5, 7, 9, 11 and 12 were added from the course links; Week 8 was refreshed. Other weeks use the archived notebooks identified below. This is a study walkthrough, not a claim that every model experiment was rerun.

Mental model

What an information retrieval system does

Place each weekly topic inside one software pipeline instead of memorising isolated functions.

Corpus
raw document collection
→
Analyzer
tokens, stopwords, stems
→
Inverted index
term → postings
→
Ranker
BM25 / dense model
Query
user information need
→
Top-k run
ranking for each query
→
Qrels
relevance judgements
→
Evaluation
MAP / nDCG / tests
Four objects to keep separate: the corpus contains all documents; a query expresses a need; a run is the system ranking; and qrels are the reference relevance judgements. Evaluation compares a run with qrels.

Candidate retrieval

BM25, dense and learned sparse models search the full collection.

→

Ranking

Rerankers and LTR models reorder a manageable candidate set.

→

Evidence

Qrels support offline metrics; clicks require bias-aware online methods.

Week 1

Indexing, text statistics, and preprocessing

Understand how a search engine converts a large text collection into a structure that can be searched efficiently.

IR, databases, and relevance

Database queries usually require exact matching and return deterministic answers. IR handles natural language and uncertain information needs, so it returns a ranked list. Relevance means whether a document satisfies a user's need in context, not merely whether it shares words with the query.

Core chain: representation + matching + ranking + evaluation.

Corpus, document, token, and term

A corpus/collection is the full set of documents. A document is one record, a token is one occurrence produced by tokenisation, and a term is the normalised unit stored in the index.

tf occurrences in one document df documents containing the term cf total occurrences in the collection

Zipf's law

A small number of terms are extremely frequent, while most terms are rare. Frequency falls approximately as a power law with rank.

frequency(r) ≈ C / rs

This produces a long tail. Very frequent items are often function words; very rare items may be names, spelling variants, or noise.

Text processing

  • Tokenisation: split text into indexable units.
  • Case folding: usually convert text to lowercase.
  • Stopping: remove frequent, weakly discriminative words, with some risk of losing phrase meaning.
  • Stemming: apply rules such as Porter stemming; the result need not be a real word.
  • Lemmatisation: use lexical knowledge to recover dictionary forms.

Inverted index

A forward representation is document → terms. An inverted index stores term → postings list, allowing the engine to find candidate documents without scanning the entire corpus.

LevelPosting contentsSupported capability
BooleandocIDpresence and AND / OR / NOT
CountsdocID + tfTF, TF-IDF, and BM25 ranking
PositionsdocID + tf + positionsphrase and proximity queries
Doc vectorsterms and statistics per documentcustom scorers read tf/df; A1 requires -storeDocvectors
Common error: df is not the total number of occurrences. A term appearing 20 times in one document contributes 1 to df but 20 to cf.
What the Week 1 practical develops
Reading a JSONL corpus, counting and inspecting documents, plotting Zipf-style term distributions, building Lucene indexes with different stemming/stopword configurations, and verifying the index with index_reader.stats().
Week 1 · Practical

Text analysis and indexing

Turn a JSON Lines (JSONL) collection into an inverted index, then use real term statistics to explain Zipf’s law and the effects of preprocessing.

Data flow: JSONL documents → analyzer → Lucene index → term statistics → frequency plots → reindex and compare

  1. Inspect the collection

    One JSONL line represents one document. Parse it, identify the ID and text fields, and count documents separately from tokens. A document ID connects later search hits to the same original text.

  2. Build the unprocessed baseline

    The supplied configuration keeps stopwords and disables stemming. Tokenisation still occurs: “noProcessing” is a folder label, not a claim that raw strings are indexed without an analyzer. Inspect index_reader.stats() after indexing.

  3. Plot the frequency distribution

    Sort terms by collection frequency (cf), then put frequency rank on the horizontal axis. The high-frequency head and long tail illustrate Zipf’s law. Compare the >50,000-frequency terms with the least frequent 20 terms; they expose different parts of the distribution.

  4. Change one representation choice

    Build a second index using Porter stemming and stopword removal. Recompute the statistics instead of reusing the previous vocabulary. Fewer distinct forms may improve matching, but can also merge different meanings.

Worked example

If a term occurs 7 times in one document and 3 times in another, its cf is 10 and df is 2. Its tf in the first document is 7. APIs sometimes call collection frequency “term frequency”; interpret the scope of the returned statistic.

Check your understanding: What should be retained for Week 2?

Both index paths, their analyzer settings, stable document IDs and the same collection. Week 2 adds queries and qrels to test effectiveness, rather than judging quality from vocabulary size.

Source map: prac-week1.ipynb: Exercises 1–2 and reindexing comparison. Independent study explanation; original files remain on the course platform.

Back to Week 1 lecture concepts
Week 2

Evaluation: proving that a system is better

Offline evaluation requires queries, qrels, and runs. Each measure represents a different user model.

Precision and Recall

Precision = |Relevant ∩ Retrieved| / |Retrieved|
Recall = |Relevant ∩ Retrieved| / |Relevant|

Precision asks how clean the returned set is. Recall asks how much of the relevant set was found. Web results often emphasise early precision; legal and medical search may place more weight on recall.

F-measure

Fβ = (1 + β²)PR / (β²P + R)
F1 = 2PR / (P + R)

F1 is the harmonic mean of precision and recall. β>1 emphasises recall; β<1 emphasises precision.

AP and MAP

AP = (1 / |Rel|) Σk=1..K P@k × rel(k)
MAP = (1 / |Q|) Σq∈Q AP(q)

P@k contributes only when the item at rank k is relevant. Relevant documents that were never retrieved remain in |Rel|, reducing AP.

RR and MRR

RR(q) = 1 / rank(first relevant result)
MRR = meanq RR(q)

These measures care only about the first relevant answer, making them suitable for question answering and navigational search.

DCG and nDCG

DCG@K = Σk=1..K (2rel(k) − 1) / log2(k + 1)
nDCG@K = DCG@K / IDCG@K

Graded relevance receives exponential gain and lower ranks receive a discount. IDCG is the score of the ideal ordering for the same query.

RBP

RBP = (1 − p) Σi=1..d ri pi−1

p is the probability that the user continues to the next result. Expected viewing depth is 1/(1-p).

Paired t-test

Score the same queries with systems A and B, calculate one difference per query, then test whether the mean difference departs from zero.

dq = metricB,q − metricA,q
H₀: mean(d) = 0

p < .05 is commonly called significant; p < .01 strongly significant.

Interpreting a p-value

It is the probability of observing the current or a more extreme result if H₀ were true. It is not the probability that H₀ is true and does not measure effect size.

Check evaluator keys: KeyError: ndcg_cut_5 normally means that measure was not requested when the evaluator was created.
The Week 2 practical pipeline
search(..., k=1000) creates a run → pytrec_eval.parse_run reads it → the evaluator scores each query → aggregation produces the mean → scipy.stats.ttest_rel compares paired query scores. Here k is the number of retrieved documents, not BM25's k1.
Week 2 · Practical

From runs to defensible comparisons

Compare two analyzer configurations and two retrieval depths using the same queries and judgments. Learn what a metric, a significance test and a plot each contribute.

Data flow: queries.tsv + index → ranked run → qrels join → per-query measures → paired differences → plots

  1. Retrieve and preserve identity

    Search both Week 1 indexes with their matching query analyzers. Retain qid, docid, rank and score. Retrieval depth k=10 or k=1000 is not the BM25 parameter k1 and is not automatically the evaluation cutoff.

  2. Separate set and rank measures

    Precision and recall describe the returned set. Average Precision (AP) and normalised Discounted Cumulative Gain (nDCG) also reward ordering. Mean Average Precision (MAP) averages AP across queries. IDCG uses the query’s available judgments, including relevant documents not retrieved.

  3. Align paired observations

    Compute one metric value per qid per system. Align arrays by the same qid order before ttest_rel. A small p-value is evidence against the no-mean-difference hypothesis under the test assumptions, not the probability that the null hypothesis is true.

  4. Explain the distribution

    For each query, compute candidate minus baseline. Positive bars are gains; negative bars are losses. Use mean scores, a gain–loss plot and a distribution plot together, then inspect documents for a large gain and a large loss.

Worked example

The four conditions are unprocessed/processed × top-10/top-1000. Hold depth fixed when comparing analyzers. For a deterministic ranker, merely extending the same ranking from 10 to 1000 should not alter its first 10 results; changes to nDCG@10 then require investigation.

Check your understanding: Is a statistically significant gain necessarily a large or universal gain?

No. Report the effect size and query-level failures as well. Ensure requested measures exist in RelevanceEvaluator before looking up keys such as ndcg_cut_10.

Source map: prac-week2.ipynb: Exercises 0–4. Independent study explanation; original files remain on the course platform.

Back to Week 2 lecture concepts
Week 3

Lexical matching and classical ranking

Start with term presence, then add frequency, rarity, length normalisation, and probabilistic reasoning.

Course diagrams: open the course platform (login required)

ModelCore ideaScore / roleMain limitation
BooleanSatisfy logical conditionsAND / OR / NOT postingsLittle or no ranking
CoordinationMatch more distinct query termsnumber of matched query termsIgnores frequency and rarity
TFMore occurrences in a document are betterΣ f(qi,D)Favours common terms and long documents
IDFRare terms are more discriminativelog(N/(1+dfi))Ignores within-document tf
TF-IDFLocal frequency × global rarityΣ tfi,D × idfiLinear tf and crude length treatment
VSMCompare query and document vector directionscosine(q,d)Still depends on lexical overlap
BIMContrast term probability in relevant/non-relevant setsprobabilistic relevance weightTerm independence and probability estimates
BM25IDF + tf saturation + length normalisationstrong sparse baselineNo native synonym or semantic matching

Course TF, IDF, and TF-IDF

TF(D,Q) = Σi=1..|Q| f(qi,D)
IDF(qi) = log(N / (1 + dfi))
TF-IDF(D,Q) = Σ tfi,D × idf(qi)

1 + df smooths the denominator. IDF depends on the term and collection, not on the current document.

Vector Space Model

cos(q,d) = (q · d) / (||q|| ||d||)

A dot product is affected by vector magnitude. Cosine normalises magnitude and compares direction. For L2-normalised vectors, dot product and cosine produce the same ranking.

BM25, factor by factor

score(D,Q) = Σi IDF(qi) × [(k₁+1)tfi] / [tfi + k₁(1 − b + b·|D|/avgdl)]
  • IDF: rewards discriminative rare terms.
  • TF saturation: the gain from tf 1→2 is larger than 100→101.
  • Length normalisation: controls the natural advantage of longer documents.
  • k1: controls how quickly tf saturates; larger values are more nearly linear.
  • b: controls length normalisation, from none at 0 to full at 1.
RSJ-IDF ≈ log((N − df + 0.5) / (df + 0.5))

Several BM25 variants exist. In A1, follow the formula in the supplied notebook and marking sheet rather than mixing definitions.

Why the Week 3 scorer receives three arguments
The helper calls scorer(tf_vector[term], df_vector[term], doc_len): one term's scalar tf, its scalar collection df, and the document length. Your scorer returns that term's contribution. The outer search helper adds contributions across matched query terms before ranking the candidate documents. Parameter names containing “vector” do not change these actual scalar inputs.
What the three assertions test
assert score(tf=3) > score(tf=1) checks tf monotonicity; assert score(short_doc) > score(long_doc) checks length normalisation; and assert np.isfinite(...) catches NaN or infinity. A false condition raises AssertionError.
Week 3 · Practical

Implementing lexical scoring

Implement Term Frequency (TF), Inverse Document Frequency (IDF), TF-IDF and BM25 (Best Matching 25), then compare them through Week 2’s evaluation workflow.

Data flow: index statistics + query terms → per-term scorer(tf, df, doc_len) → summed document score → reordered candidates → run

  1. Read the index statistics

    The practical reindexes with document vectors and positions. The document vector supplies term counts; summing its values gives the analyzed document length. Collection document count N and average document length avgdl must come from the same index.

  2. Trace the function call, not just its name

    The checked helper calls scorer(tf_vector[term], df_vector[term], doc_len). Despite the parameter names, each call receives scalar tf and df for ONE matched term. The search helper owns the outer summation over matching terms.

  3. Translate the formula

    TF returns tf; IDF returns log(N/(1+df)); TF-IDF multiplies them. BM25 adds tf saturation and a length-dependent denominator. Return a numeric value, and test the one-term case before processing every query.

  4. Know the candidate boundary

    The supplied searcher first obtains k candidates, then your scorer reorders those IDs. This is a candidate-pool comparison, not exhaustive retrieval with each custom formula. Reordering an unchanged complete top-10 set cannot change its P@10 or R@10, although AP/nDCG can change.

Worked example

For a matched term with tf=3, df=9, N=100, doc_len=avgdl, k1=1.2 and b=0.75: IDF=ln(10); the tf factor is 6.6/4.2; the contribution is about 3.61835. Only the outer helper adds other query terms.

Check your understanding: Why can your BM25 differ from built-in BM25?

The IDF convention, analyzer, query-term treatment, candidate set and parameter values may differ. Check these before assuming the difference is a coding error or a quality improvement.

Source map: prac-week3.ipynb: Exercise 0, ranking functions 1.1–1.4, Exercise 2. Independent study explanation; original files remain on the course platform.

Back to Week 3 lecture concepts
Week 4

Transformers: from tokens to contextual embeddings

Classical sparse models require lexical overlap. Transformers learn context-dependent representations that support semantic matching.

Tokenisation and embedding

A tokenizer maps text to token IDs. nn.Embedding(V,D) is a trainable lookup table mapping each ID to a D-dimensional vector. D is a model hyperparameter; BERT-base uses 768.

inputi = token_embedi + position_embedi + segment_embedi

The usual shape is N × D: N tokens, each represented by D values.

Position and segment embeddings

Self-attention alone does not encode order, so position embeddings are added. For sentence pairs, BERT uses segment/token-type embeddings and [SEP] boundaries.

WordPiece: rare words can be split into subwords; ## marks a continuation piece.

Self-attention

Q = XWQ,   K = XWK,   V = XWV
Attention(Q,K,V) = softmax(QKT / √dk)V
  1. Each token produces a query (what am I looking for?), key (what can I match?), and value (what content can I provide?).
  2. QKᵀ produces an N×N score matrix.
  3. Division by √d_k prevents large dot products from saturating softmax.
  4. Softmax gives row-wise weights summing to one; multiplying by V forms context-aware representations.

Multi-head attention

Several heads learn relationships in different projection subspaces. Their outputs are concatenated and projected back to D dimensions.

FFN, hidden, and residuals

hidden = GELU(W₁x + b₁)
out = W₂hidden + b₂

The FFN transforms each token independently, often D→4D→D. hidden is an intermediate activation tensor, not a manually chosen parameter. The learned parameters are W and b. Residual connections preserve information; LayerNorm stabilises training.

Encoder and BERT

An encoder can use left and right context, making it suitable for understanding, classification, ranking, and embeddings. BERT's main pretraining objective is masked language modelling.

LMLM = −Σi∈M log P(xi | x\M)

Decoder and GPT

A decoder uses a causal mask and sees only the left prefix, enabling token-by-token generation. An encoder backbone cannot naturally generate in the same way without an added decoder or modified objective and attention mask.

P(y₁…yT) = Πt=1..T P(yt | y<t)
Why the Week 4 practical produced NoneType.shape
If out = tf_block(x) is None, forward() or a called method is missing return x/return out. Python functions without return statements return None, so out.shape fails.
Week 4 · Practical

Follow the Transformer tensors

Build the simplified Transformer layer, inspect BERT (Bidirectional Encoder Representations from Transformers), and contrast it with GPT (Generative Pre-trained Transformer) next-token prediction.

Data flow: token IDs → embeddings [B,L,H] → attention and FFN → contextual states → pooling or vocabulary head

  1. Project and attend

    The small layer uses x shaped [N,D] without an explicit batch axis. Q=XWq, K=XWk and V=XWv keep [N,D]; QKᵀ becomes [N,N]. Softmax over keys makes each query-token row sum to 1. Multiplying by V returns [N,D].

  2. Preserve shape through the block

    The Feed-Forward Network (FFN) changes D→4D→D with a nonlinear activation between projections. Residual addition requires matching dimensions. Return the output from both SelfAttention and FFN; a missing return propagates None.

  3. Inspect BERT outputs

    Token IDs have shape [B,L]; last_hidden_state has [B,L,H]. CLS pooling or mask-aware mean pooling produces [B,H]. Mask padding in mean pooling. Compare the embedding module output before the Transformer with the contextual output after its layers.

  4. Compare prediction heads

    Masked Language Modeling (MLM) predicts a selected masked position from bidirectional context. GPT’s vocabulary logits at the final real input position predict the next token. Autoregressive generation appends a token and repeats.

Worked example

A batch of 2 texts padded to 6 tokens has IDs [2,6] and, for H=768, hidden states [2,6,768]. Mask-aware mean pooling gives [2,768], not [2,6] or [768]. These pooled vectors can become retrieval inputs in Week 5 after appropriate model training.

Check your understanding: Does a high next-token probability prove document relevance?

No. A vocabulary prediction head is trained for token prediction. Retrieval relevance requires an appropriate representation, scoring rule and training/evaluation setup.

Source map: prac-week4.ipynb and prac-week4-solution.ipynb: Exercises 1–3; archived starter labels itself 2025.1. Independent study explanation; original files remain on the course platform.

Back to Week 4 lecture concepts
Week 5

Dense retrieval, objectives, and negatives

Map queries and documents into a vector space where “car repair” can be close to “automobile maintenance.”

Course diagrams: open the course platform (login required)

Bi-encoder

score(q,d) = φ(ηq(q), ηd(d))

Queries and documents are encoded separately. Document vectors can be precomputed and indexed for ANN search, making bi-encoders suitable for first-stage retrieval.

Cross-encoder

[query; document] is encoded jointly, allowing deep token interaction. This is accurate but prevents offline document encoding, so it is usually used to rerank a smaller candidate set.

Pooling choices

  • CLS/first token: use the first special token's contextual embedding.
  • Mean pooling: average valid token vectors.
  • EOS/last token: common with decoders because the last token has seen the full prefix.
  • All-token: retain every token vector, as in ColBERT.

Similarity

dot(q,d) = Σ qidi
cos(q,d) = q·d / (||q|| ||d||)

For L2-normalised vectors, dot product and cosine rank identically. “Mean-pooling similarity” is imprecise: mean pooling aggregates a representation; it is not a similarity function.

InfoNCE / contrastive loss

L = −log [ exp(sim(q,d⁺)/τ) / (exp(sim(q,d⁺)/τ) + Σj exp(sim(q,d⁻j)/τ)) ]

The objective raises positive similarity relative to a set of negatives. A lower temperature τ makes softmax sharper. In-batch negatives reuse other queries' positive documents as negatives at little extra encoding cost.

Multi-label margin loss

L = mean(d⁺,d⁻) max(0, 1 − [s(q,d⁺) − s(q,d⁻)])

A pair contributes zero loss once the positive score exceeds the negative score by at least the margin.

ColBERT late interaction

MaxSim(q,d) = Σi=1..m maxj=1..n Eq,i · Ed,j

For each query token, find the most similar document token, then sum those maxima. This is not a single dot product between one query vector and one document vector.

Course diagrams: open the course platform (login required)

Negative typeSourceAdvantageRisk
Randomrandom collection documentscheap and stableoften too easy
In-batchother positives in the batchalmost no extra encodingfalse negatives
BM25 hardhigh-ranked but judged non-relevantlexically similar and challengingdepends on qrel completeness
ANN/self-minedcurrent model's mistaken neighbourstargets current weaknessescostly index refresh
What a smoke query or smoke test means
A smoke test checks that the pipeline runs at all; it does not prove quality. Run one smoke_query through TF and BM25, inspect top-5 output, and check the structure and finite scores. Formal conclusions still require all test queries and qrels.
Week 5 · Practical

Single-vector, multi-vector and decoder retrieval

Compare DPR (Dense Passage Retrieval), ColBERT (Contextualized Late Interaction over BERT) v2 and RepLLaMA. The practical is model inference and scoring, not a new full training run.

Data flow: BM25 candidates → text encoding → single-vector dot product OR token-level MaxSim → descending ranking

  1. Use the supplied dense helper

    The classroom dpr_encode uses ielabgroup/StandardBERT-DR and the first-token hidden state, then flattens one example into [H]. Encode the query and each candidate and take their dot product. The helper truncates at 64 tokens; that is a classroom configuration, not a theoretical DPR limit.

  2. Build BM25 + dense reranking

    Read raw text for each BM25 hit, keep docid attached to the vector/score, sort by the new score, and evaluate against the same qrels. Encoding a few candidates on demand teaches the pipeline; scalable dense first-stage retrieval instead pre-encodes the corpus and uses an index.

  3. Compute ColBERT MaxSim

    For one pair, query vectors [m,h] times passage vectors [n,h] transposed give [m,n]. Take a maximum over valid passage tokens for EACH query token, then sum those maxima. Match the model’s masks and query augmentation when comparing with the supplied model score.

  4. Inspect RepLLaMA’s representation

    The example loads a Llama backbone with a Low-Rank Adaptation (LoRA) adapter, uses query/passage prefixes and an end-of-sequence (EOS) token, then normalises the last-token vectors before a dot product. With unit-length vectors, this is cosine similarity.

Worked example

Toy MaxSim matrix [[0.9,0.2,0.1],[0.3,0.8,0.4]] gives row maxima [0.9,0.8] and score 1.7. This can exceed 1 because it is a sum of token similarities, not a probability. The extra token-level detail costs more storage than one vector per passage.

Check your understanding: How do the negative-sample lecture exercises connect?

Information Noise-Contrastive Estimation (InfoNCE) and margin losses explain how useful embeddings are learned. In-batch and hard negatives determine what must be distinguished. They are training concepts; the current practical mostly loads already-trained models.

Source map: prac-week5.ipynb: Exercises 1–3; local InfoNCE/MarginLoss/HardNegatives HTMLs are supplementary worked notes. Independent study explanation; original files remain on the course platform.

Back to Week 5 lecture concepts
Week 6

Learned sparse retrieval

Vocabulary-aligned sparse representations retain inverted-index efficiency while neural models learn contextual term weights and expansion.

The missing middle: BM25 is sparse and fast but lexical; DPR is semantic but dense. Learned sparse models use neural encoders while keeping mostly-zero vocabulary dimensions that can be interpreted as terms.
ModelQueryDocumentMatchingOnline cost
BM25observed termsterm statisticshand-crafted weighted sumvery low
DPRdense vectordense vectordot product + ANNquery encoder
TILDEv2token IDscontextual token weights, often expanded offlineexact ID match + max weightno query encoder
SPLADE(v2)learned sparse vocabulary vectorlearned sparse vocabulary vectorsparse dot productquery encoder
PromptRepsdense hidden state + sparse logitssamehybrid interpolationLLM inference

Expansion

doc2query generates likely queries offline and appends them to documents before indexing. This reduces vocabulary mismatch without adding query-time generation.

TILDEv2

score(q,d) = Σt∈q maxi: token(d_i)=t wi,d

The query is only tokenised. Exact query-token matches retrieve learned contextual document weights; repeated terms contribute their maximum weight.

SPLADE

score(q,d) = vq · vd,   v ∈ R|V| and mostly zero

An MLM head activates weighted vocabulary terms, including related terms absent from the text. ReLU, pooling and FLOPS/L1 regularisation control sparsity.

Sparse can still be neural

Sparse/dense describes the output representation. SPLADE uses BERT but emits a sparse vocabulary vector; DPR uses BERT but emits a dense embedding.

Practical pipeline: BM25 + TILDEv2

Retrieve

BM25 searches the full corpus.

→

Read candidates

Use hit IDs and raw document text.

→

Rerank

TILDEv2 scores query-document pairs.

The first stage protects efficiency and candidate recall; the second stage improves ordering within the candidate set.

Data flow inside tildev2_scoring
Document text becomes token IDs and learned weights. Query text becomes token IDs with stopwords removed. Equal IDs are matched, repeated matches use the maximum document weight, and matched query-term weights are summed into one reranking score.
Week 6 · Practical

Inspect learned term weights

Connect neural context to lexical matching: TILDEv2 (Term Independent Likelihood moDEl v2) weights document tokens; SPLADE (SParse Lexical AnD Expansion) produces vocabulary-aligned sparse representations.

Data flow: document → contextual token weights; query → token IDs → exact matches → max per matching term → sum

  1. Compare counts with contextual importance

    The exercise contrasts terms in a passage: equal occurrence counts need not mean equal learned weights. Inspect the token IDs and weights together. Repeated tokens can have different contextual weights before aggregation.

  2. Trace tildev2_scoring

    Tokenise the query without special tokens, remove its stop IDs, and locate equal document token IDs. Use the maximum document weight for each matched query ID; missing matches contribute zero. The supplied loop iterates query tokens, so repeated query IDs are counted repeatedly unless explicitly deduplicated.

  3. Rerank BM25 candidates

    BM25 provides candidate IDs and raw text. TILDEv2 supplies a new score for the same candidates. Keep the candidate set fixed for a reranking comparison. noExp identifies the no-expansion variant: contextual weighting alone does not invent every missing matching term.

  4. Decode a SPLADE representation

    For inspection, convert the small sparse output with to_dense(), count nonzeros and decode the top-10 weighted vocabulary IDs. A nonzero term absent from the original text demonstrates expansion. A sparse dot product compares query and passage on shared vocabulary dimensions.

Worked example

For one query term, document occurrence weights [0.2,0.8] contribute 0.8, not 1.0. A second matching term of weight 0.4 produces total 1.2. By contrast, SPLADE scoring multiplies query and document weights in shared vocabulary dimensions and sums them.

Check your understanding: Why might token_ids, token_weights = model.encode(...) fail?

The local modeling.py and checkpoint interface may differ. Inspect the returned type and batch nesting, then match the course helper. Do not install an unrelated package named modeling or remove a dimension merely to suppress the exception.

Source map: prac-week6.ipynb: Exercise 1 TILDEv2, Exercise 2 SPLADEv2. Independent study explanation; original files remain on the course platform.

Back to Week 6 lecture concepts
Week 7

Learning to rank, click bias, and online evaluation

LTR learns to order candidates. Online LTR replaces scarce static labels with abundant but biased user interactions.

Retriever → features → LTR ranker

Retriever

BM25, dense or learned sparse candidates.

→

Features

Lexical, neural, freshness and authority signals.

→

LTR ranker

Learned ordering of the candidate list.

Offline LTR

  • Pointwise: predict one relevance score.
  • Pairwise: predict which of two documents should rank higher.
  • Listwise: optimise an entire ranked list.

Clicks are not labels

Position bias changes examination; selection bias excludes unseen documents; presentation bias changes attraction. No click does not necessarily mean non-relevant.

Inverse Propensity Scoring

Δnaive(f) = Σ λ(ranki)ci
ΔIPS(f) = Σ [λ(ranki)/P(oi=1)]ci

IPS corrects position/exposure bias in expectation by dividing a click by its examination probability. Rarely examined observations receive more weight, which can also increase variance.

Balanced interleaving

Maintain a scan pointer for each ranked list. Inspect the list with the smaller pointer, breaking ties with a randomly chosen starting ranker. Advance the pointer even for duplicates, but append only unseen documents. This balances inspected depths, not necessarily the number contributed by each ranker.

DBGD

Sample a candidate parameter direction, compare current and candidate rankers through interleaving, and move toward the winner.

Counterfactual OLTR

A stochastic logging policy records displayed actions and propensities. IPS then estimates the risk of current and candidate rankers from the same interaction log.

Main advantage over regular interleaving: one logged randomized policy can evaluate multiple candidate rankers off-policy instead of creating a fresh interleaved comparison for every pair. It depends on accurate propensities, exploration/support, and manageable variance.
MethodDataOutputMain trade-off
Offline qrelsqueries + runs + qrelsMAP/nDCGcleaner but expensive and static
Interleavinglive clicks on a mixed listpairwise preferencesensitive, but requires live exposure
DBGDrepeated interleavingparameter update directiononline adaptation versus exploration risk
Counterfactual IPSlogged clicks + propensitiesoff-policy value/risklog reuse versus variance and support assumptions
Week 7 · Practical

Learn from labels, then from clicks

Contrast offline Learning to Rank (LTR) with Online Learning to Rank (OLTR). Logistic regression learns from explicit labels; Duelling Bandit Gradient Descent (DBGD) uses comparisons inferred from clicks.

Data flow: MQ2007 features → logistic relevance scores → query-wise ranking; candidate ranker → interleave → simulated clicks → preference → update

  1. Read the feature dataset

    Each MQ2007 row is a query–document pair with 46 features. The pointwise exercise maps labels 1 and 2 to 1. Preserve qid groups for ranking and evaluation; confirm the final query group is saved after parsing.

  2. Implement the offline update

    Compute p=sigmoid(Xθ), gradient Xᵀ(p−y)/m and θ_new=θ−α·gradient. Use the same old weights for every gradient component. Ranking by θᵀx or its sigmoid is equivalent because sigmoid is monotone.

  3. Interleave by inspected depth

    Keep a pointer into each original ranking. Inspect the shallower pointer; use one random starting choice to break ties. Advance the pointer even when a duplicate is skipped. This balances inspected depths, not strict alternation of successful insertions.

  4. Infer the preference

    If clicks exist, take the deepest displayed clicked document. Its better rank in the two original lists determines a common prefix cutoff. Count clicked IDs in each prefix; the exploratory list wins only if its count is larger. No clicks or a tie do not establish a winner.

  5. Read the learning curve critically

    DBGD samples direction u and updates toward it only when the challenger wins. Compare perfect, navigational and informational click models using fixed settings and multiple seeds. The “perfect” simulator still has a probabilistic click for relevance grade 1; its name does not mean every relevant item is always clicked.

Worked example

A=[a,b,c], B=[b,c,a], displayed clicks=[b,c]. The deepest click is c; its better original rank is 2. A’s top two receive one click and B’s top two receive two, so B wins. Inspect the helper’s random draw: np.random.randint(0,1) always returns 0 because the upper bound is exclusive; a two-outcome draw needs an upper bound of 2.

Check your understanding: Why can nDCG remain unchanged while weights change?

A small weight update can preserve every document’s ordering. Check weight differences and the training loss before diagnosing a frozen model. Conversely, an unimplemented update also leaves scores unchanged; inspect the computation, not only the plot.

Source map: prac-week7.ipynb: pointwise Tasks 1–2 and online Tasks 1–2; scripts/ClickModel.py and InterLeaving.py. Independent study explanation; original files remain on the course platform.

Back to Week 7 lecture concepts
Week 8

Transformer-based reranking: BERT and LLM rankers

Encoder rerankers jointly encode query-document pairs. Decoder-based Large Language Models (LLMs) judge, compare, or order passages through prompts. Stage one retrieves candidates; stage two makes more expensive, fine-grained relevance judgements.

Retrieval → interaction → final ranking

First-stage retrieval

BM25 searches the full collection and returns top-k candidates.

→

Neural reranking

BERT jointly encodes pairs, or an LLM evaluates candidates through a prompt.

→

New order

Sort by scores, pairwise preferences, or an output permutation.

A reranker cannot recover a relevant document omitted by Stage 1. Increasing candidate depth can protect recall but increases latency. Candidate depth connects effectiveness with efficiency.

monoBERT: pointwise cross-encoder

Bidirectional Encoder Representations from Transformers (BERT) reads [CLS] query [SEP] document [SEP]. A classifier converts the contextual [CLS] vector into a relevance score.

s(q,d) = P(relevant = 1 | q,d)

Each document is judged independently. Training commonly uses human positives and BM25 hard negatives.

Training objective

L = -Σpos log(s) - Σneg log(1-s)

Binary cross-entropy rewards high positive scores and low negative scores. The output is a ranking signal, not necessarily a calibrated real-world probability.

Long-document evidence

MethodAggregationInterpretation
BERT-FirstPfirst passage scorecheap but ignores later evidence
BERT-MaxPmaximum passage scoreone strong passage represents the document
BERT-SumPsum of passage scoresaccumulate evidence
Birchfirst-stage score + weighted sentence scoressentence-level evidence
PARADEaverage, max, attention, or Transformer over passage vectorsrepresentation aggregation
Key distinction: MaxP/FirstP/SumP combine scalar scores; Passage Representation Aggregation for Document Reranking (PARADE) combines learned passage representations before the final score.

duoBERT: pairwise reranking

duoBERT reads a query and two candidates to estimate p(dᵢ > dⱼ | q). Pairwise wins are then aggregated.

s(dᵢ) = Σj≠i p(dᵢ > dⱼ | q)

This can refine a monoBERT list, but pair comparisons add substantial encoder cost.

Multi-stage trade-off

BM25 → monoBERT → duoBERT allows separate candidate depths and model choices. More tuning knobs create a wider effectiveness-efficiency trade-off space, but also more system complexity.

Four LLM reranking families

FamilyInputSignalMain trade-off
Pointwisequery + one passageYes/No logit, label, or gradesimple; absolute judgement may be unstable
Pairwisequery + passages A and BA > B preferencerobust; many comparisons
Listwisequery + passage listgenerated permutationlist context; generation/context cost
Setwisequery + small passage setbest-item logitsfewer calls than pairwise; avoids full-list generation

“Zero-shot” here means no new contrastive retriever training after obtaining an instruction-tuned LLM; it does not mean the underlying LLM was never trained.

Prompt variation

Role text, formatting, output restrictions, and query/passage order affect results. The slides report greater sensitivity for pointwise and listwise prompts, while pairwise and setwise are generally more robust. Model size, architecture, and training still matter.

Why setwise can cost less

One call compares several passages using logits. This needs fewer comparisons than pairwise ranking and less generation than listwise permutation output.

Week 8 practical data flow

BM25 top-k

Retrieve 10 or 20 candidates and read raw passage text.

→

monoBERT

Tokenise each pair, obtain relevant-class probability, and sort descending.

→

Evaluate

Write the reordered run and compare it with qrels.

The updated LLM section compares TinyLlama, MiniCPM and Qwen3-Reranker before the pairwise exercise. It distinguishes raw Yes-token probability from Yes/No-normalised scores; compare ordering rather than score magnitudes across models. Retrieval depth and evaluation cutoff are separate parameters.

LLM4IR versus IR4LLM
Large Language Models for Information Retrieval (LLM4IR) applies LLMs to tasks such as reranking. Information Retrieval for Large Language Models (IR4LLM) retrieves external evidence for an LLM. The Week 8 ranking exercise is LLM4IR.
Why automatic prompt engineering is harder for ranking
A ranking demonstration includes a query, several passage meanings, relative relevance, and an ordering. Multiple passages may share a valid relevance level, so the desired output is more complex and less unique than one classification label.
Week 8 · Practical

Neural and LLM reranking

Follow the same candidate pool through an encoder cross-encoder and decoder-based relevance scoring. Distinguish a score used for ordering from a calibrated probability of relevance.

Data flow: BM25 top-k IDs → raw text → query–passage pair → relevance score → sorted run → same qrels

  1. Build BM25 + monoBERT

    BERT jointly encodes the query and one passage; a classification head supplies a relevant-class score. Start with 10 or 20 candidates as instructed. Sort by monoBERT, not by the old BM25 score, before writing the run.

  2. Score a general-purpose chat model

    TinyLlama and MiniCPM use the probability of a selected Yes token after a fixed prompt. Each model has its own tokenizer and chat template. Check whether Yes or leading-space Yes is one token and matches the answer format; keep the choice fixed across passages.

  3. Avoid scoring padding

    The next-token distribution must come from the final real prompt position. The updated example scores passages individually to avoid right-padding mistakes. Passing an attention mask alone does not make logits[:,−1] point to the last real token of every right-padded example.

  4. Compare the dedicated reranker

    Qwen3-Reranker uses its task-specific format and designated yes/no logits. The notebook’s interface describes a logit difference z_yes−z_no; sigmoid maps that difference to exp(z_yes)/(exp(z_yes)+exp(z_no)) without changing order. Check the installed interface’s output convention.

  5. Extend to pairwise judgments

    Provide the question and two labeled passages and request a preference. Reverse A/B positions and map the result back to the same document IDs to examine position bias. For many candidates, define ties and aggregation; pairwise preferences may be cyclic.

Worked example

Toy raw probabilities: passage A has P(Yes)=0.02 and P(No)=0.001; B has 0.40 and 0.10. Raw Yes prefers B, but Yes/No normalisation gives A≈0.952 and B=0.800, reversing the order. A’s high normalised score hides that both selected tokens had little total probability.

Check your understanding: What must stay fixed to test the effect of normalisation?

The model, prompt, evidence, answer-token choices and generation/scoring position. Change only raw-versus-normalised scoring. Compare ranked relevance against judgments rather than comparing raw values across models.

Source map: prac-week8.ipynb: BM25 + monoBERT, TinyLlama, MiniCPM, Qwen3-Reranker, optional scoring comparison, pairwise exercise; refreshed 16 October 2026. Independent study explanation; original files remain on the course platform.

Back to Week 8 lecture concepts
Week 9

Information Retrieval in the Age of LLMs

LLM4IR uses Large Language Models for retrieval and ranking; IR4LLM supplies external evidence to an LLM. This week connects retrieval models to RAG, long context and attribution.

The end-to-end evidence pipeline

Retrieve

BM25, DPR, TILDEv2, SPLADE, CiC, or a specialist model selects evidence.

→

Refine

Rewrite, rerank, filter, fuse, summarise, or compress.

→

Generate and attribute

Answer from evidence and link claims to real sources.

Retrieval effectiveness and answer quality are related but different. Better nDCG can make good evidence available, yet prompt order, truncation, conflicting model knowledge, and evidence use still determine the answer.

Prompting recap

Zero-shot gives instructions only; one/few-shot adds demonstrations; Chain-of-Thought (CoT) elicits intermediate reasoning tokens. Those tokens are generated text, not a guaranteed faithful trace of internal reasoning.

LLMs for retrieval and ranking

RepLLaMA and LLM2Vec generate dense representations. PromptReps and DiffRetriever explore multiple generated representations. Pointwise, pairwise, listwise, and setwise prompts produce ranking judgements.

Long-context search versus RAG

DimensionLC-LLM / Corpus-in-ContextRAG
Inputvery large corpus inside the promptsmall retrieved top-k
Benefitconsolidates a multi-stage pipelinescales to large and changing collections
Costlong-context attention and latencyretriever/reranker maintenance
Failureposition bias; lost-in-the-middlemissing, distracting, or conflicting evidence

Corpus-in-Context (CiC, “seek”) uses consistent document IDs, corpus-grounded examples and a fixed list output. Prefix caching reduces repeated corpus-prefix work, but does not remove position bias.

Specialised interfaces

Screenshot retrievers use a Vision-Language Model to preserve layout and visual evidence. DiffRetriever uses a diffusion language model to produce representative tokens in parallel and matches multiple representations.

Why RAG?

External evidence can be newer, private, domain-specific, updateable and inspectable. Unlike further pretraining, the collection remains separate from the generator's parameters.

Modular RAG

StageExamplesMain risk
Pre-retrievalrouting, rewriting, expansion, HyDEquery drift
Retrievallexical, dense, learned sparse, hybridgold evidence absent from top-k
Post-retrievalrerank, filter, fuse, summariselatency or useful evidence removed
Promptlexical/embedding compressionlost qualifiers or provenance
Generationread, cite, revise, retrieve againmodel prior overrides evidence

Rewrite-Retrieve-Read

A rewriter makes an underspecified query search-friendly, a retriever selects evidence, and a reader answers. The rewriter can be warmed up with pseudo-data and later optimised from downstream reward.

BlendFilter

Combine retrieval with model-generated query/answer signals, then use an LLM to filter irrelevant knowledge before generation. Retrieved results still require evidence selection.

Prompt compression

Lexical methods delete low-information tokens; embedding methods map long text to compact memory tokens. Both save tokens but may lose evidence detail and provenance.

Evidence conflict

A model may ignore corrective evidence or change a correct answer after contrary evidence. Relevance, answer correctness and groundedness must be evaluated separately.

Noise, position, and evidence amount

High-scoring distractors can sharply hurt answers; more distractors often worsen results; gold evidence in the middle can be underused; random context sometimes helps particular models. These are empirical model-dependent behaviours, not universal recipes.

Project 2 link: keep the same LLM, prompt, decoding and token budget across no-retrieval, BM25, neural and oracle evidence conditions.

Attribution

Attribution links answer claims to supporting references. Directly generated citations may be fabricated; retrieval-based attribution restricts candidates to real documents.

RARR

Retrofit Attribution using Research and Revision researches support for an existing answer, then revises unsupported content while preserving as much of the draft as possible.

Why does better retrieval not guarantee a better answer?
nDCG measures ranked evidence. Generation additionally depends on truncation, ordering, prompt design, model priors, and whether the generator follows the passages. Measure the relationship per query rather than assuming causality.
Week 9 · Practical

Build and test evidence-grounded RAG

Use Information Retrieval for Large Language Models (IR4LLM), reversing Week 8’s LLM4IR role. Retrieval-Augmented Generation (RAG) passes evidence to a generator; retrieval quality and answer quality remain separate measurements.

Data flow: question + retrieved documents → labeled context → instruction/chat template → tokens → generated continuation → claim-by-claim checking

  1. Implement rag_answer

    Join the provided documents with labels, include the question, and ask for an answer supported only by that evidence. Tokenise the model-specific chat template, generate, then decode only output_ids after the input length. Keep model and input tensors on the same device.

  2. Understand the weather demonstration

    The notebook supplies two weather snippets as example evidence. It does not implement a live weather fetch. The example teaches how external context can change an answer; its quoted temperature is not today’s verified forecast.

  3. Combine the café evidence

    The four fictional documents cover prices, caffeine, milk and a reusable-cup discount. A correct supported answer must satisfy every constraint and cite the relevant documents. Check arithmetic as well as the selected drink.

  4. Control the prompt experiment

    Compare zero-shot instructions, few-shot demonstrations and a prompt requesting an explicit evidence check while holding the documents and generation settings fixed. Keep demonstrations separate from the actual café answer so examples do not leak the solution.

  5. Separate prompt from native thinking

    First compare prompts with native thinking off. Then hold the zero-shot prompt fixed and toggle thinking for MiniCPM5/Qwen3. Record correctness, cited support, output tokens and whether the answer finishes. Thinking tokens consume the same bounded output budget.

Worked example

The supplied fictional evidence implies a decaf latte with oat milk: $4.80 + $0.70 − $0.50 = $5.00, and 5 mg caffeine ≤10 mg. D1 supports the base price, D2 the caffeine, D3 the milk substitution/surcharge, and D4 the discount. This is a hand-derived evidence check, not a reported model run.

Check your understanding: What happens when the milk-options document is removed?

The remaining evidence no longer establishes a dairy-free option or its surcharge. A grounded response should state the missing information instead of recalling the removed fact as if it were still supported.

Source map: prac-week9.ipynb: Exercise 1 rag_answer, Exercise 2 prompting strategies and thinking-mode comparison; downloaded 16 October 2026. Independent study explanation; original files remain on the course platform.

Back to Week 9 lecture concepts
Week 10

Search Agents

Static RAG retrieves once and then generates. A search agent can use an observation to decide whether to search again, inspect a candidate, read a specific section, or finish. The new idea is a feedback loop over evidence, not just a larger set of tools.

Static RAG versus an agent

SystemSequenceInsufficient evidence
Static Retrieval-Augmented Generation (RAG)query → one retrieval → prompt → answerUsually cannot revise the search after seeing the results.
Search agentgoal → action → observation → updated state → next action or finishCan reformulate, inspect, read, verify, or stop at a budget.

An agent is a goal-directed system interacting with an environment. Its policy selects an action using the current state; a tool performs that action; an observation reports the outcome. ReAct (Reasoning and Acting) interleaves reasoning with external actions. Reasoning text is a proposed decision process, not independently verified evidence.

For a two-hop question, evidence about the first entity only establishes the first hop. The agent should search for the second relation and read the resulting evidence before answering.

State and stopping

The state can include the original goal, previous queries, visited documents, observations and remaining step/token budget. Stop when the answer has adequate support, further actions offer little value, or the budget is exhausted. Distinguish a retrieval miss, malformed tool call, loop, budget stop and unsupported answer; all can produce a failed run for different reasons.

Search–Visit baseline

Rank candidates, then open a promising result. This is effective when one short page is likely to contain the answer. Visiting an entire long report can waste context before identifying the useful section.

Choose a search interaction strategy

Method and full nameAction patternSuitable settingMain risk
Search–Visitrank → open pageone short pagewhole-page context waste
SIEVE, Search–Inspect–Fetchrank → inspect headings/structure → fetch sectionlong structured reportstructure may not reveal the answer
DCI, Direct Corpus Interactiongrep raw files → read matching linesmanageable local corpus and exact known termlexical mismatch; broad scan cost
RISE, Retrieving Interaction SpacEBM25 narrows files → grep and line navigationlarge collection, useful file unknownranking may exclude the correct file

These are different search workflows. SIEVE adds a structural inspection step before fetching. RISE adds ranked candidate selection before direct file inspection. DCI can work without a prebuilt index.

Why ranking still matters

An agent can retry, but only within a finite budget. BM25 supplies lexical candidates; dense or learned sparse retrieval can help vocabulary mismatch; reranking can reorder a fixed pool. The lecture's results depend on passage versus whole-document granularity and the agent interface, so do not claim one universal winner. Evaluate answer support and action/token cost as well as offline ranking scores.

Marginal evidence gain

A document can remain topically relevant after it has already been read, yet add little new information. Agent-aware retrieval considers the user's question together with current reasoning and previous observations. The useful next document is one that advances the unresolved part of the task, not merely one that matches the original query.

How retrievers learn from agent trajectories

ApproachQuery-side inputPositive signalLimitation
AgentIR, Reasoning-Aware Retrieval for Deep Research Agentsintermediate query plus pre-search reasoninggold documents plus expensive reranking generate positive/negative passagesgold labels and external reranking are costly; snippets may omit evidence
LRAT, Learning to Retrieve from Agent Trajectoriesqueries from successful agent runsjudged visited passages, without gold-document labelsvisits alone do not prove utility; other passages may be mislabeled negative
ITER, Interaction-Aware Retrieval for Agentic Searchcurrent query, original question and previous queriestrajectory-relative judgments distinguish new evidence from visited relevant/irrelevant passagesinferred labels and selection bias need care

These methods connect Week 5's positive/negative selection to Week 7's feedback bias: documents the policy never showed are not automatically irrelevant. AgentIR uses judged documents; LRAT and ITER explore supervision from successful trajectories. ITER further models what has already been seen.

Week 10 practical: trace the data

Find candidates

grep(pattern) locates matching lines; BM25 search(query) returns candidate IDs.

→

Rerank and read

A CrossEncoder reorders the same BM25 pool; read(id, start_line, num_lines) returns numbered evidence.

→

Update and finish

Tool output enters the agent history; the policy chooses another action or a supported answer.

The notebook asks you to complete line slicing in read and query/passage scoring in search. Its small relevance labels are for human inspection, not for the agent's prompt. A grep match is a location hint and a ranking score is a candidate signal; neither proves the final answer until the passage is read. The colour-afterimage example makes this visible: one passage names afterimages, while another more directly explains visual adaptation. Optional Qwen3 thinking text is not an observed source.

Lecture question: what should the agent do after finding the city?
Search for a source identifying the river through that city, read it, and support both links in the chain. The first observation alone does not justify the river answer.
Lecture question: which workflow fits each corpus?
Choose Search–Visit for a short page, SIEVE for a long structured report, DCI for an exact term in a manageable local corpus, and RISE when a large collection needs ranking to narrow which files to inspect.
Lecture question: where can agent-aware positives and negatives come from?
Gold judgments can supervise useful documents. Without them, successful trajectories provide candidate positive visits, but each visit needs scrutiny: previously visited relevant evidence can be redundant, and unvisited documents are not automatically negative.

Research trail: ReAct · SIEVE · DCI · RISE · AgentIR · LRAT · ITER. The course PDFs and code remain on the restricted course platform.

Week 10 · Practical

From a retrieval call to a search–read loop

Trace a ReAct (Reasoning and Acting)-inspired agent: the policy selects an action, Python validates and executes it, and an observation updates the state. Complete small tools rather than treating the agent as one opaque model.

Data flow: question → policy → search/grep/read → tool observation → updated messages → another action or finish

  1. Separate the roles

    The policy is the model’s action choice; tools are Python functions; observations are their returned text/errors; state is the accumulated messages and allowed IDs; a trajectory is the sequence of actions and observations. Qrels stay outside the agent prompt.

  2. Complete read

    Convert the public 1-based start_line to a 0-based slice start. Return up to num_lines, prefix each selected line with its original line number, and provide the next starting line only when unread lines remain. The tool accepts at most 12 lines.

  3. Complete search

    Retrieve eight BM25 candidates; build (query, passage) pairs; use reranker.predict; sort the paired candidate/score objects descending; return the best k (allowed 1–5). Sorting scores separately from candidates breaks the ID-to-score association.

  4. Observe scoped evidence access

    In Part 1, grep scans the ten-document sample. Part 2 explicitly requires search→grep→read: the latest search results constrain which documents grep/read may inspect. A grep match locates text; reading context establishes what it actually says.

  5. Evaluate failures and budgets

    The classroom run caps decisions at 8, output at 512 tokens per decision and input at 8,192 tokens. Failed calls also spend steps. Inspect retrieval misses, malformed calls, repeated loops, budget stops and unsupported final claims separately.

Worked example

For lines [alpha,beta,gamma,delta], read(start_line=2,num_lines=2) should return “2: beta” and “3: gamma”, with next_line=4. Reading from 4 returns “4: delta” and next_line=None. Starting beyond the end should produce an empty window with no next page, under the supplied validation contract.

Check your understanding: Does a successful run on the ten-document sample establish general agent accuracy?

No. It demonstrates the mechanism. Compare the answer’s supported claims and token/time costs, then use broader evaluation for general conclusions. Optional thinking-on/off runs must use equal budgets and fixed questions/tools.

Source map: prac-week10.ipynb: Exercises 1 read, 2 search, comparison and optional thinking; search_agent.py and agent_display.py. Independent study explanation; original files remain on the course platform.

Back to Week 10 lecture concepts
Week 11

Web Crawling, Link Analysis, and Diverse Ranking

A web search engine must first discover pages, then use both page content and the link graph, and finally avoid returning a top list that repeats one interpretation of an ambiguous need.

The crawl–graph–rank pipeline

Discover

Start from seed URLs and take permitted unseen URLs from a frontier.

→

Fetch and parse

Request a page, parse content and links, normalise URLs, and suppress duplicates.

→

Index and rank

Build content and link structures, retrieve candidates, then balance relevance, authority and diversity.

The URL frontier is the set of discovered URLs waiting to be fetched. A useful crawler must decide which host and URL to visit next, when to revisit for freshness, and how to avoid duplicate content and crawler traps. Coverage is bounded by starting seeds, reachability, access rules, time and storage; a crawl is not a complete copy of the Web.

Politeness, robots.txt, and safety

Schedule requests per host, avoid overloading servers, identify the crawler, respect applicable access rules and handle redirects and failures. robots.txt communicates crawler access preferences; it is not authentication and must not be treated as a way to protect private content.

Keep separate: “not allowed to crawl” is a crawler rule. “not authorised to read” requires real access control.

The Web as a directed graph

Pages are nodes and hyperlinks are directed edges. An in-link points to a page; an out-link leaves it. Link analysis supports ranking, link-based clustering, classification features and crawl prioritisation. It can also reveal abnormal link distributions associated with spam.

Authority and anchor text

The lecture makes two different link hypotheses: a link may confer authority, and its anchor text may describe the target page. When indexing target page D, incoming anchor text can be added with a weight, possibly influenced by the source page's authority. This helps vocabulary mismatch but can be manipulated by spam or coordinated anchors.

PageRank: authority from recursive endorsement

PR(v) = (1 − d) / N + d Σu→v PR(u) / L(u)

N is the number of pages, L(u) the out-degree of page u, and d the probability of following a link. The remaining probability teleports to a page. A link from a high-PageRank page passes more mass, and that mass is divided across its outgoing links. Dangling pages need an explicit redistribution rule so probability does not disappear.

Compute by power iteration: start with a probability vector, distribute link and teleport mass, and repeat until the change is small. PageRank estimates graph importance, not query relevance. A production ranker can combine it with lexical, semantic, freshness and other signals.

Integrating query-independent evidence

Retrieval modelHow PageRank can enterCaution
Language modelreplace a uniform document prior P(D) with a prior based on PageRank or another document featurea convenient prior does not guarantee higher effectiveness
BM25treat text plus non-text features as a learned or tuned utilitythe base model permits extra features but does not determine their weights
Vector Space Modelcombine cosine similarity with PageRank, spam score or difficulty in an external utility functionquery-independent features do not occur naturally in the query vector

PageRank, spamminess and URL depth are document priors. They are features, not relevance labels; evaluate whether their addition actually improves the target measure.

Why diversity is a ranking objective

An ambiguous query such as jaguar may mean an animal, a car brand or a sports team. Even for one intent, near-duplicate pages waste early ranks. Diversity tries to cover plausible aspects while retaining relevance, so success is not simply “make every result different.”

MMR: relevance minus redundancy

argmaxd∈R∖S λ Rel(d,q) − (1−λ) maxs∈S Sim(d,s)

Maximal Marginal Relevance (MMR) greedily chooses the next candidate from remaining results R; S is the selected set. Larger λ favours query relevance, while smaller λ penalises similarity to what is already shown. The document–document similarity and score scales must be chosen consistently.

PRP assumptions and interdependent relevance

The Probability Ranking Principle (PRP) ranks documents by decreasing estimated probability of relevance. Its simple next-document rule assumes that the estimate is accurate/certain and that a document's relevance can be considered independently of already ranked documents. Ambiguity challenges the first assumption; redundancy challenges the second. Diversification instead asks for the marginal value of a candidate given what is already in the ranked set.

List objectiveQuestionFailure if used alone
RelevanceHow useful is this document for the query?may repeat one interpretation
CoverageWhich plausible intents/subtopics appear?may sacrifice too much relevance
NoveltyWhat new information does this result add?mere difference may not be useful

Evaluating and supplying diversity

A diversity system needs more than a reranking formula. Query-ambiguity detection estimates whether multiple intents matter; query-aspect mining proposes those intents; vertical diversification can mix result types. Evaluation can use subtopic recall/precision/MRR, α-nDCG, intent-aware nDCG or intent-aware ERR. State the intent judgments and metric convention: ordinary nDCG over one relevance label does not fully measure coverage plus novelty.

Worked example: which page should PageRank favour?
If pages A and C both link to B, while only A links to C, B receives endorsement from two pages. The exact score still depends on A and C's own PageRank, their out-degrees, the teleport probability and dangling-page handling. Counting in-links alone is therefore not PageRank.
Worked example: relevance or diversity?
Suppose three highly relevant results all discuss the Jaguar animal and a slightly lower-scoring result covers Jaguar cars. A relevance-only list may choose the three animal pages. MMR may promote the car page because it adds an uncovered interpretation. That promotion is useful only if the aspect is plausible for the query.
How should Week 11 connect to earlier weeks?
Week 1's crawl and index pipeline supplies pages and edges; Weeks 3–8 score content and rerank candidates; Week 11 adds graph authority, query-independent priors and list-level marginal utility. Link score, query relevance and diversity are separate signals and should be evaluated separately before combination.

Public reading: Stanford IR book: web crawling · Stanford IR book: PageRank · RFC 9309: Robots Exclusion Protocol · MMR paper. Week 11's released lecture supplied the course-specific scope; restricted course files are not hosted here.

Lecture and video route

The course playlist has 10 videos, totalling 28 min 36 sec. Links and chapter titles were checked on 13 October 2026; the explanations below were checked against the 40-page Week 11 lecture PDF. They are study notes, not video transcripts.

Open the complete Week 11 playlist · Course announcement (login required)

ChapterDurationLearning checkpoint
11.1 Overview2:22Place graph authority and list diversity beside content relevance.
11.2 Links3:15Distinguish an endorsement from descriptive anchor text.
11.3 Link analysis in IR3:18Explain why links help ranking, clustering, classification and crawling.
11.4 PageRank4:41Trace one random-surfer step and the role of teleportation.
11.5 Understanding PageRank1:56Use source authority and out-degree, not just the count of incoming links.
11.6 PageRank in retrieval2:06Separate a document prior from the query-dependent matching score.
11.7 Diversification1:17Explain why a relevant duplicate may add little value to a list.
11.8 PRP3:22Expand Probability Ranking Principle and state the lecture's assumptions.
11.9 Ambiguity and redundancy0:48Locate ambiguity in the query and redundancy in the result list.
11.10 Diversity framework and MMR5:31Compute the next result's relevance-minus-redundancy score.

PDF route: pp. 3–8 links and anchors; pp. 9–19 random surfer and PageRank; pp. 20–24 retrieval priors; pp. 25–36 diversity and PRP; pp. 37–40 diversification and MMR. The crawling/robots background above is a supporting extension, not the central scope of this PDF.

Three signals, three different questions

Method and full nameInputs → outputWhat changes the score?Not a substitute for
BM25 (Best Matching 25); DPR (Dense Passage Retrieval)query + document representation → matching scorequery words or meaningauthority or a diversity objective
monoBERT (BERT: Bidirectional Encoder Representations from Transformers)one query–document pair → relevance scorejoint contextual matchingcomparison with all already selected documents
PageRank (a model name, not an acronym)directed link graph + teleport rule → one authority value per pagelinks, graph boundaries and teleport distributionquery relevance or factual verification
PRP (Probability Ranking Principle)estimated relevance probabilities → descending orderthe relevance estimatesa trained encoder or a redundancy penalty
MMR (Maximal Marginal Relevance)candidate relevance + document similarity + selected set → next itemquery AND what is already selectedfirst-stage retrieval or ground-truth labels

Think of BM25/DPR as matching functions, PageRank as a graph feature, PRP as an ordering principle, and MMR as a set-aware selection rule. They can occupy different parts of the same pipeline; they are not five interchangeable neural models.

PageRank: follow every number

Original worked example: three pages with links A → B, C, B → C, and C → no out-links. Start at r₀ = (1/3, 1/3, 1/3). Let d = 0.85 mean follow-link probability and use uniform teleportation and uniform dangling-mass redistribution.

Dt = Σu: L(u)=0 rt(u)
rt+1(v) = (1−d)/N + d [Σu→v rt(u)/L(u) + Dt/N]
TargetTeleportDangling C contributionIncoming link contributionAfter one iteration
A0.15/3 = 0.050.85 × (1/3)/3 = 0.094444…00.144444…
B0.050.094444…0.85 × (1/3)/2 = 0.141667…0.286111…
C0.050.094444…0.85 × [(1/3)/2 + 1/3] = 0.4250.569444…

Check: the new entries sum to 1. This is one iteration, not the final stationary distribution. Compute every new entry from the same old vector, then replace the entire vector. Repeat until a stated tolerance such as Σ |r_new − r_old| < ε is met.

What breaks if we ignore C?

Without the dangling term, the next vector sums to 0.15 + 0.85 × 2/3 = 0.716667…. The missing mass is 0.85/3. A dangling page has no outgoing edge; a closed group may have outgoing edges internally but no exit. Teleportation also gives a way to escape such closed groups.

Notation trap: lecture p. 15 uses d for link-following, while p. 17 writes 1−λ for the same role. MMR later uses λ for relevance weight. Read the definition, not just the letter.

From a graph score to a retrieval prior

P(D | q) ∝ P(q | D) P(D)
log score(q,D) = log P(q | D) + log P(D)

Here the language model is the query-likelihood retrieval model, not necessarily a generative LLM. P(q|D) models the query from the document; P(D) favours documents before inspecting this query. A positive, normalised PageRank distribution can supply the prior.

Toy comparison: A has P(q|A)=0.02, P(A)=0.60; B has P(q|B)=0.08, P(B)=0.10. Query likelihood alone favours B; products 0.012 > 0.008 favour A. These products are unnormalised ranking values, not calibrated answer-correctness probabilities. The changed ranking may help or hurt.

MMR: work through the lecture example

Lecture p. 39 supplies relevance values A=0.8, B=0.6, C=0.5 and similarities sim(A,B)=0.9, sim(A,C)=0.1. A and B cover the same interpretation; C covers another plausible one. Start by selecting highest-relevance A. We add the explicit choice λ=0.5 to make the arithmetic reproducible.

CandidateRelevance rewardRedundancy penalty against AMMR at λ=0.5
B0.5 × 0.6 = 0.300.5 × 0.9 = 0.45−0.15
C0.5 × 0.5 = 0.250.5 × 0.1 = 0.050.20

Relevance-only order: A, B, C. With this MMR setting: A, C, B. A negative MMR value is allowed because it is a selection utility, not a probability. No new document has been retrieved: the candidate set is unchanged.

A already selected · B = −0.150; C = 0.200; A → C → B

Why does the order switch near λ=0.89?

B wins when 0.6λ−0.9(1−λ) > 0.5λ−0.1(1−λ), giving λ > 8/9. Equality is a tie, resolved here by original candidate order. At λ=1, only relevance matters. At λ=0, only redundancy matters after the initial seed; choosing A first is an explicit convention for the otherwise empty selected set.

Why maximum similarity, and why recompute?

Once S contains several documents, each remaining candidate is penalised by its most similar selected document, not its average similarity and not the sum. Recompute after every selection because S has changed. The relevance term and the document–document term may use different models; their score scales must be compatible. MMR is greedy and does not promise the global optimum for every list-level objective.

Diversity, nDCG and evidence quality

Metric references: Expected Reciprocal Rank (2009) · Intent-based diversification: metrics and algorithms (2011).

A single relevance label can rate two duplicate documents equally highly. Therefore two lists can have identical ordinary nDCG yet cover different numbers of intents. α-nDCG (alpha-normalised Discounted Cumulative Gain) discounts repeated coverage of the same judged subtopic. ERR (Expected Reciprocal Rank) models stopping at a satisfying result; plain ERR is not automatically an intent-diversity measure. Intent-aware variants such as ERR-IA aggregate per-intent utility.

Connection to Weeks 9–10, not an extra assignment requirement: under a RAG context budget, three near-duplicate passages may leave another necessary fact uncovered. Diversity-aware evidence selection can be tested while fixing the query set, generator, prompt and budget. However, novelty does not guarantee support or truth; complementary evidence, necessary corroboration and conflicting claims must still be checked.

Practice the numerical examples in Revision Q/A

Week 11 · Practical

PageRank as a probability update

Implement pagerank(pages, lam, eps) for the supplied five-page graph. Relate every matrix operation to the lecture’s random surfer. MMR (Maximal Marginal Relevance) remains a lecture topic, not an extra task in this notebook.

Data flow: column-stochastic link matrix M + teleport λ → initial r → repeated probability updates → convergence → page scores

  1. Read matrix orientation

    M[i,j] is the probability of moving FROM page j TO page i. Each column distributes one source page’s outgoing mass and sums to 1. The supplied matrix is already weighted; do not replace its 0.5 entries with 1.

  2. Translate the symbols

    Here lam=0.15 is teleport probability; 1−lam=0.85 follows links. For N=5, each target receives lam/N=0.03 teleport mass. This is the same model as the lecture formula using d=0.85 for link following.

  3. Update all pages together

    Start with r=ones(N)/N and compute r_new=lam/N+(1−lam)*(M @ r). Use the entire old vector for one update; do not overwrite one page and immediately use its new value for the next page.

  4. Define convergence and protection

    One explicit rule is sum(abs(r_new−r))<eps. Assign r_new before returning and set a maximum iteration count as a safety guard. A different norm can produce a different iteration count, so document the rule.

  5. Verify a probability vector

    Check finite nonnegative entries, total probability near 1 and a small fixed-point residual. The classroom matrix has no dangling column. For a new graph, zero-outdegree columns need redistribution, such as uniform 1/N, before applying this stochastic-matrix formulation.

Worked example

Starting from [0.2,0.2,0.2,0.2,0.2], the teacher’s matrix yields [0.200,0.115,0.115,0.285,0.285] after one step. With an L1 stopping threshold of 1e−6 it reaches approximately [0.254192,0.138032,0.138032,0.205990,0.263755] after 57 updates. The two equal middle scores follow from symmetric incoming links. These numbers were checked locally using the supplied matrix.

Check your understanding: Why does the function have no query argument?

PageRank is query-independent graph authority. BM25/DPR estimate query–document matching; MMR also considers already selected results. To test PageRank in retrieval, combine it with a query-dependent score under an explicit rule and evaluate the ranking with qrels.

Source map: prac-week11.ipynb: Implement simple pagerank; official notebook modified 14 October, downloaded 16 October 2026. Independent study explanation; original files remain on the course platform.

Back to Week 11 lecture concepts
Week 12

Relevance Feedback, Query Reformulation, and Rank Fusion

Week 12 asks how a retrieval system can learn from relevance evidence, repair a query, and combine several ranked lists without pretending their raw scores are directly comparable.

Three kinds of relevance feedback

FeedbackEvidenceMain risk
Explicitthe user marks relevant or non-relevant documentshigh quality but requires effort
Implicitbehaviour such as clicks is interpreted as a relevance signalexamination and presentation bias
Pseudo-relevance feedback (PRF)top initial results are assumed relevanta weak first ranking can cause query drift

These differ in certainty, not just interface. “More like this” is an explicit query-by-example signal; ordinary clicks are not automatically relevance labels; PRF normally supplies positive evidence without asking the user.

Rocchio: move the query in vector space

q′ = αq₀ + (β / |Dᵣ|) Σd∈Dᵣd − (γ / |Dₙᵣ|) Σd∈Dₙᵣd

The original query anchors the update; the relevant centroid pulls it toward useful terms; the non-relevant centroid pushes it away. The weights control trust in each source. A component can become negative, and a production system must define whether to keep, clip, or otherwise handle it.

Query expansion families

Add related terms using a thesaurus or controlled vocabulary, corpus/query-log statistics, or top-ranked documents. Domain thesauri such as MeSH can help specialist search, while generic synonym expansion can introduce the wrong sense. Query suggestion offers an alternative query rather than necessarily lengthening the current one.

Association needs context

Dice coefficient and mutual information estimate term association from co-occurrence. Mutual information can favour rare events. Expanding each unigram independently may miss the meaning of a phrase such as tropical fish; whole-query or n-gram context reduces this error but is harder to precompute for every possible query.

Translation language models

pt(w|d) = Σu∈d pt(w|u) p(u|d)

A translation language model gives query term w probability mass through document terms u that may express the same meaning. This translated document model can replace maximum-likelihood p(w|d) inside a smoothed query-likelihood model. Translation probabilities may come from mutual information or embedding cosine similarity, but self-translation must remain strong enough to preserve exact matching.

Embeddings as semantic expansion

Distributional representations place words with similar contexts near one another. Cosine similarity can be normalised into a translation distribution, allowing syntactic variants and related terms to contribute. Similarity is not identity: unrestricted neighbours can add topical but non-relevant words.

Query reduction

Verbose queries can contain off-focus terms. IDF-r retains a chosen proportion of the highest-IDF query terms; learned reduction can use query-performance predictors and other features to predict that proportion. Reduction and expansion solve opposite surface problems but share the same goal: retain evidence that best expresses the information need.

Why fuse rankings?

FamilyUsesExamples
Votingwhich systems nominate a documentplurality, Copeland
Rank aggregationdocument positions in each listBorda, Reciprocal Rank Fusion
Score aggregationscores, often after per-list normalisationCombSUM, weighted linear fusion, CombMNZ

The chorus effect rewards agreement; the skimming effect supplies different documents from different systems; a dark-horse system may contribute uniquely good or uniquely poor evidence. Fusion can improve the best individual run, but it does not guarantee that every added system helps.

RRF and score fusion

RRF(d) = ΣLᵢ:d∈Lᵢ 1 / (v + rLᵢ(d))

Reciprocal Rank Fusion uses only ranks, commonly with v=60, so a deep occurrence contributes less. CombSUM adds scores; linear fusion applies a system weight; CombMNZ multiplies the summed score by the number of supporting lists. Missing documents contribute nothing for that list.

Normalise before combining scores

Raw BM25, language-model and neural scores can have unrelated origins and ranges. Per-list min–max, shifted-sum, or z-score normalisation can align them. A useful scheme should be shift invariant, scale invariant and resistant to an outlier changing every other document’s value. Min–max handles negative scores but is sensitive to extreme minima or maxima.

Worked example: one Rocchio update
Let q₀=(1,0), the relevant centroid be (0.8,0.6), the non-relevant centroid (0.2,0.9), and α=1, β=0.75, γ=0.25. Then q′=(1.55,0.225). The result is a direction for a new retrieval step, not a relevance judgement by itself.
Worked example: RRF can reward agreement
With v=60, document A at ranks 1 and 4 scores 1/61+1/64≈0.03202. Document B at ranks 2 and 1 scores 1/62+1/61≈0.03252, so B wins despite not being first in both lists. Always state whether ranks start at 1.
Worked example: normalising negative scores
For one list with scores [-8,-5,-2], min–max produces [0,0.5,1]. Adding 100 to every raw score gives the same normalised values, showing shift invariance. A new extreme maximum would change the other normalised gaps.

Source status: the released 49-page Week 12 lecture and the released practical notebook with its six supporting files were checked on 20 October 2026. The official Week 12 Live Q/A deck was not available, and no Live Q/A questions are represented as official. Any Week 12 questions in this site are explicitly labelled self-authored practice. Original course files remain private.

Public reading: Stanford IR book: relevance feedback and query expansion · National Library of Medicine: MeSH.

Week 12 · Practical

Reformulate queries and fuse rankings

Implement pseudo-relevance feedback (PRF) expansion, IDF-r reduction, and three rank-fusion methods. Evaluate every change with the same MS MARCO queries and qrels instead of assuming that a longer query or a fused list must be better.

Data flow: 43 queries + index → baseline run → expand or reduce query → MAP/nDCG@10/recall@1000; four runs → per-query normalisation → Borda/CombSUM/CombMNZ → paired comparison

  1. Establish one evaluation baseline

    Load the 43 supplied queries, retrieve up to 1,000 documents with the same Lucene analyzer, and write qid, Q0, docid, rank, score and run tag. The supplied qrels contain many judged pairs, including relevance label 0; a qrel row is a judgment, not automatically a relevant document.

  2. Expand through pseudo-relevance feedback

    Retrieve an initial top-50 list, treat only the top n as pseudo-relevant, obtain each document vector, and aggregate candidate term evidence such as TF-IDF. Select the top m expansion terms, append them to the analyzed original query, rerun retrieval, then compare MAP, nDCG@10 and recall@1000. Exclude accidental noise and explain any query drift.

  3. Reduce a verbose query with IDF-r

    Analyze the query using the same Lucene analyzer, obtain document frequency for each resulting term, compute the practical’s IDF convention, and retain the n highest-IDF terms. Decide explicitly how duplicates, ties and n larger than the term count behave. A ratio-based variant must convert the ratio to a documented integer count.

  4. Normalise scores before score fusion

    The four supplied runs use TF, IDF, TF-IDF and BM25 scales. For each query and each run separately, min–max normalise scores before CombSUM or CombMNZ. Handle a constant-score list explicitly because its maximum equals its minimum. Borda uses rank positions, so raw score scale is irrelevant to its vote.

  5. Implement and compare three fusion rules

    With a one-based rank r in a list of length n, Borda contributes (n−r+1)/n; if enumerate starts at zero i, use (n−i)/n. CombSUM adds normalised scores over the union of documents. CombMNZ multiplies that sum by the number of runs in which the document has a positive score. Try combinations of the four runs, report MAP and nDCG, and use paired per-query tests for the chosen comparison.

Worked example

For two three-document rankings A=[d1,d2,d3] and B=[d2,d3,d4], Borda awards [1,2/3,1/3] by position. Totals are d2=5/3, d1=1, d3=1 and d4=1/3. If normalised score runs instead give d1 scores .9 and .2, d2=.4 once and d3=.8 once, CombSUM gives 1.1, .4 and .8; CombMNZ gives 2.2, .4 and .8 because only d1 has positive support from two runs.

Check your understanding: Why can fusion perform worse than its strongest input run?

Fusion can add correlated errors, reward documents repeated by several weak systems, or distort evidence through unsuitable normalisation. Compare against every component run on the same qids, inspect per-query differences, and distinguish a mean gain from statistically reliable improvement.

Source map: prac-week12.ipynb: Exercises 1–3 and the supplied MS MARCO qrels, queries and four run files; released and reviewed 20 October 2026. Independent study explanation; original files remain on the course platform.

Back to Week 12 lecture concepts
Week 13

Efficient Inverted Indexes and Query Processing

Week 13 returns to the inverted index and asks an engineering question: how can a search engine return good top-k results quickly over very large collections? It covers compressed postings, quantized impact scores, dynamic pruning and the efficiency cost of learned sparse retrieval, then closes with the final oral exam format.

Why inverted indexes still matter

Exact term matching is still needed for some searches, BM25 remains a strong baseline on unseen data, and inverted indexes scale well as collections grow. Learned sparse models such as SPLADE and TILDEv2 also store their output in inverted indexes, so index efficiency directly limits how practical they are. At web scale, a good result returned quickly is usually worth more than the best result returned slowly.

Postings, gaps and block access

A posting pairs a document identifier with a term frequency or score, and identifiers in a list are strictly increasing. Storing the gaps between consecutive identifiers (delta coding) produces small integers that compress well. The cost is that reaching the n-th identifier needs a prefix sum over earlier gaps. Block-based indexes store each block’s first identifier directly, so a lookup only sums gaps inside one block and whole blocks can be skipped without decompressing them.

Compression is a trade-off

Variable Byte (VByte) coding stores 7 data bits per byte and uses the remaining bit to signal whether another byte follows, so small integers use fewer bytes. Real systems mostly use block-based codecs. Smaller encodings usually take longer to encode and decode, so the right codec depends on whether space or query latency matters more, a position on a space–time Pareto frontier.

Matching is separate from ranking

A Boolean conjunction (AND) returns only documents containing every query term, found by advancing the shortest list and seeking forward in the others. A disjunction (OR) admits documents containing any term. The matching rule does not fix the ranking: a ranked conjunction scores only the conjunctive matches, while top-k disjunctive retrieval trusts the ranking function to score any matching document.

Precomputed and quantized impacts

Id,t = round( 2b · (sd,t − smin) / (smax − smin) )

For an additive model such as BM25, the only query-dependent part is which terms appear, so each term–document contribution sd,t can be computed at indexing time. Floating-point scores compress poorly, so a global min–max mapping turns them into b-bit integers stored in the postings instead of term frequencies. A document’s score becomes a sum of impacts. Note that 2b itself needs b+1 bits, so implementations usually scale by 2b − 1 or clamp the maximum.

Top-k retrieval and dynamic pruning

Exhaustive top-k retrieval scores every posting while keeping a min-heap of the best k documents; it is rank-safe but decompresses and scores everything. Dynamic pruning keeps the same rank-safe result with less work. Store each list’s maximum impact Ut at indexing time, use the heap’s smallest score as a threshold θ, and add up the upper bounds of the lists that contain a candidate. If that bound cannot beat θ, the document is skipped without scoring, and skipped blocks need not be decompressed. The requirements are an additive scoring function, precomputed list upper bounds and efficient random access within lists. Deciding whether to skip has its own overhead.

WAND and MaxScore

WAND (“weak” or “weighted” AND) sorts lists by their current document and finds the first pivot whose accumulated upper bounds exceed θ; documents before the pivot cannot qualify. MaxScore sorts terms by upper bound and marks the low-bound terms whose combined bounds cannot reach θ as non-essential: candidates come only from essential lists, and non-essential lists are probed for those candidates.

DAAT, TAAT and SAAT

StrategyTraversal orderState
Document-at-a-time (DAAT)all lists together, one document at a timeheap of current top k
Term-at-a-time (TAAT)one whole list at a timeone accumulator per document
Score-at-a-time (SAAT)postings grouped by impact, highest impacts firstaccumulators; can stop early

Why learned sparse retrieval is harder to make fast

Inverted indexes are efficient because of sparsity: a document is about few terms, a term occurs in few documents, and a query has few terms. Zipf’s law keeps most lexical terms rare. Learned sparse models weaken all three assumptions. Expansion adds many terms to documents and queries; some tokens are repurposed and appear in almost every document, behaving partly like a dense vector; and long lists can receive high learned impacts, whereas BM25 gives long lists low impacts. Upper bounds then stay high, pruning removes fewer candidates, more postings are scored and queries run slower. Regularisation that encourages sparsity is one response.

Final oral exam: format and preparation

StageWhat happensHow to prepare
First 5 minutesyou receive two prompt questions while your identification is checkedplan a short explanation for each: definition, mechanism, example and limitation
Main dialogueyou answer one prompt, then the examiner asks follow-up questions about details, problems and fixespractise explaining why a method works and what can go wrong, not only what it is
Topic changesthe examiner may move to other course topics to confirm your level or give you a chance at a higher bandconnect weeks: representation → retrieval → reranking → evaluation → RAG and agents

The exam lasts 30 minutes, is closed book and requires identification; no notes or devices may be used, and no mark is given at the end because results are moderated across the teaching team. Book your slot through the course’s official channel. Treat it like a technical interview: think aloud, state assumptions and correct yourself if needed.

Worked example: gaps and block-based lookup
Postings [3, 7, 8, 15, 30, 31, 45, 52] become gaps [3, 4, 1, 7, 15, 1, 14, 7]. Without blocks, finding the 7th identifier sums six gaps after the first. With blocks of four that store first identifiers 3 and 30 directly, the 7th identifier is 30 + 1 + 14 = 45, using only two additions.
Worked example: Variable Byte coding
Split the integer into 7-bit groups from the most significant end, set the continuation bit to 1 on every byte except the last. 130 = 1·128 + 2 is coded as 10000001 00000010; 300 = 2·128 + 44 as 10000010 00101100; 5 fits in one byte, 00000101. A 32-bit integer would always use four bytes.
Worked example: quantizing an impact
With smin=0, smax=20 and b=8, a BM25 contribution of 7.5 maps to 256 × 7.5 / 20 = 96. The maximum score would map to 256, which needs 9 bits, which is why scaling by 255 or clamping is used in practice.
Worked example: when can a document be skipped?
Let the list upper bounds be Ua=4, Ub=7, Uc=3 and the current heap threshold θ=9. A document in lists a and c has a bound of 7 < 9 and is skipped without scoring. A document in lists a and b has a bound of 11 ≥ 9 and must be scored exactly. For MaxScore, sort the bounds 3 (c), 4 (a), 7 (b): c and a together reach only 7 < 9, so they are non-essential and only list b generates candidates.

Source status: the 206-slide Week 13 guest lecture on efficient inverted indexes and the four-slide final exam briefing were checked on 27 October 2026. No Week 13 Live Q/A deck was available, so all Week 13 questions in this site are explicitly labelled self-authored practice. Original course files remain private.

Public reading: Stanford IR book: index compression · Stanford IR book: efficient scoring and ranking.

Course clarifications · checked 13 October 2026

Project 2: main task versus bonus data

These are dated paraphrases of staff replies, not new assessment rules. Follow the latest course notebook and marking sheet if later updates differ.

ScopeVerified clarificationPractical consequence
Main Project 2 / Task 2The earlier “development set” wording refers to the sampled collection, queries and qrels; staff corrected the notebook wording.Use the simplified main-task sampled-data protocol. Do not reinterpret the bonus training queries as the main task's development set.
Dense-retriever fine-tuning bonusTrain queries/qrels are reserved for the bonus. A separate staff reply says dev queries/qrels have now been attached under the bonus folder.Obtain the official bonus files; train on train data and use dev data for checkpoint/hyperparameter selection according to the bonus instructions.

Important distinction: the main-task terminology correction and the later bonus dev-file addition concern different scopes. They are not contradictory. The bonus question identifies dev_queries.tsv and dev_qrels.txt. Staff confirmed availability; this website update has not checked the contents or counts of those new files.

For a scientific report, state exactly which data selected a model and which data evaluated it. Reusing a sample for selection and comparison is a course simplification, not evidence of an independent held-out generalisation estimate.

Staff clarification: main-task sampled data (login required) · Staff clarification: bonus dev files (login required)

TILDEv2 modeling.py: still awaiting confirmation

A newer course question asks which modeling.py source to use. No staff answer was visible when checked. This page therefore does not approve a replacement implementation. Compare the class API and checkpoint compatibility before treating files from different versions as interchangeable.

Open the pending course question (login required)

Formula sheet

Formula reference

Identify the variables, then ask what each factor rewards or penalises.

NameFormulaInterpretation
P@krelevant in top k / kprecision within cutoff k
Recallretrieved relevant / all relevantcoverage of the relevant set
F12PR/(P+R)harmonic mean of P and R
AP(1/|Rel|) Σ P@k × rel(k)record precision whenever a relevant result appears
MAPmean(AP over queries)each query has equal weight
RR1/rank(first relevant)only the first relevant result matters
nDCG@KDCG@K / IDCG@Kgraded relevance plus position discount
RBP(1-p)Σ r_i p^(i-1)p models continuation probability
Model matrix

Representation, scoring, loss, and negatives

For model questions, classify each claim by these components instead of memorising one sentence.

ModelRepresentation / poolingSimilarity / interactionTrainingRole
BM25sparse term statisticsweighted sum over termsusually untrained; tune k1,bstrong lexical baseline
TILDEv2query token IDs; contextual document-token weightsexact match + per-term max weightdocument-side neural learning and expansionfast learned sparse reranker
SPLADE(v2)mostly-zero vocabulary vectorssparse dot productMLM head, distillation, sparsity regularisationlearned sparse retrieval
PromptRepsLLM dense state + sparse logitsnormalised hybrid scorezero-shothybrid representation
DPRCLS bi-encoderdot productInfoNCE/NLL; in-batch and hard negativesfirst-stage dense retrieval
RepBERTmean token embeddingsinner productMultiLabelMarginLossBERT bi-encoder
ANCECLS / first tokendot productNLL/InfoNCE-style; ANN self-mined negativesdynamic hard-negative mining
Contrievermean poolingcosineunsupervised contrastive; same-document spansunsupervised dense retriever
ColBERTall token embeddingslate-interaction MaxSimcontrastive / pairwise CEefficient fine-grained matching
E5-MistralMistral decoder; EOS/last tokentemperature-scaled cosineInfoNCE; synthetic and supervised dataLLM embedding model
LLM2Vecdecoder with bidirectional attention; poolingoften cosineMNTP + unsupervised SimCSE + optional supervisiondecoder converted to encoder
RepLLaMALlama2; EOS last hidden statedot productInfoNCE; supervision + LoRALLM retriever
Cross-encoderjoint query-document encodingclassification/regression relevance headpointwise, pairwise, or listwisehigh-accuracy reranker
monoBERT[CLS] q [SEP] d [SEP]relevant-class softmax scorebinary cross-entropy; BM25 negativespointwise BERT reranker
BERT-MaxP / FirstP / SumPdocument passagesmax / first / sum passage scoretransferred document labelslong-document score aggregation
PARADEpassage vectorsaverage / max / attention / Transformer aggregationdocument-level rankingrepresentation aggregation
duoBERTquery + two documentspairwise preference aggregationpairwise cross-entropylate-stage BERT reranker
LLM pointwise / pairwiseone document / document pair in a promptlabel logits / preferencezero-shot promptingindividual judgement / comparison
LLM listwise / setwisecandidate list / small setpermutation / best-item logitszero-shot promptinglist context / efficient selection
Corpus-in-Contextwhole corpus in an LC-LLM promptgenerated document IDsfew-shot prompting; no retriever trainingsmall-corpus model-based retrieval
Screenshot retrieverpage pixels and layoutVLM similarityvision-language contrastive learninglayout-rich documents
DiffRetrieverparallel representative tokensmulti-representation matchingdiffusion language modelgenerative multi-vector retrieval
Basic RAGquery + top-k evidenceautoregressive answerretriever and generator may be frozenevidence-based IR4LLM
Rewrite-Retrieve-Readrewritten query + evidencedownstream answer rewardpseudo-data and optional policy optimisationunderspecified questions
BlendFilterretrieved and model-generated knowledgefilter then generateprompted LLM modulesremove distractors
RARRdraft + researched evidencesupport check and revisionpost-hoc research/revisionretrofit attribution
PageRankdirected graph; one value per pagestationary random-surfer probabilitypower iteration, no relevance-label training requiredquery-independent authority feature
PRPestimated document relevance probabilitiesdescending probability ordera ranking principle, not a trained modelrelevance-oriented ordering
MMRcandidate scores + document similarities + selected setrelevance reward minus maximum redundancygreedy selection; tune the trade-off separatelydiversity-aware candidate reranking
Example multiple-choice logic: the ColBERT and DPR pairings are correct, as is RepBERT with mean pooling, inner product, and Multi-Label Margin Loss. ANCE normally uses dot product, not cosine. E5-Mistral's EOS pooling and InfoNCE are plausible, but “mean-pooling similarity” confuses pooling with the similarity function.
Acronym and definition glossary

Full names and key definitions

Short name → full English name → definition. Model names that are not acronyms are identified separately.

Short nameFull nameDefinition
IRInformation RetrievalFinding and ranking documents that satisfy an information need.
TF / DF / CFTerm Frequency / Document Frequency / Collection FrequencyCounts within one document, across documents containing the term, and across all term occurrences.
IDFInverse Document FrequencyA term's discriminative weight based on how few documents contain it.
TF-IDFTerm Frequency-Inverse Document FrequencyCombines local frequency with collection rarity.
VSM / BIMVector Space Model / Binary Independence ModelVector similarity and probabilistic term-independence approaches to ranking.
BM25Best Matching 25A lexical model combining IDF, tf saturation, and length normalisation.
RSJ / F1Robertson-Spärck Jones / F-score with β = 1A probabilistic IDF weighting foundation for BM25, and the harmonic mean of precision and recall.
AP / MAPAverage Precision / Mean Average PrecisionAverage precision at relevant ranks for one query, then averaged across queries.
RR / MRRReciprocal Rank / Mean Reciprocal RankMeasures where the first relevant result appears.
DCG / IDCG / nDCGDiscounted Cumulative Gain / Ideal DCG / Normalized DCGCombines graded relevance and rank discount, then normalises by the ideal order.
RBPRank-Biased PrecisionModels a user's probability of continuing down the ranking.
PageRankModel name, not an acronymA query-independent link-authority score defined by the stationary probability of a random surfer with teleportation.
PRPProbability Ranking PrincipleRanks documents by decreasing estimated probability of relevance, under assumptions including accurate estimates and independent relevance utility.
MMRMaximal Marginal RelevanceA greedy reranking rule that trades query relevance against redundancy with already selected results.
α-nDCGAlpha-normalised Discounted Cumulative GainA subtopic-aware measure that discounts repeated coverage of the same intent.
ERR / ERR-IAExpected Reciprocal Rank / Intent-Aware Expected Reciprocal RankERR models satisfaction-based stopping; ERR-IA averages per-intent utility using intent weights. Plain ERR is not automatically a diversity metric.
RF / PRFRelevance Feedback / Pseudo-Relevance FeedbackUpdates retrieval from relevance evidence; PRF assumes top initial results are relevant without asking the user.
RocchioModel name, not an acronymMoves a vector-space query toward the relevant centroid and away from the non-relevant centroid.
TLM / NTLMTranslation Language Model / Neural Translation Language ModelModels a query term through document terms that can translate to it; NTLM estimates relations from embeddings.
QPPQuery Performance PredictionEstimates how well a query may retrieve, and can guide how aggressively a verbose query is reduced.
RRF / CombMNZReciprocal Rank Fusion / Combination Multiply Non-ZeroCombines ranks through reciprocal discounts, or multiplies a score sum by the number of supporting lists.
VByteVariable Byte codingStores an integer in 7-bit groups, with one bit per byte signalling whether another byte follows.
WANDWeak (or Weighted) ANDA dynamic pruning algorithm that uses list upper bounds to find a pivot and skip documents that cannot enter the top k.
MaxScoreAlgorithm name, not an acronymDynamic pruning that splits terms into essential and non-essential lists by their upper bounds.
DAAT / TAAT / SAATDocument-, Term- and Score-at-a-timeIndex traversal orders: all lists per document, one list at a time, or postings in decreasing impact order.
LSRLearned Sparse RetrievalLearns term weights (and often expansion terms) but still retrieves through an inverted index.
BERTBidirectional Encoder Representations from TransformersAn encoder model that can jointly contextualise query and document tokens.
CLS / SEP / EOSClassification / Separator / End of Sequence tokenSpecial tokens for classification summaries, segment boundaries, and sequence endings.
MLM / FFNMasked Language Modeling / Feed-Forward NetworkA masked-token pretraining objective and the per-token nonlinear sublayer in a Transformer block.
GPT / LLMGenerative Pre-trained Transformer / Large Language ModelDecoder-style generation family and the broader class of large pretrained language models.
DPRDense Passage RetrievalA bi-encoder that retrieves by dense query-passage vector similarity.
ColBERTContextualized Late Interaction over BERTRetains token vectors and applies MaxSim for fine-grained late interaction.
ANN / ANCEApproximate Nearest Neighbour / Approximate Nearest Neighbor Negative Contrastive EstimationFast approximate vector search and a retriever that mines its ANN mistakes as hard negatives.
NLL / InfoNCENegative Log-Likelihood / Information Noise-Contrastive EstimationObjectives that penalise low target probability and contrast positives against negatives.
CECross-EntropyA classification loss comparing target and predicted distributions.
TILDETerm Independent Likelihood moDElLearns document-side vocabulary term likelihoods for efficient matching.
SPLADESparse Lexical and Expansion ModelLearns sparse vocabulary weights and semantic expansion terms.
ReLU / FLOPSRectified Linear Unit / Floating-Point OperationsProduces non-negative activations, while the FLOPS-inspired regulariser discourages overly dense SPLADE vectors.
T5Text-to-Text Transfer TransformerA sequence-to-sequence model that can generate offline doc2query expansions.
LTR / OLTRLearning to Rank / Online Learning to RankLearns an ordering from labelled data or continuously from user interactions.
IPSInverse Propensity ScoringReweights observations by inverse exposure probability to correct bias in expectation.
DBGDDueling Bandit Gradient DescentUses interleaving outcomes to move toward a winning exploratory ranker.
COLTRCounterfactual Online Learning to RankEvaluates candidate rankers off-policy using logged clicks and propensities.
RM3 / TRECRelevance Model 3 / Text REtrieval ConferenceA pseudo-relevance feedback model and a major standard IR evaluation programme.
QrelsQuery Relevance JudgementsGround-truth query-document relevance labels used to evaluate a run.
MS MARCO / BEIRMicrosoft Machine Reading Comprehension / Benchmarking Information RetrievalWidely used neural-ranking training data and a cross-domain retrieval benchmark suite.
JSONLJSON LinesStores one independent JSON object per line for streaming datasets.
LoRA / MNTP / SimCSELow-Rank Adaptation / Masked Next Token Prediction / Simple Contrastive Learning of Sentence EmbeddingsEfficient fine-tuning and representation-learning methods used by later embedding models.
PARADEPassage Representation Aggregation for Document RerankingAggregates encoded passage vectors for long-document ranking.
LLM4IR / IR4LLMLarge Language Models for Information Retrieval / Information Retrieval for Large Language ModelsUsing LLMs to improve IR versus retrieving evidence to support an LLM.
monoBERT / duoBERTModel names, not acronymsPointwise relevance scoring versus pairwise document preference.
RAG / LC-LLMRetrieval-Augmented Generation / Long-Context Large Language ModelRetrieve a small evidence set for generation versus place much more source text directly in context.
CiC / CoTCorpus-in-Context / Chain-of-ThoughtDirect corpus prompting for retrieval and generated intermediate reasoning steps.
VLM / HyDEVision-Language Model / Hypothetical Document EmbeddingsModels pixels and language; or retrieves by embedding a generated hypothetical answer document.
RARRRetrofit Attribution using Research and RevisionResearches evidence for a draft and revises unsupported claims.
PPOProximal Policy OptimizationA reinforcement-learning method that can optimise a trainable query rewriter while limiting update size.
Assignment 1

End-to-end A1 workflow

A1 is not just a BM25 function. It is a reproducible IR experiment with validation, tuning, comparison, and analysis.

Open the experiment study workflow. No personal submission or experiment outputs are included in this public guide.

Why separate train and test?

Train qrels select k1 and b. Test qrels are used once for unbiased final evaluation. Repeatedly changing parameters after inspecting test results leaks test information into training.

How to discuss tuned BM25

Do not write only “the score improved.” Explain how k1 changes tf saturation and b changes length normalisation, then use gain/loss queries to diagnose the effect.

# Clear scorer skeleton; adapt names to the supplied notebook
def bm25(tf_vector, df_vector, doc_len, k1=1.2, b=0.75):
    score = 0.0
    for tf, df in zip(tf_vector, df_vector):
        idf = math.log(N / (1 + df))
        norm = 1 - b + b * (doc_len / average_doc_length)
        tf_weight = ((k1 + 1) * tf) / (tf + k1 * norm)
        score += idf * tf_weight
    return score
Recall practice

Self-test

Answer first, then expand. Being able to explain why is the real test.

1. What are tf, df, and cf?
tf is the term count in the current document; df is the number of documents containing the term; cf is the term's total count across the collection.
2. Why does BM25 saturate tf?
The jump from zero to one occurrence is more informative than 100 to 101. Saturation prevents repetition from increasing the score without limit.
3. Why divide DCG by IDCG?
Queries differ in the number and grades of relevant documents. Normalisation provides a comparable scale, usually between zero and one.
4. What does p-value < .05 mean?
If H₀ were true, the probability of the observed or a more extreme difference is below 5%. It is not the probability that system B is better.
5. Why scale attention by √d_k?
Dot-product variance grows with dimension. Scaling prevents an excessively sharp softmax and helps stable gradients.
6. Encoder versus decoder?
An encoder typically sees both left and right context for understanding. A decoder uses a causal mask and sees only the left prefix for generation.
7. Why can dense retrieval match synonyms?
Training maps semantically related expressions to nearby vectors rather than requiring identical surface terms.
8. How does ColBERT calculate its score?
For every query token, find the highest similarity to any document token, then sum those maxima.
9. Why are hard negatives useful and risky?
They look relevant and provide strong gradients, but incomplete qrels can make truly relevant documents appear as false negatives.
10. Why not tune BM25 on the test set?
It adapts parameters to test judgements and makes the estimate of generalisation optimistically biased.
11. Why is SPLADE sparse although it uses BERT?
It outputs a vocabulary-sized vector with mostly zero dimensions. BERT learns which dimensions should be active.
12. TILDEv2 versus SPLADE?
TILDEv2 uses lightweight query token IDs and learned document-token weights; SPLADE encodes both sides into sparse vocabulary vectors.
13. Why put BM25 before TILDEv2?
BM25 cheaply narrows the full collection, then TILDEv2 reranks only plausible candidates.
14. Pointwise, pairwise, and listwise?
They learn from one document, a document preference pair, or an entire ranked list respectively.
15. Why are clicks biased?
Clicks depend on examination, position, selection and presentation as well as relevance.
16. What is the main purpose of IPS?
To correct exposure bias by weighting observations with inverse examination probability.
17. How does balanced interleaving work?
Mix two rankers' unseen results into one list and attribute clicks to infer pairwise preference.
18. Why use counterfactual OLTR?
It reuses one propensity-logged interaction stream to estimate several candidate rankers off-policy.
19. Why must monoBERT follow a retriever?
Joint encoding is too expensive for the whole collection. BM25 first creates a manageable candidate set that monoBERT can reorder.
20. Score aggregation versus representation aggregation?
MaxP/FirstP/SumP combine scalar passage scores; PARADE combines passage vectors before making a document-level decision.
21. monoBERT versus duoBERT?
monoBERT scores one document independently; duoBERT directly compares two documents.
22. Four LLM reranking families?
Pointwise judges one item, pairwise compares two, listwise generates an order, and setwise selects the best from a small set.
23. Why may setwise ranking cost less?
It compares several passages per inference using logits, reducing pairwise calls and avoiding full list generation.
24. Why does prompt wording matter?
Roles, output constraints, formatting, and component order alter the model context; sensitivity also varies by model.
25. LLM4IR versus IR4LLM?
LLM4IR applies LLMs to retrieval/ranking; IR4LLM retrieves external evidence for a generator.
26. Why can long context still miss evidence?
Position bias and lost-in-the-middle mean that fitting text into a context window does not guarantee that the model uses it.
27. Relevance versus groundedness?
Relevance asks whether a passage helps the query; groundedness asks whether answer claims are supported by the supplied evidence.
28. Why can one distractor harm RAG?
Semantic alignment without answer support introduces a competing signal that can mislead the generator.
29. RAG versus fine-tuning?
RAG changes inspectable external evidence at inference; fine-tuning changes model parameters.
30. What does RARR do?
It researches evidence for a draft, adds attribution, and revises unsupported content after generation.
31. Why are link authority and anchor text different signals?
Authority depends on the linking graph and the importance of endorsing pages; anchor text supplies a link author's description of the target page. One is structural evidence, the other is descriptive text.
32. What makes an incoming link contribute more PageRank?
It comes from a page with more PageRank and competes with fewer outgoing links. Teleportation and dangling-page handling keep the probability distribution well-defined.
33. Why is PageRank not a relevance score?
It is query-independent graph importance. A ranker may add it as a document prior or feature alongside query-dependent lexical or semantic evidence, then validate the combination empirically.
34. How does MMR address a limitation of a pure PRP ranking?
Pure relevance ordering can repeat the same aspect. MMR greedily balances relevance against similarity to already selected results, increasing novelty and coverage at a possible relevance cost.
35. Explicit, implicit, and pseudo relevance feedback differ how?
Explicit feedback is a direct user judgement; implicit feedback infers relevance from behaviour and inherits behavioural bias; PRF simply assumes the initial top results are relevant.
36. What do the three Rocchio terms do?
The original query anchors the update, the relevant centroid attracts it, and the non-relevant centroid repels it. α, β and γ control the respective strengths.
37. Why can PRF make retrieval worse?
If the initial top documents represent the wrong sense or topic, their terms pull the reformulated query away from the real information need: query drift.
38. Why normalise scores before CombSUM?
Different rankers may use incomparable ranges, signs and distributions. Without per-list normalisation, the system with numerically larger scores can dominate for an arbitrary reason.
39. RRF versus CombMNZ?
RRF uses only rank positions and discounts deep occurrences. CombMNZ uses normalised scores and multiplies their sum by the number of lists that returned the document.
40. Why does delta coding help, and what does it cost?
Gaps between increasing identifiers are small integers that compress well. Accessing the n-th identifier then needs a prefix sum, which block-based indexes limit to one block by storing each block's first identifier.
41. Why store quantized impacts instead of term frequencies?
For additive models the term–document contribution can be precomputed. Mapping it to a small integer makes it compressible and turns query scoring into summing impacts.
42. When can dynamic pruning skip a document safely?
When the sum of upper bounds of the lists containing it cannot exceed the current top-k threshold. The final top k is unchanged, so the method stays rank-safe.
43. DAAT versus TAAT versus SAAT?
DAAT processes all lists together one document at a time with a heap; TAAT processes one list at a time with per-document accumulators; SAAT processes postings from the highest impact down and can stop early.
44. Why do learned sparse indexes prune less effectively?
Expansion and repurposed tokens create long lists with high learned impacts, so upper bounds stay high, fewer candidates are skipped and more postings are scored.
Source map

Scope of this guide

The guide synthesises the supplied INFS7410 folder. Large corpora, indexes, and virtual environments are experimental resources rather than revision content.

  • Week 1 lecture notes, slides, and practical
  • Week 2 lecture notes, slides, and practical
  • Week 3 lecture notes, slides, and practical
  • Week 4 notes, Transformer worksheets, and solution
  • Week 5 lecture, DPR/ColBERTv2/RepLLaMA practical and supplementary training exercises
  • Week 6 TILDEv2 and SPLADEv2 practical
  • Week 6 learned sparse notes
  • Week 7 lecture and MQ2007 practical: logistic LTR, DBGD, interleaving and click simulation
  • Week 8 lecture and refreshed practical: monoBERT, TinyLlama, MiniCPM, Qwen3-Reranker and pairwise scoring
  • Week 9 lecture and practical: RAG construction, prompting, evidence checks and thinking-mode comparison
  • Week 10 full deck, live Q/A deck and practical: search agents and agent-aware retrieval.
  • Week 11 lecture and five-page PageRank practical: link analysis, anchor text, PageRank, document priors, PRP, ambiguity, redundancy, MMR and diversity evaluation.
  • Week 12 released lecture and practical: relevance feedback, PRF expansion, IDF-r reduction, translation language models, Borda/CombSUM/CombMNZ rank fusion and score normalisation. Its official Live Q/A deck was not available when checked. Original course files remain private.
  • Week 13 guest lecture on efficient inverted indexes (compressed postings, quantized impacts, dynamic pruning, DAAT/TAAT/SAAT and learned sparse efficiency) and the final oral exam briefing. No Week 13 Live Q/A deck was available; Week 13 questions here are self-authored practice.
  • Project 2 notebook, sampled BRIGHT Biology collection and marking sheet
Coverage: this edition integrates Weeks 1–13 and connects retrieval representations, candidate ranking, click feedback, neural reranking, RAG, interactive agent search, web ranking, feedback-driven query reformulation, rank fusion and efficient index-based query processing.
Question directory

Independent practice and revision Q/A

Browse 67 independent revision topics by week. These practice questions apply course concepts through rewritten scenarios and worked examples; they are not official slide questions or an official answer key. Select a topic, attempt the question, then expand its explanation. No original slide question text is published.

Open all questions, search and review progress

Week 1 (7)
  1. Information need, query and relevance
  2. Search architecture
  3. Stemmers
  4. Zipf’s law
  5. Domain-specific stoplists
  6. Text processing true/false
  7. Search in the LLM era
Week 2 (6)
  1. Precision, AP and MAP
  2. Reciprocal rank
  3. Normalised DCG
  4. Rank-Biased Precision
  5. Working with qrels
  6. Implement evaluation functions
Week 3 (6)
  1. Lexical models: features and limitations
  2. Normalised term frequency
  3. Inverse document frequency
  4. TF-IDF term weights
  5. TF-IDF query score
  6. Repeated terms and BM25 components
Week 4 (5)
  1. Vocabulary mismatch and self-attention
  2. Transformer components
  3. BERT versus GPT
  4. Input embedding matrix
  5. Use encoders/decoders for ranking
Week 5 (5)
  1. Encoder text representations
  2. Decoder similarities
  3. InfoNCE calculation
  4. Margin loss calculation
  5. Harder negatives
Week 6 (5)
  1. Why TILDE is efficient
  2. SPLADE term weights
  3. PromptReps hybrid retrieval
  4. SPLADEv1 sum pooling
  5. SPLADEv2 max pooling
Week 7 (6)
  1. Offline Learning to Rank
  2. Cascade ranking
  3. Worked interleaving preference
  4. IPS estimator
  5. DBGD with balanced interleaving
  6. Counterfactual OLTR
Week 8 (4)
  1. monoBERT versus dense retrieval
  2. monoBERT limitations
  3. Handle long documents: MaxP and PARADE
  4. Four decoder reranking methods
Week 11 (9)
  1. Link authority and anchor text
  2. PageRank calculation logic
  3. PageRank versus relevance
  4. PRP assumptions and MMR diversification
  5. Why must PageRank preserve probability mass?
  6. Does λ always mean the same thing?
  7. Calculate the second MMR result
  8. Can MMR be computed once for every document?
  9. Does ordinary nDCG prove good intent coverage?
Project 2 (1)
  1. Which data belongs to the main task and which to the bonus?
Week 12 (8)
  1. Which feedback signal should be trusted most?
  2. Calculate a Rocchio update
  3. Why can pseudo-relevance feedback drift?
  4. Compare two RRF candidates
  5. Why normalise scores before CombSUM?
  6. What must stay consistent in IDF-r reduction?
  7. Avoid Borda's indexing trap
  8. Compare CombSUM and CombMNZ
Week 13 (5)
  1. Use block starts to find a document identifier
  2. Encode integers with Variable Byte
  3. Quantize a BM25 contribution
  4. Decide which documents need scoring
  5. Explain why learned sparse retrieval is slower
No matching content. Try a shorter term.