Can LLM Agents Infer World Models? Evidence from Agentic Automata Learning
Type: kb/sources/types/snapshot.md
Author: Reef Menaged; Gili Lior; Shauli Ravfogel; Roee Aharoni; Gabriel Stanovsky Source: https://arxiv.org/pdf/2606.16576 Date: June 15, 2026 (preprint; arXiv:2606.16576v1) Project page: https://reefmenaged.github.io/Agentic_Automata_Learning
Abstract
We propose agentic automata learning to evaluate the extent to which tool-calling LLM agents can uncover hidden environments through interaction. In our setup, an agent should uncover a hidden deterministic finite automaton (DFA) by interacting with an oracle through (1) membership queries (“Does this string belong to the target language?”) and (2) equivalence queries (“Is this the target DFA?”). This yields a scalable testbed with controlled task complexity, measurable interaction efficiency, and strong baselines (classic automata-learning algorithms). Evaluating state-of-the-art LLMs, we find that performance drops sharply as DFA size increases. Reasoning models are markedly stronger than non-reasoning models, yet trajectory analyses reveal recurring failures in query planning, evidence integration, and hypothesis construction. Overall, our results show that current LLM agents can sometimes perform non-trivial interactive discovery, but remain far less robust and efficient than classic algorithms for the task.1
1 Introduction
LLMs are increasingly used as interactive agents across environments of varying complexity, from settings like games with fixed rules to dynamic environments such as navigation in open worlds (Park et al., 2025; Zheng et al., 2025). Despite their strong performance, it remains unclear whether LLMs can infer a correct world model of the environment they interact with, or whether they rely on local patterns and shallow heuristics (Vafa et al., 2024). Addressing this question requires controlled tasks in which the hidden structure of the environment is known, its complexity can be controlled systematically, and the agent’s discovery process can be observed throughout the interaction. Project page: https://reefmenaged.github.io/ Agentic_Automata_Learning. Figure 1: Agentic automata learning. An agent is tasked to identify a hidden DFA through successive interactions with the environment. Membership Queries ask whether a word is accepted by the hidden DFA (left), while Equivalence Queries submit a hypothesized DFA and ask whether it matches the hidden target. The environment either confirms equivalence or returns a counterexample on which the two DFAs differ (right). Active automata learning, exemplified in Figure 1, offers a well-studied formal framework for learning hidden structure via interaction (Rivest and Schapire, 1993; Isberner, 2015). In this classic formulation, a learner attempts to identify a hidden deterministic finite automaton (DFA) through a sequence of queries to an oracle representing the environment. Membership Queries ask whether a word belongs to the target language, while Equivalence Queries submit a hypothesis DFA, which the oracle either accepts or refutes with a counterexample, i.e., a word on which the hypothesis DFA and the hidden DFA disagree. While the task provides a simple and controlled framework for environment modeling, it is also useful for modeling real-world tasks. For instance, Rivest and Schapire (1993) framed it as an autonomous robot learning an unfamiliar deterministic environment through actions and observations, and more recently Vafa et al. (2024) examined whether LLMs can learn the world model of a deterministic environment from observations by casting a map of Manhattan as a DFA, finding that they struggle to do so.
In this work, we recast active automata learning as agentic automata learning. To do so, we initialize an oracle with a target DFA and equip an LLM agent with tools to perform membership and equivalence queries against the oracle. This formulation turns automata learning into a controlled task for testing whether LLM agents can infer latent structure through interaction. It provides formal measures for task complexity (e.g., the number of states in the DFA) as well as for discovery efficiency (e.g., the number of queries), and enables direct comparison with strong baselines, including the L∗ and TTT algorithms (Angluin, 1987, 1988; Isberner et al., 2014). Our results reveal that the task is challenging even for state-of-the-art LLMs and that substantial performance gaps exist across models. We find that the task becomes increasingly challenging as the environment complexity grows, as reflected in a sharp decline in success rates as the number of states in the DFA increases: for automata with 9 states, no model exceeds 25% success, while classic algorithms solve 100% of task instances. Discovery efficiency is also challenging: even when considering only successful runs, Gemini 3.1 Pro, the bestperforming model, requires approximately 45.8% more queries than the classic TTT algorithm. In addition, a clear performance gap emerges across models, particularly between reasoning and nonreasoning models: for example, on automata with 4–5 states, Gemini 3.1 Pro reaches 85% success, while GPT-5.4 without reasoning, Gemini 3.1 Flash Lite, and Llama-3.3-70B achieve 0% success. Beyond task performance, our analyses show that all models have substantial room for improvement in planning, reasoning, and proper use of accumulated information throughout the interaction. Models often fail to plan informative queries, reason inconsistently over accumulated evidence, or fail to reliably use prior observations when constructing hypotheses. These findings suggest that while advanced LLMs can perform non-trivial interactive discovery, they remain far from classic learners in both robustness and efficiency. To summarize, our main contributions are as follows: (1) We introduce agentic automata learning, a controlled framework for evaluating whether tool-calling LLM agents can infer latent structure through interaction; (2) show that advanced reasoning models can perform non-trivial interactive discovery, but degrade sharply as automata complexity increases; and (3) analyze interaction trajectories and identify recurring limitations in planning, reasoning, and consistent use of accumulated information.
2 Background: Automata Learning
Automata learning tests the extent to which learning algorithms are capable of discovering the structure of a hidden DFA from observations of which words it accepts or rejects. Automata learning is commonly divided into two paradigms: active automata learning, where the learner can interact with an oracle through queries, and passive automate learning, where the learner infers a DFA from a fixed set of labeled examples (Daelemans, 2010).
2.1 Active Automata Learning
In this setting, a learner interacts with an oracle through adaptively chosen queries in order to identify a hidden DFA (Isberner, 2015). The oracle has access to the hidden DFA and answers queries about the language it recognizes. Traditionally, there are two types of queries (Angluin, 1988, 1990). A Membership Query allows the learner to ask whether a given word is accepted by the hidden DFA, while an Equivalence Query allows the learner to propose a hypothesis DFA and test whether it is equivalent to the hidden DFA, which the oracle can either accept or refute with a counterexample, namely a word on which the hypothesis DFA and the hidden DFA disagree. Prior work has established formal complexity and evaluation measures, as well as efficient deterministic active automata learning algorithms (Angluin, 1987; Rivest and Schapire, 1993). Task complexity is typically characterized by the number of states in the minimal DFA accepting the language of the hidden DFA, while learning efficiency is measured by the number of queries required to identify the hidden DFA (Isberner, 2015). Classic learners such as L* and TTT solve this task through an iterative hypothesis-refinement process: they consider an hypothesis which matches all given observations using EQ, and when a counterexample is returned, use a polynomial number of MQs to construct a new hypothesis that again accounts for all given information while adding at least one previously unidentified state in the hidden DFA. These algorithms were proven to converge on the hidden DFA in polynominal time (Angluin, 1987; Isberner et al., 2014). This exemplifies several desired agentic real-world traits, including
maintaining a memory of observed behavior, reasoning over it, choosing actions based on previous interactions, and adapting to new information.
2.2 Passive Automata Learning
In passive learning, the learner does not query an oracle. Instead, it receives a fixed labeled sample of accepted and rejected words and must infer a DFA consistent with that sample (Murphy, 1996). Classical passive algorithms such as RPNI, EDSM, and Blue-Fringe learn automata from finite samples in this way (Oncina and Garcia, 1992; Lang et al., 1998). We use passive learning algorithms to assess the information gathered by LLM agents during interaction: given the labeled words collected by an agent, we test whether a passive learner can already infer the hidden DFA.
3 Agentic Automata Learning
In this section we formally define the task of agentic automata learning, which recasts the classic interactive automata learning for agentic tool-calling LLMs (§3). We then describe how task instances can be generated automatically at arbitrary scale by sampling DFAs while controlling for their complexity, and discuss how the task requires important agentic capabilities, such as adaptive planning, memory organization, and efficient tool use. Task definition. Let Σ be a finite alphabet, DΣ be the set of all DFAs over Σ, and A⋆ ∈ DΣ be a minimal DFA inducing the target language L⋆ ⊆ Σ∗. An agent interacts with an oracle OA⋆ through a sequence of tool calls, each termed a query. At each time step t = 1, . . . , T, the agent chooses one of two tool calls: (1) Membership Query, MQ : Σ∗ 7→ {0, 1} for some word w ∈ Σ∗, to which the oracle returns 1L⋆ {w}. (2) Equivalence Query, EQ : DΣ 7→ {⊤} ∪ Σ∗ for some hypothesis DFA A, to which the oracle returns either ⊤ if L(A) = L⋆, or a counterexample w ∈ L(A)△L⋆ if they differ. The agent’s prompt at time t contains the entire interaction history: ht−1 = ((a1, o1), . . . , (at−1, ot−1)), where ai is the query issued at step i and oi is the oracle response. See complete prompt examples in Appendix B. The goal of the agent is to identify the target language by issuing an equivalence query EQ(Â) such that: L(Â) = L⋆ . An interaction is successful if the oracle returns ⊤ for an equivalence query within a query budget T, while its cost is the number of queries issued up to and including the accepted equivalence query. The complexity of an interaction is defined by the number of states in A⋆. This is motivated by the classic active automata learning problem, where the number of states is a central factor affecting the efficiency of algorithms such as L* and TTT. Automatic Generation of Instances. A key advantage of agentic automata learning is that task instances can be generated procedurally and at arbitrary scale, while controlling their complexity through properties of the target DFA, such as the number of states. In particular, we use the Boltzmann sampling method, which samples uniformly from the space of accessible DFAs over a binary alphabet,2 and then applies rejection sampling to filter out non-minimal DFAs (Bassino and Nicaud, 2007). While in our experiments we keep the alphabet fixed, this sampling procedure itself does not inherently restrict the alphabet size. This procedural construction allows us to create arbitrarily many environments over a chosen alphabet, rather than relying on a fixed pool of predefined tasks or examples requiring expensive human annotation. The task measures core agentic capabilities. Agentic automata learning is designed to evaluate several capabilities of a language model operating as an interactive agent, including adaptive planning, reasoning from observations, memory organization and tool use, all of which are required to discover the latent structure of the environment defined by the hidden DFA. Adaptive planning is required as the model receives feedback from the environment after each query, and must choose a subsequent query that reduces uncertainty about the target DFA. Reasoning from observations is required as the accumulated interaction history forms a passive dataset of accepted and rejected words, from which the model can infer properties of the hidden structure. Memory organization is required as the model must maintain consistency with previous observations, avoiding hypotheses that contradict known evidence and queries whose answers
A DFA is accessible if every state can be reached from
the initial state by some input word.
Gemini 3.1 Pro Preview Deepseek-v4-Pro Gemini-3-Flash-Preview (thinking) GPT-5.4 (without thinking) Gemini-3.1-Flash-Lite-Preview Llama-3.3-70B-Instruct-Turbo 2 3 4 5 6 7 8 9 Minimal DFA States Total interaction cost ($) 2 3 4 5 6 7 8 9 Minimal DFA States Total runtime (hours) 2 3 4 5 6 7 8 9 Minimal DFA States Total tokens (millions) Figure 2: Computational cost, runtime, and token usage of model runs as the number of minimal DFA states increases. Each point is a run; the x-axis groups runs by the number of states, and point color indicates the model. are already implied by the interaction history. Finally, tool use is required as the interaction is mediated through membership and equivalence queries, which the model must invoke correctly with valid inputs.
4 Experimental Setup
In this section, we describe the different design choices and evaluation criteria used to assess LLMs on the agentic automata learning task. Models and metrics. We evaluate 6 advanced models: DeepSeek-V4-Pro (DeepSeek-AI, 2026), a 1.6T-parameter model, Gemini 3.1 Pro Preview, Gemini-3-Flash-Preview (thinking), Gemini- 3.1-Flash-Lite-Preview (Google, 2026), GPT-5.4 without thinking (OpenAI, 2026), Llama-3.3-70B- Instruct-Turbo (Meta, 2024). Unless otherwise specified, models are used in their vanilla configuration. The set includes models that differ in their use of reasoning tokens, size, architecture, and availability as closed-source or open-source systems. We did not include a GPT reasoning variant in the main evaluation due to the substantially higher computational cost of running a full evaluation, especially given that other reasoning models already provided sufficient coverage for comparison. In addition, a preliminary sample of one task instance per difficulty level did not indicate that this variant was likely to exhibit significantly different performance from the reasoning models evaluated in practice. We evaluate two aspects of model performance. First Success Rate measures the rate at which models successfully identify the hidden DFA: N N X i=1 Succ(M, xi), where Succ(M, xi) is a binary indicator of whether model M successfully infers the hidden DFA xi, and N is the number of sampled automata. Second, we measure interaction efficiency by measuring the difference between the number of tool calls made by a model M when it successfully finds the hidden DFA and the number of tool calls made by the classic algorithm over successful runs: |Ssucc| X i∈Ssucc (TCM (xi) − TCTTT(xi)) , where Ssucc denotes successful runs, and TCA(xi) denotes the number of tool calls used by algorithm A to identify the hidden DFA xi. Dataset construction. We sample an evaluation dataset consisting of 80 task instances evenly distributed into 4 complexity levels, defined by the number of states in the minimal DFA: 2–3, 4–5, 6–7, and 8–9. This provides a set of target DFAs for evaluating model performance across DFAs of the same complexity level. Although additional instances can be generated automatically, evaluation remains expensive in runtime and monetary cost. Each instance requires a long interactive run, which may involve tens to hundreds of queries and consume millions of tokens. As shown in Figure 2, runtime and cost increase sharply with DFA size, reaching up to about 20 hours, 30 million tokens,
and $50 per run. Overall, the total monetary cost of the full experimental suite was roughly $1,200. This amount aggregates costs across the services used in our evaluation, including Google Cloud credits for Gemini, the DeepSeek platform, Together AI for Llama, and the OpenAI platform for GPT. Query budget. The number of queries allowed in each instance is defined to be at most twice the number of queries required by the better of L∗ and TTT for the corresponding DFA, both of which have provable upper bounds on the number of queries. In particular, L* uses O(|Σ|n2m) queries (Angluin, 1987), while TTT uses O(|Σ|n2 + n log m) queries (Isberner et al., 2014), where n is the number of states in the minimal hidden DFA, |Σ| is the alphabet size, and m is the maximum counterexample length. Defining the budget as twice the number of queries guarantees that a correct solution exists within the allocated query budget. Oracle counterexample selection strategy. For each equivalence query, if the proposed DFA is not equivalent to the hidden DFA, the oracle must return a counterexample (a word on which the two DFAs disagree), yet the classic task formulation does not define which counterexample it should return. We return a counterexample designed to balance two considerations. On one hand, the length of the minimal counterexample directly affects the runtime of the classic learning algorithms and, consequently, the query budget allocated to the model. On the other hand, a minimal counterexample provides additional implicit information, since it implies that no shorter word distinguishes between the hypothesis DFA and the hidden DFA. Intuitively, if the oracle returns a minimal counterexample of length n, then the two DFAs agree on all words of length < n, allowing the agent to infer their membership without explicitly querying them. We therefore sample a short counterexample at random. A full description of the sampling procedure is provided in Appendix D. Task instruction and context construction. All models are provided with the same instruction describing the task and the interaction rules as defined in the agentic automata learning task (see Appendix A for the full instruction). At each interaction step, we construct the agent’s context from the observable information accumulated so far. Specifically, the context includes the previous queries issued by the agent, the oracle responses, counterexamples returned by equivalence queries, and the agent’s observable hypotheses or final answers. We do not preserve chain-of-thought reasoning across steps: only externally visible outputs and environment feedback are carried forward. This design keeps the interaction history comparable across models and avoids rapidly accumulating reasoning tokens in the context. After running all task instances, we verified that performance was not affected by context truncation. Specifically, for every task instance, the maximum constructed context throughout the interaction remained below the context-window capacity of the corresponding model. Appendix F reports the total constructed context size (including accumulated input and generated output tokens) at each interaction step for every task instance.
5 Results
Figure 3 presents our main evaluation results, reporting Success Rate which measures whether models identify the hidden DFA, and ∆ Tool Calls from TTT which measures interaction efficiency. We complement this analysis by differentiating between planning and reasoning errors in Figure 4 and examining non-informative query rates in Figure 5. Together, these results characterize task difficulty, reveal differences across models, and quantify the gap between LLM agents and classical active automata learning algorithms. We first highlight the main findings, then turn to a detailed error and cost analysis. Agentic automata learning is challenging even for state-of-the-art models and exposes substantial differences in their ability to learn through interaction. Figure 3 shows that the performance of all models declines as the number of states in the minimal DFA increases. For automata with 8–9 states, no model exceeds 25% success rate, whereas the classic algorithms solve all task instances with 100% success. The gap relative to classic algorithms is also reflected in interaction efficiency: in the same 8–9 state range, when considering only successful runs, Gemini 3.1 Pro, the best-performing model, uses about 45.8% more tool calls than TTT. Alongside the overall difficulty of the task, the framework also exposes substantial differences between models, particularly for automata with 4 states or more. A clear gap emerges between mod-
Gemini 3.1 Pro Preview Deepseek-v4-Pro Gemini-3-Flash-Preview (thinking) GPT-5.4 (without thinking) Gemini-3.1-Flash-Lite-Preview Llama-3.3-70B-Instruct-Turbo 2–3 4–5 6–7 8–9 Number of States in the Minimal DFA Success rate (%) → 2–3 4–5 6–7 8–9 TTT L Number of States in the Minimal DFA ← ∆ Tool Calls from TTT Figure 3: Model performance as the number of states in the minimal DFA increases. The left subplot shows success rate; L and TTT are omitted there because both achieve 100% success. The right subplot compares successful-run query cost relative to TTT: values above zero require more calls and values below zero require fewer. Some models are not shown in the right subplot because their success rates are low, so measuring tool calls is not meaningful, their average tool calls for successful runs are: Gemini-3-Flash: 0.55 (2–3), 16.67 (4–5); GPT-5.4: 2.64 (2–3); Gemini-3.1-Flash-Lite: -2.50 (2–3); Llama-3.3: 0.00 (2–3). els that employ reasoning mechanisms and those that do not: in the 4–5 state range, Gemini 3.1 Pro reaches 85% success, while Gemini 3 Flash, which applies reasoning only in part of the interaction steps, reaches 15% and shows intermediate performance. In contrast, GPT-5.4, Gemini 3.1 Flash Lite, and Llama-3.3-70B, which do not employ reasoning mechanisms, reach 0% success for automata with 4 states or more. LLMs do not seem to follow classical algorithms. A natural concern in evaluating LLMs on interactive automata learning is that they may have been pretrained on classical formulations of the problem, as well as with standard algorithms such as L∗ and TTT. If so, strong performance might reflect memorization or imitation of known algorithmic solutions rather than the model’s ability to solve the learning task interactively. We alleviate this concern in three ways. First, since classic algorithms are deterministic, exact imitation can be checked directly by comparing the sequence of queries up to recovery. We find no task instance in which models produces the same query sequence as a classical algorithm. Moreover, in some cases the model recovers the target DFA using fewer queries than the classic algorithms, further suggesting that it is not replaying a known algorithm. Table 1 shows a comparison of interactions between LLMs and classic algorithms. Second, we find that the best performing model (Gemini 3.1 Pro) overuses equivalence queries (EQs) in comparison to classic algorithms, in which the number of equivalence queries is bounded by the number of states in the hidden DFA. Gemini
3.1 Pro exceeds this bound in 92.5% of the task
instances, indicating behavior that differs from the query structure of the classical algorithms. Third, Gemini 3.1 Pro’s behavior violates a monotonicity property satisfied by the classic algorithms. For a task instance, monotonicity is preserved if for every hypothesis tested by an EQ, the number of states in that hypothesis is larger than the number of states in all previously tested hypotheses. We found that Gemini 3.1 Pro produced a non-monotonic hypothesis sequence in all interactions. This provides another indication that the model is not merely implementing a noisy or unstable variant of these algorithms.
5.1 Error Analysis
We conduct several analyses in order to better understand the performance of the models and shed light on which aspects of the task are more challenging to outline avenues for future research. Differentiating between planning and reasoning errors. We classify model failures into two mutually-exclusive categories: planning failures and reasoning failures. A planning failure occurs
Success Reasoning Failure Planning Failure 0 10 20 30 40 50 60 70 80 90 100 Gemini 3.1 Pro Deepseek-v4-Pro Gemini-3-Flash (thinking) GPT-5.4 (without thinking) Gemini-3.1-Flash-Lite Llama-3.3-70B-Instruct-Turbo Percentage of task instances Figure 4: Error analysis. Each row corresponds to a model, and each stacked bar shows the percentage of task instances classified as successful runs, reasoning failures, or planning failures. LLM-based learners Classic algorithms # step Gemini 3.1 Pro Llama-3.3-70B L⋆ TTT Tool Call Resp. Tool Call Resp. Tool Call Resp. Tool Call Resp.
1 EQ(∅) bba MQ(ϵ) 0 MQ(b) 1 MQ(ϵ) 0
2 EQ(Σ∗) aaa MQ(a) 0 MQ(a) 0 EQ(∅) bba
3 EQ(b ∈ w) ⊤ MQ(b) 1 MQ(ϵ) 0 MQ(bba) 1 4 — MQ(bb) 1 MQ(bb) 1 MQ(ba) 1 5 — MQ(ab) 1 MQ(ba) 1 MQ(a) 0 6 — MQ(ba) 1 EQ(b ∈ w) ⊤ MQ(b) 1 7 — EQ(¬ϵ) aa — MQ(aa) 0 8 — MQ(aa) 0 — MQ(baa) 1 9 — EQ(b ∈ w) ⊤ — EQ(b ∈ w) ⊤ Table 1: Example interactions between LLM and oracle (Resp. column), for the hidden DFA accepting all words containing at least one b, — indicates that the learner has already solved the problem. Gemini 3.1 Pro solves the task using only equivalence queries, whereas Llama-3.3-70B-Instruct-Turbo, L⋆ , and TTT use both membership and equivalence queries. In EQ notation, ∅ denotes the empty language, Σ∗ denotes all words, ¬ϵ denotes all non-empty words, and b ∈ w denotes the language of words containing b. when the model fails and none of the classic passive learning algorithms, RPNI, EDSM, or Blue-Fringe, can infer the hidden DFA from the observations accumulated by the model. In this case, we assume that the model did not collect sufficient information during interaction. In contrast, a reasoning failure occurs when the model fails, but at least one passive learning algorithm can infer the hidden DFA from the accumulated observations. Thus, the necessary information was available, but the model failed to infer the correct DFA from it. Figure 4 shows that all evaluated models suffer from both reasoning and planning failures, although stronger models have proportionally less planning failures compared to the weaker models, where planning failures are dominant. All tested LLMs tend to make non-informative queries as the interaction progresses. We measure how consistently LLMs use the information accumulated during interaction through the notion of non-informative queries: tool calls whose answers can be implied by previous oracle responses and therefore cannot provide new evidence. For membership queries, a query is noninformative if the same word has already been queried. For equivalence queries, a query is noninformative if it duplicates a previous hypothesis, or if the proposed DFA is already contradicted by known evidence; that is, if there exists a previously queried word that the hypothesis classifies differently from the oracle. For each model, we compute the percentage of non-informative queries issued at each interaction step across all task instances. Figure 5 shows that non-informative queries become increasingly common as interactions grow longer. After roughly 60 steps, even the most consistent model, DeepSeek-V4-Pro, issues noninformative queries about 20% of the time. This pattern appears across all evaluated LLMs, whereas classic active-learning algorithms maintain 0% noninformative queries by construction. These results suggest that as evidence accumulates in context, LLM agents increasingly struggle to organize and use it consistently.
Gemini 3.1 Pro Deepseek-v4-Pro Gemini-3-Flash (thinking) GPT-5.4 (without thinking) Gemini-3.1-Flash-Lite Llama-3.3-70B-Instruct-Turbo 20 40 60 80 100 Step number ← Non-informative queries (%) Figure 5: Non-informative query rate by interaction step. For each model and tool-call number, the value reports the percentage of queries at that step that are non-informative across all task instances. Curves are smoothed using a 1D Gaussian filter (σ = 2) for visualization. We report values up to step 100, as only a small number of task instances continue beyond this point.
5.2 Cost Analysis
A central question in modern evaluations of LLMs is the computational and monetary cost. This issue is especially important for agents, where each task instance may involve a long sequence of interactions: each additional interaction extends the context window and adds runtime. Figure 6 illustrates the cost of our evaluation framework, which grows linearly with the number of tool calls, with Gemini 3.1 Pro driving most of the cost. We further analyze the need for such budget, and find that it is critical and allows models to solve DFAs which they could not find with a smaller budget, as shown in Figure 9 in the Appendix.
6 Related Work
Recent benchmarks for LLM-based agents often evaluate models through end tasks in complex environments, such as web navigation, software engineering, tool use, or embodied interaction (Park et al., 2025; Zheng et al., 2025). While these benchmarks are important for measuring practical agent performance, their complexity makes it difficult to isolate specific capabilities such as adaptive information gathering, memory organization, and reasoning over accumulated observations. Prior work on learning world models with language models primarily focuses on training models, rather than interactive learning at inference time as required from an agent (Kuo et al., 2023; Vafa et al., Gemini 3.1 Pro Deepseek-v4-Pro Gemini-3-Flash (thinking) GPT-5.4 (without thinking) Gemini-3.1-Flash-Lite Llama-3.3-70B-Instruct-Turbo 1 1.25 1.5 1.75 2 Avg. Query-budget factor Average cost per task instance ($) Figure 6: Average cost as a function of the querybudget factor. The query budget factor determines the number of queries allocated to each task by multiplying the number of queries required by the more efficient classical learner between L and TTT. Here, we examine the average cost per task instance for factors of 1, 1.25, 1.5, 1.75, and 2. 2024). As a result, these approaches do not capture key agentic capabilities. In addition, these works do not analyze model performance as a function of changes in latent-structure complexity. In recent years, connections have also been established between neural networks and active automata learning (Weiss et al., 2018; Chen et al., 2024; Vazquez-Chanlatte et al., 2025). In these works, the model is trained to represent a DFA, which is subsequently extracted from the model’s weights using algorithms such as L.
7 Conclusion
We introduce agentic automata learning, a controlled framework for evaluating whether language models can infer hidden structure through interaction. By modeling environments as hidden DFAs and allowing membership and equivalence queries, the framework measures both final success and the discovery process. Our results show that even strong models struggle as complexity increases, with failures in accuracy, planning, reasoning, tool use, and management of accumulated information. These findings motivate evaluations that go beyond outcomes to examine how agents search, update beliefs, and use feedback over time. Future work can extend this framework beyond DFAs to environments with non-determinism or stochasticity. It could also relax the assumption of exact oracle feedback by introducing noisy, partial,
delayed, or incorrect signals, or by replacing equivalence queries with weaker feedback. Finally, the framework could serve not only for inference-time evaluation, but also as a training environment, for example through reinforcement learning.
8 Limitations
Our evaluation framework is costly in terms of runtime, token usage, and API spend, and these costs increase with task complexity. In total, the full evaluation suite cost approximately $1,200 for 480 runs, or $2.50 per datapoint on average, with Gemini 3.1 Pro accounting for most of the expense. This cost profile is not unique to our setting: recent work has noted that modern language-model benchmarks increasingly incur substantial computational costs, sometimes reaching thousands of GPU hours per evaluated model (Perlitz et al., 2024). For example, the recent ProgramBench reports an average evaluation cost of approximately $5 per task instance, twice the average cost per task instance incurred by our framework (Yang et al., 2026).
9 Acknowledgments
This research was supported in part by the Google Cloud Research Credits Program. We would like to thank Prof. Orna Kupferman for suggesting the automata-learning setting that inspired this work, and Prof. Dana Fisman and Gal Meirom for their valuable advice and insights.
References
Dana Angluin. 1987. Learning regular sets from queries and counterexamples. Inf. Comput., 75(2):87–106. Dana Angluin. 1988. Queries and concept learning. Mach. Learn., 2(4):319–342. Dana Angluin. 1990. Negative results for equivalence queries. Mach. Learn., 5:121–150. Frédérique Bassino and Cyril Nicaud. 2007. Enumeration and random generation of accessible automata. Theor. Comput. Sci., 381(1-3):86–104. Lekai Chen, Ashutosh Trivedi, and Alvaro Velasquez. 2024. Llms as probabilistic minimally adequate teachers for DFA learning. CoRR, abs/2408.02999. Walter Daelemans. 2010. Colin de la higuera: Grammatical inference: learning automata and grammars - cambridge university press, 2010, iv + 417 pages. Mach. Transl., 24(3-4):291–293. DeepSeek-AI. 2026. Deepseek-v4-pro. https:// huggingface.co/deepseek-ai. Google. 2026. Gemini models. https://ai.google. dev/gemini-api/docs/models. Malte Isberner. 2015. Foundations of active automata learning: an algorithmic perspective. Ph.D. thesis, Technical University Dortmund, Germany. Malte Isberner, Falk Howar, and Bernhard Steffen. 2014. The TTT algorithm: A redundancy-free approach to active automata learning. In Runtime Verification - 5th International Conference, RV 2014, Toronto, ON, Canada, September 22-25, 2014. Proceedings, Lecture Notes in Computer Science, pages 307–322. Springer. Mu-Tien Kuo, Chih-Chung Hsueh, and Richard Tzong- Han Tsai. 2023. Large language models on the chessboard: A study on chatgpt’s formal language comprehension and complex reasoning skills. CoRR, abs/2308.15118. Kevin J. Lang, Barak A. Pearlmutter, and Rodney A. Price. 1998. Results of the abbadingo one DFA learning competition and a new evidence-driven state merging algorithm. In Grammatical Inference, 4th International Colloquium, ICGI-98, Ames, Iowa, USA, July 12-14, 1998, Proceedings, Lecture Notes in Computer Science, pages 1–12. Springer. Meta. 2024. Llama-3.3-70b-instruct. https:// huggingface.co/meta-llama. Kevin P. Murphy. 1996. Passively learning finite automata. Technical Report UCB/CSD-96-917, University of California, Berkeley. Jose Oncina and Pedro Garcia. 1992. Inferring regular languages in polynomial update time. In Pattern Recognition and Image Analysis, pages 49–61. OpenAI. 2026. Gpt-5.4. https://openai.com. Dongmin Park, Minkyu Kim, Beongjun Choi, Junhyuck Kim, Keon Lee, Jonghyun Lee, Inkyu Park, Byeong-Uk Lee, Jaeyoung Hwang, Jaewoo Ahn, Ameya Sunil Mahabaleshwarkar, Bilal Kartal, Pritam Biswas, Yoshi Suhara, Kangwook Lee, and Jaewoong Cho. 2025. Orak: A foundational benchmark for training and evaluating LLM agents on diverse video games. CoRR, abs/2506.03610. Yotam Perlitz, Elron Bandel, Ariel Gera, Ofir Arviv, Liat Ein-Dor, Eyal Shnarch, Noam Slonim, Michal Shmueli-Scheuer, and Leshem Choshen. 2024. Efficient benchmarking (of language models). In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), NAACL 2024, Mexico City, Mexico, June 16-21, 2024, pages 2519–2536. Association for Computational Linguistics. Ronald L. Rivest and Robert E. Schapire. 1993. Inference of finite automata using homing sequences. Inf. Comput., 103(2):299–347.
Keyon Vafa, Justin Y. Chen, Ashesh Rambachan, Jon M. Kleinberg, and Sendhil Mullainathan. 2024. Evaluating the world model implicit in a generative model. In Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024. Marcell Vazquez-Chanlatte, Karim Elmaaroufi, Stefan J. Witwicki, Matei Zaharia, and Sanjit A. Seshia. 2025. L*lm: Learning automata from demonstrations, examples, and natural language. In International Conference on Neuro-symbolic Systems, 28-30 May 2025, University of Pennsylvania, Philadelphia, Pennsylvania, USA, Proceedings of Machine Learning Research, pages 543–569. PMLR. Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018. Extracting automata from recurrent neural networks using queries and counterexamples. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, Proceedings of Machine Learning Research, pages 5244–5253. PMLR. John Yang, Kilian Lieret, Jeffrey Ma, Parth Thakkar, Dmitrii Pedchenko, Sten Sootla, Emily McMilin, Pengcheng Yin, Rui Hou, Gabriel Synnaeve, Diyi Yang, and Ofir Press. 2026. Programbench: Can language models rebuild programs from scratch? CoRR, abs/2605.03546. Junhao Zheng, Xidi Cai, Qiuke Li, Duzhen Zhang, Zhong-Zhi Li, Yingying Zhang, Le Song, and Qianli Ma. 2025. Lifelongagentbench: Evaluating LLM agents as lifelong learners. CoRR, abs/2505.11942.
A Initial Prompt Template
We provide the full prompt template used in our experiments. This prompt is given to the model at the beginning of each task instance and defines the interaction protocol under which the model operates. Prompt Summary. The model is instructed to reconstruct an unknown deterministic finite automaton (DFA). A fixed target DFA exists, but its structure is not directly accessible. The model must learn about it through interaction with available interactive tools and its own internal reasoning. Game Rules. The model is given a budget of tool calls. At each step, it must issue exactly one tool call. On the final step, it must invoke the evaluation tool. Scoring Policy. The model is encouraged to minimize the number of tool calls while correctly reconstructing the automaton. Tool usage should be efficient and aimed at obtaining informative results. If the model believes it has identified the correct DFA, it should invoke the evaluation tool immediately, even if calls remain. Strict Output Policy. The model must output exactly one TOOL_ACTION block at each step. The output must be a JSON object of the form:
{ "tool_name": "
B Example Interaction Format
We provide an example interaction illustrating the protocol under which the model operates during a task instance: Initial Prompt: The interaction begins with the task prompt described in Appendix A Assistant:
C Best Hypothesis Similarity Metric
To complement the binary success metric, we define a continuous similarity measure that captures how close the best hypothesis proposed during interaction is to the hidden DFA. For each task instance, we compute the similarity between every intermediate hypothesis proposed by the model and the hidden DFA, and report the highest similarity value achieved throughout the interaction, referred to as Best Hypothesis Similarity. This extends the binary success metric by providing a finer-grained measure of progress toward the hidden DFA. Formally, for a hypothesis DFA h and a hidden DFA x, we compute a symmetric-differencebased similarity approximation over all words up to length k = 200: Sim△,200(h, x) = 1 − |L(h)≤200△L(x)≤200| |Σ≤200| Here, L(h)≤200 and L(x)≤200 denote the sets of words of length at most 200 accepted by the hypothesis and hidden DFAs, respectively, △ denotes the symmetric difference between the two languages, and Σ≤200 denotes the set of all words over the alphabet whose length is at most 200. This formulation measures the fraction of words on which the two DFAs agree, producing a similarity score in [0, 1], where higher values indicate greater behavioral agreement between the hypoth- Gemini 3.1 Pro Deepseek-v4-Pro Gemini-3-Flash (thinking) GPT-5.4 (without thinking) Gemini-3.1-Flash-Lite Llama-3.3-70B-Instruct-Turbo 2–3 4–5 6–7 8–9 random language proposals Number of States in the Minimal DFA Best Hypothesis Similarity (%) Figure 7: Best Hypothesis Similarity as the number of states in the minimal DFA increases. The shaded regions represent one standard deviation, and the dashed gray line represents a random hypothesis baseline. esis and hidden languages. We use symmetricdifference similarity rather than Jaccard similarity because it is better aligned with the structure of our sampled DFA distribution. Since our DFA generation process produces languages in which, in expectation, a word has approximately equal probability of being accepted or rejected, the resulting language space is relatively balanced. In this setting, normalizing by the full input space |Σ≤200| provides a stable and directly interpretable measure of behavioral agreement across the entire observable space. In contrast, Jaccard similarity normalizes by the union of accepted words, making it more sensitive to variation in language density and less suitable for our objective of measuring agreement over the full input space. Although the number of words of length at most 200 is exponential, approximately 2200 for a binary alphabet, this metric can be computed efficiently using dynamic programming over the product DFA of the two DFAs. This enables counting the number of words in the symmetric difference without explicitly enumerating all possible strings. Beyond aggregate evaluation, this metric enables tracking intermediate hypothesis similarity throughout interaction, as shown in Figure 8. This reveals whether a model gradually approaches the target DFA or instead oscillates between hypotheses without consistent and meaningful improvement over time. 0 20 40 60 80 0.5 Step / call number Similarity LLM L⋆ TTT Figure 8: Example interaction trajectory for Gemini
3.1 Pro on a single task instance. The graph tracks
the symmetric-difference similarity between the hidden DFA language and the hypotheses proposed throughout interaction.
D How Counterexamples Are Sampled
In each equivalence query between two DFAs, we construct the symmetric difference automaton, which accepts exactly the words on which the two automata disagree. A counterexample is a word accepted by this automaton. We first compute the minimal length kmin of a word accepted by the symmetric difference automaton. Instead of selecting a single word of this minimal length, we define a set of candidate words consisting of short words whose lengths lie in the range kmin to kmin + 3. The selection from this candidate set is performed in a pseudo-random yet deterministic manner. Specifically, for each given pair of automata (the target DFA and the hypothesis), we compute a fixed seed using a stable hash function over their representations. This seed is then used to select a single word from the candidate set. This approach ensures stability by maintaining identical conditions across runs, while at the same time avoiding providing the model with additional information that could simplify the problem.
E Effect of Query Budget on Success Rate
As shown in Figure 9, increasing the query budget generally improves the success rate, but the effect is highly model-dependent. While some models, such as Gemini 3.1 Pro, show only modest additional gains as the budget increases, others benefit Gemini 3.1 Pro Deepseek-v4-Pro Gemini-3-Flash (thinking) GPT-5.4 (without thinking) Gemini-3.1-Flash-Lite Llama-3.3-70B-Instruct-Turbo 1 1.25 1.5 1.75 2 Query Budget Factor Success Rate (%) Figure 9: Success rate as a function of the query budget factor. For each task instance, the allowed query budget is computed as the factor multiplied by the smaller number of queries required by L⋆ and TTT. A model is counted as successful only if it reaches the correct DFA within this factor multiplied budget. substantially; for example, Deepseek-v4-Pro improves from 0% to 55% success.
F Context Window Analysis
Figure 10: Context window size throughout interaction. Each line represents a task instance, while colors correspond to different models. The figure shows how context size evolves across tool-call steps during task execution.