Failure-Resilient and Verifiable Distributed Approximate Nearest-Neighbor Retrieval

Failure-Resilient and Verifiable Distributed Approximate Nearest-Neighbor Retrieval

arXiv:2610.34608v1 [cs.DC] 25 Oct 2026

Abdullah Al-Mamun Augusta University aalmamun@augusta.edu

Abstract

provide efficient large-scale search [14, 21, 27]. Recent distributed vector systems further improve scalability through parallel execution, communication optimization, and resource disaggregation [1, 32, 34, 41]. However, distributing retrieval also expands its trust boundary: a query result may depend on multiple shards, replicas, and workers whose behavior cannot necessarily be assumed correct. Thus, scalable distributed retrieval raises a fundamental question beyond performance: when can a distributed ANN result itself be trusted? First, authenticated state does not imply trustworthy retrieval. Authenticated data structures can establish that stored state is consistent with an authenticated representation [11], and recent verifiable ANN systems extend this principle to approximate search. ANNProof, VLAH, and CD-ANN provide mechanisms for verifying ANN search results or protecting index/vector state using authenticated structures and, in some cases, blockchain anchoring [20, 29, 37]. These approaches establish important foundations for verifiable retrieval, but their primary abstraction is verification of an index or an individual search execution. In a distributed ANN fabric, however, a worker may possess a valid authenticated index while still omitting candidates, returning stale results, manipulating rankings, or providing inconsistent responses. Thus, authenticated state does not necessarily imply trustworthy distributed retrieval. What is missing is query-level retrieval trust: whether the distributed participants involved in a query provide sufficient independent evidence to justify accepting its result. This distinction is also broader than retrieval poisoning. PoisonedRAG and related work demonstrate that malicious retrieved content can substantially manipulate RAG systems [16, 42], but a retrieval participant can also compromise the result without injecting poisoned content, for example by suppressing, replaying, or selectively manipulating results. Establishing such trust, however, creates a second challenge: coordination latency. A natural response to untrusted participants is to require them to agree before accepting a result. Byzantine-fault-tolerant consensus provides strong guarantees against faulty replicas, but requires communication and synchronization among participants [9]. Blockchain-based

Distributed vector databases increasingly support securitysensitive applications, yet existing systems primarily protect index integrity or replica availability rather than the trustworthiness of retrieved results. Consequently, a compromised replica can return a plausible but manipulated result that remains cryptographically valid, while conventional replication and Byzantine defenses do not directly establish whether the retrieved results are trustworthy. We present T RUSTANN, a middleware layer that provides query-level trust for distributed approximate nearest-neighbor (ANN) retrieval without modifying the underlying ANN algorithm. TrustANN introduces three complementary protocols: T RUSTB IND, which verifies retrieval trust from authenticated, consistent, and failure-domain-independent replica evidence; C O ORD S HIFT , which asynchronously constructs reusable coordination epochs outside the query critical path; and AVAIL G UARD, which performs bounded recovery when replicas are unavailable, stale, or conflicting while preserving the trust criterion. Queries are marked T RUSTED only when sufficient independent evidence exists for every relevant shard; otherwise, TrustANN returns U NVERIFIED. On an AWS deployment using distributed FAISS HNSW, TrustANN reduces retrieval attack success rate from 1.000 to 0.000 under the tested Byzantine-retrieval attack with two-of-three replica verification. The verification layer increases clean p95 latency by only 9.36%. Under replica crashes, TrustANN maintains trusted retrieval through 33% failures and correctly returns U NVERIFIED when sufficient evidence is unavailable.

1

Introduction

Distributed approximate nearest-neighbor (ANN) retrieval has become a core substrate for retrieval-augmented generation, recommendation, semantic search, and other vector-intensive applications [18, 38]. Modern ANN systems scale by partitioning vector collections across machines and replicating shards, while indexes such as HNSW, IVF/PQ, and DiskANN 1

distributed systems similarly use replicated agreement to establish trusted state [15,36]. Putting such coordination directly on the ANN query path, however, couples retrieval latency to distributed agreement. This conflicts with the design objective of ANN systems, where parallelism and communication efficiency are central to low-latency search [21, 27, 41]. Existing blockchain-anchored verifiable ANN systems demonstrate the value of authenticated state [20, 37], but do not address how to maintain reusable trust state without making distributed coordination a prerequisite for each retrieval operation. The challenge, therefore, is not simply to establish trust, but to establish reusable trust state without placing consensus-scale coordination on the latency-critical query path. Finally, failures make replica availability an insufficient basis for trust. Even when coordination is kept off the query path, replication provides availability rather than sufficient trustworthy evidence. Distributed vector systems replicate data to tolerate failures and sustain retrieval [1, 34, 41], yet surviving replicas may crash, become unreachable, return stale state, or produce conflicting responses. A system that simply accepts any available response can therefore mistake availability for correctness, whereas lowering the integrity threshold when replicas fail weakens the very guarantee the system is intended to provide. Byzantine-resilient systems traditionally make the fault bound explicit when determining whether sufficient replicas support an operation [9]. For distributed ANN, the analogous requirement is to distinguish having an answer from having enough evidence to trust that answer. A trustworthy retrieval system must therefore preserve its evidence threshold under failures, attempt bounded recovery using surviving replicas, and explicitly reject a result when sufficient evidence cannot be established. Proposed Solution. Existing systems address distributed ANN execution [1,32,34,41], authenticated ANN state [20,29, 37], federated retrieval confidentiality [39], or malicious retrieval content [16,42], but do not provide query-level retrieval trust with reusable coordination and failure-aware evidence recovery. We present TrustANN, a middleware layer that operates above existing ANN indexes without modifying the underlying search algorithm. TrustANN separates retrieval execution from retrieval trust and background coordination from query-level safety by three tightly coupled components. First, TrustBind establishes trust per shard from authenticated replica evidence by requiring sufficient, mutually consistent, and failure-domain-independent responses. Second, CoordShift asynchronously constructs reusable retrieval epochs through randomized, failure-domain-aware coordination; its state is cached and consumed by queries, but it is not the query-level safety boundary. Finally, AvailGuard performs bounded recovery by seeking additional independent evidence without weakening the trust threshold. If sufficient evidence cannot be established, TrustANN returns U NVERIFIED. Thus, coordination and recovery remain supporting mechanisms, while the query-level trust decision is independently deter-

mined by retrieval evidence. We implement TrustANN over an existing HNSW-based distributed ANN substrate and evaluate it on Deep10M [19] using a multi-node AWS deployment, covering retrieval attacks, evidence ablations, failures, fan-out, recovery, and asynchronous coordination. In summary, this paper makes the following contributions: (i) Query-level retrieval trust. We introduce TrustBind, which establishes per-shard retrieval trust from authenticated, consistent, and failure-domain-independent replica evidence. (ii) Asynchronous coordination. We introduce CoordShift, which builds reusable, failure-domain-aware retrieval epochs asynchronously without placing coordination on the query critical path. (iii) Bounded failure recovery. We introduce AvailGuard, which recovers additional independent evidence under replica failures without weakening the trust criterion, returning U N VERIFIED when sufficient evidence cannot be established. (iv) Prototype and empirical validation. We implement TrustANN over distributed HNSW and evaluate it on AWS. The configured majority threshold reduces R-ASR from 1.000 to 0.000 against the tested Byzantine-retrieval attack, while clean p95 overhead is 9.36%. TrustANN maintains trusted retrieval through 33% replica crashes and returns U NVERIFIED when sufficient evidence is no longer available.

2

Threat Model

We consider a distributed ANN deployment with N workers organized into M shards, each replicated across r workers. TrustANN operates under partial synchrony and evaluates retrieval trust independently for each shard reached by a query. Adversary and failure model. We consider a Byzantinecapable adversary A that may control a bounded subset of workers. For every shard j, fewer than half of its r replicas may be corrupted: fs ≤ ⌈r/2⌉ − 1. (1) Corrupted replicas may collude across shards and may return arbitrary, incomplete, stale, or conflicting candidates, manipulate rankings, replay invalid-epoch responses, or selectively respond to queries. We separately consider crash and network failures, including unavailable, slow, stale, or temporarily disconnected workers. Crash and Byzantine failures may coexist within a shard. Such failures reduce available evidence but never cause TrustANN to weaken its acceptance criteria. Evidence boundary. TrustANN evaluates evidence per shard. For each shard j reached by query q, the selected evidence Sq, j must satisfy |Sq, j | ≥ θ,

C(Sq, j ) ≥ γ,

D(Sq, j ) ≥ dmin ,

(2)

where θ is the support threshold, C(·) measures response consistency, and D(·) measures independence across configured failure domains. Evidence from different shards cannot be pooled to satisfy these conditions. Thus, coordinated 2

Table 1: Comparison of TrustANN with representative distributed, verifiable, and Byzantine-tolerant retrieval approaches. The listed systems address complementary system abstractions and are not directly comparable experimental baselines for TrustANN. System DistributedANN [1] ANNProof [20] VLAH [29] CD-ANN [37] PBFT [9] TrustANN (This work)

Distributed ANN

Search/Index Verification

Replica-Level Retrieval Trust

Failure-Aware Trust

Off-Path Coordination

Consensus-Free Query Path

✓ ×/✓ ✓ ✓ × ✓

× ✓ ✓ ✓ × ✓

× × × × × ✓

× × × × ✓ ✓

× × × ×/Partial ✓ ✓

✓ ✓ ✓ ×/Partial × ✓

Search/Index Verification covers verification of search execution, index structure, or associated state; Replica-Level Retrieval Trust denotes query-level trust from evidence across replicas. Failure-Aware Trust covers trust under replica failure, stale state, or conflicting evidence. Off-Path Coordination and Consensus-Free Query Path denote asynchronous coordination and retrieval without consensus/global synchronization, respectively.

corrupted replicas across multiple shards cannot accumulate sub-threshold evidence to satisfy a per-shard trust decision. If sufficient evidence is unavailable, TrustANN returns U NVER IFIED rather than weakening the criteria. TrustANN does not assume that distinct worker identities imply independent evidence; independence is determined using configured failuredomain metadata. Coordination boundary. CoordShift provides an authenticated, asynchronously constructed coordination reference rather than Byzantine-agreement-level certification. A coordination round may fail or be influenced by faulty workers without directly causing a query to be trusted: TrustBind independently evaluates query-level retrieval evidence. A failed round leaves the previously published epoch active and does not block queries. Assumptions and scope. We assume secure cryptographic primitives, authenticated worker identities, and an uncompromised underlying ANN implementation. Compromise of these mechanisms is outside our threat model. TrustANN’s guarantees are bounded by the stated per-shard corruption and failure-domain assumptions. It does not provide a formal ANN-recall guarantee when these assumptions are violated.

3

replica failures can leave a query operationally available while providing insufficient independent evidence to establish retrieval trust. TrustANN addresses these challenges through three complementary components: TrustBind, CoordShift, and AvailGuard. TrustBind establishes query-level trust from mutually consistent and independently attributable replica evidence. CoordShift maintains reusable retrieval epochs using asynchronous, randomized coordination with fault-domain diversity, while keeping its correctness outside the query-time safety boundary. AvailGuard performs bounded recovery by seeking additional independent evidence without weakening the trust threshold. Figure 1 presents the overall architecture.

3.1

System Model

We consider a distributed ANN deployment consisting of N retrieval workers organized into M logical shards, with each shard replicated across r workers (N = M · r). Each replica maintains an independent ANN index for its assigned shard. TrustANN does not require a particular ANN implementation; the underlying index may use HNSW, IVF, DiskANN, or another ANN structure. Let the distributed ANN state at epoch t be

System Design

It = I1t , . . . , IMt ,

(3)

where I tj denotes the state of shard j. A query q is routed to a set of relevant shards Jq ⊆ 1, . . . , M and to one or more replicas of each relevant shard. Each contacted worker performs ordinary ANN search and returns a candidate set together with compact authenticated metadata identifying the worker, shard, replica, index state, and retrieval epoch. TrustANN operates under a partially synchronous network. Workers may experience crash-stop failures for availability analysis and may behave Byzantinely for integrity analysis. The adversary is bounded separately within each shard: at most lrm fs = −1 (4) 2 of the r replicas of a shard may be corrupted at a given time. Corruption may occur independently across shards subject

TrustANN is a middleware architecture for trustworthy distributed approximate nearest-neighbor (ANN) retrieval. Rather than replacing the underlying ANN index or search algorithm, TrustANN operates above an existing distributed ANN deployment and introduces a query-level retrieval-trust layer across its shards and replicas. The design targets environments in which retrieval workers may be unavailable, stale, or adversarial. The design addresses three challenges. First, authenticating ANN index state does not establish trustworthy retrieval: a worker may possess valid index state while returning incomplete, stale, or manipulated candidates. Second, placing distributed agreement directly on every query introduces additional communication and synchronization latency. Third, 3

Figure 1: Failure-Resilient and Verifiable Distributed Approximate Nearest-Neighbor Retrieval. to this bound. A Byzantine worker may return stale candidates, omit legitimate candidates, inject arbitrary candidates, manipulate rankings, or provide inconsistent evidence. TrustANN does not require a global honest-majority assumption across all N workers. Instead, its query-level trust decision is made separately for each relevant shard using authenticated provenance, response consistency, and configured failure-domain independence. CoordShift maintains reusable coordination state, but TrustBind and AvailGuard independently determine whether sufficient retrieval evidence exists.

3.2

sets and authenticated metadata. TrustBind validates the responses and constructs an evidence graph for each relevant shard. For each shard, it seeks a sufficiently large set of mutually consistent responses whose provenance spans the configured independent failure domains. A result is considered T RUSTED only when the trust condition is satisfied for every relevant shard. If sufficient evidence is unavailable for one or more shards, AvailGuard selects additional replicas for the affected shard subject to the same independence requirements and a bounded recovery budget. It does not lower the trust threshold and does not allow evidence from one shard to substitute for missing evidence from another. If the required evidence cannot be established within the recovery budget, TrustANN returns U NVERIFIED. The retrieval and coordination paths interact only through the authenticated epoch reference, but their safety strengths are deliberately different. CoordShift does not provide a Byzantine-safe certification of the epoch contents. A sampled coordination quorum may occasionally be influenced by faulty workers; such an event affects coordination state but does not itself establish query trust. TrustBind independently validates retrieval evidence for every query. Consequently, a failed or adversary-influenced coordination round does not

Architecture Overview

As Figure 1 illustrates, TrustANN separates background coordination from query-level retrieval trust. CoordShift periodically samples workers and publishes a cryptographically authenticated retrieval epoch reference using a diversity-aware quorum. Authentication establishes the provenance and integrity of the epoch reference; it does not certify the semantic correctness of its state digest. TrustBind and AvailGuard operate on the query path, where the router selects relevant shards and replicas and workers perform ordinary ANN retrieval. When a query arrives, contacted workers return candidate 4

Algorithm 1 TrustBind: Per-Shard Retrieval Evidence Verification

directly cause a query to be trusted.

3.3

Require: Query q, authenticated epoch et , relevant shards Jq , replica sets {R j } Ensure: Trusted evidence or I NSUFFICIENT 1: for all j ∈ Jq do 2: Eq, j ← 0/ 3: for all wi ∈ R j contacted for q do 4: Ci ← ANN(wi , q) 5: σi ← Prove(Ci , µi , et , wi ) 6: validate ⟨Ci , σi , et , j, domaini ⟩ 7: if valid then 8: Eq, j ← Eq, j ∪ {(Ci , domaini )} 9: end if 10: end for 11: construct Gq, j from Eq, j 12: Sq, j ← GreedyEvidenceSelect(Gq, j , θ, γ, dmin ) 13: if |Sq, j | < θ or C(Sq, j ) < γ or D(Sq, j ) < dmin then 14: return I NSUFFICIENT 15: end if 16: end for 17: return {Sq, j } j∈Jq

Consistency-Aware Query-Level Trust

TrustBind protocol. An authenticated ANN index establishes the authenticity of a worker’s state but does not establish that its returned neighbors are trustworthy. Moreover, simple replica counting can incorrectly treat mutually inconsistent responses as equivalent evidence. TrustBind (i.e., Protocol 1) therefore evaluates retrieval evidence along three dimensions: support, consistency, and independence. Per-shard evidence boundary. Because the Byzantine bound is defined per shard, the TrustBind protocol maintains a separate evidence set for every relevant shard. Let Sq, j denote the evidence selected for query q from shard j, where j ∈ Jq . Evidence from another shard cannot be used to satisfy the threshold for shard j. This boundary prevents an adversary from accumulating mutually consistent responses across different shards and using their aggregate count to compensate for insufficient evidence within one shard. For each shard j, TrustBind accepts the retrieval evidence only if |Sq, j | ≥ θ, C(Sq, j ) ≥ γ, and D(Sq, j ) ≥ dmin , where θ is the minimum number of supporting replicas, C(·) measures response consistency, and D(·) measures coverage of independent configured failure domains. We use θ = ⌈r/2⌉. Thus, under Eq. 4, a corrupted minority within a shard cannot alone satisfy the support threshold. Evidence graph. For each relevant shard j, the TrustBind protocol constructs an evidence graph Gq, j = (Vq, j , Eq, j ), where each vertex represents a valid worker response for shard j. An edge (va , vb ) captures pairwise consistency, defined as wab = λJ(Ca ,Cb ) + (1 − λ)R(Ca ,Cb ), (5) where J(·, ·) is candidate-ID Jaccard similarity [26] and R(·, ·) is our normalized rank-agreement score computed over common candidate IDs. Thus, candidate suppression primarily affects the candidate-overlap term, whereas ranking manipulation affects the rank-agreement term. For an evidence set S ⊆ Vq, j , aggregate consistency is 2 C(S) = (6) ∑ wab . |S|(|S| − 1) va ,v ∈S

and a query is trusted only if every relevant shard satisfies this condition: Trusted(q) ⇐⇒

^

Trusted j (q).

(9)

j∈Jq

The consistency and diversity thresholds are deployment parameters. They do not replace the per-shard corruption bound, but prevent inconsistent or correlated responses from being treated as interchangeable evidence. Evidence selection. Finding an exact maximum-weight consistent subset is unnecessary for the small evidence sets used by TrustANN. We therefore use a greedy selection procedure. For each shard, the procedure begins with the highestsupported valid response and iteratively adds the response with the largest marginal consistency gain while respecting the configured failure-domain constraint. The procedure terminates when the evidence set satisfies the support, consistency, and diversity requirements or when no eligible response remains. Thus, a response contributes to query trust only when it is both independently attributable and sufficiently consistent with the supporting evidence. Replica identity alone is not treated as a sufficient indicator of independence.

b

a<b

The TrustBind protocol also evaluates evidence independence across configured failure domains. Let Dq, j denote the failure domains associated with replicas of shard j (e.g., availability zones, network domains, or independently managed replica groups), as specified by trusted deployment metadata. We define D(S) = |{d : ∃v ∈ S, domain(v) = d}| . (7) Hence, multiple responses from the same failure domain do not automatically constitute independent evidence. The trusted-evidence condition for shard j is

Epoch and provenance validation. Each response must carry a valid signature and the currently accepted epoch number. Provenance is represented by the tuple ⟨shard, replica, worker, domain⟩, which prevents duplicate counting while exposing the configured independence domain used by the trust decision. The epoch reference binds responses to the currently accepted coordination state, but the TrustBind protocol does not treat the semantic contents of the C OORD S HIFT digest as a safety oracle. Consequently, query-level trust remains independent of whether the sampled coordination quorum produced a perfectly accurate state summary.

Trusted j (q) ⇐⇒ |Sq, j | ≥ θ ∧C(Sq, j ) ≥ γ ∧ D(Sq, j ) ≥ dmin (8) 5

3.4 Diversity-Aware Asynchronous Coordination

Algorithm 2 CoordShift: Diversity-Aware Asynchronous Coordination Require: Membership W , quorum size k, pool size k′ Ensure: Authenticated epoch et+1 or no-op 1: Pt ← RandomSample(W , k′ ) 2: Qt ← GreedyDiverseSelect(Pt , k) 3: Rt ← CollectSignedSummaries(Qt , τ) 4: if Rt = 0/ then 5: return no-op 6: end if 7: Dt+1 ← 0/ 8: for all shard j do 9: v j ← MajorityValue(Rt , j) 10: if v j exists then 11: Dt+1 [ j] ← v j 12: else 13: Dt+1 [ j] ← et .D[ j] 14: end if 15: end for 16: et+1 ← ⟨t + 1, Dt+1 , τt+1 ⟩ 17: publish et+1 18: return et+1

CoordShift protocol. Requiring Byzantine consensus or synchronous agreement for every retrieval epoch would introduce coordination overhead into a latency-sensitive ANN query path. The CoordShift protocol (i.e., Protocol 2) instead maintains reusable coordination state asynchronously. Its purpose is not to provide a new Byzantine consensus protocol, but to amortize repeated coordination cost and reduce correlated exposure through diversity-aware randomized selection. Most importantly, CoordShift is not part of the query-time safety boundary. Even if its sampled quorum is influenced by Byzantine workers, the TrustBind protocol (Section 3.3) does not accept a retrieval result solely because it is consistent with the resulting coordination digest. Diversity-aware quorum selection. At the beginning of coordination round t, the CoordShift protocol samples a candidate pool Pt ⊆ W , |Pt | = k′ , (10) ′ where k > k. It then selects a quorum Qt ⊆ Pt of size k using the greedy diversity objective F(Q) = ∑ min{1, |Q ∩ d|},

erage and reduced correlated exposure. This distinction separates the coordination-resilience objective from the querylevel safety condition enforced by the TrustBind protocol (Section 3.3).

(11)

d∈D

3.5

where D represents configured fault domains, such as availability zones, network domains, or replica groups. The selection repeatedly adds the candidate providing the largest marginal increase in F(Q). This discourages a coordination quorum from being concentrated in a single correlated failure domain while retaining randomized committee selection. Each selected worker returns a signed state summary. For each shard, CoordShift selects a majority-supported summary value when one exists; otherwise it retains the previous value. A coordination round that fails to obtain usable summaries is treated as a no-op, and a subsequent round uses a newly sampled candidate pool. CoordShift therefore produces a cryptographically authenticated, reusable coordination reference, rather than a Byzantine-safe state certificate. Its epoch can be reused across many queries, while query-level retrieval safety remains the responsibility of the TrustBind protocol (Section 3.3) and the AvailGuard protocol (Section 3.5). Quorum sizing and failure-domain diversity. The quorum size k controls coordination cost and the amount of sampled evidence, while F(Q) controls representation of distinct failure domains. Increasing k increases coordination traffic; diversity-aware selection favors distinct configured domains before filling the remaining quorum positions. When the failure-domain metadata accurately represents independence, this reduces concentration within correlated domains. The design does not claim that diversity-aware sampling eliminates Byzantine influence or universally lowers the probability of an adversary-influenced coordination round. Instead, its directly intended property is increased failure-domain cov-

Independence-Aware Evidence Recovery

AvailGuard protocol. Replica failures can preserve operational retrieval availability while reducing the evidence available to establish retrieval trust. A recovery mechanism that simply collects additional responses may incorrectly interpret correlated or jointly compromised replicas as independent support. The AvailGuard protocol (i.e., Protocol 3) therefore treats independent evidence, rather than response count alone, as the recovery objective. Design. Suppose the TrustBind protocol (Section 3.3) cannot establish Trusted j (q) for a relevant shard j. AvailGuard retains the valid evidence already collected for that shard and selects additional replicas that provide new fault-domain coverage. Replicas from domains already represented by suspicious or conflicting evidence are deprioritized. Each recovery step therefore attempts to increase the independence of the evidence set rather than merely its cardinality. Importantly, evidence recovery is performed independently for the affected shard; responses from other shards cannot be used to satisfy the trust condition for shard j. Recovery is bounded by Kmax . The threshold θ and the consistency and diversity requirements remain unchanged throughout recovery. After each additional retrieval round, the TrustBind protocol (Section 3.3) reevaluates the affected shard using the same condition as Eq. 8: |Sq, j | ≥ θ,

C(Sq, j ) ≥ γ,

D(Sq, j ) ≥ dmin .

(12)

If the condition becomes satisfied, the shard is marked T RUSTED. Otherwise, AvailGuard continues while the re6

Algorithm 3 AvailGuard: Independence-Aware Evidence Recovery

TrustANN does not equate replica identity with independent evidence. The TrustBind protocol requires sufficient response consistency and failure-domain diversity as defined in Eqs. 5– 7. Responses from the same correlated domain therefore do not automatically increase the trust level. (4) Failure recovery never weakens trust. The AvailGuard protocol (Section 3.5) may obtain additional evidence after failures or insufficient evidence, but it never lowers θ or removes the consistency and independence requirements. If sufficient evidence cannot be established, TrustANN returns U NVERIFIED. Increasing Kmax therefore provides additional recovery opportunities without allowing evidence from an unrelated shard to satisfy Eq. 8. (5) Recovery is bounded. AvailGuard performs at most Kmax additional retrieval rounds, providing a bounded query-side recovery cost rather than waiting indefinitely for unavailable replicas. Recovery improves availability only when sufficient independent replicas remain available; if all available independent domains for a relevant shard are compromised or unavailable, TrustANN returns U NVERIFIED. TrustANN does not formally guarantee that a T RUSTED result has the same recall as an ideal unpoisoned corpus. Its guarantee concerns the sufficiency and consistency of the observed distributed retrieval evidence under the stated fault model.

Require: Query q, shard j, evidence Eq, j , replica set R j , θ, γ, dmin , Kmax Ensure: Trusted evidence or U NVERIFIED 1: b ← 0 2: repeat 3: Sq, j ← TrustBindSelect(Eq, j , θ, γ, dmin ) 4: if Sq, j satisfies the trust condition then 5: return Trusted(Sq, j ) 6: end if 7: if b ≥ Kmax then 8: return U NVERIFIED 9: end if 10: R′ ← SelectIndependentReplicas(R j , Eq, j ) 11: if R′ = 0/ then 12: return U NVERIFIED 13: end if 14: Eq, j ← Eq, j ∪ Query(R′ ) 15: b ← b+1 16: until false

covery budget and eligible independent replicas remain. If sufficient evidence cannot be established, the affected shard is marked U NVERIFIED, and the query is not labeled globally trusted. Safety boundary. AvailGuard never lowers θ, relaxes the consistency threshold, or removes the independence requirement in order to preserve availability. Its role is limited to finding additional evidence that is structurally independent of the evidence already collected. Thus, recovery improves availability only when sufficient independent replicas remain available; it does not guarantee trusted retrieval under arbitrary failure rates. The resulting guarantee is explicitly bounded by the configured failure-domain model. If the adversary can compromise all available independent domains for a shard, TrustANN cannot establish retrieval trust and returns U NVER IFIED rather than weakening the trust condition.

3.6

3.7

Communication and Performance Model

TrustANN communication consists of three logically separate classes: retrieval, evidence verification, and background coordination. Retrieval traffic includes ANN requests, candidate responses, and bounded AvailGuard fallback rounds. Evidence processing includes authentication, provenance validation, consistency computation, and evidence-set selection. Coordination traffic consists of state-summary requests and responses associated with the CoordShift candidate pool and selected quorum. For a query serving F = |Jq | relevant shards with replication factor r, the initial worst-case response fan-out is

Correctness and Safety Properties

TrustANN deliberately separates coordination properties from query-level retrieval safety. The three protocols described in Sections 3.3–3.5 provide the following system-level properties. (1) Coordination does not determine retrieval trust. The CoordShift protocol (Section 3.4) provides an authenticated, reusable epoch reference but does not provide a Byzantinesafe state certificate. Query-level trust is instead established independently by the TrustBind protocol (Section 3.3); therefore, an adversary-influenced coordination round cannot by itself cause a retrieval result to satisfy Eq. 8. (2) Trust is established independently per shard. The TrustBind protocol (Section 3.3) evaluates evidence separately for every relevant shard. Under the assumed bound in Eq. 4, a corrupted minority within a shard cannot alone satisfy the support threshold, and evidence from another shard cannot compensate for insufficient evidence. (3) Evidence must satisfy consistency and independence.

Bq ≤ Fr,

(13)

when all replicas are contacted. With selective fan-out, the actual cost is determined by the configured initial replica set. If a full replica set is contacted in each recovery round, a theoretical upper bound with Kmax additional rounds is Bq ≤ Fr(1 + Kmax ).

(14)

The implementation normally uses selective recovery, so these expressions serve as worst-case communication bounds rather than measured costs. CoordShift is amortized across queries because its epoch is reused until superseded. Its communication and computation are therefore measured separately from query-path retrieval and evidence processing. This separation enables TrustANN to evaluate three distinct costs: (1) query-level evidence verification, (2) background coordination, and (3) failure-induced 7

recovery. In a distributed deployment, these costs can be measured using actual inter-node communication rather than treating local process execution as a proxy for distributed behavior.

4

related shards to satisfy another shard’s threshold. Recovery terminates after a bounded number of attempts. If sufficient independent evidence cannot be obtained, TrustANN returns Unverified rather than silently weakening the trust condition. Fault injection and deployment. The prototype runs as independent processes on a multi-node AWS cluster, with each worker deployed on a separate EC2 instance and communicating through gRPC. We use Linux traffic control and netem to introduce network delay and loss. The implementation supports crash-stop failures, unreachable replicas, stale epoch references, corrupted retrieval results, and corrupted coordination summaries. These mechanisms allow the evaluation to exercise TrustBind, CoordShift, and AvailGuard under both availability and integrity faults.

Implementation

We implement TrustANN as a middleware layer above an existing distributed ANN index, without modifying the underlying ANN search algorithm. The prototype [30] is implemented in Python and comprises approximately 1.7K lines of code, excluding configuration files and experiment scripts. The system consists of a coordinator and distributed ANN workers connected through gRPC. Each worker hosts a replica of one ANN shard and independently executes the local ANN search. The coordinator implements the query router, TrustBind, AvailGuard, and the asynchronous CoordShift service. Distributed ANN substrate. We use HNSW as the underlying ANN index, with M = 16, e fConstruction = 200, and e f = 64. The ANN layer is unchanged by TrustANN. TrustANN intercepts the retrieval result and attaches compact authenticated evidence identifying the worker, shard, replica, and index epoch. This separation allows TrustANN to operate as a middleware layer over existing ANN implementations. TrustBind implementation. For each query and shard, TrustBind constructs an evidence consistency graph whose vertices represent valid replica responses. Edge weights combine candidate-set overlap and ranking consistency. Rather than solving a maximum-clique problem, we use greedy evidence selection: the initial response is chosen from the mostsupported candidate set, and subsequent responses are added according to their marginal consistency gain while satisfying the configured failure-domain independence constraint. A shard is trusted only when its selected evidence satisfies the configured support threshold, consistency threshold, and failure-domain coverage requirements. Signature and epoch checks are performed before graph construction. CoordShift implementation. CoordShift executes asynchronously and does not participate in the query critical path. At each coordination epoch, a seeded randomized candidate pool is formed, and a diversity-aware selection procedure chooses the coordination quorum. The selection favors distinct configured failure domains before filling the remaining quorum positions. Workers return signed state summaries, from which CoordShift derives the most strongly supported state reference for each shard when a majority exists. The resulting epoch is cached and reused by subsequent queries. A failed coordination round leaves the previously accepted epoch active. AvailGuard implementation. AvailGuard handles unavailable, stale, or conflicting replica evidence. Instead of lowering the TrustBind threshold, it selects additional replicas that maximize independent evidence relative to the already observed responses. Newly obtained evidence is evaluated within its corresponding shard and cannot be pooled with un-

5

Evaluation

We evaluate TrustANN on the Deep10M benchmark [19] using a multi-node AWS deployment. We examine: (Q1) whether TrustBind rejects corrupted retrieval; (Q2) whether CoordShift operates off the query critical path; (Q3) whether AvailGuard maintains trustworthy retrieval under failures; (Q4) the overhead of verification and distributed retrieval; and (Q5) whether failure-domain-aware coordination improves quorum diversity.

5.1

Experimental Setup

Dataset and ANN configuration. All experiments use the Deep10M benchmark [19]. Deep10M contains 10M 96dimensional float32 vectors generated from deep neuralnetwork features. For the multi-node AWS experiments, we use a 100K-vector subset while retaining the original 96dimensional representation and L2 distance. Ground-truth nearest-neighbor results are used to identify retrieval attacks. The data are partitioned across shards and replicated across worker nodes. Each worker maintains a local FAISS HNSW index with M = 16, e fConstruction = 200, and query-time e f = 64. We use these fixed, moderate settings to provide a stable ANN substrate while balancing search quality, construction cost, index size, and query latency [10, 22]. HNSW is used only as the underlying ANN backend for our evaluation. TrustANN’s trust layer is independent of the underlying ANN indexing method and can be deployed above other ANN backends. Unless otherwise stated, the deployment uses three shards with three replicas per shard (r=3), evidence threshold θ=2, fallback budget Kmax =1, and CoordShift quorum size k=9. The same query set and random seeds are used across corresponding configurations. Baselines. For quantitative comparison, we use an Unverified Distributed ANN baseline implemented on the same distributed HNSW substrate, dataset, workload, and AWS deployment as TrustANN, but without retrieval-level verification. This controlled baseline provides an apples-to-apples 8

comparison for measuring the cost and benefit of TrustANN’s query-level trust mechanisms. The systems summarized in Table 1 are not used as direct experimental baselines because they target different system abstractions and provide different verification or coordination semantics. In particular, DistributedANN [1] distributes a single logical DiskANN [13] graph across machines, whereas TrustANN is an indexindependent trust layer evaluated here over replicated HNSW shards. ANNProof [20] and VLAH [29] focus on search/index verification, CD-ANN [37] incorporates Byzantine coordination, and PBFT [9] provides general Byzantine consensus rather than distributed ANN retrieval. Directly reimplementing or integrating these systems would therefore not provide a controlled comparison of TrustANN’s retrieval-trust mechanisms. Testbed. TrustANN is deployed as a multi-node cluster on AWS EC2. A dedicated coordinator hosts the query router, TrustBind verifier, AvailGuard, and CoordShift, while independent EC2 worker instances host replicated ANN indexes. Workers communicate with the coordinator through gRPC, ensuring reported query latency includes distributed communication and coordinator-side verification. Unless otherwise noted, the default deployment consists of three shards with three replicas per shard, utilizing nine worker instances (though separate scale-out experiments expand this up to 144 workers). Fault experiments terminate, isolate, or disable selected workers to emulate crash-stop and Byzantine conditions, and experiments use 100–150 queries per configuration.

5.2

Table 2: TrustBind decision boundary under Byzantine and replica-availability conditions (r=3, 100 queries/configuration). Configuration θ=1 θ=2 θ=3=r θ=2 θ=2

Scenario

Avail/Selected

Trusted

R-ASR

Byzantine only Byzantine only Two honest Minority Byzantine Clean

1/1 1/1 2/2 3/2 3/2

1.000 0.000 0.000 1.000 1.000

1.000 0.000 0.000 0.000 0.000

Table 3: Ablation of TrustBind evidence conditions (100 queries/configuration). Policy Threshold only Threshold + consistency Full TrustBind Full TrustBind, collocated

Selected

C(S)

D(S)

Trusted

R-ASR

2 2 1 1

0.722 0.722 1.000 1.000

1.000 1.000 1.000 1.000

1.000 1.000 0.000 0.000

1.000 1.000 0.000 0.000

the attack but cannot establish trust when only two honest replicas are available. In contrast, θ=2 successfully trusts both clean retrieval and retrieval with a Byzantine minority, with R-ASR = 0.000. Thus, the experiment establishes the configured threshold’s safety and availability boundary. Evidence-condition ablation. We next measure whether simply counting replica responses is sufficient for retrieval trust. We compare three verification policies: threshold only, threshold plus consistency, and the complete TrustBind decision rule. The same Byzantine retrieval attack is applied while the verifier observes the corresponding replica evidence. Table 3 shows that threshold-only verification and threshold-plus-consistency both select two responses and accept the attacked retrieval, producing R-ASR = 1.000. The complete TrustBind policy instead selects an insufficient trusted evidence set and rejects the result. The collocated configuration is likewise rejected. Hence, additional responses alone do not substitute for the complete evidence requirements. This experiment is an ablation of the complete decision rule rather than independent one-factor measurements of consistency and independence. Retrieval integrity. We then directly measure whether TrustANN prevents an attacked retrieval from being reported as trusted. We compare an unverified distributed-ANN baseline, TrustANN with θ=1, and TrustANN with the configured θ=2 under the same single-Byzantine-survivor attack. A clean TrustANN configuration provides a positive control. Table 4 shows that the Unverified ANN accepts the Byzantine survivor for every query, with R-ASR = 1.000. TrustANN with θ=1 exhibits the same behavior, confirming that the threshold is essential to the protection. With θ=2, all attacked queries are rejected and measured R-ASR falls to zero, while the clean configuration remains fully trusted with R-ASR = 0.000. The protected configuration increases p95 latency from approximately 0.52 ms to 1.88 ms because replica evidence must be collected and verified. Cross-shard evidence isolation. This experiment tests

Trustworthy Retrieval

We first evaluate TrustBind’s query-level retrieval decision. The goal is to determine whether a query is marked trusted (successfully satisfying TrustBind’s per-shard evidence conditions) only when sufficient replica evidence is available. We evaluate security using the Retrieval Attack Success Rate (R-ASR), defined as the fraction of attacked queries where a manipulated or fabricated result is incorrectly accepted as trusted. We examine the threshold boundary, the role of the evidence conditions, integrity under a single-Byzantine-survivor attack, cross-shard evidence isolation, and additional retrieval manipulations. Threshold and availability boundary. This experiment measures the safety–availability boundary created by the evidence threshold. We vary θ and the set of available replicas under controlled Byzantine and availability conditions. Pattern A leaves only one Byzantine replica available, while Pattern B provides two honest replicas with one replica unavailable. We additionally test the configured policy under clean and minority-Byzantine conditions. Table 2 shows that with only one Byzantine response available, θ=1 accepts the fabricated result for every query, yielding R-ASR = 1.000. Increasing the threshold to the configured θ=2 rejects the same attack. A stricter θ=3 also rejects 9

Table 4: Retrieval integrity under a single-Byzantine-survivor attack (r=3, 100 queries/configuration).

Table 6: TrustANN under additional retrieval manipulation attacks (150 queries/configuration).

System / Condition

Trusted

R-ASR

p50 (ms)

p95 (ms)

Attack

Condition

p50 (ms)

p95 (ms)

Trusted

R-ASR

Unverified ANN TrustANN, θ=1 TrustANN, θ=2 TrustANN, clean

1.000 1.000 0.000 1.000

1.000 1.000 0.000 0.000

0.445 0.432 1.535 1.523

0.516 0.480 1.885 1.636

Candidate suppression Candidate suppression Ranking manipulation Ranking manipulation

Clean Attack Clean Attack

1.496 1.496 1.496 1.500

1.601 1.616 1.584 1.622

0.000 0.000 0.000 0.000

0.000 0.000 0.000 0.000

Table 7: CoordShift off-path behavior (r=3, fanout= 3, epoch interval = 200 ms).

Table 5: Cross-shard coordinated attack (r=3, θ=2, 100 queries/configuration). Kmax 0 1 2

Trusted rate 0.000 0.000 0.000

R-ASR

Offered QPS

0.000 0.000 0.000

50 100 200 400

whether TrustANN’s recovery mechanism can inadvertently use evidence from an unrelated shard to satisfy the trust requirement of an attacked shard. We apply a coordinated attack to the affected shard and vary the fallback budget Kmax ∈ {0, 1, 2}. As shown in Table 5, the attacked retrieval is never marked trusted and R-ASR remains zero for all fallback budgets. Increasing Kmax therefore does not allow responses from another shard to substitute for missing evidence in the affected shard. This confirms that AvailGuard remains bounded by the per-shard evidence requirement. Additional retrieval manipulation attacks. Finally, we test TrustBind against two additional retrieval manipulations: candidate suppression and ranking manipulation. Candidate suppression removes part of the expected nearest-neighbor evidence, whereas ranking manipulation changes the ordering of returned candidates. Clean and attack conditions use the same queries and deployment. Table 6 shows zero measured R-ASR for both attack types under the configured TrustBind policy. Candidate suppression changes p95 latency from 1.601 to 1.616 ms, while ranking manipulation changes it from 1.584 to 1.622 ms. These experiments therefore provide additional safety tests under retrieval manipulation; the primary clean positive-control evidence remains the integrity experiment in Table 4.

5.3

Observed queries

Query p50

Query p95

Commits

Waits

249 497 750 758

9.277 7.491 6.555 6.507

10.702 9.210 7.993 7.765

24 24 24 24

No No No No

from 50 to 400 QPS. Thus, queries continue using the previously published epoch while CoordShift constructs the next one. The observed query-count plateau at the highest offered load reflects the capacity of the deployed retrieval path rather than a coordination barrier.

5.4

Failure-Resilient Retrieval

We evaluate AvailGuard under progressively increasing replica failures. The experiment measures whether TrustANN can preserve trustworthy retrieval when the initially contacted replicas are unavailable. We uniformly increase the fraction of crashed replicas and record trusted query rate, fallback activation, and query latency. AvailGuard retains θ=2 throughout and attempts to obtain additional independent evidence rather than weakening the trust criterion. Table 8 shows that the trusted-query rate remains 1.000 through the 33% crash configuration, with fallback activated at the nonzero failure levels. At 49% crashed replicas, however, the trusted rate falls to zero because the remaining deployment cannot provide sufficient evidence. Thus, AvailGuard extends retrieval availability by locating additional evidence while preserving the same trust requirement. The lower latency at higher crash rates results from fewer live workers participating in retrieval and should not be interpreted as improved system capacity.

Off-Path Coordination 5.5

We next evaluate whether CoordShift can maintain reusable coordination state without making query processing wait for coordination. The key property being measured is whether epoch construction is asynchronous rather than a synchronization barrier on the retrieval path. We vary offered query load from 50 to 400 QPS while CoordShift constructs epochs at a fixed 200-ms interval. Table 7 shows 24 coordination commits in every load configuration, consistent with the fixed epoch interval. More importantly, no query waits for epoch construction. Query p95 remains between 7.77 and 10.70 ms as offered load increases

Distributed-System Cost

We next quantify the cost introduced by distributed evidence collection and TrustANN’s verification middleware. Query fan-out. This experiment measures how retrieval breadth affects end-to-end query cost. We vary the number of shards contacted by each query from one to three. Since each shard has three replicas, this increases the maximum number of replica responses processed by the coordinator from three to nine. Table 9 shows that increasing fan-out from one to three raises p95 latency from 1.51 to 7.46 ms and median latency 10

Table 8: Failure resilience under uniformly random replica crashes (r=3, θ=2, 150 queries/configuration). Crashed

Table 10: Clean-path performance overhead of TrustANN (150 queries/configuration).

Trusted rate

Fallback

p50 (ms)

p95 (ms)

System

1.000 1.000 1.000 1.000 0.000

0.0% 100.0% 100.0% 100.0% 100.0%

6.631 5.715 5.048 3.899 2.596

7.560 7.141 5.904 4.788 3.260

Unverified ANN TrustANN

0% 10% 20% 33% 49%

1 2 3

Max evidence

Trusted rate

p50 (ms)

p95 (ms)

3 6 9

1.000 1.000 1.000

1.315 3.270 6.583

1.513 4.030 7.455

Workers 18 36 72 144

p95 (ms)

1050.23 966.96

0.909 1.023

1.006 1.100

1

Efficiency

p95 (ms)

908.6 1134.0 1167.0 1176.5

1.000 0.624 0.321 0.162

1.258 1.159 1.436 1.482

ment, and shard migration—while queries continue to arrive. We measure the number of queries served, query errors, query p95 latency, and total reconfiguration time. Table 12 shows zero query errors for all three events. Query p95 remains between 4.38 and 4.65 ms, while measured reconfiguration takes approximately 5 s in each case. These results show that queries continue to complete while state convergence proceeds. Thus, reconfiguration is not implemented as a query-time synchronization barrier. The results do not imply instantaneous convergence; rather, they demonstrate that convergence latency is decoupled from query-path availability.

from 1.32 to 6.58 ms. The maximum evidence set simultaneously grows from three to nine responses. Trusted rate remains 1.000 in all configurations, indicating that the additional latency is associated with distributed retrieval and evidence processing rather than failure to establish trust. Clean-path overhead. We then isolate the end-to-end overhead of the TrustANN middleware under a clean workload. We compare the deployed TrustANN query path with an unverified distributed-ANN baseline using the same deployment and workload. This experiment measures performance overhead rather than retrieval-safety behavior. Table 10 shows that TrustANN achieves 966.96 QPS compared with 1050.23 QPS for the unverified distributed ANN baseline. Median latency increases from 0.909 to 1.023 ms, while p95 increases from 1.006 to 1.100 ms, corresponding to a measured 9.36% p95 increase. These measurements quantify the clean-path cost of adding TrustANN verification and distributed evidence processing. System scaling. To evaluate how the system behaves beyond our baseline topology, we also analyze weak scaling as the cluster size increases. Because this requires expanding the worker topology and data partitioning beyond our default 9worker setup, this experiment utilizes a separate scale-out deployment scaling from 18 to 144 workers (with r = 3 and θ = 2) under a fixed per-worker load. We report aggregate QPS, parallel efficiency, and p95 latency. Table 11 shows that aggregate throughput increases from 908.6 to 1176.5 QPS as the deployment grows from 18 to 144 workers. However, parallel efficiency decreases from 1.000 to 0.162. The results indicate that distributed overheads increasingly limit scaling at larger worker counts. These measurements are reported separately and are not combined with the three-shard, three-replica AWS configuration.

5.6

p50 (ms)

Table 11: Weak scaling on Deep10M at fixed per-worker load (r=3, θ=2; separate scaling deployment).

Table 9: Query fan-out sensitivity (r=3, θ=2, 150 queries/configuration). Fan-out

QPS

5.7

CoordShift Resilience

We finally evaluate whether CoordShift’s failure-domainaware selection changes the structural diversity of its coordination quorum under clustered adversaries. We vary quorum size k, adversarial fraction p, and the placement of adversarial workers across failure domains. The primary metric is domain coverage, defined as the number of distinct configured failure domains represented in the selected quorum. We also report the fraction of rounds whose selected quorum is adversary-influenced. Table 13 shows that diversity-aware selection consistently increases failure-domain coverage. For k=9 and p=0.10, coverage increases from 6.845 with uniform sampling to 9.000 with diversity-aware selection. For k=15 and k=21, diversityaware selection reaches the maximum configured coverage of 12 domains, compared with approximately 9.3–10.7 domains under uniform sampling. The adversary-influence results in Table 13, however, require a narrower interpretation. Diversity-aware selection does not universally reduce the measured fraction of adversary-influenced rounds; in several configurations, the influence rate is higher despite greater domain coverage. Therefore, this experiment demonstrates the structural effect of diversity-aware quorum selection on failuredomain coverage, but does not establish a universal reduction in adversary-influenced epochs. This coordination-layer prop-

Recovery and Reconfiguration

We evaluate whether TrustANN can continue serving queries while the distributed state is being reconfigured. We independently inject three events—replica failure, replica replace11

Byzantine coordination and fault tolerance. BFT protocols and ledgers [7, 9, 15, 36] provide strong replicated agreement but introduce communication and synchronization costs unsuitable for latency-critical ANN queries. More prior work [3–6, 23] similarly explored lightweight consensus, authenticated state, and provenance for trustworthy distributed computing. TrustANN instead separates coordination from retrieval: TrustBind establishes query-level trust from replica evidence, CoordShift maintains reusable epochs asynchronously without consensus on the query path, and AvailGuard preserves the evidence threshold during bounded recovery. Thus, TrustANN determines whether available retrieval evidence is sufficient to trust the result without placing consensus in the ANN query path.

Table 12: Recovery and reconfiguration under continuous retrieval. Values are measured on the current AWS deployment. Event Repl. failure Repl. replacement Shard migration

Queries

Q. errors

Q. p95 (ms)

Reconfig. (ms)

1411 1323 1400

0 0 0

4.496 4.655 4.376

5001.805 5002.630 5000.342

Table 13: CoordShift quorum resilience under clustered adversaries (N=60, 1500 rounds/configuration). Adv.-influenced

Domain coverage

Uniform Diversity-aware Uniform Diversity-aware

0.614 0.666 0.869 0.941

4.353 5.000 4.329 5.000

.10 .10 .30 .30

Uniform Diversity-aware Uniform Diversity-aware

0.827 0.959 0.988 1.000

6.845 9.000 6.862 9.000

15 15 15 15

.10 .10 .30 .30

Uniform Diversity-aware Uniform Diversity-aware

0.951 1.000 0.999 1.000

9.287 12.000 9.310 12.000

21 21 21 21

.10 .10 .30 .30

Uniform Diversity-aware Uniform Diversity-aware

0.993 1.000 1.000 1.000

10.677 12.000 10.749 12.000

k

p

5 5 5 5

.10 .10 .30 .30

9 9 9 9

Sampling

7

TrustANN provides a distributed trust layer for approximate nearest-neighbor (ANN) retrieval that separates query-level retrieval trust from background coordination and failure recovery. T RUST B IND establishes trust from authenticated, consistent, and failure-domain-independent replica evidence on a per-shard basis, while C OORD S HIFT asynchronously maintains reusable coordination epochs without placing coordination on the query critical path. AVAIL G UARD further provides bounded, independence-aware evidence recovery when replicas are unavailable, stale, or conflicting, without lowering the trust threshold or relaxing the consistency and independence requirements. As a result, TrustANN explicitly distinguishes between a retrieval result supported by sufficient distributed evidence and one for which such evidence cannot be established, returning U NVERIFIED rather than weakening the trust decision.

erty is distinct from query-time retrieval safety. Even when an epoch is influenced by adversarial workers, TrustBind independently evaluates the retrieval evidence before marking a query trusted. CoordShift diversity and TrustBind verification therefore serve complementary roles in the system.

6

Conclusion and Future Work

More Related Work

Distributed ANN and verifiable retrieval. Distributed ANN systems such as Milvus [31], CoTra [41], HARMONY [32], DistributedANN [1], DistVS [34], and GaussDB [28] primarily optimize scalability, partitioning, communication, and resource management. Verifiable systems including ANNProof [20], VLAH [29], and CD-ANN [37] further authenticate search or index/vector state. However, these approaches generally do not determine whether distributed shards and replicas provide sufficient independent evidence to trust a retrieval result. TrustANN instead makes the retrieval operation itself the trust boundary and establishes trust at query time. Federated and Byzantine-robust protection. CFedRAG [2], FRAG [40], and RAGRoute [12] address decentralized retrieval and privacy, while RAGuard [16] and PoisonedRAG [42] target malicious retrieved content. Byzantine-robust aggregation [8, 17, 33] and P2P defenses such as SybilGuard and X-Vine [24, 25, 35] protect aggregation or overlay membership. These mechanisms address complementary security dimensions, but do not establish retrieval-evidence sufficiency under replica failures, stale state, or retrieval-time manipulation. TrustANN bases its trust decision directly on authenticated replica evidence.

Our prototype demonstrates that these mechanisms can be implemented as a middleware layer above an existing ANN index without modifying the underlying ANN search algorithm. Experiments on distributed FAISS HNSW deployments show that TrustANN can reject the tested Byzantine retrieval attack while preserving trusted retrieval under the evaluated replica failure conditions, with a 9.36% increase in clean p95 latency. More broadly, the results demonstrate that retrieval-level trust can be established through explicit evidence requirements while keeping global coordination and recovery decoupled from the latency-critical retrieval path. As future work, we will investigate adaptive adversaries, larger-scale and more dynamic failure and reconfiguration scenarios, and stronger retrieval-level guarantees. These directions will extend TrustANN’s evidence-based trust model to increasingly dynamic and adversarial distributed retrieval environments. 12

References

[10] Geon Choi, Hoeun Lee, and Jaeyoung Do. Exploiting structural properties for efficient constraintaware hnsw hyperparameter tuning. arXiv preprint arXiv:2607.04630, 2026.

[1] Philip Adams, Menghao Li, Shi Zhang, Li Tan, Qi Chen, Mingqin Li, Zengzhong Li, Knut Risvik, and Harsha Vardhan Simhadri. Distributedann: Efficient scaling of a single diskann graph across thousands of computers. In Proceedings of the 1st Workshop on Vector Databases, 2025.

[11] Michael T. Goodrich, Roberto Tamassia, and Andrew Schwerin. Implementation of an authenticated dictionary with skip lists and commutative hashing. In Proceedings of the DARPA Information Survivability Conference and Exposition II, 2001.

[2] Parker Addison et al. C-FedRAG: A confidential federated retrieval-augmented generation system. In arXiv preprint arXiv:2412.13163, 2024.

[12] Rachid Guerraoui, Diana Petrescu, et al. Efficient federated search for retrieval-augmented generation. In Proc. 5th Workshop on Machine Learning and Systems (MLSys), 2025.

[3] Abdullah Al-Mamun, Tonglin Li, Mohammad Sadoghi, Linhua Jiang, Haoting Shen, and Dongfang Zhao. Hpchain: An mpi-based blockchain framework for data fidelity in high-performance computing systems. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC’19), Denver, CO, USA, pages 17–19, 2019.

[13] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. Diskann: Fast accurate billion-point nearest neighbor search on a single node. Advances in neural information processing Systems, 32, 2019. [14] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117–128, 2011.

[4] Abdullah Al-Mamun, Haoting Shen, and Dongfang Zhao. Dean: A lightweight and resource-efficient blockchain protocol for reliable edge computing. In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 1261–1271. IEEE, 2022.

[15] Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford. OmniLedger: A secure, scale-out, decentralized ledger via sharding. In IEEE Symposium on Security and Privacy, pages 19–34, 2018.

[5] Abdullah Al-Mamun, Feng Yan, and Dongfang Zhao. Scichain: Blockchain-enabled lightweight and efficient data provenance for reproducible scientific computing. In 2021 IEEE 37th international conference on data engineering (ICDE), pages 1853–1858. IEEE, 2021.

[16] Pushkal Kumar, Tucker Nielson, Tanish Kolhe, Shubham Zala, and Vincent Li. Raguard: A layered defense framework for retrieval-augmented generation systems against data poisoning. preprint, 2026.

[6] Abdullah Al-Mamun and Dongfang Zhao. Echain: Securing electronic device provenance through privacypreserving consortium blockchains. In 2023 53rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks-Supplemental Volume (DSNS), pages 77–83. IEEE, 2023.

[17] De Zhang Lee et al. A practical and secure ByzantineRobust aggregator. arXiv preprint arXiv:2506.23183, 2025. [18] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmented generation for knowledge-intensive NLP tasks. In Advances in Neural Information Processing Systems (NeurIPS), 2020.

[7] Zeta Avarikioti, Eleftherios Kokoris-Kogias, and Roger Wattenhofer. Divide and scale: Formalization of distributed ledger sharding protocols. In arXiv:1910.10434, 2020. [8] Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems (NeurIPS), 2017.

[19] Wenbin Li et al. Zoom: Multi-view online data management for high-performance vector search. Technical report, Microsoft Research, 2018. [20] Lingling Lu, Zhenyu Wen, Ye Yuan, Qinming He, Jianhai Chen, and Zhenguang Liu. Annproof: Building a verifiable and efficient outsourced approximate nearest neighbor search system on blockchain. Future Generation Computer Systems, 156:206–220, 2024.

[9] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation, 1999. 13

[21] Yu. A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824– 836, 2020.

Chengming Chi, Xiaohai Yang, et al. Milvus: A purposebuilt vector data management system. In Proceedings of the 2021 International Conference on Management of Data (SIGMOD), pages 2614–2627. ACM, 2021. [32] Qian Xu, Feng Zhang, Chengxi Li, Lei Cao, Zheng Chen, Jidong Zhai, and Xiaoyong Du. Harmony: A scalable distributed vector database for high-throughput approximate nearest neighbor search. 2025.

[22] Yu A. Malkov and Dmitry A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824–836, 2020.

[33] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In Proc. ICML, 2018.

[23] Abdullah Al Mamun, Feng Yan, and Dongfang Zhao. Baash: Lightweight, efficient, and reliable blockchainas-a-service for hpc systems. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–18, 2021.

[34] Peiqi Yin, Xiao Yan, Shiyuan Deng, Hui Li, Yifan Zhu, Xiangyu Zhi, Jingqi Mao, Ran Xu, Wenliang Zhang, and James Cheng. Distvs: Large-scale vector search with compute-memory disaggregation. In Proceedings of the 23rd USENIX Symposium on Networked Systems Design and Implementation (NSDI), pages 449–467, 2026.

[24] Prateek Mittal, Matthew Caesar, and Nikita Borisov. XVine: Secure and pseudonymous routing using social networks. In Proc. Network and Distributed System Security Symposium (NDSS), 2012.

[35] Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, and Abraham Flaxman. SybilGuard: Defending against Sybil attacks via social networks. In Proc. ACM SIGCOMM, 2006.

[25] Riccardo Pecori. S-Kademlia: A trust and reputation method to mitigate a Sybil attack in Kademlia. Computer Networks, 94:205–218, 2016.

[36] Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. RapidChain: Scaling blockchain via full sharding. In Proc. ACM CCS, pages 931–948, 2018.

[26] Marcel Schmidt et al. Swoop: Top-k similarity joins over set streams. The VLDB Journal, 2025.

[37] Hao Zhang et al. CD-ANN: Scalable approximate nearest neighbor search on client-side devices. Journal of Systems Architecture, 2026.

[27] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. DiskANN: Fast accurate billion-point nearest neighbor search on a single node. In Advances in Neural Information Processing Systems, volume 32, pages 13771–13781, 2019.

[38] Wenjie Zhang, Minqi Zhou, and Xiaofang Zhou. Retrieval-augmented generation (RAG): What is there for databases? SIGMOD Record, 54(4), 2025. [39] Dongfang Zhao. Frag: Toward federated vector database management for collaborative and secure retrievalaugmented generation. 2024.

[28] Yu Sun et al. GaussDB-Vector: A large-scale persistent real-time vector database for LLM applications. Proceedings of the VLDB Endowment, 18, 2025.

FRAG: Toward federated vec[40] Dongfang Zhao. tor database management for collaborative and secure retrieval-augmented generation. arXiv preprint arXiv:2410.13272, 2024.

[29] Yiping Teng, Yuyao Tang, Gang Wang, Shiqing Wang, Changze Li, and Liang Zhao. Vlah: A lightweight and verifiable framework for approximate nearest neighbor search in high-dimensional space. In 2025 IEEE 24th International Conference on Trust, Security and Privacy in Computing and Communications, pages 1608–1616, 2025.

[41] Xiangyu Zhi, Meng Chen, Xiao Yan, Baotong Lu, Hui Li, Qianxi Zhang, Qi Chen, and James Cheng. Cotra: Towards efficient and scalable distributed vector search with rdma. In Proceedings of the ACM on Management of Data, volume 4, 2025.

[30] TrustANN: Failure-Resilient and Verifiable Distributed Approximate Nearest-Neighbor Retrieval. https: //anonymous.4open.science/r/trustann-92DD/, Accessed 2026.

[42] Wei Zou, Runpeng Geng, Binghui Wang, and Jinyuan Jia. PoisonedRAG: Knowledge corruption attacks to retrieval-augmented generation of large language models. In Proc. 34th USENIX Security Symposium, 2025.

[31] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, 14

Related documents

• Failure-Resilient and Verifiable Distributed Approximate Nearest-Neighbor Retrieval#1457762
• KatoANN: Enabling Near-Exact Vector Search at the Speed of Lossy Scans with CPU Matrix Engines#1406565
• KatoANN: Enabling Near-Exact Vector Search at the Speed of Lossy Scans with CPU Matrix Engines#1403304
• Amora: Communication-Efficient Private Approximate Nearest Neighbors Search#1356510
• Amora: Communication-Efficient Private Approximate Nearest Neighbors Search#1348787