Skip to content

The Agent Capability Problem: Predicting Solvability Through Information-Theoretic Bounds

🕒 Published (v1): 2025-12-08 15:21 UTC · Source: Arxiv · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

The Agent Capability Problem (ACP) is a theoretical framework that predicts, before execution, whether an autonomous agent can solve a problem within a given resource budget, by framing search as information acquisition. The core quantity, C_effective = (I_total / I_s) × C_s, is proven to lower-bound expected search cost and is validated empirically on LLM-based slope identification and graph coloring tasks.

Problem

Autonomous agents waste resources attempting problems they cannot solve within budget, or conservatively skip solvable ones, because no principled pre-execution solvability criterion exists. Existing frameworks rely on empirical heuristics rather than theory-grounded, upfront resource estimates.

Method

ACP models problem-solving as sequential uncertainty reduction over a hypothesis space Θ. Three quantities are defined: total information required I_total = H(1(θ ∈ Θ_goal)) (entropy of the goal indicator under the prior), per-action information gain I_s = I(1(θ ∈ Θ_goal); y | a) (mutual information between outcome and goal indicator), and action cost C_s. The effective cost C_effective = (I_total / Ī_s) × C̄_s is computed a priori using a Gaussian process surrogate to estimate I_s via Monte Carlo sampling over near-optimal actions. A martingale stopping-time analysis (Theorem 3.1) proves C_effective is a lower bound on expected cost, with an additive upper bound involving the overshoot term M_2 / μ_inf². A high-probability budget estimate follows from Hoeffding's inequality. During search, ACP biases action ordering toward maximum expected-information-gain-per-cost.

Key Contributions

  • Formal definition of the Agent Capability Problem: predict solvability under budget constraints before search begins.
  • Proof that C_effective lower-bounds expected search cost (Theorem 3.1) with tight additive and probabilistic upper bounds.
  • Algorithm 1: a GP-based a priori cost estimator with error bounds from Monte Carlo and RKHS surrogate analysis.
  • Empirical validation that ACP predictions track LLM agent performance on noisy slope identification across noise levels.
  • Empirical validation on 3-coloring of random graphs (n ∈ {8,10,12,15}; 750 instances): ACP satisfies C_eff ≤ C in every trial and reduces node expansions vs. random and greedy baselines.
  • Extension to approximation algorithms: relaxing accuracy ε enlarges Θ_goal(ε), reducing I_total(ε); inapproximability maps to I_total = ∞.

Results

  • Slope identification: ACP prediction consistently lower-bounds actual LLM agent steps across noise levels σ; bound gap widens with noise, consistent with M_2 / μ_inf² term.
  • Graph 3-coloring (Table 1, node expansions, lower = better):
  • (n=8, p=0.25): Random 9.16, Greedy 8.00, ACP 8.00, Predicted 8.00
  • (n=10, p=0.30): Random 13.64, Greedy 10.16, ACP 10.00, Predicted 10.00
  • (n=12, p=0.35): Random 27.34, Greedy 13.10, ACP 13.04, Predicted 12.00
  • (n=15, p=0.35): Random 47.40, Greedy 18.58, ACP 18.34, Predicted 15.00
  • (n=15, p=0.41): Random 39.46, Greedy 18.08, ACP 16.46, Predicted 15.00
  • ACP satisfies the lower-bound condition (C_eff ≤ C) across all 750 instances; overshoot increases with graph density, as theoretically predicted.
  • ACP matches or beats greedy on harder instances; improvements over greedy are modest on small/sparse graphs.

Limitations

  • Requires a GP surrogate whose accuracy depends on whether the true function lies in the kernel's RKHS; misspecification inflates C_effective estimation error.
  • Monte Carlo estimation of I_s introduces sampling error bounded by O(√(log(2/δ)/2S)); large action spaces make this expensive.
  • The lower bound gap (upper bound term M_2 / μ_inf²) can be large when information gains deteriorate severely (µ_inf ≪ I_s), providing loose predictions on hard instances.
  • Experiments are limited to two task types (1D parameter identification, small graph coloring); applicability to complex LLM agentic workflows is asserted but not demonstrated beyond these benchmarks.
  • Multi-agent coordination, dynamic environments, and non-stationary action costs are deferred to future work.

Relevance to Harnesses / Meta-Harnesses

ACP provides a principled pre-execution oracle for deciding whether to allocate a budget to a subtask—exactly the kind of decision a meta-harness must make when routing work across agents or deciding when to retry or abort a pipeline stage. The information-theoretic framing unifies active learning, Bayesian optimization, and RL curiosity under one solvability criterion, offering a design primitive for harnesses that need to prioritize subagent invocations by predicted cost-to-solve. The GP-based estimation algorithm (Algorithm 1) is directly implementable as a pre-flight check before expensive tool calls, enabling budget-aware orchestration. Future extensions to multi-agent coordination are directly relevant to meta-harness scheduling and resource partitioning.