Recurrent Neural Language Models as Probabilistic Finite-state Automata
Authors: Anej Svete
Ryan Cotterell
Venue: EMNLP 2023 Main (2023)
Keywords: Language Models
Formal Language Theory
Recurrent Neural Networks
Finite-state Automata
Minsky
TL;DR: We show the equivalence of RNN Language models and Probabilistic Finite-state Automata.

Abstract: Studying language models (LMs) in terms of well-understood formalisms allows us to precisely characterize their abilities and limitations.
Previous work has investigated the expressive power of recurrent neural network (RNN) LMs in terms of their capacity to recognize unweighted formal languages.
However, LMs do not describe unweighted formal languages---rather, they define probability distributions over strings.
In this work, we study what classes of such probability distributions RNN LMs can represent,
which allows us to make more direct statements about their capabilities.
We show that simple RNNs are equivalent to a subclass of probabilistic finite-state automata, and can thus model a strict subset of probability distributions expressible by finite-state models.
Furthermore, we study the space complexity of representing finite-state LMs with RNNs.
We show that, to represent an arbitrary deterministic finite-state LM with $N$ states over an alphabet $\Sigma$, an RNN requires $\Omega\left(N |\Sigma|\right)$ neurons.
These results present a first step towards characterizing the classes of distributions RNN LMs can represent and thus help us understand their capabilities and limitations.

Recurrent Neural Language Models as Probabilistic Finite-state Automata
Anej Svete Ryan Cotterell
(asvete, ryan wwwterelll@inf.etteeell ethz.
ETH zürich
Abstract
Probabilistic FSAs
Studying language models (LMs) in terms of well-understood formalisms allows us pre- cisely characterize their abilities and limita- tions. Previous work has investigated the rep- resentational capacity of recurrent neural net- work (RNN) LMs in terms of their capacity to recognize unweighted formal languages. How- ever. LMs do not describe unweighted formal languages- grgguages-rather, they define probability dis- tributions over strings. In this work, we study what classes of such probability distributions RNN LMs can represent, which allows us to make more direct statements about their pabilities. We show that simple RNNs are equivalent to subclass probabilistic finite- state automata, and can thus model strict sub- set of probability distributions expressible by finite-state models. Furthermore, we study the space complexity of representing finite-slate LMs with RNNs. We show that, to represent an arbitrary deterministic finite-state LM with N states over an alphabet Σ, an RNN requires Q (N]E) neurons. These results present a first step towards characterizing the classes of distri- butions RNN LMs can represent and thus help us understand their capabilities and limitations.
Probabilistic finite-state language models
Probabilistic regular grammars
Discrete HMMs
Complexity
Deterministic
Deterministic Probabilistic FSÁS
probabilistic
finite-state
Heaviside Elman RNNs
language models
Efficiently
n-gram LMs
RNN-representahle
finite-state
D(k, m)
language models
Computational models, Examples of languages
Class of languages
Figure I: graphical summary the results. This paper establishes the equivalence between the bolded deterministic probabilistic FSAs and Heaviside Elman RNNs, which both define deterministic probabilistic finite-state languages.'
In other words: What classes of probability distributions over strings can RNNs represent?
Answering this question is essential whenever require formal guarantees of the correctness of the outputs generated by an LM. For example, one might ask language model to solve a math- ematical problem based on a textual description (Shridhar et al., 2023) or ask it to find an optimal solution to an everyday optimization problem (Lin et al., 2021, Fig. 1). If such problems fall outside the representational capacity of the LM, we have grounds to believe that the result provided by the model is correct in the general case. The question also follows long line of work on the linguistic capabilities of LMs, as LMs must be able to implement mechanisms of recognizing specific syntactic structures to generate grammatical sequences (Linzen et al., 2016: Hewitt and Manning, 2019; Jawahar et al., 2019; Liu et al.,
//tptt//githhb. http://gituuuucco/ooooooooo com/rycolab/ weighted-minsky
1 Introduction
We start with few definitions. An alphabet E is finite, non-empty set. A formal language is subset of E's Kleene closure Σa and a language model (LM) p is probability distribution over Σ* LMs have demonstrated utility a variety of NL.P tasks and have recently been proposed as a general model of computation for wide variety of prob- lems requiring (algorithmic) reasoning (Brown et al., 2020; Chen et al., 2021; Hoffmann et al., 2022: Chowdhery al., 2022; Wei al., 2022a.b; Kojima al., 2023; Kim al.. 2023, inter alia). Our paper asks a simple question: How can we characterize the representational capacity an LM based on a recurrent neural network (RNN)?
'D(A, m) refers to the Dyck language of & parenthesis types and nesting of to depth m.

---

2019; Icard, 2020; Manning et al.. 2020; Rogers et al., 2021; Belinkov, 2022, inter alia).
the WFSA is defined. Indyk (1995) showed that general unweighted FSA with N states can be simulated by an RNN with a hidden state of size O [)) We show that this compression does not generalize to the weighted case: Simulating a weighted FSA with an RNN requires Q2 (N) space due to the independence of the individual condi- tional probability distributions defined by the states of the WFSA. Lastly, we also study the asymptotic space complexity with respect to the size of the alphabet, |>] We again find that generally scales linearly with |Σ]. However, we also identify classes of WFSAs, including n-gram LMs, where the space complexity scales logarithmically with [Σ]. These results are schematically presented in Fig. 1.
A natural way of quantifying the representa- tional capacity of computational models is with the class of formal languages they can recognize (Deletang al., 2023). Previous work has connected modern LM architectures such as RNNs (Elman, 1990; Hochreiter and Schmidhuber, 1997: Cho et al., 2014) and transformers (Vaswani et al.. 2017) to formal models of computation such as finite-state automata, counter automata, and Turing machines (e.g.. McCulloch and Pitts, 1943; Kleene, 1956; Siegelmann and Sontag, 1992; Hao et al., 2018; Korsky and Berwick, 2019; Merrill, 2019; Merrill et al.. 2020; Hewitt et al., 2020; Merrill al., 2022: Merrill and Tsilivis, 2022, inter alia). Through this, diverse formal properties of modern LM architectures have been shown, allowing us to draw conclusions on which phenomena of human language they can model and what types of algorithmic reasoning they can carry out.² However, most existing work has focused on the representational capacity of LMs in terms of classi- cal, unweighted, formal languages, which arguably ignores an integral part of an LM: The probabilities assigned to strings. In contrast, in this work, we propose to study LMs by directly characterizing the class of probability distributions they can represent. Concretely, we study the relationship between RNN LMs with the Heaviside activation function H (x) {a > 0) and finite-state LMs, the class of probability distributions that can be represented by weighted finite-state automata (WFSAs). Finite- state LMs form one of the simplest classes of prob- ability distributions over strings (Icard, 2020) and include some well-known instances such as n-gram LMs. We first prove the cquivalence in the represen- tational capacity of deterministic WFSAs and RNN LMs with the Heaviside activation function, where determinism here refers to the determinism in tran- sitioning between states conditioned on the input symbol. To show the equivalence, we generalize the well-known construction of an RNN encoding an unweighted FSA due to Minsky (1954) to the weighted case, which enables us to talk about string probabilities. We then consider the space com- plexity of simulating WFSAs using RNNs. Min- sky's construction encodes an FSA with N states in space (JE)N). i.e. with an RNN with O N) hidden units, where Σ is the alphabet over which "Soe $7 for thorough discussion of relevant work.
2 Finite-state Language Models
Most modern LMs define p (у) as product of conditional probability distributions pt
ly
p
del p (BOS) |
v) p V (1)
where FOS & Σ is a special end of sequence symbol. The EOS symbol enables us to define the probability of string purely based on the conditional distributions." Such models are called locally normalized. We denote Σ del Σ U (ROS). Throughout this paper, we will assume p defines valid probability distribution over Σa, i.e., that p is tight (Du et al., 2023, $4).
Definition 2.1 (Weakly Equivalent). Two LMs and over Σ* are weakly equivalent if P (v) 2 (v) for all y E*.4 Finite-state automata are a tidy and well- understood formalism for describing languages.
Definition 2.2. A sintte-sttaee automaton (FSA) is 5-tuple (E, Q, F, 8) where E is an alphabet, Q a finite set of states, 1, F Q the set of initial and final states, and ō = Q x Σ x Q set of transitions.
We assume that states are identified by integers in Z1Q1 (0....,,Q QQ1 - 1).5 We also adopt a more
Sampling EOS ends the generation of string, which makes EOS analogous to the final weights in WFSA. We make the connection more concrete at the end of this section. "We distinguish two notions of equivalence: weak and strong equivalence. The latter. informally, corresponds to the notion that there is one-to-one correspondence between the sequences of actions performed by p and y to generate any string y E Σ* Naturally, strong equivalence implics weak equivalence.
For a cleaner presentation, we also assume that vectors and matrices are zero-indexed.

---

suggestive notation for transitions by denoting ()) 6 as 9 - d/. We call transitions of the form q " q' y-transitions and define the children the state q as the set {o' By E Σ: q 2 q' 6). FSAs are often augmented with weights.
a 0.6
b/o.1
qu/1
a/0.9
b) b/o.4
92/0.3
b/0.7
Definition 2.3. A real-weighted finite-state au- tomaton (WFSA) A is S-tuple (E, Q, p) where Σ is an alphabet, Q finite set of states, 8 Q Σ I x Q finite set of weighted transi- tions and X. p: Q R the initial and final weight- ing functions.
p(ab"ab")) p )(bb"):
1 0.6 0.1 0.9
0.7
0.3
1.0.1 0.7" 0.3
Figure 2: A weighted finite- state automaton defining a probability distribution over {a, ba,
We denote (4, Mr w. 4') 8 with 9 2/m d' and define T(q w/w () de w, where T(q w/c o) det if there are no g-transitions from q to qe The underlying FSA of a WFSA is the FSA obtained by removing the transition weights and setting ==
final weights are non-negative, and, for all q Q Σ win ofc
Egeq X (q) = 1, W + p (()) =1
The initial weights, and, for any q E Q, the weights of its outgoing transitions and its final weight, form a probability distribution. The final weights in a PFSA play an analogous role to the EOS symbol-they represent the probability of ending a path in q: p(g) corresponds to the probability of ending a string y, P (EOSS y), where is a state arrived at by A after reading y. We will use the acronym DPFSA for the important special case of deterministic PFSA.
{q E Q A (q) * 0} and F = = Q (4) # 0j. Definition 2.4. An FSA A (Σ, FF, is de- and for every (q.8) Q x E.
terministic I|
there is most one q' Q such that q V. q' 8.
A WFSA is deterministic if its underlying FSA is deterministic.
In contrast to unweighted FSAs, not all non- deterministic WFSAs admit a weakly equivalent deterministic one, i.e., they are nen-determinizable
Definition 2.8. A language model p is finite-state (an FSLM) if it can be represented by a PFSA, i.e,, if there exists a PFSA A such that, every y E E", P (v) = (gy).
Definition 2.5. A path π is a se- transitions 9N+1- Its length π is the number of transition in it and its scan (T) the concatenation of the symbols on them. We denote with (IA) the set of all paths in A and with [IAA 3) the set of all paths that scan y e Σ*
quence of consecutive 11/w1
WN/WN,
02.-.-. .N
See Fig. 2 for example of a PFSA defining an FSLM over Σ {a, b). Its support consists of the strings ab"ab" and 66 for n, m E N In general, there can be infinitely many PFSAs that express a given FSLM. However, in the deter- ministic case, there is a unique minimal canonical DPFSA.
The weights of the transitions along a path are multiplicatively combined to form the weight of the path. The weights of all the paths scanning the same string are combined additively to form the weights of that string.
Definition 2.9. Let p be an FSLM. A PFSA A is minimal DPFSA for p if defines the same prob- ability distribution as p and there no weakly equivalent DPFSA with fewer states.
Definition 2.6. The path weight of π E II(A) is w (T)) = (g1) [ [ Wn p ((N++)) The string-
Recurrent Neural Language Models
sum of y E E* A (z) ExEn((A)) (
RNN LMs are LMs whose conditional distri- butions are given by recurrent neural network. We will focus on Elman RNNs (Elman, 1990) they are the easiest analyze and special cases of more common networks, e.g., those based on long short-term memory (LSTMM; Hochreiter and Schmidhuber, 1997) and gated recurrent units (GRUs; Cho et al., 2014).
A class of WFSAs important for defining LMs is probabilistic WFSAs.
Definition 2.7. WFSA A = (Σ,Q,8,A.)) is probabilistic (a PFSA) if all transition, initial, and
"Throughout the text, we use o as placeholder free quantity, in this case, to any weight w e IR. In case there are multiple c's in an expression, they are not tied in any way.

---

Definition 3.1. An Elman RNN (ERNN) R
a (x)
(,,o, U,V. V,V, ho) is an RNN with the follow- ing hidden state recurrence:
h o (Uh-11 Vr(yt) + b):
(2)
where bn is set to some vector in R.. r: - R is the symbol representation function and a is an element-wise nonlinearity. E RD, U E DxD,
Figure 3: The sigmoid and Heaviside functions.
and V DxRR We refer to the dimensionality of the hidden state, D, as the size of the RNN.
Common choices for the nonlinear function in Eq. (2) are the sigmoid function a(x) 1+exp(-2) and the ReLU (x) = max(0, .)) However, the resulting nonlinear interactions of the parameters and the inputs make the analysis of RNN LMs challenging. One fruitful manner to make the analysis tractable making a simplifying assump- tion about a. We focus on a particularly useful simplification, namely the use of the Heaviside activation function.?
1
An RNN R can be used to specify an LM by using the hidden states to define the conditional distributions for Yr given Yct.
FIx and let R. be an RNN. An RNN LM (R, E) is an LM whose condi- tional distributions are defined by projecting Eh; onto the probability simplex f: FRR
Definition 3.2. Let
Σ using some
1
Definition 3.3. The Heaviside function is defined as H1 (x) del 1 0}.
plye
y=u) f (Ehi),.
See Fig. 3 for the graph of the Heaviside function and its continuous approximation, the sigmoid. For cleaner notation, we define the set {0, 1}. Using the Heaviside function, we can define the Heaviside ERNN, the main object of study in the rest of the paper.
We term E the output matrix. The most common choice for is the softmax defined for x E D and d ZD as
exp (Id)
softmax(x), Set
Ed- exp (Iw)
Definition 3.4. Heaviside Elman RNN (HRNN) is an ERNN R = H.
bo) where
An important limitation of the softmax is that it results in distribution with full support for all x E IRD. However, one can achieve probabilities by including extended real numbers Tे _ R {- -0,000): co): Any element with xd = -00 will result in softmax(x),
Equivalence of HRNNs and ESLMs
The hidden states of an HRNN live in BP, and can thus take 2D different values. This invites an in- terpretation of h as the state of an underlying FSA that transitions between states based on the HRNN recurrence, specifying its local conditional distribu- tions with the output matrix E. Similarly, one can also imagine designing HRNN that simulates the transitions of given FSA by appropriately spec- ifying the parameters of the HRNN. We explore this connection formally in this section and present the main technical result of the paper. The central result that characterizes the representational capac- ity HRNN can be informally summarized by the following theorem.
0.
Recently, number of alternatives to the softmax have been proposed. This paper uses the sparsemax function (Martins and Astudillo, 2016), which can output sparse distributions:
sparsemax(x) argmin ||p x
(5)
PCAD11
Importantly, sparsemax(x) for X D
On determinism. Unlike PFSAS, Elman RNNs (and most other popular RNN architectures, such the LSTM and GRU) implement inherently deterministic transitions between internal states. As we show shortly, certain types of Elman RNNs are at most as expressive as deterministic PFSAs, meaning that they can not represent non-determinizable PFSAs.
"While less common now due to its non-differentiaaillty the Heaviside function was the original activation function used in carly wark on urtificial neural networks due to its close analogy to the firing of hrain neurons (McCulloch and Pitts, 1943; Minsky, 1954; Kleene, 1956).

---

Theorem 4.1 (Informal). IRRN LMs are equiva- lent to DPFSAs.
Let n: Q x Σ 201s m: E 21
and 77: Σ - 2 bijections. We use n, m. and to define the one-hot encodings [-] of state-symbol pairs and of the symbols. i.e.,
We split this result into the question of (i) how DPFSAs can simulate HRNN LMs and (ii) how HRNN LMs can simulate DPFSAs.
we assume that [1. yla = 1I {d = n (g. y) and [vla = 1l {d= =d= m (v)3 for q Q and y y E.
4.1 DPFSAs Can Simulate HRNNS
HRNN's hidden states. The hidden state h of R will represent the one-hot encoding of the current state 9: of A at time t together with the symbol y upon reading which A entered 9t- Formally,
Lemma 4.1. For any HRNN LM, there exists a weakly equivalent DPFSA.
The proof closely follows the intuitive con- nection between the 2D possible configurations of the RNN hidden state and the states of the strongly equivalent DPFSA. The outgoing transi- tion weights of state q are simply the conditional probabilities of the transition symbols conditioned on the RNN hidden state represented by 8 This implies that HRNNs are at most as expressive as DPFSAs, and as consequence, strictly less expres- sive as non-deterministic PFSAs. We discuss the implications of this in $6.
h [[q 3t] BIQIE)
(6)
There is small caveat: How do we set the incom- ing symbol of A's initial state q.? As we show later, the symbol yt in h, = [[ yc)] does not affect the subsequent transitions- is only needed to deter- mine the target of the current transition. Therefore. we can set bo = [(2., [[] for any y E Σ.
Encoding the transition function. The idea of defining U, V. and b is for the Elman recurrence to perform, upon reading yi++1, element-wise conjunction between the representations of the chil- dren of q: and the representation of the states A can transition into after reading in 1/+11 from any state. 9 The former is encoded in the recurrence matrix U, which has access to the current hidden state encod- ing qu while the latter is encoded in the input matrix V. which has access to the one-hot representation of yt+1- Conjoining the entries in those two repre- sentations will, due to the determinism of A, result in a single non-zero entry: One representing the state which can be reached from or (1 component) using the symbol y/+1 (2nd component); see Fig. 4. More formally, the recurrence matrix U lives in IB |||[0 Each column U ,,(g,)) represents the children of the state in the sense that the col- umn contains I's at the indices corresponding to the state- symbol pairs (g', such that A transi- tions from q to q' after reading in the symbol y' That is, for 4, q' E Q and y. yf E E, we define
4.2 HRNNS Can Simulate DPFSAs
This section discusses the other direction of The- orem 4.1, showing that general DPFSA can be simulated by an HRNN LM using a variant of the classic theorem originally due to Minsky (1954). We give the theorem a probabilistic twist, making it relevant to language modeling.
Lemma 4.2. Let A = (2, Q, be DPFSA. Then, there exists a weakly equivalent HRNN LM whose RNN is of size [=
We describe the full construction of HRNN LM simulating given DPFSA in the next subsec- tion. The full construction is described to showease the mechanism with which the HRNN can simulate the transitions of given FSA and give intuition on why this might, in general, require a large number of parameters in the HRNN. Many principles and constraints of the simulation are also reused in the discussion of the lower bounds the size of the HRNN required simulate the DPFSA.
4.2.1 Weighted Minsky's Construction
Unigf (nldfs/))laa)) 1I {
{ 1//0 of EE a
(7)
For DPFSA A (E,Q,6, struct an HRNN LM (R, E) with R (E,o,,, U, V, b, ho) defining the same distribu- tion over E". The idea is to simulate the transition function 8 with the Elman recurrence by appropri- ately setting U, V. and b. The transition weights defining the stringsums are represented in E.
P) we con-
Since is free, each column is repeated |t|-immes: Once for every y E E- is why, after entering the next state, the symbol used to enter it, in the case of the initial state, any incoming symbol can be chosen to set hg-
"See Fact A. in Appendix A. for a discussion of how an HRNN can implement the logical AND operation.
"The full proof is presented in Appendix A.

---

a: w
Uh Io
+0+++o0 |
a/'oa
f ((Eh)) =
b: w"
EOS: 0
af W0o
b//w"
s''
Children
g
a//ui
a/'u
af July
thu
9
a-reachable
a/tuf
a/wo
h [
6/to"
h' = [d
[aa--laa [g'
Figure high-level illustration of fragment of an FSA starting at q (encoded in h) and reading the symbol a. The top path disjoins the representations of the children of whereas the bottom path disjoins the representations of states reachable by an a-transition. The Heaviside activation conjoins these two representations into (rightmost fragment). Projecting Eh' results in the vector defining the same prohability distribution the outcoming ares of (red box).
transition function FSA is simulated in Minsky's construction on
The input matrix lives in - and en- codes the information about which states can be reached by which symbols (from any state). The
the transition Q Mt+1/a Vt+1 = EOS. This is easy to achieve by simply en- coding the weights of the outgoing transitions into the n (4t, y1) column, depending on the projec- tion function used. This is especially simple in the case of the sparsemax formulation. By definition, in PFSA, the weights of the outgoing transitions and the final weight of state d form probability distribution over Σ for every a Q. Projecting those values to the probability simplex, therefore, leaves them intact. We can therefore define
yc-1 E E and (4:) if
non-zero entries in the column corresponding to y' Σ correspond to the state-symbol pairs (g' v/) such that o' is reachable with y' from some state:
del 1 {0 1/10 of E
Valgi mf)mm
Lastly, we define the bias as -1 Q which allows the Heaviside function to perform the needed conjunction. The correctness of this process is proved in Appendix A (Lemma A.1).
Emig/nnaa.) [(g 1//w o) if
(p(2)
otherwise
Encoding the transition probabilities. We now turn to the second part of the construction: Encoding the string acceptance weights given by A into the probability distribution defined by R. We present two ways of doing that: Using the standard softmax formulation, where make use of the extended real numbers, and with the sparsemax.
(9)
Projecting the resulting vector Eh, therefore, sults in vector whose entries represent the transi- tion probabilities the symbols E.
In the more standard softmax formulation, we proceed similarly but log the non-zero transition weights. Defining log () -x0, we set
The conditional probabilities assigned by R controlled by the ΣΣ| x [Q] diimesiinal output matrix E. Since h, is a one-hot encoding of the state-symbol pair qt: Vt. the matrix-vector product Eh, simply looks up the values in the (gt. yt)" thh column. After being projected A [ the en- try in the projected vector corresponding to some 3t+1 E should match the probability of yt+1 given that A is the state qt. i.e., the weight on
log log (4)
2//w
if y' E otherwise
Em Em((s))(gs))
(10)
It is easy to see that the entries of the vector softmax(Ehn form the same probability distri- bution the original outgoing transitions out of
q. Over the course of an entire input string, these weights are multiplied as the RNN transitions be-

---

tween different hidden states corresponding to the transitions in the original DPFSA A. The proof can be found in Appendix A (Lemma A.2). This estab- lishes the complete equivalence between HRNN LMs and FSLMs. 10
arbitrary, whereas they are defined by shared parameters (the matrix E) in an HRNN LM.
Theorem 5.1. There exists a class of FSLMs {PQ Q = +t,....,N1 NYNNE .. N with minimal DPFSAs (Aq) such that for every weakly equiv- alent HRNN LM to pq and function f (n) w (n)
5
Lower Bound on the Space Complexity of Simulating PFSAs with RNNs
it holds that D (1Q)).
Note that the linear lower bound holds in the case that the transition matrix of the DPFSA, which corresponds to the output matrix E in the RNN LM, is full-rank. If the transition matrix is low-rank, its possible decomposition into smaller matrices could possibly be carried over to the output matrix of the RNN, reducing the size of the hidden state to the rank of the matrix.
Lemma 4.2 shows that HRNN LMs are at least as expressive as DPFSAs. More precisely, it shows that any DPFSA A = (Σ, Q, 5, X, p) can be simu- lated by an HRNN LM of size O (IQ) [E]) In this section, address the following question: How large does an HRNN LM have be such that it can correctly simulate DPFSA? We study the asymp- totic bounds with respect to the size of the set of states, [Q], as well as the number of symbols, [Σ]
5.2 Asymptotic Bounds in |Σ]
Since each of the input symbols can be encoded in log | bits, one could expect that the linear factor in the size of the alphabet from the constructions above could be reduced to O (log [E). However, again find that such reduction is in general not possible- the set of FSAs presented in Appendix B is an example whose size scales lincarly with |Σ] to be simulated correctly, which implies the following theorem.
5.1 Asymptotic Bounds in [Q]
Intuitively, the 2D configurations of D- dimensional HRNN hidden state could represent 2d states of (DP)FSA, One could therefore hope achieve exponential compression of DPFSA by representing it as an HRNN LM." "I Interestingly, this is not possible in general: Extending work by Dewdney (1977), Indyk (1995) shows that there exist unweighted FSAs which require an HRNN of size & (El)IQ) to be simulated. At the same time, he also shows that any FSA can be simulated by an HRNN of size O (IEWVI@))
family that requires an HRNN
Theorem 5.2. There exists class of FSLMs (Pr Σ (yn....,yN' ,,N), N NJ such that for every weakly equivalent HRNN LM to Ps. and function f (n) E w (n) it holds that f ([E))
We now ask whether the same lower bound can also be achieved when simulating DPFSAs. We find that the answer is negative: There exist DPFSAs which require an HRNN LM of size Q(E[[Q)) to faithfully represent their probability distribution. Since the transition function of the underlying FSA can be simulated more efficiently, the bottleneck comes from the requirement of weak equivalence. Indeed, as the proof of the following theorem shows (Theorem 5.1 in Appendix A), the issue intuitively arises in the fact that, unlike in an HRNN LM, the local probability distributions of the different states in PFSA are completely
Based on the challenges encountered in the ex- ample from Appendix B, we devise simple suffi- cient condition for logarithmic compression with respect to |Σ| to be possible: Namely, that for any pair of states 9, E Q. there is at most a single transition leading from g to q' Importantly, this condition is met by classical n-gram LMs and by the languages studied by Hewitt et al. (2020). This intuitive characterization can be formalized by a property we call log Σ -/-spaarability.
Definition 5.1. An FSA A (E, (2,Q,1,F,8) is log [[|-separable if it is deterministic and, for any pair 9.4' Q, there is at most one symbol y E Σ such that q ". of E 6.
"The full discussion of the result is postponed $6.
"I IIndeed, any DPFSA defined from an RNN as described in the proof of Lemma 4.1 can naturally be exponentially compressed by representing it with an HRNN. However. not DPFSAs As are of this form.
The conditional of log | /c/-sprrrbyll is relatively restrictive condition. To amend that, we introduce simple procedure which, at the expense of enlarging the state space by factor of |Σ], transforms a general deterministic (unweighted) FSA into a | separrabe one. Since this
"hh constructions by Dewdney (1977) and Indyk (1995), which represent any unweighted FSA with a HRNN of size O (p]][ 8) and Ø [>>]/] QQ)
respectively, are reviewed
by Svete and Cotterell (2023).

---

b/0.9
fact that the normalizing constant can be computed means that it can always be re-normalized form a probability distribution over Σ Furthermore, we can draw on the various results on the minimiza- Even if the HRNN LM is not tight a priori, the
a/0.5
0/0.1
q
6/0.1
90/1
9a/1
tion of DPFSAs to reduce the size of the HRNN implementing the LM.
a a/0.5
c/0.9
While Lemma 4.1 focuses on HRNN LMs and shows that they are finite-state, a similar argument could be made for any RNN whose activation func- tions map onto a finite set. This is the case with any RNN running on computer with finite- precision arithmetic-in that sense, all deployed RNN LMs finite-state, albeit with very large state space. In other words, one can view RNNs very com- pact representations of large DPFSAs whose transi- tion functions are represented by the RNN's update function. Furthermore, since the topology and the weights of the implicit DPFSA are determined by the RNN's update function, the DPFSA can be learned very flexibly yet efficiently based on the training data. This is enabled by the sharing of parameters across the entire graph of the DPFSA instead of explicitly parametrizing every possible transition in the DPFSA or by hard-coding the al- lowed transitions as in n-gram LMs.
Figure A non-determinizable PFSA. It assigns the string ab" c the probability A (a 0.5 0.9" -0.1 0.5 - 0.1" 0.9, which can not be expressed as a single term for arbitrary Ngo-
procedure does not apply to weighted automata, it is presented in Appendix C.
6 Discussion
In $4 and $5 we provided the technical results behind the relationship between HRNN LMs and DPFSAs. To put those results in context, we now discuss some of their implications.
6.1 Equivalence of HRNN LMs and DPFSAS
The equivalence between HRNN LMs and DPFSAs based on Lemmas 4.1 and 4.2 allows us establish several constraints on the probability distributions expressible by HRNN LMs. For example, this result shows that HRNNs are at most as expressive as deterministic PFSAs and, therefore, strictly less expressive than general, non-deterministic, PFSAs due to the well-known result that not all non-deterministic PFSAs have a deterministic equivalent (Mohri, 1997). 13 An example of a simple nondetterminizable PFSA, i.e., a PFSA whose distribution cannot be expressed by an HRNN LM, is shown in Fig. 5. 14
A note on the use of the Heaviside function. Minsky's construction uses the Heaviside acti- vation function to implement conjunction. Note that, conveniently, we could also use the more popular ReLU function: A closer look at Minsky's construction shows that the only action performed by the Heaviside function is clipping negative values to O while non-negative values are left intact. 16 Since ReLU behaves the same way on the relevant set of values, it could simply be swapped in for the Hcaviside unit. This simply shows that the convenient binary structure of the Heaviside function does not enhance the representational capacity of the model in any way; as one would expect, ReLU-activated Elman RNN LMs at least expressive as Heaviside-activated ones."" !7
Moreover, connecting HRNN LMs to DPFSAs allows us to draw on results from (weighted) for- mal language theory to manipulate and investigate HRNN LMs. For example, we can apply general re- sults on the tightness of language models based on DPFSAs to HRNN LMs (Du et al., 2023, $5.1). 15
"General PFSAs are, in turn, equivalent probabilistic regular grammars and discrete HMMs (Icard, 2020).
determinized, the number of states the determinized machine can be expo- nential the size the non-deterministic one (Buchsbaum et al., 2000). this sense, non- -en-deterministic PFSAs can be seen as exponentially compressed representations of FSLMs. The compactness of this non-deterministic representation must "undone" using determinization before it can be encoded by an HRNN.
"'Even if den-deterministicc PFSA
of whether the LM forms valid probability distribution over y: which is not necessarily the case for locally normalized LMs such as RNN LMs.
only values that appear during the processing of string are -1, 1. O. and and the is mapped using the Heaviside function.
16 "More precisely,
1s NNote that the same would be more difficult to say for sigmoid- or tanh-activated Elman RNNs.
Innoormllyy the question of tightness concerns the question

---

6.2 Space Complexity of Simulating DPFSAs with HRNN LMs
model is similar to ours. However, rather than considering the probabilistic representational ca- pacity, they consider the flexibility of the update mechanisms of the variants in the sense of their long-term dependencies and the number of values the hidden states can take as function of the string length. Connecting the assumptions of saturated ac- tivations with the results of Peng et al. (2018), they establish hierarchy of different RNN architectures based on whether their update step sinite-state and whether the hidden state can be used to store arbitrary amounts of information. Analogous to our results, they show that Elman RNNs are finite- state while some other variants such as LSTMs are provably more expressive.
Theorems 5.1 and 5.2 establish lower bounds on how efficiently HRNN LMs can represent FSLMs, which are, to the best of our knowledge, the first results characterizing such space complexity. They reveal how the flexible local distributions of indi- vidual states in a PFSA require large number of parameters in the simulating RNN to be matched. This implies that the simple Minsky's construction is in fact asymptotically optimal in the case of PFSAs, even though the transition function of the underlying FSA can be simulated more efficiently. Nonetheless, the fact that RNNs can represent some FSLMs compactly is interesting. The lan- guages studied by Hewitt et al. (2020) and Bhat- tamishra et al. (2020) can be very compactly repre- sented by an HRNN LM and have clear linguistic motivations. Investigating whether other linguis- tically motivated phenomena in human language be efficiently represented by HRNN LMs is an interesting area of future work, as it would yield insights into not only the full representational ca- pacity of these models but also reveal additional inductive biases they use and that can be exploited for more efficient learning and modeling.
In different line of work, Weiss et al. (2019) study the ability to learn a concise DPFSA from given RNN LM. This can be seen as relaxed setting of the proof of Lemma 4.1, where multi- ple hidden states are merged into a single state of the learned DPFSA to keep the representation compact. The work also discusses the advantages of considering deterministic models due to their interpretability and computational efficiency, moti- vating the connection between LMs and DPFSAs. Discussion of some additional (less) related work can be found in Appendix D.
7 Related Work
8 Conclusion
To the best of our knowledge, the only existing connection between RNNs and weighted automata made by Peng al. (2018), where the authors connect the recurrences analogous to Eq. (2) of dif- ferent RNN variants to the process of computing the probability of a string under general PFSA. With this, they are able to show that the hidden states of an RNN can be used to store the prob- ability of the input string, which can be used to upper-bound the representational capacity of spe- cific RNN variants. Importantly, the interpretation of the hidden state is different ours: Rather than tracking the current state of the PFSA, Peng et al. (2018)'s construction stores the distribution over all possible states. While this suggests a way of simulating PFSAs, the translation of the probabili- ties captured in the hidden state to the probability under an RNN LM is not straightforward.
We prove that Heaviside Elman RNNs define the same set of probability distributions over strings as the well-understood class of deterministic proba- bilistic finite-state automata. To do so, we extend Minsky's 's classical construction of an HRNN simu- lating an FSA to the probabilistic case. We show that Minsky's 's construction is in some sense also optimal: Any HRNN representing the same distri- bution as some DPFSA over strings from an alpha- bet Σ will, in general, require hidden states of size at least Ω ( Σ QQ), which is the space complexity of Minsky's construction.
Limitations
This paper aims to provide a.fisst step at understand- ing modern LMs with weighted formal language theory and thus paints incomplete picture of the entire landscape. While the formalization we choose here has been widely adopted in previous work (Minsky, 1954; Dewdney, 1977; Indyk, 1995), the assumptions about the models we make, e.g., binary activations and the simple recurrent
Weiss al. (2018), Merrill (2019) and Merrill al. (2020) consider the representational capacity of saturated RNNs, whose parameters take their limiting values 10 to make the updates to the hidden states discrete. In this sense, their formal

---

steps, are overly restrictive to represent the models used in practice; see also $6 for a discussion on the applicability to more complex models. It is likely that different formalizations of the RNN LM, e.g., those with asymptotic weights (Weiss et al., 2018; Merrill ct al., 2020; Merrill, 2019) would yield different theoretical results. Furthermore, any inclusion of infinite precision would bring RNN LMs much higher up on the Chomsky hierarchy (Siegelmann and Sontag, 1992). Studying more complex RNN models, such as LSTMs, could also yield different results, as LSTMs are known to be in some ways more expressive than simple RNNs (Weiss et al., 2018; Merrill et al., 2020).
Acknowledgements
Ryan Cotterell acknowledges support from the Swiss National Science Foundation (SNSF) part of the "The Forgotten Role of Inductive Bias in Interpretability" project. Anej Svete is supported by the ETH Al Center Doctoral Fellowship. We thank William Merrill for his thorough feedback on a draft of this paper as well as the students of the LLM course at ETH Zürich (263-5354-00L), for carefully reading an early version of this paper as part of their lecture notes.
References
Another important aspect of our analysis is the use of explicit constructions to show the representational capacity of various models. While such constructions show theoretical equivalence, it is unlikely that trained RNN LMs would learn the proposed mechanisms in practice, as they tend to rely on dense representations of the context (Devlin et al., 2019). This makes it more difficult
Yonatan Belinkov. 2022. Probing classifiers: Promises, shortcomings, and advances. Computational Linguis- tics, 48( (127721992.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. On the practical ability of recurrent neural networks to recognize hierarchical languages. In Proceedings of the 28th International Conference on Computational Linguisties. pages 1481-1494, Barcelona, Spain (Online). International Committee on Computational Linguistics.
to use the results to analyze trained models. Rather, our results aim lo provide theoretical upper bounds of what could be learned.
Tom Brown, Benjamin Mann. Nick Ryder, Melanic Subbiah, Jared D. Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss. Gretchen Krueger. Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter. Chris Hesse, Mark Chen, Eric Sigler, Ma- teusz Litwin, Scott Gray. Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language models are few-shot learners. In Ad- vances in Neural Information Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc.
Lastly, we touch upon the applicability of finite-state languages to the analysis of human language. Human language is famously thought not be finite-state (Chomsky, 1957), and while large portions of might be modellable by state machines, such formalisms lack the structure and interpretability of some mechanisms higher on the Chomsky hierarchy. For example, the very simple examples of (bounded) nesting expressible with context-free grammars are relatively awkward to express with finite-state formalisms such as finite-state automata while they are expressible with such formalisms, the implementations lack the conciseness (and thus inductive biases) of the more concise formalisms. On the other hand, some prior work suggests that finding finite-state mechanisms could nonetheless be useful for understanding the inner workings of LMs and human language (Hewitt et al., 2020).
Adam L. Buchsbaum, Raffacle Giancarlo, and Jef- fery R. Westbrook. 2000. On the determinization of weighted finite automata. SIAM Journal on Com- purtin, 3005):1502-1531.
whill
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Ka- plan, Harri Edwards. Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sas- try. Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Paviov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cum- mings, Mathhas Plappert, Fotios Chantzis, Eliza- beth Barnes, Ariel Herbert-Voss. William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang. Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N.
Ethics Statement
The paper provides way to theoretically analyze language models. To the best knowledge of the au- thors, there are no ethical implications of this paper.

---

Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ily Sutskever, and Wojciech Zaremba. 2021. Evaluat- ing large language models trained on code. arXiv preprint arXiv:2107.055
the North American Chapter of the Association for Computational Linguisties: Human Language Tech- nologies, Volume (Long and Short Pupers), pages 4171-4186, Minneapolis, Minnesota. Association for Computational Linguistics.
A. K. Dewdney. 1977. Threshold matrices and the state assignment problem for neural nets. In Proceedings of the 8th SouthEastern Conference Combina- torics, Graph Theory and Computing, pages 227- 245, Baton Rouge. La, USA.
Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, and Kevin Knight. 2018. Recurrent neural net- works weighted language recognizers. In Proceed- ings of the 2018 Conference of the North American Chapter of the Association for Computational Lin- guistics: Human Language Technologies, Volume I (Long Papers), pages 2261-2271, New Orleans, Louisiana. Association for Computational Linguis- tics.
Li Du, Lucas Torroba Hennigen, Tiago Pimentel, Clara Meister, Jason Eisner, and Ryan Cotterell. 2023. A theeorect characterization of tight language models. In Proceedings of the 61 Annual Meet- ing of the Association for Computational Linguistics (Volume Long Papers), pages 9744-9770, Toronto, Canada. Association for Computational Linguistics.
Kyunghyun Cho, Bart van Merriënboer, Dzmitry Bah- danau, and Yoshua Bengio. 2014. On the properties of neural machine translation: Encoder decoder ap- proaches. In Proceedings of SSST-8, Eighth Work- shop on Syntax, Semantics and Structure in Statistical Translation, pages 103-111, Doha, Qatar. Associa- tion for Computational Linguisties.
Jeffrey L. Elman. 1990. Finding structure in time. Cog- nitive Science, 14(2)1179-211
Yiding Hao, William Merrill, Dana Angluin, Robert Frank, Noah Amsel. Andrew Benz, and Simon Mendelsohn. 2018, Context-free transductions with neural stacks. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NIP.. pages 306-315, Brussels, Belgium. Association for Computational Linguistics.
Noam Chomsky. 1957. Syntactic Structures. De Gruyter Mouton, Berlin, Boston.
Aakanksha Chowdhery, Sharan Narang. Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vin- odkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontack Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Mor- cira. Rewon Child, Oleksandr Polozov, Katherine Lee. Zongwei Zhou, Xuezhi Wang. Brennan Sacta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstem, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. 2022. PaLM: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311.
John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, and Christopher D. Manning. 2020. RNNs can generate bounded hierarchical languages with optimal memory. In Proceedings of the 2020 Con- ference on Empirical Methods in Natural Language Processing (EMNLP), pages 1978-2010, Online. As- sociation for Computational Linguistics.
John Hewitt and Christopher D. Manning. 2019. A structural probe for finding syntax in word represen- tations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Tech- nologies, Volume (Long and Short Papers), pages 4129-4138, Minneapolis, Minnesota. Association for Computational Linguistics.
Sepp Hochreiter and J'ürgen Schmidhuber. 1997. Long short-term memory. Neural Computation, 9(8): 1780.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks. Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Si- monyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent Sifre. 2022. Training compute-optimal large language models. arXiv preprint ar3iv:2003.15556.
Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. 2023. Neural networks and the Chomsky hierarchy. In The Eleventh International Conference on Learning Representations.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language under- standing. In Proceedings of the 2019 Conference of
Thomas F. Icard. 2020. Calibrating generative mod- els: The probabilistic Croomsy-SSchtzznneer hierarchy. Journal of Mathematical Psychology. 95:302308

---

P. Indyk. 1995. Optimal simulation of automata by neural nets. In STACS 95, pages 337-348, Berlin, Heidelberg. Springer Berlin Heidelberg.
Warren S. McCulloch and Walter Pitts. 1943. A logical calculus of the ideas immanent in nervous activity. The bulletin of mathematical biophysics, 5(4): 15- 133.
Ganesh Jawahar, Benoît Sagot, and Djamé Seddah. 2019. What does BERT learn about the structure of language? In Proceedings of the 57th Annual Meet- ing of the Association for Computational Linguistics, pages 3651-3657, Florence, Italy. Association for Computational Linguistics.
William Merrill. 2019. Sequential neural networks as automata. In Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges. pages 1-13, Florence. Association for Computational Linguistics.
Geunwoo Kim, Pierre Baldi, and Stephen McAleer. 2023. Language models can solve computer tasks. arXiv preprint arXiv:2303. 17491.
William Merrill, Ashish Sabharwal, and Noah A. Smith, 2022. Saturated transformers constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843-88 856.
S. C. Kleene. 1956. Representation of events in nerve nets and finite automata. In C. E. Shammon and J. Mc- Carthy, editors, Automata Studies. (AM-34), Volume 34, pages 3 3-42. Princeton University Press, Prince- ton.
William Merrill and Nikolaos Tsilivis. 2022. Extract- ing finite automata from RNNs using state merging. arXiv preprint 2rXiv:200.122551
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yu- taka Matsuo, and Yusuke Iwasawa. 2023. Large lan- guage models are zero-shot reasoners, arXiv preprint arXiv:2205.111 11916.
William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. 2020. A formal hierarchy of RNN architectures. ceedings of the 58th Annual Meeting of the Associa- tion for Computational Linguistics, pages 443-459, Online. Association for Computational Linguistics.
Pro-
Samuel A. Korsky and Robert C. Berwick. 2019. On the computational power of RNNs. CoRR, abs/1906.06349.
Marvin Lee Minsky, 1954, Neural Nets and the Brain Model Problem. Ph.D. thesis, Princeton University.
Chu-Cheng Lin, Aaron Jaech, Xin Li. Matthew R. Gormley, and Jason Eisner. 2021. Limitations of autoregressive models and their alternative.. In Pro- ceedings of the 2021 Conference of the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 5147-5173, Online. Association for Computational Linguistics.
Mehryar Mohri. 1997. Finite-state transducers in lan- guage and speech processing, Computational Lin- guistics, 23(2):269-311.
Franz Nowak, Anej Svete. Li Du, and Ryan Cot- terell. 2023. On the representational capacity of recurrent neural language models. arXiv preprint arXiv:2310.12942.
Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. 2016. Assessing the ability LSTMs to learn syntax- sensitive dependencies. Transactions of the Associa- tion for Computational Linguistics, 4:521-535.
Hao Peng. Roy Schwartz, Sam Thomson, and Noah A. Smith, 2018. Rational recurrences. In Proceedings of the 2018 Conference on Empirical Methods in Nat- ural Language Processing, pages 1203-1214 1214, Brus- sels, Belgium. Association for Computational Lin- guistics.
Nelson F. Liu, Matt Gardner, Yonatan Belinkov, Matthew E. Peters, and Noah A. Smith, 2019. Lin- guistic knowledge and transferability of contextual representations. In Proceedings of the 2019 Confer- ence of the North American Chapter of the Associ- ation for Computational Linguistics: Human Lan- guage Technologies, Volume I (Long and Short Pa- pers), pages 1073-1094, Minncapolis, Minnesota. Association for Computational Linguistics.
Anna Rogers, Olga Kovaleva, and Anna Rumshisky. 2021. A primer in BERTology: What we know about how BERT works. Transactions of the Association for Computational Linguistics, 8:842-866.
Kumar Shridhar, Alessandro Stolfo, and Mrinmaya Sachan. 2023. Distilling reasoning capabilities into smaller language models. Findings of the Asso- ciation for Computational Linguistics: ACL 2023, pages 7059-7073, Toronto, Canada. Association for Computational Linguistics.
Christopher D. Manning, Kevin Clark, John Hewitt Urvashi Khandelwal, and Omer Levy. 2020. Emer- gent linguistic structure in artificial neural networks trained by self-supervision. Proceedings of the Na- tional Academy of Sciences, (7046))3004660003
André F. T. Martins and Ramón F. Astudillo. 2016. From softmax to sparsemax: A sparse model of at- tention and multi-label classification. In Proceed- ings of the 33rd International Conference on Interna- tional Conference on Machine Learning- Volume 48 ICML' 16, page 1614-1623.
Hava T. Siegelmann and Eduardo D. Sontag. 1992. On the computational power of neural nets. Proceed- ings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, page 440-449, New York, NY, USA. Association for Computing Machin- ery.

---

Anej Svete and Ryan Cotterell. 2023. Efficiently rep- resenting state automata with recurrent neural networks. arXiv preprint arX1v:2310.05/6/13
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Eukasz Kaiser, and Illia Polosukhin. 2017. Attention all you need. In Advances in Neural Information Pro- cessing Systems, volume 30. Curran Associates, Inc.
Jason Wei, Tay, Rishi Bommasani, Colin Raf- fel, Barret Zoph, Sebastian Borgeaud, Dani Yo- gatama, Maarten Bosma, Denny Zhou, Donald Met- zler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. 2022a. Emergent abilities of large language models. arXiv preprint arXiv:2206.0768.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc V. Lc. and Denny Zhou. 2022b. Chain-of of-thought prompt- ing elicits reasoning in large language models. In Advances in Neural Information Processing Systems, volume 35, pages 044224244835 Curran Associates, Inc.
Gail Weiss, Yoav Goldberg, Eran Yahav. 2018. the practical computational power of finite precision RNNs for language recognition. In Proceedings of the 56th Annual Meeting of Association for Computational Linguistics (Volume 2: Short Papers), pages 740-745, Melbourne, Australia, Association for Computational Linguistics.
Gail Weiss, Yoav Goldberg, and Eran Yahav. 2019. Learning deterministic weighted automata with queries and counterexamples. In Advances in Neural Information Processing Systems, volume Curran Associates, Inc.

---

A Proofs
A.1 Performing the Logical AND with an HRNN
Minsky's construction requires the RNN perform the logical AND operation between specific entries of binary vectors x ε B... The following fact shows how this can easily be performed by an HRNN with appropriately set parameters.
Fact A.1. Consider indices i1, 81;....hm hm ZD and vectors x, v E IB such that v; 1 (i E (61,-.. fm)) ) ie.. with entries at indices i 11 bm Then, H (v x -(m 1)) and only if Fig for all
k 1,.... m. other words,
H (vTx- (m 1)) Fit Tim-
(11)
As special case, 2 in Fact A.l corresponds to the AND operation of two elements, which is used in Minsky's construction. There, the vector corresponds to the weights of single neuron while (m 1)
(-1 in case 2) corresponds to its bias.
We now present the proof' of the lemmas establishing the equivalence of DPFSAs and HRNN LMs.
Lemma 4.1. For any HRNN LM, there exists weakly equivalent DPFSA.
Proof. Let R (,, D, V,V, b, ho) be HRNN defining the locally normalized language model p. We construct weakly equivalent DPFSA (E, Q, X, p). Construct bijection s: IB Σzd. Now, for every state = <h) E Q Z2 construct a transition q s/ww of where of = s(a (Uh + V + b)) with the weight wo = p (y h) = f (E We define the initial function as X (s(h)) 1 [h = ho) and final function P with p (g) def (EOS (q)).. It is easy to see that A defined this way is deterministic.
We now prove that the weights assigned to strings by A and are the same. Define go s(ho) and let y E x with yy| = T. Then, let
91/wn
BT/eT
π
qu
91
9T
91'
(12)
be the path with the scan y and starting in (such a path exists since we the defined automaton is complete-all all possible transitions are defined for all states). Then, it holds that
T
Ag)) (go)
I
p ((r)
T
=1
p
(ye
s +q))) p (EOS)
--r())
1-1
=y
which is exactly the weight assigned to y by R. Note that all paths not starting in s(ha) have weight 0 due to the definition of the initial function.
Lemma A.1. Lei A (E, p) be a deterministic PFSA, = =1... DT E Σ*, and gt the state arrived at by A upon reading the prefix yog Let R be the HRNN specified by the Minsky construction for A. the permutation defining the one-hot representations of state-symbol pairs by R, and h, R's hidden state after reading Ygu- Then, it holds that hg [[g. y)] where q, is the initial state of A and y Σ and hr [(TT, W.
Proof. Define s(h = Ilg. v)1)
We can then restate the lemma as s(hr) qr for all E Σ" yl T. Let π be the y-labeled path in A. We prove the lemma by induction on the string length T.
Base case: T= = 0. Holds by the construction of hp-

---

Inductive step: T O. Let E Σ* with |y/ T and assume that s(hy 1) gr- 1. We prove that the specifications of U, V. and b ensure that s(hr) ęr. By definition of the recurrence matrix U (cf. Eq. (7)), the vector Uhr-1 will contain 1 at the entries n (d', 2/) for o' E Q and y' e such that or s//,, of E 8. This can equivalently be written as UhT
V
[(d's where the
via 9'E6
disjunction is applied element-wise.
On the other hand, by definition of the input matrix V (cf. Eq. (8)), the vector V Virrl will contain
the entries (q', yr) for Q such that Mn/o of 8. This can also be written V[y ((q'.y)).
wrih 9/066 -
By Fact A.I, И (Uhr-1+ V[yrI + b)negr H (Uhy-1 + VIyrTl 1) m holds if and only if (Uhy-1)n(q''' and (Vrrr))
This happens
qr
1// of E and yn/o of e = qT
d.
(13)
i.e., if and only if A transitions from or to or upon reading yr (it transitions only to @r due determin- ism).
Since the string y was arbitrary, this finishes the proof.
Lemma A.2. Let A (Σ, p) be deterministic PFSA, = y1.. .T Σx, and qi the state arrived al by A upon reading the prefix yog Let R be the HRNN specified by the Minsky construction for A, E the output matrix specified by the generalized Minsky construction, the permutation defining the one-hot representations of state-symbol pairs by R, and hg R 's hidden state after reading yst. Then, it holds that p (y) A (g))
Proof. Let y E Σx y T and let æ be the y y-labeled path in A. Again, let p (y) der We prove 7 (y) I wy by induction on T.
11 P yed.
Base case: = 0. In this case, y = E, i.e., the empty string, and A() = 1. R. computes p()) [l (Mt y=t)= = 1.
Inductive step: T > 0. Assume that the (1) ... 9r-1) s(br-1)= qT and s(hr) ęr. By the definition of E for the specific f, it holds that f (Ehr-1)m(y)
IT=i wy By Lemma A. we know that
r(s(hr-) 1) w/rr, s(hr)) wy. This means that p (3Er) I wt. which is what wanted prove.
Clearly, p (v) = p (y) p (EOS) y). By the definition of E (ef. Eq. (9)), (Ehr)m = p (s(hr)), meaning that p (1) = p (3) p (EOS y) = I[ wap (s(br)) A (z). Since Σ" was arbitrary, this finishes the proof.
A note on strong equivalence. The purpose of Lemma A.2 and Lemma 4.1 was to show the existence of weakly equivalent (cf. Definition 2. HRNN LM given DPFSA defining a finite-state LM and vice versa. We keep the discussion in the main part of the paper restricted to weak equivalence for brevity. However, note that the proofs of the lemmas in fact establish the existence of a strongly equivalent DPFSA and HRNN LM, respectively. This can easily be seen from the one-to-one correspondence between path scanning a given string in the DPFSA and the sequence of hidden states generating the same string the HRNN LM. In this sense, the connection between DPFSAs and HRNN LMs is even tighter than just defining the same probability distribution; however, we are mainly interested in the implications of the simpler weak equivalence.
Theorem 5.1. There exists class of FSLMS (po Q (1,...,N].
E N} with minimal DPFSAs {Ao) such that for every weakly equivalent HRNN LM to pa and function of (n) E w (ni) it holds that > f (IQ)).

---

y1 1
y2, UN
2
Figure 6: The FSA Av.
Proof. Without loss of generality, we work with R-valued hidden states. Let A be a minimal deterministic PFSA and R = (E, D, U, V, b, ho) a HRNN with p (y) = A (y) for every
Σ*. Let y=T E Σ and y&T def V-TY for some y E Σ. Define p (y) I T p (ye y-+). It is easy to see that P (y<THr) P (yer)) (Vt (-r). The probabilities in the conditional distribution p y-rr) are determined by the values in Ehy By definition of the deterministic PFSA, there are [Q] such conditional distributions. Moreover, these distributions (represented by vectors A - can generally be linearly independent. This means that for any q, the probability distribution of the outgoing transitions can not be expressed as a linear combination of the probability distributions of other states. To express the probability vectors
for all states, the columns of the output matrix E. therefore, have span I ! implying that E must have least [Q] columns. This means that the total space complexity (and thus the size of the HRNN representing the same distribution as A) is 92 (1Q)..
B Lower Space Bounds in Σ for Simulating Deterministic PFSAs with HRNNS
In this section, we provide a family of DPFSAs which require a HRNN LM whose size must scale linearly with the size of the alphabet. We also provide sketch of the proof of why compression in |X] is not possible. Let AN
(EN. {0. 1), {0), (1), dN) be an FSA over the alphabet ΣN {y,...., such that 8N = {0 f0m1 ( nn, n = 2....N (see Fig. 6).
N
Clearly, to be able to correctly represent all local distributions of the DPFSA, the HRNN LM must contain a reprexentation of each possible state of the DPFSA in unique hidden state. On the other hand, the only way that the HRNN can take into account the information about the current state dt of the simulated FSA A is through the hidden state h, The hidden state, in turn, only interacts with the recurrence matrix U, which does not have access the current input symbol 3t 1- The only interaction between the current state and the input symbol is thus through the addition in Uh + V[ This means that, no matter how the information about şi is encoded in h,, to be able to take into account all possible transitions stemming in 4: (before taking into account y1+1),, Uh, must activate all possible next states, i.e., all children of gt. On the other hand, since V[M++1] does not have precise information about (t. it must activate all states which can be entered with an -t=--transition, just like in Minsky's construction. In Minsky's 's construction, the recognition of the correct next state was done by keeping separate entry (one-dimensional sub-vector) for each possible pair 2++1, V1+1- However, when working with compressed representations of states (e.g., in logarithmic space), a single common sub-vector of size |Σ] (e.g., log| > has to be used for all possible symbols y E Σ. Nonetheless, the interaction between Uh, and V[[ n]] must then ensure that only the correct state : is activated. For example, in Minsky's 's construction, this was done by simply taking the conjunction between the entries corresponding to g, y.y in Uh, and the entries corresponding to g', b/ in V[v]] which were all represented in individual entries of the vectors. On the other hand, in the case of the log encoding, this could intuitively be done by trying to match the log | ones in the representation (p (y) 1 P (v)), where (y) represent the binary encoding of y. If the log Σ ones match (which is checked simply as it would result in large enough sum in the corresponding entry of the matrix- vector product), the correct transition could be chosen (to perform the conjunction from Fact A. correctly, the bias would simply be set to log |Σ] 1). However.
18 For this to he the case, it has to hold that |>] > [Q]-

---

issue arises as soon as multiple dense representations of symbols in Vly have to be activated against the same sub-vector in The only way this can be achieved is if the sub-vector in Uh, contains the disjunction of the representations of all the symbols which should be activated with it. If this sets too many entries in Uh, to one, this can result in "false positives". This is explained in more detail for the DPFSAs in Fig. 6 next.
Let F, represent any dense encoding of yn in the alphabet of Ay (e.g., in the logarithmic case, that would be (p (n)) 1- 1-p (n))). Going from the intuition outlined above, any HRNN simulating Av, the vector Uhg must, among other things, contain a sub-vector corresponding to the states 1 and 2. The sub- vector corresponding the state 2 must activate (through the interaction in the Heaviside function) against any Yn for = ...., N in AN. This means has to match all representations In for all n ........ N.. The only way this can be done if the pattern for recognizing state being entered with any On for n = = ......... .N is of the form r = V In- However, for sufficiently large N, = V n-2 In will be a vector of all ones including all entries active in r1. This means that any encoding of a symbol will be activated against it- it-among others, 5/1 Upon reading in state 1, the network will therefore not be able to deterministically activate only the sub-vector corresponding to the correct state 1. This means that the linear-size encoding of the symbols is, in general. optimal for representing DPFSAs with HRNN LMs.
C Transforming a General Deterministic FSA into a log -separabbee FSA
log Ss-paarrayly is relatively restrictive condition. To amend that, we introduce simple procedure which, at the expense of enlarging the state space by factor of Σ, transforms general deterministic FSA into a log -s--paraebe one. We call this log -se-ppraanooon. Intuitively, it augments the state space by introducing a new state (q: y) for every outgoing transition q "/ of of every state q E Q, such that (g. y) simulates the only state the original state q would transition to upon reading y. Due to the determinism of the original FSA, this results in a log |/-sparrbble FSA with at most [Q||[] states.
While the increase of the state space might seem like step backward, recall that using Indyk's s construction, we can construct an HRNN simulating FSA whose size scales with the square root of the number of states. And, since the resulting FSA is log -eepaaabe,,, we can reduce the space complexity with respect to E to log |_] This is summarized in the following theorem, which characterizes how compactly general deterministic FSAs can be encoded by HRNNs. To our knowledge, this is the tightest bound on simulating general unweighted deterministic FSAs with HRNNs.
Theorem C.1. Let A (E, Q, F,8) be a minimal FSA recognizing the language Then, there exists an HRNN R (E, D, U, V, b, ho) accepting L with D O llog / [MTlo)
The full log |S|-sppaatooon procedure is presented in Algorithm 1. It follows the intuition of creating a separate "target" for each transition q % q' for every state q e Q. To keep the resulting FSA deterministic, a new, artificial, initial state with no incoming transitions is added and connected with the augmented with the children of the original initial state.
The following simple lemmata show the formal correctness of the procedure and show that it results in a log -S-sapaaeb FSA, which we need for compression in the size of the alphabet.
Lemma C.1. For any y e Σ, (q. v) L (g',v/) e 5' if and only if q
3/ q¹ E 8.
Proof. Ensured by the loop on Line 3.
Lemma C.2. log Σ| -l-spparation results in an equivalent FSA.
Proof. We have to show that, for any y Σ*. y leads to a final state in A if and only if y leads to final state in A'. For the string of length 0, this is clear by Lines 13 and 14. For strings of length > 1, it follows from Lemma C.1 that y leads to a state q in A if and only if By E Σ such that y leads to (q. v) in A'. From Lines 11 and 12, (g. y) E F' if and only if q E F, finishing the proof.
Lemma C.3. log Σ -eepparration results in a log seeparabee FSA.
Proof. Since the state (g', v/) is the only state in Q' transitioned to from (g. y) after reading y' (for any y e Σ), it is easy to see that A' is indeed log | -eppaabbe

---

Algorithm 1
def S = (2,
=x==2 E 8''),8'== = 0 =
- Connnec the children of the original initial state with the new, aritificia, initial state.
4. for E E:
for / o E
add q. 4 (d' to 8
for qE Q, QyyE ::
for 9 L e
add (q.w) v (d', 3/ 8'
9.
Add all state-symbol pairs with state from the original set of final states the new set of final states.
for qu E F,y E Σ:
add (gpp y) to Fd
13. if 4. E I:
C=Corner case: If the original initial state qu is an initial state, make the artificial initial state qi final.
14. add q.' to F
return A'
D Additional Related Work
Our work characterizes the representational capacity of HRNN LMs in terms of DPFSAs. On the other end of representational capacity, Chen et al. (201 8); Nowak et al. (2023) consider the connection between Elman RNNs with arbitrary precision-a stark contrast to our model-and (probabilistic) Turing machines first established by Siegelmann and Sontag (1992). They outline some implications the relationship has on the representational capacity of RNNs and the solvability of tasks such as finding the most probable string deciding whether an RNN is tight. These tasks shown be undecidable. This is in contrast to the equivalence shown here which, among other things, means that the decidability of the tasks on PFSAs can be carried over RNN LMs.
a different note, Bhattamishra et al. (2020) and Deletang et al. (2023) provide an empirical survey the unweighted representational capacity of different LM architectures. The former focuses on RNN variants and their ability to recognize context-free languages. The authors find that RNNs indeed struggle to learn the mechanisms required to recognize context-free languages, but find that hierarchical languages of finite depth, such as (kk m), can be learned reliably. This further motivates the connection between RNN LMs and finite-state models, well as the specific construction by Hewitt et al. (2020). While the results from Deletang al. (2023) be connected to the theoretical insights provided by existing work, it is also clear that the probabilistic nature, as well as non-architectural aspects of LMs (such the training regime), make establishing clear hierarchy of models difficult."" 19
''The hierarchy of probabilistic formal languages is not as clear as the original Chomsky hierarchy, which might be one of the reasons behind the inconsistent results (Icard, 2020).


Reviews:
[{"review_id": "uZr2fSsjGr", "reviewer": "Reviewer_R8qp", "summary": "", "questions": "* Question A. Could you please clarify what you mean by the term \"tight\" in the context of probability distributions? (see: L163)\n\n* Question B. (Feel free to skip this question) “For example, the very simple examples of (bounded) nesting expressible with context-free grammars are relatively awkward to express with finite-state formalisms such as finite-state automata—while they are expressible with such formalisms, the implementations lack the conciseness (and thus inductive biases) of the more concise formalisms.” (L683-690) What do you mean by “relatively awkward” in this context? Do you mean that it would be computationally expensive to express them with finite-state automata? \n\n* Question C. Have you considered extending this framework to self-attention models?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 5, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoroughly detailed and useful review as well as the nice words appreciating the writing style and the clarity of the presentation. We are also very grateful for the recognition of the thoroughness and contributions of the paper and for the recommendation of the paper for acceptance.\n\nRegarding the request for the coverage of more background material: We fully agree with the stated points. Should the paper be accepted, we will use some of the additional space for a comprehensive discussion of background material, including all the suggested work (thank you for the comprehensive list!), as well as a plethora of other works, such as *Peng et al. Rational recurrences* and *Chen et al. Recurrent neural networks as weighted language recognizers.*\nWith this, we plan to cover the contributions of others working in the intersection of RNNs, finite-state automata, and other formalisms. We agree such existing work is in some ways conceptually similar and provides very valuable insights. We were initially simply hesitant to cover a large extent of the current work as it does not (apart from the work by Icard) talk about weighted formalisms. \n\nWe are also grateful for the spotted typos and the raised comment about Figure 1. Indeed, we have improved Figure 2 and promoted it to the first page while also removing Figure 1. \n\n**Answers to questions**:\n1. Regarding Question 1: “Tight”, also known as consistent, language models are autoregressive models that define a valid probability distribution over finite strings. It is relatively simple to construct PFSAs that put probability mass on infinite sequences, resulting in a model where the probability mass on all *finite* strings is $<1$ instead of $1$. See *Du et al. A Measure-Theoretic Characterization of Tight Language Models* for a comprehensive study and discussion of the tightness of language modes.  \n2. Regarding Question 2: Your interpretation is correct. For example, the Dyck(k) language admits a very simple description with a context-free grammar, while the description of the Dyck(k, m) language using an FSA requires a large automaton covering every “case” separately in a separate state.  \n3. Regarding Question 3: Studying self-attention is the natural next step, yes. We have done some preliminary investigation into this and while we believe similar results can be achieved, the constructions are more elaborate and nuanced; due to the parallelizability, self-attention does not keep an internal state, which means that the connection to sequential models such as FSAs is more difficult. We, however, believe it can be done by augmenting the output alphabet and plan to showcase our constructions in future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* Overall, this paper unquestionably fulfills all the criteria for publication. It stands out not only for its impeccable writing and clarity but also for its accessible and insightful exploration of the connection between Elman-RNNs and deterministic probabilistic finite-state automata. It also includes useful asymptotic bounds on the space complexity of simulating PFSAs with Heaviside-activated Elman-RNNs. \n* The formal statements, as well as the accompanying proofs, are mostly convincing and easy-to-follow.\n* Moreover, the authors' thorough research is evident as they reference not only Minsky's classical construction of an RNN encoding a weighted finite-state automaton from 1954 but also works by Dewdney (1977), Indyk (1995), and Icard (2020) on RNNs, finite-state automata, and formal languages. This broadens the context and enriches the paper’s historical background, making it a delightful and well-rounded contribution to the field.\n", "reasons_to_reject": "* While this is not a major ground for rejection in any way, I believe the authors could have generously acknowledged the contributions of—and insights from— more recent studies that also investigate the practical capabilities and theoretical expressivity of RNN-based architectures. Whilst this paper might indeed be the first paper to formally and explicitly study “modern [language models] with weighted formal language theory,” I believe other studies have also taken conceptually similar paths. These include:\n  * William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. 2020. A Formal Hierarchy of RNN Architectures. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 443–459, Online. Association for Computational Linguistics.\n  * William Merrill. 2019. Sequential Neural Networks as Automata. In Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pages 1–13, Florence. Association for Computational Linguistics.\n  * Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018. On the Practical Computational Power of Finite Precision RNNs for Language Recognition. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 740–745, Melbourne, Australia. Association for Computational Linguistics.\n  * Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languages. In Proceedings of the 28th International Conference on Computational Linguistics, pages 1481–1494, Barcelona, Spain (Online). International Committee on Computational Linguistics.\n  * Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy et al. \"Neural networks and the chomsky hierarchy.\" arXiv preprint arXiv:2207.02098 (2022).\n  * Michael Hahn. 2020. Theoretical Limitations of Self-Attention in Neural Sequence Models. Transactions of the Association for Computational Linguistics, 8:156–171.\n* I believe the paper could be improved by giving more comprehensive acknowledgments of the contributions made by other researchers in the field. While the present study itself is commendable, it would be beneficial to recognize and cite the works of relevant authors who have paved the way in areas related to Elman-RNNs, deterministic probabilistic finite-state automata, and formal languages.", "questions_to_authors": "* Question A. Could you please clarify what you mean by the term \"tight\" in the context of probability distributions? (see: L163)\n\n* Question B. (Feel free to skip this question) “For example, the very simple examples of (bounded) nesting expressible with context-free grammars are relatively awkward to express with finite-state formalisms such as finite-state automata—while they are expressible with such formalisms, the implementations lack the conciseness (and thus inductive biases) of the more concise formalisms.” (L683-690) What do you mean by “relatively awkward” in this context? Do you mean that it would be computationally expensive to express them with finite-state automata? \n\n* Question C. Have you considered extending this framework to self-attention models?", "paper_topic_and_main_contributions": "This paper provides an insightful study of the expressive capabilities of simple Elman-style recurrent neural networks (Elman-RNNs) through the lens of the weighted formal language theory. It extends Minsky’s classification construction of an Elman-RNN with the Heaviside step function as its nonlinearity (also known as, Heaviside-activated Elman-RNN) simulating a finite-state automaton to a more probabilistic setup, establishing the equivalence between Heaviside-activated Elman-RNNs and deterministic finite-state automata. This result implies that Heaviside-activated Elman-RNNs can capture a rather strict subset of probability distributes expressible by deterministic finite-state automata.\n\nFurthermore, the paper confirms a widely accepted hypothesis that a Heavisde-activated Elman-RNN capturing the same probability distribution as a deterministic probabilistic finite-state automaton with an alphabet $Σ$ and states $Q$ needs to have at least $\\Omega (|\\Sigma|||Q|)$ parameters (hidden states). It is important to note that this bound also corresponds to the space complexity of Minsky’s original construction. \n\n**Recommendation**: Overall, this paper is to be commended for its insightful and clear study of the connection between Heaviside-activated Elman-style RNNs and deterministic (probabilistic) finite state automata. Considering its high-quality content, I believe that this paper fully meets the criteria for publication at EMNLP.", "excitement": 4, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "* Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languages. In Proceedings of the 28th International Conference on Computational Linguistics, pages 1481–1494, Barcelona, Spain (Online). International Committee on Computational Linguistics.\n* Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy et al. \"Neural networks and the chomsky hierarchy.\" arXiv preprint arXiv:2207.02098 (2022).\n* William Merrill. Formal language theory meets modern NLP. arXiv preprint arXiv:2102.10094.\n* Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann. 2019. LSTM Networks Can Perform Dynamic Counting. In Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pages 44–54, Florence. Association for Computational Linguistics.\n* Bhattamishra, Satwik, Kabir Ahuja, and Navin Goyal. \"On the practical ability of recurrent neural networks to recognize hierarchical languages.\" arXiv preprint arXiv:2011.03965 (2020).\n* Jennifer C. White and Ryan Cotterell. 2021. Examining the Inductive Bias of Neural Language Models with Artificial Languages. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 454–463, Online. Association for Computational Linguistics.\n", "Typos_Grammar_Style_and_Presentation_Improvements": "* Figure 1 does not feel to contribute much to the understanding of the paper. I would rather get rid of Figure 1 and promote Figure 2 to the first page.\n* L261: Extra space before \"ERNN\"\n* L265: In theory, should r be from Sigma-Bar instead of Sigma?\n* L375: [D] = [1, …, D] ← might want to clarify this.\n \n"}}, {"review_id": "noaxqQF0h0", "reviewer": "Reviewer_uUpK", "summary": "", "questions": "line 308: A common simplification is the use of the Heaviside activation function --> Could the authors provide some citations to support the claim of \"common simplification\"?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 5, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the useful review and the recognition of the utility of the work in making precise statements about the capabilities of language models and the limitations of simple RNNs.\n\nAs pointed out, the work makes concrete limiting assumptions on the LM architecture, which, as mentioned, were discussed and justified in the limitations section. Given these assumptions, the proof is indeed not complicated. Yet, we think it is still an important contribution as it provides a novel perspective on *how* probabilities from a formal computational model can be incorporated into a more modern language model. Some of our concurrent work shows that the methodology developed in this paper can be applied to other paradigms, for example, computational models higher on the Chomsky hierarchy (e.g., pushdown automata) as well as for the analysis of Transformer models.\n\nRegarding the **question**: The “common” assumption mainly refers to classical constructions such as: \n1. *McCulloch, W.S., Pitts, W. A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics 5, 115–133 (1943). https://doi.org/10.1007/BF02478259*  \n2. *Marvin Lee Minsky. 1954. Neural Nets and the brain model problem. Ph.D. thesis, Princeton University.*  \n3. *A. K. Dewdney. 1977. Threshold matrices and the state assignment problem for neural nets. In Proceedings of the 8th SouthEastern Conference on Combinatorics, Graph Theory and Computing, pages 227–245, Baton Rouge, La, USA.*\n4. *N. Alon, A. Dewdney and T. Ott, Efficient simulation of finite automata by neural nets, Journal of Association Computing Machinery 38 (1991) 498–514.*\n5. *P. Indyk. 1995. Optimal simulation of automata by neural nets. In STACS 95, pages 337–348, Berlin, Heidelberg. Springer Berlin Heidelberg.*  \n\nThe assumption on the binary nature of the activation function is also motivated by the “limiting” behavior of the standard sigmoid function, as discussed in work by William Merrill, for example in *Merrill, W. Sequential neural networks as automata.*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. Framing the study of RNN LMs through the lens of weighted formal language theory to make precise statements about their capabilities.\n2. The paper analyzed the space complexity of simulating dPFSAs with HRNN LMs, proving linear lower bounds in both the number of states and the alphabet size. This reveals the limitations of Heaviside-activated Elman RNNs.", "reasons_to_reject": "1. The Heaviside-activated Elman RNNs makes very strong simplifying assumptions about architecture (which is fine) and the activations (which makes the proof a little trivial, since the activations are binary variables) compared to LMs used in practice. As recognized by the authors in the Limitations section, most of the useful LMs (including word2vec) use dense representations.\n2. Other limitations are also well-discussed in the Limitation Section. But overall, I think this is a good paper.", "questions_to_authors": "line 308: A common simplification is the use of the Heaviside activation function --> Could the authors provide some citations to support the claim of \"common simplification\"?", "paper_topic_and_main_contributions": "The paper investigates the expressive power of Heaviside-activated Elman RNNs, and finds they define e the same set of probability distributions over strings as dPFSA.", "excitement": 4, "reproducibility": null, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "N/A", "Typos_Grammar_Style_and_Presentation_Improvements": "N/A"}, "extra_text": {}}, {"review_id": "3ckbNXfbUL", "reviewer": "Reviewer_bmNn", "summary": "", "questions": "none", "limitations": "", "rating": 4, "confidence": 3, "soundness": 5, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review and for recognizing the utility of the work and for the nice words about the clarity.\n\nWe are grateful for the feedback about the appendices and the discussion of the results.\nWe agree that the appendices of the paper are long, however, we would like to point out that most of the space is taken up by the review of the asymptotically more efficient constructions (due to Dewdney and Indyk) not directly necessary for the understanding of the main contributions of the work. Nonetheless, we agree that the discussion of the results is important and should not be relegated to the appendix. Therefore, should the paper be accepted, we plan to use part of the additional space to move the discussion into the main part of the paper and incorporate it there. We also think this will frame the discussion better.\n\nWe also sincerely thank the reviewer for the high numeric scores awarded to the submission. Nonetheless, we would like to ask about the soundness score—is anything in the exposition not clear or convincing? If so, we would be happy to further clarify and accordingly improve the submission.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "--- interesting study and results\n\n--- paper well organized and clearly written", "reasons_to_reject": "--- a lot of the material had to be moved to the appendixes", "questions_to_authors": "none", "paper_topic_and_main_contributions": "The aim of this paper is studying the expressive power of recurrent neural networks as language models, that is considering the probability distribution they associate to strings. The conclusion is that they associate the same probability distribution as deterministic probabilistic finite-state automata, but only when some simplifying assumptions are considered, including the Heaviside activation function. Space complexity is then extensively studied for the simulation of PFSAs with RNNs.\n\nThe paper only reports the results, leaving some discussions in addition to proofs to the appendixes, which are then very long.", "excitement": 4, "reproducibility": null, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "none", "Typos_Grammar_Style_and_Presentation_Improvements": "none"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are in broad consensus that this paper makes a substantial contribution to our understanding of the capabilities of RNNs. They agree that the insight is valuable, the investigation is thorough, and the paper is well written. While Reviewer uUpK points to some simplifying assumptions that may be considered a bit strong, but the authors openly address these limitations in the paper. The extensive discussion in the appendix might make this work better suited as a journal paper, but if the authors prefer to keep that discussion in the appendix and publish in a conference, I see no good reason to stop them.

I hope the authors incorporate the presentation and literature review suggestions in their paper revisions.
Decision: Accept-Main