ConStore: Search-Overlapped Prefetch and Co-Retrieval-Aware Content Storage for Disk-Based ANNS: what it means for business leaders

ConStore cuts the time a disk-based vector search spends loading the documents it found, by prefetching likely results during the search and laying out the content store by what gets retrieved together.

1. What the method is

ConStore is a content storage engine that sits beside a disk-based approximate nearest-neighbor index such as DiskANN or SPANN. Retrieval has two storage phases: the vector search finds the IDs of the top results, and a content fetch then loads the passages, item records or features those IDs point to. ConStore attacks the second phase with two independent techniques. Speculative Inline Content Prefetch (SICP) watches the search's candidate queue as it refines and starts reading content for candidates that have stopped moving, under a bounded I/O budget, while the search is still running. Co-Retrieval-Pattern-Aware Grouping (RPAG) uses query logs to place documents that are usually retrieved together into contiguous segments, Group Content Fetch (GCF) coalesces reads within those segments into page-aligned windows, and Workload-Adaptive Segment Reorganization (WASR) regroups segments when the workload drifts. Neither technique changes the search results.

2. Why the method was developed

Most vector-search research measures top-10 results, where loading content is a small afterthought. Production search, recommendation and advertising systems ask for hundreds to thousands of candidates to feed re-ranking models, and retrieval-augmented generation can pull many passages per question. The authors profiled million- to billion-vector indexes and found that at these sizes the content fetch grows roughly linearly with the result count and can take as long as the search itself, or longer. Existing systems serialize the two phases, waiting for the final IDs before issuing any content read, and store payloads in insertion or key order, so documents that are usually requested together are scattered across the disk and each costs a separate random read. Parallelizing the fetch after search helps a single query but, under load, competes with other queries' search reads for SSD bandwidth. Grouping by embedding similarity is only a proxy, since a multi-hop question can need a film page and a director's biography from different clusters.

3. Who should care

This touches any team running retrieval over a corpus too large for memory. Platform and infrastructure engineers who operate vector databases, especially those serving large candidate sets to re-rankers or language models, are the direct audience, since the paper argues their latency budget is being spent in a phase they probably do not measure. Teams building retrieval-augmented products should care because multi-hop and agentic retrieval repeat fetches and benefit most from co-retrieval layout. Those who buy rather than build should note that the production vector databases the authors cite, including Milvus, Qdrant and Weaviate, store payloads by insertion order and do none of this, so it is a question to raise with vendors. Finance and capacity planners should notice that the gains come with lower device bandwidth, which translates into sustaining more queries per server before adding hardware.

4. How the method works

Both DiskANN and SPANN refine a candidate queue over repeated SSD reads, one by graph hops and one by posting lists. ConStore adds a read-only callback to each search loop that publishes a snapshot of the queue and a progress counter. A background worker compares successive snapshots by set overlap and, once the head has stayed stable for a configured number of checks and the search has progressed far enough, admits a bounded set of new candidates, excluding ones already scheduled, and reads their content through the page-aware planner. Later prefetches use small budgets and require a minimum number of newly promoted documents. When the search finishes, a residual fetch loads whatever final results were not covered. On the layout side, RPAG builds a graph whose edges weight how often two documents co-occur in result lists, weighting pairs in the top few ranks more, partitions it with METIS into bounded segments, falls back to embedding k-means for unseen documents, and orders documents within a segment so co-retrieved ones share pages. A packed 8-byte-per-document map resolves any ID to its segment. WASR monitors confirmed recurring pairs, and rewrites selected segments only when the cut across segments rises enough and a byte budget allows, publishing immutable layout generations so queries never mix versions.

5. How it was evaluated

The experiments ran on a two-socket Xeon server with 251 GiB of DRAM and a 1.6 TB NVMe SSD. The main corpus is the 21-million-passage Wikipedia DPR set, with roughly 1 KB passages and 768-dimensional embeddings, queried with three multi-hop QA sets: 2WikiMultihopQA, HotpotQA and MuSiQue, each question measured as two retrieval hops at top-K from 10 to 1600. Both engines were tuned to about 0.9 recall per setting. Baselines were a random insertion-order file with per-document reads, which mirrors production practice, the same segment format organized by embedding k-means, and RPAG segments with grouped fetch but no prefetch. A prefetch-only variant over the random layout isolates the overlap effect. Scaling experiments used SIFT100M and SIFT1B with synthetic 1 KB payloads and prefetch alone. Further runs measured concurrency up to 32 queries, offered load under a 100 ms P99 service objective, prefetch precision, and a replay of 500-query epochs with a workload shift to test reorganization.

6. How it performed

Against the best per-document-read baseline, the combined system cut end-to-end latency by 4% to 48% on DiskANN and up to 25% on SPANN, with gains growing as the result count grew and little benefit at small top-K on SPANN. Layout alone beat k-means segments by up to 18% on DiskANN and 9% on SPANN, with a few SPANN settings regressing by 2%. Prefetch precision ran from 63% to 98% on DiskANN and 70% to nearly 100% on SPANN, covering over 99% of final results. Under a 100 ms P99 objective, sustainable throughput rose by 20% on DiskANN and 12.5% on SPANN while device read bandwidth fell by 23% and 20%. On billion-vector SIFT, prefetch alone saved about 40% at moderate recall but only 6% to 11% when search dominated. The reorganizer rewrote 2.5% to 12% of the corpus against 15% to 26% for periodic full rebuilds. The authors note the layout gains depend on recurring co-retrieval, fade beyond the trained prefix sizes, and that faster search engines shrink the overlap window. Our call: pilot, on whichever of our retrieval paths serves large candidate sets from disk, starting with the prefetch half since it needs no layout migration. (Source: arXiv 2610.21676, 2026)