Approximate Nearest-Neighbor Search

Approximate nearest-neighbor search (ANN or ANNS) finds points close to a query while allowing some error relative to an exact nearest-neighbor result. It is a family of search methods, not a single algorithm. The purpose is to reduce query time, storage requirements, or both when exact search is too expensive.^[1] In AI systems, ANN commonly searches embeddings, numerical representations of documents, images, or other objects. It can accelerate retrieval, but it can also miss vectors that an exact search would return.^[2]

ANN is one component of a vector database. An index answers a similarity query; the surrounding database may also manage records, metadata, persistence, and access controls. A fast index does not by itself establish that the retrieved documents are relevant to a user's question.^[3]

Exact search, approximate search, and k-nearest neighbors

Given a collection of points and a query, exact nearest-neighbor search returns the closest point under the chosen distance function. A top-k query returns the k closest points. Approximation relaxes the requirement to recover that exact result; it does not change what distance the application intended to optimize.^[1]

The k-nearest neighbors machine-learning method is a related application. A classifier uses the labels of nearby training examples to predict a class, while a nearest-neighbor regressor uses nearby target values. The search procedure supplies neighbors to that prediction rule. An ANN index is therefore distinct from the classifier or regressor that might use its output.^[4]

An exhaustive scan is a useful baseline. For one dense query against n vectors of dimension d, directly computing all coordinate-wise distances takes work proportional to n times d before result selection. Vectorized implementations and batching can make this competitive, especially for small collections. Tree-based exact methods can avoid some comparisons, although their advantage can deteriorate in high-dimensional spaces.^[4]

Index construction also has a cost. Faiss's selection guide recommends considering direct search when there will be too few queries to recover the cost of building an index. Approximation is a workload decision, not an automatic requirement whenever data is represented as vectors.^[5]

What approximate accuracy means

Two different accuracy notions appear in ANN literature and software.

In a distance-factor formulation, a returned point p must satisfy:

$$D(q,p) \leq c \min_{x \in P} D(q,x)$$

Here P is the indexed collection, q is the query, D is the distance, and c is an allowed factor of at least 1. An algorithm's guarantee can also specify a success probability. A method described as approximate does not automatically offer this guarantee for every dataset or configuration.^[1][6]

Practical benchmarks often measure recovery of the exact neighbors instead. If E is an exact top-k set and A is the returned top-k set, one set-based definition is:

$$\operatorname{recall@k}=\frac{|A\cap E|}{k}$$

For example, recovering 9 of 10 exact neighbors gives recall@10 of 0.9 for that query. This is an illustrative calculation, not a reported benchmark result. ANN-Benchmarks plots average recall over queries against queries per second.^[7]

Metric definitions need to accompany reported numbers. Recovering the single closest point somewhere in ten returned candidates, often written 1-recall@10, differs from recovering nine of the exact ten closest points. A system can also return a point whose distance is almost optimal without returning the same identifier as a particular exact result. Distance error and neighbor-set recovery measure different properties.^[3]

Distance and embedding choices

The search objective must match the representation. Common choices include Euclidean distance, inner product, and cosine similarity.^[8]

For unit-normalized vectors, squared Euclidean distance and inner product satisfy squared_distance = 2 - 2 * inner_product. This relationship explains the equivalent rankings under those conditions; normalization is not a harmless transformation when vector magnitude is part of the intended objective.^[8]

The embedding model is a separate source of retrieval error. Sentence Transformers distinguishes symmetric tasks, such as finding similar questions, from asymmetric tasks, such as matching a short question to an answering passage. Its documentation recommends task-appropriate models and query/document encoding methods. Increasing index search effort cannot correct an unsuitable representation.^[2]

Main algorithm families

ANN systems often combine candidate selection with compressed distance evaluation. The following families describe mechanisms rather than mutually exclusive products.

Locality-sensitive hashing

Locality-sensitive hashing (LSH) uses a family of randomized hash functions designed so that nearby points collide with greater probability than distant points. A search consults buckets associated with the query and checks candidates found there. This differs from an ordinary hash-table lookup, whose goal is usually exact key matching.^[6]

Indyk and Motwani's 1998 work established an influential LSH approach to approximate nearest-neighbor search. Its analysis links collision probabilities to query and storage bounds. Those guarantees apply to the specified construction and assumptions; the label LSH alone does not identify one universal accuracy setting.^[6]

Hierarchical navigable small world graphs

HNSW builds several layers of proximity graphs over nested subsets of the data. The maximum layer assigned to a point is randomized. Search starts in an upper layer and proceeds toward denser lower layers, using the hierarchy to find a useful region before a more detailed search.^[9]

The original paper describes an incremental graph construction and a neighbor-selection heuristic intended to work well at high recall and with clustered data. Its reported scaling and performance are properties of the studied algorithm and experiments, not a promise that every HNSW implementation has the same worst-case latency.^[9]

In hnswlib, M controls connections created during construction, ef_construction controls construction search effort, and ef controls the dynamic candidate list during querying. Larger settings consume more memory or work and can improve recall. Query-time ef must not be smaller than the requested k. The library explicitly notes that raising construction effort eventually stops improving index quality.^[10]

Inverted files

An inverted-file index (IVF) assigns vectors to partitions, commonly using trained cluster centroids. A query searches a selected group of those partitions. In Faiss, nlist describes the partition count and nprobe controls how many inverted lists are visited at query time. Increasing probes typically exchanges speed for better coverage.^[11]

The vectors inside a visited partition can remain uncompressed. Consequently, IVFFlat can compute full-precision distances for candidates and still be approximate overall: it may never visit the partition containing a true nearest neighbor. Combining IVF with PQ adds a second approximation, in the distances used to compare candidates.^[11]

Product quantization and score-aware compression

Product quantization (PQ) divides a vector into subvectors and quantizes each subspace separately. The stored representation consists of indices into the subspace codebooks. Distance computation can then use these compact codes instead of reading every original coordinate.^[12]

Jégou, Douze, and Schmid's method includes asymmetric distance computation, which compares an uncompressed query with a compressed database vector. This avoids also quantizing the query. Their work combines PQ with inverted files to reduce both storage and the number of candidates examined.^[12]

Compression objectives need not minimize ordinary reconstruction error alone. Guo and colleagues' anisotropic vector quantization emphasizes errors that matter for maximum inner-product search. Under the paper's assumptions, its loss penalizes the component of a reconstruction residual parallel to a database vector more heavily than the orthogonal component.^[14] ScaNN implements search-space pruning and quantization methods for inner-product search and also supports Euclidean distance.^[15]

Disk-oriented search

The 2019 DiskANN system uses the Vamana graph with full-precision vectors on SSD and compressed vectors in memory. Compressed distances help decide which graph neighborhoods to fetch. Its beam search can fetch several promising neighborhoods together rather than performing each disk access in sequence.^[13]

This design allows a collection larger than available RAM to be searched, but it still requires memory and incurs storage I/O. DiskANN's published results specify datasets and hardware. They should not be interpreted as a fixed latency or capacity guarantee for a differently sized vector, storage device, or request workload.^[13]

Reranking and filtered search

A search pipeline can retrieve more candidates than it ultimately returns and rescore that shortlist. Exact distance rescoring corrects ordering errors among those candidates, but cannot recover an item absent from the shortlist. The candidate budget therefore affects the best result the later stage can achieve.^[3]

A learned reranker is a different operation. In a document-retrieval pipeline, a cross-encoder can score the query and each candidate document together, rather than merely recomputing the original vector distance. This can improve relevance ordering, but it adds model inference work and still depends on candidate retrieval.^[16]

In pgvector's approximate indexes, filtering occurs after the index scan and can leave fewer results than requested. Since version 0.8.0, iterative scans can search further until enough results are found or configured limits are reached.^[17]

These details are implementation-specific. pgvector also documents selective exact search, partial indexes, and partitioning. Its strict ordering mode orders returned distances; it does not guarantee recovery of every globally nearest eligible vector.^[17]

Evaluation and operating tradeoffs

ANN-Benchmarks tests algorithms across datasets and parameter settings, allowing comparison of quality-performance tradeoffs rather than a single default configuration. Different approaches can occupy similar parts of that tradeoff curve.^[18] Its project documentation distinguishes default single-query, single-CPU experiments from batch mode and directs billion-scale work to a separate benchmark project.^[19]

The NeurIPS 2021 billion-scale challenge separately evaluated constrained-memory hardware, hardware with SSDs, and unrestricted hardware configurations. This matters because a result obtained with a large accelerator or a disk-backed index answers a different resource question from an in-memory CPU experiment.^[20]

A useful evaluation records the following conditions alongside recall:

Evaluation should include the application's actual filters. An unfiltered benchmark cannot establish filtered-query recall, since it tests a different candidate-selection problem.^[17][19]

Training data matters for indexes that learn partitions or codebooks. Faiss warns that a training sample should represent the indexed distribution: matching dimensionality alone is insufficient. Changes to the model that produces vectors or to the media distribution can reduce accuracy or search efficiency. Duplicate and near-duplicate vectors can also concentrate work in some indexes.^[21]

There is no universal best ANN configuration. An exact baseline separates approximation error from representation quality; a parameter sweep then shows what additional recall costs in search work and memory. If exact search already satisfies the workload, an approximate index may add construction and tuning costs without a useful benefit.^[5][18]

References

1. ^1 ^2 ^3Andoni, Alexandr, Piotr Indyk, and Ilya Razenshteyn. "Approximate Nearest Neighbor Search in High Dimensions." ICM 2018 survey, arXiv:1806.09823, 2018.
2. ^1 ^2Sentence Transformers. "Semantic Search." Project documentation. Accessed September 27, 2026.
3. ^1 ^2 ^3Douze, Matthijs, et al. "The Faiss Library." arXiv:2401.08281v4, October 23, 2025. Sections 1, 3.2, and 3.5.
4. ^1 ^2Scikit-learn. "Nearest Neighbors." User guide. Accessed September 27, 2026.
5. ^1 ^2Faiss. "Guidelines to choose an index." Project documentation. Accessed September 27, 2026.
6. ^1 ^2 ^3 ^4Indyk, Piotr, and Rajeev Motwani. "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality." Proceedings of STOC 1998, pp. 604-613. DOI: 10.1145/276698.276876.
7. ^1 ^2 ^3ANN-Benchmarks. "Benchmarking Results." Project results and metric description. Accessed September 27, 2026.
8. ^1 ^2Faiss. "MetricType and distances." Project documentation. Accessed September 27, 2026.
9. ^1 ^2 ^3Malkov, Yu. A., and D. A. Yashunin. "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs." arXiv:1603.09320, first submitted 2016, revised 2018.
10. ^1 ^2Hnswlib. "HNSW algorithm parameters." Project documentation. Accessed September 27, 2026.
11. ^1 ^2 ^3Faiss. "Faiss indexes." Project documentation. Accessed September 27, 2026.
12. ^1 ^2 ^3Jégou, Hervé, Matthijs Douze, and Cordelia Schmid. "Product quantization for nearest neighbor search." IEEE Transactions on Pattern Analysis and Machine Intelligence 33(1), pp. 117-128, 2011. DOI: 10.1109/TPAMI.2010.57.
13. ^1 ^2 ^3Jayaram Subramanya, Suhas, et al. "DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node." Advances in Neural Information Processing Systems 32, 2019. Sections 3.2 and 3.3 of the paper.
14. ^Guo, Ruiqi, et al. "Accelerating Large-Scale Inference with Anisotropic Vector Quantization." Proceedings of ICML 2020, PMLR 119, pp. 3887-3896.
15. ^Google Research. "ScaNN." Project README. Accessed September 27, 2026.
16. ^Sentence Transformers. "Retrieve & Re-Rank." Project documentation. Accessed September 27, 2026.
17. ^1 ^2 ^3Pgvector. "Filtering" and "Iterative Index Scans." Project documentation. Accessed September 27, 2026.
18. ^1 ^2 ^3Aumüller, Martin, Erik Bernhardsson, and Alexander Faithfull. "ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms." arXiv:1807.05614, 2018; Information Systems, 2019. DOI: 10.1016/j.is.2019.02.006.
19. ^1 ^2 ^3ANN-Benchmarks. Project README and benchmarking principles. Accessed September 27, 2026.
20. ^1 ^2Simhadri, Harsha Vardhan, et al. "Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search." arXiv:2205.03763, 2022.
21. ^Faiss. "FAQ." Sections on representative training data, changing data distributions, and duplicate vectors. Accessed September 27, 2026.