ReliabilityRAG: Effective and Provably Robust Defense for RAG-based Web-Search
Zeyu Shen, Basileal Imana, Tong Wu, Chong Xiang, Prateek Mittal, Aleksandra Korolova
Retrieval-Augmented Generation (RAG) enhances the capabilities of Large Language Models by grounding their outputs in external documents. These systems, however, remain vulnerable to attacks on the retrieval corpus, such as prompt injection. RAG-based search systems (e.g., Google’s Search AI Overview) present an interesting setting for studying and protecting against such threats, as the defense algorithms could benefit from built-in reliability signals — such as document ranking, and represent a non-LLM related challenge for the adversary thanks to decades of work to thwart SEO. Motivated by, but not limited to, this scenario, this work introduces ReliabilityRAG, a framework designed for adversarial robustness that explicitly leverages reliability information of retrieved documents.Our first contribution adopts a graph-theoretic perspective to identify a "consistent majority" among retrieved documents in an effort to filter out malicious ones. We introduce a novel algorithm based on finding Maximum Independent Set (MIS) on a graph of documents in which edges encode contradiction relationships. Our MIS variant explicitly prioritizes higher-ranked or higher-reliability documents during selection and provides provable robustness guarantees against bounded adversarial corruption under natural assumptions. Recognizing the computational cost of exact MIS for large retrieval sets, our second contribution is a general and scalable weighted sample and aggregate framework. It explicitly utilizes reliability information of the retrieved documents, preserving some robustness guarantees while efficiently handling many documents. We present empirical results showing that ReliabilityRAG provides superior robustness against adversarial attacks compared to prior methods, maintains high benign accuracy, and excels in long-form generation tasks where prior robustness-focused methods struggled. Our work represents a significant step towards more effective and provably robust defenses against retrieved corpus corruption in RAG.