Planners that chase near-term information gains can ignore low-information builds that unlock decisive future measurements and thus perform arbitrarily badly; the authors prove this separation and introduce CG-Plan, a capability-aware replanner that recovers the capability route in simulated testbeds.

Main Finding

Myopic experiment-selection rules that score candidate actions only by information obtainable within a fixed lookahead horizon (e.g., expected information gain per cost) can be arbitrarily suboptimal when some actions are constructive—i.e., they acquire capabilities that unlock downstream measurements. For every fixed lookahead depth d, the paper constructs instances where any such bounded-horizon, information-based planner either (a) pays arbitrarily more than the optimal policy (unbounded approximation ratio, Theorem 1) or (b) never reaches the quality threshold at all (Proposition 1). The root cause is that capability acquisition is invisible within the lookahead horizon and therefore gets zero score despite being essential to reach low-cost solutions. The authors propose CG-Plan, a capability-aware incremental planner with a cost-to-go heuristic h = hcap + hexp, that addresses this failure mode.

Key Points

• Formal model: goal-directed discovery is cast as a stochastic shortest-path (SSP) problem in belief space.

  • States s = (B, D, I, v): beliefs B, archive D, capability set I (which gates actions), version v.
  • Actions/edges are experiments with preconditions req(e), gains gain(e) (capabilities), cost c(e), and outcome laws P(o | e, M*).
  • Goal: reach confidence threshold on a target query q while minimizing expected cumulative cost.

• Two experiment types in the formal result:

  • Interventional (measurement) experiments: carry information about q (gain = ∅).
  • Constructive experiments: grant capabilities (gain ≠ ∅), are low-information (deterministic or near-deterministic outcomes), and change downstream action availability or costs.

• Myopic planner class Πd:

  • Policies that, at each decision, rank actions by a functional Fs(c, O≤d) that depends only on action cost and the joint distribution of observations reachable within at most d steps.
  • Includes standard sequential Bayesian optimal experimental design (BOED) with one-step expected information gain and other bounded-horizon information-per-cost rules.
  • Fs must satisfy monotonicity and zero-information dominance: an action yielding no information within the horizon is always ranked ≤ any action with strictly positive within-horizon information.

• Capability-indistinguishability Lemma (Lemma 1):

  • If more than d constructive steps remain before a precision probe becomes available, performing the next build or paying a null action (same cost, q-independent outcome) are observationally identical within a d-step horizon. Hence all Fs in Πd give them equal scores, and a positive-information direct probe strictly dominates them.

• Unbounded separation (Theorem 1):

  • For any fixed lookahead d and any performance factor ρ > 1, there exists an instance (parameters: chain length d+1, weak direct-probe signal γ, build cost cb, target tolerance ε) so that every policy in Πd costs at least ρ·OPT. Intuition: the optimal policy builds the chain (cost ~ (d+1)cb + 1) and then does a single precise probe; any Πd policy never starts the chain and must repeatedly use a low-signal direct probe, incurring cost that blows up as the direct probe signal γ → 0.

• Failure-to-reach (Proposition 1):

  • Under a small modification (a nuisance bit that confounds direct probes), a Πd policy that never breaks ties in favor of zero-information builds can be permanently confined to low-confidence observations and thus never reach the goal.

• CG-Plan (Capability-Gated Planning):

  • An incremental replanner based on SSP algorithms, using a delete-relaxation-derived heuristic h = hcap + hexp:
    • hcap: a capability-aware term computed from the capability graph (topology of gated actions); captures the minimal build cost needed to make decisive actions reachable—this term is not a function of within-horizon observation distributions and therefore lies outside Πd.
    • hexp: an expected-information-based term (covers expected cost of informative measurements once capabilities are available).
  • In the chain-gated setting the relaxation yields an admissible heuristic; CG-Plan uses this heuristic inside an incremental planning loop and a determinization of the AND/OR belief-space graph.

• Controlled experiments:

  • A testbed demonstrates the theoretical predictions: the performance gap between bounded-horizon myopic planners and CG-Plan arises only when gating is present, persists for every fixed lookahead, depends sharply on chain length, and remains when near-miss hypotheses are generated by a data-consistent proposer rather than by hand-crafted constructs.
  • Distractor-build and no-gating controls match theoretical expectations.

• Scope and limitations:

  • The proofs use adversarial instance families (chain length = d+1) intended as lower-bound witnesses; they do not claim that capability gates are ubiquitous in real scientific discovery.
  • The formal result applies to planners whose scoring depends only on bounded-horizon observation distributions; learned scores or LLM-based scorers may or may not fall into Πd depending on whether they encode capability-aware preferences.

Data & Methods

• Theoretical methods:

  • Formalization of discovery as an SSP in belief space (AND/OR graph of epistemic states).
  • Definition of the class Πd via Blackwell-type information order on within-horizon observation ensembles; proof of indistinguishability lemma and construction of instance family I(d, γ, cb, ε).
  • Use of information-theoretic stopping-cost lower bounds (Wald-type change-of-measure arguments) to show expected sample complexity for low-signal direct probes, producing unbounded approximation ratios as γ → 0.
  • Proofs and formal arguments are provided in appendices.

• Algorithmic method:

  • CG-Plan derives a cost-to-go heuristic from a delete-relaxation of the SSP (separating capability cost and expected measurement cost), and performs standard incremental replanning (determinization of belief-space AND/OR graph and SSP search).

• Empirical illustration:

  • Controlled synthetic testbed where parameters (chain length, lookahead horizon d, gating presence, direct-probe signal γ, build cost cb, proposer behavior) are varied.
  • Comparisons between bounded-horizon myopic planners (Πd policies) and CG-Plan, with controls for distractor builds and no-gating scenarios.
  • Measures: expected cost to reach confidence goal, failure-to-reach behavior, sensitivity to chain length and lookahead horizon.

• Data: synthetic/controlled testbed only (no external empirical dataset). Evaluation reports both stopping time and correctness (since model misspecification can allow confident but incorrect stopping).

Implications for AI Economics

• Mispricing of capability-building: Standard near-term, myopic information-per-cost metrics (e.g., expected information gain per dollar or time) systematically undervalue investments in capabilities (instruments, infrastructure, simulators, data pipelines, representational primitives) whose payoff appears only through newly enabled future actions. Economically, this is a classic option-value failure: short-horizon valuation neglects the option to access high-value future experiments.

• Underinvestment in shared/platform capabilities:

  • Lab- or firm-level decision rules that maximize immediate information yield may repeatedly choose cheap, low-value measurements and fail to invest in shared infrastructure that would lower the long-run cost of answering important queries. This suggests a role for centralized funding, subsidies, or coordination mechanisms to internalize the long-term option value of capabilities (public goods provision, platform subsidies, or coordinated R&D investments).

• R&D and product development sequencing:

  • In product experimentation or A/B testing ecosystems, firms that optimize only per-experiment short-term information can miss sequences of engineering/build steps that unlock decisive downstream experiments or product features. Cost-to-go-aware planning (like CG-Plan) can more efficiently schedule investment and experimentation to reach product goals with lower cumulative cost.

• Market dynamics and platform lock-in:

  • Capability gates create network effects and path dependence: actors who first invest in certain capabilities can access classes of downstream actions (experiments, analyses) more cheaply, creating competitive advantages. Myopic selection exacerbates this by favoring visible measurements; strategic policy or investment can change market equilibria.

• Evaluation and policy design:

  • Regulators and funders should be wary of funding models that reward immediate gains (e.g., per-publication or per-experiment metrics). Evaluations should account for capability-induced reachability changes and the option value of building shared infrastructure.
  • When assessing grant proposals or corporate R&D projects, include explicit cost-to-go analyses that weigh capability-building paths even if they produce little immediate information.

• Practical recommendations for AI/economics practitioners:

  • Incorporate capability-aware terms into experiment-selection objectives: estimate minimal build costs (hcaps) needed to enable decisive downstream probes and add to expected-information terms (hexp).
  • Use incremental replanning with capability heuristics rather than fixed bounded-horizon selection rules.
  • Perform backtests or simulations on historical project data to detect capability gates (test whether short-horizon selectors would have missed lower-cost capability routes).
  • Fund and share foundational capabilities (simulators, data access pipelines, calibrated assays) as public or consortium goods to overcome collective myopia.
  • When training learned scorers / LLM-based selectors, explicitly include capability-option features or auxiliary supervision that recognizes long-horizon enabling effects, so they do not collapse into Πd-like behavior.

• Modeling implications:

  • The reachability axis introduced in this paper complements existing hardness axes (curvature/submodularity and adaptivity gaps). Economic models of discovery, innovation, and experimentation should include reachability/gating structure to accurately predict agent behavior and welfare under different incentive designs.

• Caveats:

  • The separation results are worst-case/adversarial constructions; the extent of capability gating in real-world scientific or product domains is an empirical question. The policy implications recommend empirical diagnosis (simulations and historical backtests) before wholesale changes in evaluation or funding regimes.