AI Engineering: Agents and Applications › Production Retrieval and Pipelines › Day 326
Hands-on lab — Day 326: Scaling Retrieval
- ← Back to the Day 326 lesson
- Open the hands-on files on GitHub — clone or download them from the public labs repository
- Local path in your clone:
labs/sections/ai-engineering/day-326-scaling-retrieval/
Commands
Setup
pip install -r requirements/requirements.txt Run
python examples/retrieval_demo.py Test
bash tests/run_tests.sh File tree
examples/retrieval_demo.py examples/retrieval.py expected-output/examples-run.txt expected-output/FIELDS.md expected-output/measured-values.txt expected-output/run-output.txt expected-output/starter-run.txt expected-output/test-output.txt expected-output/test-run.txt metadata.yml README.md requirements/requirements.txt security.md starter/retrieval.py tests/run_tests.sh tests/test_retrieval.py troubleshooting.md
Lab README
Lab — Day 326: Scaling Retrieval
Lesson
- Lesson title: Scaling Retrieval
- Day number: 326 of 365
- Lesson article: https://ai-roadmap-365.github.io/day-326-scaling-retrieval
- Lab files: everything you need is in this directory — follow “How to run” below.
- Browse the course locally: from the repository root, this lab also appears in the course website at
/labs/day-326-scaling-retrievalwhen the site is running.
Purpose
Measure the recall you trade for speed, rather than accepting a library's default. You implement exact search and an inverted-file index side by side, sweep the tuning parameter, and produce the recall-versus-cost curve for a corpus you control.
Everything is deterministic: the vectors come from a seeded generator, so the numbers reproduce exactly.
Learning objectives
- Implement exact nearest-neighbour search and count its cost honestly.
- Build an IVF index and identify precisely where its recall loss originates.
- Measure recall at k against an exact baseline.
- Sweep
nprobeand locate the knee of the curve. - Demonstrate that full probing costs more than exact search, and explain why.
Prerequisites
- Day 325, "Keeping Indexes Fresh" — an ANN index is a derived structure with exactly those freshness problems.
- Comfortable with Python lists, sorting with keys, and basic vector arithmetic.
- No linear-algebra library needed; cosine similarity is written by hand.
Supported operating systems
macOS, Linux and Windows (via WSL or PowerShell). Nothing is platform-specific.
Hardware requirements
Any machine running Python 3.10 or newer. No GPU. The suite completes in about 2.3 seconds and uses a few megabytes.
Required software
- Python 3.10 or newer.
pytest7 or newer.
Free and open-source options
Every dependency is free and open source: Python is PSF-licensed, pytest is MIT-licensed. No account, no API key, no hosted service. The lesson discusses FAISS, hnswlib, pgvector, Qdrant and Milvus as the real-world open-source options; none is required here, and the algorithms are written out so nothing is hidden behind a library default.
Installation
python3 -m venv .venv
.venv/bin/pip install -r requirements/requirements.txt
Removing .venv fully reverses the installation.
File structure
starter/retrieval.py your work: cosine, recall_at_k, both searches
examples/retrieval.py reference implementation
examples/retrieval_demo.py sweeps nprobe and prints the curve
tests/test_retrieval.py grouped by claim
tests/run_tests.sh suite entry point
expected-output/ real captured output and measured values
requirements/ pinned dependency
How to run
python3 examples/retrieval_demo.py # sweep nprobe, print the curve
bash tests/run_tests.sh # run the suite
To work on the exercise, edit starter/retrieval.py, then copy it over the reference:
cp starter/retrieval.py examples/retrieval.py
bash tests/run_tests.sh
Keep a copy of the reference first if you want to compare.
What the commands do
python3 examples/retrieval_demo.py builds 2,000 clustered vectors, runs exact search to establish ground truth, then runs IVF at every nprobe from 1 to 8, reporting mean recall and total comparisons for each — followed by the cheapest setting that reaches each of three recall targets.
bash tests/run_tests.sh runs pytest over seventeen tests grouped by claim: geometry, exactness, partitioning, recall and the trade-off itself.
Expected output
corpus=2000 dim=32 queries=20 k=10 nlist=8
exact search cost: 40000 comparisons
nprobe=1 recall@10=0.81 comparisons=6192 speedup=6.5x
nprobe=2 recall@10=0.88 comparisons=12051 speedup=3.3x
nprobe=3 recall@10=0.90 comparisons=16325 speedup=2.5x
nprobe=4 recall@10=0.97 comparisons=20474 speedup=2.0x
nprobe=5 recall@10=0.97 comparisons=23575 speedup=1.7x
nprobe=6 recall@10=0.97 comparisons=27527 speedup=1.5x
nprobe=7 recall@10=0.98 comparisons=34559 speedup=1.2x
nprobe=8 recall@10=1.00 comparisons=40160 speedup=1.0x
recall>=0.90: nprobe=3 (2.5x cheaper than exact)
recall>=0.95: nprobe=4 (2.0x cheaper than exact)
recall>=0.99: nprobe=8 (1.0x cheaper than exact)
Note the last data row: nprobe=8 costs 40,160 comparisons where exact search costs 40,000. expected-output/FIELDS.md explains every field and why the cost metric is comparisons rather than seconds.
Validation steps
bash tests/run_tests.shreports17 passed.- Your demo output must match the table above exactly — the generator is seeded. A mismatch means your clustering or your comparison counting differs.
- Confirm recall never falls as
nproberises, and thatnprobe=8gives exactly1.00. Anything less means your partitioning is losing vectors.
Tests
Seventeen tests in five groups:
- geometry — cosine is 1.0 for identical vectors, handles a zero vector, and the fixture is genuinely clustered rather than uniform.
- exactness — brute force returns k results in score order and costs one comparison per vector.
- partitioning — every vector is in exactly one list, full probe matches exact search, and
nprobeis clamped. - recall — membership not ordering; an empty truth set is 1.0.
- the trade-off — recall and cost both rise monotonically, full probe reaches 1.0 and costs more than exact, low probe is far cheaper, and the target search returns the cheapest adequate row.
Cleanup
rm -rf __pycache__ .pytest_cache
rm -rf .venv
Both are safe to remove and fully reversible.
Troubleshooting
See troubleshooting.md for each failure this lab is designed to produce.
Security notes
See security.md. In short: no network, no credentials, no API key. The lesson covers the multi-tenant leakage and right-to-erasure issues that real ANN indexes raise.
Extension exercises
- Per-query recall. Report the minimum and the count of queries below 0.5, then find a setting where the mean looks fine but a query returns nothing.
- Scalar quantisation. Store components as 8-bit integers, measure the memory saved and the recall lost, and find the corpus size at which quantised IVF beats exact search on both. "Never, at this size" is a legitimate finding.
- Compare to a graph index. Implement a simple navigable small-world graph and put its curve alongside IVF's on the same corpus.
Navigation
- Lesson
- Previous: Day 325 — Keeping Indexes Fresh
- Next: Day 327 — Cost Engineering for AI Systems
Expected output
FIELDS.md
# Reading the sweep output
nprobe=1 recall@10=0.81 comparisons=6192 speedup=6.5x
| Field | Meaning |
| --- | --- |
| `nprobe` | How many of the 8 inverted lists this search examined. The tuning knob. |
| `recall@10` | Mean fraction of the true top-10 that the approximate search also returned, averaged over 20 queries. Membership, not ordering. |
| `comparisons` | Total vector comparisons across all queries — `nlist` centroid comparisons per query, plus one per vector in the probed lists. |
| `speedup` | Exact search's comparisons divided by this row's. Below 1.0 means the index costs more than not having one. |
## Why comparisons rather than seconds
Wall-clock time on a laptop is dominated by interpreter overhead and whatever else is running, so it is noisy and not reproducible. Comparisons are exact, stable across machines, and are the quantity an ANN index actually reduces.
The abstraction has limits, and the lesson names them: at real scale, memory layout and cache behaviour matter as much as the comparison count, which is why a quantised index can beat an unquantised one doing the same number of comparisons.
## The target lines
recall>=0.90: nprobe=3 (2.5x cheaper than exact)
recall>=0.99: nprobe=8 (1.0x cheaper than exact)
These answer the question worth asking of an index — not "what is the best recall it can reach" but "what is the cheapest configuration good enough for this job". The second line is the honest one: reaching 99 percent required probing everything, which cost more than exact search.
examples-run.txt
corpus=2000 dim=32 queries=20 k=10 nlist=8
exact search cost: 40000 comparisons
nprobe=1 recall@10=0.81 comparisons=6192 speedup=6.5x
nprobe=2 recall@10=0.88 comparisons=12051 speedup=3.3x
nprobe=3 recall@10=0.90 comparisons=16325 speedup=2.5x
nprobe=4 recall@10=0.97 comparisons=20474 speedup=2.0x
nprobe=5 recall@10=0.97 comparisons=23575 speedup=1.7x
nprobe=6 recall@10=0.97 comparisons=27527 speedup=1.5x
nprobe=7 recall@10=0.98 comparisons=34559 speedup=1.2x
nprobe=8 recall@10=1.00 comparisons=40160 speedup=1.0x
recall>=0.90: nprobe=3 (2.5x cheaper than exact)
recall>=0.95: nprobe=4 (2.0x cheaper than exact)
recall>=0.99: nprobe=8 (1.0x cheaper than exact)
measured-values.txt
Measured on macOS 26.5.1 (Apple Silicon), Python 3.14.0, pytest 9.1.1.
python3 examples/retrieval_demo.py -> 13 lines, exit 0
bash tests/run_tests.sh -> 17 passed in 2.25s
Every number is deterministic: the vectors come from a seeded generator, so a
correct implementation reproduces this table exactly.
nprobe recall@10 comparisons speedup
1 0.81 6192 6.5x
2 0.88 12051 3.3x
3 0.90 16325 2.5x
4 0.97 20474 2.0x
5 0.97 23575 1.7x
6 0.97 27527 1.5x
7 0.98 34559 1.2x
8 1.00 40160 1.0x
exact search baseline: 40000 comparisons
Two things worth checking in your own run:
1. nprobe=8 costs 40160, which is MORE than the 40000 of exact search. The
extra 160 are centroid comparisons -- 8 lists across 20 queries. An index
tuned for perfect recall is strictly worse than no index.
2. The curve flattens after nprobe=4. The last four settings together buy 3
points of recall for twice the work.
run-output.txt
corpus=2000 dim=32 queries=20 k=10 nlist=8
exact search cost: 40000 comparisons
nprobe=1 recall@10=0.81 comparisons=6192 speedup=6.5x
nprobe=2 recall@10=0.88 comparisons=12051 speedup=3.3x
nprobe=3 recall@10=0.90 comparisons=16325 speedup=2.5x
nprobe=4 recall@10=0.97 comparisons=20474 speedup=2.0x
nprobe=5 recall@10=0.97 comparisons=23575 speedup=1.7x
nprobe=6 recall@10=0.97 comparisons=27527 speedup=1.5x
nprobe=7 recall@10=0.98 comparisons=34559 speedup=1.2x
nprobe=8 recall@10=1.00 comparisons=40160 speedup=1.0x
recall>=0.90: nprobe=3 (2.5x cheaper than exact)
recall>=0.95: nprobe=4 (2.0x cheaper than exact)
recall>=0.99: nprobe=8 (1.0x cheaper than exact)
starter-run.txt
An untouched starter fails every test:
17 failed in 0.08s
All four stubs -- cosine, recall_at_k, BruteForceIndex.search and
IVFIndex.search -- raise NotImplementedError, and every test depends on at
least one of them.
test-output.txt
................. [100%]
17 passed in 2.21s
test-run.txt
................. [100%]
17 passed in 2.21s
Source files
examples/retrieval_demo.py (1133 bytes)
#!/usr/bin/env python3
"""Sweep nprobe and show what recall costs."""
from __future__ import annotations
import os
import sys
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
from retrieval import make_vectors, sweep_nprobe
def main() -> int:
vectors = make_vectors(2000, dim=32, seed=7, clusters=8)
queries = make_vectors(20, dim=32, seed=99, clusters=8)
sweep = sweep_nprobe(vectors, queries, k=10, nlist=8)
print(f"corpus=2000 dim=32 queries=20 k=10 nlist=8")
print(f"exact search cost: {sweep.baseline_comparisons} comparisons")
for row in sweep.rows:
print(row.line(sweep.baseline_comparisons))
for target in (0.90, 0.95, 0.99):
row = sweep.cheapest_meeting(target)
if row is None:
print(f"recall>={target:.2f}: not reached at any nprobe")
else:
speedup = sweep.baseline_comparisons / row.comparisons
print(
f"recall>={target:.2f}: nprobe={row.nprobe} "
f"({speedup:.1f}x cheaper than exact)"
)
return 0
if __name__ == "__main__":
raise SystemExit(main())
examples/retrieval.py (6977 bytes)
"""Exact versus approximate retrieval, and the recall you trade for speed.
Offline, standard-library only, and deterministic: every vector comes from a
seeded generator, so the numbers in the lesson are reproducible rather than
"about right".
Cost is measured in **vector comparisons**, not wall-clock seconds. That is a
deliberate choice. Wall-clock on a laptop is dominated by interpreter overhead
and whatever else the machine is doing, so it makes a poor teaching signal and
a worse test assertion. Comparisons are the thing an ANN index actually
reduces, they are exactly reproducible, and they scale the same way the real
cost does. The lesson says where this abstraction stops being true.
"""
from __future__ import annotations
import math
import random
from dataclasses import dataclass, field
@dataclass
class Stats:
"""How much work a search did."""
comparisons: int = 0
def reset(self) -> None:
self.comparisons = 0
def make_vectors(n: int, dim: int, *, seed: int = 7, clusters: int = 8) -> list[list[float]]:
"""Generate clustered vectors, because real embeddings are not uniform.
Uniform random points would make every approximate method look terrible:
partitioning only helps when the data has structure to partition. Real
corpora cluster by topic, so the fixture does too.
"""
rng = random.Random(seed)
centres = [[rng.uniform(-1, 1) for _ in range(dim)] for _ in range(clusters)]
out: list[list[float]] = []
for i in range(n):
centre = centres[i % clusters]
out.append([c + rng.gauss(0, 0.15) for c in centre])
return out
def cosine(a: list[float], b: list[float]) -> float:
dot = sum(x * y for x, y in zip(a, b))
na = math.sqrt(sum(x * x for x in a))
nb = math.sqrt(sum(y * y for y in b))
if na == 0.0 or nb == 0.0:
return 0.0
return dot / (na * nb)
class BruteForceIndex:
"""Exact search. Always correct, and always O(n) per query."""
def __init__(self, vectors: list[list[float]]) -> None:
self.vectors = vectors
self.stats = Stats()
def search(self, query: list[float], k: int) -> list[int]:
self.stats.comparisons += len(self.vectors)
scored = [(cosine(query, v), i) for i, v in enumerate(self.vectors)]
scored.sort(key=lambda pair: (-pair[0], pair[1]))
return [i for _, i in scored[:k]]
class IVFIndex:
"""Inverted-file index: partition into lists, search only the nearest few.
This is the shape of a real IVF index. Build assigns each vector to its
nearest centroid; search compares the query to every centroid, picks the
`nprobe` closest lists, and scans only those. The recall loss comes from
one specific place: a true neighbour sitting in a list you did not probe.
"""
def __init__(self, vectors: list[list[float]], *, nlist: int = 8, seed: int = 11) -> None:
self.vectors = vectors
self.nlist = nlist
self.stats = Stats()
self.centroids, self.lists = self._build(seed)
def _build(self, seed: int) -> tuple[list[list[float]], list[list[int]]]:
"""Assign vectors to lists with a few rounds of Lloyd's algorithm."""
rng = random.Random(seed)
dim = len(self.vectors[0])
centroids = [list(self.vectors[rng.randrange(len(self.vectors))]) for _ in range(self.nlist)]
lists: list[list[int]] = [[] for _ in range(self.nlist)]
for _ in range(6):
lists = [[] for _ in range(self.nlist)]
for i, v in enumerate(self.vectors):
best = max(range(self.nlist), key=lambda c: cosine(v, centroids[c]))
lists[best].append(i)
for c in range(self.nlist):
if not lists[c]:
continue
centroids[c] = [
sum(self.vectors[i][d] for i in lists[c]) / len(lists[c]) for d in range(dim)
]
return centroids, lists
def search(self, query: list[float], k: int, *, nprobe: int = 1) -> list[int]:
nprobe = max(1, min(nprobe, self.nlist))
# Comparing against the centroids is real work and is counted.
self.stats.comparisons += self.nlist
ranked = sorted(
range(self.nlist), key=lambda c: (-cosine(query, self.centroids[c]), c)
)[:nprobe]
candidates: list[int] = []
for c in ranked:
candidates.extend(self.lists[c])
self.stats.comparisons += len(candidates)
scored = [(cosine(query, self.vectors[i]), i) for i in candidates]
scored.sort(key=lambda pair: (-pair[0], pair[1]))
return [i for _, i in scored[:k]]
def recall_at_k(approximate: list[int], exact: list[int]) -> float:
"""Fraction of the true top-k that the approximate search also returned.
Note what this does NOT measure: ordering. An index that returns all the
right documents in the wrong order scores 1.0 here, which is usually the
right call for retrieval feeding a reranker, and the wrong one if the raw
order is shown to a user.
"""
if not exact:
return 1.0
return len(set(approximate) & set(exact)) / len(exact)
@dataclass
class SweepRow:
nprobe: int
recall: float
comparisons: int
def line(self, baseline: int) -> str:
speedup = baseline / self.comparisons if self.comparisons else 0.0
return (
f"nprobe={self.nprobe:<2} recall@10={self.recall:.2f} "
f"comparisons={self.comparisons:<6} speedup={speedup:.1f}x"
)
@dataclass
class Sweep:
rows: list[SweepRow] = field(default_factory=list)
baseline_comparisons: int = 0
def cheapest_meeting(self, target: float) -> SweepRow | None:
"""The least work that still reaches a recall target.
This is the question worth asking of an ANN index -- not "what is the
best recall" but "what is the cheapest configuration good enough for
the job".
"""
for row in self.rows:
if row.recall >= target:
return row
return None
def sweep_nprobe(
vectors: list[list[float]],
queries: list[list[float]],
*,
k: int = 10,
nlist: int = 8,
) -> Sweep:
"""Measure recall and cost across every nprobe setting."""
exact = BruteForceIndex(vectors)
truth = [exact.search(q, k) for q in queries]
baseline = exact.stats.comparisons
result = Sweep(baseline_comparisons=baseline)
for nprobe in range(1, nlist + 1):
index = IVFIndex(vectors, nlist=nlist)
recalls = []
for query, want in zip(queries, truth):
got = index.search(query, k, nprobe=nprobe)
recalls.append(recall_at_k(got, want))
result.rows.append(
SweepRow(
nprobe=nprobe,
recall=sum(recalls) / len(recalls),
comparisons=index.stats.comparisons,
)
)
return result
metadata.yml (752 bytes)
lesson_id: D326
day: 326
kind: python
languages:
- python
setup_commands:
- pip install -r requirements/requirements.txt
run_commands:
- python examples/retrieval_demo.py
test_commands:
- bash tests/run_tests.sh
cleanup_commands:
- rm -rf __pycache__ .pytest_cache
requires_network: false
requires_api_key: false
estimated_minutes: 55
last_executed: '2026-08-30'
executed_on: 'macOS 26.5.1 (Apple Silicon), Python 3.14.0, pytest 9.1.1 — python3
examples/retrieval_demo.py reproduced the documented sweep exactly (deterministic, seeded generator);
bash tests/run_tests.sh -> 17 passed in 2.25s. The untouched starter was verified to fail all 17.
requires_network is false: vectors are generated in-process and no test opens a socket.'
requirements/requirements.txt (14 bytes)
pytest>=7.0.0
starter/retrieval.py (6971 bytes)
"""Exact versus approximate retrieval, and the recall you trade for speed.
Offline, standard-library only, and deterministic: every vector comes from a
seeded generator, so the numbers in the lesson are reproducible rather than
"about right".
Cost is measured in **vector comparisons**, not wall-clock seconds. That is a
deliberate choice. Wall-clock on a laptop is dominated by interpreter overhead
and whatever else the machine is doing, so it makes a poor teaching signal and
a worse test assertion. Comparisons are the thing an ANN index actually
reduces, they are exactly reproducible, and they scale the same way the real
cost does. The lesson says where this abstraction stops being true.
"""
from __future__ import annotations
import math
import random
from dataclasses import dataclass, field
@dataclass
class Stats:
"""How much work a search did."""
comparisons: int = 0
def reset(self) -> None:
self.comparisons = 0
def make_vectors(n: int, dim: int, *, seed: int = 7, clusters: int = 8) -> list[list[float]]:
"""Generate clustered vectors, because real embeddings are not uniform.
Uniform random points would make every approximate method look terrible:
partitioning only helps when the data has structure to partition. Real
corpora cluster by topic, so the fixture does too.
"""
rng = random.Random(seed)
centres = [[rng.uniform(-1, 1) for _ in range(dim)] for _ in range(clusters)]
out: list[list[float]] = []
for i in range(n):
centre = centres[i % clusters]
out.append([c + rng.gauss(0, 0.15) for c in centre])
return out
def cosine(a: list[float], b: list[float]) -> float:
# TASK 1: cosine similarity. Return 0.0 if either vector has zero norm
# rather than dividing by zero.
raise NotImplementedError("implement cosine")
class BruteForceIndex:
"""Exact search. Always correct, and always O(n) per query."""
def __init__(self, vectors: list[list[float]]) -> None:
self.vectors = vectors
self.stats = Stats()
def search(self, query: list[float], k: int) -> list[int]:
# TASK 3: exact search. Count one comparison per vector, score every
# one with cosine, and return the k best indices. Break ties by
# index so the ordering is deterministic.
raise NotImplementedError("implement BruteForceIndex.search")
class IVFIndex:
"""Inverted-file index: partition into lists, search only the nearest few.
This is the shape of a real IVF index. Build assigns each vector to its
nearest centroid; search compares the query to every centroid, picks the
`nprobe` closest lists, and scans only those. The recall loss comes from
one specific place: a true neighbour sitting in a list you did not probe.
"""
def __init__(self, vectors: list[list[float]], *, nlist: int = 8, seed: int = 11) -> None:
self.vectors = vectors
self.nlist = nlist
self.stats = Stats()
self.centroids, self.lists = self._build(seed)
def _build(self, seed: int) -> tuple[list[list[float]], list[list[int]]]:
"""Assign vectors to lists with a few rounds of Lloyd's algorithm."""
rng = random.Random(seed)
dim = len(self.vectors[0])
centroids = [list(self.vectors[rng.randrange(len(self.vectors))]) for _ in range(self.nlist)]
lists: list[list[int]] = [[] for _ in range(self.nlist)]
for _ in range(6):
lists = [[] for _ in range(self.nlist)]
for i, v in enumerate(self.vectors):
best = max(range(self.nlist), key=lambda c: cosine(v, centroids[c]))
lists[best].append(i)
for c in range(self.nlist):
if not lists[c]:
continue
centroids[c] = [
sum(self.vectors[i][d] for i in lists[c]) / len(lists[c]) for d in range(dim)
]
return centroids, lists
def search(self, query: list[float], k: int, *, nprobe: int = 1) -> list[int]:
# TASK 4: probe search.
# - clamp nprobe into [1, self.nlist]
# - count self.nlist centroid comparisons; they are real work, and
# they are exactly why full probing costs MORE than exact search
# - take the nprobe NEAREST centroids (watch the sort direction)
# - gather those lists' vectors, count one comparison each, and
# return the k best
raise NotImplementedError("implement IVFIndex.search")
def recall_at_k(approximate: list[int], exact: list[int]) -> float:
"""Fraction of the true top-k that the approximate search also returned.
Note what this does NOT measure: ordering. An index that returns all the
right documents in the wrong order scores 1.0 here, which is usually the
right call for retrieval feeding a reranker, and the wrong one if the raw
order is shown to a user.
"""
# TASK 2: fraction of `exact` that also appears in `approximate`.
# Membership, not order: [3,2,1] against [1,2,3] is 1.0.
# An empty truth set is 1.0, not a division by zero.
raise NotImplementedError("implement recall_at_k")
@dataclass
class SweepRow:
nprobe: int
recall: float
comparisons: int
def line(self, baseline: int) -> str:
speedup = baseline / self.comparisons if self.comparisons else 0.0
return (
f"nprobe={self.nprobe:<2} recall@10={self.recall:.2f} "
f"comparisons={self.comparisons:<6} speedup={speedup:.1f}x"
)
@dataclass
class Sweep:
rows: list[SweepRow] = field(default_factory=list)
baseline_comparisons: int = 0
def cheapest_meeting(self, target: float) -> SweepRow | None:
"""The least work that still reaches a recall target.
This is the question worth asking of an ANN index -- not "what is the
best recall" but "what is the cheapest configuration good enough for
the job".
"""
for row in self.rows:
if row.recall >= target:
return row
return None
def sweep_nprobe(
vectors: list[list[float]],
queries: list[list[float]],
*,
k: int = 10,
nlist: int = 8,
) -> Sweep:
"""Measure recall and cost across every nprobe setting."""
exact = BruteForceIndex(vectors)
truth = [exact.search(q, k) for q in queries]
baseline = exact.stats.comparisons
result = Sweep(baseline_comparisons=baseline)
for nprobe in range(1, nlist + 1):
index = IVFIndex(vectors, nlist=nlist)
recalls = []
for query, want in zip(queries, truth):
got = index.search(query, k, nprobe=nprobe)
recalls.append(recall_at_k(got, want))
result.rows.append(
SweepRow(
nprobe=nprobe,
recall=sum(recalls) / len(recalls),
comparisons=index.stats.comparisons,
)
)
return result
tests/run_tests.sh (207 bytes)
#!/usr/bin/env bash
# Run the day 326 scaling retrieval test suite.
# Offline, standard library plus pytest. No network, no API key.
set -euo pipefail
cd "$(dirname "$0")/.."
python3 -m pytest tests -q "$@"
tests/test_retrieval.py (5456 bytes)
"""Grouped by claim, so a failure names which property broke.
Run with: bash tests/run_tests.sh
"""
from __future__ import annotations
import os
import sys
HERE = os.path.dirname(os.path.abspath(__file__))
LAB = os.path.dirname(HERE)
sys.path.insert(0, os.path.join(LAB, "examples"))
from retrieval import ( # noqa: E402
BruteForceIndex,
IVFIndex,
cosine,
make_vectors,
recall_at_k,
sweep_nprobe,
)
SMALL = 400
DIM = 16
def corpus(n: int = SMALL, seed: int = 7):
return make_vectors(n, DIM, seed=seed, clusters=8)
# ----------------------------------------------------------------- geometry
def test_cosine_is_one_for_identical_vectors():
v = [1.0, 2.0, 3.0]
assert abs(cosine(v, v) - 1.0) < 1e-9
def test_cosine_handles_a_zero_vector_without_dividing_by_zero():
assert cosine([0.0, 0.0], [1.0, 2.0]) == 0.0
def test_generated_vectors_are_clustered_not_uniform():
# Approximate methods only help when the data has structure. If the
# fixture were uniform noise, partitioning would buy nothing and the whole
# lesson would be misleading.
vectors = corpus()
within = cosine(vectors[0], vectors[8]) # same cluster (n % 8)
across = cosine(vectors[0], vectors[4]) # different cluster
assert within > across
# -------------------------------------------------------------- exactness
def test_brute_force_returns_k_results_in_score_order():
vectors = corpus()
index = BruteForceIndex(vectors)
query = vectors[0]
got = index.search(query, 10)
assert len(got) == 10
assert got[0] == 0 # a vector is its own nearest neighbour
scores = [cosine(query, vectors[i]) for i in got]
assert scores == sorted(scores, reverse=True)
def test_brute_force_costs_one_comparison_per_vector():
vectors = corpus()
index = BruteForceIndex(vectors)
index.search(vectors[0], 10)
assert index.stats.comparisons == len(vectors)
# ------------------------------------------------------------- partitioning
def test_ivf_assigns_every_vector_to_exactly_one_list():
vectors = corpus()
index = IVFIndex(vectors, nlist=8)
assigned = [i for lst in index.lists for i in lst]
assert sorted(assigned) == list(range(len(vectors)))
def test_ivf_probing_every_list_matches_exact_search():
# nprobe == nlist means no candidate is excluded, so recall must be
# perfect. If this fails, the partitioning itself is losing vectors.
vectors = corpus()
exact = BruteForceIndex(vectors)
index = IVFIndex(vectors, nlist=8)
for q in (vectors[0], vectors[13], vectors[200]):
assert recall_at_k(index.search(q, 10, nprobe=8), exact.search(q, 10)) == 1.0
def test_nprobe_is_clamped_to_the_valid_range():
vectors = corpus()
index = IVFIndex(vectors, nlist=8)
assert len(index.search(vectors[0], 5, nprobe=0)) == 5
assert len(index.search(vectors[0], 5, nprobe=99)) == 5
# ------------------------------------------------------------------ recall
def test_recall_counts_membership_not_order():
assert recall_at_k([3, 2, 1], [1, 2, 3]) == 1.0
assert recall_at_k([1, 2, 9], [1, 2, 3]) == 2 / 3
assert recall_at_k([], [1, 2]) == 0.0
def test_recall_of_an_empty_truth_set_is_one():
assert recall_at_k([1], []) == 1.0
# ------------------------------------------------------------- the tradeoff
def test_recall_rises_monotonically_with_nprobe():
vectors = corpus()
queries = corpus(20, seed=99)
sweep = sweep_nprobe(vectors, queries, k=10, nlist=8)
recalls = [row.recall for row in sweep.rows]
assert recalls == sorted(recalls), f"recall should not fall as nprobe rises: {recalls}"
def test_cost_rises_monotonically_with_nprobe():
vectors = corpus()
queries = corpus(20, seed=99)
sweep = sweep_nprobe(vectors, queries, k=10, nlist=8)
costs = [row.comparisons for row in sweep.rows]
assert costs == sorted(costs)
def test_full_probe_reaches_perfect_recall():
vectors = corpus()
queries = corpus(20, seed=99)
sweep = sweep_nprobe(vectors, queries, k=10, nlist=8)
assert sweep.rows[-1].recall == 1.0
def test_full_probe_costs_more_than_exact_search():
# The honest part of the tradeoff: probing every list does all the work
# brute force does, PLUS the centroid comparisons. An ANN index tuned for
# perfect recall is strictly worse than not having one.
vectors = corpus()
queries = corpus(20, seed=99)
sweep = sweep_nprobe(vectors, queries, k=10, nlist=8)
assert sweep.rows[-1].comparisons > sweep.baseline_comparisons
def test_low_nprobe_is_much_cheaper_than_exact():
vectors = corpus()
queries = corpus(20, seed=99)
sweep = sweep_nprobe(vectors, queries, k=10, nlist=8)
assert sweep.rows[0].comparisons < sweep.baseline_comparisons / 3
def test_cheapest_meeting_returns_the_first_adequate_row():
vectors = corpus()
queries = corpus(20, seed=99)
sweep = sweep_nprobe(vectors, queries, k=10, nlist=8)
row = sweep.cheapest_meeting(0.80)
assert row is not None and row.recall >= 0.80
# It is the cheapest such row, so everything before it falls short.
for earlier in sweep.rows[: row.nprobe - 1]:
assert earlier.recall < 0.80
def test_an_unreachable_target_returns_none():
vectors = corpus()
queries = corpus(20, seed=99)
sweep = sweep_nprobe(vectors, queries, k=10, nlist=8)
assert sweep.cheapest_meeting(1.01) is None
Troubleshooting
Troubleshooting — Day 326
Recall at nprobe=8 is below 1.0
Probing every list means excluding no candidate, so recall must be exactly 1.0. If it is not, the partitioning itself is losing vectors — usually because _build leaves some vectors unassigned, or because a list is dropped when it comes out empty.
Check with:
python3 -c "
import sys; sys.path.insert(0,'examples')
from retrieval import make_vectors, IVFIndex
v = make_vectors(400, 16, seed=7)
idx = IVFIndex(v, nlist=8)
assigned = sorted(i for lst in idx.lists for i in lst)
print('assigned', len(assigned), 'of', len(v), '| duplicates:', len(assigned)!=len(set(assigned)))"
Recall falls as nprobe rises
You are selecting the furthest centroids rather than the nearest. Cosine similarity is higher for closer vectors, so the sort must be descending on similarity — key=lambda c: -cosine(...), or reverse=True.
Full probe costs the same as exact search rather than more
You are not counting the centroid comparisons. They are real work done on every query regardless of nprobe, and they are exactly why full probing is worse than brute force. Add self.stats.comparisons += self.nlist before ranking the centroids.
Every recall is 1.0 at every nprobe
Your corpus is too small, or the clusters are so tight that the nearest list always contains all the true neighbours. Increase the corpus size or nlist, or widen the Gaussian spread in make_vectors.
The numbers do not match the documented table
The generator is seeded, so a correct implementation reproduces it exactly. Differences usually come from one of three places: a different tie-breaking rule in the sort (break ties by index), a different number of k-means rounds in _build, or counting comparisons at a different point.
ZeroDivisionError in cosine
A zero vector has no direction, so cosine is undefined. Return 0.0 rather than raising — test_cosine_handles_a_zero_vector_without_dividing_by_zero checks this.
recall_at_k fails on the empty case
An empty truth set means there was nothing to find, so recall is 1.0 by convention rather than a division by zero.
The suite is slow
Two seconds is expected: the sweep builds a fresh IVF index for every nprobe setting, and k-means runs six rounds each time. If it is much slower, check that _build is not being called inside the per-query loop.
NotImplementedError everywhere
Expected. The starter stubs cosine, recall_at_k, BruteForceIndex.search and IVFIndex.search — see expected-output/starter-run.txt.
Security notes
Security notes — Day 326
What this lab does and does not touch
- No network. Vectors are generated in-process from a seeded pseudo-random generator. No test opens a socket, and
requires_networkisfalse. - No credentials. No API key, token or account anywhere.
- No writes outside this directory. Only
__pycache__/,.pytest_cache/and, if you create it,.venv/. - No
sudo, no global installs. - No unbounded memory. The corpus is 2,000 vectors of 32 dimensions — a few megabytes.
What real approximate indexes raise, which this lab deliberately simulates
An ANN index is a shared data structure, and that creates problems a flat list does not have:
- Multi-tenant leakage. If tenants share an index, one tenant's vectors can sit inside a list another tenant's query probes. Filtering after retrieval is not sufficient: the candidate set was already computed across the boundary, and timing differences can be observable. Partition by tenant, or apply the filter during traversal rather than afterwards.
- Deletion is not removal. Graph indexes such as HNSW commonly tombstone a deleted vector rather than removing it, and the data remains in the structure until a compaction runs. For a right-to-erasure request that is not enough — the obligation is to delete, not to hide. Check what your index actually does rather than assuming, and confirm that compaction has run.
- Rebuilds copy everything. An index rebuild materialises a second full copy of the vectors, often on disk. That copy inherits the same access-control and retention obligations as the original, and is easy to forget.
Privacy
Embeddings are derived from content and are not anonymous: inversion attacks can recover meaningful information about the source text from a vector. Treat an embedding store with the same care as the documents it was built from, not as a harmless numeric artefact.
Reversing everything this lab did
rm -rf __pycache__ .pytest_cache .venv
Nothing else was created, and nothing outside this directory was modified.