acceptodds
Under review as a conference paper at ICLR 2027

Can Agents Infer Environment from Interaction? Evidence from 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, a capability increasingly required in agentic tasks (e.g., reproducing an executable without access to its source code by interacting with it). 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.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Large Language Models, LLM Agents, Active Automata Learning, Interactive Learning, Agent Evaluation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Xh88OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors assess if tool-calling LLM agent being told to learn/discover a hidden deterministic finite automaton (DFA) over the alphabet {a, b} . The agent can ask two kinds of questions: a membership query (MQ: is this word accepted?) and an equivalence query (EQ: here is my hypothesis DFA, is it equivalent to the hidden one, and if not give me a word on which they differ?). The agent is successful if if an EQ returns “equivalent” under a constrained budget. This is the setting for which classical learners exist and have been propose and for which efficiency proofs exist. In this way, the authors can compare an LLM against well-understood algorithms on the same instances. The authors ask whether frontier reasoning models can infer a hidden structure from interaction, how this depends on the structure’s size, and whether an explicit state-tracking scaffold helps.

Critical strengths

The paper proposes a novel idea, which is interesting albeit not groundbreaking. The authors propose a DFA learning as an agentic testbed and assess the LLM as a learner. The contribution of budgets derived from L* and TTT is also original. The contribution consists also in the combination of exact structural recovery, guaranteed solvability and an algorithmic yardstick. The paper is well written and contains well defined benchmarks, The formal task is well introduced and the authors relate to classical references , an explicit context-limit check. Additionally, they provide full prompts and comprehensive cost report.

Critical weaknesses

I could not understand why the chosen model is so simple. The paper investigates only single fixed (binary) alphabet and such the natural question arises if larger sized alphabets would also be suitable for the approach. The authors use uniformly sampled random DFAs over {a, b}. These DFAs have no real world equivalent and as such do not represent meaningful use cases. The reviewer can't imagine a real world application which can benefit from the proposed solution. The authors analyze only deterministic environments. Nondeterministic and/or probabilistic environments are mentioned as future work, but are more realistic.

Questions for authors

What is the maximum sized alphabet for which the proposed method works. Why have larger alphabets have not beed used ? Can the authors present a real world scenario for which the proposed solution works ? What happens if structured (non-random) DFAs and noisy or non-minimal counterexample policies are tested ? Who are the "target users" of the proposed approach ? Basically, which research community needs to leverage the solution ? Can the authors provide more information about OpenHands ? Most readers might not have heard about it.

4 comments

We would like to thank the reviewer for their feedback. We are happy that the reviewer finds our idea novel and interesting, and appreciate them pointing out the contribution of our setup in terms of its structure, solvability, and algorithmic grounding.

Regarding the concern that our binary alphabet setup is simple, we agree with the reviewer that the alphabet size is an interesting difficulty knob that remained under explored in our current experiments, and following the reviewer’s comment we conducted a small-scale experiment with larger alphabet sizes, fixing the number of states (see Q1 below). We find that larger alphabets make the task harder for the agent: success drops from 100% on 4-state DFAs over 2 letters to 50% on 4-state DFAs over 8 letters. These results establish alphabet size as another meaningful difficulty knob, alongside the number of states, which is the focus of our work. The number of states corresponds to the number of “rules” of the induced language that the learner has to extract. As shown in the paper, the agent’s success rate drops as the number of states grows, which shows that the agent struggles to recover the environment even with a binary alphabet. In the revised manuscript, we will discuss the different difficulty knobs that affect this task and include the results of this small-scale experiment to support this.

Regarding the concerns about the applicability of our proposed solution/approach, we would like to clarify that the main contribution of our work is an evaluation framework. By leveraging the problem's established theoretical foundations and the existence of classic learning algorithms, our evaluation framework can be used to systematically evaluate agent behavior and identify current limitations in their reasoning and learning process. Moreover, we argue that our results do have practical importance, as if models fail in such scenarios, then this is an indication that they will fail in more complex, real-world ones, where for example noise is introduced and the vocabulary is large. We will add this point to the paper.

Below we answer specific questions raised by the reviewer.

Q1: What is the maximum sized alphabet for which the proposed method works.

Our sampling method allows us to generate DFAs with any finite number of states and any finite alphabet size, and to test any generated DFA in the active learning evaluation framework we propose in this work. To demonstrate this flexibility, we conducted a small-scale experiment with increasing alphabet sizes, fixing the number of DFA states to 4, and evaluated Gemini 3.1 Pro with our stateful scaffold on 32 task instances (8 per alphabet size). The results, presented in the table below, suggest that larger alphabets make the task harder. However, given the small sample size and the wide confidence intervals, more instances are needed to establish the precise trend and its statistical significance. More broadly, alphabet size is one of several difficulty factors, alongside DFA structure, sampling distribution, and counterexample policy. Our framework supports varying each of them, opening the door for future work to explore their effect on agent performance. We will include this experiment as an additional analysis in the revised manuscript, along with a discussion of other difficulty factors, and clarify that our framework allows generating DFAs with different alphabet sizes.

Success rate of Gemini 3.1 Pro on 4-state DFAs with varying alphabet sizes (bootstrapped 95% CIs):

Model|Σ| = 2|Σ| = 4|Σ| = 6|Σ| = 8
Gemini 3.1 Pro Preview (High)100%, CI [100, 100]75%, CI [37.5, 100]37.5%, CI [12.5, 75]50%, CI [12.5, 87.5]

Q2: Can the authors present a real world scenario for which the proposed solution works ?

As mentioned above, our main contribution is an evaluation framework, which is theoretically established and allows systematic analysis of agent behaviour. This hidden environment recovery task is motivated from real-world scenarios in which the agent needs to act in an unknown environment, where it can only interact with it via tools (e.g., API calls or function calling for coding agents), but is not aware of its underlying rules (e.g., it cannot access the source code). We will clarify this in the revised manuscript.

We address the remaining reviewer questions (Q3–Q5) in a follow-up response.

Q3: What happens if structured (non-random) DFAs and noisy or non-minimal counterexample policies are tested ?

The counterexamples that the oracle returns are not minimal – if the minimal counterexample is of size n, the oracle returns a counterexample of length between n to n+3 (Section 4, “Oracle counterexample selection strategy.”). However, a preliminary experiment we ran with Gemini 3.1 Pro over half of the dataset, had used minimal counterexample oracle strategy. In that setup we saw that the agent identifies that the returned counterexample is minimal and leverages this as some kind of a “shortcut”, which makes the agent converge to a correct solution quicker than in experiments described in the paper with non-minimal counterexamples, as shown in the table below. We will clarify our counterexample selection strategy in our revised manuscript, and add a discussion about how the agent leverages the signal in a setup where counterexamples are minimal.

Query efficiency results table – Δ queries from classic algorithms, lower is better, calculated over 20 DFAs in each row

Number of statesΔ for Minimal counterexampleΔ for Non-minimal counterexample
2–3-0.751.00
4–5-0.265.06
6–72.054.92
8–915.2725.40

Q4: Who are the “target users” of the proposed approach ? Basically, which research community needs to leverage the solution ?

Our proposed evaluation framework is relevant to users who deploy agents to work in unknown or new environments, in which the tools given to the model can interact with the environment but never be exposed to the rules that are forming it. Our evaluation framework can shed light on the current limitation of agents’ planning, reasoning, and their ability to follow a plan over a long trajectory, as well as testing the effect of different harnesses on the performance. Due to the robustness of our DFA sampling method, as models will improve we can always refresh the data to remain unsaturated, by arbitrarily enlarging the number of states in the DFA, or as the reviewer suggested, extending the alphabet size, to increase the task difficulty. We will clarify this in the revised manuscript.

Q5: Can the authors provide more information about OpenHands?

OpenHands [1] is an open-source platform for AI software development agents that provides tools for writing, editing, and executing code. Each agent runs in a Docker-sandboxed environment that includes a bash shell, an interactive Python (IPython) server, file-editing tools, and a web browser (which we disabled in our experiments, as the agent had no Internet access). This is a popular approach used in many recent papers, for example to train software engineering agents on SWE-Gym [2] and to evaluate agents on real-world workplace tasks in TheAgentCompany [3]. We will include a detailed explanation of the OpenHands platform in the revised manuscript.

References

[1] X. Wang, B. Li, Y. Song, F. F. Xu, X. Tang, M. Zhuge, J. Pan, Y. Song, B. Li, J. Singh, H. H. Tran, F. Li, R. Ma, M. Zheng, B. Qian, Y. Shao, N. Muennighoff, Y. Zhang, B. Hui, J. Lin, R. Brennan, H. Peng, H. Ji, and G. Neubig, “OpenHands: An open platform for AI software developers as generalist agents,” in Proc. 13th Int. Conf. Learning Representations (ICLR), 2025.

[2] J. Pan, X. Wang, G. Neubig, N. Jaitly, H. Ji, A. Suhr, and Y. Zhang, “Training software engineering agents and verifiers with SWE-Gym,” in Proc. 42nd Int. Conf. Machine Learning (ICML), PMLR vol. 267, 2025, pp. 47717–47737.

[3] F. F. Xu, Y. Song, B. Li, Y. Tang, K. Jain, M. Bao, Z. Z. Wang, X. Zhou, Z. Guo, M. Cao, M. Yang, H. Y. Lu, A. Martin, Z. Su, L. Maben, R. Mehta, W. Chi, L. Jang, Y. Xie, S. Zhou, and G. Neubig, “TheAgentCompany: Benchmarking LLM agents on consequential real world tasks,” arXiv:2412.14161, 2024.

We would greatly appreciate it if you could take a moment to let us know whether our response has adequately addressed your concerns. If any questions or concerns remain, we would be happy to continue the conversation.

Thank you for your time and consideration!

As the rebuttal period is about to end, we would appreciate hearing your thoughts on our rebuttal.

We took your feedback about the simplicity of our environments into account and clarified that we focus on simple settings because they enable controlled evaluation while agents still struggle with them today, implying that they will fail on more complex real-world environments.

As agents improve, the same framework can support more complex, realistic environments by changing how the hidden structure is sampled or how the oracle behaves.

We hope this addresses your concerns and would welcome your updated assessment. Thank you very much for your time and effort!

Reviewer_K8gmOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper casts Angluin's active automata learning setting as a tool-calling task: an LLM agent must identify a hidden binary-alphabet DFA using membership and equivalence queries, under a budget set at twice the queries of the better of L* and TTT. Instances are generated procedurally, with the number of minimal states as the difficulty knob. The authors evaluate three reasoning models, each under a stateless scaffold and a stateful scaffold that adds goal, working-memory, and thought fields. Success drops as the DFA grows, while the stateful scaffold generally helps. The authors split failures into planning and reasoning failures by checking whether passive learners RPNI, EDSM, and Blue-Fringe recover the target from the agent's collected data, and the rate of non-informative queries is tracked over the interaction. The authors conclude that models know L* but cannot execute it reliably, based on a coding-tool experiment and on how closely query trajectories conform to L*.

Critical strengths
  • The testbed is well posed and provably solvable within budget, with procedural instances and the number of minimal states as a simple difficulty knob that does not saturate for current models. This is the main reason the paper is worth reading: the testbed makes the degradation of agentic automata learning with problem size easy to measure, and the generator can be reused as models improve.
  • L* and TTT serve as an efficiency reference with provable query bounds rather than an arbitrary baseline, and the budget sweep shows how much of the success depends on the budget multiplier.
Critical weaknesses
  • The reported conformance statistics don't test the "knowing how to solve a task is not sufficient" conclusion. No correct strategy other than L* can match the L* query sequence exactly. The two conformance properties, an EQ count bounded by the number of states and a monotone hypothesis size, are violated by sound alternatives like the EQ-first strategy in Table 1. So the tests count deviation from L*, not the failure of a plan the model adopted; nothing shows the scored runs were attempts at L*.
  • The "knowing" half rests on a short paragraph reporting that all examined models write L* in the OpenHands harness, with no correctness check of that code or success rate. As this is the main analytical claim, I don't think the paper's contribution beyond a difficulty curve is supported so far.
  • The split into planning and reasoning failures measures what three heuristic passive learners can recover. RPNI requires a structurally complete sample. EDSM and Blue-Fringe are merge heuristics, so a learner may fail on data that does identify the target, and that counts as a planning failure. A learner may reach the target from data that doesn't identify it, through its merge bias, and that counts as a reasoning failure.
  • The planning and reasoning diagnostics cannot attribute the lower stateful failure rates to state tracking, since the stateless and stateful scaffolds differ both in output format and in carried state.
Questions for authors
  1. What is the end-to-end success rate per size bucket, and the query count, when the model-written L* from the coding experiment runs against the oracle?
  2. In how many scored runs does the model say it follows L*? How often do those runs satisfy the two conformance properties?
  3. How does the knowing-versus-executing finding compare with Sinha et al. ("The Illusion of Diminishing Returns: Measuring Long Horizon Execution in LLMs") and with the knowing-doing gap in Schmied et al. ("LLMs are Greedy Agents"), which report a similar separation in controlled settings?
  4. A stateless arm that permits free-form reasoning text would show how much of the stateful gain comes from carried state and how much from a visible reasoning channel. Do results change when the prompt omits the query budget?
  5. A SAT check of whether the target is the only minimal DFA within n states consistent with the collected data would tell whether the planning and reasoning proportions hold.
Reviewer_EBLEOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposed agentic automata learning, a controlled framework for evaluating whether LLM agents can infer hidden environmental structure through interaction. The task requires agents to reconstruct an unknown DFA by issuing membership and equivalence queries to an oracle. By leveraging classical automata-learning theory, the framework provides measurable task complexity, interaction efficiency, and classic active learning algorithms such as L* and TTT. The authors evaluate advanced LLMs under stateless and stateful agent scaffolds. The results show that while LLM agents can reliably recover simple DFAs, their success rates decline substantially as the number of states increases. Explicit state tracking generally improves performance, but significant gaps remain compared with classical learning algorithms. Through detailed trajectory analyses, the authors identify recurring failures in query planning, evidence integration, and hypothesis construction.

Critical strengths
  1. This benchmark is important to the community. The paper adapts classical active automata learning into an interactive evaluation framework for LLM agents. Unlike many agent benchmarks, it provides precise definitions of task complexity, success, and interaction efficiency. Procedural DFA generation also makes the framework scalable and reduces dependence on manually constructed tasks.
  2. The empirical result looks convincing. The experiments evaluate three models under both stateless and stateful scaffolds across 160 DFA instances. The results demonstrate a clear degradation in performance as DFA complexity increases. For 8–9-state DFAs, the highest success rate is only 30.0% with stateless scaffolding and 57.5% with stateful scaffolding. The authors also report bootstrap confidence intervals, strengthening the empirical presentation.
Critical weaknesses
  1. The benchmark focuses exclusively on binary-alphabet DFAs with ideal membership and equivalence oracles, which limits the generalizability of its findings. The authors should therefore better position the scope of their contribution. The term "agentic automata learning" is too broad and ambitious given the relatively restricted setting considered in this work.
Questions for authors
  1. Some efficiency analyses are conditioned on successful runs. Can authors provides more details about this choice?
  2. The authors classify a failure as a planning failure when none of the three passive learning algorithms can recover the target DFA from the collected observations. However, does the failure of these algorithms necessarily imply that the collected information is insufficient? Conversely, does successful reconstruction by a passive learner guarantee that the target DFA is uniquely identifiable from the observations? Could the authors clarify the justification for this classification and discuss its limitations?
2 comments

We thank the reviewer for their positive feedback. We highly appreciate their recognition of the importance of our dataset to the community, mentioning the precise definitions and the scalability of the framework. We are also happy that the reviewer finds our reported results convincing.

Regarding the concern about the limited setup of binary-alphabet DFAs with ideal membership and equivalence oracles, we agree that “Agentic Automata Learning” includes more setups than the ones we ran in this work. We will clarify the scope of our findings in the revised manuscript. In addition, following this comment and also reviewer Xh88’s comment about the binary alphabet, we conducted a small-scale experiment with increasing alphabet sizes, fixing the number of DFA states to 4, and evaluated Gemini 3.1 Pro with our stateful scaffold on 32 task instances (8 per alphabet size). The results, presented in the table below, suggest that larger alphabets make the task harder, though more samples are needed to establish statistical significance. More broadly, alphabet size is one of several difficulty factors, alongside DFA structure, sampling distribution, and oracle behavior. Our framework supports varying each of them, opening the door for future work to explore their effect on agent performance.

Model|Σ| = 2|Σ| = 4|Σ| = 6|Σ| = 8
Gemini 3.1 Pro Preview (High)100%, CI [100, 100]75%, CI [37.5, 100]37.5%, CI [12.5, 75]50%, CI [12.5, 87.5]

Answers to specific questions:

Q1: Some efficiency analyses are conditioned on successful runs. Can authors provide more details about this choice?

We calculate the query count over successful runs to allow fair efficiency comparison with classic algorithms, which are guaranteed to succeed. Failed runs are runs in which the agent exhausts the query budget and so we terminate the run and mark it as failed. If we include those runs in the query counts it will be impossible to isolate between what indicates a failure and what indicates inefficiency in a correct solution, which will result in a biased comparison to the classic algorithm’s efficiency. We will clarify this in the revised manuscript.

Q2: Classic algorithms’ sufficiency

Following reviewer’s K8gm suggestion, we analyzed failure types using a SAT-based method, which determines whether the collected observations uniquely identify the target DFA among automata with at most n states. We ran SAT over all of our instances and reproduced the error types analysis over the entire dataset. This increases the average planning failure rate from 11.7% to 15.8%, while our main findings remain unchanged, particularly the consistent reduction in planning failures achieved by the stateful scaffold. Additionally, the SAT check allows us to distinguish between Complete Planning Success, where the collected observations uniquely identify the target DFA, and Partial Planning Success, where the agent succeeds despite insufficient evidence for unique identification. We will update Figure 4b and all of its related text in the revised manuscript.

Thank you for the detailed response and clarifications. I have reviewed the rebuttal. While I appreciate the authors' efforts to address my concerns, I believe my original assessment remains appropriate. Therefore, I will maintain my original score.

Comments on the paper

1 comment

We thank all reviewers for their constructive feedback. We have revised the manuscript to address the concerns raised, with all new additions highlighted in blue for ease of review.

Summary of the main revisions:

SAT-based failure analysis (Sections 2.2, 5.1): In response to reviewers' concerns about our failure classification, we conducted a new SAT-based identifiability analysis across all benchmark instances, updated Figure 4, and distinguished complete from partial planning success.

Refined knowledge–execution claim (Section 5, Appendix B): To address reviewers' concerns, we conducted new experiments using the OpenHands coding environment, demonstrating substantial performance improvements and analyzing the learning algorithms implemented by the models. Accordingly, we refined our original claim, focusing on the observed gap between models’ ability to implement learning algorithms using coding tools and their ability to execute them reliably in-context.

Additional ablations (Section 6): Added a ReAct scaffold to distinguish the effects of visible reasoning from explicit state tracking. The results suggest that visible reasoning alone does not explain the benefits of the stateful scaffold. We also conducted an ablation removing the explicit query budget from the prompt, finding little effect on success rates.

Alphabet-size experiment (Appendix C): Conducted new experiments with larger alphabets, finding that increasing alphabet size generally makes the task harder.

As the discussion period is approaching its end, we would greatly appreciate knowing whether our responses and revisions have adequately addressed your concerns. If so, we would be very grateful if you could consider updating your score.

If any concerns remain unresolved, please let us know before the discussion closes so we can provide further clarifications or conduct additional analyses if needed.

Thank you again for your time and valuable feedback!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.