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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 1 of its 11 references that are in the map.
- First posted on arXiv 8 Dec 2025.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

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

- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)

## Abstract (arXiv)

When should an autonomous agent commit resources to a task? We introduce the Agent Capability Problem (ACP), a framework for predicting whether an agent can solve a problem under resource constraints. Rather than relying on empirical heuristics, ACP frames problem-solving as information acquisition: an agent requires Itotal bits to identify a solution and gains Istep bits per action at cost Cstep, yielding an effective cost Ceff = (Itotal/Istep), Cstep that predicts resource requirements before search. We prove that Ceff lower-bounds expected cost and provide tight probabilistic upper bounds. Experimental validation shows that ACP predictions closely track actual agent performance, consistently bounding search effort while improving efficiency over greedy and random strategies. The framework generalizes across LLM-based and agentic workflows, linking principles from active learning, Bayesian optimization, and reinforcement learning through a unified information-theoretic lens.