HyperPage: Learned Page Layouts for Disk-Resident Graph Vector Indexes

Xinyu Zhang, Jingze Li, Baihua Zheng, Weiwei SunarXiv 2026 · arXiv

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.

The HyperPage workflow: from logging finished runs to replaying and auditing new layouts.

Key components include:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.

Conceptual example showing how a learned layout reduces page reads from 4 to 3 for the same query.
  • 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

Abstract

Disk-resident graph indexes such as DiskANN store each vector with its graph edges as one record on SSD pages. A search needs the page of every record it expands, so its page reads depend on the page layout, that is, which records share a page. Search agents trained with reinforcement learning query one such index run after run, and every graph traversal can be logged with the records it expands. We therefore use the logs of a finished run to lay out the index for a declared memory budget, so later runs read fewer pages. In contrast, existing layouts such as Starling and MARGO are computed from the graph and vectors and use no logs. Learning a layout from logs is challenging, because the logs must stay valid under every layout, the saving depends on what the budget caches, and the best layout is NP-hard to find. Our key observation is that DiskANN-style search routes on in-memory codes and the records it expands, never on their page-mates. As a result, the logged traversals price every layout by replay, and cached records add no page reads. Accordingly, we propose HyperPage, which first builds layouts for the declared budget on the logged traversals of uncached records. It then selects one layout, together with the budget split between hot records and a page cache, by replaying validation steps. In addition, a Lagrangian lower bound shows how far a layout may be from the optimum. We learn from one Search-R1 agent run and test on a later run with a different reward, over 1M and 21M passages. Across seven cache budgets, HyperPage reads 5.2% to 21.2% fewer pages than MARGO, and no compared layout reads fewer. The advantage is largest when the cache is small. For example, at 1% of the 1M index, MARGO needs nearly 3 times the budget to read as few pages. On the 21M index, HyperPage also cuts search time per step by up to 10.4%. The saving holds for a second agent model and a second corpus.
BibTeX
@misc{zhang2026hyperpage,
  author = {Xinyu Zhang and Jingze Li and Baihua Zheng and Weiwei Sun},
  title = {{HyperPage: Learned Page Layouts for Disk-Resident Graph Vector Indexes}},
  year = {2026},
  eprint = {2611.16149},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.16149},
}
Figure