Optimize Vector Search When RAM Will get Too Costly: On-Disk vs. In-Reminiscence ANN Indexes

, vector search has turn into a important 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 tens of millions scale to the a whole bunch of tens of millions and even billions. At this scale, storing indexes and related knowledge in RAM will value 1000’s of {dollars} per 30 days, and HNSW can turn into a scalability bottleneck.

On this article I wish to dive into the small print of what truly makes semantic search quick and environment friendly: approximate nearest neighbor (ANN) algorithms, what completely different choices exist, and their trade-offs.

Deep dive into vector DB

Vector databases include three major elements:

• embeddings – the numeric illustration of the corpus 
• search algorithm and index construction – the algorithm defines the search high quality and pace
• storage – how the information is saved (in reminiscence, on disk, payload along with embeddings, and so on.). 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 deal with search algorithms, and particularly ANN ones. There are usually two approaches for the search execution:

• Actual search – which demonstrates the perfect retrieval metrics though it doesn’t scale effectively by way of latency 
• Approximate nearest neighbor (ANN) – which trades off the retrieval high quality for the latency and scalability. 

The precise search is a straightforward method which loops by way of all the entries within the index and calculates the space 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 terrific method for both very small indexes or experimentation, however usually not very appropriate for the manufacturing scale. 

Attention-grabbing truth: many fashionable vector databases assist you to bypass index constructing for small collections, falling again to kNN search as a result of the overhead of constructing an index just isn’t value it for just a few thousand vectors.

The second choice is approximate nearest neighbor algorithms, which is a bunch of algorithms with the primary function of bettering 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 range, 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 regardless that ANN algorithms are all following an identical idea to realize the purpose of offering a brief path to the tip end result, there are completely different implementations with completely different algorithms having distinctive units of trade-offs, which makes it essential to pick out the one that matches your precise use case. 

On this article I wish to deal with two completely different teams of the ANN algorithms:

• RAM-based – such algorithms are optimized for storing all or a giant 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 (a minimum of partially), however they’re optimized for the precise storage kind and subsequently will present the perfect outcomes using what they had been designed for. 

In-memory ANN

HNSW (Hierarchical Navigable Small World)

The preferred ANN algorithm utilized by virtually 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 terrific match for small-medium use circumstances and can present the perfect retrieval pace.

Nevertheless, 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 might trigger a big drop in retrieval high quality. The principle cause for such a efficiency hit is that the HNSW construction just isn’t optimized for the clustered disk entry, and in consequence, the search would produce quite a lot 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 might considerably enhance latency, from milliseconds to a whole bunch of milliseconds or worse underneath 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 might 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 cut back the storage prices whereas offering acceptable latency. It’s a terrific alternative if search latency just isn’t important and the index dimension is predicted to be massive. We will take into account two major 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 massive billion-vector+ indexes that gained’t slot in RAM or might be too costly to be saved in reminiscence. The thought is to arrange factors in clusters, which is a pure property of the embedding area, choose a centroid illustration of the cluster, and put it to use for the routing layer. Centroids and mainly the entire routing layer may 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 subsequently may be loaded from it quick and effectively. Throughout search, centroids are used to search out the closest teams of vectors, after which the vectors related to these centroids are loaded from disk to carry out a full scan.

Word: 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 one centroid are grouped on disk and subsequently 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 method, DiskANN maintains a single-layer graph known as Vamana. The principle thought behind it’s to attenuate the variety of hops required to search out the highest ok factors and subsequently the variety of random disk entry operations. It’s achieved by conserving some longer-range connections as an alternative of solely the closest ones, so fewer hops are wanted to succeed in 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 decreasing 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 info on disk just isn’t clustered, and the disk I/O is minimized by the routing layer doing a minimal variety of hops to get to comparable vectors, resulting in extremely environment friendly search in apply. There are quite a lot of inner particulars on how precisely it’s applied, 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

Word: the costs under 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 slightly than precise quotes

With RAM costing about 5$ per GB by way of cloud suppliers, EBS is about 50 occasions 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 will likely be 1024 * 4 bytes = 4 KB per vector, and with production-grade replication of three it’ll require 12 KB of storage per vector.

Subsequently, for 100,000,000 vectors, the overall required quantity of storage is 1.2 TB. After all, there’s a quantization choice, which can cut 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:

In consequence, regardless 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 part in engineering, the associated fee discount offered by on-disk ANN algorithms just isn’t 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 is probably not a deal breaker. Contemplating circumstances equivalent to RAG, the place outcomes from the vector db are then handed to the reranker and LLM, the 100ms delay on the retrieval just isn’t going to be the primary bottleneck, however for circumstances equivalent to agentic reminiscence, context, and so on., it truly could also be most well-liked 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 arduous to present a transparent quantity for on-disk latency, and that’s form of the purpose, it extremely is determined by 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 modifications. Turbopuffer’s benchmark on a 10M-vector index reveals 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. Common steering is that disk-based ANN algorithms present slower latency than HNSW (in RAM) simply because RAM entry is far sooner.

Select properly

With each on-disk and in-memory algorithms, it’s essential to make the correct alternative about which one might be a greater match on your use case. Whereas HNSW supplies a straightforward, well-rounded resolution for small and medium dimension indexes, it could be value exploring the on-disk choices as soon as your index grows larger 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 might be a bottleneck comparatively early or large low-dimensionality indexes which might make the most of RAM for for much longer. For engineers, it’s essential to concentrate on such use circumstances and make a complete determination on the trade-offs applicable for his or her use circumstances. 

References