PaperlayerView exact revision on arXiv

Source-linked AI summary

Coverage Is Not Containment: A Fundamental Limit of Admission-Time Defenses Against Coordinated Poisoning of Vector Retrieval

Prashant Kumar Pathak, Tarun Kumar Sharma

arXiv:2608.16044v1cs.CRcs.CLcs.IR

TL;DR

Coordinated poisoning can evade ingestion-time defenses by making individually benign documents jointly capture a target query. The paper formalizes and measures this indistinguishability, finding that retrieval-time demand provides an effective detection signal instead.

  • Problem

    RAG vector stores are a security boundary, yet evidence is limited on whether ingestion-time defenses contain coordinated attacks targeting specific queries.

  • Method

    The paper formalizes attack cones and proves an indistinguishability limit for ingestion-blind defenses, then evaluates learned admission detectors and a demand-aware retrieval-time detector.

  • Results

    No ingestion-time defense reliably separates coordinated attack cones from legitimate topic uploads, while the retrieval-time detector catches 100% of attacks at a 1% false-positive rate.

  • Takeaways & Limitations

    Defending coordinated poisoning requires moving beyond admission-time geometry to signals such as retrieval-time demand.

  • Takeaways & Limitations

    The indistinguishability result is scoped to ingestion-blind defenses, and extending it to all encoders and benign-ingestion models remains future work.

Abstract

from arXiv · show

Retrieval-augmented generation (RAG) answers a question by retrieving passages from a vector store and trusting them as context, so anyone who can add documents can try to steer the answer. A recent, appealing defense filters poisoning at ingestion, rejecting any document that behaves like a hub. We show it -- and every ingestion-time filter -- is defeated by a coordinated adversary that injects a handful of individually unremarkable documents which together surround one target query and seize its top-k (on BGE-large / BEIR, m=10 documents take 10/10; 9.9/10 on a live HNSW index). The attack is not theoretical. Realized as ordinary fluent text and run end-to-end through a BGE-large + HNSW + Qwen2.5-7B pipeline, it makes the generator emit the attacker's planted claim in 88% of targets, versus 0% without the injection. And no admission-time defense stops it: at ingestion an attack cone is geometrically identical to a legitimate niche upload, so -- measuring this directly -- the strongest trained classifier, given every feature and thousands of examples, separates the two no better than chance, catching 4.2% of attacks at a 1% false-positive rate. We prove this limit for the entire class of ingestion-time statistics (any decision from documents and reference queries alone), and it reproduces -- and worsens -- across two corpora and five encoders. The one signal that separates an attack from legitimate niche ingestion -- a query's demand -- is invisible before retrieval, which is also the escape: a retrieval-time detector that observes demand catches 100% of the attacks at the same 1% false-positive rate. Coverage of the query space by an admission gate is not containment of coordinated poisoning; robust defense must move past the front door, to demand.

I. INTRODUCTION

The paper shows that coordinated poisoning defeats admission-time defenses: individually admissible documents can jointly seize a target query’s retrieval, while no ingestion-time statistic based only on documents and sentinels can reliably distinguish the attack from legitimate niche ingestion. Because the separating signal is retrieval-time demand, effective defense must observe retrieval rather than rely solely on admission.

  • Attack and limitation: A coordinated adversary injects individually quiet documents that together dominate one target query’s top-k retrieval.Per-document gates catch loud hubs, but coordinated documents can each evade rejection while jointly surrounding a peripheral target query.
  • Attack and limitation: 10 documents seize 10/10 top-k results on BGE-large / BEIR and 9.9/10 on a live HNSW index.The attack uses documents in a tight cone around the target query and can be realized as fluent text that evades a perplexity filter.
  • Attack and limitation: 4.2% recall at 1% FPR is achieved by the strongest trained classifier distinguishing attacks from location-matched legitimate uploads.The paper states that this no-better-than-chance separation is a fundamental limit for the entire class of ingestion-time statistics.
  • Constructive escape: 100% of attacks are caught at 1% FPR by a retrieval-time detector, versus 4.2% by the best admission-time detector.Retrieval-time demand provides the distinguishing signal unavailable before retrieval.
  • Systems implications: ∼10% of insert latency is the cost of the collective defense, while a per-shard view misses bursts split across shards.The systems results motivate global consistency for detection.

II. BACKGROUND AND RELATED WORK

The section situates the work within RAG poisoning, retrieval defenses, hubness, and adaptive security evaluation. It frames the contribution as showing that coordinated poisoning defeats admission-time defenses while motivating retrieval-time protection.

  • RAG security and corpus poisoning: RAG poisoning exploits trusted retrieved passages to steer generation, extending from targeted corpus attacks and backdoors to indirect prompt injection and broader data-poisoning research.
  • Defenses against retrieval poisoning: Defenses span ingestion and retrieval, but the paper argues that ingestion-time filtering cannot withstand coordinated poisoning at acceptable false-positive rates.Retrieval-time approaches include robust aggregation and certifiable defenses designed to prevent a minority of poisoned passages from dominating.
  • Hubness: Hubness research includes reduction methods and adversarial hubs, while the attacked admission gate specifically targets broad hubs retrieved across many queries.
  • Admission-time control and its geometry: The paper contrasts a global reverse-kNN admission gate for broad hubs with coordinated poisoning that defeats the entire class of ingestion-time defenses.The prior gate attributes its effectiveness to embedding anisotropy and uses sentinel queries with a single global threshold.

III. THREAT MODEL AND PROBLEM FORMULATION

The paper models a vector-retrieval system with an admission gate and a white-box adversary that coordinates admitted documents to seize a target query’s top-k results. The attack requires only write access and approximately k short passages, with evaluation using BGE-large on four BEIR collections under a 1% false-positive-rate gate.

  • System: The vector store retrieves the top-k documents by cosine similarity between unit-normalised document embeddings and the query.The k-th largest corpus similarity, sk(q), is the threshold for entering a query’s top-k.
  • Admission gate: The admission gate admits a candidate only when its reverse-kNN hub rate h(d) falls below θ, calibrated to a benign false-positive rate of ϕ = 1%.The gate compares candidate similarity against per-sentinel k-th-nearest-neighbor thresholds.
  • Adversary: A white-box adversary injects m documents and maximizes the number of attacker-held slots in a target query’s top-k while requiring every document to satisfy h(di) < θ.A covert document is admitted and seizes a slot; success means seizing a large fraction of k.
  • Threat realism and cost: Seizing an entire target top-k requires only m ≈k short passages, and the cost is independent of corpus size.The threat assumes injection through partially open indexed sources such as wikis, forums, crawled pages, uploads, tickets, and knowledge bases.
  • Evaluation setup: The primary evaluation uses BGE-large-en-v1.5 with D=1024 on four BEIR collections containing 10,200 grounded queries and n=5,570 sentinels, with k=10 and θ frozen at 1% FPR.Results average five random seeds and report 95% confidence intervals using Student-t.

IV. THE COORDINATED POISONING ATTACK · A. Single-document feasibility and its geometry · B. The coordinated multi-slot attack

A single document can evade admission-time filtering when it targets a peripheral query, while a coordinated cone of individually admissible documents scales this weakness to seize the entire top-k context. The attack exploits retrieval geometry: documents remain quiet to the gate yet highly similar to the target query.

  • A. Single-document feasibility and its geometry: The most aggressive single poison is d ≈ q∗, which maximizes similarity to the target and requires no optimization.Whether this document is admitted is determined by the embedding geometry.
  • A. Single-document feasibility and its geometry: A central query makes d = q∗ loud and detectable, whereas a peripheral query makes it quiet and admissible.Under anisotropy, hub rate equals the fraction of sentinels within the target query’s retrieval neighbourhood, so poisoning is feasible where coverage is weakest.
  • A. Single-document feasibility and its geometry: 50.6% of 10,200 target queries are directly poisoned by a single admitted document.Admissibility is 60.9% for low-centrality queries versus 38.4% for high-centrality queries, with centrality–hub-rate rank correlation +0.21.
  • A. Single-document feasibility and its geometry: A small off-axis shift restores admissibility for central targets, with median smallest admitting β = 0.20.The construction is d(β) = normalize(q∗ − βµ).
  • B. The coordinated multi-slot attack: The coordinated attack places m documents in a tight cone around q∗, using an admissible off-axis base plus small lateral perturbations.Each document has cosine ≈ 0.98 to q∗, exceeding the top-k bar sk(q∗) ≈ 0.68, so documents occupy distinct slots while remaining as quiet as the base.
  • B. The coordinated multi-slot attack: m = 10 seizes 10/10 top-k slots, with 9.96 ± 0.03 over five seeds and 99% all-admissible.Slots scale linearly with the budget: m = 1→1, m = 3→3, and m = 5→5.
  • B. The coordinated multi-slot attack: The coordinated attack is uniform across peripheral and central queries, with the tiny median β∗ = 0.05 handling central queries.Consequently, the per-document gate provides essentially no protection against coordinated targeted poisoning.

C. Text realizability · D. Poisoning a real index · E. End-to-end output harm

The coordinated attack survives realization as ordinary text, captures retrieved context in a live HNSW index, and propagates through RAG to make the generator emit a planted claim.

  • C. Text realizability: 0.771 mean cosine to the target was achieved by text-realized documents, which poisoned 92% of targets individually and evaded the gate 67% of the time.HotFlip-through-BGE optimized token sequences whose embeddings aligned with q∗; the resulting documents were non-fluent but valid and ingestible.
  • C. Text realizability: The embedding-space attack survived text constraints, demonstrating that coordinated poisoning remains realizable with valid documents.The realized documents were generated by optimizing token sequences through BGE and reached the target directions despite their known non-fluency.
  • D. Poisoning a real index: 9.9/10 of the actually retrieved top-k documents were attacker-controlled in a live HNSW index, with a median of 10 and at least half retrieved for 100% of targets.The experiment used a 100,000-document corpus and ruled out brute-force search as the explanation for coordinated poisoning.
  • E. End-to-end output harm: 10/10 of the retrieved context was seized by fluent attack documents that each passed the per-document gate.The end-to-end pipeline used a BGE-large retriever over the 100,000-document HNSW index and Qwen2.5-7B-Instruct.
  • E. End-to-end output harm: The attack documents were relevant to a single query rather than broad hubs, yet poisoning propagated through admission, retrieval, and the model’s answer.The canary never appeared in the clean baseline, establishing that the emitted claim was attributable to the injection.

V. COLLECTIVE ADMISSION CONTROLS · A. Near-duplicate-burst statistic · B. The adaptive game

Because attack documents are individually admissible, collective admission controls examine admitted streams rather than isolated documents. A near-duplicate statistic catches tight cones, but adaptive widening creates a middle-band evasion window that still seizes the entire top-k.

  • V. COLLECTIVE ADMISSION CONTROLS: 1% benign false-positive rate is used to calibrate every collective statistic against bulk uploads of M legitimate same-topic documents.The confound represents a routine ingestion event.
  • V. COLLECTIVE ADMISSION CONTROLS: Collective examination is necessary because each attack document is individually admissible.The defense therefore evaluates the admitted stream rather than documents in isolation.
  • A. Near-duplicate-burst statistic: 100% recall is achieved against the naive attack by mean cosine to the top-C co-admitted documents at 1% FPR.For tight cones with δ=0.10, mutual cosine is approximately 0.99 and the statistic scores far above a legitimate topic batch.
  • A. Near-duplicate-burst statistic: δ=0.10 produces a tight cone whose documents are mutually very similar.The statistic sim(d) is defined as the mean cosine from document d to its top-C co-admitted documents.
  • B. The adaptive game: δ ≤0.30 is caught by both the per-document gate and the burst statistic.The adaptive adversary widens the cone, lowering mutual similarity and sim(d).
  • B. The adaptive game: δ ≈0.4–0.7 evades both defenses while each document retains cosine ≈0.92 to q∗ and covertly seizes the entire top-k.This middle band forms a clean evasion window.
  • B. The adaptive game: δ=1.0 eventually removes the documents from the top-k.The attack succeeds only across an intermediate widening range rather than with arbitrarily wide cones.

C. A retrieval-side co-retrieval statistic · VI. A PERSISTENT FUNDAMENTAL LIMIT · A. The defender frontier

Retrieval-side co-retrieval statistics reduce coordinated poisoning but leave a persistent covert residual. Tightening thresholds eliminates that residual only at a degenerate 100% benign false-positive rate, while the residual persists across attack and retrieval settings.

  • C. A retrieval-side co-retrieval statistic: Wide-cone documents evade document-similarity checks by co-activating a shared sentinel neighbourhood around the target query.The co-retrieval statistic is defined from shared-sentinel incidences across other documents.
  • C. A retrieval-side co-retrieval statistic: 10/10 to 4.5 ± 0.4/10: the combined defense leaves a covert residual over five seeds.Similarity catches tight cones, while co-retrieval catches most of the wide burst; δ≈0.55–0.70 survives.
  • VI. A PERSISTENT FUNDAMENTAL LIMIT: The persistent residual remains across every achievable benign FPR up to 10%.The 4.5 ± 0.4/10 residual holds at each mapped operating point through 10% benign FPR.
  • A. The defender frontier: 100% true benign FPR: the residual vanishes only when the co-retrieval threshold flags any sentinel sharing.That degenerate threshold flags all legitimate same-topic batches.
  • A. The defender frontier: m documents seize min(m, k) top-k slots, with m=2, 4, 6 seizing 2, 4, 6 slots and m ≥k saturating.The covert residual scales with this linear seizure relationship.
  • A. The defender frontier: 0.44 per-slot fraction at deployed k=10: the residual holds across k ∈{5, 10, 20, 50}.The result is not tuned only to the deployed retrieval depth.
  • A. The defender frontier: 0.44→0.88 of the top-k: reducing sentinels from 5,570 to 1,114 raises the residual as the collective statistics weaken.More sentinels help but never close the attack.

B. A scoped indistinguishability limit

The paper formalizes a scoped indistinguishability limit for ingestion-time defenses that decide from co-admitted documents and sentinels without observing target queries or user demand. Within this class, coordinated attack batches can be indistinguishable from legitimate same-topic batches, while retrieval-time demand and provenance defenses remain outside the bound.

  • Scope: The proposition is scoped to ingestion-blind defenses and does not constrain defenses that observe retrieval-time demand or document provenance.Those defenses are not functions of the co-admitted batch and sentinels and therefore escape the bound by construction.
  • Defense scope: The defense class D uses only co-admitted document embeddings and sentinels, excluding target queries and topic demand at ingestion time.Both the per-document gate and collective statistics belong to D.
  • Indistinguishability: Proposition 1 states that every D ∈D induces a batch test whose attack recall and legitimate-ingestion false-positive rate are constrained by attack–legitimate batch overlap.The proposition fixes batch size m and compares coordinated attack batches with legitimate same-topic batches.
  • Indistinguishability: Near-identical batch laws force ingestion-time defenses toward recall ≤ FPR, preventing both recall→1 and FPR→0 unless maximal overlap stays below 1.Equivalently, the minimum total variation distance must be large enough to separate the distributions.

C. Why the overlap is near-total: the geometry · D. Can a learned detector separate them?

The geometry makes a coordinated adversarial cone near a peripheral query indistinguishable at ingestion from a legitimate same-topic niche upload because demand has not yet been observed. A learned detector confirms this limit: it performs at chance on location-matched uploads, catching only 4.2% of attacks at a 1% false-positive rate.

  • C. Why the overlap is near-total: the geometry: ρ ≈1 for any D ∈D because a wide adversarial cone and a legitimate same-topic bulk upload are geometrically identical to ingestion-time defenses.Both appear as mutually similar documents converging on a direct direction near a peripheral query.
  • C. Why the overlap is near-total: the geometry: A defense in D cannot use whether real users demanded the topic, because that demand is unavailable at ingestion.Thus, coverage of the query space by an admission gate is not containment.
  • D. Can a learned detector separate them?: Proposition 1 reduces separability to the overlap ρ, while the strongest learned classifier provides an upper bound on every ingestion-time statistic.A classifier two-sample test uses separating advantage as a lower bound on TV(Aδ, B).
  • D. Can a learned detector separate them?: AUC 1.00 separates attacks from natural-location content, but this comparison only distinguishes peripheral from central locations.The meaningful benign comparison must be location-matched because admissible attacks occupy sentinel-under-covered directions.
  • D. Can a learned detector separate them?: AUC 0.46 separates attacks from location-matched admissible uploads, which is chance.The same chance result holds against random, tightest, and low-coverage niche topics only when comparing natural locations; location-matched uploads remain indistinguishable.
  • D. Can a learned detector separate them?: 4.2% of attacks are caught at a 1% false-positive rate, while legitimate uploads are flagged at 3.8%, the same rate.The classifier therefore cannot distinguish coordinated attacks from legitimate admissible niche uploads.

E. Generalisation · F. The residual persists across encoders

The attack and persistent residual generalize to a second corpus and worsen there, showing the limit is not corpus-specific. Across five encoders spanning approximately 12× anisotropy, the combined-defense covert residual remains substantial rather than disappearing toward isotropy.

  • E. Generalisation: 89.9% (vs. 50.6%) single-document admission reproduces on a second, compositionally distinct general-web corpus and is worse there.The corpus also yields a 7.8 ± 0.4/10 (vs. 4.5 ± 0.4/10) combined-defense residual across five seeds.
  • E. Generalisation: The second corpus offers the adversary more peripheral directions despite being more isotropic and broadly sampled.This supports the conclusion that the limit is not an artefact of one corpus.
  • F. The residual persists across encoders: The encoder sweep spans a ≈12× anisotropy range, measured by mean pairwise query cosine from 0.061 to 0.740.The independently rebuilt pipeline includes MiniLM-L6, BGE-base, BGE-large, GTE-large, and E5-large.
  • F. The residual persists across encoders: The near-total overlap and persistent limit are regularities of anisotropic retrieval geometry rather than artifacts of BGE-large.The pipeline re-encodes the corpus, queries, and sentinels independently for each encoder.
  • F. The residual persists across encoders: 7.6–9.3/10 residual stays across five encoders spanning a ≈12× anisotropy range and does not shrink toward the isotropic end.The figure reports the same cross-encoder persistence as the five-encoder sweep.
  • F. The residual persists across encoders: 7.6 to 9.3/10 combined-defense covert residual persists across all five encoders.Each encoder was evaluated over five seeds at a fresh 1%-FPP operating point.

VII. SYSTEMS CONSIDERATIONS · VIII. DISCUSSION

The admission gate is lightweight but operationally constrained, and sharding creates a blind spot unless admissions have a globally consistent view. The discussion concludes that ingestion-blind defenses cannot contain coordinated poisoning, motivating provenance and retrieval-time demand signals while acknowledging adaptive failures and responsible deployment.

  • VII. SYSTEMS CONSIDERATIONS: ∼10% of HNSW insert time is the measured cost of computing collective statistics, 0.29 ms versus 2.97 ms per admitted document.The overhead is independent of corpus size N, adding fixed per-write cost as the store scales.
  • VII. SYSTEMS CONSIDERATIONS: A batch-dependent admission decision requires buffering, which adds write latency, or asynchronous evaluation, which creates a bounded exposure window.Sharding sharpens this latency-versus-exposure trade-off.
  • VII. SYSTEMS CONSIDERATIONS: ≤1 attack document per shard makes a per-shard collective defense blind to a distributed burst; detection therefore requires a globally consistent admission view.A global view catches the tight cone, whereas a per-shard view does not.
  • VIII. DISCUSSION: No ingestion-time filter, whether per-document or collective, contains coordinated poisoning because an adversarial cone is indistinguishable from legitimate topic demand at ingestion.The proposed alternatives are provenance or source trust and retrieval-time anomaly detection.
  • VIII. DISCUSSION: 4.2% of attacks are caught at a 1% false-positive rate by the strongest ingestion-blind detector, versus 100% by a retrieval-time detector at the same rate.The comparison uses a fair benign stream that includes legitimate fresh uploads.
  • VIII. DISCUSSION: Recency and demand concentration supply retrieval-time signals absent from document-and-sentinel tests, distinguishing recent clusters retrieved by few workload queries from legitimate fresh uploads.The detector combines the fraction of a query’s top-k ingested recently with how few distinct workload queries retrieve the same fresh cluster.
  • VIII. DISCUSSION: The retrieval-time escape weakens under genuine organic demand, but adversaries can target popular queries, distribute payloads, inject slowly, or manufacture demand synthetically.The passage frames the escape as not a finished defense and calls for robust temporal demand modeling.
  • VIII. DISCUSSION: Admission-style hubness filters should not be relied upon against targeted or coordinated poisoning and should be paired with provenance and retrieval-time controls.The attacked defense is described as a research proposal, and no turnkey exploit is released.

IX. LIMITATIONS · X. CONCLUSION

The indistinguishability limit applies to ingestion-blind defenses where adversarial and legitimate embeddings substantially overlap, while coordinated poisoning remains individually admissible. The conclusion is that containment requires moving beyond admission time.

  • IX. LIMITATIONS: Proposition 1 is scoped to the class D of ingestion-blind defenses.Its strength depends on near-total overlap between adversarial and legitimate distributions.
  • IX. LIMITATIONS: Near-total overlap is expressed as maxδ ρδ = 1 − minδ TV(Aδ, B) being near one, equivalently minδ TV≈0.The paper establishes this overlap empirically and argues for it geometrically.
  • IX. LIMITATIONS: The overlap remains near-total across the anisotropy spectrum in the five-encoder sweep.Residual performance ranges from 7.6–9.3/10 across the least- to most-anisotropic encoder.
  • X. CONCLUSION: An admission gate can stop broad hubs but cannot contain a coordinated, low-amplitude adversary targeting one query.The attack uses individually admissible documents rather than a broad hub.
  • X. CONCLUSION: The adversarial cone and a legitimate topic batch share the embedding anisotropy used by the gate.This makes their failure geometric rather than statistical.
  • X. CONCLUSION: No ingestion-time observer separates the adversarial cone from legitimate topic batches at an acceptable false-positive rate.The conclusion therefore directs defenses beyond admission time.
Loading 2608.16044v1…