Agentic Search for Counterfactual Recourse under Fixed LLM Budgets

• URL: http://arxiv.org/abs/2606.08696v1
• Date: Sun, 07 Jun 2026 15:53:10 GMT
• Title: Agentic Search for Counterfactual Recourse under Fixed LLM Budgets
• Abstract summary: We propose Comp-MCTS, an agentic tree-search framework that maximizes the yield of unique, oracle-validated counterfactuals.<n>We show that Comp-MCTS substantially outperforms single-candidate LATS-style baselines in the yield of unique, oracle-validated counterfactuals.
• Score: 0.033842793760651545
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 Comp-MCTS, an agentic tree-search framework that maximizes the yield of unique, oracle-validated counterfactuals under this budget while maintaining favorable quantity--quality trade-offs. Comp-MCTS allocates the budget toward novel intervention directions via LLM-based proposal generation, oracle validation, and compression-guided pruning, in a training-free, oracle-only setting. Experiments on four real-world tabular datasets show that Comp-MCTS substantially outperforms single-candidate LATS-style baselines in the yield of unique, oracle-validated counterfactuals, and offers favorable quantity--quality--efficiency trade-offs against stronger multi-candidate variants: comparable or higher yield at similar or lower oracle-evaluation cost on three of four datasets, plus competitive proximity, sparsity, and novelty.

Related papers

• Instance-Optimal Estimation with Multiple LLM Judges on a Budget [84.31744861038106]
  We formalize this question as *budgeted heteroskedastic multi-judge estimation*.<n>Given $K$ prompt-response pairs, $J$ judges with known costs, and unknown query-judge variances, the goal is to estimate a bounded score vector while minimizing an $ell_p$-error.<n>We prove that EST-IVWE matches the oracle IVWE rate up to lower-order terms in the budget.
  arXiv  Detail & Related papers  (2026-05-22T08:26:08Z)
• Mixture of Complementary Agents for Robust LLM Ensemble [28.210955621253863]
  Multi-AI collaboration, such as ensembling or debating large language models (LLMs), is a promising paradigm for aggregating information and boosting performance.<n>Existing approaches primarily focus on accuracy (picking the strongest models) or diversity (ensuring variety)<n>We reframe proposer selection as a selection problem akin to feature selection, where the value of an LLM lies in its complementarity with others.
  arXiv  Detail & Related papers  (2026-05-21T21:29:05Z)
• Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data [57.996437077411315]
  We study the reasoning behavior of large language models (LLMs) under limited computation budgets.<n>We introduce an anytime reasoning framework and the Anytime Index, a metric that quantifies how effectively solution quality improves as reasoning tokens increase.<n> Experiments on NaturalPlan (Trip), AIME, and GPQA datasets show consistent gains across Grok-3, GPT-oss, GPT-4.1/4o, and LLaMA models.
  arXiv  Detail & Related papers  (2026-01-16T07:09:30Z)
• Aligning LLMs on a Budget: Inference-Time Alignment with Heuristic Reward Models [23.37504394417425]
  We propose HIA (Heuristic-Guided Inference-time Alignment), a tuning-free, black-box-compatible approach that uses a lightweight prompt.<n>We find that HIA is effective under low-inference budgets with as little as one or two response queries.
  arXiv  Detail & Related papers  (2025-08-07T08:54:27Z)
• Efficient LLM Collaboration via Planning [56.081879390960204]
  Small and large models take turns acting as planner and executor, exchanging plans in a multi-stage cascade to collaboratively solve tasks.<n>We demonstrate that COPE achieves performance comparable to large proprietary models, while drastically reducing the inference API cost.
  arXiv  Detail & Related papers  (2025-06-13T08:35:50Z)
• Minimax and Communication-Efficient Distributed Best Subset Selection with Oracle Property [0.358439716487063]
  The explosion of large-scale data has outstripped the processing capabilities of single-machine systems. Traditional approaches to distributed inference often struggle with achieving true sparsity in high-dimensional datasets. We propose a novel, two-stage, distributed best subset selection algorithm to address these issues.
  arXiv  Detail & Related papers  (2024-08-30T13:22:08Z)
• Towards Efficient LLM Grounding for Embodied Multi-Agent Collaboration [68.29746557968107]
  We propose a novel framework for multi-agent collaboration that introduces Reinforced Advantage feedback (ReAd) for efficient self-refinement of plans.<n> Experiments on Over-AI and a difficult variant of RoCoBench show that ReAd surpasses baselines in success rate, and also significantly decreases the interaction steps of agents.
  arXiv  Detail & Related papers  (2024-05-23T08:33:19Z)
• Optimising Calls to Large Language Models with Uncertainty-Based Two-Tier Selection [80.63946798650653]
  Decision centers on whether to use a large LLM with better performance or a smaller one with reduced costs. We propose a simpler solution; we use only the uncertainty of the generations of the small LLM as the decision criterion. Our experiments reveal this simple solution optimally balances cost and performance, outperforming existing methods on 25 out of 27 experimental setups.
  arXiv  Detail & Related papers  (2024-05-03T14:38:59Z)
• Efficient Prompt Optimization Through the Lens of Best Arm Identification [50.56113809171805]
  This work provides a principled framework, TRIPLE, to efficiently perform prompt selection under an explicit budget constraint. It is built on a novel connection established between prompt optimization and fixed-budget best arm identification (BAI-FB) in multi-armed bandits (MAB)
  arXiv  Detail & Related papers  (2024-02-15T05:31:13Z)
• On Leveraging Large Language Models for Enhancing Entity Resolution: A Cost-efficient Approach [7.996010840316654]
  We propose an uncertainty reduction framework using Large Language Models (LLMs) to improve entity resolution results. LLMs capitalize on their advanced linguistic capabilities and a pay-as-you-go'' model that provides significant advantages to those without extensive data science expertise. We show that our method is efficient and effective, offering promising applications in real-world tasks.
  arXiv  Detail & Related papers  (2024-01-07T09:06:58Z)
• Solving Multistage Stochastic Linear Programming via Regularized Linear Decision Rules: An Application to Hydrothermal Dispatch Planning [77.34726150561087]
  We propose a novel regularization scheme for linear decision rules (LDR) based on the AdaSO (adaptive least absolute shrinkage and selection operator) Experiments show that the overfit threat is non-negligible when using the classical non-regularized LDR to solve MSLP. For the LHDP problem, our analysis highlights the following benefits of the proposed framework in comparison to the non-regularized benchmark.
  arXiv  Detail & Related papers  (2021-10-07T02:36:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.