Agentic Search for Counterfactual Recourse under Fixed LLM Budgets

Counterfactual recourse generation under fixed LLM budgets shifts from finding a single optimal explanation to efficiently generating a diverse set of oracle-validated alternatives, which is crucial for users who benefit from multiple feasible options. This work proposes Comp-MCTS, an agentic tree-search framework that maximizes the yield of unique, oracle-validated counterfactuals by strategically allocating a fixed LLM call budget toward novel intervention directions through proposal generation and compression-guided pruning.

Problem Formulation

The research frames counterfactual recourse generation as a fixed-budget search problem:

1. The goal is to maximize the yield of unique, oracle-validated counterfactuals, denoted as maximizing the size of the set after canonicalization: max Unique(S).

2. This maximization is subject to two primary constraints: every candidate must be approved by the oracle (∀x′ ∈ S, f(x′) = 1), and the total cost of generating these candidates must not exceed a fixed LLM-call budget (cost(S) ≤ BLLM).

3. Secondary objectives guide the search toward highquality counterfactuals that are easy for the user to act upon, specifically favoring: (i) Proximity (small, actionable changes), (ii) Sparsity (few feature changes), and (iii) Novelty (diversity within the set S).

Search Framework: Comp-MCTS

Comp-MCTS is an agentic tree search method based on Monte Carlo Tree Search [9], [10] designed to manage the fixed budget effectively. It modifies the standard MCTS loop by integrating three key components:

1. Multi-candidate Expansion: In each step, the LLM generates K candidate feature edits in a single inference call, maximizing information yield per LLM call.

2. Prompt-as-Memory: To avoid redundant exploration, the LLM is made stateful by constructing a context summary, Hctx(x(n)), which includes an outcome-aware summary of previous trials, such as [APPROVED] / [REJECTED] / [PRUNED] status tags for nodes on the path. This history is truncated to maintain prompt budget locality and noise reduction.

3. Compression-Guided Pruning: Before oracle evaluation, candidates are filtered using a search-time redundancy proxy, the Normalized Information Gain ∆C (Eq. 3). A candidate is pruned if "∆C < θ, where ∆C measures the gain in compressed size when combined with the compression history Hcomp. This mechanism is introduced to allocate budget toward novel intervention directions by removing redundant / low-information-gain candidates."

Multi-Objective Reward Shaping

The simulation phase utilizes a multi-objective shaped reward function, r(x(nk)), to guide the search toward the desired trade-offs:

r(x(nk)) = g(p(x(nk))) × w1p(...) + w2sprox(...) + w3sspar(...) + w4snov(...)

This reward prioritizes oracle validity (via the soft gate g), proximity (proximity score sprox), sparsity (sparsity score sspar), and novelty (novelty score snov). The raw weights are internally normalized to sum to 1. This shaping ensures that the search balances fidelity with user-centric preferences, guiding it away from safe but invalid edits by suppressing low-probability candidates via the soft gate g(p).

Empirical Findings

Experiments across four real-world tabular datasets (Loan, Adult, Credit, HELOC) demonstrate that Comp-MCTS substantially outperforms single-candidate LATS-style baselines in the yield of unique, oracle-validated counterfactuals. Specifically:

CompMCTS substantially outperformed single-candidate LATS-style baselines in the yield of unique, oracle-validated counterfactuals.

The method achieves favorable quantity–quality–efficiency trade-offs, showing comparable or higher yield at similar or lower oracle-evaluation costs on three of the four datasets. Furthermore, pruning comparisons reveal that compression-guided pruning offers a significant oracle cost reduction at comparable yield on Adult, and in some cases, even better efficiency than embedding-based pruning.

Comparison with Existing Work

Comp-MCTS is compared against both LATS-style baselines and oracle-budgeted non-LLM methods (like DiCE or Growing Spheres). The paper highlights that while convergence-oriented agentic searches tend to concentrate the returned options on a few similar options, Comp-MCTS addresses this by explicitly targeting a diverse set of valid and feasible alternatives. The results show that Comp-MCTS dominates original K=1 LATS variants in terms of unique valid yield across all four datasets.

Here are specific improvements for AI systems based on the Comp-MCTS framework described in this paper, detailing what these improved systems can achieve:

---

AI System Improvements Derived from Comp-MCTS:

1. Improve Counterfactual Generation Yield Under Strict LLM Budget Constraints:

The system will be fundamentally redesigned to move beyond single-candidate generation (like standard LATS) by implementing a Monte Carlo Tree Search (MCTS) structure.

• Specific Capability: Generate a significantly higher yield of unique, oracle-validated counterfactuals from a fixed, limited number of LLM calls (e.g., 30 LLM calls).

• Mechanism: Comp-MCTS allocates the budget dynamically across novel intervention directions using LLM-based proposal generation, strict black-box oracle validation, and compression-guided pruning.

2. Enhance Trade-off Optimization (Quantity vs. Quality):

The system will incorporate a multi-objective reward function into the search process, allowing users to explicitly tune the desired output characteristics rather than optimizing for a single metric (like proximity).

• Specific Capability: Produce counterfactual sets that are simultaneously actionable, sparse, and diverse.

• Mechanism: The reward function in Comp-MCTS balances four objectives: oracle validity (primary), proximity (actionability/small edits), sparsity (simplicity/few feature changes), and novelty (diversity within the set). Users can adjust the weights of these objectives via reward shaping.

3. Minimize Redundancy and Optimize Budget Efficiency:

The system will actively suppress redundant search paths to ensure every LLM call contributes new information, directly addressing the primary constraint of fixed budgets.

• Specific Capability: Maximize the information yield per LLM call by avoiding near-duplicate feature change patterns.

• Mechanism: Compression-Guided Pruning uses a deterministic canonicalization function and a compression history metric to calculate an Information Gain score. Candidates with low gain are pruned before expensive oracle validation, ensuring the budget is spent on genuinely novel directions.

4. Improve Search Robustness Against Adversarial Traps:

The system will be designed to mitigate the risk of generating semantically meaningless edits that exploit model vulnerabilities.

• Specific Capability: Produce counterfactuals that are more likely to correspond to semantically meaningful feature changes, rather than just minimal input-space perturbations.

• Mechanism: The search framework explicitly prioritizes novelty and uses a soft gate in the reward function to suppress low-probability candidates, steering the search away from potentially dangerous boundary crossings.

5. Adapt Search Strategy Based on Contextual History (Prompt-as-Memory):

The system will maintain stateful knowledge across successive LLM calls, leading to more coherent and less repetitive generation strategies.

• Specific Capability: Generate a sequence of edits that are contextually informed by prior successes and failures in the search path.

• Mechanism: The Prompt-as-Memory component constructs a compact, outcome-aware history (status tags for [APPROVED], [REJECTED], and [PRUNED]) that is fed into the LLM prompt for each new candidate generation step.

6. Provide Robust Performance Across Diverse Data Types:

The architecture is designed to perform effectively across various tabular data structures by employing flexible parsing and distance metrics.

• Specific Capability: Generate high-quality recourse for numerical, categorical, and mixed feature sets (as demonstrated by performance on Loan, Adult, Credit, HELOC datasets).

• Mechanism: The system uses a mixed distance metric combining dimension-normalized L2 distance (for numerical features) and mean Hamming distance (for categorical features), allowing it to evaluate actionability consistently across feature types.

7. Enable Comparative Benchmarking of Generative vs. Non-Generative Methods:

The framework provides a standardized, budget-aware setting for rigorously comparing the performance of different recourse generation paradigms.

• Specific Capability: Quantify the precise efficiency and quality trade-offs between an agentic search approach (Comp-MCTS) and traditional generative methods (like Diffusion or CCHVAE) when constrained by a fixed inference budget.

• Mechanism: By fixing the LLM call budget (BLLM), the system allows for direct comparison of how effectively different search strategies convert that limited resource into actionable recourse versus merely generating plausible samples.