Can LLM Agents Infer World Models?

Analysis

Why This Paper Matters

This paper addresses a fundamental question: can LLM agents, equipped with tool-calling capabilities, actively uncover hidden environments through interaction? While LLMs have shown impressive performance on static tasks, their ability to perform interactive discovery—where they must plan queries, integrate evidence, and form hypotheses—is less understood. The authors introduce a novel testbed based on automata learning, which offers a controlled and scalable way to measure this capability. This is significant because it bridges the gap between classic computational learning theory and modern LLM agent research, providing a rigorous benchmark that can guide future development.

The paper's findings are sobering: current LLM agents, despite their advanced reasoning abilities, struggle to match the efficiency and robustness of classic algorithms like L*. This highlights a critical gap in current AI systems: they are not yet reliable at interactive exploration and hypothesis refinement. The work also underscores the importance of reasoning models, which show marked improvements, but still fall short. This paper matters because it sets a clear benchmark for measuring progress in agentic learning and exposes specific weaknesses that need to be addressed.

Technical Contributions

• Agentic Automata Learning Framework: The paper formalizes the task of learning a hidden DFA through membership and equivalence queries, providing a clean and controllable environment for evaluating LLM agents.
• Scalable Testbed: The framework allows for systematic variation of task complexity (DFA size), enabling fine-grained analysis of performance degradation.
• Baseline Comparison: By comparing against classic automata-learning algorithms, the authors establish a strong baseline that highlights the relative inefficiency of LLM agents.
• Trajectory Analysis: The paper provides detailed analysis of agent behavior, identifying specific failure modes such as poor query planning, failure to integrate evidence, and flawed hypothesis construction.
• Evaluation of Reasoning Models: The study compares reasoning and non-reasoning LLMs, showing that reasoning models are significantly stronger, offering insights into the benefits of chain-of-thought in interactive settings.

Results

The paper reports that LLM agents' performance drops sharply as DFA size increases. For instance, while agents may succeed on small DFAs, their accuracy plummets on larger ones. Reasoning models (e.g., those with extended thinking) markedly outperform non-reasoning models, but even they are far less efficient than classic algorithms. The trajectory analysis reveals that agents often make redundant queries, fail to update their hypotheses based on new evidence, and propose incorrect DFAs. These results quantify the gap between LLM agents and algorithmic approaches, showing that current agents are not yet capable of robust interactive discovery.

Significance

This work has significant implications for the AI community. It provides a rigorous, controlled environment for evaluating and improving LLM agents' interactive learning abilities, which are crucial for real-world applications like autonomous experimentation, scientific discovery, and tool use. The identified failure modes offer actionable insights for future research, such as improving memory and hypothesis management in agents. Moreover, the benchmark can serve as a standard for measuring progress in agentic learning, much like other benchmarks in NLP. Ultimately, this paper pushes the field toward more capable and reliable AI agents that can actively learn from their environment.