Vector Databases: Approximate Nearest Neighbor Search in Large-Scale Embeddings

The input to a vector database is never just raw vectors. Every ingested record should carry the object embedding, a stable document or chunk ID, source text location, metadata, permission information, and version number; the output of the database is similar candidates and retrievable original content. This asymmetry between input and output determines the true role of a vector in the entire retrieval chain: it is only a search key, not the answer itself.

The first question to answer in the storage stage is: after vectors are stored, where do the source text and permissions go? An embedding model compresses a piece of text into a fixed-dimensional numerical sequence; the compression process inevitably discards source text information, and the vector itself cannot reconstruct the original sentence. If only vectors are stored in the database, after a hit there is no content that can be displayed or verified. Therefore, each vector must be associated with a stable document or chunk ID, metadata, and an explicit source text location. The ID allows the same content to be precisely located during subsequent updates and deletions; the source text location enables retrieval results to fetch the source text; metadata carries business attributes such as language, source, and time for filtering and permission decisions.

The causal chain in the retrieval stage is therefore divided into two steps. First, vectors are only responsible for finding candidates: the query vector is compared with vectors in the database, yielding a set of objects that are close in the representation space. Second, the answer must return to the source text and undergo permission verification: retrieve the content at the source text location by the candidate ID, and then check permissions as the current request principal. High similarity only indicates that two objects are close in the embedding space; it does not indicate that the content is factually trustworthy, nor that the current principal has permission to view it. Similarity is the basis for recall; source text and permissions are the basis for the answer. The two must not be conflated. A vector lacking a source-text mapping or permission field cannot directly serve as an answer, even if the similarity calculation is completely correct.

Capacity planning should likewise revolve around the true data scale. When planning, use the actual number of vectors, dimensions, data types, index edge count, number of replicas, and growth rate, not just the raw file size. Raw file size reflects text volume; the memory and storage occupied by a vector index are jointly determined by the number of vectors times bytes per vector, the number of edges connected in the index graph, and the number of replicas, and they grow as data grows. Therefore, capacity must be estimated based on these parameters.

Pre-launch validation should also use “whether business evidence can still be found” as the acceptance criterion. Save in advance a set of exact nearest-neighbor benchmark queries, and slice them by tenant filter rate, language, document age, and difficulty. After that, each time you adjust parameters such as ef, probes, quantization, or sharding, re-measure Recall, p95/p99 latency, memory usage, and empty-result rate on the same benchmark simultaneously. Only by keeping the benchmark unchanged and observing these four items simultaneously can you distinguish between “the index became faster” and “business evidence can still be found”: the former only indicates a speed improvement, while the latter indicates that recall quality has not been damaged by parameter tuning and that the business can still find the content it should find.

The core operation of vector retrieval is to compare the query vector with each candidate vector in the database one by one, obtain similarity scores, and rank results accordingly. How the score is calculated depends on the chosen metric. The three commonly used metrics are cosine similarity, dot product, and Euclidean distance. Their relationship can be described clearly using the magnitudes of vectors and the angle between them.

Let two vectors be a and b, with magnitudes ‖a‖ and ‖b‖ respectively, and the angle between them be θ. The dot product is defined as a·b = ‖a‖·‖b‖·cos θ; cosine similarity divides the dot product by the two magnitudes, that is, cos θ = a·b / (‖a‖·‖b‖), and it measures only consistency of direction, independent of length; squared Euclidean distance is ‖a − b‖² = ‖a‖² + ‖b‖² − 2·a·b, which measures the actual distance between the two endpoints in space.

When do the three metrics give the same ordering? The key is normalization. If all vectors are L2-normalized, that is, scaled to unit length ‖a‖ = ‖b‖ = 1, then the dot product reduces to a·b = cos θ, which is exactly the same as cosine similarity; squared Euclidean distance also reduces to ‖a − b‖² = 2 − 2·cos θ, where smaller distance ⇔ larger cosine. Therefore, the three orderings—maximum dot product, maximum cosine, and minimum squared Euclidean distance—are completely equivalent, and choosing any one of them yields the same result. The ordering by squared Euclidean distance is also the same as by Euclidean distance, because squaring is a monotonically increasing function; in engineering implementations, squared distance is often compared to avoid the square-root operation.

Without normalization, the three are no longer equivalent. Vector magnitude gets mixed into the dot product: at the same angle, a vector with a larger magnitude has a larger dot product, so dot product ordering is biased by length; cosine similarity is unaffected by length because it divides by the magnitudes; Euclidean distance is affected by both direction and length. Therefore, the distance metric must be consistent with how the embedding model was trained: if the model was trained with cosine similarity or normalized dot product as the objective, inference should also use normalized vectors and the corresponding metric; if it was trained without normalization, the dot product objective itself includes the effect of magnitude, so inference should also remain unnormalized. Otherwise, the meaning of the metric no longer corresponds to the training objective.

Whichever metric is chosen, similarity scores are only a basis for ordering, not the probability of “the answer is correct”. A high score only indicates that the candidate is close to the query in the representation space; it does not mean the content is factually trustworthy.

Exact nearest neighbor search is actually simple: for each query, compute its distance to all N vectors in the database one by one, sort them, and take the top K. The problem is that the cost grows linearly with the size of the database. Every query requires N distance calculations; when the database reaches the million or ten-million level, both the latency per query and the memory bandwidth consumed per second scale linearly, making it unable to meet online service requirements. This is why comparing against the entire database one by one does not scale.

The idea behind approximate indexes is not to compare all vectors one by one, but to organize or compress the data in advance so that each query only accesses a small portion of it, thereby reducing latency and memory, at the cost of possibly missing the true nearest neighbor. The inputs to an ANN index are a large set of vectors and a query, and the output is approximate top-k neighbors. HNSW, IVF, and PQ, three typical structures, represent three different strategies of "accessing less or storing less."

HNSW builds a multi-layer adjacency graph: each vector is a node in the graph, and edges connect nodes that are close to each other; the upper layers are sparse with large edge spans and are responsible for quickly jumping to the approximate region, while the lower layers are dense with small edge spans and are responsible for fine-grained positioning. The query starts from the top-layer entry point, greedily moves to neighboring nodes that are closer to the query, and then descends layer by layer to the bottom. The whole process only visits a very small fraction of the nodes in the graph, and the time cost is far lower than a full scan; but greedy navigation may take a suboptimal path in some layer and thus miss the true nearest neighbor, which is the source of recall loss.

IVF follows a "select buckets first, then search finely" approach. It first partitions all vectors in the database into several coarse clustering buckets, each with a representative point; at query time, it first computes the distances between the query vector and the representative points of the buckets, selects only the few nearest buckets, and then performs more precise comparisons within those buckets. The number of vectors accessed is thus greatly reduced. The risk is that the true nearest neighbor may fall into a bucket that was not selected; once the wrong bucket is selected, that neighbor cannot be found.

PQ, on the other hand, compresses the vectors themselves. It approximates each vector as a short code, greatly reducing the storage overhead per vector, so the same memory can hold more vectors; distances are also computed approximately on the short codes, reducing storage and bandwidth usage. The short code is a lossy approximation of the original vector, and quantization error may change the relative order of neighbors, also causing recall loss.

The common logic of the three strategies is: trade a small amount of recall loss for order-of-magnitude improvements in latency and memory, and whether this trade-off is worthwhile depends on the scenario. When the data volume is small and full comparison is already fast enough, or when the business must guarantee finding exact nearest neighbors, you should use full exact search; you should not force the use of approximate indexes just because they sound "more advanced."

Every parameter of an approximate index trades off among recall quality, latency, and memory; the essence of parameter tuning is to choose an acceptable operating point in this triangle. Take HNSW's ef and IVF's probes as examples: they control search breadth at query time.

When HNSW navigates the graph, it maintains a candidate set; ef determines the size of this set, that is, the maximum number of candidate nodes examined during the search. The larger ef is, the more nodes are visited and the greater the chance of finding the true nearest neighbors, so Recall@k rises accordingly; but each extra node visited requires extra distance calculations, and latency rises in step. IVF's probes controls the number of buckets fine-searched at query time: the larger probes is, the more buckets are fine-searched and the higher the probability that the true nearest neighbors are covered, so Recall rises; at the same time, the number of vectors to compare increases, and latency increases. Both follow the same rule: a broader search usually improves recall and also increases latency.

Other parameters act on the index-building side. When building the graph, how many edges each node connects directly determines the index's memory footprint and build cost: the more edges, the denser the graph, and the greater the memory and build time. Quantization precision determines the short-code length of each compressed vector: the more information the short code retains, the higher the recall, and the more memory each vector occupies. Therefore, the graph edge count and quantization precision mainly affect memory and build, while ef and probes mainly affect query latency; all four fall together in the Recall—latency—memory triangle.

Proper parameter tuning must have an external yardstick: first compute exact nearest neighbors on the target query set as a baseline, then compare the approximate index's results on the same query set with the exact results to obtain Recall; at the same time, record latency, memory, and build cost. Repeat this process after each parameter change, and you can draw Recall—latency—memory curves. Once parameters change, you must compare again against exact neighbors, because any 'faster' or 'cheaper' adjustment may quietly sacrifice recall.

Every point on the curve is a set of trade-offs; the criterion for selecting a point is recall of business evidence and SLO, not maximizing a single QPS. You should choose the configuration whose recall satisfies the business baseline and whose latency and memory fall within the service level objectives, rather than the one that maximizes throughput metrics.

Vector retrieval ranking only knows "similar or not," not "can be viewed or not." When a query carries tenant and permission conditions, a practical problem arises: if you do vector search first and then filter, why might you end up with zero results?

The first approach is post-filtering: first perform vector search over the entire database to get the global top-k, then remove results that the current subject is not authorized to access. The reason this fails is that the index does not know about permissions. The global top-k may be almost entirely occupied by vectors from other tenants or unauthorized documents—they are just as close to the query in representation space, but they do not belong to the current subject's allowed domain. After deleting them, the remaining results may be fewer than k, or even none, even though similar content clearly exists within the allowed domain, just ranked after the global k-th position. Vector ranking is independent of permissions, so post-filtering ends up deleting all unauthorized results.

The second approach is pre-filtering: first delineate the allowed domain, then perform vector search. Its cost falls on index efficiency. An approximate index is a structure built for the entire vector collection; graph adjacency and clustering bucket partitions are all formed globally. Suddenly restricting the search to a scattered subset destroys the premises of navigation and bucket selection, the index's acceleration assumptions no longer hold, and latency may rise substantially.

Therefore engineering requires filter-aware search: push the filter conditions into the search process itself, so that traversal only expands within the allowed candidate domain, or first retrieve more than k candidates, apply filtering among them, and continue supplementing. Its goal is only candidate coverage—ensure that similar vectors within the allowed domain actually enter the candidate set. This solves the problem of insufficient result quantity, but it is not equivalent to completing authorization.

Real authorization must be performed by an authoritative system before returning results, and it must target the original text rather than similarity scores. No matter what index metadata claims, any sensitive content cannot rely solely on permission fields in the index: a vector index is not an authorization system, and neither the model nor the index has authorization capability. The retrieval stage provides candidates according to the allowed domain; before returning the original text, authoritative authorization makes the final decision. Both steps are indispensable.

A vector database is not static: documents are updated and deleted, and embedding models are also upgraded or replaced. Both types of changes raise the question of whether old and new data can coexist.

First, consider changing models. Different embedding models—and even different versions of the same model—produce different geometric spaces: coordinate meanings, dimensional scales, and semantic distributions all differ, so distance values between old vectors and new vectors are not comparable. Therefore, after changing models, old vectors cannot be mixed with new vectors—if mixed in a query, ranking scores would be compared across spaces and the results would be meaningless. The solution is to have the index record an embedding version for each vector. During migration, use dual-write rebuild plus atomic switchover: rebuild the index in a new namespace with the new model while the old namespace continues to serve traffic; after the rebuild is complete, switch traffic to the new namespace in a single atomic operation. Atomic switchover ensures that at any moment a query uses either the old space entirely or the new space entirely, with no intermediate state that mixes scores across spaces.

Next, consider deletion. Deleting a document is not just about removing its vector from the index. The answer service must go back to the source text, and caches and replicas also hold content in their respective places, so deletion must cover the entire chain: vectors, metadata, source text, cache, and replicas. If you delete only the vector but not the source text, the source text may still be retrieved through other paths; if you delete only the primary database but not the replicas, replicas still retain the content and subsequent queries may still hit the deleted data. At the same time, two anomalies need monitoring: stale records—deleted but still visible somewhere; orphan records—the source text no longer exists, but the vector remains in the index.

The key lifecycle constraint is the behavior while propagation is incomplete: when a deletion or update has not yet propagated through the entire chain, results must be marked as stale, or the service must be stopped outright; it must never continue returning content that may have become invalid. In addition, a reminder throughout the update process: high vector similarity does not equal factual relevance or trustworthiness; the basis for update and deletion operations is business facts and permissions, not similarity scores.

Only by making the scale concrete can you see clearly why an index is needed and what exactly 'approximate' sacrifices. Suppose the database contains one million 768-dimensional FP32 vectors, each dimension taking 4 bytes. The raw vector memory is 1,000,000 × 768 × 4 bytes, about 3.07 GB (2.86 GiB)—and that only counts the payload itself; graph edges, IDs, metadata, and allocator overhead are not included yet.

The cost of exact scanning falls on the query side: each query must perform multiply-adds over all 768M dimensions and also stream 3.07 GB of data through memory. As the store grows, single-query latency and bandwidth consumption scale linearly, so full-store one-by-one comparison is infeasible at million-level. The HNSW in Figure 1 uses a hierarchical adjacency graph to reduce the number of visited nodes, lowering per-query access from the million-level to a small fraction; 'approximate' is therefore an explicit recall–latency tradeoff, not a free speedup. The yardstick for measuring the tradeoff must use exact search as an offline baseline: first compute the exact top-k, then count how many of them the approximate results hit. For example, if approximate top-k hits 9 of the exact top-k, Recall@10 = 90%.

The meaning of that 90% figure must be carefully qualified. It only says that the approximate index reproduces 90% of the exact vector ranking, and nothing more. Evidence relevance and answer quality are not within this metric: if the embedding model itself did not place the correct evidence into the exact top-k, no matter how high the index Recall is, it cannot repair defects in semantic representation. The upper bound of an approximate index is exact ranking; it reproduces the ranking, not new semantics.

The estimate of 'storing only 3 GB' is still an underestimate. HNSW's per-point adjacency edges, metadata indexes, replicas, and service overhead will continue to inflate actual usage. To compress the payload you can use 8-bit quantization, reducing a single vector to 768 × 1 bytes and the raw payload to about 0.77 GB, but the storage of the quantization codebook and the precision loss are not included, and quantization changes how distances are approximated, further affecting recall. Therefore conclusions about capacity and performance must draw Recall, p95 latency, memory, and build time curves together on a real query set, rather than only comparing the QPS advertised by the database.

When a user can access only 1% of documents in the entire database, “retrieve global top-k first and then filter” is almost doomed to fail, and the reason can be calculated directly with expected values. Suppose among 1 million chunks in the entire database, tenant A has only 10,000 chunks, accounting for 1%. If similar candidates are approximately independent of tenants, then the expected number of items belonging to A in the global top-k is only 10 × 1% = 0.1—post-filtering is very likely to return an empty set. Expanding top-k to 100 still gives an expected value of only 1, while the scan scope, network overhead, and risk of unauthorized disclosure all increase. Note this is a capacity intuition under an independence assumption, used to judge that “this usually doesn't work”, not a guarantee for any single query. The correct approach is to make the index search itself aware of tenant and permission filtering, allow candidates to be generated only within the domain, and have an authoritative authorization layer re-check before returning.

Filtering is just one link in the entire chain. The four types of lifecycle events—update, permission revocation, deletion, and upgrade—each require a set of objects to be synchronized, an observable invariant, and a corresponding failure manifestation:

The safe landing of deletion is usually an asynchronous process, but asynchronous does not mean unconstrained: there must be completion status, retries, auditing, and maximum propagation time. Embedding upgrades use blue-green rebuild: write new vectors to an independent namespace with a new encoder, and after offline regression verification, atomically switch the query alias. Do not overwrite old vectors with new vectors one by one in the same index—during the transition period, query vectors cannot simultaneously interpret two geometric spaces, and mixed writes inevitably produce meaningless scores.

The failure boundary must be repeatedly emphasized: metadata filtering is a retrieval condition that narrows candidates, not final authorization. Index configuration errors, cache misses, or replication delays may allow filtering to be bypassed; sensitive source text must be authorized again at the retrieval/return boundary according to the current subject, resource, and action, rather than trusting the “already filtered” conclusion given by the retrieval stage.

A query from ingestion to answer passes through stages in which each stage takes the previous stage's output as input; a break in any link makes the final answer lose its basis.

The starting point is document chunking and embedding. The original document is split into chunks, and vectors are generated using a versioned embedding model; the version is recorded because vectors from different versions belong to different geometric spaces, so subsequent retrieval can only compare within the same space.

The second step is writing. Vectors are stored together with the original text and metadata: each vector is associated with a stable id, original text location, permissions, and time-validity information. The vector is only a search key; the answer must eventually return to the original text, so if any field is missing at this layer, the subsequent stages cannot be completed.

The third step is candidate generation. The query vector enters the ANN index and produces approximate similar candidates. The index trades a small amount of recall loss for orders-of-magnitude reductions in latency and memory; this cost must be measured by Recall against exact nearest neighbors.

The fourth step is filtering. Candidates are narrowed by permissions and time validity to the range allowed by the current subject and still valid. This step must be filter-aware: taking the global top-k first and then filtering, for tenants with low filter rates the expected number of hits may be far less than 1, resulting in an empty result; at the same time, filtering only narrows the retrieval conditions for candidates, not authorization itself.

The fifth step is retrieval and reranking. The system fetches the original text by candidate id, reranks if necessary, and performs final authorization at the return boundary using the current subject's permissions. What is returned at this point is the original content available for answering, not vector scores.

Finally, there is a two-layer evaluation. The first layer examines the index: compare against exact nearest neighbors on the target query set, jointly measuring Recall, latency, memory, and build cost to confirm that the approximate index indeed reproduces the exact ranking. The second layer examines the final answer: confirm that the correct evidence actually entered the answer—because no matter how high the index Recall is, it can only reproduce the ranking given by the embedding model; if the embedding did not place the correct evidence into the exact top-k, the index cannot repair the defect in the semantic representation. Together, the two layers of evaluation distinguish “the index is faster” from “business evidence can still be found”.