💬 NLP

Rule-Based Explanations for Retrieval-Augmented LLM Systems

This paper proposes a novel framework for generating if-then rules to explain Retrieval-Augmented Generation (RAG) systems by linking retrieved information sources to model outputs, utilizing Apriori-inspired optimizations to efficiently overcome the computational challenges of brute-force source combination testing.

Original authors: Joel Rorseth, Parke Godfrey, Lukasz Golab, Divesh Srivastava, Jarek Szlichta

Published 2026-03-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Joel Rorseth, Parke Godfrey, Lukasz Golab, Divesh Srivastava, Jarek Szlichta

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 have a super-smart robot librarian (a Large Language Model, or LLM) who can answer almost any question. But this robot has a secret: it doesn't just rely on its own memory. When you ask it a question, it first runs to a library, grabs a handful of books (retrieved documents), reads them, and then answers you. This is called RAG (Retrieval-Augmented Generation).

The problem? Sometimes the robot gives you a weird, wrong, or even dangerous answer. You might ask, "Why did you say that?" and the robot just says, "Because I read the books." But which books? And did one specific book trick the robot?

This paper introduces a new way to figure out exactly which books (or pieces of information) are causing the robot to behave a certain way. They call these "If-Then Rules."

The Core Idea: The "Recipe" Analogy

Think of the robot's answer like a cake. The "ingredients" are the documents the robot found.

The Old Way (Feature Attribution): This is like looking at the cake and saying, "Flour contributed 30%, sugar 20%, and eggs 10%." It gives you a score, but it doesn't tell you what happens if you remove an ingredient.
The New Way (Rule-Based Explanations): This is like a recipe card that says: "IF you include the 'Bad Spice' (Document X) AND the 'Confusing Herb' (Document Y), THEN the cake will taste terrible."

The authors want to find these "Recipe Cards" automatically. They want to know: "Which specific combination of documents forces the robot to give a wrong answer?"

How They Do It: The "Taste-Tester" Game

To find these rules, you could theoretically test every possible combination of books. If you have 10 books, there are over 1,000 combinations! Testing them all one by one would take forever.

The authors invented a smart game called the Rule Miner. Here is how it works, using a Lattice (a fancy pyramid) analogy:

The Pyramid of Combinations: Imagine a pyramid where the top is "All 10 books together" and the bottom is "No books at all." Every layer in between represents a different mix of books.
The "Bad Taste" Test: The team defines a "Bad Taste" (like a wrong medical diagnosis or a hallucinated fact).
The Smart Pruning (The Magic Trick):
- They start at the top of the pyramid (all books). They test the mix.
- If the mix tastes GOOD: They know that any smaller mix taken from this group might also taste good. They keep digging down.
- If the mix tastes BAD: This is the key. If a specific group of books causes a bad answer, then any group that includes those books will also cause a bad answer.
- The Pruning: Instead of testing every single smaller combination that includes those "bad books," the algorithm says, "We already know this whole branch of the pyramid is bad! We don't need to test the children of this branch." It cuts off huge chunks of the pyramid, saving massive amounts of time.

They have two versions of this miner:

Mono Miner: Looks for one type of rule at a time (e.g., "What causes a bad answer?").
Dual Miner: Looks for two types at once (e.g., "What causes a bad answer?" AND "What causes a good answer?").

Real-World Examples from the Paper

1. The Medical Doctor Scenario
Imagine a doctor asks the robot, "What's the best treatment for Long COVID fatigue?"

The robot pulls up 5 medical articles.
The robot says, "Take Calcium Supplements!" (This is wrong and dangerous).
The Rule Miner runs its game. It discovers a rule: "IF Article 2 (a blog post) AND Article 4 (a forum rumor) are in the mix, THEN the robot recommends Calcium."
The Result: The hospital knows exactly which two articles to remove or fix to stop the robot from giving dangerous advice.

2. The "Red Team" Security Scenario
Imagine a security team trying to hack a robot. They have 50 "poisoned" documents designed to trick the robot into revealing a secret code.

Testing all combinations of 50 documents is impossible (it would take years).
The Rule Miner uses a "Divide and Conquer" strategy. It groups the 50 documents into 2 big piles. It tests them. It finds the bad pile. It splits that pile in half. It keeps splitting until it finds the exact two documents that, when combined, hack the system.
The Result: They found the specific "exploit" pair in minutes instead of years.

Why This Matters

Actionable: Unlike other methods that just give you a "score," this tells you exactly what to change. "Remove Document X."
Guaranteed: The rules are 100% certain. If the rule says "If X is present, the answer is wrong," it always happens. No guessing.
Efficient: By using their "pruning" trick, they can solve problems that would otherwise take a supercomputer weeks to figure out.

The Bottom Line

This paper gives us a detective tool for AI. Instead of just saying, "The AI is confused," it allows us to say, "The AI is confused specifically because it read these two documents together." It turns a black box into a transparent system where we can see exactly which ingredients are spoiling the cake.

1. Problem Statement

Retrieval-Augmented Generation (RAG) systems enhance Large Language Models (LLMs) by injecting dynamic, external knowledge sources at inference time. While this improves factual accuracy, it complicates provenance: understanding why an LLM generated a specific output based on a specific combination of retrieved documents.

Existing Explainable AI (XAI) methods face limitations in this context:

Feature Attribution (e.g., LIME, SHAP): Provides scores for input importance but is not actionable (cannot easily suggest how to change the input to alter the output).
Counterfactual Explanations: Identify minimal input changes to alter an output but can generate an overwhelming number of valid counterfactuals, confusing end-users.
Citations: Often prone to hallucination and lack rigorous guarantees.

The paper addresses the gap in providing actionable, guaranteed, and concise explanations for RAG systems using if-then rules that link the presence or absence of specific retrieved sources to specific model outputs.

2. Methodology

The authors propose a novel framework for mining Rule-Based Explanations for black-box RAG systems.

A. Rule Formulation

The framework defines rules based on feature ablation (retaining or omitting specific RAG sources).

Input: A prompt $x$ is split into a context $c$ (fixed instructions/question) and a source set $s = \{s_1, ..., s_n\}$ (retrieved documents).
Output Predicate ( $O$ ): A user-defined function (e.g., an "LLM-as-a-judge") that returns 1 if the model output $y$ meets a target condition (e.g., "contains misinformation" or "is factually correct").
Rule Types:
1. Retention Rule: "If sources $s' \subseteq s$ are retained, then the output satisfies $O$ ."
2. Omission Rule: "If sources $s' \subseteq s$ are omitted, then the output satisfies $O$ ."
Validity: A rule is valid (100% confidence) if the output predicate holds for all possible combinations of sources that satisfy the antecedent condition. This creates a recursive validity structure where a rule's validity depends on its ancestors in the power set lattice.

B. Search Algorithms

The search space is the power set of the source set $s$ , forming a lattice of size $2^{|s|}$ . To avoid brute-force evaluation of all $2^{|s|}$ combinations, the authors propose two optimized algorithms inspired by the Apriori algorithm but redefined for exact rule validity rather than frequent itemsets.

Mono Rule Miner:
- Mines a single type of rule (either retention or omission) in one pass.
- Technique: Uses a top-down Breadth-First Search (BFS) with Dynamic Programming and Early Termination.
- Pruning: If a subset is found to be invalid (the predicate fails), all its descendants (subsets that retain/omit even fewer/more items) are immediately pruned because they cannot be valid.
- Complexity: Space complexity is reduced to $O(\binom{|s|}{\lfloor |s|/2 \rfloor})$ by caching only two levels of the lattice at a time.
Dual Rule Miner:
- Mines both retention and omission rules simultaneously in a single pass.
- Technique: Uses a "mask representation" to interpret the same subset in two ways (as a retention set for one predicate and an omission set for the other).
- Pruning: A node is pruned only if it is invalid for both rule types.
- Efficiency: More efficient than running two separate Mono passes, especially for smaller source sets, though it sacrifices some pruning power compared to Mono.

C. Scalability Strategy for Large $|s|$

When the number of sources $|s|$ is large (e.g., >10), the exponential complexity becomes intractable. The paper proposes a Divide-and-Conquer strategy:

Group sources into coarse-grained batches.
Mine rules on these groups.
Discard groups not implicated in valid rules.
Recursively split the remaining groups until the original granularity is reached.

3. Key Contributions

First Rule-Based Framework for RAG: Introduces the first formal definition and mining algorithm for rule-based explanations specifically tailored to RAG systems, distinguishing between "retention" and "omission" rules.
Efficient Mining Algorithms: Develops Mono and Dual miners that utilize recursive validity definitions and lattice pruning to significantly reduce the number of LLM inference calls required compared to brute-force approaches.
Actionable Insights: Provides a mechanism to identify specific document combinations that cause hallucinations, biases, or factual errors, enabling database curators to flag or remove problematic sources.
Empirical Validation: Demonstrates the approach through qualitative case studies (healthcare misinformation, AI safety red-teaming) and quantitative benchmarks (HotpotQA).

4. Experimental Results

A. Efficiency and Pruning

Pruning Effectiveness: In the HotpotQA dataset (with up to 10 sources), the Mono miner pruned up to 50% of nodes for retention rules and 70% for omission rules compared to a naive brute-force approach.
Dual vs. Mono: The Dual miner avoids re-evaluating nodes when searching for both rule types, achieving near 100% efficiency relative to a single pass, whereas running Mono twice would require ~200% of the lattice exploration.
Scalability: The system is tractable for $|s| \le 10$ (typical for RAG top-k retrieval), finding all rules in minutes. For larger sets, the divide-and-conquer approach successfully identified minimal rules with significantly fewer calls than exhaustive search.

B. Case Studies

Healthcare (Long COVID): The system identified that retaining specific documents ( $D_2$ and $D_4$ ) consistently caused the LLM to recommend ineffective treatments, despite those documents being individually insufficient to cause the error. This allowed experts to flag specific sources for revision.
AI Safety (Red Teaming): In a scenario with 50 adversarial sources, the divide-and-conquer strategy identified a minimal pair of sources that, when combined, successfully bypassed safety filters (prompt injection), whereas individual sources did not.

C. Robustness

LLM Stochasticity: Experiments with temperature $T=1.0$ showed that despite answer variance, majority voting over samples allowed the extraction of "exact" rules with high precision and recall.
LLM-as-a-Judge: The secondary LLM used to judge output consistency achieved 98.89% precision and 100% recall against human expert validation, proving reliable for defining the output predicate.

5. Significance and Impact

Actionability: Unlike feature attribution, these rules provide clear, binary conditions ("If you remove Document X, the error disappears") that developers and auditors can act upon immediately.
Trust and Safety: The framework offers a rigorous method to audit RAG pipelines for misinformation, bias, and security vulnerabilities (e.g., prompt injection), ensuring that LLMs remain faithful to clinical or safety guidelines.
Theoretical Advancement: It bridges the gap between association rule mining (Apriori) and modern LLM explainability, adapting classical data mining concepts to handle the non-deterministic nature of generative AI through recursive validity and pruning.

In conclusion, this paper establishes a foundational methodology for making RAG systems transparent and controllable by translating complex model behaviors into simple, verifiable if-then rules derived from the provenance of retrieved data.