Towards Persistent Noise-Tolerant Active Learning of Regular Languages with Class Query
Authors: Lekai Chen
Ashutosh Trivedi
Alvaro Velasquez
Venue: ICLR 2026 Poster (2026)
Keywords: Active Learning
Automata Theory
Large Language Models
Regular languages
Value Alignment
Preference Modeling
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)

Abstract: Large Language Models (LLMs) are increasingly deployed in human–AI collaborative decision-making systems, where they are expected to align precise formal representations with ambiguous natural language. However, their ad hoc strategies for resolving ambiguity often lead to hallucinations and inconsistencies. We formalize this setting via probabilistic Minimally Adequate Teachers (pMATs) that (i) answer membership queries with fixed but possibly flipped labels, and (ii) return valid counterexamples to hypothesis equivalence. We present **CAPAL** (**C**lass-query **A**ctive, **P**ersistent-noise-**A**ware **L**earning), an active algorithm for learning deterministic finite automata (DFAs) that remains correct under persistent membership noise without demonstrations. CAPAL augments the classic \$L^\star\$ loop with two components grounded in our implementation: (1) a *class query* realized as a statistical same-state test that compares disagreements between two prefixes against a noise-floor estimate \$\hat{\eta}\$ with Hoeffding tolerances; (2) a *discrimination tree* that selects a near-minimal discriminator, keeping the core suffix set small. An efficient micro-bootstrap and cache-reuse scheme estimates \$\hat{\eta}\$ with few new queries. We prove convergence given a perfect language-equivalence oracle and show substantial membership-query savings in practice. Our evaluation across multiple benchmarks, including RegexLib and KB13, demonstrates that this approach enhances both the efficiency and robustness of DFA learning under noisy oracles, supporting the view of LLMs as fallible yet useful collaborators for synthesizing verifiable formal artifacts.

Published as a conference paper at ICLR 2026
TOWARDS PERSISTENT NOISE-TOLERANT ACTIVE LEARNING OF REGULAR LANGUAGES WITH CLASS QUERY
Lekai Chen, Ashutosh Trivedi & Alvaro Velasquez Department of Computer Science University of Colorado, Boulder Boulder, CO 80309, USA {lekai, chen, ashutosh. trivedi, t alvaro. / @colorado edd
ABSTRACT
Large Language Models (LLMs) are increasingly deployed in human-Al collabo- rative decision-making systems, where they are expected align precise formal representations (e.g. temporal-logic monitors or reward machines for reinforce- ment learning) with ambiguous natural language. However, their hoc strate- gies for resolving ambiguity often lead to hallucinations and inconsistencies. We formalize this setting via probabilistic Minimally Adequate Teachers (pMATs) that (i) answer membership queries with fixed but possibly flipped labels, and (ii) return valid counterexamples to hypothesis equivalence. We present CAPAL (Class-query Active, Persistent-noise- Aware Learning), active algorithm for learning deterministic finite automata (DFAs) that remains correct under persis- tent membership noise without demonstrations. CAPAL augments the classic L* loop with two components grounded in our implementation: realized statistical same-state test that compares disagreements between two prefixes against noise-floor estimate f with Hoeffding tolerances; (2) discrim- ination tree (DT) that selects near-minimal discriminator, keeping the core suffix set small. An efficient micro-bootstrap and cache-reuse scheme estimates r) with few new queries. We prove convergence given a perfect language-equivalenic or- acle and show substantial membership-query savings in practice. Our evaluation across multiple benchmarks, including RigexLib and KB13, demonstrates that this approach enhances both the efficiency and robustness of DFA learning under noisy oracles, supporting the view of LLMs as fallible yet useful collaborators for synthesizing verifiable formal artifacts.
(1) a class query
INTRODUCTION
Formal languages offer principled framework for modeling human preferences and values in precise, verifiable, and interpretable manner, making them ideal for aligning the behavior of neu- ral networks with high-level human intent. In reinforcement learning, temporal logics such LTL have been used to specify complex tasks (Camacho et al., 2019: Voloshin et al. 2022 Bagatella al. 2025), while automata-based representations like reward machines enable modular, struc- tured reward functions (Toro Icarte et al. 2019 2022) Camacho et al., 2019). Safety-critical sys- tems benefit from shielding techniques, which enforce logical constraints at runtime prevent un- safe actions (Alshickh et al. 2018). In meuro-symbolic systems, logical rules have been incorpo- rated into the training process through logic regularization or differentiable programming, allowing human-aligned constraints such as fairness to shape learned model behavior (Innes & Ramamoorthy, 2020). These developments demonstrate that formal artifacts are not only expressive enough to cap- ture the richness of human values, but also actionable and integrable within neural architectures for Al alignment. In this paper, we study how such formal representations reegula regular languages and their automaton realizations can be learned via interaction with (noisy) large language model (LLM) under probabilistic extension of Angluin's 's Minimally Adequate Teacher (MAT) framework (An- gluin 1987).

---

Published as a conference paper at ICLR 2026
Constructing such formal artifacts by hand is cumbersome and error- error-prone, prone, especially when only informal or scattered specifications exist. Recent work uses LLMs to close this gap by extracting automaton- -aasad task knowledge from natural language and integrating the resulting automata into planning and verification pipelines (Yang et al.) b025c a). As a concrete example, consider an autonomous driving agent deployed in new city whose driving conventions differ from those seen during training: a designer specifies desired behavior in natural language, an LLM judges whether example trajectories satisfy these guidelines, and a driving simulator tests candidate automata and supplies counterexample trajectories. The learned automaton then serves as a reward machine or safety shield for reinforcement learning, with the LLM acting as a noisy membership oracle and the simulator providing equivalence queries by searching for disagreeing PMAT scenario we formalize below.
precissll the
Regular languages occupy well-hehaved corner of the Chomsky hierarchy, with rich closure prop- erties, canonical representations, and efficient algorithms for manipulation and inference, Among their many descriptions, DFAs stand out for interpretability, expressiveness, and learnability; they
have consequently become central to formal alignment (Toro Icarte et al.,
2019
2022
Camacho
et al.
2019 Bejerano
2003 Liu et al.
2023 Merrill 2019).
Active learning of DFAs, epitomized by L and its descendants (Angluin 1987; Kearns & Vazi-
rani
1994; Rivest & Schapire 1989; Denis et al.) 2004 [Bonard al. 2005 Isberner et al. 2014
Volpato & Tretmans| 2015). proceeds by querying an oracle with membership queries (MQs) and
equivalence queries (EQs) to iteratively refine hypothesis until it matches the target language.
However, deploying LLMs as oracles raises robustness concerns. Prior work has explored two main
uses of LLMs in automata inference: (i) employing them as noisy MQ oracles (Vazquez-Chanlale
et al. 2024), often requiring human demonstrations to bootstrap the learner; and (ii) prompting them to synthesize DFA transitions directly from natural language (Alsadat et al. 2024). implicitly
assuming reliable translation from informal specifications to precise transition structures. Neither route provides correctness guarantees, because hallucinated outputs are difficult to detect and correct systematically.
Passive DFA learning methods, such as RPNI and its variants (e.g.. RPNI-EDSM et al. (1988). ).
infer automata from fixed sets of labeled examples using state-merging techniques Oncina & García [1933; Lang et al. (1998.. While these algorithms are PAC-learnable under certain conditions Board & Pitt 1992), their performance is often constrained by limited data and overfitting risks Bugalho & Oliveira )2005); Board& & Pitt (1992). Enhancements like combining passive learning with active strategies Yang et al. (2019) offer improvements but do not address the persistent errors in member- ship queries that challenge real-world applicability.
The broader challenge of learning with oracle errors is well known. Angluin et al. (1977) showed that DFAs remain learnable under finitely many MQ errors when the EQ oracle is perfect, via the LEARNANYWA. algorithm, which replaces suspected mistakes with counterexamples. In practice, however, short counterexamples are rarely available (Isberner et al., 2014). As counterexamples grow in length, the number of LLM-induced mislabels encountered during refinement can scale superlinearly, rendering naïve applications of LEARNANYWAL impractical.
To address these limitations, we introduce the pMAT formalism, in which the oracle may persistently err on MQs but always returns valid counterexamples when EQs fail. Building on this model, we propose CAPAL (Class-query Active, Persistent-noif noiee-ooiieiai Aware Learning). an active DFA learning algorithm that remains correct under persistent membership noise and requires demonstrations. CAPAL leverages two key ideas: (i) even a noisy membership oracle can exploited statistically to decide whether two prefixes belong to the same Myhill-Nerode class (a class query); and (ii) discrimination trees enable efficient hypothesis refinement with near-minimal distinguishing suf- fixes (lsbernrr et al.] 2014). To further strengthen robustness, we augment the framework with an adaptive reasoning pipeline that allows L.LMS to invoke external symbolic solvers or simulators when processing MQs, improving both accuracy and practical applicability.
Our main contributions are:
1. We introduce PMAT, an extension of Angluin's MAT that models noisy LLM membership responses while preserving exact counterexamples from the equivalence oracle.
2

---

Published as a conference paper at ICLR 2026
Figure LLMS Probabilistic MATs.
g
Learner
(abi Counteresample
The target language only accepts number The alphabet is (a.b). aab In the target language?
Membership Query
Equivalence Query
Target Language
LLMs
Yes
Equivelence Oracle
Answer
probabillittcc
a.b
Hypothesis
2. We formalize the notion of persistent errors, showing why mislabels produced by LLMs as PMAT cannot be corrected by re-sampling and must be resolved through counterexamples.
3. We propose CAPAL, the first active DFA learning algorithm that provides theoretical cor- reciness guarantees under persistent MQ noise, requiring neither demonstrations nor aux- iliary supervision.
4. We design a program-basse bason oracle that leverages LLMs to synthesize deterministic check- ers, converting natural-languaee specifications into executable predicates that answer MQs consistently and reliably.
2 PRELIMINARIES
Deterministic Finite Automata. Let Σ be finite set of symbols called the alphabet. A language over Σ is set of words (i.e., finite sequences of symbols from E). A regular language is one that is representable by finite automaton.
alphabet E is a tuple A = (Q, Σ, qo. ó, F') where Q is a finite set of states, go E Q the initial state, : Q x Q the transition function, and F C the set of accepting states.
Definition 2.1 (DFA), A deterministic finite automaton (DFA)
The language of A is defined as L(A) {w 8-(25, w) E FÅJ. We write 8 x Σ- + Q for the standard extension of to words and use for 8* when this is unambiguous. The language recognized by A is (AA { w E E* 5(go, w) F.. For word E' also use the shorthand
{1
A(w] E P,
A A[w] == 8(qu. w) E Q
A(w)
o
otherwise,
so A(w) is exactly the label an ideal membership oracle would return for w.
Learning DFA from MAT' In Angluin's 's minimally adequate teacher (MAT) framework (Angluin al. 1997). a learner interacts with an unknown target DFA M only through two types of queries.
MQs ask, for word w E Σ", whether w belongs to the target language: the teacher returns M(w) E (0. 1) EQs present hypothesis DFA M: the teacher either answers that M is correct or provides a counterexample word w with M(w) + M(w). We assume the learner stores all MQ and EQ interactions in caches CMQ and CEQ, and write Cmq(w) for the (possibly noisy) label stored for w when defined.
The L algorithm is canonical polynomial-time learner in this setting. It maintains an observation table with a finite set S C Σ* of prefixes (including E) and a finite set F. C Σ* of suffixes. For each
Here M(10) 1 iff T(M)).
3

---

Equivalence oracle OEQ (exact). On input a hypothesis DFA M, OEQ outputs OK if Published as a conference paper at ICLR 2026
E U SE and e E E, the learner issues an MQ the concatenation se and records the answer M(s).. The row associated with s is therefore the function E + {0, 1} given by + M(se), which represents the residual language after reading s.
Whenever the table is closed (every row for s E 5D coincides with some row for S) and consistent (rows that agree on E have successors that also agree), I. constructs hypothesis DFA whose states correspond to distinct rows in S. This hypothesis is submitted as an EQ. If the teacher returns counterexample word w, the algorithm adds suitable prefixes of to S suffixes to E, refines the table, and repeats. Under an exact MAT, L* eventually converges to the unique minimal DFA for M using a number of MQs and EQs polynomial the number of states of M.
PROBABILISTIC MATS
3.1 THE PMAT FORMULATION
We generalize Angluin's Minimally Adequate Teacher (MAT) model to a setting which mem- bership answers may be probabilistically wrong while equivalence answers remain exact. Let the (unknown) target DFA be MME + 10. A learner L interacts with two oracles: an (imperfect) membership oracle OaQQ and (perfect) equivalence oracle OEQ-
Definition 3.1 (pMAT), Given a target DFA M over E, a probabilistic MAT (pMAT) is a pair (OMQ, OEq) with the following behavior.
Membership oracle Oæi (stochastic). On imput a context and a membership query q E Σ", the oracle returns
X X~ Po(.aa on {0,
where Pe is a fixed but unknown distribution determined by e. (alphabet, SUL description, environment configuration, etc.). Repeating the same pair (c, q) yields i..d draws from Pol: q) (stationarity under a fixed context).
M = M, else noise-free counterexample with M[w] + M[w].
Running example. Figure I depicts a typical PMAT interaction on the parity-of-a language over Σ = b). The learner queries the stochastic membership oracle, e.g., "Is aab in the target language?" and receives a (possibly noisy) MQ answer (Yes in the illustration). When the current hypothesis is submitted to Ogq- the perfect equivalence oracle may return counterexample such as FALFE..E. Incorporating this countcrexample updates the hypothesis from an incorrect two-state automaton (left) to the correct parity DFA (right). The figure emphasizes the roles: OMq is informative yet fallible; OgQ is the noise-free verifier that prevents drift due to systematic MQ mistakes.
For a single query under context define the (unknown) correctness probability p" (c. q)
Pr [X M[ql], X~Pa(-la)
<(q c) (²(c, q).
Let n² be the number of MQs used by optimal exact-MAT learner (e.g.. L*) when Ozq returns shortest counterexamples. The average MQ mistake rate along such a minimal set {qI,..., 9n²) is
1 e(q: c).
E(c)
In pMAT, these mistakes arise from approximate MQ oracles and and-critiially--errii across resam- pling unless corrected by external verification.
Fix and q. Consider i.idd samples Xj.... X, Pa(- q) and any resampling-bate based aggregator Am(X (X1.m)) E (0, (majority vote, self-consistency, etc.). Definition 3.2 (Persistent error). Query q exhibits a persistent error (under e) if the mode of the oracle's 's distribution disagrees with the Iruth:
mode Pa(x 9) * M(ql =E(0.1)
+ p²(c))) +
4

---

Published as a conference paper at ICLR 2026
Convergence empirical distribution
PMAT Membership
Performanice
Connect Weong
Correct Whong
06-
0.6
0.
0.4
0.
0.4
0.0
0.0
20
160
121531
10)
Figure 2: Empirical behavior of LLM MQ oracles. (a) Convergence of the empirical distribution under resampling for a query with p" < : as the number of samples m grows, the empirical mode concentrates on the wrong label (variance 4, bias unchanged). (b) Per-query correctness probabil- ities for set of binary strings in the divisible-by-3 language; bars show the LLM's probability of answering an MQ correctly (green) vs. incorrectly (red). Several queries have green 30%, i.e. persistent errors. Model: EPT-4o-mimg temperature 0.9, 30 samples per query.
3.2 LLMs AS PMAT MEMBERSHIP ORACLES
Large language models provide a concrete instantiation of the stochastic membership oracle Oasq in p.AT., Given a context an LLM induces conditional distribution py y |c). After post-processing to binary MQ decision for a query word Σ" (e.g., mapping True/F alse to 0)), we obtain
Ox c] ~ Pe(- q) = Bernoulli(p" (c, q)): c(q c) p" (c. q).
Multiple forward passes (different sampling seeds, self-consistency chains, etc.) simply draw addi- tional i.i.d. samples from the same P.(. q).
Self-consistency amplifies bias (Fig. 2a). By the Strong Law of Large Numbers, any aggregator that asymptotically returns the empirical mode satisfies
Am (X(mm) T0-300
mode Po(x q).
Hence resampling reduces variance but cannot remove bias: if pf (c, q) < then
Pr[An (X (X1:m) + M[q]] - 1,
and majority vote converges almost surely to the wrong label. Figure visualizes this phenomenon: as the number of samples m increases, the empirical distribution collapses onto a single label-but when the oracle is biased, that label is incorrect. Thus ra-sampling increases consistency while leaving systematic mistakes intact unless noise-free verifier intervenes.
Empirical evidence structured language (Fig. 2D). We probe LLM the "divisible-by- 3" regular language using fixed prompt (context c). Each bar on the z-axis corresponds to binary query (shown decimal for legibility). The green segment indicates the probability the model labels the MQ correctly; the red segment indicates the probability of an incorrect label. Several queries satisfy p² q) < (green < 50%), demonstrating persistent errors: resampling or majority vote will converge to the wrong answer for these queries. Together with the schematic in Fig. [ these plots justify the PMAT assumption for LLMs: MQ answers are informative yet noisy biased, query-dependent manner, while perfect EQ oracle is required to detect and correct the resulting systematic mistakes.
Prompting strategies. Under PMAT, the context e captures the full prompt (language definition, alphabet, examples, and instructions) used to elicit MQ answers. Different prompt styles induce different distributions P. q) and thus different error profiles e(q c). We explored four prompt- ing families: Baseline (direct Frue/Falle answers), CoT (chain-of-thoughh reasoning before answering). Verification (a second pass that checks CoT consistency), and Discrimination (con- trastive examples drawn from a discrimination tree). Each aims to improve p" (c, q) by encouraging consistency, coherence, analogical reasoning. Full prompt templates given in Appendix A.5
5

---

Published as a conference paper at ICLR 2026
Algorithm 1: Noise-Robust I.* with CE Labels and a Discrimination Tree
Input: Alphabet E; oracles (OMq, OEQ); significance a; tolerance cap Tmax. Output: Hypothesis DFA H.
S 4 {=}; Ecore +- 0: Epool f- short suffixes U few randoms.
Estimate i with a small-budget routine; set Pa + 2fi(1 f)
while true do
// (1) Build classes with noise-award same-state test
Use union-find S with SAMESTATE(U, v; Po; a), cache negatives and early-stop. Choose canonical representatives rep(C") for classes C.
// (2) Closedness
while 3s E S,a E s.t. Bu S with sa ~ u do
L Insert all prefixes of sa into S and continue.
discrimination tree Build a DT from Feeaee and the reps rep(C).
// (3) Consi stency via
3 a whose successors lead to two distinct classes C1 + C2 then
e e (CA, C2).
10
11
i then add the single column a+e to Exore: continue else enumerate short t-il; tail E' and add the first separator; continue
// (4) Build hypothesis H
Define transitions (C, = C where rep(C)a rep(C"). For acceptance: if any stored CE e that reaches C' has CMQ [] 1, mark C accepting; else use majority over {ī(s) C}.
13
14
15
FrO [H] OK then
L return 7
16
// (5) Process counterexample C E* from OEQ
Label: set CMQld] + - H(g)'
17
RS split: find earliest c = wae with 6 (H((), a) # H(ua]. found then add to Fecorei insert prefixes into $
18
19
29
else (label-only) record on repeat of the same add all suffixes of e to Ecore
Code-based oracle. Unlike prompt-based methods, the code-based oracle uses the LLM only once to synthesize an executable predicate (e.g., Python) from the natural-language description of the DFA. All MQs then answered deterministically by evaluating this predicate. This eliminates variance, lowers еттог rates, and reduces LLM cost to a single call per task, converting free-form responses into verifiable logic. See Appendix A.3 for examples and implementation details.
CAPAL ALGORITHM
We operate in the pMAT setting (Section 3). where the learner L interacts with probabilistic membership oracle OmQ and a perfect equivalence oracle OzQ to identify the unknown target DFA M (QM, Σ. gd 8.M F.M.. Memhership answers are persistently noisy: for any word E D" the (cached) response [M]]w]= {0, }} equals the true label M(ggM w) with expected probability 7 and is flipped with expected probability < 1; asking again yields the same (persistent) value since repeated queries will not converge to the ground truth, we therefore cache the initial response. The EQ is exact: hypothesis DFA H. OEQ returns either OK counterexample n with H. # M(g. c).
maintain a prefix-closed set S C Σ* and a multiset of suffixes E Ecore U Epool S Σ to construct observation table in the L* (Angluin, 1987). For u E S and e E E we store the cached membership label 7(u u e) (mqlu-e like LEARNANY (Angluin et al. 1997). The row of is the vector row(u) (7(u e)).Eg. The subset Ecore contains musst-use discriminators for state comparisons; Epoot provides extra columns to increase statistical power but sampled under fixed budget.

---

Published as a conference paper at ICLR 2026
woise-aware class query. Given estimate of the membership error rate, we define the noise floor pa = 21((1 - f)). For u, U.v. E
let
1 m HEEE: Huu)) + ū(ve) H/ 3 == Ecore (a capped sample from Epool):
D(u, v)
with m = [8). We use SAMESTATE(U, Po. a) to represent the class query: it accepts same state "u v" (the noise-aware class query accepts u and v as belonging the same Myhill-Nerode class) iff D(u, v) I Po + т, where r min m Tmuxx v /In(2/a)
(definitions of a and m in App. A.3.2). We cache every negative outcome (u, v) DIFFERENT (monotone under persistence) and perform early stopping once even the best possible final average would exceed po + Using this test, we maintain classes over S via union-find. We estimate î with a tiny bootstrap and reuse-first procedure that limits new MQs via a strict budget. This only affects the threshold po and does not change correctness. We run micro-bootstrap to estimate r and a confidence radius that feeds the Hoeffding tolerance. We conservatively cap i) I n) with 2 7i this raises Po and makes false "DIFFERENT" decisions harder, which is required for the soundness of negative-result caching (details in App. A.3.2
Closedness and consistency Closedness requires that for every E S and a E Σ there exists E S with sa u, violations cause us to insert all prefixes of sa into S. Closedness alone does not guarantee DFA; we also enforce consistency: whenever 81 82 and E E, their successors 8 a and 820 must land in the same class. To repair inconsistencies with few columns, we maintain a discrimination Iree (DT) T (Isberner et al. (014) over current classes: internal nodes store discriminators e E Ecore: leaves store disjoint sets of classes. For two classes C1 # C2. the lowest common ancestor (LCA) carries discriminator eLCA that separates them. Thus, when class C' has successors to two distinct classes under a, we add a single column a e to Evore (and lazily cache the needed cells). If the LCA discriminator fails to separate due noise on a representative, we fall back to a short enumerated search for a short a-ee that separates. By ensuring the closedness and consistency of the observation table, can theoretically guarantee the correctness of the learned DFA. We put the proof in the Appendix A.3
Hypothesis construction and refinement For each class C, pick a canonical representative rep(C) (e.g., short-lex). Define transitions by 6* a) C³ such that rep(C)a rep(C"). For acceptance: if any stored CE that reaches C' has CMQ [c] = 1, mark C accepting; otherwise decide by majority over ([(s) : e C}. The resulting DFA is H. = (Q*, E, oft 8H, FHH with states Q* identified with classes.
When Ogo returns c E Σ' with H(10 c) * MigM c). we then attempt RS analysis Rivest & Schapire 1989; y scan c = uae for the earliest position at which 5t (H[u), a) * H uul: if found, we add e to Ecore and insert prefixes of into S. If no split is found (pure label conrection), we gate processing: record the CE label and do not add columns the first time; only if the same CE reappears do we minimally escalate by adding all suffixes of eto Ecore- This is purely for MQ efficiency: when an RS split is absent, the CE is likely due to state mislabel rather than a structural error. If the same label-only CE reappears, this suggests that the current suffix set cannot isolate the erroneous class, which then justifies adding all suffixes of c to Ecore.
The algorithm combines L"'s table discipline, noise-aware statistical equality test with negative caching, CE label overrides for states, and a TTT-style DT for near-optimal consistency repairs. It converges under persistent MQ noise with an exact EQ, while keeping both the number of discrimi- nators and the number of MQs small.
Theorem 1 (Query complexity). Let the target minimal DFA have (n) states, alphabet Σ, access diameter P. and counterexamples of length at most I-E.- Under a perfect EQ and persistent MQ noise with y <, 2. CAPAL terminates whh.p. and returns the exact language. Moreover,
# #EQ = =((), #MQ = O(E),n² nLCE) + O(m, (E),
where m = 0 2o0ly2/og(1//00) (o))) is the suffix budget per class decision for noise margin ry at confidence 1 - For fixed noise/confidence. (m) is constant and the asymptotics match classical L". (Proof in App. A.3) DT bounds |Eomel S n - 1; closedness/consiitenny touch [[E),|S) pairs with |S| O(n)); each class decision uses most m suffixes; counterexamples contribute OnT.e))
7

---

Published as a conference paper at ICLR 2026
S, Ecore
Closedness
Build
Consistency
Build
EQ
Errors
CE-lA (eise)
Iter
E2S0/E3
CE:ja
CREHES
Iter
[r,a), (ED
Nuil (CK)
10
1:al
Figure 3: Running example for CAPAL. One CAPAL the DFA SIMPLE-01 (even number of a a's); each row is an outer iteration. The Closedness block enumerates all (s, a) with E S and Σ; red cells mark pairs violating 3u S sa u. The remaining blocks show, respectively, the discrimination tree (internal nodes are discriminators, leaves are classes written as (ID: MEM- BERS)), the consistency table (class IDs reached by sa). the current hypothesis DFA (double green circles are accepting states), the EQ result, and the set of persistent MQ errors.
Running Example Figure 3 shows one CAPAL run on the DFA SIMPLE-01, which accepts ex- actly the words over > {a. b} with an even number of a's. We connect CAPAL to a pMAT with persistent membership noise 77 = 0.1 and a perfect EQ oracle. A short bootstrap makes few dozen MQs, estimates f), and thus fixes the noise floor Po and threshold po + that appear in the rightmost column of the Closedness tables. Words whose MQ labels are flipped by the noisy oracle are listed the Errors column.
We start with the prefix set S = {e} and empty core suffix set Frore = 0. The first closedness check examines s =, a===== and fails because there is no u with sa offending word (and its prefixes) is therefore added, giving $ = {s, a), and second closedness pass over this S and E then succeeds for all pairs (s, a). Union-find on yields two classes with representatives and a; since Eeore is still empty, the discrimination tree collapses to single leaf and the consistency check is trivially satisfied (each class has one member). CAPAL builds two-state hypothesis Hi whose transitions already match the even/odd-a DFA, but because has been persistently mis-labeled, both states are marked accepting, so the EQ oracle returns the counterexample a.
Iteration 1.
u. The
Using the trusted EQ label, CAPAL first corrects the label of a. The Rivest-Schapire scan finds no transition mismatch along c, so is treated as a label-only counterexample and its short suffix is promoted into Eoore. while S remains {e, a} and closedness still holds. Rebuilding the discrimination tree with core suffix now separates the classes: appending a to E and leads to different acceptance, so they fall into distinct leaves. The Consistency table confirms that for every class C' and symbol E Σ, s E have successors sa single class, so no further refinement is needed. Rebuilding the hypothesis Ha keeps the same transition graph but now only the even-a state accepting; the EQ oracle finds no further counterexample, and CAPAL halts with the correct even-parity DFA.
Iteration 2.
5 EMPIRICAL RESULTS
This section evaluates our prompting strategies and the CAPAL algorithm, comparing them against baseline active/passive learners.
Setup. Implementations are from LearnLib Isberner et al. (2015). We use 200 hu-
man-interpretable DFAs (2-50 states) from Sipser (1996); RegexLib.com (025): Kushman & Barzilay (0033). Each DFA can be described by a short natural language specification; the LLM oracle receives this description and the alphabet. We vary counterexample length and the PMAT membership error rate e to probe robustness. Unless stated otherwise, the oracle is gpt-4o with temperature 0.9.
natural-language
8

---

Published as a conference paper at ICLR 2026
Table I: LLM query cost and oracle error. Average std. LLM calls per DFA for LEARNANY- WAY (LA) and CAPAL; is the empirical MQ eπror rate. We omit TTT and L here-whree they fail learn the harder DFAs, their query counts become non-comparable.
Oracle Type
LA
CAPAL
Baseline
46.07
(433.0)
43.75
(1:302)
0.156
CoT
52.64 (137.3)
30.93
(116.5)
0.068
Verification & CoT
51.57
(+3..5)
28.96
(1977
0.044
Discriminator & CoT
51.82 (+40.1)
29.14 (=15.8)
0.047
Code-based
(=0)
(0)
0.013
Table 2: Learning accuracy (fraction of DFAs learned exactly). Here TTT and I.* are included because accuracy remains comparable even when some DFAs are not learned.
Oracle Type
TTT
L'
LA
CAPAL
Target DFA (upper bound)
1.000
1.000
1.000
1.000
Baseline
0.107
0.071
0.107
0.250
CoT
0,429
0.393
0.500
0.571
Verification & CoT
0.464
0.429
0.714
0.679
Discriminator & CoT
0,571
0,536
0.714
0.821
Code-based
0.750
0.678
0.786
0.928
5.1 PROMPT STUDY
Table [ compares different prompting methods. Moving from a direct Baseline prompt to CoT more than halves the MQ error rate (e: 0.156 - 0.068, -56%). Adding an explicit Verification hints drives to x 0.045 (0.044 and 0.047, - 72% and 70% vs. Baseline). The query budgets mirror this improvement when the same learner reuses consistent (Baseline) to 30.93 (CoT, -2%%), and answers: for example, CAPAL's LLM calls drop from 43. 75
step or Discriminator-guide
further to 28.96 (Verification, - 34%) or 29.14 (Discriminator, - -33)). In contrast, richer prompts that perform explicit veveiiiintveriiiaation the L.M on every MQ (see the LA column), even though their is lower.
add small constant overhead for learners that query
The code-based oracle changes the regime entirely: single synthesis call produces deterministic checker, after which MQs are answered without further LLM interaction. This yields the lowest error rate 0.013, 92% vs. Baseline) and collapses the LLM budget to 1 call per task for both learners 2 97% reduction relative to any prompting-one method).
5.2 ALGORITHM COMPARISON
Table 2 summarizes end-to-end success. Standard active learners (TTT, L*) are brittle under noisy MQs, rarely recovering from systematic mislabels. LEARNANYWAY (LA) improves robustness via counterexamples, but CAPAL is consistently as good or better across oracle types; the gap is largest when prompts reduce (e.g., CAPAL 0.821 vs. LA 0.714 with Discriminator&&of:: 0.928 0.786 with code-based).
Then discuss how class queries and discrimination trees of CAPAL helps:
Class queries tame persistent noise. Instead of trusting single MQ labels, CAPAL asks whether two prefixes u, e belong to the same -ehidl class. This is decided by aggregating MQ evidence over small set of suffixes. Under PMAT,, if each MQ has correctness probability p² (c.-) 3. then majority on a handful of suffixes yields statistically reliable class decision, even when any individual MQ may be wrong. Thus, CAPAL converts noisy Bernoulli answers into robust hypothesis- refinement signal that is resilient to persistent, query-dependent biases.
Discrimination trees localize and minimize queries. Rather than maintaining large observation table (as in L*) or repeatedly repairing with long counterexamples (as in LA), a discrimination tree indexes states by short distinguishing suffixes. New information only traverses single root-to-leaf

---

Published as a conference paper at ICLR 2026
Figure 4: LEARNANYWAY, RPNI-EDSM, CAPAL comparison as varies. Both RPNI-EDSM and CAPAL learn within 10d MQs; CAPAL requires fewer MQs than LA and keeps counterexample use stable
MOS vs Epsiion
EQs vs Epsilon
Accuracy vs Epsilon
1.00
10-
Near Nembers-p Quertes (log.
Equirolennee Quarric togl
0.90
0.92
0.08
CAPAL (Qura) LEARNONTART
0-
0.00
0.05
0.30
0.15
0.00
0.05
0.10
0.25
0.00
0.05
0.30
0.15
(Probebility Emro))
Epsiton (Probability Emro))
Epstor (Probablitt
path, so each refinement reuses previously validated separators and touches Olog [Q) tests. This (i) avoids re-asking brittle MQs; (ii) amortizes errors across repeated tests on the same separators; and (iii) naturally favors near-minimal discriminators, reducing both query count and exposure to error on long words.
5.3 SCALING WITH PERSISTENT NOISE
To stress-test robustness, we inject a probabilistic oracle with error rate E [0, and allow counterexamples up length 10. Figure E shows that CAPAL fewer MQs than LA noise grows and does not require polynomially more counterexamples. When 2 0.18, purely pas- sive RPNI-EDSM can be more query-efficien because avoids MQs altogether: however, the prompt strategies in Table ttyiccally keep < 0.1, where CAPAL clearly outperforms both LA and RPNI-EDSM.
DISCUSSION AND CONCLUSION
CAPAL demonstrates that active learning of regular languages can be made robust to persistent membership noise when a perfect equivalence oracle is available. The central shift is from trust- ing individual MQ labels to issuing a class query that aggregates evidence against principled noise floor, with early stopping and monotone (negative) caching avoid re-litigating pairs already shown different. On top of the observation-tabb loop, a discrimination tree selects single derived column a+eLLCA to repair each inconsistency, which keeps |Ecorll linear in the number target states. Counterexamples supply bias-free labels; we use them to override acceptance for the reached hy- pothesis state and to gate processing of label-only CEs, thereby preventing bursts of fresh MQs that would inject additional persistent errors.
Limitations suggest directions for future work. If Ozo is approximate, false negatives (missed CEs) require extending the theory tolerate occasional incorrect OK responses. If í) underestimates the true error rate, negative caching could principle lock in spurious splits; our conservative cap mitigates this, but fully adaptive, PAC-style control across many tests is desirable. Finally, persistent noise may drift with prompt context; adaptive re-calibration and drift detection would strengthen robustness.
Beyond DFAs, the CAPAL pattern class queries, DT-guided repairs, CE-label overrides, and gated CE handling- extends naturally to Mealy/Moore machines, register automata (with domain-aware discriminators), and symbolic automata. Overall, PMAT plus CAPAL offers a practical route to verifiable neuro-symbolie systems: even when language models are fallible, structured interaction with a perfect equivalence oracle suffices to synthesize formal artifacts whose correctness can be certified at the end of the loop.
Reproducibility Statement. We have taken several steps ensure the reproducibility of our sults. All code and datasets used in this work will be released to the public, including implementa- tions of CAPAL, prompt templates, and experimental scripts. Detailed descriptions of experimental
10

---

Published as a conference paper at ICLR 2026
settings (e.g., random seeds, hyperparameters, query budgets, and noise models) are provided in Sec- tion and the Appendix. Prompt templates for all oracle variants are also included Appendix Together, these materials enable independent researchers to reproduce all experiments and results reported in this paper.
REFERENCES
Shayan Meshkat Alsadat, Jean-Raphael Gaglione, Daniel Neider, Ufuk Topeu, and Zhe Xu. Using large language models to automate and expedite reinforcement learning with reward machine, 2024.
Mohammed Alshickh, Roderick Bloem, Rüdiger Ehlers, Mykel J Kochenderfer, Ufuk Topcu, and Moshe Y Vardi. Safe reinforcement learning via shielding. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 32, 2018. URL https: pettps:/ddoes org.:////ooooooooooo.ooooooooooo 1609/
aaai. v3211 11797
Dana Angluin. Learning regular sets from queries and counterexamples. Information and Computa- lion, 75(2):87-106, 1987. ISSN 0890-5401. doi:
(877)0005-6
Dana Angluin, Märtinš Krikis, Robert H. Sloan, and György Turán. Malicious omissions and errors in answers membership queries. Machine Learning. 28(2):211-255 1997. ISSN 1573-0565.
doi: 10. 10.1023/A:100031111222
Marco Bagatella, Andreas Krause, and Georg Martius. Directed exploration in reinforcement learn- ing from linear temporal logic. Transactions on Machine Learning Research, 2025. ISSN 2835- 8856. URLhttps: http:://pppeeeeeeeeeeeeemee http://wwww.eeeettreeaaaaaaaa-//
Gill Bejerano. Automata learning and stochastic modeling for biosequence analysis. Citeseer, 2003.
Raymond Board and Leonard Pitt. On the necessity of occam algorithms. Theoreti- cal Computer Science, 100(1):157-184, 1992. ISSN 0304-3975. doi: https://doi.org org/110. 101600004-39755992906666000 URL
wwtp//ettt.cc/cccieeeeeee scinne/
atticie/p.1/0000333552222
Josh Bongard, Hod Lipson, and Stefan Wrobel. Active coevolutionary learning of deterministic finite automata. Journal of Machine Learning Research, 6(10), 2005.
Miguel Bugalho and Arlindo L Oliveira. Inference of regular languages using state merging algo- rithms with search. Patlern Recognition, 38(9):1457-146) 2005.
Alberto Camacho, Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. Mcll- raith. Lıl and beyond: Formal languages for reward function specification in reinforcement learn- ing. In Proceedings of the Twemy-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 6065-6073. International Joint Conferences Artificial Intelligence Organiza- tion, 7 2019. doi: 10.24963/ijcai..20 2ttp://icai.00119//... 2019/8409. 9/40/
URL
François Denis, Aurélien Lemay, and Alain Terlutte. Learning regular languages using rfsas. Theo- retical computer science, 313(2):267-294, 2004.
Craig Innes and Ram Ramamoorthy. Elaborating on learned demonstrations with temporal logic specifications. In Mare Toussaint, Antonio Biechi, and Tucker Hermans (eds.), Proceedings of Robotics: Science and System XVI, July 2020. doi: 00.15607/RS..22200 2020.XV1.004. URL https:: /tops::/rrbbtt.i woaboticsconffeeeee
org/ Robotics: Science and Systems 2020, RSS 2020 Conference date: 12-07-2020 Through 16-07-2020.
Malte Isberner, Falk Howar, and Bernhard Steffen. The ttt algorithm: A redundancy approach to active automata learning. In Borzoo Bonakdarpour and Scott A. Smolka (eds.), Runtime Veri- ficatiin, pp. 307-322, Cham, 2014. Springer International Publishing.

---

Published as a conference paper at ICLR 2026
Malte Isberner, Falk Howar, and Bernhard Steffen. The open- learnlib A framework for active automata learning. In Daniel Kroening and Corina S. Pasareanu (eds.), Computer Aided Verification 27th International Conference, CAV 2015, San Francisco. CA, USA, July 18-24, 2015, Proceedings, Part I, volume 9206 of Lecture Notes in Computer Science, pp. 487-495. Springer, 2015. doi: 0000779978-3311-216990
Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.
Nate Kushman and Regina Barzilay. Using semantic unification to generate regular expressions from natural language. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NA,CL-HLT),
pp. 826- 836, 2013.
Kevin J. Lang, Barak A. Pearlmutter, and Rodney A. Price. Results of the abbadingo one dfa learning competition and evidence-driver state merging algorithm. In Vasant Honavar and Giora Slutzki (eds.). Grammatical Inference, pp. 1-12, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg. ISBN 118-3-540-68707-3
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference Learning Representa- tions, February 2023.
William Merrill Sequential neural networks automata. In Jason Eisner, Matthias Gallé, Jeffrey Heinz, Ariadna Quattoni, and Guillaume Rabusseau (eds.). Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pp. 1-13, Florence, August 2019. Associa- tion for Computational Linguistics. doi: 10.18653/v1/W 1t////199999
José Oncina and Pedro García. IDENTIFYING REGULAR LANGUAGES IN POLYNOMIAL TIME, pp. 99-108. World Scientific, 1993. doi: 10.1142/9799812777799900
RegexLib.com. RegexLib: A Regular Expression Library. http:://w..rgexxxb... com/
2025. Accessed: 2025-05-06.
Ronald L Rivest and Robert E Schapire. Inference of finite automata using homing sequences. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pp. 411-420, 1989.
Michael Sipser. Introduction the theory of computation. ACM Sigact News, 27(1):27-29, 1996.
Rodrigo Toro Icarte, Ethan Waldie, Toryn Klassen, Rick Valenzano, Margarita Castro, and Sheila MclIraith. Learning reward machines for partially observable reinforcement learning. In H. Wal- lach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. Mcllraith. Reward ma- chines: Exploiting reward function structure in reinforcement learning. Journal of Artificial In- telligence Research, 73:173-2000 January 2022. ISSN 1076-9757. doi: 10.1613/jair, 11161//arr...1222 1.14440.
Marcell Vazquez-Chanlatte Karim Elmaaroufi, Stefan J. Witwicki, and Sanjit A. Seshia. ImIm: Learning automata from examples using natural language oracles, 2024.
Cameron Voloshi,, Hoang Minh Le, Swarat Chaudhuri, and Yisong Yue. Policy optimization with linear temporal logic constraints. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL /ttp:///pppeeeieeieeeee n www.:neee//o.dd//eee..e. wtw.:mommmxxyyee2222.000
Michele Volpato and Jan Tretmans. Approximate active learning of nondeterministic input output transition systems. In Proceedings of the 15th International Workshop on Automated Verifica- tion of Critical Systems (AVOCS 2015), volume 72 of Electronic Communications of the EASST, Nov 2015. doi: 0..14279tuj..ccaastt. 72. URL https: /ww. (tt.oooorg/....2277999.. eceasst. 72, 1008
12

---

Published as a conference paper at ICLR 2026
Nan Yang, Kousar Aslam, Ramon Schiffelers, Leonard Lensink, Dennis Hendriks, Lock Cleophas, and Alexander Serebrenik. Improving model inference in industry by combining active and pas- sive learning. In 2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER), pp. 253-263. IEFE, 2019.
Yunhao Yang, Neel P. Bhatt, Pranay Samineni, Rohan Siva, Zhanyang Wang, and Ufuk Topcu. Repv: Sefety- latent spaces for scalable neurosymbolic plan verification, 2025a. URL
Yunhao Yang, Junyuan Hong, Gabriel Jacob Perin, Zhiwen Fan, Li Yin, Zhangyang Wang, and Ufuk Topcu. Ad-vf: Llm-automatic differentiation enables fine-tuning-free robot planning from formal methods feedback, 2025b. URL URLLittsss//rrii..er//aaaa wttp:////aabbaaaa/o 18384
Yunhao Yang, Cyrus Neary, and Ufuk Topcu. Automaton-based representations of task knowledge from generative language models. In George Pappas, Pradeep Ravikumar, and Sanjit A. Se- shia (eds.). Proceedings of the International Conference on Neuro-symbolic Systems, volume 288 of Proceedings of Machine Learning Research, pp. 765-783. PMLR, 28-30 May 2025c. URL ittps://procecing wwwpediinnss.....ommmm press. v288 2a12228yyann2aaaa...a 5hmmmml
13

---

Published as a conference paper at ICLR 2026
A APPENDIX
A.1 RELATIONSHIP BETWEEN ERRORS AND CE LENGTH
Figure 5: Relationship between errors and CE length. The average length of CEs refers to the length parameter used during generating CEs. They must be longer than this length parameter unless longer counterexample exists. If the average CE length set to O, the oracle returns the shortest counterexample. This test is running on simple automaton that recognizes strings with more than 3 "a's and more than 2 bbs, employing the LEARNANY WAY & TTT as the DFA learner.
MOs Length
EOs Length
Length
Membenhi Overes (og100
Esitalence Queres DoggtOn
Entes Deg
3.
2.2
3.8
2.0
3.
10
14
10
14
10
14
Arg. CE Length
Arg. CE Length
Avg. CE Lengt?
A.2
EFFECTS AND SOLUTION OF AN IMPERFECT EQ ORACLE
120
eta mq 0.05
20
cta ma 0.05
100
PAC (n=4, eta m.00.00
PAC (n=4, eta, etaelttaaaaaaaaeeeeeee mammmq-0000
PAC 0.00)
0.6
E0S
10
5
mg
0.05
0.2
PAC (n=4, eta, eaaeletaaaaaaeeeeeeeee ma=0.0)
(n-4, eta, ma-0.mmm..mm
0.0
0.000
0.025
0.050 0,075 0.100
0.000 0,025 0.050
0.075 0.100
0.000
0.025
0,050
0.075 0.100
EQ failure probability P
EQ failure probability
EQ failure probability
Figure 6: Robustness to imperfect equivalence oracle. We corrupt the EQ oracle so that whenever the hypothesis is not equivalent the target, it independently fails return a counterexample with probability p E [0, 0.1] (but still answers "equivalent" correctly when the languages match). We re- port mean and standard deviation over repeated runs for (left) learning accuracy, (middle) number of MQs, and (right) number of EQs, under two MQ noise levels (7MQ = 0 and 0.05) and with/without a PAC-style EQ wrapper with n 4 retries.
Figure shows that CAPAL remains surprisingly robust even when the EQ oracle is imperfect. With a single noisy EQ call per round (eta.mç = 0 0/0. 05 curves), the learner maintains high suc- cess probability across the entire range p S 0.1: accuracy typically stays the 80-95% range, and failures are mostly due to rare runs where the EQ oracle repeatedly misses the same counterexample and the algorithm stops early. Importantly, the average number of MQs and EQs is essentially flat in p. indicating that CAPAL does not become unstable or enter long oscillations even when the EQ oracle occasionally misses counterexamples.
To further harden the algorithm, we wrap each EQ query in simple PAC-style repetition scheme: instead of calling the imperfect oracle once, CAPAL issues up to n = independent EQ calls and only accepts equivalence if they all return "no counterexample: This reduces the probability of silently accepting an incorrect hypothesis from p to at most p (e.g.. 10 when p = 0.1), while increasing the EQ budget by most constant factor of The dotted P PAC curves in Fig. o this behavior: accuracy is driven back close to 100% for all tested and both MQ-noise settings, yet the number of EOs only increases modestly and the number of MQs is virtually unchanged.
14

---

Published as a conference paper at ICLR 2026
Thus, when the practical EQ oracle is approximate, CAPAL can be made highly reliable by lightweight PAC-wrap that introduces only a small, constant-factor overhead in EQ usage.
A.3 CORRECTNESS AND CONVERGENCE IN THE PMAT SETTING
We analyze Algorithm in the PMAT model (Section 3 the learner interacts with perfect equiva- Ience oracle OEO and a persistent-noisy membership oracle OmQ with error rate < 2 The target DFA is M (Q.M E, % 8M, FM).
What have been proved in /R/TTTTT. The following facts are classical and we cite them with- out reproving:
1. Closed consistent tables define a DEA hypothesis. In the exact-MQ setting, closed and consistent observation table induces well-defined DFA H. whose states correspond to distinct rows and whose transitions are induced by row successors (Angluin) 1987 Angluin
(tt al. 1997).
2. Counterexamples enforce progress via suffixes. Rivest-Schapire decomposition extracts, from any CE e, short suffix that distinguishes appropriate rows; adding e strictly creases the table's discriminating power (Rivest & Schapire 1989).
3. Discrimination trees are O (QM)). A TTT-style discrimination tree (DT) over n states uses most n n- internal discriminators and repairs inconsistencies using single LCA discriminator [Isberner et al. 2014).
4. Termination in the exact-MQ case. With exact MQ and perfect EQ, L terminates and returns DFA equivalent to the target (Angluin 1987 Angluin et al. 1997).
What remains to prove in our setting. Because OmQ is noisy and persistent, while OFo is perfect, we must justify:
a noise-aware same-state test with negative-result caching,
the use CE labels (no MQ) to fix state acceptance,
gated processing of label-only CEs avoid noise amplification, and
finite convergence with high probability under safe noise bound.
A.3.1 SOUNDNESS
Theorem (Soundness). If Algorithm haalts with DBQ[H] OK, then L(H) L(M).
Proof. Immediate from the correctness of perfect equivalence oracle: OK iff the languages are equal.
L
A.3.2 NOISE-AWARE ROW EQUALITY AND SAFE NEGATIVE CACHING
Let v be the leamner's estimate of and define the noise floor = 2fj(1 f) We fix a per- comparison significance level (0, 1): upper-bounds the probability that single SAMESTATE call incorrectly declares two truly equivalent rows as different.
For u. S, the test SAMESTATE( u, vx Po. a) chooses a finite set of suffixes
E F (a capped sample from Epool), m = [8],
where is exactly the number of suffixes (i.e., "votes") used in this particular class comparison. It then computes the empirical disagreement rate
D(u v) = 1 -e E ((ue) + Ø(ve)}
and compares it to the threshold Pu T, where
In(2/a)
T min Fmax:
2m
15

---

Published as a conference paper at ICLR 2026
We cache negative outcomes (declare v) and do not cache positives.
We assume the test uses a safe upper bound rj 2 17 (c.g.. by capping f)): then po( 2 2ny11 7), which makes false negatives harder, not easier. By Hoeffding, with m samples the probability that a single comparison misclassifies a truly equal pair is at most a; with at most Namp comparisons over the run, union bound yields total failure probability 8 I Nempa. Thus the negative cache is sound with probability at least 1
A.3.3 COUNTEREXAMPLES UNDER PERSISTENT NOISE
Given H. # M, OEQ returns c E E" with H((c) + M(c).
Trusted CE labels. Because OEQ is perfect, the CE's true label is: CmQld] < - 1 We store this as gold override for the exact word e and insert into S (prefix-closure already ensured by the algorithm).
Structural vs. label-only CFs. We attempt Rivest- Schapprr decomposition on c: if there exists an earliest factorization e wae with 5 (H(u), a) * H[ua], we add the bare suffix to Feore (structural progress). Otherwise is label-only and gate processing: record CmQ(c) [c] and do not add columns on the first occurrence; on a repeat of the same c we minimally escalate (add all suffixes of c).
Acceptance override for CE-reached states. When building H. if any CE reaches class C (i.e., M[c]] E C), we override C's acceptance to match Carold)
A.3.4 FINITE CONVERGENCE WITH HIGH PROBABILITY
Define the finite potential
= ((p.4) S CQM: not yet separated by Ecore
+
(hypothesis states with wrong acceptance)
Panxx
Suubet
Lemma 1 (Each CE decreases & w.h.p.). Assume the negative cache uses (o( with nj 2 n and per-comparison error probability at most a. Then with probability at least 1 - over all same-state tests (for suitable union bound 8), each CE returned by OEQ strictly decreases 4:
If RS finds split une, adding strictly increases the separation power of Ecore (by Rivest & Schapire 19891);; hence Struet decreases.
Otherwise is label-only: the CE override forces the acceptance of the reached state, decreasing Pinhel permanently (or, under the positive-only variant, escalation ensures the class majority flips the CE label after finitely many repeats).
Theorem (Finite convergence w.h.p.). Let I Under a perfect OEQ and persistent-noisy OMQ with 7 < 5. and using safe noise cap ij 2 1j in the same-state thresh- old, Algorithm] [
terminates after finitely many iterations with probability at least 1 - ö, and by Theorem 2 returns H. with LLH)- L(M). Moreover, the number of bare discriminators added to Ecore is (n) and in fact at most n - by the DT bound of Isberner et al. (2014).
Proof sketch. By Lemma 1 each CE strictly decreases the finite potential t < (*) + with prob- ability at least - 5. Hence only finitely many CEs occur before OEQ must answer OK, and soundness (Theorem 2 gives correctness at termination. The O(n) discriminator bound follows from the cited DT result.
Choosing schedule a aa/t² makes the sum Σ, Cce finite, yielding fixed 8 without needing an a-priori Nemp-
A symmetric override (both Csrale = 1 and 0 force the state's acceptance) gives the cleanest proof. The implementation may positive-only override; then repeated lahel-only CFs trigger bounded suffix additions that make the class majority agree with the CE, and the convergence argument below still goes through.
16

---

Published as a conference paper at ICLR 2026
Remarks. (i) The only probabilistic step is the row-equality test; by increasing the capped column budget (or decreasing a') we can make 6 arbitrarily small. (ii) Using a safe cap fj makes the neg- ative cache conservative:
lock in spurious split due to underestimating the noise floor. (iii) Gating label-only CEs prevents large bursts of fresh MQs that would introduce additional persistent errors; escalation on repeats is bounded and ensures eventual correction.
A.4 COMPLEXITY ANALYSIS
Let M be the minimal DFA for the target language, with := 1Qml states and alphabet E. Let denote the access diameter, i.e., the maximum length of a shortest access string to any state, and let LCE bound the length of counterexamples returned by the equivalence oracle.
Structural complexity CAPAL follows exactly classic loop: it maintains a prefix-closed set S S Σ* finite set of distinguishing suffixes Ecore S Σ², enforces closedness and consistency, constructs hypothesis DFA H, and submits it to an equivalence oracle. The only algorithmic difference is that consistency repairs guided by discrimination tree, which guarantees that the number bare discriminators at most n (TTT bound).
If access strings kept shortest, the prefix-closed set S has size
S = (np))
because each state admits at most one shortest access string of length at most p. and all prefixes of these strings are also included. Each time closedness and consistency are enforced, most [S] rows and |eore] columns of the observation table are queried. With |ecorl S 1, this yields
table-filling MQs ( |S| [Boore) = ( n² p).
Each counterexample contributes an additional O(LCE) MQs fill the row/column positions along the offending access path, just in T. Standard arguments then imply that at most ((n) coun- terexamples are needed: each either adds one new discriminator (at most n - in total) or fixes the acceptance of one previously misclassified state. Hence, in the noiseless case
#EQ O(n),
#MQ ( n² p nLCE),
which matches the usual L* regime up to constant factors.
Additional cost from noisy MQs and class queries the PMAT model, MQ answers may be incorrect with average eтror rate 1) and may exhibit persistent bias individual queries. The only place where CAPAL pays an extra cost compared to L is deciding whether two prefixes u, E S should be treated as belonging to the same Myhill-Nerode class. Instead of comparing single table rows, CAPAL uses a class query: draws a multiset suffixes C Σ*, computes empirical disagreement rate
D(u, v) [E]
(e E: y(ue) # y(ve))
and declares "u ~ v" iff D(u, u) < Po + T, where 2 n) is a conservative noise floor and is a Hoeffding tolerance.
Let (u, v) = [u, v)] Po denote the true gap between the disagreement rate of (u, v) and the noise floor. A standard concentration argument shows that, for any fixed confidence parameter (0, 1), there exists universal constant > O such that
log
1
Pr the test misclassifies (u, v))
7(u, v)2
Thus each logical "same/different" decision on pair (u, v) is implemented by class query con- suming at most
m
7(.,oY= log
noisy MQs. In particular, when 7 is bounded away from 1 and only require fixed confidence level, m can be treated as a constant independent of n, |Σ], and p. In the noiseless limit (n = 0), one can take 1, and the class query reduces classical row equality.
17

---

Published as a conference paper at ICLR 2026
Since class queries are only needed when checking closedness and consistency, the number of logical pairs (u, u) that are ever examined at most on the order of |X] |S| (each extension sa must be related to representative in S). Therefore the extra MQ cost due to class queries is
(class-query MQs) = (m | (S)) = ( 1
This term is of the same polynomial order as the table- sable-filling term; when m is treated as a constant depending only the noise level and desired confidence, the asymptotic behavior is unchanged.
Main complexity bound Combining the structural bounds with the class-query overhead and us- ing that the number of bare discriminators most n 1 and the number of counterexamples is On)) we obtain:
Theorem (Complexity of CAPAL). Let M be a minimal DFA with n states, alphabet E, access diameter p. and counterexample length bounded by LCE. Assume pMAT oracle with persistent MQ noise of average rate <. 2 and a perfect EQ. Then CAPAL terminates with high probability and returns DFA equivalent M. Moreover, for any fixed confidence parameter o, there exists constant YT = O + log 2) depending only on the noise margin 7 > O such that
#EQ O()),
#MQ O( n² n.CE) + O(m p)
In particular, if m is treated as a constant (e.g. 7 bounded away from &/ fixed a.), the asymptotic order collapses the classical L rate up constants:
#EQ = O(n), #MQ O( nLCE).
In the noiseless case (1) = 0), we have m and CAPAL reduces exactly to the L*/TTT discipline.
This matches the intended design: CAPAL preserves the query-complexity guarantees of classical active DFA learning, while paying only a controlled multiplicative overhead for the statistical class queries needed tolerate persistent MQ noise.
A.S PROMPT ENGINEERING
A.5.1 BASELINE PROMPT
We minimal instruction that states the language definition and alphabet, then asks whether word wo E E' is in the language, requesting terse True faae/Faalss False output (Fig. 7 left). This serves our simplest MQ oracle and exposes the error profile Po(: w) under pMAT.
Template (abridged).
Language definition: [...]
Alphabet: [...]
Word: [...]
Answer with exactly True or False.
A.5.2 CHAIN-OF-THOUGHT (CoT) PROMPT
To reduce shortcut errors, the CoT variant asks the model to reason before committing to a label (Fig. 7 middle/right). The final decision is still parsed single Boolean token, while intermediate text is ignored by the learner.
Template (abridged).
Language definition: [...]
Alphabet: [...]
Word: [...]
Reason step by step. Then output on line:
Final: True or False
Full prompt text, examples, and ablations for both templates provided in Appendix 7
18

---

Published as a conference paper at ICLR 2026
Figure 7: An Overview of Basic Prompts
Baseline
COT Prompt
Verification Prompt
Model
Moddel
Model
Rerris snggaae only aoccets sttins numpiti mhsaphhettiaa SNA repecii by Une langugg??
lasisom deligno suppue
о The larget
Botulot Din Siven autiin 29..0 2.. a does 2 soting takogg tmngugg??
the formut (awwholh 1Wiiss enaivil here detail.-
teacct porieitoon on (rox labe). 'muttt pppel puppelt (Brae laball
Dhement: comatiio biece
<: Damasee detestion Maarsaeeti seqaance Vigaany" joy noi) the languoge, becuue (aaf
belange innweer' Trui))
Beamy (mmmenl) en Down the mesen language
language detintten (Alanseetil anguage??
Mozel Output
Mode Ouepue
"neaet's "The comabi uecuunne tt's The lampugge vod duddda only the singue uepuenee (KT) and (M)) oninntngg contare
"anahvis Thk langunge is cefired includl soqger
incept for the sinuueer taples Itrs and PR-AA althatel sequerec
character
ponsirs 'ol
mutet the scur soquanors contalle than shanscie and nome of sut sequercee or the aequanoe lsal reatrcted la the lanqusan deristion, Tharsfora, the and cont sacuanes (+) le, the beguage.
A.5.3 VERIFICATION PROMPT
The Verification prompt extends the capabilities of the Chain of Thought (CoT) prompts. Ini- tially, LLMs respond to membership queries by performing analyses similar to those demonstrated in example queries as we see in figure However, due to the tendency of LLMs to generate hal- lucinated content, these analyses may not always be relevant to the actual query input or the lan- guage definitions, leading to incorrect membership decisions. To address this issue, we introduce Verification step.
Upon receiving the initial response from the LLM to a CoT query, a secondary process begins where a "teacher" L.LM checks whether the response aligns with the expected definitions and the context of the query. This involves comparison of the initial analysis against set of language definitions that constitute a correct response, as well as the original query input. The LLMs are required to
output JSON object containing three components:
whether the analysis matches the language definition,
whether the analysis is consistent with the query input, and
the reasons why the analysis matches the definitions, as well as why the analysis is based on the query input.
If the teacher finds discrepancies between the initial answer and the expected standards, the fol- lowing actions are taken: a) If the input sequence and definition match but the initial response was incorrect, the answer is inverted (changed from true to false, or vice versa). b) If there is mismatch in the input sequence definition, the system revises its additional prompt based the teacher's analysis and re-evaluates the query. This verification step significantly enhances the reliability of the system's outputs. By ensuring that each membership query's 's response is not only generated but also rigorously checked, the LLMs minimize errors and align their outputs closely with accurate interpretations of the language rules.
A.5.4 DISCRIMINATION PROMPT
The idea behind the Discrimination Prompt that L.MSs perform better with examples compared to direct inference. However, handling the large volume of membership queries necessary for learn- ing an automaton is challenging, particularly when it is impractical to present all cached queries to LLMs. That is, we have to find the most similar ones prompt LLMs. Intuitively, words that appear similar should share properties within the same language, but this is not universally applicable. See the example in figure Consider an automaton in (a), for membership query the word (abbbbb), among the cached queries in (c). The (bb6b66) appears more similar due to a lower edit distance. Yet, prompting L.MMs with (bbbbbb) might lead them to incorrectly infer non-membership, mirroring its
19

---

Published as a conference paper at ICLR 2026
Figure 8: Discrimination prompt running example: (a) target automaton that only accepts the string starting with a. (b) The corresponding discrimination tree to the target DFA. The leaves are states in the automaton. The inner nodes represent the discriminator that makes the states left and right side different. (c) The edit distance between the new query and the cached queries.
Cached Queries
Edit Distance
New Query
True
b False
ababbb ?
bbbbbb False
(a)
(b)
(c)
Algorithm 2: Find Similar Counterexamples by Discrimination Tree
Procedure HistoryOracle (C, q):
q E CEo then
return Ceolal
else return False
Represent HistoryOracle by OH
Procedure
www.siieeeeeeeeeerarere... (q)
Construct the hypothesis H. via any active learner by OH
Build the discrimination tree DT based on H.
10
Find the lowest common ancestor of H[q] and another child of d Use Levenshtein Distance L to estimate similarity between words
11
12
Initialize 14 +- 00, 1, + 00 for each query q: C do
13
14
if H[[9.] = Hl[g] and L(g:, 9) < lg then 1g T(g:.q)
W1y qa
else if H(q = H(s) and L(g. g) < 1 then
17
L(g. ④)
W. - g
20
return Wgg W
negative example. Conversely, using (a) prompt highlights that valid strings should start with "a', though it might not instill confidence due to significant differences from the query word.
To address these challenges, we implement the Discrimination prompt, which maintains a dis- crimination tree in (b) to remember the EQs and their relationships. Upon receiving a new mem- bership query, the algorithm identifies the query's 's position within the tree-specifiically, which leaf' (state) the new word belongs to. It then proceeds to the lowest common ancestor of that leaf and selects the most similar word by edit distance from each child of that ancestor. Words on the same leaf share the same state in the hypothesized automaton, while words adjacent leave (sub-treee diverge in their outputs upon receiving identical inputs. this case, both the (a) and (bbbbób) will be chosen to prompt L.Mss. A more detailed process be found in algorithm This method
20

---

Published as a conference paper at ICLR 2026
Figure 9: The Code-based Oracle
CODE-BASED ORACLE
LLM
der is.accepted_vy by. (verd: Tuple)
-- bool
DFA Desoription
languge
words thesquence:
The alalobet consiets T
retur (word) and ward[-2:] (b))
ensures that selected queries not only exhibit similarity in terms of edit distance but also align in their properties, thereby teaching the LLM what is permissible and what is not in the language.
A.5.5 CODE-BASED ORACLE PROMPT
While current LLMs demonstrate impressive capabilities, they often struggle with consistency, lead- ing instability in MQ responses. Specifically, LLMs may provide contradictory answers queries involving the same concept. However, LLMs excel at translating natural language into precise pro- gramming logic. Leveraging this strength, we propose code-basee oracle: instead of relying on direct LLM answers to MQs, use the LLM to generate a Boolean function that formally encodes intended concept or domain knowledge. This function acts as deterministic existence oracle, evaluating whether given word satisfies the desired property.
Figure provides a concrete illustration of how the code- base- oracle operates. Given DFA de- scription and its alphabet, the LLM synthesizes Python function that determines whether word accepted by the target language. This function encodes the concept in executable logic, serving deterministic oracle. For example, if the DFA accepts words ending with the sequence ( ('a', 'b') ) the LLM generates a function that checks for this property explicitly. By converting natural language into stable, verifiable form, the code-based oracle mitigates the inconsistency commonly observed in direct LLM responses.
To demonstrate the advantages of the code- based oracle direct LLM querying, compared its performance with several standard prompting approaches. Additionally, we introduced two novel prompting methods (see Appendix and that improve the LLM MQ answering accuracy and evaluated them alongside the code-base based oracle. We compare the code-oracle with 3 prompting- based oracles to prove the necessity of code-based oracle. These comparisons are detailed in the evaluation section.
A.6 DFA LEARNING EXAMPLES
Figure 10: Simple-01: A DFA language of words containing an even number a's. The alphabet is ['a', 'b']. The empty word is represented by O)
21

---

Published as a conference paper at ICLR 2026
Figure 11: Simple-03: A DFA language of words that end with ('a", 'b'). The alphabet is "b". The empty word represented by
Figure 12: Simple-05: A DFA language of words containing Caa', 'a", 'b', 'a'). The alphabet is ['a', "b'J. The empty word is O)
Figure 13: Normal-01: A DFA language of words with at least three a's and two b's. The alphabet
I'a", "b']. The empty word is ()
22

---

Published as a conference paper at ICLR 2026
Figure 14: Normal-03: A DFA language of words with an even number of a's and one or two b's. The alphabet is ['a', 'b']. The empty word is O)
Figure 15: Normal-05: A DFA language of words starting with and having one b. The alphabet is ['a', 'b']. The empty word is ().
Figure 16: Difficult-03: A DFA language excluding the substrings ('a', 'b') and ('b', 'a'). The alphabet is ['a', 'b']. The empty word is ()
Figure 17: Difficult-09: A DFA language of words of length or more, where the third symbol is an The alphabet is ['a', 'b']. The empty word is ().
23

---

Published as a conference paper at ICLR 2026
Figure 18: Difficult-12: A DFA language of binary numbers (['O', 'I'I) that are multiples of 3. The empty word is O.
24


Reviews:
[{"review_id": "6h0y5stPJp", "reviewer": "Reviewer_1zKR", "summary": "This work considers the problem of learning a deterministic finite automaton from a natural language derived oracle. Specifically, an LLM as a membership oracle to answer yes/no questions about a natural language description of a formal language. This can either be done by answering questions one at a time or converting the description into code, e.g., python. A fundamental problem is that the LLM may make systematic errors in labeling queries. This can result in learning arbitrarily incorrect languages. This is classically addressed by the LEARNANYWAY algorithm, however requires small counterexamples to be made practical. This however is typically not the case as counterexamples are often found via formal analysis or random search/conformance testing.\n\nThe contribution of this work is CAPAL algorithm which seems to perform fairly efficiently even in the presence of labeling errors. The key assumption, called pMAT, is that in addition to a natural language membership oracle (with the possibly to err) there is a perfect counter example oracle. The algorithm is relies on a combination of statistical tests and clever usage of a discrimiation tree, ala Kearns and Vazirani.", "questions": "See weakness #3.\n\nAlso, do you have a sense how this would compare against SAT based approaches allowing for up to `k` labels being flipped (where `k` is derived from the noise floor?) Presumably, this is more scalable, but on the hand works like L*LM showed that creating distinguishing sequences of the smallest consistent DFAs resulted in less hallucination opportunities.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The idea of extracting formal structure from natural language is timely and important. While easy to generate such things in an ad-hoc manner, e.g., code gen, this and related work help provide rigor and guarantees to such procedures. The focus on DFAs is interesting as it is the simplest structure that allows for memory, being the target of decades of learning research.\n\nThe techniques are as far as I know novel, and the framing of pMAT makes the underlying assumptions and limitations fairly clear. While clearly strong, see weaknesses, it allows for progress made in understanding this problem.", "weaknesses": "1. The primary weakness of this approach is the very strong assumption of an equivalence oracle. While there are a few settings this might make sense, e.g., when an (expensive) verification process exists and is cheap compared to the LLM query required for program translation, it obviously not typically available. In such settings conformance testing and random sampling are much more common, typically yielding PAC like guarantees. This seems like a natural next step, and is explicitly acknowledged in the discussion.\n\n2. Another minor writing point is that, in exposition, this paper leans heavily on existing knowledge of automata learning. While not strictly required, I think without a fairly good automata learning background, a reader will likely bounce off of this work. This is particularly likely with much ICLR community. Nevertheless, I think the paper is understandable.\n\n3. Finally, a quick nit pick about exposition with the L*LM related work. My understanding is that the demonstrations only come into play as a mechanism for refining the language *after* an automata has been guessed using a classic learning algorithm. One should able to drop in CAPAL directly into the L*LM framework and still leverage the demonstration modality right?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zF3m2KUfdt", "reviewer": "Reviewer_A92o", "summary": "This paper studies active learning of regular languages with membership queries and equivalence queries.This problem regained recent interest due to the usage of LLMs in converting high-level description of regular languages to a deterministic automata, where LLM can serve as an oracle in answering these two types of queries. The paper assumes that responses to membership queries can have persistent noise, while the response to equivalence queries are noiseless. The paper proposes CAPAL algorithm and establishes its correctness guarantees. Experiments show that the proposed algorithm has lower number of queries and a better learning accuracy.", "questions": "See questions above.  Also, can the authors comment on why in Figure 3, CAPAL's success rate is not always 1 for all epsilon?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- I think the problem motivation is interesting. Converting an informal language description to a formal language allows constructing guardrails of agents, ensuring agent's safety and avoiding unintended consequences in a provable way. \n\n- The experimental results look good to me", "weaknesses": "- I am not sure if assuming the equivalence query oracle is noiseless is practical. Such oracle is also implemented using LLM in practice, am I understanding correctly? Then they may hallucinate?\n\n- I wasn't able to follow the presentation of the CAPAL algorithm, perhaps due to me not being an expert in active learning with regular languages. For example, in line 6, how is sa ~ u defined - is it an equivalence relationship defined by the partition in line 5? In line 8, what are the nodes of the decision tree, and what are the splitting criteria for the tree nodes? \n\nAlso, it is mentioned in line 307-308 that the membership answers equals to the true label with probability 1-eta with eta < 1/2 -- is this for all the queries? If so, then this seems to be inconsistent with Definition 3.2 (where it is mentioned that for some query, the mode of the oracle's response distribution disagrees with the truth)? \n\nAlso, is the label flipping probability assumed to be homogeneous across all queries in theoretical analysis? It seems not the case from the empirical result in Figure 2. \n\n- The paper provides some correctness guarantees of the algorithm (Theorem 1 and 2). It relies on some assumption on the knowledge of the safe noise cap \\bar{\\eta}. Can this be known, or estimated? Alg. 1 line 2 proposes to estimate \\hat{\\eta}, but not enough details are given. \n\n- Is there some formal theorem query complexity that can be given? Without that the theory seems incomplete.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8R1avWlKmA", "reviewer": "Reviewer_dPdj", "summary": "The paper introduces a probabilistic framework for learning formal languages from large language models (LLMs) that act as noisy oracles. The authors formalize this setting through probabilistic Minimally Adequate Teachers (pMATs), which can provide incorrect answers to membership queries but always return valid counterexamples for failed equivalence queries. Within this framework, they propose CAPAL (Class-query Active, Persistent-noise-Aware Learning), an algorithm for actively learning deterministic finite automata (DFAs) that remains theoretically correct even when the oracle produces persistent labeling errors. CAPAL extends Angluin’s classic L* algorithm with statistical same-state tests that distinguish language classes under bounded noise, and with a discrimination tree intended to keep the hypothesis compact. The method also estimates the oracle’s noise rate using a lightweight bootstrap procedure that minimizes redundant queries. The authors prove convergence of CAPAL under a perfect equivalence oracle and show empirically that in certain settings the method requires fewer membership queries than existing approaches. More specifically, when applied to datasets such as RegexLib and KB13 the method shows improved robustness in DFA learning from noisy oracles. Overall, the results support the idea that LLMs, despite their fallibility, can serve as useful collaborators for synthesizing verifiable formal models from natural language.", "questions": "No question.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The idea of using LLMs to guide automata learning algorithms is interesting. Their implementation CAPAL provide evidence that  active learning of regular languages can be made robust to persistent membership noise when a perfect equivalence oracle is available. The main approach is to shift from trusting individual MQ labels to issuing a class query that aggregates evidence against a principled noise floor, with early stopping and monotone (negative) caching to avoid re-litigating pairs already shown different.", "weaknesses": "The main problem is that the approach does not work if the equivalence oracle is approximate, and no extension to the approximate case is provided . This is an issue because perfect equivalence oracles are typically expensive, and in practice approximate equivalence oracles are used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "56T9tGjmvL", "reviewer": "Reviewer_6djq", "summary": "This paper tackles the challenge of using Large Language Models (LLMs) to learn formal representations, specifically deterministic finite automata (DFAs). \n\nIt proposes a new learning model called the Probabilistic Minimally Adequate Teacher (pMAT). This framework assumes the LLM acts as a noisy membership query (MQ) oracle but is paired with a perfect equivalence query (EQ) oracle that provides definitive counterexamples to incorrect hypotheses.\n\nThe paper presents CAPAL (Class-query Active, Persistent-noise-Aware Learning), an algorithm designed to learn Deterministic Finite Automata (DFAs) correctly within the pMAT model. Instead of trusting individual noisy answers, CAPAL uses a statistical class query to determine if two prefixes belong to the same state and a discrimination tree to efficiently refine its hypothesis with minimal new queries.\n\nExperiments show that CAPAL significantly outperforms standard active learning algorithms in noisy environments. The study also finds that having the LLM generate a code-based oracle (a deterministic program to answer queries) is far more effective than direct prompting, reducing errors by over 90% and cutting LLM calls to just one per task.", "questions": "1. The paper's entire theoretical and practical framework relies on a perfect, noise-free $O_{EQ}$. How do you expect CAPAL to perform if this oracle is imperfect? For instance, what happens if the $O_{EQ}$ fails to return a counterexample for an incorrect hypothesis (a \"false negative\") or provides a spurious counterexample for a correct one (a \"false positive\")?\n2. The paper states that for label-only counterexamples (where the DFA's structure is correct but a state's acceptance is wrong), the algorithm only escalates by adding all suffixes of c to $E_{core}$ if the exact same counterexample c reappears. What is the specific rationale for this \"repeat-only\" escalation policy?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.  It introduces a novel learning framework (pMAT) and a provably correct algorithm (CAPAL) to solve it. The paper formalizes the problem of \"persistent noise,\" where an LLM is consistently wrong about certain queries, which is a more challenging and practical scenario than random errors. The proposed CAPAL algorithm is specifically designed to be robust to this noise by using a statistical \"class query\" and is backed by a formal proof of convergence, demonstrating its theoretical soundness.\n2.  It provides a solution with the \"code-based oracle.\" The paper's practical finding is that using an LLM a single time to synthesize a deterministic program (a code-based oracle) is far more effective than using it for repeated queries. \n3. The claims are supported by a thorough and rigorous experimental evaluation. The authors validate it extensively against multiple different active and passive learning baselines across multiple benchmarks.", "weaknesses": "1. The entire theoretical guarantee and the practical success of CAPAL hinge on the assumption of a perfect, noise-free Equivalence Query (EQ) oracle that always returns a valid counterexample. This is a limitation, as real-world verifiers (whether human or automated) are often fallible. The paper acknowledges this but does not investigate the consequences. The work could be strengthened by including experiments with an imperfect EQ oracle (e.g., one that fails to find a counterexample with some probability). \n2. The algorithm's strategy for a \"label-only\" counterexample (where a state is simply mislabeled as accepting/rejecting) is to wait for the exact same counterexample to reappear before escalating by adding its suffixes as discriminators . This seems potentially inefficient. A different counterexample that reaches the same mislabeled state would not trigger this escalation, possibly leading to many wasted EQ cycles to fix one incorrect label. The paper would be more convincing if it justified this specific design choice with evidence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4fKljGz2U4", "reviewer": "Reviewer_w6ef", "summary": "The paper studies a new learning theory problem for regular languages, have a noisy membership query (MQ) oracle, but a perfect equivalence query oracle in a L* learning setup. Such noisy MQ oracles could be LLMs, though I am not sure why they are needed for the simple problems studied. The proposed algorithm CAPAL shows high accuracy with fewer calls to the MQ oracle.", "questions": "1. Why is the code based oracle deterministic? In repeated samples from the MQ oracle LLM, we could get different codes and hence even this scenario is stochastic?\n2. I wonder whether the CAPAL algorithm necessarily needs LLMs. What would it look like theoretically and empirically for any other kind of  noisy MQ oracle, other than LLM?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. I like the problem formulation of pMAT and the recognition of persistent errors.\n2. The work studies a variety of prompting strategies and compares them for their effectiveness within membership query oracles. \n3. The code-based oracle is pretty interesting and gives consistently better results.", "weaknesses": "1. My biggest criticism of the paper is in the motivation. I think the abstract and intro could provide more evidence for the utility of the problem studied from the practical perspective, with detailed, concrete examples, especially involving LLMs for membership queries. The abstract doesn't introduce the problem and is hard to follow.\n2. I question whether the assumption of a perfect EQ oracle is realistic. For the experiments, how is the perfect EQ oracle implemented? How would we get a perfect EQ oracle for practical problems?\n3. The main algorithm/contribution, CAPAL's description is pretty dense and hard to follow. Multiple crucial steps are introduced, but there is less background provided to fully understand and appreciate it.\n\nI recommend rejection mainly for the paper's writing, which currently lacks motivation for the problem and its assumptions and is pretty dense. I encourage the authors to simplify the writing, maybe by including some examples, which can make their contributions more accessible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)