DiskANN

DiskANN stores the primary search index—a Navigable Small World (NSW) graph—directly on Solid State Drive (SSD). Vectors are stored contiguously on disk, and the graph structure holds pointers (offsets) to these vector locations. This design exploits the high sequential read bandwidth and low random access latency of modern SSDs, allowing the system to hold orders of magnitude more data than RAM-limited indexes like pure HNSW.

• The on-disk graph is built to maximize locality, grouping connected nodes close together on disk to minimize seek times during traversal.
• Search involves greedily walking this graph, reading vector data from disk only for the nodes visited.

To mitigate SSD access latency, DiskANN maintains a small, dynamic in-memory cache of frequently accessed data. Crucially, it caches two distinct elements:

• Graph Neighborhood: The connectivity list (edges) of the NSW graph for cached nodes. This is tiny (just lists of IDs) and allows the algorithm to plan its traversal without disk I/O.
• Vector Data: The actual vector embeddings for a subset of nodes. The system employs a cost-aware caching policy that prioritizes caching vectors for nodes that are central hubs in the graph, as visiting them is highly probable during many searches.

This hybrid approach ensures that RAM is used as a smart accelerator, not a storage bottleneck, typically requiring only 1-5% of the total dataset size in memory.

DiskANN uses the Vamana algorithm to build its underlying graph index. Vamana is a graph construction method similar to HNSW but optimized for a disk-resident setting. Its key features include:

• Robust Pruning: During insertion, Vamana aggressively prunes edges from new and existing nodes to maintain a constant out-degree (e.g., 64-128), which is critical for controlling the size of the on-disk index and the cache footprint.
• Long-Range "RNG" Edges: It ensures the graph contains Relative Neighborhood Graph (RNG) edges, which act as "highways" for greedy search, preventing traversal from getting stuck in local minima and enabling high recall with short search paths.
• The construction is a single-pass process, making it suitable for large-scale batch indexing.

DiskANN's query algorithm uses a beam search (or greedy beam search) strategy tailored for disk I/O. Instead of exploring one path at a time, it maintains a priority queue (candidate list) of fixed size (L).

1. The search starts from a few entry points.
2. It expands the top candidates in the queue by fetching their graph neighbors and corresponding vectors from disk (or cache).
3. New candidates are added to the queue, which is then pruned back to size L.

This approach is I/O-efficient because it amortizes the cost of a disk read: fetching one vector from disk allows the evaluation of all its neighbors in the queue. The beam width L is a tunable parameter that balances I/O, accuracy, and latency.

Performance is controlled via intuitive search-time parameters that directly manage the I/O-compute trade-off:

• L (Search List Size): The beam width. A larger L explores more candidates per iteration, increasing accuracy (recall) and disk I/O.
• R (Beam Width): Often synonymous with L, controlling the breadth of the search.

These parameters allow operators to dial in the required Service Level Agreement (SLA). For example, a low-latency application might use a small L, accepting slightly lower recall, while a batch processing job can use a large L for maximum accuracy. The design ensures that even at the highest quality settings, the memory footprint remains constant.

DiskANN solves a different scalability problem than purely in-memory indexes like HNSW.

DiskANN is not a replacement for HNSW but a complementary technology for the next order of magnitude in data scale.

DiskANN's primary application is enabling approximate nearest neighbor (ANN) search on datasets with hundreds of millions to billions of vectors. By storing the primary graph index on Solid-State Drives (SSD) and caching only a small working set in RAM, it bypasses the memory bottleneck of purely in-memory indices like HNSW or IVFPQ. This makes it feasible to search colossal embedding spaces—common in web-scale recommendation, image retrieval, or enterprise document search—on servers with tens of GBs of RAM instead of terabytes.

In Retrieval-Augmented Generation (RAG) pipelines, DiskANN drastically reduces the infrastructure cost of the retrieval layer. It allows enterprises to deploy a high-performance semantic search over a large, proprietary knowledge base without provisioning expensive, high-memory cloud instances. The system maintains millisecond-level query latencies for cached hot data while efficiently handling cold data from disk, enabling accurate context retrieval for LLMs from massive internal document repositories, codebases, or support ticket histories on a budget.

DiskANN is deployed in large-scale recommendation engines where the candidate pool (e.g., products, videos, articles) is represented as dense embeddings. Its ability to perform fast Maximum Inner Product Search (MIPS) or cosine similarity search on a disk-resident index supports real-time personalization for millions of users. The architecture allows for efficient batch querying, maximizing SSD I/O bandwidth to serve thousands of queries per second, making it suitable for news feeds, e-commerce platforms, and streaming media services.

Unlike systems requiring full index rebuilds, DiskANN supports incremental updates. New vectors can be inserted into the graph index with minimal disruption, enabling near-real-time retrieval on evolving datasets. This is critical for applications like:

• Social media search with constantly new content.
• Log and telemetry analysis where new events are continuously indexed.
• Financial time-series retrieval with streaming market data. The system manages these updates while maintaining search quality and performance, avoiding costly downtime for re-indexing.

The disk-based design makes DiskANN ideal for multi-tenant SaaS applications where each tenant has a large, isolated vector dataset. A single server can host dozens of separate DiskANN indices on its storage drive, each serving a different customer, with memory caching adapted per tenant's query patterns. This provides strong resource isolation and cost efficiency compared to loading all tenant data into a shared, monolithic in-memory index, which would require prohibitively large RAM.

DiskANN efficiently combines vector similarity search with metadata filtering. During search, the algorithm can prune graph traversal paths based on attached scalar attributes (e.g., date > 2023, category = 'legal'). This enables complex, multi-modal queries common in enterprise search: "Find technical documents about neural networks from the last quarter." The filtering is integrated into the graph search process, avoiding the latency penalty of a naive post-filtering approach that might discard all initially retrieved results.

Approximate Nearest Neighbor Search (ANN) is a family of algorithms designed to efficiently find vectors in a high-dimensional dataset that are most similar to a query vector. It trades perfect accuracy for significantly reduced search latency and computational cost, which is essential for real-time applications like RAG. DiskANN is a specific implementation optimized for disk-based storage.

• Core Trade-off: Balances recall (accuracy) against query latency and memory usage.
• Algorithm Families: Includes graph-based methods (e.g., HNSW), hashing-based methods (e.g., LSH), and quantization-based methods (e.g., PQ, IVF).

Hierarchical Navigable Small World (HNSW) is a graph-based ANN algorithm that constructs a multi-layered graph for fast search. It is a primary in-memory algorithm and often serves as the underlying graph structure that DiskANN stores on SSD. Long-range connections on higher layers enable fast, greedy traversal to find nearest neighbors.

• In-Memory Benchmark: Often the gold standard for high-recall, low-latency in-memory search.
• DiskANN Relation: DiskANN can persist an HNSW-like graph to disk, caching only the top layers in RAM.
• Key Parameter: efSearch controls the size of the dynamic candidate list during search, directly affecting the recall-latency trade-off.

Product Quantization (PQ) is a lossy compression technique that dramatically reduces the memory footprint of vectors by splitting them into subvectors and quantizing each subspace. IVFPQ combines PQ with an Inverted File Index (IVF) for cluster pruning.

• PQ Mechanism: Represents a 128-dimensional vector as a short 8-byte code, enabling billion-scale indices to fit in RAM.
• IVFPQ Workflow: 1) IVF selects the nprobe most relevant clusters. 2) PQ approximates distances within those clusters using lookup tables.
• Contrast with DiskANN: While IVFPQ optimizes for memory, DiskANN optimizes for disk-throughput, often achieving higher recall for the same latency on SSD-resident data.

The recall-latency trade-off is the fundamental compromise in ANN search between accuracy (finding the true nearest neighbors) and speed (query response time). System design involves tuning parameters to meet specific Service Level Agreements (SLAs).

• Recall: The fraction of true top-K neighbors found by the approximate search.
• Latency: The time from query submission to result return, often measured as P95 or P99.
• Tuning Knobs: In DiskANN/HNSW, efSearch. In IVF, nprobe. Increasing these values improves recall but increases latency.
• System Goal: Achieve the required recall (e.g., 95-99%) at the lowest possible latency and resource cost.

Faiss (Facebook AI Similarity Search) and ScaNN (Scalable Nearest Neighbors) are leading open-source libraries for efficient similarity search. They provide optimized, in-memory implementations of algorithms like IVF, PQ, and HNSW.

• Faiss: Developed by Meta. Offers extensive GPU acceleration and is a standard benchmark. Includes IVFPQ and HNSW implementations.
• ScaNN: Developed by Google Research. Introduces anisotropic vector quantization to better optimize the loss function for Maximum Inner Product Search (MIPS), common with dense retrievers.
• Comparison to DiskANN: These are primarily in-memory libraries. DiskANN addresses the use case where the dataset exceeds affordable RAM, leveraging fast SSDs as primary storage.

P99 Latency and Multi-Stage Retrieval are critical concepts for production RAG systems focusing on consistent performance and optimal quality.

• P99 Latency: The worst-case latency experienced by 1% of queries. A key SLA metric for user-facing applications. DiskANN's predictable I/O patterns help control P99.
• Multi-Stage Retrieval: A cascaded architecture to optimize the precision-latency trade-off.
  1. First Stage: A fast, high-recall retriever (e.g., DiskANN) fetches 100-500 candidates.
  2. Second Stage: A slower, precise cross-encoder reranker scores and reorders the small candidate set.
• Benefit: Achieves high final accuracy with low overall latency, as the expensive model runs on only a few documents.