Disk-Resident Graph Indexes and the Memory Bandwidth Wall

An in-memory graph index spends its query budget on pointer chasing and vector fetches, both of which are cache misses but both of which are served by DRAM at tens of gigabytes per second and a few hundred nanoseconds of latency. The traversal being relocated is the layered walk of HNSW Layer Assignment and the Greedy Descent. Once the collection outgrows memory, the same traversal becomes a sequence of random reads from a device that answers in tens of microseconds and delivers a few hundred megabytes per second when asked sequentially. The structure of the index has to change to match that asymmetry, and the changes are not merely engineering: they alter which parts of the algorithm are worth computing.

The arithmetic that forces a different design

A billion 768-dimensional float32 vectors occupy 3.07 terabytes. No single machine holds that in RAM, and the number is not the only obstacle: even a hundred million vectors need 307 gigabytes, beyond most servers once the graph’s edges and the operating system’s own footprint are counted.

Compression helps but does not close the gap. At 96 bytes per record from product quantization, a billion records occupy 96 gigabytes of codes, which fits in a large machine’s memory but leaves the exact vectors on disk for rescoring. The encoding that produces those bytes, and the table lookups that score them, are described in Product Quantization and the Asymmetric Distance Computation. The two-tier arrangement, with compressed codes in memory and full vectors on disk, is a legitimate architecture, and it is what the “codes in RAM, rerank from disk” pattern does. But it only works when the shortlist is small, because each rescore is a random read.

The alternative is to keep the graph and the vectors on solid-state storage and design the traversal around page granularity. That is the approach taken by disk-oriented graph indexes, and its central constraint is that a random read costs a page, not a byte.

A typical page is 4 kibibytes at the device level, and devices and file systems expose larger units of 8, 16, or 64 kibibytes, because the underlying flash translation layer reads in larger chunks. Reading a 32-byte vector identifier from a 4 KiB page wastes 99 percent of the transfer. Reading a 3072-byte vector from a 4 KiB page wastes a quarter. The ratio of useful bytes to transferred bytes is the figure that governs throughput, and it is entirely a matter of layout.

Page-oriented adjacency

The first structural change is to store each node’s adjacency list and its vector together, in one page-sized record. If a node has 32 links at four bytes each, its adjacency list is 128 bytes; adding a 3072-byte vector brings the record to 3200 bytes, which fits a 4 KiB page with room for the level information and a length field. A hop then reads one page and obtains both the neighbor identifiers and the vector needed to score them.

The second change is to align records to page boundaries, so that one logical read maps to one physical read. Without alignment, a record spanning two pages doubles the device operations per hop. With alignment, each hop costs exactly one read, and the cost of a traversal is the number of hops times the device’s random read latency.

At 32 links per node and a traversal visiting a few hundred nodes, the number of reads per query is in the hundreds. At a random read latency around 100 microseconds for a consumer solid-state device and perhaps 10 to 20 microseconds for an enterprise device with deep queues, a few hundred reads per query bounds throughput at tens to hundreds of queries per second per device before any queueing. That is the wall. It is not a compute limit and not a bandwidth limit; it is a limit on the number of independent random operations the device can sustain.

Raising the queue depth helps, because the device can overlap reads. The traversal is partially sequential in its dependencies, since a hop’s result determines the next node, but the candidate list provides parallelism: several frontier nodes can be expanded concurrently, and their reads can be issued together. Batching the reads of the current frontier turns a serial chain of dependent reads into a group of independent ones, which is why disk-oriented graph implementations maintain a frontier rather than a single current node.

What compression buys on disk

Product quantization changes the arithmetic of a page substantially. A 96-byte code plus a 128-byte adjacency list fits in a 256-byte record, so sixteen nodes share a 4 KiB page. A hop reads the same page and scores sixteen candidates instead of one, and the number of pages touched per query falls by roughly the same factor.

The cost is that the scores are approximate. The traversal must therefore be conservative: it explores using codes, collects a shortlist, and then fetches the full vectors of the shortlist from disk for exact rescoring. The shortlist fetch is again random reads, but there are only tens of them rather than hundreds, and they can be issued in parallel.

A middle path keeps full-precision vectors on disk but stores a compressed copy in memory for routing. The traversal runs entirely against the in-memory codes, which are small enough to fit, and only the final shortlist touches disk. This is the arrangement that makes a billion-record index servable from a single machine with a few hundred gigabytes of RAM and a terabyte of flash, and its performance depends on the ratio of code size to record size: 96 bytes against 3072 is a factor of 32, which is the difference between needing three terabytes of RAM and needing ninety-six gigabytes.

Caching and the shape of the working set

Query distribution is not uniform, and neither is the graph’s visitation distribution. A small set of nodes is visited by many traversals: the top-layer entry points, the hubs of dense clusters, and the nodes near the centroid of the collection’s distribution. These are the nodes worth caching, and caching them turns a large fraction of the hops into memory reads.

The working set is measurable and often surprisingly small. A graph’s top layers contain a tiny fraction of the nodes, so caching every node above the base layer costs little and removes the descent’s disk reads entirely. The base layer’s hot set is a function of the query distribution; a cache holding a few percent of the base layer, chosen by access frequency, can serve a large share of hops.

The interaction with the operating system’s page cache is the practical complication. If the index file is memory-mapped, the kernel caches pages transparently, and the effective cache size is whatever memory is not otherwise in use. That is convenient and unpredictable: the cache’s contents depend on the whole system’s behavior, and a competing workload can evict the index. An explicit application-level cache with a known replacement policy gives stable behavior at the cost of managing memory manually.

import os

PAGE = 4096
REC = 3200   # 128-byte adjacency + 3072-byte float32 vector + header

def read_record(fd: int, node: int) -> tuple[list[int], bytes]:
    """One positional read per node, aligned to page boundaries by construction.

    os.pread is POSIX; it reads at an absolute offset without moving a shared
    file position, which keeps concurrent readers from interleaving.
    """
    off = node * PAGE
    buf = os.pread(fd, REC, off)
    n = int.from_bytes(buf[0:2], "little")
    links = [int.from_bytes(buf[2 + 4 * i: 6 + 4 * i], "little") for i in range(n)]
    return links, buf[128:]

def expand_frontier(fd: int, frontier: list[int], limit: int = 16):
    """Issue up to `limit` reads before scoring any of them, so the device overlaps."""
    batch = frontier[:limit]
    return [read_record(fd, n) for n in batch]

The loop is deliberately naive about scoring; the point it illustrates is the batching. Issuing sixteen reads before consuming the first result lets the device’s queue absorb them, and the wall-clock cost approaches one read latency rather than sixteen.

Failure modes specific to the medium

Torn reads and partial writes are the first hazard. A record that spans a page boundary, or a write that is interrupted, leaves a node whose adjacency list references identifiers that were never written. The traversal follows the link, reads a page belonging to a different node, and scores a vector that does not correspond to the identifier. Checksums per record catch this at the cost of a few bytes and a few instructions per read; without them, corruption manifests as degraded recall rather than as an error.

Write amplification is the second. Updating a single node’s vector requires rewriting its whole page, and if the record is aligned, that is a 4 KiB write for a 3 KiB payload. Building an index by inserting nodes one at a time produces a random write per node, which is far slower than sequential construction. Bulk construction that writes the graph in node order, then patches the neighbor lists in a second pass, converts the random writes into sequential ones and is the standard approach.

The third is that the graph’s quality depends on construction having seen the whole collection, while a disk-resident build may process records in an order that produces poor links. The two-pass structure helps: the first pass assigns levels and builds an approximate graph in memory over a sample, and the second pass streams the full collection, connecting each record to its neighbors using the in-memory structure and writing the completed records sequentially. The sample’s quality determines the graph’s reachability, and a sample that misses a dense region leaves that region poorly connected.

A fourth is that deletes and updates have no cheap representation. A tombstone is a page read that returns nothing useful, and the traversal still pays for it. Compaction requires rewriting pages, which reintroduces random writes. The maintenance problem is treated in Tombstones, Merges, and the Cost of Keeping a Vector Index Current, and its cost is higher on disk than in memory by exactly the ratio of the write costs.

What the wall implies for index choice

The memory bandwidth wall reframes the index selection question. In memory, the question is how many distance computations a query can avoid; on disk, the question is how many random reads it can avoid. A structure that saves computations but scatters reads is worse than one that performs more arithmetic on data already in hand.

This is why the disk-resident designs converge on a small number of large sequential reads, aggressive compression for routing, and a two-phase exact rescore. It is also why the same designs are poor choices for collections that fit in memory: the page alignment wastes memory, the compression loses accuracy that an in-memory index would not need to trade, and the two-phase structure adds a disk round trip that an in-memory index performs as a cache hit.

The threshold between the two regimes is not the collection size against the RAM size, but the collection size against the RAM available after the rest of the system takes its share, and against the query rate the deployment must sustain. A collection that fits in memory but is queried at a rate where the memory subsystem saturates is a candidate for compression even without disk involvement, which is the same trade in a different medium. What stays constant is the quantity being conserved: bytes moved per query, whether from DRAM or from flash.