🤖 machine learning

Diverse and Plausible Algorithmic Recourse via Tractable Recourse Distributions

The paper proposes "Tractable Recourse Distributions," a probabilistic framework that models the space of feasible algorithmic recourse as a closed-form distribution over favorable outcomes, enabling the generation of diverse, plausible, and actionable alternatives without retraining the underlying model.

Original authors: Anagha Sabu, Hrithik Suresh, Narayanan C. Krishnan

Published 2026-08-06

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Anagha Sabu, Hrithik Suresh, Narayanan C. Krishnan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where a computer decides your future. It's the gatekeeper for your loan, your job interview, or your college acceptance. Sometimes, it says "no." In the past, if you asked why, the computer might have given a vague answer or just a list of rules you broke. But knowing why you failed doesn't help you fix it. You need a map. You need to know exactly what changes you can make to turn that "no" into a "yes." This is the heart of a field called Algorithmic Recourse. Think of it as a GPS for life decisions: instead of just telling you you're lost, it suggests a route to get you to your destination.

However, there's a catch. Most GPS systems only give you one route. But in real life, there are often many ways to get to the same place. Maybe you can get a loan by paying off a credit card, or maybe by getting a higher-paying job, or by getting a co-signer. Different people have different tools, time, and constraints. A good system shouldn't just give you one rigid path; it should offer a menu of realistic, diverse options that actually fit your life. This is the problem a new paper from researchers at the Indian Institute of Technology Palakkad tries to solve. They want to move away from finding a single "perfect" answer and instead create a whole landscape of possible solutions, showing you the many ways you could succeed.

The Old Way: Finding a Single Needle in a Haystack

Imagine you are trying to find a specific key in a giant, messy room (the room is all the possible changes you could make to your life). The old way of doing this was to send a robot in with a flashlight to find the one key that is closest to where you are standing right now. The robot would scan the floor, calculate distances, and pick the single best spot. If the robot found a key, great! But what if that key was in a part of the room that was actually locked or dangerous? Or what if the robot missed a perfectly good key just a few feet away because it was too focused on the first one?

The researchers point out that existing methods work like this robot. They treat the problem as a math puzzle to find one or a few specific "counterfactuals" (a fancy word for "what if" scenarios). They try to force the solution to be close to your current situation and involve changing as few things as possible. But in doing so, they often miss the bigger picture. They might give you a solution that is mathematically close but totally unrealistic for your life, or they might give you ten solutions that are all basically the same thing, just slightly tweaked. It's like a GPS that only shows you the shortest route, even if that route is a dead end, while ignoring the scenic, viable alternatives.

The New Idea: A Probability Map of Possibilities

The authors, Anagha Sabu, Hrithik Suresh, and Narayanan C. Krishnan, propose a completely different approach. Instead of hunting for a single needle, they want to draw a map of the entire room, showing you where all the good keys are likely to be. They call this a Tractable Recourse Distribution (TRD).

Think of it like this: Imagine you have a magical, glowing map of all the ways you could get a loan approved. This map isn't just a list of points; it's a heat map. The brightest, hottest spots on the map represent the changes that are most likely to work, are closest to your current life, and don't require you to change too many things at once. The dimmer spots are still possible, but they require bigger leaps.

The magic of their method is how they make this map. They start with a model of what "successful" people look like (the positive-class distribution). Then, they use a mathematical trick called exponential tilting. Imagine you have a bag of marbles representing all possible futures. Most marbles are just random. But you want to find the ones that are close to your current situation. So, you put a magnet on the bag. The magnet pulls the marbles that are close to you (proximity) and the ones that don't require changing many features (sparsity) to the top. The marbles that are far away or require huge changes sink to the bottom.

Because they use a specific type of mathematical structure called a Probabilistic Circuit, they can do this pulling and sorting exactly and instantly. They don't need to retrain the whole system for every single person. They just take the existing map, apply the magnet (the tilt), and boom—you have a personalized map for that specific person.

What They Found: A Menu of Realistic Options

The researchers tested this idea on standard datasets used for things like loan approvals and credit scores, as well as on images (turning a picture of an 8 into a 0, or a 7 into a 1). Here is what they discovered:

1. Diversity without the Chaos
When they let their system sample from this new map, it naturally produced a wide variety of different solutions. Some people might change their income, others might change their debt, and others might change their employment history. The system didn't need a special "diversity" rule to force this variety; the map itself was diverse. In fact, they found that even if they just picked random samples from the map, they got a good mix of options. The only thing they added was a "clustering" step to make sure the final list wasn't just ten copies of the same advice.

2. Keeping it Real (Plausibility)
One of the biggest fears with these systems is that they might suggest crazy, impossible changes, like "move to a different country" or "become a different age." The researchers found that their method kept the suggestions grounded. Because the map started with real data about successful people, every suggestion was a realistic scenario. In their tests, the "worst" suggestion in their list was still much more realistic than the suggestions from other methods. For example, on the German Credit dataset, their method kept the "worst" suggestion very plausible, whereas other methods suggested changes that were mathematically possible but practically nonsense.

3. The Trade-off Control
The researchers showed that they could control the map. By adjusting the strength of the "magnet" (the tilt parameters), they could tell the system: "Give me the closest possible changes, even if I have to change a few things," or "Give me changes that affect as few parts of my life as possible, even if they are a bit further away." They found that using both controls together gave the best results, offering solutions that were both close to the user's current life and required minimal changes.

4. It Works on Images Too
They even tried this on pictures. If you have a picture of the number 8 and want to turn it into a 0, the system doesn't just guess. It creates a distribution of all the ways to turn an 8 into a 0. As they increased the "tilt" strength, the generated images kept more of the original 8's pixels, making the change smaller and more subtle. However, they noted a trade-off: if you tilt too hard, the image might look too much like the original 8 and fail to be recognized as a 0. This showed that the method works in complex, high-dimensional spaces, not just simple tables of numbers.

The Bottom Line

The paper concludes that this approach is a practical, powerful way to help people. It doesn't just give you one answer; it gives you a menu of diverse, realistic, and actionable options. It's like having a travel agent who doesn't just book you the cheapest flight, but shows you five different routes, explains the pros and cons of each, and lets you pick the one that fits your schedule and budget.

The researchers are careful to note that this isn't a magic wand that solves every problem. The system relies on "rejection sampling," which means it generates many possibilities and throws away the ones that don't work. If the rules are too strict (like very complex laws about what changes are allowed), it might be harder to find a good path. But for the datasets they tested, it worked remarkably well, serving every single person they tested with at least one valid, realistic option. They suggest that in the future, they might be able to bake these strict rules directly into the map itself, making the process even smoother.

In short, this paper moves us from a world where computers tell us "here is the one thing you must do" to a world where they say, "here are all the different ways you could make it work, and here is the best one for you."

Technical Summary: Diverse and Plausible Algorithmic Recourse via Tractable Recourse Distributions

Problem Statement

Algorithmic recourse (AR) aims to assist individuals in reversing unfavorable automated decisions by recommending actionable changes to their attributes. While existing literature acknowledges that multiple distinct paths often exist to achieve a favorable outcome, current AR approaches predominantly treat recourse as an optimization problem. These methods typically construct a single counterfactual or a small, fixed set of counterfactuals by explicitly optimizing for objectives such as validity, proximity, sparsity, and plausibility.

The authors identify three primary limitations in this point-wise optimization paradigm:

Lack of Distributional Modeling: Existing methods treat recourses as isolated points rather than modeling the underlying space of feasible alternatives available to an individual.
Trade-offs: In practice, these methods often sacrifice diversity, plausibility, or feasibility to secure the others.
Rigid Diversity: When multiple recommendations are generated, diversity is often enforced via explicit objectives or enumeration, failing to capture the relative likelihood of different strategies or the broader structure of the solution space.

Methodology: Tractable Recourse Distributions (TRD)

The paper proposes Tractable Recourse Distributions (TRD), a probabilistic framework that reformulates AR as the construction of an individualized probability distribution over favorable outcomes for a given factual instance.

Core Framework

Base Distribution: The method starts with a learned probability distribution over the positive class, denoted as $p_+$ . This distribution encodes the plausibility of favorable outcomes based on the data manifold.
Exponential Tilting: To personalize $p_+$ for a specific factual instance $x^-$ (which received an unfavorable prediction), the authors apply exponential tilting. They define a factual-specific intervention cost function $G_{\delta,\nu}(x; x^-)$ comprising:
- Proximity Cost: $\delta \|x - x^-\|_1$ (magnitude of changes).
- Sparsity Cost: $\nu \|x - x^-\|_0$ (number of features changed).
The resulting TRD is defined as:
$\tilde{p}_{\delta,\nu}(x | x^-) = \frac{p_+(x) \exp\{-G_{\delta,\nu}(x; x^-)\}}{Z(\delta, \nu; x^-)}$
where $Z$ is the normalization constant. This transformation concentrates probability mass on favorable outcomes that require smaller and fewer changes from the factual instance.
Tractability via Probabilistic Circuits (PCs):
- The positive-class distribution $p_+$ is represented using a smooth and decomposable Probabilistic Circuit (PC).
- The intervention cost $G$ is additively separable across features.
- Key Theoretical Result: The authors prove that smooth and decomposable PCs are closed under exponential tilting by additively separable costs. This allows the TRD to be constructed exactly as a new PC with the same topology as the base model.
- Implication: This construction enables exact normalization, likelihood evaluation, conditioning, and sampling without retraining the model or performing per-instance optimization.
Feasibility Enforcement:
- Actionability: Hard constraints (immutable features, monotonicity) are enforced via conditioning on the actionable set $A(x^-)$ . Because PCs support exact conditioning, this is performed efficiently.
- Validity & Causality: Classifier validity (prediction score) and causal constraints are enforced via rejection sampling. Samples are drawn from the actionable TRD and accepted only if they satisfy the classifier's threshold and causal rules.
Diverse Recourse Set Construction:
- Instead of solving an optimization problem for diversity, the method samples a pool of feasible counterfactuals from the TRD.
- To avoid redundancy, the pool is clustered using k-medoids, and the medoid of each cluster is returned.
- The number of clusters $k$ is determined adaptively using the silhouette score, allowing the number of returned recourses to vary based on the structure of the sampled distribution.

Key Contributions

Distributional Formulation: Introduction of TRD, which represents favorable alternatives as an individualized probability distribution rather than a fixed set of optimized points.
Exact Construction: Demonstration that smooth and decomposable PCs are closed under exponential tilting by additive costs. This yields an exact TRD construction for proximity and sparsity objectives while preserving tractable inference properties without retraining.
Theoretical Characterization: Proof that exponential tilting concentrates probability mass toward lower-cost interventions, theoretically guaranteeing that the distribution favors proximal and sparse counterfactuals.
Empirical Validation: Demonstration on tabular benchmarks (Adult, German Credit, GMSC) and MNIST that TRD generates diverse and plausible recourse sets with joint control over proximity and sparsity, while maintaining sufficient feasible probability mass for practical rejection sampling.

Experimental Results

The authors evaluated TRD against state-of-the-art methods (DiCE, LiCE, and MIO) on standard tabular benchmarks and MNIST.

Balance of Metrics: TRD achieves a consistent balance across diversity, plausibility, and feasibility. Unlike DiCE (which maximizes diversity but often violates feasibility) or LiCE (which maximizes plausibility but collapses to a single strategy), TRD returns multiple distinct strategies that remain plausible and feasible.
Coverage: TRD achieved 100% coverage (Served %) across all datasets, providing at least one feasible counterfactual for every evaluated factual instance within a fixed sampling budget.
Plausibility: TRD maintained low Negative Log-Likelihood (NLL) across the entire returned set (best, mean, and worst), indicating that diversity was not achieved by appending implausible instances.
Diversity: While not always the absolute highest in Count-Diversity, TRD returned multiple distinct intervention strategies ( $k_{eff}$ ) that were actionable and causally consistent.
Control: Experiments confirmed that proximity and sparsity tilts provide complementary control; joint tilting yielded the lowest distance and feature changes compared to single-term tilting.
MNIST Extension: In high-dimensional image tasks, TRD successfully demonstrated the trade-off between proximity (tilt strength) and validity, showing that the mechanism extends beyond tabular data.

Significance and Claims

The paper claims that TRD offers a principled alternative to point-wise optimization by modeling the space of feasible alternatives rather than just finding points within it.

Efficiency: The framework requires no retraining and no per-instance optimization, making it computationally efficient at deployment time.
Intrinsic Diversity: Diversity is shown to be intrinsic to the recourse distribution; clustering serves only to summarize this existing diversity rather than creating it via explicit objectives.
Practicality: The authors assert that TRD retains sufficient probability mass over feasible counterfactuals to make rejection sampling a practical alternative to repeated optimization, even under strict constraints.

The authors modestly note a limitation: the effectiveness of rejection sampling depends on the feasible probability mass, which may diminish under highly restrictive validity or causal constraints. Future work is suggested to investigate compiling constraints directly into the circuit and adapting tilt strengths to individual factuals.