Augmenting Transformers with Recursively Composed Multi-grained Representations
Authors: Xiang Hu
Qingyang Zhu
Kewei Tu
Wei Wu
Venue: ICLR 2024 poster (2024)
Keywords: NLP; recursive neural network; multi-grain representation; compositional representation;span labeling;relation extraction; grammar induction;language understanding
Primary area: representation learning for computer vision, audio, language, and other modalities
TL;DR: Augmenting transformers with recursively composed multi-grained representations

Abstract: We present ReCAT, a recursive composition augmented Transformer that is able to explicitly model hierarchical syntactic structures of raw texts without relying on gold trees during both learning and inference. 
Existing research along this line restricts data to follow a hierarchical tree structure and thus lacks inter-span communications.
To overcome the problem, we propose a novel contextual inside-outside (CIO) layer that learns contextualized representations of spans through bottom-up and top-down passes, where a bottom-up pass forms representations of high-level spans by composing low-level spans, while a top-down pass combines information inside and outside a span. By stacking several CIO layers between the embedding layer and the attention layers in Transformer, the ReCAT model can perform both deep intra-span and deep inter-span interactions, and thus generate multi-grained representations fully contextualized with other spans.
Moreover, the CIO layers can be jointly pre-trained with Transformers, making ReCAT enjoy scaling ability, strong performance, and interpretability at the same time. We conduct experiments on various sentence-level and span-level tasks. Evaluation results indicate that ReCAT can significantly outperform vanilla Transformer models on all span-level tasks and recursive models on natural language inference tasks. More interestingly, the hierarchical structures induced by ReCAT exhibit strong consistency with human-annotated syntactic trees, indicating good interpretability brought by the CIO layers.

Published as a conference paper at ICLR 2024
AUGMENTING TRANSFORMERS WITH RECURSIVELY COMPOSED MULTI-GRAINE) REPRESENTATIONS
Xiang Hu', Qingyang Zhu?, Kewei Tu?*, Wei Wu
1 "Ant Group "ShanghaiTech University
aaaron.hx; congyue. ww) antgrroupccom /zhuqy: tukw) @eshanghiitcch.du.co edw..e
ABSTRACT
We present ReCAT, recursive composition augmented Transformer that is able to explicitly model hierarchical syntactic structures of raw texts without relying on gold trees during both learning and inference. Existing research along this line re- stricts data to follow a hierarchical tree structure and thus lacks inter-span commu- nications. To overcome the problem, propose novel contextual inside-outside (CIO) layers, each of which consists of a top-down pass that forms representations of high-level spans by composing low-level spans, and a bottom-up pass that com- bines information inside and outside span. The bottom-up and top-down passes are performed iteratively by stacking CIO layers fully contextualize span rep- resentations. By inserting the stacked CIO layers between the embedding layer and the attention layers in Transformer, the ReCAT model can perform both deep intra-span and deep inter-span interactions, and thus generate multi- multi-grained repre- sentations fully contextualized with other spans. Moreover, the CIO layers can be jointly pre-trained with Transformers, making ReCAT enjoy scaling ability, strong performance, and interpretability at the same time. We conduct experiments on various sentence-level and span-level tasks. Evaluation results indicate that Re- CAT can significantly outperform vanilla Transformer models on all span-level tasks and recursive models natural language inference tasks. More interest- ingly, the hierarchical structures induced by ReCAT exhibit strong consistency with annan-an syntactic trees, indicating good interpretability brought by the CIO layers.
INTRODUCTION
Recent years have witnessed a plethora of breakthroughs in the field of natural language processing (NLP), thanks to the advances of deep neural techniques such as Transformer (Vaswani et al.] (017)) BERT (Devlin et al. 2019), and GPTs (Brown et al.] 2020 OpenAl 2023). Despite the success of the architecture, syntax and semantics in Transformer models are represented in an implicit and entangled form, which is somewhat divergent from the desiderata of linguistics. From a linguistic point of view, the means to understand natural language should comply with the principle that "the meaning of a whole is a function of the meanings of the parts and of the way they are syntactically combined" (Partee 1995). Hence, it is preferable to model hierarchical structures of natural lan- guage in an explicit fashion. Indeed, explicit structure modeling could enhance interpretability (Hu) al. 2023), and result in better compositional generalization (Sartran et al.) 2022). The problem is then how to combine the ideas of Transformers and explicit hierarchical structure modeling, so as to obtain a model that has the best of both worlds.
In this work, we attempt to answer the question by proposing novel Contextual -utiiideutsiee (CIO) layers as an augmentation the Transformer architecture and name the model "Recursive Composi- tion Augmented Transformer" (ReCAT). Figure] Iillusttraes the architecture of ReCAT. In a nutshell, ReCAT stacks several CIO layers between the embedding layer and the deep self-attention layers in Transformer. These layers explicitly emulate the hierarchical composition process of language and
"Corresponding authors
'Code released httppppp///gighib...matatteeeeee
RTDT

---

Published as a conference paper at ICLR 2024
provide Transformers with explicit multi-grainn representations. Specifically, we propose variant of the deep inside-outside algorithm (Drozdov et al., 2019). which serves as the backbone of the CaOers CIO layer. As shown in Figure I a). multiple CIO layers are stacked to achieve iterative up-and- down mechanism to learn contextualized span representation. During the bottom-up pass, the model composes low-level constituents to refine high-level constituent representations from the previous iteration, searching for better underlying structures via dynamic programming approach (Mail- lard et al. 2017); while during the top-down pass, each span merges information from itself, its siblings, and its parents to obtain a contextualized representation. By this means, the stacked CIO layers are able to explicitly model hierarchical syntactic compositions of inputs and provide con- textualized constituent representations to the subsequent Transformer layers, where constituents at different levels can sufficiently communicate with each other via the self-attention mechanism. Re- CAT enjoys several advantages over existing methods: first, unlike Transformer Grammars (Sartran) ict al. 2022), our model gets rid of the dependence on expensive parse tree annotations from human experts, and is able recover hierarchical syntactic structures in an unsupervised manner; second, unlike DIORA (Drozdov et al., (211)) and R2D2 (Hu et al., 2021). our model breaks the restriction that information exchange only happens either inside outside a span and never across the span boundaries, and realizes cross-span communication in a scalable way. Moreover, we reduce the space complexity of the deep inside-outside algorithm from cubic linear and parallel time com- plexity to approximately logarithmic. Thus, the CIO layers can go sufficiently deep. and the whole ReCAT model can be pre-trained with vast amounts of data.
Time flies like an arrows Frutt flles a banona.
layer
top-down
NxTranstormers
Pin
112
CIO layer 1
bottom-up up
embeddings
contestuual Inside quiide- layer
b) best induced tree
self-attention over constiteetss
Figure I: ReCAT model architecture. The contextual inside-outside layers take v. token embeddings and output
2Tc- node representations.
We evaluate ReCAT GLUE (Wang et al. 2019) (sentence-level tasks), OntoNotes (Weischedel
jet al. 2013) (span-level tasks), and PTB (Marcus et al. 1993) (grammar induction). The empir- ical results indicate that: (1) ReCAT attains superior performance compared to Transformer-only baselines on all span-level tasks with an average improvement over 3%; (2) ReCAT surpasses the hybrid models composed of RvNNs and Transformers by 5% on natural language inference; and (3) ReCAT outperforms previous RvNN based baselines by 8% on grammar induction. Our main contributions are three-fold:
1. We propose a Contextual Inside Outsiie (CIO) layer, which can be jointly pre-trained with Transformers efficiently, induce underlying syntactic structures of text, and learn contextualized multi-grained representations.
2. We further propose ReCAT, a novel architecture that achieves direct communication among con- stituents at different levels by combining CIO layers and Transformers. We reduce the complexity of the deep inside-outside algorithm from cubic to linear, and further reduce the parallel time complexity from linear to approximately logarithmic.
2 RELATED WORKS
The idea of equipping deep neural architectures with syntactic structures has been explored in many studies. Depending on whether gold parse trees are required, existing work can be categorized into two groups. In the first group, gold trees are part of the hypothesis of the methods. For example, Pol- (1990) proposes encoding the hierarchical structures of text with an RvNN: SNNN:(Sccher et al. (2013) verify the effectiveness of RvNNs with gold trees for sentiment analysis; RNNG (Dyer et al. 2016 and Transformer Grammars (Sartran et al. 2022) perform text generation with syntactic knowledge.
Though rendering promising results, these works suffer from scaling issues due to the expensive and elusive nature of linguistic knowledge from human experts. To overcome the challenge. the other group of work induces the underlying syntactic structures in an unsupervised manner. For in- stance, ON-LSTM et al. (201h) and StructFormer (Shen et al. 2021) integrate syntactic struc-
2

---

Published as a conference paper at ICLR 2024
tures into LSTMs Transformers by masking information in differentiable ways; Yogatama et al. (017)) propose jointly training the shift-reduce parser and the sentence embedding components; URNNG (Kim al., 2019b) applies variational inference over latent trees to perform unsupervised optimization of the RNNG; Chowdhury & Caragea (2023) propose a Gumbel-Tree (Choi et al., 2018) based approach that can induce tree structures and cooperate with Transformers
flexible
module by feeding contextualized terminal nodes into Transformers; Maillard et al. (2017) propose an alternative approach based on a differentiable neural inside al algorithm: Drozdov et al. (2019) pro- pose DIORA, an auto- cetio-encoder---ee like pre- pre-trained model based on an onside-uutside algorithm (Baker, 1979 Casacuberta 1994); and R2D2 reduces the complexity of the neural inside process by pruning, which facilitates exploitation of complex composition functions and pre-training with large corpus. Our work is inspired by DIORA and R2D2, but a major innovation of our work is that our model can be jointly pre-trained with Transformers efficiently, which is not trivial to achieve for DIORA A and R2D2. Both of them have to obey the information access constraint (i.e., information flow is only allowed within (inside) among (outside) spans), due to their training objectives of predicting each token via its context span representations. Joint pre-training with Transformers would break the constraint and lead to information leakage, thus not feasible.
METHODOLOGY
3.1 MODEL
Overall, there are two basic components in ReCAT: CIO layers and Transformer layers. As illus- trated in Figure [ the CIO layers take token embeddings as inputs and output binary trees with node representations. During the iterative up-and-down encoding within the CIO layers, each span representation learns to encode both context and relative positional information. The multi maatt--rained representations are then fed into the Transformer layers where constituents at different levels can interact with each other directly.
3.1.1 PRUNING ALGORITHM
3
3
52
53
84
55
56
51
52
53
54
%
81
82
83
84
8/
8
$12
83
54
$p16
(b)
(C)
(4)
(e) (3,4.25.133
Figure 2: Example of the pruning process. 8; and Suy denotes the i-th token and sub-string covering to j. both included. The numbers are split indices. In (e), the merge order is the reverse order of the split order, which is 51,5,2,4,3)
We propose to improve the pruned deep inside algorithm Hu et al. (202)) so that it can be com- pleted in approximately logarithmic steps. The main idea is to prune out unnecessary cells and simultancously encode the remaining cells once their sub-span representations are ready. As shown in Figure ee an unsupervised parser is employed assign each split point score and recursively splits the sentence in the descending order of the scores. Thus the reverse of the split order can be considered the merge order of spans and cells that would break the merged spans are deemed un- necessary. During the pruning pass, we record the encoding order B of cells and their valid splits KC. As shown in Figure there is pruning threshold m which is triggered when the height of encoded cells (in grey) in the chart table reaches m. At the beginning, cells beneath m are added bottom-up to B row by row. Once triggered, the pruning process (refer (c) in Figure works as follows:
Group split points according to their height the tree, with each group corresponding to their height in the induced tree, e.g., group1: {1,5), 5], group2: {2, 4), group3: {3).
1. Merge all spans simultaneously in the current merge group, e.g., (81, 82) and (s6, $6) in (b).
2. Remove all conflicting cells that would break the now non-splittable span from Step 1, e.g. the dark cells in (c), and reorganize the chart table much like in the Tetris game as in (d).
3. Append the cells that just descend height to B and record their valid splits in AC, e.g., the cell highlighted with stripes in (d) whose valid splits are (2, 3} and {3,4) respectively. Then go back Step I until no cells are left.
3

---

Published as a conference paper at ICLR 2024
In this way. the entire inside algorithm be finished within tree-height steps, whose parallel time complexity is upproximately logarithmic based on our empirical study in Appendix The detailed pseudo-code can be found in Appendix A.3 The optimization of the unsupervised parser parser is explained in the next section.
3.1.2 CONTEXTUAL INSIDE-OUTSIDEE OUTSIDE LAYERS
In this part, we explain contextual inside- outside layers, and how extend linear neu- ral inside algorithm to our contextual inside- outside layers.
CIO Layer1
Our contextual inside-outside algorithm hor- rows the neural inside-outside idea from DIORA (Drozdov al., 2019), but differs from in the following ways. First, the outside pass designed to contextualize span representation instead of constructing auto-encoding loss. As result of introducing information leakage, the original pre-training objective does not work any- more. Second, we introduce an iterative up-and-down mechanism by stacking multiple CIO layers refine span representations and underlying structures layer by layer. We use masked language modeling as the new pre-training objective thanks to the mechanism allowing spans affected by masked tokens contextualize their representations through iterative up-and-down processes.
g
(a)
Figure 3: The first layer of stacked CIO layers.
Denotations. Given a sentence S = =s11 (8, 82, ... 8n} with n tokens, Figure 3 shows multi-layered chart tables. We denote the chart table at the I-th layer as T where each cell Th, covers span (i,j) corresponding
sub-string St.j For span ji, its set of inside pair consists of span pairs k(1,k), (Ke + } for h = i,..,j-- k(i,k), (j+1, k)} for k = = a sentence {s1, $2, 83, S1). the inside pairs of span (1, 3) are {11, 1), (2, and {(1, (3, 3) and the outside pairs of span (2, 3) are (1, (1, 1)) and {(2, 4), (4, We denote the representations computed during the inside pass and the outside pass as è and respectively.
For span (i,j). its set of outside pair consists of span pairs and {(k, j), (ks, i 1)} for k: = L,.... 1. For example, given
Pruned Inside Pass. During the inside process the 1-th layer, given inside pair of span (i,j) split on & s.t. S < j. we denote its composition representation and compatibility score as eg k] and di respectively. The compatibility score means how likely an inside pair is to be merged. e' [k] is computed by applying the composition function to its immediate sub-span representations
ef and 4 Meanwhile, the composition function additionally takes the outside representation " from the previous layer to refine the representation, as illustrated in Figure 3 [k] is computed by recursively summing up the scores of the single step compatibility score [k and the corresponding immediate sub-spans, i.c., af,x and d The inside score of.y and representation e` of each cell Te, are computed using a soft weighting over all possible inside pairs, i.e., ['_][k] [k]] and ét, [k] with & E Kij, where K. is the set of valid splits for each span generated during the pruning stage. The inside representation and score of a cell are computed as follows:
e|,[k]] = Compose (el, (el,,,eh4.5 ", [k]] = @a ChTL.) slssk]] a + a',a + d
(t)
w/. [k] Evek,, explar, [RT) 2i Σ
wh, [e]e [k], di.
Σ kEK
wi, [k]]
kek.,
(1) We elaborate on details of the Compose function and the compatibility function o afterwards. For bottom cell at the first chart table T we initialize ét, as the embedding of s; and at, as zero. For T we assign shared learn-able tensor to -- We encode the cells in the order of B that when
computing the representations and scores of a span, its inside pairs needed for the computation are already computed.
Contextual Outside Pass. A key difference in our outside pass is that we mix information from both inside and outside of span. Meanwhile, to reduce the complexity of the outside to linear, only consider cells and splits used in the inside pass. Analogous to inside, we denote the outside representation and score of given span as Et [k]] and bl (k) respectively, whose parent span is (i, k)
4

---

Published as a conference paper at ICLR 2024
or (k: () for & or i. Then, oi [k] and b/ , [k] can be computed by:
(b,,(0] CCmppoer ((6
34 [Compose (f 2. (
[ + +6 bi, (i K = (eatch 2..21) ML19 = ( (l, M2.;
[ e.
for
"for <
The parameters of the Compose follow the order of left, right and parent span. According to that obtain mapping from
records all valid splits for each span during the pruned inside pass, a span to its immediate sub-spans. By reversing such mapping, we get a mapping from a span to its valid immediate parent spans denoted as P, which records the non-overlapping endpoint k in the parent span (i, k) or (k. j) for given span (i. Thus, we have:
exp(b),)(a)
[
E EvEE,, exp(U,,[(T) E..
Σ kEP
Σ kEPL,
(3)
By following the reverse order of B, we can ensure that when computing ei sentation of parent span (i,j) needed for the computation are already computed
[k] the outside repre-
Composition and Compatibility functions. We borrow the idea from R2D2 (Hu al.] 2021] to use single-layered Transformer as the composition function. As shown in Fig- ure 4 there are three special tokens indicating the role of each input. During the inside pass, we feed e/-11 2/ 1 summed up with their role embeddings into the Transformer and take the output of 2 et [R] shown in Fig- ure Ma). Analogously, we can get the out- side representation as shown in Figure 4b). To compute the compatibility score, we feed ex, and 1441, through MLP!, MLP used to capture left and right syntax features of sub-spans and calculate their scaled inner product:
[kl
Transformer
Transformer
(
[RIGHT]
IPRM
LERT]
[RIGHT]]
[PRT]
(a) Composea
(b) Composep
Figure 4: The Compose function for the inside and out-
side pass
de MLP'. .). Bh+1s
(eae..,),) ((l,,,, = (fl,e) /4+1.//Vd
(4)
where Rd. (s ét ()+1.) and ( (1, ( be computed in similar way. For effi ciency considerations, da and dg used in different layers share the same parameters.
Tree induction. For a given span (i.j) at the 1-th CIO layer, the best split point is h with the highest a, [ l Ki.j. Thus it is straightforward to recover the best parsing tree by recursively selecting the best split point starting from the root node Tik, in a top-down manner, where is the total number of CIO layers.
Multi-grained self-attention. Once recover the best parsing tree as described above (c.f., Fig- ure e)), we feed outside representations of nodes from the last CIO layer into subsequent Trans- formers, enable constituents at different levels communicate directly and output multi-grained representations fully contextualized with other spans.
3.2 PRE-TRAINING
Algorithm Pre-training ReCAT
I: function FORWARD(S. x, v)
b the original input, x is the input with 15% tokens masked. y is the target MLM. b Corresponds to dection[3.1.1 & is the parameter for the top-down parser. b Initialize the chart table at the 0-th layer with word embeddings Run L-layered CIO blocks. Iteratively encode the sentence up and down. Eq I as the inside parameters of the i-th CIO layer
3: B= PrPunee(SS0 (b
4: Initialize T
5: for E to L do
Inside(B, T 7 , a.)
7:
ContextualOutsideee T,
Eq B is the outside parameters of the i-th CIO layer
8: induce_treee(T4)
gather(TT out Transformers((7
I Gather node representations from the CIO layer. >> Feed contextualized node presentations into Transformers > The loss for the top-down parser used in Prune. > The loss for masked language modeling.
10:
11:
parser_loss log (5
12:
mlm_loss cross_ (et_entrooyclllsttttt
13:
return parser_loss + mim_loss
Detailed parallel implementation could be found in the Appendix A.1
5

---

Published as a conference paper at ICLR 2024
As our contextual outside pass brings information leakage, the original training objective designed for DIORA does not work anymore. Instead, here we use the MLM objective. For simplicity, we use the vanilla MLM objective instead of its more advanced variants such as SpanBERT (Joshi et al. 2020). Since each masked token corresponds to a terminal node in the parsing tree, we just take the Transformer outputs corresponding to these nodes to predict the masked tokens. As masking tokens may bring an extra difficulty to the top-down parser, we make all tokens visible to the parser during the pruning stage and only mask tokens during the encoding stage.
Parser feedback. We use hard-EM approach (Liang et al., 2017) optimize the parser used for the pruning. Specifically, we select the best binary parsing tree z estimated by the last CIO layer. As shown in Figure([je) at step L, the span corresponding to given split a, is determined, which denoted as ("). Thus we can minimize the neg-log-likke loglliielloooo of the parser as follows:
exp(Fa.)
p(ac(S)= Eker' exp(ex)
log p(z))
log Dgg((ar(S) (S).
(5)
Algorithm summarizes the procedure to pre-train ReCAT.
4 EXPERIMENTS
System
# params
Fast-R2D2
32M
We compare ReCAT with vanilla Transformers and recursive models through extensive experiments variety of tasks.
Fast-R2D24 Transformer
2oss-R2D24Trnnffommee
67M
DIORA TTrnsformer
77M
142M
Data for Pre-training. For English, we pre-train our model and baselines WikiText103 (Merity al., 2017). WikiText103 is split at the sentence level, and sentences longer than 200 after to- kenization are discarded (about 0.04%c of the original data). The total number of tokens left is 110M.
Transfomerr 3
46M
Transfomerxx
67M
Transformerx
88M
ReCAT [1, 1.3]
63M
ReCATaam [3, 1,3]
70M
ReCATTuslurd (3, 1.
S8M
ReCAT medum: [3. 1,6]
109M
ReCAT setups. We prepare different configurations for ReCAT to conduct comprehensive experiments. We use ReCAAsharehodaa indicate whether the Compose functions used in the inside and outside passes share the same parameters or not. Mcanwhile, we use ReCAT ji k] to denote Re- CAT made up of stacked CIO layers, a j-layer Composc function, and k--ayee Transformer. Specifically, ReCAT share w/o iter and ReCAT share wio TFM are designed for the ablation study, corre- sponding to no iterative up-and-down mechanism and no Transformer layers.
ReCAT Sture
70M
Table 1: Parameter sizes.
Baselines. For fair comparisons, we select baselines whose parameter sizes are close to ReCAT with different configurations. We list the parameter sizes of different models in Table Details of baseline models are explained in the following sections 3
4.1 SPAN-LEVEL TASKS
Dataset. We conduct experiments to evaluate contextualized span representations produced by model four classification tasks, namely Named entity labeling (NEL), Semantic role label- ing (SRL), Constituent labeling (CTL), and Coreference resolution (COREF), using the annotated OntoNotes 5.0 corpus (Weischedel al. 2013). For all the four tasks, the model is given input sentence and the position of a span or span pair, and the goal is to classify the target span(s) into the correct category. For NEL and CTL, models are given single span label, while for SRL and COREF, models are given span pair.
Baselines. We use Transformer and Fast-R2D2 as our baselines. Fast- could be regarded as a model only with the inside pass and using a 4-layer Transformer as the Compose function. For reference, we also include BERT as baseline which is pre-trained on a much larger corpus than our model. For BERT, we use the HuggingFace WWolf et al. 2019) implementation and select the cased version of BERT-base. Given span, R2222-based models (our model and Fast-R2D2) can encode the representation directly, while for Transformer- pooling in the construction of the span representation from token representations.
models, try both mean pooling and max
Fine-tuning details. Our model and the Transformers are all pre-trained epochs and fine-tuned on the four tasks respectively for 20 epochs. We feed span representations through a two-layer MLP using the same setting as in Toshniwal et al. (2020). For the downstream
Wiki-103 for 30
Please find the paraeetassmeters for the baselines in Appendix A.2

---

Published as a conference paper at ICLR 2024
System
NEI.
SRI.
CTL.
CORFF
Fast-R2D2
91.67/92.67
79.49/80.21
91.34/90.43
87.77/86.97
TransformerGueun
90.41/90.17
88.37/88.48
95.99/93.84
89.55/88.
Transformer6.ax
90.49/90.70
88.86/88.99
96.33/95.28
90.01/89.45
ReCAT share [3, 1
95.03/94.78
92.73/92.79
98.49/98.47
93.99/92.74
Transformer9neee
90.37/89.27
88, 48.46/88.77
96.21/92.98
89.37/88.0P
Transformer9
90.93/90.28 28
89 10,,0088.11 12
96,49/95.92
90.32/89.38
ReCAT nachare [3, 3
94,84/94.18
92.86/93.01
98.56/98.58
94.06/93.19
For Reference
BERT
96.49/95.77
93.41/93.49
98.31/97.91
95.63/95.58
BERT max
96.61/96.17
93.48/93.60
98.35/98.38
95.71/96.00
Table 2:
Dev/Test performance for four span-level tasks on Ontonotes 5.0. All tasks are evaluated using Fl score. All models except BERT are pre-trained on wiki103 with the same setup.
classification loss, we use the cross entropy loss for single-label classification and binary cross tropy loss for multi-label classification. In particular, during the first 10 epochs of fine-tuning, inputs also masked by 15% and the final loss the summation of the downstream task loss, the parser feedback loss, and the MLM loss, For the last 10 epochs, we switch to the fast encoding mode, which is described in Appendix [A.3] during which inputs are not masked anymore and the top-down parser is frozen. We use learning rate of 5e to tune the classification MLP. learning rate of 5e 55 to tune the backbone span encoders, and a learning rate of 1e-3 3 to tune the top-down parser.
Results and discussion. Table 2 shows the evaluation results. We can that ReCAT outper- forms the vanilla Transformers across all four tasks, with absolute improvements of around 4 F1 scores on average. Furthermore, though BERT has twice many layers as our model and is pre- trained on corpus 20x larger than ours, ReCAT is still comparable with BERT (even better than BERT on the CTL task). The results verify our claim that explicitly modeling hicrarchical syntactic structures can benefit tasks that require multiple levels of granularity, with span-level tasks being one of them. Since Transformers only directly provide token-level representations, all span-level repre- sentations reside in hidden states in an entangled form, and this increases the difficulty of capturing intra-span and inter-span features. On the other hand, our model applies multi-layered self-attention layers on the disentangled contextualized span representations. This enables the construction of higher-order relationships among spans, which is crucial for tasks such as relation extraction and coreference resolution. In addition, we also observe that although Rast-R2D2 works well on NEL, its performance in other tasks is far less satisfactory. Fast-R21D2 performs particularly poorly in the SRL task, where model improves the most. This is because Fast-R21>2 solely relies local inside information, resulting in a lack of spatial and contextual information from the outside which crucial for SRL. On the other hand, our model compensates for this deficiency by contextualizing the representations in an iterative up-and-dows manner.
4.2 SENTENCE-LEVER TASKS
Dataset. We use the GLUE WWng et al. 2019) benchmark to evaluate the performance of our model on sentence-level language understanding tasks. The General Language Understanding Eval- uation (GLUE) benchmark is collection of diverse natural language understanding tasks.
Baselines. We select Fast-R2D2, DIORA variant, and vanilla Transformers baselines which are all pre-trained on 1ik with the same vocabulary. The Transformer baselines include Trans- formers with 3.6, and 9 layers corresponding different parameter sizes of ReCAT with different configurations. To study the gain brought by representations of non-terminal nodes, we include a baseline in which representations of non-terminal nodes in ReCAT are not fed into the subsequent Transformer, denoted as ReCAT The settings of the Fast-R2D2 and the Transformers are the same as in Section 4.1 For reference, we list results of other RvNN variants such as Gumbel- Tree Choi et al. (2018), OrderedMemory (Shen et al. 2019a), and CRvNN (Chowdhury & Caragea 2021).
Fine-tuning details. Our model and the Transformer models are all pre-trained on Wiki- 103 for 30 epochs and fine-tuned for 20 epochs. Regarding to the training scheme, we use the same masked language model warmup as in 4n4.1 for models pre-trained via MLM. The batch size for all models is
Detail setup of baselines is described in Appendix A.4

---

Published as a conference paper at ICLR 2024
natural language inference
single-sentence SST-2
sentence similarity MRPC(f1)
System
MNI.I-m//mm)
RTE
QNLI
CoI.A
QQP
Fast-R2D2
69. 69.64/69.57
54.51
76.49
90.71
40.11
79.53
85.95
www.R2DD-Trrnnfomon
68.25/67.30
55.96
76.93
89.10
36.06
78.09
87.52
+ Transformer
68.87/68.35
55.56
77.23
88.89
36.58
78.87
86.69
Transfrere
67.95/67.16
54.74
76.18
88.53
18.32
77.56
86.13
Transfomerrx3
69.20/69.90
53.79
72.91
85.55
30.67
78.04
85.06
Transformerx6
73.93/73.99
57.04
79.88
86.58
36.04
80.80
86.81
ReCAT noshare
noshhare [1, 1,
72.77/73.59
54.51
73.83
84.17
23.13
79.24
85.02
ReCAT share wio ite:
75.03/75.32
56,32
80.96
84.94
20.86
78.86
85.36
ReCAT share wil
74.24/74.06
55.60
80.10
85.89
28.36
79.03
85.98
ReCAT share wil 1FM
68.87/68.24
83.94
ReCATabare [3, 3|
75.48/75.43
56.68
81.70
86.70
25.11
79,45
86.10
Transformerx3 x9
76.01/76.47
56,70
83.20
86.92
36.89
79.71
88.18
ReCAT noshare [3, 1,
75.75/75.79
57.40
82,01
86,80
26.69
80.65
85,97
ReCATnoshard [3, 1,
76.33/77.12
56.68
82.04
88.65
35.09
80.62
86.82
For reference
GumbelTree'
69.50/
90.70
CRvNN
72.24/72.65
88.36
Ordered Memory"
72.53/73.2
90.40
Table 3: Evaluation results on GLUE benchmark. The models with 1 are based on Glo Ve embeddings and their
results are taken from Ray Chowdhury & Caragea (023). The others are pre-trained on wiki103 with the same setups.
128. As the test dataset of GLUE is not published, we fine-tune all models on the training set and report the best performance (acc. by default) on the validation set.
Results and discussion. Table reports evaluation results on GLUE benchmark. First, we ob- serve interesting phenomenon that ReCAT significantly outperforms RvNN-based baselines on NLI tasks, underperforms the models on single-sentence tasks, and achieves comparable perfor- mance with them sentence similarity tasks. Our conjecture is that the phenomenon arises from the contextualization and information integration abilities of the self-attention mechanism that en- able the MI.Ps in pre-trained Transformers to retrieve knowledge residing in parameters in better way. Therefore. for tasks requiring inference (i.c., knowledge beyond the literal text), ReCAT can outperform RvNN-based baselines. RvNN-based baselines perform well on tasks when the literal text is already helpful enough (c.g., single-sentence tasks and sentence similarity tasks), since they can sufficiently capture the semantics within local spans through explicit hierarchical composition modeling and deep bottom-up encoding. ReCAT, on the other hand, sacrifices such a feature in exchange for the contextualization ability that enables joint pre-training with Transformers, and thus suffers from degradation single-sentecee tasks. Second, even with only one CIO layer, ReCAT [1, 1, significantly outperforms Transformerx3 on the MNLI task. When the number of CIO layers increases 3. ReCAT boshare [3, 3] even outperforms Transformer x6. The results verify the effectiveness of explicit span representations introduced by the CIO layers. An expla- nation is that multi-layer self-attention intra-span and inter-span relationships, which are critical to NLI tasks but less beneficial to single- sentence and sentence similarity tasks. Third, the iterative up-and-down mechanism is necessary, as ESCATposhare [3, 1,3] significantly outperforms ReCAT share w/o and BoCATToshance [1, 1, 3J. even though ReCAT noshare [3, 1,3] and ReCAT share wio iter have almost the same number of parameters. We speculate that multiple CIO layers could enhance the robustness of the masked language models because the masked tokens may break the semantic information of inputs and thus affect the induc- tion of syntactic trees, while multi-layer CIO could alleviate the issue by contextualization during multiple rounds of bottom-up and top-down operations. Finally, we notice that ReACT [3, 1,3) has parameter size close to Transformerx9 but underperforms Transformerx This may stem from the difference in the number layers (i.e., v.s. 9). The results imply that the increase in parameters of the independent Compose functions in the inside and outside pass cannot reduce the gap brought by the number of layers. It is noteworthy that B2D2+Transforman especially on CoLA, indicating that syntactic information learned from a few human annotations is less useful than that obtained by learning from vast amounts of data.
explicit span representations is capable of modeling
is worse than Fast-
4.3 STRUCTURE ANALYSIS
We further evaluate model unsupervised grammar induction and analyze the accuracy of syntactic trees induced by our model.
8

---

Published as a conference paper at ICLR 2024
Model
NNP
VP
ADJP
mem.
PTB
Model
cplx
F((e))
Fast-R2D2
83.44
63.80
70.56
68,47
Fast-R2122m--
O(a)
57.22
ReCAT share 3. 1,3 m==
77.22
67.05
66.53
69,44
ReCATTaum (3. mm34
O(n)
56.07
ReCAT share 1, m-d
85.41
66.14
68.43
72.92
ReCAT shure (3, 1,33,,ma
O(n)
55.11
ReCAT noshare [3, 1,1,3]m
80.36
64.38
80.93
80.96
ReCAT mnsture [3, 1, smd
O(n)
65.00
ReCAT noshare 3, 1,3
81.71
70.55
82,94
78.28
ReCAT (3, 1.3] m-1
O(n)
64.06
m-4
ReCAT noshure wio mnd
O(n)
45,20
For Reference
Table 4:
Left table: Fl score unsupervised parsing on PTB dataset. Values with f and & are taken from Yang et al. (0022 and et al.] (2021) respectively.
C-PCFG
O(ne)
55.21
NBL-PCIG
((n))
60.41
TN-PCFG
(nn²)
64.11
Upper table: Recall of constituents.
ON-LSTM
O(n)
47.71
Word-level: NNP (proper noun). Phrase-level: VP (Verb Phrase),
S-DIORA
O(n²)
57.61
(Noun Phrase), ADIP (Adjective Phrase).
StructFormer
O(n²)
54.03
Samples of deduced trees can be found in Appendix A.7
Baselines & Datasets. For fair comparison, we select Fast-R2D2 pre-trained on Wiki-103 as the baseline. In both models, only the top-down parser after training utilized during test. Some works have cubic complexity, and thus not feasible to pre-train over large corpus. Therefore, we only report their performance on PTB (Marcus et al. 1993) for reference. These works include approaches specially designed for grammar induction based on PCFGs such as C-PCFG (Kim et al.) 2019a), NBL-PCFG (Yang et al. 202I). and TN-PCFG (Yang et al. (022), and approaches based on language modeling tasks to extract structures from the encoder such S-DIORA (Drozdov et al. 2020). ON-LSTM (Shen et al.) 2019b), and StructFormer (Shen et al. 202T).
Training details. We pre-train our model on Wiki-103 for 60 epochs, and then continue to train it on the training set of PTB for another 10 epochs. We randomly pick 3 seeds during the continue- train stage, then select the checkpoints with the best performance on the validation set, and report their mean fl on the test set. As our model takes word pieces as inputs, align with other models with word-level inputs, we provide our model with word-piece boundaries as non-splittable spans.
Results and discussions. Table 4 reports the evaluation results. ReCAT significantly outperforms most of the baseline models in terms of F1 score and achieves comparable performance with TN- PCFG which is specially designed for the task. Moreover, from the cases shown in Appendix AA.7] one can see strong consistency between the structures induced by ReCAT and the gold trees obtained from human annotations. The results indicate that the CIO layers can recover the syntactic structures of language, even though the model learned through fully unsupervised approach. The induced structures also greatly enhance the interpretability of Transformers since each tensor participating in self-attention corresponds to an explicit constituent. We also notice a gap between ReCAT share and ReCAT noshare. To further understand the difference, we compute the recall of different constituents, as shown in the right table in Table 4 We find that both models work well on low-level constituents such as NNP, but ReCAT noshore is more performant on high-level constituents such as ADJP and NP. Considering the intrinsic difference
the meaning of the Compose function for the inside and outside passes, non-shared Compose functions may cope with such discrepancy in better way. Despite of this, when referring to Table 3, we do not see a significant difference between ReCAT shere and ReCAT noshere downstream tasks. A plausible reason might be that the self- attention mechanism mitigates the gap owing to the structural deficiencies in its expressive power. The pruning threshold m only has a limited impact on the performance of the model on grammar induction, which means that we can largely reduce the computational cost by decreasing m without significant loss on the learned structures.
5 CONCLUSION & LIMITATION
We propose ReCAT, recursive composition augmented Transformer that combines Transformers and explicit recursive syntactic compositions. It enables constituents at different levels to commu- nicate directly, and results in significant improvements on span-level tasks and grammar induction.
The application of ReCAT could be limited by its computational load during training. A straight- forward method is to reduce the parameter size of CIO layers. Meanwhile, the limitation can be mitigated to a significant extent under the fast encoding mode described in Appendix during the fine-tuning and the inference stage, whose total cost is around 2 3x as the cost of Transformers.

---

Published as a conference paper at ICLR 2024
6 ACKNOWLEDGEMENT
This work was supported by Ant Group through the CCF-Ant Research Fund.
REFERENCES
James K. Baker. Trainable grammars for speech recognition. Journal of the Acoustical Society of America, 65, 1979.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, lya Sutskever, and Dario Amodei. Language models are few-shot learners. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020. December 6- 12, 2020, virtual, 2020. URL https: 42ff44ff4424 Abs http://iiinnnnnnrrs.....ooopapep
(457cod4bfcb496741555 wwweeBaccc2ff4444
Francisco Casacuberta. Statistical estimation of stochastic context-free grammars using the inside- outside algorithm and transformation on grammars. In Rafacl C. Carrasco and José Oncina (eds.), Grammatical Inference and Applications, Second International Colloquium, ICGI-94, Alicante, Spain, September 21-23, 1994, Proceedings. volume 862 of Lecture Notes in Com- puter Science, pp. 10070..1.010000 540-
Springer, 1994. doi: 10.1007/3-540-554770001
URL https:
142
Jihun Choi, Kang Min Yoo, and Sang-goo Lee. Learning to compose task-specific tree structures. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial In- telligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp- 5094-5100 AAAI Press. 2018 CXLLattss:/// /ww. http://wwaaaaa.... www.oos.//ooooooooooooooooooooo/ wwtp///xc////.i.oo//////o http://AAAAAAAAAA1/ppppe//////
1 16682
Jishnu Ray Chowdhury and Cornelia Caragea. Modeling hierarchical structures with continuous recursive neural networks. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 1975-1999999 1988. PMLR, 2021. URL http::/proceedinng wtw.://s.......sssssrem htwp:3////hoodury2.aa......
Jishnu Ray Chowdhury and Cornelia Caragea. Efficient beam tree recursion, 2023.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA. June 2-7, 2019, Volume I (Long and Short Papers), pp. 4171- 4186. Association for Computational Linguistics, 2019. doi: 10.18653/v1/119-4443 URL 1423.
https://dci http://ii..rr///// 1tt.:/1...111111111111 18653/vl
Andrew Drozdov, Patrick Verga, Mohit Yadav, Mohit lyyer, and Andrew McCallum. Unsupervised latent tree induction with deep inside-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 (Long and Short Papers), pp. 1129-1141, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.18653/vI/N19. 1116.
https: www. web www../gg//a.aooooooooooooooooo egy 1-1NN111111 1116
10

---

Published as a conference paper at ICLR 2024
Andrew Drozdov, Subendhu Rongali, Yi-Pei Chen, Tim O'Gorman, Mohit lyyer, and Andrew Me- Callum. Unsupervised parsing with S-DIORA: single tree encoding for deep inside-outside re- cursive autoencoders. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceed- ings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pp. 4832-4845. Association for Computational Linguis- tics, 2020. doi: 11111666//11222.cmmmlpp-- 392. URL httpp:://:/dd http:s////oo..cggg...88633/// 2020 www.eennnnnmmnmme 392
Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith. Recurrent neural network grammars. In Proceedings of the 2016 Conference of the North American Chapter of the Asso- ciation for Computational Linguisties: Human Language Technologies, pp. 199-209, San Diego, California, June 2016. Association for Computational Linguistics. doi: (0.188633/1/N166 1024. ac
URL https: www.walwwwwoo..o. www../wwww..rg////hhcclg//////// 6-
Xiang Hu, Haitao Mi, Zujie Wen, Yafang Wang. Yi Su, Jing Zheng, and Gerard de Melo. R2D2: Recursive transformer based on differentiable tree for interpretable hierarchical language model- ing. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp.
Online, August 2021. Association for Computational Linguisties. doi: 10.18653/v 1/2021 acl-long.379, URL /tr.psss//aclannhoooyyooooo
actpe2...ccllee lonelllong... 379
Xiang Hu, Haitao Mi, Liang Li, and Gerard de Melo. Fast-r2d2: A pretrained recursive neural network based on pruned CKY for grammar induction and text representation. In Yoav Goldberg, Zoriissa Kozareva, and Yue Zhang (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022, pp. 2809-2821. Association for Computational Linguistics, 2022. URL https://acl
emnlp-ma 181
Xiang Hu, Xinyu Kong, and Kewei Tu. A multi-grained self-interpretable symbolic-neural model for single/multt-labeeles text classification. The Eleventh International Conference on Learn- ing Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL https::/ net. /tte//dff... pdf? 2id-LL1SIMSEEEEE
Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel Weld, Luke Zettlemoyer, and Omer Levy. Span- bert: Improving pre- tre-trainin by representing and predicting spans. Trans. Assoc. Comput. Lin- guistics, 8:64-77, 2020.
doi: 10. 162/tacl) a), 00300. URL httpt::t////t //oii http///o.oogg////// org//10.112/
Eacl 00300
Yoon Kim, Chris Dyer, and Alexander Rush. Compound probabilistic context-free grammars for grammar induction. In Proceedings of the 57th Annual Meeting of the Association for Compu- tational Linguistics, pp. 2369-2385, Florence, Italy, July 2019a. Association for Computational Linguisties. doi: 10. 10.18653//1/P19-1225
Yoon Kim, Alexander Rush, Lei Yu, Adhiguna Kuncoro, Chris Dyer, and Gábor Melis. Unsu- pervised recurrent neural network grammars. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Compulational Linguisties: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 1105-1117, Minneapolis, Minnesota, June 2019b. Association for Computational Linguisties. doi: 10.18653/11/19--1144 URL
Chen Liang, Jonathan Berant, Quoc V. Le, Kenneth D. Forbus, and Ni Lao. Neural symbolic ma- chines: Learning semantic parsers freehase with weak supervision. In Regina Barzilay and Min-Yen Kan (eds.), Proceedings of the 55th Anmual Meeting of the Association for Computa- tional Linguistics, ACL 2017, Vancouver, Canada, July 30- August 4, Volume 1: Long Papers, pp. 23-33. Association for Computational Linguistics, 2017. doi: 0.11653/v1//11--1000 URL http:://dd...rg/11118535333
Jean Maillard, Stephen Clark, and Dani Yogatama. Jointly learning sentence embeddings and syntax with unsupervised tree-Istms. CoRR, abs/1 (05.99189, 2017. URL Intpp:/ http///axvvvv/. www.v..rrg/aaa. abs/
705. 09189
11

---

Published as a conference paper at ICLR 2024
Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313-33 1993. URL
https: /wwww./www........//////////.. http://.wwwwww..../ acwweb.w....... org/ wtt.a//ooloy/y////////.//
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In 5th International Conference on Learning Representations, ICLR 2017. Toulon,
France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https:
OpenAL. GPT-4 technical report.. CoRR, abs/2ab3.08/77777 2023. doi: 10:48500/rXii.2233.87744
URL htttp:://do..rrg/ http:///....r/1.....////////////
40550044550000100 http://wwwwvvvvvv..... 08704
Barbara H. Partee. Lexical semantics and compositionality. 1995.
Jordan B. Pollack.
Recursive distributed representations. Artif. Intell,, 46(1-2):77-105, 1990.
doi: 10:01660004-77009900000--4 URL https::/dci..org//// 101 6/0064000000000000 30000000000000000000000
90005-K K
Jishnu Ray Chowdhury and Cornelia Caragea. Beam tree recursive cells. In Proceedings of the 40th International Conference Machine Learning, 2023.
Laurent Sartran, Samuel Barrett, Adhiguna Kuncoro, Milos Stanojevic, Phil Blunsom, and Chris Dyer. Transformer grammars: Augmenting transformer language models with syntactic induc-
tive biases at scale. Trans. Assoc. Comput. Linguistics, 10:1423-1439, 2022. URL https:
//transacl.crg///5s// s/inddxxxxxx.oo
Yikang Shen, Shawn Tan, Seyed Arian Hosseini, Zhouhan Lin. Alessandro Sordoni, and Aaron C. Courville. Ordered memory. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 0038-5049, 2019a. URL 1B52144e7777500cddaa2222aeaaa a Abstract.htm
hew.sinn..............r..... neurips. cc/papprr2019//aaat
Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron C. Courville. Ordered neurons: Integrat- ing tree structures into recurrent neural networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019b. net
URL httpp:://ppereeiiiiie wttp::/wwweeeueeeeeeeeeee forum/oorm?? 1116giR5F)
Yikang Shen, Yi Tay. Che Zheng, Dara Bahri, Donald Metzler, and Aaron C. Courville. Struct- former: Joint unsupervised induction of dependency and constituency structure from masked language modeling. In Chengging Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Proceed- ings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference Natural Language Processing, ACI/IJCNP 2021, (Volume 1; Long Papers). Virtual Event, August 1-6, 2021, pp. 7196-720000 Association for Computational Linguistics, 2021. doi: 111113/v122221111 v1 02/2021.ac/ awl.oong...11...0 559
htwp:////22...lloooo...... wol.acll....55511 559. URL https: http::://doi.oo http://i.i..g11111......
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng. and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, EMNLP 2013, 18-21 October 2013, Grand Hyatt Seattle, Seattle, Washington, USA, meeting of SIGDAT, a Special Interest Group of the ACL, pp. 1631-1642. ACL, 2013. URL httpss://ac.anthhllogg.. wrwppyy..rg/1111110000
Shubham Toshniwal, Haoyue Shi, Bowen Shi, Lingyu Gao, Karen Livescu, and Kevin Gimpel. A cross-task analysis of text span representations. In Proceedings of the 5th Workshop on Rep- resentation Learning for NLP, pp. 166-176, Online, July 2020. Association for Computational Linguistics. doi: 18.18653/v 1/2.6633/1122200rpl444lz.g 1.20. URL http::/:///aaaaaaooooooooo ott.aaatttooooyoorr/2220002 org/2C2C.
repp4n1 4n11p111p12
12

---

Published as a conference paper at ICLR 2024
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus. S. V. N. Vishwanathan, and Ro- man Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Confer- ence Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA. pp. 1998-6008 2017. URL/attps::/proceddii wtwp:/ccedddnnn...n........... wtwp:r/ppp..cppppp////////////// 335o25544oe1300551444ttooooooee
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bow- man. GLUE: A multi-task benchmark and analysis platform for natural language understand- ing. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https:://ppeneevlov fct/forummid=
DJ 7J4km2R5t7
Ralph Weischedel, Martha Palmer, Mitchell Marcus, Eduard Hovy, Sameer Pradhan, Lance Ramshaw, Nianwen Xue, Ann Taylor, Jeff Kaufman, and Michelle Franchini et al. OntoNotes release 5.0 LDC2013T19, Linguistic Data Consortium, 2013.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierrie Cistac, Tim Rault, R'emi Louf, Morgan Funtowicz, and Jamie Brew. HuggingFace's Transformers: State-of-the-art Natural Language Processing. arXiv, abs/1910.03771,, 2019.
Songlin Yang, Yanpeng Zhao, and Kewei Tu. Neural bi-lexicalized PCFG induction. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACI/IJCNLP 2021, (Volume I: Long Papers), Virtual Event, August 1-6, 2021, pp. 2688-2699, Association for Computational Linguistics, 2021. doi: 10. 18653/v1/2021 aacl-long. 209. https::/s///:. http://66....c./.....8./////000. acl long. 209
Songlin Yang, Wei Liu, and Kewei Tu. Dynamic programming in rank space: Scaling structured inference with low-rank HMMs and PCFGs. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics; Human Language Tech- nologies, pp. 4797-4809, Seattle, United States, July 2022. Association for Computational Lin- guistics. doi: 10.18653/v122022.nm maacl-main.33. URL
wwwp:/oooooooooog/222e222e2 2222.
naacl main.
Dani Yogatama, Phil Blunsom, Chris Dyer, Edward Grefenstette, and Wang Ling. Learning to compose words into sentences with reinforcement learning. In 5th International Conference on Learning Representattonns, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Pro- ceedings. OpenReview.net, 2017. URL /tttpss://ppezeeiiieeeeee net htt.:e//oooonl..-sssggsrrr
Yu Zhang, Houquan Zhou, and Zhenghua Li. Fast and accurate neural CRF constituency parsing. In Christian Bessiere (ed.), Proceedingy of the Twenty-Ninth International Joint Conference Artificial Intelligence, IJCAI 2020, pp. 4053-4053, ijcai.org, 2020. doi: 10.24963/ijcai 2020/5660. 20200500.....22005500.
| htt:://ci.oogo////// 220 2020/505600220000
13

---

Published as a conference paper at ICLR 2024
A APPENDIX
A.1 PARALLELED IMPLEMENTATION FOR OUTSIDE
Unlike the inside pass in which the count of the inside pairs for given span is most, the count of the outside pairs for a given span is not determined. Thus this brings extra difficulty compute weighted outside representations. To compute outside representations efficiently, propose a cumulative update algorithm. We traverse span batches in the reverse order of B and then compute the outside representations for their immediate sub-spans and update their weighted outside representations by cumulative softmax as follows:
Te 1:6-17
Soflmaxx
) beumlt log(exp(beum))t)) exp(B,
(6)
she-1 1
& [D], 10 = bi w(.
As a sub-span may be updated many times, we denote the outside score at 1-th time as [ (P) 1.0 We initialize boum as -cc. Thus once all parents are traversed, the final result of det equivalent to the result computed according to Equation 3
4 will be
A.2 HYPERPARAMETERSS
For all baselines, we the same vocabulary and hyperparameters but different layer numbers. We follow the setting in Devlin et al. (2019), using 768- -i--diensiionl embeddings, a vocabulary size of 30522, di7e-dimensi hidden layer representations, and 12 attention heads as the default setting for the Transformer. The top-down parser of our model uses 4-layer bidirectional LSTT with 128-dimensional embeddings and 256-dimensional hidden layer. The pruning threshold is set to 2. Training is conducted using Adam optimization with weight decay using learning rate of 10 for the tree encoder and 1 10-3 for the top-down parser. Input tokens are batched by length, which is set to 10240. We preitrain all models on 8 A100 GPUs.
A.3 FAST ENCODING
After pre-training, one can exploit ReCAT encode sequence of tokens. Though the complexity of the inside-outside process ((n) with n the length of the sequence, the computational load still many times higher than that of the vanilla Transformer. Specifically, the complexity of single CIO layer is 0(m²n) with m the pruning threshold (set as 2 in our experiments). Please refer Appendix A.6 for detailed efficiency analysis. To further speed up encoding in fine-tuning and evaluation, we follow the force encoding proposed in Fast-R2D2 Specifically, we directly use the pretrained top-down parser predict parse tree for a given sentence and apply the trained Compose functions to compute contextualized representations of nodes following the tree and feed them into Transformer.
A.4 BASELINE SETUPS
The DIORA variant uses the linear onsidc-outside and a Transformer-bused Compose function just as our model but still with the information access constraint. We also include an RvNN variant with trained parser Zhang et al. (2020). The parser provides constituency trees and we use the encoder of Fast-R2D2 to compose constituent representations following the tree structure. The parser is trained with gold trees from Penn Treebank(PTB) (Marcus al.) 1993). Except for the RvNN+Parser baseline, all other models have no access to gold trees. For fair comparisons, we further combine F2st-R2D2, DIORA, and RvNN+Parser with Transformer by taking their node representations as the input of the Transformer and name the models 22D2+Transformes DIORA+ Transffrrrrrrrrr and Parser+Trane Transformer respectively.
14

---

Published as a conference paper at ICLR 2024
A.5 IMPROVED PRUNING ALGORITHM
We propose an improved implementation of the pruning algorithm which could reduce the steps to complete the inside algorithm from approximate log(n). Such improvement could largely increase the training efficiency under parallel computing environments like GPU groups. The key idea to simultaneously encode all cells whose sub-span representations are ready, thus more cells could be encoded in one batch even if they are not on the same row. To achieve this goal, we just need build the encoding order of the cell batches according to the merge order, which is shown in Algorithm
Once the cell dependency graph is built, the cells at the bottom row are set ready. Once a cell is set to ready, will notify the higher-level cells that depend on Once all sub-spans of cell are ready, the cell will be encoded in the next batch.
Algorithm 2 Build cell batches
1: function BUILD_CELL BULLDCCELLDEPENEENCISSS
T)
2:
B is the encoding order after pruning descrihed in Section 3.1.1 T is the chart table.
3: for (1,j) E B do for E Ki., do append( N (1, append( J N, (i,j))
b is splits for span (i.j). > Add (i.j) to the notify list. Once (i, k) is encoded, inform (i.j).
5:
6:
7:
8:
function BUILD.CELLS T)
BUB.D.CCHL.DEPEEDEECCCCC
10:
B
=
Rebuild new encoding orders of cells
11:
12:
Q =|
13:
for E 0 T.lenggh do Tr..ready = true append( Q Tr.)) for c do
b Ready default false for each cell.
15:
16:
Iterate ready cells the batch
17:
for (i, E C.VV do if all sub-spans of Tr are ready & [Tg > 0 then If cell does participate in the encoding of higher-level cells, there need to encode it. Teg.ready = true
18:
19:
20:
21:
append( @neett Ti,))
22:
append(B, @next)
Cells to encode single step in the inside-outside algorithm
23:
Q = Onext
24:
return
A.6
EFFICIENCY ANALYSIS
2000
Fast-R2D2
1750
ReCAT
1500
Inside MLPP Runs
1250
1000
500
250
0
100
150
200
Seq Len
Figure S: MI.P runs for the inside pass.
15

---

Published as a conference paper at ICLR 2024
Fast-R2D2
175
ReCAT
Inside Steps
125
100
75
50
/ Mww //
25
0-
50
100
150
200
Seq Len
Figure 6: Steps for the inside pass.
1200
Fast-R2D2
1000
ReCAT
Running Time (scconds)
800
600
200
0
32
48
64
80
96
Batch Size
Figure 7: Practical training time.
To further study the efficiency improvement compared with the original pruning algorithm, we com- pare the MLP runs, inside steps, and training time of CIO layers using the original pruning algorithm versus our improved version.
set the pruning threshold m to 2 and limit the input sentence length ranging from 0 to 200. We keep the model architecture the same but only differ in the pruning algo- rithm. We denote the original pruning algorithm as Fast-R2D2 and the improved one as ReCAT. The total training time is evaluated on 5,000 samples with different batch sizes on 1 A100 GPU with 80G memory. The result is shown in Figure Figure and Figure 7 The overall FLOPS is reduced by around 1/3. As can find from the result, the total training time has significant improvement.
16

---

Published as a conference paper at ICLR 2024
A.7 SAMPLES OF LEARNED CONSTITUENCY TREES
ReCAT:
The Dow Jones Industrial Average tumbled 39.55 points to 2613.73 in active trading
gold tree:
The Dow Jones Industrial Average tumbled 39.55 points to 2613.73 in active trading
ReCAT:
The bleak automotive results were offset by strong carnings from some non-automotive operations
gold tree:
The bleak automotive results offset strong earnings from some non-automotive operations
ReCAT:
Merrill Lynch Capital Markets Inc. is the sole underwriter for the offering
17

---

Published as a conference paper at ICLR 2024
gold tree:
Merrill Lynch Capital Markets Inc. is the sole underwriter for the offering
ReCAT:
The market 's pessimism reflects the gloomy outlook in Detroit
gold tree:
The market 's pessimism reflects the gloomy outlook in Detroit
ReCAT:
Nearly all the decline came in Ford 's U.S. automotive operations
gold tree:
Nearly all the decline came in Ford 's U.S. automotive operations
18


Reviews:
[{"review_id": "v1Xqxi8jag", "reviewer": "Reviewer_FCy4", "summary": "The paper proposed to augment the Transformer architecture with a contextual inside-outside layer (CIO). The CIO layer model explicitly the recursive syntactic compositions. The CIO layer goes in between the embedding layer and the self-attention layer. The author proposed a new variant of the inside-outside algorithm with contextualization ability. The CIO layer allows modeling of the inter-span and intra-span interactions. Experiments show that the proposed method outperforms the plain Transformer models on span-level tasks. It also outperforms recursive models on natural language inference tasks. The CIO also has good interpretability since it has strong consistency with human-annotated syntactic trees.", "questions": "1. It would be interested to see if the gains still holds when we scale to larger models. (It is recognized it's not always possible/easy to experiment with a larger model.)\n2. I'm wondering if the CIO layer can be trained at the finetuning stage so that we can still utilize a powerful pre-trained model and augment it with the CIO layer only at the finetuning stage.\n3. This might be diverging or outside the scope of the paper, but I'm curious how tokenization would be affecting the effectiveness of the proposed method. For example, if it's byte or character-level vocabulary, do we observe a similar gain.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The author proposed a novel method that include the recursive syntactic composition information into the Transformer architecture. The method is verified to be effective, especially for span-based tasks, by experiments with", "weaknesses": "As authors pointed out, the CIO layer can be expensive. I'm also wondering how is the effect", "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": "", "extra_scores": {}}, {"review_id": "qdjcm8r2Ac", "reviewer": "Reviewer_46mR", "summary": "The paper proposes a syntax-augmented transformer based on producing span representations following the inside and outside traversals of a parse chart. Unlike existing methods following this idea (Fast-R2D2, DIORA), they incorporate cross-span contextualization. The resulting architecture is competitive with vanilla transformers on span-level and GLUE tasks while achieving strong grammar induction results.", "questions": "(1) I find it a bit surprising that Fast-R2D2+Transformer is worse than Fast-R2D2 on GLUE (Table 3). Is there some intuition for why this is the case?\n\n(2) Is there an ablation for ReCat without extra transformer layers?\n\n(3) What are the model sizes for ours_{share} and ours_{noshare} in Table 2?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "(1) The method performs well compared to both transformers and Fast-R2D2 on span-level and sentence-level tasks, while also achieving strong grammar induction results.\n\n(2) The method is evaluated on a wide range of tasks and compared to a wide range of baselines.", "weaknesses": "(1) As the authors mention, one of the main motivations for augmenting transformers with syntax is to improve compositional generalization (as well as potentially interpretability and controllability). Therefore, while the method does outperform transformers for span-level tasks, I think the results would stronger if there were experiments addressing these original motivations.\n\n(2) While I understand that the method is inherently complex, I still think the methods section could be made a little clearer. For example, maybe a self-contained step-by-step summary of the algorithm at the end of the section would be helpful.\n\n(3) While their method does outperform Fast-R2D2, the ideas feel very similar, limiting the scientific contribution of this work. As it stands, it feels a bit like a complex combination of ideas from Fast-R2D2 and DIORA, where the takeaway is a bit unclear. Is the key difference scalability, the use of transformers, pruning, cross-span communication, or all of the above? If the key difference is cross-span communication, why is that important and what are the specific changes in the algorithm that enable this difference? And are there ablation experiments that support the claim that cross-span communication is important?\n\n(4) Related to (3), the paper would benefit from ablations to support the claims of why certain design decisions were effective.", "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": "", "extra_scores": {}}, {"review_id": "JV5gThDNtj", "reviewer": "Reviewer_fRFA", "summary": "This paper proposes contextual inside-outside (CIO) layers to explicitly model the syntactic structures of raw text in the encoding process of Transformers. The CIO layers are driven by a variant of the inside-outside algorithm proposed by DIORA (Drozdov et al. (2019) ). The authors leverage the linear neural inside algorithm proposed by R2D2 to prune cells that are unnecessary to encode during the bottom-up inside pass and propose to mix information from both inside and outside a span.\n\nThe benefits brought by CIO include (1) explicitly modeling syntactic structures without requiring parse tree annotations; (2) unlike previous work which only allows information flow within a span, CIO enables cross-span communications in a scalable way; (3) reducing the complexity of the inside-outside algorithm from cubic in DIORA to linear.\n\nThe major contributions are: (1) effectively combining ideas from two methods DIORA and R2D2 with innovative modifications. (2) introducing cross-span communication that breaks the information access constraint. (3) the experimental results on span-level tasks, natural language inference, and grammar induction demonstrate the effectiveness of the proposed method.", "questions": "- How do you deal with sub-word tokens: if a word is broken into multiple tokens, how do you handle them in the CIO layer?\n\n- In 3.3, you mentioned “Specifically, we directly use the pretrained top-down parser to predict a parse tree for a given sentence and apply the trained Compose functions”, does this mean that your method requires a pretrained top-down parser?\n\n- Is it necessary to train the Transformer from scratch in the experiments? One way of using CIO layers is to use them as adaptors which can be plugged into multiple transformer layers. Training a model from scratch can impose significant computational cost and it could be more efficient to harness the pretraining of existing Transformers instead of training from scratch.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Proposed an effective method to explicitly model the syntactic structure in the encoding process of transformers.\n\n- It’s interesting to see that the Vanilla MLM can be used to replace the training objective of DIORA and the model can effectively learn the syntactic structure with the simple MLM objective.\n\n- Results show that CIO can improve the transformer’s performance on span-based tasks and even help it to learn syntactic trees in an unsupervised manner.", "weaknesses": "- Contribution is not significant: the proposed method is an effective way of combining ideas of the inside-outside algorithm from DIORA and node-pruning algorithm from R2D2 with modifications to fit them into the transformer framework and address some weaknesses in DIORA and R2D2 such as the lack of communication between spans.\n\n- Efficiency is low: (1) as mentioned by the author, the computational load is many times higher than that of the vanilla Transformer model and the complexity of a single CIO layer is O(m2n). (2) If using fast-r2d2, the CIO layer needs a pre-trained top-down parser to predict a parse tree for a given sentence.\n\n- The major performance improvement is on Span-level tasks, and on sentence-level tasks ReCAT achieves worse performance compared with a vanilla transformer with similar size. On the structure-prediction task, ReCAT achieves similar performance compared with the previous method TN-PCFG.", "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": "", "extra_scores": {}}, {"review_id": "HWeb8Hmxn6", "reviewer": "Reviewer_m86F", "summary": "This paper proposes Recursive Composition Augmented Transformer (ReCAT), a model that aims to explicitly incorporate syntactic and structured trees into Transformers. The main change of ReCAT is the proposed contextual inside-outside (CIO) layers, which are inserted into a standard Transformer encoder right after the embedding layer. The CIO layer consists of the bottom-up and top-down modules. By stacking CIO layers, the iterative bottom-up and top-down layer-by-layer passes can unsupervisedly construct syntactic structures for the input sequence and produce contextualized representations for tree nodes.\n\nBy pre-trained with masked language modeling (MLM) and then fine-tuned, ReCAT was compared with Transformer-only methods and Fast-R2D2 and showed superior performance on multiple sentence-level and span-level tasks. Moreover, the syntactic trees induced by ReCAT exhibit strong consistency with human-annotated trees, proving that CIO layers can accurately learn syntactic structures.", "questions": "- What are the advantages of the proposed method compared with Fast-R2D2?\n- What is the computational cost and complexity of the proposed layers?\n- How to choose the hyperparameters and the model configurations of the ReCAT models?\n- Can the proposed method be incorporated and augmented to pre-trained models like BERT?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- It is interesting and useful to augment transformers with multi-grained representations in an unsupervised manner.\n- The proposed method is practical and effective based on the downstream task evaluation.", "weaknesses": "- The paper is poorly written, with many notations without explanation. Figure 2 is a copy from Figures in Fast-R2D2, with an unclear caption.\n- Lack of important details, e.g. the computational cost of the proposed layers, how to choose the number of layers, and the hidden dimension of the stacked CIO layers.\n- It would be helpful to explain the main differences and advantages of the proposed method compared with related works, e.g. Fast-R2D2.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)