REWEAVE lets vector indexes learn from queries to boost ANN recall

Vector‑search engines power everything from recommendation systems to retrieval‑augmented generation, and most of them rely on Hierarchical Navigable Small World (HNSW) graphs for approximate nearest‑neighbor (ANN) lookup. The new REWEAVE algorithm, presented in a pre‑print on arXiv on 13 Nov 2026, shows how an HNSW index can be continuously reshaped by the very queries it serves, closing a long‑standing gap between static graph construction and dynamic query workloads.\n\n## What is REWEAVE and why does it matter?\nAccording to the authors – Minghao Li, Nick Koudas and Raghav Mittal – REWEAVE (Reward‑Guided Rewiring of Vector Graphs) is an online index‑maintenance framework that learns the utility of each outgoing edge from query feedback and periodically rewires the bottom layer of the HNSW graph while respecting the original per‑node degree cap. In practice this means the same amount of memory and cache traffic is used, but the graph’s topology better reflects the actual distribution of queries, which can be highly skewed or shift over time. The paper argues that static graphs built solely from the corpus often waste degree budget on edges that are rarely traversed, leading to lower recall or higher search cost.\n\n## How does REWEAVE adapt HNSW indexes?\nThe method treats navigation through the graph as an online learning problem. Each outgoing edge $(u, v)$ is considered an arm in a multi‑armed bandit setting, and the learner receives a reward that measures how helpful that move was for the current query. The paper describes a five‑step loop (Figure 2 in the source):\n1. Navigation – the query follows a greedy or UCB‑guided walk, optionally using an $\epsilon$‑greedy strategy.\n2. Reward assignment – after the answer is returned, a binary endpoint reward (exact match or not) and a recall‑based reward are computed.\n3. Value estimation – running means with time‑indexed discounting update an edge‑value estimate.\n4. Candidate generation – a neighbor buffer and a missed‑neighbor buffer collect potential replacement edges.\n5. Budget‑preserving rewiring – at scheduled intervals the bottom‑layer out‑edges of each node are rewired to the highest‑valued candidates, never exceeding the original out‑degree $M$ (where $M = 2 M_{\rm HNSW}$ in standard HNSW).\nThe algorithm supports two feedback regimes: sparse exact‑neighbor feedback (where the true top‑$k$ set is occasionally provided) and self‑labeling, where the system reuses its own answer as a noisy label. This mixed feedback drastically reduces the labeling cost while still allowing the graph to converge toward the optimal edge set.\n\n## What performance gains does REWEAVE show?\nThe authors evaluated REWEAVE on several benchmarks up to 100 M vectors, comparing against frozen HNSW and other query‑aware baselines such as NGFix. Key findings include:\n* Recall improvement – on the GIST‑1M dataset REWEAVE lifted Recall@100 by 16.3 percentage points, and on a T2I‑10M dataset by 23.3 percentage points over a static HNSW graph.\n* Throughput advantage – under the same recall target of 0.80, REWEAVE achieved up to 3.3× the query throughput of NGFix.\n* Drift handling – on the Amazon‑ESCI workload, which simulates query‑distribution drift, REWEAVE raised stream Recall@100 from 0.745 to 0.979 while cutting search‑distance computations by 34 % compared with a frozen index.\nThese results demonstrate that, without increasing the per‑node degree budget, REWEAVE can both improve retrieval quality and reduce the computational effort of each search.\n\n## What theoretical guarantees back REWEAVE?\nThe paper provides two main analytic contributions. First, under explicit assumptions about the feedback model (e.g., unbiased binary rewards and sufficient exploration), the authors prove that edge‑value estimates converge to their true expected rewards with high probability. Second, they establish a regret bound against a “value‑greedy” benchmark that always selects the highest‑valued outgoing edge. The regret grows logarithmically with the number of queries when using an Upper‑Confidence‑Bound (UCB) navigation policy, and the authors extend the analysis to handle non‑stationary workloads via discounted estimation. In practical terms, the guarantees mean that the extra learning overhead incurred during adaptation is bounded and that the rewired graph will asymptotically approach the optimal in‑budget configuration.\n\n## How can Grafy users experiment with REWEAVE?\nWhile Grafy does not yet ship a built‑in REWEAVE module, the workflow fits naturally into several existing apps. Researchers can upload the REWEAVE source code and the accompanying benchmark datasets to Grafy Code (/code) to run the five‑step loop on a cloud instance, tweaking parameters such as the exploration rate or rewiring frequency. Developers interested in visualising the evolving graph can pipe the edge‑value logs into Grafy Graph (/graph), creating a branching view that shows how candidate buffers and rewired edges change over time. Finally, anyone wanting to read the full paper, extract equations, or ask ad‑hoc questions can use Grafy Reader (/reader) to upload the PDF and interactively query the content. By combining these tools, users can reproduce the authors’ experiments, explore custom feedback signals (e.g., user clicks), and prototype workload‑adaptive indexes for their own vector databases.\n\n---\nSource: https://arxiv.org/abs/2611.16060

---

Source: Grafy Research Lab — REWEAVE: Online Learning for Workload-Adaptive HNSW Indexes