Dear engineers, your AI agent has goldfish memory.
Every coding agent on your laptop (Claude Code, Cursor, Copilot) starts each session blind. It forgets yesterday's design decisions, hallucinates function names that do not exist, and re-derives bug fixes you already shipped. You read about this in Case Study 0.2: claude-mem and QMD are 2026 tools that fix it by indexing your codebase and your decisions into a local SQL database, so the agent can look things up before it makes things up.
In Project 1 you queried other people's databases. In Project 2 you build the engine the next generation of AI tools is built on.
If Tobi Lütke (CEO of Shopify) shipped the first version of QMD in a weekend, you can build a deeper version in five weeks.
.ipynb) plus a 5-minute screen recording, due Nov 20.sqlite3 stdlib plus pip install sqlite-vec), used as
your production reference.Proposal due Oct 30. Final due Nov 20. Five weeks of work, about 8 hours a week. Jot AI surprises as they happen so you can write them up later.
Oct 17 to Oct 23 · 8 to 10 hours · Phases 0 + 1 (start)
Load both 100 MB datasets into SQLite with FTS5 and sqlite-vec. Run your first BM25 query and your first vector query on both datasets. You have a two-dataset search engine in 30 lines. Then start hand-rolling the inverted index on the toy dataset.
Oct 24 to Oct 30 · 8 to 10 hours · Phase 1 + proposal
Finish your inverted index and BM25 scoring. Pass the parity test against FTS5 on the 100 MB code dataset. Submit the proposal at the end of this week with Phase 0 already working: FTS5 and sqlite-vec query output from both datasets, a paragraph on what surprised you, then your plans (target tier, custom fusion, partner divvy).
Oct 31 to Nov 6 · 8 to 10 hours · Phase 2
Random projections, banding, candidate ranking by hit count, exact cosine re-rank. Pass the parity test against sqlite-vec. If your recall craters, revisit the FAQ on candidate selection.
Nov 7 to Nov 13 · 7 to 8 hours · Phases 3 + 4
Build hybrid retrieval, your custom fusion variant, and the query planner. Run the two-dataset benchmark. This is where you watch the same engine produce opposite winners on code vs knowledge. The lesson is not which algorithm wins, it is which workload favors which. Spend a paragraph on it in your writeup notes.
Nov 14 to Nov 20 · 5 to 7 hours · Phases 5 + 6
Run the production scoreboard: your numbers vs FTS5 and sqlite-vec, same dataset, same eval, same metrics. By the end you know exactly how close your hand-rolled engine got to industry baselines, where production wins, and why. Record the 5-minute demo (2 min of NanoMem running, 3 min walking through your code). Submit.
Pick one row before you write the proposal. You can climb later, but the proposal asks you which tier you are aiming for so partners (and we) know how to plan the work. Tier 87 is the spec target; Tier 93 and Tier 100 are where memory starts to bite back.
| Tier | What you ship | Dataset size | Effort |
|---|---|---|---|
| Tier 80 | Hand-rolled engine matches FTS5 + sqlite-vec on parity. End-to-end demo of all five retrievers running on both datasets. | 100 MB (25K docs per dataset) | 34 to 42 hours. ~350 LOC. Any laptop. |
| Tier 87 spec target |
Same code at 10× the data. Where most students land. Workload asymmetry between code and knowledge becomes obvious. | 1 GB (250K docs per dataset) | 36 to 45 hours. ~350 LOC (same as Tier 80). Any laptop or free Colab CPU. |
| Tier 93 | HashPartition with single-shard residency. Memory turns into the constraint that drives the design. Module 3 partitioning applied to retrieval. | 5 GB (1.25M docs, at least one dataset) | 41 to 52 hours. +80 LOC for shard build and query merge (~430 total). Free Colab CPU. |
| Tier 100 | Streaming retrieval over Wikipedia at a 1 GB working set. The algorithm is the same; what changes is the discipline. | 22 GB Wikipedia (6.7M articles → 25M passages) | 48 to 60 hours. +80 more LOC for streaming embed and bounded vocab (~510 total). Colab T4 GPU for the embedding pass. |
| +5 bonus | Top 3 quality-per-millisecond on the Tier 93 leaderboard. Independent of where you land on the ceiling. | Tier 93 dataset | Not LOC; profile and tune. |
Final score = min(quality_score, tier_ceiling) + bonus.
Quality is the bottleneck more often than scale; a polished Tier 87 project earns 87,
a sloppy Tier 93 project earns 72. Push both.
Choosing between the two Project 2 options? In this project tiers are a scale ceiling: the same code, bigger data raises the cap. The Data Science project (BigQuery Part Deux) grades tiers the other way, adding a new section per tier.
Going further (optional, not graded).
Fighting the memory ceiling at Tier 93 or Tier 100? One lever we deliberately did
not require: stop storing float32 embeddings and quantize them instead.
pip install turbovec, about five lines, and 384-dim MiniLM vectors
compress roughly 8× at bit_width=4 with little recall loss.
Measure Recall@k against peak memory and put the trade-off in your writeup.
Why this works, when it does not, and the classic-PQ-versus-TurboQuant story:
Case Study 2.4: Compressing a Billion Embeddings.
Your final grade has two axes: a quality score out of 100 (judged from the 7-phase rubric below) and a tier ceiling (which row of Tiers at a glance you reach). Push both.
psutil) is the high-water mark your process actually held.
Working set is what's live in memory at any one moment, which is
what we grade against the 2 GB and 1 GB targets at Tier 93 and Tier 100.
At Tier 80 and Tier 87 you just report both numbers, no cap. See
Tier 93 FAQ for what to keep visible in your
notebook so we can verify residency without re-running.The per-tier ceilings and effort are in Tiers at a glance above. This section is the quality side: the 7-phase rubric that scores your 0-to-100 quality number, regardless of which tier you land.
Each phase carries its rubric, its tests, its parity bar, and a "what good looks like" inline in
nanomem-template.py. Read the section header before you start coding. The point totals:
| Phase | Section | Points |
|---|---|---|
| 0 | Production setup (SQLite + FTS5 + sqlite-vec, both datasets). The end-of-week-1 proposal IS this phase. Submit by then to bank the 10 points; miss the deadline and they forfeit. | 10 |
| 1 | Inverted index + BM25 from scratch (parity vs FTS5) | 20 |
| 2 | LSH for vector search from scratch (parity vs sqlite-vec) | 20 |
| 3 | Hybrid retrieval + query planner (RRF + your custom variant) | 15 |
| 4 | Two-dataset benchmark (all 5 retrievers, both datasets) | 10 |
| 5 | Production scoreboard (your numbers vs FTS5 and sqlite-vec) | 10 |
| 6 | Writeup + 5-min demo + AI takeaways | 15 |
| Total | 100 | |
The specific test functions, parity bars (e.g., "within X% of FTS5 on R@5"), and pedagogical goals for each phase are documented in the template's section headers. They are the canonical source; this table is the macro summary.
What the staff reference produces, end-to-end, on real CodeSearchNet (Mac CPU, no GPU). Use these as a sanity check for your own numbers. They are not a target. If yours land in the same neighborhood you are probably correct; if you are far off, that is worth explaining in your writeup.
Aiming for Tier 93 or Tier 100? See Tier 93 FAQ for the sharded-recall heads-up, the iterate-on-50 / report-on-500 tip, and what "single-shard residency" means for grading.
| Tier | Build | Eval p50 | R@5 | Working set | Notes |
|---|---|---|---|---|---|
| Tier 80 (100 MB, unsharded) | < 1 s | ~30 ms | ~0.98 | ~1.2 GB | recall ceiling, no constraints |
| Tier 80 (100 MB, sharded N = 4) | ~1 s | ~360 ms | ~0.72 | ~1.1 GB | sharded retrieval tradeoff visible already |
| Tier 87 (1 GB, unsharded) | ~5 s | ~250 ms | ~0.88 | ~1.5 GB | spec target. No sharding needed at this tier. |
| Tier 93 (5 GB, sharded N = 4) | ~20 s | ~3.6 s | ~0.72 | ~1.7 GB | HashPartition required to stay under 2 GB |
Sharded R@5 is typically lower than unsharded. That is a real tradeoff to discuss
in your writeup, not a bug. The "working set" column is the size of what's live at
any one moment, which is what we grade against the 2 GB target;
psutil's peak RSS will read higher because Python doesn't return
freed pages to the OS. See
Tier 93 FAQ for the details.
Core rule: the algorithms in your final submission must be your own. You may use production tools as your baseline (Phase 0) and as your parity reference (Phases 1, 2, 5). You may not use them as your retrieval algorithm.
Use AI freely to learn the concepts. Ask Claude to explain LSH three different ways. Watch a 3Blue1Brown video on hashing. Paste the original BM25 paper and have AI walk you through the math. The intuition layer is exactly what AI is good at, and you should use it.
Write the algorithm yourself. The inverted index, the LSH bands, the BM25 scoring loop, the hybrid combiner. Write your own code. Not because typing matters, but because writing them yourself is what tells you whether you actually understood the intuition you just absorbed. The line, in one sentence: if you could not explain the code you submitted to a TA in plain English, with the chat window closed, you crossed it.
sqlite3 for metadata storage.dict, set, Counter,
heapq as your data structures.model.encode(text).rank_bm25 or any other pre-built BM25 implementation.You must follow the Stanford Honor Code. Original engineering is required.
The proposal IS Phase 0, worth 10 points, due Oct 30 (end of week 2). Submit it on time with Phase 0 actually working and the 10 points are yours; miss the deadline and Phase 0 forfeits. One markdown cell at the top of your notebook (with the Phase 0 code cells run above it), covering:
The point of the on-time milestone is pace. Ship the proposal on time and the back half of the project has room to breathe instead of a final-week scramble.
Inline in nanomem-template.py. Each phase has its rubric, its tests, and its parity
bar in the section header. The summary on this page is the macro picture; the per-section
details live in the code.
For Phase 0 (production baseline) and Phase 5 (production scoreboard), yes. SQLite + FTS5 is the BM25 reference; sqlite-vec is the vector KNN reference. Both ship with Python. For the rest of your engine, NO. Build it however you want.
For each term, a list of (doc_id, term_frequency) pairs. Optionally also
positions if you want phrase queries. When a query comes in, you look up the
posting list for each query term and combine them. A
dict[str, list[tuple]] works fine for the in-memory representation.
Three things to check, in order. First: are you tokenizing the query the same way you tokenized
the dataset? If you stripped underscores in one and not the other, your match rate will drop.
Second: is your IDF formula correct? The + 1 inside the log keeps IDF non-negative
for very common terms. Without it, common terms can get a NEGATIVE score and pull the whole
document down. Third: is your length normalization computing |d| / avgdl, not
|d| - avgdl?
Yes. The tokenizer is substrate, not the algorithm. Modify if you want, but you do not have to.
Note that the template tokenizer is identifier-aware (keeps verify_jwt as one
token) while FTS5's default tokenizer is not (splits on underscores). This will produce
measurable differences in your parity test. Both are defensible; document what you chose and
why.
The most common LSH bug (recall craters between Tier 80 and Tier 87) is documented in
the Phase 2 section header of nanomem-template.py. Read that header
before you start coding LSH.
Start with n_bands=60, bits_per_band=3. That gives 8 buckets per band, expected
bucket size N/8. Across 60 bands, the candidate set with rank-by-hits will surface the true
nearest neighbors at the top. The recall/latency curve as you vary one parameter is a great
thing to plot in your writeup; do not try to find the global optimum from scratch.
After bucketing, you might have 10K candidates. Re-ranking all of them with exact cosine defeats the point of LSH. Cap candidates at some K (e.g., 1000) and re-rank only those. The cap trades recall for latency; document the tradeoff.
No, that is exactly the finding to write up. Naive RRF gives equal weight to a strong and a weak signal; on a dataset where one signal dominates (BM25 on code, LSH on knowledge), RRF drags down the dominant signal's right answers with the weak signal's wrong ones. This is why you build a custom fusion in Phase 3. to do better than naive RRF.
Anything meaningfully different from RRF that you can defend. Examples:
0.7 * bm25 + 0.3 * lsh (or whatever weights).
Document what you did and why, in a comment at the top of your custom_fusion
function.
R@1, R@5, R@10, MRR, p50 and p95 latency, peak memory (RSS). See the Metrics card at the top of Grading for definitions.
Mount Google Drive and write the cache there. Drive persists across sessions; Colab's local disk does not. The standard pattern:
from google.colab import drive
drive.mount('/content/drive')
CACHE_DIR = Path("/content/drive/MyDrive/nanomem_cache")
CACHE_DIR.mkdir(exist_ok=True)
# Then point cached_embed_batch() at this directory.For Tier 100 (Wikipedia, ~25M passages), consider running the embedding pass on a separate machine with a beefier GPU and uploading the resulting Parquet to Drive. You only need to do it once.
Skip this subsection if you are aiming for Tier 87. The two callouts below are where most Tier 93 confusion starts, so read them before debugging.
Component-by-component breakdown across the three
memory-constrained tiers. The substrate's memory_breakdown(...) prints
this same table for your own indexes, so you can compare against the reference numbers.
| Component | Tier 87 (1 GB, 250K) | Tier 93 (5 GB, 1.25M) | Tier 100 (20 GB, 25M) |
|---|---|---|---|
| Embedding matrix (float32) | ~380 MB | ~1.9 GB | ~38 GB |
| Inverted index postings (numpy) | ~400 MB | ~2.0 GB | ~10 GB |
| LSH bands (60 × bucket dicts) | ~300 MB | ~1.5 GB | ~12 GB |
| Doc texts in memory | ~250 MB | ~1.25 GB | ~25 GB |
| Vocabulary keys | ~30 MB | ~150 MB | ~500 MB |
| Model + misc | ~100 MB | ~100 MB | ~100 MB |
| Total unsharded | ~1.4 GB | ~7 GB | ~85 GB |
| RAM budget | unlimited | 2 GB | 1 GB |
| Single-shard working set | n/a (no sharding) | ~1.7 GB (N = 4) | ~700 MB (N = 128). Scale N up; that's the primary lever. |
Tier 87 fits unsharded. Tier 93's total (~7 GB) blows past the 2 GB budget, so HashPartition with N = 4 brings the single-shard working set under the cap. Tier 100 needs the same idea with a larger N. One algorithm at every tier; the only knob is N.
Only one shard's data structures (inverted index, LSH bands, posting lists)
should be referenced in Python at any moment. After you query shard
i, drop it before loading shard i+1. Your working
set (the size of what's live) should stay under 2 GB; that's what we
grade against. psutil's peak RSS will often
read higher than your working set because Python doesn't return freed heap
pages to the OS, so we treat the raw RSS number as a soft signal, not a
hard cap. Print your peak RSS in the notebook, explain it in one line in
your writeup, and you are fine.
How to make this gradable. Leave the following outputs visible in your submitted notebook so we can verify residency by reading, not by re-running:
memory_breakdown(...) for at least one shard
build. This is the per-component table; it should show the live shard
well under 2 GB.[mem] prints from MemoryBudget
(working set and peak RSS) for the eval run.R@1, R@5, R@10, MRR, p50, p95, peak_mb summary
cell.The bottleneck is usually one of three things. Check in this order:
del model; gc.collect() when you are not
embedding.Maybe. Worth trying. You met Bloom filters in M2 as one of the standard storage tricks; the question is whether they buy you anything here.
The natural place to try one is per-shard: build a small Bloom of "every token that appears in any doc in this shard," and at query time skip loading shards whose Bloom says "definitely none of my query tokens." Implement it, measure how often the Bloom actually skips a load, and report what you find. The answer is partitioning-dependent in an interesting way, and a clean Bloom-vs-no-Bloom microbenchmark is exactly the kind of analysis that strengthens your writeup and, if it speeds your queries, your standing on the Tier 93 leaderboard.
Only attempt Tier 100 after Tier 93 is working. The algorithm is the same; what changes is the size of N and the discipline of the residency.
wikimedia/wikipedia (English subset, 6.7M articles, ~22 GB compressed / ~75 GB uncompressed, roughly every fact on the open web). Chunk into ~25M passages, embed yourself (~3 to 5 hours on Colab T4 GPU or ~30+ hours on CPU; consider running the embedding pass on a separate machine with a beefier GPU and uploading the resulting Parquet to Google Drive). Then index and retrieve against it. Tier 100 is bonus precisely because the engineering is hard.
Two things stack. First the data: scale your HashPartition build to the full ~22 GB English Wikipedia dataset (~6.7M articles chunked into ~25M passages). Second the constraint: keep the working set under 1 GB (single-shard residency at N = 128). The memory budget is what makes this tier hard; the algorithmic answer is more shards, not new machinery.
What that forces you to do: lazy-load shards one at a time, stream posting-list scans (don't materialize the full posting in Python), bound LSH band caches, and aggressively delete intermediate state between query phases. The biggest one-time cost is still the embedding pass at 3 to 5 hours on a Colab T4 GPU. Cache embeddings to Drive so you don't lose them on session restart.
Use AI freely for the conceptual layer. Asking Claude to explain LSH from the original paper. Asking it to walk you through the BM25 formula. Asking it to debug a NumPy shape mismatch. These are exactly what AI is good at, and using it well is a skill we want you to develop.
Not OK: AI-written inverted indexes, LSH implementations, or BM25 scorers. The algorithms were covered in lecture and the FAQ has the formulas. Implement them yourself. The bar is whether you can talk through your inverted index, your LSH, and your hybrid combiner in plain English without pulling up a chat window.
Short and informal. Half a page, not a report. 2 to 3 anecdotes (a few sentences each) plus one plain-English walkthrough of a piece of your engine. Good anecdotes capture a moment:
Both deliverables go to Gradescope. Dates and what each one contains are above; this is the file checklist.
.ipynb notebook with all output cells visible
(printed numbers, tables, and any [mem] prints from
MemoryBudget). We read these to grade; we do not re-run your
notebook.memory_breakdown(...) output and the per-query [mem]
prints visible. That's how we verify single-shard residency by reading rather
than by re-running. See the
Tier 93 FAQ for what specifically to keep.The mission, the schedule, the tier ladder, what gets graded, and why this matters. Watch this first if you have not read the page yet.
A tour of nanomem-template.py: what is given, what you write, and the trap that bites every cohort.