---
adr: 194
title: "GNN-Enhanced Candidate Reranking for Approximate ANN Search"
status: accepted
date: 2026-05-21
authors: [ruvnet, claude-flow]
related: [ADR-143, ADR-193, ADR-184]
tags: [gnn, reranking, ann, vector-search, graph, rag, nightly-research]
---

# ADR-194 — GNN-Enhanced Candidate Reranking for Approximate ANN

## Status

**Accepted.** Implemented on branch `research/nightly/2026-05-21-gnn-rerank` as
`crates/ruvector-gnn-rerank`.  All 14 unit tests pass; build is green with
`cargo build --release -p ruvector-gnn-rerank`.

Benchmark (x86-64, Linux 6.18, `cargo run --release`, N=5K, D=128, K=10,
retrieval_k=80, noise_σ=0.40):

| Variant | recall@10 | mean µs | p50 µs | p95 µs |
|---------|-----------|---------|--------|--------|
| NoisyScore (baseline) | 28.0% | 0.2 | 0.2 | 0.2 |
| GnnDiffusion (1-hop, α=0.60) | **38.4%** | 1006 | 997 | 1053 |
| GnnMincut (coh≥0.50, α=0.60) | **38.4%** | 999 | 992 | 1025 |
| ExactL2 (oracle) | 74.9% | 13.8 | 12.5 | 16.5 |

GNN score diffusion delivers **+10.4 pp recall@10** over the noisy baseline.

## Context

Every approximate ANN index — whether HNSW, DiskANN, IVF, or RaBitQ — returns
a ranked candidate set whose distance estimates contain noise.  For quantised
indexes (1-bit RaBitQ, low-bit PQ, coarse IVF with small `nprobe`) this noise
can cause significant recall loss: items near the K-boundary swap order, pushing
true positives out of the top-K window.

Existing ruvector crates address the *first stage* (better indexing: RaBitQ in
ADR-177, RAIRS IVF in ADR-193, filtered ACORN in ADR-187) but not the *second
stage* (post-retrieval reranking).

The 2025–2026 literature identifies graph-based reranking as a promising
direction:
- GNRR (arXiv:2406.11720): +5.8% Average Precision on TREC-DL19
- Maniscope (arXiv:2602.15860): +7% NDCG, 3.2× faster than cross-encoders
- AQR-HNSW (arXiv:2602.21600): 2.5–3.3× QPS with 98%+ recall using multi-stage reranking

No production vector database (Milvus, Qdrant, Weaviate, LanceDB, FAISS, pgvector)
applies GNN message passing over the ANN candidate subgraph topology.

## Decision

We introduce `crates/ruvector-gnn-rerank` implementing the `CandidateReranker`
trait with four variants:

| Variant | Algorithm | Use case |
|---------|-----------|----------|
| `NoisyScoreReranker` | passthrough | baseline measurement |
| `GnnDiffusionReranker` | 1-hop score averaging | general reranking after quantised retrieval |
| `GnnMincutReranker` | structurally-gated diffusion | reranking with cross-cluster isolation |
| `ExactL2Reranker` | exact Euclidean sort | oracle and production fallback |

### Core algorithm (GnnDiffusionReranker)

1. Accept `n` candidates (id, full-precision vector, noisy_score).
2. Build a cosine k-NN graph over the candidate set: O(n² × dim).
3. Run `hops` rounds of score averaging:
   `s_i^{t+1} = α · s_i^t + (1-α) · mean_{j ∈ N(i)} s_j^t`
4. Sort by final score; return top-k.

### Why diffusion improves recall

True top-K items occupy the same vector cluster; in the candidate k-NN graph
they are mutually connected.  Averaging their noisy scores cancels i.i.d. noise
by the law of large numbers.  False positives with artificially high noisy scores
are isolated from the true cluster, so diffusion reduces rather than amplifies
their apparent relevance.  This is discrete graph spectral low-pass filtering.

### Mincut coherence gating

`GnnMincutReranker` gates propagation on structural edge weight (cosine
similarity between candidates) rather than on score ratios.  This prevents
cross-cluster score bleeding while allowing intra-cluster diffusion.  Score-ratio
gating was explicitly rejected because it blocks the most important edges — those
connecting a true positive that received a low noisy score to its correctly-scored
true-positive neighbours.

## Consequences

### Positive
- +10.4 pp recall@10 over noisy baseline (measured).
- Composable with any first-stage retriever via the `CandidateReranker` trait.
- No external service dependency.
- WASM-compatible (no unsafe code, no OS dependencies).
- Production candidate for use after `ruvector-rairs` / `ruvector-rabitq` retrieval.

### Negative / Trade-offs
- Graph construction is O(n² × dim): adds ~1ms latency for n=80, dim=128.
- `ExactL2Reranker` is 73× faster (14µs vs 1000µs) and provides the recall
  ceiling (74.9% at this noise level); GNN reranking only makes sense when exact
  vector comparison for all candidates is too expensive (e.g., remote fetch).
- The +10.4 pp gain is relative to a noisy baseline; the oracle gap is 36.5 pp.

## Alternatives considered

| Alternative | Rejected reason |
|-------------|-----------------|
| Cross-encoder reranking | Requires a learned model; Python dependency |
| Exact L2 (oracle) | Already in PoC; use directly when vectors are local |
| Score-ratio coherence gating | Blocks useful edges for low-noisy-score true positives |
| 2-hop diffusion | Marginal gain, 2× graph-build cost; future work |
| Multi-vector (ColBERT-style) | Different problem; higher design cost |

## Implementation plan

1. `crates/ruvector-gnn-rerank` — core library (this ADR). ✓ Done.
2. Integration into `ruvector-server` search pipeline — future work.
3. Candidate graph construction from compressed (RaBitQ) vectors — future work.
4. Adaptive alpha / hop selection via query feedback — future work.

## Benchmark evidence

Hardware: Intel Celeron N4020, x86-64, Linux 6.18.5, `rustc 1.87.0 --release`.
Data: multi-Gaussian, 20 clusters, σ=0.5, N=5K, D=128, 100 queries, K=10.
Noisy retrieval simulates quantised index: score = −L2 + N(0, 0.40²).

Full output: `cargo run --release -p ruvector-gnn-rerank --bin benchmark`.

## Failure modes

- **Candidate graph too sparse**: if candidates are from disjoint clusters, k-NN
  graph is disconnected; diffusion has no effect.  Mitigation: use `ExactL2Reranker` fallback.
- **Noise too high / coverage too low**: if true top-K items aren't in the
  candidate set, no reranker can recover them.  Mitigation: increase `retrieval_k`.
- **Alpha too low**: aggressive diffusion (small alpha) washes out signal; score
  homogenisation hurts recall.  Recommendation: α ≥ 0.5.
- **k_graph too small**: insufficient graph density → poor noise cancellation.
  Recommendation: k_graph ≥ 5, typically 8.

## Security considerations

- No file I/O, no network calls, no unsafe code.
- Candidate vectors are caller-provided; no validation of vector dimensionality
  across candidates (caller responsibility).
- No secrets or credentials involved.

## Migration path

`CandidateReranker` is a new trait; no existing code is modified.  Integration
into `ruvector-server` would add a post-search pipeline stage behind a feature
flag `gnn-rerank`.

## Open questions

1. Can candidate graph be built from compressed (4-bit) vectors with < 5%
   recall degradation, removing the need to fetch full-precision vectors?
2. What is the optimal α for production workloads with real embedding models?
3. Is 2-hop diffusion worth the 2× graph cost at larger n (200, 500)?
4. Can the O(n²) graph construction be approximated in O(n log n)?