A Causal Study on The Learnability of Formal Languages

Thanks so much for the detailed review! We will digest all the comments over the week and make substantial changes to the presentation in the manuscript. Many of the comments will certainly improve our work.

One initial thought is about your remark “On a related note, the paper claims its counting semiring is novel, but it is essentially the same as a polynomial semiring with 1 variable (except that the convolution gets truncated), which has been well studied. I suppose the two pages of proofs in Appendix C wouldn’t be necessary if you observe that there is a homomorphism from the polynomial into the counting semiring.”

It’s true that we can construct an isomorphism to the polynomial semiring over 1 variable with truncated convolution as the times. And, it’s true the two pages of proof are routine with one exception. That exception is the construction of the Kleene star and an algorithm for it. Goodman (1999) does not deal with the Kleene star. Indeed, deriving the Kleene star was the only non-trivial part of the proof in our eyes. Do you know a reference for the claim that this exists in the literature? We would happily replace the tedious appendix with a citation, but we had to work out the details ourselves so we are working towards a publication that includes it for completeness of the literature.

Thanks! We did some digging. I think the following construction would work. I think the semiring of truncated polynomials is in fact a ring. Here's a sketch of the derivation. Let R[x] be the ring of polynomials. Suppose we want truncated at $N$. For the ring of polynomials, all polynomials with degree > $N$ form an ideal. Call this $I$. Then, we can compute the quotient ring $R[x] / I$. I think this quotient ring is isomorphic to the truncated semiring. This, of course, implies we will get an inverse. We have to push this through.

With respect to your suggestion, it's true that the monic polynomials $a x^{i+1}$ form an ideal and, thus, we could construct $R[x] / x^{i+1}$, but this would not be isomorphic to our truncated ring. I think the above generalization can be made to be pushed through, though.

Do you think this derivation would help the paper? It may be shorter, as you suggest, but it requires more knowledge of algebra. Maybe we could provide both?

Re the Kleene star, I think the provenance semiring is not close enough to what we want. As I understand it, it's very similar to Goodman's derivation semiring. We will keep searching.

EDIT: We actually now think the provenance semiring framework might be general enough to handle our use case. We will keep you posted.

One final question: What would you think an appropriate claim with respect to novelty is?

We are glad you found the work interesting and will address the unclear notation.

1. The majority of the paper is dedicated to developing an extremely general and abstract framework for efficient constrained generation from PFSA. I don't think much is gained by defining the algorithm in terms of a counting semi-ring instead of directly describing the data structure used to track feature counts. More general theory should be put in the appendix. This would also free up space for a deeper analysis of the experimental results.

We agree that the paper is a bit heavy on the abstract and general, and will make some changes to make the experimental section more prominent. We see the general nature of the proposed theory as a strength but we agree that we should make the practical benefits clearer, see for instance our first response to reviewer FMxv. If we had described data structures directly, i.e. only in the context of the experiments it would have been hard to derive the same general results that can be applied to other situations or as easily extended to more complex pattern counting.

2. Modeling complex joint distributions with FSA incurs a large computational overhead, so it's unclear how to apply a technique based on FSA (even with the asymptotic improvements of the new sampling algorithm) to study more complex types of dataset properties or even natural language.

We don’t see the computational overhead of using synthetic data as a tradeoff, the synthetic languages enable us to study properties that we could not study using natural language—since we can’t control the generative process in the same way. Synthetic methods also enable sampling of an arbitrary amount of languages, facilitating more robust analysis, rather than focusing on specific languages. We cite a fair amount of related literature on this topic and will clarify this point in the writing. We do however acknowledge the importance of studying more complex datasets and those inspired by natural language. We see the suggested methodology as a key part of doing this, e.g. by (1) scaling up language complexity using strongly connected components with Tarjans’s (or Kosaraju’s) algorithm, or (2) analyzing properties of natural languages through formal grammars that are defined over parts of them, by converting these to simpler machines the semiring can be used for controlled sampling and analysis of structural properties that relate to natural language.

3. One suggestion would be to contextualize the observed results to explain differences observed between Transformers and LSTMs in other domains (such as natural language).

This is a good suggestion, we will expand on this in the updated version over the coming days.

Thanks for the update in the summary, let us answer your concerns more directly.

Runtime complexities

We describe the complexity of $v^*$, and the use of the fast-fourier theorem, in the appendix in lines 1022-1043. But this should all have been made clearer and fully contextualized as you point out. The cost of the convolution would have been $O(n^2)$ since we do the scalar multiplication $1+2+3 + … + (n+1) = (n+1)(n+2)/2=O(n^2)$ times, but the FFT trick brings this down to $O(n\cdot \text{log})(n)$. Now for the efficiency of the sampling:

(1) Occurrence sampling: We first sample the number of occurrences of the property we target, i.e. how often the property should occur in each of the $K$ strings. We need to do $K$ convolutions each with the cost of a convolution, $n\text{log}(n)$, giving us $K\cdot n\text{log}(n)$. Even if we store the prior result for practical gains this does not improve the big-O.

(2) Property occurrence sampling: We first need to calculate the pathsum (allsum) of all states. The pathsum computation using Lehmann’s algorithm requires $O(|Q|^3)$ operations (since we need to do $|Q|$ iterations in the calculations for $|Q|$ states and max $|Q|$ transitions in a fully connected graph). Then for each of these operations, we need to do the multiplication over a vector of size $n+1$, which we can do in $n \text{log}(n)$ using the FFT approach. So we get $O(|Q|^3n \text{log}(n))$. Then we sample a symbol for each step in the max length, let’s call this $L$, and we have $K$ strings for which we need to do a convolution each so we get $O(KLn\text{log}(n))$. This means the pathsum calculations dominate unless $KL>|Q|^3$.

Also, refer to our response to FMxv about the complexity of the prior approach.

Additional focus on experiments

While the experimental discussion was a bit sparse, our focus was on demonstrating what can be done with controlled targeted sampling using the semiring. We are, however, also adding new experiments, where we demonstrate directly the causal impact of frequencies of symbols on their learnability. We do this by causally sampling under the counting intervention, we then compare the results to an ancestral sampling baseline. We plot the Monte Carlo estimate of the expected decomposed KL for the symbol transitions against the number of occurrences in the training corpus. See https://i.imgur.com/1jfDXPK.png for a plot comparing the two (updated causal graph at https://i.imgur.com/MBpjt0h.png). It shows that the causal interventions indicate the impact of the number of occurrences is overestimated for low occurrences. At the same time, it is underestimated for higher frequencies, compared to relying on standard sampling. This demonstrates how our method can be used to analyze direct causal effects given an intervention on the property count in a PFSA—something that has not been done before to the best of our knowledge. We maintain that the key contribution is the mechanism for controlled sampling, and how it enables causal analysis like the one we just described, not the comparison between RNNs and Transformers as such--we will do our best to clarify this in the manuscript.

Aditional use-cases beyond string feature counts

The semiring and sampling algorithm could also be applied to different settings than analyzing counts of symbols in strings. Is this what you are asking about? That is, as long as the process can be modeled by a probabilistic automaton. Consider for instance, as an example, if one wants to construct a playlist and there are probabilities of what song a person likes given another song, then we might want to constrain the number of songs included by a specific artist, the counting intervention would allow this.

We have also checked the citations you recommend—these are relevant and we’ll incorporate them!

Are you OK with the complexity analysis? We are happy to provide more details and are grateful for any comments or suggestions you think can improve the clarity.

Thanks for the clarifications. Echoing Reviewer H83n's concerns I do think that the writing could be a bit more clear on how exactly the paper's contributions relate to "causality". Based on Section 7 and the rewrite, my understanding is that this paper is arguing for more studies that train LMs on different datasets to study the (causal) effect of the dataset on the trained LM, rather than studying the behavior of a single (pretrained) LM. To that end, the paper's main contribution is a more efficient way to sample datasets with certain constraints from FSAs.

Similar to Reviewer FMxv I think the paper could use additional motivation for why the algorithm represents a major advancement in this line of research. For instance, I think the motivation would be more convincing if the authors could point a number of pressing experiments that are just waiting for an efficiently sampling method. However, in my opinion, the reality is that designing interesting, well-motivated interventions is itself the more salient question (rather than being able to sample from the posterior efficiently).

I have therefore revised my score up to a 5, but will not object if the paper is ultimately accepted.

Given that we are reaching the end of the discussion period, I will leave the following suggestions for the authors for future revisions.

• Lines 37-39 are confusing: "Sampling from formal languages allows us to correlate properties of language with the performance of different architectures", but then none of the citations involve sampling from formal languages, but are rather studies of pretrained LLMs. I think this line is trying to draw the distinction described in my first paragraph (causal studies that train LMs on different datasets vs. observational studies that study a pretrained LM). I might suggest including an explicit example of an observational study to help drive the distinction home.
• I would suggest including wall-clock times for FSA intersection as an additional baseline (to rejection sampling). My main question is whether the included experiments are feasible without the techniques developed in the paper.
• The citation [1] (and possibly its predecessor [2]) should be included in the related works for causal analysis (e.g., line 40).

[1] https://openreview.net/forum?id=98ekcwQqb7

[2] https://proceedings.mlr.press/v235/jin24e.html

As the discussion period is ending soon, we would like to kindly check if our runtime complexity analysis addresses your concerns. We understand that reviewing is a time-consuming process, and we greatly appreciate the effort you’ve already put into evaluating our work. If there are any further questions or clarifications needed, we’d be happy to address them.

Thanks for increasing the score!

Regarding H83n’s concern about causality, we appreciate their acknowledgment that the revision improved clarity. To summarize, our work introduces a method for efficient controlled sampling from PFSAs, enabling systematic interventions to study the causal factors affecting language models' learnability. The derivation of the decomposed KL-divergence provides a direct measure of these effects, marking a key step forward in causal analysis.

Our primary focus is on introducing a methodology for training multiple LMs on diverse datasets to causally analyze the learnability of different architectures. This approach sheds light on what properties specific architectures can learn and generalize. While this work does not extend to causal studies of pre-trained general-purpose models, it establishes a foundation for such investigations in the future, particularly for analyzing in-context learning.

On the significance of our algorithm: we agree that designing well-motivated experiments is important. At the same time, we stress the value of providing the methodological tools to make such experiments feasible. For instance, our method supports Monte Carlo sampling over a family of automata, enabling causal exploration of generalization at scale. Examples include: How does training on strings up to a certain length affect the learnability of longer strings? Or how does training on data from one generative structure transfer to another overlapping structure (e.g., generalizing from 'run' to 'jump')?

We appreciate the feedback on lines 37-39 and the suggestion of additional references; these will be addressed in revision. Lastly, while the complexity of our approach is established, we are actively working to include wall-clock times for FSA intersection as a baseline to further demonstrate feasibility.

Thanks for the thorough review!

1. Further motivation for intervening on the number of transitions:

We agree that this should be clearer. We are primarily interested in research applications where one can control for the properties of the generated corpus directly at sampling time, both to understand what languages are hard to model, but also how the models generalize:

a) In the SCAN paper (Lake and Baroni, 2017) the authors ask if the models generalize from RUN to JUMP. Using the counting semiring we can sample such settings directly without having to hand curate datasets. The same holds for their length splits, we can simply count all symbols and sample strings of target lengths. Here the benefit is a more efficient sampling algorithm and the fact that we can target the patterns of interest directly by how the automata is constructed, without parsing the output afterwards.

b) Borenstein et al., 2024, consider how the global properties of formal languages impact their learnability. Being able to sample directly based on marked transitions enables us to analyze the effect of the local structural properties on the learnability of these languages. We can ask questions such as: what structural properties make it hard to learn this word as we do in our work. That is, the new semiring enables granular controls that allow us to study more complex properties than those based on surface-level properties of the generated strings.

c) We are interested in analyzing generalization from one emitted term (A to B) based on structural similarity. We can directly sample strings to evaluate whether the models are learning to generalize over a given transition in the subgraph. By controlling for the occurrences of B only on the parts of the machine where there is a structural similarity to the parts emitting A, we can ask directly if the model is generalizing from A to B and how much coverage of the shared structure is needed. We don’t see how this could be done another way.

2. Example where being able to increase the maximum count further is beneficial?

If we want to do length-controlled sampling as in the length sampling example above. We can then directly sample strings of longer lengths that would take a far longer time to sample with rejection sampling. This is valuable for analyzing e.g. the generalization capabilities from shorter strings to longer strings.

3. A comparison with existing methods to contextualize the importance of the efficiency gain. Is the n^4 method mentioned the best previously known method?

It's a simple baseline using the fastest standard algorithms we're aware of. The recent MLRegTest paper (https://arxiv.org/abs/2304.07687) is an example that uses a method similar to the baseline we mentioned, to do length-constrained sampling from a DFA. They intersect a DFA with a DFA for the language $\Sigma^n$, and assign weights using topological sort. This suggests that it runs in $O(n^2)$ time (although they don't provide a runtime analysis), their method is specific to unweighted DFAs and does not implement sampling from the true posterior distribution of a PDFA, which is necessary for our experiments. To modify their algorithm to sample from the posterior, we would need to run weight pushing on each intersected DFA, resulting in $O(n^4)$ time.

4. The experimental results in Figure 2 could be better presented. Perhaps additionally including aggregated statistics would be easier to interpret, e.g. plotting the average across the machines with error bars while retaining the current figure in Appendix.

This is a good idea and we will look into updating the figures to better represent the effects.

5. What is the rationale for training RNNs for 4 epochs but Transformers for 10?

We found that the RNNs needed a shorter time to converge, while the Transformers kept improving. Our thinking was that instead of trying to match parameters that can impact the two architectures differently we would get the most out of each setting. We should have made this clearer and we will report the number of epochs taken to converge for each architecture.

6. Why are the occurrences on the plots at irregular values?

Well caught, we found an issue in our code that led to the values not being fixed except for the symbol interventions, you’ll see they are at fixed intervals. This will be addressed.

7. How did you choose the specific numbers for the empirical results?

We choose the highest number of states, symbols, and counts that would fit in memory with a GPU-based implementation. We thought a higher number of states would give rise to more interesting machines. The maximum transition counts chosen exceed those reported for individual symbols as used in Valvoda et al. (2022). In future work, we will use Tarjan’s algorithm for strongly connected components to scale up the analysis to much larger setups.

We’ll also address the citations and figure formatting, thanks!

We appreciate the constructive feedback and answer your questions below:

1. While using a semiring approach to study the counting properties of weighted automata is indeed a classical method in automata theory, there is limited comparison between the proposed method and traditional approaches. A comparison would help clarify the contribution and novelty of this work, positioning it more effectively within the broader research landscape.

This is a valid point we will address. Reviewer FZWr pointed out the term “counting semiring” has been used before, is this what you refer to? Our “counting semiring” differs from it despite the choice of name, which we will change so there is not a conflict. On the other hand, we now recognize the relation to polynomial semirings, see the discussion with FZWr. We will expand on this to better position our work.

2. The use of causality in the current structure appears somewhat extraneous. In this context, causal "interventions" seem equivalent to conditioning rather than introducing true causal effects. Since no causal effects are explicitly evaluated in the experiments, it may improve clarity to describe these interventions simply as conditional operations.

To clarify our point of view: We think of the changes to the generative process as causal interventions on the trained neural networks. This allows us to ask how the model's behavior would change if we modified specific aspects of the language generation process. Even if the do-intervention calculations can sometimes simplify to the conditionals, we still hold that this doesn’t rule out a causal analysis since we are interested in the causal question. We are, however, redrawing the causal graph, the $\Pi$s should not be independent as in the current version, they have a complex joint distribution that leads to backdoor paths, we are fixing this. Could you elaborate on what you mean by “true causal effects”?

3. More information on the sampling process for probabilistic finite-state automata (PFSAs) with 100 states and 10 samples would be helpful, such as the random seed selection process and the composition of final sets across different intervention types.

We use the built-in random number generator in Python to sample the transitions between states, along with Dirichlet sampling (numpy.random.dirichlet) to sample the weights so they sum to 1. This is described in lines 338 and down, but we will try and make this clearer in the paper. Is there something specific about the composition of the resulting datasets that you would like to see made clearer?

4. In line 309, the term "DPFSA" is introduced, prior sections mention only "PFSA". Could you clarify the meaning of "DPFSA"?

Thanks, we will unify this. DPFSA means a deterministic probabilistic finite automaton, i.e. that a given state has at most a single transition that emits a given symbol. Our experiments only consider DPFSAs, we will clarify this in the writing.

The revised paper improved the clarity in the causality part, which increased my rating. I would like to advise the author to address the question 1 in the next version.