HyperPage: Learned Page Layouts for Disk-Resident Graph Vector Indexes
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "HyperPage: Learned Page Layouts for Disk-Resident Graph Vector Indexes".
Jane: Here's the gist of the paper. 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, on 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 that later runs read fewer pages Our key observation is that DiskANN-style search routes on in-memory codes and on the records it expands, never on their page-mates Accordingly, we propose HyperPage, which first builds layouts for the declared budget on the logged traversals of the uncached records It then selects one layout, together with the split of the budget between hot records and a page cache, by replaying validation steps 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 Pruning redundant reasoning tokens The paper introduces HyperPage, a method that learns optimal page layouts for disk-resident graph vector indexes by leveraging logs of finished search runs This approach addresses the challenge of physical design decisions in vector databases, where page layout dictates page reads Existing layouts like Starling and MARGO are computed from the graph and vectors without logs, which is a limitation HyperPage learns a layout from logs by replaying validation steps to select the best configuration for a declared memory budget How the training signal is built The training process involves several components that build the learned layout (3) Logging (2) Scope hypergraph (3) Refinement (4) Selection for D (5) Replay (6) Logging records the expanded set in expansion order and the group that issued it, which is valid under every layout The optimizer receives the unions Eσ of the training scopes, merged with multiplicity The objective is to minimize Fconn(π) which is defined as X EωEλπ(E) − 1 Where the gains come from The performance gains stem from the fact that DiskANN-style search routes on in-memory codes and on the records it expands, never on their page-mates The key observation is that logged traversals price every layout exactly under read-once buffers, and under a shared cache in the logged order The objective Fconn minimizes the reads of a read-once workload, and Corollary 2 shows an exact optimizer at B = 2 The refinement step uses Algorithm 1, which applies the best move or swap by exact gain under the hard capacity Optimization Audit The optimization audit confirms that the learned layouts read at most 2.05 to 2.20 times the optimum under read-once group scopes, against 2.59 times for MARGO The bound leaves the true gap open, as a Lagrangian bound shows how far a layout may be from the optimum The saving persists as the index grows (Fig.
Tom: 4, with uniform 5M and 10M samples of the corpus and the same queries) The logs of one finished agent run price every page layout of a fixed disk-resident graph index, and cached records add no page reads HYPERPAGE builds layouts on the uncached part of the logged traversals and selects one by replay Once the cache serves most accesses, the budget must enter refinement A Lagrangian bound brackets the remaining gap to the optimum The index updates, larger corpora and the optimum under a shared cache remain open Page 5 --- A page holds B records, and holds B = 3 records With a read-once buffer, a later group that expands a to f reads 4 pages under the incumbent layout and 3 under the learned one Search agents in training issue such queries at scale Page 7 --- Corollary 2 gives an exact optimizer at B = 2, against which we calibrate the lower bound of this section The clique expansion of a layout in Π2 form a matching of weight Fwclq (π), and any matching extends to a layout by pairing unmatched nodes, which cannot decrease the nonnegative weight Page 8 --- Corollary 3 (Reads under a record cache).
Jane: Let A1 to A4 hold for a scope σ, and let a fixed set C of records be served from memory Then Sσ reads exactly λπ(Eσ − C) pages for every π ∈ ΠB and every arrival order Page 9 --- Proposition 7 (A lower bound valid for every layout).
Tom: Partition the records into classes C1,..., Cr and write c(u) for the class of u Then for real γvE, one per record v and set E ∋ v, and for µ ∈ R r ≥0, let wγvu = P E∋u,v ωEγvE Then for every π ∈ ΠB the reads Fconn(π) + P EωE satisfy X EωEλπ(E) ≥ X v hX E∋v ωEψE(γvE) − max T ⊆V - T≤β X u∈T wγvu − µc(u) Page 10 --- Proposition 2 (Size and capacity bound).
Paper summary: Tom: So, this paper introduces something called HyperPage, which is trying to figure out the best way to organize disk-resident graph vector indexes. The basic idea here is that each vector and its connections are stored on SSD pages. When you search, you have to read the page for every record you expand in your search. So how those records are laid out on the page matters a lot for how many times you have to read the disk.
Jane: Exactly. And what they’re tackling is that existing ways of figuring out this layout, like Starling and MARGO, just calculate it based on the graph and the vectors without looking at any search logs. HyperPage learns a layout from those logs by replaying validation steps to find the best configuration for a fixed memory budget.
Lu: It’s challenging because those logs have to be valid under every possible layout, and finding the absolute best layout is NP-hard once a page holds three or more records <ref:2611.16149#pg2>. HyperPage tries to solve that by using the logs of finished search runs to build layouts for a declared memory budget.
Meng: What I wonder is how much of this actually matters in practice. If we have a fixed budget, does learning the layout from logs give us a real win over just picking one layout beforehand?
Tom: The main claim they make is that DiskANN-style search routes on in-memory codes and on the records it expands, never on their page-mates <ref:2611.16149#pg2>. This means the key observation is that the search doesn't care about what's next to it on the page.
Jane: That’s a big thing because if it only cares about in-memory codes and expanded records, then those things price every layout exactly under read-once buffers and under a shared cache in the logged order <ref:2611.16149#pg2>. Plus, records held in a memory cache add no extra page reads, no matter where they sit <ref:2611.16149#pg2>.
Lalam: I’ve looked over it; the objective they minimize is Fconn of pi, which is defined as X EomegaElambda pi(E) minus one <ref:2611.16149#pg3>. It seems like they are trying to minimize reads for a read-once workload, and Corollary two shows an exact optimizer at B equal to two <ref:2611.16149#pg7>.
Tom: So the method involves logging the expanded set in expansion order and which group issued it, which is valid under every layout <ref:2611.16149#pg3>. Then the optimizer receives unions of these training scopes merged with multiplicity to minimize that objective function <ref:2611.16149#pg3>.
Lu: The refinement step uses Algorithm one, which applies the best move or swap by exact gain under the hard capacity <ref:2611.16149#pg2>. It seems they are using those logged traversals to price every layout exactly under read-once buffers <ref:2611.16149#pg7>.
Meng: If you look at the optimization audit, it confirms that the learned layouts read at most two point zero five to two point two times the optimum under read-once group scopes, against twenty point five nine times for MARGO <ref:2611.16149#pg4>. That gap still leaves room for improvement, which is good because a Lagrangian bound shows how far a layout may be from the optimum <ref:2611.16149#pg3>.
Jane: That sounds like they found something that's close to optimal, even if it’s not perfectly perfect yet. So, this HyperPage method seems to be using historical search data—the logs—to create a layout that performs better than what you could guess or calculate without those logs. This sets up the next part of how we get there.
Conclusion: Tom: So, to wrap up this discussion on HyperPage, we have Zhang, Li, Zheng, and Sun from Fudan University and Singapore Management University working on this paper <ref:2611.16149#pg1>. They’ve developed a method that learns optimal page layouts for disk-resident graph vector indexes using logs from search runs.
Jane: What this means in plain terms is that instead of calculating a layout based only on the static graph structure, HyperPage uses real search data to figure out how to arrange the records on those SSD pages so that when you run your AI queries, you read as few pages as possible given a memory budget.
Lu: The core idea is that they price every possible page layout exactly under two key conditions: under read-once buffers and under a shared cache in the logged order <ref:2611.16149#pg2>. This suggests that the actual search path, which uses in-memory codes and expanded records, is what really matters for performance.
Meng: If we think about deployment costs, this suggests a way to tailor the physical storage layout of our vector index to the specific workload we expect, instead of using a one-size-fits-all approach <ref:2611.16149#pg3>. It moves us from pre-calculated layouts to learned ones.
Tom: And it does show that records held in a memory cache don't add any page reads, which is another practical win for performance tuning on disk storage <ref:2611.16149#pg2>.
Jane: It’s an interesting piece of work because it shows how we can use past operational data from search agents to design the physical structure of a database index for future efficiency <ref:2611.16149#pg3>. It’s a concrete way to bridge the gap between theoretical layout optimization and real-world indexing challenges.
Fudan University · Singapore Management University
cs.DB, cs.IR
Submitted: 2026-11-12
Updated: 2026-11-12
Comments: 14 pages, 4 figures, 7 tables. Code available at: https://github.com/zhangshea/HyperPage
Code: https://github.com/CodenameYZY/MARGO
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 91/100
The gist: 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…
Key concepts
- DiskANN-style search
- This refers to how data is searched in disk-resident indexes where each vector and its graph edges are stored on SSD pages. Searching requires reading the page containing every record that needs to be expanded, making page layout critical for performance.
- Scope hypergraph
- This structure represents the training workload. It maps records (nodes) to search scopes (queries) and tracks which sets of records are expanded together in a single traversal. The optimizer uses this graph structure to understand how different queries interact.
- Read-once scope buffer
- This assumption states that once a page is fetched during a specific search scope, it serves all subsequent requests for that page within the same scope until the scope ends. This allows the system to reuse data efficiently within a single traversal.
- Fconn(π)
- This objective function measures the total number of reads required for a specific search plan (π). The goal of HyperPage's optimization is to minimize this value by choosing the best page layout configuration.
Terminology
Summary
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, on 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 that later runs read fewer pages Our key observation is that DiskANN-style search routes on in-memory codes and on the records it expands, never on their page-mates Accordingly, we propose HyperPage, which first builds layouts for the declared budget on the logged traversals of the uncached records It then selects one layout, together with the split of the budget between hot records and a page cache, by replaying validation steps Across seven cache budgets, HyperPage reads 5. p. 02% to 21.2% fewer pages than MARGO, and no compared layout reads fewer The advantage is largest when the cache is small
Pruning redundant reasoning tokens
The paper introduces HyperPage, a method that learns optimal page layouts for disk-resident graph vector indexes by leveraging logs of finished search runs This approach addresses the challenge of physical design decisions in vector databases, where page layout dictates page reads Existing layouts like Starling and MARGO are computed from the graph and vectors without logs, which is a limitation HyperPage learns a layout from logs by replaying validation steps to select the best configuration for a declared memory budget
How the training signal is built
The training process involves several components that build the learned layout
(3) Logging (2) Scope hypergraph (3) Refinement (4) Selection for D (5) Replay (6)
Logging records the expanded set in expansion order and the group that issued it, which is valid under every layout The optimizer receives the unions Eσ of the training scopes, merged with multiplicity The objective is to minimize Fconn(π) which is defined as X EωEλπ(E) − 1
Where the gains come from
The performance gains stem from the fact that DiskANN-style search routes on in-memory codes and on the records it expands, never on their page-mates The key observation is that logged traversals price every layout exactly under read-once buffers, and under a shared cache in the logged order The objective Fconn minimizes the reads of a read-once workload, and Corollary 2 shows an exact optimizer at B = 2 The refinement step uses Algorithm 1, which applies the best move or swap by exact gain under the hard capacity
Optimization Audit
The optimization audit confirms that the learned layouts read at most 2.05 to 2.20 times the optimum under read-once group scopes, against 2. p. 559 times for MARGO The bound leaves the true gap open, as a Lagrangian bound shows how far a layout may be from the optimum The saving persists as the index grows (Fig. p. 0 4, with uniform 5M and 10M samples of the corpus and the same queries)
Conclusion
The logs of one finished agent run price every page layout of a fixed disk-resident graph index, and cached records add no page reads HYPERPAGE builds layouts on the uncached part of the logged traversals and selects one by replay Once the cache serves most accesses, the budget must enter refinement A Lagrangian bound brackets the remaining gap to the optimum The index updates, larger corpora and the optimum under a shared cache remain open
--- Page 5 ---
A page holds B records, and holds B = 3 records With a read-once buffer, a later group that expands a to f reads 4 pages under the incumbent layout and 3 under the learned one Search agents in training issue such queries at scale
--- Page 7 ---
Corollary 2 gives an exact optimizer at B = 2, against which we calibrate the lower bound of this section The clique expansion of a layout in Π2 form a matching of weight Fwclq (π), and any matching extends to a layout by pairing unmatched nodes, which cannot decrease the nonnegative weight
--- Page 8 ---
Corollary 3 (Reads under a record cache). Let A1 to A4 hold for a scope σ, and let a fixed set C of records be served from memory Then Sσ reads exactly λπ(Eσ − C) pages for every π ∈ ΠB and every arrival order
--- Page 9 ---
Proposition 7 (A lower bound valid for every layout). Partition the records into classes C1,. p. 5.., Cr and write c(u) for the class of u Then for real γvE, one per record v and set E ∋ v, and for µ ∈ R r ≥0, let wγvu = P E∋u,v ωEγvE Then for every π ∈ ΠB the reads Fconn(π) + P EωE satisfy X EωEλπ(E) ≥ X v hX E∋v ωEψE(γvE) − max T ⊆V - T≤β X u∈T wγvu − µc(u)
--- Page 10 ---
Proposition 2 (Size and capacity bound). Let ¯b = maxE min(E, B) over the sets with ωE > 0 For every π ∈ ΠB, g(π) ≤ Fwclq (π) ≤ ¯b2 g(π)
--- Page 3 ---
Definition 8 (Scope hypergraph and objective). A training workload is a set Σtr of scopes The scope hypergraph is H = (V, E, ω) with E = Eσ: S q∈σ. p. 2 Identical unions are merged, and ωE > 0 is the normalized multiplicity of E
--- Page 4 ---
Definition 3 (Logged runs, requests, groups). A logged run has numbered steps In a step, each prompt is rolled out ν times A group b is the set of sub-queries of one (step, prompt) over its ν rollouts
--- Page 8 ---
Assumption 3 (A3: cold start). The buffer is empty when its sub-query or scope starts
--- Page 5 ---
Assumption 4 (A4: read-once scope buffer). Within a scope, a page that has been fetched, or is in flight, serves every later request for that page by any sub-query of the scope until the scope ends
--- Page 7 ---
Assumption 1 (A1: layout-independent walk). For every subquery q, every round e(t) q is a function of (q, G, L, W) and the PQ codes alone A1 holds when routing uses only the in-memory codes and the adjacency lists in the records of expanded nodes
--- Page 8 ---
Assumption 2 (A2: reads of expanded nodes only). The engine reads whole pages, only pages in π(eq), and holds page π(v) when it expands v ∈ e(t) q
--- Page 8 ---
Assumption 4 (A4: read-once scope buffer). Within a scope, a page that has been fetched, or is in flight, serves every later request for that page by any sub-query of the scope until the scope ends
--- Page 8 ---
Assumption 4 (A4: read-once scope buffer).
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved layout selection by using a replay model that
prices every layout from one run’s logs.
This allows systems toselect one layout, together with the split of the budget between hot records and a page cache, by replaying validation steps
to achieve5.2% to 21.2% fewer pages than MARGO
across various budgets. -
Cache-aware refinement and selection for a declared budget allows systems to build layouts on
the unions of the uncached records and selects the layout and cache split by replay on validation steps.
This specifically enables performance gains when thecache is small,
as seen in savings of 19.8% at 1M under specific conditions. -
A per-incidence Lagrangian bound provides a mechanism to
bound the reads of every layout from below,
allowing researchers to determine how far a layout may be from the optimum, which is critical for understanding the limitations of existing layouts like Starling and MARGO.
Sources
- DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models
- Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning
- Bandana: Using Non-volatile Memory for Storing Deep Learning Models
- OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries
- DiskANN++: Efficient Page-based Search over Isomorphic Mapped Graph Index using Query-sensitivity Entry Vertex
- Scalable Disk-Based Approximate Nearest Neighbor Search with Page-Aligned Graph
- Optimizing SSD-Resident Graph Indexing for High-Throughput Vector Search
- DGAI: Decoupled On-Disk Graph-Based ANN Index for Efficient Updates and Queries
- GoVector: An I/O-Efficient Caching Strategy for High-Dimensional Vector Nearest Neighbor Search
- LSM-Vec: A Memory-Efficient Disk-Based System for Large-Scale Dynamic Vector Search
- CoWalk: Cooperative Walks for Agentic Batch Queries on Disk-Resident Graphs
- DeepResearchGym: A Free, Transparent, and Reproducible Evaluation Sandbox for Deep Research
- InfoAgent: Advancing Autonomous Information-Seeking Agents
- Semantics Delivery Network: Rethinking Web Retrieval Infrastructure for LLM Agents
- Catapults to the Rescue: Accelerating Vector Search by Exploiting Query Locality
- WaRP: Workload-Aware Request Planning for Vector Retrieval on Object Storage
- Cross-Modal Data Co-Locality for Heterogeneous Storage Systems
- OpenResearcher: A Fully Open Pipeline for Long-Horizon Deep Research Trajectory Synthesis
Related papers
- Beyond Overlap: Hierarchical Graph Abstraction for Out-of-Core Vector Search
- EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates
- Open Biomedical Knowledge Graphs at Scale: Construction, Federation, and AI Agent Access with Samyama Graph Database
- Samyama: A Unified Graph-Vector Database with In-Database Optimization, Agentic Enrichment, and Hardware Acceleration
- GenTUS: Table Union Search via Constrained Generation of Semantic Table Identifiers
- Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs