Vector search engines find the stored items closest to a query by walking a graph, called a proximity graph, in which each item links to a few nearby items. Two separate bodies of work have improved these engines, and they do not talk to each other. One reorders the graph in memory so that nodes visited together sit on the same cache lines. On a frozen index this cuts query latency by up to 40% (Graph Reordering for Cache-Efficient Near Neighbor Search). The other keeps the graph searchable while items are continually inserted and deleted (The DiskANN library). Real systems face constant insertions and deletions. Under that churn, a carefully ordered memory layout decays back toward random pointer chasing, and nobody measures how fast this happens or what it costs.
This note proposes to measure that decay and to repair it cheaply. The repair piggybacks on work streaming indices already do: the periodic background sweep that removes deleted nodes. We also propose a way to score layout quality that does not depend on a particular machine. The score counts the distinct cache lines a query touches, replayed from the query's access trace. It sits between raw wall-clock time, which is noisy and specific to one machine, and logical counts such as "nodes visited," which are blind to memory layout.
Core Claim
We make three claims. First, on streaming benchmarks with realistic churn, the locality gained from offline reordering erodes measurably within a modest number of update cycles. Second, most of that loss can be recovered with two cheap changes. New nodes are placed into reserved empty slots next to their graph neighbors. Local, traffic-weighted re-placement is then folded into the existing sweep that consolidates deleted nodes. Third, the combination matches a periodic full reorder within a small latency gap, at a fraction of its cost and without the latency stalls a full reorder causes.
The first claim is also the thing most likely to fail. If decay turns out to be slow, periodically rerunning the offline reorderer is enough, and we will report exactly that.
Why this gap is real
Offline reordering methods all operate on static snapshots. These include Gorder, Corder, and profile-guided Porder on CPU (Graph Reordering for Cache-Efficient Near Neighbor Search), and Hub Sort, RCM and Gorder on GPU (On the Effectiveness of Graph Reordering for Accelerating Approximate Nearest Neighbor Search on GPU). The first paper names dynamic layout maintenance as future work. These papers motivate the proposal, and their reorderers supply the offline reference we compare against.
Streaming systems handle churn but not layout. FreshVamana keeps deleted nodes as "tombstones" that still carry search traffic, and prunes them in periodic sweeps (The DiskANN library). It optimizes for recall and for disk pages, not CPU cache lines. DQF keeps a small in-memory index of frequently queried items beside the full index and reports QPS without analyzing cache behavior (Frequency-Aware Graph Construction and Search for Dynamic Vector Databases). We reuse FreshVamana's consolidation sweep as the moment to act.
Dynamic graph coarsening supplies the template for incremental maintenance. There, DIGC freezes old assignments and places only new nodes, while ACNR lets nodes be reassigned under a bounded-drift guarantee (Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening). Our two changes mirror these two modes, applied to memory addresses instead of supernodes.
The layout objective, and why we do not convexify it
Let $Q$ be a sample of recent queries. For each query $q$, let $\mathrm{lines}_\pi(q)$ be the number of distinct cache lines of size $L$ that the search touches when node data is laid out according to address assignment $\pi$. The layout cost is
$$ J(\pi) = \frac{1}{|Q|}\sum_{q \in Q} \mathrm{lines}_\pi(q). $$
We also report a variant that counts misses under a simulated least-recently-used cache of capacity $C$. Minimizing $J$ is a discrete, arrangement-type problem with many local optima.
The convexity literature bears on this problem as a constraint rather than a tool. Invex methods such as DINGO assume a smooth objective whose stationary points are all global minima (DINGO). Nothing like that holds for a permutation. Solver-based convex layers also tend to be slow and fragile when problems degenerate (End-to-end Stochastic Optimization with Energy-based Model; Leveraging augmented-Lagrangian techniques for differentiating over infeasible quadratic programs), although that evidence comes from other problem classes. We therefore claim no global optimality. We use local search on $J$ and report the gap to a fresh offline reorder as our analogue of ACNR's drift bound. We include a convex-relaxation variant, spectral ordering, only as an ablation, to test the relaxation route directly.
Research Program
The work proceeds in three steps.
Build the measurement harness. The harness instruments a streaming index (FreshVamana-style insert, delete and consolidate) so that it logs node-access traces. From these traces it computes $J$, for several line sizes, alongside hop counts, distance computations, hardware L1/L3 miss counters, and wall-clock latency. The first scientific question is whether $J$ tracks wall-clock latency across at least two CPU generations and one GPU better than hop counts do. The file describes this tension without resolving it: ProS advocates hardware-independent counts (ProS), while traversals with identical hop counts differ by up to 40% in latency (Graph Reordering for Cache-Efficient Near Neighbor Search).
Characterize decay. Starting from a Gorder- or Porder-ordered index, we run churn cycles and track $J$ and latency per cycle. We separate three sources of loss: appended insertions, holes left by tombstones, and query traffic shifting toward regions that were not traffic-weighted when the layout was built.
Build the repair. It has two parts:
- Slack placement. Memory blocks keep a fill factor below one, in the spirit of database page slack. Each new node is written into the free slot closest to the block holding the majority of its out-neighbors.
- Consolidation-time re-placement. Whenever the sweep already rewrites a region to prune tombstones, it re-places that region's nodes by greedy swaps that reduce a traffic-weighted version of $J$. Traffic weights come from the same kind of hot-item counts DQF uses.
The data rewritten per sweep is therefore bounded by what consolidation writes anyway. For high-dimensional data, the reordering benefit fades as dimensionality grows (On the Effectiveness of Graph Reordering for Accelerating Approximate Nearest Neighbor Search on GPU), because each vector spans several cache lines. To address this, we test storing neighbor lists and compressed codes separately from full vectors, and applying the layout only to the compact part.
Baselines
Naive reference. The simplest reference is FreshVamana as described in The DiskANN library, with nodes stored in arrival order and tombstones consolidated in place. Its reported behavior is more than 95% recall maintained over 50 churn cycles. Every method must match that recall at equal search budgets. Speed gains that come from lost recall do not count.
Strongest competitor. The strongest competitor is the same streaming index plus a periodic full offline reorder with Gorder or Porder, run in the background at several periods. On static SIFT100M this family reports up to 40% lower mean latency, 20% lower P99, and L1 misses cut from about 19.5% to 14.5% (L3 from 6.5% to 4.0%) (Graph Reordering for Cache-Efficient Near Neighbor Search). No reported result was found on Lacuna for any reorderer under churn. It is the strongest competitor because it achieves the best known layout; its only costs are reorder time and the stall or double-buffering needed while the reorder runs. We charge the total CPU-seconds of every reorder against it and give our method the identical budget. Beating it means one of two outcomes. Either our method reaches mean latency within 5% of the best periodic schedule with at least a 5× smaller reorder budget, or it achieves strictly lower P99 latency at an equal budget.
GPU reference. On GPU, the reference is the reported gain of up to 15% in QPS from reordering on Deep1M with CAGRA (On the Effectiveness of Graph Reordering for Accelerating Approximate Nearest Neighbor Search on GPU). We compare against periodic RCM and Gorder on that engine.
DQF. DQF reports 2.0× to 5.7× QPS over HNSW and NSG at 95% recall (Frequency-Aware Graph Construction and Search for Dynamic Vector Databases). We run it both as a competitor and in combination with our method, because its hot index attacks skewed traffic by a different route.
Ablations. Four ablations isolate the ingredients: slack placement alone, consolidation-time re-placement alone, re-placement without traffic weighting, and incremental spectral (convex-relaxation) ordering in place of greedy swaps. Hyperparameters for all methods (fill factor, reorder period, swap budget) are tuned on a held-out churn trace with the same number of trials each.
Why not just…?
Why not just rebuild the layout periodically? This is the real threat. Gorder preprocessing takes minutes, not hours (Graph Reordering for Cache-Efficient Near Neighbor Search), so if locality decays slowly, a nightly reorder wins on simplicity. The decay study settles this directly. We will plot latency against cycles since the last reorder and ask whether any reorder period achieves our latency at our cost. If one does on all benchmarks, the contribution shrinks to the decay measurement and the metric, and we will say so.
Why not just sort nodes by degree, or append new nodes in order? Degree sorting was already found not to help consistently, because effective reordering must account for local connectivity (Graph Reordering for Cache-Efficient Near Neighbor Search). Append order is our naive baseline. Slack placement is itself the cheapest connectivity-aware heuristic, and the ablation shows whether it alone captures most of the gain. If it does, that is a welcome, simpler answer.
Why not just rely on the hot index? DQF's small hot index may fit in cache and hide the layout decay of the full index on skewed traffic. It does nothing for queries that fall outside the hot set, and it reported a recall compromise on GloVe (Frequency-Aware Graph Construction and Search for Dynamic Vector Databases). We will evaluate under both Zipf and uniform query traffic, and with DQF stacked on our method, to check whether the two gains add.
Why not just count hops? Hop counts cannot see layout, and identical traversals differ by up to 40% in latency depending on node order (Graph Reordering for Cache-Efficient Near Neighbor Search). The metric experiment tests whether $J$ closes this gap across machines.
Proposed Experiments
Datasets. Streaming churn runs use Wikipedia-Cohere-35M and OpenAI-ArXiv-2M from the DiskANN evaluation, together with SIFT100M and DEEP100M driven by synthetic insert/delete cycles. Dimensionality effects are tested on GIST1M (960 dimensions) and Deep1M/Yandex T2I on GPU. Queries follow both uniform and Zipf ($\beta = 1.2$) distributions, matching DQF's setup. Every run spans at least 50 churn cycles.
Metrics. We report recall@10, mean and P99 latency, QPS, hardware L1/L3 misses, the trace metric $J$, and the total CPU-seconds spent on layout maintenance.
Decisive checks. Four results decide the outcome:
- Metric validity. $J$ must rank methods consistently with wall-clock latency on two CPUs and one GPU, with Spearman correlation clearly above that of hop count. If it does not, we fall back to reporting hardware counters per platform.
- Decay. We ask whether latency after reordering degrades by more than half of its offline gain within 50 cycles on at least two streaming datasets. If it does not, periodic reorder is the right answer.
- Repair. Our method must stay within 5% of the best periodic-reorder latency while spending at most a fifth of its maintenance CPU time, with recall unchanged.
- Dimensionality. We test whether storing compact data separately from full vectors restores a reordering gain on GIST1M that plain reordering does not deliver there.
References
- Graph Reordering for Cache-Efficient Near Neighbor Search
- The DiskANN library: Graph-Based Indices for Fast, Fresh and Filtered Vector Search
- On the Effectiveness of Graph Reordering for Accelerating Approximate Nearest Neighbor Search on GPU
- Frequency-Aware Graph Construction and Search for Dynamic Vector Databases
- Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening
- DINGO: Distributed Newton-Type Method for Gradient-Norm Optimization
- End-to-end Stochastic Optimization with Energy-based Model
- Leveraging augmented-Lagrangian techniques for differentiating over infeasible quadratic programs in machine learning
- ProS: data series progressive k-NN similarity search and classification with probabilistic quality guarantees