- 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
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.
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′∈V satisfies
∣A(w′)−R(w′)∣≤e,
where A 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 M 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 500000 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.