The Proximity-Robustness Trade-off in Algorithmic Recourse

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 276 papers141 conceptsfrozen 2026-10-04

If a bank’s AI denies your loan application, it might provide a "counterfactual explanation" (CFE): "If your annual income were $5,000 higher, your loan would have been approved." This advice, known as algorithmic recourse, tells a user the minimum change required to flip a model's decision.

However, research by Junqi Jiang, Francesco Leofante, and Francesca Toni in Formalising the Robustness of Counterfactual Explanations for Neural Networks reveals a critical flaw: these explanations are notoriously fragile. Because standard methods optimize for the smallest possible change, they tend to place the user exactly on the model's decision boundary. If the model is retrained on new data or its parameters shift slightly, that boundary moves, and the previously "valid" advice becomes obsolete.

The Fragility of the Boundary

The core problem is a fundamental tension between proximity (how easy the change is for the user) and robustness (how likely the change is to remain valid over time).

When an algorithm searches for the "closest" counterfactual, it is effectively looking for the nearest point on the other side of a fence. As Sanghamitra Dutta and Saumitra Mishra argue in Robust Counterfactual Explanations for Tree-Based Ensembles, points located directly on this boundary are the most susceptible to invalidation. Even a minor update to the model's weights can shift the fence just enough to leave the user on the "denied" side again.

To solve this, researchers have introduced the concept of a reliability premium. To ensure a recommendation survives model updates, the user must be asked to move deeper into the target region. This creates a "buffer" or safety margin. While this requires more effort from the user, it provides a probabilistic or even deterministic guarantee that the recourse will remain valid.

Accounting for Model Multiplicity

The challenge of robustness is compounded by the Rashomon Effect: the fact that many different models can achieve nearly identical accuracy on the same dataset while having very different decision boundaries.

In ElliCE: Efficient and Provably Robust Algorithmic Recourse via the Rashomon Sets, Bohdan Turbal and Lesia Semenova demonstrate that recourse should not just be valid for one specific model, but for the entire "Rashomon set" of high-performing models. If a bank could have reasonably chosen any of ten different models, a truly robust explanation must work for all of them. This "future-proof" recourse inevitably requires larger feature changes than a recommendation optimized for a single, static model.

Formalizing Stability and Delta-Robustness

To move beyond heuristic fixes, the field has developed formal frameworks to quantify this trade-off:

Beyond Proximity: Plausibility and Uncertainty

Robustness isn't just about surviving model shifts; it's also about ensuring the suggested change is realistic. Eoin D. Delaney and Mark T. Keane point out in Uncertainty Estimation and Out-of-Distribution Detection for Counterfactual Explanations that minimal-distance changes often result in "adversarial" examples—points that are technically across the boundary but look nothing like real data.

Methods like PROPLACE, developed by Jianglin Lan and Antonio Rago, attempt to navigate this multi-dimensional space by jointly optimizing for proximity, robustness, and plausibility. By using robust optimization, these frameworks identify the minimal necessary change that remains valid across a range of potential model states while staying within the distribution of real-world data.

The shift in the research direction is clear: moving away from "how can we find the smallest change?" toward "how can we find the smallest change that we can actually trust?"

Papers in this version

Showing 60 of 76 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 45 papers
  2. Version 1 · 2026-10-04 · 76 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_proximity_robustness_tradeoff_c57f1622,
  title = {proximity-robustness tradeoff},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proximity-robustness-tradeoff/rdr_c57f1622820b4652bfe81ffea49c0abe},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_proximity_robustness_trade_off_in_al_c57f1622_v1,
  title = {The Proximity-Robustness Trade-off in Algorithmic Recourse},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-proximity-robustness-trade-off-in-algorithmic-recourse/rdr_c57f1622820b4652bfe81ffea49c0abe/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}