Pushdown Layers: Encoding Recursive Structure in Transformer Language Models
Authors: Shikhar Murty
Pratyusha Sharma
Jacob Andreas
Christopher D Manning
Venue: EMNLP 2023 Main (2023)
Keywords: recursive structure
syntactic language models
generalization

Abstract: Recursion is a prominent feature of human language, and fundamentally challenging for self-attention due to the lack of an explicit recursive-state tracking mechanism. Consequently, Transformer language models poorly capture long-tail recursive structure and exhibit sample-inefficient syntactic generalization. This work introduces Pushdown Layers, a new self-attention layer that models recursive state via a stack tape that tracks estimated depths of every token in an incremental parse of the observed prefix. Transformer LMs with Pushdown Layers are syntactic language models that autoregressively and synchronously update this stack tape as they predict new tokens, in turn using the stack tape to softly modulate attention over tokens---for instance, learning to ``skip'' over closed constituents. When trained on a corpus of strings annotated with silver constituency parses, Transformers equipped with Pushdown Layers achieve dramatically better and 3-5x more sample-efficient syntactic generalization, while maintaining similar perplexities. Pushdown Layers are a drop-in replacement for standard self-attention. We illustrate this by finetuning GPT2-medium with Pushdown Layers on an automatically parsed WikiText-103, leading to improvements on several GLUE text classification tasks.

Pushdown Layers: Encoding Recursive Structure in Transformer Language Models
Shikhar Murtyl Pratyusha Sharma' Jacob Andreas
Christopher D. Manning!
*Computer Science Department, Stanford University MIT CSAIL
(smurty, manning) stanford. edu, {pratyusha, jda] edu
Abstract
The dog
in the park
Recursion is a prominent feature of human language, and fundamentally challenging for self-attention due to the lack of an explicit recursive-state tracking mechanism. Conse- quently, Transformer language models poorly capture long-tail recursive structure and ex- hibit -inflce-nefficceett syntactic generaliza- tion. This work introduces Pushdown Layers, a new self-attention layer that models recur- sive state via stack tape that tracks estimated depths every token in an incremental parse the observed prefix. Transformer LMs with Pushdown Layers are syntactic language mod- els that autoregressively and synchronously up- date this stack tape they predict new tokens, in turn using the stack tape to softly modu- instance, learn- ing to "skip" over closed constituents. When trained on corpus of strings annotated with sil- ver constituency parses, Transformers equipped with Pushdown Layers achieve dramatically better and 3-5x more sample-efficient syntac- tic generalization, while maintaining similar perplexities. Pushdown Layers are drop-in replacement for standard self-attention. lustrate this by finetuning Pushdown Layers on an automatically parsed WikiText-100 103, leading improvements on sev- eral GLUE text classification tasks.
park
(c)
000
000
000
000
000
00
000
000
000
attention over tokens
(b)
hg
h!
h


The
dog
in
the
(a)
0
0
0
The dog in the
with
Figure I: (a) Pushdown Layers use a stack-tape to fea- turize contents of an explicit stack, terms of estimated token depths. where the stack represents incremental parses. (b) These depths map onto depth embeddings (in blue) that added token keys before computing attention scores, softly biasing attention towards re- cursive syntactic computation. (c) stack updated synchronously with the newly predicted word, via attachment head that selects a constituent to reduce the newly predicted word with, attention.
1 Introduction
An important property human language and thought is recursion, which allows us to compose and reason about complex objects in terms of sim- pler constituents (Hauser et al., 2002). While ex- tensively studied in natural language syntax and semantics, recursion is also key component of sev- eral other aspects of intelligent behaviors including mathematical reasoning, programming, and goal- directed planning. Most recursi systems model recursive processes via a stack memory, which is updated as new computation is performed.
For instance, programming language may imple- ment recursion by maintaining run-time stack of caller-callee frames, storing intermediate outputs in the stack, and updating the stack as new func- tion calls are made. Similarly, a shift-reduce parser implements recursion through a stack of intermedi-

---

ate constituents, shifting tokens onto the stack as they are observed, and occasionally reducing stack elements into constituents as they are completed. In contrast, the self-attention mechanism under- lying modern neural sequence models has no plicit mechanism to maintain stack memory it generates strings, and instead relies on hidden rep- resentations implicitly but imperfectly encode such information (Manning et al., 2020). While this encoding can model bounded recursive structure in formal languages (Yao et al., 2021), it is unclear if it is sufficient for robust syntactic generalization, especially under data-constrained settings.
ization improvements over standard Transformer LMs. When trained on depth-bounded Dyck strings and evaluated on deeper Dyck strings, Pushdown Transformers improve performance over baselime LMs by over 23% (Section 4.1). When trained on sentence-level language modeling on the BLLIP- LG datasets of Hu et al. (2020), Pushdown Trans- formers improve syntactic generalization over stan- dard Transformer LMs by 5-13 points well other joint models of strings and parses such as Qian (2021); Sartran et al. (2022) by 0.3- points (Section 4.2). When trained on a new, 100-million-tokee dataset of parsed Wikipedia ar- ticles we call WIKITREES, Pushdown Transform- ers match the syntactic generalization of ordinary Transformers with 3-5x less data. Finally, when Pushdown Layers are inserted into pre-traine pre-trained GPT-2 (medium) model and fine-tuned on WIK- ITREES they yield improvements of 0.3-1 points on several GLUE text classification tasks.
In this work, we show that an explicit stack mem- ory mechanism can improve syntactic generaliza- tion in Transformer language models (LMs). We in- troduce Pushdown Layers', drop-in replacement for standard self-attention that augments Trans- former LMs with stack memory. This memory is modeled using a stack lape that stores estimated depths of every token in an incremental parse of the observed prefix. The stack tape is updated autore- gressively: as new tokens are predicted, Transform- ers with Pushdown Layers (Pushdown Transform- ers) synchronously make probabilistic attachment decisions to either "shift", thus ussigning the newly predicted token a depth of O, or "reduce" with one of the constituents in the prefix far, updating to- ken depths accordingly (see Fig. 1). This stack tape is used additively and softly modulate the atten- tion the Transformer over tokens for instance, Pushdown Layers may guide the LM to only attend to head words of constituents, or skip over reduced constituents by decreasing attention.
Background
Multi-Head Self-Attention. Transformer lan- guage models (Vaswani et al., 2017) are class of neural sequence models that use multi-head self-attention to obtain contextualized represen- tations of tokens in a sequence, which are then used to predict the next token. In particular, let = {z1, T2, Fn. be an input sequence. Let h! Rd be the hidden representation of the 7th token at the 1th attention block. Then, the hidden representation of the 7th token is updated
N = FF(O (ATO-))) Ak(h
Pushdown Transformer LMs are syntactic lan- guage models that learn joint probabilities of se- quences and parses in terms of individual word predictions and structure- bruuctur-builddng operations, and can be trained on any text corpus annotated with constituency parses. But unlike other syntactic lan- guage models with structural supervision (Vinyals al., 2015; Choe and Charniak, 2016; Qian et al., 2021: Sartran et al., 2022), Pushdown Layers do not change the output space of the underlying se- quence model, and impose no constraints on atten- tion mechanisms manner in which Pushdown Layers use syntactic structure for representation building is learnt purely via gradient descent.
where O E Rdxd is a learnt matrix, FF denotes a feed-forward + residual + layer-norm block, and Ap is the pd self-attention head. Each attention head performs weighted average over its inputs,
(p Σ
aig W hy.
(2)
where aij is the attention weight assigned the jth token by the 7th token. These attention weights are computed as
aij softmax((WP)))) h() Tw ht].
(3)
Pushdown Transformers obtain strong general-
Each self-attention head introduces learnt param- eters W.P Wauery: W
WWe borrow this term from pushdown automata, which are finite state machines augmented with stacks.
value E dd/Kxd
key

---

Limitations of Self-Attention. When trained on text corpora, transformers implicitly encode sev- eral aspects of linguistic structure unsupervisedly (Clark et al., 2019; Hewitt and Manning, 2019; Murty et al., 2023). However, there is mounting evidence that recursion, a key feature of human language, remains challenge. Hahn (2020) shows theoretically that hard-attention cannot model sim- ple recursive structures like 2DYCK (see Section 6 for an extended discussion). Empirically, Lakretz al. (2022) show that self-attention struggles on center embedding phenomenon, and Zhang et al. (2023) show poor performance on simple recursive tree-traversal problems. We hypothesize that a key reason for poor modeling of recursive structure in self-attention is lack of an explicit structural in- ductive bias. One common way to add such inductive bias is via joint modeling of strings and syntactic structure, which we introduce next.
head. Second, inference in neural models operat- ing on transitions require bespoke decoding proce- dures that carefully balance tradeoffs between high- entropy word-level predictions and low-entropy structural predictions (Stern et al., 2017). Finally, to explicitly bias Transformer computations to mir- ror the recursive structure of parse trees, some ap- proaches like PLM-mast (Qian et al., 2021) and 'Gs (Sartran et al., 2022) impose hard constraints on attention patterns. Pushdown Layers provide a softer syntactic bias that is amenable to gradient- based learning, while having broader applicabil- ity to phenomena beyond local tre-sttrucuuredness. such as topical dependencies, coreference, etc.
3 Pushdown Layers
Transformer LMs with Pushdown Layers are syn- tactic language models that generate strings while simultancously building a parse tree over these strings from left to right. This parse tree is built incrementally by tracking the recursive state of ev- ery token, which is synchronously updated along with word-level predictions. This recursive state is represented via our stack tape as tree-depths of every prefix token, and updates are realized with a stack. The contents of the stack tape are used to softly modulate attention over prefix tokens via additive offsets to attention logits (Fig. 2).
Syntactic Language Models. Let y be the ground-truth syntactic parse of x. A long line of work (Vinyals et al., 2015; Dyer et al., 2016; Choe and Charniak, 2016; Qian et al., 2021; Sartran et al., 2022) considers learning joint distributions p(ar, y) incorporate explicit syntactic structure into neu- ral language models, by learning to output a se- quence of transition actions,
p(a, v) p(azy) II p(a; acs))
3.1 Stack Tape
Like ordinary self-attention, Pushdown Layers take sequence of hidden states (hk} as input, and out- put sequence (h/-1), Additionally, Pushdown Layers use a stack tape Wj E &.* to simulate a pushdown automaton that performs shift/reduce op- erations over tokens as they are predicted (Fig. 2). The contents of the stack tape encode recursive state by tracking the depth of each token within reduced constituents in the stack. Concretely, af- ter observing the prefix 2gk { #2, ....... ... 2x }. W& = 0 if token zy has not been reduced with any other token, while WiDi = p means that æ has appeared in p reduce operations such that the resulting constituent has token xÿ at depth p in Fig. 2, the stack tape encodes [1, 1, 0] for the incremental parse [The dog] is.
where actions a, correspond both word-level pre- dictions as well as structural actions corresponding to opening and closing of constituents, building up the parse tree in a top-down, left-to-right manner. Recent work explores using Transformers to param- eterize these joint distributions. For instance, Qian et al. (2021); Sartran et al. (2022) train Transformer LMs over transition actions (Parsing as Language Modeling or PLM), sometimes with constrained at- tention heads -mak)),,)k,.... and Transformer Gram- mars (TG; Sartran et al., 2022) model transition ac- tions with Transformers, also with hard constraints on attention to model shift/reduce actions.
These models have several limitations that moti- vate our proposed approach. First, their outputs are sequenees of transition actions that include both text and tree-building operations; as each con- stituent in a parse tree has an opening and closing transition action, and there are R constituents for x, this increases input length by factor of 3, lead- ing to significant computation and memory over-
Updating the Stack Tape. As shown in Fig. 2. along with predicting the next word happy, Trans- formers with Pushdown Layers (Pushdown Trans- formers) make an attachment decision to update their stack tape. In our running example, this is

---

Algorithm 1: Stack Tape Update
The dog
The dog is
The dog is happy
Input: Wk 1, k, rks stack
Output: Wa. stack
dog
happy
UpdateStackTape( rhe stack)
We + W4
consti constituent tuent + [
The
The dog
The dog 18
rx = k then
stack. s (ubsck.pshhconnttituuen))
return end
Figure Illustration of how the parse [[The dog [is kuppyl] is built as unique sequence of stack-tape up- dates Pushdown LMs. Here, as the word happy is predicted, the attachment head chooses constituent (bolded) from the current incremental parse, via atten- tion. Attachment decisions are made to constituents by attending to their rightmost token, and none of the other tokens of constituent can be attended to (shown as dashed lines). These attachment decisions are used to update depth values in the tape.
while True do top + stack..cppp)) // Perform a reduce
constituent <- top + consti I1 Update depths in stack tape
forall constituent do W& end
if top == rs then break
done by selecting a constituent from the incremen- tal parse [The dog] is happy.
end end
Concretely, given prefix Teck Pushdown Trans- formers predict the next token Iy well update to the stack tape W3-1. This is done by se- lecting a token r% to reduce with, out candidate ..)... via attention over hidden states (h h2 n 1i11: h where L is the nal layer of the Transformer, and hig is vector representation for the newly predicted token æk= obtained as h MLP(# 1 This vector attends to all tokens to make a probabilistic attach- ment decision,
stack. stack.push(com) cownoiittsstttt
3.2 Computing Attention Scores
tokens {x1, .2...... Fkj.
We map contents of WA onto per-layer depth embedding d' for every token j E (0, 1....... k)). These depth embeddings keys, resulting in a locally additive modulation attention scores,
added to attention
kg = softmax((1, + dlyg [ Whey Wquery ht)
(6)
p(rk- 5 Feki Wk-1) & i * k. shift reduce shift only
Of course, since these logits are themselves part of softmax and non-lincarities, the overall effect can be arbitrarily non-lime non-linear. These modified attention weights are used to compute contextualized vectors using Eq 2 and Eq 1.
(T (heT (T h
(5)
where W Raxd a learnt parameter ma- trix. We use these probabilities to select token = arg sagmaxpl p(j Teki Wx-1) to reduce Tyk with, and the stack tape is updated accordingly via Algorithm 1. Note that attachment decisions to constituents made by computing the attachment score for the rightmost token in the constituent. In our running example, the model selects the con- stituent [The dog] by selecting the word dog, form- ing the parse [[The dog] [is happy]] and updating the stack tape from [1, 1, 0] [2, 2, 2, 2].
3.3 Training and Inference
Training. Given a corpus of strings annotated with parses, we first extract ground-truth values of Wj for every prefix Tgg.- We also extract ground- truth attachment decisions for I'k given prefix T>ck- With these quantities precomputed, we can train Pushdown Transformers parallel, like standard Transformers. Attachment probabilities (Eq 5) are supervised with ground-trui trudh attachments, along with the standard LM objective, all using hidden

---

states that are contextualized using the Pushdown Layer attention mechanism that uses the precom- puted stack tape.
Thus, token at position builds its representation based on attending Tza with stack tape that may soon become "stale" due to future transition opera- tions that reduce tokens in Igi with new tokens. As an example, suppose we have the incremental parse [[The dog] [in [the park]l]. Here, the representation for in attends to representations of The, dog and in with depths [1, 1, 0] while the representation for park attends to these representations with updated depths [2, 21.
Inference. For any string a and parse joint probability p(x, y) factorizes product of word- level and attachment scores
a
y)x,y)
II (p(ona meki Wk x)x k=1
p(rk I res Wa-1)).
(7)
Experiments
While computing the full marginal p(x) Eg p(z, y) computationally infeasible due to the large space of possible parses, we approximate this by marginalizing over a smaller subset with beam search. Crucially, since our model predicts words and structural actions in parallel rather than sequentially. we do not need to use complex word- synchronous decoding procedures (Stern et al., 2017) that introduce additional hyperparameters.
4.1 Warm-up: Dyck Languages
We train 6 layer LMs with Pushdown Layers (Pushdown-LM) well as standard LMs on 100k strings sampled from DYCK20,10: the language of well-nested brackets with 20 bracket types and max max-nesting depth of 10. To ensure that improve- ments are not merely due to multi-task learning with an attachment head, base-LM is also trained with an attachment loss in a standard multi-task learning setup. To test generalization, models are provided input prefix from separate DYCK language, and evaluated on choosing the correct closing bracket. Specifically, we test generalization to DYCK strings with deeper nesting of 15-50, and DYCK strings with longer-range dependencies than seen at training time (measured as the distance to the matching bracket that needs to be closed). From Table 1, we find that Pushdown-LM obtains over 25% accuracy point improvement over standard language models at generalizing deeper struc- ture, as well as large improvements at generalizing to longer-range dependencies.
3.4 Implementation Details
FLOPs and memory overhead. Consider query and key matrices Q E Ra K E Rd where ny and ny refer to destination (hidden states at- tending) and source (hidden states being attended to). Let S E Ruaxxs be the (lowerttriangular) matrix denoting pre-computed stack tape values for every prefix. For each Pushdown Layer, S index into depth embeddings obtain obtain
D RRaax, which added KD E Reaxn,xd Unlike standard self-attention which multiplics Q and K dircetly, Pushdown Lay- ers multiply Q (a 2D tensor) with Kp (a 3D ten- sor). This is done by casting Q into a 3D ten- sor E IR=axlxd and performing batched ma- trix multiplication with KD. leading to the same number of operations as standard self-attention' However, since Pushdown Layers require storing 3D tensors for keys, this increases memory re- quirements from O T1 + ng + ny d) to O(n n, + ng Ri + ny d). We provide stan- dalone code for implementing a Pushdown Layer block in Appendix D.
Base-LM
Pushdown-LM
Long RangeRange Dependencies
DYCK (50)
90.0
96.5
Dyck (100)
81.0
88.0
DYCK (200)
40.6
61.2
DYCK (300)
14.1
42.9
Deeper Embedded Structure
Depth Gen.
40.6
68.3
Attending to hidden states with old memory. Pushdown Transformers build parse trees incre- mentally from left-to-right, and so, depth values of prefix tokens change as new tokens are predicted.
Table 1: Evaluating LMs closing Dyck prefixes with longer dependencies (dep. length in brackets) and deeper structure. We find significant improvements from using Pushdown Layers over standard self-ate attentio...
We note that standard self-attention is faster in practice due to hetter GPU memory handwidth management,

---

100
Base-LM
Pushdown-LM (ours)
80
Accuracy
60
40
20
Agreement
Center Embedding
Garden-Path Path Effects
Gross Syntactic State
Licensing
Long-Distn Distance Dependencies
Long
Figure 3: Comparing Pushdown-LMs with baseline Transformer LMs and other syntactic LMs. While Pushdown- LMs are comparable with Transformer Grammars (TG; Sartran et al., 2022) across all examples in SG test suites (Table 2), they outperform TGs on out of tests, including the recursive center embedding tests.
4.2 Sentence-Level Language Modeling
step t. We fix the beam size at 300.
Results. We present results on SG suites Figure 3. As baselines, we compare against a standard 16 layer Transformer LM and prior struc- tured models (TG, PLM) from Sartran et al. (2022). As expected, all models with an explicit notion of structure have much better syntactic general- ization across all test suites. Next, note that Pushdown-Lan -LM, 16 layer Transformer LM with all self-attention blocks replaced with Pushdown Layers, outperforms prior Saarracchss-Pushheee LM beats TG on 4/6 tests and PLM on 3/6 tests with similar performance on licensing. Next, we present results (averaged across seeds) on BLIMP as well as aggregate SG test suite results and per- plexity on the BLLIP test set in Table 2. Here. note that Pushdown-LM achieves better syn- tactic generalization than prior structured models (including the PLM-mask model from (Qian al., 2021)) on BLIMP. Finally, we find that Pushdown- LM achieves slight gains in perplexity compared to Base-LM.
Setup. Next, we train 16-layer Pushdown Trans- former LMs on the BLLIP-IG dataset Charniak et al. (2000), with training splits from Hu et al. (2020), and the same pre-processing as Qian et al. (2021). We use the same hyperparameters (model size, dropout, learning rate schedulers) Sartran al. (2022). To measure syntactic generalization, we evaluate on BLIMP (Warstadt et al., 2020) and the SG test suites (Hu et al., 2020). In BLIMP, models are provided with a grammatical and un- grammatical sentence, and evaluated on assigning a higher probability to the grammatical sentence. SG test suites consist of an extensive set of hand- crafted test cases, covering 6 fine-g fine-grained syntactic phenomena. Each test case involves satisfying specific inequality constraint among surprisal val- ues of various continuations given prefixes, where these inequalities are grounded in theories of in- cremental language processing-for instance, as- signing a higher surprisal to the last verb in The painting that the artist deteriorated painted vs. The painting that the artist painted deteriorated. For BLIMP, obtain p(x) by approximate marginal- ization via beam search. Since surprisal values log p( (xet) in SG test suites are meant to re- flect incremental sentence processing, we perform marginalization based on the beam state at time
4.3 Language Modeling with WIKITREES
Can Pushdown Layers continue offer improve- ments on larger-scale language modeling? We con- struct WIKITREES, a dataset of over 100 million to- kens extracted from Wikipedia Articles (WikiText-

---

Model
BLIMP
SG test suites
PPL
GPT2-small (-98 tokens)
80
Models that add structural tokens inputs
Syntactic Generalization
75
PLM
75.1
80.2
29.8
70-
PLM-Mask
75.3
78.3
49.17
TG
82.5"
30.3
65
Models do not add extra tokens inputs
60
Basc-LM
70.1
69.5
20.1
55
Pushdown-
Pushdown-LLk (ours)
75.6
82.3
19.9
Base-LM
0.2
0.6
10
Table 2: Syntactic Generalization on BLIMP and SG test suites. All results for PLM-Mask are taken from Qian at. (2021) and results for PL.M and TGs taken from Sartran et al. (2022). denotes differences that are not significant. PPI. results marked with $ are taken from prior work and not comparable due to differences in tokenization.
Number of Tokens
1eB
Figure 4: Comparing standard GPT-2 small archi- tecture (Base-LM) with model where the last self- attention blocks use Pushdown Layers, trained on vari- ous amounts of tokens from WIKITREES. We find that Pushdown Layers greatly improve sample efficiency of syntactic generalization. For reference, we also include GPT2-small, which is trained on over 9 billion tokens.
103: Merity et al. (2017)), parsed automatically using a state-of-the-ee neural constituency parser (Kitaev et al., 2019). Typically, LMS trained on web-scale data are given multi-sentence contexts with large window sizes as inputs, and to adapt this to Pushdown-LMs we make small number of modifications (see Appendix B for details).
WIKITREES. We this model to obtain parses on text classification tasks: RTE, SST5, MRPC and STS-B from GLUE (Wang et al., 2019a), and use these parses to pre-compute the stack tape for every token. Then, in second finetuning step, Pushdown-GPPe is trained to perform text classi- fication over these datasets by reducing each task into language modeling via prompting (See Ap- pendix A for prompt details). As a comparison. also perform the same staged finetuning for the standard GPT2-medium architecture. We report averaged results across seeds in Table We find that Pushdown Layers offer improvements on 3 out of 4 text classification tasks.
Sample-Ffficient Generalization. To measure sample efficiency in Pushdown Transformers, we train LMs on [10M, 50M, 100M] tokens from WIK- ITREES. To ensure stable training under low data regimes, we train 12 layer GPT2 using the exact configuration and tokenization scheme as GPT2- small (Radford al., 2019), and additionally use dropout to prevent overfitting. For these experi- ments, we compare Basc-LM with an LM where the final self-attention blocks are Pushdown Lay- ers (Pushdown-LM)). To measure syntactic gener- alization, we compute aggregate performance on the SG test suites. From results in Fig. 4, we find that Pushdown-LMs exhibit drastically more sample-efficient syntactic generalization for in- stance, syntactic generalization of Pushdown-LM trained on 10M tokens requires over 40M tokens for the Base-LM to surpass.
Model
RTE
SST5
MRPC
STS-B
GPT2
72.2
54.8
88.4
89.6/89.8
Pushdown GPT2
72.9
89.3
89.8/90.1
Table 3: Finetuning models on various semantic text classffication/regrssioo tasks. We report accuracy for RTE and SST5, F1 for MRPC. and Spearman/Pearson Correlation for STS-B.
Finetuning for text classification. Can Push-
Analysis
down Layers offer improvements on language un- derstanding tasks, beyond syntactic generalization? To answer this, we perform staged finetuning of GPT2-medium with Pushdown Layers. Specifi- cally, we finetune GPT-2 medium with the final 12 self-attention blocks replaced with Pushdown Layers GPTsh) as a language model on
For all analyses, we use the 16 layer Pushdown-LM trained on BLLIP-IG from Section 4.2.
Parsing, Since Pushdown-LM a syntactic lan- guage model, we obtain parses via beam search (beam size 300) to approximately recover the most likely parse y = arg max, p(x, v) under our

---

tasks, models are presented with prefix consist- ing of main subject and distractor embedded subject, where these items conflict in number. The objective is to assign a higher logprob to the verb that agrees with the main subject rather than the distractor subject. For instance, for prefix The au- thor that hurt the senators, the model must assign higher probability to is than are.
Avg. Attention over distractor token
0.08
From Fig. 3, we find that Pushdown-LM sig- nificantly outperforms other models with close to 80% accuracy while Base-LM achieves less than 60% accuracy. To understand how Pushdown Lay- ers modulate attention on these examples, we ob- tain attention scores over all prefix tokens (aver- aged across all layers). We present the average attention assigned to the distractor token for both Pushdown-LM and Base-LM Fig. 5 where we observe that Pushdown-LM pulls attention away from the distractor noun, allowing it to predict the correct verb. Finally, we plot some (averaged) at- tention heatmaps in Fig. 6.
number_orc number_prep
number_sic
Figure For the three subject-verb agreement tasks from (Marvin and Linzen, 2018), we compute average attention over the distractor noun when the verb is be- ing predicted, for both the Base-LM and Pushdown-LM (ours). Across all variants, we find that our model con- sistently pulls attention away from distractor nouns.
model. However, since this parse is (a) unlabeled and (b) binarized, perform unlabeled Fl eval- uation (using EVALB; Collins, 1997) over binarized ground-truth parses from the PTB test set. We also remove instances consisting of unknown words for our model, since our model is trained without any UNK tokens, giving us 2335 out of 2416 sentences. We compare our model against Kitaev et al. (2019), the parser that was used to annotate training data for Pushdown-LM. We also present unlabeled Fl on the auto-parsed BLLIP-LG test set. From re- sults in Table we note that our model achieves very competitive unlabeled Fl score of 95.3, out- performing the official implementation of Kitaev et al. (2019)3. We also find that our model obtains a high Fl score of 97.3 on the BLLIP-LG test set.
Other Related Work
While recursive structure is fundamental to natu- ral language, modeling such structure is difficult for self-attention. Hahn (2020) considers DYCK, the simplest formal language with recursive struc- ture, proving that hard attention cannot recognize DYCK and soft attention cannot recognize DYCK with low cross-entropy. In practice, we find that even simpler languages like PARITY are challeng- ing for encoder-only Transformers (Chiang and Cholak, 2022: Bhattamishra et al., 2020). On the other hand, Transformers with decoders have been shown be Turine-complete (Perez et al., 2021), but these constructions rely on the impractical as- sumption of running the decoder for an unbounded number of steps. In practice, we find that Trans- former LMs struggle with generalization beyond regular languages and tend to learn shortcuts in- stead (Deletang al., 2023; Liu al., 2023).
Model
PTB
BILIP-LC
Pushdown-LM
95.3
97.3
(Kitaev et al., 2019)
94.7
Table 4: Unlabeled F1 scores against binarized ground- truth parses from the PTB and BLLIP test sets. We filter examples from the PTB test set with unknown words, giving us 2335 out of 2416 sentences. Annotations BLLIP-LG are obtained using Kitaev et al. (2019).
Given these limitations, there is significant in- terest in inductive biases that encourage recursive structure in Transformers. One line of work con- siders constraining alffattention patterns accord- ing to syntactic parses (Strubell et al., 2018; Wang et al., 2019b; Peng al., 2019; Deshpande and Narasimhan, 2020, among others). second line of work adds structure to language modeling by learning joint probabilistic modeling of structure and strings (Chelba, 1997; Mirowski and Vlachos,
Case Study: Analyzing attention patterns on subject-verb agreement tasks. We consider the 3 Subject- Verb agreement tasks (Marvin and Linzen, 2018) from the SG test suites. On these
We use the benepar_en la_large model from https:// gi attthb.ccomnikiii..... com/nikitakit//elll httt://ellatttttiieeeeeeeee
which reports a score of 96.29 on the full PTB test set, while we obtain 95.66 (labeled F1, using the standard EVALB script).

---

Base-LM
manner, but unlike prior work, the specific design of Pushdown Layers makes training parallclizable. Finally, there have been several efforts add syntactic inductive biases into sequence models (typically RNNs) that can acquire and use parse structures in an unsupervised manner (Bowman et al., 2016; Shen et al., 2019; Drozdov et al., 2019; Kim et al., 2019, among others). We leave unsuper- vised training of Pushdown Transformers for future work.
Layer
[Sos] The authors
that
hurt
the
senator
Conclusion
Pushdown-LM
We propose Pushdown Layers, a new kind of self- attention that augments Transformer language mod- els with stack based memory. Pushdown Layers enable augo-regressive Transformers to softly bias attention towards recursive syntactic computation. through updatable stack-tape that stores token depths in incremental parse. When trained synthetic and natural languages, we find that Trans- former LMs with Pushdown Layers achieve better gencralization to deep recursive structure, as well as better and more sample-efficient syntactic gen- eralization. When pre-trained LMs are finetuned with Pushdown Layers, we obtain improvements some GLUE tasks.
Layer
[SOS] The authors
that hurt
the
senator
Figure 6: Given prefix containing main noun and a distractor noun, Pushdown-L.M pulls attention away from the distractor (here senator), helping the model predict the verb with the correct number. These attention maps average across the instances in the number_st test of SG test suites, and show the attention over all prefix tokens when the main verb is predicted
8 Reproducibility
Code and data for these experiments is available at http:////habbaaa..///aa/ahha/aaa
Limitations
2015; Choe and Charniak, 2016; Dyer al., 2016, among others). Both of these ideas are combined in recent work of Qian et al. (2021); Sartran et al. (2022), that proposes joint string, parse Trans- former language models with constrained attention patterns. While Pushdown Layers are also in this modeling tradition, we do so without operating long transition actions, and enforce structural constraints via gradient based learning.
Pushdown Layers require constituency-parse anno- tated datasets, which may not be available for many languages due to a lack of high performing off-the- shelf constituency parsers. This also limits appli- cability to domains beyond natural and synthetic languages, such as algorithmic reasoning. Finally, Pushdown Layers can only be applied to languages with constituency structure, and our experiments are limited to English.
separate line of work proposes neural net- works augmented with structured memory like stacks (Das et al., 1992; Grefenstette et al., 2015; Joulin and Mikolov, 2015; DuSell and Chiang, 2022) or random access memories (Kurach et al., 2015). Such augmented neural networks are vastly better algorithmic generalization and learning recursive structure (Suzgun et al., 2019; Deletang al., 2023). Our work is the first that designs structured memory (the stack-tape) for Transform- ers, that is updated just like stacks shift/reduce
Acknowledgements
SM was funded by a gift from Apple Inc. CM is fellow in the CIFAR Learning in Machines and Brains program. PS and JA are funded by Project CETI via grants from The Audacious Project: collaborative funding initiative housed TED. We thank John Hewitt, Sidd Karamcheti and Róbert Csordás for feedback and discussions.

---

References
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.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. On the Ability and Limitations of Transform- ers to Recognize Formal Languages. In Proceed- ings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7096-7116, Online. Association for Computational Linguistics.
Ameet Deshpande and Karthik Narasimhan. 2020. Guiding attention for self-supervised learning with transformers. In Findings of the Association for Com- putational Linguistics: EMNLP 2020, pages 4676- 4686.
Samuel Bowman, Jon Gauthier, Abhinav Rastogi, Raghay Gupta, Christopher D Manning, and Christo- pher Potts. 2016. A fast unified model for parsing and sentence understanding. In Proceedings of the 54th Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), pages 1466-1477.
Andrew Drozdov, Patrick Verga, Mohit Yadav, Mo- hit lyyer, and Andrew McCallum. 2019. Unsuper- vised latent tree induction with deep ouside-outside recursive auto-encoders. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 1129-1141.
Eugene Charniak, Don Blaheta, Niyu Ge, Keith Hall, John Hale, and Mark Johnson. 2000. Bllip 1987-89 wsj corpus release Linguistic Data Consortium, Philadelphia, 36.
Brian DuSell and David Chiang. 2022. Learning hierar- chical structures with differentiable nondeterministic stacks. In International Conference on Learning Rep- resentations.
Ciprian Chelha. 1997. A structured language model. In 35th Annual Meeting of the Association for Compu- tational Linguistics and 8th Conference of the Euro- pean Chapter of the Association for Computational Linguistics, pages 498-500.
Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith. 2016. Recurrent neural network grammars. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguisticy: Human Language Technologies, pages 199 209, San Diego, California. Association for Computational Linguistics.
David Chiang and Peter Cholak. 2022. Overcoming a theoretical limitation of attenion Proceed- ings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pa- pers), pages 7654-7664, Dublin, Ireland. Association for Computational Linguistics.
Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. 2015. Learning transduce with unbounded memory. Advances in neural information processing systems, 28.
Do Kook Choe and Eugene Charniak. 2016. Parsing as language modeling. In Proceedings of the 2016 Conference on Empirical Methods Natural Lan- guage Processing, pages 2331-2336, Austin, Texas. Association for Computational Linguistics.
Michael Hahn. 2020. Thcoretical Limitations of Self-
Attention in Neural Sequence Models. Transactions of the Association for Computational Linguistics, 8:156-171.
Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher Manning. 2019. What does BERT look at? an analysis of BERT's attention. In Pro- ceedings of the 2019 ACL Workshop BlackboxNLP. Analyzing and Interpreting Neural Networks for NLP. pages 276-286, Florence, Italy. Association for Com- putational Linguistics.
Mare D. Hauser, Noam Chomsky, and W. Tecumseh Fitch. 2002. The faculty of language: What is it, who has it, and how did it evolve? Science. 15655999):156-11777
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 Pupers), pages 1139,4 Minneapolis, Minnesota. Association for Computational Linguistics.
Michael Collins. 1997. Three generative, lexicalised models for statistical parsing. In 35th Annual Meet- ing of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguisties, pages 16- 23.
Sreerupa Das, C Lee Giles, and Guo-Zheng Sun. 1992. Learning context-free grammars: Capabilities and limitations of recurrent neural network with an ex- ternal stack memory. In Proceedings of The Four- teenth Annual Conference of Cognitive Science Soci- ety. Indiana University, volume 14.
Jennifer Hu, Jon Gauthier, Peng Qian, Ethan Wilcox, and Roger Levy. 2020. A systematic assessment of syntactic generalization neural language mod- els. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 1725-1744 Online. Association for Computational Linguistics.
Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris

---

Armand Joulin and Tomas Mikolov. 2015. Inferring algorithmic patterns with stack-augmented recurrent nets. Advances in neural information processing systems, 28.
Hao Peng, Roy Schwartz, and Noah A. Smith. 2019. PaLM: A hybrid parser and language model. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Lan- guage Processing (EMNLP-IJCNLP), pages 3644- 3651, Hong Kong, China. Association for Computa- tional Linguisties.
Yoon Kim, Alexander M Rush, Lei Yu, Adhiguna Kun- coro, Chris Dyer, and Gábor Melis. 2019. Unsuper- vised recurrent neural network grammars. In Pro- ceedings of the 2019 Conference of the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 1105-1117.
Jorge Perez, Pablo Barcelo, and Javier Marinkovic. 2021. Attention is auring-ompplee. Journal of Ma- chine Learning Research, 22(75):1-33.
Nikita Kitaev, Steven Cao, and Dan Klein. 2019. Multi- lingual constituency parsing with self attentotenton and pre- treinini. In Proceedings of the 57th Annual Meet- ing of the Association for Computational Linguistics, pages 3499-3505.
Peng Qian, Tahira Nascem, Roger Levy, and Ramón Fernandez Astudillo. 2021. Structural guidance for transformer language models. In Proceedings of the 59th Annual Meeting of the Association for Compu- tational Linguistics and the 11th International Joint Conference Natural Language Processing (Vol- ume 1: Long Papers), pages 3735-3745, Online. As- sociation for Computational Linguistics.
Karol Kurach, Marcin Andrychowicz, and Tlya Sutskever. 2015. Neural random-access machines. arXiv preprint urXiv:1511.06392.
Yair Lakretz, Théo Desbordes, Dieuwke Hupkes, and Stanislas Dehaene. 2022. Can transformers process recursive nested constructions, like humans? In Proceedings of the 29th International Conference on Computational Linguisties, pages 2232,, Gyeongju. Republic of Korea. International Com- mittee on Computational Linguistics.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners.
Laurent Sartran, Samuel Barrett, Adhiguna Kuncoro, Miloš Stanojevié, Phil Blunsom, and Chris Dyer. 2022. Transformer Grammars: Augmenting Trans- former Language Models with Syntactic Inductive Biases at Scale, Transactions of the Association for Computational Linguistics, 10:1423-1439.
Bingbin Liu, Jordan T. Ash. Surbhi Goel, Akshay Kr- ishnamurthy, and Cyril Zhang. 2023. Transformers learn shortcuts to automata. In The Eleventh Interna- tional Conference on Learning Representations.
Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. 2019. Ordered neurons: Integrating tree structures into recurrent neural networks. In In- ternational Conference on Learning Representations.
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 Nu- tional Academy of Sciences, 117:30046 30054.
Mitchell Stern, Daniel Fried, and Dan Klein. 2017. Ef- fective inference for generative neural parsing. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1695-1700. Copenhagen. Denmark. Association for Computational Linguistics.
Rebecca Marvin and Tal Linzen. 2018. Targeted syn- tactic evaluation of language models. In Proceed- ings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1192-1202 Brussels, Belgium. Association for Computational Linguistics.
Emma Strubell, Patrick Verga, Daniel Andor, David Weiss, and Andrew McCallum. 2018. Linguistically- informed self-attention for semantic role labeling. In Proceedings of the 2018 Conference on Empiri- cal Methods in Natural Language Processing, pages Brussels, Belgium. Association for Com- putational Linguistics.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. 2017. Pointer sentinel mixture mod- els. In International Conference on Learning Repre- sentations.
Piotr Mirowski and Andreas Vlachos. 2015. Depen- dency recurrent neural language models for sentence completion. In Proceedings of the 53rd Annual Meet- ing of the Association for Computational Linguistics and the 7th International Joint Conference Natu- ral Language Processing (Volume 2: Short Papers), pages 51 1-517.
Mirac Suzgun, Sebastian Gehrmann. Yonatan Belinkov, and Stuart M Shieber. 2019, Memory-augmented recurrent neural networks can learn generalized dyck languages. arXiv preprint arXiv:1911.03322
Shikhar Murty, Pratyusha Sharma, Jacob Andreas, and Christopher D Manning. 2023. Characterizing intrin- sic compositionality in transformers with tree projec- tions. The Eleventh International Conference on Learning Representations.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Fukasz Kaiser, and Illia Polosukhin. 2017, Attention is all you need. In Advances in Neural Information Pro- cessing Systems, volume 30, Curran Associates, Inc.

---

Oriol Vinyals, Lukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015. Gram- mar foreign language. In Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman, 2019a. GLUE: multi-task benchmark and analysis plat- form for natural language understanding. In Interna- rional Conference on Learning Representations.
Yaushian Wang, Hung-Yt Yi Lee, and Yun-Nung Chen. 2019b. Tree transformer: Integrating tree structures into self-attention. In Proceedings of the 2019 Con- ference Empirical Methods in Natural Language Processing and the 9th International Joint Confer- ence on Natural Language Processing (EMNLP- (JCNLP), pages 1061-1070. Hong Kong. China. As- sociation for Computational Linguistics.
Alex Warstadt, Alicia Parrish, Haokun Liu, Anhad Mo- hanamey, Wei Peng, Sheng-Fu Wang, and Samuel R. Bowman. 2020. BLiMP: The benchmark of linguis- tic minimal pairs English. Trunsactions of Association for Computational Linguistics, 8:377- 392.
Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. 2021. Self-attention net- works can process bounded hicrarchical languages. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and 1 1th International Join Conference on Natural Lan- guage Processing (Volume 1: Long Papers), pages 3770-3785, Online. Association for Computational Linguistics.
Shizhuo Dylan Zhang, Curt Tigges. Stella Biderman, Maxim Raginsky, and Talia Ringer. 2023. Can trans- formers learn to solve problems recursively? arXiv preprint 23055 14699.

---

A Model Hyperparameters
appropriately initialized. We get around this by simply sampling these context windows always start at sentence boundaries. We also prepend spe- cial token ROOT before the start of every sentence such that the attachment decision the final word is made to this ROOT token.
BLLIP. All our hyperparameters for BLLIP are borrowed from the 16-layer Transformer LM used in Sartran et al. (2022). This includes model hy- perparameters (hidden state dimension, number of attention heads, number of layers), dropout (input dropout, output dropout, attention dropout), and learning rate schedulers. We train for 300k steps, evaluating every 3k steps and early stop based on validation set perplexity.
C Parsing with Pushdown-LM.
Since the BLLIP-IG trained Pushdown-L.N op- crates over sub-word tokens, parses produced by this model have subwords as leaf nodes. We pro- cess this by recursively merging leaf siblings that are part of the same word. For instance, given the bracketing (ab, (ra, (ca, dabra))), we recursively merge these to get single node abracadabra. This procedure deterministically converts the parse over subwords into a parse tree over words.
WekiTrees. For experiments WikiTrees, the same model hyperparameters as GPT2- small, and context window of 512. We train with a batch size of 480, and train till validation loss stops decreasing, with a learning rate that lin- early warms up from 0 to 6e-4 over 200 iterations, followed by a cosine learning rate scheduler. For sample efficiency experiments, we add dropout of 0.2 to prevent overfitting.
D Implementation details: Pseudocode for implementing Pushdown Layers
GPT2-medium finetuning. We use batch size of 256, and constant learning rate of 3e-5. We early stop based on validation set performance, and report average of 3 runs. To convert text classifi- cation tasks into language modeling, we use the following prompts:
See Fig. and Fig. for reference implementations of Pushdown Layers and the attachment head.
Premise: /p). Hypothesis: (h). Label: (1), given premise, hypothesis pair (p.h) with label mapped into (Yes, No).
RTE:
MRPC: Given the sentence pair 82). create prompt Sentencel: [81]- Sentence2: [s2). Label: (lJ. where
10.
SSTS: Sentence: (s). Sentiment: (l) for an input sentence with label I.
Given the sentence pair (s1, 82), we create prompt Sentencel: (81-- Sentence2: (s2/, and use the final hidden state to featurize linear regressor, trained jointly with the LMM.
STS-B:
B Training Pushdown-LM with context-windows
In standard LMs, context windows for training are arbitrary offsets into the entire corpora- window might start in the middle of some sentence. Be- cause Pushdown-LMs always start with the stack state initialized as all Os and make attachments only to stack tape contents, a Pushdown-Lee cannot start in the middle of a sentence without the stack tape

---

class FAttnddennSellAtttenennn (nn. Module))
def (srl, x, stack_tape):
B. T, size
9, self welf.ccattn(() sxelt n_embd, dim=2)
(a, nh, (dest),
view(B т, self headd, // self.n_henl n_head). transpose (1, 2) (B, nh, I (src). hs)
10
view(BB T, neead
self.ngheat nghead) transpose (1, 2)
(B, nh, T, hs) v.view(B, T,
15
// self self.n_head). transpose()). 2)
16
augmented k. unsqueeze (2) self. bet int ()) unsqueeze( sugmented__eys /= math. (k. size(-1)) a a nh x T (dest) T(sre)
19
augmented_ats (q. unsqueezezee (3)
augmented_ transpose (-2, -1)) squeeze
20
augnented_att. wtw.:/dddtttmmsee__iiiia filllddffilllee (self. i, AT, :T1 0, float (*-inf"))
22
25
att to (att, din=-l)
self wtt..aatnnrroouutcCc
25
(B, nh, T, T) (8, nh, T, hs) >> (B, nh, T, hs)
26
att re-assemble all head
side side
25
y. (ranpssssse 2). contiguous ()-vew(( view(B, T, c)
29
output projection
self. resid_dropout (self. (y) return
31
Figure 7: Python implementation of a Pushdown Layer attention block.

---

class AttachaendHeeaddcn (nn. (ne.eeennceedd..o.u.. Mocule):
def (SOl,, stack cape. vord]
B, T, C- x.aize()
self, self. daFFdddat_to_n((()) split(sel (en webd,din,, dir-?)
(B. T (deat), hx)
text_.ord__ self. sttrrtr
next.word), dim--1))
T (dest).
seif, seif.k.next w...xtt.orr.iibtterh..oom
noxd) dim=-1))
(dest), (sre),
repeat
(cest) belf.betaastackk. int
kuxith_arite__ie =-13)
depth_enbds),
first, calculate attention betneon query keys k.asth wnteerrrtt_neeeeeee nath.sarrtkk.iize-1)) attach_ legits (next_ unsqueeze (2) k.vith_arite,infa transpose s1)).sque62 (2)
if nо reduce. then ve conoute score with itseir text_ 1" nath, size logits self (next_ (2) (2)
unss.....sseeeeeeeeee (3)) (3)).
now insert legits_zeef into the krich position of logach_ for each pad_terson
tarch, tarch. (attaca tacttahh_ngiii lngita shapetol, logitt. - tos.ceenattachh.lgitt... device))
sttach sttach_lorits__ torch. catttat logits, pad_tensor)), diss-1)
logits attach_iogits_ Logits_
2.
terch arange(T))
(8)
(-1)
legits Jogits_1
by padding firxt
logits
logits. (0)
logits. shape[2).
device-login device,
logits, dim=1
set upper triangular part to -inf logits logits fill bim. (Te1] - (lowe("-inf")) return logitst: 1:]
Figure 8: Python implementation of the Attachment head Pushdown Transformers.


Reviews:
[{"review_id": "55CvABrQoF", "reviewer": "Reviewer_HLRB", "summary": "", "questions": "Please see Reasons To Reject.1.\n\nTable 2 confuses me. As the stack tape provides parse information, adding embeddings of the stack tape gives the model structural information. Why do the authors believe they are not structural information?  For instance, in Figure 1, the stack tape \"1 1 0 0 1 2 2\" gives structural information regardless of the numerical formation. Do you mean you are using learnable structural information while baseline models apply off-the-shelf POS labels?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review - we were pleased that you found $\\lambda$-layers a well motivated and straightforward approach.\n\n**Does the lambda-LM really pull attention away from distractors**? In Fig 6, the distractor is the noun *senator* (as mentioned in the caption), and the relevant observation is that the lambda-LM places less mass on this token than the ordinary LM (compare the last column in the two sub-figures, especially in layers 11 and 8). We apologize if this figure is unclear! This can also be seen quantitatively in Fig 5, which aggregates these attention weights over the entire Marvin & Linzen dataset.\n\n\n**Why not modify values?** The intuition is that a token’s syntactic position should change which other tokens attend to it (via keys). However, syntactic position should not change a token representation’s *content* (via its value embedding). We agree that these other variants would be interesting to explore in future work. We’d be happy to discuss possibilities with you further during the discussion phase.\n\n**Questions about Table-2**: Table 2 divides models based on whether they add *structural tokens* to the input string. The distinction is not whether structural information is available (we agree that lambda-layers also provide structural information), but instead the cost of including this information. As mentioned in background (Lines 173-194), models in the top portion of the table increase the size of the input string by adding constituent labels i.e. an input string “The man likes apples” becomes “(S (NP The man NP) (VP likes apples VP) S)”. This increases input size from n tokens to ~3n tokens that must receive full forward passes (in contrast to lambda-layers, where structural computation takes place within an ordinary forward pass).", "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. This work is well-motivated, the idea is straightforward, and the method is simple.\n2. The method shows advances in parsing long dependencies (Table 1).", "reasons_to_reject": "1.  I do not understand why the authors believe $\\lambda$-LM pulls attention away from the distractor in Figure 6. This figure shows that  $\\lambda$-LM still pays attention to the distractor at the bottom layers, and base-LM has a similar behavior but at the middle layers. Since the authors add the embeddings of the stack tape to the layer input, the authors might provide more analysis about how the embeddings impact the attention behavior. \n\n2. Following the above question, some import variants might be provided and discussed. The authors add embeddings of the stacked tape to self-attention's \"q\" and \"k\" (i.e., attention score). How about applying to \"v\"? Why do you not apply them to Eq.5? Does it imply that the depth does not impact the attachment? \n\nI'm happy to discuss these questions.", "questions_to_authors": "Please see Reasons To Reject.1.\n\nTable 2 confuses me. As the stack tape provides parse information, adding embeddings of the stack tape gives the model structural information. Why do the authors believe they are not structural information?  For instance, in Figure 1, the stack tape \"1 1 0 0 1 2 2\" gives structural information regardless of the numerical formation. Do you mean you are using learnable structural information while baseline models apply off-the-shelf POS labels?", "paper_topic_and_main_contributions": "This paper studies the recurrent/recursive inductive bias (like RNN’s) for Transformer-based parse models. To track the depth,  the authors suggest a self-inferred stack tape that records the recursive state for each token. To update the stack tape record for the current token, the authors consider a model of probabilistic attachment decision to find the relevant prefixes, attach the current token to the relevant prefixes, and update the record of the current token in the stack tape based on the record of the relevant prefixes. Finally, to use the stack tape, in each  $\\lambda$-layer, authors use records as embeddings to force recursions and add them to the layer input.\n\nExperiments on 4 parse tasks support the idea.", "excitement": 3, "reproducibility": 3, "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": "Although this paper focuses on parse tasks, some similar ideas are explored to consider the recurrent (or recursive) mechanism for attention models (also the usage of embeddings for additional states in every layer), which can be adapted to parse tasks. \n\nM. Dehghani, S. Gouws, O. Vinyals, J. Uszkoreit, and Ł. Kaiser, “Universal transformers,” in 7th International Conference on Learning Representations, ICLR 2019, 2019, pp. 1810–1822.\n\nX. Ai and B. Fang, “Leveraging Relaxed Equilibrium by Lazy Transition for Sequence Modeling,” in Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics, 2022, vol. 1, pp. 2904–2924."}}, {"review_id": "T2MpAG3PTE", "reviewer": "Reviewer_iyy7", "summary": "", "questions": "A. Why are \\lambda-layers called that? They remind me strongly of \\lambda-calculus, and I was confused when I discovered that your model has no lambdas in it. I'd strongly recommend a different name.\n\nSection 3.1: The presentation of the model is not very precise. \n\nB. There are a number of words written in scare quotes that should be defined better: \"attachment decision\", \"recursive state\", \"on-the-fly\", \n\nC. It talks about shift/reduce operations but doesn't define clearly what grammar these operations use. Is the grammar just S -> S S, S -> a for all words a? \n\nD. Does the stack tape losslessly encode a partial run of a shift-reduce PDA?\n\nE. Why are reduces described as being between two tokens? Shouldn't they be between two constituents (which could also be tokens)? Can x_k be reduced with a token that is at depth > 0? Presumably this has something to do with the note at line 244, but it's not clear.\n\nF. Why is there a nonzero probability for x_k to reduce with itself? Is that a shift? Please explain.\n\nIn Figure 2, \n\nG. Why are constituents drawn as left-pointing arrows, instead of `/\\` as is standard?\n\nH. What do solid, dotted, and red lines mean? \n\nI. At time t=1, what is the significance of the attachment head pointing just slightly to the right of the 1?\n\nSection 3.3\n\nJ. Do you have to do anything special to backpropagate through the argmax?\n", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comprehensive and very helpful review! And we’re glad you found the model interesting.\n\n**The requirement of gold or \"silver\" trees is a hard requirement”**: Thank you for mentioning this. As you note, we do point it out early on, we actually use the term “syntactic language model” as a submission keyword, and we mention several times (line 77, 416) that lambda-layers model the joint probability of strings and parses. Nevertheless, we will reword to emphasize this unambiguously and further adopt the term syntactic language model.\n\nWe will aim to make the model presentation in sections 3 and 4 much more precise. Thank you also for the helpful references and discussion of them. We believe that our model benefits from the helpful inductive bias rather than what can be represented. \n\nNext, we respond to questions:\n\nQuestions about Section 3.1:\n\nA) We take inspiration from $\\lambda$-calculus where constructions such as the Y combinator are used to implement recursion in programming languages that lack an implementation for recursion. \n\nB) **Defining Attachment decision**: attaching the current token with a prefix token j refers to constructing a constituent by performing multiple reduce operations with the top element of the stack until prefix token j is included in the constituent. This new constituent is then pushed on the stack. (Please see Algorithm 1 for a precise specification of this operation)\n\nC) **Defining the grammar**: Yes, we model a language of unlabeled brackets, so the grammar is is `S -> SS`, `S and S -> a`.\n\nD) **Does the stack-tape losslessly encode…?** Yes.\n\nE) **Why do reduce operations involve two tokens?** Reduction operations ultimately build up constituents (chosen from the incremental parse, see Lines 223-224). However, the module that predicts these decisions does so using a single summary token representation from each constituent. In particular, this is the right-most token: as we mention in the note on Line 244, this is necessary since in left-to-right LMs, only the rightmost token of a span contains all the information about words in that span. \n\nF) **Why can x_k reduce with itself?** Yes, reducing x_k with itself corresponds to a shift operation. We will annotate Eq 5 so that this is clearer.\n\nQuestions about Figure 2:\n\nG) **Why arrows for constituents?** This is intended as a visual representation of how the constituent-building operation works: *cat* “attends” backward to reduce with *the*, and *happy* attends backward to reduce with *[the cat]*, which requires first reducing with *is*. We’ll clarify this in the figure caption.\n\nH) **What do lines mean?** We will clarify this in the figure caption. Solid line: the chosen token, according to Eq~5. Red line: token that cannot be chosen since it is not the rightmost token of any constituent. Dotted line: some candidate token that was not chosen.\n\nI) **Why does the attachment head point to the right of the 1?** Sorry, this is just a positioning issue. The arrow from the attachment head to the stack tape is meant to indicate that the attachment head outputs modify the *entire* stack tape (positioning w.r.t individual numbers in the tape is coincidental) \n\nJ) **Backprop through argmax?** We only have to perform this inference at test time, since we use gold / silver trees to compute stack tape values for learning (Line 267). We think that treating these attachment decisions as latent is an exciting direction for 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": "The model is interesting, and the experiments are thorough with good results.\n", "reasons_to_reject": "The description of the model in Section 3 is not very precise. It uses vague terminology in scare quotes, and it seems to make assumptions about how a shift-reduce parser works that might be particular to dependency parsing (?) and not shared by everyone.\n\nNot reasons to reject, but weaknesses that I think should be corrected:\n\nSection 4: For all of these tasks, it seems to me there's more than one way to construct the binary-branching trees that are used in training. Could you please add explanations?\n\nThe requirement of gold or \"silver\" trees is a hard requirement, but I feel the wording of the paper doesn't quite convey this. It says \"When trained on a corpus of strings annotated with silver constituency parses\" (17) and it \"can be trained on any text corpus annotated with constituency parses\" (80), which leaves open the possibility that it can be trained on unannotated text. I think you could be more up-front about this, for example, by calling \\lambda-LM a \"syntactic language model\" or \\lambda-layers \"syntactic self-attention layers\".\n", "questions_to_authors": "A. Why are \\lambda-layers called that? They remind me strongly of \\lambda-calculus, and I was confused when I discovered that your model has no lambdas in it. I'd strongly recommend a different name.\n\nSection 3.1: The presentation of the model is not very precise. \n\nB. There are a number of words written in scare quotes that should be defined better: \"attachment decision\", \"recursive state\", \"on-the-fly\", \n\nC. It talks about shift/reduce operations but doesn't define clearly what grammar these operations use. Is the grammar just S -> S S, S -> a for all words a? \n\nD. Does the stack tape losslessly encode a partial run of a shift-reduce PDA?\n\nE. Why are reduces described as being between two tokens? Shouldn't they be between two constituents (which could also be tokens)? Can x_k be reduced with a token that is at depth > 0? Presumably this has something to do with the note at line 244, but it's not clear.\n\nF. Why is there a nonzero probability for x_k to reduce with itself? Is that a shift? Please explain.\n\nIn Figure 2, \n\nG. Why are constituents drawn as left-pointing arrows, instead of `/\\` as is standard?\n\nH. What do solid, dotted, and red lines mean? \n\nI. At time t=1, what is the significance of the attachment head pointing just slightly to the right of the 1?\n\nSection 3.3\n\nJ. Do you have to do anything special to backpropagate through the argmax?\n", "paper_topic_and_main_contributions": "This paper describes \\lambda-LM, a language model using \\lambda-layers, which perform a shift-reduce parse, whose stack history is used to influence self-attention. It is trained on gold or \"silver\" trees. Experiments are on both synthetic languages (Dyck) and various natural language benchmarks for syntactic generalization.\n", "excitement": 4, "reproducibility": 3, "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": "56, 462: Yao et al actually show that transformers can model unbounded recursive structure (Appendix B.4), but express doubt about how well it can be learned.\n\n470: Chiang and Cholak (2022) actually show that transformers can recognize PARITY, although, again, they express doubt about how well it can be learned.\n\n499: Further work on neural networks with stacks has been done since 2015:\n- https://arxiv.org/abs/1911.03329\n- https://ieeexplore.ieee.org/ielaam/9078688/9445210/9337907-aam.pdf?tag=1\n- https://arxiv.org/pdf/2109.01982.pdf\n- contemporaneous work: https://arxiv.org/pdf/2304.12955.pdf chapter 10, which uses stacks in transformer layers\n"}}, {"review_id": "DCcWFQfmcy", "reviewer": "Reviewer_tLfe", "summary": "", "questions": "A. 087, 185: It's not clear what you mean by fewer constraints on attention mechanisms. In what way are $\\lambda$-layers \"softer\" and more general in relation to TGs and PLM?\n\nB. $W_k$ keeps track of the depth of each token, but is there anything that lets the model detect the boundaries of constituents with the same depth? For example, in Fig 2, is the model able to tell that at $t = 2$, \"cat\" and \"is\" are in separate constituents?\n\nC. When the lambda layer selects token $x_i$ to reduce with out of $\\{ x_1, \\ldots, x_k \\}$, does this mean that $x_i, ..., x_k$ are reduced into a new constituent?\n\nD. What does it mean when $x_k$ is reduced with itself ($r_k = x_k$)?\n\nE. Why is the \"on-the-fly\" vector for timestep $k$ computed from $h^L_{k-1}$, as opposed to any other $h^L_i$? There's no recurrence, so I don't see what would be special about the last timestep.\n\nF. 248: If attachment decisions are made using the score for the rightmost token in the constituent, what happens if the model selects a token in the middle of a constituent? For example, if selecting \"cat\" causes the (The cat) to be part of the new constituent, what would happen if \"The\" were selected?\n\nG. 270, footnote 1: What is the overall time and space complexity of the $\\lambda$-layer? Is this an *extra* factor of $n$, making it $O(n^3)$?\n\nH. 271: What objective function is used for attachment probabilities, and how is it weighted vs. the LM objective?\n\nI. This seems like a fair comparison, although I would be interested in more details about the multi-task setup.\n\nJ. 302: Do you exclude opening brackets from this prediction, and just take the highest of the closing brackets?\n\nK. Table 1: How many examples are used in the test set? Do you evaluate on different positions within the same Dyck string?\n\nL. Table 1: Why do you think your model doesn't get 100%?\n\nM. 301: Can you give more details of how these prefixes are generated? For example, for the depth gen. task, is the prefix just a sequence of 15-50 open brackets?\n\nN. 295: Can you give more details of the distribution over strings in the training data? What is your algorithm for sampling Dyck strings?\n\nO. 293: Do all 6 layers have $\\lambda$-layers?\n\nP. 351: The results on SG score look pretty mixed for $\\lambda$-LM. Can you explain why $\\lambda$-LM might be doing well on some test suites but not on others? These tests are of quite different character. Garden-Path Effects and Center Embedding are arguably the most syntax-oriented.\n\nQ. Table 2: I would be curious to see results for Base-LM without being trained with attachment data, but this isn't required. I ask because I'm curious how much of a boost you get just by adding the attachment data.\n\nR. 409: For the GPT2-medium architecture, do you also train with attachment decisions using multi-task learning?\n\nS. What is the expected effect of stacking multiple $\\lambda$-layers? Shouldn't just one be enough to implement a shift-reduce parser?\n\nT. Why use different, unrelated embeddings for each of the depths? What if you just used one embedding for depth 0 and the same embedding for all depths >0?\n\nU. Fig 6: $\\lambda$-LM still doesn't seem to attend to \"authors\" much. Mostly it attends to \"the\". Any idea why that happens?\n", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the very thoughtful and comprehensive review! We are glad you liked the variety of experiments.\n\n\n**Decisive advantage over other approaches?**\n\nWe argue that our method is better by not tripling the sequence length with structural tokens, and not needing a bespoke decoding procedure. We decisively are better than PLM and PLM-mask models of Qian et al. as shown in Table-2. Next, compared to transformer grammars, we suggest that we do win on more syntactic tests (as shown in figure 3), but nevertheless we do accept that the quantitative gains are present but not decisive.\n\n\n\n**Attention patterns in Fig 6?**\n\nNote that since the model is auto-regressive, information about the prefix gets automatically propagated into the next word. Thus, information about the word “authors” is already present in “that”, “hurt” and “the”. However, information about the distractor word “senator” is not present in any of the other words, and the only way that information is used is via self-attention. Thus, a model that has higher attention over the distractor is likely to predict the incorrect verb. On the other hand, a model need not attend over the main noun (authors) to predict the correct word since information about this word is also contained in “that”, “hurt” and “the”. \n\nHere, we see that both models read off information about the main noun from the word the but lambda-LM assigns smaller attention weight to the word *senator*, indicating that it is less affected by this distractor word.\n\nThank you for the additional references and presentation suggestions, which we will use to improve the paper.\n\n**Answers to questions:**\n\nA) TGs impose a hard attention constraint — once a constituent closes, subsequent words are not allowed to attend to words inside the constituent, and can only attend to the special constituent token. Lambda-layers have no such constraint, and the model can learn to attend to any word in the prefix.\n\nB) No, but since the stack information is updated autoregressively, the stack contents at the previous time step can inform the model about constituent boundaries. \n\nC) Yes.\n\nD) This corresponds to a “shift” operation. We will annotate Eq 5 so it indicates this.\n\nE) We use this vector to represent the next word because it’s closest in vector space to the next word (since it will be part of a softmax and trained to predict the next word). All of the other $h_i^{L}$ will be closer in vector space to word $w_i$.\n\nF) We ensure that this never happens i.e. once a constituent is formed, only the rightmost word of that constituent is allowed to be chosen (can be easily implemented by setting scores for middle tokens to -INF), see Fig-2 caption and the note in Line 244.\n\nG) Time complexity is the same as ordinary self-attention. At training time, instead of keeping 2D tensors, we have to store 3D tensors for computing attention scores (since depth of a prefix token changes multiple times as a sentence as processed) so the memory requirement is $O(bn^2)$ where b is the max sentence length across all sentences in the input string. For inference, memory requirement is the same as ordinary attention.\n\nH) It’s a multi-class classification loss based on probabilities from Eq 5 (i.e. maximize probability of correct attachment). Classes are weighted equally.\n\nI) We use the same multi-task setup as the Scaffold-LM model from https://aclanthology.org/2021.acl-long.289v2.pdf.\n\nJ) Yes, this prevents opening brackets from competing.\n\nK) Yes, 5000 examples in the test set (we will include these details in the appendix).\n\nL) Since the model has to infer the parse structure at test time, it can fail to do so for some strings, resulting in incorrect predictions.\n\nM) We sample a dyck string of a given length, and then prepend an open bracket. Then, we measure if the model can close this bracket. i.e. for length 5, we might sample `()()` and prepend `[`, giving `[ () ()`.\n\nN) We just sample uniformly from the language (using an implementation similar to https://github.com/princeton-nlp/dyck-transformer).\n\nO) Yes.\n\nP) Note that we outperform all methods on center embedding. \n\nQ) Sure, happy to include this. For BLIMP, we find that without the multi-task loss, the base-LM gets 67.8% (compared to 70.1) and on SG test suites, we find that the model gets about 67% (compared to 69.5%).\n\nR) Yes, which is why it gets close to ~69 with 50M tokens (similar to the size of BLLIP-LG).\n\nS) This is true, in theory but in practice, multiple stacked lambda-layers improved performance.\n\nT) This simply provides more features to the model as opposed to just knowing if a token has been closed or not.\n\nU) Please see our explanation for figure-6 above.", "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": "This paper makes progress on an important research question: how can we modify the transformer architecture so that it learns recursive syntax more effectively? The authors present a new model and show that it consistently outperforms the baseline transformer, and it performs at least competitively with two recent baselines that similarly model sequences and parses jointly. Unlike these baseline methods, this paper's method does not require a \"bespoke\" decoding procedure because the syntactic structure is not part of the output sequence.\n\nThe experimental section of the paper includes an excellent variety of tasks, evaluation metrics, and baseline models. A particularly nice result IMO is that $\\lambda$-layers are much more data-efficient that baseline transformers in terms of SG score (see line 289).\n", "reasons_to_reject": "As pointed out in the paper, there are already a couple of syntactically-supervised transformer architectures out there, and $\\lambda$-layers don't seem to have a decisive advantage in terms of task performance.\n\nI found the description of some aspects of the method to be vague, and I would appreciate more details. See the Questions section for specifics. Something that would be beneficial for understanding the method is a plain-English description of what Algorithm 1 is doing.\n\nI didn't find the conclusions about the learned attention patterns from Fig. 6 very convincing (see question U).\n", "questions_to_authors": "A. 087, 185: It's not clear what you mean by fewer constraints on attention mechanisms. In what way are $\\lambda$-layers \"softer\" and more general in relation to TGs and PLM?\n\nB. $W_k$ keeps track of the depth of each token, but is there anything that lets the model detect the boundaries of constituents with the same depth? For example, in Fig 2, is the model able to tell that at $t = 2$, \"cat\" and \"is\" are in separate constituents?\n\nC. When the lambda layer selects token $x_i$ to reduce with out of $\\{ x_1, \\ldots, x_k \\}$, does this mean that $x_i, ..., x_k$ are reduced into a new constituent?\n\nD. What does it mean when $x_k$ is reduced with itself ($r_k = x_k$)?\n\nE. Why is the \"on-the-fly\" vector for timestep $k$ computed from $h^L_{k-1}$, as opposed to any other $h^L_i$? There's no recurrence, so I don't see what would be special about the last timestep.\n\nF. 248: If attachment decisions are made using the score for the rightmost token in the constituent, what happens if the model selects a token in the middle of a constituent? For example, if selecting \"cat\" causes the (The cat) to be part of the new constituent, what would happen if \"The\" were selected?\n\nG. 270, footnote 1: What is the overall time and space complexity of the $\\lambda$-layer? Is this an *extra* factor of $n$, making it $O(n^3)$?\n\nH. 271: What objective function is used for attachment probabilities, and how is it weighted vs. the LM objective?\n\nI. This seems like a fair comparison, although I would be interested in more details about the multi-task setup.\n\nJ. 302: Do you exclude opening brackets from this prediction, and just take the highest of the closing brackets?\n\nK. Table 1: How many examples are used in the test set? Do you evaluate on different positions within the same Dyck string?\n\nL. Table 1: Why do you think your model doesn't get 100%?\n\nM. 301: Can you give more details of how these prefixes are generated? For example, for the depth gen. task, is the prefix just a sequence of 15-50 open brackets?\n\nN. 295: Can you give more details of the distribution over strings in the training data? What is your algorithm for sampling Dyck strings?\n\nO. 293: Do all 6 layers have $\\lambda$-layers?\n\nP. 351: The results on SG score look pretty mixed for $\\lambda$-LM. Can you explain why $\\lambda$-LM might be doing well on some test suites but not on others? These tests are of quite different character. Garden-Path Effects and Center Embedding are arguably the most syntax-oriented.\n\nQ. Table 2: I would be curious to see results for Base-LM without being trained with attachment data, but this isn't required. I ask because I'm curious how much of a boost you get just by adding the attachment data.\n\nR. 409: For the GPT2-medium architecture, do you also train with attachment decisions using multi-task learning?\n\nS. What is the expected effect of stacking multiple $\\lambda$-layers? Shouldn't just one be enough to implement a shift-reduce parser?\n\nT. Why use different, unrelated embeddings for each of the depths? What if you just used one embedding for depth 0 and the same embedding for all depths >0?\n\nU. Fig 6: $\\lambda$-LM still doesn't seem to attend to \"authors\" much. Mostly it attends to \"the\". Any idea why that happens?\n", "paper_topic_and_main_contributions": "This paper presents a modification of the transformer architecture, called $\\lambda$-layers, designed to model recursive syntax. The method requires syntactic supervision during training and can be used to extract unlabeled, binarized parse trees. The method works by inserting a new mechanism just prior to the attention layer that resembles a shift-reduce parser. While reading the input, it keeps track of a stack of constituents, and at each timestep, it decides how many constituents will be reduced with the next token. The output of this mechanism is the depth of each input token, i.e. the number of reduce operations it has been involved in. These depths are added to the keys of the standard attention layer, so the model can attend to inputs based on the structure of the syntax tree.\n\nThe authors compare this method against a baseline transformer that is trained with the same syntactic information using multi-task learning, and other recent transformer architectures that jointly model sequences and parses: Transformer Grammars (TGs) by Sartran et al. (2022), and PLM by Qian et al. (2021). The main experimental results are:\n1. On the Dyck language, $\\lambda$-layers generalize better than baseline transformers\n2. Mixed results on the Syntactic Generalization test suites (Hu et al. 2020), but always better than the baseline transformer\n3. Better BLIMP score than baseline transformers\n4. Slightly better perplexity than baseline transformers on the BLLIP test set\n5. Much better data-efficiency than the baseline GPT2 architecture on a large language modeling task, evaluating on SG score\n6. Mixed results on GLUE, but often better\n7. Better unlabeled, binarized parsing on BLLIP than the model of Kitaev et al. (2019)\n8. Analysis of the learned attention patterns on a subject-verb agreement task with distractor noun phrases (Marvin and Linzen 2018)\n\nOverall, it looks like $\\lambda$-layers are better than baseline transformers at learning recursive syntax and are at least competitive with existing syntactically-supervised baselines.\n", "excitement": 4, "reproducibility": 3, "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": "More types of neural networks augmented with stacks to put in Section 6:\n\n* ON-LSTM https://arxiv.org/abs/1810.09536\n* Nondeterministic Stack RNN https://arxiv.org/abs/2210.01343\n"}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "A. Can you explain why you chose the name $\\lambda$-layer?\n\nB. Is \"depth\" really referring to the height of the tree of each reduced constituent? In a shift-reduce parser, \"depth\" would refer to the depth of the stack of shifted terminals and nonterminals.\n\nC. 208: A *deterministic* PDA.\n\nD. 260: What does \"arbitrarily non-linear\" mean?\n\nE. 266: It would be good to describe how to precompute these ground-truth values from the parses.\n\nF. 287: I don't think this has to do with the fact that they're predicted in parallel (which they aren't?), but with the fact that the output vocabulary does not include brackets for encoding the parse tree.\n\nG. Fig 6: Could you label the layers on the y axis? I don't know which direction the layers go in.\n"}}]

Author rebuttal:

Meta-review: This paper improves Transformers by adding \lambda-layers, which perform a shift-reduce parser and enable the self-attention over the stack history (paring prefix) beside the surface tokens. Transformers with \lambda-layers are jointly trained on strings with annotated (or parsed) trees. Experiments on both synthetic languages and various NL benchmarks show the generalization of their approach. All reviewers raise some questions about the clarity of this paper and some missing references related to shift-reduce stack parsing, recursive mechanism over attentions.
Decision: Accept-Main