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.