Backward Distrust for Multi-Hop RAG Under Compromised Sources

When a language model answers a question whose evidence is scattered across several documents — "where was the director of this film born?" — modern systems do not fetch everything at once. They work step by step: retrieve a document, learn the director's name, use that name as a new search query, retrieve again. This iterative style, called multi-hop retrieval-augmented generation (RAG), fixes one problem but creates another: every retrieved passage is added to a growing context and treated as true. If one intermediate passage is lying, every later step is built on the lie, and the system has no mechanism to look back and ask which document caused the failure.

At the same time, security research has documented that attackers deliberately place malicious content on trusted infrastructure — compromised subdirectories of legitimate websites, reputable cloud providers, corporate link shorteners — precisely because reputation filters trust those hosts. And attackers bury their payloads deep in redirect chains, on average 6.94 hyperlink hops from any reputable starting point, beyond the crawling depth of security scanners. The uncomfortable observation motivating this proposal is that iterative RAG is a deep crawler. A multi-hop RAG system happily follows exactly the kind of long, trusted-prefix chains that attackers have already optimized to defeat security scanners — and then it quotes the payload as fact. No prior work has measured this collision, and no existing defense operates inside the reasoning loop where the damage happens.

Core Claim

The claim is threefold. First, multi-hop RAG systems are structurally more vulnerable to compromised-infrastructure poisoning than one-shot RAG, because a single false intermediate "bridge fact" hosted on a high-reputation source cascades through all downstream hops — a failure mode that Chain-of-Retrieval Augmented Generation documents for accidental noise but that no one has studied under a deliberate adversary. Second, existing defenses cannot help here, because they all operate outside the loop: domain reputation is exactly the signal the attacker exploits, and per-passage content detectors miss poisons that are individually innocuous. Third, the fix is to invert the direction of the pipeline: when a downstream verification fails, propagate distrust backward through the session's provenance record to the passage that supplied the poisoned premise, evict it, and re-retrieve. This transplants the key idea of DOITRUST: Dissecting On-chain Compromised Internet Domains via Graph Learning — which pushes distrust backward from suspicious leaf nodes to reputable referrers on a static web graph — from an offline domain classifier into the live reasoning loop of a RAG system, where it needs no labeled malicious corpus and no web-scale crawl.

Threat Model and Attack Benchmark

The adversary controls one or more passages on high-reputation hosting: a compromised subdirectory of a legitimate CMS, a cloud-storage bucket, or content reachable through a corporate shortener. This is realistic on all three counts. DeltaPhish: Detecting Phishing Webpages in Compromised Websites shows embedded phishing pages on reputable domains survive for weeks because scanners refuse to flag the benign root; Characterizing the Networks Sending Enterprise Phishing Emails found, across 4 billion enterprise emails, that over one-third of successfully delivered phishing originates from highly reputable networks such as Amazon and Microsoft, which cannot be blocklisted without breaking business communication; and Misdirection of Trust: Demystifying the Abuse of Dedicated URL Shortening Service found 22 of 88 corporate shorteners (25%) could be abused to route users to arbitrary destinations, yielding 16 CVEs. Crucially, the poisoned passage contains no injection instructions and no malicious keywords — it is simply a plausible false statement that answers an intermediate sub-query. This mirrors the per-step innocuousness that makes StepJack: Benchmarking Computer-Use Agent Safety Against Multi-Step Indirect Prompt Injection so effective (its attack success rate on GPT-5.4-mini rose from 41.7% for a monolithic payload to 72.9% when split across three innocuous steps), but transposed from GUI agents and instruction injection to RAG pipelines and factual poisoning — a setting StepJack explicitly leaves open.

We will build the first benchmark for this threat by extending three existing corpora. The base is MultiHop-RAG: Benchmarking Retrieval-Augmented Generation for Multi-Hop Queries, whose news corpus has real source attribution and four query types (inference, comparison, temporal, and null queries that test abstention), supplemented with MuSiQue: Multi-hop Questions via Single-hop Question Composition and 2WikiMultihopQA for controlled 2–4 hop chains. For a sampled fraction of test questions we generate adversarial bridge documents that answer an intermediate sub-query falsely, tag them with high- versus low-reputation host labels, and vary three attack parameters: which hop is poisoned (early hops should hurt more, given the cascading failure documented by CoRAG), whether the false premise is split across two individually-plausible documents (StepJack-style decomposition, $k=1$ vs $k=2$), and whether the poison also offers a shortcut answer that lets the model skip the genuine verification chain — inverting the DiRe disconnected-reasoning exploit that MuSiQue introduced, under which a single-paragraph model scores 64.8 F1 on HotpotQA but only 32.0 on MuSiQue. The headline metric is Attack Success Rate: the fraction of poisoned questions whose final answer matches the adversary's intended target.

Defense: Backward Distrust in the Retrieval Loop

The defense instruments an ordinary iterative loop — either IRCoT-style interleaving from Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions or CoRAG-style sub-query prediction — with two additions. The first is a provenance log: a directed graph $G_t$ whose nodes are retrieved passages and whose edge $p \to q$ records that a sub-answer derived from passage $p$ generated the query that retrieved passage $q$. The second is a set of cheap verification signals that fire at hop $t$: contradictory premises across retrieved passages, a failed one-step lookahead (the same device GRAT: Guiding Retrieval-Augmented Reasoning through Process Rewards Tree Search uses for valuing reasoning branches), disagreement between tree-search branches, or a null-query abstention trigger. When a signal fires, the flagged terminal nodes $F_t$ launch backward distrust propagation with per-hop decay $\lambda$:

$$\delta_t(p) \;=\; \sum_{q\,:\,p\,\to\,q\,\in\,G_t} \lambda\,\big(\mathbf{1}[q \in F_t] \;+\; \delta_t(q)\big), \qquad s_t(p) \;=\; 1 - \min\!\big(1,\;\delta_t(p)\big)$$

where $s_t(p)$ is the retained trust in passage $p$ after hop $t$. Passages whose trust falls below threshold are evicted from the context bank, their derived sub-answers are retracted, and the loop re-retrieves with the retracted premise masked. Two design choices matter. Priors are uniform: unlike DOITRUST, which initializes from known-bad labels and a crawled domain graph, we assume no labeled malicious corpus, because a per-session mechanism must work against content that has never been seen by any blacklist — the dynamic-evasion weakness DOITRUST itself acknowledges. And distrust is deliberately not persisted into a permanent blocklist, since a rehosted copy of the same lie on a fresh high-reputation page must be caught again by reasoning, not by lookup; this addresses the coarse domain-granularity problem that Minimizing Trust Leaks for Robust Sybil Detection and Unleashing the power of indirect attacks against trust prediction via preferential path identify in graph-based trust systems, where attackers siphon trust through reputable intermediaries without touching the target directly.

Research Program

The program has three parts. Part one builds the poisoned benchmark described above and measures raw vulnerability: attack success rate for one-shot RAG versus iterative RAG versus tree-search RAG, as a function of poisoned hop position, host reputation, and decomposition depth. Our hypothesis is that iterative systems amplify poisoning relative to one-shot retrieval, because a poisoned premise is reused as a query and thus contaminates retrieval itself, not just generation — the cascading mechanism CoRAG observed with noise, now under an adversary that targets it. Part two implements backward distrust propagation on top of both an IRCoT-style loop and a GRAT-style tree search, and measures recovery: accuracy under poisoning, regression on clean corpora, and compute overhead (the provenance graph has at most tens of nodes per question, so propagation itself is negligible next to retrieval). Part three settles an open question from the file that cuts both ways: does tree search resist poisoning because it explores alternative branches, or does it enlarge the attack surface because it issues many more retrieval queries and thus encounters compromised nodes more often? GRAT's own ablation shows removing retrieval entirely drops performance by over 20%, so retrieval exposure is the dominant term; we will measure attack success rate as a function of branching factor, with and without distrust pruning at each node.

Baselines

The "do nothing" reference point is an unmodified iterative RAG pipeline — IRCoT-style interleaving or CoRAG-style sub-query prediction — run on the poisoned corpus with no defense, giving the raw attack success rate that any defense must reduce. Its clean-corpus performance anchors the comparison: on MultiHop-RAG, GPT-4 achieved 0.56 answer accuracy with retrieved chunks and 0.89 with gold evidence, and dense retrieval topped out at 0.7467 Hits@10, so there is a large accuracy headroom between what retrieval delivers and what the evidence supports, and a defense must not spend that headroom. All systems in every comparison use the same corpus, the same base model, the same retrieval index and top-$k$ budget, and the same tuning budget (grid search over each method's own hyperparameters, equal total trials), so improvements cannot come from better retrieval or more compute.

The strongest existing competitor is the DOITRUST pipeline of DOITRUST: Dissecting On-chain Compromised Internet Domains via Graph Learning, Personalized IncredulityRank plus decoupled graph neural networks, rerun as a pre-retrieval corpus filter: we build the corpus's host-and-link graph, give it the same small labeling budget it was designed for (it reached over 90% detection accuracy with under 1% labeled nodes on a 1.7-million-node graph, with a 94.55% true-positive rate under expert review), and drop passages it scores as malicious before they enter the index. It is the strongest competitor because it is the only published method that detects multi-hop compromise via backward distrust at all. Beating it means higher poisoned-passage detection recall at a matched false-positive rate on legitimate passages from the same hosts — and we expect the decisive gap to appear exactly on multi-tenant, high-reputation hosting, where a domain-level score cannot act and a session-level mechanism can.

A second baseline is an external per-passage detector — a prompt-injection or malicious-content classifier applied to every retrieved chunk before it enters the context, the deployment StepJack tested, where a detector caught monolithic malicious prompts 56% of the time but degraded sharply once attacks were split into innocuous sub-steps. We rerun this on our factual poisons, which contain no instructions at all, to quantify how much of the threat per-step screening can and cannot cover. Finally, two ablations isolate the proposal's key ingredient: the full defense minus backward propagation (a static uniform-trust pipeline with eviction only on direct flags, showing whether tracing through intermediate hops matters) and the full defense plus a domain-reputation prior on $s_0$ (testing whether reputation helps as a soft signal once it is no longer the only signal). A third ablation on the tree-search variant — branching with versus without distrust pruning — isolates the Gap-4 question. Beating the baselines means recovering at least half the accuracy drop caused by early-hop poisoning while regressing clean-corpus accuracy by no more than one point.

Why not just…?

Why not just use a bigger, more capable model to notice the contradiction? The evidence says scale does not close this gap. On MultiHop-RAG, GPT-4 scored only 0.56 with retrieved chunks versus 0.89 with gold evidence — the bottleneck is what enters the context, not model capacity; and IRCoT showed a 3B model with interleaved retrieval beats a 175B model with one-shot retrieval, so architecture dominates scale on multi-hop tasks. More pointedly, StepJack found more capable agents were more vulnerable to decomposed attacks, with success rates roughly doubling under three-step decomposition. Still, this is a genuine threat to the proposal: a frontier model with strong internal consistency checking might catch a false bridge premise unaided, which would shrink the defense's value. Our experiments therefore include frontier-model runs across all decomposition depths; if a large model resists $k=2$ poisoning without any defense, we will report it and reposition the defense for the smaller open models that most deployed RAG systems actually use.

Why not just filter untrusted domains before retrieval? This is precisely the heuristic the attack exploits, and the file's evidence rules it out on every axis. Over one-third of delivered enterprise phishing already comes from Amazon and Microsoft ranges that cannot be blocklisted; 25% of corporate shorteners route trusted domains to arbitrary destinations; DeltaPhish documents that blocking a compromised reputable root causes unacceptable collateral damage; and DOITRUST's 6.94-hop average burial depth sits beyond every production scanner's crawl budget, so pre-computed reputation is stale or absent exactly where the poison lives. The honest caveat is that a soft reputation prior could still add signal, which is why the reputation-prior ablation exists: if adding domain reputation to the initial trust $s_0$ materially improves recovery without letting high-reputation hosts mask accrued distrust, we will fold it in — but as one input among many, never as the gate.

Why not just run a content detector on each retrieved passage? StepJack already measured this: detectors caught monolithic malicious prompts 56% of the time and failed on individually innocuous sub-steps, because a detector with no memory of earlier hops cannot see that a mundane statement completes an adversarial chain. Our factual poison is an even harder case for per-step screening — a false bridge fact on a reputable news-style page contains nothing any classifier trained on injection or malware patterns would flag; the only evidence of wrongdoing is the downstream contradiction, which by construction appears after the damage would be done. The detector baseline in our experiments will make this quantitative rather than rhetorical: if some detector does catch decomposed factual poisons at acceptable false-positive rates, the proposal's contribution narrows to the attribution-and-recovery component, and we will say so in the results.

Decisive Checks

The proposal stands or falls on four numbers. First, the amplification curve: attack success rate versus poisoned-hop position for one-shot, iterative, and tree-search RAG — if iterative systems are not more vulnerable than one-shot, the threat model weakens and the defense is solving a smaller problem than claimed. Second, recovery: accuracy under early-hop poisoning with and without backward distrust propagation, where recovering at least half the drop at no more than one point of clean-corpus regression across MultiHop-RAG, MuSiQue, and 2WikiMultihopQA (on which GRAT with Llama3-70B reports 75.2% accuracy, the clean-corpus ceiling our stack should approach) would support the core claim. Third, the granularity test against the DOITRUST-as-filter baseline: matched-recall comparison at equal false-positive rate on legitimate passages hosted on the same multi-tenant domains as the poison. Fourth, the attribution check: among sessions where the defense fires, the fraction in which the evicted passage is actually the planted poison, verified against the benchmark's ground-truth poisoning labels — because a defense that evicts the wrong passage is just a slower way of failing. Together these checks either establish that a per-session, backward-looking distrust mechanism is the missing piece for RAG operating on live web infrastructure, or they bound exactly how far reasoning-time defense can go before infrastructure-level coordination becomes necessary.