Candidate retrieval
BM25, dense and learned sparse models search the full collection.
Information Retrieval · Weeks 1–13 · Practicals · Projects
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.
One course pipeline, with the code exercises next to the concepts they make concrete.
| Week / Lecture | Practical | Concept bridge |
|---|---|---|
| Week 1 | Text analysis and indexing | Tokens, tf/df/cf, inverted indexes and Zipf |
| Week 2 | From runs to defensible comparisons | Qrels, ranking measures and paired tests |
| Week 3 | Implementing lexical scoring | TF-IDF, BM25 saturation and candidate limits |
| Week 4 | Follow the Transformer tensors | Attention, tensor shapes, pooling and prediction |
| Week 5 | Single-vector, multi-vector and decoder retrieval | Bi-encoders, late interaction and decoder embeddings |
| Week 6 | Inspect learned term weights | Contextual weighting, exact matching and expansion |
| Week 7 | Learn from labels, then from clicks | Pointwise loss, clicks, interleaving and DBGD |
| Week 8 | Neural and LLM reranking | Cross-encoding, answer-token scores and pairwise ranking |
| Week 9 | Build and test evidence-grounded RAG | RAG, attribution, missing evidence and controlled prompts |
| Week 10 | From a retrieval call to a search–read loop | Policy, tools, observations, state and budgets |
| Week 11 | PageRank as a probability update | Random surfer, stochastic matrices and convergence |
| Week 12 | Reformulate queries and fuse rankings | PRF, 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.
Place each weekly topic inside one software pipeline instead of memorising isolated functions.
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.BM25, dense and learned sparse models search the full collection.
Rerankers and LTR models reorder a manageable candidate set.
Qrels support offline metrics; clicks require bias-aware online methods.
Understand how a search engine converts a large text collection into a structure that can be searched efficiently.
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.
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
A small number of terms are extremely frequent, while most terms are rare. Frequency falls approximately as a power law with rank.
This produces a long tail. Very frequent items are often function words; very rare items may be names, spelling variants, or noise.
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.
| Level | Posting contents | Supported capability |
|---|---|---|
| Boolean | docID | presence and AND / OR / NOT |
| Counts | docID + tf | TF, TF-IDF, and BM25 ranking |
| Positions | docID + tf + positions | phrase and proximity queries |
| Doc vectors | terms and statistics per document | custom scorers read tf/df; A1 requires -storeDocvectors |
df is not the total number of occurrences. A term appearing 20 times in one document contributes 1 to df but 20 to cf.index_reader.stats().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
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.
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.
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.
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.
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.
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 conceptsOffline evaluation requires queries, qrels, and runs. Each measure represents a different user model.
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.
F1 is the harmonic mean of precision and recall. β>1 emphasises recall; β<1 emphasises precision.
P@k contributes only when the item at rank k is relevant. Relevant documents that were never retrieved remain in |Rel|, reducing AP.
These measures care only about the first relevant answer, making them suitable for question answering and navigational search.
Graded relevance receives exponential gain and lower ranks receive a discount. IDCG is the score of the ideal ordering for the same query.
p is the probability that the user continues to the next result. Expected viewing depth is 1/(1-p).
Score the same queries with systems A and B, calculate one difference per query, then test whether the mean difference departs from zero.
p < .05 is commonly called significant; p < .01 strongly significant.
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.
KeyError: ndcg_cut_5 normally means that measure was not requested when the evaluator was created.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.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
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.
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.
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.
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.
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.
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 conceptsStart with term presence, then add frequency, rarity, length normalisation, and probabilistic reasoning.
Course diagrams: open the course platform (login required)
| Model | Core idea | Score / role | Main limitation |
|---|---|---|---|
| Boolean | Satisfy logical conditions | AND / OR / NOT postings | Little or no ranking |
| Coordination | Match more distinct query terms | number of matched query terms | Ignores frequency and rarity |
| TF | More occurrences in a document are better | Σ f(qi,D) | Favours common terms and long documents |
| IDF | Rare terms are more discriminative | log(N/(1+dfi)) | Ignores within-document tf |
| TF-IDF | Local frequency × global rarity | Σ tfi,D × idfi | Linear tf and crude length treatment |
| VSM | Compare query and document vector directions | cosine(q,d) | Still depends on lexical overlap |
| BIM | Contrast term probability in relevant/non-relevant sets | probabilistic relevance weight | Term independence and probability estimates |
| BM25 | IDF + tf saturation + length normalisation | strong sparse baseline | No native synonym or semantic matching |
1 + df smooths the denominator. IDF depends on the term and collection, not on the current document.
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.
Several BM25 variants exist. In A1, follow the formula in the supplied notebook and marking sheet rather than mixing definitions.
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.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.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
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.
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.
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.
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.
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.
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 conceptsClassical sparse models require lexical overlap. Transformers learn context-dependent representations that support semantic matching.
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.
The usual shape is N × D: N tokens, each represented by D values.
Self-attention alone does not encode order, so position embeddings are added. For sentence pairs, BERT uses segment/token-type embeddings and [SEP] boundaries.
## marks a continuation piece.QKᵀ produces an N×N score matrix.√d_k prevents large dot products from saturating softmax.Several heads learn relationships in different projection subspaces. Their outputs are concatenated and projected back to D dimensions.
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.
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.
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.
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.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
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].
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.
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.
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.
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.
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 conceptsMap queries and documents into a vector space where “car repair” can be close to “automobile maintenance.”
Course diagrams: open the course platform (login required)
Queries and documents are encoded separately. Document vectors can be precomputed and indexed for ANN search, making bi-encoders suitable for first-stage retrieval.
[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.
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.
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.
A pair contributes zero loss once the positive score exceeds the negative score by at least the margin.
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 type | Source | Advantage | Risk |
|---|---|---|---|
| Random | random collection documents | cheap and stable | often too easy |
| In-batch | other positives in the batch | almost no extra encoding | false negatives |
| BM25 hard | high-ranked but judged non-relevant | lexically similar and challenging | depends on qrel completeness |
| ANN/self-mined | current model's mistaken neighbours | targets current weaknesses | costly index refresh |
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.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
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.
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.
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.
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.
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.
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 conceptsVocabulary-aligned sparse representations retain inverted-index efficiency while neural models learn contextual term weights and expansion.
| Model | Query | Document | Matching | Online cost |
|---|---|---|---|---|
| BM25 | observed terms | term statistics | hand-crafted weighted sum | very low |
| DPR | dense vector | dense vector | dot product + ANN | query encoder |
| TILDEv2 | token IDs | contextual token weights, often expanded offline | exact ID match + max weight | no query encoder |
| SPLADE(v2) | learned sparse vocabulary vector | learned sparse vocabulary vector | sparse dot product | query encoder |
| PromptReps | dense hidden state + sparse logits | same | hybrid interpolation | LLM inference |
doc2query generates likely queries offline and appends them to documents before indexing. This reduces vocabulary mismatch without adding query-time generation.
The query is only tokenised. Exact query-token matches retrieve learned contextual document weights; repeated terms contribute their maximum weight.
An MLM head activates weighted vocabulary terms, including related terms absent from the text. ReLU, pooling and FLOPS/L1 regularisation control sparsity.
Sparse/dense describes the output representation. SPLADE uses BERT but emits a sparse vocabulary vector; DPR uses BERT but emits a dense embedding.
BM25 searches the full corpus.
Use hit IDs and raw document text.
TILDEv2 scores query-document pairs.
The first stage protects efficiency and candidate recall; the second stage improves ordering within the candidate set.
tildev2_scoringConnect 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
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.
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.
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.
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.
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.
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 conceptsLTR learns to order candidates. Online LTR replaces scarce static labels with abundant but biased user interactions.
BM25, dense or learned sparse candidates.
Lexical, neural, freshness and authority signals.
Learned ordering of the candidate list.
Position bias changes examination; selection bias excludes unseen documents; presentation bias changes attraction. No click does not necessarily mean non-relevant.
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.
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.
Sample a candidate parameter direction, compare current and candidate rankers through interleaving, and move toward the winner.
A stochastic logging policy records displayed actions and propensities. IPS then estimates the risk of current and candidate rankers from the same interaction log.
| Method | Data | Output | Main trade-off |
|---|---|---|---|
| Offline qrels | queries + runs + qrels | MAP/nDCG | cleaner but expensive and static |
| Interleaving | live clicks on a mixed list | pairwise preference | sensitive, but requires live exposure |
| DBGD | repeated interleaving | parameter update direction | online adaptation versus exploration risk |
| Counterfactual IPS | logged clicks + propensities | off-policy value/risk | log reuse versus variance and support assumptions |
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
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.
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.
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.
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.
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.
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.
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 conceptsEncoder 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.
BM25 searches the full collection and returns top-k candidates.
BERT jointly encodes pairs, or an LLM evaluates candidates through a prompt.
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.
Bidirectional Encoder Representations from Transformers (BERT) reads [CLS] query [SEP] document [SEP]. A classifier converts the contextual [CLS] vector into a relevance score.
Each document is judged independently. Training commonly uses human positives and BM25 hard negatives.
Binary cross-entropy rewards high positive scores and low negative scores. The output is a ranking signal, not necessarily a calibrated real-world probability.
| Method | Aggregation | Interpretation |
|---|---|---|
| BERT-FirstP | first passage score | cheap but ignores later evidence |
| BERT-MaxP | maximum passage score | one strong passage represents the document |
| BERT-SumP | sum of passage scores | accumulate evidence |
| Birch | first-stage score + weighted sentence scores | sentence-level evidence |
| PARADE | average, max, attention, or Transformer over passage vectors | representation aggregation |
duoBERT reads a query and two candidates to estimate p(dᵢ > dⱼ | q). Pairwise wins are then aggregated.
This can refine a monoBERT list, but pair comparisons add substantial encoder cost.
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.
| Family | Input | Signal | Main trade-off |
|---|---|---|---|
| Pointwise | query + one passage | Yes/No logit, label, or grade | simple; absolute judgement may be unstable |
| Pairwise | query + passages A and B | A > B preference | robust; many comparisons |
| Listwise | query + passage list | generated permutation | list context; generation/context cost |
| Setwise | query + small passage set | best-item logits | fewer 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.
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.
One call compares several passages using logits. This needs fewer comparisons than pairwise ranking and less generation than listwise permutation output.
Retrieve 10 or 20 candidates and read raw passage text.
Tokenise each pair, obtain relevant-class probability, and sort descending.
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.
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
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.
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.
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.
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.
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.
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.
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 conceptsLLM4IR 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.
BM25, DPR, TILDEv2, SPLADE, CiC, or a specialist model selects evidence.
Rewrite, rerank, filter, fuse, summarise, or compress.
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.
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.
RepLLaMA and LLM2Vec generate dense representations. PromptReps and DiffRetriever explore multiple generated representations. Pointwise, pairwise, listwise, and setwise prompts produce ranking judgements.
| Dimension | LC-LLM / Corpus-in-Context | RAG |
|---|---|---|
| Input | very large corpus inside the prompt | small retrieved top-k |
| Benefit | consolidates a multi-stage pipeline | scales to large and changing collections |
| Cost | long-context attention and latency | retriever/reranker maintenance |
| Failure | position bias; lost-in-the-middle | missing, 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.
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.
External evidence can be newer, private, domain-specific, updateable and inspectable. Unlike further pretraining, the collection remains separate from the generator's parameters.
| Stage | Examples | Main risk |
|---|---|---|
| Pre-retrieval | routing, rewriting, expansion, HyDE | query drift |
| Retrieval | lexical, dense, learned sparse, hybrid | gold evidence absent from top-k |
| Post-retrieval | rerank, filter, fuse, summarise | latency or useful evidence removed |
| Prompt | lexical/embedding compression | lost qualifiers or provenance |
| Generation | read, cite, revise, retrieve again | model prior overrides evidence |
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.
Combine retrieval with model-generated query/answer signals, then use an LLM to filter irrelevant knowledge before generation. Retrieved results still require evidence selection.
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.
A model may ignore corrective evidence or change a correct answer after contrary evidence. Relevance, answer correctness and groundedness must be evaluated separately.
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.
Attribution links answer claims to supporting references. Directly generated citations may be fabricated; retrieval-based attribution restricts candidates to real documents.
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.
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
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.
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.
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.
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.
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.
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.
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 conceptsStatic 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.
| System | Sequence | Insufficient evidence |
|---|---|---|
| Static Retrieval-Augmented Generation (RAG) | query → one retrieval → prompt → answer | Usually cannot revise the search after seeing the results. |
| Search agent | goal → action → observation → updated state → next action or finish | Can 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.
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.
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.
| Method and full name | Action pattern | Suitable setting | Main risk |
|---|---|---|---|
| Search–Visit | rank → open page | one short page | whole-page context waste |
| SIEVE, Search–Inspect–Fetch | rank → inspect headings/structure → fetch section | long structured report | structure may not reveal the answer |
| DCI, Direct Corpus Interaction | grep raw files → read matching lines | manageable local corpus and exact known term | lexical mismatch; broad scan cost |
| RISE, Retrieving Interaction SpacE | BM25 narrows files → grep and line navigation | large collection, useful file unknown | ranking 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.
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.
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.
| Approach | Query-side input | Positive signal | Limitation |
|---|---|---|---|
| AgentIR, Reasoning-Aware Retrieval for Deep Research Agents | intermediate query plus pre-search reasoning | gold documents plus expensive reranking generate positive/negative passages | gold labels and external reranking are costly; snippets may omit evidence |
| LRAT, Learning to Retrieve from Agent Trajectories | queries from successful agent runs | judged visited passages, without gold-document labels | visits alone do not prove utility; other passages may be mislabeled negative |
| ITER, Interaction-Aware Retrieval for Agentic Search | current query, original question and previous queries | trajectory-relative judgments distinguish new evidence from visited relevant/irrelevant passages | inferred 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.
grep(pattern) locates matching lines; BM25 search(query) returns candidate IDs.
A CrossEncoder reorders the same BM25 pool; read(id, start_line, num_lines) returns numbered evidence.
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.
Research trail: ReAct · SIEVE · DCI · RISE · AgentIR · LRAT · ITER. The course PDFs and code remain on the restricted course platform.
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
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.
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.
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.
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.
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.
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.
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 conceptsA 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.
Start from seed URLs and take permitted unseen URLs from a frontier.
Request a page, parse content and links, normalise URLs, and suppress duplicates.
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.
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.
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.
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.
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.
| Retrieval model | How PageRank can enter | Caution |
|---|---|---|
| Language model | replace a uniform document prior P(D) with a prior based on PageRank or another document feature | a convenient prior does not guarantee higher effectiveness |
| BM25 | treat text plus non-text features as a learned or tuned utility | the base model permits extra features but does not determine their weights |
| Vector Space Model | combine cosine similarity with PageRank, spam score or difficulty in an external utility function | query-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.
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.”
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.
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 objective | Question | Failure if used alone |
|---|---|---|
| Relevance | How useful is this document for the query? | may repeat one interpretation |
| Coverage | Which plausible intents/subtopics appear? | may sacrifice too much relevance |
| Novelty | What new information does this result add? | mere difference may not be useful |
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.
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.
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)
| Chapter | Duration | Learning checkpoint |
|---|---|---|
| 11.1 Overview | 2:22 | Place graph authority and list diversity beside content relevance. |
| 11.2 Links | 3:15 | Distinguish an endorsement from descriptive anchor text. |
| 11.3 Link analysis in IR | 3:18 | Explain why links help ranking, clustering, classification and crawling. |
| 11.4 PageRank | 4:41 | Trace one random-surfer step and the role of teleportation. |
| 11.5 Understanding PageRank | 1:56 | Use source authority and out-degree, not just the count of incoming links. |
| 11.6 PageRank in retrieval | 2:06 | Separate a document prior from the query-dependent matching score. |
| 11.7 Diversification | 1:17 | Explain why a relevant duplicate may add little value to a list. |
| 11.8 PRP | 3:22 | Expand Probability Ranking Principle and state the lecture's assumptions. |
| 11.9 Ambiguity and redundancy | 0:48 | Locate ambiguity in the query and redundancy in the result list. |
| 11.10 Diversity framework and MMR | 5:31 | Compute 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.
| Method and full name | Inputs → output | What changes the score? | Not a substitute for |
|---|---|---|---|
| BM25 (Best Matching 25); DPR (Dense Passage Retrieval) | query + document representation → matching score | query words or meaning | authority or a diversity objective |
| monoBERT (BERT: Bidirectional Encoder Representations from Transformers) | one query–document pair → relevance score | joint contextual matching | comparison with all already selected documents |
| PageRank (a model name, not an acronym) | directed link graph + teleport rule → one authority value per page | links, graph boundaries and teleport distribution | query relevance or factual verification |
| PRP (Probability Ranking Principle) | estimated relevance probabilities → descending order | the relevance estimates | a trained encoder or a redundancy penalty |
| MMR (Maximal Marginal Relevance) | candidate relevance + document similarity + selected set → next item | query AND what is already selected | first-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.
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.
| Target | Teleport | Dangling C contribution | Incoming link contribution | After one iteration |
|---|---|---|---|---|
| A | 0.15/3 = 0.05 | 0.85 × (1/3)/3 = 0.094444… | 0 | 0.144444… |
| B | 0.05 | 0.094444… | 0.85 × (1/3)/2 = 0.141667… | 0.286111… |
| C | 0.05 | 0.094444… | 0.85 × [(1/3)/2 + 1/3] = 0.425 | 0.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.
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.
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.
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.
| Candidate | Relevance reward | Redundancy penalty against A | MMR at λ=0.5 |
|---|---|---|---|
| B | 0.5 × 0.6 = 0.30 | 0.5 × 0.9 = 0.45 | −0.15 |
| C | 0.5 × 0.5 = 0.25 | 0.5 × 0.1 = 0.05 | 0.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
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.
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.
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
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
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.
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.
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.
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.
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.
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.
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 conceptsWeek 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.
| Feedback | Evidence | Main risk |
|---|---|---|
| Explicit | the user marks relevant or non-relevant documents | high quality but requires effort |
| Implicit | behaviour such as clicks is interpreted as a relevance signal | examination and presentation bias |
| Pseudo-relevance feedback (PRF) | top initial results are assumed relevant | a 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.
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.
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.
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.
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.
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.
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.
| Family | Uses | Examples |
|---|---|---|
| Voting | which systems nominate a document | plurality, Copeland |
| Rank aggregation | document positions in each list | Borda, Reciprocal Rank Fusion |
| Score aggregation | scores, often after per-list normalisation | CombSUM, 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.
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.
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.
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.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.[-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.
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
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.
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.
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.
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.
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.
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.
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 conceptsWeek 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.
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.
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.
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.
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.
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.
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 (“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.
| Strategy | Traversal order | State |
|---|---|---|
| Document-at-a-time (DAAT) | all lists together, one document at a time | heap of current top k |
| Term-at-a-time (TAAT) | one whole list at a time | one accumulator per document |
| Score-at-a-time (SAAT) | postings grouped by impact, highest impacts first | accumulators; can stop early |
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.
| Stage | What happens | How to prepare |
|---|---|---|
| First 5 minutes | you receive two prompt questions while your identification is checked | plan a short explanation for each: definition, mechanism, example and limitation |
| Main dialogue | you answer one prompt, then the examiner asks follow-up questions about details, problems and fixes | practise explaining why a method works and what can go wrong, not only what it is |
| Topic changes | the examiner may move to other course topics to confirm your level or give you a chance at a higher band | connect 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.
[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.10000001 00000010; 300 = 2·128 + 44 as 10000010 00101100; 5 fits in one byte, 00000101. A 32-bit integer would always use four bytes.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.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.
These are dated paraphrases of staff replies, not new assessment rules. Follow the latest course notebook and marking sheet if later updates differ.
| Scope | Verified clarification | Practical consequence |
|---|---|---|
| Main Project 2 / Task 2 | The 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 bonus | Train 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)
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.
Identify the variables, then ask what each factor rewards or penalises.
| Name | Formula | Interpretation |
|---|---|---|
| P@k | relevant in top k / k | precision within cutoff k |
| Recall | retrieved relevant / all relevant | coverage of the relevant set |
| F1 | 2PR/(P+R) | harmonic mean of P and R |
| AP | (1/|Rel|) Σ P@k × rel(k) | record precision whenever a relevant result appears |
| MAP | mean(AP over queries) | each query has equal weight |
| RR | 1/rank(first relevant) | only the first relevant result matters |
| nDCG@K | DCG@K / IDCG@K | graded relevance plus position discount |
| RBP | (1-p)Σ r_i p^(i-1) | p models continuation probability |
| Name | Formula | Intuition |
|---|---|---|
| IDF | log(N/(1+df)) | rarer collection terms discriminate better |
| TF-IDF | Σ tf × idf | within-document importance × collection rarity |
| Cosine | q·d/(||q||||d||) | compare direction while reducing magnitude effects |
| BIM weight | log((N-df)/df) | probabilistic term advantage |
| BM25 | Σ IDF × saturated_tf(length-normalised) | rarity, saturation, and document length |
| Name | Formula | Intuition |
|---|---|---|
| Softmax | exp(z_i)/Σexp(z_j) | convert scores to weights summing to one |
| Attention | softmax(QKᵀ/√d_k)V | relevance-weighted value aggregation |
| InfoNCE | -log exp(s+)/[exp(s+)+Σexp(s-)] | classify the positive among candidates |
| Margin | max(0, m-(s+-s-)) | positive must lead by at least m |
| MaxSim | Σ_i max_j E_qi·E_dj | best document-token match for each query token |
| Autoregressive | Π_t P(y_t|y_<t) | predict the next token from the prefix |
| monoBERT | P(relevant=1|q,d) | pointwise score from joint encoding |
| Binary cross-entropy | -Σ_pos log(s)-Σ_neg log(1-s) | raise positives and suppress negatives |
| duoBERT | s(d_i)=Σ_{j≠i}p(d_i>d_j|q) | aggregate pairwise wins |
| Name | Formula | Interpretation |
|---|---|---|
| Naive clicks | Σ λ(rank_i)c_i | retains exposure bias |
| IPS | Σ [λ(rank_i)/P(o_i=1)]c_i | corrects examination bias in expectation |
| Off-policy weight | P(action|new)/P(action|logging) | reweights logged actions for a candidate policy |
| Counterfactual update | Risk_IPS(f) < Risk_IPS(f₀) | prefer lower estimated counterfactual risk |
For model questions, classify each claim by these components instead of memorising one sentence.
| Model | Representation / pooling | Similarity / interaction | Training | Role |
|---|---|---|---|---|
| BM25 | sparse term statistics | weighted sum over terms | usually untrained; tune k1,b | strong lexical baseline |
| TILDEv2 | query token IDs; contextual document-token weights | exact match + per-term max weight | document-side neural learning and expansion | fast learned sparse reranker |
| SPLADE(v2) | mostly-zero vocabulary vectors | sparse dot product | MLM head, distillation, sparsity regularisation | learned sparse retrieval |
| PromptReps | LLM dense state + sparse logits | normalised hybrid score | zero-shot | hybrid representation |
| DPR | CLS bi-encoder | dot product | InfoNCE/NLL; in-batch and hard negatives | first-stage dense retrieval |
| RepBERT | mean token embeddings | inner product | MultiLabelMarginLoss | BERT bi-encoder |
| ANCE | CLS / first token | dot product | NLL/InfoNCE-style; ANN self-mined negatives | dynamic hard-negative mining |
| Contriever | mean pooling | cosine | unsupervised contrastive; same-document spans | unsupervised dense retriever |
| ColBERT | all token embeddings | late-interaction MaxSim | contrastive / pairwise CE | efficient fine-grained matching |
| E5-Mistral | Mistral decoder; EOS/last token | temperature-scaled cosine | InfoNCE; synthetic and supervised data | LLM embedding model |
| LLM2Vec | decoder with bidirectional attention; pooling | often cosine | MNTP + unsupervised SimCSE + optional supervision | decoder converted to encoder |
| RepLLaMA | Llama2; EOS last hidden state | dot product | InfoNCE; supervision + LoRA | LLM retriever |
| Cross-encoder | joint query-document encoding | classification/regression relevance head | pointwise, pairwise, or listwise | high-accuracy reranker |
| monoBERT | [CLS] q [SEP] d [SEP] | relevant-class softmax score | binary cross-entropy; BM25 negatives | pointwise BERT reranker |
| BERT-MaxP / FirstP / SumP | document passages | max / first / sum passage score | transferred document labels | long-document score aggregation |
| PARADE | passage vectors | average / max / attention / Transformer aggregation | document-level ranking | representation aggregation |
| duoBERT | query + two documents | pairwise preference aggregation | pairwise cross-entropy | late-stage BERT reranker |
| LLM pointwise / pairwise | one document / document pair in a prompt | label logits / preference | zero-shot prompting | individual judgement / comparison |
| LLM listwise / setwise | candidate list / small set | permutation / best-item logits | zero-shot prompting | list context / efficient selection |
| Corpus-in-Context | whole corpus in an LC-LLM prompt | generated document IDs | few-shot prompting; no retriever training | small-corpus model-based retrieval |
| Screenshot retriever | page pixels and layout | VLM similarity | vision-language contrastive learning | layout-rich documents |
| DiffRetriever | parallel representative tokens | multi-representation matching | diffusion language model | generative multi-vector retrieval |
| Basic RAG | query + top-k evidence | autoregressive answer | retriever and generator may be frozen | evidence-based IR4LLM |
| Rewrite-Retrieve-Read | rewritten query + evidence | downstream answer reward | pseudo-data and optional policy optimisation | underspecified questions |
| BlendFilter | retrieved and model-generated knowledge | filter then generate | prompted LLM modules | remove distractors |
| RARR | draft + researched evidence | support check and revision | post-hoc research/revision | retrofit attribution |
| PageRank | directed graph; one value per page | stationary random-surfer probability | power iteration, no relevance-label training required | query-independent authority feature |
| PRP | estimated document relevance probabilities | descending probability order | a ranking principle, not a trained model | relevance-oriented ordering |
| MMR | candidate scores + document similarities + selected set | relevance reward minus maximum redundancy | greedy selection; tune the trade-off separately | diversity-aware candidate reranking |
Short name → full English name → definition. Model names that are not acronyms are identified separately.
| Short name | Full name | Definition |
|---|---|---|
| IR | Information Retrieval | Finding and ranking documents that satisfy an information need. |
| TF / DF / CF | Term Frequency / Document Frequency / Collection Frequency | Counts within one document, across documents containing the term, and across all term occurrences. |
| IDF | Inverse Document Frequency | A term's discriminative weight based on how few documents contain it. |
| TF-IDF | Term Frequency-Inverse Document Frequency | Combines local frequency with collection rarity. |
| VSM / BIM | Vector Space Model / Binary Independence Model | Vector similarity and probabilistic term-independence approaches to ranking. |
| BM25 | Best Matching 25 | A lexical model combining IDF, tf saturation, and length normalisation. |
| RSJ / F1 | Robertson-Spärck Jones / F-score with β = 1 | A probabilistic IDF weighting foundation for BM25, and the harmonic mean of precision and recall. |
| AP / MAP | Average Precision / Mean Average Precision | Average precision at relevant ranks for one query, then averaged across queries. |
| RR / MRR | Reciprocal Rank / Mean Reciprocal Rank | Measures where the first relevant result appears. |
| DCG / IDCG / nDCG | Discounted Cumulative Gain / Ideal DCG / Normalized DCG | Combines graded relevance and rank discount, then normalises by the ideal order. |
| RBP | Rank-Biased Precision | Models a user's probability of continuing down the ranking. |
| PageRank | Model name, not an acronym | A query-independent link-authority score defined by the stationary probability of a random surfer with teleportation. |
| PRP | Probability Ranking Principle | Ranks documents by decreasing estimated probability of relevance, under assumptions including accurate estimates and independent relevance utility. |
| MMR | Maximal Marginal Relevance | A greedy reranking rule that trades query relevance against redundancy with already selected results. |
| α-nDCG | Alpha-normalised Discounted Cumulative Gain | A subtopic-aware measure that discounts repeated coverage of the same intent. |
| ERR / ERR-IA | Expected Reciprocal Rank / Intent-Aware Expected Reciprocal Rank | ERR models satisfaction-based stopping; ERR-IA averages per-intent utility using intent weights. Plain ERR is not automatically a diversity metric. |
| RF / PRF | Relevance Feedback / Pseudo-Relevance Feedback | Updates retrieval from relevance evidence; PRF assumes top initial results are relevant without asking the user. |
| Rocchio | Model name, not an acronym | Moves a vector-space query toward the relevant centroid and away from the non-relevant centroid. |
| TLM / NTLM | Translation Language Model / Neural Translation Language Model | Models a query term through document terms that can translate to it; NTLM estimates relations from embeddings. |
| QPP | Query Performance Prediction | Estimates how well a query may retrieve, and can guide how aggressively a verbose query is reduced. |
| RRF / CombMNZ | Reciprocal Rank Fusion / Combination Multiply Non-Zero | Combines ranks through reciprocal discounts, or multiplies a score sum by the number of supporting lists. |
| VByte | Variable Byte coding | Stores an integer in 7-bit groups, with one bit per byte signalling whether another byte follows. |
| WAND | Weak (or Weighted) AND | A dynamic pruning algorithm that uses list upper bounds to find a pivot and skip documents that cannot enter the top k. |
| MaxScore | Algorithm name, not an acronym | Dynamic pruning that splits terms into essential and non-essential lists by their upper bounds. |
| DAAT / TAAT / SAAT | Document-, Term- and Score-at-a-time | Index traversal orders: all lists per document, one list at a time, or postings in decreasing impact order. |
| LSR | Learned Sparse Retrieval | Learns term weights (and often expansion terms) but still retrieves through an inverted index. |
| BERT | Bidirectional Encoder Representations from Transformers | An encoder model that can jointly contextualise query and document tokens. |
| CLS / SEP / EOS | Classification / Separator / End of Sequence token | Special tokens for classification summaries, segment boundaries, and sequence endings. |
| MLM / FFN | Masked Language Modeling / Feed-Forward Network | A masked-token pretraining objective and the per-token nonlinear sublayer in a Transformer block. |
| GPT / LLM | Generative Pre-trained Transformer / Large Language Model | Decoder-style generation family and the broader class of large pretrained language models. |
| DPR | Dense Passage Retrieval | A bi-encoder that retrieves by dense query-passage vector similarity. |
| ColBERT | Contextualized Late Interaction over BERT | Retains token vectors and applies MaxSim for fine-grained late interaction. |
| ANN / ANCE | Approximate Nearest Neighbour / Approximate Nearest Neighbor Negative Contrastive Estimation | Fast approximate vector search and a retriever that mines its ANN mistakes as hard negatives. |
| NLL / InfoNCE | Negative Log-Likelihood / Information Noise-Contrastive Estimation | Objectives that penalise low target probability and contrast positives against negatives. |
| CE | Cross-Entropy | A classification loss comparing target and predicted distributions. |
| TILDE | Term Independent Likelihood moDEl | Learns document-side vocabulary term likelihoods for efficient matching. |
| SPLADE | Sparse Lexical and Expansion Model | Learns sparse vocabulary weights and semantic expansion terms. |
| ReLU / FLOPS | Rectified Linear Unit / Floating-Point Operations | Produces non-negative activations, while the FLOPS-inspired regulariser discourages overly dense SPLADE vectors. |
| T5 | Text-to-Text Transfer Transformer | A sequence-to-sequence model that can generate offline doc2query expansions. |
| LTR / OLTR | Learning to Rank / Online Learning to Rank | Learns an ordering from labelled data or continuously from user interactions. |
| IPS | Inverse Propensity Scoring | Reweights observations by inverse exposure probability to correct bias in expectation. |
| DBGD | Dueling Bandit Gradient Descent | Uses interleaving outcomes to move toward a winning exploratory ranker. |
| COLTR | Counterfactual Online Learning to Rank | Evaluates candidate rankers off-policy using logged clicks and propensities. |
| RM3 / TREC | Relevance Model 3 / Text REtrieval Conference | A pseudo-relevance feedback model and a major standard IR evaluation programme. |
| Qrels | Query Relevance Judgements | Ground-truth query-document relevance labels used to evaluate a run. |
| MS MARCO / BEIR | Microsoft Machine Reading Comprehension / Benchmarking Information Retrieval | Widely used neural-ranking training data and a cross-domain retrieval benchmark suite. |
| JSONL | JSON Lines | Stores one independent JSON object per line for streaming datasets. |
| LoRA / MNTP / SimCSE | Low-Rank Adaptation / Masked Next Token Prediction / Simple Contrastive Learning of Sentence Embeddings | Efficient fine-tuning and representation-learning methods used by later embedding models. |
| PARADE | Passage Representation Aggregation for Document Reranking | Aggregates encoded passage vectors for long-document ranking. |
| LLM4IR / IR4LLM | Large Language Models for Information Retrieval / Information Retrieval for Large Language Models | Using LLMs to improve IR versus retrieving evidence to support an LLM. |
| monoBERT / duoBERT | Model names, not acronyms | Pointwise relevance scoring versus pairwise document preference. |
| RAG / LC-LLM | Retrieval-Augmented Generation / Long-Context Large Language Model | Retrieve a small evidence set for generation versus place much more source text directly in context. |
| CiC / CoT | Corpus-in-Context / Chain-of-Thought | Direct corpus prompting for retrieval and generated intermediate reasoning steps. |
| VLM / HyDE | Vision-Language Model / Hypothetical Document Embeddings | Models pixels and language; or retrieves by embedding a generated hypothetical answer document. |
| RARR | Retrofit Attribution using Research and Revision | Researches evidence for a draft and revises unsupported claims. |
| PPO | Proximal Policy Optimization | A reinforcement-learning method that can optimise a trainable query rewriter while limiting update size. |
A1 is not just a BM25 function. It is a reproducible IR experiment with validation, tuning, comparison, and analysis.
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.
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
Answer first, then expand. Being able to explain why is the real test.
The guide synthesises the supplied INFS7410 folder. Large corpora, indexes, and virtual environments are experimental resources rather than revision content.
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