The Faithfulness Gap: Evaluating Dependency Faithfulness in LLM Reasoning via Minimal Support Recovery

Abstract

Current evaluations of logical reasoning in large language models (LLMs) often conflate correct answer prediction with correct logical derivation. We formalize dependency-faithful reasoning: given facts, rules, and a query, a model must output both an entailment label and the rule identifiers forming the minimal support for the conclusion. We instantiate this objective in propositional Horn-clause systems and evaluate it using a controlled positive-entailment benchmark of 1,350 instances across 27 structural regimes varying proof depth, support width, and graph noise, with each instance having a unique minimal support. Across six instruction-tuned models, we observe a persistent Faithfulness Gap (∆): models can achieve high positive-instance entailment accuracy while recovering substantially less of the required dependency structure. A mixed incomplete-support validation set further shows that recovering support when a proof exists does not always imply reliable rejection when required rules or source facts are missing. These results suggest that answer correctness alone can overestimate reasoning reliability. We also find that stronger dependency recovery can introduce measurable deployment overhead through increased token usage, observed end-to-end API latency, and sensitivity to inference budgets. In particular, constrained token budgets can cause Reasoning Stall, where reasoning-tuned models consume the budget before emitting a valid final support set. Overall, this work argues that trustworthy LLM reasoning should be evaluated not only by final-answer correctness, but also by faithful and efficient recovery of verifiable supporting structure.