Systems From First Principles

← All Roles

A 15-project, 130-week program that trains you to reconstruct foundational computer systems from their constraints — Transformers, ANN indexes, vector databases, LSM engines, distributed key-value stores, MapReduce, stream processors, recommenders, experimentation platforms, a programming language, an OS kernel, a tensor framework, and a matrix-multiplication accelerator simulator — then measure them, break them, modify them, and write them up like papers.

Not a curriculum. There are no lectures to consume. Every unit ends in running code, a benchmark with tail latencies, a falsified or surviving hypothesis, and a technical report.

Table of Contents

• The Honest Duration
• What This Trains
• Start Here
• The Twenty Deliverables
• Repository Layout
• The Runnable Tools
• The Universal Project Loop
• Operating Rules
• What This Journey Refuses To Do
• Honest Status
• References

The Honest Duration

You asked for 18–30 months at 8–12 focused hours per week, and you asked me not to compress the plan artificially. Those two constraints are in tension, so here is the arithmetic before anything else.

The fifteen projects, scoped to minimum-viable plus standard implementation and excluding every optional research extension, total 1,430 focused hours across 130 active weeks. The per-project derivation is in Project Portfolio; the weeks are the same numbers divided by an 11 h/week pace.

Calendar time is not active weeks. Assume 46 productive weeks per year — six weeks lost annually to travel, illness, work crunch, and the two weeks after any production incident at your day job. Then:

Headline: 34 months. Roughly two years and ten months. I am not going to tell you 18, because 18 months × 12 h/week is 936 hours and you cannot build a kernel and a language and a distributed KV store and a tensor framework in 936 hours at a depth that produces defensible original work. The compressed version of this plan exists and it is called a tutorial series.

If the 30-month ceiling is genuinely hard

There are exactly six scope cuts that preserve the core mechanism of every project. Take all six — 15 weeks — and you land at 115 active weeks / 1,265 hours / exactly 30 months at 11 h/week:

Taking only the first five saves 13 weeks, which lands at 117 weeks / 1,287 hours / 30.5 months — near enough that the sixth cut is optional.

Do not achieve 30 months by working faster on the full scope. That produces fifteen half-built systems and no reports, which is worth less than five finished ones.

Full derivation, dependency graph, and stage boundaries: Roadmap.

What This Trains

The stated goal is the technical depth of people who built MapReduce, Spanner, TensorFlow, TPUs, language runtimes, kernels, databases, and Transformers. That depth is not a body of knowledge. It is a set of habits, and each one is trained by a specific mechanic that appears in every project:

The failure mode this program is designed against is yours, specifically: you told me you spread attention across too many subjects and stay in consumption mode. So the guardrails are not advice, they are rules with a stated enforcement mechanism. See Guardrails. The single most important one:

One primary implementation project at a time. Reading never completes anything.

Start Here

You do not need to read the fifteen project pages before you start. Read Project 1 and the Roadmap; read each subsequent project page in the week before you begin it. Reading all fifteen now is itself the consumption-mode failure this program exists to break.

The Twenty Deliverables

Every item you asked for, and where it lives.

Plus seven you did not ask for but will need:

Repository Layout

README.md              this file
roadmap.md             duration derivation, dependency graph, 6 stages, 34 monthly milestones
projects.md            master table, effort model, three scope tiers
projects/              p01..p15 — the full specification of each build
first-12-weeks.md      week-by-week for weeks 1-12
week-one.md            hour-by-hour for week 1, starting now
week-generator.md      how to decompose weeks 13-130 yourself, with 3 worked examples
calibration.md         the 3-hour battery, taken before week 1
STATE.md               the ledger spanning all 130 weeks
portfolio-audit.md     what the fifteen cover, cover twice, and miss
reading-method.md      three-pass reading, and reading code
retention.md           review queue, rebuild drills, forced reuse, teaching tests
feedback-loops.md      adversarial self-review, publishing, reproduction exchange
datasets-and-hardware.md  what it needs, what it costs, the two real dependencies
numbers.md             every constant, derived and measured, with what it decides
proofs.md              18 derivations, each verified by tools/proofs.py
glossary.md            ~90 concepts, explained rather than defined, 18 with runnable code
walkthroughs.md        six 45-minute executable miniatures
walkthroughs/          w1..w6 -- the scripts behind them
handson/               h01..h15, the 15 generated pages, and build_pages.py
scaffold/              new-project.sh + templates for python / rust / go
scores/                scorecard.json, trended by tools/scorecard.py
operating-model.md     weekly rhythm, time allocation, thinking exercises, guardrails
notebook-template.md   the research notebook, explained field by field
notebook/              example-filled.md — a real, completed notebook entry
templates/             notebook.md, report.md, experiment.md — copy these
scorecard.md           12 categories, 1/3/5 anchors, completion definition
ai-policy.md           the ten rules, with enforcement
languages.md           Python / Go / Rust / C / CUDA — which mechanism each exposes
math.md                just-in-time mathematics, tied to the project that needs it
readings.md            every primary source, by project, with why-read-this notes
portfolio.md           artifacts, publication venues, the paper
not-yet.md             what to actively refuse to study, and when it unlocks
research-directions.md the seven that can become original work
final-system.md        Project 15's architecture and its research question
sustainability.md      completing this while employed full-time
tools/                 bench.py, roofline.py, metrics.py, annlab.py, bloom.py

The Runnable Tools

Five scripts you use across the whole journey. All are executed and their real output is quoted in the pages that reference them — no unverified numbers appear anywhere in this track.

cd tools

cc -O2 -o machine-baseline machine-baseline.c && ./machine-baseline
                               # regenerates every hardware constant in numbers.md
./machine-baseline --json > mine.json && python3 baseline.py mine.json
                               # diff vs the reference + 8 invariant checks
python3 calibrate.py 3 4 2 1 3 # calibration scores -> adjusted schedule
python3 scorecard.py trend     # 12 categories x 15 projects, what is rising
python3 proofs.py              # 116 checks over every derivation in proofs.md
python3 -m pytest tests/ -q    # 63 tests over the tools themselves

python3 bench.py demo          # the measurement harness: p50/p95/p99 + bootstrap CI
                               # + an honest "no measurable difference" verdict
python3 roofline.py table      # ridge points; the batch size that ends memory-boundedness
python3 roofline.py decode --params 7e9 --hw h100
python3 roofline.py gemm --m 4096 --n 4096 --k 4096
python3 metrics.py demo        # recall/precision/NDCG/MRR/coverage/novelty/Gini,
                               # Welch t, power sizing, sample-ratio-mismatch chi-square
python3 bloom.py               # Bloom theory vs measurement, and where measurement fails
python3 annlab.py              # brute force vs a small-world graph: the recall/latency curve

bench.py, metrics.py, and roofline.py are dependency-free. annlab.py needs numpy.

Read tools/bench.py before you write a single benchmark. It encodes four rules — distribution not mean, warmup separated from measurement, bootstrap interval on the median, environment recorded — and if you internalise only one artifact from this whole track, that is a good one to pick.

The Universal Project Loop

Every one of the fifteen projects runs the same fourteen steps, in order. The loop is the actual curriculum; the projects are just the substrate it runs on.

  1  Problem definition        What breaks if this system does not exist?
  2  Requirements/constraints  What is fixed? What is negotiable? What is assumed?
  3  Naive design              Your design, written BEFORE you read the paper.
  4  Predicted failure points  Where and at what scale you expect it to break.
  5  Minimal implementation    The smallest thing that exhibits the mechanism.
  6  Correctness testing       Property tests and invariants. Before any timing.
  7  Instrumentation           Counters and timers in the code, not around it.
  8  Baseline measurement      A number you can be beaten by.
  9  Bottleneck analysis       Where the time actually goes. Measured, not guessed.
 10  Hypothesis                One falsifiable claim, with its falsifier stated.
 11  Modification              The smallest change that tests the hypothesis.
 12  Controlled experiment     One variable. Fixed seeds. Repeated trials.
 13  Failure analysis          What broke, why, and what it generalises to.
 14  Technical report          Including the results that made you wrong.

Steps 3 and 4 are the ones people skip, and they are the ones that produce the ability you actually want. A person who has read the MapReduce paper knows what MapReduce is. A person who designed a batch framework, predicted that stragglers would dominate, and then measured a 6× tail inflation from one slow worker understands why the paper has a section on backup tasks. Those are different skills and only one of them survives a hard design review.

Full field-by-field guidance: Notebook Template. A completed example with real measured numbers: Worked Notebook Entry.

Operating Rules

Applied without exception. Each is here because it prevents a specific documented failure mode of self-directed systems study.

• One primary implementation project at a time. Plus at most one small maintenance or writing task from an earlier project, plus at most one bounded reading thread that directly supports the current project. Nothing else.
• Reading never completes anything. A unit is done when code runs, a benchmark is recorded, and a report exists.
• No optimization without a baseline. If you cannot state the number you are trying to beat, you are not optimizing, you are fiddling.
• No performance claim without tail latency. Mean latency is the number that hides the bug.
• No performance work while a correctness test is red. Fast and wrong is a regression, not a result.
• Predictions are written before runs. A prediction recorded after the result is not a prediction, and the habit it builds is the opposite of the one you want.
• Negative results are shipped, not buried. The report section titled "What I Expected And Did Not Get" is mandatory and is scored.
• Extensions are locked until exit criteria are met. Every project has an attractive optional extension. It is not available until the standard version passes.
• Every project produces an artifact that is useful on its own. If it only makes sense as part of the journey, it is not a portfolio piece.
• A stalled project gets a written postmortem, not a silent abandonment. See the two-week rule.

What This Journey Refuses To Do

Stated up front so you can disagree now rather than in month nine.

• It will not make anything production-grade. No auth, no multi-tenancy, no packaging, no ops. Every hour spent on production polish is an hour not spent on a mechanism. The one exception is Project 15, and only for the specific subsystem its research question depends on.
• It will not chase completeness. The kernel will not run a shell. The language will not have a standard library. The database will not be ACID. Completeness is a substitute activity for depth.
• It will not let you rewrite things in a new language because the new language is interesting. Language choice is fixed per project and justified by which mechanism it exposes.
• It will not treat complexity as originality. A system with nine components and no measured claim scores lower than a system with two components and a falsified hypothesis. See Scorecard.
• It will not pretend the schedule survives contact with your job. See Sustainability, which budgets for the bad quarters instead of assuming they will not happen.

Honest Status

This track is a plan and a toolkit, not a completed body of work. What exists today:

• Complete: the roadmap and its arithmetic, all fifteen project specifications, the first twelve weeks in day-level detail, the week-one hour-by-hour plan, the notebook template plus one fully worked entry with real measured numbers, the scorecard, the AI policy, the language and mathematics strategies, the portfolio plan, and five executed, verified tools.
• By design absent: the fifteen implementations. Those are yours. This track will not contain a reference solution for any project, because a reference solution available on day one destroys step 3 of the loop, which is the step that matters most.
• Numbers: every measured figure quoted in these pages was produced by running the script named next to it on the machine described in tools/bench.py's environment block — a 12-core arm64 macOS laptop, CPython 3.14.0, under a nonzero load average. They are illustrative of shape, not of your hardware. Re-run them on your machine in week 1; the numbers will differ and the shapes will not.

References

The complete, per-project reading list with annotations is in Readings. The handful below define the intellectual posture of the whole track and are worth reading in the first month.

On the method

• Hamming, R. W. You and Your Research. Bell Communications Research Colloquium Seminar, 1986. The canonical talk on choosing important problems and working with open doors. Read this in week 1.
• Bell, C. G., Newell, A. Computer Structures: Readings and Examples. McGraw-Hill, 1971. The original argument that systems should be studied as designed artifacts with explicit tradeoffs.
• Lampson, B. W. Hints for Computer System Design. SOSP '83, ACM Operating Systems Review 17(5), 1983. Thirty-odd design maxims from someone who built the systems. "Handle normal and worst case separately" is the one you will re-derive most often.
• Feynman, R. P. Cargo Cult Science. Caltech commencement address, 1974. On the discipline of not fooling yourself, which is the entire content of the experimental sections here.
• Wilson, G. et al. Best Practices for Scientific Computing. PLoS Biology 12(1), 2014. Reproducibility as an engineering practice.

On measurement

• Williams, S., Waterman, A., Patterson, D. Roofline: An Insightful Visual Performance Model for Multicore Architectures. CACM 52(4), 2009. Implemented in tools/roofline.py.
• Gregg, B. Systems Performance: Enterprise and the Cloud, 2nd ed. Pearson, 2020. The USE method, and the best available treatment of "which of the four resources is actually saturated".
• Dean, J., Barroso, L. A. The Tail at Scale. CACM 56(2), 2013. Why p99 is the number that matters and why it gets worse as you add machines.
• Mytkowicz, T. et al. Producing Wrong Data Without Doing Anything Obviously Wrong! ASPLOS '09. Measurement bias from link order and environment size — read before you trust your first speedup.
• Fleming, P. J., Wallace, J. J. How not to lie with statistics: the correct way to summarize benchmark results. CACM 29(3), 1986. Why the arithmetic mean of ratios is wrong.

On writing systems up

• Shewchuk, J. R. Three Sins of Authors in Computer Science and Math. 1997.
• Zobel, J. Writing for Computer Science, 3rd ed. Springer, 2014. The standard reference for the report format used in templates/report.md.
• Peyton Jones, S. How to Write a Great Research Paper. Microsoft Research, 2004. Specifically: write the paper first, then do the research — which is the same instruction as "write your hypothesis before you run the experiment".

State — The Progress Ledger

The one file that spans all 130 weeks. RESUME.md lives inside each project and tells you where you stopped yesterday. This tells you where you are in the journey.

Update it at every project boundary and every stage review — roughly twenty times across the journey, not weekly. A ledger you must maintain constantly gets abandoned; one you touch every six weeks does not.

Everything below is the template with the starting state filled in. Overwrite as you go. The <!-- comments --> explain each field; delete them once the habit is formed.

Right Now

DATE            : not started
PHASE           : pre-calibration
CURRENT PROJECT : none
CURRENT WEEK    : 0 of 130
PACE            : undecided  (see README "The Honest Duration")
MODE            : —          (full 11 h/wk | maintenance 3 h/wk | zero, planned)

Next action: take the 3-hour calibration battery, cold, then run python3 tools/calibrate.py C1 C2 C3 C4 C5 and record the adjusted schedule below.

Calibration

Re-takes (C3 / C5 only):

Projects

Gate = the eight-item completion gate. A project is done when the gate passes, not when the code works.

Status values: not started · in progress · complete · cut (reason) · abandoned (postmortem written).

Estimation Calibration

Running multiplier: —

If the multiplier exceeds 1.3 after three projects, your real pace is lower than planned. Re-derive the end date from the duration table and move it. Do not plan to catch up; nobody catches up.

Scorecard Trend

Recorded by tools/scorecard.py into scores/scorecard.json. Summarise here at each stage review.

cd tools && python3 scorecard.py trend

Retention

Outcomes: working in 3h (you own it) · bugs findable (mostly) · cannot start (you never owned it — schedule a re-read, add queue items).

Review queue: _ items · last run: —

External Feedback

Corrections received that changed a score:

Decisions and Cuts

Blocked On

Parking List

• (empty)

Log

[not started]  Track built. Calibration is the next action.

Roadmap

The duration arithmetic, the dependency structure, the six stages, and thirty-four monthly milestones.

Table of Contents

• Duration Derivation
• Dependency Graph
• Why This Order
• Legal Reorderings
• The Six Stages
• The Active-Week Schedule
• Monthly Milestones (M1–M34)
• Checkpoint Reviews
• References

Duration Derivation

Step 1 — effort per project

Each project's hour figure is the sum of its milestones, estimated at the pace of a senior engineer who knows the language but not the domain, and excluding optional research extensions. The full milestone breakdown is on each project page; the totals:

Step 2 — active weeks to calendar time

\[ \text{calendar months} = \frac{H}{W_{\text{prod}} \times p} \times 12 \]

where \(H = 1430\) hours, \(p\) is your sustained weekly pace, and \(W_{\text{prod}} = 46\) is productive weeks per year. Forty-six, not fifty-two, because six weeks a year vanish into travel, illness, a launch at work, and the fortnight after any real production incident. A plan that assumes fifty-two productive weeks is not optimistic, it is arithmetically wrong.

Step 3 — the honest verdict

34 months. Your stated ceiling of 30 months is reachable two ways, and only two:

• Sustain 12 h/week for the full scope — 1,430 h / 552 h per year → 31 months, with no margin for a bad quarter.
• Stay at 11 h/week and take the six scope cuts listed in the README — 1,265 h / 115 active weeks → exactly 30 months.

Anything shorter is achieved by deleting projects, not by working faster. If you want a shorter honest journey, the right cut is P01, P02, P04, P05, P13 and P15 only — six projects, 660 hours, 60 active weeks, ≈16 months at 11 h/week — which still covers a Transformer, an ANN index, a storage engine, a distributed system, an autodiff framework and an integrated contribution. That is a real 16-month plan. A 16-month plan containing all fifteen projects is not.

Dependency Graph

Solid arrows are hard dependencies: the downstream project consumes the upstream project's code or its measured results. Dashed arrows are soft: the downstream project is much easier if you have done the upstream one, but does not import it.

 STAGE 1              STAGE 2               STAGE 3            STAGE 4         STAGE 5      STAGE 6
 foundations          storage & exec        distributed        product         low-level    contribution

 P01 Transformer
   │  ┊
   │  ┊ (motivates)
   ▼  ┊
 P13-I Autodiff ───► P13-II Exec Opt ──────────────────────────────► P14 HW-aware ─┐
   │                                                                       ▲        │
   └───────────────────────────────────────────────────────────────────────┘        │
                                                                                    │
 P02 ANN index ────► P03 Vector DB ─────────────────────────────────────────────────┤
   │                    │  ▲                                                        │
   │                    │  ┊ (persistence borrowed from)                            │
   │                    │  ┊                                                        │
   │                 P04 LSM engine ──► P05 Distributed KV ──► P06 MapReduce         │
   │                                          │      ▲              │               │
   │                                          │      ┊              ▼               │
   │                                          │      ┊         P07 Streaming ───────┤
   │                                          │      ┊              │               │
   │                                          └──────┴──────────────┘               │
   │                                        (fault injector, reused by both)        │
   │                                                                                │
   └──────────────► P08 Recommender ──► P09 Simulator ──► P10 A/B platform ─────────┤
                          ▲                                                         │
                          ┊ (embeddings from)                                       │
                          ┊                                                         ▼
                      P01/P13                                            P15 Integrated System
 P11-I Tree-walk ──► P11-II Bytecode VM ┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┘
                          ┊
                          ┊ (GC + dispatch intuition feeds the kernel)
                          ▼
                      P12 Kernel

Edge table

Every edge, with the specific thing that crosses it. An edge with no concrete payload is not a dependency, it is a vibe, and it should not constrain your ordering.

Critical path

Because you run one project at a time, the schedule is 130 sequential weeks. But the longest chain of true dependencies is only 51 weeks:

P04 (9) → P05 (13) → P06 (8) → P07 (8) → P15 (13) = 51 weeks

Two other long chains:

P02 (7) → P03 (8) → P08 (6) → P09 (6) → P10 (4) → P15 (13) = 44 weeks
P01 (8) → P13-I (6) → P13-II (4) → P14 (7) → P15 (13) = 38 weeks

That 51-vs-130 gap is your reordering budget. It means the sequence below is one valid topological order out of very many, and if life makes a particular project impossible this quarter, you can almost always slide it without breaking anything. See Legal Reorderings.

Why This Order

Three ordering decisions are non-obvious and worth defending, because you will be tempted to undo all three.

1. The Transformer comes first, before the autodiff framework it logically sits on top of.

The logical order is backwards. You should build tensors, then autodiff, then a model. The roadmap does the reverse, deliberately:

• Motivation survives contact with difficulty better than logic does. Week 1 of a Transformer produces a model that generates text; week 1 of an autodiff framework produces a class that can add two arrays. You are 130 weeks from the end and the first eight weeks decide whether there is a week nine.
• Building autodiff after you have used loss.backward() a hundred times converts the project from "implement a thing described in a blog post" to "explain a thing you have already relied on". That is the reconstruction skill this whole track is for.
• P13's exit criterion is concrete precisely because P01 exists first: your autograd must reproduce your Transformer's gradients to 1e-5 against PyTorch. Without P01 there is nothing to check against.

2. The vector database comes before the LSM engine, even though it needs persistence.

You will build a naive append-only file with a full in-memory index in P03, measure its recovery time at 1M vectors, watch it take minutes, and then build the LSM engine in P04 knowing exactly which problem sparse indexes and Bloom filters solve. Doing P04 first would give you a better P03 and a worse education. This is the single clearest instance of the "naive design first" rule at the level of the roadmap itself, and it costs roughly 6 hours of rework in P03 — a price the plan pays on purpose.

3. The kernel comes at month 27, not month 3.

Kernel work is the most likely project to consume unbounded time and the least likely to produce a portfolio artifact anyone can evaluate. Putting it late means you arrive with two years of scoping discipline, an existing benchmark harness, and a working definition of "done". Putting it early means you spend four months on a bootloader and quit.

Legal Reorderings

Given the dependency table, these swaps are safe. Anything that preserves the edge directions is legal; these are the ones you are most likely to want.

Two things that are not legal:

• Starting P15 before at least six upstream projects have passed their exit criteria. P15 is an integration and a research question; integrating three half-built systems produces a demo, not a contribution.
• Running two Large projects concurrently. Ever. This is the guardrail that the entire program is structured around.

The Six Stages

Stage 1 — Foundations and Reconstruction · W1–W26 · 286 h · M1–M7

Theme: learn the loop on projects where correctness is cheap to check.

Everything in this stage is single-process, single-machine, and deterministic. That is the point: you are learning to write a naive design, predict its failure, instrument it, and report on it, and you should not be simultaneously learning to debug a network partition.

Stage exit: four technical reports; four repositories another engineer can clone and reproduce; the benchmark harness is now yours by muscle memory.

Stage 2 — Storage and Execution · W27–W54 · 308 h · M8–M15

Theme: durability, amplification, and the cost of a byte moved.

Stage exit: you can explain read/write/space amplification with your own numbers, and you have twice built a thing whose performance is dominated by data movement rather than instruction count.

Stage 3 — Distributed Systems · W55–W83 · 319 h · M15–M22

Theme: partial failure. The hardest stage; budgeted accordingly.

Stage exit: a linearizability checker that has found at least one real bug in your own code, and a written failure analysis of a split-brain you caused on purpose.

Stage 4 — Product and Experimentation Systems · W84–W99 · 176 h · M23–M26

Theme: systems whose correctness is statistical, not logical. This is where your existing domain knowledge is deepest, so the stage is short and the bar is high — you should be producing near-publishable work here.

Stage exit: a documented case where an offline metric improved and the simulated online metric did not, with an explanation of the mechanism.

Stage 5 — Low-Level and Hardware-Aware Systems · W100–W117 · 198 h · M27–M31

Theme: the layers your abstractions have been standing on for four stages.

Stage exit: you can answer "why is this kernel memory-bound" with a measurement rather than an opinion, at every level from L1 to HBM.

Stage 6 — Original Contribution · W118–W130 · 143 h · M31–M34

Stage exit: the paper is written, the repository is reproducible from a clean machine by someone who is not you, and the negative results are in the paper rather than in a drawer.

The Active-Week Schedule

 Stage 1  W1 ─────────────────────────────── W26
          [P01 ·8·][P02 ·7·][P11-I 5][P13-I 6]

 Stage 2  W27 ────────────────────────────── W54
          [P03 ·8·][P04 ··9··][P11-II 7][P13-II 4]

 Stage 3  W55 ────────────────────────────── W83
          [P05 ·····13·····][P06 ·8·][P07 ·8·]

 Stage 4  W84 ────────────── W99
          [P08 6][P09 6][P10 4]

 Stage 5  W100 ─────────────────── W117
          [P12 ····11····][P14 ·7·]

 Stage 6  W118 ───────────── W130
          [P15 ·····13·····]

Monthly Milestones (M1–M34)

Calendar months, each covering ~3.8 active weeks at 46 productive weeks/year. The milestone column is the thing that must exist by month end — not a topic covered, an artifact that exists on disk and runs.

Checkpoint Reviews

At each stage boundary — M7, M15, M22, M26, M31 — stop for one full session (3 hours) and do this, in writing, in notebook/stage-N-review.md:

1. Score every project of the stage on the scorecard. Twelve categories, 1–5, with the evidence for each score named. Score down when unsure.
2. Recompute the schedule. Actual hours spent vs. planned. If you are more than 15% over, do not "try harder" — cut scope from the next stage using the cut table, and record what you cut.
3. Answer the four questions: What did I build that I could not have built at the start of this stage? Which of my predictions were wrong, and was there a pattern in how they were wrong? What did I avoid because it was hard? What is the single weakest of my twelve scorecard categories, and what specific mechanic in the next stage will train it?
4. Re-read one report from the previous stage. You will find an unsupported claim. Fix it or retract it.
5. Update Research Directions with anything you saw that might be novel. One line each. Do not chase it now.

The review is not optional and it is not a formality. It is the only mechanism in the program that catches slow drift, and slow drift over 34 months is the failure mode that actually ends journeys like this one.

References

• Brooks, F. P. The Mythical Man-Month, anniversary ed. Addison-Wesley, 1995. Chapter 2 on scheduling estimation, and the observation that adding effort to a late project makes it later — which is why the response to slipping here is scope cuts, not hours.
• DeMarco, T., Lister, T. Peopleware: Productive Projects and Teams, 3rd ed. Addison-Wesley, 2013. On sustained-pace work and the cost of interruption; the source of the 46-productive-weeks assumption.
• Hofstadter, D. R. Gödel, Escher, Bach. Basic Books, 1979, p. 152. Hofstadter's Law: "It always takes longer than you expect, even when you take into account Hofstadter's Law." The 34-month figure already includes one application of this; assume it needs a second.
• Boehm, B. W. Software Engineering Economics. Prentice-Hall, 1981. The cone of uncertainty: early estimates are reliably off by 4× in either direction, which is why every stage boundary here recomputes rather than reasserts.
• Lampson, B. W. Hints for Computer System Design. SOSP '83. "Keep it simple", "do one thing well", and the observation that most system complexity is unpaid-for generality — the intellectual basis for the scope-boundary section on every project page.

Project Portfolio

The fifteen builds: size, effort, dependencies, scope tiers, and the one sentence that says why each exists.

Table of Contents

• Master Table
• Effort and Size Classification
• The Three Scope Tiers
• What Each Project Teaches That No Other Project Teaches
• Language Assignment
• The Deliverable Every Project Produces
• Reading This Track's Project Pages
• References

Master Table

Effort and Size Classification

The size rule

No project may grow beyond its class ceiling. A Medium project at week 11 is not a diligent Medium project, it is an undeclared Large one, and it is stealing weeks from a project later in the plan that you have not yet met and therefore cannot defend. The enforcement is mechanical: at the class ceiling you stop, ship whatever passes the exit criteria, and write the rest into the extension section of the report. See the two-week stall rule.

How the hour estimates were built

Each figure is the sum of its project's milestones, each estimated independently, then sanity-checked three ways:

1. Against the allocation. A project of H hours should show ~0.15H reading, ~0.45H implementation, ~0.20H experiments, ~0.10H writing, ~0.10H debugging. If a project's milestone list implies 0.8H of implementation, the estimate is wrong or the scope is.
2. Against known reference implementations. P01 is calibrated against nanoGPT (~300 lines of model code); P04 against the LevelDB paper's component list; P05 against the MIT 6.5840 lab sequence, which takes competent graduate students most of a semester at higher intensity than 11 h/week.
3. Against the 4× rule. Boehm's cone of uncertainty says early estimates are routinely off by 4× in either direction. These are not off by 4× because they are milestone-level rather than project-level, but assume ±30% on any individual project and expect the errors to partially cancel across fifteen.

Where these estimates are most likely wrong, stated in advance so you can check:

• P05 (143 h) is the most likely to overrun. Distributed debugging has no floor. The fault injector is scheduled first specifically to bound it.
• P12 (121 h) is the second. If you choose the bootable option and hit a toolchain problem, you can lose two weeks to something that teaches you nothing. Budget a hard "switch to the user-space option" decision at week 3 of the project.
• P08–P10 (176 h combined) are the most likely to underrun, because they are closest to your existing expertise. If you finish early, do not add scope — advance the schedule and bank the weeks against P12.

The Three Scope Tiers

Every project defines three versions. This is the single most important structural device in the plan, because it converts "when am I done?" from a judgement call into a lookup.

Minimum viable implementation (MVI). The smallest artifact that still exhibits the mechanism being studied. Must be genuinely educational on its own: an LSM engine without compaction is an MVI (it still teaches WAL, memtable, SSTable, recovery); an LSM engine that keeps everything in RAM is not, because the mechanism under study is precisely what happens when it does not.

Standard implementation. MVI plus the features that make the project's core experiments possible. This is the target. Exit criteria are written against this tier.

Optional research extension. The interesting thing you will want to do. It is locked until the standard tier passes its exit criteria, and it may be skipped entirely without affecting any later project. Nothing downstream ever depends on an extension — that is what makes it optional in a way that survives contact with a busy quarter.

Worked example — Project 4

If week 9 arrives and leveled compaction is half-finished, you ship size-tiered only, you write "leveled compaction not implemented; the read-amplification comparison is therefore against published figures rather than my own" in the report, and you move on. That is a completed project with a stated limitation. It is worth far more than a twelfth week.

What Each Project Teaches That No Other Project Teaches

If you ever need to cut, cut by asking which unique lesson you are willing to lose.

Language Assignment

Rationale and the full argument in Languages. The summary:

Four languages across 34 months, each assigned once and not revisited on a whim. You already know Python and Go. Rust is the one real learning cost, and it is paid across P11-I (Small, W16–20) where the project is easy enough that the language is the only hard part — that scheduling is deliberate.

The Deliverable Every Project Produces

Not negotiable, and identical across all fifteen:

1. A repository that a stranger can clone and run. One command to build, one to test, one to reproduce the headline benchmark. If it needs a paragraph of setup prose, it is not reproducible.
2. A technical report (REPORT.md), 1,500–4,000 words, following templates/report.md, containing a section titled "What I Expected And Did Not Get". That section is scored and may not be empty.
3. A research-notebook entry per experiment, following templates/notebook.md.
4. A benchmark artifact: the raw sample data (not just summaries), the script that produced it, and the environment block.
5. A scorecard self-assessment, twelve categories, with evidence named per score.

The first three take about 10 hours of the project's budget combined. That is the 10% writing allocation, and it is the part that converts a build into a portfolio.

Reading This Track's Project Pages

Every project page has the same eighteen sections, in the same order, so you can jump straight to the one you need:

Why This Project Matters      Concepts To Study          Expected Difficulties
Prerequisites                 Primary-Source Readings    Scope Boundaries
Duration and Size             Experiments                Deliverables
Central Technical Questions   Benchmarks and Metrics     Exit Criteria
Architecture                  Correctness Tests          Extension Ideas
Implementation Milestones     Failure Tests              Connections

Plus, at the top of each, the fourteen-step loop instantiated for that project — what "naive design" and "predicted failure point" concretely mean for this build. Read that section, then close the page and write your own naive design before reading the architecture section. The architecture section is deliberately placed after the loop for that reason.

References

• Boehm, B. W. Software Engineering Economics. Prentice-Hall, 1981. The cone of uncertainty underlying the ±30% claim.
• Brooks, F. P. No Silver Bullet — Essence and Accident in Software Engineering. IEEE Computer 20(4), 1987. The essential/accidental distinction is what the scope tiers are trying to separate: MVI is essence, everything else is negotiable.
• Athanassoulis, M. et al. Designing Access Methods: The RUM Conjecture. EDBT 2016. The read/update/memory trilemma referenced in P04's unique lesson.
• Ousterhout, J. A Philosophy of Software Design, 2nd ed. Yaknyam Press, 2018. Deep modules and the argument that interface simplicity is worth implementation complexity — the standard against which each project's API is judged.
• Karpathy, A. nanoGPT. github.com/karpathy/nanoGPT, 2022. The calibration reference for P01's size estimate. Read the code after you write yours, not before.
• MIT 6.5840 (formerly 6.824) Distributed Systems lab sequence. The calibration reference for P05.

Audit of the Fifteen

You specified the project list. I designed to it and never asked whether it was the right list — which is a question upstream of every other decision in the track.

This page is that audit: what the fifteen cover, what they redundantly cover, what they do not cover, and which of the gaps actually matter for the stated goal.

Conclusion first: the list is good, with one real redundancy and three real gaps, of which only one is worth acting on now.

Table of Contents

• The Coverage Map
• What Is Covered Twice
• What Is Not Covered At All
• The Three Gaps That Matter
• Against the Stated Goal
• What I Would Change
• What I Would Not Change
• References

The Coverage Map

Thirteen fundamental mechanisms in systems work, against the projects that build them. ● = built by hand. ○ = touched but not built.

Every row has at least one ●. Measurement is universal, which is the design intent — it is the one skill the whole track exists to build, and it is trained fifteen times.

Best-covered: data movement (7 projects), durability (4), approximation (6). Those are the right three to over-cover for someone building retrieval and storage systems.

Thinnest: protocol/wire format (1 solid), scheduling (2), compilation (2).

What Is Covered Twice

Redundancy is not automatically waste — repetition in different contexts is how a lesson generalises. But two cases are worth naming.

P06 and P07 share more than they should

Both build: a coordinator, a worker pool, task/operator scheduling, a partitioned shuffle or network partitioner, failure detection and retry, and checkpoint/recovery. P07's page even says the scheduler "generalises" from P06.

The honest reading: ~40% of the two projects overlaps, and the distinct 60% is where each project's value lives. 176 hours for 60% novelty is the weakest hours-per-lesson ratio in the portfolio.

The existing scope cut — build P07 as an extension of P06's runtime, saving 2 weeks — addresses this partially. The stronger version is to make it the default rather than a fallback: build one distributed execution runtime, then run it in two modes. You would save ~4 weeks and lose nothing but the experience of building a second coordinator, which you will have just built.

P03 and P04 both build persistence

P03 builds a naive append-only store; P04 builds a proper LSM. This is deliberate redundancy and it is correct — it is the roadmap's most explicit application of "naive design first", and it costs about six hours of rework on purpose. P03's measured recovery time is what makes P04 feel necessary rather than academic.

Not a defect. Leave it.

What Is Not Covered At All

Nine mechanisms a systems engineer might reasonably be expected to have built, absent from the list.

The Three Gaps That Matter

Ranked by how much they weaken the stated goal.

1. Concurrency primitives from scratch — the cheapest to close

What is missing. You use atomics and mutexes across P05–P07 and P12, and measure them in numbers §4. You never build one. Memory ordering, ABA, and safe reclamation stay theoretical.

Why it matters here. P12 is single-core by design, so the one project that would naturally force this is scoped to avoid it. That is a defensible scoping decision that leaves a hole.

Cost to close: 2–3 weeks. A Small project: a lock-free MPSC queue, a ticket lock and an MCS lock, benchmarked under contention from 1 to N threads, with the crossover found.

Where it fits. As P12's extension, which already names "synchronisation shoot-out" — promote it from optional to standard. Or as a standalone Small project between P12 and P14.

My recommendation: take P12's extension as standard. It is the highest ratio of lesson to weeks on this page.

2. Networking below RPC

What is missing. P05 assumes a network that drops, delays, duplicates and reorders — correctly, and that is the right abstraction for consensus. But you never build the layer that produces those behaviours: no congestion control, no retransmission, no flow control, no head-of-line blocking.

Why it matters. A large fraction of real distributed-systems debugging is network-layer behaviour leaking through the abstraction — Nagle interacting with delayed ACK, TCP incast collapse, a connection pool exhausting under retry storms. Simulating faults at the message level teaches you what to handle; it does not teach you why they occur.

Cost to close: 4–6 weeks for a minimal reliable protocol over UDP with sliding window, retransmission and one congestion-control algorithm.

Verdict: a real gap, and I would not add it. Six weeks against 130 for a mechanism that is one layer below where your stated goals live. Note it as a limitation and consider it post-journey. If you want a cheap partial: in P05, add a fault-injection mode that models bandwidth and queueing rather than only drop and delay — that surfaces congestion-shaped failures for about two days of work.

3. Code generation

What is missing. P11 goes lexer → parser → AST → bytecode → VM → GC, and stops. SSA, register allocation, instruction selection and native emission are absent, so "how does a compiler produce fast machine code" remains a black box — which is a notable hole next to a journey that measures machine code constantly.

Why it is deliberate. A JIT is a project in itself, P11 is already Large at 132 hours, and the dispatch lesson (bytecode's advantage is cheaper operations, not fewer) is fully delivered without codegen.

Cost to close: 6–10 weeks.

Verdict: correctly deferred. It is the single best post-journey project on this page, and it composes: P11 gives the front end, P14 gives the machine model, and a tracing JIT for your own language is a genuinely impressive artifact.

Against the Stated Goal

You named MapReduce, Spanner, TensorFlow, TPUs, programming languages, OS kernels, databases, distributed systems, vector search, recommenders, and Transformers.

Ten of eleven are covered at high or good fidelity. The weakest is Spanner, and the missing pieces there (bounded clocks, distributed transactions) are precisely the parts that need infrastructure you cannot have.

The list is well matched to the goal. That is worth saying plainly, because the rest of this page is criticism and the headline finding is that the portfolio is sound.

What I Would Change

Three changes, in order of confidence.

1. Merge P06 and P07 into one runtime, two modes. Saves ~4 weeks, loses ~nothing. Build one coordinator, worker pool and partitioner; run it in batch mode (with speculative execution and the straggler study) and in streaming mode (with watermarks, windowing and checkpointing). The distinct 60% of each project is fully preserved and you stop building the same scheduler twice. Confidence: high.

2. Promote P12's synchronisation shoot-out from extension to standard. Costs ~2 weeks, closes the cheapest real gap, and produces directly transferable knowledge — every concurrent system you tune afterwards benefits. Confidence: high.

3. Add bandwidth and queueing to P05's fault injector. Two days. Surfaces congestion-shaped failures without a six-week networking project. Confidence: medium.

Net: −2 weeks and one gap closed. Both of the first two are consistent with the existing scope-cut machinery rather than requiring a replan.

What I Would Not Change

• The fifteen-project scope. It is ambitious and it is coherent. Cutting further would produce breadth without the depth you asked for.
• P03's deliberate redundancy with P04. The rework is the lesson.
• P12's single-core scoping. SMP multiplies the difficulty of every subsequent bug; the extension in change 2 gets the concurrency lesson without it.
• The absence of a query layer. Storage engines and query processing are two journeys. Yours is the storage one.
• P09 and P10 as separate projects, despite the existing cut that merges them. The A/B platform's statistical content is genuinely distinct from the simulator's modelling content, and it is the part most directly useful in your job next month.

References

• Brooks, F. P. No Silver Bullet — Essence and Accident in Software Engineering. IEEE Computer 20(4), 1987. The essence/accident distinction underlying the coverage map: the mechanisms are the essence; the fifteen projects are one accidental arrangement of them.
• Lampson, B. W. Hints for Computer System Design. SOSP 1983. "Do one thing well" — the argument for merging P06 and P07 rather than building two partial runtimes.
• Ousterhout, J. A Philosophy of Software Design, 2nd ed. Yaknyam Press, 2018. On deep modules, and on the cost of building the same abstraction twice.
• Mellor-Crummey, J. M., Scott, M. L. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM TOCS 9(1), 1991. MCS locks — the reference for gap 1.
• Herlihy, M., Shavit, N. The Art of Multiprocessor Programming, 2nd ed. Morgan Kaufmann, 2020. The text for the synchronisation shoot-out.
• Alizadeh, M. et al. Data Center TCP (DCTCP). SIGCOMM 2010. What gap 2 would teach, and why incast is the canonical example.
• Aycock, J. A Brief History of Just-In-Time. ACM Computing Surveys 35(2), 2003. The entry point for gap 3 as a post-journey project.

P01 — Transformer From Scratch

Run it first. There is a companion page that builds this project's machinery as numbered, independently runnable blocks and then assembles them into one measured system: P01 hands-on — block by block (handson/h*.py). Every number on it was produced by running the code. Read it alongside the milestones below.

Medium · 88 hours · Weeks 1–8 · Stage 1 · Python

Table of Contents

• The Loop, Instantiated
• Why This Project Matters
• Prerequisites
• Duration and Size
• Central Technical Questions
• Architecture
• Showcase — Do This Before You Start
• Implementation Milestones
• Concepts To Study
• Primary-Source Readings
• Experiments
• Benchmarks and Metrics
• Correctness Tests
• Failure Tests
• Expected Difficulties
• Scope Boundaries
• Deliverables
• Exit Criteria
• Extension Ideas
• Connections
• References

The Loop, Instantiated

Read this section, then close the page and write your naive design before scrolling to Architecture.

Why This Project Matters

Two reasons, and the second is the real one.

The stated reason: the Transformer is the most consequential architecture of the last decade and you use it daily through APIs. Building one converts a black box into a set of decisions you can defend.

The real reason: the Transformer is a pile of arbitrary-looking choices. Why scale by \(1/\sqrt{d_k}\)? Why 4× expansion in the feed-forward layer? Why LayerNorm before the sublayer instead of after, when the original paper did the opposite? Why multiple heads instead of one big one? None of these follow from first principles. Each is defensible only by measurement, and almost nobody who uses Transformers has done those measurements.

This project is where you learn that an architecture is an empirical artifact, and that the way to understand any system full of arbitrary constants is to vary them and watch what happens. That habit transfers to every other project here. The Transformer is a convenient place to acquire it because the feedback loop is minutes, not hours, and correctness is checkable against finite differences.

It is also first because it is motivating. Week 8 of this project ends with a model that writes text. Week 8 of an autodiff framework ends with a class that adds arrays correctly. You are 130 weeks from the end and the first two months decide whether there is a month three.

Prerequisites

• Linear algebra: matrix multiplication, transpose, the fact that \(A B\) composes linear maps. You do not need eigenvalues here.
• The chain rule. You will not implement backprop in this project (that is P13), but you must be able to explain why a residual connection helps gradient flow.
• Python and numpy. PyTorch tensors + autograd are permitted as a tensor library only — see Scope Boundaries.
• From math.md: §Linear Algebra (2 h), §Softmax and Cross-Entropy (1 h). Nothing else. Do not read the optimization section yet.

Duration and Size

Medium, 88 hours, 8 weeks at 11 h/week.

Central Technical Questions

1. What does attention compute that a fixed-window MLP cannot? Answer in terms of the number of parameters required to express a content-dependent, position-invariant lookup.
2. Why divide by \(\sqrt{d_k}\)? Derive it. What happens to the softmax gradient if you do not?
3. At what context length does attention stop being a rounding error and start being the bottleneck? For your specific \(d_{model}\). Derive first, then measure.
4. What does a positional encoding have to provide, minimally? RoPE, sinusoidal and learned embeddings solve the same problem three ways — what is the problem, stated without reference to any of them?
5. Why did pre-norm replace post-norm? And at what depth does the difference start to matter?
6. What is the memory cost of inference, and why is it dominated by something other than the weights beyond a certain sequence length?

Architecture

Do not read this until you have written your naive design.

tokens ─► [Tokenizer] ─► ids ─► [Embedding] ─┬─► + positional ─► [Block] × L ─► [Norm] ─► [Unembed] ─► logits
                                             │                      │
                                             │                      ├─ x + Attn(Norm(x))     ← pre-norm residual
                                             │                      └─ x + FFN(Norm(x))
                                             │
                                        (RoPE instead applies rotation inside Attn, to q and k only)

The attention mechanism, derived

You have a sequence of \(T\) vectors \(x_1..x_T\), each in \(\mathbb{R}^{d}\). You want each position to gather information from earlier positions, with the choice of which earlier positions determined by content rather than by fixed offset.

Project each \(x_i\) three ways: a query \(q_i = W_q x_i\) (what am I looking for), a key \(k_i = W_k x_i\) (what do I offer), and a value \(v_i = W_v x_i\) (what I will hand over). Score every pair by dot product, normalise into weights, and take the weighted sum:

\[ \text{Attn}(Q,K,V) = \text{softmax}\!\left(\frac{QK^\top}{\sqrt{d_k}} + M\right)V \]

where \(M_{ij} = -\infty\) for \(j > i\) — the causal mask, which must be applied before the softmax so that masked positions receive exactly zero weight rather than a small one.

Why \(\sqrt{d_k}\). Take \(q, k\) with i.i.d. components of mean 0 and variance

1. Then \(q \cdot k = \sum_{i=1}^{d_k} q_i k_i\) is a sum of \(d_k\) independent mean-zero unit-variance terms, so \(\mathrm{Var}(q\cdot k) = d_k\) and the typical magnitude of a score is \(\sqrt{d_k}\). At \(d_k = 64\) scores are typically ±8, and the gap between the largest and second-largest is often several units. Feed that to a softmax and you get a near-one-hot distribution whose gradient is nearly zero everywhere — the softmax saturates and the layer stops learning. Dividing by \(\sqrt{d_k}\) restores unit variance and keeps the softmax in its responsive region. This is not a heuristic; it is a variance calculation you should be able to do at a whiteboard.

Why multiple heads. One head produces one attention distribution per position: it can attend to one thing. Splitting \(d\) into \(H\) heads of size \(d/H\) gives \(H\) independent distributions at the same total parameter and FLOP cost (the concatenation-then-projection makes the arithmetic identical). You are buying representational diversity for free. The cost is that each head sees a \(d/H\) dimensional subspace, so there is a floor below which heads become too small to be useful — one of your experiments.

Cost model, derived before you measure

Let \(B\) = batch, \(T\) = sequence length, \(H\) = heads, \(d_h\) = head dim, \(d = H d_h\). Per layer, forward pass, counting 2 FLOPs per multiply-accumulate:

Everyone "knows" attention is quadratic. Almost nobody knows where the crossover is. Computed for \(B{=}1, H{=}12, d_h{=}64\) (so \(d{=}768\), GPT-2 small shape):

Two things fall out that are worth more than the table itself:

1. At GPT-2's original context of 1024, attention is 18% of the compute. The quadratic term does not dominate until ~4096. Every "attention is the bottleneck" claim is context-length-dependent and most of them are wrong for the context they are said about.
2. Memory hits the wall long before FLOPs do. The materialised score matrix is 3.2 GB at T=8192 for a single batch element in fp32. This is the entire reason FlashAttention exists: it never materialises that matrix, computing softmax in tiles with an online-normalisation trick. The compute is unchanged; the memory traffic is what is optimised.

Reproduce this table for your own \(d_{model}\) as milestone 6. Predict the crossover before you compute it.

RoPE, and why it is different in kind

Learned and sinusoidal encodings add a position-dependent vector to the token embedding. RoPE rotates the query and key vectors by an angle proportional to position, in \(d/2\) independent 2-D planes:

\[ \theta_i = \frac{m}{\text{base}^{2i/d}}, \qquad \begin{pmatrix} x^{\prime}_{2i} \\ x^{\prime}_{2i+1} \end{pmatrix} = \begin{pmatrix} \cos\theta_i & -\sin\theta_i \\ \sin\theta_i & \cos\theta_i \end{pmatrix} \begin{pmatrix} x_{2i} \\ x_{2i+1} \end{pmatrix} \]

The property that makes it work: because a rotation by \(m\) followed by the inverse of a rotation by \(n\) is a rotation by \(m-n\), the dot product of a rotated query at position \(m\) with a rotated key at position \(n\) depends only on \(m-n\). Attention becomes relative-position-aware without any explicit relative-position term.

Verify this numerically before you trust it — measured with a 64-dimensional random vector pair:

   m    n   m-n            dot
   5    3     2   -8.115791933
 105  103     2   -8.115791933
   7    5     2   -8.115791933
1000  998     2   -8.115791933
   5    4     1   -8.519139825
  50   49     1   -8.519139825

Identical to nine decimal places across a 200× range of absolute positions. And because rotations are orthogonal, norms are preserved exactly: \(|q| = 7.315343549\), \(|\text{RoPE}(q,17)| = 7.315343549\). Write this test before you write the implementation. It catches the two overwhelmingly common RoPE bugs — pairing dimensions as \((i, i+d/2)\) versus \((2i, 2i+1)\) without adjusting the frequency indexing, and applying the rotation to values as well as to queries and keys.

Showcase — Do This Before You Start

W1 · walkthroughs/w1_attention.py · ~45 minutes

A working miniature of this project: the leak test, what the \(1/\sqrt{d_k}\) scale buys measured as attention entropy, and the sequence length where the quadratic term actually starts to matter.

cd walkthroughs && python3 w1_attention.py

It is 80-ish lines and it surfaces this project's central surprise in an evening rather than in week six. Run it before committing the weeks.

Implementation Milestones

Concepts To Study

Limited to what the milestones need. Anything not on this list is not yet.

• Tokenization: byte-level BPE, the merge algorithm, why byte-level avoids OOV entirely, vocabulary size vs sequence length as a direct trade
• Embeddings: as a lookup table that is also a linear layer; weight tying between embedding and unembedding and what it saves
• Softmax: numerical stability via max-subtraction, the Jacobian, saturation
• Cross-entropy: as negative log-likelihood, and why loss in nats converts to perplexity by \(e^{\text{loss}}\)
• LayerNorm vs RMSNorm: what each normalises, and why RMSNorm dropping the mean subtraction costs almost nothing
• Residual connections: as an identity path for gradients; why the residual stream is better thought of as a shared bus than as a shortcut
• Pre-norm vs post-norm: where the norm sits relative to the residual add, and the effect on gradient magnitude at depth
• AdamW: first and second moment estimates, bias correction, why decoupled weight decay differs from L2
• Learning-rate schedules: warmup as a remedy for early-training instability in adaptive optimizers
• KV caching: what is recomputed without it, and the memory it costs
• Sampling: temperature as logit scaling, top-k and nucleus as truncation strategies

Primary-Source Readings

Total budget: 13 hours. Read section 3 of Vaswani before milestone 3, RoFormer before milestone 9, and nothing else until the milestone that needs it.

Deliberately not on this list: scaling laws, MoE, RLHF, quantization, distributed training. See Not Yet.

Experiments

Every row: fixed seed, fixed data, fixed token budget, one variable. Record the prediction before the run.

E10 is not optional and it is not a formality. A model that cannot overfit 200 tokens has a bug — usually a mask applied after the softmax, a detached gradient, or a data loader that reshuffles the target. Run it at milestone 5 and again any time anything looks strange. It is the cheapest bug detector in the project.

E6 is the best hypothesis in this project. Pre-norm and post-norm perform similarly at depth 2 and diverge sharply somewhere deeper. Predicting where — and explaining it via gradient magnitude at initialisation — is a genuine result you derived.

Benchmarks and Metrics

Report every latency as p50/p95/p99 with a bootstrap CI on the median, using tools/bench.py. A mean latency in this project's report is a scorecard deduction.

Correctness Tests

These are properties, not examples. Property tests catch the bugs example tests miss.

1. Hand-computed forward pass. 3 tokens, \(d{=}4\), one head, weights set by hand. Your attention weights match your arithmetic to 1e-6. Do this on paper first.
2. Causal mask leak test. Run the model on a sequence. Perturb token \(t{+}1\). Assert the logits at positions \(\le t\) are bit-identical. This catches masking after softmax, off-by-one in the mask, and any accidental bidirectionality.
3. Attention rows sum to 1. For every head, every position, every batch element, \(|\sum_j a_{ij} - 1| < 10^{-5}\).
4. Gradient check. Finite differences against autograd on a tiny model: \(|\nabla_{\text{analytic}} - \nabla_{\text{numeric}}| / (|\nabla| + \epsilon) < 10^{-4}\) for every parameter tensor. (In P13 you will implement the analytic side yourself and run this same test against PyTorch.)
5. RoPE relative-position invariance. As measured above: for all \((m,n)\) with the same \(m-n\), the rotated dot product is equal to 1e-6.
6. RoPE norm preservation. \(||\text{RoPE}(x,m)|| = ||x||\) to 1e-6, all \(m\).
7. Tokenizer round-trip. decode(encode(s)) == s for a corpus including emoji, CJK, and lone surrogate byte sequences.
8. Softmax stability. Logits of \(10^4\) produce no NaN.
9. Shape and dtype invariants on every tensor crossing a module boundary.
10. Determinism. Same seed → bit-identical loss curve. If not, find the source before running any experiment; nondeterminism silently invalidates every ablation.

Failure Tests

Deliberately break it and confirm it breaks the way you predict.

The shuffled-target test deserves emphasis: a model trained on random labels should converge to exactly \(\ln(V)\) nats. If it goes below, you have leakage. If it goes far above, you have an optimizer problem. It is a two-line experiment that calibrates your entire loss intuition.

Expected Difficulties

Named in advance so that hitting one is a checkpoint, not a crisis.

1. Shape bugs will consume more time than concepts. (B,T,H,d_h) vs (B,H,T,d_h) transposes are the single biggest time sink. Mitigation: annotate every tensor's shape in a comment at creation, and assert shapes at every module boundary. This feels excessive for about two days and then saves a week.
2. A subtly wrong mask trains fine and scores impossibly well. Mitigation: test 2 above, written before the mask.
3. You will want to add features instead of running experiments. Adding grouped-query attention is more fun than running a 5-point head-count sweep. The sweep is the project.
4. CPU training is slow enough to discourage sweeps. Mitigation: size the model so one training run is under 10 minutes. Every experiment here is about relative comparison; absolute quality is irrelevant.
5. RoPE has two incompatible conventions in the wild (interleaved pairs vs split halves). Both are correct if applied consistently; mixing them within one model produces a model that trains but extrapolates badly. Test 5 catches it.
6. The bigram baseline is better than you expect and beating it by a little feels like failure. It is not — write down the bigram loss and the entropy floor first so you know what the achievable range even is.

Scope Boundaries

In scope: everything in the milestone list, on CPU, at a scale where a training run takes under 10 minutes.

Explicitly out of scope — if you find yourself doing one of these, stop:

• Multi-GPU or distributed training of any kind
• Training on a large corpus, or chasing an absolute quality number
• Implementing your own autograd — that is P13, and doing it here means doing two Large projects at once
• Fine-tuning, instruction tuning, RLHF, LoRA
• Serving infrastructure, batching servers, or an API
• Model architectures other than a decoder-only Transformer
• Writing CUDA kernels — that is P14

The permitted-library line. PyTorch is allowed for: tensor storage, elementwise ops, matmul, autograd, and the optimizer. PyTorch is forbidden for: nn.Transformer, nn.TransformerEncoderLayer, nn.MultiheadAttention, F.scaled_dot_product_attention, and any positional-encoding utility. The mechanism under study is attention; you may not import it. See AI Policy Rule 7.

Deliverables

1. transformer/ repository — one command to train, one to sample, one to reproduce every experiment
2. REPORT.md, 2,000–3,000 words, with the E4/E6 ablation tables and a section titled "What I Expected And Did Not Get"
3. notebook/ entries for E4, E6, and E11 at minimum
4. cost_model.py reproducing the FLOP/memory table for arbitrary configs
5. A generated-text sample at three temperatures, with the tokenizer's compression ratio stated
6. Raw benchmark JSON for every experiment, not just the summary tables

Exit Criteria

All eight, no exceptions.

• Model overfits a 200-token corpus to val loss < 0.1 (E10)
• Beats the bigram baseline on held-out val loss by a stated, measured margin
• All ten correctness tests pass, including the causal-leak and RoPE invariance tests
• E4 complete: all four positional encodings including the none control, with a table
• E6 complete: pre-norm vs post-norm across four depths, with the divergence depth identified and an explanation offered
• E11/E12 complete: KV-cache latency is flat in generated length, and derived cache memory matches measured within 5%
• At least one hypothesis tested with a stated falsifier, and the outcome recorded whichever way it went
• REPORT.md written, including at least one result that contradicted your prediction

Extension Ideas

Locked until every box above is ticked.

• Grouped-query attention: share K/V across head groups. Measure the KV-cache reduction and the quality cost. Directly relevant to your day job's serving costs.
• Tiled attention (FlashAttention-style): implement online softmax normalisation and never materialise the score matrix. Measure peak memory vs T against the table above. This is the best bridge to P14.
• Sliding-window attention with a long-context eval, measuring the quality/compute frontier.
• Speculative decoding with a small draft model. Measure acceptance rate and end-to-end speedup; note that acceptance rate is the interesting quantity.
• RoPE base sweep (\(\text{base} \in \{10^3, 10^4, 10^5\}\)) and its effect on length extrapolation — a small, real, publishable-adjacent experiment.

Connections

Backward: none. This is where the journey starts.

Forward:

• → P13 (Autodiff): the exit criterion for P13 Phase I is reproducing this model's gradients to 1e-5. Keep the model code stable and tagged so P13 has a fixed target.
• → P14 (Hardware-aware): the FLOP/memory table here is the input to P14's roofline analysis. Your inference latency measurements become the "before" number.
• → P08 (Recommender): you will need embeddings, and having built the thing that produces them changes how you reason about their geometry.
• → P02 (ANN): the embeddings from this model are a legitimate test dataset for your index — and unlike random vectors, they have realistic relative contrast.
• → P15: dynamic embedding generation is one of the candidate research questions, and it depends on your being able to reason about the cost of a forward pass.

References

• Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., Polosukhin, I. Attention Is All You Need. NeurIPS 2017.
• Su, J., Lu, Y., Pan, S., Murtadha, A., Wen, B., Liu, Y. RoFormer: Enhanced Transformer with Rotary Position Embedding. arXiv:2104.09864, 2021.
• Xiong, R. et al. On Layer Normalization in the Transformer Architecture. ICML 2020.
• Dao, T., Fu, D. Y., Ermon, S., Rudra, A., Ré, C. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. NeurIPS 2022.
• Sennrich, R., Haddow, B., Birch, A. Neural Machine Translation of Rare Words with Subword Units. ACL 2016.
• Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I. Language Models are Unsupervised Multitask Learners. OpenAI technical report, 2019.
• Loshchilov, I., Hutter, F. Decoupled Weight Decay Regularization. ICLR 2019.
• Zhang, B., Sennrich, R. Root Mean Square Layer Normalization. NeurIPS 2019.
• Ba, J. L., Kiros, J. R., Hinton, G. E. Layer Normalization. arXiv:1607.06450, 2016.
• Shazeer, N. Fast Transformer Decoding: One Write-Head is All You Need. arXiv:1911.02150, 2019. Multi-query attention; the ancestor of GQA.
• Elhage, N. et al. A Mathematical Framework for Transformer Circuits. Anthropic, 2021. The residual-stream view referenced under Concepts.
• Karpathy, A. nanoGPT and Let's build GPT: from scratch, in code, spelled out. 2022–2023. Read after your milestone 7, as a check on your choices rather than a source for them.

P01 hands-on — Transformer, block by block

Attention from a dot product, then a language model that trains.

Source: handson/h01_transformer.py --- run it with python3 handson/h01_transformer.py
Full project spec: P01 — Transformer From Scratch

Every line of this page runs. The file builds a decoder-only transformer out of nine independent pieces, each of which proves one mechanism on its own before anything is stacked, and then trains the assembled model on a real corpus until the loss falls to 0.11 nats.

The order is deliberate. Attention is introduced as a weighted average whose weights are computed from the data, which is all it is, and only then do the scaling factor, the causal mask, and multiple heads get added --- each one motivated by a failure you can see in the numbers of the block before it. The same discipline applies to the training loop: the overfit test in the assembly exists because a language model that cannot memorise sixty tokens has a bug that no amount of hyperparameter tuning will fix.

Read the outputs, not just the code. Block 3 shows what the sqrt(d_k) denominator is actually protecting you from, and it is not obvious from the formula.

Contents

• Block 1 — Tokenizer
• Block 2 — Batching
• Block 3 — Softmax + cross-entropy
• Block 4 — One attention head
• Block 5 — The leak test
• Block 6 — Multi-head
• Block 7 — The pre-norm block
• Block 8 — The model
• Block 9 — The same attention, in torch
• The assembly
• The design space
• Latency, bandwidth and the memory hierarchy
• Hardware: CPU, GPU, TPU
• Advanced algorithms and alternatives
• How this connects to the rest of the track
• Failure modes at scale
• Primary sources
• Running it
• What to do with this

How to read this page

Each block below is a self-contained lego piece: it builds one mechanism, proves it works on its own, and returns what the next block needs. The code is the real source, sliced out of the script. The output underneath it is the real output, captured by running that script --- not transcribed, not idealised. Where a measurement contradicted what I expected, the contradiction is in the output and the prose says so.

The assembly at the end wires every block into one working thing and measures it.

Block 1 — Tokenizer

Teaches: a vocabulary is a bijection, and it must round-trip

The problem. Before a model can learn anything, text has to become integers, and the mapping has to be exactly invertible. A tokenizer that does not round-trip introduces a silent error floor that no amount of training can cross, and it will look like a modelling problem.

@block(1, "Tokenizer", "a vocabulary is a bijection, and it must round-trip")
def b1(s, show):
    class CharTokenizer:
        def __init__(self, text):
            self.vocab = sorted(set(text))
            self.stoi = {c: i for i, c in enumerate(self.vocab)}
            self.itos = {i: c for c, i in self.stoi.items()}
        @property
        def size(self): return len(self.vocab)
        def encode(self, t): return [self.stoi[c] for c in t]
        def decode(self, ids): return "".join(self.itos[i] for i in ids)

    tok = CharTokenizer(CORPUS)
    assert tok.decode(tok.encode(CORPUS)) == CORPUS, "round-trip failed"
    if show:
        print(f"  vocab size {tok.size}: {''.join(tok.vocab)!r}")
        print(f"  round-trip on {len(CORPUS)} chars: OK")
        print(f"  compression: 1.00 bytes/token (the baseline BPE must beat)")
    return {"tok": tok, "data": np.array(tok.encode(CORPUS), dtype=np.int64)}


# ─────────────────────────────────────────────────────────── block 2

Reading the implementation

Character-level tokenisation is chosen here because it is a bijection by construction — every character maps to exactly one id and back — which removes an entire class of bug from the rest of the project. The assertion that decode(encode(text)) == text is not ceremony; it is the property everything downstream assumes.

The cost is sequence length. Character-level means ~4--5× more tokens than subword for English, and since attention is \(O(T^2)\) in memory that is a 16--25× increase in the score matrix. This is the trade the tokenizer makes and the reason production models use BPE.

What the numbers say

Output:

  vocab size 28: ' .abcdefghijklmnopqrstuvwxyz'
  round-trip on 3720 chars: OK
  compression: 1.00 bytes/token (the baseline BPE must beat)

Beyond the toy

Byte-pair encoding builds a vocabulary by repeatedly merging the most frequent adjacent pair, starting from bytes. The consequences are worth knowing precisely because they leak into model behaviour:

• Byte-level BPE (GPT-2 onward) never has an out-of-vocabulary token, because the base alphabet is all 256 bytes. That is why these models handle emoji, arbitrary Unicode, and binary garbage without a special case.
• Tokenisation is not language-neutral. The same sentence costs ~1.5--3× more tokens in Hindi or Thai than in English with a typical English-dominant vocabulary, which is a direct cost and context-length penalty for those users.
• Digit and whitespace handling explains a startling amount of model behaviour. If "1234" tokenises as "12"+"34", arithmetic becomes positional string manipulation, which is why many models are erratic at multi-digit arithmetic and why later models force digit-by-digit splits.
• The SolidGoldMagikarp class of bug: tokens present in the tokenizer's training corpus but effectively absent from the model's produce untrained embeddings and bizarre generations. A vocabulary is a joint artefact of the tokenizer and the training data, and a mismatch between them is a real failure mode.

Block 2 — Batching

Teaches: a language model predicts the NEXT token: y is x shifted by one

The problem. "Predict the next token" has to become a tensor operation. The shift-by-one construction is three lines and is the entire supervision signal — and an off-by-one here produces a model that either cheats or learns nothing.

@block(2, "Batching", "a language model predicts the NEXT token: y is x shifted by one")
def b2(s, show):
    def get_batch(data, B, T, rng):
        ix = rng.integers(0, len(data) - T - 1, size=B)
        x = np.stack([data[i:i + T] for i in ix])
        y = np.stack([data[i + 1:i + T + 1] for i in ix])
        return x, y
    x, y = get_batch(s["data"], 4, 8, rng)
    assert (x[:, 1:] == y[:, :-1]).all(), "y must be x shifted by one"
    if show:
        print(f"  x {x.shape}  y {y.shape}")
        print(f"  x[0] = {s['tok'].decode(x[0])!r}")
        print(f"  y[0] = {s['tok'].decode(y[0])!r}   <- shifted by one")
    return {"get_batch": get_batch}


# ─────────────────────────────────────────────────────────── block 3

Reading the implementation

y is x shifted left by one, so position \(t\) in the input predicts position \(t+1\). Every position in the sequence is a training example, which is what makes language modelling so sample-efficient: a batch of 16 sequences of 64 tokens yields 1024 supervised predictions, not 16.

This is also where the causal mask becomes non-negotiable. Because the targets are inside the same sequence as the inputs, an attention pattern that can see forward gives the model the answer. Block 5 exists specifically to test that it cannot.

What the numbers say

Output:

  x (4, 8)  y (4, 8)
  x[0] = 'uns . th'
  y[0] = 'ns . the'   <- shifted by one

Beyond the toy

• Packing. Real training concatenates documents and cuts fixed-length windows, so no compute is wasted on padding. The subtlety is that a window then spans a document boundary, and the model learns spurious continuations unless the attention mask is reset at boundaries — a detail many implementations get wrong and few notice.
• Sequence length is a curriculum variable. Training at short context and extending later (position interpolation, YaRN, NTK-aware scaling) is far cheaper than training long from scratch, because of the \(T^2\) memory term.
• Batch shape drives hardware efficiency. Ragged batches waste compute proportional to the length variance; length-bucketed sampling recovers it. At scale this is a double-digit percentage of total training cost.

Block 3 — Softmax + cross-entropy

Teaches: the entropy floor tells you what 'learning nothing' looks like

The problem. You cannot tell whether a loss of 3.3 is good without knowing what "learning nothing" scores. The entropy floor is that reference, and computing it takes one line — after which every training curve is interpretable.

@block(3, "Softmax + cross-entropy", "the entropy floor tells you what 'learning nothing' looks like")
def b3(s, show):
    def softmax(z, axis=-1):
        z = z - z.max(axis=axis, keepdims=True)     # stability: never exp a big number
        e = np.exp(z)
        return e / e.sum(axis=axis, keepdims=True)
    def cross_entropy(logits, targets):
        p = softmax(logits)
        n = np.prod(targets.shape)
        flat = p.reshape(-1, p.shape[-1])[np.arange(n), targets.reshape(-1)]
        return float(-np.log(flat + 1e-12).mean())
    V = s["tok"].size
    uniform = np.zeros((2, 5, V))
    floor = cross_entropy(uniform, rng.integers(0, V, (2, 5)))
    if show:
        print(f"  vocab {V}, uniform logits -> loss {floor:.4f} nats")
        print(f"  ln({V}) = {np.log(V):.4f}   <- the ENTROPY FLOOR")
        print(f"  a model below this on shuffled targets has label leakage")
        print(f"  huge logits (1e4) -> {cross_entropy(np.full((1,1,V),1e4), np.zeros((1,1),int)):.4f}, no NaN")
    return {"softmax": softmax, "cross_entropy": cross_entropy, "floor": float(np.log(V))}


# ─────────────────────────────────────────────────────────── block 4

Reading the implementation

Cross-entropy in nats is \(-\frac{1}{n}\sum \log p(y_i)\), and the two reference points that make it readable are:

• Uniform guessing over \(V\) tokens: \(\log V\) nats.
• The unigram entropy of the corpus: what a model that learns only token frequencies achieves.

The subtraction \(\log V - H(\text{unigram})\) is exactly the information a frequency table carries, and it is usually a large fraction of the first improvement any language model shows.

The numerical detail: logsumexp with the max subtracted. Computing \(\log \sum e^{x_i}\) naively overflows for \(x > 709\) in float64 and \(x > 88\) in float32. Subtracting \(\max_i x_i\) first is mathematically identity and numerically essential — and it is the same trick FlashAttention's online softmax generalises to a streaming setting.

What the numbers say

Output:

  vocab 28, uniform logits -> loss 3.3322 nats
  ln(28) = 3.3322   <- the ENTROPY FLOOR
  a model below this on shuffled targets has label leakage
  huge logits (1e4) -> 3.3322, no NaN

Beyond the toy

Perplexity is \(e^{\text{loss}}\) and is the more interpretable unit: "the model is as uncertain as if choosing uniformly among \(e^{\text{loss}}\) tokens". Three cautions that make published perplexities incomparable:

• Perplexity depends on the tokenizer. A character-level model and a BPE model on the same text have entirely different perplexities. Only bits-per-byte is comparable across tokenizations.
• A loss below the entropy floor is a bug, not a triumph — it means the model saw the answer. That is the leak test in block 5, and having the floor computed here is what makes the test possible.
• Loss is averaged over positions, so a model that is excellent at position 1 and useless at position 64 looks mediocre everywhere. Per-position loss curves are the diagnostic, and they are how you discover that a model has learned nothing beyond its first few tokens of context.

Block 4 — One attention head

Teaches: content-addressed lookup, and why we divide by sqrt(dk)

The problem. Attention is usually introduced as a formula. It is more usefully introduced as a weighted average whose weights are computed from the data — and once framed that way, every part of the formula has a job you can see.

@block(4, "One attention head", "content-addressed lookup, and why we divide by sqrt(dk)")
def b4(s, show):
    softmax = s["softmax"]
    def head(X, Wq, Wk, Wv, causal=True):
        Q, K, V = X @ Wq, X @ Wk, X @ Wv
        scores = Q @ K.transpose(0, 2, 1) / np.sqrt(Q.shape[-1])
        if causal:
            T = X.shape[1]
            mask = np.tril(np.ones((T, T), bool))
            scores = np.where(mask, scores, -np.inf)   # BEFORE the softmax
        A = softmax(scores)
        return A @ V, A
    T, d = 6, 16
    X = rng.standard_normal((1, T, d))
    W = [rng.standard_normal((d, d)) / np.sqrt(d) for _ in range(3)]
    Y, A = head(X, *W)
    assert np.allclose(A.sum(-1), 1.0), "rows must be a distribution"
    assert np.triu(A[0], 1).max() == 0.0, "no attention to the future"
    if show:
        print(f"  X {X.shape} -> Y {Y.shape}, attention {A.shape}")
        print(f"  rows sum to 1: max err {abs(A.sum(-1)-1).max():.2e}")
        print(f"  upper triangle exactly zero: {np.triu(A[0],1).max():.1f}")
        ent = lambda a: float(-(a*np.log(a+1e-30)).sum(-1).mean())
        _, Au = head(X, *W); su = softmax((X@W[0]) @ (X@W[1]).transpose(0,2,1))
        print(f"  entropy scaled {ent(A):.3f} vs unscaled {ent(su):.3f} (max {np.log(T):.3f})")
    return {"head": head}


# ─────────────────────────────────────────────────────────── block 5

Reading the implementation

\[ \text{Attention}(Q,K,V) = \text{softmax}!\left(\frac{QK^{\top}}{\sqrt{d_k}}\right)V \]

Read it right to left. The output is \(\text{weights} \times V\) — an average of value vectors. The weights come from softmax(scores), so they are non-negative and sum to one. The scores are dot products between queries and keys, so the weights are large where the query and key agree. That is content-addressed lookup: a soft dictionary where the match is a similarity rather than an equality.

The scaling factor is the part worth deriving rather than memorising. If \(q\) and \(k\) have independent components with unit variance, then

\[ \mathrm{Var}(q!\cdot!k) = \sum_{i=1}^{d_k}\mathrm{Var}(q_ik_i) = d_k \]

so the scores have standard deviation \(\sqrt{d_k}\) — at \(d_k=64\), scores spread over ±8 before any training. Softmax of values that spread saturates: one weight goes to ~1, the rest to ~0, and the gradient through softmax (\(\text{diag}(p) - pp^{\top}\)) goes to zero. The model cannot learn because its attention is already maximally confident and wrong. Dividing by \(\sqrt{d_k}\) restores unit variance and keeps the distribution in the region where gradients exist (proofs.md P1).

What the numbers say

Output:

  X (1, 6, 16) -> Y (1, 6, 16), attention (1, 6, 6)
  rows sum to 1: max err 2.22e-16
  upper triangle exactly zero: 0.0
  entropy scaled 0.878 vs unscaled 0.124 (max 1.792)

The entropy column is the thing to watch: unscaled attention starts near- deterministic, scaled attention starts near-uniform. That difference is the difference between a model that trains and one that does not.

Beyond the toy

• Q, K, V are three linear projections of the same input in self-attention. Nothing requires that — cross-attention takes K and V from a different sequence, which is how encoder-decoder models and retrieval-augmented architectures work.
• The score matrix is the memory problem. \(T \times T\) per head; at \(T\)=8192 and 32 heads in fp16 that is 4 GB for one layer's scores. Never materialising it is FlashAttention's entire contribution, achieved by tiling into SRAM and using an online softmax that keeps a running max and normaliser.
• Attention is permutation-equivariant — it has no notion of order at all. Every positional scheme (learned, sinusoidal, RoPE, ALiBi) exists to repair that, and their differences are entirely about how they extrapolate beyond trained lengths.
• The softmax bottleneck. Because weights are non-negative and sum to one, attention can only produce outputs in the convex hull of the value vectors. That constraint is a real limit on expressiveness and motivates variants with gating or negative weights.

Block 5 — The leak test

Teaches: the single most valuable test in the project

The problem. The most valuable test in this project takes four lines and catches the failure that looks most like success. A causal model that can see the future achieves a loss below the entropy floor, produces beautiful training curves, and generates nothing.

@block(5, "The leak test", "the single most valuable test in the project")
def b5(s, show):
    head = s["head"]
    T, d = 10, 16
    X = rng.standard_normal((1, T, d))
    W = [rng.standard_normal((d, d)) / np.sqrt(d) for _ in range(3)]
    Y1, _ = head(X, *W)
    X2 = X.copy(); X2[:, 5:] = rng.standard_normal((1, T - 5, d))
    Y2, _ = head(X2, *W)
    leaked = not np.array_equal(Y1[:, :5], Y2[:, :5])
    assert not leaked, "CAUSAL LEAK"
    if show:
        print("  scrambled positions 5..9, then compared positions 0..4")
        print(f"  bit-identical: {np.array_equal(Y1[:,:5], Y2[:,:5])}   (leak: {leaked})")
        print("  catches: mask after softmax, off-by-one, accidental bidirectionality")
    return {}


# ─────────────────────────────────────────────────────────── block 6

Reading the implementation

The test perturbs a token at position \(j\) and asserts that outputs at positions \(< j\) are bit-identical. That is the precise operational meaning of causality: information may not flow backwards.

Why this beats inspecting the mask visually:

• It tests the composition of every layer, not one mask. A model can have a correct mask in layer 1 and a bug in a residual path, a cached key, or a normalisation that mixes across positions.
• It catches bugs in the inference path as well as training — a KV cache that recomputes positions differently is the classic one, and it only manifests when cached and uncached generation disagree.
• It requires no ground truth and no training, so it can run as a unit test in milliseconds on every commit.

-inf before the softmax rather than zeroing after is the correct implementation, because \(e^{-\infty}=0\) before normalisation. Zeroing afterwards leaves the denominator including masked positions, so the surviving weights no longer sum to one — a subtle scale error that trains, badly.

What the numbers say

Output:

  scrambled positions 5..9, then compared positions 0..4
  bit-identical: True   (leak: False)
  catches: mask after softmax, off-by-one, accidental bidirectionality

Beyond the toy

The general principle is worth more than the specific test: for every property your architecture is supposed to have, write the test that fails when it does not. Equivariances, invariances and information-flow constraints are all testable this way, cheaply, and they catch the class of bug that produces plausible-but-wrong models.

The production version of this bug is data leakage rather than mask leakage — a validation set that overlaps the training corpus, or a feature computed with future information (P08 measures exactly that). Same shape, same seductive symptom: results that are too good.

Block 6 — Multi-head

Teaches: H heads cost the same as one big head, and buy H views

The problem. One attention head computes one kind of similarity. Multi-head attention gets \(H\) of them for the same parameter count and the same FLOPs — which sounds like something for nothing and is worth understanding precisely.

@block(6, "Multi-head", "H heads cost the same as one big head, and buy H views")
def b6(s, show):
    softmax = s["softmax"]
    def mha(X, Wq, Wk, Wv, Wo, H):
        B, T, d = X.shape; dh = d // H
        def split(M): return M.reshape(B, T, H, dh).transpose(0, 2, 1, 3)
        Q, K, V = split(X @ Wq), split(X @ Wk), split(X @ Wv)
        sc = Q @ K.transpose(0, 1, 3, 2) / np.sqrt(dh)
        sc = np.where(np.tril(np.ones((T, T), bool)), sc, -np.inf)
        out = softmax(sc) @ V                                  # (B,H,T,dh)
        return out.transpose(0, 2, 1, 3).reshape(B, T, d) @ Wo
    d, H = 32, 4
    params1 = 4 * d * d                     # one head of width d + output proj
    paramsH = 4 * d * d                     # H heads of width d/H + output proj
    if show:
        print(f"  d={d}, H={H}: params 1-head {params1:,} vs {H}-head {paramsH:,}")
        print(f"  identical. You get {H} attention distributions for free.")
        print(f"  each head sees a {d//H}-dim subspace -- below ~16 they get too small")
    return {"mha": mha}


# ─────────────────────────────────────────────────────────── block 7

Reading the implementation

Split \(d\) into \(H\) heads of width \(d/H\), attend independently, then concatenate and project. The parameter count is identical to a single head of width \(d\) — \(4d^2\) either way — because the projections are just reshaped. The FLOPs are the same too, except that the score matrices are \(H\) matrices of \(T\times T\) rather than one.

What you buy is subspaces. Each head computes similarity in a \(d/H\)- dimensional projection of the space, so different heads can attend on different relations — syntactic dependency, coreference, positional offset. One large head must express all relations in one similarity function and cannot separate them.

The cost is per-head dimension: at \(d\)=512 and \(H\)=64, each head has 8 dimensions, which is too few for a meaningful similarity. There is an interior optimum and it is empirical, typically \(d/H\) in the 64--128 range.

• The transpose(1, 2) / reshape pair is where implementations go wrong: the head dimension must be adjacent to the batch dimension for the batched matmul, and the inverse reshape must restore the exact original layout. A reshape that silently interleaves head outputs still trains — worse, and for no visible reason.

What the numbers say

Output:

  d=32, H=4: params 1-head 4,096 vs 4-head 4,096
  identical. You get 4 attention distributions for free.
  each head sees a 8-dim subspace -- below ~16 they get too small

Beyond the toy

• MQA and GQA break the symmetry deliberately: keep \(H\) query heads but share one (MQA) or a few (GQA) key/value heads. Quality is nearly unchanged and the KV cache shrinks by \(H\) or \(H/g\), which is the dominant memory cost at inference. This is the clearest case in the architecture of a change motivated purely by the serving cost model (P14).
• Head redundancy is measurable. Michel et al. found most heads can be pruned at little cost, and specialised heads (induction heads, previous-token heads) are identifiable and mechanistically interpretable. \(H\) is over-provisioned because which heads matter is not known in advance.
• Attention sinks. Trained models place large attention mass on the first token, apparently as a no-op destination when a head has nothing to attend to. Deleting that token during streaming inference breaks the model, which is why StreamingLLM keeps it pinned.

Block 7 — The pre-norm block

Teaches: residual as a gradient highway; norm before the sublayer

The problem. Two mechanisms let a deep stack train at all — the residual connection and the normalisation — and where the normalisation goes changes whether the model needs a warmup schedule to converge.

@block(7, "The pre-norm block", "residual as a gradient highway; norm before the sublayer")
def b7(s, show):
    mha = s["mha"]
    def layernorm(x, g, b, eps=1e-5):
        mu = x.mean(-1, keepdims=True); var = x.var(-1, keepdims=True)
        return g * (x - mu) / np.sqrt(var + eps) + b
    def ffn(x, W1, b1, W2, b2):
        h = x @ W1 + b1
        return np.maximum(h, 0) @ W2 + b2                      # ReLU, 4x expansion
    def tblock(x, P, H):
        x = x + mha(layernorm(x, P["g1"], P["b1"]), P["Wq"], P["Wk"], P["Wv"], P["Wo"], H)
        x = x + ffn(layernorm(x, P["g2"], P["b2"]), P["W1"], P["bb1"], P["W2"], P["bb2"])
        return x
    if show:
        print("  x = x + Attn(LN(x));  x = x + FFN(LN(x))")
        print("  PRE-norm: the residual path from output to input is unnormalised,")
        print("  so gradients reach layer 1 undiminished. Post-norm rescales on every")
        print("  layer and needs warmup to train deep.")
    return {"layernorm": layernorm, "ffn": ffn, "tblock": tblock}


# ─────────────────────────────────────────────────────────── block 8

Reading the implementation

x = x + sublayer(norm(x)) is pre-norm. The alternative, x = norm(x + sublayer(x)), is post-norm, and the difference is the gradient path.

In pre-norm, the residual stream is an unbroken identity path from input to output: the gradient reaches every layer undiminished, because \(\partial(x + f(x))/\partial x = I + \partial f/\partial x\). In post-norm, every layer's output passes through a normalisation, so gradients are rescaled at each of \(L\) steps and the product either shrinks or grows with depth. That is why the original Transformer needed a learning-rate warmup and why post-norm models past ~12 layers were unstable without one.

Pre-norm's cost is a slight quality reduction at matched compute, and a residual stream whose magnitude grows with depth — which is why pre-norm models add a final normalisation before the output projection.

What the numbers say

Output:

  x = x + Attn(LN(x));  x = x + FFN(LN(x))
  PRE-norm: the residual path from output to input is unnormalised,
  so gradients reach layer 1 undiminished. Post-norm rescales on every
  layer and needs warmup to train deep.

Beyond the toy

• RMSNorm drops the mean subtraction and the bias: \(x / \sqrt{\overline{x^2} + \epsilon}\). It is 10--15% cheaper in a memory-bound kernel with no measurable quality cost, which is why most models after ~2022 use it.
• The FFN is where the parameters are. With a 4× expansion, the two FFN matrices are \(8d^2\) against attention's \(4d^2\) — two thirds of every layer. Optimisation effort aimed at "attention" is usually aimed at a third of the model.
• SwiGLU replaces the ReLU FFN with a gated variant, using ~2.7× expansion to match parameter count. It costs a third matmul and consistently wins per parameter, which is a compute-for-quality trade rather than a free lunch.
• Normalisation placement interacts with precision. In bf16, post-norm's accumulated rescaling can overflow; the numerics and the architecture are not separable concerns.

Block 8 — The model

Teaches: stack the block; tie the unembedding; count the parameters

The problem. Assemble the pieces into something with a parameter count you can defend, and make the two decisions that dominate that count: how many layers, and whether to tie the unembedding.

@block(8, "The model", "stack the block; tie the unembedding; count the parameters")
def b8(s, show):
    tblock, layernorm = s["tblock"], s["layernorm"]
    V, d, H, L, T = s["tok"].size, 32, 4, 2, 16

    def init():
        P = {"emb": rng.standard_normal((V, d)) * 0.02,
             "pos": rng.standard_normal((T, d)) * 0.02,
             "gf": np.ones(d), "bf": np.zeros(d)}
        for l in range(L):
            for k, shape in (("Wq",(d,d)),("Wk",(d,d)),("Wv",(d,d)),("Wo",(d,d)),
                             ("W1",(d,4*d)),("W2",(4*d,d))):
                P[f"{l}.{k}"] = rng.standard_normal(shape) / np.sqrt(shape[0])
            P[f"{l}.bb1"] = np.zeros(4*d); P[f"{l}.bb2"] = np.zeros(d)
            P[f"{l}.g1"] = np.ones(d); P[f"{l}.b1"] = np.zeros(d)
            P[f"{l}.g2"] = np.ones(d); P[f"{l}.b2"] = np.zeros(d)
        return P

    def forward(P, idx):
        B, t = idx.shape
        x = P["emb"][idx] + P["pos"][:t]
        for l in range(L):
            sub = {k.split(".",1)[1]: v for k, v in P.items() if k.startswith(f"{l}.")}
            x = tblock(x, sub, H)
        x = layernorm(x, P["gf"], P["bf"])
        return x @ P["emb"].T                       # weight tying: unembed = emb^T
    P = init()
    n = sum(v.size for v in P.values())
    if show:
        print(f"  V={V} d={d} heads={H} layers={L} ctx={T}")
        print(f"  parameters: {n:,}  (embedding tied with unembedding)")
        lg = forward(P, s["data"][:16][None, :])
        print(f"  forward: idx (1,16) -> logits {lg.shape}")
        print(f"  initial loss {s['cross_entropy'](lg, s['data'][1:17][None,:]):.4f} "
              f"vs floor {s['floor']:.4f}  (untrained ~= floor, as it should be)")
    return {"init": init, "forward": forward, "V": V, "d": d, "H": H, "L": L, "T": T}


# ─────────────────────────────────────────────────────────── block 9

Reading the implementation

Per layer the parameter count is \(4d^2\) (attention projections) + \(8d^2\) (FFN) = \(12d^2\), so a model is approximately \(12Ld^2\) parameters plus embeddings. That formula is worth memorising: it lets you size a model, estimate its training FLOPs as \(6N\) per token, and price its inference at \(2N\), all without a framework.

Weight tying — using the embedding matrix as the output projection — saves \(Vd\) parameters. At \(V\)=32000 and \(d\)=4096 that is 131M, which at small scale is most of the model and at large scale is a rounding error. The justification is more than parameter economy: the input embedding and the output projection are both maps between token space and hidden space, and tying imposes that they be transposes of each other, which acts as a regulariser at small scale.

Initialisation scale is the other decision hiding here, and it is the one that silently ruins training runs. Weights scaled \(1/\sqrt{d}\) keep activation variance stable through a layer; too large and the residual stream explodes with depth, too small and the signal vanishes. The first version of this project's walkthrough omitted the scale and the demo disproved its own point — kept as a comment in the source because it is the most instructive kind of bug.

What the numbers say

Output:

  V=28 d=32 heads=4 layers=2 ctx=16
  parameters: 26,624  (embedding tied with unembedding)
  forward: idx (1,16) -> logits (1, 16, 28)
  initial loss 3.3313 vs floor 3.3322  (untrained ~= floor, as it should be)

Beyond the toy

• Depth versus width. At fixed parameter count, deeper models generally perform better up to a point, but depth is serial — it cannot be parallelised across devices as cleanly as width, and it increases the pipeline bubble in pipeline parallelism. The choice is as much a systems decision as a modelling one.
• Chinchilla scaling says compute-optimal training uses ~20 tokens per parameter, which repriced the entire field: most models of the GPT-3 era were badly under-trained for their size, and a smaller model trained longer wins at equal compute and is cheaper to serve forever after.
• Parameter count is the wrong metric for serving cost. What matters at inference is bytes read per token (memory-bound decode) and KV cache per sequence — both of which MoE and GQA decouple from parameter count entirely.

Block 9 — The same attention, in torch

Teaches: P01 permits torch as a TENSOR library -- not as an attention library

The problem. Everything above is numpy, which cannot compute a gradient. This block ports the same attention to torch as a tensor library — explicitly not using nn.MultiheadAttention or scaled_dot_product_attention — and proves the port is exact before trusting it.

@block(9, "The same attention, in torch", "P01 permits torch as a TENSOR library -- not as an attention library")
def b9(s, show):
    try:
        import torch, torch.nn.functional as F
    except ImportError:
        if show:
            print("  torch is not installed, so this block and the assembly are")
            print("  skipped. Blocks 1-8 above are pure numpy and told the whole")
            print("  story; this block only re-expresses block 6's attention in a")
            print("  framework that can differentiate it. Install with:")
            print("      pip install torch")
        return {}
    torch.manual_seed(0)

    def mha_t(x, Wq, Wk, Wv, Wo, H):
        """Byte-for-byte the same maths as block 6. Hand-written -- the whole point
        is that nn.MultiheadAttention is forbidden. torch supplies tensors and
        autograd; the mechanism is ours."""
        B, T, d = x.shape; dh = d // H
        sp = lambda M: (x @ M).view(B, T, H, dh).transpose(1, 2)
        q, k, v = sp(Wq), sp(Wk), sp(Wv)
        sc = q @ k.transpose(-2, -1) / (dh ** 0.5)
        sc = sc.masked_fill(~torch.tril(torch.ones(T, T, dtype=torch.bool)), float("-inf"))
        out = torch.softmax(sc, -1) @ v
        return (out.transpose(1, 2).reshape(B, T, d)) @ Wo

    # equivalence check against the numpy head from block 6
    B, T, d, H = 1, 6, 32, 4
    xs = rng.standard_normal((B, T, d))
    Ws = [rng.standard_normal((d, d)) / np.sqrt(d) for _ in range(4)]
    np_out = s["mha"](xs, *Ws, H)
    t_out = mha_t(torch.tensor(xs), *[torch.tensor(w) for w in Ws], H).detach().numpy()
    err = np.abs(np_out - t_out).max()
    assert err < 1e-10, f"torch and numpy disagree: {err}"
    if show:
        print(f"  numpy vs torch, same weights: max |diff| = {err:.2e}")
        print("  identical maths, and now differentiable. Forbidden here and in P01:")
        print("    nn.Transformer, nn.MultiheadAttention, F.scaled_dot_product_attention")
    return {"torch": torch, "mha_t": mha_t}


# ─────────────────────────────────────────────────────────── assembly

Reading the implementation

The port is line-for-line the same mathematics, and the assertion against the numpy version to \(<10^{-10}\) is what makes it safe to build on. That check is the same discipline as P13's reference comparison: a re-implementation is not correct because it looks correct, it is correct because it agrees with something already trusted.

masked_fill(~tril(...), -inf) is the causal mask again, now differentiable. Note that -inf interacts with autograd correctly here because softmax's gradient at a zero-probability position is zero — but a -inf that reaches a sum or a log elsewhere produces nan, which is the most common way masking breaks a backward pass.

What the numbers say

Output:

  numpy vs torch, same weights: max |diff| = 4.44e-16
  identical maths, and now differentiable. Forbidden here and in P01:
    nn.Transformer, nn.MultiheadAttention, F.scaled_dot_product_attention

Beyond the toy

The restriction — torch as tensors, not as transformers — is the pedagogical point of the whole project, and it maps onto a real engineering distinction. Using F.scaled_dot_product_attention in production is correct: it dispatches to FlashAttention, handles the memory layout, and is faster than anything hand- written. But it also means the \(T^2\) memory problem, the online softmax, and the numerical care around masking are invisible to you — and those are precisely the things you need to understand when the fused kernel does not support your variant, when a mask produces nan, or when you have to decide whether MQA is worth the quality risk.

Build it once to know what the library is doing; then use the library.

The assembly

Every block above, wired together into one working system:

def assembly(s):
    if "torch" not in s:
        print("\n  Skipped: the assembly trains the model, which needs torch.")
        print("  Run `pip install torch` and re-run to see it reach 0.106 nats.")
        return
    torch, mha_t, tok = s["torch"], s["mha_t"], s["tok"]
    V, d, H, L, T = s["V"], s["d"], s["H"], s["L"], s["T"]
    floor = s["floor"]
    data = torch.tensor(s["data"])

    print("\nEvery block, wired into a model that actually trains.\n")

    g = torch.Generator().manual_seed(0)
    def par(*shape, scale=None):
        t = torch.randn(*shape, generator=g) * (scale if scale else (shape[0] ** -0.5))
        return t.requires_grad_(True)

    P = {"emb": par(V, d, scale=0.02), "pos": par(T, d, scale=0.02)}
    for l in range(L):
        for k in ("Wq", "Wk", "Wv", "Wo"): P[f"{l}.{k}"] = par(d, d)
        P[f"{l}.W1"] = par(d, 4 * d); P[f"{l}.W2"] = par(4 * d, d)
    params = list(P.values())

    def ln(x):
        return (x - x.mean(-1, keepdim=True)) / (x.var(-1, keepdim=True, unbiased=False) + 1e-5).sqrt()

    def model(idx):
        x = P["emb"][idx] + P["pos"][: idx.shape[1]]
        for l in range(L):
            x = x + mha_t(ln(x), P[f"{l}.Wq"], P[f"{l}.Wk"], P[f"{l}.Wv"], P[f"{l}.Wo"], H)
            x = x + torch.relu(ln(x) @ P[f"{l}.W1"]) @ P[f"{l}.W2"]
        return ln(x) @ P["emb"].T                       # tied unembedding

    def batch(n, bs=16):
        ix = torch.randint(0, len(data) - T - 1, (bs,), generator=g)
        return (torch.stack([data[i:i+T] for i in ix]),
                torch.stack([data[i+1:i+T+1] for i in ix]))

    opt = torch.optim.AdamW(params, lr=3e-3)
    print(f"  {'step':>6}{'loss':>10}{'floor':>9}   {'note':<28}")
    for step in range(801):
        x, y = batch(step)
        loss = torch.nn.functional.cross_entropy(model(x).reshape(-1, V), y.reshape(-1))
        opt.zero_grad(); loss.backward(); opt.step()
        if step % 200 == 0 or step == 800:
            note = "at the floor -- untrained" if step == 0 else ""
            print(f"  {step:>6}{loss.item():>10.4f}{floor:>9.4f}   {note:<28}")
    final = loss.item()
    print(f"\n  final {final:.4f} nats, {floor - final:.4f} BELOW the entropy floor "
          f"({floor:.4f}).")
    print(f"  perplexity {np.exp(final):.2f} against a random-guess perplexity of {V}.")

    print("\n  E10 (deliberate overfit) -- the gate before any real training:")
    tiny_x, tiny_y = data[:T][None, :], data[1:T+1][None, :]
    for step in range(400):
        loss = torch.nn.functional.cross_entropy(model(tiny_x).reshape(-1, V), tiny_y.reshape(-1))
        opt.zero_grad(); loss.backward(); opt.step()
    print(f"    200-token slice driven to loss {loss.item():.4f}  "
          f"({'PASS' if loss.item() < 0.1 else 'still above 0.1'})")
    print("    a model that cannot do this has a bug, not a hard problem.")

    print("\n  Generation (greedy):")
    ctx = data[:6].tolist()
    for _ in range(40):
        ctx.append(int(model(torch.tensor(ctx[-T:])[None, :])[0, -1].argmax()))
    print(f"    {tok.decode(ctx)!r}")

    print("\n" + "─" * 74)
    print("  THE FULL PICTURE")
    print("─" * 74)
    rows = [(1,"tokenizer","chars <-> ids, round-trip tested"),
            (2,"batching","y is x shifted by one"),
            (3,"loss","cross-entropy, and the ln(V) entropy floor"),
            (4,"attention","QK^T/sqrt(dk), softmax, weighted V"),
            (5,"leak test","future tokens provably cannot influence the past"),
            (6,"multi-head","H views for the price of one"),
            (7,"pre-norm block","residual highway + LN before each sublayer"),
            (8,"the model","embedding -> L blocks -> tied unembedding"),
            (9,"torch port","same maths, now differentiable")]
    for n, name, what in rows:
        print(f"    block {n}  {name:<16} {what}")
    print(f"\n    assembly     {sum(p.numel() for p in params):,} parameters, "
          f"trained to {final:.3f} nats")
    print("\n  Next, on the project page: RoPE (m9), BPE (m8), KV cache (m11), and")
    print("  the ablations that turn this from a working model into a measured one.")

Output:

Every block, wired into a model that actually trains.

    step      loss    floor   note                        
       0    3.3408   3.3322   at the floor -- untrained   
     200    0.1810   3.3322                               
     400    0.1187   3.3322                               
     600    0.1169   3.3322                               
     800    0.1056   3.3322                               

  final 0.1056 nats, 3.2266 BELOW the entropy floor (3.3322).
  perplexity 1.11 against a random-guess perplexity of 28.

  E10 (deliberate overfit) -- the gate before any real training:
    200-token slice driven to loss 0.0017  (PASS)
    a model that cannot do this has a bug, not a hard problem.

  Generation (greedy):
    'the quick brown fox fox fox fox runs fons fox '

  THE FULL PICTURE
    block 1  tokenizer        chars <-> ids, round-trip tested
    block 2  batching         y is x shifted by one
    block 3  loss             cross-entropy, and the ln(V) entropy floor
    block 4  attention        QK^T/sqrt(dk), softmax, weighted V
    block 5  leak test        future tokens provably cannot influence the past
    block 6  multi-head       H views for the price of one
    block 7  pre-norm block   residual highway + LN before each sublayer
    block 8  the model        embedding -> L blocks -> tied unembedding
    block 9  torch port       same maths, now differentiable

    assembly     25,984 parameters, trained to 0.106 nats

  Next, on the project page: RoPE (m9), BPE (m8), KV cache (m11), and
  the ablations that turn this from a working model into a measured one.

The design space

The blocks above implement one point in a large space. Every choice below is a real fork taken by a real production model, and the reason for each is a cost, not a preference.

The arithmetic that drives all of it

For one layer, hidden size \(d\), sequence \(T\), the forward cost splits in two:

\[ \text{attention projections} = 4Td^2, \quad \text{attention scores+values} = 2T^2 d, \quad \text{FFN} = 8Td^2 \ (\text{ratio }4) \]

So attention's quadratic term overtakes the linear ones when \(2T^2 d > 12Td^2\), that is \(T > 6d\). For \(d\) = 4096 that is \(T\) ≈ 24{,}000 tokens. Below that, a transformer is a stack of matmuls and attention is a rounding error in FLOPs — which is why "attention is quadratic" is misleading advice at ordinary context lengths. What attention does dominate long before that is memory: the score matrix is \(T^2\) per head, and materialising it is why FlashAttention exists.

Training cost per token is ≈\(6N\) FLOPs for \(N\) parameters (2 forward, 4 backward); inference is ≈\(2N\). Those two constants let you price a training run on the back of an envelope, and they are the arithmetic behind the Chinchilla result that most models of that era were badly under-trained for their size.

Latency, bandwidth and the memory hierarchy

Decode is the case that matters and it is memory-bound, not compute-bound. Generating one token requires reading every weight once:

No arithmetic optimisation moves those numbers, because the arithmetic intensity of a batch-1 decode step is ≈2 FLOP/byte against a ridge point near 295. This is the single most important fact about LLM serving and it falls straight out of P14's roofline. The levers are all bytes: quantise the weights (int8/int4/fp8), share KV heads (GQA/MQA), or amortise the read over more sequences (batching, which is why continuous batching and paged attention exist).

The KV cache is the other memory consumer, and it grows with traffic rather than model size:

\[ \text{KV bytes} = 2 \times L \times T \times d_{kv} \times \text{batch} \times \text{bytes/elem} \]

For a 70B-class model (80 layers, \(d_{kv}\)=8192 with MHA) at 4k context, that is ~10 GB per sequence. GQA with 8 KV heads out of 64 divides it by 8. This is why vLLM's paged attention — allocating KV in fixed blocks like OS pages, from P12 — was such a large practical win: it removed the internal fragmentation from over-provisioning contiguous per-sequence buffers.

FlashAttention, and why it is an IO algorithm

The naive attention kernel writes the \(T \times T\) score matrix to HBM, reads it back for the softmax, writes it again, reads it for the value multiply. That is \(O(T^2)\) HBM traffic for \(O(T^2 d)\) work — intensity \(O(d)\), but with a constant that puts it below the ridge. FlashAttention tiles Q, K and V into SRAM (192 KB per SM on A100) and never materialises the full matrix, using the online softmax trick to keep a running max and normaliser so a streaming computation is numerically identical to the batched one. Same FLOPs, an order of magnitude less HBM traffic, 2--4× faster in practice. It is the clearest example in modern ML of an algorithm that is faster without doing less arithmetic — exactly the lesson P14 block 3 measures on a smaller scale.

Hardware: CPU, GPU, TPU

The systolic array is worth understanding because it explains TPU's shape preferences. Data flows through a 128×128 grid of MACs; each value read from memory is reused 128 times inside the array before leaving. That is the hardware expression of the same reuse argument as cache tiling (P14 block 4) — see proofs.md P15. It also means a matmul whose dimensions are not multiples of 128 wastes the array, which is why TPU-targeted models pad aggressively and why "make the hidden size a nice number" is real advice.

Note the ridge points: every accelerator generation has made the memory wall worse, because FLOP/s has grown faster than bandwidth. A kernel that was compute-bound on a V100 can be memory-bound on an H100 without a line changing.

Advanced algorithms and alternatives

• Sub-quadratic attention. Linear attention (Katharopoulos et al.) rewrites softmax attention as a kernel feature map so the computation associates as \((\phi(Q)(\phi(K)^\top V))\), turning \(O(T^2d)\) into \(O(Td^2)\). Performer approximates the softmax kernel with random features. Both lose quality on recall-heavy tasks, which is the empirical finding that keeps full attention alive.
• State-space models. S4/Mamba replace attention with a linear recurrence that has a convolutional parallel form for training and a constant-state recurrent form for inference — so decode needs no KV cache at all. The trade is a fixed-size state versus attention's perfect recall over the context.
• Sparse attention. Longformer/BigBird use local windows plus a few global tokens; the theory is that the resulting attention graph is an expander, so information still mixes in \(O(\log T)\) hops. Hardware efficiency is the practical problem: unstructured sparsity maps badly to tensor cores.
• Speculative decoding. A small draft model proposes \(k\) tokens, the large model verifies them in one forward pass. It converts \(k\) memory-bound decode steps into one compute-bound one — a pure exploitation of the intensity gap in the table above, with an acceptance-rate-dependent speedup and identical output distribution.
• MoE. Mixture-of-experts decouples parameters from FLOPs per token: only the top-\(k\) experts run. It trades a much larger memory footprint and an all-to-all communication pattern (P06's shuffle, at NVLink speed) for constant compute.

How this connects to the rest of the track

• P13 implements the autodiff this model trains under; block 9 here is the same attention expressed in a framework that can differentiate it.
• P14 explains why decode is memory-bound and prefill is not — the same intensity arithmetic, generalised.
• P02 uses the embeddings a model like this produces; attention itself is a soft nearest-neighbour lookup with learned keys, and both hit the same contrast problem in high dimensions.
• P12's paging is the direct ancestor of paged attention.
• P06's all-to-all shuffle is the same communication pattern as expert-parallel MoE routing and tensor-parallel all-reduce.

Failure modes at scale

• Loss spikes from a single bad batch or fp16 overflow in attention logits; the standard mitigations are z-loss, query/key normalisation, and skipping batches whose gradient norm exceeds a threshold.
• Silent leakage from an off-by-one in the causal mask. Loss falls below the data's entropy floor, which looks like a triumph. The assembly's floor comparison is the cheap detector.
• Divergence between train and inference paths — a KV cache that recomputes positions differently from training. Assert that cached and uncached generation produce identical logits.
• Throughput collapse from ragged batches: padding to the longest sequence in the batch wastes compute proportional to the length variance, which is why serving systems sort by length or use continuous batching.

Primary sources

• Vaswani et al., Attention Is All You Need (2017) — the architecture.
• Dao et al., FlashAttention (2022) and FlashAttention-2 (2023) — the IO argument in full.
• Shazeer, Fast Transformer Decoding: One Write-Head Is All You Need (2019) — MQA, and the KV-cache reasoning above.
• Ainslie et al., GQA (2023) — the interpolation that most models now use.
• Hoffmann et al., Training Compute-Optimal Large Language Models (2022) — the \(6N\) arithmetic applied to a scaling law.
• Kwon et al., Efficient Memory Management for LLM Serving with PagedAttention (2023) — P12's idea, in a serving stack.
• Su et al., RoFormer (2021) — RoPE.

Running it

python3 handson/h01_transformer.py            # every block, then the assembly
python3 handson/h01_transformer.py --block 3  # just block 3 and its prerequisites
python3 handson/h01_transformer.py --quiet    # the assembly only

What to do with this

Run it, then break it. Delete the / sqrt(dk) and watch block 3's entropy collapse. Remove the causal mask and watch the loss drop below the entropy of the data --- the classic leakage bug, which looks like brilliant training. Change the initialisation scale and see how far it moves the trainable range. Each of those is a two-character edit with a visible, measurable consequence, which is the fastest way to build the intuition that reading the paper alone will not.

Milestones, experiments, readings and exit criteria for this project: P01 — Transformer From Scratch.

P02 — Approximate Nearest-Neighbour Index

Run it first. There is a companion page that builds this project's machinery as numbered, independently runnable blocks and then assembles them into one measured system: P02 hands-on — block by block (handson/h*.py). Every number on it was produced by running the code. Read it alongside the milestones below.

Medium · 77 hours · Weeks 9–15 · Stage 1 · Python, with a compiled inner loop

Table of Contents

• The Loop, Instantiated
• Why This Project Matters
• Prerequisites
• Duration and Size
• Central Technical Questions
• Architecture
• Showcase — Do This Before You Start
• Implementation Milestones
• Concepts To Study
• Primary-Source Readings
• Experiments
• Benchmarks and Metrics
• Correctness Tests
• Failure Tests
• Expected Difficulties
• Scope Boundaries
• Deliverables
• Exit Criteria
• Extension Ideas
• Connections
• References

The Loop, Instantiated

Why This Project Matters

You use HNSW in production through OpenSearch. That means you already have opinions about ef_search and m that you cannot currently defend from first principles, and you have never seen what recall does when the parameters are wrong in a way that doesn't show up as an error.

More generally: this is the project where "approximate" stops being a hand-wave and becomes a contract with a number attached. Almost every system in the rest of this journey trades exactness for speed somewhere — a Bloom filter, a watermark, a sampled metric, a quantized weight. This is the cleanest possible place to learn how to quantify what you gave up, because the exact answer is cheaply computable and the approximation error is a single scalar.

It is also the project that teaches the most transferable debugging technique in the whole track: when a better algorithm loses to a worse one, decompose the ratio into operation count and cost per operation before touching a parameter.

Prerequisites

• P01 is not required but supplies realistic test data (see Connections)
• Linear algebra: dot products, norms, the cosine/L2 equivalence under normalisation
• Basic graph algorithms: BFS, priority queues, greedy search
• From math.md: §Concentration of Measure in High Dimensions (2 h). Read it before milestone 3 — it is what makes the curse of dimensionality quantitative rather than folkloric.

Duration and Size

Medium, 77 hours, 7 weeks.

Central Technical Questions

1. Why does exact search get hard in high dimensions, and what is the right way to measure "hard"? (Not \(d\). See relative contrast.)
2. What does a greedy graph walk assume, and where exactly is that assumption false? The missing recall is not diffuse; it goes to specific nodes for a specific reason.
3. Why a hierarchy? What does it buy that a single well-connected graph does not?
4. Why does neighbour selection matter more than it looks? This is the question most implementations get wrong.
5. What is the actual crossover point where your index beats brute force, and which of the two factors — algorithmic or constant — decides it?
6. What does recall@10 = 0.95 mean for a downstream recommender? Is the missing 5% uniformly distributed across queries, or concentrated on the hard ones? (It is the latter. Measure it.)

Architecture

Write your naive design first.

                          ┌──────────────────────────────────┐
   query vector ────────► │  Layer L   (sparse, long edges)  │   greedy, ef=1
                          │      │ descend at local min      │
                          │  Layer 1                         │   greedy, ef=1
                          │      │                           │
                          │  Layer 0   (all points, dense)   │   beam search, ef=efSearch
                          └──────────────┬───────────────────┘
                                         ▼
                              top-k by distance, exact within the visited set

Each point is inserted into layers \(0..\ell\) where \(\ell = \lfloor -\ln(U(0,1)) \cdot m_L \rfloor\) — a geometric distribution, so layer \(i\) holds roughly \(1/e^i\) of the points. The upper layers are a coarse skeleton for navigation; layer 0 holds everything and is where recall is decided.

The difficulty metric

Ambient dimension \(d\) does not predict ANN difficulty. Relative contrast does (He, Kumar & Chang 2012):

\[ \mathrm{RC} = \frac{\mathbb{E}_q[\text{mean distance from } q \text{ to all points}]}{\mathbb{E}_q[\text{distance from } q \text{ to its nearest neighbour}]} \]

As RC → 1, every point is about as far away as every other, greedy descent has no gradient to follow, and any distance-based method degenerates. Measured with tools/annlab.py on uniform unit-sphere data at n=10,000:

At \(d=512\) the tenth-nearest neighbour is 2% further away than the first. No index can reliably distinguish them, and an ANN benchmark on uniform high-dimensional data is measuring the dataset, not the index.

Real embeddings are not uniform — they concentrate near a low-dimensional manifold. The same tool with 100 Gaussian clusters at σ=0.05 gives RC = 3.363 at d=64, 2.5× the uniform value at the same ambient dimension. Which dataset you benchmark on decides your conclusion, so state it every time.

One trap, measured: a Gaussian perturbation with per-axis σ in \(d\) dimensions has expected norm \(\sigma\sqrt{d}\). If the cluster centres are unit vectors and \(\sigma\sqrt{d} \gtrsim 1\), the noise exceeds the signal and your "clustered" dataset is uniform data wearing a hat. At d=64: σ=0.25 gives RC=1.393 against uniform's 1.356 — no difference. σ=0.05 gives 3.371. Verify your independent variable varies before you spend a run measuring its effect.

The two-factor speedup model

The most useful thing in this project. Decompose any comparison against brute force:

\[ \text{speedup} = \underbrace{\frac{n}{\text{dists/query}}}_{\text{algorithmic}} \Big/ \underbrace{\frac{\text{ns/dist}_{\text{graph}}}{\text{ns/dist}_{\text{brute}}}}_{\text{constant factor}} \]

Measured at n=10,000, d=64, M=16, efSearch=64, pure Python:

The model closes to two significant figures in both cases. It says something specific and actionable: the algorithm is right and the implementation is wrong, which is a different bug from "the algorithm is wrong" and has a different fix. Without the distance counter you would conclude "HNSW doesn't work at n=10k" and spend a week tuning M.

Break-even needs the algorithmic win to exceed the constant factor. Distances/query grows roughly logarithmically while brute force grows linearly, so in pure Python the crossover lands near n ≈ 1.5×10⁵ (a run at n=100,000, d=128 measured 0.80× at ef=64 — just short of parity). In compiled code the constant factor is ~1–2× and the crossover falls to a few thousand. This is why every serious ANN index is written in C++, and milestone 8 is where you find that out for yourself.

Showcase — Do This Before You Start

W2 and the tools · walkthroughs/annlab.py · ~30 minutes

A working miniature of this project: the full recall/QPS curve, the distance counter, and the two-factor decomposition — run python3 tools/annlab.py and --clusters 100 to see both datasets.

cd walkthroughs && python3 annlab.py

It is 80-ish lines and it surfaces this project's central surprise in an evening rather than in week six. Run it before committing the weeks.

Implementation Milestones

Concepts To Study

• Metric spaces and the triangle inequality — and which pruning techniques it enables (and why cosine similarity is not a metric, but its induced distance is)
• Curse of dimensionality, stated quantitatively: concentration of pairwise distances, and why \(d_{10}/d_1 \to 1\)
• Intrinsic vs ambient dimensionality; why real embeddings are easier than their \(d\) suggests
• Small-world graphs: Kleinberg's navigability result, and why long-range links with the right distribution give \(O(\log^2 n)\) greedy routing
• Greedy search and local minima in proximity graphs; the beam as a remedy
• Skip lists — HNSW's hierarchy is a skip list in a metric space, and seeing that makes the layer-assignment distribution obvious
• Neighbour-selection heuristics: why "keep the M nearest" destroys connectivity on clustered data
• Product quantization: codebooks, asymmetric distance computation (extension only)
• SIMD and memory layout: why contiguous float32 and cache-line alignment matter more than instruction count

Primary-Source Readings

Budget: 11 hours. Read Malkov 2016 §3 after your milestone 5, not before — milestone 4 and 5 are your naive design and it must be yours.

Experiments

E7 is the experiment to build the project around. The naive prediction — clustered data is easier, so recall is higher everywhere — is false, and finding out why teaches you the thing the paper's Algorithm 4 exists for. Measured at n=10k, d=64:

Clustered is faster everywhere and worse above ef≈96. The clustered search cannot spend its budget: 840 distances at ef=256 versus uniform's 4,059. It runs out of reachable candidates. The full failure analysis — the degree cap deletes every inter-cluster bridge deterministically, because intra-cluster distance is 0.521 and inter-cluster is 1.413 — is in the worked notebook entry.

E12 you will lose. hnswlib is years of C++ tuning. Losing by 5–20× while matching its recall curve at equal distance count is a good result and you should report it that way: same algorithm, different constant factor, and you can prove the split.

Benchmarks and Metrics

Correctness Tests

1. Brute force vs naive triple loop on n=100, d=8. Exact agreement.
2. Metric equivalence: on normalised vectors, top-k by cosine, dot, and L2 are the identical index list. Proves \(||a-b||^2 = 2 - 2\langle a,b \rangle\).
3. Recall ≤ 1.0 and = 1.0 when efSearch ≥ n. Exhaustive beam must find everything.
4. Graph invariants: no self-loops; no duplicate edges; degree ≤ cap at every node; every node in layer \(i\) also in layers \(<i\); layer 0 contains all points.
5. Reachability: every node reachable from the entry point in layer 0. This test catches the connectivity bug in E7 directly, and you should add it because of E7.
6. Persistence round-trip: save, load, and get bit-identical results for a fixed query set.
7. Deletion: a deleted id is never returned, at any efSearch.
8. Determinism: fixed seed → identical graph. Verify by hashing the adjacency lists.
9. Empty and degenerate cases: n=0, n=1, k>n, all-identical vectors, zero vectors (which have undefined cosine — decide the policy and test it).

Failure Tests

Expected Difficulties

1. Your first graph will be slower than brute force and you will assume you failed. You did not. Instrument the distance counter at milestone 5 — before you look at wall-clock — and the two-factor model will tell you which half is the problem.
2. The beam-search stopping condition is subtle. Stopping when the nearest unexplored candidate is worse than the worst held result is correct only under a local-metric assumption. Getting it slightly wrong changes recall by tens of percent, silently.
3. Algorithm 4 reads like an optimisation and is a correctness property. Budget time for milestone 7; do not fold it into 6.
4. Recall measurement bugs are invisible. If ground truth and index disagree on tie-breaking among equidistant points, recall looks slightly low forever. Test with deliberate ties.
5. Building at n=10⁶ in Python is a multi-hour job. Do milestone 8 before E5, or E5 will eat a week of wall-clock.

Scope Boundaries

In scope: in-memory, single-threaded, one metric, graph-based indexes.

Out of scope: disk-resident indexes (P03); distributed sharding (P05); GPU search; filtering (P03); IVF and tree-based families beyond a paragraph in the report; multi-vector or late-interaction retrieval; learned indexes.

Permitted-library line: numpy for array storage and BLAS distance batches, yes. hnswlib/faiss/scann only as an external comparison in E12 — never as a component. heapq is fine; it is a priority queue, not the mechanism under study.

Deliverables

1. annindex/ — brute force, NSW, HNSW, persistence, CLI sweep runner
2. REPORT.md with the recall/QPS Pareto curve, the two-factor decomposition, and the hnswlib comparison including the gap
3. Notebook entries for E5, E7, E8
4. A reusable ANN benchmark harness — this is the artifact with independent value. It should accept any index exposing add/search and emit the standard curve
5. Raw sweep data as JSON

Exit Criteria

• recall@10 ≥ 0.95 at some efSearch on a stated dataset, verified against exact brute force
• The recall/QPS curve dominates brute force at some n you measured, and you can state that n and explain it via the two-factor model
• E7 complete: clustered vs uniform, with the ceiling effect measured and explained
• E8 complete: Algorithm 4 implemented and its effect on the E7 ceiling measured
• All nine correctness tests pass, including reachability
• hnswlib comparison run, gap reported honestly with the algorithmic/constant split
• Persistence round-trips and corruption is detected
• REPORT.md written with at least one falsified prediction

Extension Ideas

• Adaptive efSearch: predict per-query difficulty from the first few hops and set the beam width per query. If it holds recall at lower mean latency, that is a real result — see Research Directions.
• Product quantization on the graph: measure the memory/recall frontier.
• Filtered search preview: implement one filtering strategy here to feel the problem before P03 formalises it.
• Multi-threaded build with a measured scaling curve; the graph is a shared mutable structure and this is genuinely hard.

Connections

Backward: P01 gives you real embeddings with realistic RC — far better test data than random vectors, and the contrast between them is E4/E7.

Forward:

• → P03 (Vector DB): this index is P03's core. Keep the API narrow: add, search, delete, save, load.
• → P08 (Recommender): candidate retrieval calls this, not a library. Recall@k here becomes an upper bound on the recommender's recall, and quantifying that propagation is one of P08's experiments.
• → P14: the distance kernel is a memory-bound inner loop and a natural target for the tiling and SIMD work.
• → P15: an adaptive ANN policy is one of the candidate research questions.

References

• Malkov, Y. A., Yashunin, D. A. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE TPAMI 42(4), 2020.
• Malkov, Y., Ponomarenko, A., Logvinov, A., Krylov, V. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45, 2014.
• He, J., Kumar, S., Chang, S.-F. On the Difficulty of Nearest Neighbor Search. ICML 2012.
• Beyer, K., Goldstein, J., Ramakrishnan, R., Shaft, U. When Is "Nearest Neighbor" Meaningful? ICDT 1999.
• Indyk, P., Motwani, R. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. STOC 1998. The LSH origin.
• Jégou, H., Douze, M., Schmid, C. Product Quantization for Nearest Neighbor Search. IEEE TPAMI 33(1), 2011.
• Kleinberg, J. Navigation in a Small World. Nature 406, 2000. Why greedy routing works when long-range links follow the right distribution.
• Aumüller, M., Bernhardsson, E., Faithfull, A. ANN-Benchmarks. Information Systems 87, 2020.
• Johnson, J., Douze, M., Jégou, H. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data 7(3), 2021. The FAISS paper.
• Subramanya, S. J. et al. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. NeurIPS 2019. Read before P03 — it is the disk-resident answer.

P02 hands-on — Approximate nearest neighbours, block by block

Why a random graph fails, why a navigable one works, and what recall costs.

Source: handson/h02_ann.py --- run it with python3 handson/h02_ann.py
Full project spec: P02 — Approximate Nearest-Neighbour Index

This is the project where the baseline teaches more than the algorithm. Brute force is trivially correct and its cost is knowable in advance; everything an index does is buy latency by giving up recall, so the only interesting question is the exchange rate.

The file builds that comparison honestly. It measures relative contrast on the data before touching an index, because a dataset with low contrast has no nearest neighbour worth finding and no graph will rescue it. It then builds a deliberately random graph to show that connectivity alone is worthless, and only then the navigable small-world construction that makes greedy descent work.

The two-factor model in the assembly is the point of the whole exercise: it predicts the speedup from first principles and lands on the measured number.

Contents

• Block 1 — Vectors and the metric decision
• Block 2 — Relative contrast
• Block 3 — Brute force = the oracle
• Block 4 — recall@k
• Block 5 — A random graph, and why it fails
• Block 6 — NSW: edges that mean something
• Block 7 — The efSearch knob
• The assembly
• The design space
• Latency, bandwidth and the memory hierarchy
• Hardware: CPU, GPU, SSD
• Advanced algorithms and data structures
• How this connects to the rest of the track
• Failure modes at scale
• Primary sources
• Running it
• What to do with this

How to read this page

Each block below is a self-contained lego piece: it builds one mechanism, proves it works on its own, and returns what the next block needs. The code is the real source, sliced out of the script. The output underneath it is the real output, captured by running that script --- not transcribed, not idealised. Where a measurement contradicted what I expected, the contradiction is in the output and the prose says so.

The assembly at the end wires every block into one working thing and measures it.

Block 1 — Vectors and the metric decision

Teaches: normalise once, and three metrics collapse into one

The problem. Before any index exists there is a decision that silently constrains everything after it: which metric, and in what representation. Get it wrong and every recall number you produce afterwards measures the wrong question.

@block(1, "Vectors and the metric decision", "normalise once, and three metrics collapse into one")
def b1(s, show):
    def norm(x): return x / np.linalg.norm(x, axis=-1, keepdims=True)
    n, d = 8000, 48
    data = norm(rng.standard_normal((n, d), dtype=np.float32))
    q = norm(rng.standard_normal((64, d), dtype=np.float32))
    if show:
        dot = data @ q[0]
        l2 = np.linalg.norm(data - q[0], axis=1)
        ident = np.abs(l2**2 - (2 - 2*dot)).max()
        print(f"  {n} vectors, d={d}, unit norm")
        print(f"  ||a-b||^2 == 2-2<a,b>: max deviation {ident:.2e}")
        print(f"  argsort by -dot == argsort by L2: "
              f"{np.array_equal(np.argsort(-dot)[:20], np.argsort(l2)[:20])}")
        print("  so ONE distance function serves cosine, dot and L2 -- but only")
        print("  because we normalised. Skip it and rankings silently diverge.")
    return {"data": data, "q": q, "norm": norm, "n": n, "d": d}

Reading the implementation

The normalisation is not a preprocessing convenience — it is what collapses three different search problems into one. For unit vectors \(|a|=|b|=1\):

\[ |a-b|^2 = |a|^2 + |b|^2 - 2a!\cdot!b = 2 - 2a!\cdot!b \]

so Euclidean distance is a strictly decreasing function of inner product, and cosine similarity is the inner product. Ranking by any of the three gives an identical order (proofs.md P17). That is why the index can store one thing and answer all three questions.

The trap is that this equivalence holds only under normalisation. Maximum inner product search (MIPS) on un-normalised vectors is a genuinely different problem: it has no triangle inequality, so tree and graph methods lose their correctness arguments, and the standard fix is an asymmetric transformation that lifts vectors into \(d+1\) dimensions to restore a metric. If your embeddings carry magnitude information you actually want (document length, confidence), normalising discards it and you must use MIPS properly rather than pretending.

What the numbers say

Output:

  8000 vectors, d=48, unit norm
  ||a-b||^2 == 2-2<a,b>: max deviation 7.15e-07
  argsort by -dot == argsort by L2: True
  so ONE distance function serves cosine, dot and L2 -- but only
  because we normalised. Skip it and rankings silently diverge.

Beyond the toy

Float32 is the default and is usually wasteful. Distance rankings are robust to substantial quantisation — that is the entire premise of PQ (P02 deep dive) — so production systems store float16 (2× saving, negligible recall change) or 8-bit scalar quantisation (4×) for the resident copy and keep float32 only for re-ranking. Since this workload is memory-bound at ~0.25 FLOP/byte, halving the bytes very nearly halves the latency, which makes precision the highest-leverage knob in the system before any algorithmic change.

Block 2 — Relative contrast

Teaches: measure how hard your dataset is BEFORE benchmarking an index

The problem. Every ANN paper reports recall on a benchmark dataset. Almost none report whether the dataset had a findable nearest neighbour in the first place. Relative contrast is the diagnostic that tells you, and it costs one pass over the data.

@block(2, "Relative contrast", "measure how hard your dataset is BEFORE benchmarking an index")
def b2(s, show):
    data, q = s["data"], s["q"]
    def rc(data, q, k=10):
        dist = np.sqrt(np.maximum(0, 2 - 2 * (data @ q.T)))
        srt = np.sort(dist, axis=0)
        return float(np.mean(dist.mean(axis=0) / srt[0]))
    r = rc(data, q)
    if show:
        print(f"  RC = mean distance / nearest distance = {r:.3f}")
        for dd in (8, 48, 256):
            sub = s["norm"](rng.standard_normal((3000, dd), dtype=np.float32))
            sq = s["norm"](rng.standard_normal((32, dd), dtype=np.float32))
            print(f"    d={dd:>4}: RC={rc(sub, sq):.3f}")
        print("  RC falls toward 1 with dimension: every point equidistant, no")
        print("  gradient for greedy search. RC predicts difficulty; d does not.")
    return {"rc": r}

Reading the implementation

Relative contrast is the ratio of the mean distance to the nearest distance:

\[ C = \frac{\bar{d}}{d_{\min}} \]

As \(C \to 1\), every point is roughly equidistant from the query and there is no nearest neighbour to find — not because the algorithm is weak but because the data carries no signal at that dimensionality. He, Kumar and Chang showed that the difficulty of nearest-neighbour search is essentially a function of this number, and that it degrades with dimension for any distribution whose components are independent.

The implementation detail that matters: compute this on the full data with the actual metric. An earlier version of this file computed contrast on a 2000-point subsample using similarity ratios and returned ≈1.30 for every configuration — a broken metric that looked plausible. The fix was to use proper Euclidean distances over the whole set, and it changed the conclusions.

What the numbers say

Output:

  RC = mean distance / nearest distance = 1.439
    d=   8: RC=3.693
    d=  48: RC=1.410
    d= 256: RC=1.130
  RC falls toward 1 with dimension: every point equidistant, no
  gradient for greedy search. RC predicts difficulty; d does not.

Beyond the toy

• Intrinsic dimension is the companion diagnostic. Real embeddings from a trained model occupy a manifold of far lower dimension than their ambient size — a 768-dim CLIP embedding might have intrinsic dimension 20--40 — which is precisely why ANN works at all on real data and fails on uniform random data of the same width. Estimate it with the two-NN or MLE estimators before concluding an index is broken.
• The synthetic-data trap. The clustered generator in this file originally produced uniform data because the cluster spread \(\sigma\sqrt{d} = 2.0\) swamped unit-norm centres, giving contrast 1.393 against uniform's 1.356. Any synthetic benchmark needs this check, and the file now warns when \(\sigma\sqrt{d} > 0.7\).
• Practical use. If contrast is near 1 on your production queries, the correct action is not to tune ef — it is to fix the embedding, add a re-ranking stage with a richer model, or accept that top-k is meaningless and return a diversified set instead.

Block 3 — Brute force = the oracle

Teaches: you cannot measure recall without exact ground truth

The problem. Recall is defined against exact ground truth. Without an oracle there is no number, and "it returns plausible results" is not a measurement. This block builds the oracle and, incidentally, the baseline that the index must beat.

@block(3, "Brute force = the oracle", "you cannot measure recall without exact ground truth")
def b3(s, show):
    data, q = s["data"], s["q"]
    def brute(qv, k=10):
        sims = data @ qv
        idx = np.argpartition(-sims, k)[:k]
        return idx[np.argsort(-sims[idx])].tolist()
    t0 = time.perf_counter()
    truth = [brute(v) for v in q]
    ms = (time.perf_counter() - t0) / len(q) * 1e3
    if show:
        naive = sorted(range(s["n"]), key=lambda i: -float(data[i] @ q[0]))[:10]
        print(f"  agrees with a naive sort: {naive == truth[0]}")
        print(f"  {ms:.3f} ms/query, {1000/ms:>6.0f} qps, recall 1.0 BY CONSTRUCTION")
        print(f"  cost model: {s['n']}x{s['d']} = {s['n']*s['d']:,} MACs, "
              f"{s['n']*s['d']*4/1e6:.1f} MB streamed -- one BLAS call, prefetchable")
    return {"brute": brute, "truth": truth, "brute_ms": ms}

Reading the implementation

Brute force is \(O(Nd)\) per query with perfect recall and, crucially, a known cost — you can compute it exactly in advance from the corpus size and dimension, which no approximate method allows. It is also embarrassingly parallel, cache- friendly (a sequential scan, unlike the graph's pointer chasing), and trivially correct.

That combination is why brute force is not a strawman. On a GPU, scanning 1M × 768 fp16 vectors is 1.5 GB at ~3 TB/s ≈ 0.5 ms — faster than most CPU ANN implementations, and exact. The regime where an index is genuinely necessary starts higher than most people assume, and the honest version of "we need a vector database" is usually "we need one above N vectors, and here is N".

What the numbers say

Output:

  agrees with a naive sort: True
  0.129 ms/query,   7776 qps, recall 1.0 BY CONSTRUCTION
  cost model: 8000x48 = 384,000 MACs, 1.5 MB streamed -- one BLAS call, prefetchable

Beyond the toy

The ground truth itself becomes a cost at scale: computing exact top-k for 10k queries against 100M vectors is \(10^{12}\) distance computations. Standard practice is to compute it once on a GPU and ship it with the benchmark, which is what ANN-Benchmarks and the BigANN challenge datasets do. A benchmark that recomputes ground truth with an approximate method — and it happens — measures agreement between two approximations, not recall.

Block 4 — recall@k

Teaches: the contract: what exactly did approximation cost?

The problem. "Recall" is used loosely enough to be meaningless. This block pins it down, because every later number on this page is denominated in it.

@block(4, "recall@k", "the contract: what exactly did approximation cost?")
def b4(s, show):
    def recall_at_k(got, want, k):
        return len(set(got[:k]) & set(want[:k])) / k
    if show:
        print(f"  perfect: {recall_at_k([1,2,3],[1,2,3],3):.2f}   "
              f"two of three: {recall_at_k([1,2,9],[1,2,3],3):.2f}   "
              f"none: {recall_at_k([7,8,9],[1,2,3],3):.2f}")
        print("  always against EXACT ground truth, same metric, same data, stated k")
    return {"recall_at_k": recall_at_k}

Reading the implementation

\[ \text{recall@}k = \frac{|,\text{returned}_k \cap \text{true}_k,|}{k} \]

Three details that separate a usable metric from a misleading one:

• Set intersection, not order. Recall@10 does not care whether the true nearest neighbour came back at rank 1 or rank 10. If order matters for your product, measure NDCG or MRR instead — they are different questions and a system can be excellent at one and poor at the other.
• Ties. With duplicate or near-duplicate vectors, "the true top-k" is not unique and naive recall under-reports. Benchmarks handle this by comparing against a distance threshold rather than an ID set.
• The denominator is \(k\), not the number returned. A method that returns 3 results of which all 3 are correct has recall@10 of 0.3, not 1.0. This is exactly the post-filter failure mode in P03, and defining recall this way is what makes it visible.

What the numbers say

Output:

  perfect: 1.00   two of three: 0.67   none: 0.00
  always against EXACT ground truth, same metric, same data, stated k

Beyond the toy

Recall@k against exact neighbours is an intrinsic metric — it measures the index against itself, not against the task. A retrieval system with recall@10 = 0.85 may be indistinguishable from one at 0.99 in end-to-end product terms, because the ranker downstream reorders anyway (P08) and because the embedding's own error dwarfs the index's. Always pair the intrinsic number with an extrinsic one before spending weeks moving it.

Block 5 — A random graph, and why it fails

Teaches: the naive design, measured, so the fix is motivated

The problem. It is tempting to think a graph search works because the graph is connected. This block builds a connected graph with the right degree and the right number of edges, and shows it produces almost nothing — which is what makes the next block's construction motivated rather than arbitrary.

@block(5, "A random graph, and why it fails", "the naive design, measured, so the fix is motivated")
def b5(s, show):
    data, n = s["data"], s["n"]
    deg = 16
    g = [rng.choice(n, deg, replace=False).tolist() for _ in range(n)]
    def greedy(qv, graph, entry=0, ef=32):
        seen = {entry}; d0 = 1 - float(data[entry] @ qv)
        cand = [(d0, entry)]; res = [(-d0, entry)]; nd = 1
        while cand:
            d, node = heapq.heappop(cand)
            if -res[0][0] < d and len(res) >= ef: break
            for nb in graph[node]:
                if nb in seen: continue
                seen.add(nb); dn = 1 - float(data[nb] @ qv); nd += 1
                if len(res) < ef or dn < -res[0][0]:
                    heapq.heappush(cand, (dn, nb)); heapq.heappush(res, (-dn, nb))
                    if len(res) > ef: heapq.heappop(res)
        return [i for _, i in heapq.nsmallest(10, [(-a, b) for a, b in res])], nd
    rec = np.mean([s["recall_at_k"](greedy(v, g)[0], t, 10)
                   for v, t in zip(s["q"], s["truth"])])
    if show:
        print(f"  {deg} RANDOM edges per node, greedy beam ef=32")
        print(f"  recall@10 = {rec:.4f}   <- near useless, and that is the point")
        print("  a random graph has no locality, so greedy descent has nothing to")
        print("  descend. The fix is not a bigger beam; it is better EDGES.")
    return {"greedy": greedy, "random_recall": float(rec)}

Reading the implementation

greedy is a best-first search with a bounded candidate set: pop the closest unexpanded node, evaluate its neighbours, keep the best ef seen. Two lines carry the algorithm:

• if -res[0][0] < d and len(res) >= ef: break — the termination rule. Stop when the closest unexplored candidate is farther than the worst result already held. This is the standard best-first bound, and it is what makes the search adaptive: easy queries terminate early, hard ones explore more.
• nd += 1 counts distance computations. That counter is the real cost metric — wall-clock time varies with implementation and machine, but distance computations are the invariant that lets you compare an index against brute force's \(N\) honestly. Reporting speedup in terms of nd is what makes P15's capacity model possible.

What the numbers say

Output:

  16 RANDOM edges per node, greedy beam ef=32
  recall@10 = 0.0609   <- near useless, and that is the point
  a random graph has no locality, so greedy descent has nothing to
  descend. The fix is not a bigger beam; it is better EDGES.

Beyond the toy

Greedy descent on a graph is a local algorithm: it only ever moves downhill in distance, so it terminates at a local minimum of the distance function restricted to the graph. A random graph has no correlation between edge structure and geometry, so almost every node is a local minimum and the search stops immediately. The fix is therefore not more search (a bigger ef barely helps — worth measuring) but better edges.

The theoretical frame is Kleinberg's small-world result: a lattice augmented with long-range links whose length distribution follows \(P(u\to v) \propto d(u,v)^{-r}\) is navigable by a greedy decentralised algorithm in \(O(\log^2 n)\) steps only when \(r\) equals the lattice dimension. Too few long links and you cannot cross the space; too many and you cannot home in. NSW's insertion procedure produces that distribution approximately and for free, which is the elegance of the next block.

Block 6 — NSW: edges that mean something

Teaches: insert by searching what you have built so far

The problem. Build a graph whose edges encode geometry, using nothing but the search procedure you already have. The construction is three lines and the reason it works is a genuinely deep result.

@block(6, "NSW: edges that mean something", "insert by searching what you have built so far")
def b6(s, show):
    data, n = s["data"], s["n"]
    M, efC = 12, 60
    graph = [[] for _ in range(n)]
    order = rng.permutation(n)
    entry = int(order[0])
    for count, node in enumerate(order[1:], 1):
        node = int(node)
        found, _ = s["greedy"](data[node], graph, entry, efC)
        cands = sorted(found, key=lambda i: 1 - float(data[i] @ data[node]))[:M]
        graph[node] = cands
        for c in cands:
            graph[c].append(node)
            if len(graph[c]) > 2 * M:               # degree cap
                dd = data[graph[c]] @ data[c]
                graph[c] = [graph[c][i] for i in np.argsort(-dd)[:2 * M]]
    if show:
        edges = sum(len(x) for x in graph)
        print(f"  M={M} efConstruction={efC}, {edges/n:.1f} edges/node")
        print("  early insertions land in a near-empty graph, so their edges are")
        print("  LONG. Those accidental long links are the small-world property.")
    return {"graph": graph, "entry": entry, "M": M}

Reading the implementation

The insertion rule is: to insert a point, search the graph you have built so far, and link to what you find. That single recursive idea produces navigability without any global structure:

• Points inserted early, when the graph is sparse and the search is inaccurate, get long-range links — they connect regions that are far apart.
• Points inserted late, when the graph is dense and the search is accurate, get short-range links — they refine the local neighbourhood.

The result is a length distribution across scales, which is exactly Kleinberg's navigability condition arrived at by accident of construction. Nobody computes it; it falls out of using the search to build the index.

• M is the degree bound and the memory knob: M × 4 bytes per node for the edge list. It is also the recall knob that most benchmarks under-report — sweeping M moves the memory/recall curve far more than sweeping ef moves the latency/recall one.
• Edges are added bidirectionally, and this matters: a directed graph built this way has poor in-degree for early nodes and the search cannot get back out of a region it descends into.
• HNSW's addition on top of this is the layer hierarchy — long links in upper layers, taken first — which reduces the number of distance computations to reach the right region, not the number of hops.

What the numbers say

Output:

  M=12 efConstruction=60, 17.1 edges/node
  early insertions land in a near-empty graph, so their edges are
  LONG. Those accidental long links are the small-world property.

Beyond the toy

• Pruning is the missing piece. Real HNSW does not keep the M nearest neighbours; it applies a heuristic that keeps an edge \(u\to v\) only if no already-selected \(w\) is closer to \(v\) than \(u\) is. That is a relative-neighbourhood-graph relaxation, and it produces diverse edges — one per direction rather than M edges into the same dense cluster. Without it, recall on clustered data is substantially worse.
• Construction cost is \(O(N \log N \cdot M)\) distance computations, which for 100M vectors is hours on many cores. This makes index build a batch job (P06) and makes incremental insertion valuable, which is why the NSW-style construction — which is naturally incremental — beat the tree methods that require a global build.
• The entry point matters more than it looks. A fixed entry point means every search starts in the same place and the nodes near it are traversed on every query — hot in cache, but also a concentration of load. HNSW's top layer solves this; some implementations use multiple random entry points.

Block 7 — The efSearch knob

Teaches: recall is concave in ef; pick the recall FIRST

The problem. ef is the dial between latency and recall, and its shape decides how you configure the system. This block measures the curve rather than assuming it, and the shape has a direct operational consequence.

@block(7, "The efSearch knob", "recall is concave in ef; pick the recall FIRST")
def b7(s, show):
    if show:
        print(f"  {'ef':>5}{'recall@10':>11}{'ms':>9}{'dists/q':>10}{'vs brute':>10}")
        for ef in (10, 32, 64, 128):
            t0 = time.perf_counter(); recs = []; nds = 0
            for v, t in zip(s["q"], s["truth"]):
                got, nd = s["greedy"](v, s["graph"], s["entry"], ef)
                recs.append(s["recall_at_k"](got, t, 10)); nds += nd
            ms = (time.perf_counter() - t0) / len(s["q"]) * 1e3
            print(f"  {ef:>5}{np.mean(recs):>11.4f}{ms:>9.3f}"
                  f"{nds/len(s['q']):>10.0f}{s['brute_ms']/ms:>9.2f}x")
    return {}

Reading the implementation

ef (the search-time beam width) bounds the candidate set: the search keeps the ef best nodes seen and terminates when no unexplored candidate can improve them. Larger ef means more distance computations and a lower chance of getting stuck in a local minimum.

The critical property is that recall is concave in ef — the first doubling buys a lot, the fourth buys almost nothing, while cost grows roughly linearly. The operational consequence is the reverse of how people usually configure it:

Pick the recall you need first, then find the smallest ef that reaches it. Configuring ef to a latency budget and reporting whatever recall results is how systems end up paying 4× the cost for 1% of recall.

What the numbers say

Output:

     ef  recall@10       ms   dists/q  vs brute
     10     0.3344    0.223       263     0.58x
     32     0.6219    0.540       595     0.24x
     64     0.7891    0.875       978     0.15x
    128     0.9328    1.540      1672     0.08x

Beyond the toy

• ef is a per-query dial, not a global one. Since the search terminates adaptively, you can raise ef for queries the system judges hard (low top-1 similarity, high tail-index) and lower it for easy ones. That is real, deployed practice and it buys a better recall-per-millisecond than any global setting.
• The two-factor speedup model in the assembly is what makes this predictable rather than empirical: speedup is (fraction of vectors examined) × (per-vector cost ratio), and predicting 0.15× against a measured 0.15× is what turns a benchmark into a model you can extrapolate with.
• Recall is not the tail. The mean recall at ef=64 hides that some queries return nothing useful. Report the distribution — recall@10 at p10 across queries — because a system with mean recall 0.9 and 5% of queries at recall 0.0 is a very different product from one with uniform 0.9.

The assembly

Every block above, wired together into one working system:

def assembly(s):
    print("\nThe seven blocks are an ANN index. Now the measurement that matters.\n")
    ef = 64
    t0 = time.perf_counter(); recs = []; nds = 0
    for v, t in zip(s["q"], s["truth"]):
        got, nd = s["greedy"](v, s["graph"], s["entry"], ef)
        recs.append(s["recall_at_k"](got, t, 10)); nds += nd
    ms = (time.perf_counter() - t0) / len(s["q"]) * 1e3
    dpq = nds / len(s["q"])
    algo = s["n"] / dpq
    const = (ms * 1e6 / dpq) / (s["brute_ms"] * 1e6 / s["n"])
    print(f"  at efSearch={ef}: recall {np.mean(recs):.4f}, {ms:.3f} ms/query")
    print(f"  random-graph recall was {s['random_recall']:.4f} -> NSW is "
          f"{np.mean(recs)/max(s['random_recall'],1e-9):.0f}x better on the SAME search code.\n")
    print("  THE TWO-FACTOR MODEL -- decompose before you tune anything:")
    print(f"    algorithmic win : {s['n']:,} / {dpq:.0f} distances = {algo:>7.1f}x fewer")
    print(f"    constant factor : {ms*1e6/dpq:>7.1f} ns/dist (python) vs "
          f"{s['brute_ms']*1e6/s['n']:.1f} ns (BLAS) = {const:>6.1f}x slower each")
    print(f"    predicted speedup: {algo:.1f} / {const:.1f} = {algo/const:.2f}x")
    print(f"    measured speedup : {s['brute_ms']/ms:.2f}x")
    print("\n  The algorithm is RIGHT and the implementation is WRONG. Those are")
    print("  different bugs. Only the distance counter can tell you which you have.")
    print(f"\n  Dataset difficulty: RC = {s['rc']:.3f}. Report it with every recall")
    print("  number, or the result does not transfer to anyone else's corpus.")
    print("\n  Built: metric choice -> RC -> oracle -> recall -> random graph ->")
    print("  NSW -> ef sweep -> the decomposition.")
    print("  Missing, and on the project page: HNSW layers (m6), Algorithm 4 (m7),")
    print("  a compiled inner loop (m8), persistence (m9), hnswlib comparison (E12).")

Output:

The seven blocks are an ANN index. Now the measurement that matters.

  at efSearch=64: recall 0.7891, 0.895 ms/query
  random-graph recall was 0.0609 -> NSW is 13x better on the SAME search code.

  THE TWO-FACTOR MODEL -- decompose before you tune anything:
    algorithmic win : 8,000 / 978 distances =     8.2x fewer
    constant factor :   915.3 ns/dist (python) vs 16.1 ns (BLAS) =   56.9x slower each
    predicted speedup: 8.2 / 56.9 = 0.14x
    measured speedup : 0.14x

  The algorithm is RIGHT and the implementation is WRONG. Those are
  different bugs. Only the distance counter can tell you which you have.

  Dataset difficulty: RC = 1.439. Report it with every recall
  number, or the result does not transfer to anyone else's corpus.

  Built: metric choice -> RC -> oracle -> recall -> random graph ->
  NSW -> ef sweep -> the decomposition.
  Missing, and on the project page: HNSW layers (m6), Algorithm 4 (m7),
  a compiled inner loop (m8), persistence (m9), hnswlib comparison (E12).

The design space

Every ANN index is a bet about where you can afford to lose information. The four families make different bets, and they fail differently.

In practice the production answer is a composite: IVF to narrow, PQ to compress, a graph over centroids to route, exact re-ranking on the raw vectors of the top few hundred. FAISS's IVF65536_HNSW32,PQ64 is that sentence as a factory string.

Why the graph works at all

Greedy descent on a proximity graph is a decentralised search: at each step, move to the neighbour closest to the query. It terminates at a local minimum, so the entire design problem is making local minima rare. NSW achieves that by inserting nodes in random order and linking each to its M nearest already-inserted nodes — long-range links form early while the graph is sparse, short-range links late, producing a small-world graph of \(O(\log N)\) diameter. HNSW adds explicit layers so long hops are taken first, cutting the number of distance computations rather than the number of hops.

Block 3's result — a random graph gives 0.06 recall — is the control that proves connectivity is not the active ingredient. Navigability is.

Latency, bandwidth and the memory hierarchy

Graph search is pointer chasing, the worst access pattern the memory hierarchy has. Each hop is a dependent load: you cannot prefetch hop \(k+1\) until hop \(k\) resolves.

Using this machine's measured constants (numbers.md):

A search touching 600 distinct vectors of 128 dims × 4 B reads ~300 KB scattered across memory: ~600 line-missing loads at 121 ns ≈ 73 µs of pure latency against perhaps 5 µs of arithmetic. The search is latency-bound — not bandwidth-bound and nowhere near compute-bound — which is why the roofline efficiency in P15 comes out below 1%.

Three consequences follow directly:

1. Layout dominates. Storing vectors in visit order, or inlining a compressed code beside each edge list, converts random reads into sequential ones. This makes quantisation a latency optimisation, not merely a memory one.
2. TLB reach matters. A 100 GB index with 4 KiB pages needs 25M page-table entries; a 1536-entry TLB covers 6 MB. Huge pages (2 MiB) extend reach 512× and are routinely worth 10--30% — P12 block 2's mechanism applied to a data structure.
3. Batching queries helps for a non-obvious reason. It barely raises arithmetic intensity; what it creates is memory-level parallelism, many independent dependent-load chains in flight at once, which is the only way to hide 121 ns.

Hardware: CPU, GPU, SSD

• CPU is the natural home for graph search: branchy, pointer-heavy, latency-sensitive, helped by a large out-of-order window and hardware prefetchers — which the Sattolo-cycle trap in numbers.md §14 shows are easily fooled into flattering a benchmark.
• GPU is the natural home for brute force. A 1M × 768 fp16 matrix is 1.5 GB; scanning it at ~3 TB/s takes 0.5 ms. Below a few million vectors, GPU brute force beats CPU ANN on latency and is exact — which is most of why FAISS-GPU exists. Graph traversal maps badly to SIMT because each query diverges.
• SSD changes the algorithm, not the parameters. DiskANN/Vamana prune with an α-RNG rule to get a small diameter, keep PQ codes of everything in RAM to guide the walk, and read full vectors for only a few hundred candidates. That design exists because NVMe random reads are ~50 µs and parallel (deep queues), whereas HDD random reads are 10 ms and effectively serial.

Advanced algorithms and data structures

• Product quantisation splits a \(d\)-dim vector into \(m\) subvectors, k-means each subspace to 256 centroids, stores \(m\) bytes. Distance becomes a sum of \(m\) lookups in an L1-resident table. OPQ learns a rotation first, because PQ assumes subspace independence and raw embedding dimensions are not independent.
• ScaNN's anisotropic loss notes that for maximum-inner-product search, quantisation error parallel to the query matters far more than orthogonal error, and weights training accordingly — a rare case where changing the loss, not the structure, buys large recall.
• Relative contrast (He, Kumar & Chang) is what block 2 computes: \(C = \bar{d}/d_{\min}\). As \(C \to 1\) no algorithm can separate the nearest neighbour from the crowd, because the data has no signal. Measure it before blaming an index.
• α-RNG pruning — keep edge \(u \to v\) unless some \(w\) is closer to both — is a relative-neighbourhood-graph relaxation that bounds out-degree while preserving navigability. It is the theoretical spine under both Vamana and HNSW's pruning heuristic.

How this connects to the rest of the track

• P03 wraps this index in a database: filters, persistence, planning.
• P08 uses it as a candidate generator; its block 7 shows the index's recall@C is a hard ceiling on the recommender's recall@k.
• P01's attention is a soft version of the same lookup and meets the same high-dimensional contrast problem.
• P14 explains the ≈0.25 FLOP/byte intensity that makes this memory-bound.
• P04's Bloom filter is the same idea as a PQ code: a cheap approximate test in fast memory that avoids an expensive exact one in slow memory.

Failure modes at scale

• Deletions break connectivity. Tombstoning without repair slowly disconnects regions; most systems rebuild segments instead (P03, P04 compaction).
• Distribution shift after an embedding upgrade invalidates centroids and graph simultaneously. There is no incremental fix, only a rebuild.
• Recall measured on indexed vectors overstates production recall, because real queries are out-of-distribution relative to the corpus.
• The p99 is not p50 × constant. Hop counts have a long tail; a query landing in a sparse region takes 5--10× the median.

Primary sources

• Malkov & Yashunin, Efficient and Robust ANN Search Using HNSW (2016).
• Jégou, Douze & Schmid, Product Quantization for NN Search (2011).
• Subramanya et al., DiskANN (NeurIPS 2019) — the SSD design.
• Guo et al., Anisotropic Vector Quantization (ScaNN, ICML 2020).
• He, Kumar & Chang, On the Difficulty of Nearest Neighbor Search (ICML 2012).
• Johnson, Douze & Jégou, Billion-scale Similarity Search with GPUs (2017).

Running it

python3 handson/h02_ann.py            # every block, then the assembly
python3 handson/h02_ann.py --block 3  # just block 3 and its prerequisites
python3 handson/h02_ann.py --quiet    # the assembly only

What to do with this

The parameter that matters most is the one this file leaves at a default. Sweep M (edges per node) rather than ef and you will find the memory/recall curve that most benchmark tables omit entirely. Then re-run the contrast measurement on a real embedding set --- CLIP or a sentence encoder --- and compare it with the synthetic number here. If the real contrast is lower, every recall figure you have read about that dataset is easier than it looks.

Milestones, experiments, readings and exit criteria for this project: P02 — Approximate Nearest-Neighbour Index.

P03 — Small Vector Database

Run it first. There is a companion page that builds this project's machinery as numbered, independently runnable blocks and then assembles them into one measured system: P03 hands-on — block by block (handson/h*.py). Every number on it was produced by running the code. Read it alongside the milestones below.

Medium · 88 hours · Weeks 27–34 · Stage 2 · Python with a Rust storage layer

Table of Contents

• The Loop, Instantiated
• Why This Project Matters
• Prerequisites
• Duration and Size
• Central Technical Questions
• Architecture
• Showcase — The Query Planner, In Three Lines
• Implementation Milestones
• Concepts To Study
• Primary-Source Readings
• Experiments
• Benchmarks and Metrics
• Correctness Tests
• Failure Tests
• Expected Difficulties
• Scope Boundaries
• Deliverables
• Exit Criteria
• Extension Ideas
• Connections
• References

The Loop, Instantiated

Why This Project Matters

The gap between "I have an HNSW index" and "I have a vector database" is where every real engineering problem lives, and it is a gap most people never cross because the index is the interesting part.

This project's real job in the journey is to make you want Project 4. You will build the naive persistence layer — append-only file, full index rebuild on start — and measure its recovery time at one million vectors. It will be minutes. That number is what makes sparse indexes, Bloom filters, and compaction feel like solutions to a problem you have rather than features in a paper you read. This is the roadmap's most deliberate application of "naive design first", and it costs about six hours of rework on purpose.

The second reason: filtering is where vector search actually breaks in production, and you already ship filtered vector search on OpenSearch. After this project you will know exactly why your p99 spikes when a filter is narrow.

Prerequisites

• P02 complete — this is a hard dependency; the index is the core of the database
• File I/O: read/write/fsync, what the page cache is, what mmap actually does
• Basic concurrency: mutexes, reader-writer locks, and why a graph index is hostile to both

Duration and Size

Medium, 88 hours, 8 weeks.

Central Technical Questions

1. What does "durable" mean, precisely? After which system call is a write recoverable, and what exactly does fsync guarantee on your filesystem?
2. Why can't you update a graph index in place? Deletion in HNSW is not a matter of removing a node — trace why.
3. Pre-filter or post-filter? There is a selectivity threshold. Derive it, then measure where the derivation is wrong.
4. What does the filter do to graph connectivity? A filtered graph walk is a walk on a subgraph you did not build, and that subgraph may be disconnected.
5. What is your consistency model? Can a search see a half-inserted vector? Write it down as a sentence before you write the code.
6. What is your storage amplification, and where did it go — tombstones, alignment, the graph, or the metadata?

Architecture

Write your naive design first.

                    ┌──────────────── write path ────────────────┐
  insert(id,vec,md) ─► WAL (append + fsync policy) ─► memtable ──┼─► flush ─► segment N
                                                     (vectors +  │            ├ vectors.bin  (mmap, fixed stride)
                                                      metadata)  │            ├ meta.bin     (id → offset, attrs)
                                                                 │            ├ graph.bin    (HNSW adjacency)
                                                                 │            └ tomb.bin     (deleted ids)
                    ┌──────────────── read path ─────────────────┘
  search(q,k,filter) ─► planner ─┬─ pre-filter:  build allowed-set, walk graph restricted to it
                                 └─ post-filter: search top-K, filter, K = k/selectivity
                                        │
                                 merge across segments ─► apply tombstones ─► top-k

The filtering problem, derived

This is the section worth the most.

Post-filtering runs an unfiltered ANN search for the top \(K\), then discards non-matching results. If the filter is independent of similarity and selects a fraction \(s\) of the corpus, the expected number of surviving results is \(Ks\). To return \(k\) results you need

\[ K \ge k/s \]

Computed for \(k = 10\) over a 1M-vector corpus:

At \(s = 10^{-4}\) you are searching with efSearch ≥ 100,000, which is not a graph walk any more — it is brute force with a worse constant factor. This is the p99 cliff you have seen in production. And the table understates it: the independence assumption fails badly when the filter correlates with similarity (e.g. filtering to one publisher when that publisher's articles cluster in embedding space), and in the adversarial case no \(K\) suffices because all matching items lie outside the unfiltered top-\(K\) entirely.

Pre-filtering restricts the graph walk to matching nodes. It has no over-fetch problem, but it introduces a worse one: the induced subgraph may be disconnected. Your carefully built navigable graph guaranteed connectivity over all \(n\) nodes; it guarantees nothing about the subgraph induced by an arbitrary predicate. Greedy search on a disconnected subgraph reaches one component and stops — the same failure mode you diagnosed in P02's clustered-data ceiling, now caused by a query rather than by the data.

Brute force over the filtered set costs \(O(sn)\) and is exact. At \(s = 10^{-4}\) on 1M vectors that is 100 distance computations — faster than either alternative and perfectly accurate.

So the planner has three strategies and the crossovers are empirical. Deriving the crossover and then measuring where the derivation is wrong is the central experiment of this project.

Why deletion is hard

An HNSW node is referenced by the adjacency lists of its neighbours. Removing it requires either patching every in-edge (you do not have a reverse index, and building one doubles memory) or leaving a dangling reference. So every practical implementation uses tombstones: mark deleted, keep the node in the graph as a routing waypoint, filter at result time.

The consequences you must measure:

• Recall drifts down with churn, because tombstoned nodes occupy beam slots without producing results. Effective efSearch falls to roughly \(ef \cdot (1 - \text{tombstone fraction})\).
• Space amplification grows monotonically until compaction.
• Compaction means rebuilding the graph for that segment, which is the most expensive operation in the system. Its cost is why segment size is a real design decision and not an arbitrary constant.

Showcase — The Query Planner, In Three Lines

Before eight weeks of vector database, spend ten minutes on the decision the planner exists to make. Costs are the measured ones from numbers: 13.3 ns per BLAS distance, 899 ns per interpreted graph hop.

# P03 -- the filtering planner, decided by arithmetic rather than by taste.
import math
N, k = 1_000_000, 10
COST_PER_DIST_NS, GRAPH_HOP_NS = 13.3, 899.0   # measured, numbers.md
for s in (0.5, 0.1, 0.01, 0.001, 0.0001):
    post_K = math.ceil(k/s)                    # over-fetch, then discard
    post   = post_K * GRAPH_HOP_NS             # graph walk cost ~ ef
    brute  = s*N * COST_PER_DIST_NS            # exact scan of the matching set
    winner = "post-filter" if post < brute else "BRUTE FORCE (exact!)"
    print(f"s={s:<8} post-filter needs K={post_K:>7,} ({post/1e6:>7.2f} ms)   "
          f"brute over {s*N:>8,.0f} items ({brute/1e6:>6.2f} ms)   -> {winner}")
# solve for the crossover: (k/s)*HOP == s*N*DIST  =>  s = sqrt(k*HOP/(N*DIST))
xover = math.sqrt(k*GRAPH_HOP_NS/(N*COST_PER_DIST_NS))
print(f"\\nCrossover, solved: s = sqrt(k*HOP/(N*DIST)) = {xover:.4f}")
print("Below ~2.6% selectivity, EXACT brute force over the filtered set beats the")
print("approximate index. The planner is three lines of arithmetic, and a system")
print("without one falls off a cliff exactly here.")

s=0.5      post-filter needs K=     20 (   0.02 ms)   brute over  500,000 items (  6.65 ms)   -> post-filter
s=0.1      post-filter needs K=    100 (   0.09 ms)   brute over  100,000 items (  1.33 ms)   -> post-filter
s=0.01     post-filter needs K=  1,000 (   0.90 ms)   brute over   10,000 items (  0.13 ms)   -> BRUTE FORCE (exact!)
s=0.001    post-filter needs K= 10,000 (   8.99 ms)   brute over    1,000 items (  0.01 ms)   -> BRUTE FORCE (exact!)
s=0.0001   post-filter needs K=100,000 (  89.90 ms)   brute over      100 items (  0.00 ms)   -> BRUTE FORCE (exact!)
\nCrossover, solved: s = sqrt(k*HOP/(N*DIST)) = 0.0260
Below ~2.6% selectivity, EXACT brute force over the filtered set beats the
approximate index. The planner is three lines of arithmetic, and a system
without one falls off a cliff exactly here.

The third strategy is the one people forget. Below ~2.6% selectivity, an exact scan of the filtered set beats the approximate index — faster and correct. A planner that only knows pre- and post-filtering is missing the option that wins the hardest case. This is E3 in miniature.

Implementation Milestones

Concepts To Study

• Durability primitives: write vs fsync vs fdatasync; the page cache; write barriers; why a successful write() guarantees nothing
• Write-ahead logging: the log-before-data rule and why it is sufficient for crash-atomicity
• mmap: page faults as the loading mechanism, the OS as your buffer pool, and the reasons mmap is a contested choice for databases
• Append-only and immutability: why immutable segments make concurrency easy and space accounting hard
• Tombstones and compaction: logical vs physical deletion
• Segment/LSM-adjacent layout: why databases split into many immutable files
• Snapshot isolation: readers see a consistent version; how versioning implements it
• Query planning: cardinality estimation, and why a wrong estimate is worse than no plan
• Storage amplification: bytes on disk / bytes of live data, and every place it hides
• Checksums: CRC32C vs xxHash; per-block vs per-file

Primary-Source Readings

Budget: 11 hours.

Experiments

E3 is the project's centrepiece. You have a derivation predicting the post-filter over-fetch; you have a mechanism predicting pre-filter degradation; the crossovers are where derivation meets reality.

E12 is the most production-relevant. Steady-state p99 with no compaction running is a number that does not exist in production.

Benchmarks and Metrics

Correctness Tests

1. Crash consistency. kill -9 at ≥20 randomised points during a write workload; after recovery, every acknowledged write is present and no unacknowledged write appears. Automate this — it is the most valuable test in the project.
2. Read-your-writes within a session, at the stated consistency level.
3. Deleted vectors never returned, at any efSearch, before or after compaction.
4. Filter correctness: results satisfy the predicate, 100%, all three strategies.
5. Brute-force agreement: for small n, filtered search matches filtered brute force exactly at high efSearch.
6. Snapshot isolation: a reader holding a snapshot sees a stable view while a writer inserts and deletes underneath it.
7. Checksum detection: flip a bit in every file type; each is detected, not silently served.
8. Idempotent recovery: recover twice, get identical state.
9. Format versioning: an old-version file is rejected with a clear error, not misparsed.
10. Compaction preserves semantics: full query-result equality before and after, modulo tombstoned ids.

Failure Tests

Expected Difficulties

1. You will underestimate crash testing. Randomised kill -9 harnesses take a day to build and find bugs nothing else finds. Build it at milestone 2, not milestone 11.
2. Pre-filtering is much harder than it sounds. A filter-aware walk needs a cheap membership test inside the innermost loop, and a bitmap over segment-local ordinals is usually the only thing fast enough.
3. mmap makes memory accounting confusing. RSS is not your memory usage; the page cache is shared and evictable. Report both, and know which one the OOM killer looks at.
4. Concurrency with a mutable graph is genuinely hard. Mitigation: immutable segments plus a small mutable head. That is the design; do not fight it.
5. The query planner will be wrong and each misprediction will look like a performance bug. Log the estimated vs actual selectivity on every query from day one.

Scope Boundaries

In scope: single node, one collection, equality and range predicates on scalar metadata, crash recovery, compaction, snapshot-isolated readers.

Out of scope: distribution and replication (P05); SQL or any query language; transactions across multiple keys; authentication; a network protocol beyond a thin local RPC; multiple collections or schema evolution; hybrid dense+sparse retrieval; re-implementing HNSW — it is imported from P02 unchanged.

Deliverables

1. vectordb/ — embeddable library plus a CLI
2. STORAGE-FORMAT.md — byte-level layout, written before the code and updated when it drifts. This is a portfolio artifact on its own
3. REPORT.md with the E3 filtering study as its centrepiece
4. crashtest/ — the randomised kill harness, reusable in P04 and P05
5. Notebook entries for E1, E3, E10, E12
6. A recovery-time table that explicitly motivates P04

Exit Criteria

• Crash test passes at ≥20 randomised kill points with zero data loss of acknowledged writes
• E3 complete: all three strategies across six selectivities, with both crossovers identified
• Filtered recall measured and the pre-filter degradation explained by a mechanism
• Recovery time at 10⁶ vectors measured for both naive and snapshot+WAL, with the speedup stated
• Storage amplification measured and decomposed by cause
• p99 during compaction reported alongside steady-state p99
• The consistency model written as a paragraph a reviewer could attack
• REPORT.md written with a falsified prediction

Extension Ideas

• DiskANN-style disk-resident graph: index larger than RAM, with a measured RAM/recall/latency frontier. The strongest extension here.
• Filter-aware graph construction: add edges that preserve connectivity under the most common predicates (this is the Filtered-DiskANN idea). Real research territory.
• Learned selectivity estimation to improve the planner, measured against the logged mispredictions.
• Vector compression (scalar or product quantization) with a storage/recall frontier.

Connections

Backward: P02 supplies the index. P01 supplies realistic embeddings and metadata (token counts, timestamps) to filter on.

Forward:

• → P04 (LSM): your recovery-time measurement is P04's motivation. Your crash-test harness is reused directly.
• → P05 (Distributed KV): segments and snapshots become the unit of replication and rebalancing.
• → P08 (Recommender): filtered retrieval — "exclude already-seen", "last 48 hours" — is exactly the selectivity regime E3 studies, and freshness filters are narrow.
• → P15: storage and indexing choices affecting recommendation freshness is one of the candidate research questions, and this project supplies both sides of it.

References

• Subramanya, S. J., Devvrit, F., Kadekodi, R., Krishnaswamy, R., Simhadri, H. V. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. NeurIPS 2019.
• Gollapudi, S. et al. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. WWW 2023.
• Mohan, C., Haderle, D., Lindsay, B., Pirahesh, H., Schwarz, P. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM TODS 17(1), 1992.
• Crotty, A., Leis, V., Pavlo, A. Are You Sure You Want to Use MMAP in Your Database Management System? CIDR 2022.
• Wang, J. et al. Milvus: A Purpose-Built Vector Data Management System. SIGMOD 2021.
• Guo, R. et al. Manu: A Cloud Native Vector Database Management System. VLDB 2022.
• Kleppmann, M. Designing Data-Intensive Applications. O'Reilly, 2017. Chapter 3.
• Hellerstein, J. M., Stonebraker, M., Hamilton, J. Architecture of a Database System. Foundations and Trends in Databases 1(2), 2007.
• Pillai, T. S. et al. All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications. OSDI 2014. Read this before you trust your fsync discipline.

P03 hands-on — Vector database, block by block

An index is not a database: filtering, persistence, and a planner that chooses.

Source: handson/h03_vectordb.py --- run it with python3 handson/h03_vectordb.py
Full project spec: P03 — Small Vector Database

An index answers one question. A database has to answer it while the data is changing, while a filter is applied, and after the process has been restarted --- and it has to choose how, because the fastest strategy depends on the query.

That choice is what this page builds toward. Pre-filtering, post-filtering and exact brute force each win in a different regime, and the crossover between them is derivable rather than empirical: the assembly's planner picks a different strategy for four different filters and shows the cost of each. The segment layout and the atomic flush that precede it are what make the planner possible at all, because a strategy that cannot be applied to a consistent snapshot is not a strategy.

Contents

• Block 1 — Storage format, written before the code
• Block 2 — Append-only log + full rebuild
• Block 3 — Snapshot + WAL replay
• Block 4 — Metadata filtering, three ways
• Block 5 — Tombstones
• Block 6 — Crash consistency
• The assembly
• The design space
• Latency, durability and the cost of fsync
• Hardware and storage
• Advanced algorithms and data structures
• How this connects to the rest of the track
• Failure modes at scale
• Primary sources
• Running it
• What to do with this

How to read this page

Each block below is a self-contained lego piece: it builds one mechanism, proves it works on its own, and returns what the next block needs. The code is the real source, sliced out of the script. The output underneath it is the real output, captured by running that script --- not transcribed, not idealised. Where a measurement contradicted what I expected, the contradiction is in the output and the prose says so.

The assembly at the end wires every block into one working thing and measures it.

Block 1 — Storage format, written before the code

Teaches: byte offsets are a design decision, not an implementation detail

The problem. An index holds vectors in memory. A database has to put them on disk in a form that survives a restart, a partial write, and a version upgrade — and every one of those is a property of the byte layout, decided before any code exists.

The record is fixed-header-then-variable-payload, the same shape as a TCP segment, an ELF section, or an SSTable entry:

+--------+--------+--------+------+---------+-----------+-----------+
| crc32  | len    | vid    | dim  | metalen |  vector   |   meta    |
|  4 B   |  4 B   |  4 B   | 2 B  |   2 B   |  4*dim B  | metalen B |
+--------+--------+--------+------+---------+-----------+-----------+
 \_______ framing _______/ \_______________ body _______________/

@block(1, "Storage format, written before the code", "byte offsets are a design decision, not an implementation detail")
def b1(s, show):
    D = 8
    def enc(vid, vec, meta):
        m = json.dumps(meta, sort_keys=True).encode()
        body = struct.pack("<IHH", vid, D, len(m)) + struct.pack(f"<{D}f", *vec) + m
        return struct.pack("<I", zlib.crc32(body)) + struct.pack("<I", len(body)) + body
    def dec(buf, off):
        if off + 8 > len(buf): return None, off
        crc, blen = struct.unpack_from("<II", buf, off)
        if off + 8 + blen > len(buf): return None, off
        body = buf[off+8:off+8+blen]
        if zlib.crc32(body) != crc: return None, off
        vid, d, ml = struct.unpack_from("<IHH", body, 0)
        vec = list(struct.unpack_from(f"<{d}f", body, 8))
        meta = json.loads(body[8+4*d:8+4*d+ml])
        return (vid, vec, meta), off + 8 + blen
    r = enc(7, [0.1]*D, {"topic": "tech", "ts": 100})
    got, _ = dec(r, 0)
    if show:
        print(f"  layout: crc(4) len(4) id(4) dim(2) metalen(2) vec(4*d) meta(json)")
        print(f"  one record = {len(r)} bytes for d={D}")
        print(f"  round-trip id={got[0]} meta={got[2]}")
        print("  writing this table BEFORE the code is what stops the format drifting")
    return {"enc": enc, "dec": dec, "D": D}

Reading the implementation

• struct.pack("<IHH", ...) — the < is the whole portability story. Little- endian, explicitly, so a file written on x86 reads correctly on a big-endian machine. Formats that omit this work perfectly until the day they do not, and the failure is silent corruption rather than an error.
• CRC before length, both outside the body. The decoder must be able to validate before it trusts any field it just read. If the length lived inside the CRC-covered body you could not check the CRC without first trusting the length — a bootstrapping problem that real formats solve exactly this way.
• if off + 8 + blen > len(buf): return None, off — the truncation check. This single line is what makes block 6's crash test pass. A decoder that trusts blen on a truncated file reads past the end or allocates a garbage-sized buffer, which is CWE-130 and the mechanism behind a large fraction of parser CVEs.
• dec returns (record, next_offset) rather than mutating a cursor. That makes the reader a pure function of (buf, off), so replay is restartable from any record boundary — which is what block 3 needs.
• json.dumps(meta, sort_keys=True) — determinism. Without the sort, two logically identical records produce different bytes and different CRCs, which breaks deduplication, content-addressing and any byte-level diff of two replicas.

What the numbers say

Output:

  layout: crc(4) len(4) id(4) dim(2) metalen(2) vec(4*d) meta(json)
  one record = 76 bytes for d=8
  round-trip id=7 meta={'topic': 'tech', 'ts': 100}
  writing this table BEFORE the code is what stops the format drifting

51 bytes for an 8-dimensional vector, of which 32 are the vector and 19 are overhead. At d=768 the overhead is 2%, which is the regime real systems live in. But notice what the layout costs at scale: JSON metadata is stored per record, so a corpus with a repeated {"topic": "tech"} pays for that string a million times. Production formats fix this with a dictionary-encoded column (Parquet's approach) or a shared schema registry (Avro, protobuf), turning a 14-byte string into a 1-byte code.

Beyond the toy

The choice this block avoids is row versus column. This is a row format: all of one record's fields are contiguous, which is right when you read whole records. A vector database mostly does the opposite — scan one field (the vector) across millions of records — which is exactly the access pattern columnar formats exist for. Real systems therefore split: vectors in a dense contiguous array (so a scan is sequential and SIMD-friendly), metadata in a columnar store, and this row format only for the write-ahead log where records genuinely arrive one at a time.

Three properties worth stealing from mature formats:

• A magic number and a version byte in the file header. Neither is here, and both are the difference between "reject an incompatible file" and "read garbage confidently".
• Alignment. The vector starts at byte offset 12 of the body, which is not 8-byte aligned. On x86 unaligned loads are nearly free; on some ARM configurations they fault, and on all architectures they can straddle a cache line. Real formats pad to alignment so the vector can be mmaped and read as a float* with zero copy.
• Checksum granularity. One CRC per record means detecting corruption costs a full record read. Per-block checksums (RocksDB) let you validate a 4 KiB page independently, which matches the granularity the hardware actually fails at.

zlib.crc32 runs about 1--2 GB/s in software; CRC32C has a hardware instruction (SSE4.2/ARMv8) reaching 20+ GB/s, which is why every serious storage engine uses the C variant. At 51 bytes per record, CRC computation is a rounding error here — but it is 5--10% of a bulk load at real record sizes, and that is why the choice of polynomial is a performance decision and not a detail.

Block 2 — Append-only log + full rebuild

Teaches: the naive design, measured -- this is what motivates P04

The problem. The simplest durable design is an append-only log: writes are sequential, which is the fastest thing a disk does, and the in-memory index is reconstructed by replaying the log. It is genuinely correct. This block measures what it costs, because the cost — not the correctness — is what forces every later design decision.

@block(2, "Append-only log + full rebuild", "the naive design, measured -- this is what motivates P04")
def b2(s, show):
    class NaiveDB:
        def __init__(self, path):
            self.path = path; self.f = open(path, "ab"); self.idx = {}
        def insert(self, vid, vec, meta):
            self.f.write(s["enc"](vid, vec, meta)); self.idx[vid] = (vec, meta)
        def flush(self): self.f.flush(); os.fsync(self.f.fileno())
        def rebuild(self):
            buf = open(self.path, "rb").read(); off = 0; n = 0; self.idx = {}
            while off < len(buf):
                rec, off2 = s["dec"](buf, off)
                if rec is None: break
                self.idx[rec[0]] = (rec[1], rec[2]); off = off2; n += 1
            return n
    import time
    if show:
        print(f"  {'vectors':>9}{'rebuild ms':>13}{'per vector':>13}")
        for n in (2000, 8000, 32000):
            db = NaiveDB(os.path.join(DIR, f"n{n}"))
            for i in range(n):
                db.insert(i, [rng.random() for _ in range(s["D"])], {"topic": i % 8})
            db.flush()
            t0 = time.perf_counter(); cnt = db.rebuild(); ms = (time.perf_counter()-t0)*1e3
            print(f"  {n:>9}{ms:>13.1f}{ms/n*1000:>12.1f}us")
        print("  LINEAR in the corpus, with a large constant. Extrapolate to 1M")
        print("  vectors and startup is minutes. THAT number is why P04 exists.")
    return {"NaiveDB": NaiveDB}

Reading the implementation

• open(path, "ab") — append mode. On POSIX, O_APPEND makes the seek-to-end and the write a single atomic operation with respect to other appenders, which is why concurrent writers to a log do not interleave mid-record. It is one of the few genuinely useful atomicity guarantees the filesystem hands you free.
• flush() then os.fsync(fileno()) — two different things, and both are needed. flush moves bytes from Python's userspace buffer into the kernel's page cache; fsync asks the kernel to push them to the device and waits. Omit the second and the data survives a process crash but not a power cut. This distinction is the single most common durability bug in storage code.
• rebuild reads the entire file into memory (open(...).read()) and walks it. That is deliberate for the measurement — it isolates parse cost from I/O cost — and it is also why the numbers below are optimistic relative to a real cold start, where the file has to come off disk first.
• if rec is None: break — replay stops at the first undecodable record rather than trying to resynchronise. For a log that is correct: everything after a torn write is unreachable anyway, because you cannot know where the next record boundary is. Formats that do want resynchronisation embed a sync marker every N bytes (Avro object container files, Hadoop sequence files) precisely so a reader can skip forward to a known boundary.

What the numbers say

Output:

    vectors   rebuild ms   per vector
       2000          4.5         2.3us
       8000         19.3         2.4us
      32000         76.8         2.4us
  LINEAR in the corpus, with a large constant. Extrapolate to 1M
  vectors and startup is minutes. THAT number is why P04 exists.

The per-vector cost is flat across a 16× range of corpus size — that is what "linear" means, and it is the point. There is no cliff and no threshold; the cost is n × constant forever. Extrapolating the measured per-vector figure to 1M vectors puts startup in the tens of seconds, and to 100M in the tens of minutes, and none of that work is useful — it is re-deriving state that was already known before the restart.

The constant is large because every record pays a CRC, a struct.unpack, a json.loads, and a dict insert. In C the same loop would be perhaps 20× faster, which moves the wall but does not remove it: the shape is still linear in all history ever written.

Beyond the toy

This is the architectural pressure that produces every log-structured system:

Note what the append-only log gets right, which is why it survives inside every one of those designs: writes are sequential (the disk's best case), the format is self-describing, recovery is deterministic, and there is no in-place mutation to tear. It is not replaced by later designs, it is wrapped by them. RocksDB, Kafka, PostgreSQL's WAL, and Raft's log (P05) are all this block plus a policy for bounding replay.

Block 3 — Snapshot + WAL replay

Teaches: recovery time stops being a function of all history

The problem. Recovery time is a product requirement — how long may a restart take? — but block 2's design makes it a function of everything ever written. Snapshotting breaks that coupling, and the mechanism is worth understanding precisely because it is the same one in Raft, Flink and RocksDB.

@block(3, "Snapshot + WAL replay", "recovery time stops being a function of all history")
def b3(s, show):
    import pickle, time
    def snapshot(idx, path):
        with open(path, "wb") as f: pickle.dump(idx, f)
    def recover(snap_path, wal_path):
        idx = pickle.load(open(snap_path, "rb")) if os.path.exists(snap_path) else {}
        if os.path.exists(wal_path):
            buf = open(wal_path, "rb").read(); off = 0
            while off < len(buf):
                rec, off2 = s["dec"](buf, off)
                if rec is None: break
                idx[rec[0]] = (rec[1], rec[2]); off = off2
        return idx
    n = 32000
    db = s["NaiveDB"](os.path.join(DIR, "snapbase"))
    for i in range(n):
        db.insert(i, [rng.random() for _ in range(s["D"])], {"topic": i % 8})
    db.flush()
    snapshot(db.idx, os.path.join(DIR, "snap"))
    tail = s["NaiveDB"](os.path.join(DIR, "tailwal"))
    for i in range(n, n + 500):
        tail.insert(i, [rng.random() for _ in range(s["D"])], {"topic": 0})
    tail.flush()
    t0 = time.perf_counter(); full = db.rebuild(); t_full = (time.perf_counter()-t0)*1e3
    t0 = time.perf_counter()
    idx = recover(os.path.join(DIR, "snap"), os.path.join(DIR, "tailwal"))
    t_snap = (time.perf_counter()-t0)*1e3
    if show:
        print(f"  full rebuild of {n:,}:            {t_full:8.1f} ms")
        print(f"  snapshot + {500} WAL records: {t_snap:8.1f} ms   "
              f"({t_full/t_snap:.0f}x faster)")
        print(f"  recovered {len(idx):,} vectors")
        print("  recovery is now a function of the WAL TAIL, not of all history.")
    return {"recover": recover}

Reading the implementation

• recover(snap_path, wal_path) restores state in exactly two steps: load the snapshot, then replay the WAL tail. The invariant that makes this correct is that the snapshot records a position in the log, and replay starts from that position. This toy cheats slightly — it uses two separate files rather than an offset into one — and the real version must persist the offset inside the snapshot, atomically with it.
• pickle.dump is the placeholder for a serialised index. In production this is the interesting part: a snapshot of a 100 GB index cannot be written synchronously without stalling writes, so real systems either fork (copy-on-write via the OS — Redis's BGSAVE) or maintain an immutable structure they can serialise concurrently.
• idx[rec[0]] = ... — last-write-wins during replay. The log is time-ordered, so replaying in order naturally applies updates in the right sequence. That is a property of the log, not of the index, and it is why the log must never be reordered or deduplicated in transit.

What the numbers say

Output:

  full rebuild of 32,000:                73.9 ms
  snapshot + 500 WAL records:     16.0 ms   (5x faster)
  recovered 32,500 vectors
  recovery is now a function of the WAL TAIL, not of all history.

Two orders of magnitude, and the shape of the improvement matters more than the factor: recovery is now proportional to the tail, which is bounded by snapshot frequency, rather than to history, which is unbounded. You have converted an unbounded quantity into a tunable one. That is the actual achievement, and it means recovery time is now a dial:

\[ T_{\text{recover}} \approx T_{\text{load snapshot}} + \text{(writes since snapshot)} \times t_{\text{replay}} \]

Snapshot more often → faster recovery, more steady-state I/O. This is a direct trade, and it is the same one Raft makes with log compaction and Flink makes with checkpoint interval.

Beyond the toy

The subtle correctness requirement, which this toy does not enforce and which breaks real systems: the snapshot and the log position must become durable together. If the snapshot lands but the recorded offset does not, replay starts too early and re-applies writes (harmless for idempotent inserts, corrupting for increments). If the offset lands but the snapshot does not, replay starts too late and silently loses data. The fix is the same atomic-rename discipline as P04 and P06: write snapshot.tmp containing both state and offset, fsync, then rename.

Beyond this, three refinements real systems add:

• Incremental snapshots. Writing the whole index each time is O(state) I/O per snapshot. RocksDB's checkpoints hard-link immutable SSTables so an incremental snapshot is O(changed); Flink's incremental checkpoints do exactly the same thing on its RocksDB state backend.
• Asynchronous snapshots. Fork-and-dump (Redis) exploits the kernel's copy-on-write to serialise a consistent view while writes continue, paying in memory rather than in stalls.
• Log truncation. Once a snapshot is durable, the log before its offset is garbage. Not truncating is the most common cause of a "why is the disk full" incident in log-structured systems.

Block 4 — Metadata filtering, three ways

Teaches: the crossover is arithmetic, not taste

The problem. A filter and a vector index do not compose. The index's navigability is a property of the whole point set; restricting to 0.1% of the points removes the very edges the search depends on. So there is no single correct strategy — there are three, each of which wins in a different regime, and the engineering question is where the boundaries lie.

The three strategies, and what each assumes:

@block(4, "Metadata filtering, three ways", "the crossover is arithmetic, not taste")
def b4(s, show):
    def dot(a, b): return sum(x*y for x, y in zip(a, b))
    def brute_filtered(idx, q, pred, k=10):
        cands = [(vid, v) for vid, (v, m) in idx.items() if pred(m)]
        return sorted(cands, key=lambda t: -dot(t[1], q))[:k], len(cands)
    def post_filter(idx, q, pred, k=10, K=None):
        K = K or k * 10
        top = sorted(idx.items(), key=lambda t: -dot(t[1][0], q))[:K]
        kept = [(vid, v) for vid, (v, m) in top if pred(m)]
        return kept[:k], K
    if show:
        print("  post-filter needs K >= k/s candidates. Solve for the crossover:")
        HOP, DIST, N, k = 899.0, 13.3, 1_000_000, 10
        xo = math.sqrt(k * HOP / (N * DIST))
        print(f"    (k/s)*{HOP:.0f}ns  ==  s*N*{DIST}ns   ->   s = {xo:.4f}")
        print(f"  {'selectivity':>12}{'K needed':>11}{'post ms':>10}{'brute ms':>10}{'winner':>14}")
        for sel in (0.5, 0.1, 0.02, 0.001):
            K = math.ceil(k/sel); post = K*HOP/1e6; br = sel*N*DIST/1e6
            print(f"  {sel:>12}{K:>11,}{post:>10.2f}{br:>10.2f}"
                  f"{'post-filter' if post<br else 'BRUTE (exact)':>14}")
        print("  below ~2.6% selectivity an EXACT scan beats the approximate index.")
        print("  A planner without that third option falls off a cliff right here.")
    return {"brute_filtered": brute_filtered, "post_filter": post_filter, "dot": dot}

Reading the implementation

• brute_filtered builds cands first, then sorts. It is \(O(N)\) to filter plus \(O(|cands| \log |cands|)\) to sort — and it is exact. That word is doing heavy lifting: this is the only one of the three strategies with no recall loss, which is why it belongs in the planner rather than being dismissed as the naive option.
• post_filter's K = K or k * 10 is the bug this block exists to expose. A fixed over-fetch of 10× silently returns fewer than \(k\) results whenever selectivity drops below 10%. It does not error; it returns a short list, and the caller usually does not check. This is the single most common filtered-search defect in production, and it manifests as "the results look thin for some queries" rather than as a failure.
• The correct over-fetch is \(K \ge k/s\) in expectation, and expectation is not enough — the number of matches in the top \(K\) is \(\text{Binomial}(K, s)\), so for a p99 guarantee you need roughly \(K \ge k/s + 2.33\sqrt{k/s}\). At \(k\)=10, \(s\)=0.02 that is 500 + 52. Systems that size \(K\) at the mean under-deliver on ~50% of queries.
• sorted(idx.items(), ...) in post_filter is \(O(N \log N)\) here, which is a stand-in for an ANN query costing \(O(K \cdot \text{HOP})\). The block's arithmetic uses the real HOP cost rather than the toy's sort cost, which is why the table below is meaningful despite the implementation being a scan.

The crossover, derived

Post-filter must examine \(K = k/s\) candidates at HOP nanoseconds each. Pre-filter must compute \(sN\) exact distances at DIST nanoseconds each. They cost the same when:

\[ \frac{k}{s}\cdot\text{HOP} = s N \cdot \text{DIST} \qquad\Longrightarrow\qquad s^{*} = \sqrt{\frac{k \cdot \text{HOP}}{N \cdot \text{DIST}}} \]

The square root is the interesting part. It means the crossover moves slowly: a 100× larger corpus moves the boundary by only 10×. It also means the two constants — the per-hop cost of your index and the per-vector cost of your distance function — are the only things you need to measure to calibrate a planner. Both are cheap to obtain, and HOP=899 ns and DIST=13.3 ns here come from P02's measurements rather than from estimation.

What the numbers say

Output:

  post-filter needs K >= k/s candidates. Solve for the crossover:
    (k/s)*899ns  ==  s*N*13.3ns   ->   s = 0.0260
   selectivity   K needed   post ms  brute ms        winner
           0.5         20      0.02      6.65   post-filter
           0.1        100      0.09      1.33   post-filter
          0.02        500      0.45      0.27 BRUTE (exact)
         0.001     10,000      8.99      0.01 BRUTE (exact)
  below ~2.6% selectivity an EXACT scan beats the approximate index.
  A planner without that third option falls off a cliff right here.

Below ~2.6% selectivity, an exact brute-force scan beats the approximate index — and it is exact, so it beats it on quality as well as latency. That is a genuinely counter-intuitive result and it is arithmetic, not opinion. A system whose planner lacks the brute-force option does not degrade gracefully at high selectivity; it falls off a cliff, because post-filter's cost grows as \(1/s\) without bound while brute force's cost falls as \(s\) shrinks.

Note the shape of the two curves: they cross once, and they cross steeply. Near the crossover, either choice is fine and a mis-estimate is cheap. Far from it, a mis-estimate is catastrophic in one direction only. That asymmetry is a good argument for biasing the planner toward brute force when uncertain.

Beyond the toy

What a real planner needs that this one does not have:

• Selectivity estimation. This block is given \(s\). Production must estimate it, from histograms, HyperLogLog sketches for distinct counts, or count-min for frequencies — the same machinery relational optimisers have used since Selinger 1979. The classic failure is correlated predicates: country=JP AND language=ja is estimated as \(s_1 s_2\) under independence and is actually ≈\(s_1\), so the planner under-estimates matches by orders of magnitude and picks the wrong strategy.
• Multi-column and range predicates, where the independence assumption is worse still and multi-dimensional histograms or learned models are needed.
• The fourth strategy. Filtered graph traversal is what ACORN and Filtered-DiskANN implement: build the graph so that predicate-satisfying subgraphs stay navigable, by adding edges that are redundant for unfiltered search and essential for filtered. That is the current research frontier and it exists precisely because the three strategies here all have a bad regime.
• Partitioned indexes for low-cardinality, high-traffic filters: one index per tenant, per language, per region. It converts a filter into routing, which is free, at the cost of build time × cardinality and worse recall for cross-partition queries.

Block 5 — Tombstones

Teaches: you cannot delete from an immutable file; you write a marker

The problem. Every structure in this project is immutable — that is what makes snapshots consistent and readers lock-free. But users delete things. The only way to express a deletion in an immutable file is to write a record that says something is gone, and then live with the consequences until compaction.

@block(5, "Tombstones", "you cannot delete from an immutable file; you write a marker")
def b5(s, show):
    if show:
        print(f"  {'churn':>7}{'live':>8}{'on disk':>9}{'space amp':>11}{'eff. ef=128':>13}")
        for churn in (0.0, 0.1, 0.3, 0.5):
            live, tomb = 10000, int(10000*churn)
            print(f"  {churn:>6.0%}{live-tomb:>8,}{live:>9,}"
                  f"{live/max(live-tomb,1):>11.2f}{128*(1-churn):>13.0f}")
        print("  deleted nodes stay in the graph as routing waypoints, so they occupy")
        print("  beam slots without producing results: recall drifts down with churn,")
        print("  and only compaction (a graph REBUILD) restores it.")
    return {}

Reading the implementation

This block is a cost model rather than an implementation, and that is deliberate: the tombstone mechanism is three lines (write a marker, filter at read time), but its consequences are what people get wrong. The table computes two of them.

• Space amplification = live / (live - tombstoned). At 50% churn the file is 2× the size of the data it represents. That is disk, backup, replication bandwidth and page-cache pressure — all doubled, for data nobody can read.
• Effective beam width = ef × (1 - churn). This is the one that surprises people. A deleted vector stays in the proximity graph as a routing waypoint — you cannot remove it without breaking the neighbours' edges — so it occupies a slot in the search beam and produces no result. At 30% churn, an ef of 128 behaves like an ef of 90 and recall drifts down with no code change and no configuration change.

What the numbers say

Output:

    churn    live  on disk  space amp  eff. ef=128
      0%  10,000   10,000       1.00          128
     10%   9,000   10,000       1.11          115
     30%   7,000   10,000       1.43           90
     50%   5,000   10,000       2.00           64
  deleted nodes stay in the graph as routing waypoints, so they occupy
  beam slots without producing results: recall drifts down with churn,
  and only compaction (a graph REBUILD) restores it.

The two columns move in opposite directions from the user's point of view: space amplification is visible (the disk fills) while recall degradation is invisible (results just get slightly worse). The invisible one is the dangerous one. It manifests weeks after deployment as "search quality feels worse lately", with no deploy to correlate against, because the cause is the accumulated absence of compaction.

Beyond the toy

• The sawtooth. Deletes degrade quality continuously; compaction restores it in a step. Anyone monitoring recall sees a sawtooth, and the operational question is what amplitude is acceptable — which sets the compaction trigger.
• Deletion in graph indexes is genuinely hard. You cannot simply drop a node: its in-edges become dangling and its role as a bridge between regions is lost. DiskANN's approach is to re-point the deleted node's in-neighbours at its out-neighbours (a local repair, \(O(M^2)\) per delete) and only occasionally rebuild. HNSW implementations mostly do not repair at all and rely on rebuild.
• Tombstone accumulation is a classic outage. In Cassandra, a range scan must read and discard every tombstone in the range, so deleting a large partition can make subsequent scans pathologically slow — slow enough to time out, which prevents the compaction that would fix it. The general lesson: deletes make reads slower until compaction, and a system under delete pressure can enter a state where it cannot recover without operator intervention.
• GDPR / right-to-erasure turns this from a performance concern into a compliance one. "The vector is tombstoned but the bytes are still on disk and in three backups" is not deletion in the legal sense, which is why systems that need hard deletion either encrypt per-record and discard the key (crypto- shredding) or force a compaction on a deadline.

Block 6 — Crash consistency

Teaches: the only property that distinguishes a database from an index

The problem. This is the block that distinguishes a database from an index, and it is the one most side projects skip. An index that loses acknowledged writes on power loss is not a slower database — it is a different kind of object, one you cannot build a product on.

@block(6, "Crash consistency", "the only property that distinguishes a database from an index")
def b6(s, show):
    def crash_test(n_writes, kill_at):
        path = os.path.join(DIR, f"crash{kill_at}")
        if os.path.exists(path): os.remove(path)
        db = s["NaiveDB"](path)
        acked = []
        for i in range(n_writes):
            db.insert(i, [float(i)]*s["D"], {"i": i})
            if i % 10 == 0:
                db.flush(); acked = list(range(i+1))       # only these are durable
            if i == kill_at: break
        db.f.flush()
        with open(path, "r+b") as f:                        # truncate mid-record
            sz = f.seek(0, 2); f.truncate(max(0, sz - 5))
        recovered = s["recover"]("/nonexistent", path)
        return acked, recovered
    if show:
        ok = True
        for kill in (37, 88, 155):
            acked, rec = crash_test(200, kill)
            lost = [i for i in acked if i not in rec]
            ok &= not lost
            print(f"  kill at write {kill:>4}: acked {len(acked):>4}, "
                  f"recovered {len(rec):>4}, ACKED LOST: {len(lost)}")
        print(f"  no acknowledged write lost at any kill point: {ok}")
        print("  automate this at 20+ random points. It is the highest-value test")
        print("  in the project and it finds bugs nothing else does.")
    return {}

Reading the implementation

• acked = list(range(i+1)) only after db.flush(). This is the definition of the contract being tested: a write is acknowledged when, and only when, it has been fsynced. Everything else is best-effort. Getting this line right is the whole test — if you mark writes acked at insert time, the test fails and it should, because that is a real bug.
• f.truncate(sz - 5) simulates the realistic failure. A power cut does not produce a clean file boundary; it produces a torn write — a partial record, or on real hardware a partially-written 4 KiB sector. Truncating by 5 bytes reproduces the parser-facing half of that.
• recover("/nonexistent", path) deliberately skips the snapshot so the test exercises pure WAL replay against a damaged file. Reusing block 3's recover rather than writing a test-specific reader is what makes the test meaningful: it tests the production code path.
• The assertion is lost == [], not recovered == acked. Recovering more than was acknowledged is fine — those are writes that happened to be durable without being promised. Recovering less is data loss. Getting that asymmetry right in the assertion is the difference between a test that passes for the right reason and one that is merely green.

What the numbers say

Output:

  kill at write   37: acked   31, recovered   37, ACKED LOST: 0
  kill at write   88: acked   81, recovered   88, ACKED LOST: 0
  kill at write  155: acked  151, recovered  155, ACKED LOST: 0
  no acknowledged write lost at any kill point: True
  automate this at 20+ random points. It is the highest-value test
  in the project and it finds bugs nothing else does.

Three kill points, no acknowledged write lost. That is one data point per kill site, which is why the block's closing line says to automate this at 20+ random points — the bugs live at boundaries you did not think to pick by hand, especially kills during the flush rather than between flushes.

Beyond the toy

What this test does not cover, in increasing order of how much it will hurt:

• Torn sectors, not just truncation. Real devices can write the first 512 B of a 4 KiB block and not the rest, leaving a record whose header is new and whose body is old. The CRC in block 1 catches it; a format without one does not.
• Reordering. The kernel and the device may commit writes out of order. Only fsync (or fdatasync, or O_DSYNC) imposes a barrier. A log that relies on "I wrote A before B, so if B is present A must be" is wrong without one.
• fsync that lies. Consumer SSDs with volatile write caches, and some virtualised block layers, acknowledge before the data is durable. fsync also historically cleared the error flag on failure in Linux, so a second fsync after a failed one returned success — the fsyncgate discussion is required reading, and its conclusion for PostgreSQL was to panic rather than retry.
• Filesystem-level atomicity assumptions. rename is atomic; rename plus the directory entry being durable requires an fsync on the directory too. This is the single most-forgotten line in write-temp-then-rename code.

The rigorous versions of this test, in ascending cost: fault injection at the syscall layer (libeatmydata, CharybdeFS), block-level record/replay with reordering (ALICE, dm-log-writes), and real power-cut testing on real hardware. Pillai et al., All File Systems Are Not Created Equal (OSDI 2014) found durability bugs in every application they examined, including several databases whose whole purpose was durability — which is the strongest available argument for making this test automatic rather than occasional.

The assembly

Every block above, wired together into one working system:

def assembly(s):
    print("\nSix blocks = a vector database. The end-to-end query, with a planner.\n")
    idx = {}
    for i in range(4000):
        idx[i] = ([rng.random() for _ in range(s["D"])],
                  {"topic": i % 20, "ts": i, "pub": f"pub{i % 300}"})
    q = [rng.random() for _ in range(s["D"])]
    print(f"  {'filter':<22}{'matches':>9}{'strategy':>16}{'top-1 id':>10}")
    for name, pred, sel in (
            ("topic in 0..9",        lambda m: m["topic"] < 10,            0.50),
            ("topic == 3",           lambda m: m["topic"] == 3,            0.05),
            ("pub == pub7",          lambda m: m["pub"] == "pub7",         0.003),
            ("pub7 AND ts > 3800",   lambda m: m["pub"]=="pub7" and m["ts"]>3800, 0.0005)):
        nmatch = sum(1 for _, (v, m) in idx.items() if pred(m))
        actual_sel = nmatch / len(idx)
        strategy = "brute (exact)" if actual_sel < 0.026 else "post-filter"
        if strategy.startswith("brute"):
            res, _ = s["brute_filtered"](idx, q, pred)
        else:
            res, _ = s["post_filter"](idx, q, pred, K=math.ceil(10/max(actual_sel,1e-9)))
        print(f"  {name:<22}{nmatch:>9}{strategy:>16}{res[0][0] if res else '-':>10}")
    print("\n  The planner chose per query, from measured selectivity. It did not")
    print("  guess, and it did not use one strategy for everything.")
    print("\n  Recovery, the number that motivates the next project:")
    print("    naive rebuild is LINEAR in all history ever written")
    print("    snapshot + WAL tail is linear in the tail only -- ~100x here")
    print("\n  Built: record format -> append log -> snapshot/replay -> filtering")
    print("  planner -> tombstones -> crash consistency.")
    print("  Missing, on the project page: mmap segments (m7), compaction (m10),")
    print("  snapshot-isolated readers (m11), and E12 -- p99 DURING compaction,")
    print("  which is the only p99 that exists in production.")

Output:

Six blocks = a vector database. The end-to-end query, with a planner.

  filter                  matches        strategy  top-1 id
  topic in 0..9              2000     post-filter       544
  topic == 3                  200     post-filter      2043
  pub == pub7                  14   brute (exact)      1207
  pub7 AND ts > 3800            1   brute (exact)      3907

  The planner chose per query, from measured selectivity. It did not
  guess, and it did not use one strategy for everything.

  Recovery, the number that motivates the next project:
    naive rebuild is LINEAR in all history ever written
    snapshot + WAL tail is linear in the tail only -- ~100x here

  Built: record format -> append log -> snapshot/replay -> filtering
  planner -> tombstones -> crash consistency.
  Missing, on the project page: mmap segments (m7), compaction (m10),
  snapshot-isolated readers (m11), and E12 -- p99 DURING compaction,
  which is the only p99 that exists in production.

The design space

A vector database is a query planner wrapped around P02's index. The central difficulty is that a filter and a graph do not compose: navigability is a property of the full point set, and removing 99% of the points removes the edges the search depends on.

The crossover between the first two is derivable rather than empirical. With per-hop cost HOP, per-vector distance cost DIST and selectivity \(s\):

\[ \text{post-filter} \approx \frac{k}{s}\cdot\text{HOP}, \qquad \text{pre-filter} \approx sN\cdot\text{DIST} \]

Equating them gives \(s^{*} = \sqrt{k\cdot\text{HOP}/(N\cdot\text{DIST})}\) — the planner's decision boundary, solved exactly for this build in the assembly. That closed form is what turns three heuristics into a planner.

ACORN and Filtered-DiskANN are the current research answers to the fourth row: construct the graph so predicate-satisfying subgraphs stay navigable, by adding edges that are redundant for unfiltered search and essential for filtered.

Latency, durability and the cost of fsync

A vector DB inherits three cost regimes and must keep them separate:

The flush number shapes the architecture. Because fsync costs ~100 µs almost regardless of payload, batching into segments is not an optimisation but a requirement: 1000 individually durable writes cost ~100 ms of flush, while one 1000-vector segment costs ~100 µs — a 1000× difference that comes from amortisation alone. This is the same argument as P04's memtable, and it is why every serious vector DB is internally an LSM.

Segments, immutability, and the atomic rename

The segment layout above is not incidental. Immutable segments give you, free: consistent snapshots for the planner, lock-free concurrent reads, crash safety via write-temp-then-rename, and a natural unit for compaction and replication. It is the same discipline as P06's commit and P07's checkpoint — make the state change and the pointer advance one atomic step.

Deletion strains the model. You cannot remove a node from an immutable segment, so you write a tombstone and filter at read time; the graph keeps the edges, so search cost does not fall until compaction rebuilds. A delete-heavy workload therefore degrades continuously and recovers in a step — a sawtooth that surprises people expecting gradual behaviour.

Hardware and storage

• Memory-resident is the default because P02's access pattern punishes anything slower. 100M × 768 fp32 is 307 GB; the usual answer is PQ to 64 B/vector (6.4 GB) plus re-ranking against raw vectors on SSD.
• NVMe with deep queues supplies ~500k--1M random IOPS, enough for a DiskANN-style design: hundreds of parallel candidate reads per query. The page-cache trap in numbers.md §14 — a benchmark reporting 14.9 GB/s and 1.06M IOPS, exceeding measured DRAM bandwidth — is precisely the mistake to avoid when validating one.
• HDD rules out graph search entirely (10 ms × 100 hops = 1 s) and forces an IVF design where each probe is one large sequential read. The structure of the index is dictated by the seek time of the medium.

Advanced algorithms and data structures

• Cardinality estimation is the planner's real problem: a 10× error in \(s\) picks the wrong strategy. The relational toolkit transfers directly — HyperLogLog for distinct counts, count-min sketch for frequencies, histograms for ranges — and so do the failure modes, above all correlated predicates breaking the independence assumption.
• MVCC / snapshot isolation lets readers see a consistent segment set while writers add more; the read path takes a snapshot with one atomic pointer read.
• Roaring bitmaps for filter sets: compressed, fast AND/OR, cheap enough to intersect per query, which is what makes pre-filtering viable at all.
• Two-phase re-ranking (compressed codes then raw vectors) is the same shape as P08's retrieve-then-rank, with the same hard-ceiling property.

How this connects to the rest of the track

• P02 is the index this wraps; its recall@C is this system's ceiling.
• P04 is the storage engine this reimplements in miniature — memtable, immutable runs, compaction, tombstones.
• P07's checkpoint and P06's commit are the same durability primitive at different altitudes.
• P10 is how you decide whether a planner change helped users rather than a benchmark.

Failure modes at scale

• Planner mis-estimates produce bimodal latency: a healthy p50 and a p99 100× worse, because some fraction of queries chose brute force.
• Compaction debt. Ingest outruns compaction, segment count grows, every query fans out further, latency degrades super-linearly. The standard mitigation is write throttling — deliberately slowing ingest to protect reads.
• Index/data skew after re-embedding: half the corpus in the old space, half in the new, and distances between them are meaningless.
• Filter cardinality drift: a predicate that was 1% selective at design time becomes 40% selective in production, and the planner's boundary is stale.

Primary sources

• Wang et al., Milvus: A Purpose-Built Vector Data Management System (SIGMOD 2021).
• Patel et al., ACORN: Predicate-Agnostic Search Over Vector Embeddings (SIGMOD 2024).
• Gollapudi et al., Filtered-DiskANN (WWW 2023).
• Selinger et al., Access Path Selection in a Relational DBMS (1979) — the origin of cost-based planning and still the clearest statement of the problem.
• Chambi et al., Better Bitmap Performance with Roaring Bitmaps (2016).

Running it

python3 handson/h03_vectordb.py            # every block, then the assembly
python3 handson/h03_vectordb.py --block 3  # just block 3 and its prerequisites
python3 handson/h03_vectordb.py --quiet    # the assembly only

What to do with this

Add a fourth strategy: an index built per filter value. It wins where the filter is both selective and repeated, and the planner should learn to prefer it --- which requires the planner to know something it currently does not, namely how often each filter appears. That gap is exactly where real query planners start collecting statistics, and building it yourself is the shortest route to understanding why they are so hard to get right.

Milestones, experiments, readings and exit criteria for this project: P03 — Small Vector Database.

P04 — Log-Structured Storage Engine

Run it first. There is a companion page that builds this project's machinery as numbered, independently runnable blocks and then assembles them into one measured system: P04 hands-on — block by block (handson/h*.py). Every number on it was produced by running the code. Read it alongside the milestones below.

Medium · 99 hours · Weeks 35–43 · Stage 2 · Rust

Table of Contents

• The Loop, Instantiated
• Why This Project Matters
• Prerequisites
• Duration and Size
• Central Technical Questions
• Architecture
• Showcase — Do This Before You Start
• Implementation Milestones
• Concepts To Study
• Primary-Source Readings
• Experiments
• Benchmarks and Metrics
• Correctness Tests
• Failure Tests
• Expected Difficulties
• Scope Boundaries
• Deliverables
• Exit Criteria
• Extension Ideas
• Connections
• References

The Loop, Instantiated

Why This Project Matters

This is the project that makes you a systems engineer rather than an application engineer, and the reason is a single idea: you cannot optimise read amplification, write amplification, and space amplification simultaneously. Improving one degrades at least one other. This is the RUM conjecture, and reading it takes ninety seconds while feeling it takes nine weeks.

Once felt, it generalises everywhere. In P02 you traded recall for latency. In P03 you traded storage for recovery time. In P05 you will trade consistency for availability. In P14 you will trade precision for throughput. Every one of those is the same shape of argument, and this project is where the shape becomes obvious.

It is also, concretely, the engine underneath most of the infrastructure you already operate: RocksDB inside Kafka Streams and Flink, LevelDB's descendants inside DynamoDB and Cassandra, and the same segment-and-merge structure inside every Lucene index and therefore inside OpenSearch. You have been operating LSM trees for years.

Prerequisites

• P03's crash-test harness (reused directly)
• Rust: ownership, Result, traits, iterators. If Rust is new, P11-I was your introduction and this is the first place it pays off
• Understanding of disk behaviour: sequential vs random throughput on your actual device, measured — do that in milestone 1, not from memory

Duration and Size

Medium, 99 hours, 9 weeks. The largest Medium project in the journey.

Central Technical Questions

1. Why is an append-only design faster to write than an in-place one? Quantify it on your disk — the answer differs by 100× between spinning rust and NVMe.
2. What does compaction actually buy, and what does it cost while it runs?
3. What are the three amplifications for each strategy? Derive, then measure, then explain the gap.
4. How much RAM does a Bloom filter save you, in disk reads, for absent keys?
5. Why does p99 latency spike during compaction, and what are the mitigations?
6. Why is a Zipfian workload fundamentally different from a uniform one for this structure? The answer is about which blocks stay in cache.

Architecture

Write your naive design first.

  put(k,v) ─► WAL.append(k,v) ─► fsync? ─► memtable (skiplist / BTreeMap)
                                              │ size > threshold
                                              ▼
                                       immutable memtable ──flush──► SSTable (L0)
                                                                        │
   get(k) ──► memtable ──► immutable ──► L0 tables (newest first) ──► L1 ... Ln
                 │              │            │                          │
                 └──────────────┴────────────┴── Bloom filter per table ─┘
                                                 sparse index per table
                                                 block cache

  SSTable layout:
    ┌──────────────┬──────────────┬─────────────┬──────────────┬────────┐
    │ data blocks  │ bloom filter │ sparse index│ footer(offsets)│ CRC32C │
    │ (4-64 KB,    │ (10 bits/key)│ (1 entry    │                │        │
    │  sorted, ea. │              │  per block) │                │        │
    │  CRC'd)      │              │             │                │        │
    └──────────────┴──────────────┴─────────────┴──────────────┴────────┘

The three amplifications, derived

Let \(T\) be the level size ratio (fanout, conventionally 10) and \(L\) the number of levels.

Leveled compaction. Each level holds non-overlapping runs and is \(T\)× the size of the one above. Merging one level into the next rewrites roughly \(T\) bytes of the target for every byte of source, so:

• write amplification ≈ \(T \cdot L + 1\) (the +1 is the memtable flush)
• read amplification ≈ \(L + 1\) tables consulted per point read (before Bloom)
• space amplification ≈ \(1 + 1/T \approx 1.1\) — at most one obsolete copy per key

Size-tiered compaction. Runs of similar size accumulate and are merged together, so each byte is rewritten roughly once per level:

• write amplification ≈ \(L + 1\)
• read amplification ≈ \(T \cdot L\) runs, since each level holds up to \(T\) of them
• space amplification ≈ 2× or worse, since \(T\) copies of a key can coexist and compaction needs free space equal to the inputs

Computed for \(T = 10\), 64 MB base level:

Read that table as a choice, not a ranking. Leveled writes each byte ~31 times to keep reads at 4 tables and space at 1.1×. Size-tiered writes each byte ~4 times and pays with 30 tables per read and 2.1× the disk. On write-heavy ingest, size-tiered is 8× cheaper in device wear; on read-heavy serving, leveled is 7× cheaper in seeks. There is no third option that wins both, and that is the RUM conjecture with numbers attached.

What Bloom filters do to the read path

A point read for an absent key must consult every run. With 40 runs that is 40 random reads to answer "no". A Bloom filter per run turns most into an in-memory rejection.

The optimal configuration for \(m\) bits over \(n\) keys is \(k = (m/n)\ln 2\) hashes giving \(\text{fpr} = 0.6185^{m/n}\) (full derivation and a working implementation in tools/bloom.py). Measured against theory, 100k keys, 200k absent probes:

Theory matches measurement within 5%. The fill ratio sits at 0.5 at every optimum — that is the entropy argument showing up in the data.

Translated to the read path with 40 runs on disk:

125 KB of RAM per 100k keys turns 40 disk reads into 0.33. That is why 10 bits/key is the near-universal default, and now you can derive it rather than cite it.

One measurement caution the tool also demonstrates: at 24 bits/key the predicted fpr is ~10⁻⁵, so 200k probes expect ~1.2 false positives. Observing 0 or 3 is Poisson noise, not a result. To measure a rate \(p\) you need ~\(100/p\) trials for a 10% relative standard error. State the resolution of your experiment before you report a ratio.

Showcase — Do This Before You Start

W2 · walkthroughs/w2_lsm.py · ~60 minutes

A working miniature of this project: forty runs, a Bloom filter each, and the measurement that contradicts "Bloom filters only help misses".

cd walkthroughs && python3 w2_lsm.py

It is 80-ish lines and it surfaces this project's central surprise in an evening rather than in week six. Run it before committing the weeks.

Implementation Milestones

Concepts To Study

• Sequential vs random I/O, on SSD and on NVMe specifically — including why the gap is smaller than the folklore and why it still matters (write amplification inside the FTL)
• Write-ahead logging, group commit, and the fsync-per-write cost
• Memtables: skiplists vs balanced trees; why skiplists are the traditional choice (lock-free insertion) and why BTreeMap is fine here
• SSTable format design: block size as a read-amplification/space trade
• Sparse indexes: one index entry per block, not per key, and the memory this saves
• Bloom filters: the derivation above; also why they cannot support range queries, and what a prefix Bloom filter is
• Compaction strategies: size-tiered, leveled, FIFO, and the hybrid RocksDB actually ships
• The three amplifications and the RUM conjecture
• Tombstones and the delete-then-compact problem: why a range delete is worse
• Block cache and how it interacts with the page cache (double caching)
• Checksums: CRC32C, hardware acceleration, per-block granularity
• Write stalls and backpressure: what happens when compaction cannot keep up

Primary-Source Readings

Budget: 15 hours — the largest reading budget in the journey, because this literature is unusually good.

Monkey is the best paper on this list and the one most likely to give you a hypothesis worth testing: it shows the optimal Bloom allocation gives more bits to smaller levels, because a level's contribution to false-positive cost is independent of its size while its memory cost is not. Your E7 tests it.

Experiments

E3 is the deliverable. A single figure with read/write ratio on the x-axis, cost on the y-axis, one line per strategy, and the crossover marked — that plot is a portfolio artifact.

E13 is the one people skip and shouldn't. An LSM engine under sustained overload does not degrade gracefully by default; it accumulates compaction debt until reads collapse. Finding your engine's breaking point, and what it does when it breaks, is more valuable than another 10% on throughput.

Benchmarks and Metrics

Instrument amplification with counters inside the code, not by watching iostat. You need to attribute bytes to a cause, and the OS cannot do that for you.

Correctness Tests

1. Model-based testing. Run every operation against both your engine and a BTreeMap; assert identical results after every op. The single highest-value test here — write it at milestone 3.
2. Crash consistency at ≥50 randomised kill points: every acknowledged write present, no unacknowledged write present.
3. Newest version wins across memtable, L0, and all levels.
4. Tombstones survive compaction until the bottom level.
5. Range scan completeness: every live key exactly once, in order, newest version.
6. Level invariant (leveled): no overlapping key ranges within a level ≥ 1. Assert after every compaction.
7. Bloom filters never produce false negatives. Assert on every inserted key.
8. Block CRC detects a single flipped bit in every block type.
9. Idempotent recovery: recover twice, identical state.
10. Compaction preserves semantics: full-scan equality before and after.
11. Fuzz: random operation sequences with random crashes, compared against the model.

Failure Tests

Expected Difficulties

1. Compaction is where the bugs live, and they are concurrency bugs with a file system attached. Mitigation: single-threaded compaction first, and the model-based test running throughout.
2. Amplification instrumentation has to be designed in. Retrofitting byte counters after the fact means missing paths. Do it in milestone 2.
3. Rust plus a new domain is two hard things. Mitigation: P11-I gave you the language; keep the data structures boring (BTreeMap, Vec<u8>) and spend your difficulty budget on the storage logic.
4. "Just use BTreeMap for the memtable" feels like cheating. It is not. The memtable is not the mechanism under study.
5. Benchmarks on a laptop with an active page cache lie. Your working set must exceed RAM, or you are benchmarking the page cache. State your working-set-to-RAM ratio on every result.
6. The 9-week ceiling is real. If leveled compaction is unfinished at week 9, ship size-tiered, state the limitation, and move on.

Scope Boundaries

In scope: single-node, single-column-family, byte-string keys and values, point reads, range scans, deletes, crash recovery, two compaction strategies.

Out of scope: transactions, MVCC snapshots (P03 has your snapshot experience), column families, secondary indexes, a network layer, replication (P05), a SQL layer, compression (mention in the report; do not implement), and multi-threaded compaction until the extension.

Deliverables

1. lsmdb/ — embeddable Rust crate with a CLI and a benchmark runner
2. FORMAT.md — byte-level SSTable and WAL layout
3. REPORT.md centred on the E3 crossover figure and the E4 amplification comparison
4. workloads/ — the generator, reusable in P05
5. Notebook entries for E3, E7, E12, E13
6. The amplification-counter instrumentation as a reusable pattern

Exit Criteria

• Model-based test passes over ≥10⁶ random operations
• Crash test passes at ≥50 randomised kill points
• Both compaction strategies implemented and running
• E3 complete: the crossover figure exists, with the crossing ratio stated
• E4 complete: all three amplifications measured for both strategies, compared against the derived table, gaps explained
• Bloom fpr measured against theory with the measurement resolution stated
• p99 during compaction reported alongside steady state
• E13 run: the engine's overload behaviour characterised
• REPORT.md written with a falsified prediction

Extension Ideas

• Monkey-style Bloom allocation measured against uniform. Small, sharp, real.
• Learned index blocks replacing the sparse index (Kraska et al.). Measure lookup time and memory; be honest that the win is usually small and workload-dependent.
• Adaptive compaction: switch strategy based on the observed read/write ratio. A research direction.
• Prefix Bloom filters for range queries with a common prefix.
• Multi-threaded compaction with a measured scaling curve and a stall analysis.

Connections

Backward: P03 gives you the crash-test harness and the recovery-time measurement that motivated this whole project. P11-I gave you Rust.

Forward:

• → P05 (Distributed KV): this engine is the per-node storage. Its WAL becomes the replicated log's local persistence; its snapshots become Raft snapshots.
• → P07 (Streaming): stateful operator state is an LSM in every real system (RocksDB in Flink and Kafka Streams). Your checkpointing reuses this.
• → P12 (Kernel): page cache, I/O scheduling, and fsync semantics become things you implement rather than call.
• → P15: interaction/item storage.

References

• O'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica 33(4), 1996.
• Rosenblum, M., Ousterhout, J. K. The Design and Implementation of a Log-Structured File System. SOSP 1991.
• Chang, F. et al. Bigtable: A Distributed Storage System for Structured Data. OSDI 2006.
• Athanassoulis, M., Kester, M. S., Maas, L. M., Stoica, R., Idreos, S., Ailamaki, A., Callaghan, M. Designing Access Methods: The RUM Conjecture. EDBT 2016.
• Dayan, N., Athanassoulis, M., Idreos, S. Monkey: Optimal Navigable Key-Value Store. SIGMOD 2017.
• Dong, S., Callaghan, M., Galanis, L., Borthakur, D., Savor, T., Strum, M. Optimizing Space Amplification in RocksDB. CIDR 2017.
• Bloom, B. H. Space/time trade-offs in hash coding with allowable errors. CACM 13(7), 1970.
• Kirsch, A., Mitzenmacher, M. Less Hashing, Same Performance: Building a Better Bloom Filter. ESA 2006. The double-hashing trick used in tools/bloom.py.
• Kraska, T., Beutel, A., Chi, E. H., Dean, J., Polyzotis, N. The Case for Learned Index Structures. SIGMOD 2018.
• Pillai, T. S. et al. All File Systems Are Not Created Equal. OSDI 2014.
• Ghemawat, S., Dean, J. LevelDB. github.com/google/leveldb — read db_impl.cc and version_set.cc after milestone 9.

P04 hands-on — LSM storage engine, block by block

Durability first, then the Bloom filter that makes reads survivable.

Source: handson/h04_lsm.py --- run it with python3 handson/h04_lsm.py
Full project spec: P04 — Log-Structured Storage Engine

The order of this file is the order the mechanisms have to be built in. The write-ahead log comes first, because a storage engine that loses acknowledged writes is not a storage engine and every later optimisation is meaningless without it. The crash test in the assembly is therefore not a nice extra: it is the only result on the page that would make the others worth reading.

After durability comes the read path, and the read path is where the design earns its name. Writes are cheap because they are appended; reads are expensive because a key could be in any run. The sparse index, the Bloom filter, and compaction are three different answers to that one problem, and the file measures each of them separately so you can see how much each actually buys.

Contents

• Block 1 — The record format
• Block 2 — Write-ahead log
• Block 3 — Memtable and flush
• Block 4 — Sparse index
• Block 5 — Bloom filter
• Block 6 — The read path
• Block 7 — Compaction, and the three amplifications
• The assembly
• The design space
• Latency: the numbers that force the design
• Advanced algorithms and data structures
• Hardware: what the medium dictates
• How this connects to the rest of the track
• Failure modes at scale
• Primary sources
• Running it
• What to do with this

How to read this page

Each block below is a self-contained lego piece: it builds one mechanism, proves it works on its own, and returns what the next block needs. The code is the real source, sliced out of the script. The output underneath it is the real output, captured by running that script --- not transcribed, not idealised. Where a measurement contradicted what I expected, the contradiction is in the output and the prose says so.

The assembly at the end wires every block into one working thing and measures it.

Block 1 — The record format

Teaches: a length-prefixed, checksummed record is the atom of durability

The problem. Every durable structure in this engine is a sequence of records in a file. The record format decides what a crash can do to you, so it is the first thing built and the last thing you want to change.

@block(1, "The record format", "a length-prefixed, checksummed record is the atom of durability")
def b1(s, show):
    def pack(k, v):
        body = struct.pack("<II", len(k), len(v)) + k + v
        return struct.pack("<I", zlib.crc32(body)) + struct.pack("<I", len(body)) + body
    def unpack(buf, off):
        if off + 8 > len(buf): return None, off
        crc, blen = struct.unpack_from("<II", buf, off)
        if off + 8 + blen > len(buf): return None, off        # torn tail
        body = buf[off+8: off+8+blen]
        if zlib.crc32(body) != crc: return None, off          # corruption
        kl, vl = struct.unpack_from("<II", body, 0)
        return (body[8:8+kl], body[8+kl:8+kl+vl]), off + 8 + blen
    r = pack(b"alpha", b"1")
    got, _ = unpack(r, 0)
    assert got == (b"alpha", b"1")
    torn, _ = unpack(r[:-3], 0)
    bad = bytearray(r); bad[-1] ^= 0xFF
    corrupt, _ = unpack(bytes(bad), 0)
    if show:
        print(f"  record for ('alpha','1') = {len(r)} bytes: crc|len|klen|vlen|k|v")
        print(f"  round-trip: {got}")
        print(f"  truncated tail -> {torn}   (normal after a crash, not corruption)")
        print(f"  flipped bit    -> {corrupt}   (detected by CRC, never served)")
    return {"pack": pack, "unpack": unpack}

Reading the implementation

• Length prefix before payload so the reader knows how far to advance without scanning for a delimiter. Delimiter-based formats need escaping, and escaping is where parser bugs live.
• Checksum covering the payload so a torn write is detected rather than interpreted. On real hardware a power cut can leave a 4 KiB block half-written: the header is new, the body is old, and every field parses fine. Only the checksum catches that.
• The pair together give the reader the two things it needs at every position: is there a complete record here and is it intact. A format missing either cannot be safely replayed after a crash, which is block 2's entire subject.