Building and Searching 100 Million Vectors#

Authored by Lyon Lay

TL;DR: We built an open-source vector index that indexes 100 million vectors in 1 hour and searches them at 23 ms p99 latency with 96% recall@100. We found no published build on comparable data and hardware that is faster.¹ It has many favorable scaling properties, suggesting it could scale to 100B vectors. The purpose of this post is to make this work available to the industry.² The code, benchmarks, and results are all open source.

Vector search is a core component of many AI systems; it enables search for similar documents, images, or text over vast corpora of data. Brute force gives exact answers but is untenable at scale.³ An index makes search practical by reducing the work needed; it finds most of the nearest neighbors while only reading a small fraction of the data. Prequisite knowledge and terminology are in the appendix.

Hierarchical SPANN, our index architecture, is a tree that divides the collection into progressively smaller regions, allowing a query to traverse to the most promising regions. This structure scales well horizontally as subtrees can be divided across machines.

How the index works#

The data structure#

A leaf holds a posting list; an internal node holds its children's centers. With a target of about a hundred children per internal node, the measured 100M tree has four levels and the 100B-shaped tree has six. The tree stays shallow, though preserving recall may require exploring more branches.

Compression makes comparisons cheap. The query routes with 4-bit-per-dimension centroid codes, scans posting-list codes, 1-bit-per-dimension compressions of each stored vector (codes for short), and checks its shortlist at full precision. Both kinds of code use RaBitQ ⁵.

Subtrees also provide natural boundaries between machines. Splitting a proximity graph such as HNSW can leave search paths crossing machines and paying network round trips. A subtree owns a set of leaves that can be served together.

The query algorithm#

Building the index#

The writer alternates insertion with balancing: moving vectors, creating or removing nodes, and adding levels. It publishes snapshots for readers, allowing construction and querying to use different settings, representations, and machines.

The build time includes keeping the tree balanced and searchable after each batch. As the collection grows, insertion navigates a larger tree and balancing operates over more leaves.⁶

Storing each vector in one list simplifies maintenance. SPANN can replicate boundary vectors across neighboring lists to improve recall ⁴. In my experiments, the modest recall gain came with much longer builds: moving a vector requires removing its outdated copies. One copy also avoids cross-machine replica bookkeeping.

In Chroma's production architecture, writes enter our durable wal3 log, background workers publish index versions, and queries combine a committed index with recent writes. Integrating this prototype and measuring sustained-write performance are work for a later post.

Sharding the index#

When opening a snapshot, the reader orders leaves depth first to keep subtrees together, then divides them into equally sized parts. A coordinator routes the query; each machine scans its selected leaves and returns a shortlist. Full vectors come from a block store ⁷ on demand, and each machine indexes only its own leaves' blocks.

Each machine caches the full routing tree, about 0.75 bytes per stored vector at 100M, to avoiding distributed routing overhead: potentially a network round trip at every level.

Splitting preserves the selected lists and candidates. Each part reranks its own shortlist, however, so more parts check more candidates at full precision. Recall rises slightly, along with reranking work.

Scaling behavior#

As the collection grows so does the index. For an index to scale, we want to see that the work done for each query (# computations performed, the cost per computation, # of MB loaded) scales sub-linearly with collection size, or even converges on a cieling. This is indeed what we observe.

I built one FineWeb ⁸ index, saving checkpoints from 1M to 100M. The query set, dataset source, dimensions, construction settings, and hardware stay fixed; exact answers are computed for each size.

Maintaining accuracy at scale#

Moving from 10M to 100M vectors, recovering the same fraction of neighbors requires roughly two to three and a half times the scan, depending on the recall target. Brute force would require ten times the work.

Latency grows faster than codes scanned because navigating the larger tree adds work. To understand that cost, separate how well lists group neighbors from how well queries find those lists.

We lose the most accuracy when traversing the tree#

Grouping holds up over the directly measured range: from 1M to 10M, nearly all true neighbors remain concentrated in a few dozen lists.

Finding those lists gets harder as more centers compete for similar ranks. A center summarizes a list; it need not be among the closest centers for its list to contain a true neighbor. Relevant lists with far-away centers slip further down the ranking, requiring a wider search.

Internal routing faces the same choice. At small sizes, a query can score every internal node. Around 50M, retaining only approximately the best tenth of the second level saves enough work to search more leaves, reaching higher recall in less time.

The hierarchy still skips most vectors, but preserving recall requires more work to choose the right lists. That routing cost also limits the gains from distributing scans.

Scaling across machines#

Sharing leaves across machines increases capacity and throughput more than it improves single-query latency. I measured the difference by serving the same 100M index from one, two, four, and eight identical machines.

Once scans are distributed, routing dominates latency. Parallelizing it across the coordinator's cores helps, but selecting the next beam remains sequential. Queries also wait for the slowest scan worker, and selected lists rarely divide evenly.

At 100M, queries touch nearly every machine despite subtree placement. Communication would fall only if each machine owned a much larger region than a query typically explores. The deeper-tree experiment below tests that possibility.

The coordinator also caps throughput: it routes, scans its part, and merges every query. Total CPU work per query rises with machine count because scanning the same codes in smaller pieces adds overhead.

What would it take to search 100B vectors?#

Extending the 10M–100M trend three more factors of ten gives too wide a range for a useful prediction. Instead, I test a real routing tree at the depth of a 100B index and do some napkin math to derive the rest. A narrower 1B prediction is in the appendix.

A larger collection needs a wider search space#

Routing compares queries only with centers, so it can be tested without building every posting list. I use 70M real vectors as stand-in leaf centers in a tree with the depth and level widths expected at 100B. This measures routing work and retention of nearest centers, not end-to-end recall over 100B vectors.

A beam that retains nearly all nearest centers at the 100M shape loses recall as the tree deepens. Retaining 95% at the 100B shape requires an internal beam of about 8,192. Shallow navigation still takes substantial work.

The deeper tree offers more locality: selected lists concentrate in fewer subtrees, contacting a smaller fraction of machines. Distribution has room to grow if routing can keep up.

Routing accuracy is the bottleneck#

The budget separates measured results, estimates derived from current rates, and extrapolated trends. The scan estimate is an order of magnitude, not a promised operating point.

At the measured scoring rate, routing alone would take roughly 100–175 ms per query, before scanning any lists. This is derived, not directly timed on the 100B-shaped tree. Distributing more leaf data does not remove that bottleneck.

The hierarchy makes large collections practical by skipping most of their vectors. The next gains depend on choosing what to skip more efficiently.

Suggested reading#

These are the systems and papers closest to this work. Each takes a different position on where vectors live, how queries are routed and how vectors are compressed.

Vector search at production scale#

• turbopuffer, ANN v3: 200ms p99 query latency over 100 billion vectors (2026). A hierarchical clustered index with compressed vectors in memory and full vectors on local SSD, serving 100B vectors.
• Andy Kimball, Real-Time Indexing for Billions of Vectors (Cockroach Labs, 2025). C-SPANN: a hierarchical k-means tree over a distributed SQL database, with incremental splits and merges.
• Sandeep Lingam, Explore YugabyteDB's Vector Indexing Architecture (Yugabyte, 2025). Vector indexes inside a distributed database's storage layer.
• Adams et al., DistributedANN: Efficient Scaling of a Single DiskANN Graph Across Thousands of Computers (Microsoft, 2025). One 50B-vector graph spread over more than a thousand machines, in production for Bing.
• Faiss, Indexing 1T vectors (GitHub wiki, 2020). Practical lessons from building a trillion-vector index.

Partitioned and hierarchical indexes#

• Chen et al., SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search (NeurIPS 2021). The disk-resident posting-list design this index builds on.
• Xu et al., SPFresh: Incremental In-Place Update for Billion-Scale Vector Search (SOSP 2023). Keeping a SPANN index balanced under inserts and deletes.
• Sun et al., SOAR: Improved Indexing for Approximate Nearest Neighbor Search (NeurIPS 2023). Assigning vectors to extra partitions so that partition misses are less correlated.
• Mohoney et al., Quake: Adaptive Indexing for Vector Search (2025). Multi-level partitioning with query-adaptive search budgets and workload-aware maintenance.

Compression#

• Gao and Long, RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound (SIGMOD 2024). The 1-bit codes with error bounds used for posting scans here.
• Gao et al., Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search (2024). Extends RaBitQ to multiple bits per dimension.
• Zandieh et al., TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate (2025), with its predecessors QJL (2024) and PolarQuant (2025). Data-oblivious quantizers developed for KV caches and vector search.

Graph indexes on disk#

• Guo and Lu, Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD (OSDI 2025). PipeANN: overlapping graph search with SSD reads.
• Lou et al., DGAI: Decoupled On-Disk Graph-Based ANN Index for Efficient Updates and Queries (2025). Separating graph topology from vector storage on disk.

Appendix#

Next steps#

The prototype builds on one machine with bounded balancing work, publishes immutable snapshots, and serves them across machines with full-vector retrieval on demand. The next improvements target routing and storage costs:

• Parallelize beam selection. Address the sequential step that limits routing once scans are distributed.
• Distribute query coordination. Let each machine route and merge a share of queries. Alternatively, split routing itself across subtrees, trading local work for network round trips. Subtree placement and beam allocation determine whether that pays off.
• Improve list selection. Better predictions of which lists contain neighbors could narrow the required beam. Full-precision centers are one option, but precision alone need not improve ranking. Their codes occupy eight times the space of 4-bit codes, increasing routing memory unless the tree is split.
• Fetch full vectors individually. Reranking reads blocks containing whole lists, fetching far more than its shortlist uses on a cold cache. Finer-grained storage would reduce that amplification.

A prediction for 1B#

The figure extends the fitted 10M–100M trend one more factor of ten, recording a prediction before the 1B experiment runs.

Four assumptions define the prediction:

1. The trend continues. A much larger scan or routing requirement would show it bending beyond the measured range.
2. The search grid approximates target recall. Budgets double between settings. Even the 100M starting points are interpolated, contributing to wide ranges.
3. Memory conditions hold. Latency assumes one machine holds the index in memory. At 1B, full vectors alone occupy about 3 TB; a practical deployment would split the index and incur the measured routing floor and coordination costs.
4. Routing preserves enough candidates. The stand-in retains 98% of nearest lists at the 1B shape with a moderate beam. A real index requiring a much wider beam would challenge the prediction.

Background#

The post assumes some familiarity with the topics below. If one is new, the linked article is a good starting point.

• Vectors and embeddings: representing text, images and other data as points in a high-dimensional space, where similar items sit close together. Embedding (machine learning)
• Distance between vectors: how closeness is measured, usually Euclidean distance or cosine similarity. Euclidean distance, Cosine similarity
• Nearest-neighbor search (k-NN): finding the k stored vectors closest to a query. Nearest neighbor search, k-nearest neighbors
• Approximate nearest-neighbor search (ANN): trading a little accuracy for much less work, measured by recall. Approximate nearest neighbor, Precision and recall
• Database indexes: auxiliary structures that let a query read a small part of the data instead of all of it. Database index
• Vector databases: databases built around storing and searching embeddings. Vector database
• Clustering and quantization: grouping nearby points around centroids, and compressing vectors into short codes. k-means clustering, Vector quantization
• Posting lists: the per-group lists of items that partitioned indexes scan, a term borrowed from text search. Inverted index
• Beam search: exploring a tree or graph by keeping only the best few candidates at each step. Beam search
• Graph indexes: the main alternative to partitioned indexes, contrasted with the tree in "A wide tree keeps navigation shallow". Hierarchical navigable small world
• Sharding: splitting one database across machines. Shard (database architecture)

Terminology#

• Collection: the set of stored vectors being searched. Its size is the number of vectors, written N.
• Dataset: where the vectors come from and how they are distributed, here FineWeb. The experiments vary the collection's size while keeping the dataset fixed.
• Posting list (list): a group of nearby vectors that is searched as a unit.
• Centroid (center): the vector that summarizes a list or a group of nodes; queries compare against it to decide where to search.
• Leaf: a tree node that owns one posting list.
• Internal node: a tree node that holds the centroids of its children and only routes queries.
• Routing tree: all internal nodes and leaf centroids; it is small enough to keep in memory on every machine.
• Routing: walking down the routing tree to choose which lists to search.
• Beam (beam width): how many nodes a query keeps at each level while routing; a wider beam finds more of the right lists and costs more.
• Posting-list code (code): the compressed, 1-bit-per-dimension form of a stored vector that the scan reads; each list holds one code per vector. Cost is measured in codes scanned per query.
• Scan: scoring every code in the chosen lists.
• Shortlist: the best candidates from the scan, passed on to rerank.
• Rerank: computing exact distances for the shortlist with full-precision vectors and returning the best k.
• Recall@k: the share of a query's true k nearest neighbors that appear among the k results.
• Part: the share of the leaves one machine serves when the index is split across machines; each part is a run of whole subtrees.
• Routing machine: the machine that routes a query, scans its own part and merges the other machines' shortlists.
• Writer, reader and snapshot: the writer builds and balances the tree and publishes immutable snapshots; readers open a snapshot to serve queries.
• Block store: Chroma's S3-backed storage for large immutable blocks, cached on local disk and in memory.

Code and data#

The implementation, full results, and benchmark code are in chroma-core/chroma#7960 (as of commit 4de458a), for reproducing the measurements, tuning the index, and testing the forecast on other datasets.