← Back to list
AI & Data
#ANN#벡터인덱스#HNSW#IVF-PQ#벡터검색
Last updated · 2026-11-11

Approximate Nearest Neighbor Search (ANN) and Vector Indexes (HNSW·IVF·PQ)

1. Overview

A. Definition

Approximate Nearest Neighbor (ANN) search is a search technique that, when finding the top-K vectors closest to a query vector in a high-dimensional vector space, abandons brute-force search (computing the distance to every vector one by one) and instead sacrifices a little accuracy (recall) to drastically shrink the search space, thereby lowering query latency by tens to thousands of times; the data structure that organizes vectors in advance as graphs, clusters, or quantization codes for this purpose is called a vector index.

The question ANN answers is "what are the K items most semantically similar to this query vector." Document, image, and user vectors expressed as [[embedding]]s typically reach hundreds to thousands of dimensions, and similarity is defined as the cosine similarity or Euclidean distance between those vectors. Answering exactly requires computing the distance to all N vectors for each query, so the cost grows linearly as O(N·d). For [[rag]], recommendation, and search services that must search hundreds of millions of vectors within milliseconds, this brute-force search is practically impossible. ANN redefines the problem as finding, "not the exact #1 but candidates likely to be in the top K, quickly and with high probability."

Here it is important not to confuse ANN with a [[vector-database]]. A vector database is the system (product) responsible for storing, updating, filtering, replicating, and transacting on vectors, whereas ANN is the core algorithm/index layer that handles "how to quickly narrow down candidates near a given query" inside it. In other words, the engine that effectively determines a vector DB's search performance is the ANN index, and even with the same embeddings, recall, latency, memory, and cost turn out entirely different depending on which index is configured with which parameters.

B. Background and Necessity

As deep representation learning became ubiquitous, text, images, speech, and behavior logs were all reduced to high-dimensional embedding vectors, and vector search—searching, recommending, and detecting by "semantic similarity" rather than "keyword match"—became a core service feature. In the generative-AI era, [[rag]] injects relevant documents retrieved as vectors from a knowledge base on every query to reduce LLM hallucination, so the latency and recall of vector search directly govern both response quality and response speed. The problem is scale. When enterprise documents, products, and users reach tens of millions to billions of vectors, brute-force search takes seconds per query and exceeds the latency budget of interactive services.

The very fact of high dimensionality makes this problem harder. Because of the curse of dimensionality, traditional spatial indexes that partition space into grids (the k-d tree and R-tree family of [[multidimensional-index]]) see pruning efficiency drop sharply beyond hundreds of thousands of dimensions, becoming effectively no different from brute force. That is, finding the "exact" nearest neighbor quickly in high dimensions is fundamentally expensive, as confirmed in both theory and practice. ANN engineers around the operational reality that "even if 1–2% of search results are not the true nearest neighbors, it has almost no impact on recommendation or RAG quality," trading a small concession in accuracy for a large reduction in latency and cost.

The necessity is clear in numbers. Brute-forcing 100 million 768-dimensional vectors requires about 10^11 floating-point operations per query, taking seconds on a single core. By contrast, a graph index like HNSW achieves recall above 95% in milliseconds with only a few thousand distance computations per query. This four-to-five-order-of-magnitude speed gap is why ANN has become the de facto standard search technique for large-scale vector services.

C. Characteristics

ANN performance is expressed not as a single number but as a four-dimensional trade-off among recall, latency/QPS, memory, and build time. Whereas brute force guarantees 100% recall at high cost, ANN selects a point on this trade-off curve by tuning parameters. Therefore "ANN is fast" must always be interpreted together with the condition "at what recall," and a latency figure that does not report recall is meaningless—this is the first principle of the field.

Another characteristic is that three design axes are orthogonal to one another. An ANN index is largely composed of combinations of ① graph search (HNSW), ② clustering-based candidate reduction (IVF), and ③ vector compression (PQ), which solve the distinct problems of "how to narrow," "how much to narrow," and "how small to store." So a practical index is usually not a single technique but combines several axes, like IVF+PQ or HNSW+PQ, to meet memory, recall, and latency requirements at once.

Finally, ANN must be operated on the premise that it is sensitive to data and query distribution. Even with the same algorithm and parameters, recall varies with the embedding's dimensionality, how clustered the vectors are in space (clusteredness), and how closely the queries resemble the data distribution. So "settings that worked well in service A" do not carry over unchanged to service B, and even benchmark-verified figures must be re-measured on one's own data. This data dependence is a core premise revisited repeatedly in the later sections on parameter design and operational monitoring.

2. Structure and Operating Principle

ANN's overall structure becomes clear when understood as a two-stage pipeline: "when a query arrives, ① the index quickly narrows to a small set of candidates (candidate generation), ② precise distance computation ranks only those candidates (reranking), and ③ the top K are returned." How much you shrink the candidate set on which distance is computed out of all N is the speed, and how many true nearest neighbors are inside that candidate set is the recall.

flowchart TB
    Q["query vector q (d-dim)"] --> IDX["vector index search (graph·cluster·quantization)"]
    IDX --> CAND["candidate set (a few out of all N)"]
    CAND --> RR["precise distance recomputation·rerank (reranking)"]
    RR --> TOPK["return top-K results"]
    subgraph BUILD["offline index build"]
      V["N embedding vectors"] --> B["index build (graph links·k-means·codebook training)"]
      B --> IDX
    end

The key metric in this pipeline is Recall@K. If G is the set of a query's true nearest K and R is the K returned by the index, then Recall@K = |G ∩ R| / K. For example, Recall@10 = 0.98 means "on average 9.8 of the top 10 match the brute-force result." A service typically tunes parameters toward "the minimum latency that satisfies Recall@10 ≥ 0.95," and this target recall is precisely the starting point of ANN design.

The distance/similarity definition also affects design. Euclidean distance (L2), inner product, and cosine similarity are mainly used; cosine becomes equivalent to inner product once vectors are normalized, so many engines handle it as inner product after normalization. Because the index's cluster boundaries and graph links change depending on which distance is used, matching the distance the embedding model was trained with to the index's distance is a hidden premise of recall. In practice, a mismatch of "the embedding was trained with cosine but the index was built with L2" is a common cause of recall degradation, so it is safe to document the distance-metric setting together with the embedding convention when creating the index.

The efficiency of the candidate-generation stage also matters because it dominates the whole. Reranking is cheap only when candidates are small—hundreds to thousands—so an index design that "includes the true nearest neighbors in a small candidate set with high probability" is the essence of ANN. The three algorithms in the next section are different answers to precisely this problem of "making good candidates cheaply."

Here we must note why graph, cluster, and quantization are used instead of traditional spatial indexes. In low dimensions (2–3-dimensional geographic coordinates), k-d trees and R-trees prune the search space effectively by alternately splitting axes. But in hundreds of dimensions, because of distance concentration, where all points lie at similar distances from one another, pruning that "looks only at the near branch and discards the far one" stops working. That is, the tree's branching condition ends up opening almost every branch, degrading into brute force. The ANN family circumvents this limit by "abandoning exact boundary guarantees and gathering only statistically near candidates," which is the fundamental reason one has no choice but to choose approximation in high dimensions.

3. Major Index Algorithms — HNSW · IVF · PQ

The three representative algorithms each handle the search space with a different strategy of graph, partition, and compression. Rather than simply listing them, understanding "what each tried to solve" grounds the rationale for combination and parameter choice.

flowchart LR
    subgraph HNSW_G["HNSW (hierarchical graph)"]
      L2["upper layer (sparse·long-range edges)"] --> L1["middle layer"]
      L1 --> L0["bottom layer (dense·short-range edges)"]
    end
    subgraph IVF_G["IVF (inverted file·cluster)"]
      C["query → select nearest nprobe clusters"] --> CELL["search only that cell's vectors"]
    end
    subgraph PQ_G["PQ (product quantization)"]
      SUB["split vector into m subvectors"] --> CODE["compress each part to a codebook ID"]
    end

A. HNSW (Hierarchical Navigable Small World graph). HNSW stacks, in multiple layers, a proximity graph where vectors are nodes and "nearby vectors are connected by edges." The upper layers have few nodes and long edges to jump far, and the lower you go the denser it becomes for fine-grained approach. A query starts from an entry point in the topmost layer and descends layers by repeating a greedy search that "moves to the neighbor of the current node that is closer to the query." This is like taking a highway to roughly the right location and then finding the destination via side streets and alleys, reducing distance computations per query to close to logarithmic scale rather than all N. Key parameters are the number of edges per node M (graph density·memory), the search width at build time efConstruction (graph quality·build time), and the search width at query time efSearch (recall·latency). In particular efSearch is "the size of the candidate list kept per query"; raising it increases recall and proportionally increases latency, making it the main dial that adjusts recall-latency in real time. HNSW belongs to the axis with the best recall-latency curve, but because it must store graph edges in addition to the original vectors, it typically incurs 30–50% extra memory relative to the vectors.

B. IVF (Inverted File Index). IVF first partitions all vectors into nlist clusters (cells) with k-means and sets each cell's centroid as a "coarse quantizer." When a query arrives, it opens only the nprobe cells nearest to the query—not all vectors—and computes distances only to the vectors within them. With nlist=10,000 and nprobe=16, on average only about 0.16% of the whole is searched, so distance computation shrinks by hundreds of times. Here nprobe is the main dial of recall-latency. Opening few is fast but may miss the true nearest neighbor when the query is near a cell boundary and it sits in an adjacent cell; opening many raises recall but increases latency. IVF has a simple structure and small memory overhead, so it is widely used combined with PQ in large-scale, memory-constrained environments.

C. PQ (Product Quantization). PQ is not a search strategy but a vector-compression technique that reduces memory and distance-computation cost at the same time. It splits a d-dimensional vector into m subvectors and then replaces each subspace with the ID of a codebook (typically 256 representative vectors) trained by k-means. A single vector is then compressed into m 1-byte codes, reducing, for example, a 768-dimensional float vector (3,072 bytes) to 96 bytes at m=96—about 32×. At query time, the distances between each of the query's subvectors and the codebook's representative vectors are precomputed into a table (asymmetric distance computation, ADC), and a candidate vector's distance is approximated by summing table entries via its code IDs, so distance computation also becomes very fast. The price is recall degradation due to quantization error, and to compensate, a design that filters first-stage candidates with PQ and then reranks with the original vectors is commonly used.

Combining the three techniques is the practical standard. Because compression is essential to fit billions of vectors in memory, IVF+PQ becomes the mainstay combination for large scale, while HNSW (and HNSW+PQ when needed) is used when recall-latency is the top priority and memory is ample. In other words, the essence of ANN design is to assemble the axes so that "IVF or HNSW handles how much to narrow, and PQ handles how small to store."

A typical means to recover recall in a compressed index is two-stage reranking. In the first stage, distance approximation with PQ codes cheaply narrows to thousands of candidates; in the second stage, exact distances are recomputed with original (or high-precision) vectors only for those candidates to finalize the top K. Because the candidates are small, the second stage's precise-computation cost is small, and it corrects the ranking disturbed by quantization error, raising recall. This structure of "narrow with cheap approximation and finalize with expensive precision" is the core design pattern of ANN that takes both compression and accuracy.

4. Comparison and Parameter Design

Algorithm choice is not "what is fastest" but "what is optimal under the given memory and recall requirements." The table below organizes the character differences of the three axes, but its values vary with data distribution, dimensionality, and hardware, so you must always measure the recall-latency curve on your own data.

Technique Core strategy Main parameters Strength Limitation
HNSW hierarchical proximity-graph search M, efConstruction, efSearch best recall-latency, relatively easy updates graph memory overhead (30–50% of vectors)
IVF k-means cell partition, search only nprobe cells nlist, nprobe memory efficient, suited to large scale recall drop for cell-boundary queries
PQ subvector codebook compression m, codebook size 32×+ compression, distance-computation speedup recall drop from quantization error
IVF+PQ partition + compression combined nlist, nprobe, m handles billion scale in memory complex tuning, reranking needed

The starting point of parameter design is always the target recall. For example, if the requirement is "Recall@10 ≥ 0.95 at minimum latency," the typical procedure in HNSW is to build the graph with M=16 and efConstruction=200, then measure recall while increasing efSearch from 64 to 512, and choose the smallest efSearch that exceeds the target. Raising M from 16 to 32 roughly doubles graph memory but yields diminishing returns of only a few % recall improvement, and in particular M, once set, cannot be changed without a rebuild, so it must be fixed carefully.

In IVF, the rule of thumb is to set nlist near roughly √N. For 100 million vectors, set nlist at the level of a few thousand to ten thousand and match recall-latency by increasing nprobe. If nlist is too small, a single cell grows large and search volume rises; if too large, training and management costs rise and recall becomes unstable because there are few vectors per cell. In PQ, a larger m (number of subvectors) lowers the compression ratio (number of bytes = m) but reduces quantization error and raises recall, so set m by back-calculating from the memory budget and compensate for insufficient recall with reranking.

Doing the memory estimate in numbers builds design intuition. Keeping 100 million 768-dimensional float32 vectors as-is is about 307GB, exceeding a single node's memory. Adding HNSW (M=16) on top piles on tens more GB for graph edges, so cost surges. By contrast, applying PQ with m=96 (codebook 256) reduces each vector to 96 bytes, making the whole about 9.6GB, and narrowing search cells with IVF lets even billion scale be handled on a single node. Thus estimating "original memory → compressed memory → graph/index overhead" in numbers first and back-calculating node count and cost is a step you must go through before choosing an index.

Build time is also a design variable you must not overlook. Raising HNSW's efConstruction improves graph quality and raises recall at the same efSearch, but build time grows nonlinearly—in some cases doubling efConstruction quadruples build time. IVF/PQ codebook training is also iterative k-means over a full data sample, so it can take hours at large scale. Therefore, compute early in design that not only "query performance" but "rebuild cycle × build time" is directly reflected in operating cost, and the more frequently data changes, the more you should prioritize indexes that allow incremental updates (HNSW, FreshDiskANN, etc.).

A point you must note is the asymmetry that these parameters are only partially adjustable after the index is built. efSearch/nprobe can be changed freely at query time to adjust recall-latency in real time, but M/nlist/m/codebook are fixed at build and require a full rebuild to change. Therefore, distinguish "query-time dials" from "build-time constants," and decide the latter looking ahead to the service life cycle and data growth.

5. Application Cases

ANN permeates nearly every service that must "compute semantic similarity quickly at scale." The cases below, though in different domains, all share the identical skeleton of "high-dimensional embedding → ANN candidate generation → precise processing," and it is worth noting that only the priority among recall, latency, and memory is set differently in each case.

The generative-AI RAG pipeline is a representative use of ANN. [[rag]] embeds the user's question, retrieves the top-K similar documents from the knowledge base with ANN, and injects them into the LLM prompt. Since retrieval latency is added directly to total response latency, indexing tens of millions of chunks with HNSW to achieve Recall@10 ≥ 0.95 within a few ms governs both quality and perceived speed. If recall is low, relevant evidence is omitted and the LLM hallucinates, so ANN's recall directly translates into the factuality of the RAG answer.

In recommendation systems, the core of the candidate-generation stage is embedding users and products and then pulling "K products near this user vector" with ANN. The standard is a two-stage structure that generates hundreds of candidates within milliseconds from a catalog of hundreds of millions of products and then reranks with a precise ranking model. Here ANN converts "the cost of putting all products into the ranking model" into "the cost of putting only a few candidates," forming the typical approximate-precise combination pattern that captures accuracy and latency/cost at once.

Image/multimedia search and duplicate detection is also a longstanding ANN application. Finding similar images with image embeddings, identifying the same audio source with audio fingerprints, and removing plagiarism/duplicates with document embeddings all require nearest-neighbor search of high-dimensional vectors. At the scale of hundreds of millions of items, a design that compresses vectors by 32×+ with IVF+PQ to fit in a single node's memory and reranks PQ candidates with originals to restore recall is widely used. Meta's FAISS library became an industry standard by providing such large-scale compressed indexes as first-class citizens.

Anomaly detection and security are also efficient uses of ANN. If you embed normal behavior, logs, and network traffic and accumulate them in an index, then when a new event arrives you can quickly obtain with ANN "the distance to the nearest normal neighbor" and judge it an outlier if that distance is large. Since comparing hundreds of millions of normal patterns with every event by brute force is impossible, obtaining only the approximate nearest-neighbor distance in near-constant time with ANN is the premise of real-time detection. Here, even if recall is somewhat low, "obvious anomalies" are far from any neighbor and get filtered, so parameters prioritizing latency are reasonable.

On the platform/DBMS productization side, HNSW and the DiskANN family are spreading rapidly. pgvector added HNSW/IVF indexes to PostgreSQL to enable vector search inside a relational DB, and Milvus, Elasticsearch, OpenSearch, and others adopted HNSW as a default index. Microsoft's DiskANN stores the graph on SSD to exceed memory limits and handle billion scale on a single node, becoming the basis of several products such as Azure Cosmos DB and pgvectorscale. Thus ANN is no longer a research algorithm but has settled in as a basic building block of data infrastructure.

6. Deep Dive — Latest Trends and Disk-Based·Filtered Search

ANN research is developing rapidly along two axes: "larger beyond the memory wall, and more accurate with conditions attached." The first axis is the disk-based index. A pure in-memory graph requires hundreds of GB of memory at a billion vectors and thousands of dimensions, so cost explodes. Microsoft's DiskANN (Vamana graph) keeps only compressed vectors in memory and the full graph on SSD, designing the graph to minimize page accesses, and handles billion scale on a single node at the 95%-recall level. Adding dynamic-update research such as FreshDiskANN, which supports insertion and deletion without rebuilds, it tackles the two hard problems of large scale and real-time updates together.

The second axis is filtered search (filtered ANN). In practice, metadata conditions and vector similarity are required together, as in "the most similar among documents from the last year, in a specific category, that I have access to." Applying the condition after search (post-filtering) causes the problem of empty results when all candidates get filtered out, and applying it first (pre-filtering) is slow because the index's graph/cell structure cannot be used. Filtered-DiskANN (WWW 2023) reflects label information in graph edges from the index-build stage, handling conditional search at higher recall than conventional approaches that change only the search. However, which approach is advantageous depends on filter selectivity, and there are reports that the IVF family can be advantageous when the filter removes most of the data, so conditional search is still an active research topic.

Third, quantization and hardware acceleration keep pushing the precision-cost boundary. Beyond PQ, OPQ (optimized product quantization), scalar quantization, and binary quantization are improving the balance of compression ratio and recall, and as LLM embeddings have recently grown to thousands of dimensions, designs that combine dimensionality reduction ([[dimensionality-reduction]]) with quantization to lower storage and distance-computation cost have become important. Mass distance-computation acceleration using GPU/SIMD has also become standard in FAISS and others, greatly raising throughput (QPS) at the same recall.

Fourth, hybrid search (dense + sparse) raises quality. Vector similarity (dense) captures meaning well but is weak at exact matches of proper nouns, code, and rare words, while keyword-based inverted indexes (sparse, e.g., BM25) are the opposite. So a hybrid that runs both searches and combines the results is becoming standard in [[rag]] and enterprise search, merging both strengths with combination techniques like score normalization and Reciprocal Rank Fusion (RRF). Since the dense-side candidate generation here is ANN, the quality of the hybrid ultimately depends on ANN recall too.

Fifth, evaluation standardization has matured. ann-benchmarks.com has become the de facto benchmark that publicly compares the recall-QPS curves of multiple libraries on diverse datasets. The key lesson is that "there is no single winner": because the optimal index varies with data distribution, dimensionality, memory budget, and update frequency, the principle is to select by measuring the curve on your own data and query patterns rather than trusting vendor figures as-is.

7. Considerations and Implications

First, explicit design of recall-latency-memory (application strategy). The starting point of adopting ANN is to nail down "the lowest acceptable recall" and "the memory/latency budget" from business requirements first. Where the cost of omission is high, as with RAG factuality, prioritize high recall; where looseness is tolerable, as with exploratory recommendation, prioritize latency/cost. From a professional engineer's perspective, the key is the design capability to decompose "is the question exact nearest neighbor or approximation-tolerant, is the constraint memory or latency" and map it to an index and parameters.

Second, separating build constants from query dials (trade-off). M/nlist/m/codebook are build constants that cannot be changed without a rebuild, while efSearch/nprobe are dials adjusted at query time. Confusing the two leads to the costly mistake of "triggering a full rebuild while trying to raise recall in operation." Set build constants with margin looking ahead to data growth and distribution change, while separating the operational design so that everyday recall-latency adjustment is absorbed by query dials.

Third, data change and recall monitoring (operations·observability). If you replace the embedding model or the data distribution shifts, recall can drop even at the same parameters. Therefore, continuous verification of approximation quality is needed—periodically running brute-force search on a small number of queries to measure actual Recall@K and exposing it on a dashboard. From the standpoint of [[observability]], indexing "how much search quality has degraded right now" lets you judge the timing of index rebuild/retuning with data.

Fourth, alignment with architecture and cost structure (related technology·outlook). Index choice is itself the infrastructure cost structure. In-memory HNSW is fast but memory-costly, the DiskANN family lowers cost with SSD but increases latency, and IVF+PQ reduces node count through compression. You must design the whole search path combined with [[vector-database]], filtering, and [[caching-strategy]], and the outlook is that as disk-based, filtering, quantization, and hardware acceleration converge, ANN will cement its place as the standard engine of billion-scale real-time semantic search. Since the principle that "there is no single optimal index" holds, however, internalizing organization-level benchmarking and tuning capability becomes a sustainable competitive edge.

Fifth, security·privacy and update consistency (risk management). Because vector search's embeddings themselves carry the original content's information, there is a risk that an index leak could restore the original text or personal data via embedding inversion, so storage and access control must be applied the same as for ordinary data. Also, to respond to deletion requests (the right to be forgotten), the relevant vector must actually be removed from the index, but many ANN indexes incur latency and detection-quality degradation from deletion, so operational procedures such as soft deletion followed by periodic rebuild are needed. In filtered search, applying permission conditions after the fact can expose unauthorized documents in the candidates, so it is important to integrate access control into the index design to guarantee "searchable scope = access-permitted scope."

References


In one line: ANN is a technique that accelerates nearest-neighbor search of high-dimensional vectors by tens to thousands of times by conceding a little recall, combining the three orthogonal axes of graph search (HNSW), cluster partition (IVF), and vector compression (PQ) and designing the recall-latency-memory trade-off by back-calculating from a target recall—the core engine of large-scale vector search.