Simple Hardware-Efficient PCFGs with Independent Left and Right Productions
Authors: Wei Liu
Songlin Yang
Yoon Kim
Kewei Tu
Venue: EMNLP 2023 Findings (2023)
Keywords: grammar induction
unsupervised parsing
latent variable models
TL;DR: A simplistic PCFG formalism built upon a stronger independence assumption exhibits remarkable performance

Abstract: Scaling dense PCFGs to thousands of nonterminals via low-rank parameterizations of the rule probability tensor has been shown to be beneficial for unsupervised parsing. However, PCFGs scaled this way still perform poorly as a language model, and even underperform similarly-sized HMMs. This work introduces $\emph{SimplePCFG}$, a simple PCFG formalism with independent left and right productions. Despite imposing a stronger independence assumption than the low-rank approach, we find that this formalism scales more effectively both as a language model and as an unsupervised parser. We further introduce $\emph{FlashInside}$, a hardware IO-aware implementation of the inside algorithm for efficiently scaling simple PCFGs. Through extensive experiments on multiple grammar induction benchmarks, we validate the effectiveness of simple PCFGs over low-rank baselines.

Simple Hardware-fffcient PCFGs with Independent Left and Right Productions
Wei Liu!: Songlin Yang", Yoon Kim², Kewei Tu
School of Information Science and Technology, ShanghaiTech University Shanghai Engineering Research Center of Intelligent Vision and Imaging 3 "Massachusetts Institute of Technology {liuwei4, tukww@shanghai tech. edu. cn (yangs166, yoonkim) edu
Abstract
more effectively (in terms of both language mod- eling and unsupervised parsing) than previous ap- proaches which scale PCFGs by factorizing the rulc probability tensor into low-rank components (Yang et al., 2021b, 2022). In particular, we find that sim- ple PCFGs can obtain significantly lower perplexity in language modeling while achieving higher un- supervised parsing performance compared to low- rank PCFGs with similar number of nonterminals, achieving a near state-of-the-ee of-the--rt unsupervised pars- ing performance on the Penn Treebank with an Fl of 65.1. We further describe a hardware-efficient IO-aware implementation of the inside algorithm, dubbed FlashInside, to facilitate scalable learning of simple PCFGs.
Scaling dense PCFGs to thousands of nonter- minals via low-rank parameterization the rule probability tensor has been shown to be beneficial for unsupervised parsing. However, PCFGs scaled this way still perform poorly language model, and even underperform similarly-sized HMMs. This work introduces SimplePCFG, simple PCFG formalism with independent left and right productions. Despite imposing a stronger independence assumption than the low-rank approach, we find that this formalism scales more effectively both as a lan- guage model and an unsupervised parser, As an unsupervised parser, our simple PCFG ob- tains an average F1 of 65.1 I on the English PTB, and language model, obtains a perplexity of 119.0, outperforming similarly-sized low- rank PCFGs. further introduce FlashInside, a hardware IO-aware implementation of the inside algorithm for efficiently scaling simple PCFGs.
Simple PCFGs
A PCFG be defined by a 6-tuple g (S,N E, R, T), where S is the distinguished start symbol, N/P/E are finite set of non- terminal/pre-terinna//teeem
symbols, R is a set production rules of the form,
1 Introduction
Despite the improvements in unsupervised pars- ing obtained through scaling neural probabilistic context-free grammars (PCFGs), their language model performance scales less favorably compared to, for example, hidden Markov models (HMMs) and neural language models. On the Penn Tree- bank, a neural PCFG with 30 nonterminals and 60 preterminals obtains 250 perplexity (Kim al., 2019), and while scaling neural PCFGs to thou- sands states via a low-rank parametcrization can improve perplexity to RS 170 (Yang et al., 2022), this still lags behind similarly-sized HMM, which obtains x 130 perplexity (Chiu et al., 2021), de- spite the fact that HMMMs are subclass of PCFGs simple
S - A, A - BC, AEN,B.CENUP TEP,WEE
ACN
w,
and R - [0, 1] maps rules to their associated probabilities. In simple PCFGs, decompose TA-BC into TBAA T TA-C, effectively assuming that left and right children are generated indepen- dently. We denote L, R E [| as the ma- trix representation of TBrA and h ArxC and apply neural parameterization over these matrices to compute the rule probabilities (Kim et al., 2019). See Appendix A for details.
This work proposes SimplePCFG, PCFG formalism with independent left and right productions. We find that this simple PCFG scales
For brevity we not distinguish between N and P the paper.
the
"This formalism has been discussed in Hsu et al. (2012). i.c., PCFG-I. We also experimented with PCFG-IE, where
"quual contribution.
L = R. hut found it necessary to distinguish between L and R. to achieve good performance.
Code: http:://wwwttbbooooosoutccoon//e

---

to avoid repeated computation, similar Cohen et al. (2013) and Yang et al. (2022). The result- ing complexity ( 12())) where I is sentence length.
A
R1
U
T
VUT
WUT
R
V
W
Vector form. We abuse the notation to have Daj Sij E RM,, Then we can write Bij Lickey Tik @ Say and My LB Sij R, where is the element-wise product.
B
C
B
R2
R3
Taj
(a)
(b)
(c)
Figure I: Bayesian network-like representations of PCFG binary rules: (a) original grammar, (b) after ten- sor decomposition (Yang et al., 202Ib), and (c) rank space grammar (Yang et al., 2022). Our simple PCFG is almost the same as (c) but uses a flexible parameteri- zation.
3.2 FlashInside
necessary to implement the inside algorithm on GPUs efficiently to facilitate scaling of simple PCFGs. We introduce FlashInside, a hardware- efficient I0-aware implementation of the inside algorithm in the spirit of FlashAttention (Dao et al., 2022). FlashInside comprises of four main tech- niques:
Comparing simple vs. low-rank PCFGs. The previous approach to scaling HMMs and PCFGs to thousands of nontermals is parameterizing the rule probability tensor T [ to be low- rank (Chiu al., 2021; Yang et al., 2021b, 2022). Low-rank PCFGs can be viewed as introducing new latent variable, namely "rank variable" R, to decompose TA-BC into ΣR TARRTB-RTROCC as shown in Fig. 1, where the tensor/matrix rep- resentations of TA-BC, TA-R; TBOR: RR are T, U, V.V.W. W, respectively. Yang et al. (2022, Sect. 4.2) show that low-rank PCFG can be re- parameterized as simple PCFG with independent left/right productions by marginalizing nontermi- nal variables and viewing the rank variables as new nonterminal variables. As such, low-rank PCFGs parameterize L, R in a more restrictive manner: L = VUT R = WUT. We speculate that the shared U would restrict the expressiveness of low- rank PCFGs and thus hinder optimization, which motivates our simple PCFGs.
Span-level parallelism. Given the span width w, the inside probability vector (((+w) could be computed in parallel for different starting position i (Yi et al., 2011, Sect. 4.2).
The log-einsum-exp trick. To improve numeri- cal stability, is common use the "log-sum-exp" trick. For example, letting o log Big. aij log nijs bij = log Sij. we have
oi = x² + +log Σ
exp(a = byj - xx) (1)
ickjj
where x² maxxaxxx bky) R Using log-sum-cxp could expensive when computing aı and bij. so we resort to the "log-einsum-ery" trick (Peharz et al., 2020, Sect. 3.2),
ai x² + log Lexp(os - x²))
3
A Hardware-efficient Inside Algorithm
by x + log R expp(o. - x1)
The inside algorithm for simple PCFGs The inside algorithm for simple PCFGs has the following recursive formula:
3.1
R.3 This allows us to leverage matrix multiplication operators, which are highly optimized on GPUs, to compute L Le - x²) and R. exp(o.; - x!).
where æt max Oij
3
Σ B.CEN
Σ
BB
TBeA JANC
Sckcj
Kernel fusion. The above computation involves many element-wiss operations and is thus memory- bounded. Loading and storing these vectors mul- tiple times would cause significant IO-cost (Dao et al., 2022). We reduce the 10-cost by fusing these operations whenever possible. Concretely, when
Σ
Σ
TBOA
BB
Σ
TAnC
BEN
CEN
where 3/ is the inside probability for span (A, i, with the base case 3 = π. A-way We cache By S
We abuse the notation for broadcasting vector-scalar ad- dition/subtraction.

---

Algorithm
W
1
Speed
Memory
Model
NT
ppl (J)
log-sum-exp
512
20
1x
100x
NHMM
4096
147
log-einsum-eNy exp
512
20
4.8x
3x
LHMM
16384
131.8
FlashInside
512
20
9.5x
1x
Rank HMM
16384
127.0
log-cinsum-cre
8192
20
1x
2x
Rank HMM
32768
126.4
FlashInside
8192
20
6x
Rank PCFG
4096
174.5
log-sum-exp
512
40
Ix
50x
Rank PCFG
8192
161.2+s.9
Ing-cinsum-exp
512
40
16x
3x
SN-PCFG 4096
125.4
FlashInside
512
40
44x
SN-PCFG
8192
119.0
log-cinsum-exp
8192
40
1x
2.4x
Table 2: Results on the PTB language modeling split from Mikolov al. (2011). NT denotes the number of nonterminals and ppl denotes perplexity. Top results are from previous papers (Chiu et al., 2021; Yang et al., 2022), while the bottom results from the current work. Our runs are averaged over 4 seeds.
FlashInside 8192
40
39x
1x
Table Ablation of how different elements of FlashIn- side contribute to speed and memory effiency, with different numbers of nonterminals ([V) ) and sentence lengths ()). For speed the regular log-sum-exp imple- mentation from Torch-Struct (Rush, 2020) is the base- line, whereas for memory our FlashInside serves as the baseline.
parallelism (e.g.. in Morch-Struc (Rush, 2020)). We can see that the use of log-einsun-exp trick significantly accelerate the running speed and re- duce the memory footprint. FlashInside uses the kernel fusion and recomputation techniques in ad- dition, resulting in further improvement, especially on larger grammars and longer sentences.
computing exp(oi at), we perform max, - exp in the same kernel that computes oiy; and we com- pute aij, bij at once by
[a:]bba]] = x² + log [L/R] exp(oij - -x') xx))
4 Experimental Setup
followed by fused element-wise log and addition operations.
Datasets. We conduct experiments the Penn Treebank (PTB) (Marcus al., 1993) dataset with two different splits: one for language modeling (Mikolov al., 201 1), and one for unsupervised parsing (Shen et al., 2018, 2019). We also evaluate our model on Chinese Treebank 5.1 (CTB) (Xue et al., 2005) and German and French treebanks from SPRML (Seddah et al., 2014).
Recomputation. While it possible to rely on automatic differentiation (AD) backpropagate through the inside algorithm (Fisner, 2016), this can be memory-inefficiet since AD would save all the intermediate results the DP computation, which are not needed. For example, in Eq. the partial differentiation between Oi and aik, buj is given by,
Baselines. Our HMM baselines include neural
HMM (NHMM) (Chiu et al., 2021), LHMM (Chiu et al., 2021), and Rank HMM (Yang et al., 2022). Our PCFG basclines include Neural/Compound PCFG (N/C-PCFG) (Kim et al., 2019), TN-PCFG Yang et al., 2021b) and Rank PCFG (Yang et al., 2022). t denotes our reimplementation. For Rank
dos 801j exp (aik + byj x²)
S0, öbbj
Σx exp (a.s + by - xx)
exp (aik + bbj - xx) cxp (asss + bkj Oij)
(o x²)
In the backward pass, we could recompute exp(ax + buj Oij) without the need to store exp(ax + byj x=") in the forward pass, thus sav- ing memory We found that this manual backprop- agation led slight decrease in running speed but greatly increased memory savings, and thus use it for all our experiments.
PCFG we use rank size 4096. See Appendix B for more implementation details.
We use perplexity (ppl) to evaluate language modeling and sentence-level F1 (S-FI) (Kim al., 2019) evaluate unsupervised parsing.
Evaluation.
5 Results
Speed comparison Table shows running speed and memory footprint measured under single NVIDIA-A40 GPU, where we compare against the standard log-sun-exp implementation of the inside algorithm which only leverages span-level 'This is also known as gradient checkpointing (Chen et al.,
We compare simple neural PCFG (SN-PCEF) to the baseline models. Table 2 shows the language modeling performance on PTB. SN-PCFG obtains significantly lower perplexity than Rank PCFG, and outperforms similarly-sizer HMMs. This in- dicates that simple PCFGs provide a viable path
2016).

---

Chinese
French
German
Model
NT
S-PI(1)
ppk())
S-FI(f)
ppl())
S-FI(t)
ppl(L)
Left Branching
7.2
5.7
10.0
Right-Brannn Branching
25.5
26.4
14.07
Random Trees
15.2
16.2
13.9
Kim (2022)
41.9
47.3
1. and Lu (2023)
48.7
40.8
N-PCIG
30
26.3+2..
45.0+2.0
42.3+110
C-PCFG
30
38.7+0.6
45.0+1.1
43.5=1.2
TN-PCFG
250
39.225.0
39.114.1
47.1
Rank PCFG
4096
31.00+8.9
409.4
31.2+9..
355.8+13.7
35.6=9.1
215.3
Rank PCFG
8192
32.418.2
372.6131.4
32.9_10.6
332.2
38.9
190.5
SN-PCFG
4096
39.9183
328.3
38.013.1
379.7
46.7
165.
SN-PCFG
8192
41.213.5
288.2
43.3
259.9
46.9
159.5
SC-PCFG
512
38.4
47.9
47.7 47.7
SC-PCFG
2048
42.9+2.9
49.9+1.7
49.1=1.0
Table 3: Results on the Chinese, French, and German treebanks. All runs are averaged over seeds.
Model
NT
S-F1 (1)
ppl (1)
ence for learning (see the appendix for the full pa- rameterization). We find that SN-PCFG performs better English while SC-PCIG achieves the best parsing performance in languages other than En- glish. We remark that the compound parameteriza- tion reported be compatible with low-rank parameterization probably due to optimization is- sues (Yang et al., 2021b). This work successfully scales compound PCFGs to thousands of states, which could be useful in some settings such as multimodal grammar induction which condition on vector representations of side information (Zhao and Titov, 2020; Jin and Schuler, 2020; Zhang al., 2021, 2022; Li al., 2022).
N-PCFG
30
50.8
252.6
C-PCFG
30
55.2
TN-PCFG
500
57.7
210.0
Rank PCFG
4500
64.1
168.0
Rank PCFG
4096
60. 7.6
17.7
Rank PCFG
8192
61.1 5.9
171.2
N-PCFG!
128
56.7_3.7
181.1
SN-PCFG
128
51.1-4.1
231.748.1
SN-PCFG
4096
65.1 2.1
132.5
SN-PCFG
8192
62.9
134.6+9.1
SC-PCFG
54.3 4.8
SC-PCFG
2048
60.6_3.6
PRPN
37.4
47.7
DIORA +span constraint
61.2
S-DIORA
57.6
Simple PCFG vs. Neural PCFG. Despite the better scalablity of simple PCFGs, we find that under the same number of nonterminal (i.c., 128), SN-PCFG expectedly underperforms N-PCFG both language modeling and unsupervised parsing (Table 4) due to the stronger independence assump- tion that is necessary for scaling. Nevertheless, N-PCFG does not scale well and (for example) runs into memory issues even with just 256 nonter- minals, while SN-PCFG can scale to 8192 nonter- minals on a single A40 GPU.
Constituency test
62.8
StructFormer
54.0
Fast-R2D2
57.2
Bight-Branching
39.5
Oracle Trees
84.3
Table 4: Unsupervised parsing performance the PTB
test set, including comparison against prior work (bot-
tom): PRPN (Shen al., 2018), ON (Shen et 2019).
DIORA (Drozdov et al., 2019; Xu et al., 2021). S- DIORA (Drozdov et al., 2020), Constituency tests (Cao al., 2020), StructFormer (Shen et al., 2021), and Fast- R2D2 (Hu et al., 2022). Whereever possible, we take the average Fl numbers across different seeds reported the above papers (instead of the max).
Simple PCFG vs. Rank PCFG. Recall that the rank PCFG and simple PCFG share an identical dynamic programming structure. The rank vari- able in the rank PCFG amounts to the nontermi- nal variable in the simple PCFG. Consequently, if we align the rank size in the rank PCFG with the nonterminal size in the simple PCFG, we achieve parity in terms of memory footprint and compu- tational speed within the dynamic programming computation. In our experiments, we opt for rank size of 4096 in the low-rank PCFG. The results, as presented in tables 2-4, showcase the worse perfor-
towards scaling PCFGs, despite the strict indepen- dence assumption.
Table 4 and 3 show the unsupervised parsing performance. SN-PCFG consistently outperforms Rank PCFG in S-F1 while obtaining much lower perplexity. We also experiment with the com- pound version of simple PCFGs (SC-PCFG) which uses an auxiliary sentence-level vector to model sentence-level properties and uses variational infer-

---

mance of the rank PCFG when compared to SN- PCFG with 4096 nonterminals. Interestingly, this work was motivated by our observation that merely augmenting the rank size of PCFG falls short in bridging the performance gap between HMMs and PCFGs in language modeling. This resulted in our exploring alternative parameterizations, culminat- ing in the straightforward independent left/right productions based parameterization which yields superior results in both language modeling and un- supervised parsing.
tral focus on optimizing the sentence log marginal likelihood objective function.
Simple PCFGs, due to their restrictive grammar nature, require many nonterminals for optimal per- formance. However, we observe diminishing re- turns while scaling up simple PCFGs. This phe- nomena is common in scaling up latent-variable models and future work might consider leveraging the technique from Liu al. (2023) to mitigate this issue.
When scaling up simple PCFGs, the computa- tion of grammar rule probabilities could also be ex- pensive, especially when constructing the emission probability matrix of size [|||) Compound parameterization exacerbates this issue since each sentence will have its own set of grammar rule probabilities. Consequently, we only used up 2048 nonterminals our SC-PCFG experiments.
6 Related Work
Independence assumptions are frequently made grammar learning for tractability and scalabil- ity. Simple PCFGs assume independent generation of left and right children, thus resembling split- head dependency grammars (Eisner, 1996; Collins, 1997; Eisner and Satta, 1999; Paskin, 2001; Klein and Manning, 2004). We have shown that trading expressiveness (of grammar formalism) for scal- ablity is beneficial, and this idea could be applied to other complex grammar formalism of high parsing complexity, such as mildly context-sensinee gram- mars (Yang et al., 2023), synchronized grammars (Kim, 2021: Wang et al.. 2022; Friedman et al.. 2022; Lou and Tu, 2023) and lexicalized grammars (Zhu et al., 2020; Yang et al., 2021a).
Acknowlgedment
This study was supported by the National Natural Science Foundation of China (61976139) and by funds from an MIT-IBM Watson Al Lab grant.
References
Steven Cao, Nikita Kitaev, and Dan Klein. 2020. Unsu- pervised parsing via constituency tests. In Proceed- ings of the 2020 Conference on Empiricul Methods in Natural Language Processing (EMNLP), pages 4798 4808, Online. Association for Computational Linguistics.
7
Conclusion
In this work we explore a simpler variant of PCFGs (SimplePCFG) that shows better scaling properties than previous approaches in terms of both language modeling and unsupervised parsing performance. We also introduce a hardware-aware version of the inside algorithm (FlashInside) which improves over existing vectorized GPU implementations.
Tianqi Chen, Bing Xu, Chiyuan Zhang, and Carlos Guestrin. 2016. Training deep nets with sublinear memory cost. CoRR, abs/1604.06174.
Justin T. Chiu, Yuntian Deng, and Alexander M. Rush. 2021. Low-rank constraints for fast inference in structured models. In Advances in Neural Infor- mation Processing Systems 34: Annual Conference Newral Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 2887-2898.
Limitations
We have successfully bridged the gap between HMMs and PCFGs in language modeling. How- ever, a significant disparity remains between PCFGs and neural models like Transformers. While we recognize the potential of our hardware- efficient inside algorithm implementation for con- ducting large-scale language modeling experi- ments, our aim is position PCFGs direct rivals to neural models, given the intrinsic limi- tations arising from PCFG's strong context-free independence assumption. Our main objective is to enhance unsupervised PCFG learning, with a cen-
Shay B. Cohen, Giorgio Satta, and Michael Collins. 2013. Approximate PCFG parsing using tensor de- composition. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguisticx: Human Language Technologies, pages 487-496, Atlanta, Georgia. As- sociation for Computational Linguistics.
Michael Collins. 1997. Three generative, lexicalised models for statistical parsing. In 35th Annual Meet- ing of the Association for Computational Linguistics and Sth Conference of the European Chapter of the

---

Association for Computational Linguisties, pages 16- 23, Madrid, Spain. Association for Computational Linguisties.
Conference on Empirical Methods in Natural Lan- guage Processing, pages 2809-2821, Abu Dhabi, United Arab Emirates. Association for Computa- tional Linguistics.
Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. 2022. Flashattention: Fast and memory-efficient exact attention with io-awareness. In NewrlPS.
Lifeng Jin and William Schuler. 2020. Grounded PCFG induction with images. In Proceedings of the 1st Conference of the Asia-Pacific Chapter of the Asso- ciation for Computational Linguistics and the 10th International Joint Conference on Natural Language Processing, pages 396-408, Suzhou, China. Associa- tion for Computational Linguistics.
Andrew Drozdov, Subendhu Rongali, Yi-Pei Chen, Tim O'Gorman, Mohit lyyer. and Andrew McCallum. 2020. Unsupervised parsing with S-DIORA: Single tree encoding for deep inside-outside recursive au- toencoders. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Process- ing (EMNLP), pages 1832-4845, Online. Association for Computational I Linguistics.
Taeuk Kim. 2022. Revisiting the practical effective- ness of constituency parse extraction from pre-trained language models. In Proceedings of the 29th Inter- national Conference Compitational Linguistics, pages 5398 5408. Gyeongju, Republic of Korea. In- ternational Committee on Computational Linguistics.
Andrew Drozdov, Patrick Verga, Yi-Pei Chen, Mohit lyyer, and Andrew McCallum. 2019. Unsupervised labeled parsing with deep inside-outside recursive autoencoders. In Proceedings of the 2019 Confer- ence on Empirical Methods Natural Language Pro- cessing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 1507-1512 Hong Kong, China, Association for Computational Linguistics.
Yoon Kim. 2021. Sequeecc-to-scquenee learning with latent neural grammars. In Advances in Neural In- formation Processing Systems 34: Annual Confer- ence on Neural Information Processing Systems 2021, NeurlPS 2021. December 6-14, 2021, virtual, pages
Yoon Kim. Chris Dyer, and Alexander Rush. 2019. Compound probabilistic context-free grammars for grammar induction. In Proceedings of the 57th An- nual Meeting of the Association for Computational Linguistics, pages 2369-2385, Florence, Italy, Asso- ciation for Computational Linguistics.
Jason Eisner. 2016.
ouside- and forward- backward algorithms are just backprop (tutorial pa- per). In Proceedings of the Workshop on Structured Prediction for NLP, pages 1-17, Austin, TX. Associ- ation for Computational I. Linguistics.
Dan Klein and Christopher Manning. 2004, Corpus- based induction of syntactic structure: Models of dependency and constituency. In Proceedings of the 42nd Anmual Meeting of the Association for Computational Linguistics (ACL-044) pages 478-485, Barcelona, Spain.
Jason Fisner and Giorgio Satta. 1999, Efficient parsing for bilexical context-free grammars and head automa- ton grammars. In Proceedings of the 37th Annual Meeting of the Association for Computational Lin- guistics, pages 457-464, College Park. Maryland, USA. Association for Computational Linguistics.
Boyi Li, Rodolfo Corona, Karttikeya Mangalam, Cather- ine Chen, Daniel Flaherty, Serge J. Belongie, Kil- ian Q. Weinberger, Jitendra Malik. Trevor Darrell, and Dan Klein. 2022. Does unsupervised grammar induction need pixels? CoRR, abs/2212. 10564.
Jason M. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In COLING 1996 Volume 1: The 16th International Conference on Computational Linguistics.
Dan Friedman, Alexander Wettig, and Danqi Chen. 2022. Finding dataset shortcuts with grammar in- duction. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 4345-4363, Abu Dhabi, United Arab Emirates. Association for Computational Linguisties.
Jiaxi Li and Wei Lu. 2023. Contextual distortion reveals constituency: Masked language models are implicit parsers. In Proceedings of the 61 Annual Meet- ing of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5208 -5222, Toronto, Canada. Association for Computational Linguisties.
Daniel J. Hsu, Sham M. Kakade, and Percy Liang. 2012. Identifiability and unmixing of latent parse trees. In Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meet- ing held December 3-6, 2012. Lake Tahoe, Nevada, United States, pages 1520-1528.
Anji Liu, Honghua Zhang, and Guy Van den Broeck. 2023. Scaling up prohabilistic circuits by latent vari- able distillation. In The Fleventh International Con- ference on Learning Representations.
Chao Lou and Kewei Tu. 2023. Improving grammar- based sequence- to-seuuence modeling with decom- position and constraints. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics ( (Volume 2: Short Papers), pages 1918- 1929, Toronto, Canada. Association for Computa- tional Linguistics.
Xiang Hu, Haitao Mi, Liang Li, and Gerard de Melo. 2022. Fast-R2D2: A pretrained recursive neural net- work based on pruned CKY for grammar induction and text representation. In Proceedings of the 2022

---

Mitchell P. Mareus, Beatrice Santorini. and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of english: The penn treebank. Comput. Lin- guistics, 19(2):11-3330
Workshop on Machine Learning and Programming Languages, MAPL@ PLDI 2019. Phoenix, AZ, USA, June 22, 2019, pages 10-19. ACM.
Bailin Wang. Ivan Titov, Jacob Andreas, and Yoon Kim. 2022. Hierarchical phrase-based sequence-to- sequence learning. In Proceedings of the 2022 Con- ference on Empirical Methods in Natural Language Processing, pages 8211-8811888 18199, Abu Dhabi, United Arab Emirates. Association for Computational Lin- guistics.
Tomás Mikolov, Anoop Deoras. Stefan Kombrink, Lukás Burget, and Jan Cernocky. 2011. Empirical evaluation and combination of advanced language modeling techniques. In INTERSPEECH 2011, 12th Annual Conference of the International Speech Com- munication Association, Florence, Italy, August 27- 31, 2011, pages 605-608. ISCA.
Mark Paskin. 2001. Grammatical bigrams. In Ad- vances in Neural Information Processing Systems, volume 14. MIT Press.
Zhiyang Xu, Andrew Drozdov, Jay Yoon Lee, Tim O' O'Gorman, Subendhu Rongali, Dylan Finkbeiner, Shilpa Suresh, Mohit lyyer, and Andrew McCallum. 2021. Improved latent tree induction with distant su- pervision via span constraints. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 481 18-4831, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
Robert Peharz, Steven Lang. Antonio Vergari, Karl Stelzner. Alejandro Molina, Martin Trapp. Guy Van den Broeck, Kristian Kersting, and Zoubin Ghahra- mani. 2020. Einsum networks: Fast and scalable learning of tractable probabilistic circuits. In Pro- ceedings of the 37th International Conference on Machine Learning. JCML 2020, 13-18 July 2020, Vir- tual Event, volume 119 of Proceedings of Machine Learning Research, pages 7563-7574. PMLR.
Nianwen Xue, Fei Xia, Fu-Dong Chiou, and Martha Palmer. 2005. The penn chinese treebank: Phrase structure annotation of a large corpus. Nat. Lang. Eng. 1122):007-233.
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 Linguisties.
Songlin Yang. Roger P Levy, and Yoon Kim. 2023. Un- supervised discontinuous constituency parsing with mildly context- context-sensitive grammars. In Proceedings of ACI.
Djamé Seddah, Sandra Kübler, and Reut Tsarfaty, 2014. Introducing the SPMRL 2014 shared task on pars- languages. In Proceedings
Songlin Yang, Wei Liu, and Kewei Tu. 2022. Dynamic programming in rank space: Scaling structured in- ference with low-rank HMMs and PCFGs. Pro- ceedings of the 2022 Conference of the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, pages Seattle, United States. Association for Computational Linguistics.
ing morphologically-tin of the First Joint Workshop on Statistical Parsing of Morphologically Rich Languages and Syntactic Anal- ysis of Non-Canonicnt Languages, pages 103-109, Dublin, Treland. Dublin City University.
Yikang Shen, Zhouhan Lin, Chin-Wei Huang, and Aaron Courville. 2018. Neural Language Modeling by Jointly Learning Syntax and Lexicon. In Proceed- ings of ICLR.
Songlin Yang, Yanpeng Zhao, and Kewei Tu. 2021a. la. Neural bi-lexicalized PCFG induction. In Proceed- ings of the 59th Annual Meeting of the Association for Computational Linguisties and the 1 1ith International Joint Conference on Natural Language Processing ( (Volume I: Long Papers), ), pages 2688-2699 Online. Association for Computational Linguisties.
Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. 2019. Ordered Neurons: Integrat- ing Tree Structures into Recurrent Neural Networks. In Proceedings of ICLR.
Yikang Shen, Yi Tay. Che Zheng, Dara Bahri, Donald Metzler, and Aaron Courville. 2021. StructFormer: Joint unsupervised induction of dependency and con- stituency structure from masked language modeling. In Proceedings of the 59th Annual Meeting of the A Association for Computational Linguistics and the
Songlin Yang, Yanpeng Zhao, and Kewei Tu. 2021b. PCFGs can do better: Inducing probabilistic context- free grammars with many symbols. In Proceedings of the 2021 Conference of the North American Chap- ter of the Association for Computational Linguistics: Human Language Technologies, pages 1487-1498, Online. Association for Computational Linguistics.
1 1tth International Joint Conference on Natural Lan- guage Processing (Volume 1: Long Papers), pages 7196-7209, Online. Association for Computational Linguistics.
Youngmin Yi, Chao- Lai, Slav Petrov, and Kurt Keutzer. 2011. Efficient parallel CKY parsing on GPUs. In Proceedings of the 12th International Conference Parsing Technologies, pages 175-185, Dublin, Ireland. Association for Computational Lin- guistics.
Philippe Tillet, Eisiang-Tsung, Kung, and David D. Cox. 2019. Triton: an intermediate language and com- piler for tiled neural network computations. Pro- ceedings of the 3rd ACM SIGPLAN International

---

Songyang Zhang, Linfeng Song. Lifeng Jin, Haitao Mi, Kun Xu, Dong Yu, and Jiebo Luo. 2022. Learning grammar inducer from massive uncurated instruc- tional videos. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Process- ing, pages 233-247, Abu Dhabi, United Arab Emi- rates. Association for Computational Linguistics.
across different grammar rules; and the use of resid- ual connections in f2, fa. fa.
Simple Compound PCFG Similar to compound PCFGs, we parameterize our simple compound PCFGs with a latent variable p(=). We replace three rule probabilities TBAA: TBCA and тт- with x, gr Eg; 0), while leaving the remain- ing rule probabilities as gr (. 0). The function Tr gr Eg; f) can take one of the following forms:
Songyang Zhang. Linfeng Song, Lifeng Jin, Kun Xu, Dong Yu, and Jiebo Luo. 2021. Video-aided unsuper- vised grammar induction. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1513-1524, Online. Association for Computational Linguistics.
exp (f2 (W f' ([W =]))
Yanpeng Zhao and Ivan Titov. 2020. Visually grounded compound PCFGs. In Proceedings of the 2020 Con- ference on Empirical Methods in Natural Language Processing (EMNLP), pages 4369-4379, Online. As- sociation for Computational Linguistics.
TBAA
LB'eNuu exp (f2 (w (v)) I'' ([wai z1))
exp (fa (w)) I's ([WA; 2]))
TAnC
Ecerup exp (/4 (W2) S/J ([WA; =|))
Hao Zhu, Yonatan Bisk, and Graham Neubig. 2020.
exp (u ([WT; =]))
The Return Lexical Dependencies: Neural Lexi- calized PCFGs. Transactions of the Association for Computational Linguistics, 8:647-661.
TT >u
Enrex exp (u [wr;2])
where fa S' are neural networks which are sim- ilar to fa, f' but with different input shape.
A Neural Parameterization
We present the neural parameterization of our sim- ple neural pefg and simple compound pcfg. We use Eg [w N (S) UNUP) to denote sym- bol embeddings for simple PCFG and function gr (::0) = Tr parameterized by 9 to denote neural parameterization function.
B Implementation Details
We follow Mikolov et al. (2011) to preprocess PTB language modeling split data. For other datasets, we use the preprocessing from Yang et al. (2021b). We implement our model based on the code- base of Yang et al. (2022). And most hyper- parameters follow their settings. We use Xavier normal initialization to initialize neural networks. Our model is optimized by Adam optimizer with 31 0.75, 822 0.999, and learning rate 0.002. All dimensions of symbol embeddings are set to 512. Our FlashInside is implemented with Triton (Tillet et al., 2019) S, an open-source python-like GPU programming language. For the latent vari- able in SC-PCFG, we follow the implementation of Kim et al. (2019) which applies max- maxx-oooiing layer over the hidden states of the BiLSTM to obtain sentence representation and generates 64- dimensional mean vectors u(w) and log-variances log o (w) by leveraging an affine layer.
We use neural networks to parameterize these rule probabilities. The neural parameterization of all rule probabilities n, starts from corresponding symbol embeddings in Eg. Pa- rameterization function gr can be formulated as gr (Eg: () in simple neural PCFG, which takes from one these forms:
Simple Neural PCFG
exp /1 (wss)
TS > Σ AEEN exp (1 (uy' (ws))*
exp (fe ( f3 (WA))
TB Σ BENUP exp (fz (WB:) fa (wa))
exp (fr (wT) fa (Wa)
TA-C EoeNUp exp (fs (wT)) fs (WA))
We run all experiments on NVIDIA V100 and NVIDIA A40. All experimental results are aver- aged from four runs.
exp (uT (wr))
Tr yo Ewer exp Tu fa (WT))
where S1, fo are two-layer residual networks; f2. fa. f4 are one-linear-layer with ReLU activa- tion function and residual connections. We high- light the usefulness of sharing symbol embedding


Reviews:
[{"review_id": "ObLmV9x9KT", "reviewer": "Reviewer_vYhR", "summary": "", "questions": "", "limitations": "", "rating": 2, "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": "Thank you for your comment. We would like to clarify a major misunderstanding of our main contribution.\n- First of all, our primary contribution lies in the identification of a more effective parameterization for PCFGs, one that offers superior scalability properties in both language modeling and unsupervised parsing. This primary contribution (described in section 2) is independent of FlashInside, our second contribution (section 3). \n- Second, within FlashInside, the cache trick is introduced as a background technique in section 3.1 and is certainly not our main contribution.\n\nWith regard to the experimental scale, we observe that our setup is well-aligned with common practices in the literature of unsupervised parsing. While we recognize the potential of our hardware-efficient inside algorithm implementation for conducting large-scale language modeling experiments,our aim is **not** to position PCFGs as direct rivals to neural models, given the intrinsic limitations arising from PCFG's strong context-free independence assumption.\n\nOur primary goal is improving unsupervised PCFG learning. The crux of this lies in optimizing the objective function of sentence log marginal likelihood.  By pivoting from a low-rank parameterization to a more straightforward independent left/right productions based parameterization, we observe better scaling properties (i.e., better language modeling/unsupervised parsing performance as we increase the number of nonterminals). \n\n Regarding the lack of more recent and better baselines, we believe we have compared our models to other strong unsupervised parsers for English. We will add more baselines such as [1, 2] for German and French. To the best of our knowledge, rank PCFG, TN-PCFG, [1] achieved SOTA performance before in English, German and French, respectively. Our simple PCFG outperforms these models and thereby achieving new SOTA in these languages. \nFor language modeling, as we explained above, we deliberately do not compare our model to strong neural models.\n\n[1] https://aclanthology.org/2023.acl-long.285/ \n\n[2] https://aclanthology.org/2022.coling-1.479/", "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": "* Detailed descriptions of the tricks needed\n* Well rounded experiments", "reasons_to_reject": "* The main contribution is a very simple almost trivial trick which caches children and hence allows for span-level parallelism  which has been proposed before (Cohen et al., 2013; Yang et al., 2022); this paper implements it on GPUs. **(In response to confusion raised in the author response:)  This technique (FlashInside) along with SimplePCFG, that is, independent left and right productions give rise to the more GPU-efficient implementation that has been helpful on PCFG-based unsupervised parsing but not on language modelling in terms of PPL**\n* Experiments are small scale\n* Lacks comparisons with more recent and better baselines", "questions_to_authors": "", "paper_topic_and_main_contributions": "This paper proposes a GPU efficient variant of PCFGs\n(SimplePCFG) that scales better than previous approaches, demonstrating improvements over previous proposals in both language modelling (zh, de, en) and unsupervised parsing (ptb). The main contributions are FlashInside -- an inside estimation which is GPU parallelizable on the span level and some other tricks to make it GPU efficient.", "excitement": 2, "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": "AyJ8ufl5Jo", "reviewer": "Reviewer_KFL6", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comment. In fact, we have already investigated “how the simple PCFG formulation affects memory/speed compared to the rank PCFG formulation” . It's worth noting that the rank PCFG and simple PCFG share an identical dynamic programming structure. The rank variable in the rank PCFG amounts to the nonterminal variable in the simple PCFG, as mentioned in Sect. 2. Consequently, if we align the rank size in the rank PCFG with the nonterminal size in the simple PCFG, we achieve parity in terms of memory footprint and computational speed within the dynamic programming computation. This particular aspect has been explored in our experiments. As indicated in lines 183-184, we opt for a rank size of 4096 in the rank PCFG. The results, as presented in tables 2-4, showcase the worse performance of the rank PCFG when compared to SN-PCFG with 4096 nonterminals.\n\nLastly, we'd like to remark that this work was motivated by our observation that merely augmenting the rank size of PCFG falls short in bridging the performance gap between HMMs and PCFGs in language modeling. This resulted in our exploring alternative parameterizations, culminating in the straightforward independent left/right productions based parameterization which yields superior results in both language modeling and unsupervised parsing.", "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 paper is clearly written, offering a simple yet robust formulation and an efficient implementation supported by solid experiments for a short paper.", "reasons_to_reject": "I believe this is a valuable paper that should be accepted. One comparison that is missing is how the simple PCFG formulation affects memory/speed compared to the rank PCFG formulation. Presumably, the more expressive formulation would require more memory, and it would be insightful to compare these two approaches at the same memory footprint.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper proposes a simple PCFG formulation for unsupervised parsing with independent left and right products, which scales more effectively to large number of nonterminals. Their formulation resembles the low-rank PCFG but does not utilize the low-rank restriction, granting it greater expressive power. Additionally, the authors present a hardware-efficient implementation that leverages span-level parallelism, the log-einsum-exp trick, and kernel fusion to enhance speed and reduce memory requirements. The experiments conducted on English, Chinese, French, and German treebanks demonstrate that the proposed approach achieves significantly improved parsing and language modeling capabilities. ", "excitement": 4, "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": "7AMh9AYTUp", "reviewer": "Reviewer_ZpL2", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review. We want to emphasize that our proposed simple PCFG achieves SOTA performance in terms of **unsupervised parsing** on multiple languages: English, German and French. We have incorporated many strong baselines for English and will include other strong baselines such as [1] for German and French.  To the best of our knowledge, rank PCFG, TN-PCFG, [1] achieved SOTA performance in English, German and French, respectively. Our simple PCFG outperforms these models and thereby achieving new SOTA.  For language modeling, as we will explain later, we deliberately do not compare our model to strong neural models such as Transformers.\n\n[1] https://aclanthology.org/2023.acl-long.285/ \n\nWith regard to the experimental scale, we observe that our setup is well-aligned with common practices in the literature of unsupervised parsing. While we recognize the potential of our hardware-efficient inside algorithm implementation for conducting large-scale language modeling experiments, it's important to clarify our objective. Our aim is not to position PCFGs as direct rivals to neural models, given the intrinsic limitations arising from PCFG's strong context-free independence assumption.\n\nOur primary goal is improving unsupervised PCFG learning. The crux of this lies in optimizing the objective function of sentence log marginal likelihood.  By pivoting from a low-rank parameterization to a more straightforward independent left/right productions based parameterization, we observe better scaling properties (i.e., better language modeling/unsupervised parsing performance as we increase the number of nonterminals).", "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": "- Simple and clean formulation.", "reasons_to_reject": "- Fairly light on substance.\n- Results are far from state-of-the-art and very small scale.", "questions_to_authors": "", "paper_topic_and_main_contributions": "This short paper proposes a simple factoring of the binary production rules of a PCFG. Instead of generating both children together, each child is produced independently. I am somewhat surprised that this has not been proposed before.\nThe authors then additionally discuss efficient an implementation that is optimized for GPUs.\nFinally, the paper presents perplexity results on the Penn Treebank. The experiments are very small scale. The proposed method outperforms regular PCFGs and similar-sized HMMs, but there are no comparisons to the state of the art (which achieves far stronger results).", "excitement": 2, "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": {}}]

Author rebuttal:

Meta-review: This short paper proposes a simple PCFG formalism, which produces each child independently in a PCFG production rule. This simplification scales more effectively to large number of nonterminals. Experimental results on four treebanks show significant improvements over low-rank PCFG with same number of nonterminals, and also better performance than other unsupervised parsing algorithms (e.g. C-PCFG, S-DIORA and ON). This paper also introduces a hardware-efficient implementation to speedup the computation with lower memory usage.  Despite the simplicity of this approach, as a short paper, the experimental results on both unsupervised parsing and language modeling should be beneficial to the community of unsupervised parsing.
Decision: Accept-Findings