AI Frontiers, part 61: Retrieval at scale — sharding, freshness, and cache invalidation

Part 61from the AI Frontiers series · 65 parts in all

The retrieval stack in part 6 looked like a solved problem: embed documents, store vectors, query for neighbors. Everything in that description is true at a million vectors and increasingly misleading at a billion, for the same reason databases are easy in a tutorial and hard in production — the access pattern is unusual, the update pattern is worse, and the performance characteristics are governed by memory rather than by computation. Elasticsearch taught a generation of engineers that search is a distributed systems problem. Vector search is the same problem with a longer list of ways to lose recall silently.

This entry is the operational side of retrieval. It assumes part 43's point that the embedding layer is infrastructure, and part 52's point that the retriever's job is context assembly, and asks what changes when the corpus, the query volume, and the update rate all grow by three orders of magnitude.

Three axes of scale, three different problems

Teams say "our retrieval needs to scale" when they mean one of three things, and the solutions barely overlap.

Corpus scale. The index is large and mostly static. The challenges are memory footprint, index build time, and recall at high dimension. This is the regime the classic approximate-nearest-neighbor literature addresses.

Query scale. The index is modest but the traffic is heavy. The challenges are throughput, tail latency, and caching — this is the regime of replication, fan-out, and batch fusion.

Update scale. The index changes constantly: new documents, edits, deletions, permission changes, tenant churn. This is the hardest one, and it is the one that modern vector stores handle least gracefully, because the index structures that make approximate search fast are not the structures that make mutation easy.

Establishing which axis you are actually on is the first useful step, because a design that optimizes the wrong one produces a system that is fast where you do not need it and fragile where you do.

Billion-scale approximate search

Exact nearest-neighbor over a billion high-dimensional vectors is not feasible at interactive latency, so every production system is approximate, and every approximate index trades recall for speed along an explicit dial. The core toolkit is well established and worth knowing by name because the trade-offs differ, and because the design space of the surrounding systems — storage, filtering, distributed execution — has grown large enough to need a survey of its own (Pan et al.).

Graph indexes. Hierarchical navigable small-world graphs give excellent recall at high speed, at the cost of a large in-memory structure and expensive construction and updates (Malkov and Yashunin). For corpora that fit in memory, this is usually the right default.

Quantization-based indexes. Product quantization compresses vectors into short codes and searches the codes, cutting memory by an order of magnitude and introducing a distance approximation that must be accounted for in recall measurements. Inverted-file variants combine coarse clustering with residual quantization and remain the workhorse for very large, memory-constrained corpora. FAISS remains the reference implementation and documentation for this family (Johnson et al.; Douze et al.).

Disk-resident indexes. DiskANN and its successors keep the graph structure on SSD with a compressed in-memory representation, which is how corpora that do not fit in RAM are served at acceptable latency and cost (Subramanya et al.). The engineering consequence is that your performance model now includes storage IOPS, and your tail latency now includes disk scheduling.

Learned and anisotropic quantization. ScaNN's approach to anisotropic vector quantization showed that optimizing the quantization error for the inner-product ordering rather than for reconstruction accuracy measurably improves the recall-speed frontier (Guo et al.). The general lesson is that the right objective for a retrieval index is ranking quality, not geometric fidelity.

Two operational rules matter more than the choice of family. First, measure index recall against exact search on a fixed query sample, separately from end-to-end quality — they diverge, and the divergence tells you whether the problem is the index or the pipeline. Second, treat the index build as a batch job with a version: the index is an artifact, and artifacts need to be reproducible, swappable, and rollback-able.

Sharding, routing, and the recall you lose in the merge

Past a certain size, the index is partitioned, and partitioning introduces a class of failure that is invisible in single-node testing.

How to partition. Consistent hashing remains the standard for spreading keys across nodes with minimal movement when the node set changes (Karger et al.), and the practical improvement over naive modulo hashing is dramatic during resharding. Tenant-based partitioning is preferable where it is possible, because it converts a global scaling problem into per-tenant problems with independent lifecycles — and it gives you the isolation and residency properties that part 58 argued are increasingly mandatory. The universal caveat: partitioning by a key that correlates with query patterns creates hotspots, so partition keys must be chosen against the query distribution, not just the storage distribution.

Fan-out and merge. A query against a sharded index must either be routed to a subset of shards or broadcast to all of them and merged. Broadcasting is simple and correct; it multiplies tail latency by the number of shards (the slowest shard sets the response time) and it multiplies cost. Routing depends on a router that is itself a model or a classifier, and its mistakes are silent recall losses — the document is in a shard you did not query. The comparison with the router discussion in part 59 is exact: a router is a policy, and its errors are only visible if you measure the recall of the whole system rather than the latency of the parts.

Post-filtering at scale. Part 43 flagged metadata filtering applied after the nearest-neighbor search. At scale the effect compounds: with a hundred shards and a ten-percent selectivity filter, each shard returns neighbors that are then discarded, and recall collapses for exactly the restrictive queries that matter most. Pre-filtering requires an index that supports it, which is the single most important capability to evaluate when choosing a vector store.

Freshness: the problem vector stores handle worst

Deletes and updates are where the metaphor breaks. A graph index has no cheap way to remove a node that other nodes point to, so most implementations mark it deleted and return fewer results, degrading recall over time until a rebuild. A quantized inverted index rebuilds coarse clusters periodically. Neither gives you the property that a relational database gives you for free: that a query reflects committed writes.

The research answer is incremental graph maintenance with a fresh and a stale sub-index, merged lazily, which makes a continuous stream of updates sustainable without full rebuilds (Singh et al., "FreshDiskANN"). The pragmatic answer for most teams is a tiered design: a small, frequently rebuilt index over recent content searched alongside a large, stable index over the archive, with results fused. That pattern is easy to reason about, easy to roll back, and it handles the common real-world distribution where most relevance lives in recently changed material.

Two freshness rules follow. Never let the vector index be the only copy of freshness information: keep the authoritative store as the system of record and treat the index as a derived artifact with a known lag, which is what makes blue-green reindexing possible. And measure freshness as a product metric — the age of the newest content a query can find — not as an internal pipeline latency. The difference between "indexed within five minutes" and "the index reflects writes within five minutes" is where most incidents live.

Cache invalidation, honestly

Retrieval is cache-friendly for a reason that has nothing to do with search: it is expensive, idempotent, keyed by text, and heavily skewed. In most systems I have measured, the top few percent of queries account for a large fraction of volume, which is Zipfian in exactly the way caching was invented for. The lessons from large-scale cache deployments transfer directly (Nishtala et al.), including the hard ones.

What to cache. Query embeddings (cheap to cache, short-lived, removes an inference call from the hot path); retrieval results keyed by normalized query plus filter plus index version (the largest win, and the one with the sharpest staleness risk); reranker outputs; and prompt prefixes, which the serving layer caches as part 50 described.

Key design. Every cached value that depends on the index must include the index version in its key. This is the single most common bug in retrieval caching: an index swap happens, the old results keep being served, and the fix is discovered when someone notices that recently added documents are invisible. Similarly, anything depending on permissions must include the authorization scope, or you have built a cross-tenant leak with a performance optimization.

Invalidation strategy. Choose one deliberately and write it down. Short TTLs plus version-keyed entries is the simplest defensible policy, because the version component makes invalidation a namespace operation: bump the version and old entries become unreachable. Event- driven invalidation on document change is more precise and much harder to get right, since one document change can affect many cached queries. The classic advice — that cache invalidation is one of the two hard problems — remains accurate; the mitigation is to make correctness not depend on invalidation, which version-keying does.

Running it

What operational maturity looks like, briefly. An index build pipeline that produces a versioned artifact and can be swapped atomically with a rollback. A reindex runbook that includes the failure mode where a run dies halfway and leaves two half-populated shards invisible to the health check. Recall and latency SLOs measured at the system level, with the index-recall measurement kept separate. Freshness tracked as data age. Replica and shard balance reviewed on a schedule, since skew accumulates slowly and then appears as a latency incident. And a query-level trace, per part 49, that records which shards were queried, which candidates survived filtering, and which index version answered — because without that, every retrieval bug becomes an argument about whose component is at fault.

None of this is specific to AI. What makes it feel new is that the retrieval layer is now on the critical path of a system whose quality is judged by the fluency of its output, which means a silent recall regression presents as the model being stupid. The teams that debug that fastest are the ones that kept retrieval a database — with versions, SLOs, runbooks, and a system of record — instead of letting it become an opaque library call.

Build or buy, and the exit cost

The last operational question is whether to run any of this yourself, and the answer changed decisively between 2023 and 2026: managed vector services now handle partitioning, replication, filtering, and incremental updates well enough that self-hosting is rarely worth it below a large scale. What is worth reasoning about explicitly is the exit cost, because that is where the engineering decisions in this entry show up on a balance sheet.

Four properties determine how expensive it will be to leave. Whether your vectors can be exported along with the metadata that makes them interpretable. Whether the filter and query semantics you rely on are expressible in an open interface or specific to one product — this is the modern version of the classic concern about database portability, and the same lesson applies: query expressiveness is worth paying for, and vendor-specific query languages have a price measured in years. Whether the embedding model is pinned and documented, so that a migration can recompute vectors deterministically rather than guess. And whether your evaluation harness can score a candidate index from recorded queries — which, once again, is the piece that makes every other decision reversible.

The honest guidance is to buy the storage and the index, and own the pipeline that produces it: the embedding job, the chunking rules, the metadata schema, and the evaluation set. Those four things are small, mostly plumbing, and they are what makes the next migration a project rather than a rewrite.

Works Cited

Douze, Matthijs, et al. "The Faiss Library." arXiv, 2024, arxiv.org/abs/2401.08281. Accessed 5 Mar. 2026.

Guo, Ruiqi, et al. "Accelerating Large-Scale Inference with Anisotropic Vector Quantization." arXiv, 2020, arxiv.org/abs/1908.10396. Accessed 5 Mar. 2026.

Johnson, Jeff, Matthijs Douze, and Hervé Jégou. "Billion-Scale Similarity Search with GPUs." arXiv, 2017, arxiv.org/abs/1702.08734. Accessed 5 Mar. 2026.

Karger, David, et al. "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web." Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 654–663. Accessed 5 Mar. 2026.

Malkov, Yury A., and Dmitry A. Yashunin. "Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs." arXiv, 2016, arxiv.org/abs/1603.09320. Accessed 5 Mar. 2026.

Nishtala, Rajesh, et al. "Scaling Memcache at Facebook." Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation, 2013, pp. 385–398. Accessed 5 Mar. 2026.

Pan, James Jie, Jianguo Wang, and Guoliang Li. "Survey of Vector Database Management Systems." arXiv, 2023, arxiv.org/abs/2310.14021. Accessed 5 Mar. 2026.

Singh, Aditi, et al. "FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search." arXiv, 2021, arxiv.org/abs/2105.09613. Accessed 5 Mar. 2026.

Subramanya, Suhas Jayaram, et al. "DiskANN: Fast Accurate Billion-Point Nearest Neighbor Search on a Single Node." Advances in Neural Information Processing Systems, 2019. Accessed 5 Mar. 2026.