The Surprising Computational Power of Nondeterministic Stack RNNs
Authors: Brian DuSell
David Chiang
Venue: ICLR 2023 poster (2023)
Keywords: formal languages
pushdown automata
language modeling
RNN

Abstract: Traditional recurrent neural networks (RNNs) have a fixed, finite number of memory cells. In theory (assuming bounded range and precision), this limits their formal language recognition power to regular languages, and in practice, RNNs have been shown to be unable to learn many context-free languages (CFLs). In order to expand the class of languages RNNs recognize, prior work has augmented RNNs with a nondeterministic stack data structure, putting them on par with pushdown automata and increasing their language recognition power to CFLs. Nondeterminism is needed for recognizing all CFLs (not just deterministic CFLs), but in this paper, we show that nondeterminism and the neural controller interact to produce two more unexpected abilities. First, the nondeterministic stack RNN can recognize not only CFLs, but also many non-context-free languages. Second, it can recognize languages with much larger alphabet sizes than one might expect given the size of its stack alphabet. Finally, to increase the information capacity in the stack and allow it to solve more complicated tasks with large alphabet sizes, we propose a new version of the nondeterministic stack that simulates stacks of vectors rather than discrete symbols. We demonstrate perplexity improvements with this new model on the Penn Treebank language modeling benchmark.

Published as a conference paper at ICLR 2023
THE SURPRISING COMPUTATIONAL POWER OF NONDETERMINISTIC STACK RNNS
Brian DuSell and David Chiang
Department of Computer Science and Engineering University of Notre Dame
[bdusell1 11, dchiang @ndd edu
ABSTRACT
Traditional recurrent neural networks (RNNs) have fixed, finite number of mem- ory cells. In theory (assuming bounded range and precision), this limits their for- mal language recognition power to regular languages, and in practice, RNNs have been shown to be unable to learn many context-free languages (CFLs). In order to expand the class of languages RNNs recognize, prior work has augmented RNNs with a nondeterministic stack data structure, putting them on par with pushdown automata and increasing their language recognition power to CFLs. Nondetermin- ism is needed for recognizing all CFLs (not just deterministic CFLs), but in this paper, show that nondeterminism and the neural controller interact produce two more unexpected abilities. First, the nondeterministic stack RNN can recog- nize not only CFLs, but also many non-context-free free languages. Second, can recognize languages with much larger alphabet sizes than one might expect given the size of its stack alphabet. Finally, to increase the information capacity the stack and allow it to solve more complicated tasks with large alphabet sizes, we propose a new version of the nondeterministic stack that simulates stacks of vec- tors rather than discrete symbols. We demonstrate perplexity improvements with this new model on the Penn Treebank language modeling benchmark.
INTRODUCTION
Standard recurrent neural networks (RNNs), including simple RNNs (Elman, 1990), GRUs (Cho et al., 2014), and LSTMs (Hochreiter & Schmidhuber, 1997), rely on fixed, finite number of neu- rons to remember information across timesteps. When implemented with finite precision, they are theoretically just very large finite automata, restricting the class of formal languages they recognize to regular languages (Kleene, 1951). In practice, too, LSTMs cannot learn simple non-regular lan- guages such { w E {0, }}} (DuSell & Chiang, 2020). To increase the theoretical and practical computational power of RNNs, past work has proposed augmenting RNNs with stack data structures (Sun al., 1995; Grefenstette al., 2015; Joulin & Mikolov, 2015; DuSell & Chiang. 2020), inspired by the fact that adding a stack to a finite automaton makes it pushdown automaton (PDA), raising its recognition power context-free languages (CFLs).
Recently, we proposed the nondeterministic stack RNN (NS-RNN) (DuSell & Chiang, 2020) and renormalizing NS-RNN (RNS-RNN) (DuSell & Chiang, 2022), augmenting an LSTM with a dif- ferentiable data structure that simulates real-time wal-time nondeterministic PDA. (The PDA is real-time in that it executes exactly one transition per input symbol scanned, and is nondeterministic in that executes all possible sequences of transitions.) This was in contrast to prior work stack RNNs, which exclusively modeled deterministic stacks, theoretically limiting such models to deterministic CFLs (DCFLs), which are a proper subset of CFLs (Sipser, 2013). The RNS-RNN proved more effective than deterministic stack RNNs at learning both nondeterministic and deterministic CFLs.
In practical terms, giving RNNs the ability to recognize context-free patterns may be beneficial for modeling natural language, as syntax exhibits hierarchical structure; nondeterminism in particular is necessary for handling the very common phenomenon of syntactic ambiguity. However, the RNS- RNN's reliance on PDA may still render it inadequate for practical use. For one, not all phenomena in human language are context-free, such cross-serial dependencies. Secondly, the RNS-RNN's

---

Published as a conference paper at ICLR 2023
output
Y
Yt
yt+1
controller
h
h
hi+1
It-
O++1
stack
St
8t
input
X
Xt
Xi+1
Figure 1: Conceptual diagram of the RNN controller-stack interface, unrolled across portion of time. The LSTM memory cell is not shown.
computational cost restricts it to small stack alphabet sizes, which is likely insufficient for storing detailed lexical information. In this paper, we show that the RNS-RNN surprisingly good at over- coming both difficulties. Whereas ordinary weighted PDA must use the same transition weights for all timesteps, the RNS-RNN can update them based on the status of ongoing nondeterministic branches of the PDA. This means it can coordinate multiple branches in way a PDA cannot-for example, to simulate multiple stacks, or to encode information in the distribution over stacks.
Our contributions in this paper are follows. We first prove that the RNS-RNN can recognize all CFLs and intersections of CFLs despite restrictions on its PDA transitions. We show empirically that the RNS-RNN can model some non-CFLs; in fact is the only stack RNN able to lear {w w E f0, }. whereas a deterministic multi-stack RNN cannot. We then show that, surprisingly an RNS-RNN with only 3 stack symbol types can learn to simulate stack of no fewer than 200 symbol types, by encoding them as points in vector space related to the distribution over stacks. Finally, in order to combine the benefits of nondeterminism and vector representations, we propose model that simulates PDA with stack of vectors instead of discrete symbols. We show that the new vector perplexity than other stack RNNs on the Penn Treebank. Our code is publicly available.'
outperforms the original on the Dyck language and achieves better
2 STACK RNNS
In this paper, we examine two styles of stack-augmented RNN, using the same architectural frame- work as in our previous work (DuSell & Chiang, 2022) (Fig. 1). In both cases, the model consists of an LSTM, called the controller, connected to differentiable stack. At each timestep, the stack receives actions from the controller (e.g. to push and pop elements). The stack simulates those actions and produces reading vector, which represents the updated top element of the stack. The reading is fed as an extra input to the controller at the next timestep. The actions and reading con- sist of continuous and differentiable weights so the whole model can be trained end-to-end with backpropagation; their form and meaning vary depending on the particular style stack.
We assume the input memory consists of a hidden state h, and memory cell c, (we set ho = Co = 0). The controller computes the next state (h,, cz) given the previous state, input vector xt, and stack reading r
Wi W., is encoded
sequence of vectors X1, X,,- The LSTM's
(he, c.) = LSTM ((h--1.--1)
X
rt-1 (
The hidden state generates the stack actions a and logits yt for predicting the next word w1+1- The previous stack and new actions generate new stack 8t, which produces new reading ry:
a, ACTIONS(h,) y. W W
bay s, ST r, READING
Each style of stack differs only in the definitions of ACTIONS, STACK, and READING.
2.1 SUPERPOSITION STACK RNN
We start by describing a stack with deterministic actions-the superposition stack of Joulin & Mikolov (2015) which we include because it was one of the best-performing stack RNNs we
httpp::/ com httpb//wwsennnnetterrrrre
2

---

Published as a conference paper at ICLR 2023
investigated previously (2020; 2022). The superposition stack simulates combination of partial stack actions by computing three new, separate stacks: one with all cells shifted down (push), kept the same (no-op), and shifted up (pop). The new stack is an element-wise, interpolation ("superpo- sition") of these three stacks. The stack elements are vectors, and a; = (ar. ve), where the vector a, is probability distribution over the three stack operations. The push operation pushes vector Vt. which can be learned or set to he The stack reading is the top vector element.
2.2 RENORMALIZING NONDETERMINISH STACK RNN
The main focus of this paper is the renormalizing nondeterministic stack RNN (RNS-RNN) (DuSell & Chiang, 2022). The RNS-RNN's stack module is a simulation of real-time weighted PDA, complete with its own finite state machine and stack. Let Q be the set of states and I' be the stack alphabet of the PDA. The initial PDA state is do E Q and the initial stack is 1 E Г. The PDA's computation is governed by weighted transitions that manipulate its state and stack contents; valid sequence of transitions is called a run. The PDA is nondeterministicc in that all possible runs are simulated in parallel. Each run has weight, which is the product of the weights of its transitions.
The ACTIONS emitted by the controller are the PDA's transition weights. The weights at t. denoted A[t], are computed A cxp( @xspW,,ll hh,, + ba). Let q. Q and u, 8 E r", and let Aft][g, u - r, v] denote the weight, at timestep t, of popping u from the stack, pushing U, and transitioning to state r if the previous state was q and the previous stack top was u. Transitions have one of three forms, where v. y E r: A[][2, - r, zyl (push y), A[][[,,2 x - r, r] (replace x with y) and Aif]q, - r, (pop rt). We say that transitions limited these three forms are in restricted form.
The READING is the marginal distribution, over all runs, of each pair (r. E Q x 1, where r is the current PDA state, and y is the top stack symbol. Let T; be a PDA transition, let π Ti- 71.-77 Tr be a PDA run, and let (T)) = I Ali][T]] [ be the weight of run æ. Let x ~4 t, r. y mean that run i ends at timestep in state r with y on top of the stack. The stack reading r, E RIQQIITI is defined as
Exenetr (TT))
[r v) En of (((T)
Equation (1) is sufficient for describing the RNS-RNN mathematically, but it sums over an expo- nential number of runs, so the RNS-RNN relies on dynamic programming algorithm to compute it in (n²)) time (Lang, 1974). The rest of this section describes this algorithm and may safely be skipped unless the reader is interested in these implementation details or Eqs. (9) to (11).
The algorithm uses tensor of weights called the stack WFA, so named because it can be viewed as a weighted finite automaton (WFA) that encodes the weighted language of all possible stacks the PDA can have at time t. Each WFA state is of the form (i. 9, 2)., representing a configuration where the PDA is in state g with stack top x at time i. For any WFA transition from (i, q, x)) to (4, r. y), its weight is equal to the sum of the weights of all runs that bring the PDA from configuration (i. g, x) to (1, r, v) (possibly over multiple timesteps) without modifying æ, with the net effect of putting a single y top of it. The tensor containing the stack WFA's transition weights, also called inner weights, is denoted 7 and elements are written as 7(2 - t|[g, x + r. y]. For s s n - 1 and -1 siist- 1
-|11 0100, + +.,y] = [[ = 20 Ax LA 20 A y 11
init.
>[i + l1[0, x + r. = I[i = t-1]
A [t]g, +
push
(3)
Σ >/1
|| - 2] A|1](, + r.vl
repl.
8,2
Σ 7i4 + ki] x u,y) 7kk + 011u, y - r]
pop
kmi+1
I/ke + eulu + r]
7kk - 11 s, A[]ss A r, (0 1oskst-20 2). (4)
The RNS-RNN sums over all runs using a tensor of forward weights denoted a, where the element a[[[rr y] is the total weight of reaching the stack WFA state (1, r. v). These weights are normalized
3

---

Published as a conference paper at ICLR 2023
to get the final stack reading at t.
a(-1][rr = I[r 20 ^ y-=yy = 1]
(5)
a/t][r, u] Σ Σ
- t| - (0ll)00tt5 (0stsn-1)
(6)
1=-1 a,
r.((r, y) Er.yy' [
We have departed slightly from the original definitions of and a (DuSell & Chiang. 2022), for two reasons: (1) to implement asymptotic speedup by factor of [Q] (Butoi al., 2022), and (2) to fix peculiarity with the behavior of the initial _. See Appendix A for details.
3 RECOGNITION POWER
In this section, we investigate the power of RNS-RNNs as language recognition devices, proving that they can recognize all CFLs and all intersections of CFLs. These results hold true even when the RNS-RNN is run in real time (one timestep per input, with one extra timestep to read EOS). Although Siegelmann & Sontag (1992) showed that even simple RNNs are as powerful as Turing machines, this result relies on assumptions of infinite precision and unlimited extra timesteps, which generally do not hold true in practice. The same limitation applies to the neural Turing machine (Graves et al., 2014), which, when implemented with finite precision, is more powerful than finite automaton, as its tape does not grow with input length. Previously, Stogin et al. (2020) showed that a variant of the superposition stack is at least as powerful as real-time DPDAs. Here we show that RNS-RNNS recognize a much larger superset of languages.
For this section only, we allow parameters have values of to0, to enable the controller emit probabilities of exactly zero. Because we use RNS-RNNS here for accepting or rejecting strings (whereas in the rest of the paper, only them for predicting the next symbol), start by providing formal definition of language recognition for RNNs (ef. Chen et al., 2018).
Definition 1. Let N be an RNN controller, possibly augmented with one of the stack modules above. Let h, Rdd be the hidden state of N after reading t symbols, and let be the logistic sigmoid function. We say that N recognizes language L if there is an MLP layer y = o (W o (W, hpm b,) + b2) such that, after reading w EOS, we have > iff w E L.
The question of whether RNS-RNNS can recognize all CFLs can be reduced to the question of whether real-time PDAs with transitions in restricted form (Section 2.2) can recognize all CFLs. The real-time requirement does not reduce the power of PDAs (Greibach, 1965), but what about restricted form? We prove that does not either, and RNS-RNNS can recognize all CFLs.
Proposition 1. For every context-free language L, there exists RNS-RNN that recognizes L.
Proof sketch. We construct a CFG for I. and convert it into a modified Greibach normal form, called 2-GNF, which we can convert into PDA whose transitions are in restricted form. Then we construct an RNS-RNN that emits, at every timestep. weight I for transitions of P and 0 for all others. Then y > iff the PDA ends in an accept configuration. See Appendix B. for details. O
Proposition 2. For every finite set of context-free languages Li...., ... Lx over the same alphabet E, there exists an RNS-RNN that recognizes L1 .... T.k.
Proof sketch. Without loss of generality, assume k = 2. Let P1 and P2 be PDAs recognizing L and Lz, respectively. We construct PDA P that uses nondeterminism simulate P1 Pz, but the controller can query Pi and Pa's configurations, and it can set > iff P1 and Pz both end in accept configurations. See Appendix B.2 for details.
Since the class of languages formed by the intersection of CFLs is proper superset of the class formed by the intersection of (k 1) CFLs (Liu Weiner, 1973), this means that RNS-RNNE are considerably more powerful than nondeterministic PDAs.
4

---

Published as a conference paper at ICLR 2023
4 NON-CONTEXT-FREE LANGUAGES
We now explore the ability of stack RNNs to recognize non-context-free phenomena with language modeling task on several non-CFLs. Each non-CFL, which we describe below, can be recognized by real-time three-stack automaton (see Appendix C for details). We also include additional non- CFLs Appendix C.
w w# #ww The language (w+w #o 1).]
w#w The language {w+w w E {0, ")")
www The language {ww'
{0,1}* and w' <(w)}, where é is the homomorphism <(0)
2, (11) = 3.
ww The language {ww w E {0,1}"}
The above languages all include patterns like w w...w, w, which are known in linguistics as cross-serial dependencies. In Swiss German (Shieber, 1985), the two w's are distinguished by part-of-speech (a sequence of nouns and verbs, respectively), analogous to ww'. In Bambara (Culy, 1985), the two w's are the same, but separated by a morpheme analogous wtw.
We follow our previous experimental framework (DuSell & Chiang, 2022). If is a language, let Le be the set of all strings in L of length L. To sample string E L. we first uniformly sample length l from /40, 80), then sample uniformly from Le (we avoid sampling lengths for which Le is empty). So, the distribution from which is sampled is
1
(w(
{e E [40, 80] L. + 0} |L
We require models to predict EOS symbol at the end of each string, each language model M defines a probability distribution par (w). Let the per-symbol cross-entropy of a probability
distribution p on of strings S, measured in nats, be defined
H(S,p) - - log p(w)
Ewes(1ul +)
The +1 in the denominator accounts for the fact that the model must predict EOS. Since we know the exact distribution from which the data is sampled (for each non-CFL above, [L can be computed directly from ww). learned and true distributions, or H (S,, (S,P)) ) HS, PL). Lower is better, and is optimal.
evaluate model M by measuring the cross-entropy difference between the
We compare five architectures, each of which consists of an LSTM controller connected a different type of data structure. We include a bare LSTM baseline ("LSTM"). We also include a model that pushes learned vectors of size 10 superposition stack ("Sup. 10"), and another that pushes the controller's hidden state ("Sup. h²"). Since each of these languages can be recognized by a three- stack automaton, we also tested model that is connected
three independent instances of the (
superposition stack, each of which has vectors of size 3 ("Sup. 3-3-3"). Finally, we include an RNS- RNN with [Q] and [[| 3. where [Q] is sufficient for the model to be able to simulate at least three different stacks. In all cases, the LSTM controller has one layer and 20 hidden units. We encoded all input symbols as one-hot vectors.
Before each training run, we sampled a training set of 10,000 examples and validation set of 1,000 examples from PL- For each language and architecture, we trained 10 models and report results for the model with the lowest cross-entropy difference on the validation set. For each language, we sampled a single test set that was reused across all training runs. Examples in the test set vary in length from 40 to 100, with 100 examples sampled uniformly from Le for each length l. Additional training details can be found in Appendix D.
We show the cross-entropy difference on the validation and test sets in Fig. 2. We show results for additional non-CFLs in Appendix E. Strings in w w R u contain two hints to facilitate learning: explicit boundaries for w, and extra timesteps in the middle, which simplify the task of transferring symbols between stacks (for details, compare the solutions for w w f ww and w i us described in Appendix C). Only models that simulate multiple stacks, Sup. 3-3-3 and RNS 3-3, achieved
5

---

Published as a conference paper at ICLR 2023
LSTM
Sup. 10
Sup. 3-3-3
Sup.
RNS 3-3
Cross catropy Dift.
0.6
Cross-entropy Dift.
wr un 1
0.4
0.5
0.2
Mm
20
60
80
100
120
140
50
60
70
80
90
100
Cross-cntie coss-entropy Diff.
0.4
to
Cross-entropy Diff.
0.6
0.4
0.2
0.2
0
50
100
150
200
40
50
60
70
80
90
100
Cros- Cros-entropy Dift.
0.4
wad
Cross-entropy Dift.
wwd
0.3
0.2
0.2
0.1
0
20
40
60
80
100
120
140
40
50
60
70
80
90
100
Cross entropy Diff.
Cross-entropy Diff.
0.3
0.2
0.2
0.1
50
100
150
200
60
70
Epoch
Length
Figure Performance on non-context-free languages. Cross-entropy difference in nats, on the validation set by epoch (left), and on the test set by string length (right). Each line is the best of 10 runs, selected by validation perfomance. On u #w, which has both explicit boundaries and extra timesteps in the middle, only multi-stack models (Sup. 3-3-3 and RNS 3-3) achieved optimal cross-entropy. On w and ww', which have no extra timesteps, only RNS 3-3 did.
optimal cross-entropy here, although RNS 3-3 did not generalize well on lengths not seen in training. Only RNS 3-3 effectively learned w and ww'. This suggests that although multiple deterministic stacks are enough to learn copy string given enough hints in the input (explicit boundaries, extra timesteps computation), only the nondeterministic stack succeeds when the number of hints reduced (no extra timesteps). No stack models learned copy string without explicit boundaries (ww), suggesting a nondeterministie multi-stack model (as opposed to one that uses nondeterminism to simulate multiple stacks) may be needed for such patterns.
5 CAPACITY
In this section, we examine how much information each model can transmit through its stack. Con- sider the language fw#w" w E ). can be recognized by real-time PDA with [I| = when |Σ| = 2, but not when [Σ] > 2, as there is always a sufficiently long w such that there are more possible w's than possible PDA configurations upon reading the 4. Similarly, because all the neural stack models consider here also real-time, expect that they will be unable to model context-free languages with sufficiently large alphabets. This especially relevant to natural languages, which have very large vocabulary sizes.

---

Published as a conference paper at ICLR 2023
Neural networks can encode large sets of distinct types in compact vector representations: in fact, Schwartz et al. (2018) and Peng et al. (2018) showed connections between the vector representations in RNNs and the states of WFAs. However, since the RNS-RNN simulates discrete stack, it might struggle on tasks that require it to store strings over alphahets with sizes greater than [T]. On the other hand, a model that uses a stack of vectors, like the superposition stack, might model such languages more easily by representing each symbol type as a different cluster of points in a vector space. Here, make the surprising finding that the RNS-RNN can vastly outperform the superposition stack even for large alphabets, though not always. In addition, to see if we can combine the benefits of nondeterminism with the benefits of vector representations, we propose a new variant of the RNS- RNN that models PDA with stack of discrete symbols augmented with vectors.
5.1 VECTOR RNS-RNN
The RNS-RNN is computationally expensive for large [T]. To address this shortcoming, we propose new variant, the Vector ENS-RNN (IRNS-RNN)) that uses stack whose elements are symbols drawn from I and augmented with vectors of size m, which it can use to encode large alphabets. Its time and space complexity scale only linearly with m. Now, each PDA run involves stack of elements in Ix" We assume the initial stack consists of the element (L. vo), where Vo = (wv)), and w. is learned parameter. The stack operations now have the following semantics:
Push g, x r, If q is the current state and (æ, u) is top of the stack, go to state and push (y, vr) with weight A [t][g, x - r, sy]. where V; = oWW,, + b.).
Replace q, + r, y If q is the current state and (z, u) is on top of the stack, go state r and replace (z., u) with (v. u) with weight A A[f][g, - r, v. Note that we do not replace u with væ;
we replace the discrete symbol only and keep the vector the same. When x = y, this is a no-op.
Pop q, + r If y the current state and (z, u) on top of the stack, go to state r and remove (z, u) with weight A[t][g, x - r], uncovering the stack element beneath.
Let (T)) denote the top stack vector at the end of run и. The stack reading E RIQH-FI now includes, for each (r, v) E Q x I, an interpolation vTz) for every run т ~ L, y, normalized by the weight of all runs.
Em-tary ((T) v())
r (r((,,y))] Er'y Emmer w (x))
We compute the denominator using 7 and a as before. compute the numerator, we compute a new tensor Ç which stores (x(x)) (T). For I 1 < n - 1 and -1 < i i
<i-1 + 0lgg. x r, r. I[q @o A x = -Ar 90 A
vo
init.?
(9)
Ç/i + Elgg. + r, = 1|i = 1-1] A |t vyl V:
push (10)
Σ c 1 A|t 2 - r,
repl.
t-2
Σ
E blg u. r' lk + E|[u, y + r]. pop
k=++1
We compute before, and we compute the normalized stack reading r, as follows.
re((T.,,3)]
mr m]
Σ
aalilaa x] Cii f|[g, x r.vl
(11)
Er [1
5.2 EXPERIMENTS
We evaluate models using cross-entropy difference in Section 4. We express each language L as a PCFG, using the same PCFG definitions as in prior work (DuSell & Chiang, 2020), but modified
"Our code and experiments implement Çi-1 + O][g, + r.y] vo instead due to mistake found late in the publication process. Consequently. in Eq. (11), runs can start with any (r,y) E Q x I in the numerator, but only (go, 1.) in the denominator, Empirically the VRNS-RNN still appears work as expected.
7

---

Published as a conference paper at ICLR 2023
LSTM VRNS 1-1-3
Sup.
RNS 1-3
RNS 2-3
VRNS 2-1-3
VRNS 2-3-3
Cross-entropy Diff.
w
Cross-entropy Diff.
Dyck
1.75
0.8
1.5
1.25
0.6
0.75
0.4
0.5
0.2
0.25
2
40
80
120
160
200
2
40
80
120
160
200
Alphabet Size k
Alphabet Size k
Figure 3: Mean cross-entropy difference the validation set input alphabet size. Contrary to expectation, RNS 2-3, which models a discrete stack of only 3 symbol types, learns to solve w wt with 200 symbol types more reliably than models with stacks of vectors. On the more complicated Dyck language, vector stacks perform best, with our newly proposed TRNS-RNN performing best.
0.6
0.4
0.2
0.2
-0.4
-0.4
0.2
0
0.2
0.4
0.6
Figure 4: When RNS 2-3 run on w#w" with 40 symbol types, the stack readings are as visualized above. The readings are 6-dimensional vectors, projected down to 2 dimensions using PCA. The color of each point represents the top stack symbol. Points corresponding type cluster together, indicating the RNS-RNN has learned to encode symbols as points in the 5- dimensional simplex. The disorganized points the middle are from the first and last timesteps of the second half of the string, which appear to be irrelevant for prediction.
the same symbol
to include & symbol types. order to sample from and compute (w), we used the same sampling and parsing techniques before (DuSell & Chiang, 2020). We tested the information capacity of each model on two DCFLs, varying their alphabet size from very small to very large.
w#w The language (w#w" "
10, -k-13")
Dyck The language of strings over the alphabet (1, ) 1, (2, (2,)2. 2,... (k. k where all brackets properly balanced and nested in pairs of (; and 5.
We compare four types of architecture, including an LSTM baseline ("LSTM"), and superposition stack that pushes learned vectors of size 3 ("Sup. 3"). We use the notation "RNS [Q]-[r]" for RNS-RNNs, and "VRNS IQ1-I1'=m" for VRNS-RNNs. All details of the controller and training procedure are the same as in Section 4. We varied the alphabet size l from 2 to 200 in increments of 40. For each task, architecture, and alphabet size, we ran random restarts.
In Fig. 3, for each task, we show the mean cross-entrops difference on the validation set as function of alphabet size; we provide plots of the best performance Appendix On ## the single- state RNS 1- 1-3, and even VRNS 1-1-3 and Sup. 3, struggled for large k. Only the multi-state models RNS 2-3, VRNS 2-1-3, and VRNS 2-3-3 show a clear advantage over the LSTM. Surprisingly, RNS 2-3, which models discrete stack alphabet of only size 3, attained the best performance large alphabets; in Fig. 7, it is the only model capable of achieving optimal cross-entropy on all alphabet sizes. On the Dyck language, more complicated DCFL, the model rankings are expected: vector stacks (Sup. and VRNS) performed best, with the largest VRNS model performing best. RNS- RNNs still show clear advantage the LSTM, but not much vector stack RNNs.
8

---

Published as a conference paper at ICLR 2023
Validation and test perplexity on the Penn Treebank of the best of 10 random restarts for each architecture. The model with the best test perplexity is our new VRNS-RNN when it combines a modest amount of nondeterminism (3 states and 3 stack symbols) with vectors of size 5.
Table 1:
Model
Val.
Test
LSTM, 256 units
129.99
125.90
Sup. (push hidden), 247 units
124.99
121.05
Sup. (push learned), |va| = 22
125.68
120.74
RNS 1-29
131.17
128.11
RNS 2-13
128.97
122.76
RNS 4-5
126.06
120.19
VRNS 1-1-256
130.60
126.70
VRNS 1-1-32
124.49
120.45
VRNS 1-5-20
128.35
124.63
VRNS 2-3-10
129.30
124.03
VRNS 3-3-5
124.71
120.12
If RNS 2-3 has only 3 symbol types at its disposal, how can it succeed on w w#w" w for large k? Recall that r, is vector that represents probability distribution over Q x r. Perhaps the RNS-RNN, via To represents symbol types as different clusters of points in ((2H-1)) To test this hypothesis, we selected the RNS 2-3 model with the best validation performance on w#w for & 40 and evaluated it on 100 samples drawn from PL- For each symbol between and EOS, we extracted the stack reading vector computed just prior to predicting that symbol. Aggregating over all 100 samples, reduced the stack readings to 2 dimensions using principal component analysis. We plot them in Fig. 4, labeling each point according to the symbol type to be predicted just after the corresponding stack reading. Indeed, see that stack readings corresponding cluster together, suggesting that the model is orchestrating the weights of different runs in a way that causes the stack reading to encode different symbol types as points in the 5-dimensional simplex. We show heatmaps of actual reading vectors in Appendix G.
the same symbol
6 NATURAL LANGUAGE MODELING
We now examine how stack RNNs fare on natural language modeling, as the combination of non- determinism and vector representations in the VRNS-RNN may prove beneficial. Following our prior work (DuSell & Chiang. 2022), we report perplexity on the Penn Treebank as preprocessed by Mikolov et al. (2011). We used the same LSTM and superposition stack baselines, and various sizes of RNS-RNN and TRNS-RNN, The controller has one layer and, unless otherwise noted, 256 hidden units. For each architecture, we trained 10 random restarts and report results for the model with the best validation perplexity. Appendix H has additional details.
We show results in Table 1. Most stack RNNs achieved better test perplexity than the LSTM base- line. The best models are those that simulate more nondeterminism (VRNS when [Q] 3 and [ = 3. and RNS when IQ| = and [T] = 5). Although the superposition stack RNNs outper- formed the LSTM baseline, it is the combination of both nondeterminism and vector embeddings (VRNS 3-3-5) that achieved the best performance, combining the ability to process syntax nonde- terministically with the ability to pack lexical information into vector space on the stack.
CONCLUSION
We showed that the RNS-RNN (DuSell & Chiang, 2022) can recognize all CFLs and a large class of non-CFLs, and it can even learn cross-serial dependencies provided the boundary is explicitly marked, unlike a deterministic multi-stack architecture. We also showed that the RNS-RNN can far exceed the amount of information it seemingly should be able to encode in its stack given its finite stack alphabet. Our newly proposed VRNS-RNN combines the benefits of nondeterminism and vector embeddings, and we showed that it has better performance than other stack RNNs on the Dyck language and natural language modeling benchmark.

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
To facilitate reproducibility, we have publicly released all code we used conduct our experiments and generate the figures and tables in this paper. During both development and experimentation, we ran our code in containers to simplify reproducing our software environment. Our code includes the original Docker image definition we used, as well as the exact shell commands we used for each experiment, figure, and table. We have thoroughly documented our experimental settings in Sections 4 to 6 and Appendices D and H.
ACKNOWLEDGMENTS
This research was supported in part by Google Faculty Research Award to Chiang. We would like to thank Darcey Riley and Stephen Bothwell for their comments on an earlier draft of this paper, and the Center for Research Computing the University of Notre Dame for providing the computing infrastructure for our experiments.
REFERENCES
Jean-Michel Autebert, Jean Berstel, and Luc Boasson. Context-free languages and pushdown tomata. In Grzegorz Rozenberg and Arto Salomaa (eds.), Handbook of Formal Languages, pp- 111-174. Springer, 1997. doi: 10.1007/978-33-62-5913----
Alexandra Butoi, Brian DuSell, Tim Vieira, Ryan Cotterell, and David Chiang. Algorithms for weighted pushdown automata. In Proc. EMNLP, 2022.
Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, and Kevin Knight. Recurrent neural networks weighted language recognizers. In Proc. NAACL HLT (Long Papers), pp. 2261-2271, 2018. doi: 10.18653/v I/N18-1205.
Kyunghyun Cho, Bart van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the prop- erties of neural machine translation: Encoder-decoder approaches. In Proc. Workshop on Syntax. Semanties and Structure in Statistical Translation (SSST), pp. 103-111, 2014. doi: 10.3115/v1W14-4012..
Christopher Culy. The complexity of the vocabulary of Bambara. Linguisties and Philosophy, 8: 345-351, 1985.
Brian DuSell and David Chiang. Learning context-free languages with nondeterministic stack RNNs. In Proc. Conference on Computational Natural Language Learning (CoNLL), pp. 507- 519, 2020. doi: 10.18663/w1/2020.comll/ coo.0101.....11..11111
Brian DuSell and David Chiang. Learning hierarchical structures with differentiable nondetermin- istic stacks. In Proc. ICLR, 2022. URL https: / wttpee/wwwwweeeddd/i/..e.eooe QplBiF.
Jeffrey L. Elman. Finding structure in time. Cognitive Science, 14(2):179-211, 1990. doi: 10.1016/ 0364-0213390))00022EE
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural Turing machines, 2014. URL http:// arxiv. abs 11101..40 5401. arXiv:1410.5401.
Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blun- Learning to transduce with unbounded memory. In Proc. NeurIPS, vol- URL https: //tpp:://ppppraaa nips cc cc/paper/ memory-eerr.....m .d
ume 2, pp. 1828-1836. 2015.
1148-leatee 1elllaannn www.eeiin-oooorrannoooooooo
Sheila A. Greibach. new normal-form theorem for context-free phrase structure grammars. J. ACM, 12(1):42-52, 1965. doi: 10. 00.1145/2212503222254
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8): 1735-1780, 1997. doi: 10.1162/neco. 1997.9 1997.9.8.175..
10

---

Published as a conference paper at ICLR 2023
Armand Joulin and
Tomas
Mikolov. Inferring algorithmic patterns with stack- nets. In Proc. NeurIPS, volume pp. 190-198, wwtpppppe///1///eeeeeeee Absttrraat.......t.............. html.
augmented recurrent 2015.
URL https: https///ppoceeddnnnnneeeeeeeeeee cc..cc//ppecoo
S. C. Kleene. Representation of events in nerve nets and finite automata. Technical Report RM-774, RAND, 1951. URL https: mesearch
wwtp//ogg//oeeeeeeeee /can:/t//////// rand/aandiaaaaaa /ubs/ pdf.
Bernard Lang. Deterministic techniques for efficient non-deterministic parsers. In Proc. Col- loquium on Automata, Languages, and Programming (ICALP), pp. 255-269, 1974. doi:
Leonard Liu and Peter Weiner. An infinite hierarchy of intersections of context-free languages. Math. Syst. Theory, 7(2):185-192, 192, 1973. doi: 10.1007/BF01762233.
Tomas Mikolov, Anoop Deoras, Stefan Kombrink, L. Burget, and Cernocký. Empirical eval- uation and combination of advanced language modeling techniques. In Proc. INTERSPEECH, pp. 605-608, 2011. URL https: /www sscaisscsppse secca-sppech.... org/ httg//archive_v/rrccccc. pdf.
papers/
Hao Peng. Roy Schwartz, Sam Thomson, and Noah A. Smith. Rational recurrences. In Proc. EMNLP, pp. 1203-1214, 2018. doi: 10.18653v1/D18-.. 1152.
Roy Schwartz, Sam Thomson, and Noah A. Smith. Bridging CNNs, RNNs, and weighted inite-state machines. In Proc. ACL (Long Papers). pp. 295-305, 2018. doi: 10.18653/v1/P18. 1028.
Stuart M. Shieber. Evidence against the context-freeness of natural language. Linguistics and Phi- losophy, 8:333-344, 1985.
Hava T. Siegelmann and Eduardo Sontag. On the computational power of neural nets. In Proc. Workshop Computational Learning Theory (COLT), pp. 440-449, 1992. doi: 10. 10.1145/130385. 130432.
Michael Sipser. Introduction to the Theory of Computation. Cengage Learning, 3rd edition, 2013.
John Stogin, Ankur Arjun Mali, and C. Lee Giles. Provably stable interpretable encodings of context free grammars in RNNs with differentiable stack, 2020. URL https: //axxiv///xvv..//// org/ / 2006. v3.5vv3. wrXiv:2006.03651
G. Z. Sun, C. Lee Giles, H. H. Chen, and Lee. The neural network pushdown automaton: Model, stack, and learning simulations. Technical Report UMIACS-TR-93-77 and CS-TR-3118 111-1118, University Maryland, 1995. URL version.
05738. Revised
Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power of finite pre- cision RNNs for language recognition. In Proc. ACL (Short Papers), pp. 740-745, 2018. doi: 10.18653/v//118-21177
Dani Yogatama, Yishu Miao, Gábor Melis, Wang Ling, Adhiguna Kuncoro, Chris Dyer, and Phil Blunsom. Memory architectures in recurrent neural network language models. In Proc. ICLR, 2018. URL httpt:://tpppttiteee http::::///ppeeeeiewee net ottpaa/ewweeeeeeeeeoooooooooooee http.aeeeeeeepeeeetfetee/
A CHANGES TO THE RNS-RNN
In this section, we describe two minor changes to the original definition of the RNS-RNN that improve its time complexity and expressivity. We first reiterate the original definitions for y and

---

Published as a conference paper at ICLR 2023
(DuSell & Chiang, 2022). For 0 si<tšn-1 y/2 - =|lg. + y, y) =
T[i 1-1] | x any
push
+ Σ >/4 + -- s, 2] A|t][s r.yl
repl.
1-2
+
Σ
ΣΣ
7/ kl10,1 - u.yl 7/- t-1][ 8 A|] 8 - r,e]
pop
k=
5,2
(12)
a00 = = 90
(13)
att] v) = Σ Σ 1=0
atilaa >/ t][q, r,
(1stsn) n).
(14)
qar
Note that in RNN where r is used compute h, and yr, the last timestep = n is not needed,
so A (t) is only defined for S S n 1, and and a only need to be computed for / S n 1.
Now, we describe the two changes have made to Eqs. (12) to (14) arrive at Eqs. (2) to (6).
Asymptotic speeddu As can be seen in Eqs. (7) and (12) to (14), the is O(QQ""ITT" and its space complexity is O( ( in²). The computational complexity of the RNS-RNN limits us to relatively small sizes for Q and However, is possible improve its asymptotic time complexity with respect to Q) with simple change: precomputing the product 7kk + t-1][u, y + s A[[[s, > r used the pop rule in Eq. (12), which we store in a tensor 7/- This reduces the time complexity of the RNS-RNN to O(QQ) 3 s n² + 1Q1 allowing us train larger models.
time complexity
Bottom symbol fix There are some peculiarities of the initial 1 marker that are not described in previous work: (1) the initial instance of I the bottom of the stack can never be popped or replaced, (2) any symbol that sits directly above it cannot be popped (but it can be replaced), and (3) the symbol type can be reused freely elsewhere symbol can never be uncovered again after the first timestep, possibly complicating detection of the bottom the stack later on. We rectify this by allowing the symbol above the initial I to be popped, and allowing the initial 1 symbol to be replaced with different symbol type at any time. We do this by simulating an extra push action at -1.
the stack. Point (2) is odd because the
B PROOFS OF LANGUAGE RECOGNITION RESULTS
B. PROOF OF PROPOSITION
In this section, we prove that the restricted form of real-time PDA used in the RNS-RNN can recog- nize all CFLs. We then show how to convert PDAs in this form to RNS-RNN recognizers (assuming some parameters can have values of +o00,, proving that RNS-RNNS
recognize all CFL.s
Definition 2. A pushdown automaton is a tuple (Q, E. 0, go, F, L), where
Q is a finite set of states
V is a finite input alphabet
r is finite stack alphabet
8 C Q x p (EUe) x * 1 is set of transitions
go E Q is the start state
F FCC Q is the set of accept states
12

---

Published as a conference paper at ICLR 2023
L I' is the bottom stack symbol.
PDA always starts in state qo with stack consisting I,, and it accepts its input iff there is a run that terminates in an accept state with 1 top of the stack.
Definition 3. restricted PDA one whose transitions have one of the following forms, where 9, E Q, Σ, and x; y E T:
4 2 r; ay
push y on top of x
q, 2 T;
replace with pop x.
4 9 r,e
The usual construction for removing non-scanning transitions (Autebert et al., 1997) involves con- verting Greibach normal form (GNF) and then converting a PDA. However, this construction produces transitions of the form q, S> r, zy where x * z, which our restricted form does not allow. Simulating such transitions in restricted PDA presents challenge because it requires performing a replace and then a push while seanning only one symbol. To simulate such transitions, we need to use modified GNF, defined below.
Lemma 3. For any CFG G, there is a CFG equivalent to G that has the following form (called 2 Greiibach normal form):
The start symbol does not appear on any right-hand side.
Every rule has one of the following forms:
S -
A - - abBı ... Bp
p p20.
Proof. Convert to Greibach normal form. Then for every rule A + aA1 ... Am and every rule A + bB, ... B₁, substitute the second rule into the first to obtain A + abB, ... B,A, ... Am- Then discard the first rule.
Lemma 4. For any CFG G in 2-GNE, there is PDA equivalent G whose transitions all have one of the forms:
9, - 2,,111
g, - T,y
(15)
g + T,
Proof. We split the rules into four cases:
S +
A +
+
A + abB
B, p p21 1.
The PDA has an initial state Oo and main loop state Qoop- It works by maintaining all of the unclosed constituents on the stack, which initially is S. The state Noop is an accept state. For now, we allow the PDA to have one non-scanning transition, 40, S Noop: L.S.
G has the rule - E, we make state qo an accept state.
For each rule in G of the form - a, we add pop transition Ωooop A 4 Qloop.
For each rule in G of the form A + ab, we add new state q, a replace transition Ωooop A - 4, and pop transition q, A 2 Qoop, è. This simply scans two symbols while popping A.
For each rule in G of the form - abB, By where 1, add state q, replace tran- sition [ooop A 2 q, Bp, and push transition g, B, - Noopp BB By-1 .... Bi. These two transitions
13

---

Published as a conference paper at ICLR 2023
equivalent to scanning two symbols while replacing A with ByBp-1... B1 on the stack. Note that we have taken advantage of the fact that 2-GNF affords us two scanned imput symbols to work around the restriction that push transitions of the form 9 r, ryy1 ... yh cannot modify the top symbol and push new symbols in the same step. We have split this action into replace transition followed by push transition, using the state machine to remember what to scan and push after the replace transition.
Finally, we remove the non-scanning transition qo, 1 S Gloop LS, and for every transition Пoops S S r, a,a, we add push transition qu. 1 S r. La. Now all transitions are scanning.
Lemma 5, For any PDA P in the form (15), there is a PDA equivalent to P in restricted form.
Proof. At this point, there is maximum length & such that g. 9 a transition and |a|- We redefine the stack alphabet of the PDA to be I' -rrr....u Stack symbols now represent strings of the original stack symbols. Let [ denote single stack symbol for any string a. We
replace every push transition q, 9 r, r, with push transitions 9. oz T.
0
B
for all E
UN r We replace every replace transition g. x 5 r,y with replace transitions for all And we replace every pop transition q, S r, with replace transitions q. 0:2 for all a with |a| 2 1, and a pop transition
OCE r,
T,E.
So for every CFL L, there exists a restricted PDA P that recognizes L. The last step is to construct an RNS-RŇN. As noted in Section 3, here do allow parameters with values of toc.
Lemma 6. For any restricted-form PDA P that recognizes language L, there is RNS-RNN that recognizes L.
Proof. Let L,t,=
We write ct(w) for the total number of runs of P that read and end with 1 top of the stack. We assume that cr(w) > O; this can always be ensured by adding to P an extra non-accepting state Strap and transitions qu: 1 S quap: 1 and quap: S quap: 1 for all E Σ.
For any state set X C Q, we write cr(w, X) for the total number of runs of P that read w and end in a state in X with 1 on top of the stack. Then for any string w, if w E L. then cr(w, F) 2 1; otherwise, ct(w, F) = 0.
We use the following definition for the LSTM controller of the RNS-RNN, where i,, f,, and o, are the input, forget, and output gates, respectively, and g: the candidate memory cell.
= (WW
X,
+ bb;)
h
f, = oWW
+ bb:)
h/-1
g: = tanh W
X,
+ bg)
h
O: = o (W.
X
+ bo)
h
C, = f @ ---1
1,
④ gr
h, 3 tanh(c.)
Construct RNS-RNN follows. At each timestep f, upon reading input embedding x make the controller emit a weight of for all transitions of P that scan input symbol wi, and a weight of 0 for all other transitions (by setting the corresponding weights of A to -c)).
Let n = [w]. After reading w, the stack reading r,, is the probability distribution of states and top stack symbols of P after reading w, which the controller use compute h and the MI.P
14

---

Published as a conference paper at ICLR 2023
output y follows. Let
c((w, F)
p= Σ n 1)] SEF
ct(w)
Note that p is positive if w E T., and zero otherwise. An affine layer connects h, X and In to the candidate memory cell gn+1 (recall that the input at + 1 is EOS). Designate unit 9 in gn+11 For each f E F, set the incoming weight from r., Tn[(f,,]]] 1]] to and all other incoming weights to O, so that Fn+1 = Lanh(p). Set this unit's input gate and forget gate to O, so that memory cell c44 tanh(p). Set its output gate to 1, so that hidden unit h h tanh(tanh(22) which positive w and zero otherwise.
Finally, to compute use one hidden unit y1 in the output MLP layer, and set the incoming weight from hatt to 1, and all other weights to O. So y1 = (ttan((tanh(p)), which is greater than if w E L and equal to 1/ otherwise. Set the weight connecting Y1 to y to 1, and set the bias term to 2. so that y (((((aan(tanhh())) },), which is greater than 2 if L, and equal to otherwise.
B.2 PROOF OF PROPOSITION 2
Without loss of generality, assume k 2. Let sy and P3 (Q2, E, 2, 0g 82, F2, L. be restricted-form PDAs recognizing L1 and L2, respectively. We can construct both so that Q1 n Q2 = and $1 and 82 each have no incoming transitions. Construct new PDA
P (Q.EIIiUTg,dds.FF
Q = (Q1 (s))) (ss))
(
(
QEQi
8(g,2,0)
82(q,2,,)
g E \ {82)
61(51, (
g=
(F1 \ ( ( (F2 (82))
81 ERE F2 otherwise.
F
((F) \ (s))) (x2))
So far, this is just the standard union construction for PDAs.
Construct an RNS-RNN that sets A according to 6, and assume cr(w) > 0, as in Lemma 6. Let
[[] c(w,F))
Σ
Pt
ct(w)
SEF
ci(w, F2)
P2 = Σ rr[(U,1)
ct(w)
JEF
Let n = -ww] For each Pt, designate a unit accept in ga+1 that will be positive pı > and negative if P1 = 0. In order to ensure that pocens 4 0, we subtract small value from p; that smaller than the smallest possible non-zero value of p.. The RNS-RNN computes this value as follows. Let b [2 1), which is the maximum number of choices P can make from any given configuration. Designate one memory cell coffeet in C₁ At the first timestep, e initialized f. and each subsequent timestep, the forget gate used to multiply this cell by (the input gate is set to 0). So after reading symbols, ceffsct it Set the output gate for that cell to 1, so there is a hidden unit goffeet in h, that contains the value tanh( f
coffset is
). The smallest non-zero value of p; is [w and since c((w) < 6" and tanh(x) < x when x > 0, Aoffset is smaller than it.
As for the incoming weights to accept for each f E F;, set the weight for I,, 1)] to 1, and set the weight for hoffset to 11; set all other weights to O. So Iint1 positive if p; > 0 and negative otherwise. Set this unit's 's input gate to and forget gate to 0, so that accept
tanh(p; p; hoffset which is
accept). ) memory cell ,,141 = accept Set its output gate to 1, so that hidden unit h haceept = tanh(g ( which is positive if p; and negative otherwise.
gin+1
15

---

Published as a conference paper at ICLR 2023
In the output MLP's hidden layer, for each h include unit Ye, and set its incoming weight from hgn+1 to oc, and all other weights to O. So yi = 0 (xt+1), which is p: > 0 and O otherwise. Finally, compute y, set the incoming weights from each y; to and set the bias term to 2. So = o + - 2) which is greater than 2 if both p1 > 0 and pa > 0, meaning E L1 O I22 and less than 2 otherwise.
C ADDITIONAL DISCUSSION OF NON-CONTEXT-FREE LANGUAGES
Below we discuss each of the non-CFLs of Section 4 in more detail, including details of how real-time multi-stack automaton could recognize We also describe three con-CFLs not included in Section 4.
a ab""c" The language {a"b"c" n 2 0}, a classic example of a non-CFL (Sipser, 2013). A two-stack automaton can recognize this language as follows. While reading the a a's, push them to stack 1. While reading the b's, match them with a's popped from stack I while pushing b's to stack 2. While reading the c's, match them with b's popped from stack 2. As the stacks are only needed to remember the count of each symbol type, this language is also an example of counting language; Weiss et al. (2018) showed that LSTMs can learn this language by using their memory cells as counters.
##w #w The language {w w "ofl"##ww # E {.. A two-stack automaton can recognize it as follows. While reading the first w, push it to stack While reading the middle w match with symbols popped from stack while pushing w to stack 2. While reading the last w, match with symbols popped from stack The explicit # symbols are meant to make it easier for model to learn when to transition between these three phases.
#w
" The language [w4"w E recognize it follows. While reading the first w. push it to stack While reading 4", move the symbols from stack to stack 2 in reverse. While reading the final w, match it with symbols popped from stack Unlike Ro the middle #" section offers a model few hints that should push w to the stack beforchand.
2 O, and w = =n. A two-stack automaton can
w#w The language {wit w E [0,1}*), ). A three-stack automaton can recognize this language ur where |u| = |v] (for simplicity assume |w]] is even). While reading the
as follows. Let first u. push it to stack 1. While reading the first push it to stack 2, and move the symbols from stack I to stack 3 in reverse. While reading the second u, match it with symbols popped from stack 3, and move the symbols from stack 2 to stack in reverse. While reading the second v, match it with symbols popped from stack 1. The explicit # symbol is meant to make learning this task easier.
www The language {wo' | w E 1) and w' - )(w), where is the homomorphism Φ(0) A three-stack automaton can recognize this language using a similar strategy to w.w. In this case, a switch to different alphabet, rather than a symbol, marks the second half of the string.
2, <(1)
uw The language (ww"Bw | w E {0, 1).). two-stack automaton can recognize it using a similar strategy to w# #w.
#w. but it must nondeterministical guess [w].
ww The language [ww | w E {0,1}") another classic example of non-CFL (Sipser, 2013). A three-stack automaton can recognize using a similar strategy wil except must nondeter- ministically guess |w/]
D ADDITIONAL DETAILS FOR FORMAL LANGUAGE EXPERIMENTS
Here we describe the training procedure used for the non-CFL and capacity experiments in Sec- tions 4 and 5 in more detail. We trained each model by minimizing its cross-entropy (summed over the timestep dimension of each batch) on the training set, and we used per-symbol cross-entropy on the validation set as the early stopping criterion. We optimized the parameters of the model with Adam. For each training run, randomly sampled the initial learning rate from log-uniform dis- tribution over [5 x 10 x 10_ and we used a gradient clipping threshold of 5. We initialized all fully-connected layers except for those in the LSTM controller with Xavier uniform initialization,
16

---

Published as a conference paper at ICLR 2023
LSTM
Sup. 10
Sup. 3-3-3
Sup.
RNS 3-3
-10-2
a"b"c"
0.3
a a"b"""
Cross-entropy Dift.
Croxs-entropy Diff.
0.2
2
0.1
0
30
60
100
u
Cross-entropy Dift.
0.3
Cross-entropy Diff.
0.4
0.2
0.1
0.2
200
60
100
and Pa
Cross- entropprrppp Dift.
0.4
Cross-entropy ents-eentropy Diff.
0.4
0.2
0.2
0
100
150
200
50
60
70
90
100
Epoch
Length
Figure 5: Performance on three non-CFLs not included in Section 4. Cross-entropy difference in nats, on the validation by epoch (left), and the test set by string length (right). Each line is the best of 10 runs, selected by validation perfomance. All models easily solved a"b"c", As with w w, only multi-stack models (Sup. 3-3-3 and RNS 3-3) solved w*" w. As with ww, models solved " w.
and all other parameters uniformly from [-0.1, 0.1]. We used mini-batches of size 10; each batch always contained examples of equal lengths. We randomly shuffled batches before each epoch. We multiplied the learning rate by 0.9 after epochs of no improvement on the validation set, and we stopped early after 10 epochs of no improvement.
E ADDITIONAL RESULTS FOR NON- CFL EXPERIMENTS
In Fig. 5, we show results for three non-CFLs which we did not include in Section 4. The input and forget gates of the LSTM controller are not tied, so the values of its memory cells are not bounded to (0, and can be used counters. All models easily learned a " likely because the LSTM controller by itself can solve using a counting mechanism (Weiss et al., 2018). Only the models capable of simulating multiple stacks, Sup. 3-3-3 and RNS 3-3, achieved optimal cross-entropy on w & u R w and wa w.. No models succeeded on the unmarked copying tasks (ww Ro and ww), although Sup. 10 achieved the best performance the test set for R..
17

---

Published as a conference paper at ICLR 2023
F ADDITIONAL RESULTS FOR CAPACITY EXPERIMENTS
Here, we describe the languages of Section in more detail, plus an additional language, ww
w#w The language {w#w@ w 10,, -- This a simple deterministic CFL.
Dyck The language of strings over the alphabet { (1, ) 1. (2, 2.-11 (ss ) where all brackets are properly balanced and nested in pairs of (j and ) 4- This is more complicated but still deterministic CFL.
www The language {www w E (0,1,- - 13"} This is nondeterministic CFL which requires model to guess |w]-
In Fig. 6, we show the results of the same experiments as in Section 5, but with standard deviations included. We also show results for the language wwft. In Fig. 7, for the same experiments, we show the minimum cross-entropy difference on the validation set out of all 10 random restarts, rather than the mean. None of the models performed significantly better than the LSTM on the nondeterministic www language, suggesting that they cannot simultaneously combine the tricks of encoding symbol types points in high-dimensional space and nondeterminnstically guessing |w]- Although the VRNS-RNN does combine both nondeterminism and vectors, the nondeterminism only applies to the discrete symbols of I, of which there are no more than 3, far fewer than when A Z 40.
G HEATMAPS OF STACK READING VECTORS
In Fig. 8 we show heatmaps of stack reading vectors across time on an example string in w w when k = 40.
H ADDITIONAL DETAILS FOR NATURAL LANGUAGE EXPERIMENTS
Here we describe the Penn Treebank experiments in more detail. For each architecture, we used word embedding layer of the same size as the hidden state. In order to preserve context across batches, we trained all models using truncated backpropagation through time (BPTT), treating each dataset one long sequence and limiting batches to length of 35. As we noted previously (DuSell & Chiang, 2022), training stack RNNs with truncated BPTT requires bounding the size of the stack data structure, as having it grow indefinitely from batch to batch would computationally infea- sible. We limited the depth of the superposition stack 10, following Yogatama et al. (2018) and our previous paper (DuSell & Chiang, 2022). To limit the size the RNS-RNN, we used the incre- devised previously (DuSell & Chiang. 2022), which limits non-zero
mental execution technique entries in to those where i S D, for some constant window size D. We applied the same technique to the VRNS-RNN by imposing the same limitation both and Ç, restricting non-zero entries of Ç to those where i < D. In both cases, we set / = 35. We used the standard train/validation/test splits for the Penn Treebank.
We trained each model by minimizing its cross-entropy (averaged over the timestep dimension of each batch) on the training set, using per-symbol perplexity on the validation set the early stopping criterion. We optimized the parameters of the model with simple SGD. For each training run, we randomly sampled the initial learning rate from log- ungiurm distribution over [1. 100). and the gradient clipping threshold from a log-uniform distribution over [0.0112, 1.12]. We initialized all parameters uniformly from [-0.05, 0.05). We used mini-batch size of 32. We divided the learning rate by 1.5 whenever validation perplexity did not improve after an epoch, and we stopped early after 2 epochs of no improvement.
18

---

Published as a conference paper at ICLR 2023
LSTM
Sup. VRNS 2-1-3
RNS 1-3
RNS 2-3
VRNS 1-1-3
VRNS 2-3-3
2.5
w
2
Cross-entropy Diff.
1.5
1
0.5
2
40
80
120
160
200
Dyck
1
Cross-entropy Diff.
0.8
0.6
0.4
0.2
0
2
40
80
120
200
2.5
ww
Cross-entropy Diff.
1.5
0.5
0
2
40
80
120
160
200
Alphabet Size k
Figure 6: Mcan cross-entropy difference on the validation set input alphabet size. The shaded regions indicate one standard deviation. We include experiments on "t no models performed significantly better on average than the LSTM baseline.
19

---

Published as a conference paper at ICLR 2023
LSTM VRNS 1-1-3
Sup. VRNS 2-1-3
RNS 1-3
RNS 2-3
VRNS 2-3-3
w#w
1.75
Cross-entrops Diff.
1.5
1.25
0.75
0.5
0.25
2
40
80
120
160
200
Dyck
0.8
Cross-entropy Diff.
0.6
0.4
0.2
2
40
80
120
160
200
2.5
www
2
Cross-entropy Difl.
1.5
1
0.5
2
40
80
120
160
200
Alphabet Size k
Figure 7: Best cross-entropy difference on the validation set vs. input alphabet size. On ## surprisingly, only RNS 2-3 achieved optimal cross-entropy for all alphabet sizes. On the more complicated Dyck language, our new VRNS-RNN (VRNS 2-1-3, VRNS 2-3-3) achieved the best performance for large alphabet sizes. No models performed much better than the LSTM baseline on " although RNS 2-3 performed well for & 40.
20

---

Published as a conference paper at ICLR 2023
Input Symbol
ROS
ROS
(9) 09).0)
()
(g0.0) 9)
(q), 0)
0)
(91.1)
(9..))
(4o.
(90.1)
(49)
(go.
Reading Element
Reading Element
Reading Element
Figure 8: Heatmaps of r, over time on string from w R when h = 40, generated from the best RNS 2-3 model (left) and two other random restarts (middle, right). The wr string repeats the pattern 0123, which is clearly seen in the reading vectors. Black 1, and white 0.
21


Reviews:
[{"review_id": "vGUDw3ab3dC", "reviewer": "Reviewer_ACch", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the properties of nondeterministic stack RNN, and proposes a new version with stacks of vectors. (1) The paper shows that nondeterministic stack RNN can recognize non-context-free languages. (2) The stack RNN with small stack alphabet can recognize languages with a much larger alphabet. (3) RNN with stacks of vectors show improved performance.", "summary_of_the_review": "The paper makes a solid theoretical contribution. The new version with stack of vectors is empirically useful. ", "strength_and_weaknesses": "Strengths: \n\n(1) The paper is theoretically solid. The analysis of the ability of nondeterministic stack RNN in recognizing formal language is a useful theoretical contribution. \n\n(2) The proposed stack of vectors is a useful improvement of nondeterministic stack RNN.\n\nWeaknesses: \n\n(1) The paper relies heavily on the previous paper of DuSell and Chiang, and is not entirely novel. \n\n(2) The experiments mostly compare with baseline LSTM, which may not be a strong baseline. \n\n(3) No discussion of related models such as neural Turing machine. \n\n(4) It is unclear in what sense the model understands natural language. Can it do better than transformer model in terms of language understanding? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "uhLnWZ7zYci", "reviewer": "Reviewer_Gwva", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a part empirical / part theoretical analysis of the representational power of non-deterministic stack RNNs.  It is shown theoretically that renormalizing nondeterministic stack RNNs  (RNS-RNNs) have the power to recognize context-free languages and their intersections (Props 1 and 2).  The ability of RNS-RNNs to recognize context-free languages is investigated empirically, whose performance is shown to surprisingly exceed what might be expected theoretically.  The authors show that the model is using the non-deterministic state of the stack to exceed the limitations that would otherwise exist for a deterministic model (Fig. 3).  This prompts the introduction of a novel architecture, where the stack is allowed to store real vectors rather than only discrete symbols, and it is shown that this representation achieves SOTA performance when modeling real language data in terms of perplexity (Table 1).", "summary_of_the_review": "An interesting investigation of the representational strength of a neuro-symbolic model, combining theoretical and empirical analysis.  The work will be of interest to those working on formal languages, deep-learning and natural language processing.", "strength_and_weaknesses": "Stengths:\n\n-  The paper is clearly presented, and investigates an interesting phenomena.  Particularly, the comparison of neuro-symbolic models' representational strength using formal languages is a promising approach, which is currently under-explored.\n-  The theoretical analysis is thorough,\n-  The empirical analysis is convincing, and provides good motivation for why the vector-valued stack should increase the model's power (essentially by allowing the model to choose the number of symbols stored on the stack).\n\nWeaknesses:\n\n-  The theoretical analysis is essentially the translation of a pushdown automata (PDA) construction into a RNS-RNN, which in itself is not surprising (although useful for determining the dimensions of an RNS-RNN equivalent to a given PDA strength).\n-  It is unclear if there is a specific advantage to using vector RNS-RNNs with its stack memory model in terms of performance as opposed to say models with access to a key-value based memory model, as in a DQN model.  It would be interesting to see such comparisons, both on the formal and natural language data (for the former, one would expect that there are limitations on representational strength imposed by the number of possible keys, but it is not clear how non-determinism would affect this).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "r9kc1egTmGz", "reviewer": "Reviewer_HmX3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the capacity of stack-RNNs, with a particular focus on the existing architecture of the renormalizing nondeterministic stack RNN (RNS-RNN), which they contrast with deterministic stacks. First, they prove analytically that the RNS-RNN is capable of recognizing arbitrary context free languages. Then, they prove that the RNS-RNN is capable of recognizing *intersections* of sets of arbitrary CFLs, which is a language class that is not guaranteed to be context free.\n\nThey then look experimentally at the ability of stack RNNs to recognize 6 specific non-context free languages. They find that the nondeterministic stack architecture can recognize these languages with some additional explicit hints during training, and an architecture with multiple deterministic stacks can recognize these languages if given more hints. They develop a new architecture by using a stack of vectors instead of symbols, and show that it improves perplexity on penn tree bank and learns Dyck languages better.", "summary_of_the_review": "This topic is very niche and might not attract much attention, because it’s such a specific analysis of the capacity of a very specific recent architecture. However, in general people have been paying more attention to questions of computational capacity in neural networks. The result is interesting to me personally: that in theory as well as in practice, the nondeterministic stacks permit the learning of some non context free languages.", "strength_and_weaknesses": "Strengths:\n- This paper is both clear and precise.\n- The computational capacity of neural models in general has seen some increased interest lately.\n- The result is interesting to me personally: that in theory as well as in practice, the nondeterministic stacks permit the learning of some non context free languages.\n- The proposed architecture points to a possible future in which we continue to develop models inspired by discrete symbolic automata, but replacing more and more of them with continuous representations.\n\n\nWeaknesses:\n- This topic is very niche and might not attract much attention, because it’s such a specific analysis of the capacity of a very specific recent architecture. However, in general people have been paying more attention to questions of computational capacity in neural networks, as evidenced by how widely shared https://arxiv.org/abs/2207.02098 (Neural Networks and the Chomsky Hierarchy) recently was.\n- I would like to see a little bit more discussion of the exact level of context sensitivity required for the languages being studied. Are they covered by particular indexed grammars? Can we characterize what particular classes of mildly context sensitive languages can be recognized? \n- PTB, the only “realistic” dataset, is a very weak benchmark if you are using Mikolov’s approach, which has a high rate of unknown token masking and word-level tokenization.\n\nMinor/Questions:\n- It’s not really clear to me what you mean when you talk about needing multiple time steps for the deterministic case.\n- It might be a good idea to briefly explain things like cross serial dependencies. I understand that the target audience probably knows these concepts, though.\n- I felt like I would have benefited from a diagram during the extensive description of all of the different variables involved in these architectures.\n- “Restricted form” doesn’t seem to be defined explicitly, and I’m not sure what makes these forms restricted.\n- Admittedly, my automata theory is somewhat rusty. However, I recall that intersecting context free languages yields an undecidable problem (due to the post correspondence problem). Could you help me understand why undecidability isn’t an issue when you are proving that every intersection of a finite set of CFLs is recognizable by an RNS-RNN?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "iIHcvI9jug", "reviewer": "Reviewer_AKsm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper examines the capacity of renormalizing nondeterministic stack RNN (RNS-RNN), a stack RNN variant proposed by previous work, and proves that it can recognize all context-free languages. It empirically shows that, surprisingly, it performs well in recognizing non-context-free languages, even when the language’s alphabet is larger than the stack’s. To increase its capacity, the paper proposes a new variant that embeds the stack states into vectors and shows that it achieves competitive performance in recognizing large-alphabet formal languages.\n", "summary_of_the_review": "This paper provides new insights into stack RNNs. I vote for acceptance.", "strength_and_weaknesses": "Strength:\n- The paper is fairly clear for how dense it is.\n- The experiments are well-designed to support the claims\n- It provides new insights into the modeling capacity of stack RNNs.\n\nWeaknesses:\n- The paper can be more self-contained. It heavily builds on the RNS-RNN work; for readers unfamiliar with this previous work (like myself), several details need to be verified to examine some of the claims.\n- The results are too weak to back up the claim that “nondeterministic stack RNN can recognize many non-context-free languages.”\n- The empirical contribution is not the paper’s strength. The results are on synthetic experiments or tiny-scale natural language tasks. This could limit the paper’s impact.\n\nDetails:\n- I appreciate the detailed description of RNS-RNN; but there are several details I want to double-check with the authors. Regarding the transition weight function above Eq. 1: can the authors confirm that the transition weight function conditions on the state of the stack, through $\\mathbf{h}_t$? \n- I assume each row of $\\mathbf{W}_a$ can be seen as a vector representation of an action. For example, are “push(x)” and “push(y)” considered different actions and get different representations in $\\mathbf{W}_a$?\n- Following the above: if “push(x)” and “push(y)” get different vector representations, each symbol is already embedded into a vector representation. If this is the case, can the authors comment on why it is surprising that RNS-RNN can recognize CFLs with large alphabets?\n- How does the theoretical result in Section 3 connect to existing conclusions on real-time PDA and context-free languages ([1] and the older works cited therein)?\n- Regarding the results in Figure 1: even the best stack RNN variant (RNS 3-3) achieves mixed results compared to the LSTM baseline (outperforms in 2 languages and underperforms in others). The framing is too strong that stack RNNs can recognize “many” non-context-free languages.\n- I would appreciate it if the paper could include an evaluation of non-context-free languages with large alphabets.\n- Missing references: using vector states in automata was explored in [2] and [3]\n\n[1] https://arxiv.org/pdf/1302.1046.pdf\n\n[2] https://arxiv.org/abs/1805.06061\n\n[3] https://arxiv.org/abs/1808.09357\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster