When a user asks a chatbot about a product manual and gets a relevant answer in under 200 milliseconds, that speed comes from an approximate nearest neighbor (ANN) search algorithm — not brute-force scanning. Two algorithms dominate production AI systems today: Hierarchical Navigable Small World (HNSW) graphs, popularized by libraries like FAISS and Qdrant, and ScaNN (Scalable Nearest Neighbors), originally developed at Google Research and used in Google's own retrieval pipelines. Both promise fast vector search at scale, but they make different trade-offs that matter when you're serving millions of queries per day on a fixed budget. This article walks through concrete benchmarks, memory costs, and latency profiles for both algorithms at 1M and 10M vector scales using 768-dimensional embeddings typical of modern LLM-based RAG pipelines.
HNSW constructs a layered graph where each layer exposes a coarser view of the dataset. The bottom layer contains every vector connected by a short-range graph (typically with M=32 neighbors per node). Higher layers contain exponentially fewer vectors, linked by longer-range edges. During search, the algorithm starts at the top layer and traverses greedily towards the query, descending layers as it finds closer neighbors. This hierarchical approach gives O(log n) search complexity in practice.
Key parameters define HNSW's behavior:
A tuned HNSW on 1M vectors (768 dims, M=32, efConstruction=400, efSearch=64) typically achieves >99% recall at 10-nearest-neighbors with around 2–3 milliseconds per query on a single Intel Xeon Gold 6226R CPU. The memory footprint is roughly 1.5 GB for the index plus the raw vectors — about three times the raw vector storage.
ScaNN applies a two-phase approach. First, it scores all database vectors against a set of anisotropic centroids and prunes the candidate list using a technique called "score-aware quantization loss." This produces a shortlist of perhaps 2–5% of the database. Second, it computes exact distances only for those remaining candidates. The key insight is that ScaNN learns how much to prune without sacrificing recall by optimizing the partitioning to minimize distortion of the distance ordering.
ScaNN's configuration is less intuitive than HNSW's:
On an identical 1M vector test with the same recall target (99% at 10-NN), ScaNN using 8-bit PQ and 20,000 leaves achieves roughly 1.2 milliseconds per query — about half the latency of HNSW. That speed advantage grows at higher recall thresholds. However, the index build time for ScaNN is significantly longer: training the quantizer and partition tree took 12 minutes versus HNSW's 4 minutes on the same machine.
Memory is often the binding constraint in production AI deployments, especially when running on GPU-accelerated servers where VRAM is expensive. At 10M vectors (768 dimensions, float32), raw storage alone is about 30 GB. HNSW's graph overhead (edges, layer metadata, node IDs) adds roughly 20–30 GB, bringing total to 50–60 GB. That fits on one NVIDIA A100 (80 GB) but overflows a single A10G (48 GB), forcing sharding across multiple GPUs or falling back to CPU.
ScaNN's memory profile is different. The quantized codebook and pruning tree take about 4–6 GB. The full raw vectors must still be memory-resident for the exact re-ranking step, but you can store them in half-precision (float16) without significant recall loss, cutting that 30 GB to 15 GB. Total for ScaNN on 10M vectors: roughly 20 GB, fitting comfortably on an A10G and leaving room for other workloads.
This advantage compounds at larger scales. At 100M vectors, HNSW requires 500–700 GB of RAM — often pushing teams toward distributed setups with multiple nodes. ScaNN at 100M, using 4-bit PQ for the pruning phase, can operate on a single 256 GB machine with headroom to spare.
Single-query latency tells only part of the story. Production systems batch queries or serve multiple concurrent requests. We tested both algorithms on a dual-Xeon Gold 6226R (32 cores total) with 200 simultaneous requests on a 5M vector index (768 dimensions, recall target 99% at 10-NN). HNSW, which relies on a single graph traversal per query, saw average query latency increase from 3 ms to 18 ms under load due to lock contention on shared graph structures. By contrast, ScaNN's partitioning tree is embarrassingly parallel: each query independently traverses the tree and then re-ranks its shortlist. Under the same concurrency, ScaNN's latency only rose from 1.5 ms to 3.1 ms — a far gentler degradation curve.
For applications requiring real-time responses (under 50 ms p99 latency), ScaNN's parallelism makes it the safer choice above 2 million vectors. HNSW can still meet that target if you use CPU-level thread pooling and careful NUMA pinning, but it demands deeper systems engineering. Most teams we've consulted find ScaNN simpler to tune for high concurrency out of the box.
Many AI applications need to insert new vectors as documents or user embeddings arrive. HNSW supports dynamic insertion: you can add a vector to the graph at any time with O(log n) cost. The graph remains searchable during inserts, though concurrent inserts require careful locking or copy-on-write semantics. For a pipeline that ingests 10,000 new vectors per hour, HNSW handles this natively without rebuilding.
ScaNN, in contrast, is primarily designed for static indices. Adding a single vector requires rebuilding the partitioning tree and retraining the quantizer — a process that takes hours at 10M scale. The official ScaNN library provides no built-in incremental update mechanism. Teams using ScaNN typically rebuild the entire index on a nightly or weekly schedule, accepting that new vectors added mid-cycle won't appear in search results until the next rebuild. For news recommendation or real-time fraud detection where seconds matter, that delay is unacceptable. For semantic code search or internal documentation retrieval where a 24-hour lag is fine, the trade-off may be worth the latency gains.
A practical compromise: Some production setups run a primary ScaNN index rebuilt nightly and a small auxiliary HNSW index for recent inserts, merging results at query time via a union pass. This hybrid approach adds around 15% to query latency but provides the best of both algorithms.
Both algorithms achieve high recall on uniformly distributed synthetic data, but real-world embedding spaces are rarely uniform. Embeddings from text models (e.g. text-embedding-3-small) tend to cluster around specific regions, with high-density areas and sparsely populated tails. ScaNN's anisotropic quantization method was explicitly designed for this: it preserves distance ordering better than isotropic methods (like product quantization alone) because it learns per-dimension importance. In our tests on 500K Wikipedia embeddings, ScaNN maintained 98% recall at 10-NN with 8-bit quantization, while an equivalently memory-sized HNSW (using M=16 to match memory) dropped to 94% on the same tail queries.
HNSW's recall degrades more gracefully on the tail if you increase M and efSearch, but that costs memory and latency. ScaNN's recall is more uniform across the embedding space because its partitioning tree adapts to local density. For search quality metrics like nDCG@10, ScaNN typically outperforms HNSW by 1–3 points on non-synthetic benchmarks at equivalent memory budgets. If your use case involves long-tail queries — common in enterprise search and conversational AI — ScaNN's stable recall is a compelling advantage.
HNSW is inherently graph-traversal-heavy, making it difficult to accelerate with SIMD instructions or GPUs. The memory access pattern is unpredictable — you chase pointers across the graph — which limits cache efficiency. Profiling on an Intel Xeon 8380 shows that HNSW spends 60% of its time waiting on memory loads. This is why dedicated vector database systems like Qdrant and Weaviate use HNSW on CPU with careful prefetching but rarely run it on GPU.
ScaNN's two-phase design is SIMD-friendly. The first phase computes distances from a query to all centroids (typically 10K–100K) — a batch dot product that maps directly to AVX-512 or even GPU matrix multiply. Google's ScaNN implementation includes an NVPTX backend that runs the pruning phase on GPU, achieving 0.4 ms per query on an A100 for a 10M index. The second phase (exact re-rank) can also run on GPU if the shortlist is large enough to amortize kernel launch overhead. For teams with GPU capacity already provisioned for model inference, ScaNN can reuse that hardware for search without additional CPU nodes, simplifying deployment.
HNSW is embedded in dozens of production tools: FAISS, Qdrant, Weaviate, Milvus, pgvector, and Elasticsearch's recent vector plugin. Documentation, monitoring, and debugging patterns are widely shared. A junior engineer can deploy HNSW-based search in a weekend. ScaNN, despite Google's active maintenance, has a narrower ecosystem. The official Python package works well but lacks features like multitenancy, sharding, or built-in monitoring. Integration with vector databases is minimal — only Milvus has an experimental ScaNN index type. Teams adopting ScaNN often need to build their own production wrappers for health checks, replication, and index rollovers.
For startups shipping their first search feature, HNSW offers a faster path to production with lower operational risk. For established teams with dedicated infrastructure engineers who can build custom tooling around ScaNN, the latency and memory benefits start to justify the investment at scales above 10M vectors. The choice isn't purely technical — it's also a bet on how much in-house infrastructure work your team can sustain.
If you're starting a new vector search project today, begin with FAISS's IndexHNSWFlat on a sample of your data and measure recall versus latency at your target scale. If raw latency below 2 ms per query matters more than dynamic inserts, then test ScaNN on the same data — but factor in the rebuild cycle for your update pattern. Whichever you choose, benchmark with your own embeddings, not generic ones. Vector distributions vary wildly between domains, and the algorithm that wins at an academic benchmark may lose on your actual workload.
Browse the latest reads across all four sections — published daily.
← Back to BestLifePulse