acceptodds
Under review as a conference paper at ICLR 2027

Learning Weighted Automata from Recurrent Neural Networks using Hidden-State Partitioning

Abstract

Recurrent neural networks (RNNs) are able to learn complex sequential behaviours, but their hidden-state representations make them difficult to interpret. This paper presents a new method for learning Weighted Finite Automata (WFAs) from RNNs. The method works within the standard active learning framework, where the main challenge is in comparing a hypothesised WFA with an RNN. The key novelty lies in how this comparison is realised, thereby answering equivalence queries. This is achieved through a partitioning of the RNN hidden-state space that is iteratively refined until each partition has been sufficiently explored and has small relative variance. The partitioning guides the search for counterexamples between the RNN and the learned WFA and provides a practical criterion for terminating the algorithm when no significant discrepancy is identified. Theoretical guarantees on the correctness and termination of the extraction procedure are provided under appropriate conditions. An empirical comparison of the approach with existing methods for WFA extraction from RNNs is given, and the experiments show that the proposed method efficiently extracts compact WFAs with high fidelity to the underlying RNN while generally achieving substantially lower extraction times than existing approaches.

Primary area:
learning theory
Keywords:
Weighted finite automata, recurrent neural networks, automata extraction, explainable AI, active learning, hidden-state partitioning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_bAGmOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

#Summary The paper introduces a new algorithm for checking equivalence between a hypothesized weighted finite automaton (WFA) and a recurrent neural network (RNN) as a core contribution. Specifically, the proposed algorithm checks equivalence exhaustively for strings up to a size budget, and guides the equivalence checks towards an underexplored region of the RNN's state space by using break-conditions to stop equivalence checks for partitions that have been explored sufficiently well. The state-partitioning is refined during the equivalence checks based on variance measures. Whenever a string is found that witnesses a difference, the string is returned as a counterexample.

On a higher level, the equivalence checking procedure becomes part of an existing pipeline for learning the WFA from the RNN. Specifically, the paper relies on prior work for constructing a WFA from a basis B that is initially empty, and augmented based on the obtained counterexamples to refine the WFA in a loop until the WFA is either equivalent, or some break-condition is triggered for ensuring termination.

Evaluation

Overall, the proposed method's core idea, splitting the state space of the RNN for checking equivalence is intuitive and may indeed yield good results, the implementation of the idea, however, has shortcomings, both theoretically, and practically.

On a theoretic level, some claims appear to be false (see Question Q1&3), and some other claim's proofs seem to rely on results from other papers - and without precise pointers those claims, the proofs are hard to verify as a reviewer (See Questions Q2&4).

On a practical level, the experiments provide only limited insights into the method's performance. Specifically, the use of only one baseline without discussing whether other baselines are conceivable (Q7), and a narrow comparison on a new synthetic data set (Q10) without highlighting potential tradeoffs between the methods (Q6) makes the experiments less convincing. Furthermore, the discussion of the experimental results lacks depth: The experiments show that increasing the number model complexity (measured by the number of states if the WFA), improves the runtime of all baselines, which is at odds with the expected behavior - but the paper does not dive deeper into explaining the reason for this observation (Q5). Lastly, the source code for reproducing the experiments is not provided, which reduces reproducability.

Taking these points into account, I recommend rejection.

Critical strengths
  • Interesting and challenging problem: The connection between neural networks and symbolic representations is timely and provides many applications in neuro-symbolic reasoning, explainability, and verification.
  • Good writing style: It was easy to read and understand the paper, the authors successfully ensured that the cognitive load on the reviewer was as low as possible.
Critical weaknesses

Major Weaknesses:

  • Some claims and proofs appear false (See questions), making the validity of the contributions unclear.
  • Experimental evaluation is not thorough and leaves open questions (see questions).
  • No source code provided.

Minor Weaknesses/Feedback:

  • The Algorithms are presented as prose in the main body, making them ambiguous. I suggest the pseudocode from the appendix should be placed into the main body, and the prose should only support intuition concisely.
  • The examples (Example 1 and running example) don't add much value to facilitate understanding the Algorithm in this case. Those can be placed to the appendix.
  • Presentation issue: Proof of Proposition 5 itself contains a lemma nested in it, which is proved first within the proof of the proposition. That is a confusing for the reader.
  • The total length of all proofs in the paper is half a page - which could easily fit into the main body as well. (E.g., by reducing the discussion section, or making Intro+Related work more compact).
  • You can use "thm-restate" latex package when restating a theorem, so it does not get a new (different) ID.
Questions for authors

Questions on theory:

Q1: Proof of Proposition 4 (Line 755). Since the partitioning is kept when reconstructing a new WFA, old words that were correct for the old WFA may have become counterexamples for the new WFA - which is at odds with how the proof is constructed here. Can the authors please clarify. If this sentence does not hold, then the stated proposition has no proof at all.

Q2: Proposition 1 (= Proposition 5 in Appendix) line 709, the sentence: "[...] hence adding at least one row in HBi+1 that is not generated by the rows of HBi [...]" needs further justification. It appears that the claim leans on existing results but there is no pointer to literature for the reader to check and verify.

Q3:Proposition 3 seems wrong as written there: if Lmax is infinite, and M is finite, then Algorithm 2 can just keep splitting some partition infinitely often: since partitions are defined over reals, and each split resets the visits, the max cluster visit threshold M may never be reached, thus no termination.

Q4 Proof of Corollary 2 in Line 735: Where does the "fact" come from in the sentence "Minimality comes from the fact that the rank of the Hankel matrix of the rational series computed by R equals the minimum number of states of any WFA realising it"?

Questions on experiments:

Q5: The experiments do not discuss the surprising observation that increasing the number of states Q, drastically reduces runtime. While the fidelity deteriorates, as expected, the runtime reduction seems surprising. See the three rows with |Σ| = 10 in Table 1, where the runtime decreases for all baselines, especially REG with an order of magnitude. Is that an artefact of the experimental setup, or is there a reason why the methods terminate faster for more complex models?

Q6: It is not clear how exactly the REG baseline works, and in which situations the baseline may perform better than the work presented here ("Trade-off" unclear).

Q7: Are other baselines conceivable? If so, why has REG been chosen? In my understanding, all works mentioned in lines 57-67 could serve as potential baselines, is that correct?

Q8: no standard deviations were reported. While I appreciate the statistical significance test for some conclusions in the discussion, it would be better to have standard deviations directly in Table 1, especially when e.g., there is only 3 rows in Table 1 to infer how the number of states may impact the runtime. I suggest rerunning the algorithm for each row several times and reporting standard deviations as well (especially with other random seeds).

Q9: Is there any reason why the source code has not been submitted?

Q10: Why did you not include results on the dataset from the REG paper? Furthermore, what is the motivation for adding 30% zero-entries in your synthetic data?

8 comments
AuthorsOpenReview ↗

Response to Reviewer bAGm - part 1

We thank the reviewer for their careful evaluation of our work and constructive feedback. We have carefully considered the comments and revised the manuscript accordingly. We address the reviewer's concerns and questions below.

Q1: Proof of Proposition 4

We thank the reviewer for identifying the potential issue in the original proof. You are correct that satisfying the error tolerance for an intermediate hypothesis does not guarantee that the same bound holds for the final hypothesis. In the original submission the algorithm revisits all strings at each equivalence check, guaranteeing that the property is satisfied by the output automaton, however, the text in Section 4.1 was inconsistent with this. The algorithm has been revised to ensure consistency with the text and implementation, and the property is now satisfied by lines 17 to 19 of Alg 1.

That is, upon termination, every previously visited string w′∈Vw' \in V satisfies

∣A(w′)−R(w′)∣≤e,|A(w')-R(w')|\leq e,

where AA is the final extracted WFA.

Importantly, the proposition does not claim that every string within a partition satisfies the error tolerance. Rather, it establishes that every final partition contains at least one previously visited representative whose output error is within the specified tolerance.

In addition, Algorithms 1 and 2 have been updated to accurately reflect the equivalence-query and partitioning procedures. Before returning the final WFA, the revised algorithm explicitly rechecks all previously visited strings against the final hypothesis.

If a counterexample is identified during this step, it is handled in the same manner as any other counterexample encountered during the extraction process. The experimental results have been updated accordingly.

Q2: Proposition 1

Proposition 1 follows from an established result in the literature, as presented by Balle and Mohri (2015) and originally established by Bergadano and Varricchio (1996). We have included the corresponding citations in the manuscript to clarify the theoretical foundation of this proposition.

Q3: Proposition 3

We thank the reviewer for identifying this issue. We agree that a finite MM alone does not necessarily guarantee termination. We have therefore removed this condition from Proposition 3 and revised the statement to establish termination under a finite maximum sequence length.

Q4: Corollary 1

This follows from the theorem established by Michel Fliess (1974). We have included the corresponding citation in the revised manuscript.

Q5: Effect of the number of target WFA states on extraction runtime.

We thank the reviewer for highlighting this observation.

The runtime does not monotonically increase or decrease with the number of states. This behaviour can be influenced by the method used for the construction of the training datasets and the behaviour learned by the RNNs.

As noted in the discussion, the structural complexity of the target WFA does not necessarily correspond to the complexity of the behaviour learned by the RNN. Although a WFA with more states may be expected to represent more complex behaviour, the complexity of the function learned by the RNN does not necessarily match that of the target WFA. Thus, the function learned by the RNN may be represented by a lower-dimensional WFA. Consequently, increasing the number of states in the target WFA does not necessarily imply that extracting a WFA from the trained RNN will be more difficult.

The training datasets were generated by systematically enumerating strings in lexicographical order, up to a maximum of 500000500000 strings. As the alphabet size increases, the number of possible strings grows exponentially, resulting in datasets containing a greater proportion of shorter strings. This may influence the complexity of the behaviour learned by the RNNs and, consequently, the difficulty of extraction.

Therefore, the observed runtime reduction should not be interpreted as evidence that more complex WFAs are inherently easier to extract. Rather, the extraction difficulty depends on the learned RNN behaviour, which is not directly characterised by the number of states of the target WFA. We have clarified this limitation in the experimental discussion.

AuthorsOpenReview ↗

Response to Reviewer bAGm - part 2

Q6: REG baseline and the observed trade-off.

REG refers to the regression-based WFA extraction method introduced by Okudono et al. (2019). It employs a regression-based abstraction of the RNN state space to guide equivalence-query exploration and identify counterexamples for refining the extracted WFA.

The main distinction between REG and our proposed HYP method lies in their partitioning and refinement mechanisms. REG uses regression-based abstraction, whereas HYP employs variance-triggered hyperplanes with geometric partitioning.

The trade-off discussed in the paper primarily concerns extraction time and approximation error. Our results indicate that HYP can achieve approximation errors comparable to REG while requiring less extraction time. Thus, the principal advantage of HYP in these settings is its computational efficiency rather than a consistent reduction in approximation error compared with REG.

Q7: Choice of baseline.

We agree that several related methods exist in the literature. However, not all methods discussed in Lines 57--67 address the same extraction setting or provide directly comparable experimental procedures.

For example, the work of Weiss et al. focuses on automata extraction for classification or next-symbol prediction tasks, rather than extracting real-valued WFAs that approximate the numerical outputs of an RNN. Similarly, the work of Balle et al. provides theoretical foundations for spectral WFA learning, but does not establish a directly comparable RNN-to-WFA extraction benchmark for our experimental setting.

We selected REG because it directly addresses the extraction of real-valued WFAs from RNNs using active learning and guided equivalence queries. It therefore provides a directly relevant baseline for evaluating our proposed method under comparable experimental conditions.

Furthermore, Okudono et al. (2019) previously compared REG against breadth-first search (BFS). We acknowledge that additional comparisons with alternative equivalence-query strategies, including BFS under matched query budgets, would provide further insight into the relative computational efficiency of the proposed method.

Q8: Standard deviations and repeated experiments.

We thank the reviewer for this suggestion. Standard deviations have now been included in the appendix of the revised manuscript to provide additional information about the variability of the experimental results.

Q9: Availability of source code.

The source code was not included in the initial submission as the implementation is part of an ongoing research project and is still being developed and prepared for public release. We recognise the importance of reproducibility and intend to make a documented version of the implementation publicly available once it has been finalised. In the meantime, we are willing to provide the current implementation to the reviewers through an appropriate anonymous review mechanism.

Q10: REG dataset and sparsity of transition matrices.

The REG paper does not provide a fixed, publicly available dataset for direct reuse. Instead, it describes an experimental procedure for generating target WFAs, constructing training datasets, and training RNNs.

We considered the experimental setup described by Okudono et al. (2019) to ensure that REG and HYP were evaluated under comparable conditions. In particular, both methods were evaluated using the same generated target models and corresponding trained RNNs within our experimental framework.

The introduction of 30% zero entries in the transition matrices was intended to reduce the density of transitions between states in the randomly generated WFAs. Without this sparsity, randomly generated transition matrices would typically contain nonzero weights for almost every state-to-state transition for each input symbol. By setting a proportion of these weights to zero, we obtain WFAs with fewer nonzero transitions, rather than fully connected transition structures. This allows us to consider randomly generated WFAs with sparser transition structures.

The 30% sparsity level was chosen as a fixed experimental setting to introduce sparse transitions while retaining a substantial proportion of nonzero transition weights.

Thank you for the answers.

I do not see any changes made to the manuscript (9 hours have passed since the comment above). Therefore, my concerns about the soundness of this paper remain.

Specifically, without having access to the updated manuscript, the reference to "Michel Fliess (1974)" (Q4) remains ambiguous because Michel Fliess has two publications in that year; the other references from Q2 that the proofs supposedly lean on contains several results, and it is unclear which one the authors refer to.

The supposed fixes presented in Answers to Q1 and Q3 appear reasonable, but they cannot be confirmed without the updated manuscript.

I thank the authors for the new insights into the experiments section of the paper. However, it remains unclear how these insights will be presented and reflected in the manuscript.

I believe the questions Q6 (explanation of the baseline, potential trade-off), Q7 (selection of baselines), Q10 (justification of the dataset) are important enough to be addressed in the main body of the paper, and not only in this rebuttal.

Lastly, given that the authors admitted that the Algorithm presented in the initial submission indeed deviated from the actual implementation ("The algorithm has been revised to ensure consistency with the text and implementation"), I believe the submission needs more thorough proofreading than what the last day of the rebuttal phase can provide.

Reviewer_45TVOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper deals with the (somewhat niche, but cool) task of extracting symbolic weighted automata from trained RNNs.

Like previous work in this line, it uses the membership queries, equivalence queries and counterexample active learning framework of Angluin.

The paper proposes a novel method for answering equivalence queries ("does this RNN implement this automata") that is based on space partitioning, and which result in comparable results but significantly faster running times from existing methods.

I am familiar with the topic, interested in it and was actively researching it some years ago, but am not actively working in the area now and have not followed the literature since. I therefore do not know if the method is indeed novel (and to what extent) and also do not know if the comparison is to the current state-of-the-art method, though I do remember the comparison class to have been a strong competitor when it came out 6 years ago. The proposed method itself is clearly presented, seems correct as much as I could verify, and makes sense to me.

Overall this is a nice contribution in a somewhat niche topic, which would be a nice addition to the literature.

Critical strengths

The paper is clearly written and easy to follow. This is way beyond all other papers in my batch.

The paper presents an effective technique for implementing equivalence queries for RNNs and WFAs which is significantly (several orders of magnitude) more efficient than previous techniques.

Critical weaknesses
  • The topic is a bit niche. I do not see it as disqualifying, though.

  • I am not familiar with the current literature, so I could not assess novelty and baseline strength. However, this is a weakness of my assessment, not of the work, and I do generally trust the authors that they do not mis-represent their novelty or ignore stronger baselines. I will defer this point to other reviewers.

Questions for authors

Thanks for the clear and interesting paper.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 45TV

We thank the reviewer for their positive assessment of our work and for recognising the clarity of the presentation and the significant improvements in computational efficiency achieved by the proposed equivalence-query procedure.

We appreciate the reviewer's comments regarding the novelty of the approach and the strength of the baseline comparison. Our work builds on the active learning framework for WFA extraction and introduces a variance-based hidden-state partition refinement mechanism for approximating equivalence queries. To the best of our knowledge, this mechanism has not been explored in previous WFA extraction methods.

Regarding the baseline, we compare our approach against the regression-based WFA extraction method proposed by Okudono et al. (2020), which is a closely related approach to extracting WFAs from RNNs. The experimental results demonstrate that our method achieves comparable extraction accuracy while substantially reducing computational time.

We thank the reviewer again for their encouraging feedback and constructive assessment of our contribution.

Reviewer_4ejiOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the computational cost of equivalence queries when actively extracting weighted finite automata (WFAs) from recurrent neural networks (RNNs). It builds on an existing active-learning framework in which membership queries supply the entries of a Hankel matrix, spectral learning constructs a candidate WFA, and counterexamples are used to refine the hypothesis. The main contribution is a new approximate equivalence-query procedure that explores the RNN's hidden-state space through an adaptively refined partition. A partition is split by a hyperplane when adding a newly observed hidden state causes sufficiently large absolute and relative increases in within-partition variance. Per-partition visit limits and a maximum string length restrict further exploration. The authors compare this hyperplane-partitioning approach (HYP) against a regression-based equivalence-query method (REG) using LSTMs trained to approximate randomly generated WFAs. The main experiments report substantial reductions in extraction time while generally maintaining relatively low approximation errors. Additional experiments vary the visit limit, variance thresholds, rank tolerance, hidden-state dimension, and training-data sampling strategy. The paper also presents termination and correctness results under assumptions including exact Hankel rank and, for some results, an RNN computing a rational series. Strengths. The paper studies a well-defined bottleneck in active WFA extraction and develops a relatively lightweight alternative to regression-guided counterexample search. The runtime improvements are substantial across the evaluated synthetic configurations, and the hyperparameter studies help characterize practical accuracy–efficiency trade-offs. Weaknesses. The high-level combination of active WFA learning and iterative hidden-state partitioning was already discussed in cited prior work, leaving the precise novelty of the present algorithm insufficiently distinguished. The experiments do not isolate the benefit of variance-driven partitioning from simpler search and pruning strategies. Moreover, the strongest theoretical results rely on assumptions not used in the experiments, and several details of the pseudocode and proofs need clarification.

Critical strengths
  1. The paper targets a genuine computational bottleneck with a practical alternative to regression-based equivalence queries. Membership queries and Hankel-based spectral learning are established components of active WFA extraction, but searching for counterexamples against an RNN is substantially more difficult. The proposed method uses hidden-state geometry to guide and prune the search without fitting an additional continuous regression model. This is a meaningful algorithmic design choice: the partition serves as an exploration aid rather than defining the extracted WFA's states, which still come from spectral learning. The resulting procedure is relatively simple and directly addresses extraction cost.
  2. The empirical runtime improvement is substantial and consistently demonstrated on the evaluated configurations. Table 1 shows that HYP25 is faster than REG across all ten reported configurations, sometimes by more than two orders of magnitude. For example, in the (alphabet size, target-state count) = (8, 8) configuration, HYP25 takes approximately 3.96 seconds versus 858.53 seconds for REG, with NRMSEs of 1.1% and 0.8%, respectively. Appendix C reports a significant runtime difference (Wilcoxon p=0.002p=0.002) and no statistically significant NRMSE difference (p=0.106p=0.106). Although the latter should not be interpreted as a formal equivalence result, the experiments provide convincing evidence of an attractive empirical speed–accuracy trade-off on these tasks.
  3. The parameter and robustness analyses provide useful evidence about the method's operating regime. The comparisons among M∈5,10,25M\in{5,10,25} reveal the effect of the exploration budget on fidelity and runtime. Appendix D examines the absolute variance threshold τ\tau, relative variance threshold vv, and Hankel rank tolerance tt; notably, Table 5 shows that setting t=0t=0 can cause severe numerical or approximation problems despite its role in the idealized theoretical analysis. Section 5.3 additionally tests 50-dimensional hidden states and two training-sequence sampling strategies. These experiments go beyond reporting a single favorable result and expose important practical trade-offs.
Critical weaknesses
  1. The paper does not sufficiently separate its algorithmic novelty from the prior partitioning-based WFA extraction framework. The paper cites Wickramasinghe et al. (2025), Extracting Weighted Finite Automata from RNNs via Iterative Partitioning and Spectral Learning, which already identifies iterative hidden-state abstraction as a way to support active WFA learning. It also cites work on hyperplane partitioning for DFA extraction. Thus, the broad idea of combining active learning, hidden-state partitioning, and spectral construction should not itself be presented as a new conceptual framework. The present paper appears to contribute a concrete variance-triggered splitting rule, visit-based pruning procedure, and empirical validation. These are legitimate advances, but Section 2 and the contribution statements do not clearly establish which aspects are new relative to the earlier proposal, nor why the specific splitting and pruning decisions are preferable to alternative implementations.
  2. The evaluation demonstrates speed but does not adequately establish the unique value or behavioral reliability of the partitioning mechanism. Table 1 provides a strong comparison against the regression-based REG method, but there is no direct ablation against simpler equivalence-query searches using the same RNN-evaluation budget, such as breadth-first exploration with visit/length limits, random or fixed partitions, or another inexpensive splitting criterion. As a result, it is unclear how much of the gain comes specifically from the proposed variance-driven hyperplanes rather than from pruning the search earlier. The hidden-state coverage experiment in Section 5.3 measures coverage of geometric reference clusters, not whether the explored strings detect most regions of large WFA–RNN output discrepancy. Finally, the experiments use LSTMs trained on synthetic WFA-generated data and evaluate strings of limited length; they do not establish reliability for less structured target functions or longer unseen sequences. These limitations do not invalidate the reported synthetic results, but they restrict the scope of the broader claims.
  3. The theoretical guarantees and algorithm specification are not yet fully aligned with the implemented, finite-budget procedure. The strongest guarantees in Section 4.2 assume that the RNN computes a rational series and that the rank tolerance is t=0t=0, while practical experiments use t=0.01t=0.01 and finite search limits. Proposition 2 requires M=Lmax⁡=∞M=L_{\max}=\infty and does not ensure finite-time termination under those settings. Proposition 4 only states that each final partition contains at least one string with output error at most ee; it does not bound the error of other strings in that partition. Its proof also appears to assume that previously accepted strings remain accurate for the final WFA, even though the WFA hypothesis changes after counterexamples. In addition, Section 4.1 describes continuing the search frontier between equivalence queries, whereas Algorithm 2 resets the queue on each call; the partition-update pseudocode leaves some state-maintenance operations implicit. These issues should be resolved before the theoretical and practical guarantees can be interpreted confidently.
Questions for authors
  1. Regarding the contribution beyond earlier iterative-partitioning methods. What are the exact conceptual and algorithmic differences between the proposed method and Wickramasinghe et al. (2025)? In particular, which components of the equivalence-query procedure were already proposed, and which are developed for the first time in the current paper? Why were variance-triggered hyperplane splitting and visit-based pruning selected over alternative partitioning criteria? Could the authors state the novelty claims in terms of these specific advances rather than the overall combination of active WFA learning and hidden-state partitioning?
  2. Regarding the necessity and reliability of the proposed search mechanism. Can the authors compare HYP against simpler equivalence-query baselines under matched RNN-query budgets, including a non-partitioned search and a fixed or random partitioning strategy? How often does the visit-based pruning rule cause the algorithm to miss strings whose WFA–RNN discrepancy exceeds ee? Beyond geometric k-means cluster coverage, can the authors evaluate the error distribution, worst observed error, or counterexample detection rate on an independent set of strings, especially at lengths not well represented during training or extraction?
  3. Regarding the theoretical results and the exact algorithm being evaluated. Does the implementation preserve the exploration queue and visit counts across successive equivalence queries, as indicated in Section 4.1, or reinitialize them as written in Algorithm 2? How are child partitions intersected with the parent and their previously visited states reassigned? In Proposition 4, why does a state accepted under an earlier WFA hypothesis necessarily remain non-counterexample evidence for the final hypothesis? Finally, which correctness or termination statements remain valid under the practical settings t>0t>0, finite MM, and finite Lmax⁡L_{\max}?
1 comment
AuthorsOpenReview ↗

Response to Reviewer 4eji

We thank the reviewer for their careful evaluation of our work and constructive feedback. We have carefully considered the comments and revised the manuscript accordingly. We address the reviewer's concerns and questions below.

Q1: Contribution beyond earlier iterative-partitioning methods.

We thank the reviewer for the opportunity to clarify the contributions of the present work relative to Wickramasinghe et al. (2025). The earlier work is a preliminary workshop paper that introduces a framework for WFA learning but does not include an implementation of the proposed methods. In contrast, the present work develops and implements an equivalence-query procedure for WFA extraction based on partitioning the RNN hidden-state space, which, to the best of our knowledge, has not been implemented in previous work. Furthermore, the present work provides theoretical analysis and empirical evaluations of the proposed approach, extending the framework into a fully implemented and evaluated extraction methodology.

In particular, the variance-based partition refinement approach is a new contribution of the present work and was not included in Wickramasinghe et al. (2025). While the earlier paper proposed exploring different iterative partitioning strategies, the present work develops and evaluates a concrete variance-based refinement mechanism within the equivalence-query procedure.

Q2: Necessity and reliability of the proposed search mechanism.

Comparison with BFS.

The effectiveness of BFS-based equivalence-query approximation has already been investigated by Okudono et al., who demonstrated that BFS can extract accurate WFAs, particularly when the RNN closely approximates the behaviour of the target WFA. However, BFS systematically explores strings in increasing order of length without using the RNN hidden-state information to guide exploration or identify branches for pruning. Consequently, the exploration queue continues to expand as longer strings are generated, leading to potentially substantial computational costs.

Our approach addresses this limitation by exploiting the RNN's hidden-state space to guide exploration. Hidden-state partitioning and visit-based pruning determine which branches should be explored further and which should be terminated. Combined with a finite maximum sequence length, this guarantees finite termination of the equivalence-query procedure. However, BFS can also be terminated by imposing a fixed exploration budget or maximum sequence length.

Q3: Theoretical results and implementation details.

Persistence of the exploration state.

The implementation preserves the exploration queue and visit counts across successive equivalence queries. These are maintained throughout the extraction process rather than reinitialised for each new WFA hypothesis. The queue is initialised with the empty string ε\varepsilon only when the queue is empty at the beginning of the algorithm. We have revised Algorithm 2 to reflect this behaviour. This behaviour was already implemented in our code but was not correctly reflected in the original pseudocode.

Partition refinement and state reassignment.

The hidden-state partitioning is represented using a decision tree, where each internal node corresponds to a hyperplane-based split. When a partition is refined, the corresponding leaf node is replaced by two child nodes. Consequently, each child partition is geometrically restricted to its parent region, as the new hyperplane is applied only to hidden states reaching that leaf.

Following each refinement, all previously stored hidden states are reclassified using the updated decision tree. The partition assignments and visit counts are then reconstructed to reflect the refined partitioning.

Previously explored words are checked to ensure that they remain within the specified error tolerance for the current WFA hypothesis. This is now explicitly reflected in lines 17–19 of Algorithm 1.

In a practical setting, termination is guaranteed with a finite LmaxL_{max}, Proposition 3. In Proposition 2, the error bound holds for all w∈Vw\in V, where VV is the set of visited words. Proposition 4 holds in a practical setting.

To address the concerns regarding Proposition 4, we have also revised Algorithm 1 to explicitly validate all previously visited strings before returning the final WFA. If a string violates the error tolerance, it is treated as a counterexample, and the extraction process continues. The experimental results have been updated accordingly.

Reviewer_v8iMOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes a new method to extract WFAs from RNNs with real-valued outputs (discreet inputs). The method leverages weighted L* active-learning framework from Balle et al. (2015), particularly proposes to use a partition-based approach that directly operates on the hidden state space of the RNN for the equivalence query. Unlike regression-based method (Okudono et al. (2020)), the proposed method does not rely on fitting of a regression model. Instead it iteratively refine the partition via inference-only approach, significantly increases the efficiency. The paper outlines theoretical guarantees on the correctness and termination of the extraction procedure under strict conditions (rational series). It provides toy examples for experiments to further illustrate its efficiency compared to regression-based method.

Critical strengths
  • The paper has a well-motivated problem. It might feel a bit unrelated to the current research trend, but the equivalence query remains a challenging problem for the L* based method for WFA extractions. Proposing an efficient algorithm is a great step towards interpretating RNN results and could spark new research onto other SSMs such as Mamba.
Critical weaknesses
  • Theory has flaws: Proposition 8 (Proposition 4 in main part) proof states that a hidden state only enters \hat{P} if its string was not a counterexample (Alg. 2 returns at line 6 before adding it), so every stored point is not a counter-example and is a string where |A(w') − R(w')| <= e. However, in Alg. 2, A is actually the currently extracted WFA from line 10 in Alg 1, not the final WFA A as stated in proposition 4, which breaks the proof. Proposition 4 in itself is a bit of an over-claim as there's no assumption on the smoothness of the hidden space nor discussion of the hidden state space of the RNN learned from WFA generatetd data.
  • Experiments are limited to toy examples, with further clarifications needed for making a convincing story (see questions below).
Questions for authors
  • For the experiments, the data is first generated with an underlying WFA, then a two-layers LSTM was trained using the generated data. It feels unclear to what h(w) would be here, is it last layer hidden state, cell state, concatenation of both layers, which subsequently affects the understanding of \tau and v in the experiments.
  • It seems that for each configureation, 10 runs were conducted, and the average was reported for that configuration. Here, standard deviation should also be reported. Especially for the first configuration (2, 3) in Table 1, there seems to be quite some gap between HYP 25 and REG.
  • Also, in table 1, the authors never discussed about this discrepency at (2, 3) compared to other configurations. My guess, from the paper description "The datasets contained 500,000 strings of maximum length 20 generated using systematic enumeration" is that the the strings generated by the alphabet are listed in a shortest-first fashion, and stopping at 500,000. So, effectively, as alphabet size grows, the length of the generated string decreases. When |\Sigma| = 2, the length could go up to 18-19 (2^19 = 524,288), when |\Sigma| = 4, the length would only go up to 9. If this is the case, then the comparable performance can only be achived with short sequences. Another thing that might be happening here is due to the randomly generated WFA, where \alpha_0 and A_\sigma are row-stochastic. This could cause the sequence to reach to a mixing point and the length that takes this mixing to happen is shorter when the number of states is higher, which could cause that numerically the Hankel matrix might have a very low rank (steep Hankel spectrum) even with high |Q|, which in turn results a much simpler task to learn. We see for example for |Q| = 20, average |\hat{Q}| is only 3.7. I think a clarification on this particular row (2, 3) is needed from the authors, together with more detailed description of the sampling process of the generated data as well as Hankel singular values of the target WFAs for all configurations.
  • The effect of partitions. From table 4, it seems that the effect of partitions is quite minimal. For example, for (8, 8), (10, 10) configurations, the performance is similar across different number of partitions. This is odd, but the authors did not seem to comment on this, especially partition is the base of this method.
  • The experiments are performed 10 times and averaged results are reported in Table 1 and Table 2. I'm quite confused why in Table 1, for REG at (15, 15) configuration, |\hat{Q}| is 9.45? |\hat{Q}| needs to be an integer, 9.45*10 = 94.5. How can 10 integers add up to a decimal number? Also, for Table 2, at configuration (5, 8), N_p (number of partitions) are 5.75. Again, 5.75*10 = 57.5 which I'm not sure how this number comes up.
  • The authors mainly examined the extraction error. Another experiment might be interesting to explore is to see how do the learned LSTM and the extracted WFA generalize to unseen sequence length (i.e., compared to the ground truth WFA). Since the target is itself a WFA, the extracted WFA might generalise better than the LSTM to longer strings, where the extraction step could act as a "denoiser" in-between.
2 comments
AuthorsOpenReview ↗

Response to Reviewer v8iM - part 1

We thank the reviewer for their careful evaluation and constructive feedback. We appreciate their time, and we address the theoretical concerns and experimental questions below.

Response to Theoretical Concern Regarding Proposition 4

We thank the reviewer for identifying the potential issue in the original proof. You are correct that satisfying the error tolerance for an intermediate hypothesis does not guarantee that the same bound holds for the final hypothesis. In the original submission, the algorithm revisits all strings at each equivalence check, guaranteeing that the property is satisfied by the output automaton; however, the text in Section 4.1 was inconsistent with this. The algorithm has been revised to ensure consistency with the text and implementation, and the property is now satisfied by lines 17–19 of Algorithm 1.

That is, upon termination, every previously visited string w′∈Vw' \in V satisfies

∣A(w′)−R(w′)∣≤e,|A(w')-R(w')|\leq e,

where AA is the final extracted WFA.

Importantly, the proposition does not claim that every string within a partition satisfies the error tolerance. Rather, it establishes that every final partition contains at least one previously visited representative whose output error is within the specified tolerance (as partition refinement is performed using the visited hidden states).

The additional validation step rechecks all previously visited strings before returning the final WFA. If a counterexample is identified, it is handled in the same manner as any other counterexample encountered during extraction. The experimental results have been updated accordingly.

Q1. Definition of the RNN Hidden State

The partitioning method operates on the hidden-state representation h(w)h(w) obtained after processing the input string ww. In our LSTM implementation, h(w)h(w) corresponds to the final hidden state of the second LSTM layer. This is consistent with previous approaches, including those of Okudono et al. (2020) and Weiss et al. (2019).

Q2. Reporting Standard Deviations

We agree that reporting standard deviations provides a more informative assessment, and we have added a new table (appendix Table 3 of the updated manuscript) reporting the mean and standard deviation of the error metrics.

Q3. Dataset Generation, Hankel Spectrum, and the Discrepancy at (∣Σ∣,∣Q∣)=(2,3)(|\Sigma|,|Q|)=(2,3)

The training datasets were generated by systematically enumerating strings in lexicographical order, up to a maximum of 500,000500{,}000 strings. As the alphabet size increases, the number of possible strings grows exponentially, resulting in datasets dominated by shorter strings. Consequently, RNNs trained with larger alphabets may encounter fewer long sequences, which could influence the complexity of their learned behaviour. However, the low MSE values between the RNNs and the target WFAs indicate that the RNNs have learned to approximate the behaviour of the target WFAs well.

As noted in the discussion section, our experimental results do not establish a direct relationship between the structural complexity of the target WFA used for training and the difficulty of extracting a WFA from the resulting RNN. Therefore, increasing the number of states in the target WFA does not necessarily imply greater extraction difficulty.

Regarding the discrepancy observed for (∣Σ∣,∣Q∣)=(2,3)(|\Sigma|,|Q|)=(2,3), the results exhibit considerable variability across the ten independent runs. As reported in the newly added Table 3 in the appendix, HYP25 achieves an MSE of (7.99±12.64)×10−5.(7.99 \pm 12.64)\times 10^{-5}. The relatively large standard deviation indicates substantial variability in extraction performance for this configuration.

Further examination of the extraction logs suggests that, in some runs, the variance-based refinement conditions are not satisfied, potentially limiting exploration of the RNN hidden-state space and the discovery of additional counterexamples. Since counterexamples are used to update the extracted WFA, this can contribute to the observed variability in extraction accuracy. It should be noted that the experiments were run with fixed hyperparameters, and model-specific parameter selection is identified as a direction for future work in the conclusion.

We also acknowledge the reviewer's observation concerning the potential effect of the target WFA's Hankel spectrum on extraction difficulty. Using the approach described in Laumen (2024), Minimising Q-Weighted Finite Automata over Z, we verified that the Hankel ranks of the target WFAs equal their respective numbers of states. The smaller numbers of states observed in the extracted WFAs may be attributed to the truncation of smaller singular values with t>0t>0 used during spectral learning, together with the permitted approximation error during equivalence checking. However, having full Hankel rank does not rule out the presence of small singular values, which may affect the effective rank and consequently the number of states in the extracted WFAs.

AuthorsOpenReview ↗

Response to Reviewer v8iM - part 2

Q4. Effect of Partitioning

Partitioning primarily supports the equivalence-query procedure by guiding the search through the RNN hidden-state space via partition refinements and providing termination criteria for the exploration. It can influence the extent of state-space exploration, the discovery of counterexamples, and the computational time required.

A larger number of partitions can allow exploration to continue further, potentially leading to the discovery of additional counterexamples and a reduction in extraction error. However, when different partitioning configurations identify sufficiently informative counterexamples, they may produce WFAs with comparable extraction errors despite differences in computational time.

For example, in Table 4, for (∣Σ∣,∣Q∣)=(10,10)(|\Sigma|,|Q|)=(10,10), the number of counterexamples discovered is similar across different partitioning settings, and the resulting MSE values are comparable. However, the time required to discover these counterexamples differs. This may be because, for some models, informative counterexamples may be discovered during the early stages of exploration, before search branches are pruned.

These observations suggest that partitioning primarily controls the extent and computational cost of equivalence-query exploration, rather than necessarily improving the final extraction accuracy.

Q5. Non-integer Average Numbers of Extracted States and Partitions

We thank the reviewer for identifying these inconsistencies. The reported values were typographical errors. These values have been corrected in the revised tables.

Q6. Generalisation to Unseen Sequence Lengths

We thank the reviewer for this suggestion and acknowledge this as an important direction for further experimental investigation. Evaluating the behaviour of both the trained LSTM and the extracted WFA on sequences longer than those encountered during training would provide valuable insight into their respective generalisation capabilities.

One important consideration is the effect of the error tolerance used during extraction. Since the extracted WFA is constructed to approximate the RNN within a specified error tolerance, some discrepancy between their outputs is permitted. Furthermore, truncating smaller singular values during spectral learning introduces additional approximation error. Consequently, the extracted WFA may exhibit a larger discrepancy from the ground-truth WFA than the original RNN, potentially affecting its generalisation performance on longer sequences.

The experimental results presented in the manuscript show that the MSE between the target WFA and the RNN is lower than the MSE between the extracted WFA and the RNN. This suggests that the approximation errors introduced during extraction may also affect performance on unseen sequences, although further evaluation is required to determine whether this trend persists for longer sequences.

Experimental Scope

We acknowledge the reviewer's concern regarding the scope of the experimental evaluation. The experiments were conducted on RNNs trained using data generated from synthetic target WFAs to ensure that the RNNs learn behaviour that can be closely approximated by a WFA. This provides a controlled experimental setting for evaluating the proposed extraction algorithm, allowing us to investigate its fidelity and computational efficiency across different criteria. We acknowledge that this setting does not fully capture the complexity of RNNs trained on real-world sequential data, and extending the evaluation to such models is an important direction for future work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.