Can Agents Infer Environment from Interaction?

The setup

Try it yourself! Can you discover a hidden DFA through two kinds of questions?

Diagram of agentic automata learning: an agent issues membership and equivalence queries to an environment holding a hidden DFA.

Figure 1 Agentic automata learning. An agent identifies a hidden DFA through repeated interaction. Membership queries ask whether a word is accepted (left). Equivalence queries submit a candidate DFA and ask whether it matches the target; the environment confirms equivalence or returns a counterexample where the two disagree (right).

Interactive challenge The hidden language is over {a,b}. Ask membership queries, then submit a regular expression as an equivalence query.

Ask membership queries

Type a word over a and b. The empty word is written as ε.

Ask a membership query to start collecting examples.

#	word	answer
No membership queries yet.

Submit a regular expression

Use a, b, parentheses, union |, Kleene star *, and plus +. Your regex is converted to a DFA, minimized, and compared with the hidden DFA.

Submit a hypothesis when you think you know the language.

→ Hidden regex: a(a|b)*b

Proposed hypotheses

No counterexamples yet.

Abstract

Active learning, as an agent task

We propose agentic automata learning to evaluate the extent to which tool-calling LLM agents can uncover hidden environments through interaction, a capability increasingly required in agentic tasks. 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?”. Agentic automata learning yields a scalable testbed with controlled task complexity, measurable interaction efficiency, and strong algorithms to compare against from the classic automata-learning literature.

Evaluating state-of-the-art LLMs with a multi-turn agent scaffold, we find that while they are able to recover simple DFAs, their performance drops sharply as DFA size increases. Results improve with a more elaborate ReAct-style state-tracking scaffold, yet strong models still struggle with complex instances. Trajectory analyses reveal recurring failures in query planning, evidence integration, and hypothesis construction. These failures occur even though the models mention classic automata-learning algorithms in their reasoning, and can implement and execute them when given access to a coding environment. Our results suggest that for state-of-the-art LLMs, identifying a solution to the problem is insufficient, and reliably executing the resulting plan still poses a distinct challenge.

Findings

Agentic automata learning remains challenging for frontier models, while explicit state tracking substantially improves performance and interaction efficiency.

Success rate and query efficiency by minimal DFA size, comparing stateful and stateless scaffolds across three frontier models.

Figure 3. Model performance and query efficiency as the number of states in the minimal DFA increases. Left: success rate for DFA-state buckets 2–3, 4–5, 6–7, and 8–9, with n = 40 runs for each bucket. Right: mean Δ Tool Calls relative to deterministic algorithms (L^*, TTT). Positive values indicate more tool calls than the more query-efficient of the classic strategies.

Under both stateless and stateful scaffolds, performance generally declines as the number of states in the minimal DFA increases. For automata with 8 or 9 states, the highest success rate is 57.5% under the stateful scaffold and 30.0% under the stateless scaffold. The gap relative to classic algorithms is also reflected in interaction efficiency: in the same 8–9-state range, when considering only successful runs, even the most efficient model-scaffold combination, Gemini 3.1 Pro with a stateful scaffold, uses approximately 23.5% more tool calls than TTT.

Stateful scaffolding generally improves performance

The stronger models, DeepSeek-v4-Pro and Gemini 3.1 Pro, benefit substantially from the stateful scaffold in both success rate and interaction efficiency. One possible explanation is that the agent does not need to repeatedly re-integrate all accumulated information at every step. In contrast, the smaller Gemini 3.8 Flash model is harmed by the addition of state, possibly because the more complex structured-output format makes it harder to satisfy the scaffold requirements consistently. This interpretation is supported by an increase in its invalid tool-call rate from 0.2% to 8.7% when state tracking is added.

Error analysis showing non-informative query rates over interaction steps and success, reasoning failure, and planning failure rates for stateful and stateless scaffolds.

Figure 4. Error analysis at two levels: query level on the left and task-instance level on the right. The left panel shows the percentage of queries at each interaction step that are non-informative across all task instances, for each model and scaffold. Curves are smoothed using a 1D Gaussian filter (σ = 2) for visualization. Values are reported up to step 100 because only a small number of task instances continue beyond this point. The right panel shows the percentage of task instances classified as successful runs, reasoning failures, or planning failures.

Models fail both in planning and in reasoning from available evidence

We classify model failures into two mutually exclusive categories. A planning failure occurs 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, the model did not collect sufficient information during interaction. A reasoning failure occurs when the model fails, but at least one passive learning algorithm can infer the hidden DFA from the accumulated observations: the necessary information was available, but the model failed to infer the correct DFA from it. All evaluated models suffer from both failure types, while failure rates are generally lower under the stateful scaffold.

Non-informative queries increase as interactions progress

We measure how consistently LLMs use accumulated information through non-informative queries: tool calls whose answers can already be implied by previous oracle responses and therefore cannot provide new evidence. For membership queries, this includes repeating a previously queried word. For equivalence queries, it includes duplicating a previous hypothesis or proposing a DFA already contradicted by known evidence. The rate of non-informative queries increases as interactions grow longer, suggesting that models increasingly struggle to organize and use accumulated evidence consistently. Explicit state tracking reduces, but does not eliminate, this behavior.

Average evaluation cost and success rate as the query budget increases from 100 to 200 percent of the classic learner baseline.

Figure 5. Effect of the query budget on evaluation cost and success rate. The budget ranges from 100% to 200% of the number of queries required by the more efficient classic learner between L^* and TTT on the corresponding task instance.

More query budget helps, but models saturate at different points

Evaluation cost increases with the query budget, while success rates saturate at different budgets across models. Additional budget is critical for solving DFAs that models cannot recover under smaller budgets. DeepSeek-v4-Pro improves from 3.1% at 100% of the baseline budget to 55.6% at 200%, with each increase yielding a substantial improvement in success rate. In contrast, Gemini 3.1 Pro Preview reaches 54.4% success already at 125% of the baseline budget, after which the gains taper, reaching 70.6% at 200%. Across the full experimental suite, the total monetary cost was approximately $3,000.

LLM agents identify L^* as the appropriate solution, but struggle to execute it reliably

In a complementary evaluation, we give the models access to coding tools through the OpenHands harness without Internet access and test whether they can identify prior work on automata learning and reproduce a classic algorithm for the task. All examined models identify and write the code for the classic L^* algorithm. Thus, the performance gap does not stem from a lack of knowledge of the classic algorithms or from failing to recognize them as an appropriate solution. However, this knowledge does not translate into reliable execution during interaction. We find no task instance in which a model exactly reproduces the same deterministic query sequence as a classic algorithm. Every model-scaffold combination also violates at least one of two classical properties — the bound on equivalence queries and monotonic growth in hypothesis size — in a substantial fraction of runs. Even the combination closest to classic behavior, DeepSeek-v4-Pro with a stateful scaffold, satisfies both properties in only 31% of runs.

Step	Gemini 3.1 Pro		DeepSeek-v4-Pro		L^*		TTT
Step	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(aa)	0	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	-	-	MQ(bb)	1	-	-	MQ(aa)	0
8	-	-	MQ(aba)	1	-	-	MQ(baa)	1
9	-	-	MQ(aaa)	0	-	-	EQ(b ∈ w)	⊤
10	-	-	EQ(b ∈ w)	⊤	-	-	-	-

Table 1. Example interactions with an 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 DeepSeek-v4-Pro, L^*, and TTT use both membership and equivalence queries. In EQ notation, ∅ denotes the empty language, Σ* denotes all words, and b ∈ w denotes the language of words containing b.

Can Agents Infer Environment from Interaction?

Try it yourself! Can you discover a hidden DFA through two kinds of questions?

Ask membership queries

Submit a regular expression

Four things this paper adds

A controlled framework

Discovery that degrades with complexity

State tracking helps

Knowing a solution is not enough

Active learning, as an agent task

Agentic automata learning remains challenging for frontier models, while explicit state tracking substantially improves performance and interaction efficiency.

Stateful scaffolding generally improves performance

Models fail both in planning and in reasoning from available evidence

Non-informative queries increase as interactions progress

More query budget helps, but models saturate at different points

LLM agents identify L^* as the appropriate solution, but struggle to execute it reliably

Probe a hidden DFA yourself

Cite this work

Try it yourself! Can you discover a hidden DFA through two kinds of questions?

Ask membership queries

Submit a regular expression

Four things this paper adds

A controlled framework

Discovery that degrades with complexity

State tracking helps

Knowing a solution is not enough

Active learning, as an agent task

Agentic automata learning remains challenging for frontier models, while explicit state tracking substantially improves performance and interaction efficiency.

Stateful scaffolding generally improves performance

Models fail both in planning and in reasoning from available evidence

Non-informative queries increase as interactions progress

More query budget helps, but models saturate at different points

LLM agents identify L* as the appropriate solution, but struggle to execute it reliably

Probe a hidden DFA yourself

Cite this work

LLM agents identify L^* as the appropriate solution, but struggle to execute it reliably