HNSW and Annoy: Two Ways to Avoid Comparing Every Vector
Before you start: vectors and distances, plus the indexing overview. We focus on candidate search, with relevance evaluation linked separately.
A flat exact scan compares a query with every stored vector. Approximate nearest-neighbor search tries to examine a promising subset and still return nearly the same neighbors. Its central risk is easy to state: an excellent item cannot be returned if the search never discovers it.
HNSW discovers candidates by following graph links. Annoy discovers them through partitions of vector space. We will trace both with deliberately small, constructed examples. Their numbers explain the mechanics; they are not production performance measurements.
HNSW: use a sparse hierarchy to reach a useful starting point
HNSW stores each vector as a node in the base graph. A random subset also appears one level up, a smaller subset appears above that, and so on. A node promoted to a high level remains present below it. These are nested sets of the same vectors, not separately trained embeddings.
Search starts at the top entry point, follows links to closer nodes, then descends from the best position found. In the paper’s query algorithm, upper levels use greedy search; the base level performs the broader exploration described below. Malkov and Yashunin, Algorithms 2 and 5.
Keep “waiting to explore” separate from “best found”
At the base layer, keep a frontier of discovered nodes whose outgoing links may still be explored, and a retained set of the best candidates found so far. The search setting ef, often called efSearch, limits that retained set. The requested output count is K; here K = 1.
Pop the closest frontier node. Examine its previously unseen neighbors. A neighbor enters the frontier and retained set if there is room, or if it is closer than the worst retained candidate. When the retained set grows beyond ef, remove its worst member. A seen-node set avoids repeated distance calculations.
The standard stopping rule ends exploration when the closest pending node is worse than the worst retained candidate. That node’s unexplored neighborhood might still contain something better: the rule is an approximation, not a proof of global optimality. The hnswlib search implementation makes the candidate and retained queues explicit.
Squared distance to query: P 100 · S 36 · A 20 · B 29 · C 2
With ef = 1, expanding S retains A and rejects the farther B. A has no route onward except back to S, so search returns A. With ef = 2, B remains available; expanding it discovers C, which becomes the returned neighbor. P can remain pending even after leaving the retained set, until the stopping rule discards further exploration.
ef is not a limit on visited nodes or distance computations. With ef = 2, this trace evaluates all five vectors and can hold three pending nodes while retaining only two. Real costs depend on the graph and query. hnswlib requires ef to be at least K; library names and details should be recorded with the benchmark. hnswlib parameter definitions.
Where the graph’s distances come from
The query is (0, 0). Use vectors P=(8, 6), S=(6, 0), A=(4, 2), B=(5, −2) and C=(1, −1). Squaring and adding coordinate differences gives 100, 36, 20, 29 and 2. Squared Euclidean distance has the same ordering as Euclidean distance, so square roots are unnecessary for this trace.
Build choices determine which routes will exist
During insertion, a new vector searches for candidate neighbors, chooses connections, and may cause existing connection lists to be pruned. Choosing diverse directions can preserve useful routes; connecting only to a tight group of very similar nodes can leave poor access to another region. Larger query effort explores the graph you built; it does not add missing links. The paper’s neighbor-selection heuristic addresses this navigation problem.
| Setting | Controls | Cost to inspect |
|---|---|---|
| M | Connection budget during construction; exact per-level limits vary | Graph memory, connectivity and build work |
| efConstruction | Candidate exploration while inserting vectors | Build time and the quality of selected links |
| efSearch / ef | Retained candidate capacity during a query | Distance computations and recall on the built graph |
| K | How many neighbors the caller requests | Output size and the minimum compatible search effort |
More effort can improve recall, but it is not a universal latency formula or a guarantee that every individual query improves. Benchmark your vector distribution, insertion order and settings. HNSW also stores graph links and bookkeeping in addition to vectors; vector bytes alone understate its memory footprint.
Annoy: reach candidates through several partitions
A projection split separates a region into two sides. Repeated splits form a tree whose leaves contain candidate IDs. A query tends to follow its side of a split first, but a nearby item can sit just across the boundary. Several trees provide different partitions; broader search can revisit alternative branches.
The diagrams below use two hand-chosen one-split trees. Query Q=(0.1, 0.1) is just right of the vertical boundary. Its nearest item A=(−0.1, 0.1) is just left of it. The horizontal tree instead puts Q and A on the same side. Compare the candidate sets before scoring their distances.
The vertical query-side leaf contains B and D. Their squared distances are 0.50 and 1.06, so B wins. The horizontal leaf contains A and B; A has squared distance 0.04 and wins. Combining those leaves gives A, B and D after deduplication. Exploring both sides of the vertical split also finds A, at the cost of scoring C as well.
Annoy’s actual search uses a priority queue over tree nodes and alternative branches, then deduplicates candidate IDs and scores them. Its Euclidean split implementation uses a randomized two-center procedure to construct a separating plane; it is not limited to axis-aligned splits like our drawing. Annoy source: two_means, Euclidean::create_split and _get_all_nns.
n_trees is a build-time choice affecting index size and construction. search_k controls query effort; its default is the requested neighbor count multiplied by the number of trees. Set it explicitly when comparing different K or tree counts. It is a search budget, not a promise of that many unique distance evaluations. Annoy’s API and tradeoffs.
The normal Annoy workflow builds and saves an immutable index that processes can memory-map. Adding new items requires rebuilding the built index. Pages loaded on demand can make early queries slower than warm queries, so loading a file and measuring steady-state search are separate experiments.
Match the distance before comparing the indexes
Raw inner product rewards alignment and can also reward a large vector norm. Cosine similarity divides out the norms. For example, with query (1, 0), item U=(1, 0) has cosine 1 and dot product 1; V=(2, 2) has cosine about 0.707 but dot product 2. The two objectives choose different winners.
For unit-length vectors, the relationship is simpler. Write $q$ for the normalized query and $x$ for a normalized item. Their dot product $q^\top x$ equals their cosine similarity. Expanding squared Euclidean distance gives:
Thus maximizing cosine and minimizing Euclidean distance produce the same ordering for these normalized vectors. Annoy’s angular distance is the square root of this quantity: a cosine of 0.8 corresponds to squared distance 0.4 and angular distance about 0.632. Report the score the API returns, and handle zero vectors before normalization.
Use the workload to choose the operating point
An index that shares an immutable file across processes and a graph that supports incremental insertion solve different operational problems. Check the specific library’s update, deletion and filtering support, together with vector dimension, memory, build time and target recall. Neither algorithm has a universal winning setting.
Exact scoring of discovered candidates cannot recover a neighbor that candidate discovery missed. It also cannot repair an embedding that ranks irrelevant items nearby. Use the stage-diagnosis chapter for that distinction, and the next chapter to measure approximation and cost under a controlled workload.
Example HNSW curve: Recall@10 vs. query latency across efSearch
To see how efSearch shapes the speed-versus-recall Pareto frontier on a built HNSW graph ($N = 1{,}000{,}000$ vectors, $d = 768$, M = 16, efConstruction = 200, $\text{top\_k} = 10$), sweep efSearch from its legal floor (efSearch = k = 10) up to 1024:
efSearch ($N = 1\text{M}$, $d = 768$, $M = 16$, $\mathrm{efConstruction} = 200$, $k = 10$). Operating at the knee of the curve (efSearch = 64–128) delivers $96.5\%\text{–}98.4\%$ recall at $1.45\text{–}2.55\text{ ms}$, while pushing beyond efSearch = 256 hits the build-time graph ceiling ($\approx 99.6\%$).efSearch | Avg Layer 0 Distance Evals | Recall@10 | Marginal Gain | p50 Latency | p95 Latency | 1-Core QPS | Operating Regime |
|---|---|---|---|---|---|---|---|
| 10 (min $= k$) | ~290 (0.03%) | 78.4% | — | 0.31 ms | 0.42 ms | ~2,380 QPS | Under-explored (premature stop) |
| 16 | ~430 (0.04%) | 84.6% | +6.2% | 0.43 ms | 0.58 ms | ~1,720 QPS | Steep climb |
| 32 | ~740 (0.07%) | 91.8% | +7.2% | 0.66 ms | 0.88 ms | ~1,135 QPS | Steep climb |
| 64 | ~1,320 (0.13%) | 96.5% | +4.7% | 1.10 ms | 1.45 ms | ~690 QPS | Knee / Production Sweet Spot |
| 100 | ~1,910 (0.19%) | 97.8% | +1.3% | 1.55 ms | 2.05 ms | ~485 QPS | Knee / Production Sweet Spot |
| 128 | ~2,420 (0.24%) | 98.4% | +0.6% | 1.92 ms | 2.55 ms | ~392 QPS | Knee / High-Recall Sweet Spot |
| 256 | ~4,650 (0.47%) | 99.2% | +0.8% | 3.65 ms | 4.85 ms | ~206 QPS | Diminishing returns |
| 512 | ~9,100 (0.91%) | 99.5% | +0.3% | 7.10 ms | 9.40 ms | ~106 QPS | Heavy latency penalty |
| 1024 | ~17,800 (1.78%) | 99.6% | +0.1% | 13.80 ms | 18.20 ms | ~55 QPS | Saturated at build-time ceiling |
| Exact Scan | 1,000,000 (100%) | 100.0% | +0.4% | 82.00 ms | 85.00 ms | ~12 QPS | Brute-force baseline ($O(Nd)$) |
Time & space complexity of HNSW — and the TC gain compared to skip lists & flat NSW
HNSW is the high-dimensional proximity-graph generalization of a 1D Probabilistic Skip List (Pugh, 1990) combined with a Navigable Small World (NSW) graph (Malkov et al., 2014):
- Hierarchy height ($L_{\max}$): With promotion probability $p = e^{-1/m_L} = 1/M$ (when $m_L = 1/\ln M$), expected height is $L_{\max} = \Theta(\log_M N) = \Theta\!\left(\frac{\ln N}{\ln M}\right)$.
- Phase 1 (Upper-layer greedy zoom-in, Layers $L_{\max} \dots 1$): $O(1)$ expected greedy hops per layer, each scoring at most $M_{\max} = M$ neighbors of dimension $d$: $\mathcal{T}_{\text{Phase 1}} = O\!\left(d \cdot M \log_M N\right)$.
- Phase 2 (Layer 0 beam search): Expands $O(\mathrm{efSearch})$ candidates on Layer 0, each scoring up to $M_{\max0} = 2M$ neighbors: $\mathcal{T}_{\text{Phase 2}} = O(d \cdot M \cdot \mathrm{efSearch})$.
- Total Query, Build, and Space Complexities:
$$\mathcal{T}_{\text{query}}(\text{HNSW}) = O\!\left(d \cdot M \left(\log_M N + \mathrm{efSearch}\right)\right) = \mathbf{O(d \log N)},$$$$\mathcal{T}_{\text{build}}(N) = O\!\left(N \cdot d \cdot M \left(\log_M N + \mathrm{efConstruction}\right)\right) = \mathbf{O(N \log N)}, \qquad \mathcal{S}(\text{HNSW}) = \mathbf{O\bigl(N(d + M)\bigr)}.$$
Where does the time-complexity (TC) gain compared to a Skip List & Flat NSW come from?
- Generalizing $O(\log N)$ from 1D total order to $\mathbb{R}^d$ (where 1D skip lists degrade to $O(Nd)$): A 1D Skip List achieves $O(\log N)$ only because 1D keys have a total order ($x_1 < x_2 < \dots < x_N$). In $\mathbb{R}^d$ ($d \ge 128$), projecting onto a 1D skip list or space-filling curve scatters true neighbors across $O(2^d)$ intervals, degrading high-recall search back to $O(Nd)$. HNSW replaces each layer’s 1D linked list with a $d$-dimensional Relative Neighborhood proximity graph, preserving $O(d \log N)$ routing in $\mathbb{R}^d$.
- The $\Theta(\log N)$ TC gain of Skip-List layers over Single-Layer Flat NSW ($O(\log^2 N) \to O(\log N)$): In a single-layer Flat NSW graph without skip-list layers, early “hub” nodes accumulate both long-range and short-range edges simultaneously, so hub degree grows with corpus size as $\Theta(M \log N)$. Every greedy hop must check $\Theta(M \log N)$ neighbors across $\Theta(\log N)$ hops, giving polylogarithmic query time $O(d \cdot M \log^2 N)$ and build time $O(N \cdot d \cdot M \log^2 N)$. By introducing the Skip-List hierarchy, HNSW separates links by length scale across layers and strictly caps per-layer node degree at $O(M)$, cutting query and build time by a full $\Theta(\log N)$ factor:
$$\underbrace{O(d \cdot M \log^2 N)}_{\text{Single-Layer Flat NSW}} \;\xrightarrow{\text{Skip-List Scale Separation (cap degree at } M\text{)}}\; \underbrace{O(d \cdot M \log_M N) = O(d \log N)}_{\text{HNSW }(\mathbf{\Theta(\log N)\text{ TC gain}})}.$$
- Base-$M$ height compression vs. binary Skip Lists ($\log_M N$ vs. $\log_2 N$ levels): A binary skip list ($p = 1/2$) builds $\log_2 N$ levels ($\approx 20$ levels at $N = 10^6$). Because each HNSW node already fans out to $M$ directions per layer ($M = 16\text{–}32$), HNSW sets $p = 1/M$ ($m_L = 1/\ln M$), shrinking hierarchy height by $\log_2 M\times$ ($\log_{16}(10^6) = \mathbf{5\text{ levels}}$ vs. $\mathbf{20\text{ levels}}$) and scoring $M$ neighbors in a SIMD batch rather than chasing 20 serial pointers.
| Index Structure | Metric Space | Levels | Max Degree / Layer | Query Time Complexity | Build Time Complexity ($N$ items) | Space Complexity | Key TC Bottleneck or Gain |
|---|---|---|---|---|---|---|---|
Exact Brute-Force (Flat) | Any $\mathbb{R}^d$ | 1 | — | $O(N \cdot d)$ | $O(N \cdot d)$ | $O(N \cdot d)$ | Linear wall: scans 100% of corpus on every query |
| 1D Skip List (Pugh, 1990) | 1D total order ($\mathbb{R}^1$) | $O(\log_2 N)$ | $O(1)$ pointers | $O(\log_2 N)$ in 1D ($O(Nd)$ in $\mathbb{R}^d$) | $O(N \log_2 N)$ | $O(N)$ | Fast in 1D, but cannot route $\mathbb{R}^d$ neighborhoods without $2^d$ blowup |
| Single-Layer Flat NSW | General $\mathbb{R}^d$ | 1 (all scales) | $\Theta(M \log N)$ at hubs | $O(d \cdot M \log^2 N)$ | $O(N \cdot d \cdot M \log^2 N)$ | $O(N(d + M \log N))$ | Polylogarithmic bottleneck: hub degree grows as $O(\log N)$ |
| HNSW (Skip-List + NSW) | General $\mathbb{R}^d$ | $O(\log_M N)$ | Bounded $O(M)$ ($2M$ on L0) | $O\bigl(d \cdot M(\log_M N + \mathrm{efSearch})\bigr) = O(d \log N)$ | $O\bigl(N \cdot d \cdot M(\log_M N + \mathrm{efConstruction})\bigr) = O(N \log N)$ | $O\bigl(N(d + M)\bigr)$ | $\Theta(\log N)$ faster than Flat NSW by capping per-layer degree at $M$; $\log_2 M\times$ fewer levels than binary skip list |
Complete HNSW parameter reference: complexity terms, directional effects and extreme limits ($\to \infty$ vs. $\to 0$)
The reference table below answers how each HNSW parameter enters the time/space complexity, what happens when you increase it, whether you can push it to $\infty$ (or $N$) or shrink it to $0$ (or $1$), and how to set it in production:
| Parameter & Complexity Term | What Happens When You Increase It ($\uparrow$)? | Can You Increase It to $\infty$ (or $N$)? | Can You Decrease It to $0$ (or $1$)? | How to Set It in Practice |
|---|---|---|---|---|
efSearch (ef)Default: 16–64 | Range: 32–256TC: $+O(d \cdot M \cdot \mathrm{efSearch})$ | Keeps the stopping bar $\max_{w \in W} d(q, w)$ looser for longer, admitting more leads into min-heap $C$. Monotonically increases Recall@k (up to the build-time graph ceiling) and scales Layer 0 query TC linearly as $O(d \cdot M \cdot \mathrm{efSearch})$. Zero effect on RAM or build time. | Capped at $N$ — degrades query TC to $O(Nd + N\log N)$. Because visited prevents scoring any node twice, $\mathrm{efSearch} \ge N$ traverses the entire connected Layer 0 graph ($N$ distance checks), which is $5\times\text{–}20\times$ slower than a contiguous SIMD brute-force scan due to random pointer-chasing cache misses. | No — hard floor is $\mathrm{efSearch} \ge K$ (and $\ge 1$). At $\mathrm{efSearch} = 0$, heap $W$ has capacity $0$ and cannot hold even the entry point. All engines enforce $\mathrm{efSearch} \ge K$. At $\mathrm{efSearch} = 1$ ($K=1$), Layer 0 reduces to pure greedy hill-climbing and halts at the first local minimum. | Enforce $\mathrm{efSearch} \ge K$. Start at 64, sweep 16 → 512 on a validation set, and pick the knee of the Recall-vs.-latency curve (64–128). |
MDefault: 16 | Range: 12–64TC/Space: $\mathcal{T} \propto d \cdot M$, $\mathcal{S} = O(N(d+M))$ | Increases bidirectional links per node, raising the recall ceiling (especially in high dimensions $d \ge 768$). Graph RAM grows linearly as $O(N \cdot M)$ ($\approx 8.5 \times M$ bytes/vector), and per-hop query/build work scales as $O(d \cdot M)$ while hierarchy height shrinks as $\log_M N$. | No — $M \to N$ degrades Space to $O(N^2)$, Query TC to $O(Nd)$, and Build TC to $O(N^3)$. Layer 0 becomes a complete graph ($O(N^2)$ integers) and expanding just the Layer 0 entry point scores all $N-1$ vectors. Even $M > 128$ loses to $M = 32\text{–}64$ on QPS at equal recall. | No — hard floor is $M \ge 2$ (practically $M \ge 4$). At $M = 0$, zero edges exist ($N$ isolated vertices; search cannot step away from the entry point). At $M = 1$, the graph shatters into disconnected pairs/trees. | Use M = 16 for $d \le 768$. Raise to M = 32–48 for $d \ge 1024$ or $\text{Recall}@10 > 0.99$. Use M = 8–12 only under tight RAM limits. |
M_max & M_max0Default: $M, 2M$ TC role: Caps degree at $O(M)$ | Allows popular “hub” nodes to hold more incoming reverse edges before triggering Algorithm 4 pruning, preventing hub bottlenecks on Layer 0 at the cost of larger fixed adjacency arrays per node. | No — $M_{\max} \to \infty$ destroys HNSW’s $O(\log N)$ TC advantage over Flat NSW. Uncapped hubs accumulate $\Theta(M \log N)$ or $O(N)$ edges just like Flat NSW, degrading query TC back to $O(d \cdot M \log^2 N)$ or $O(Nd)$. | No — must satisfy $M_{\max0} \ge M$. At $M_{\max0} = 0$, no node can store edges. If $M_{\max0} < M$, newly inserted nodes immediately prune the $M$ edges they just wired. | Keep at $M_{\max} = M$ and $M_{\max0} = 2M$ (configured automatically from M). |
efConstructionDefault: 200 | Range: 100–500TC: $+O(N \cdot d \cdot M \cdot \mathrm{efConstruction})$ | Widens the beam search during node insertion so Algorithm 4 selects from true nearest/diverse neighbors. Raises the recall ceiling with zero increase in index RAM or query TC; scales build time linearly as $O(N \cdot d \cdot M \cdot \mathrm{efConstruction})$. | Capped at $N$ — degrades Build TC from $O(N \log N)$ to $O(N^2 d)$ with zero graph gain past saturation. Once efConstruction discovers the true local neighborhood (200–500), the chosen $M$ edges stop changing. | No — hard floor is $\mathrm{efConstruction} \ge M$ (and $\ge 1$). At $0$, no candidates are found. At $\mathrm{efConstruction} = 1$, nodes wire only to greedy local minima, permanently baking disconnected islands into the graph. | Set $\mathrm{efConstruction} \ge 2M$ (100–200 for $M=16$, 200–400 for $M=32$) until build validation recall is $\ge 0.95$. |
m_LDefault: $1/\ln(M)$ TC: $L_{\max} = \Theta(m_L \ln N)$ | Raises promotion probability $e^{-1/m_L}$ to upper layers, growing hierarchy height as $\Theta(m_L \ln N)$ and increasing upper-layer RAM and Phase 1 descent hops. | No — $m_L \to \infty$ creates an infinite tower of duplicate layers ($L_{\max} \to \infty$) ($e^{-1/m_L} \to 1$), blowing up memory and descent time. | Yes ($m_L = 0$ is valid!) — collapses HNSW into a 1-layer flat graph ($L_{\max} = 0$) ($\ell = 0$ for all nodes). Without upper-layer expressways, worst-case routing hops grow from $O(\log N)$ toward $O(N^{1/d})$ (or $O(\log^2 N)$ if hub degree is uncapped). | Leave at the theoretical optimum $m_L = 1/\ln(M)$ ($\approx 0.3607$ for $M = 16$). |
Algorithm 4 HeuristicDefault: ONTC: $O(M \cdot \mathrm{efConstruction})$ / insert | Filters candidates by $d(q, e) < d(r, e)$ so edges span diverse angles and bridge separate clusters. keepPrunedConnections = true backfills to degree $M$. | Enabling extendCandidates = true expands neighbors-of-neighbors before pruning, increasing per-insert pruning TC to $O(M^2 \cdot \mathrm{efConstruction})$ (helpful only on ultra-clustered low-$d$ manifolds). | Turning the heuristic OFF (naive $M$-nearest) traps all edges inside tight clusters, creating disconnected islands that cause catastrophic recall failure regardless of efSearch. | Always keep Algorithm 4 Heuristic = ON with keepPrunedConnections = true and extendCandidates = false. |
References and further reading
- Malkov and Yashunin: HNSW — nested graph levels, layer search, insertion and navigation-aware neighbor selection.
- hnswlib: algorithm parameters — the meaning of M, construction effort and query ef, including its relationship to K.
- hnswlib: search implementation — separate candidate and retained queues, visited nodes and stopping conditions.
- Spotify Annoy: API and tradeoffs — build versus query settings, angular distance, index immutability and memory-mapped loading.
- Annoy: split and search implementation — randomized two-center splits, prioritized branch exploration, candidate deduplication and distance scoring.