A search index rewires links to match query demand
REWEAVE: Online Learning for Workload-Adaptive HNSW Indexes · arXiv:2611.16060
In plain words
A vector-search index uses links between stored items to find similar ones quickly. Those links are usually built from the data, even though people’s searches may focus on only part of it or shift over time.
REWEAVE learns from searches which links help, then replaces less useful links while keeping each item’s link limit.
In tests with concentrated or changing query workloads, it improved average search recall over an unchanged index; the tests used constructed workloads, including a simulated sequence of shopping-query categories.
The research
A vector-search index can spend its limited links on routes that searches rarely use, especially when searches concentrate in one area or shift over time.
The result changes the expectation that a graph built from the stored data must stay fixed: query feedback can help it adapt while preserving each node’s link budget.
REWEAVE learns from query feedback and rewires HNSW’s bottom-layer links within each node’s existing link limit to better match the search workload.
For each arriving query, REWEAVE searches the current graph and serves its answer before using feedback to score links and propose alternatives. At intervals, it replaces links while preserving each node’s link limit.
On constructed stationary workloads, the best configuration improved held-out recall over frozen HNSW. A separate constructed drift stream also favored adaptation, though those results do not cover production query traces.
The recall improvements come from constructed stationary workloads and a constructed shopping-query drift stream. The theoretical guarantees also depend on assumptions about stable reward means, clear gaps between choices, retained observations, and access to useful candidate edges.
Repeated evaluation is a separate coverage condition; a finite graph and decaying exploration alone do not ensure it.
What the evidence shows
- A graph can miss query demand
REWEAVE (Reward-Guided Rewiring of Vector Graphs) is an online maintenance method for HNSW vector indexes. It learns from query feedback which links help search, then periodically replaces links while preserving each node’s outgoing-link limit.
The method addresses a mismatch: the corpus determines the original graph, while the query workload determines which routes are useful.
- Learned scores help rank candidates
Both ranking methods used the same candidate pool and other settings, so the comparison tests whether learned scores help order those candidates. With self-labels after 1,000 training queries, learned ranking reached mean held-out Recall@100 of 0.877, versus 0.805 for random ranking; test recall was measured against exact neighbors.
This supports learned ranking within that pool, though the starting graph initialization is unspecified.
- The full design raises recall
The best combined configuration used UCB(64) navigation, recall rewards and both candidate buffers. On constructed stationary skew workloads, it improved mean held-out Recall@100 over frozen HNSW by 16.3 percentage points on GIST-1M and 23.3 points on T2I-10M; the gains shrank as queries spread out.
- Design choices interact
The joint design tests led the authors to identify navigation as the dominant factor in the tested configurations. Other choices depended on it: missed-neighbor proposals added less when wider-beam navigation already examined more true neighbors, while recall rewards helped more with UCB(64). This makes the result a claim about how these components worked together in the tested settings.
- Other tests probe distinct settings
Separate comparisons extended the evidence to query-aware graph repair and workload drift, using different workloads and measures. On GIST-1M, REWEAVE had a higher single-thread query rate than NGFix at a specified recall point.
On a constructed shopping-query stream, it also improved mean recall over frozen HNSW. These tests suggest the approach can help in more than one setting, but do not make the settings interchangeable.
Deep
- Original paper authors
- Minghao Li, Nick Koudas, Raghav Mittal
- Submitted to arXiv
- License
- arXiv non-exclusive