HyperPage reuses one agent run's search logs to lay out disk-resident vector indexes, reading 5.2% to 21.2% fewer pages than MARGO at equal cache
Synopsis
The page layout of a disk-resident graph vector index decides how many SSD pages a search reads, yet layouts such as Starling and MARGO are computed from the graph and the vectors and use no query logs. HyperPage treats the expanded-node sets logged in one finished Search-R1 agent run as the workload, builds layouts for the uncached records under a declared memory budget, then replays validation steps to pick a layout and the split of the budget between hot records and a page cache. Across seven cache budgets on 1M and 21M passage indexes it reads 5.2% to 21.2% fewer pages than MARGO, with the largest gain when the cache is small.
Interpretation
A disk-resident graph vector index stores each vector with its adjacency list as one record, and a search must read the whole page holding every node it expands, so which records share a page changes page reads without changing the answers returned. Existing layouts such as Starling and MARGO compute co-location scores from the graph and the vectors and use no query logs, and MARGO's weights assume queries follow the distribution of the indexed vectors. On the 1M and 21M passage indexes across seven cache budgets from 1% to 25%, HyperPage reads 5.2% to 21.2% fewer pages than MARGO and no compared layout reads fewer; at a 1% budget MARGO needs 1.5 to 3.0 times the budget to read as few pages.
The approach turns the traversals left by one run into a page-read price that holds under every layout, then uses it to choose a layout for a declared budget. The key premise is that DiskANN-style search routes on in-memory product-quantization codes and on the adjacency lists of the records it expands, never on their page-mates, so the logged expanded sets stay valid under any layout and cached records add no page reads wherever they sit. Training uses steps 241 to 400 of one Search-R1 agent run and testing uses steps 71 to 200 of a later run with a different reward, 16,640 rollout groups whose prompts never occur in training; in a 12-thread patched DiskANN engine the median search time per step falls by up to 10.38% on the full corpus.
Perspective
The demonstrated setting is a fixed Vamana graph with 8 KB pages and 384-dimensional int8 records, workloads from Search-R1 agent retrieval over 1M and 21M passage indexes, and cache budgets of 1% to 25% of the index; the graph is fixed, so inserts and deletes stay outside the study.
Under a shared page LRU the window bound lies 11 to 48 times below HyperPage's reads, so the optimum of the primary metric remains open; under read-once scopes a Lagrangian bound places the 1M test optimum between 543.2 and 974.4 reads per group, and the bound is loose at small cache shares. Cache-blind layouts lose to MARGO once the cache serves most accesses, so the budget must enter refinement, and a cache-aware layout is tied to its own budget.