Annoy — Spotify’s ANN

The problem: exact nearest neighbor doesn't scale

Given N vectors in d dimensions and a query q, the honest answer is brute force: compute the distance from q to all N points and keep the smallest. That is O(N · d) per query — fine for thousands of vectors, ruinous for the tens of millions a recommender holds at hundreds of queries per second.

The classic spatial tricks do not save you either. A k-d tree degrades to brute force once d is more than a couple of dozen — the curse of dimensionality means almost every point sits near a splitting boundary, so pruning stops pruning. The escape is to stop demanding the exact nearest neighbor. Approximate nearest-neighbor search trades a small, controllable amount of recall for orders-of-magnitude speed: return the true top-k most of the time, and when you miss, return the 3rd-closest instead of the 1st. For recommendations, search, and retrieval that trade is almost free — nobody notices a slightly different ‘similar songs’ list.

The core idea: split space with a random hyperplane

Annoy’s single building block is a binary split of the point set by a hyperplane. Rather than choose an axis (like a k-d tree) or optimize the plane, Annoy picks it randomly but data-dependently: sample two points p and q from the set at hand, and use the perpendicular bisector of the segment joining them as the splitting plane. Every point on p’s side goes into the left child, every point on q’s side into the right.

The bisector of two random samples is a cheap, unbiased cut through the local density: it tends to separate two clusters when the samples land in different ones, and because the points are drawn from the data the plane sits where the points actually are, not through empty space. Recurse on each child until a node holds at most a small leaf capacity K (a few dozen), and you have a tree whose leaves are buckets of nearby points and whose internal nodes are a routing table of hyperplanes.

The split math

Two sampled points p and q define the plane. Let the midpoint be m = (p + q) / 2 and the normal be n = p − q. For any point x define the margin as the signed projection onto the normal:

margin(x) = n · (x − m)
         = n · x − n · m
         = (p − q) · x − (||p||^2 − ||q||^2) / 2

This is not arbitrary. Expanding the difference of squared distances to the two sampled points gives ||x−q||^2 − ||x−p||^2 = 2 · margin(x). So margin(x) > 0 means x is closer to p (go right), margin(x) < 0 means closer to q (go left), and margin(x) = 0 is exactly the bisecting plane. The routing rule sign(margin(x)) is one dot product and one comparison — O(d) per node. The absolute value |margin(x)| measures how far the query sits from the boundary, and that number becomes the key to the whole search.

Building one tree

Building is a straight recursion. Start with all N points at the root; sample p and q, compute the plane, split by the sign of each margin, and recurse on each half. Stop when a node holds ≤ K points and make it a leaf storing those IDs.

Because each split roughly halves the set, the tree has depth about log2(N / K) and building it costs O(N · d · log(N / K)) — every point touched once per level. If a random p, q pair splits very unevenly, Annoy resamples a few times to avoid lopsided trees. The finished tree is compact: internal nodes store a plane and two child pointers; leaves store a short list of IDs. Descending it is O(d · log N) — a handful of dot products down to one leaf of a few dozen candidates. That is the fast part; accuracy needs more than one tree.

A forest, not a tree

One tree is a lucky guess, and its fatal flaw is the boundary problem: when a query lands close to a hyperplane near the top of the tree, its true nearest neighbor may sit just on the other side of that plane and get routed into a completely different subtree. A single descent never sees it, and no amount of care fixes it — the cut had to go somewhere, and some neighbors always straddle it.

Annoy’s fix is a forest: build n_trees independent trees, each from its own random (p, q) samples, so each carves space differently. A neighbor lost across a boundary in tree 1 is very likely on the same side of the cut in tree 7 — the random splits make the trees diverse and their errors decorrelated. Searching descends all of them and unions the leaves they reach. More trees means more independent chances to catch each true neighbor — recall climbs with n_trees at the cost of a larger index and slower build.

Search: one priority queue across all trees

The clever part is not descending each tree to a single leaf — that returns only n_trees × K candidates and still misses neighbors just across a boundary. Instead Annoy runs a best-first search with one shared priority queue spanning every tree. Seed it with the root of all trees at priority +∞. Then repeat: pop the node with the largest priority; a leaf dumps its IDs into the candidate set; an internal node evaluates the query’s margin and pushes both children back with updated priorities.

pop node with max priority P
  leaf?     -> add its IDs to candidates
  internal? -> margin = n · q − n · m
               push near-child with priority min(P,  |margin|)
               push far-child  with priority min(P, −|margin|)
stop when |candidates| ≥ search_k  (or queue empty)

The priority is a budget for how deep into the ‘wrong’ side you are willing to go. The near child (the side the query falls on) keeps the current budget; the far child pays |margin|. A query near a boundary (|margin| small) barely spends its budget crossing, so the far side stays high-priority and gets explored — catching exactly the straddling neighbors one tree would miss. Because the queue is shared, that budget flows to whichever tree it buys the most in.

search_k is the query-time knob: the search runs until the candidate pool reaches search_k IDs (default n_trees × k). Those pooled candidates are the union across trees, deduplicated. Then the one exact step: compute the true distance from q to each of the ≈ search_k candidates and return the closest k. The trees never decide the answer — they nominate a small, high-quality shortlist, and a final brute-force rerank over it makes the returned order exact among the candidates. Query cost is O(search_k · d + search_k · log(search_k)).

The tree-count vs accuracy trade

Annoy exposes two dials, and separating them is the key to using it well. n_trees is set at build time: more trees means a bigger index and slower build, but higher achievable recall because each query gets more independent chances to catch a neighbor. search_k is set at query time: larger explores more nodes and reranks more candidates — higher recall, slower query — and it tunes per request without rebuilding.

A worked feel: say N = 1,000,000 vectors and you want top-10. With n_trees = 10 and search_k = 100 you might inspect ~100 candidates and hit ~85% recall in a fraction of a millisecond. Raise n_trees to 50 and search_k to 5,000 and recall climbs past 98%, the index grows roughly 5×, and each query reranks 5,000 distances — still far under the 1,000,000 a brute-force scan would touch. The recall-vs-latency curve is smooth and monotone: build once at the chosen n_trees, then trim search_k live to hit a latency target.

mmap and static indexes

Annoy’s deployment story matters as much as its algorithm. After build(), the forest is serialized to a single flat file whose layout mirrors the in-memory nodes — fixed-size records of planes and child offsets, with vectors inline. Loading is not a parse: Annoy mmaps the file into the process’s address space, so the operating system pages nodes in on demand and caches them in the shared page cache.

This has two big consequences. Startup is effectively instant regardless of index size — no deserialization, just a mapping — so a fresh worker serves immediately. And because the mapping is read-only and backed by the same file, many processes on one machine share one physical copy in RAM: fork 32 query workers and they cost roughly the memory of one index, not 32. For a recommender fanning a large embedding table across many serving processes, that shared, zero-copy, page-cache-resident footprint is often the deciding advantage — the index behaves like a static asset shipped next to your binary, not a database you stand up.

Why read-only, and how it differs from HNSW

Every one of those advantages assumes the index does not change. The trees are built from a fixed sample of the data; the file is mmap-ed read-only; the planes are frozen. There is no incremental insert — add a vector and you rebuild the whole forest. That is a deliberate trade: Annoy gives up mutability to buy simplicity, a tiny shared footprint, and instant load. It shines on static, immutable datasets rebuilt on a schedule — nightly embeddings, a catalog snapshot — and is a poor fit for a stream of live updates.

That is exactly where HNSW differs. HNSW is not a projection forest at all — it builds a layered, navigable small-world graph, and search is a greedy walk hopping edge to edge toward the query. It typically reaches higher recall per unit of latency and supports incremental insertion, but the mutable graph lives in per-process heap, is heavier in memory, and does not mmap-share cleanly across workers. The clean split: reach for the HNSW graph when the index is large, mutable, and latency-critical; reach for the Annoy forest when it is static, rebuilt in batch, and you want a dead-simple file that dozens of read-only workers can share.