TL;DR
HyperPage is a novel system that optimizes the physical disk layout of large-scale vector indexes by learning from query logs. By replaying previous search workloads to co-locate frequently co-accessed records on the same SSD pages, it reduces disk I/O by up to 21% and cuts search latency by over 10% compared to state-of-the-art workload-agnostic methods.
What Problem Does This Paper Address?
Modern vector databases often handle billions of embeddings, far exceeding the capacity of main memory (DRAM). To manage this, systems like DiskANN store the full vector data and adjacency graphs on SSDs, keeping only compact "Product Quantization" (PQ) codes in DRAM to guide the search.
When a search agent traverses the graph, every "node expansion" requires reading a record from the SSD. These records are stored in fixed-size pages (e.g., 8 KB). If the records needed for a single search are scattered across many different pages, the system suffers from excessive disk I/O, which is the primary bottleneck for search speed.
Existing layout methods like MARGO or Starling try to group records based on the graph's structure (e.g., putting neighbors on the same page). However, they ignore the actual workload—the specific paths that real-world queries take. The challenge is that finding the absolute best layout is an NP-hard problem, and query patterns can change depending on the available memory budget.
Methods
The authors introduce HyperPage, a framework that turns index layout into a measurable optimization problem using workload logs.
Key components include:
- Workload Logging: It logs the "expanded sets" (the records touched) during a search run. Crucially, the authors observe that in DiskANN-style systems, the search path depends only on in-memory codes, not the disk layout. This means logs from one run remain valid for evaluating any hypothetical layout.
- Scope Hypergraph: It treats groups of co-accessed records as "hyperedges." The goal is to partition these records into disk pages to minimize the number of pages touched by these hyperedges.
- Refinement Algorithm: A greedy "swap-descent" algorithm that starts from an incumbent layout and iteratively moves or swaps records between pages to reduce total I/O.
- Cache-Aware Selection: It doesn't just optimize the disk; it optimizes for a specific DRAM budget. It decides how to split that budget between a static "hot record" cache and a dynamic LRU page cache by replaying validation steps.
- Lagrangian Audit: To understand how well they are doing, the authors developed a mathematical lower bound to estimate the theoretical minimum number of reads possible, providing a "map" of the remaining optimization gap.
Datasets
The researchers evaluated HyperPage using several large-scale workloads:
- W3 (Main): Derived from two public runs of the Search-R1 agent task, searching a corpus of 21 million passages.
- W1 & W2: Deep-research sessions from OpenResearcher and outcome-based agent trajectories.
- W4: Proxy groups from OLMo-3-7B trajectories.
- DEEP1M: A standard benchmark for billion-scale vector search.
Key Insights and Ideas
- Layout-Independent Replay: This is the "aha" moment. Because the search logic doesn't care how data is arranged on disk, you can "replay" a log against a thousand different layouts in seconds to find the best one without ever touching the actual SSD.
- The Power of Scopes: Instead of optimizing for individual queries, HyperPage optimizes for "rollout groups" (scopes). This captures the data reuse that happens when an agent issues multiple related queries in a single reasoning step.
- Memory Substitution: A better layout acts as a substitute for physical RAM. The authors found that at small cache sizes, HyperPage allows a system to achieve the same performance as a workload-agnostic layout using 3x less memory.
Key Results
HyperPage consistently outperformed all baselines, including the state-of-the-art MARGO.
- I/O Reduction: On the 1M record index, HyperPage read 16.4% to 21.2% fewer pages than MARGO. On the full 21M corpus, it saved up to 16.9% of reads.
- Latency Gains: In a real-world 12-thread engine, these I/O savings translated to a 10.4% reduction in search time per step.
- Efficiency: The advantage is most pronounced when the DRAM cache is small (e.g., 1% of the index), which is the most common scenario for massive datasets.
Limitations and Future Work
- Static Graphs: The current model assumes the graph structure is fixed. Future work is needed to handle dynamic indexes where nodes are frequently inserted or deleted.
- Training Time: While the refinement is efficient, it still requires a "finished run" to learn from. Adapting the layout in real-time as a workload shifts is a promising next step.
- Shared Cache Theory: While the paper provides strong bounds for "read-once" buffers, the theoretical optimum for shared LRU caches remains an open mathematical challenge.
Summary updated