Approximating CKY with Transformers
Authors: Ghazal Khalighinejad
Ollie Liu
Sam Wiseman
Venue: EMNLP 2023 Findings (2023)
Keywords: transformer
algorithmic reasoning
dynamic programming
constituency parsing
TL;DR: We investigate the ability of transformer models to learn the CKY algorithm.

Abstract: We investigate the ability of transformer models to approximate the CKY algorithm, using them to directly predict a sentence's parse and thus avoid the CKY algorithm's cubic dependence on sentence length. We find that on standard constituency parsing benchmarks this approach achieves competitive or better performance than comparable parsers that make use of CKY, while being faster. We also evaluate the viability of this approach for parsing under \textit{random} PCFGs. Here we find that performance declines as the grammar becomes more ambiguous, suggesting that the transformer is not fully capturing the CKY computation. However, we also find that incorporating additional inductive bias is helpful, and we propose a novel approach that makes use of gradients with respect to chart representations in predicting the parse, in analogy with the CKY algorithm being a subgradient of a partition function variant with respect to the chart.

Approximating CKY with Transformers
Ghazal Khalighinejad
Ollie Liu
Sam Wiseman Duke University
Duke University gk gk126@duke.edn
University of Southern California
zliu2898 @ usc.edu
swiseman @ cs.duke.edu
Abstract
networks more generally, to implement or approxi- mate classical algorithms (Xu al., 2019; Csordás et al., 2021; Dudzik and Veličković, 2022; Delétang et al., 2022, inter alia).
We investigate the ability transformer mod- els to approximate the CKY algorithm, using them to directly predict a sentence's 's parse and thus avoid the CKY algorithm's cubic depen- dence sentence length. We find that stan- dard constituency parsing benchmarks this ap- proach achieves competitive better perfor- mance than comparable parsers that make use of CKY, while being faster. We also evaluate the viability of this approach for parsing under random PCFGs. Here we find that performance declines as the grammar becomes more ambigu- ous, suggesting that the transformer is not fully capturing the CKY computation. However, we also find that incorporating additional induc- tive bias is helpful, and we propose novel approach that makes use of gradients with re- spect chart representations in predicting the parse, in analogy with the CKY algorithm be- ing subgradient partition function variant with respect to the chart.
indeed approxi- mating CKY, there would be several implications. Practically, such a finding might lead to faster neural parsers. Whereas statc-of-the-ar parsers (e.g., that of Kitaev and Klein (2018) and follow- up work (Kitaev et al., 2019; Tian et al., 2020)) tend to implement CKY on top of transformer- representations, thus incurring parsing time- complexity that is cubic in the sentence length, could conceivably extract a parse from sim- ply running a transformer over the sentence; this would involve a time-complexity cost that is only quadratic in the sentence length. Moreover, since there is significant academic and industrial effort aimed at making standard transformers faster (e.g.- that of Dao et al. (2022)), this progress could con- ceivably transfer automatically to the parsing case.
If standard transformers
In addition to more practical considerations, the task of producing CKY parses with transformers provides an excellent opportunity for investigating whether endowing transformers with additional in- ductive bias can help them in implementing classi- cal algorithms, topic recently studied by Csordás et al. (2021) and others. The results of such an investigation would also bear on recent results re- lating to the computational power of transformers trained in the standard way (Delétang et al., 2022; Liu et al.. 2023).
1 Introduction
Parsers based on transformers (Vaswani et al., 2017) currently represent the state of the art in constituency parsing (Mrini et al., 2020; Tian et al., 2020), and recent work (Tenney et al., 2019; Jawa- har al., 2019; Li et al., 2020; Murty et al., 2022; Eisape al., 2022; Zhao al., 2023) has found that transformers are capable of learning constituent- like representations of spans of text. Given these successes, it is natural to wonder whether trans- formers capture the algorithmic processes we asso- ciate with constituency parsing, such as the CKY algorithm (Kasami, 1966; Younger, 1967; Baker, 1979). Indeed, one might suspect that the layers of transformer are building up phrase-level represen- tations, much as the CKY algorithm itself builds up its chart. Such a hypothesis has become par- ticularly compelling in light of recent work study- ing the ability of transformers, and graph neural
Accordingly, we first show that having a pre- trained transformer simply predict an entire parse by independently labeling cach span - an ap- proach similar to that taken in a different con- text by Corro (2020) only at training time - is sufficient to obtain competitive or better perfor- mance standard constituency parsing bench- marks, while being significantly faster.
While these constituency parsing results are en-

---

couraging, they do not imply that trained trans- formers are implementing the CKY algorithm, be- cause the transformer may simply be predicting a parse without it being sighent-scoring under some grammar. We accordingly go on to investigate transformers' performance in predicting CKY parse under randomly generated PCFGs. Given randomly generated PCFG, it is of course easy to check whether a predicted parse is indeed highest- scoring. In this setting we find that the performance of transformers negatively correlates with the am- biguity of the PCFG, suggesting that they are not in fact implementing something CKY-like. At the same time, we find that incorporating additional in- ductive bias into the standard architecture is helpful, and we propose novel approach, which makes use of gradients with respect to chart representations in predicting the parse. This inductive bias is inspired by the fact that the CKY algorithm can be viewed as computing the gradient of the "max score" parti- tion function (Eisner, 2016; Rush, 2020), and we find that this improves performance on random PCFGs significantly.
of x under G, and it requires ( computa- tion time.
Following the notation in Rush (2020), let e R [RIR x[]]XX represent the log potentials (e.g., log probabilities) associated with the rules in PCFG G, and let (xx E R R'X represent the log poten- tials corresponding each token in input sentence 2, We can use these log potentials to compute the chart 3 [TxTx[W] for 2, where B[i. a) repre- sents the sum (under particular semiring) of all weight associated with the a-th non-terminal yield- ing Zej. These log potentials can also be used to compute a highest-scoring parse, which we will refer to 3 E {0, 1 1 x|Mi; this is the one-hot representation of parse, with 8 [i a] 1 iff j 2 and nonterminal a yields Tey in the parse.
CKY as subgradient Recent work (Eisner, 2016; Rush, 2020) has emphasized that inference algorithms such as CKY may be fruitfully viewed as a special case of calculating the gradient or a subgradient of a generalized log partition function with respect to (some function of) the log potentials associated with an input. In particular, the CKY algorithm can be viewed as computing subgra- dient of the "max score" variant of the log parti- tion function with respect to input sentence x's chart; see Appendix A for details. Thus, 9 is rela- tively easily obtained with automatic differentiation frameworks. However, computing in this way is exactly equivalent to running the traditional CKY algorithm, and so still requires (([[[T)) time.
In summary, we show that:
using transformers to directly predict parses performs competitively with explicit CKY- based approaches, while being faster;
this impressive performance is likely not due to transformers implicitly implementing the CKY algorithm, as they fail to accurately parse ambiguous synthetic PCFGs;
biasing the model to produce parses from gra- dients with respect to the chart signifcantly im- proves synthetic PFCG parsing performance.
Transformer-basee based CKY approximations The remainder of the paper focuses on training model (i.e., an inference network (Kingma and Welling, 2014: Johnson et al., 2016; Tu and Gimpel, 2018)) to predict 3 directly, in the hope of parsing more efficiently. Rather than use e and e (z) to recur- sively compute 3* as the traditional CKY algorithm does, compute 3 by differentiating with respect to 3, instead propose to simply train trans- former map sentence a correct 3 for it. The hope is that the trained transformer will learn represent information about the grammar implicitly in its weights, and that it can then be used with- out log potentials to parse unseen sentences from the same grammar. This approach is illustrated in schematic form in Figure 1.
Code for reproducing all experiments is available at https://gi thub. com/ cttc www.zalkaalggiinneeee.. approximating-ca
2 Background and Notation
The CKY algorithm (Kasami, 1966; Younger, 1967; Baker, 1979) computes a highest scoring parse of a sentence under probabilistic context- free grammar (PCFG). Let G = (N, Σ, R, W) be PCFG, with NN the set of non-terminals, Σ the set of terminals, R the of rules, S' start non-terminal, and W set of probabilities per rule (which normalize over left-hand-sides). Given a sentence x E ΣT, the CKY algorithm uses a dy- namic program to compute a highest scoring parse
We seek to evaluate our trained inference net- work's 'ss approximation to 3" on held-out sentences that are from the same distribution (i.e., sampled
2

---

training
inference
e
autbdlt
classical
N/A
"brool with jum"
(
"luaed
learned
(mn)
tanaformr
{
Figure I: schematic view of training and inference under the classical approach (top) and under learned transformer approximation (bottom). Classical parsing has no training phase, and uses pre-defined log potentials to parse unseen sentences. Our proposed learned parser (an "inference network") trains on pairs sentences and parses computed under of log potentials, and then parses unseen sentences without access the potentials.
from the same PCFG) as the training sentences. This contrasts with the vast majority of work on approximating classical algorithms with neural net- works (Graves et al., 2014; Kaiser and Sutskever, 2016), which instead evaluates performance out- of-distribution, and in particular longer, inputs than those on which the model was trained. We do not focus on length generalization, first because believe generalizing even in-domain is useful in parsing applications, and second because we find transformers trained on random PCFGs struggle to generalize even to inputs of the same length.
then define Big E A W as
B. def softmax(FFN((),.d)) h,.22.))))))) (1)
where above we have concatenated the first half of h; and the second half of h,, and where FFN BERT-like (Devlin al., 2019) classification head comprising a single hidden-layer, GELU non- linearity (Hendrycks and Gimpel, 2016), Layer- Norm (Ba et al., 2016), and final linear projection to W scores. This classification head produces score for each nonterminal label as well as for a non-constituent label. This representation is simi- lar to (but distinct from) that computed by Kitaev and Klein (2018) before using CKY top of the computed scores. We set the lower triangle of P (i.e., along the first two dimensions) to zero, and use it as our approximation of 3
CKY variants Modern span-based neural con- stituency parsers do not assume underlying PCFG. Rather, these parsers score spans compo- sitionally (Stern et al., 2017: Gaddy al., 2018; 8; Kitaev and Klein, 2018) using log potentials e E xTXXX/ produced by a neural network, such as a transformer. Such parsers use CKY variant that requires O computation time. We focus us- ing transformers to approximate both the classical CKY algorithm and this simpler variant.
Decoding Note that forming 3 from the h; is only quadratic sentence-length, and if can extract a parse from it in sub-cubic time we will im- prove (asymptotically) over CKY. In practice, we simply take the highest-scoring label for each span, and ignore spans for which the highest-scoring la- bel is non-constituent, We then sort the predicted spans, first in decreasing order of end-token and then (stably) in increasing order of start-token, and build up the tree from left right. We thus incur only an O ([W) + logz T)) decoding cost.'
3 Predicting Parses
As described in Section 2. we define 8 E {0, 1)7XTX AVl to be chart-sized tensor represent- ing a CKY parse of sentence x, with (* a] and only if nonterminal yields Tzy- We will use very simple approach to predict 3* with transformer.
Training Given a gold (binarized) parse S*, we simply treat predicting the labels of each span as T(T + 1)/2 independent multi-class classifi-
Let h, ddd be an encoder-only transformer's final-layer representation of the i-th token in ir and let h,.d/2 and h; d/ both d/2/ be (respec- tively) the first and last d/2 elements in h, We
Note this procedure only necessary for constituency parsing, where unary productions are allowed. For parsing PCFGs in CNF we simply take the 7' highest scoring spans.
3

---

cation problems, and we use the standard cross- entropy loss. Note that Corro (2020) proposes this training approach in the context of discontinuous constituency pars- ing (though with fixed zero-weight for the non- constituent label). We note that concureent work by Yang and Tu (2023) also explores both training and decoding by making span predictions indepen- dently.
propagation with respect to the h Fortu- nately, this is now simple to achieve with mod- ern auto-diferentiaation frameworks, such as Py- torch (Paszke et al., 2019), which we use in all experiments.
Discussion It is worth noting that while 3 is itself subgradient of the max score partition func- tion, our proposal above merely decodes 3 from the gradient of the inner score function. That is, the gradients g: are concatenated and fed into additional classification head, which is used to pro- duce something chart-sized. The reason for this discrepancy is computational: we were to feed something chart-sized into our score function, and if score required running transformer over its in- put, our approach would be quartic in T. Instead, our approach retains quadratic dependence T. Because it involves calculating gradients with spect the LTd-sized transformer representations, however, it in practice more expensive than using Equation (1); see Appendix C for details.
3.1 Decoding Parses from Chart Gradients
As described in Section (also see Appendix A), a CKY parse a subgradient of the "max score" par- utionn function, which calculates the maximum log (joint) probability under a PCFG of a sentence and its parse tree. If we are interested in making CKY- like predictions, then, it may be useful inductive bias to form predicted parse from the gradient of some scoring function, just as CKY does. We propose use a transformer to define this scoring function, and to predict parse from the gradients of this scoring function with respect to its inputs.
More concretely, again letting h; be an encoder- only transformer's final-layer representation of the i-th token in sentence x, we define the following "inner" score of x:
Constituency Parsing Experiments
We conduct experiments in two main settings. We first consider modern neural constituency parsing on standard benchmark datasets. We then consider parsing under randomly generated PCFGs. We highlight several important differences between these two settings. First, modern constituency pars- ing is grammarless. As such, modern constituency parsers do not predict the highest scoring parse under some PCFG, and they use a simpler vari- ant of CKY which composes spans but has no- tion of grammar-rules, While it is still interesting (at least from a computational efficiency perspec- tive) to see if directly predicting parses compet- itive with running this simpler CKY variant, it is difficult to distinguish a transformer learning this CKY variant from simply learning to predict gold parses. This concern motivates our second setting, of randomly generated PCFGs, where there are well-defined highest-scoring parses under each PCFG, and where we evaluate whether the transformer has predicted them. We consider this random PCFG setting Section 5.
T score(x) def FFN T
h.).
where FFN is a BERT-like classification head pro- ducing only single logit. Thus, we simply mean- pool over the transformer's final-layer token rep- resentations, and feed them to a feed-forward net- work to obtain a scalar score.
Let h.") denote an encoder-only transformer's 1-th layer representation of the i-th token. Since score is differentiable function of all the h,") may take gradients with respect to them. In particu- def 1 E/= V scoro( That is, g, is
lar, let g, the average of the gradients of score with respect to each transformer layer's 's representation of the i-th token. We can then form span-predictions from the gi substituting them for the h, in Equation (1), to obtain
g def Doftmax(FFN((( (.. B)./2.))
Datasets We conduct constituency parsing exper- iments on the English Penn Treebank (PTB; Mar- cus et al., 1993), the Chinese Penn Treebank (CTB; Xue et al., 2005), as well as the treebanks in the SPMRL 2013 and 2014 shared tasks (Seddah et al.,
In the remainder of the paper, we refer models making use of Equation (2) as "grad decoding." Training grad decoding model requires back- propagating parameter gradients through a back-
4

---

English
Chinese
German
Korean
Dev Set
Test Set
Dev Set
Test Set
Dev Set
Test Set
Dev Set
Test Set
Kitaev al. (2019)"
95.59
91.75
90.20
88,80
Kitacv et al. (2019)*
95.61
95.48
94.23
92.13
93.39
90.32
89.74
88.55
Ours
95.50
95.64
93.17
90.54
93.47
90.13
89.74
89.05
Ours + grad decode
95.07
96.16
93.75
91.25
93
89.63
89.26
88.46
Table 1: Comparison of Fi score on PTB, CTB, and the German and Korean treebanks from the SPMRL 2014 shared task. All models use the same pretrained initialization; see text for details. The Kitaev et (2019)* results are those reported in the paper, which make use of an additional factored self-attention layer, while Kitaev al. (2019)* are the results of running their code without this additional layer.
2013). We use the standard dataset splits through- out.
Inference Speed (sent/s)
PTB
CTB
Kitacv al. (2019) Ours
485 (1.0x)
704 (1.00x)
949 (1.96x)
1466 (2.08x)
Model Details We adapt the chart parser first pro- posed by Kitaev and Klein (2018), and later refined by Kitaev et al. (2019) to involve fine-tuning pre- trained model. In particular, while Kitaev al. (2019) fine-tune a pretrained BERT model (De- vlin et al., 2019) using a margin-based structured loss between the CKY parse and the gold parse, we instead fine-tune BERT to simply predict the parse as in Equation (I), and we train with the independent-span cross-entropy loss described in Section 3. Some of the experiments in Kitaev al. (2019) also make of additional fac- tored self-attention layer that consumes the BERT representations, but we do not use this layer when predicting according to Equations (I) or (2). Our implementation is a modification of the pub- lie Kitaev et al. (2019) implementation, which also forms our main baseline. While this parser is not always state-of-the-art, it is quite close, and otate-of-the-art parsers generally make use of its architecture and approach (Mrini al., 2020; Tian et al., 2020).
Table Inference speed (in sentences/second) of the CKY-based Kitaev et al. (2019) parser and our own, averaged over the PTB and CTB development sets.
which starts with 160 steps of warm-up. then de- creases the learning rate by multiplying by 0.5 when the F1 score stops improving. We used a grid- search to select hyperparameters, and we provide the grid search details and the optimal hyperparam- eters found in Appendix F.
Results In Table we report parsing results on these datasets, using the standard evalb evalua- tion. We find that our approach is competitive with the Kitaev et al. (2019) approach, slightly outper- forming it on the English and Korean datasets, and slightly underperforming it on the Chinese and Ger- man datasets (see Appendix D for the results on the rest of the SPMRL treebanks). this setting, grad decoding does not improve over simply using Equation (1). However, as we discuss in Section 5, sharing transformer layers is important in seeing the benefits of grad decoding, which we cannot do effectively with pretrained BERT models.
The pretrained models used to initialize both the Kitaev et al. (2019) model and our own for the English and Chinese treebanks are BERT-large- uncased (Devlin et al., 2019) and BERT-base- chinese?, respectively: BERRT-bae--mulilinnua- cased (Devlin et al., 2019) used to initialize models for Korean, German, and the rest of the SPMRL treebanks (see Appendix D). As the im- plementation of Kitaev et al. (2019), we train with AdamW (Loshchilov and Hutter, 2018; Kingma and Ba, 2015) until validation parsing performance stops increasing. We use the same learning rate scheduler as suggested in Kitaev al. (2019),
The fact that our simplest approach competi- tive on these constituency parsing benchmarks is interesting, given that it is much faster. In Table 2 we compare the speed of our approach (in sentences parsed per second) to that of the baseline parser, and we see it is roughly two times faster. These numbers reflect the time necessary to parse the PTB and CTB development sets using the Kitaev et al. (2019) parser, and using our modification of it. Both experiments were run on the same machine, using an NVIDIA RTX A6000 GPU. We also em- phasize that this comparison is somewhat favorable to the baseline parser, since we use the original
'https://gitie httpss///gggttu....o/iiitttttttt self-attentive--arser Phttps: /htggginggaac.eeeeee//oooo/a http://gggiggggceeeeeeeeeeeeeeee seseert-bae-cchiness
5

---

PTB
CTB
and 800 rules, respectively. The number of termi- nals and lexical rules is set 5000. Having more rules per nonterminal generally increases ambigu- ity, and so we would expect a synthetic grammar with 800 rules to be significantly more difficult to parse than one with 100, and synthetic grammar with 20 nonterminals to be more difficult than one with more.
Kitaev (2019)
89.83
81.72
Ours
90.07
80.98
Ours SL grad decode
89.91
81.76
Table 3: Performance of our approaches and baseline when trained from scratch and evaluated in terms of Fi on the PTB and CTB development sets (respectively). "SL." indicated that transformer layers are shared.
It is common to quantify ambiguity in terms of the conditional entropy of parse trees given sen- tences (Clark and Fijalkow, 2021), which can be estimated by sampling trees from the PCFG and averaging the negative log conditional probabilities of the trees given their sentences. The conditional entropy of a PCFG G is thus estimated as
code's batching, whereas our approach makes it ex- tremely easy to create big, padded batches, and thus speed up parsing further. Additionally, we made comparison with Supar's (Zhang et al., 2020b,a) implementation, which did include since was slower than Kitaev et al. (2019).
While the above experiments all fine-tune pre- trained BERT-style models for parsing, it is also worth examining the performance of these mod- els when trained from scratch. We accordingly train transformers from scratch using models of the size as those in Table 1 on the PTB and CTB training sets, and report results the development sets in Table We find again that non- Y based models are competitive. Furthermore, since we can now casily share transformer layers without sacrificing the advantage of pretrained layers, grad decoding has a more positive effect. We did not see a corresponding benefit to sharing transformer layers when predicting without grad decoding.
Ho(r|w) Σ log Po(x((), x(t)) pa(x(1))
pc(x)())<(n))
where the (zfn), -(n)) are sampled from G, and where (a( is calculated with the inside al- gorithm. We use N 1000 samples. Below report the Hc(r(ar) of each random grammar along with parsing performance; we will see that (T((T negatively correlates with performance. Our datasets consist of sentences sampled from these PCFGs and their corresponding parses, which were parsed with the CKY algorithm.
Dataset size Because ing the ability of transformers capture the CKY algorithm, we must ensure that the training set is sufficiently large that prediction errors can be at- tributed to the transformer failing to learn the algo- rithm, and not to sparsity in the training data. We ensure this by simply adding data until validation use 200K
interested in test-
5 Random PCFG Experiments
To generate random PCFGs, we follow the method used by Clark and Fijalkow (2021).* Their method involves first generating a synthetic context-free grammar (CFG) with a specified number of termi- nals, non-terminals, binary rules, and lexical rules. To assign probabilities to the rules, they then use an EM-based estimation procedure (Lari and Young, 1990; Carroll and Charniak, 1992) to update the production rules such that the length distribution of the estimated PCFG is similar to that of the PTB corpus (Marcus et al., 1993).
performance plateaus. In particular, sentences for training and 2K held-out sentences. To control the complexity of our datasets, also limit the maximum sentence length to 30, which decreases the average sentence length from 20-25 words per sentence to 18.
5.2 Models and baselines
5.1 Data
Whereas the experiments in the previous section mostly make use of standard BERT-like architec- tures, either fine-tuned or trained from scratch, in this section we additionally consider making parse predictions (as in Equations (1) and (2)) with trans- former variants which intended improve per- formance on "algorithmic" tasks. Indeed, recent
The approach of Clark and Fijalkow (2021) allows construct random grammars with desired number of nonterminals and rules, and we generate grammars having 20 nonterminals, 5 and 100, 400,
"See ht tttp:///ee thub. con/ com/alexct wwwaaae/xx//s/aeeeee httccc///ttttippctttcccc *We found performance patterns were the same when using more than 20 nonterminals, though results are slightly higher
since the grammars become less ambiguous.
6

---

[R]
100
400
800
Ha(r(a)
0.35
3.99
9.74
F1
Alp
F1
Alp
Fi
App
CKY Transformer
100.0
100.0
0
100.0
0
98.31
0.04
87.86
0.29
74.80
0.45
Transformer
98.61
89.89
0.19
79.91
0.29
Transformer CG
98.97
0.02
89.43
0.21
78.64
0.31
Transformer GD
99.06
0.01
91.07
0.17
81.78
0.28
Table 4: Labeled span Fi performance (as in evalb) on randomly generated PCFGs with [V] 20 nonterminals, and R 100, 400, and 800 rules, respectively. Ho(T [x) indicates estimated conditional entropy of the grammar. Dlp the average log probability difference between CKY and predicted parses. "SL" indicates that transformer layers are shared, "CG" that copy-gate used, and "GD" that grad decoding used.
research has shown that transformers often fail generalize algorithmic tasks (Saxton al.. 2019; Hupkes et al., 2020; Dubois et al., 2020; Chaabouni et al., 2021), which has motivated ar- chitectural modifications, such as the Universal Transformer (UT; Dehghani et al., 2018) and the Neural Data Router (NDR; Csordás et al., 2021).
sentences/second
batch size
32
64
128
CKY
698
1162
1576
Ours
1817
2132
2161
Table 5: Inference speed of GPU-based torch-struct CKY parsing and our transformer-base approach on a random grammar with [R 400 rules. We report the median speed of running model and CKY times 60K samples in batches 32, 64, and 128, respectively.
One major architectural modification common to both UT and NDR is that all transformer lay- ers share the same parameters; this modification is intended to capture the intuition that recursive computation often requires upplying the same func- tion multiple times. NDR additionally makes use of "copy gate," which allows transformer repre- sentations at layer / be simply copied over as the representation at layer | + without being further processed, as well as "geometric attention," which biases the self-attention to attend to nearby tokens. We found geometric attention to significantly hurt performance in preliminary experiments, and so we report results only with the shared-layer and copy-gate modifications.
Evaluation We evaluate our predicted parses against the CKY parse returned by torch-struct (Rush, 2020), using Fi over span-labels as in evalb. Since there may be multiple highest-scoring parses, we also report the average difference in log probability, averaged over each production, between the CKY parse returned by torch-struct and the predicted parse. We refer to this metric as "Aip" in tables. Because transformer-based parsers may predict invalid productions, we smooth the PCFG by adding 10-5 to each production probability and renormalizing before calculating Alp-
All models in this section are trained from scratch. This is convenient for UT- and -tylstyle architectures, for which we do not have large pre- trained models, but we also found in preliminary ex- periments that on random PCFGs pretrained vanilla transformers (such as BERT) did not improve over transformers trained from scratch. We did find a modest benefit to fine-tuning a BERT-style model that we pretrained on sentences from our randomly generated grammars (rather than natural lan- guage), which accords with the recent work of Zhao al. (2023); see Appendix E for details. Our im- plementation is based on the BERT implementation in the Hugging Face transformers library (Wolf et al., 2020).
The results of these synthetic parsing ex- periments are in Table 4, where show parsing performance
Results
three random grammars with dif- ferent conditional entropies. We see that transform- ers struggle as the ambiguity increases, suggest- ing that these models are not fact implementing CKY-like processing. At the same time, we see that incorporating inductive bias does help in nearly all cases, and that gradient decoding together with sharing transformer layers performs best for all grammars.
We conduct a speed evaluation in Table 5, where we compare with the CKY implementation torch-struct (Rush, 2020), which is optimized
7

---

for performance on GPUs. For fixed number of nonterminals, neither the speed of corch-structs CKY implementation nor of our transformer-baser approximation is significantly affected by the num- ber of rules. Accordingly, we show speed results for parsing just the synthetic grammar with 400 rules, for three different batch-sizes. All timing experiments are on the same machine and uti- lize an NVIDIA RTX A6000 GPU. We see that the transformer-basee approximation is always faster, although its advantage decreases as batch-size in- creases. We note, however, that because our im- plementation uses Hugging Face transformers components (Wolf et al., 2020), which at present do not make use of optimization such as FlashAt- tention (Dao et al., 2022), our approach could likely be sped up further.
dency parsing, It is worth emphasizing that while the Zhang et al. (2019) work shows that a scor- ing model with quadratic complexity can approx- imate the also quadratic Shu--Lu-Edmonne algo- rithm (Chu and Liu, 1965), used for decoding dependency parsing, our work focuses approx- imating a cubic complexity decoding algorithm using scoring model with quadratic complexity.
We are additionally motivated by recent work on neural algorithmic reasoning (Xu et al., 2019; Csordás et al.. 2021; Dudzik and Veličković, 2022;
Delétang et al.. 2022; Ibarz et al., 2022; Liu et al.. 2023), some of which has endeavored to solve clas- sical dynamic programs (Veličković et al., 2022) and MDPs (Chen al., 2021) with graph neural net- works and transformers, respectively. One respect in which learning to compute CKY differs from many other algorithmic reasoning challenges (in- cluding other dynamic programs) is that in addition to its discrete sentence input, CKY also consumes continuous log potentials.
6 Related Work
Modern neural constituency parsers typically fall into one of three camps: chart-based parsers (Stern et al., 2017; Gaddy et al., 2018; Kitaev and Klein, 2018; Mrini et al., 2020; Tian et al.. 2020; Tenney et al., 2019; Jawahar et al., 2019; Li et al. 2020; Murty et al., 2022), transition- based parsers (Zhang and Clark, 2009; Cross and Huang, 2016; Vaswani and Sagae, 2016; Vi- lares and Gómez- Rodriggzz 2018; Fernandez As- tudillo et al., 2020), or scquence-O-scqqeecee-tyy parsers (Vinyals et al., 2015; Kamigaito et al., 2017: Suzuki et al., 2018; Fernández-González and Kóómez-Rodrigue Yang and Tu, 2022).
Finally, the idea of training a model to produce the solution an optimization problem is known as training an "inference network," and has been used famously in approximate probabilistic infer- ence scenarios (Kingma and Welling, 2014) and in approximating gradient descent (Johnson et al.. 2016). Most similar to our approach, Tu and Gim- pel (2018) train an inference network to do Viterbi- style sequence labeling, although they do not con- sider parsing, and they require inference networks for both training and test-time prediction due their eaggemarggin approach.
2020; Nguyen et al., 2021;
Our approach most closely resembles chart- based methods, in that we compute scores for all spans for all non-terminals. However, unlike chart-based parsers, we aim to only approximate, or amortize, rumning the CKY algorithm. Un- like transition-based or sequence-to-sequeeee-syy methods, our approximation involves attempting predict parse jointly and independently, rather than incrementally. Within the world of bbart- neural parsers, those of Kitaev and Klein (2018) and Kitaev ct al. (2019) have been enormously in- fluential, and state-of-the-art constituency parsers, such as those of Mrini et al. (2020) and Tian et al. (2020), adapt this approach while improving it.
Discussion and Conclusion
Our findings on the ability of transformers to ap- proximate CKY are decidedly mixed. On the one hand, using transformers to independently predict spans in constituency parse is competitive with using very strong neural chart parsers, and it is moreover much faster to predict parses in this inde- pendent, non- Man--KY-ui CKY-based way. On the other hand, transformers are capturing the CKY computation, they ought to be able to parse even under random PCFGs, and is clear that as the ambiguity of the grammar increases they struggle with this.
We have also found that making a transformer's computation more closely resemble that of classi- cal algorithm, either by sharing computation layers as proposed by Dehghani et al. (2018) and Csor- dás et al. (2021), or by having make use of the
The approach of employing an independent-span classification training objective along with greedy decoding for inference has also been explored by Zhang et al. (2019) in the context of depen-
8

---

gradient with respect to scoring function, is help- ful. This finding both confirms previous results in this area, and also suggests that the inductive bias we seek to incorporate in our models may need to closely match the problem.
References
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hin- ton. 2016. Layer normalization. arXiv preprint arXiv:160700643
James K Baker. 1979. Trainable grammars for speech recognition. The Journal of the Acoustical Society of America, (5($1):8132-$13)
There are many avenues for future work, and attempting to find minimal general-purpose archi- tecture that can in fact parse under random PCFGs is an important challenge. In particular, it is worth exploring whether other forms of pretraining (i.e., pre-training distinct from BERT's) might benefit this task more. Another important future challenge to address is whether it is possible to have a model consume both the input sentence as well as the parameters (as the CKY algorithm does), rather than merely pretrain on parsed sentences generated using the parameters.
Glenn Carroll and Eugene Charniak. 1992. Two exper- iments on learning probabilistic dependency gram- mars from corpora. Department of Computer Sci- ence, Univ.
Rahma Chaabouni, Roberto Dessi, and Eugene Kharitonov. 2021. Can transformers jump around right in natural language? assessing performance transfer from SCAN. In Proceedings of the Fourth BlackboxNLP Workshop on Analyzing and Interpret- ing Neural Networks for NLP, pages 136-148, Punta Cana, Dominican Republic. Association for Compu- tational Linguistics.
Limitations
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. 2021. Decision trans- former: Reinforcement learning via sequence mod- eling. Advances in neural information processing systems, 34: 14:15084-15097.
A limitation of the general paradigm of learning to compute algorithmically that it requires a training phase, which can be expensive computationally, and which requires annotated data. This is less of a limitation in the case of constituency parsing, however, since we are likely to be training models in any case.
Y. J. Chu and T. H. Liu, 1965. On the shortest arbores- cence of a directed graph. Science Sinica, 14.
Another important limitation of our work is that we have only provided evidence that transformers are unable to implement CKY in our particular ex- perimental setting. While we have endeavored to find the best-performing combinations of models and losses (and while this combination appears to perform well for constituency parsing), it is pos- sible that other transformer-basee architectures or other losses could significantly improve in terms of parsing random grammars.
Alexander Clark and Nathanaël Fijalkow. 2021. Con- sistent unsupervised estimators for anchored PCFGs. In Proceedings of the Society for Computation Lin- guistics 2021, pages 471-473, Online. Association for Computational Linguistics.
Caio Corro. 2020. Span-based discontinuous con- stituency parsing: family of exact chart-hased algo- rithms with time complexities from O(n '6) down to O(n"3). In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 2753-2764, Online. Association for Computational Linguistics.
We also note that a limitation of the grad decod- ing approach we propose is that we have found that it is more sensitive to optimization hyperparame- ters than are the baseline approaches.
James Cross and Liang Huang. 2016. Span-based con- stituency parsing with a structure- system and provably optimal dynamic oracles. In Proceedings of the 2016 Conference on Empirical Methods in Natu- ral Language Processing, pages 1-11, Austin, Texas. Association for Computational Linguistics.
Finally, we note that our best- persforeroon con- stituency results make use of large pretrained mod- cls. These models are expensive to train, and do not necessarily exist for all languages we would like to parse.
Róbert Csordás, Kazuki Trie, and Jürgen Schmidhuber. 2021. The neural data router: Adaptive control flow in transformers improves systematic generalization. In International Conference on Learning Representa- tions.
Ethics Statement
We do not believe there are significant ethical is- sues associated with this research, apart from those that relate to training moderately-sizze machine learning models on GPUs.
Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. 2022. FlashAttention: Fast and memory-efficient exact attention with IO-awareness. In Advances in Neural Information Processing Sys- lems.
9

---

Mostafa Dehghani, Stephan Gouws, Oriol Vinyals. Jakob Uszkoreit, and Lukasz Kaiser. 2018. Universal transformers. In International Conference Learn ing Representations.
the North American Chapter of the Association for Computational Linguisties: Human Language Tech- nologies. Volume 1 (Long Papers), pages 999-1010, New Orleans, Louisiana. Association for Computa- tional Linguistics.
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Mar- Hutter, Shane Legg, and Pedro A Ortega. 2022. Neural networks and the chomsky hierarchy. arXiv preprint ar0i::2207. 02099.
Jonas Geiping and Tom Goldstein. 2022. Cramming: Training a language model on a single gpu in one day.
Alex Graves, Greg Wayne, and Ivo Danihelka. 2014. Neural turing machines. arXiv preprint 111iv:1410.5401.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and
Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language under- standing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, Volume I (Long and Short Papers), pages 4171 1171-4186, Minneapolis, Minnesota. Association for Computational Linguistics.
Dan Hendrycks and Kevin Gimpel. 2016. Gaus- sian error linear units (gelus). arXiv preprint 1606
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 Linguisticx: Human Language Tech- nologies, Volume (Long and Short Papers), pages 4129-4138, 4138, Minneapolis, Minnesota. Association for Computational Linguistics.
Yann Dubois, Gautier Dagan, Dieuwke Hupkes, and Elia Brumi. 2020. Location Attention for Extrapola- tion to Longer Sequences. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages (03-413, Online. Association for Computational Linguistics.
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. 2020. Compositionality decomposed: How do neural networks generalise? (extended abstract). In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI-20 pages 5065-5066. International Joint Conferences on Artificial Intelligence Organization. Journal track.
Andrew Dudzik and Petar Veličković. 2022. Graph neural networks are dynamic programmers. In ICLR 2022 Workshop on Geometrical and Topological Rep- resentation Learning.
Tiwalayo Eisape, Vineet Gangireddy, Roger Levy, and Yoon Kim. 2022. Probing for incremental parse states in autoregressive language models. In Find- ings the Association for Computational Linguistics: EMNLP 2022, pages 2801-2813, Abu Dhabi, United Arab Emirates. Association for Computational Lin- guistics.
Borja Ibarz. Vitaly Kurin, George Papamakarios, Kyr- iacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Dudzik, Matko Bošnjak, Alex Vitvitskyi, Yulia Rubanova, et al. 2022. A generalist neural al- gorithmic learner. arXiv preprini arXiv: 142.
Ganesh Jawahar, Benoît Sagot, and Djamé Seddah. 2019. What does BERT learn about the structure of language? In Proceedings of the 57th Annual Meet- ing of the Association for Computational Linguistics. pages 3651-3657 Florence, Italy. Association for Computational Linguistics.
Jason Eisner. 2016. Inside-outside and forward- backward algorithms are just backprop (tutorial pa- per). In Proceedings of the Workshop Structured Prediction for NLP. pages 1-17, Austin, TX. Associ- ation for Computational Linguistics.
Justin Johnson, Alexandre Alahi, and Li Fei-Fei. 2016. Perceptual losses for real-time style transfer and super-resolution. European conference on com- puter vision, pages 694-711. Springer.
Ramón Fernandez Astudillo, Miguel Ballesteros, Tahira Naseem, Austin Blodgett, and Radu Florian. 2020. Transition based parsing with stack-transfor transforrro..... In Findings of the Association for Computational Lin- guistics: EMNLP 2020, pages 1001-1007, Online. Association for Computational Linguistics.
Lukasz Kaiser and Ilya Sutskever. 2016. Neural gpus learn algorithms. In 4th International Conference Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Pro- ceedings.
Daniel Gernandez-Gozálle and Carlos Gómez- Rodríguez. 2020. Enriched in-order linearization for faster sequence-to-sequence constituent parsing. In Proceedings of the 58th Annual Meeting of the As- sociation for Computational Linguistics, pages 4092- 4099, Online. Association for Computational Lin- guistics.
Hidetaka Kamigaito, Katsuhiko Hayashi, Tsutomu Hirao, Hiroya Takamura, Manabu Okumura, and Masaaki Nagata. 2017. Supervised attention for sequence-to- eqquence-to-sqquence constituency parsing. In Pro- ceedings of the Fighth International Joint Conference Natural Language Processing (Volume 2: Short Papers), pages 7-12, Taipei. Taiwan. Asian Federa- tion of Natural Language Processing.
David Gaddy, Mitchell Stem, and Dan Klein. 2018. What's going on neural constituency parsers? an analysis. In Proceedings of the 2018 Conference of
10

---

Tadao Kasami. 1966. An efficient recognition and syntax- anallss algorithm for context-free languages. Coordinated Science Laboratory Report no. R-257.
Association for Computational Linguistics: Human Longuage Technologies. pages 124-131, Online. As- sociation for Computational Linguisties.
Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In 3rd Inter- national Conference on Learning Reprexentations, ICIR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings.
Khalil Mrini, Franck Demoncourt, Quan Hung Tran, Trung Bui, Walter Chang, and Ndapa Nakashole. 2020. Rethinking pretability in neural parsing. In Findings of the As- sociation for Computational Linguistics: EMNLP 2020, pages 731-742, Online. Association for Com- putational Linguistics.
aelfaattentoon Towards inter-
Diederik P. Kingma and Max Welling. 2014. Auto- Encoding Variational Bayes. In Proceedings of ICLR.
Shikhar Murty, Pratyusha Sharma, Jacob Andreas, and Christopher D Manning. 2022. Characterizing intrin- sic compositionality in transformers with tree projec- tions. arXiv preprint arXiv:2211.012.
Nikita Kitaev, Steven Cao, and Dan Klein. 2019. Multi-
lingual constituency parsing with self- attention and pre-training. In Proceedings of the 57th Annual Meet- ing of the Association for Computational Linguistics, pages 3499-3505, Florence, Italy, Association for Computational Linguistics.
Thanh-Tung Nguyen, Xuan-Phi Nguyen, Shafiq Joty, and Xiaoli Li. 2021. A conditional splitting frame- work for efficient constituency parsing. In Proceed- ings of 59th Annual Meeting of the Association for Computational Linguistics and the 1 1thh International Joint Conference on Natural Language Processing (Volume I: Long Papers). pages 5795-5807, Online. Association for Computational Linguistics.
Nikita Kitaev and Dan Klein. 2018. Constituency pars ing with a self-attentive encoder. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 2676-2688 Melbourne, Australia. Association for Computational Linguistics.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32.
K. Lari and S. Young. 1990. The estimation of stochastic context-free grammars using the inside- outside algorithm. Computer Speech and Language, 4:35-56.
Bowen Li, Taeuk Kim, Reinald Kim Amplayo, and Frank Keller. 2020. Heads-up! unsupervised con- stituency parsing via self-attention heads. In Pro- ceedings of the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Lin- guistics and the 10th International Joint Conference on Natural Language Processing, pages 409 424, Suzhou, China. Association for Computational Lin- guistics.
A Alexander Rush. 2020. Torch-struct: Deep structured prediction library. In Proceedings of the 58th An- nual Meeting of the Association for Computational Linguistics: System Demonstrations, pages 335-342, Online. Association for Computational Linguistics.
David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. 2019. Analysing mathemati- cal reasoning abilities of neural models. ArXiv, abs/1904.01557.
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Kr- ishnamurthy, and Cyril Zhang. 2023. Transformers learn shortcuts to automata.
Djamé Seddah, Reut Tsarfaty. Sandra Kübler, Marie Candito, Jinho D. Choi, Richárd Farkas, Jennifer Fos- ter. Iakes Goenaga, Koldo Gojenola Galletebeitia. Yoav Goldberg, Spence Green, Nizar Habash, Marco Kuhlmann, Wolfgang Maier, Joakim Nivre, Adam Przepiórkowski. Ryan Roth, Wolfgang Sceker, Yan- nick Versley, Veronika Vineze, Marcin Wolinski, Alina Wróblewska, and Fric Villemonte de la Clerg- erie. 2013. Overview of the SPMRL 2013 shared task: A framework evaluation of parsing morphologically rich languages. In Proceedings of the Fourth Workshop on Statistical Parsing of Morphologically- -ich Languages. pages 146-182, Seattle, Washington, USA. Association for Computa- tional Linguistics.
Tlya Loshchilov and Frank Hutter. 2018 Decoupled weight decay regularization. In International Confer- ence on Learning Representations.
Christopher D. Manning. Kevin Clark, John Hewitt, Urvashi Khandelwal, and Omer Levy. 2020. Emer- gent linguistic structure in artificial neural networks uraindd by superviuerv Proceedings of the Na- tional Academy of Sciences, 117:30046 30054.
Mitchell P. Marcus, Mary Ann Mareinkiewicz, and Beat- rice Santorini. 1993. Building large annotated cor- pus of english: The penn treebank. Comput. Lin- guist., 1933333
Mitchell Stern, Jacob Andreas, and Dan Klein. 2017. A minimal span-based neural constituency parser. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume
Rowan Hall Maudslay and Ryan Cotterell. 2021. Do syntactic probes probe syntax? experiments with jabberwocky probing. In Proceedings of the 2021 Conference of the North American Chapter of the
I: Long Papers). pages 118-827, Vancouver, Canada. Association for Computational Linguistics.

---

Jun Suzuki, Sho Takase, Hidetaka Kamigaito, Makoto Morishita, and Masaaki Nagata. 2018. An empirical study of building strong baseline for constituency parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Vol- ume 2: Short Pupers), pages 612-618, Melbourne, Australia. Association for Computational Linguisties.
Demonstrations, pages 28-45, Online, Association for Computational Linguistics.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2019. What can neural networks reason about? In Interna- tional Conference on Learning Representations.
lan Tenney, Dipanjan Das, and Ellie Pavlick. 2019. BERT rediscovers the classical NLP pipeline. In Proceedings of the 57th Annual Meeting of the Asso- ciation for Computational Linguistics. pages 4593- 4601, Florence, Italy, Association for Computational Linguistics.
Naiwen Xue, Fei Xia, Fu-dong Chiou, and Marta Palmer. 2005. The penn chinese treebank: Phrase struc- ture annotation of large corpus. Nat. Lang. Eng.. 11(2):207-238.
Songlin Yang and Kewei Tu. 2022. Bottom-up con- stituency parsing and nested named entity recogni- tion with pointer networks. In Proceedings of the 60th Annual Meeting of the Association for Compu- tational Linguistics (Volume I: Long Papers), pages 2403-244 2416, Dublin, Ireland. Association for Compu- tational Linguistics.
Yuanhe Tian, Yan Song, Fei Xia, and Tong Zhang. 2020. Improving constituency parsing with span attention. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 1691-1703, Online. Association for Computational Linguistics.
Songlin Yang and Kewei Tu. 2023. Don't 't parse, choose spans! continuous and discontinuous constituency parsing via autoregressive span selection. In Proceed- ings of the 6t Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 8420-8433, Toronto, Canada. Association for Computational Linguistics.
Lifu Tu and Kevin Gimpel, 2018. Learning approxi- mate inference networks for structured prediction. In ICLR.
Ashish Vaswani and Kenji Sagae. 2016. Efficient struc- tured inference for transition-based parsing with neu- ral networks and error states. Transactions of the Association for Computational Linguistics, 4:183- 196.
Daniel H Younger. 1967. Recognition and parsing of context-free languages in time n². Information and control, 10(2):199-20
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in neural information processing systems, 30.
Biao Zhang, Ivan Titov, and Rico Sennrich. 2020a. Fast interleaved bidirectional sequence generation. In Pro- ceedings of the Fifth Conference on Machine Trans- lation, pages 503-515, Online, Association for Com- putational Linguistics.
Petar Veličković, Adrià Puigdomenech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Da- shevskiy, Raia Hadsell, and Charles Blundell. 2022. The cirs algorithmic reasoning benchmark. arXiv preprint arxiv:2205.1550 15659.
Yu Zhang, Zhenghua Li, and Min Zhang, 2020b. Effi- cient second-order TreeCRF for neural dependency parsing. In Proceedings of the 58th Annual Meet- ing of the Association for Computational Linguistics, pages 3295-3305, Online, Association for Computa- tional Linguistics.
David Vilares and Carlos
2018. Transition-hased parsing with lighter feed-forward networks. In Proceedings of the Second Workshop on Universal Dependencies (UDW 2018), pages 162- 172, Brussels, Belgium. Association for Computa- tional Linguisties.
Yue Zhang and Stephen Clark. 2009. Transition- based parsing of the Chinese treebank using global dis- criminative model. In Proceedings of the 11th International Conference on Parsing Technologies (IWPT'09), pages 162-171, Paris, France. Associa- tion for Computational Linguistics.
Oriol Vinyals, Eukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015, Grammar foreign language. Advances in neural informa- tion processing systems, 28.
Zhisong Zhang, Xuezhe Ma, and Eduard Hovy. 2019. An empirical investigation of structured output mod- eling for graph-based neural dependency parsing. In Proceedings of the 57th Annual Meeting of the Asso- ciation for Computational Linguistics, pages 5592- 5598, Florence, Italy. Association for Computational Linguistics.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pier- ric Cistac, Tim Rault, Remi Louf, Morgan Funtow- icz, Joe Davison, Sam Shleifer. Patrick von Platen, Clara Ma. Yacine Jernite. Julien Plu, Canwen Xu, Teven Le Seao. Sylvain Gugger, Mariama Drame. Quentin Lhoest, and Alexander Rush. 2020. Trans- formers: State-of-the thr natural language processing. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System
Haoyu Zhao, Abhishek Panigrahi, Rong Ge, and San- jeev Arora. 2023. Do transformers parse while pre- dicting the masked word?
12

---

A Additional background on CKY
their licenses (Apache 2.0). For our deep learning framework, we use Py PyTorch (Paszke et al., 2019) which is under the BSD-3 license. We also make use of code provided by Kitaev et al. (2019) Their code is available under the MIT license.
Letting ( E [ represent the log po- tentials (c.g., log probabilitics) associated with the rules in PCFG G, and (xx) с RTX|||] the log potentials corresponding to each token in input sen- tence we compute the chart / R X| for 2, where B[i. a] represents the sum (under a par- ticular semiring) of all weight associated with the o-th non-terminal yielding Zi:j. In particular, with semiring operations @ and &, and if S < <
Computational Budget All of our experiments were run on NVIDIA RTX A6000 GPUs. We pro- vide the computational time of our experiments on constituency parsing datasets and a random PCFG, Since the training times of random PCFGs with |R| 100, 100, and 800 rules are similar, we only provide that of the PCFG with [R] 400.
T, we have J. a] = Ds.6,c gR "ob, & Bii, k, b] & A[k + 1, c]. Assuming the first slice of & along the first dimension (i.e., ( corresponds to rules with S on the left-hand-side, the log partition func-
Models Details In Table 7 and 8, we provide the number of model parameters used in constituency parsing and random PCFG experiments, respec- tively.
tion is then given by A {B) = TI
Furthermore, under the max-plus semiring, one of the subgradients of A(eR, ,B8) with respect to 9 is a one-hot representation of a highest scoring parse for a under G (Eisner, 2016; Rush, 2020). We refer to such a one-hot subgradient 3* E
Model
Size
PTB CTB SPMRI.
BEKT-large-uncee
345M
{0, 1)7XX NV1, Rush (2020) therefore proposes to compute 3 using automatic differentiation, and
BERTT-bas--hinnse
102M
BeBRT-bas--muliiiingua--ee
178M
provides fast implementation tuned for use on GPUs.
Table 7: Model sizes for constituency parsing exper- iments. All models are initialized from the Hugging Face transformers library (Wolf al., 2020).
B Model, Training, and Dataset Details
Dataset Details dard constituency parsing datasets used in our ex- periments in Table 6.
We provide details on the stan-
Model
Size
Transformer Transforer + SL
89.6M
11.1M
Transformer + SL +
11.9M
train
dev
test
Transformer + SL + GD
11.7M
PTB
39,831
1,700
2,416
CTB
17.544
352
348
Table 8: Model sizes for random PCFG experiments.
German
40,472
5,000
5,000
Korean 23,010
2,066
2,287
Table 6: Number of examples in the standard splits of the English Penn Treebank (Marcus et al., 1993), the Chinese Penn Treebank (Xue al., 2005), and the SPMRL Treebanks (Seddah et al., 2013).
PTB
CTB
German
Korean
Ours
I
0.5
4.5
1.5
Ours + grad decode
8
4.5
8.5
2.5
Table 9: Approximate total training time (in number of hours) of our model with and without grad decoding on the parsing datasets. find that grad decoding models take longer to converge.
Terms of Use We used the standard English Penn Treebank, Chinese Penn Treebank, and treebanks (except for Arabic) from SPMRL 2013 and 2014 shared tasks in accordance with their licenses. Both PTB and CTB are under the Linguistic Data Con- sortium (LDC) licenses. The German, Hebrew, Korean, and Swedish Treebank are not under any specific licenses. The Basque Treebank is licensed under the Creative Commons license. The Polish Treebank is licensed under GPL v3. We also use Hugging Face code and models in accordance with
C Gradient Decoding Details
Speed Comparison In Table 11 we compare the inference time between our models (with and with- out gradient decoding) and CKY.
htt //gi thub. com/nikite takit/
13

---

R 400
pretrained on synthetic PCFG data may be approx- imating the insidc-outside algorithm. Since inside- outside and CKY are related, natural to ques- tion whether MLM pretraining can also be helpful when comes to approximating CKY.
Transformer
11
Transformer SL
7
Transformer SLL CG
Transformer SI. GD
Table 10: Approximate total training time (in number of hours) of model random PCFG, "SL" indicates that transformer layers are shared, "CG" that copy- gate is used, and "GD" that grad decoding is used.
We therefore pretrain a transformer model on 500K sentences generated from the random PCFG with 800 rules. We selected our training setup fol- lowing the Cramming training recipe (Geiping and Goldstein, 2022). For training, we utilized large batch size of 4096, accumulating gradients and per- forming an update every 32 steps. We employed a linear warmup schedule for 10% of the total train- ing steps, with peak learning rate of x 10-4, The model achieved a training perplexity of 92.01 and a validation perplexity of 92.20.
sentencces/sccond
hatch size
32
64
128
CKY
698
1162
1576
Ours
1817
2132
2161
Ours + GD
1111
1524
1632
Table 11: Inference speed of GPU-based torch-struct CKY parsing and our transformer-hased approach on random grammar with [R] 400 rules. We report the median speed of running our models and CKY 5 times on 60K samples in batches of 32, 64, and 128, respectively.
In Table 13, show that fine-tuning the pre- trained model leads performance improvements. particularly when layers are not shared. It is impor- tant to highlight that while pretraining is helpful, it comes with higher computational costs compared to relying solely on inductive biases, and it demon- strates less improvement compared to gradient de- coding.
Memory Comparison The maximum memory allocation of our model with gradient decoding is 1.52 GB, which is only 10% higher compared to our model without gradient decoding, which has maximum memory allocation of 1.38 GB.
F Hyperparameters
Table 14 shows the grid we used to search for the optimal hyperparameters of the models used in con- stituency parsing and random PCFG experiments. We also provide the optimal hyperparameters in Table 15 and 16. For the baseline result (Kitaev and Klein, 2018) in Table I, we used the hyperpa- rameters recommended in their code. The results in Table 1 and 4 make use of the optimal hyperpa- rameters and are based on single run using a fixed seed throughout all experiments.
D Constituency Parsing Results SPMRL
Table 12 shows that our approach outperforms Ki- taev et al. (2019) on half of the SPMRL treebanks. We excluded the Arabic treebank since we were unable to get its corresponding license.
Considering that gradient decoding did not lead substantial improvements in the results for PTB,
CTB, German, and Korean, as indicated in Table 1, we decided not to perform the gradient decoding experiments on the rest of the SPMRL treebanks due to limitations in computational resources.
E MLM Pretraining on Random PCFG-Generated Data
Several works have suggested that pretrained mod- cls can capture syntactic information (Hewitt and Manning. 2019; Manning al., 2020; Maudslay and Cotterell, 2021; Zhao et al., 2023). In partic- ular, Zhao et al. (2023) argued that a connection exists between MLM and the inside-outside algo- rithm. Through probing, they show that models
14

---

German
Korean
Basque
French
Hebrew
Hungarian
Polish
Swedish
Kitaev (2019)
90.20
88.80 89.05
90.70
87.35
92.95
94.60
96.26 95.86
89.94
Ours
90.13
90.93
87.59
92.69
94.64
89.29
Table 12:
Comparison of F1 score on the test sets SPMRL treebanks. The Kitaev al. (2019) results are those reported in the paper.
Ours
scheduler
LR
grad clip
AD
English
linear
5e-5
0.3
0.1
Chinese
default
6e-5
0.4
0.1
German
default
Se-5
0.3
0.1
Korean
default
5e-5
0
0.1
R| = 800
Basque
default
5c-5
0.3
0.1
Transformer Transformer SL
78.14
French
default
6e-5
0
0.1
78.88
Hehrew
default
5c-5
0.5
0.1
Transformer St. GD
80.64
Hungarian
default
5e-5
0.3
Polish
default
5c-5
0.3
0.1
Swedish
default
6e-5
0.3
0.1
Table 13: Fi performance of pretrained models on ran- domly generated PCFGs with [.] = 20 nonterminals, and [R] 800 rules.
Ours grad decode
English
default
7e-5
0.2
0
0.1
Chinese
default
8e-5
0.3
0.1
German
default
8e-5
0.3
0
0.1
Korean
default
7e-5
0.2
0.1
Kitaev et al. (2019)
All
default
5c-5
0.001
0.2
Table 15: Optimal hyperparameters used for our con- stituency parsing experiments. We denote the learn- ing rate "LR", weight decay "WD", and atten- tion dropout as "AD", Similar hyperparameters are used in the baseline model (Kitaev al., 2019) across the datasets. Results are provided in Table 1.
Constituency parsing Experiments
Hyperparameter
Values
Transformer
Scheduler
[default linear"1
LR
grad clip
WD
AD
WS
Learning
[5c-5, 6e-5, 7e-5, 86-51 0.2, 0.3, 0.4] [0. 1e-3, 1e-2) [0.1, 0.2)
R
100
lc-3
0.3
4000
Gradient clipping
R
400
le-4
le-3
0.3
Weight decay
R 800
lc-3
0.3
4000
Attention dropout
Transformer SL
Random PCFG Experiments
R 100
le-4
1e-3
0.3
4000
Scheduler
constant + warmup
400
1.3e-4
le:3
0.3
4000
Learning rate
[1c-4, 1.3c-4, 1.5e-4, 1.7e-4]
R 800
1.3e-4
le-3
0.3
4000
Gradient clipping
[0.3, 0.4, 1] [0. le-3, Ic-2]
Weight decay
Transformer + SL + CG
Attention dropout
1, 0.2]
R 100
1.3e-4
le-3
0.3
4000
Warmup steps
12000, 4000]
R 400
le-4
le-3
0.3
4000
IR] 800
lc-4
1c-3
0.3
4000
Table 14: The grid used search for optimal hy- perparameters in our constituency parsing and random PCFG experiments. "The default scheduler used in Ki- et al. (2019) mentioned in section 4. b 160 steps of warm-up then decreasing the learning rate linearly.
Transformer
GD
R 100
lc-4
0.4
le-3
0.3
4000
R 400
1.3e-4
0.4
le-3
0.3
4000
800
lc-4
0.4
le-3
0.3
4000
Table 16: Optimal hyperparameters used for our random PCFG experiments. We denote the learning rate "LR", weight decay as "WD", attention dropout as "AD". and the number warmup steps as "WS". Results are provided in Table 4.
15


Reviews:
[{"review_id": "o9F1G6uQJW", "reviewer": "Reviewer_Fb95", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "We thank Reviewer Fb95 for the thoughtful comments and suggestions.\n\nAs suggested by Reviewer Fb95, below we provide our results on all the other SPMRL datasets except for Arabic which we currently do not have access to; we will try to include it in our next revision.\nPlease note that we did not do extensive hyperparameter tuning and therefore our results on these languages will most likely improve in our next revision. Furthermore, the results of Kitaev et al. are those reported in the paper which makes use of an additional factored self-attention layer. Finally, we use the training setting suggested by Kitaev et al. for our experiments which makes this comparison favorable to their parser. Despite all this, our approach still outperforms or comes very close to the Kitaev et al. results while being significantly faster.\n|               | Basque | French | Hebrew | Hungarian | Polish | Swedish |\n| ------------- | ------ | ------ | ------ | --------- | ------ | ------- |\n| Kitaev et al. | 90.70  | 87.35  | **92.95**  | 94.60     | **96.26**  | **89.94**   |\n| Ours          | **90.93**  | **87.59**  | 92.69  | **94.64**     | 95.86  | 89.29   |\n\n**Response to the reproducibility score:**\nWe emphasize that we have provided all the hyperparameters and details on the model architectures in Appendix E and Section 4-Model Details. Furthermore, The code will be open-sourced upon publication and will include instructions for reproducing all the experiments.\nRegarding the dataset generation or any other point of confusion, we would be happy to clarify any questions or concerns that Reviewer Fb95 might have in our next revision.", "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 studies an interesting question of whether transformers approximate CKY algorithm. The experiments are thorough with detailed analysis of the results. Rather than just experimenting with English treebank, the authors experiment with four diverse treebanks which shows that the approach works for diverse languages. Similarly in addition to constituency treebanks, experiments were conducted on synthetic PCFGs which add more value to the work.", "reasons_to_reject": "It is great to see the results on four languages. But it would be even better to have results on all the language treebanks in SPMRL 2013.", "questions_to_authors": "", "paper_topic_and_main_contributions": "This paper investigates whether transformers can learn CKY algorithm. The authors first presented how transformer based constituency parsers work and how that information is used in CKY algorithm. Then the changes to training and inference are presented which predicts the gradient to decode the parse. Four constituent treebanks (English, Chinese, German and Korean) are considered to evaluate the hypothesis and show that their approach give competitive accuracies with double the speed of state-of-the-art parsers. Then they experiment with synthetic PCFGs and show that transformers are indeed not learning CKY internally since it fails to work for synthetic PCFGs. ", "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": {}}, {"review_id": "mf5Qqqo4DR", "reviewer": "Reviewer_LCCU", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "We thank Reviewer LCCU for the thoughtful comments.\n\n> The model is essentially a CKY parser (with subgradient constraints, Eisner, 2016) with the core being a pretrained BERT, and UT and NDR (without pretrained models) for the synthetic experiments\n\n**Response to reason to reject #1:**\nWe respectfully disagree with Reviewer LCCU’s view that the model is essentially a CKY parser. Indeed, unlike the vast majority of previous work on constituency parsing, our parser never runs the CKY algorithm. As we emphasize, this has ramifications both for runtime (quadratic rather than cubic) and for understanding to what extent transformers approximate classical algorithms. Further, the idea of decoding predictions from gradients with respect to a chart representation is entirely novel, as far as we are aware.\n\n> All main ideas have been proposed before and used in similar ways, and the main contributions represent slight variations of them only\n\n**Response to reason to reject #2:**\nWe emphasize that the experiments in the paper are not (only) designed to present a new architecture or loss, but to test the hypothesis that transformers are approximating the CKY algorithm. We believe our empirical findings are novel and that they bear on this important question, whether or not certain architectures or losses have also been used before in other contexts. \n\n\n\n> The performance on random PCFGs mainly comes from UR and NDR transformers (Table 4)\n\n**Response to reason to reject #3:**\nWe respectfully disagree with Reviewer LCCU’s view that the performance on random PCFGs comes mainly from UT and NDR. First note that \"Transformer + SL + GD\" does not use \"CG\", which is the contribution of NDR, and that this variant improves over \"Transformer + SL\" by **~0.45**, **~1.18**, and **~1.87** points of F1-score, respectively, on the three synthetic grammars. We further observe that performance gap *increases* as the grammar gets harder, and as performance in general decreases.\n\n**Response to the reproducibility score:**\nWe emphasize that we have provided all the hyperparameters and details on the model architectures in Appendix E and Section 4-Model Details. Furthermore, The code will be open-sourced upon publication and will include instructions for reproducing all the experiments. \nRegarding the dataset generation or any other point of confusion, we would be happy to clarify any questions or concerns that Reviewer LCCU might have in our next revision.", "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 papers presents a model with positive results \n* Positive synthetic experiments on random PCFGs", "reasons_to_reject": "* The model is essentially a CKY parser (with subgradient constraints, Eisner, 2016) with the core being a pretrained BERT, and UT and NDR (without pretrained models) for the synthetic experiments\n* All main ideas have been proposed before and used in similar ways, and the main contributions represent slight variations of them only\n* The performance on random PCFGs mainly comes from UR and NDR transformers (Table 4)", "questions_to_authors": "", "paper_topic_and_main_contributions": "The main results of this paper use a pretrained BERT model to do supervised constituent parsing by predicting the highest-scoring constituent and ignoring non-constituents. The core chart parsing model is based on that of Kitaev and Klein (2018), however, instead of using a max-margin loss, a corss-entropy loss scoring possible constituents over spans is used. Using this approach, competitive parsing performance is shown on four languages (en, de, zh, and ko). The paper further extends the baseline model to predict random PCFG generated parses, demonstrating that by using additional structural chart constraints in the form of subgradients (Eisner, 2016) this further improves over the BERT-based baseline. The main contribution of this paper is a variation of the loss used in Kitaev and Klein (2018).", "excitement": 3, "reproducibility": 4, "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": {}}, {"review_id": "xn8vR6DMms", "reviewer": "Reviewer_e4gq", "summary": "", "questions": "- \"Physics of Language Models: Part 1, Context-Free Grammar\" (https://arxiv.org/pdf/2305.13673.pdf) demonstrates that Transformers can perfectly learn Context-Free Grammar (CFG). Does this finding contradict your results?  If not, could you kindly provide a brief explanation? \n\n- I am curious to know if \"Transformers Learn Shortcuts to Automata\" is related to the Transformers' ability to learn dynamic programs.", "limitations": "", "rating": 3, "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": "We thank Reviewer e4gq for the thoughtful comments, questions, and suggestions.\n\n>The distribution of constituency parse trees for a given sentence is highly peaked, which makes it a less suitable task to study whether Transformers can implement CKY, as acknowledged by the author in lines 81-86. The primary contribution of the first experiment in constituency parsing lies in the use of local loss and greedy decoding to improve parsing efficiency. However, it is worth noting that the parsing literature has already demonstrated that with a powerful neural encoder, parsers can achieve good performance using local classification loss and greedy decoding, as illustrated in Figure 1 of https://aclanthology.org/P19-1562.pdf and Table 5 of https://aclanthology.org/2023.acl-long.469.pdf. As a result, the significance of this particular contribution in the present work is somewhat diminished.\n\n**Response to reason to reject #1:**\nRegarding previous demonstrations of the viability of local classification and greedy decoding: we note that our work differs from the Zhang et al. (2019) work in that we consider constituency parsing rather than dependency parsing and in that we use a transformer-based architecture rather than an LSTM-based one. As the focus of our work is precisely on the extent to which transformers approximate CKY (an algorithm not used in dependency parsing), we feel our experiments are necessary and substantially different from those of Zhang et al.\n\nRegarding the work of Yang & Tu (2023), we assume Reviewer e4gq is referring to the “greedy” ablation in Table 5, as most of the Yang & Tu paper deals with an autoregressive encoder-decoder model, unlike ours. Yang & Tu mention that this ablation is based on Teng & Zhang (2018), which Reviewer e4gq also highlights as a missing reference. We agree this is a missing reference, and appreciate Reviewer e4gq mentioning it. However, it differs from our approach in that it is a two-step parser, which first predicts an unlabeled tree (by classifying spans as constituents or not), and then predicts labels for each span using a tree-LSTM. In contrast we use a simpler single-step approach and a transformer. We also note that our approach to appears to very slightly outperform the results in Yang & Tu’s table 5, and that we include results on more languages (see response to Reviewer Fb95 for additional languages). Finally, we note that the Yang & Tu work is considered contemporaneous to ours under EMNLP’s policy (https://2023.emnlp.org/calls/main_conference_papers/), and indeed this paper was not yet published at the time we submitted. \n\n> My complaint about this paper is that I believe the experiments in the constituency parsing section are entirely unnecessary. Emphasizing the speed advantage does not seem appropriate as the main or even partial motivation for this article. It would be more suitable to focus on fundamental questions like whether Transformers can learn dynamic programming algorithms like CKY. However, the study of this aspect in the paper appears to be relatively superficial and not very thorough, as it does not provide me with significantly novel insights.\n\n**Response to reason to reject #2:**\nRegarding the necessity of the constituency parsing experiments, we believe that without these experiments many readers would wonder to what extent our results carried over to the practical constituency parsing case, and we have tried to fill out the paper by answering this question for a fairly extensive number of natural languages.\n\nRegarding superficiality and lack of thoroughness, we would be very happy to hear suggestions for further experiments from Reviewer e4gq, and we will endeavor to add them in the next revision.\n\n\n**Response to questions:**\n\n> \"Physics of Language Models: Part 1, Context-Free Grammar\" (https://arxiv.org/pdf/2305.13673.pdf) demonstrates that Transformers can perfectly learn Context-Free Grammar (CFG). Does this finding contradict your results? If not, could you kindly provide a brief explanation?\n\nThe “Physics of Language Models” paper does not contradict our results because it considers a different setting and task. That paper considers decoder-only transformers trained as language models, and it evaluates them on the task of generating continuations of prefixes such that the resulting string belongs to a particular CFG. In contrast, we consider encoder-only transformers trained with a different loss on *weighted* CFGs (namely, on PCFGs), where the task is to parse, i.e., to predict the highest-scoring tree under the relevant PCFG. This task is not considered by the Physics of LM paper and so their results do not extend to our setting.\n\n> I am curious to know if \"Transformers Learn Shortcuts to Automata\" is related to the Transformers' ability to learn dynamic programs.\n\nYes, we agree that there is an intuitive connection between the Shortcuts to Automata paper and the ability (or not) of transformers to learn dynamic programs. We agree this is an interesting avenue 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 research topic holds significant importance as it aims to provide insights into the working mechanism of Transformers.\n\n- The proposed gradient decoding strategy is innovative and intriguing, adding novelty and interest to the study.", "reasons_to_reject": "- The distribution of constituency parse trees for a given sentence is highly peaked, which makes it a less suitable task to study whether Transformers can implement CKY, as acknowledged by the author in lines 81-86. The primary contribution of the first experiment in constituency parsing lies in the use of local loss and greedy decoding to improve parsing efficiency. However, it is worth noting that the parsing literature has already demonstrated that with a powerful neural encoder, parsers can achieve good performance using local classification loss and greedy decoding, as illustrated in Figure 1 of https://aclanthology.org/P19-1562.pdf and Table 5 of https://aclanthology.org/2023.acl-long.469.pdf. As a result, the significance of this particular contribution in the present work is somewhat diminished.\n\n- My complaint about this paper is that I believe the experiments in the constituency parsing section are entirely unnecessary. Emphasizing the speed advantage does not seem appropriate as the main or even partial motivation for this article. It would be more suitable to focus on fundamental questions like whether Transformers can learn dynamic programming algorithms like CKY. However, the study of this aspect in the paper appears to be relatively superficial and not very thorough, as it does not provide me with significantly novel insights.", "questions_to_authors": "- \"Physics of Language Models: Part 1, Context-Free Grammar\" (https://arxiv.org/pdf/2305.13673.pdf) demonstrates that Transformers can perfectly learn Context-Free Grammar (CFG). Does this finding contradict your results?  If not, could you kindly provide a brief explanation? \n\n- I am curious to know if \"Transformers Learn Shortcuts to Automata\" is related to the Transformers' ability to learn dynamic programs.", "paper_topic_and_main_contributions": "This study investigates the feasibility of implementing CKY using Transformers. The authors conduct two experiments: (1) training a neural constituency parser and (2) training on a synthesis dataset generated by a predefined PCFG. Both experiments utilize a local span classification loss and a heuristic greedy decoding algorithm without CKY.\n\nIn the first experiment, the authors achieve competitive performance compared to span-based parsers with CKY while achieving faster parsing speed.\n\nIn the second experiment, the authors observe that Transformers perform poorly when the grammar is highly ambiguous, suggesting that Transformers cannot perfectly implement CKY. However, they propose several effective techniques, such as weight sharing across layers, copy gates, and gradient decoding, to mitigate this issue and improve the performance.", "excitement": 3, "reproducibility": 4, "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": "- In lines 76-77 and 239-247, the paper \"https://aclanthology.org/C18-1011.pdf\" should be cited. This work is the earliest known usage of local span classification loss for constituency parsing."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates the feasibility of Transformers to approximate CKY algorithms. The authors evaluate their Transformer-based  CKY approximations on two data sets: standard benchmarks and a synthetic data set. This paper also introduces some changes in Transformer-based approximation, including a cross-entropy loss over possible constituents for spans, an inductive bias, decoding prediction from gradients etc. The main findings are 1): their Transformer-based  CKY approximation outperforms and runs faster over CKY algorithms on half of the standard benchmark sets; 2) however, experiments on more ambiguous synthetic data suggest their approach is not able to fully capturing the CKY. Those findings are beneficial to our parsing community.
Decision: Accept-Findings