Agentic Search for Counterfactual Recourse under Fixed LLM Budgets

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.