🤖 machine learning

Algorithmic Recourse of In-Context Learning for Tabular Data

This paper introduces the first study of algorithmic recourse for in-context learning on tabular data, providing theoretical guarantees on solution convergence and proposing ASR-ICL, a novel zeroth-order framework that efficiently generates sparse, actionable recourse for black-box ICL models.

Original authors: Wenshuo Dong, Jiaming Zhang, Shaopneg Fu, Hongbin Lin, Di Wang, Lijie Hu

Published 2026-06-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wenshuo Dong, Jiaming Zhang, Shaopneg Fu, Hongbin Lin, Di Wang, Lijie Hu

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 you are applying for a loan, but a computer says "No." You want to know: "What could I change to get a 'Yes' next time?" This is the problem of Algorithmic Recourse. It's like asking a GPS, "If I want to reach the destination, which turns should I take?"

For years, we've had good answers for this when the computer is a standard, pre-trained model. But recently, a new type of AI called In-Context Learning (ICL) has become popular. Think of ICL not as a fixed map, but as a smart travel agent who looks at a few examples of other people's trips right before giving you advice. Because this agent changes its mind based on the examples it sees right now, the "rules" for getting a loan approval can shift slightly every time you ask.

This paper tackles a big question: How do we give good, actionable advice to people when the "travel agent" (the AI) keeps changing its rules based on the examples it's looking at?

Here is a breakdown of their work using simple analogies:

1. The Problem: The Shifting Goalpost

In the old days, the AI was like a fixed vending machine. Once you put money in, the buttons and the snacks inside never changed. If you wanted a different snack, you knew exactly which buttons to press.

With In-Context Learning, the AI is more like a chameleon. It looks at a few examples (the "context") provided at the moment you ask a question, and then it changes its color (its decision rule) to match them.

The Challenge: If the rules keep shifting, how do we know if a suggested change (like "increase your income") will actually work? What if the AI changes its mind halfway through?

2. The Theory: Proving the Rules Still Exist

The authors first did some heavy math to prove that even though the AI is a chameleon, it's not chaotic.

The Analogy: Imagine the chameleon is sitting on a branch. Even though it changes color, the branch itself is solid. The authors proved that as long as you show the AI enough examples (a large "context"), its advice becomes stable and predictable.
The Result: They showed that if you give the AI enough examples to look at, its advice converges (settles down) to be just as reliable as a traditional, fixed model. They also proved that there is always a "limit" to how much you need to change to get a different result; you won't be asked to do the impossible.

3. The Solution: ASR-ICL (The Smart Searchlight)

Since the AI is a "black box" (we can't see inside its brain to see how it calculates things), we can't use standard math tricks to find the answer. We have to guess and check, which is slow and expensive.

The authors created a new tool called ASR-ICL.

The Analogy: Imagine you are looking for a specific key in a giant, dark room full of 1,000 drawers.
- Old Method: You open every single drawer one by one. This takes forever and burns a lot of energy (queries).
- ASR-ICL Method: This tool is like a smart searchlight. Instead of checking every drawer, it quickly scans the room and realizes, "Hey, the key is probably in just these 5 drawers." It then focuses all its energy on those 5 drawers, ignoring the other 995.
Why it works: In real life, you usually only need to change a few things (like your income or debt) to get a loan approved, not everything. ASR-ICL automatically figures out which few features matter most and ignores the rest. This makes it fast, cheap, and efficient.

4. The Results: It Works in the Real World

The team tested this on real-world data (like credit scores, criminal risk assessments, and medical data) using different types of AI models.

Success: Their tool found valid solutions (ways to get a "Yes") just as often as the old methods, but it did so by asking the AI fewer questions (queries).
Efficiency: Because it focused on a small subset of features, the suggested changes were often simpler and more realistic (e.g., "lower your debt by $500" instead of "change your job, move cities, and get a new car").
Multi-Class: It even worked when there were more than two outcomes (like getting a "Good," "Fair," or "Poor" credit rating), not just "Yes" or "No."

Summary

The paper says: "Don't panic about the new, shifting AI models. We proved that their advice is stable if you give them enough examples. Furthermore, we built a smart tool (ASR-ICL) that acts like a spotlight, finding the few, simple changes you need to make to get a better outcome, without wasting time checking every single possibility."

Key Takeaway: Even when the AI's rules change based on what it's looking at, we can still give people clear, actionable, and efficient advice on how to improve their situation.

Technical Summary: Algorithmic Recourse of In-Context Learning for Tabular Data

Problem Definition

The paper addresses the gap between the emerging paradigm of In-Context Learning (ICL) for tabular data and the established field of Algorithmic Recourse. While predictive models are increasingly deployed in high-stakes domains (e.g., credit lending, criminal justice) where individuals require actionable guidance to reverse unfavorable decisions, existing recourse methods assume a fixed, trained decision function.

In contrast, ICL models (such as TabPFN, TabICL, and general Large Language Models) induce predictions dynamically based on a set of labeled examples provided at inference time. This results in a context-conditioned predictor ( $f_C$ ) where the decision rule varies depending on the specific context set $C$ . This dynamic nature challenges the core assumptions of classical recourse, raising fundamental questions:

Is recourse well-defined and bounded when the decision rule is not fixed?
Is recourse stable across different context compositions?
Can recourse be computed efficiently for black-box ICL models without gradient access?

Methodology

1. Theoretical Analysis

The authors formalize algorithmic recourse within the ICL framework using a linear regression task induced by a single-layer linear self-attention (LSA) model.

Feasibility Guarantees: They establish conditions under which recourse is guaranteed. Specifically, if all features are unbounded, recourse is guaranteed for all individuals provided at least one feature is actionable. Conversely, if features are bounded and immutable features exist, recourse may be denied for some individuals, similar to classical linear classifiers.
Convergence and Bounds: The paper derives a closed-form solution for the optimal recourse perturbation ( $\delta^*_{ICL}$ $δ_{I C L}^{*}$ ) and proves a high-probability upper bound on the recourse cost.
- Key Insight: As the number of context examples ( $M$ ) and pre-training demonstrations ( $N$ ) increase, the ICL-based recourse converges to the optimal recourse of the underlying linear model. The perturbation bound tightens as $M$ and $N$ grow, with the error term depending on $O(1/N)$ and $O(\sqrt{\ln(d)/M})$ .
- Implication: This suggests that with sufficient context, ICL models behave increasingly like classical linear models, stabilizing the recourse solution.

2. Proposed Algorithm: ASR-ICL

To address the practical challenges of black-box, high-dimensional tabular data where gradients are unavailable, the authors propose Adaptive Subspace Recourse for In-Context Learning (ASR-ICL).

Zeroth-Order Optimization: ASR-ICL treats recourse generation as a constrained black-box optimization problem. It relies solely on function evaluations (queries to the LLM) rather than gradients.
Adaptive Subspace Selection: To mitigate the curse of dimensionality and reduce query budgets, the algorithm does not optimize over all $d$ $d$ features simultaneously. Instead, it:
1. Maintains an importance score for each feature.
2. Samples a small subset of features (subspace size $k \ll d$ ) based on these scores.
3. Optimizes the recourse within this low-dimensional subspace using a zeroth-order solver (RACOS).
4. Updates the feature importance scores based on the success of the optimization in the sampled subspace, gradually focusing the search on influential features.
Constraints: The framework enforces feasibility constraints (e.g., immutability of age, monotonicity of income) via a projection operator $\Pi_\Omega$ on candidate solutions.
Multi-class Support: The method naturally extends to multi-class tabular tasks without task-specific modifications by optimizing toward a desired target class.

Key Results

Experimental Setup

The authors evaluated ASR-ICL on five real-world datasets (Australian Credit, COMPAS, Diabetes, Corporate Rating, Student Performance) covering binary and multi-class tasks. They tested against specialized tabular ICL models (TabPFN-2.5, TabICL) and general-purpose LLMs (Qwen3, LLaMA-3, GPT-4o). Baselines included DiCE, Actionable Recourse (AR), and FACE, implemented on trained models for comparison.

Performance Findings

Validity and Cost: ASR-ICL achieves recourse validity comparable to existing methods for trained models (often reaching 100% validity) while maintaining significantly lower recourse costs. For instance, on the Australian Credit dataset, ASR-ICL achieved perfect validity with an average cost of 3.83, compared to 8.96 for DiCE.
Query Efficiency: ASR-ICL is highly query-efficient. It achieves comparable validity to full-space zeroth-order baselines while reducing the average query budget by 2–3 $\times$ .
Theoretical Validation: Experiments confirmed the theoretical convergence behavior. As the number of in-context instances increased (from 4 to 64 shots), recourse validity stabilized and costs decreased, approaching the performance of linear-model references.
Robustness: The method demonstrated robustness to variations in context distribution and ordering, though some sensitivity was observed in general LLMs under specific prompt orderings.
Sparsity: ASR-ICL naturally produces sparse recourse solutions. Case studies showed it could flip predictions by modifying only 2 actionable features, whereas other methods often required changing 5 or more.

Significance and Claims

The paper claims to present the first systematic study of algorithmic recourse under in-context learning for tabular data. Its significance lies in:

Theoretical Foundation: Establishing that recourse remains well-defined and bounded under dynamic, context-conditioned predictors, and proving that ICL-based recourse converges to classical solutions as context size increases.
Practical Framework: Introducing ASR-ICL, the first recourse framework specifically designed for black-box ICL models. It bridges the gap between classical recourse methods (designed for fixed models) and emerging ICL paradigms.
Efficiency and Actionability: Demonstrating that adaptive zeroth-order optimization can generate sparse, actionable, and low-cost recourse in high-dimensional spaces without requiring model internals or gradients.

The authors maintain a modest tone, noting that while their results validate the feasibility and convergence of recourse in ICL settings, the performance of general LLMs can still vary based on prompt sensitivity and task difficulty, particularly in multi-class scenarios. They do not claim to solve all challenges of ICL but rather provide a foundational step toward making these dynamic models accountable and actionable.