# Autonomous Assessment of Generalizability of AI Agent Capabilities

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

## 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 20 of its 43 references that are in the map.
- First posted on arXiv 18 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, 20 of 20)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [π0.5: a Vision-Language-Action Model with Open-World Generalization](https://mlsanity.com/paper/2504.16054/) (2025)
- [On the Utility of Learning about Humans for Human-AI Coordination](https://mlsanity.com/paper/1910.05789/) (2019)
- [DeepXplore: Automated Whitebox Testing of Deep Learning Systems](https://mlsanity.com/paper/1705.06640/) (2017)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [PDDLGym: Gym Environments from PDDL Problems](https://mlsanity.com/paper/2002.06432/) (2020)
- [LLMs as Planning Formalizers: A Survey for Leveraging Large Language Models to Construct Automated Planning Models](https://mlsanity.com/paper/2503.18971/) (2025)
- [Text2World: Benchmarking Large Language Models for Symbolic World Model Generation](https://mlsanity.com/paper/2502.13092/) (2025)
- [Efficient, Safe, and Probably Approximately Complete Learning of Action Models](https://mlsanity.com/paper/1705.08961/) (2017)
- [Active Goal Recognition](https://mlsanity.com/paper/1909.11173/) (2019)
- [Learning Portable Representations for High-Level Planning](https://mlsanity.com/paper/1905.12006/) (2019)
- [One Life to Learn: Inferring Symbolic World Models for Stochastic Environments from Unguided Exploration](https://mlsanity.com/paper/2510.12088/) (2025)
- [From Real World to Logic and Back: Learning Generalizable Relational Concepts For Long Horizon Robot Planning](https://mlsanity.com/paper/2402.11871/) (2024)
- [Learning Lifted STRIPS Models from Action Traces Alone: A Simple, General, and Scalable Solution](https://mlsanity.com/paper/2411.14995/) (2024)
- [Autonomous Capability Assessment of Sequential Decision-Making Systems in Stochastic Settings (Extended Version)](https://mlsanity.com/paper/2306.04806/) (2023)
- [Invariant Synthesis for Incomplete Verification Engines](https://mlsanity.com/paper/1712.05581/) (2017)
- [Data-Driven Invariant Learning for Probabilistic Programs](https://mlsanity.com/paper/2106.05421/) (2021)
- [Integrating Reinforcement Learning, Action Model Learning, and Numeric Planning for Tackling Complex Tasks](https://mlsanity.com/paper/2502.13006/) (2025)
- [HDDLGym: A Tool for Studying Multi-Agent Hierarchical Problems Defined in HDDL with OpenAI Gym](https://mlsanity.com/paper/2505.22597/) (2025)
- [CrafterDojo: A Suite of Foundation Models for Building Open-Ended Embodied Agents in Crafter](https://mlsanity.com/paper/2508.13530/) (2025)

## Abstract (arXiv)

Safe deployment of black-box AI (BBAI) systems such as foundation model agents requires methods for evaluating their capabilities in novel settings. We define an agent's capability as its ability to achieve a short term objective and formalize the problem of learning models that predict whether, with what effects, and under what conditions, an agent can perform a capability. We introduce Monte Carlo Query Search (MCQS), an active query-synthesis method for learning symbolic stochastic capability models of BBAIs. MCQS models capabilities as conditional probability distributions over outcomes and formulates capability evaluation as an active learning problem over policies. We use Monte Carlo tree search to synthesize queries that maximally distinguish between extremal capability hypotheses: the lattice meet and join corresponding to the most pessimistic and optimistic models consistent with observed behavior. Executing these queries yields trajectories that prune inconsistent hypotheses. We prove soundness, completeness, and convergence properties under standard realizability and sampling assumptions. Experiments with multiple BBAI systems show that MCQS learns accurate capability models more efficiently than baseline query strategies, enabling systematic characterization of agent capability boundaries with fewer interactions.