Can an LLM agent figure out the rules of an unseen system just by poking at it and reading the responses? A new paper on arxiv tests that question directly, using a formal framework from automata theory, and finds that current models are not yet up to the task.
Agentic Automata Learning as a Benchmark
The researchers propose what they call agentic automata learning, a controlled testbed for measuring how well tool-calling LLM agents can reverse-engineer hidden environments through interaction. The setup is clean and well-defined: an agent must discover a hidden deterministic finite automaton (DFA) by querying an oracle.
A DFA is a formal structure that accepts or rejects strings based on a set of states and transitions. Think of it as a tiny program with a fixed number of states, each one reading an input character and moving to the next state accordingly. The agent does not know the DFA's structure. It can only learn by asking questions.
The agent has two types of queries available. Membership queries ask whether a specific string belongs to the language the DFA accepts. Equivalence queries ask whether a proposed DFA matches the hidden one. This mirrors classical automata-learning algorithms like L* and RPNI, which have been studied for decades and serve as strong baselines.
Performance Collapses as DFAs Grow
The team evaluated state-of-the-art LLMs on this task and found that performance drops sharply as the DFA increases in size. Small automata with a handful of states are tractable. Larger ones with more states and transitions quickly become overwhelming.
Reasoning models, the variants trained specifically for multi-step logical thinking, performed markedly better than non-reasoning models. But even reasoning models hit a wall. The gap between LLM performance and classical algorithms widened fast as complexity increased.
Classical automata-learning algorithms like L* are designed for exactly this problem. They make optimal use of membership and equivalence queries, constructing hypotheses and refining them with provable guarantees. The LLMs, by contrast, stumbled in predictable ways.
Where Agents Go Wrong
The researchers analyzed agent trajectories to understand the failure modes. Three recurring problems showed up across models and task sizes.
Query planning was the first issue. Agents struggled to decide which string to query next. Classical algorithms choose queries based on a formal strategy that maximizes information gain. LLMs tended to pick strings that were either redundant or low-information, wasting queries without narrowing the hypothesis space.
Evidence integration was the second problem. Agents received answers to their queries but failed to synthesize those answers into a coherent picture. Each query result was treated somewhat in isolation rather than being incorporated into a growing model of the DFA.
Hypothesis construction was the third failure point. Even when agents had gathered enough information to propose a DFA, the proposals were often structurally inconsistent or incomplete. The agents could not reliably translate a collection of query results into a valid automaton.
What This Means for Agentic AI
The results are specific to automata learning, but the implications extend to any task where an agent must interact with an unknown system to build an internal model. Tool-calling LLM agents in production face similar challenges: they must decide which tools to call, interpret the results, and update their understanding of the environment.
The paper suggests that current LLMs lack the structured reasoning needed for efficient interactive discovery. They can sometimes perform non-trivial inference, but they are far less robust and far less efficient than algorithms designed for the problem. For teams building agents that need to explore and learn from their environment, this is a concrete signal that specialized reasoning strategies or hybrid approaches may be necessary.
The formal nature of the benchmark makes it a useful yardstick for future models. Because DFAs are well-understood and automata-learning algorithms provide clear baselines, any improvement in LLM performance on this task would represent genuine progress in interactive reasoning, not just a better score on a subjective evaluation.