Vamana: The algorithm behind Disk-ANN
Vamana is a graph-based approximate nearest neighbor algorithm that underpins Disk-ANN. Unlike HNSW, it is a single-layer graph with a bounded out-degree: each node has at most a fixed number of outgoing edges. This makes it possible to lay out the graph on disk so that each node (and its neighbors) fit in a small number of blocks, reducing random I/O during search. Query is a greedy walk similar to other graph ANN: start at an entry point, repeatedly move to the neighbor closest to the query until no improvement, returning the best k found. This topic covers build, search, and why Vamana fits disk.
Summary
- Single-layer graph, bounded out-degree; build via insert-and-prune so that graph remains navigable. Designed for disk layout and low I/O. Compare to HNSW (hierarchical, higher degree).
- Build: add nodes, find approximate neighbors, add edges, prune to enforce degree bound. Query: greedy walk from entry point.
- Bounded degree enables packing each node (and neighbors) into few disk blocks; layout and caching minimize random I/O.
- Trade-off: predictable I/O and disk-friendly layout vs. HNSW’s often slightly better in-memory recall; on disk, Vamana’s layout can win.
- Practical tip: tune degree bound and build-time candidate count (like efConstruction); use for disk-first or when memory-per-node must be fixed.
Build and search
During build, nodes are added one by one (or in batch). For each new node, you find its approximate nearest neighbors in the current graph, add edges to and from them, then prune the graph so that every node’s out-degree does not exceed the bound (e.g. keep the most useful edges for navigation). Parameters include the degree bound and the number of candidates considered during search (similar to efConstruction). The result is a graph where every node has a small, fixed number of neighbors, so storing and loading one node is a small, predictable I/O.
Query pipeline: start at entry point (fixed or from a small set) → repeatedly expand neighbors, move to closest to query → stop when no improvement → return best k. Same greedy idea as HNSW but on a single layer with bounded degree.
Why it fits disk
Because out-degree is bounded, you can pack a node and its neighbor IDs (and optionally the node’s vector) into one or a few contiguous disk blocks. When the search visits a node, it reads those blocks; with a good layout (e.g. clustering frequently co-visited nodes), you get mostly sequential or localized reads. HNSW’s hierarchical layers and variable connectivity are harder to pack as predictably, which is why Vamana is often chosen for disk-first systems even though HNSW can give slightly better in-memory recall.
Trade-offs and practical use
Vamana trades a bit of in-memory recall (vs. HNSW) for predictable, disk-friendly layout. When the index is on SSD, I/O dominates; Vamana’s bounded degree and layout can yield better end-to-end latency and throughput than trying to run HNSW on disk. Inserts: add node, connect to neighbors, prune. Deletes: typically tombstoning or periodic rebuild, as with other graph indexes. Practical tip: use Vamana when you target disk or need fixed memory per node; use HNSW when you are in-memory and want maximum recall for a given latency.
Frequently Asked Questions
Vamana vs HNSW: which has better recall?
In memory, HNSW often has an edge due to the hierarchy. On disk, with the same memory budget (e.g. cache), Vamana’s predictable layout can make better use of I/O, so end-to-end recall and latency depend on the implementation and workload.
Can I use Vamana in memory?
Yes. It’s a valid in-memory graph index; the bounded degree keeps memory predictable. Many implementations support both in-memory and disk-backed modes.
How is the entry point chosen?
Typically a fixed node (e.g. the first or a random node) or a small set of entry points. Some systems build a short list of “start” nodes for different regions to reduce the length of the walk.
Does Vamana support inserts and deletes?
Inserts can be done by adding a node and connecting to neighbors, then pruning. Deletes are trickier (as with graph indexes); common approaches are tombstoning or periodic rebuild. Implementation-dependent.