# Capability-Gated Planning: Cost-to-Goal Discovery and the Limits of Myopic Experiment Selection

arXiv: https://arxiv.org/abs/2608.05085 · HTML: https://mlsanity.com/paper/2608.05085/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 5 Aug 2026.

## Builds on (most cited first, 21 of 21)

- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [The AI Scientist: Towards Fully Automated Open-Ended Scientific Discovery](https://mlsanity.com/paper/2408.06292/) (2024)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [The AI Scientist-v2: Workshop-Level Automated Scientific Discovery via Agentic Tree Search](https://mlsanity.com/paper/2504.08066/) (2025)
- [Accelerating scientific discovery with Co-Scientist](https://mlsanity.com/paper/2502.18864/) (2025)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Variational Bayesian Optimal Experimental Design](https://mlsanity.com/paper/1903.05480/) (2019)
- [DESPOT: Online POMDP Planning with Regularization](https://mlsanity.com/paper/1609.03250/) (2016)
- [Deep Adaptive Design: Amortizing Sequential Bayesian Experimental Design](https://mlsanity.com/paper/2103.02438/) (2021)
- [Kosmos: An AI Scientist for Autonomous Discovery](https://mlsanity.com/paper/2511.02824/) (2025)
- [On Nesting Monte Carlo Estimators](https://mlsanity.com/paper/1709.06181/) (2017)
- [Empowerment -- an Introduction](https://mlsanity.com/paper/1310.1863/) (2013)
- [Pandora's Box Problem with Order Constraints](https://mlsanity.com/paper/2002.06968/) (2020)
- [Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions](https://mlsanity.com/paper/1608.00673/) (2016)
- [Online Learning for Min Sum Set Cover and Pandora's Box](https://mlsanity.com/paper/2202.04870/) (2022)
- [Optimal Value of Information in Graphical Models](https://mlsanity.com/paper/1401.3474/) (2014)
- [Weitzman's Rule for Pandora's Box with Correlations](https://mlsanity.com/paper/2301.13534/) (2023)
- [(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing](https://mlsanity.com/paper/1902.01461/) (2019)
- [Why LLMs Fail at Causal Discovery and How Interventional Agents Escape](https://mlsanity.com/paper/2605.27567/) (2026)

## Abstract (arXiv)

Systems that automate scientific discovery must repeatedly decide which experiment to run, which hypothesis to test, which tool to build, and when to stop. Many systems make these decisions by maximizing a myopic score such as expected information gain per unit cost or a learned plausibility score. We identify a structural limitation of this approach. Some actions are constructive: they acquire an epistemic capability (an instrument, assay, pipeline, simulator, or abstraction) whose value lies not in the information returned immediately but in the future actions it makes available. When the least-cost route to a confident answer requires a chain of such constructions, a planner that scores actions only by information obtainable within a bounded horizon cannot value the first construction: it yields no information within the horizon and is dominated by any measurement with positive information, however small. We formulate goal-directed discovery as a stochastic shortest-path problem in belief space in which constructive experiments change the downstream action graph, and prove that for every lookahead depth d there is an instance on which every myopic information-maximizing planner has an unbounded approximation ratio, and a related instance on which it never reaches the goal. The mechanism is a capability-indistinguishability lemma: within the horizon, acquiring a capability can be observationally indistinguishable from paying for a null action. This establishes capability gating as a reachability axis of difficulty distinct from curvature (submodularity) and information order (adaptivity gaps). We introduce CG-Plan, an incremental replanner with a capability-aware cost-to-go heuristic h = h_cap + h_exp. In a controlled testbed, the performance gap appears only under gating, persists for every fixed horizon, and arises when near-miss hypotheses come from a data-consistent proposer.