HorizANN introduces ghost edges for elastic billion‑scale vector search
A new paper from the Grafy Research Lab proposes HorizANN, a graph‑based ANN index that uses ghost edges to add or drop machines without rebuilding the whole.
Source: Grafy Research LabApproximate nearest neighbor (ANN) search underpins many modern AI workloads, from retrieval‑augmented generation to recommendation engines. A new pre‑print from the Grafy Research Lab, HorizANN: Elastically Scaling Vector Search with Ghost Edges, proposes a way to grow or shrink ANN indexes across many machines without the costly full‑reindex step that currently hinders billion‑scale deployments.
What is HorizANN and why does it matter?
HorizANN is a graph‑based ANN indexing technique that keeps the high recall‑throughput balance of existing proximity graphs while adding a mechanism called ghost edges to maintain connectivity between data partitions. According to the paper, traditional graph indexes require the entire dataset to be repartitioned and each partition’s graph rebuilt whenever the cluster topology changes. This makes horizontal scaling expensive and time‑consuming, especially for datasets that already contain billions of vectors. By contrast, HorizANN’s ghost edges act as lightweight bridges that preserve search paths across partitions, allowing new machines to be introduced or removed with only incremental updates.
How does the ghost‑edge approach differ from traditional partitioning?
Conventional multi‑machine ANN systems split the vector collection into disjoint shards, build a separate proximity graph on each shard, and treat each graph as an isolated search space. When the number of machines changes, the shards must be recomputed to rebalance load, and the graphs are reconstructed from scratch. HorizANN replaces this rigid boundary with ghost edges: artificial edges that point from vectors in one shard to their nearest neighbours in another shard, without physically moving the vectors. These edges are maintained lazily; they are added when a new node joins the cluster and trimmed when a node departs. The result is a flexible overlay that preserves the global graph structure while keeping each shard’s core graph untouched.
What performance or scalability benefits does the paper claim?
The authors report that the ghost‑edge layer incurs only a modest memory overhead compared with a fully rebuilt index, because each vector stores a small fixed number of cross‑shard links. More importantly, the incremental update cost scales with the number of newly added or removed machines rather than with the total dataset size. This means that adding a single server to a billion‑vector cluster can be completed in minutes rather than hours, and removal can be performed without a full re‑index. The paper also highlights that search latency remains comparable to a monolithic graph because the ghost edges provide direct shortcuts to relevant regions of the overall index.
Practical implications for developers building large‑scale vector search
For engineers who already rely on graph‑based indexes such as HNSW or DiskANN, HorizANN offers a migration path that preserves existing graph construction pipelines while augmenting them with a thin ghost‑edge layer. The approach reduces operational downtime during scaling events, which is valuable for cloud‑native services that must respond to traffic spikes or cost‑driven instance resizing. It also simplifies capacity planning: instead of forecasting a fixed cluster size for the lifetime of the index, teams can provision additional nodes on demand and let the ghost‑edge mechanism handle the integration.
Using Grafy to explore or prototype HorizANN concepts
Grafy provides several tools that can help researchers and developers experiment with the ideas in HorizANN without writing a full production system from scratch:
- Reader lets you upload the arXiv PDF, ask natural‑language questions about the methodology, and retrieve specific excerpts about ghost‑edge construction.
- Code offers an AI‑assisted coding environment where you can prototype a small‑scale ghost‑edge overlay on top of an existing HNSW implementation, using the built‑in code execution sandbox.
- Graph can be used to visualise the multi‑layer graph structure, showing both intra‑shard edges and the cross‑shard ghost edges, which helps in debugging connectivity issues.
- Chat enables you to converse with multiple model back‑ends to explore alternative designs for ghost‑edge maintenance policies (e.g., periodic refresh versus on‑demand insertion).
These apps let you move from reading the paper to a hands‑on proof‑of‑concept in a single workspace, accelerating the iteration cycle for anyone looking to adopt elastic ANN indexing.
Frequently asked questions
Does HorizANN eliminate the need to ever rebuild a graph?
No. HorizANN reduces the frequency of full rebuilds by handling most scaling events with ghost‑edge updates, but occasional full re‑indexing may still be required for major data drifts or algorithmic upgrades.
Are ghost edges stored alongside the original graph data?
Yes. Each vector keeps a small, fixed‑size list of cross‑shard neighbours, which the authors describe as a lightweight memory overhead relative to the main proximity list.
Can HorizANN be applied to non‑graph ANN methods such as product quantisation?
The paper focuses on graph‑based indexes, and the ghost‑edge concept relies on explicit neighbour links. While the underlying idea of cross‑partition shortcuts could inspire extensions, direct application to quantisation‑only methods would need additional research.
Source: Grafy Research Lab, HorizANN: Elastically Scaling Vector Search with Ghost Edges, arXiv abs/2611.19077 (2026‑11‑17).
Source: Grafy Research Lab — HorizANN: Elastically Scaling Vector Search with Ghost Edges


