aiqbench analysis
This research addresses the high cost of LLM prompting in counterfactual recourse by introducing ReCo-MCTS, an agentic framework that maximizes the yield of valid alternatives under strict call budgets. By integrating Monte Carlo Tree Search with constraint checking and oracle evaluation, the method efficiently generates diverse explanations without exhausting computational resources. The approach demonstrates improved performance on real-world datasets compared to existing baselines, offering a practical solution for scaling explainable AI applications.
Agentic Search for Counterfactual Recourse under Fixed LLM Budgets
arXiv:2606.08696v2 Announce Type: replace 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.
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.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2606.08696 [cs.LG]
(or arXiv:2606.08696v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2606.08696 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 300 words
Related coverage
Agentic Search for Counterfactual Recourse under Fixed LLM Budgets
arXiv · Jun 9, 2026
Why do models task game?
AI Alignment Forum · Aug 6, 2026
EvoAlloc: A Self-Evolving Resource Allocation Agent for Efficient Program Evolution
arXiv · Oct 10, 2026
Untrusted advice for AI control: Short, strong advice significantly uplifts weak LLMs
LessWrong · Jul 27, 2026