Catching Advice That Asks People to Change What They Cannot

Language models are increasingly used as advisors: "What would I need to change to get this loan approved?", "How could I qualify for this trial?" A good answer names actions the person can actually take. A bad answer tells them to be five years younger, to have no prior default, or to be a different sex. Researchers who study algorithmic recourse, meaning the actions that would flip an unfavorable automated decision, have long made such advice impossible by construction. Their methods freeze "immutable" features such as age, ethnicity, or past records while searching for the smallest change that flips the decision. Retrieval-augmented generation (RAG) works differently: a model looks up relevant documents and writes an answer conditioned on them. RAG has no equivalent safeguard. It can retrieve a policy or a case history that describes someone with different fixed traits, and it can then produce advice that the retrieved text fully supports but that is impossible for the person asking.

This note proposes treating that failure as its own kind of hallucination: an entailed but infeasible action. We would detect it by converting each piece of free-text advice into the change it implies to the person's profile. We would check that change against a declared list of which attributes are mutable. We would then use conformal selection, a calibration method that gives finite-sample error guarantees, to control the fraction of released advice that violates immutability. Conformal methods need correct labels on a held-out calibration set, and we would take those labels from formal recourse solvers rather than from a language-model judge. The guarantee is therefore stated against provable ground truth. That includes cases where a solver has certified that no feasible action exists, so the only correct answer is to decline.

Core Claim

Current hallucination controls for RAG check whether generated claims are supported by the retrieved text. CiteGuard scores each sentence-level claim with an entailment verifier and applies Benjamini–Hochberg selection, a standard procedure for controlling the false discovery rate (FDR), which is the expected fraction of released claims that are wrong. TRAC builds conformal prediction sets for question-answering correctness. Both are the right statistical machinery, but they target the wrong error for recourse. Advice copied from a retrieved case about a 20-year-old applicant is perfectly entailed and still infeasible for a 60-year-old. FaithEval shows the underlying problem: models follow in-context premises even when those premises contradict reality. CiteGuard's own authors describe their guarantee as only as reliable as the verifier behind it.

Our claim has two parts. First, in text-based recourse a large share of harmful outputs are feasibility violations, and entailment verifiers do not detect them. Second, a verifier that maps advice to an action vector $\delta$ over the user's attributes and tests whether $\delta_i = 0$ for every immutable attribute $i$ (or respects directional constraints such as "age only increases") catches these violations. With calibration labels from exact solvers, that verifier supports the guarantee

$$\mathbb{E}\left[\frac{\#\{\text{released advice that is infeasible}\}}{\max(1, \#\{\text{released advice}\})}\right] \le \alpha .$$

Here "infeasible" means the advice requires changing an immutable attribute, or the person lies in a region where no feasible recourse exists. $\alpha$ is the user-chosen risk budget.

Research Program

The mutability taxonomy we rely on comes from Generalized Inverse Classification and A budget-constrained inverse classification framework. They split features into immutable, directly actionable, and indirectly affected. We ask deployers to declare this taxonomy for their domain's profile schema. We do not try to learn it.

The first component is a benchmark, because none exists. We would start from tabular recourse tasks where ground truth can be computed exactly: Adult and COMPAS, as used by MACE and CARLA, and HELOC, GiveMeCredit, and the Pennsylvania sentencing risk instrument (SRAI), as audited by ReVer. For each task we train a small tree or linear classifier. We then write its decision logic as a natural-language policy document. We build a retrieval corpus of narrative case histories of past applicants whose fixed traits differ from those of the queried individual. Each query pairs a person's profile, stated in text, with the question "what could this person do to get a favorable outcome?"

The ground truth for each query comes from two solvers. MACE is complete, meaning it finds a feasible counterfactual whenever one exists and reports 100% coverage, so it gives the set of feasible actions. ReVer uses exact optimization to certify "confined regions": parts of the feature space where no feasible action can change the decision. Its SRAI case study proves that everyone under 21, and males aged 21–25, can never be classified low-risk. For people in those regions, any advice other than "no feasible change exists" is wrong by construction. This gives a clean test of hallucinated recourse that no existing RAG benchmark provides.

The second component is the verifier. An extraction model reads the generated advice and outputs a structured $\delta$ over the schema, including implicit changes. "Wait until you are older" becomes a directional change to age. "Apply as someone with no prior default" becomes a change to a fixed historical record. A deterministic checker then compares $\delta$ with the declared mutability constraints. It also tests the proposed action against the policy's decision rule. Where a causal graph is available, it propagates effects to downstream features, following Algorithmic Recourse: from Counterfactual Explanations to Interventions, which argues that freezing coordinates independently misses causal entanglement between features. The verifier's score becomes a conformal p-value, and Benjamini–Hochberg selection decides which pieces of advice are released. Advice that is withheld turns into an abstention.

Solver labels are used only in calibration and evaluation, where the tabular model exists. At deployment only the text policy exists. The central scientific question is therefore how much of the guarantee survives when the calibration set comes from solver-labelled synthetic cases and the test distribution is realistic advice.

Baselines

The naive reference point is vanilla RAG. A strong instruction-tuned model retrieves the top-$k$ passages from the policy and case corpus and answers directly. We report its rate of immutability violations and its rate of non-abstention on ReVer-confined individuals. On natural-question claims, CiteGuard reports vanilla RAG FDR of 30.6%; we have no reported figure for recourse, since no reported result was found on Lacuna for immutability-violation rates of LLM recourse advice.

The second baseline is prompting: a system prompt that lists the immutable attributes and forbids changing them, with and without chain-of-thought. It costs nothing and is what practitioners would try first. Beating it means a significantly lower violation rate at equal or better coverage of feasible advice.

The third baseline is metadata-filtered retrieval. Case histories are hard-filtered to exactly match the user's immutable attributes, which is a text analogue of the exact-match step in Private Counterfactual Retrieval With Immutable Features. This is the strongest retrieval-side competitor, and we run it both alone and combined with our output-side filter.

The fourth baseline, the strongest existing method, is CiteGuard. It uses the same Benjamini–Hochberg procedure and the same calibration split and budget $\alpha$, with its entailment verifier in place of our mutability verifier. CiteGuard reports reducing FDR from 30.6% to 9.4% at $\alpha = 0.10$ while keeping 86–92% of supported claims on Natural Questions. Beating it means that, at matched $\alpha$, our method's realized infeasible-advice rate stays at or below $\alpha$ while CiteGuard's exceeds it, and that we keep comparable feasible-advice yield.

We also run the abstention method RC-RAG, which reports a 14.77% average carefulness gain, as the competitor for the confined-region subset. We run CF-RAG, which reports 88.58% exact match on HotpotQA, as the competitor for retrieval robustness.

Last, we run a neurosymbolic pipeline. An LLM compiles the retrieved policy text into logical constraints, a MACE-style solver finds recourse with immutables frozen, and the LLM verbalizes the result. We also report an oracle version given the true tabular model, as an upper bound.

All systems share the same generator, corpus, retriever, calibration and test splits, and prompt-tuning budget. Ablations isolate the key ingredient. We compare an entailment score versus a mutability score inside the same conformal procedure, extraction of explicit changes only versus extraction of implicit and directional changes, and calibration labels from solvers versus labels from an LLM judge.

Why not just…?

Why not just tell the model which attributes are fixed? FaithEval found that conflict-aware prompting makes models sycophantic, flagging problems in valid contexts. It also found that chain-of-thought improves faithfulness without closing the gap. Prompting also gives no statistical guarantee. The prompting baseline measures this directly. If it drives violations close to zero on the confined-region subset, the output filter is unnecessary and we would report that.

Why not just filter retrieval by immutable attributes? This is a real threat for the part of the failure caused by retrieving mismatched cohorts. Filtering does not stop the generator from inventing implicit changes, swapping roles between entities (which MEDIMP reports in clinical text), or giving advice to people for whom no recourse exists. The decisive comparison is filtered retrieval alone versus filtered retrieval plus our verifier. If the gap is small, the contribution shrinks to a benchmark and an audit, and we would say so.

Why not just use CiteGuard or another entailment-based verifier? Such verifiers check support, not feasibility. CiteGuard's authors state that the guarantee depends on the verifier, and FaithEval shows models faithfully repeating context that contradicts reality. Our planted-distractor split is designed so that infeasible advice is entailed by the retrieved text. On that split, an entailment score should have little power to separate violations from valid advice.

Why not solve recourse symbolically and let the model only verbalize? When a formal model exists, this is the right approach, and our oracle pipeline will likely win. Our target setting is different: the decision rule exists only as retrieved text. There, the LLM that compiles rules into logic can itself hallucinate constraints, and the verbalization step can still swap entities. We measure where the compile-and-solve pipeline's errors come from. If its violation rate matches ours at lower cost, we adopt it as the generator and keep our verifier only as the calibrated release gate.

Decisive Checks

The first check is whether the realized infeasible-advice rate stays at or below $\alpha$ for $\alpha \in \{0.05, 0.1, 0.2\}$ across all five tabular sources, with CiteGuard exceeding $\alpha$ on the planted-distractor split. The second is non-abstention on ReVer-certified confined individuals, where any released advice counts as an error; this subset directly tests the model's tendency to keep answering when it should stop. The third is transfer. We calibrate on Adult and HELOC and test on COMPAS and SRAI, to measure how much the exchangeability assumption behind the guarantee breaks under domain shift. That shift is the main threat to deployment, so we report it honestly rather than assume it away.