When Relevance Is Not Enough: Minimal Support Recovery for Faithful RAG Reasoning

Abstract

Retrieval-augmented generation (RAG) can make large language model outputs more traceable by conditioning generation on retrieved evidence. However, retrieving relevant-looking evidence is not the same as retrieving the complete support needed for reasoning. In multi-step reasoning tasks, a retriever may return rules that overlap with the query while missing intermediate dependencies required to justify the answer. We study this problem through retrieval-augmented minimal support recovery. We build RAG-style Horn-clause corpora with symbolically verified minimal supports, distractors, and hard negatives, allowing us to separately evaluate the true support S∗, the retrieved evidence ${\hat R_k}$, and the generator-selected support $\hat S$. We compare BM25, naive and validated graph retrieval, and oracle controls under strict and expanded retrieval budgets. Under strict budgets, BM25 often retrieves substantial partial proof support but fails support-complete retrieval beyond easy settings. Validated graph retrieval closes this gap when explicit dependency structure is available. Under expanded budgets, the complete proof is often retrieved alongside distractors, but generators may still underuse the evidence, over-abstain, or fail because of output truncation. A small ProofWriter pilot shows a similar qualitative tradeoff in controlled natural-language rule reasoning. Our results show that support-complete retrieval is necessary but not sufficient for faithful RAG reasoning: faithful reasoning requires both retrieving the complete dependency support and correctly utilizing it during generation. These findings motivate evaluating retrieval completeness and evidence utilization as distinct but interconnected components of trustworthy RAG systems.