🤖 AI

ReliabilityRAG: Effective and Provably Robust Defense for RAG-based Web-Search

This paper introduces ReliabilityRAG, a framework that leverages document reliability signals and graph-theoretic algorithms, specifically a reliability-prioritized Maximum Independent Set approach and a scalable weighted sampling method, to provide provably robust defenses against corpus corruption in Retrieval-Augmented Generation systems while maintaining high accuracy.

Original authors: Zeyu Shen, Basileal Imana, Tong Wu, Chong Xiang, Prateek Mittal, Aleksandra Korolova

Published 2026-02-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zeyu Shen, Basileal Imana, Tong Wu, Chong Xiang, Prateek Mittal, Aleksandra Korolova

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a Chef (the AI) trying to cook a delicious, accurate meal (the answer) for a customer. To do this, you don't just rely on your memory; you ask a Librarian (the Search Engine) to bring you a stack of cookbooks (documents) from the library that might have the recipe you need.

This is how RAG (Retrieval-Augmented Generation) works. It makes AI smarter by giving it fresh, external information.

The Problem: The Saboteur in the Library

The problem is that the library isn't perfectly secure. A Saboteur (the hacker) has snuck in and planted fake, misleading cookbooks right on the shelves.

If the Librarian grabs a fake book from the top of the pile (the most trusted spot), the Chef might read it and serve a poisoned meal.
If the fake book is buried at the bottom, the Chef might ignore it, but if the Librarian grabs too many books, the fake one might still slip in.

Existing defenses are like a Chef who just reads all the books and tries to guess the truth by counting how many say "salt" vs. "sugar." But if the fake books are written very cleverly, the Chef gets confused and serves a bad meal.

The Solution: ReliabilityRAG

The authors of this paper, ReliabilityRAG, propose a smarter way for the Chef to handle the stack of books. They introduce two main ideas:

1. The "Truth Detective" Game (The Graph Method)

Imagine the Chef lays out the top 10 books on the table.

Step 1: The Chef reads each book individually and writes down a short summary of the recipe.
Step 2: The Chef acts as a Truth Detective. They compare every summary against every other summary.
- "Book A says 'Add salt.' Book B says 'Add sugar.' These contradict!" -> Mark them as enemies.
- "Book C says 'Add salt.' Book D says 'Add salt.' They agree." -> Mark them as friends.
Step 3: The Chef builds a Friendship Map (a graph). Friends are connected; enemies are not.
Step 4: The Chef looks for the Biggest Group of Friends who all agree with each other and none of them are enemies. This is called the "Maximum Independent Set."

The Secret Sauce: The Chef knows that books at the top of the stack (from the Librarian's top results) are usually more trustworthy. If there are two groups of friends that are the same size, the Chef picks the group that includes the top-ranked books.

Why it works: The Saboteur can only plant a few fake books. Even if they try to trick the Chef, the fake books will likely contradict the many real books. The "Biggest Group of Friends" will naturally be the group of real books, leaving the fake ones out in the cold.

2. The "Tasting Spoon" Method (Sampling for Huge Libraries)

What if the Librarian brings 50 or 100 books? Checking every single pair of books to see who is friends with whom takes too long (like trying to introduce every person at a massive wedding to everyone else).

So, the Chef uses a Sampling Strategy:

Instead of reading all 100 books, the Chef picks a small handful (say, 2 books) to taste.
Crucial Twist: The Chef is more likely to pick books from the top of the stack because they are more reliable. It's like picking the freshest ingredients first.
The Chef repeats this tasting process 20 times, creating 20 small groups.
Finally, the Chef combines the results from these 20 groups to make the final decision.

This is fast, efficient, and still very hard for the Saboteur to fool because the fake books are usually at the bottom of the stack and rarely get picked.

Why This Matters

It's Provably Robust: The math shows that as long as the Saboteur doesn't control more than half the books (which is very hard to do in real search engines), the Chef will almost always pick the truth.
It Keeps the Good Stuff: Unlike older methods that might throw away good information just to be safe, this method keeps the high-quality, trusted documents, so the answers remain accurate even when no one is attacking.
It Handles Long Stories: It works great even when the Chef needs to write a long biography, not just a short fact.

The Bottom Line

ReliabilityRAG is like giving the AI a smart filter that doesn't just blindly trust the first result or blindly distrust everything. Instead, it cross-checks the information, looks for contradictions, and heavily favors the sources the search engine already told us are the most reliable. It turns a chaotic pile of potentially fake news into a clear, trustworthy answer.

1. Problem Statement

Retrieval-Augmented Generation (RAG) systems, which combine Large Language Models (LLMs) with external document retrieval (e.g., Google Search AI Overview), are vulnerable to adversarial attacks on the retrieval corpus.

Threats: Attackers can poison the corpus via Corpus Poisoning (injecting false facts) or Prompt Injection (embedding instructions to hijack the LLM's output).
Limitations of Existing Defenses: Current robust RAG frameworks (e.g., RobustRAG) often rely on simple majority voting over retrieved documents. These methods suffer from:
- Information Loss: Reducing free-form natural language to keywords or token probabilities discards context.
- Poor Scalability: They struggle with long-form generation tasks.
- Ignored Reliability Signals: They treat retrieved documents as an unordered set, ignoring the fact that search engines provide reliability signals (e.g., ranking, PageRank) which are difficult for adversaries to manipulate for high-ranking positions.

2. Methodology: ReliabilityRAG

The authors propose ReliabilityRAG, a defense framework that explicitly leverages document reliability signals (rank or weights) to filter malicious documents before generation. The framework operates in two settings:

A. Ordinal-Reliability Setting (Rank-Based)

This approach assumes the retriever provides an ordered list of documents ( $x_1 \succeq x_2 \succeq \dots \succeq x_k$ ), where $x_1$ is the most reliable.

Core Algorithm: Maximum Independent Set (MIS) on a Contradiction Graph.
1. Isolated Answering: The LLM generates an answer for each retrieved document individually.
2. Contradiction Graph Construction: A graph $G=(V, E)$ is built where vertices are documents. An edge exists between two documents if a Natural Language Inference (NLI) model detects a contradiction between their isolated answers.
3. Rank-Aware Selection: The algorithm finds the Maximum Independent Set (MIS) (the largest subset of mutually non-contradictory documents).
  - Tie-Breaking: If multiple MISs exist, the algorithm selects the one with the smallest lexicographic order of indices. This explicitly prioritizes higher-ranked (more reliable) documents.
4. Generation: The LLM generates the final answer using only the documents in the selected MIS.
Theoretical Guarantee: Under bounded corruption assumptions (adversary can only corrupt a small fraction of documents) and reasonable NLI error rates, the probability of selecting a malicious document vanishes exponentially as the number of retrieved documents increases.

B. Cardinal-Reliability Setting (Weighted)

For scenarios with large retrieval sets (e.g., $k=50+$ ) where exact MIS is computationally expensive ( $O(2^k)$ ), the authors propose a Weighted Sample and Aggregate framework.

Mechanism:
1. Weighted Sampling: Documents are sampled with replacement based on their reliability weights (e.g., exponential decay based on rank).
2. Context Generation: For each sample (context), an intermediate answer is generated.
3. Aggregation: The intermediate answers are aggregated. The aggregator can be the MIS algorithm itself (applied to the sampled subset) or other robust aggregation functions.
Benefit: This scales the robustness guarantees to large document sets while maintaining high utility.

3. Key Contributions

Novel Graph-Theoretic Defense: Introduced a method to find a "consistent majority" using MIS on a contradiction graph, explicitly prioritizing high-reliability documents.
Provably Robust Guarantees: Provided theoretical proofs showing that the MIS-based approach is robust against bounded adversarial corruption, provided the NLI model performs within specific error bounds.
Scalable Framework: Developed a weighted sample-and-aggregate framework that extends these guarantees to large-scale retrieval scenarios where exact MIS is infeasible.
Comprehensive Evaluation: Demonstrated that the method outperforms state-of-the-art baselines (RobustRAG, AstuteRAG, InstructRAG) in both benign accuracy and adversarial robustness, particularly in long-form generation tasks.

4. Experimental Results

The authors evaluated ReliabilityRAG on four datasets (RealtimeQA, NaturalQuestions, TriviaQA, and a Biography generation dataset) using three LLMs (Mistral-7B, Llama3.2-3B, GPT-4o-mini).

Benign Performance: ReliabilityRAG maintained high accuracy on clean data, significantly outperforming RobustRAG (which often degrades in benign scenarios due to information loss) and matching or exceeding AstuteRAG and InstructRAG.
Adversarial Robustness:
- Prompt Injection & Corpus Poisoning: ReliabilityRAG showed superior resilience. For example, in long-form biography generation, it maintained high scores (~~71-73) under attack, whereas RobustRAG dropped significantly (~~53).
- Rank Awareness: The system demonstrated that attacks on lower-ranked documents (e.g., position 10 or 50) were less successful than attacks on top-ranked documents, confirming the framework effectively leverages reliability signals.
- Graceful Degradation: As the number of attacked documents increased, ReliabilityRAG's performance degraded more gracefully compared to baselines, which often collapsed rapidly.
Latency: The overhead introduced by the "isolated answering" and NLI steps was minimal (typically <1 second per query on modern hardware), making it practical for real-world deployment.

5. Significance

Bridging the Gap: ReliabilityRAG addresses a critical gap in RAG security by utilizing built-in reliability signals (like search rankings) that adversaries find difficult to manipulate. This creates a "defense-in-depth" strategy.
Long-Form Generation: Unlike previous robust methods that struggled with complex, long-form outputs, ReliabilityRAG excels in these tasks, making it suitable for advanced search applications like AI Overviews.
Theoretical Foundation: The work provides the first provable robustness guarantees for RAG systems that incorporate document reliability, moving beyond heuristic defenses.
Practicality: The framework is modular and can be integrated into existing RAG pipelines without requiring retraining of the LLM, offering a practical path toward more trustworthy AI search systems.