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)).