Approximate vector search: find useful neighbors without visiting every point
Balance vector-index recall, latency, and freshness.
Semantic search often starts with a simple picture: convert a query and a collection of items into vectors, then return the items nearest to the query. The picture is useful, but it hides a practical question. How should a system find nearby vectors when comparing the query with every stored item becomes too expensive for its workload?
Approximate nearest-neighbor search trades some exactness in the search procedure for a different balance of latency, memory, and construction cost. That trade can be worthwhile, but it introduces a second source of error alongside the embedding model itself. Understanding which layer failed is essential when a search result looks plausible yet omits the document the user actually needed.
Establish an exact reference first
Imagine a hypothetical museum searching its collection of object descriptions. A curator asks for carved wooden boxes with floral patterns. The embedding model converts that request into a vector, and the search system looks for nearby descriptions under a chosen similarity measure.
For a manageable evaluation collection, compute the exact nearest neighbors by checking every eligible vector. This gives the team a reference for measuring approximation error. It does not establish that the embedding model's neighbors are the best answers to the curator's question; that requires relevance judgments about the objects.
Keep those two references separate. Exact-vector neighbors tell you whether an approximate index recovered the intended geometric result. Human or task-specific relevance judgments tell you whether that geometric result helps the user. Improving one layer cannot automatically repair problems in the other.
Similarity depends on the representation
The distance or similarity measure must match how the embeddings are intended to be used. Normalization, vector dimensions, and the model that produced them are part of the retrieval configuration. A query encoded by one incompatible model cannot reliably search a collection encoded by another simply because both outputs are lists of numbers.
For the museum, document how descriptions are assembled before embedding. Including a long conservation history may emphasize different information from including a short object description. A search index can faithfully return neighbors of a representation that has already obscured the feature the curator cares about.
When evaluating an embedding change, distinguish it from an index change. Rebuilding the collection with new vectors and switching the search algorithm simultaneously makes regressions harder to explain. Use controlled comparisons before choosing the complete configuration that will serve real queries.
How graph search avoids visiting everything
Graph-based indexes connect vectors so a search can move through promising neighbors instead of examining the entire collection. Hierarchical Navigable Small World graphs, introduced by Yu. A. Malkov and D. A. Yashunin, organize this navigation across layers. Upper layers support broader movement, while lower layers support a more local search.
Read the original research paper on arXiv
The useful intuition is a network of stepping stones, not a perfect map that reveals the answer immediately. The construction and query settings influence how much of the graph is explored. Spending more effort on search can improve recovery of exact neighbors while also increasing query cost.
For the curator, a fast response is only valuable if relevant objects remain discoverable. The team therefore needs a range of operating points instead of one default setting. Measure what changes as the search budget increases and decide which point supports the intended user experience.
Other index families make different trades
Some approaches partition the space so a query searches selected regions. Others compress stored vectors or combine partitioning with compressed representations. These choices affect memory, construction, and distance estimates in different ways. A method attractive for a large static collection may be inconvenient for a frequently changing one.
The Faiss project's index-selection guidance discusses choices in relation to available memory, dataset size, and whether exact results are needed. It is a practical primary reference for framing an index comparison, not a universal prescription for every deployment or hardware configuration.
Begin with the simplest option that can meet the actual workload. The museum's collection might be small enough for exact search, especially with suitable hardware and batching. Adopting approximation before measuring the baseline creates complexity without establishing that the trade is necessary.
Measure index recall and user relevance separately
Index recall at a chosen result count measures how many exact reference neighbors the approximate search recovered. State the similarity measure, reference collection, and treatment of ties. Without these details, two recall figures may describe different tasks despite sharing the same label.
User relevance asks whether the returned objects answer the question. The nearest vectors might contain many near-duplicate catalog descriptions, leaving little variety in the visible results. Conversely, an approximate result that differs from the exact set may still be useful to a curator. That does not make the approximation metric wrong; it gives it a specific scope.
Create query groups that reflect the collection. Include materials, visual motifs, historical terms, ambiguous descriptions, and exact identifiers. Exact identifiers may benefit from lexical matching, so evaluate the complete retrieval strategy rather than assuming semantic similarity should handle every search equally well.
Filters change the search problem
The curator may restrict results to objects in a particular collection or items available for exhibition. A nearest-neighbor search over all objects followed by filtering can return too few eligible results. Raising the initial candidate count may help in some cases but requires measurement under selective filters.
Use an exact reference over the same eligible subset when evaluating filtered queries. Otherwise the test compares different problems. Include common filters and combinations that leave only a small fraction of the collection available, because these can behave differently from an unrestricted demonstration.
Authorization is a separate boundary. If some records are private, ensure their content and identifying metadata cannot reach an unauthorized user through results, snippets, debugging output, or later reranking. A relevance filter and an access-control rule may share implementation machinery while carrying different consequences if applied incorrectly.
Reranking cannot recover missing candidates
A second-stage model can reorder retrieved candidates using a richer comparison with the query. That can improve visible relevance, but it only evaluates what the first stage supplies. If the relevant wooden box never enters the candidate pool, a reranker cannot select it from that pool.
Measure candidate retrieval before evaluating the final ranking. For each missed answer, ask whether the item was absent from the index, absent from the candidate set, or ranked poorly after retrieval. These failure categories point to different fixes and prevent unnecessary changes to a component that worked correctly.
Also include the reranker's latency and cost in the complete request measurement. A larger candidate pool may improve quality while making the second stage more expensive. The right retrieval budget is therefore connected to both the first-stage index and the processing that follows it.
Updates are part of index quality
Collections change. New records arrive, descriptions are corrected, objects move between categories, and access permissions are revised. An index that answers old queries well but reflects updates slowly can still fail the product's requirements. Define how quickly each kind of change must affect results.
For the museum, an obsolete description should not remain searchable indefinitely after a correction. Track the relationship between source records, embedding versions, and index entries. When rebuilding, preserve a consistent snapshot or a clear update protocol so the deployed index does not mix incompatible states accidentally.
Test deletion and replacement directly. Verify that removed content is absent from the serving path, including replicas and caches relevant to the application. A background rebuild that eventually fixes the index is different from an immediate removal guarantee and should be described accordingly.
Benchmark realistic operation
Run queries while the system performs the updates and concurrency expected in production. Measure latency distributions, memory usage, index construction time, and quality at each configuration. Include cold and warm behavior when loading or caching materially affects the experience.
Use representative queries rather than only randomly selected stored vectors. Searching with a vector already present in the collection can be an easier problem than interpreting a curator's short, imperfectly phrased request. Preserve the query set and reference results so future changes can be compared fairly.
Record unsuccessful searches and timeouts as outcomes. Excluding them makes a fast-looking configuration appear more dependable than it is. A useful operational report connects quality and latency under a stated workload, rather than presenting the best number from separate favorable conditions.
Choose a tradeoff that stays understandable
The final choice should explain why approximation is needed, how much exact-neighbor recovery it sacrifices, and what that means for users. Include the embedding model, index family, construction and search settings, filters, update behavior, and reranking stages in the release record.
Approximate search is a way to spend computation selectively. Its value depends on retaining useful candidates while meeting the system's practical constraints. For the museum, success is a curator finding the right objects promptly and consistently, with enough visibility into the pipeline to explain why a missing result was missed.
Sources and rights
The HNSW paper is available under arXiv's non-exclusive distribution licence, with copyright retained by its authors. Faiss software uses the MIT licence; its linked documentation is cited for reference, without reproducing code or documentation text. The museum scenario is original and illustrative.