Research map / Label-efficient and robust learning / Recognition and long-tail
Prediction without Preclusion: Recourse Verification with Reachable Sets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces recourse verification, a model-agnostic procedure that builds discrete reachable sets via MIP enumeration to certify whether a model assigns fixed predictions (preclusion) under actionability constraints on consumer finance data.
Problem
Machine learning models used in lending and hiring may assign fixed predictions to individuals because features are not actionable, precluding access; there is no reliable way to verify whether a model provides recourse under complex actionability constraints.
Approach
Construct reachable sets (all points attainable via feasible actions) for discrete feature spaces using a mixed-integer program with no-good cuts and feature-wise decomposition, so any model can be audited by querying its predictions over reachable points; verification can certify infeasibility (no recourse) rather than just provide actions.
Key results
- On heloc, DiCE returns a loophole (action violating actionability constraints) for 42.1% of individuals denied by an XGBoost model.
- On heloc, DiCE fails to find an action for 42.7% of denied XGBoost individuals, of which 21.1 points are blindspots (recourse exists).
- Logistic regression assigns predictions without recourse to 22.2% of heloc individuals; with monotonicity and integrality only, AR appears to give recourse to about 99% of points, illustrating the illusion of feasibility.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use reachable-set verification with inherent actionability constraints | Logistic regression on HELOC · HELOC | prediction without recourse | Mixed |
| Enforce more complex actionability constraints in addition to simple constraints such as immutability and monotonicity (ablation) | Actionable Recourse on HELOC · HELOC | prediction without recourse detection: 22.2% | Helped |
| Audit using only monotonicity and integrality constraints (ablation) | Actionable Recourse on HELOC · HELOC | apparent recourse feasibility: ≈ 99% | Mixed |
| Use DiCE to generate recourse actions instead of verifying with reachable sets | XGBoost on HELOC · HELOC | loopholes: 42.1% | Hurt |
| Choose XGBoost rather than random forest for deployment | HELOC classifiers · HELOC | predictions without recourse: 11% difference | Helped |
Surprising findings
- Methods that enforce only simple constraints (immutability, monotonicity) report near-universal recourse, hiding infeasibility that appears once complex constraints are enforced.
- On heloc, RF and XGB with similar test AUC (~0.780) differ by 11% in predictions without recourse.
Limitations
- Only certifies infeasibility over discrete feature spaces; continuous features are left to future sampling-based work with probabilistic guarantees.
- Does not handle probabilistic causal effects; only deterministic actionability constraints are considered.
- Reachable sets grow exponentially with the number of features, so complete enumeration may be infeasible under time constraints.
Experimental setup
Datasets: heloc german givemecredit
Benchmarks: heloc german givemecredit
Metrics: percentage certifying no recourse percentage outputting action loophole rate blindspot rate
Baselines: AR DiCE
Builds on: AR (Actionable Recourse) DiCE
Closest papers by meaning
- Feature Responsiveness Scores: Model-Agnostic Explanations for Recourse (ICLR 2025 · similarity 0.89)
- Providing Fair Recourse over Plausible Groups (AAAI 2024 · similarity 0.85)
- SafeAR: Safe Algorithmic Recourse by Risk-Aware Policies (AAAI 2024 · similarity 0.84)
- ElliCE: Efficient and Provably Robust Algorithmic Recourse via the Rashomon Sets (NeurIPS 2025 · similarity 0.83)
- From Search to Sampling: Generative Models for Robust Algorithmic Recourse (ICLR 2025 · similarity 0.83)
- Understanding Fixed Predictions via Confined Regions (ICML 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.