acceptodds
Withdrawn from ICLR 2027

Agentic Search for Counterfactual Recourse under Fixed LLM Budgets

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Counterfactual recourse aims to provide actionable feature changes that would alter an unfavorable decision made by a predictive model. In practice, affected individuals often benefit from multiple feasible alternatives rather than a single optimal explanation. A natural way to produce such alternatives is to prompt large language models (LLMs). However, prompting incurs a practical constraint: the number of LLM calls is often the dominant computational and economic cost. Together, the need for multiple alternatives and this cost constraint shift the problem from finding a single high-quality counterfactual to efficiently generating a set of oracle-validated counterfactuals under a fixed LLM-call budget. In this work, we study counterfactual recourse generation in the LLM-agentic setting as a fixed-budget search problem and propose Recourse Monte Carlo Tree Search (ReCo-MCTS), an agentic tree-search framework that aims to increase the yield of unique, oracle-validated counterfactuals under this budget while accounting for the extent of the required changes. ReCo-MCTS combines LLM-based multi-candidate generation, constraint checking, black-box oracle evaluation, and UCT-guided tree search to accumulate valid counterfactuals under a fixed LLM-call budget. On four real-world tabular datasets, ReCo-MCTS returns more counterfactuals than the evaluated baselines in our main comparison under the specified resource limits, with trade-offs in the extent of the required changes.

Primary area:
interpretability and explainable AI
Keywords:
Counterfactual explanations, algorithmic recourse, large language models, Monte Carlo tree search

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_WCCrOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

Generating counterfactual explanations / recourse can be understood as a MCTS (i believe there is previous work along these lines). This paper proposes using LLMs in the expansion phase of a typical MCTS recourse search. The authors claim that this results in more counterfactuals being found than via other approaches.

The authors conduct a small experiment testing 4 hyperparameter settings of their method on 4 available datasets. They compare with 3 baselines.

Critical strengths

It was difficult to find aspects of this work that were particularly strong. Generating counterfactuals with LLMs does not seem to be novel or unique, and the provided evaluation does not convince me that it confers meaningful advantages in terms of cost (computational cost of search or recourse implementation costs).

Critical weaknesses

The abstract states (line 14/15) that a natural way to generate counterfactuals is by prompting LLMs, but this claim does not seem to have a related citation or evidence. Further, the selected motivation/evaluation metric of "number of valid counterfactuals produced" seems arbitrary and suspect. I am not aware of prior literature that focuses on this aspect, and none of the baselines evaluated against optimise for this goal. Diversity in generated counterfactuals and returning a multitude of options to users as candidate recourses have some precedent (eg. the DICE baseline used in this paper), but this is not the same as simply generating more counterfactuals.

In particular, I suspect a naive baseline, an integer programming approach such as those already cited (Russel, 2019, or Ustun et al, 2019), or even a MCTS with a "random" expansion where the search does not terminate after reaching it tradiotnal goals (of finding a minimum edit counterfactual or a multitude of diverse counterfactuals) would generate more / better counterfactuals than prompting an LLM.

I would encourage the authors to either provide a thorough evaluation across hyperparameters and methods (appropriately modifying the methods for their objectives -- using a technique optimised for objective A and then evaluating it using objective B does not provide clear evidence) that demonstrates tangible benefits in using Reco-MCTS; or (more likely) to prove theoretically, empirically, through user studies, or other methods that the counterfactuals generated via LLM are "nicer" than those generated through other means.

Questions for authors

Claims that should be cited / proved instead of being asserted:

  1. line 14-15
  2. line 129-30
  3. A comparison of total flops/compute used (since the paper seems to claim the limited LLM call budget being satisfaction as a unique Reco-MCTS ability) by Reco-MCTS vs DICE and other baselines. Does the method really confer any advantage in compute-per-counterfactual produced than other "vanilla" search strategies?

Typos:

  1. line 137 missing space

Unclear:

  1. Line 160 mentions a quality-quantity trade-off, but I don't see this in the paper.
  2. Line 349-350 mention "same 100 evaluation prompts" and "every condition" but it is not immediately clear what these numbers are referring to
  3. Is L being overloaded in line 359? Does it refer to edits from parent to child as well as edits wrt the initial datapoint?
Reviewer_qAZ2OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper presents a counterfactual (CF) explanation (CFE) generation method that utilizes LLM prompts within an LLM-budget-constraint Monte Carlo Tree Search (MCTS) search process to identify, assess and eventually select a final CF sets. The goal of the method is to gather a large set of valid and unique CFs. The authors compare with three baseline methods, in a poorly set experimental evaluation, producing inconclusive results. The motivation, problem formulation, optimization objective, evaluation measures and experimental setting have issues, as elaborated in the detailed review. My recommendation is clear rejection.

Critical strengths

None.

Critical weaknesses

WK1: Problem motivation. The proposed method lack proper motivation. CFE in general, diverse CFE, actionable CFE, feasible CFE, etc., are well motivated through the literature. However, it is unclear why a user would need many, unique, sparse, similar to the factual CFE, as produced by the method, and the authors should pay attention at this and properly motivate their work. Also, the use of LLMs is not motivated either, neither justified by the experimental results, as discussed later in the review.

WK2: Problem formulation, optimization objective and evaluation measures. The authors discuss the problem formulation, optimization objective and evaluation measures in 4 subsections (3.1, 3.3.3, 3.3.4, 3.3.5) which present contradicting/conflicting claims and information. In 3.3.1 they claim that the main optimization objective is Uniqueness. However, Uniqueness is not included in the actual optimization process described in 3.3.4. Nevertheless, Uniqueness is again included 3.3.5 which reintroduces a different optimization objective. There, Novelty is also introduced as an optimization objective, however this objective too is absent from 3.3.4, which describes the algorithm. What is more, 3.3.3 claims that Uniqueness is used as an evaluation measure. This series of contradictions comprise a significant flaw of the paper.

WK3: The diversity claim. The authors claim diversity for their proposed method. However, the core paper does not report any results on the respective Novelty (D) measure; such results are found later on in Table 9 of the appendix and showcase that DICE achieves much higher diversity than RECO. Moving the specific, highly unfavorable, results in the appendix, while claiming diversity is a significant issue of the paper I note that diversity is a well-motivated (in the literature) property of CFE, in contrast to, e.g., the number of CF found.

WK4: The experimental setting. Aside of the experimental setting related issues (e.g. measures), the results of Table 3 wrt to GS and CCHVAE baselines are alarming and the authors omit to discuss them. These two baselines are shown to hardly identify any CFE, which is inconsistent with the literature, e.g. on CCHVAE*, since such considerable issue of the method is not identified or discussed. Together with Section C of the appendix, this comprises an indication that the authors most probably have not fine tuned the baselines at all, which could be considered unfair to the latter. What is more, the measures presented in Table 3, even jointly considered, does not motivate why RECO is better than DICE. As far as the reader can understand, the high CF, P and low S values could as well mean many, similar to the factual, similar to each other CFEs, thus a redundant set of solutions. *https://dl.acm.org/doi/10.1145/3366423.3380087 https://link.springer.com/article/10.1007/s10618-024-01017-y https://dl.acm.org/doi/10.1145/3677052.3698673

WK5: The lack of LLM performance and resource consumption performance. The authors set different constraints to their, LLM-based method and to the baselines, which however are not comparable wrt to performance, computation resource consumption and cost. These are considerable aspects given the use of the LLM, and lack of even rough estimations/projections makes the constraint selections seem arbitrary and hurts, again, the motivation of the proposed method: to the best of my knowledge, I can run the CFE baselines in my laptop for free, while to use the proposed method I need a service of unquantified/incomparable computation demand and cost.

WK6: Structuring and easiness to read. The core paper is overly condensed, required several back and forths to read, contains redundant but also contradicting objectives definitions and includes important information for its comprehension in the appendix. All these make it not self-contained.

Questions for authors

Deriving concrete questions from the weaknesses section: -What is exactly the optimization objective used in the algorithm? -Why is Novelty not reported in the core paper, even though diversity is a claim for the proposed method? -What is the authors’ interpretation of the poor performance of GS and CCHVAE in CF? Was any fine tuning performed in the baselines?

  • What is the authors’ interpretation of the poor performance of RECO in the Novelty measure, even though Novelty appears to be an optimization term?
Reviewer_rjsFOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes and interesting solution to the recourse problem by repeatedly prompting an LLM to generate counterfactuals. The authors compare their method to baselines such as DiCE and growing spheres, finding their approach produces a greater set of valid counterfactual options, with reasonable proximity and sparsity etc.

Critical strengths
  • I like the general idea, it seems obvious to me that this is where the recourse field should head, to overcome perhaps the final great challenge in the field of causal validity and human actionability.
Critical weaknesses
  • There is no evidence presented by the authors that this recourse method has a practical real-world advantage over baselines (all of which are many years old at this point). For example, if I gave a real user your method's counterfactual, are the (1) likely to improve their situation more, and (2) actually follow the recourse? Look at the Tominaga et al. IJCAI paper recently, it demonstrates this [1].
  • No causal verification, it is possible these counterfactuals are not actually causally valid
  • Missing simple baselines like a brute force search. If all we care about is getting a lot of different counterfactuals, this seems an obvious baseline
  • Missing simple prompt baseline, why not just prompt an LLM once to give 50 recourse options? I'm sure it would probably do a good job. The real challenge now is trying to filter such a set into useful recourse people will actually follow.

DiCE is getting better counterfactual diversity, more is not always better.

[1] Reassessing Evaluation Functions in Algorithmic Recourse: An Empirical Study from a Human-Centered Perspective

Questions for authors

See weaknesses

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.