, vector search has turn into a crucial piece of AI infrastructure, powering use circumstances from RAG and semantic search to agentic reminiscence and context layers. With the rise of agentic programs, firms are attempting to supply as a lot context to the brokers as attainable, which requires vector db indexes to develop from an preliminary million or dozens of thousands and thousands scale to the a whole bunch of thousands and thousands and even billions. At this scale, storing indexes and related knowledge in RAM will value hundreds of {dollars} monthly, and HNSW can turn into a scalability bottleneck.
On this article I want to dive into the main points of what truly makes semantic search quick and environment friendly: approximate nearest neighbor (ANN) algorithms, what totally different choices exist, and their trade-offs.
Deep dive into vector DB
Vector databases encompass three foremost elements:
- embeddings – the numeric illustration of the corpus
- search algorithm and index construction – the algorithm defines the search high quality and velocity
- storage – how the information is saved (in reminiscence, on disk, payload along with embeddings, and so forth.). Whether or not in RAM or on disk, it determines the prices and latency at scale
Embeddings are already effectively outlined and mentioned in lots of articles, and this one will concentrate on search algorithms, and particularly ANN ones. There are typically two approaches for the search execution:
- Actual search – which demonstrates the most effective retrieval metrics though it doesn’t scale effectively when it comes to latency
- Approximate nearest neighbor (ANN) – which trades off the retrieval high quality for the latency and scalability.
The precise search is an easy strategy which loops by means of all the entries within the index and calculates the gap between your search question and present knowledge. There are not any losses associated to any approximation or generalization with the trade-off of the latency and scalability. It’s a fantastic strategy for both very small indexes or experimentation, however typically not very appropriate for the manufacturing scale.
Fascinating reality: many fashionable vector databases permit you to bypass index constructing for small collections, falling again to kNN search as a result of the overhead of constructing an index shouldn’t be value it for a number of thousand vectors.
The second choice is approximate nearest neighbor algorithms, which is a gaggle of algorithms with the primary function of enhancing scalability by avoiding visiting all of the entries within the index. The thought right here is to supply some shortcuts to hurry up the search and ingestion. The implementations fluctuate, though many fashionable ANN algorithms (for instance, HNSW and DiskANN) depend on a graph construction to supply low question latency.
Approximate nearest neighbor algorithms
It’s essential to debate that despite the fact that ANN algorithms are all following the same idea to realize the purpose of offering a brief path to the tip end result, there are totally different implementations with totally different algorithms having distinctive units of trade-offs, which makes it essential to pick out the one that matches your actual use case.
On this article I want to concentrate on two totally different teams of the ANN algorithms:
- RAM-based – such algorithms are optimized for storing all or an enormous chunk of information in reminiscence, which supplies extraordinarily low latency with the prices as a trade-off. The usual instance right here is HNSW (Hierarchical Navigable Small World)
- On-disk – these algorithms are minimizing RAM utilization and relying closely on disk to load the required knowledge. An instance right here is DiskANN or SPANN
It’s required to say that it’s attainable to retailer underlying knowledge constructions of each of those algorithm teams both on disk or in reminiscence (not less than partially), however they’re optimized for the particular storage kind and due to this fact will present the most effective outcomes using what they have been designed for.
In-memory ANN
HNSW (Hierarchical Navigable Small World)
The preferred ANN algorithm utilized by nearly any fashionable vector database. The thought is to make the most of a layered graph-based knowledge construction to attach vectors with close to neighbors, which supplies extraordinarily quick retrieval when storing the entire index in reminiscence. It’s a fantastic match for small-medium use circumstances and can present the most effective retrieval velocity.
Nonetheless, as soon as the index is large enough that it now not suits in RAM or storing it in RAM turns into very costly, the choice is to both transfer knowledge to disk, which can trigger a drastic efficiency hit, or extremely quantize it, which may trigger a major drop in retrieval high quality. The primary purpose for such a efficiency hit is that the HNSW construction shouldn’t be optimized for the clustered disk entry, and consequently, the search would produce plenty of non-sequential I/O operations. Contemplating a number of hops per search and comparatively excessive learn visitors, the disk I/O will turn into a bottleneck, which may considerably improve latency, from milliseconds to a whole bunch of milliseconds or worse below heavy I/O strain.
The in-memory algorithms are extremely optimized to retailer all vectors and connections in RAM, which makes them extraordinarily quick, however with a trade-off of being reminiscence hungry. Furthermore, with on-disk choices such algorithms depend on random disk entry, which may turn into a possible bottleneck for large-scale indexes (100 million+).
Instance vector databases: Qdrant, Milvus, pgvector, OpenSearch, Weaviate, Redis
On-Disk ANN
This group of algorithms is designed particularly to interrupt the RAM consumption limitation of the in-memory ANN algorithms and scale back the storage prices whereas offering acceptable latency. It’s a fantastic alternative if search latency shouldn’t be crucial and the index dimension is anticipated to be giant. We are able to think about two foremost algorithms on this group:
SPANN
It’s a disk-based ANN algorithm that follows the inverted-index (IVF) methodology: vectors are grouped into clusters, every represented by a centroid. It was particularly designed to deal with extraordinarily giant billion-vector+ indexes that received’t slot in RAM or will likely be too costly to be saved in reminiscence. The thought is to prepare factors in clusters, which is a pure property of the embedding house, choose a centroid illustration of the cluster, and put it to use for the routing layer. Centroids and mainly the entire routing layer might be saved in RAM whereas the vectors represented by the centroids are saved on disk. The essential element is that vectors represented by the identical centroid are saved on disk sequentially and due to this fact might be loaded from it quick and effectively. Throughout search, centroids are used to seek out the closest teams of vectors, after which the vectors related to these centroids are loaded from disk to carry out a full scan.
Notice: In comparison with HNSW with the on-disk storage choice, SPANN ensures that as an alternative of random disk entry, the vectors represented by the only centroid are grouped on disk and due to this fact loaded as blocks, which dramatically reduces the variety of required disk I/O operations whereas offering acceptable latency.
Instance vector databases: Turbopuffer (constructed on SPFresh, a SPANN successor), Chroma DB (cloud)
DiskANN
As a substitute of a centroid-based strategy, DiskANN maintains a single-layer graph known as Vamana. The primary thought behind it’s to attenuate the variety of hops required to seek out the highest okay factors and due to this fact the variety of random disk entry operations. It’s achieved by retaining some longer-range connections as an alternative of solely the closest ones, so fewer hops are wanted to achieve the goal. The unique vectors are saved on disk whereas the extremely quantized model of the vectors is saved in RAM, which additionally contributes to lowering the required variety of disk entry operations. In comparison with SPANN, DiskANN’s Vamana graph is constructed over each level, so the graph itself scales with the dataset, which is an actual reminiscence consideration at billion scale, the place SPANN solely wants its centroids resident. The information on disk shouldn’t be clustered, and the disk I/O is minimized by the routing layer doing a minimal variety of hops to get to related vectors, resulting in extremely environment friendly search in apply. There are plenty of inner particulars on how precisely it’s carried out, and I extremely suggest exploring the origin paper, which is linked within the references for this text.
Instance vector databases: Milvus, PostgreSQL (through pg_diskann)
Economics
Notice: the costs beneath are approximate and present as of writing. Cloud pricing shifts over time and varies by supplier, area, and dedication, so deal with these figures as illustrative of the RAM-vs-disk ratio quite than actual quotes
With RAM costing about 5$ per GB by means of cloud suppliers, EBS is about 50 instances cheaper, round 0.08-0.10$ per GB, and native NVMe SSD round 0.20-0.25$ per GB. Subsequently, for the 100,000,000 index in 1024 dimensions with float32 precision, it is going to be 1024 * 4 bytes = 4 KB per vector, and with production-grade replication of three it’s going to require 12 KB of storage per vector.
Subsequently, for 100,000,000 vectors, the entire required quantity of storage is 1.2 TB. In fact, there’s a quantization choice, which can scale back this quantity, and the most well-liked and least invasive scalar quantization would require 25% of the storage, which is 300 GB.
Subsequently, the approximate month-to-month storage related prices:
- Non-quantized in RAM ~6000 USD
- Scalar-quantized in RAM ~ 1500 USD
- Distant Disk ~120 USD
- Native Disk ~ 300 USD
And since it is a linear relationship, the hole solely widens because the index grows towards the size agentic programs are pushing towards:
| Vectors | Storage (non-quantized) | RAM value/month | Scalar-quantized RAM value/month | Distant Disk value/month | Native Diskvalue/month |
| 100M | 1.2 TB | ~6,000 | ~1,500 | ~120 | ~300 |
| 500M | 6 TB | ~30,000 | ~7,500 | ~600 | ~1500 |
| 1B | 12 TB | ~60,000 | ~15,000 | ~1,200 | ~3000 |
In consequence, despite the fact that scalar quantization reduces the invoice considerably, it’s nonetheless a excessive value in comparison with the on-disk choice.
The trade-off
As with every little thing in engineering, the associated fee discount offered by on-disk ANN algorithms shouldn’t be free. Whereas the routing layer does guarantee environment friendly knowledge retrieval and narrows down the exploration to the smaller subset, the information nonetheless must be loaded from the disk, which is considerably slower than loading it from RAM. It’s value mentioning that for lots of use circumstances it will not be a deal breaker. Contemplating circumstances akin to RAG, the place outcomes from the vector db are then handed to the reranker and LLM, the 100ms delay on the retrieval shouldn’t be going to be the primary bottleneck, however for circumstances akin to agentic reminiscence, context, and so forth., it truly could also be most popular to have the ability to execute search as quick as attainable, particularly if there are a number of calls throughout a single agent request processing.
It’s genuinely laborious to offer a transparent quantity for on-disk latency, and that’s type of the purpose, it extremely is dependent upon the precise setup. For instance, the SPANN paper stories reaching 90% recall in round 1ms at billion scale, however that’s a imply latency on a single machine with the index saved on native SSD. As soon as you progress to an actual deployment, the image adjustments. Turbopuffer’s benchmark on a 10M-vector index exhibits round 14ms at p50 when the index is heat on quick storage, however near 874ms when it’s chilly and needs to be fetched from object storage, which is round a 60x distinction on the identical knowledge simply from the cache state. Elements like {hardware} and whether or not the information is heat (already in cache) can every transfer the quantity by 10x or extra. Basic steerage is that disk-based ANN algorithms present slower latency than HNSW (in RAM) simply because RAM entry is far quicker.
Select properly
With each on-disk and in-memory algorithms, it’s essential to make the proper alternative about which one will likely be a greater match on your use case. Whereas HNSW supplies a simple, well-rounded resolution for small and medium dimension indexes, it could be value exploring the on-disk choices as soon as your index grows greater and the related prices of storing vectors in RAM turn into a burden. Furthermore, there are at all times edge circumstances like comparatively high-dimensional vectors for which RAM will likely be a bottleneck comparatively early or enormous low-dimensionality indexes which may make the most of RAM for for much longer. For engineers, it’s essential to pay attention to such use circumstances and make a complete determination on the trade-offs acceptable for his or her use circumstances.
| Algorithm | What stays in RAM | Latency | Scales to | Attain for it when |
| Actual search | Full vectors (or streamed from disk) | grows with N | < ~10k | tiny collections, ground-truth eval |
| HNSW | complete index (disk attainable, huge latency penalty) | usually in sub 10ms | ~1M–100M in RAM | latency-critical, index suits RAM finances |
| DiskANN | PQ vectors + graph; graph grows with N | low ms heat, gradual when chilly | 100M–1B+ | giant & cost-sensitive |
| SPANN | centroids solely | low ms heat, gradual when chilly | 100M–multi billions | even PQ-in-RAM is just too costly |
