Comp-MCTS uses agentic tree search for counterfactual recourse under LLM budget limits
Researchers propose Comp-MCTS, an agentic tree-search framework that maximizes the yield of unique, oracle-validated counterfactual recourse alternatives under a fixed LLM-call budget.
Score breakdown
The work addresses the practical economic and computational constraint of LLM-call costs in counterfactual recourse, showing that a structured agentic search strategy can produce more diverse, validated alternatives without increasing budget expenditure.
- 01The paper frames counterfactual recourse generation as a fixed-budget search problem in the LLM-agentic setting.
- 02The proposed framework, Comp-MCTS, is a training-free, oracle-only agentic tree-search approach.
- 03Comp-MCTS uses LLM-based proposal generation, oracle validation, and compression-guided pruning to allocate its budget.
Counterfactual recourse seeks to tell affected individuals what feature changes would flip an unfavorable prediction — for example, what would need to change for a loan application to be approved. While a single optimal explanation is the classical goal, affected individuals benefit more from a diverse set of feasible alternatives. LLMs are a natural tool for generating such alternatives, but each LLM call carries computational and economic cost, making the number of calls a dominant practical constraint. Yasuo Tabei's paper reframes the problem as a fixed-budget search: given a limited number of LLM calls, how can an agent maximize the yield of unique, oracle-validated counterfactuals?
The proposed solution, Comp-MCTS, is an agentic tree-search framework that operates in a training-free, oracle-only setting.
The proposed solution, Comp-MCTS, is an agentic tree-search framework that operates in a training-free, oracle-only setting. It allocates its fixed budget across three components: LLM-based proposal generation to suggest novel intervention directions, oracle validation to confirm whether proposed counterfactuals actually flip the model's decision, and compression-guided pruning to avoid redundant exploration. Evaluated on four real-world tabular datasets, Comp-MCTS substantially outperforms single-candidate LATS-style baselines in counterfactual yield. Against stronger multi-candidate variants, it achieves comparable or higher yield at similar or lower oracle-evaluation cost on three of four datasets, while also maintaining competitive proximity, sparsity, and novelty — the standard quality metrics for counterfactual recourse.
Key facts
- 01The paper frames counterfactual recourse generation as a fixed-budget search problem in the LLM-agentic setting.
- 02The proposed framework, Comp-MCTS, is a training-free, oracle-only agentic tree-search approach.
- 03Comp-MCTS uses LLM-based proposal generation, oracle validation, and compression-guided pruning to allocate its budget.
- 04The goal is to maximize the yield of unique, oracle-validated counterfactuals under a fixed LLM-call budget.
- 05Experiments were conducted on four real-world tabular datasets.
- 06Comp-MCTS substantially outperforms single-candidate LATS-style baselines in counterfactual yield.
- 07On three of four datasets, Comp-MCTS achieves comparable or higher yield at similar or lower oracle-evaluation cost versus multi-candidate variants, with competitive proximity, sparsity, and novelty.
Topics
Summary and scoring are generated automatically from the original article. We always link back to the publisher and never republish images or paywalled content. Last processed Jun 9, 2026 · 17:05 UTC. How this works →