Training Neural Networks as Recognizers of Formal Languages

Thank you very much for your positive comments and feedback. We greatly appreciate your suggestions for improving the paper further.

Table 2: decide on a threshold and make results above it visually dissimilar, this will give a better idea of where a model sits on these benchmarks and the hierarchy they’re measured to be in

Thank you for this suggestion; we agree that making the positive results visually distinctive would be useful. We are hesitant to decide on a uniform threshold across languages like Deletang et al. (2023), because a score above 90% accuracy does not necessarily imply success, due to the individual characteristics of each language. For example, as discussed in our results section, on Cycle Navigation, all models top out at about 93% accuracy, but this is because they only learn the format of positive examples and fail to reject strings where the digit at the end is wrong.

One idea would be to simply bold the best score among the three architectures in each row. Would that be helpful?

Missing a more conclusive figure regarding placement of models wrt to their level in the chomsky hierarchy. I know this is a tough ask, since the mapping of these models don’t fit as neatly into the Chomsky hierarchy as Deletang, et. al. 2023 suggest. Perhaps a better visual representation could be figured out.

Thank you for this suggestion also. One idea would be to include a Venn diagram similar to Deletang et al. (2023), and to include each language that an architecture gets 100% accuracy on as a dot in the Venn diagram. We will try to include this if we have space. As you pointed out, we don't expect the architectures to correspond neatly with classes in the Chomsky hierarchy. LSTMs have been shown to recognize non-regular counting languages, and transformers cut unevenly across the Chomsky hierarchy (see the survey by Strobl et al. (2024)). We will include more discussion of this in the results section of our next revision.

Can the length constrained algorithm for DFAs be modified for other automata? I suspect not due to the combinatorial way the paths compose for these other automata, and the infinite nature of the stack, etc.

Yes, it can! It can be applied to any type of automaton that supports a semiring-general "allsum" algorithm that sums over all path weights. This includes pushdown automata (PDAs, corresponding to context-free languages) and embedded pushdown automata (EPDAs, corresponding to mildly context-sensitive languages, equivalent to tree-adjoining grammars, see [1]). Although PDAs can have infinitely many possible stack configurations, we can sum over all of their path weights using dynamic programming, based on a variant of Lang's algorithm [2]. It is similarly possible to do this for EPDAs. We plan to extend what we did for DFAs to PDAs and EPDAs in future work.

[1] K. Vijay-Shanker. "A Study of Tree Adjoining grammars." 1987. Ph.D. thesis, University of Pennsylvania.

[2] Bernard Lang. "Deterministic techniques for efficient non-deterministic parsers." 1974. In Proc. Colloquium on Automata, Languages, and Programming, pages 255–269.

Thank you very much for your review, for your positive remarks, and for pointing out areas where our work can be better contextualized with respect to past work.

The paper overlooks significant existing work on training neural networks for formal language recognition tasks (e.g. [1, 2, 3]). This oversight diminishes the claimed novelty of the proposed experimental setup. The authors should acknowledge and position their work in relation to previous studies.

Thank you for these references. You are correct to point out that there are many prior empirical studies that attempt to train neural networks on formal languages; another example of a highly relevant paper is MLRegTest [4], which we will make more explicit comparisons to in the next revision. Broadly speaking, although there have been a number of past papers that use neural networks for formal language recognition, each paper uses a slightly different methodology, without much empirical justification for the particular choices made. Our work is an attempt to unify this methodology, to extend it to the broadest possible class of languages, to compare different training objectives used in past work, and to spur theoretically sound empirical work in the future. We believe that our work does improve on each of these prior papers in significant ways.

Our work differs from [1] and [3] in the following ways:

1. They only use the next symbol prediction objective (NS) with MSE loss, whereas we experiment with multiple objectives (R, R+LM, R+NS, R+LM+NS). As far as we are aware, our work is the first to compare these different objectives for training recognizers. One of the interesting findings in our work is that using just binary cross-entropy (R) is often just as good as or better than NS, which overturns common wisdom going back to before Gers and Schmidhuber (2001) that using next symbol prediction is necessary. Reference [1] includes a discussion comparing NS to R and LM objectives in Appendix D.1, but we are the first to empirically compare them.
2. They do not do negative sampling. Next symbol prediction does implicitly include negative samples if it requires predicting EOS, but even then, negative examples are restricted to proper prefixes of positive examples. Our negative sampling approach is more general, and it can be used without needing an algorithm for computing the next symbol sets at each timestep. This is useful because for some languages, it might be feasible to write algorithms for positive sampling and membership testing, but much more complicated to compute next symbol sets. In this way, our work enables empirical testing on more languages than before. Negative examples in general are theoretically important for formal language learning (see [5]).
3. Reference [1] only tests regular and counter languages, and reference [3] only tests on Dyck languages, whereas we test languages from both inside and outside those classes.
4. They use simple language-specific algorithms for length-constrained sampling from regular languages, whereas we have proposed an efficient length-constrained sampling technique that works for arbitrary regular languages expressed as DFAs.

Reference [2] only uses a language modeling objective (LM) and does not do negative sampling, and it is specific to the language $a^n b^n c$. As mentioned above, we also compare multiple training objectives and provide a general method for negative sampling. Moreover, in our work, we show that the LM objective is least often the best objective for training recognizers, whereas R is most often the best objective. We will emphasize this in the results section of our next revision.

Reference [4] is more similar to our work than [1-3]. It does both positive and negative sampling, although it is restricted to regular languages expressed as DFAs, whereas our method applies to non-regular languages as well. Their negative sampling technique relies on algorithms that are specific to DFAs, and they only generate adversarial negative examples with edit distance 1. They propose an algorithm for length-constrained sampling from DFAs, but they do not provide a runtime analysis, and it does not sample from the true posterior distribution of the uniformly-weighted PDFA. They sample strings up to length 50, whereas we sample strings up to length 500.

We will be sure to highlight these distinctions in the next revision as space allows.

(Continued in next comment)

Thank you very much for your review and positive feedback.

The authors report aggregated scores over strings of all lengths. It would be interesting to include a discussion on input length v/s performance for different models. Are there tasks where the transformer's performance shows a more exponential/drastic drop with input length?

In early experiments on Marked Reversal, we did not see a trend in accuracy as a function of length, which is why we chose to analyze edit distance instead. We did not examine this for other languages, but we agree that doing so would be interesting, since a common failure mode in the language modeling/transduction setup of Deletang et al. (2023) was for accuracy to decrease dramatically with length. We will analyze this for the other languages and report back with our findings.

Are there tasks where the additional language model loss and the next symbol loss hurt performance? For example, for parity, language model loss can intuitively hurt performance as the token at each step could be randomly selected for each string.

Yes. For Parity, the language modeling term hurts the mean test accuracy of the LSTM but has almost no effect for the transformer (see Table 6). For Even Pairs, next symbol prediction hurts the mean test accuracy of the LSTM, but benefits the RNN, and has little effect on the transformer. We didn't notice a consistent trend across languages or architectures. In general, recognition alone (R) is the most frequent best loss function, followed by next symbol prediction (R+NS). Loss functions that include language modeling (R+LM, R+LM+NS) are least frequently the best. We will add more discussion of the effect of different loss terms to our results section in the next revision.

We'd like to note that language modeling doesn't necessarily hurt performance due to randomness in the language per se; if there is randomness, the language modeling head just needs to learn the optimal distribution over next symbols.

Furthermore, how do the optimal $\lambda$ hyper-parameters behave for different tasks for different models? Are there cases, where the additional losses help one architecture more than others?

We will analyze the $\lambda$ values and get back to you.

Yes, there are cases where additional loss terms help one architecture more than others. For instance, on the language First with the short validation set, the LM loss increases the mean test accuracy for the RNN much more than for the transformer, although the transformer has higher accuracy. It has little effect on the LSTM.

How is 64k parameters and 5 layers decided for the experiments?

This was admittedly a somewhat arbitrary choice. We deliberately kept the number of hyperparameters we swept over very small in order to keep the number of experiments manageable. Using 64k parameters is enough for the RNN to have 79 hidden units, for the LSTM to have 40 hidden units, and for the transformer to have a $d_{model}$ of 32 when the alphabet is binary. These model sizes are comparable with prior work that evaluates NNs on formal languages, where it is typical to use smaller models than one would use for, say, natural language. Using 5 layers seemed like a reasonable compromise between too few and too many layers. A lot of prior work on formal languages uses only 1 layer, so we wanted to use more.

What happens for smaller and wider models?

We had time to run some experiments to answer this question. We trained models with 32k, 64k, and 128k parameters with (R) loss and with the long validation set, and looked at the max test accuracy of 10 runs. In general, we see that there is no difference in accuracy for most architectures on most languages, suggesting that the results are due to inherent properties of the architecture. There are only three notable exceptions where model size does correlate with accuracy:

We had time to generate plots of recognition cross-entropy vs. length for the models with the best test accuracy scores after being trained on the long validation set. In general, we found that cross-entropy did not increase significantly on longer strings for all languages and architectures. This is in contrast to Deletang et al. (2023), who found that many architectures fail catastrophically on longer strings in their language modeling/sequence-to-sequence setup. This difference might partly be because our experimental setup tests expressivity instead of inductive bias, so it is less prone to overfitting on the training length distribution.

Would you be interested in seeing these plots in the next revision?

We have uploaded a revised draft of our paper. In particular, you may be interested in the following changes:

1. We have added plots of cross-entropy vs. length to the appendix, which we discuss in the main text. For some languages, such as Repeat 01 and Dyck-(2, 3), we actually do see a slight upward trend in cross-entropy for the transformer, but it is quite gradual, unlike what is shown in Deletang et al. (2023).
2. We have added a discussion of cases where certain loss terms help and hurt in the Results section, pointing out that LM is detrimental for the LSTM on Parity.

When we have time, before the camera-ready, we will also add the results on smaller and larger models.

Regarding the $\lambda$ values: below is a table of the $\lambda$ values of the best models trained on the long validation set. A value of 0.000 means the corresponding loss term wasn't included. They tend to have pretty high variance for all architectures. It does seem like the transformer favors a range of smaller LM and NS coefficients than the RNN/LSTM. Other than that, we haven't noticed any clear trends.

Thank you very much for your thoughtful review and feedback.

The general method for training neural networks as language recognizers is straightforward and is difficult to see as a substantial contribution (see similarities with e.g. [2]).

We agree that MLRegTest is an important point of comparison -- it's an excellent paper. MLRegTest focuses exclusively on regular languages, and its negative sampling method is specific to regular languages and cannot be readily applied to non-regular languages. In contrast, our method generalizes to any language (including non-regular languages), as long as that language has (1) an algorithm for positive sampling and (2) an algorithm for membership testing. We also provide a simple, general method for generating adversarial negative examples. Reference [2] specifically cited the difficulty of negative sampling as a reason that they did not do language recognition, which ultimately weakened their claims.

The negative sampling method for MLRegTest converts the DFA for the language to a DFA that recognizes the complement of the language, then renormalizes and samples from the complement DFA to generate negative samples. They also generate adversarial examples by composing the DFA with an FST, and they only generate examples with an edit distance of 1. Our perturbation-based negative sampling is an improvement in that it is simpler, faster (since it does not require FST composition), is not restricted to an edit distance of 1, and is not restricted to regular languages.

The algorithm for efficiently sampling from a regular language is described, and the authors state that they use it for sampling training and evaluation instances from the regular languages (class R in Table 1). Since the algorithm is only used to generate data for 25% of the types of languages in this study, the amount of page real estate devoted to it seems disproportionate, particularly since algorithms for sampling from a formal language are not typically showcased in this venue.

A fair point. We will consider ways of making this section more succinct. Although it is currently used only for regular languages, we do believe our length-constrained sampling algorithm is an important contribution, and it requires a fair bit of technical explanation, which is why we devoted so much space to it in the main text. Additionally, this algorithm can be useful for sampling from non-regular languages as it can be extended for other types of automata, which is something we are planning to do in future work.

(Continued in next comment)

Thank you very much for the clarification wrt MLRegTest. I should have caught that a key difference between your work and MLRegTest is the scope of the languages. (It's right there in the title of their paper, after all, but some of the terms they use is unfamiliar to me and I see now they are different types of regular languages.)

With respect to the amount of the paper devoted to the sampling algorithm, I understand that its contribution is substantial. My concern is that most or all of the description of the algorithm is already included in the concurrent work cited on line 196. If that's the case, the paper under review here could benefit from -- as you indicate -- a more succinct treatment of the algorithm and more experimental results and analysis. I do acknowledge the need for some presentation of the algorithm, but the results and analysis sections could be burgeoned to great effect.

Based on author responses, I have increased my rating from 5 to 6. If this paper is accepted, I would like to see more results and analysis thereof in the camera-ready version, and a more succinct treatment of the sampling algorithm.