Adaptive vector search in practice

Abstract

As a vector corpus grows, much of the cost comes from comparing high-dimensional vectors again and again. I used a two-pass search to reduce that work. The first pass builds a shortlist from a truncated embedding; the second reranks those candidates against the full vector. Matryoshka embeddings make this possible because their prefixes remain useful embeddings. There is no second model and no extra inference call.

The first measurements were not flattering. At roughly 13,000 chunks, the two-pass query was about five times slower than a single search against the full index. I kept it because the two cost curves grow differently. Once the corpus reached 23,839 chunks, the warm-cache penalty had fallen to about 0.6 ms and the two-pass path was already faster on a cold cache. Below are the design, its storage and index choices, and both sets of measurements. The ugly numbers are part of the story.

1. The problem

Given N text chunks with D-dimensional embeddings, a query needs the K nearest neighbours by cosine similarity. An ordered scan over the table is fine at first. Once N reaches the tens of thousands, an approximate nearest-neighbour index becomes necessary. In pgvector that usually means HNSW (Malkov and Yashunin 2018).

Two things determine the query cost. The index visits more vectors as ef_search rises, buying accuracy with extra traversal. Each comparison also gets more expensive as the vectors get wider: cosine distance for two 1,536-dimensional vectors takes about 1,500 floating-point operations, against roughly 500 for two 512-dimensional vectors. A search repeats that comparison many times.

The two-pass design does most of the traversal on smaller vectors, then pays the full-dimensional cost for the shortlist alone.

2. Matryoshka embeddings

The design rests on a property of how certain embedding models are trained. OpenAI's text-embedding-3-small and -3-large are trained with a Matryoshka loss (Kusupati et al. 2022), which optimises the full output vector and each prefix of it. The first 64 dimensions form a coarse embedding, the first 256 a finer one, the first 512 finer still, and the full 1,536 the most precise. The dimensions are ordered by importance by construction.

This is materially different from compressing a learned embedding after the fact, whether by principal component analysis, an autoencoder, or product quantisation. Post-hoc compression discards ranking signal in the tails, which is precisely where a shortlist pass needs to remain trustworthy. Under a Matryoshka model, taking the first 512 dimensions of a vector yields a valid lower-fidelity embedding at no cost: no second model, no additional inference call, and no additional latency at query time. OpenAI's own documentation endorses the prefix-slicing approach directly.

Without this property, the first pass would be wrong or expensive. There would be little point building it.

3. The two-pass design

The first pass runs an approximate nearest-neighbour search against an index on the truncated embeddings. It returns a shortlist considerably wider than the requested result set. The second pass computes exact cosine distances between the query's full-dimensional embedding and the full-dimensional embeddings of the shortlisted candidates only, sorts them, and returns the top K.

The second pass does not use the full-dimensional index at all. It is an in-memory sort over a hundred or so rows, and the index built on the full-dimensional column, which we retain, goes unused on this path.

The shortlist ratio is the main tuning decision. It trades recall against cost: the list must be wide enough that the true top K is almost certainly contained within it, and narrow enough that the rerank remains cheap. We default to roughly ten candidates per returned result, so a request for ten results shortlists a hundred. At that ratio the rerank is sub-millisecond, and we have not observed the first pass dropping a result that should have ranked in the final ten. That is an observation from use rather than a measured recall figure, and it should be read as such.

Two implementation details proved useful. The database function sets the traversal accuracy for the current transaction, so this query can use a generous value without affecting other workloads. Access control runs after retrieval by intersecting the returned documents with the repositories the caller can see. That keeps authorisation logic out of the retrieval function.

4. Storage and index configuration

Both embedding columns are stored as halfvec, pgvector's 16-bit floating point type, rather than the 32-bit vector type.

That is approximately 4 KB of embeddings per chunk against the 8 KB that 32-bit storage would require, with corresponding effects on index size and memory pressure. For a hypothetical million-chunk corpus the difference is 4 GB against 8 GB on disk. The quality cost of 16-bit storage for cosine distance is, for this use case, below the noise floor; quantised embeddings are in routine use on public retrieval benchmarks without measurable degradation.

Both columns carry HNSW indexes built with a graph degree of 16, the default, and a construction-time search width of 200 against a default of 64. The latter is a one-time cost at build time that improves recall at query time. Sizes at the two points where we have taken measurements:

The truncated index is now 33% of the full index's size, close to the ratio of their dimensions and slightly better than the 35% measured at the smaller scale. Keeping both is cheap enough, while the absolute size difference grows with the corpus.

5. What it costs

5.1 The original measurement

Query plans captured at roughly 13,000 chunks, with the traversal width set to 200, gave a single-pass scan over the full-dimensional index at approximately 2.99 ms, against approximately 16.84 ms for the two-pass pattern, of which roughly 3.49 ms was the shortlist traversal and roughly 13.10 ms the rerank.

At that scale the pattern was five to six times slower. The argument for keeping it was entirely about what would happen as the corpus grew. Single-pass cost rises roughly with traversal width multiplied by the logarithm of corpus size. The extra two-pass work depends on shortlist size and dimensionality, so it stays bounded as N grows. I also expected the full index to outgrow shared buffers before the truncated one, with a sharp penalty once it did. Finally, a generous traversal width costs less on the smaller index.

5.2 Re-measured after growth

The corpus has since reached 23,839 chunks, roughly eighty per cent larger, which is enough to test the projection. The same measurements, taken with the same traversal width:

The warm figures have converged. A fivefold penalty is now about 0.6 ms, effectively parity on a shared instance. The shortlist traversal takes roughly 5.5 ms and the rerank roughly 1.9 ms, so the rerank remains cheap, as predicted, while the traversal it replaces has become the dominant term.

The cold figures show the cache-pressure effect earlier than I expected. On first touch, the 69 MB full-dimensional index costs 1,288 ms to page in, against 868 ms for the two-pass path, which reads a 23 MB index for the traversal and then touches only a hundred full-dimensional rows. The two-pass pattern is already the faster option whenever the working set has been evicted, and it will remain so by a widening margin as the full index grows.

The exact scan is there for scale. Thirteen seconds of brute-force comparison against every row settles the case for having an index at all.

5.3 What this does and does not establish

The measurements moved in the expected direction. I would no longer defend the original estimate of a crossover between 100,000 and 500,000 chunks. The warm crossover now looks likely to arrive sooner, while the cold crossover has already passed.

These are limited results. Each number is one observation, not a distribution, so the warm comparison is vulnerable to ordinary variance. The hosted instance was carrying other load. "Cold" means the pages were absent on the first run, not that I controlled the cache directly. The query vector also came from the corpus instead of a real query. That is enough to measure cost and says nothing about recall.

Keeping the pattern while it was slower still looks like the right call. The overhead was affordable, retrieval would become harder to replace as more code depended on it, and the numbers moved in the direction the design assumed.

6. When the pattern does not apply

Several situations rule it out.

For corpora below roughly 5,000 rows, a single indexed scan is correct and the two-pass design is pure cost. For models not trained with a Matryoshka objective, truncation produces a worse representation than an equivalently small purpose-trained embedding would, and the pattern requires either a second model or post-hoc dimensionality reduction, both of which reintroduce the complexity it was meant to avoid. Current models from several providers train this way, but the model documentation should be checked rather than assumed.

Where exact nearest neighbours are required, the pattern is unsuitable by construction: the first pass may drop a vector that belongs in the true top K but does not rank in the truncated top hundred. Deduplication and near-duplicate detection are the obvious cases, since they depend on precisely the tail behaviour that the shortlist discards. Finally, where a strict tail latency budget applies, the two-pass design has both a higher median and a slightly less predictable tail, and paying a consistent 3 ms may be preferable to paying 17 ms most of the time.

7. Variations

There are three obvious variations, none of which I have needed.

A three-pass cascade extends the idea, shortlisting first at 64 dimensions before the 512-dimensional pass and the full rerank. The returns diminish against the additional moving parts.

Hybrid lexical and vector retrieval reranks the vector shortlist with a term-frequency score such as BM25 (Robertson and Zaragoza 2009), which helps where queries contain identifiers or rare proper nouns that should match exactly rather than semantically. This is the variation we would reach for first, since a documentation corpus contains a great many function and product names.

Replacing the rerank with a cross-encoder, which scores query and candidate jointly rather than embedding each independently, improves quality substantially at considerably greater cost. It suits top-of-funnel search where the user is attending closely to relevance.

8. Summary

For pgvector search with a Matryoshka-trained model, store the full embedding and a truncated prefix as indexed halfvec columns. Search the smaller index, then sort that shortlist in memory by full-dimensional distance. A shortlist around ten times the requested result count is a reasonable starting point, subject to actual recall testing. The implementation is two indexes, one database function and one slice.

I adopted this while the measurements said it was slower because carrying a small early overhead seemed cheaper than replacing retrieval later. After the corpus grew by eighty per cent, the warm penalty disappeared and the cold case reversed. On this occasion, the judgement held.

That is weak evidence: one system, two measurement points and a single observation at each. I have already revised the original crossover estimate. The useful part is the decision method. If a design choice is cheap now, expensive to reverse later and points in the direction the workload is already moving, today's benchmark is only one part of the decision.

References

• Kusupati, A., Bhatt, G., Rege, A., et al. (2022). Matryoshka Representation Learning. NeurIPS 2022. arXiv:2205.13147.
• Malkov, Y. A. and Yashunin, D. A. (2018). Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE TPAMI 42(4), 824–836.
• Robertson, S. and Zaragoza, H. (2009). The Probabilistic Relevance Framework: BM25 and Beyond. Foundations and Trends in Information Retrieval 3(4), 333–389.
• OpenAI. Embeddings guide, on shortening embeddings by prefix truncation.
• pgvector. HNSW index reference, and the 0.7.0 release introducing halfvec.
• Supabase (2024). Fewer dimensions are better: benchmarking dimensionality reduction against retrieval quality in pgvector.