ConStore: Search-Overlapped Prefetch and Co-Retrieval-Aware Content Storage for Disk-Based ANNS

1 Introduction

• At large K, content-fetch latency can match or exceed vector-search latency, making it a first-class retrieval cost.Both phases grow approximately linearly with K in the measured large-K regime.Source: §1 · p. 1
• Up to 48% on DiskANN and 25% on SPANN: ConStore reduces end-to-end retrieval latency over the best per-document-read baseline across three multi-hop QA workloads.The techniques preserve retrieval results; separate experiments on 100M- and billion-vector indexes demonstrate SICP at larger scales.Source: §1 · p. 2
• SICP prefetches content for stable leading candidates under a bounded I/O budget, overlapping reads with search without changing the final top-K.Progressive SSD I/O exposes likely results before search finishes, but early candidates can change and late prefetches leave little time to hide I/O.Source: §1 · pp. 1–2
• RPAG groups frequently co-retrieved documents using query logs, addressing locality that insertion order and embedding-based clustering can miss.For example, a multihop query may retrieve a film page and its director’s biography from different semantic clusters.Source: §1 · p. 2

2.1 ANNS Retrieval Pipeline

• The retrieval pipeline first identifies top-K item IDs through vector search, then loads their payloads from storage for downstream processing.Both phases contribute to end-to-end retrieval latency.Source: §2.1 · p. 2

2.2 Disk-Based ANN Indexes

• DiskANN refines candidates through SSD graph-neighborhood reads, whereas SPANN progressively reads and scores SSD posting lists selected through an in-memory head index.These graph-based and clustering-based indexes refine results over successive SSD I/O rounds.Source: §2.2 · pp. 2–3

2.3 Motivations and Challenges

• Vector-search latency depends on index size N and result count K; in the measured large-K regime, both vector search and content fetch grow approximately linearly with K, making content fetch non-negligible.Figures 2 and 3 show this trend from small- to large-scale indexes.Source: §2.3 · p. 3, Figure 2 · p. 3, Figure 3 · p. 3
• Serial post-search fetch preserves the search-plus-fetch sequence, while uncontrolled parallel reads can compete with other queries for SSD bandwidth and queue capacity.The candidate queue can stabilize before search completes, creating an opportunity to overlap content reads with remaining search I/O.Source: §2.3 · p. 3
• Insertion- or key-ordered payloads scatter co-retrieved items, while embedding proximity is only a proxy for co-access locality.A film page and its director’s biography may be retrieved together despite belonging to different semantic clusters.Source: §2.3 · p. 4

3 ConStore Overview

• SICP overlaps bounded content prefetch with search while preserving the final top-K, and it works with any content layout that supports document-to-extent lookup.The two techniques are complementary and independently applicable.Source: §3 · p. 4
• RPAG groups frequently co-retrieved documents into CCS segments, and GCF coalesces requested content into page-aware reads.WASR selectively regroups segments under a bounded rewrite budget when recurring co-retrieval patterns change; this path requires no ANN-engine changes.Source: §3 · p. 4
• When combined, SICP issues GCF’s grouped reads during search and shares the same planner with post-search fetch.The query’s foreground search runs to completion; any missing payloads are fetched afterward through GCF.Source: §3 · p. 4

4 Speculative Inline Content Prefetch

• SICP checks read-only candidate snapshots and prefetches likely results under a bounded I/O budget, preserving final results through a residual fetch for misses.It works with insertion-order payloads as well as the layout described in Section 5.Source: §4 · p. 4

4.1 Overall Design

• A lightweight read-only callback reports search progress and candidate state to a background worker, which issues content reads without changing foreground search.DiskANN reports graph-search hops; SPANN reports SSD posting-list entries processed during refinement.Source: §4.1 · p. 4

4.2 Prefetching Strategy

• SICP checks progress and candidate stability before prefetching, then admits a bounded candidate pool and selects content under a per-prefetch I/O budget.Later prefetches avoid previously selected documents; residual fetch serves final top-K documents not already covered by completed or pending reads.Source: §4.2 · pp. 5–6

4.3 Per-Engine Instrumentation

• DiskANN publishes candidate snapshots at configurable graph-hop intervals, while SPANN publishes capped, sorted snapshots at configurable posting-count intervals.Both engines retain their existing foreground search logic and continue to completion.Source: §4.3 · p. 6

5 Co-Retrieval-Aware Content Layout and Group Fetch

• The layout path independently reduces per-fetch cost, and its CCS, RPAG, and GCF components also support SICP’s prefetch worker.The same layout and fetch path can be used for post-search fetch or combined with SICP.Source: §5 · p. 6

5.1 Co-Retrieval Content Segments (CCS)

• CCS stores bounded groups of documents contiguously, with an offset-and-length index that keeps content placement independent of the ANN backend.A constant-time doc_map resolves document IDs to segments and local indices, using 8 B per document in the reported workloads.Source: §5.1 · p. 6

5.2 Co-Retrieval-Pattern-Aware Grouping (RPAG)

• RPAG builds a rank-weighted co-retrieval graph and partitions it so high-weight document pairs stay within bounded CCS segments.Prefix weighting favors pairs co-retrieved near the head of wider result lists; cold or unseen documents instead receive embedding k-means placement.Source: §5.2 · pp. 6–7
• RPAG then orders documents within each segment so co-retrieved items lie near one another and can share page-aligned GCF windows.Its greedy ordering rewrites touched segments while preserving segment membership and recall.Source: §5.2 · p. 7

5.3 Workload-Adaptive Segment Reorganization (WASR)

• WASR detects recurring co-retrieval locality degradation and selectively regroups segments under rewrite and workload guardrails.It requires repeated evidence and a sufficient expected gain; a token bucket and foreground queue-depth and tail-latency guardrails bound rewriting.Source: §5.3 · pp. 7–8

5.4 Group Content Fetch (GCF)

• GCF groups requested documents by CCS segment, reads their index slab, and plans page-aware windows from their content extents.It greedily merges aligned windows subject to limits on window size, read amplification, and gaps, avoiding whole-segment reads.Source: §5.4 · p. 8
• GCF’s shared window plan serves both speculative and residual fetches, marking covered documents warm so residual fetch skips them.Grouped reads reduce content requests and device pages per top-K fetch; a miss falls back to a single-document window without changing ANN results.Source: §5.4 · p. 8

6.1 Setup

• The primary corpus contains 21M Wikipedia DPR passages; evaluation uses three multi-hop QA workloads and DiskANN and SPANN configured for recall@K≈0.90.Experiments use paired hop1+hop2 latency; scaling experiments use SIFT100M and SIFT1B with synthetic 1 KB payloads.Source: §6.1 · pp. 8–9

6.2 End-to-End Retrieval Latency

• 4–48% on DiskANN and up to 25% on SPANN: ConStore reduces end-to-end latency over the best per-document-read baseline, with the combined approach achieving the lowest geometric-mean latency at every evaluated K.Benefits generally grow with K; small-K SPANN cases show little benefit.Source: Figure 8 · p. 9, Figure 9 · p. 9, §6.2 · p. 10

6.3 Prefetch Precision and Coverage

• Figure 10 reports prefetch precision of 62.6–98.3% for DiskANN and 70.4–99.9% for SPANN; both cover over 99% of results at K=160.SICP’s prefetch quality is evaluated on the RPAG layout used by ConStore in Figures 8 and 9.Source: §6.3 · p. 10

6.4 Scalability

• 20% on DiskANN and 12.5% on SPANN: ConStore increases sustainable offered QPS over Post-Parallel-Fetch under a 100 ms total-P99 SLO and a 95% achieved/offered-QPS gate.At the baselines’ highest sustainable rates, P99 latency is lower by factors of 1.46× and 2.90×; at the same operating points, device read bandwidth falls by 23.4% on DiskANN and 19.7% on SPANN.Source: Figure 12 · p. 10, §6.4 · pp. 10–11, Figure 13 · p. 10

6.5 Scaling with Top-𝐾and Index Size

• 42% on SIFT100M and 40% on SIFT1B: DiskANN latency reductions reach these values at recall targets 0.90/0.95, while SPANN saves 30–43% at K=1600 across both scales.At SPANN’s 0.99 target, savings fall to 6–11% as search dominates; overlap does not change the final top-K.Source: §6.5 · p. 11

6.6 Content Fetch Speedup

• 45–47% over Random and 19–22% over K-Means: RPAG lowers fetch latency with page-aware fetch and local reordering, without prefetching.RPAG places about half of hop-2 results in segments touched by hop-1, versus roughly 15% for K-Means and 4% for Random; this is a layout-derived upper bound, not a measured cache-hit rate.Source: §6.6 · p. 11

6.7 Layout Staleness and Adaptation

• 2.5–12% of the corpus: across seven scenarios, WASR rewrites this amount versus 15–26% for periodic full rebuilds.After a workload shift, static RPAG loses locality; WASR selectively reorganizes segments, and it avoids rewriting on a unique-query replay without recurring evidence.Source: §6.7 · p. 11

Vector search and retrieval systems

• ANN systems optimize search I/O or scoring, while retrieval and RAG work motivates large or repeated evidence fetches without changing payload placement.The cited RAG and LLM serving systems optimize caching, scheduling, or model execution rather than the storage-side content path.Source: §7 · pp. 11–12

Evaluation figures

• The supplied figure captions identify comparisons of SICP latency, content-fetch latency, and WASR adaptation, but do not state their outcomes.The captions describe latency across top-K and recall targets, layout and fetch engine, and segments touched versus rewrite budget.Source: Figure 14 · p. 12, Figure 15 · p. 12, Figure 16 · p. 12

Storage for AI workloads and vector DB payloads

• AI-storage and vector-database systems target model loading, artifacts, caching, or general payload storage; the described systems do not use co-retrieval-aware layout or GCF-style batching.The passage identifies insertion order, key order, and segment format as existing payload-placement approaches.Source: §7 · p. 12

• ConStore treats content fetch as a first-class cost of disk-based ANNS retrieval.Source: §8 · p. 13
• SICP overlaps bounded content reads with search, while RPAG and GCF reduce fetch I/O through co-retrieval-aware layout.Source: §8 · p. 13
• Together, the complementary techniques preserve final top-K results and reduce end-to-end retrieval latency by up to 48% on DiskANN and 25% on SPANN over the best per-document-read baseline.Source: §8 · p. 13