Adaptive Vector Search in Practice

Abstract

Vector search over a growing corpus becomes expensive in a specific and predictable way: the cost is dominated less by the index traversal itself than by the repeated comparison of high-dimensional vectors. This note describes a two-pass retrieval pattern that addresses both terms of that cost. A first pass shortlists candidates against a truncated, low-dimensional form of each embedding; a second pass reranks the shortlist against the full-dimensional vector. The pattern depends on Matryoshka representation learning, under which a prefix of an embedding remains a usable embedding, so the cheap first pass requires no second model and no additional inference call.

We set out the design, the storage and index configuration it implies, and the measured cost at the scale of the knowledge base described in the companion paper. The pattern was adopted when it was demonstrably the slower option, on a forward-looking argument about where the two cost curves cross. Re-measuring after the corpus grew from roughly 13,000 chunks to nearly 24,000 finds that argument largely borne out: what was a fivefold penalty is now approximate parity on a warm cache, and on a cold cache the two-pass pattern is already the faster of the two by a wide margin. We report both sets of figures, including the ones that were unflattering at the time.

1. The problem

Given a corpus of N text chunks, each carrying a D-dimensional embedding, and a query embedding, the task is to return the K nearest neighbours by cosine similarity. The naive formulation, an ordered scan over the whole table, is adequate until N grows into the tens of thousands, at which point an approximate nearest-neighbour index becomes necessary. In pgvector this is typically HNSW (Malkov and Yashunin 2018).

Per-query cost is then governed by two quantities. The first is the number of vectors the index visits, which rises with the ef_search parameter that controls the accuracy of the traversal. The second is the cost of a single comparison, which scales with dimensionality: a cosine distance between two 1,536-dimensional vectors is on the order of 1,500 floating-point operations, against roughly 500 for two 512-dimensional vectors. The ratio matters because the comparison is performed many times per query.

The pattern described here attacks both quantities. Most of the traversal happens at low dimensionality, and the full-dimensional cost is paid only on a small set of surviving candidates.

2. Matryoshka embeddings

The pattern 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 not only the full output vector but every prefix of it. The first 64 dimensions constitute 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 either wrong or expensive, and the pattern would not be worth building.

3. The two-pass design

Once the truncated vector is accepted as usable, the design follows. The first pass runs an approximate nearest-neighbour search against an index built on the truncated embeddings, returning a shortlist considerably wider than the number of results ultimately wanted. 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 ratio of shortlist size to result count is the one substantive tuning decision. It trades recall against cost: the shortlist 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 are worth recording. The traversal accuracy parameter is set inside the database function and scoped to the current transaction, so a generous setting applies to this query without affecting other workloads on the same database. And access control is applied after retrieval, by intersecting the returned documents against the repositories the caller may see, which keeps the retrieval function itself free of authorisation logic.

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 size of the full one, which is what the dimension ratio predicts and slightly better than the 35% observed at the smaller scale. Carrying both is therefore an easy trade, and the gap between them widens in absolute terms as the corpus grows, which is the point.

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 therefore slower, by something in the region of five to six times, and the case for it rested entirely on projection. Three arguments were offered. The first was that the two cost curves scale differently: single-pass cost grows roughly with the traversal width multiplied by the logarithm of corpus size, while the additional two-pass term is proportional to shortlist size and dimensionality and is bounded, so it does not grow with N. The second was cache pressure, on the reasoning that the full-dimensional index would eventually outgrow shared buffers while the truncated one would not, producing a step change rather than a gradual degradation. The third was that a generous traversal width is cheap on the truncated index and expensive on the full one.

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. What was a fivefold penalty is now a difference of about 0.6 ms, which is approximate parity and within the range that ordinary variance on a shared instance would produce. 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 are the more striking result, and they are the cache-pressure argument arriving earlier than 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 figure is included for scale rather than as a serious comparison: 13 seconds for a brute-force comparison against every row makes the case for having an index at all, which is not in dispute.

5.3 What this does and does not establish

The direction of travel is clear, and it matches the projection. We would still not defend the original estimate that the crossover falls between 100,000 and 500,000 chunks, because on these numbers the warm crossover looks likely to arrive earlier than that, and the cold crossover has already passed.

Several caveats apply and should be read as limiting the result. Each figure is a single observation rather than a distribution, so the warm comparison in particular is not robust to variance. The measurements were taken against a hosted instance carrying other load. The cold and warm conditions were distinguished by first and subsequent execution rather than by deliberate cache control, so "cold" means only that the pages were not resident at the moment of measurement. And the query vector was drawn from the corpus itself rather than produced by embedding a genuine query, which is adequate for cost measurement and tells us nothing whatever about recall.

The conclusion we draw is narrow. Carrying the pattern through the period when it was measurably slower was the right call, not because the overhead was trivial, though it was, but because the cost of replacing a retrieval layer rises with how much depends on it, and the numbers moved in the direction the design assumed they would.

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

Three variations are worth knowing about, none of which we 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-backed search over a Matryoshka-trained embedding model, the pattern is: store the full embedding and its truncated prefix, both as halfvec, both indexed; run the approximate search against the truncated index; sort the shortlist in memory by full-dimensional distance; and set the shortlist at roughly ten times the result count, tuning from there if recall proves inadequate. Two indexes, one database function, one slice.

The wider point is about adopting a pattern whose measured cost is, at the time of adoption, negative. That decision rested on the shape of the curves rather than on the numbers then available, and on the asymmetry between carrying a small overhead early and rewriting retrieval late. Eighty per cent of corpus growth later, the warm penalty has closed to nothing and the cold case has inverted, so on this occasion the judgement held.

It is worth being clear about how weak a vindication that is. One system, two measurement points, single observations at each, and a projection whose specific figures we have already had to revise. The transferable part is not the crossover estimate, which was wrong, but the reasoning: where a design choice is cheap now, reversible only expensively later, and pointed in the direction the workload is already moving, the measured cost today is the wrong thing to optimise.

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.