Imagine you fail a driving test for three independent reasons: bad parallel parking, running a stop sign, and a broken tail light. The examiner says "you ran a stop sign" — true! — and you study intersections for a month. You retake the test and fail again because of the other two. The examiner gave you a correct reason but useless advice. This paper formalizes that gap for LLM-generated explanations of denied requests and calls the missing property "recourse validity." The committed claim: when a rule system denies a request for multiple independent reasons, a single correct reason almost never constitutes valid recourse — and standard LLM correctness checks (whether computed or judged by another LLM) cannot distinguish true-but-useless explanations from true-and-actionable ones. The authors prove this with a hitting-set argument: if k independent rules each deny the request, citing fewer than k reasons leaves at least one blocker standing. The prediction falls directly out of the policy structure, no learning required. Seven rule systems were ported from real-world access control policies and US benefit eligibility rules. In six of seven, a single correct reason provided valid recourse in almost no cases when multiple rules applied simultaneously. This is not a model failure — it is a structural property of multi-rule denial. The paper then tests 20 LLMs across these systems, measuring whether correctness-focused evaluation (asking "is this reason true?") can detect the recourse gap. The answer: close to chance. The hitting-set argument predicts exactly this — correctness is orthogonal to recourse when multiple independent blockers exist. One evaluation strategy does work: asking a strong judge model whether acting on the explanation would actually change the outcome. This recourse-oriented evaluation significantly outperforms correctness checks. But the ceiling matters. Stronger and reasoning-capable models do better, yet still fail on many denials involving four or more independent reasons. The combinatorial burden of enumerating all blockers grows with k, and no model tested achieves reliable recourse for high-k denials. Architecturally, this is a formal-methods paper dressed in LLM evaluation clothing. The core machinery is combinatorial: hitting sets over Boolean rule conjunctions, computed exactly from the policy. The LLM evaluation is the empirical layer on top. The paper does not propose a new model or fine-tuning regime — it proposes a new evaluation criterion (recourse validity) and shows that the standard criterion (correctness) is structurally insufficient. One practical intervention tested: asking for every applicable rule rather than just one. This helps every open model with room to improve, though it does not close the gap entirely. The integrity regime is solid for a formalization paper. The seven rule systems come from published access-control and eligibility benchmarks, not invented toy examples. The hitting-set prediction is a mathematical argument, not an empirical claim — it either holds or it doesn't, and the experiments confirm it does. Twenty LLMs is a broad sweep. The main limitation the authors acknowledge is that real-world eligibility systems are more complex than the ported rule sets, and human studies of people acting on recourse are absent. The practical implication is sharp: if you are building systems that use LLMs to explain denied benefits, loan applications, or access requests, checking whether the explanation is correct is not enough. You must check whether acting on the explanation would change the outcome. This reframes the entire evaluation paradigm for explainable AI in high-stakes decision systems. The gap between correctness and recourse is not a bug in any particular model — it is a structural feature of multi-reason denials that no amount of model scaling will fix without changing what you ask the model to do.
The analogy
You fail a driving test for three reasons; the examiner names one true reason. You fix that one, retake the test, and fail again. The reason was correct. The advice was useless. This paper proves that gap is structural, not accidental, whenever multiple independent rules deny a request.
Driving test
Examiner cites one true failure reason out of three; fixing it alone doesn't pass you
Multi-rule denial
LLM cites one true blocking rule out of k; fixing it alone doesn't flip the decision
Honest assessment
This is a sharp formalization paper that identifies a real and underappreciated gap: LLM explanations of denied requests can be perfectly correct yet completely useless for getting a different outcome. The hitting-set argument is clean and the 20-model evaluation is thorough. What's missing — human studies and production deployment — is exactly what you'd expect from a single-author formal-methods contribution. If you build systems that explain denials to people, this paper should change how you evaluate those explanations. If you're a model developer, the finding that 'ask for every rule' helps is immediately actionable.
What Is CLAIMS?
70
/ 100
BedrockNews applies a structured analytical framework called CLAIMS to academic papers and technical research releases.
How CLAIMS worksClaim
4/5
Ladder
4/5
Architecture
3/5
Integrity
3/5
Milestone
3/5
Successor
4/5
What is this paper actually committing to?
Genuine new criterion. Recourse validity is formalized and proven structurally distinct from correctness — not an incremental benchmark improvement but a reframing of what 'good explanation' means for rule-based denials.
The field fight
Are LLM-generated explanations of automated decisions trustworthy enough for real-world deployment?
Side A
Correctness is the right criterion — if the explanation names a true reason, it's a good explanation
Held by: Most XAI evaluation benchmarks, faithfulness literature
Side B
Correctness is insufficient — explanations must enable actionable recourse, not just cite true facts
Held by: Algorithmic recourse community, this paper
Milestone tracker
Unlocks: Evidence that recourse-valid explanations actually improve denied applicants' outcomes
Current
20
LLMs evaluated
this paper
Next
1
real deployment + human study
production eligibility system
~1-3 years if adopted by government agency or fintech
Verified Facts (6)
In six of seven rule systems ported from access control and US benefit eligibility, a single correct reason almost never gives recourse when several reasons apply
Across 20 LLMs, checks of whether the cited reasons are correct are close to chance at spotting this failure
A strong judge asked whether acting on the explanation would work does spot it
Stronger and reasoning models do better but still fail on many denials with four or more independent reasons
Asking for every rule helps every open model with room to improve
A hitting-set argument predicts from the policy alone when a correct reason fails
Practical Implications (4)
Systems explaining denied benefits, loans, or access requests should evaluate explanations by recourse validity (would acting on this flip the decision?), not just correctness (is the cited reason true?)
Prompting LLMs to list all applicable blocking rules, not just one, measurably improves recourse for open models
Standard LLM-as-judge correctness checks are near-chance at detecting useless-but-true explanations — recourse-oriented judge prompts significantly outperform
Denials with 4+ independent blocking rules remain hard for all tested models including reasoning-capable ones — plan for human review in high-k cases
More latest news
Read all