Worked Notebook Entry — A Real One, With Real Numbers

A template teaches you the fields. It does not teach you what a good answer in each field looks like, or how much you are allowed to be wrong. So here is a completed entry from an actual experiment, run on the machine described below, with the raw output included. Everything in it is reproducible with tools/annlab.py.

Read this before you read the template. The most important thing in it is section 11: my central prediction was wrong, and the entry is better because of it.

Table of Contents

• 1. Problem
• 2. Constraints
• 3. Existing Approach
• 4. My Naive Design
• 5. Predictions
• 6. Hypothesis
• 7. Experimental Setup
• 8. Baseline
• 9. Results
• 10. Surprises
• 11. Failure Analysis
• 12. Next Experiment
• 13. Generalization
• What This Entry Did Right

1. Problem

Exact k-nearest-neighbour search over n vectors costs one pass over all n vectors per query. For a recommender serving 5,000 QPS over 10M items, that is 5×10¹⁰ distance computations per second, which no single machine can do. I want sub-linear query cost at a recall I choose, and I want to know exactly what the recall costs me.

2. Constraints

• Single machine, single thread. No GPU. Concurrency is a later project.
• Vectors fit in RAM. On-disk indexes are Project 3, not this experiment.
• Cosine similarity on L2-normalised vectors. Fixed for the whole project so that every number in this notebook is comparable to every other.
• I am allowed to be approximate. I am not allowed to be silently approximate: recall is measured against exact brute force on the same data, every time.
• Python. This is a constraint with consequences that I did not appreciate until section 10, and which turned out to be the most useful thing I learned.

3. Existing Approach

HNSW (Malkov & Yashunin, 2016): a hierarchy of proximity graphs with exponentially decaying layer membership. Search descends from a sparse top layer, greedily, refining at each level. Reported to give ~0.95 recall at 1–2 orders of magnitude fewer distance computations than brute force. The layer structure is claimed to remove NSW's dependence on lucky long-range links formed by insertion order.

I read the abstract and the algorithm pseudocode, and then stopped reading before the neighbour-selection heuristic (Algorithm 4), on purpose, so that section 4 would be mine.

4. My Naive Design

A single-layer navigable small-world graph:

1. Insert points one at a time in random order.
2. For each new point, greedily search the graph built so far with a beam of width efConstruction, connect the new node to the M nearest found, add reciprocal edges.
3. Cap every node's degree at 2M, keeping the M-nearest when it overflows.
4. Query: beam search from a fixed entry point with beam width efSearch. Stop when the closest unexplored candidate is further than the worst result currently held.

My reasoning for skipping the hierarchy: early insertions happen into a nearly-empty graph, so their edges are necessarily long. Those accidental long edges should give me the small-world property for free, and the hierarchy should be an optimisation rather than a requirement. This reasoning is wrong, and section 11 explains exactly how.

5. Predictions

Written before running anything. Recorded with a timestamp so I cannot retro-fit them.

6. Hypothesis

H1: On data with higher relative contrast (RC = mean distance / nearest-neighbour distance), a single-layer NSW graph achieves strictly higher recall@10 at every efSearch than on data with lower relative contrast, holding n, d, M and efConstruction fixed.

Falsifier: any efSearch at which the high-RC dataset shows lower recall@10 than the low-RC dataset, by more than the run-to-run spread.

7. Experimental Setup

• Hardware: 12-core arm64 (Apple Silicon), macOS 15.0, load average 4.3 at run time — not an idle machine, which inflates tail latencies and is recorded here so the p95 numbers are not mistaken for clean-room figures.
• Software: CPython 3.14.0, numpy 2.4.6. numpy links a vendor BLAS; brute force is one @ call, so it runs at BLAS speed while the graph walk runs at interpreter speed. This asymmetry is the entire subject of section 10.
• Data: n=10,000, d=64, L2-normalised.
  • Uniform: i.i.d. standard normal, then normalised → uniform on the unit sphere.
  • Clustered: 100 Gaussian clusters, per-axis σ=0.05.
• Queries: 200, drawn from the same distribution as the data.
• Index: M=16, efConstruction=100, seed=0. efSearch swept over {10,16,24,32,48,64,96,128,192,256}.
• Ground truth: exact top-10 by brute force, same distance function, same data.
• Command: python3 annlab.py --n 10000 --d 64 and python3 annlab.py --n 10000 --d 64 --clusters 100

A setup bug I found before running the real experiment

My first clustered generator used σ=0.25. It produced a dataset with RC=1.393 against uniform's 1.356 — statistically indistinguishable. Had I not measured RC before running, I would have run the whole comparison on two datasets that were the same dataset, found no difference, and concluded something false about clustering.

The mechanism: a Gaussian perturbation with per-axis σ in d dimensions has expected norm σ√d. At d=64, σ=0.25 gives σ√d = 2.0, while the cluster centres are unit vectors. The noise was twice the signal. The clusters existed in my code and not in my data.

Measured sweep at d=64, 100 clusters:

Clusters only exist when σ√d ≪ 1. Lesson: verify that your independent variable actually varies before you spend a run measuring its effect.

8. Baseline

Exact brute force, data @ q then argpartition. Recall 1.000 by construction.

Brute force is data-independent, as expected — it does the same n·d work regardless of structure. The 4% gap is noise from a non-idle machine.

9. Results

Uniform, RC = 1.363. Build 16.22 s, 25.8 edges/node, 3.59 MB (1.40× raw vectors).

Clustered, RC = 3.363. Build 6.29 s, 25.0 edges/node, 3.56 MB (1.39× raw).

Verdict on each prediction

Two of five predictions survived. That ratio is normal and is not a sign that the experiment went badly — it is a sign that the predictions were specific enough to be wrong.

10. Surprises

Surprise 1 — the index is slower than the thing it replaces, and the reason is arithmetic

I predicted a 10–100× win and measured a 3–33× loss. The distance counter explains it exactly. Decompose the speedup into two independent factors:

\[ \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}} \]

At efSearch=64 on uniform data:

• algorithmic win: 10,000 / 1,459 = 6.9× fewer distance computations
• constant factor: 899 ns/dist (Python loop) vs 13.3 ns/dist (BLAS) = 67.5× slower each
• predicted speedup: 6.9 / 67.5 = 0.10×
• measured speedup: 0.10×

And on clustered data: 31.1× fewer distances, 102.9× slower each, predicted 0.30×, measured 0.30×. The model is exact to two significant figures in both cases.

This is the single most valuable result in the entry, and it is a negative one. It says: my algorithm is right and my implementation is wrong, and those are different bugs with different fixes. Without the distance counter I would have concluded "HNSW does not work at n=10k", which is false, and I would have spent a week tuning M and efConstruction, which would not have helped.

Break-even requires the algorithmic win to exceed the constant factor. Distances/query grows roughly logarithmically in n while brute force grows linearly, so the crossover in pure Python lands near n ≈ 1.5×10⁵ — consistent with a separate run at n=100,000, d=128 which measured 0.80× at efSearch=64, just short of parity. In a compiled implementation the constant factor is ~1–2× and the crossover moves down to n of a few thousand. This is why every serious ANN index is written in C++.

Surprise 2 — clustered data has a lower recall ceiling

At efSearch ≤ 96 clustered beats uniform, as predicted. At efSearch ≥ 128 it loses, and the gap widens: at ef=256, uniform reaches 0.9930 and clustered only 0.9670. H1 is falsified.

The mechanism is visible in the distance counter, not in the recall column. At ef=256:

• uniform evaluates 4,059 distances per query
• clustered evaluates 840

The clustered search cannot spend its budget. It is not choosing to stop early to save time; it runs out of reachable candidates. Raising efSearch buys nothing because the beam is never the binding constraint.

11. Failure Analysis

Why H1 failed. My section-4 reasoning was that random insertion order produces accidental long-range edges, which give the small-world property for free. That argument holds on uniform data, where an early insertion's nearest neighbours are genuinely spread across the whole space. It fails on clustered data for a reason I did not anticipate: the degree-cap prunes exactly the edges the argument depends on.

Walk through it. When node v in cluster A accumulates more than 2M edges, my rule keeps the M nearest. Measured on this dataset (20,000 sampled pairs): mean intra-cluster distance 0.521, mean inter-cluster distance 1.413 — a clean 2.7× separation with no overlap in the bulk of the distributions. So the pruning rule deletes every single long edge, deterministically, the moment a node gets busy. On uniform data there is no such clean separation, so pruning by distance removes edges roughly at random and long edges survive by luck. On clustered data the pruning rule is a perfectly efficient long-edge destroyer, and the tighter the clusters, the more efficient it gets.

The result is a graph that is 100 well-connected islands with almost no bridges. Greedy search descends into one island, exhausts it in ~800 distance computations, and terminates — with any true top-10 neighbours that happen to live in an adjacent cluster permanently unreachable.

And this is precisely what HNSW's Algorithm 4 exists to prevent. The neighbour-selection heuristic I deliberately did not read keeps a candidate edge only if the candidate is closer to the base node than to any already-selected neighbour — which preserves edges pointing in directions not already covered, i.e. exactly the long bridges. I skipped it because it looked like an optimisation. It is not an optimisation; it is a connectivity guarantee, and on clustered data it is load-bearing.

I could not have learned this by reading the paper. I learned it by building the version without it and being unable to explain a recall ceiling.

Secondary failure — my p95/p50 prediction (P4) was wrong in direction. I assumed longer walks mean more variance. For uniform data the ratio fell from 1.39 to 1.13 as ef grew. Retrospectively obvious: at small ef the walk length is dominated by where the query happens to land relative to the entry point, which is high-variance; at large ef every query does a lot of work and the relative spread shrinks. I was reasoning about absolute variance and predicting about relative variance. The measurement caught a confusion in my head, not a property of the system.

12. Next Experiment

The smallest experiment that reduces the most uncertainty:

E1 — Instrument inter-cluster edge fraction. For the clustered index, compute the fraction of edges whose endpoints are in different clusters, before and after degree-cap pruning. Cost: ~40 minutes. Prediction: below 1% after pruning, versus ~15% before. If confirmed, the failure analysis above is established rather than plausible. If the fraction is high, my explanation is wrong and the ceiling has some other cause.

Then, in order:

• E2 — Replace the distance-based degree cap with HNSW's Algorithm 4 heuristic. Prediction: clustered recall@10 at ef=256 rises from 0.967 to above 0.99, with distances/query rising toward uniform's ~4,000. Cost: ~3 hours.
• E3 — Add the layer hierarchy. Prediction: it helps latency (fewer hops to reach the right region) far more than recall (which E2 already fixed). This prediction is the one I would most like to be wrong about, because the paper presents the hierarchy as the headline contribution and my model says the heuristic is doing more of the work.
• E4 — Port the inner loop to compiled code and re-measure the crossover n against the model in Surprise 1. Prediction: crossover falls below n=10,000.

Note that E1 costs 40 minutes and would settle the main open question. Do the cheap decisive one first; do not start E2 before E1 tells you whether E2 is even aimed at the right thing.

13. Generalization

Where the "clustering hurts recall" result should hold: any graph index that prunes edges by raw distance, on any dataset with well-separated modes. That includes real production cases — multilingual embedding spaces, catalogues with strong category structure, and any corpus where near-duplicates form tight clumps. It predicts a specific production failure: recall that looks fine on a uniform synthetic benchmark and degrades on the real corpus, in a way that adding efSearch does not fix. That is a falsifiable claim about someone else's system, which makes it the most valuable sentence in this entry.

Where it should not hold: IVF/quantization indexes, which partition rather than navigate and are largely indifferent to modality; and graph indexes whose pruning already preserves directional diversity, which is most production HNSW.

Where the constant-factor result generalises: everywhere, and it is the more transferable of the two. Any time an algorithmically superior structure loses to a brute-force scan, decompose the ratio into operation count and cost per operation before touching a parameter. Applied to later projects in this journey: an LSM read path that loses to a hash map, a graph traversal that loses to a table scan, a fused kernel that loses to two unfused ones — same decomposition, same diagnostic power.

Where it fails: when the two implementations do not share a countable unit of work. There is no "distance" to count when comparing a B-tree to an LSM tree, so you need a different common currency (bytes read from disk, usually).

What This Entry Did Right

Worth naming explicitly, because these are the habits and not the content.

1. The predictions were written first and were specific enough to be wrong. "It will be faster" is unfalsifiable. "10–100× faster at n=10,000" got destroyed by the data, which is what made section 10 possible.
2. A secondary metric explained the primary one. Recall and latency alone give you "it is slow and it plateaus". The distance counter turns both into arithmetic that closes to two significant figures. Instrument the mechanism, not just the outcome.
3. The setup was validated before the experiment ran. Measuring RC caught a generator whose independent variable did not vary. That check cost ten minutes and saved a worthless run.
4. The failure analysis names a specific line of the design. Not "clustering is hard" but "the degree-cap prunes by raw distance, which on separated modes deletes every bridge deterministically". Specific enough to fix, and specific enough to be wrong.
5. The next experiment is 40 minutes, not two weeks. Decisive and cheap beats thorough and slow, every time, when uncertainty is the bottleneck.
6. The generalization makes a claim about systems I have not built. That is the step from "I did an experiment" to "I know something".

The entry is ~2,000 words and represents roughly six hours of work including the failed setup. That ratio — a substantial written artifact per handful of hours — is what the 10% writing allocation in the operating model buys you.

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 (arXiv:1603.09320). Algorithm 4 is the neighbour-selection heuristic discussed in section 11.
• He, J., Kumar, S., Chang, S.-F. On the Difficulty of Nearest Neighbor Search. ICML 2012. Source of the relative-contrast measure used throughout.
• Malkov, Y., Ponomarenko, A., Logvinov, A., Krylov, V. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45, 2014. The single-layer NSW that section 4 reinvented.
• Beyer, K. et al. When Is "Nearest Neighbor" Meaningful? ICDT 1999. Why RC→1 in high dimensions and what that does to every distance-based method.
• Aumüller, M., Bernhardsson, E., Faithfull, A. ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. Information Systems 87, 2020. The protocol this entry's recall/QPS curve imitates.