Walkthroughs

Six executable mini-projects, 40–60 minutes each. Every one is a miniature of a real project in the track, produces a measured result, and ends in a finding that contradicts something people commonly believe.

cd walkthroughs
python3 w1_attention.py    python3 w2_lsm.py         python3 w3_raft.py
python3 w4_watermarks.py   python3 w5_autodiff.py    python3 w6_popularity.py

All six were executed to produce the output quoted below. Only w1 and w6 need third-party packages (numpy; w6 imports the track's own tools/metrics.py).

These are not the projects. They are 80-line sketches you can finish in an evening, built so you can feel a mechanism before committing eight weeks to it — and so that the central surprise of each project arrives early enough to be useful.

Why These Exist
W1 — Attention, and the Test That Catches Leakage
W2 — An LSM Read Path, and What Bloom Filters Really Buy
W3 — Split-Brain, Caused and Then Prevented
W4 — The Answer That Is Quietly Wrong
W5 — Autodiff Is Bookkeeping
W6 — The Popularity Trap
What All Six Have in Common
References

Why These Exist

Three reasons.

A cheap prior on the project. Spending 45 minutes on a sketch of P04 before committing 99 hours tells you whether the domain grips you. That is worth knowing in week 34 rather than week 39.

The central surprise, early. Each project's most valuable finding usually arrives in its last third. These bring one forward — you meet the bloom-filter-helps-hits result in an hour rather than in week 40, and it reframes the whole project you then build.

They are the calibration battery's natural follow-up. If C1 scored low, W1 is the remedy. If C3 scored low, W2 and W4 are.

Walkthrough	Mini of	Minutes	The finding
W1	P01	45	Attention is 18% of the compute at GPT-2's own context length
W2	P04	60	Bloom filters help hits 17×, contradicting the usual summary
W3	P05	60	Split-brain is one inequality, not a bug
W4	P07	45	The completeness curve has a dead zone where tuning buys nothing
W5	P13	45	The hard part is accumulation, not calculus
W6	P08	40	A bestseller list wins NDCG by 2.5× over personalisation

W1 — Attention, and the Test That Catches Leakage

w1_attention.py · 85 lines · numpy

Single-head causal attention, plus the two property tests that catch the bugs example tests miss.

The masking detail that matters, and the reason it is a comment in the code:

if causal:
    T = X.shape[0]
    # -inf BEFORE the softmax, so masked positions get exactly zero weight.
    # Applied after, they would get a small nonzero weight and the model would
    # quietly cheat.
    scores = np.where(np.tril(np.ones((T, T), bool)), scores, -np.inf)

The leak test

The single most valuable test in P01, and it is six lines:

Y1, _ = attention(X, Wq, Wk, Wv)
X2 = X.copy()
X2[6:] = rng.standard_normal((T - 6, d))     # scramble everything from row 6 on
Y2, _ = attention(X2, Wq, Wk, Wv)
assert np.array_equal(Y1[:6], Y2[:6]), "CAUSAL LEAK"

TEST 2 — the causal mask does not leak
  rows 0..5 bit-identical after scrambling rows 6..11: True
  rows 6..11 changed:                                  True

Bit-identical, not "close". A mask applied after the softmax, an off-by-one, or accidental bidirectionality all fail this and all produce a model that trains beautifully and reports an impossibly good validation loss.

What the scale buys

TEST 3 — what the 1/sqrt(dk) scale buys
  dk=  16   mean row entropy: scaled 1.477   unscaled 0.654   (max 2.485)
  dk=  64   mean row entropy: scaled 1.350   unscaled 0.141   (max 2.485)
  dk= 256   mean row entropy: scaled 1.443   unscaled 0.090   (max 2.485)

Read the columns, not the rows. Scaled entropy is flat at ~1.4 across a 16× range of \(d_k\); unscaled collapses from 0.654 to 0.090. That is P1 made visible: the scale is what keeps the softmax responsive as dimension grows.

A bug I shipped in the first draft, kept as a comment. The initial version initialised W without a \(1/\sqrt{d_k}\) factor, so \(Q\) already had variance \(d_k\) per component and both columns showed near-zero entropy — the demo appeared to disprove its own point. Initialisation and score scaling are two separate defences against the same failure, and forgetting either produces the same symptom.

Where the quadratic term actually bites

       T   attn GF    ffn GF  quad share
     128     0.65G     1.21G        2.7%
    1024     8.05G     9.66G       18.2%
    4096    70.87G    38.65G       47.1%
    8192   244.81G    77.31G       64.0%

At GPT-2 small's own context length of 1024, attention is 18% of the layer. The quadratic term does not dominate until ~4096. "Attention is the bottleneck" is a claim about a context length, and it is usually made about the wrong one.

W2 — An LSM Read Path, and What Bloom Filters Really Buy

w2_lsm.py · 86 lines · stdlib only

Forty immutable sorted runs, a Bloom filter per run, and a counter on every simulated block read.

def get(self, key, stats, use_bloom=True):
    if use_bloom and self.bloom is not None and key not in self.bloom:
        stats["bloom_rejects"] += 1
        return None                       # no disk read at all
    stats["block_reads"] += 1             # the expensive part
    return self.d.get(key)

40 sorted runs x 2000 keys = 80,000 keys

 bits/key  absent: reads  present: reads  bloom rejects
--------------------------------------------------------
     none         40.000           20.50            0.0
        4          5.882            3.83           34.1
        8          0.850            1.44           39.1
       10          0.335            1.17           39.7
       16          0.016            1.01           40.0

Two findings, and the second contradicts the folklore

The absent column confirms the derivation in P3: 40 reads → 0.335 at 10 bits/key, a 119× reduction, against a predicted 40 × 0.00819 = 0.328. Theory and measurement agree to within 2%.

The present column is the interesting one. The usual summary is "Bloom filters help misses, not hits." Measured: present-key reads fall from 20.50 to 1.17, a 17× improvement.

The mechanism is obvious once seen and invisible until measured: a hit must still skip every newer run that lacks the key, and the filter skips those without a read. Without a filter, finding a key costs a scan of ~half the runs.

The folklore is describing the asymptote, not the common case: as the filter becomes perfect, absent-key cost → 0 while present-key cost floors at 1, the one unavoidable read. Both improve; only one can reach zero.

This is a small, checkable instance of the track's central method — a widely repeated statement that is true in the limit and misleading in practice, caught by a counter.

W3 — Split-Brain, Caused and Then Prevented

w3_raft.py · 76 lines · stdlib only

A deterministic leader election under partition. Five nodes split 3–2; one candidate stands in each partition. The only variable is the quorum rule.

N = 5 replicas, partitioned into a 3-group and a 2-group

quorum=3  majority  (Q=3, 2Q=6 > 5)  CORRECT
    term 1: node 0 elected with 3 votes
    -> 1 leader(s);  SPLIT-BRAIN: False

quorum=2  plurality (Q=2, 2Q=4 <= 5) BROKEN
    term 1: node 0 elected with 3 votes
    term 1: node 3 elected with 2 votes
    -> 2 leader(s);  SPLIT-BRAIN: True

Two leaders in the same term, both accepting writes. Not a race, not a timing bug — an arithmetic consequence of choosing \(Q\) with \(2Q \le N\).

The script then brute-forces the inequality over every \((N, Q)\) pair, which is P4 as an exhaustive check rather than a proof:

  N   Q   2Q>N  disjoint quorums exist?
  5   2  False                     True
  5   3   True                    False
  6   3  False                     True
  6   4   True                    False

Note \(N=6\): a majority is four, not three. Even replica counts are exactly where operators get this wrong, and "we run six replicas for extra safety" with a quorum of three is a split-brain waiting for a partition.

What this buys you before P05. Thirteen weeks of Raft is a large commitment. An hour here gives you the safety property the whole protocol is organised around, so that when you read §5.2's voting rules they read as consequences rather than as arbitrary detail.

W4 — The Answer That Is Quietly Wrong

w4_watermarks.py · 92 lines · stdlib only

Sixty thousand events over a simulated day, counted per hour three ways. 88% arrive within seconds; a 12% "offline sync" cohort arrives 20 minutes to 5 hours late — the bimodal pattern any mobile product has.

  oracle (batch over the whole day)     total abs error       0
  bucketed by PROCESSING time           total abs error   1,139   (1.9% of events misattributed)
  bucketed by EVENT time, delay=0       total abs error  13,292   (6,646 dropped as late)

The 1.9% is not noise. It lands entirely on the offline-sync cohort — one identifiable segment of users, systematically miscounted, every single day. That is the difference between an error and a bias, and it is why event time exists.

The frontier, and its dead zone

       delay  completeness   dropped
       0 min        88.92%     6,646
       1 min        88.97%     6,619
       5 min        89.08%     6,552
      15 min        89.43%     6,342
         1 h        91.69%     4,984
         5 h       100.00%         0

This is not the concave curve you expect. Completeness is essentially flat from 0 to 15 minutes (+0.5 percentage points) and then climbs to 100% only as the delay reaches five hours.

The shape is set entirely by the lateness distribution, not by any property of windowing. With a bimodal stream there is no knee, because there is nothing in the middle of the distribution to recover. The operational consequence is uncomfortable: accept ~89% completeness, or wait five hours. Tuning the delay to 5 or 15 minutes — the usual instinct — lands in the dead zone and buys latency for nothing.

Measure your own lateness distribution before choosing a delay. The exchange rate between completeness and latency is a property of your data, not your code.

W5 — Autodiff Is Bookkeeping

w5_autodiff.py · 120 lines · stdlib only

Scalar reverse-mode autodiff, gradient-checked, then used to train a small network.

The whole engine is the graph plus a topological traversal. The derivative rules are one line each; the engineering is +=:

def back():
    # ACCUMULATE (+=), never assign. If a value is used twice, both
    # contributions must sum. Assigning here makes gradients too small by
    # an exact integer factor -- which looks like a learning-rate problem
    # and gets "fixed" by raising the learning rate.
    self.grad += out.grad; o.grad += out.grad

TEST 1 — gradients match central finite differences
  worst relative error over 600 partials: 1.09e-08

TEST 2 — the accumulation bug, demonstrated
  d(x*x)/dx at x=3: got 6.0, correct 6.0  -> OK
  With `=` instead of `+=` in __mul__ this prints 3.0: exactly half.
  An integer-factor error is the signature of a missing accumulation.

TEST 3 — train something.
  epoch    0  mse 0.046711
  epoch  600  mse 0.002794
  final mse 0.002794 over 25 parameters
  Reverse mode computed all 25 gradients in ONE backward pass.
  Finite differences would need 26 forward passes for the same.

The diagnostic worth memorising

An exact integer factor in a gradient error means a missing accumulation. Not 1.03× off — exactly 2×, or exactly 3×. Floating-point bugs give you noise; structural bugs give you integers. When your P13 gradients disagree with PyTorch by precisely 2.0, you know where to look before you start reading code.

The second habit the script builds is zero_grad. Forget it and gradients accumulate across epochs, the effective learning rate grows without bound, and training silently diverges or stalls — with no error anywhere.

W6 — The Popularity Trap

w6_popularity.py · 105 lines · imports tools/metrics.py

Four recommenders over a Zipf(1.0) catalogue, scored on accuracy and catalogue health.

1500 users, 2000 items, Zipf(alpha=1.0) popularity, k=10

recommender     NDCG@10  recall@10  coverage    Gini  novelty
-------------------------------------------------------------
random           0.0065     0.0065    0.9995   0.207    10.86
bestseller       0.1918     0.1424    0.0050   0.000     3.32
topic-only       0.0325     0.0322    0.0400   0.019     6.32
topic+pop        0.0761     0.0623    0.0400   0.019     6.32

The bestseller list wins NDCG outright — 2.5× the best personalised recommender — while showing the same ten items to all 1,500 users. Coverage 0.0050: ten items out of two thousand. Ship it and the accuracy dashboard is green and the catalogue is dead.

This is P18 arriving as a product decision: at \(\alpha = 1.0\) the top 1% of items carries 53% of engagement, so trivially exploiting popularity is a very strong accuracy strategy.

The subtler finding

topic-only and topic+pop have identical coverage (0.0400), Gini (0.019) and novelty (6.32) despite NDCG differing by +134%.

They are permutations of the same candidate pool, and a permutation cannot change which items were shown. Catalogue metrics are blind to ranking; they only see retrieval.

The consequence is diagnostic and useful: the popularity trap is sprung at the retrieval stage, not the ranking stage. If coverage is collapsing, look at candidate generation — no amount of reranking will move it.

And the control that makes the frontier legible: random has 0.9995 coverage and 0.0065 NDCG. Coverage alone is not a goal either. The suite is the measurement; no single column is.

What All Six Have in Common

Not an accident of selection — this is the shape the track is trying to install.

1. Each has a measurement that contradicts a plausible belief. Bloom filters "only help misses" (they help hits 17×). The completeness curve "has a knee" (it has a dead zone). Coverage responds to ranking (it cannot). Every one of those beliefs is reasonable, and every one is wrong in a way only a counter reveals.

2. Each instruments a mechanism, not just an outcome. block_reads and bloom_rejects, not just latency. Attention entropy, not just loss. Distance counts, not just recall. The outcome tells you something happened; the mechanism tells you why, and only the second lets you predict the next system.

3. Each is small enough to hold entirely in your head. 76–120 lines. That is the size at which you can be certain there is no hidden effect, which is what makes a surprising result trustworthy rather than suspicious.

4. Three of the six contain a bug I made and kept. W1's missing initialisation scale, W2's wrong conclusion about hits, W4's wrong claim about the curve shape, W6's wrong comparison — all written confidently, all contradicted by the output, all now documented in place. That ratio is normal, and hiding it would misrepresent what the work is like.

5. None of them is the project. They are 45-minute prospectuses. The projects are where you find the results nobody has written down for you.

References

Vaswani, A. et al. Attention Is All You Need. NeurIPS 2017. — W1
Bloom, B. H. Space/time trade-offs in hash coding with allowable errors. CACM 13(7), 1970. — W2
O'Neil, P. et al. The Log-Structured Merge-Tree. Acta Informatica 33, 1996. — W2
Ongaro, D., Ousterhout, J. In Search of an Understandable Consensus Algorithm. USENIX ATC 2014. §5.2 on the voting rules W3 demonstrates.
Gifford, D. K. Weighted Voting for Replicated Data. SOSP 1979. — W3
Akidau, T. et al. The Dataflow Model. VLDB 8(12), 2015. — W4
Baydin, A. G. et al. Automatic Differentiation in Machine Learning: a Survey. JMLR 18, 2018. — W5
Karpathy, A. micrograd. github.com/karpathy/micrograd. W5 is the same idea; read it after writing yours.
Cañamares, R., Castells, P. Should I Follow the Crowd? SIGIR 2018. Why popularity baselines are so hard to beat — W6, analysed properly.
Steck, H. Calibrated Recommendations. RecSys 2018. — W6

Systems From First Principles — Build · Measure · Publish