Failure-Resilient and Verifiable Distributed Approximate Nearest-Neighbor Retrieval

Replication in a distributed vector database keeps results available, but it does not make them true. A compromised replica can return nearest neighbors that carry a perfectly valid signature and still contain tampered content. TrustANN adds a middleware layer above the router without changing the ANN algorithm. For each shard it asks whether enough replicas, consistent with each other and spread across different failure domains, return the same answer. If the evidence is missing, it returns "Unverified" instead of quietly passing the result along. On a 9-node cluster in Amazon's cloud, the share of tampered results accepted as trusted fell from 100% to 0. Clean p95 latency rose by only 9.36%, and trusted results survived a third of replicas crashing.

Engineers working on retrieval security, multi-tenant vector services or RAG backends should read it. It separates two things people often mix up: an intact index and live replicas do not mean this query's result can be trusted. The idea in one line: judge trust per query and per shard, keep coordination in the background, and when replicas fail, look for new independent evidence without lowering the bar. It is a single-author paper with 100K vectors and 100–150 queries per setting, and its latency numbers are not measured the same way across tables. Treat it as a design reference.

What problem is it actually solving?

Take an enterprise knowledge-base search as an illustration. The vector store has 3 shards with 3 replicas each, placed in different availability zones. One machine is breached. The attacker makes it swap an internal expense policy for a forged version in its neighbor list. The machine still holds valid keys, so signature checks pass. If the router asks only that replica, or only counts how many replicas replied, the forged result flows straight into the downstream LLM.

So the issue is not cryptography. It is what kind of reply counts as evidence. The threat model allows at most ⌈r/2⌉−1 of a shard's r replicas to misbehave at once, which is 1 when r=3. A bad replica may return stale results, drop true neighbors, inject fake candidates or reorder the ranking.

The pipeline

The system has two paths. The background path belongs to CoordShift. Every so often (200 ms in the experiments) it produces a signed coordination epoch. It holds an epoch number and a digest of each shard's current index state, roughly "which version each shard is on". During online checks, every replica reply must carry the currently accepted epoch number and a valid signature, or it is dropped. That keeps stale replies and replays of an old version out of the evidence set. Many later queries reuse one epoch. The online path runs five steps per query. It picks the relevant shards. It sends the query to their replicas, and each replica runs ordinary HNSW search and attaches a signature, shard ID, replica ID, epoch number and failure domain. TrustBind checks the evidence shard by shard. If a shard falls short, AvailGuard looks for new independent replicas. Only when every shard passes is the result marked trusted. The candidates from each shard's selected evidence are then merged, re-sorted by vector distance, and the top ones are returned.

The two paths connect only through the epoch number. Each reply's signature covers the candidate set, the replica's index state and the epoch number. So a reply is bound to which replica produced it and on which version, and it cannot be altered later. A signature cannot stop a bad replica from signing a stale or fake result with the current epoch, though. That is why the consistency and independence checks are still needed. Whether a query is trusted is decided entirely on the online path, so a background round influenced by bad nodes cannot by itself make a query trusted.

TrustBind: three conditions, all at once

Why not just count replicas? Three replies may come from one data center and fail together. Two may contradict each other, giving enough votes but mismatched content. TrustBind therefore checks three things for each shard:

1. Support: at least θ selected replies, with θ = ⌈r/2⌉. With r=3, θ=2, so one bad replica cannot reach the count alone.
2. Consistency: every pair of replies gets a similarity score equal to λ × overlap + (1−λ) × rank agreement. Overlap is the intersection of the two candidate ID sets divided by their union. Rank agreement looks only at shared candidates and turns their relative order into a 0–1 score. Think of it as the share of shared-candidate pairs ordered the same way on both sides: identical order scores 1, fully reversed scores 0. The average over all pairs in a group must reach γ. Dropping candidates lowers overlap and reordering lowers rank agreement, so both kinds of tampering show up.
3. Independence: selected replies must cover at least d_min distinct failure domains, such as availability zones or network domains. Two replies from the same zone count as one domain.

Selection is greedy. It starts with the reply whose total similarity to the others is highest. At each step it adds one more reply, preferring replies from failure domains not yet covered, and among those the one that raises average similarity the most. It stops when all three conditions hold or no candidates remain.

One rule is strict: evidence is never borrowed across shards. The misbehavior bound is defined per shard. If spare evidence from shard A could fill a gap in shard B, an attacker holding one replica in each of several shards could pool them to clear the bar.

Here is a worked example with θ=2 and d_min=2. Shard 2 has three replicas: a1 and a2 in zone a, b1 in zone b. The router first asks a1 and a2. Their results match exactly, so support and consistency pass, but only one failure domain is covered. The shard is marked insufficient, and AvailGuard contacts b1, which has not been asked yet. If b1 agrees with zone a, one zone-a reply plus b1 covers two domains and the shard passes. If b1 is down, or compromised and swaps rank 3 for a forged document so similarity drops below γ, no valid evidence set exists. The whole query then returns Unverified.

CoordShift: moving coordination off the query path

Why coordinate in the background? Running Byzantine consensus, a voting protocol that tolerates some lying nodes, on every query is too expensive for millisecond-scale search. CoordShift runs a light round periodically instead. It samples a candidate pool larger than needed and greedily picks the k nodes that cover the most failure domains. Both k and the pool size are deployment parameters, and a larger k means more coordination traffic. It collects their signed state summaries. For each shard it takes the majority value, or keeps last round's value if there is no majority. A round that gets nothing is a no-op, and the next round resamples.

The author is explicit that this is not a new consensus protocol. Its output is a signed, reusable reference state with no guarantee that the content is correct. Query safety stays with TrustBind and AvailGuard. The payoff is that if coordination is slow or disturbed, queries keep running on the previous epoch without waiting.

AvailGuard: more evidence, same bar

When replicas crash, the system can often still return results, but trusted evidence shrinks. Simply asking more replicas is risky. A new reply may share a failure domain with an existing one, or both may be compromised together. AvailGuard keeps the valid evidence it already has and prefers replicas that add a new failure domain. Domains that already produced suspicious or conflicting replies go to the back of the line. Each shard may contact at most K_max extra replicas, which defaults to 1. If the cap is reached without enough evidence, it returns Unverified. It never lowers θ and never uses another shard's evidence.

Results

The testbed runs on Amazon cloud virtual machines. One coordinator hosts the router, TrustBind, AvailGuard and CoordShift. Nine workers form 3 shards × 3 replicas. The data is a 100K-vector, 96-dimensional subset of Deep10M, and each replica uses a FAISS HNSW index. The baseline is the same deployment without the verification layer. Attack success rate means the share of attacked queries whose tampered result is marked trusted.

Three conclusions follow. First, "at least two replicas" is not enough. In the ablation, checking only count, or count plus consistency, assembled 2 replies (one tampered) and marked them trusted. With the full three-part rule, every attack in the same batch was rejected. The author notes that the ablation toggles the whole rule and does not separate how much consistency and independence each contribute, so the only conclusion is that all three belong together. Second, the clean-path cost is modest: about 8% less throughput and about 0.1 ms more at p95. Third, the availability boundary is clear. Crashes are drawn uniformly at random across replicas. Stopping 33% of 9 is about 3 machines, and since the trusted rate stays at 100%, each shard could still assemble two independent replies. At 49%, about 4 or 5 machines, the trusted rate drops to 0, meaning affected shards could no longer find two, and the system marks everything Unverified rather than relax the bar.

In the coordination test, load rose from 50 to 400 queries per second and no query waited for an epoch, which means coordination really is off the query path. Raising fan-out from 1 to 3 shards lifted p95 from 1.51 to 7.46 ms, because the replies to collect and compare grew from 3 to 9.

Limitations as I see them

1. Latency is reported inconsistently. The clean comparison shows only 9.36% more p95. In the single-bad-replica test, turning on θ=2 makes p95 about 3.6 times higher. Because these numbers come from different setups, readers cannot easily estimate the real cost in their own system.
2. Scale and attacks are small. There are only 100K vectors, 9 nodes and 100–150 queries per setting, and the attack model is a single bad replica. In a run with fixed per-node load, nodes grew from 18 to 144, which is 8 times. Ideal throughput would grow 8 times too, but it rose only from 908.6 to 1176.5 queries per second. Parallel efficiency is actual over ideal throughput, and it fell to 0.162. That suggests evidence collection itself becomes the bottleneck as nodes grow.
3. Some tests lack a positive control. In the table for dropped-candidate and reordering attacks, the clean condition also has a trusted rate of 0. Those results show the system was not fooled, but not that clean results pass. Also, failure-domain metadata relies on the operator configuring it honestly; if it is wrong, the independence check means little.

How a recommendation or search team could try this

1. Map failure domains first. Label each shard's replicas by zone, rack and owning team, and see how many shards actually crowd into one domain.
2. Compare replica replies offline. Send a sample of real queries to all replicas of a shard and measure candidate overlap and rank agreement. This tells you what γ should be under normal conditions and avoids false alarms.
3. Run verification in shadow mode. Without changing live responses, apply θ=2 checks to a small slice of sensitive queries, such as permission-gated document search. Log only the Unverified rate and the added latency.
4. Then decide whether to enforce. If the Unverified rate is low and the latency acceptable, wire it downstream: demote, flag or refuse unverified results.

Bottom line

TrustANN turns "can this retrieval result be trusted" into an explicit decision that is allowed to say no. The idea is worth borrowing, but measure the cost again in your own system.