Treepiece: Faster Semantic Parsing via Tree Tokenization
Authors: Sid Wang
Akshat Shrivastava
Aleksandr Livshits
Venue: EMNLP 2023 Findings (2023)
Keywords: semantic parsing
decoding
tokenization algorithm
parse tree
TL;DR: We introduce TreePiece, a new technique that accelerates semantic parsing modeling by tokenizing parse trees into subtrees.

Abstract: \emph{Autoregressive} (AR) encoder-decoder neural networks have proved successful in many NLP problems, including \emph{Semantic Parsing} -- a task that translates natural language to machine-readable \emph{parse trees}. However, the sequential prediction process of AR models can be slow. To accelerate AR for semantic parsing, we introduce a new technique called \emph{TreePiece} that tokenizes a parse tree into subtrees and generates one subtree per decoding step. On TOPv2 benchmark, TreePiece shows $4.6$ times faster decoding speed than standard AR, and comparable speed but significantly higher accuracy compared to \emph{Non-Autoregressive} (NAR).

TreePiece: Faster Semantic Parsing via Tree Tokenization
Sid Wang Meta Inc. USA yuwang2020@mette com
Akshat Shrivastava Meta Inc. USA
Aleksandr Livshits Meta Inc. USA alll@meta. com
akshatsemeta.com com
Abstract
Utteranee
prodictions
Autoregressive (AR) encoder-decoder neural networks have proved successful in many NLP problems, including Semantic Parsing a task that translates natural language to machine- readable parse trees, However, the sequential prediction process of AR models can be slow. To accelerate AR for semantic parsing, we in- troduce a new technique called TreePiece that tokenizes parse tree into subtrees and gener- ates one subtree per decoding step. On TOPv2 benchmark, TreePiece shows 6.1 times faster decoding speed than standard AR, and compa- rable speed but significantly higher accuracy compared Non-Autoregressive (NAR).
NAR Uttrrnce Decoder
TreePince predictions
AR TreePioce
Decoder
Utterance Ecuceder
Figure 1: TreePiece-bassee parse tree modeling design.
1 Introduction
Autoregressive (AR) modeling (Sutskever et al., 2014) is commonly adopted framework in NLP where the next prediction is conditioned the pre- viously generated tokens. This paper focuses on AR approach for Semantic Parsing (Wong, 2005), an NLP task that converts natural language ut- terance to a machine-ine iittiinnnintrrrrtabllc symbolic rep-
Our contributions
We proposc a novel approach of tokenizing parse trees into large units called TreePiece units, and then building an AR model that predicts one TreePiece wnit at time, thus reducing the number of steps needed to generate full parse tree. To the best of our knowledge, subword-tokenizer algorithm to semantic trees such that each token subtree.
the first to extend
resentation called logical form. The sequence of actions to derive logical form is isomorphic to directed tree and often referred to as parse tree (Zettlemoyer and Collins, 2005).
We validate our approach on TOPv2 bench- mark and show that TreePiece decoding is 6.1 times faster than standard AR with less than 0.15% accu- racy degradation, and nearly as fast as NAR with up to 0.7% accuracy gains.
The runtime latency of AR linearly correlates the output length and could result in low inference speed (Gu al., 2017; Wang et al., 2018), Non-Autoregresssvv (NAR) modeling (Gu et al., 2017; Wei et al., 2019; Ma et al., 2019), on the other hand, is able to produce outputs in parallel and reduce latency by an order of magnitude (Ghazvininejad et al., 2019). However, NAR performs considerably worse than its AR counterparts without extra training recipes (Wang al., 2019; Zhou and Keung, 2020; Su et al.. 2021). The quality benefits of AR models therefore motivates us to improve their speed, rather than exploring NAR.
We provide theoretical proofs to support our main algorithms and their variants.
2 Methods
2.1 Parse tree
In this paper, we utilize the hierarchical seman- tic representations based on intent and slot (Gupta et al., 2018), allowing for modeling complex com- positional queries in task-oriented dialog systems. See Figure 2 (LHS) for an example. Now let us

---

insereate reminder
increatte _
Alperson reniidede
si todo
Create placeholder
MISSING
diperion_remindeer
all todo
Tokenize
Replace
in: menange
sead message
slrrciiionn
aicontent
Airecipicot
slccontent exact
Assemble
Create placeholder
Susan
in:get_event event
Suan
MISSING
Replace
alicategory event
slidate_time
in in:getevvent
moeting
tonight
c.ccttgoryy event
sldatte time
the meeting
tonight
Figure 2: Illustration of tokenizing parse tree/assembling TreePiece units with the placeholder design for given utterance "Remind me send Susan email about the meeting tonight".
define a few recurring notions in the paper: Definition 2.1 (Ontology). parse tree node is called an ontology iff represents an intent/slot, prefixed by in: and sl: respectively.
computes the optimal tokenization and probability for given skeleton
Notations in Algorithm 1:
Definition 2.2 (Skeleton). The skeleton of parse tree is the subtree that consists of all ontologies. Definition 2.3 (Utterance leaf). A text-span node is called ulterance leaf iff its parent is !
(1) T is the set of all subtrees of S that share the same root as S denoted by T; T admits a natural filtration To C ... C Ta-1 C Ta C .... T.
where Ta is the set of all depth-d-subtrees.
(2) L is the log probability on T as follows:
2.2 TreePiece tokenizer
p(()
if V. otherwise
2.2.1 Tokenizer algorithm
_l()
-00
Definition 2.4. TreePiece tokenizer is an algorithm that segments any skeleton into subtrees of an open vocabulary. The minimal open vocabulary of TreePiece tokenizer is called TreePiece vocabu- lary, where element called TreePiece unit. Definition 2.5 (TreePiece simplex). Let V be TreePiece vocabulary and & be any TreePiece unit. A Tree Piece simplex is a mapping from V to the unit interval [0, 1] such that Σiev ((t)=
where V is the TreePiece vocabulary and the TreePiece simplex.
(3) for efficiency we apply Filter(s, t) to re- strict subtrees e' such that (a) l' is subtree of (b) the set difference At has exactly one con- nected component and it is a TreePiece unit.
In summary, the the forward step uses dynamic pro- gramming inductive on tree-depth to update all subtrees' fog-probabilities and eventually obtain P(S: p) the probability of the skeleton S. The forward step also returns map S that stores for each E T the optimal position of its previous partition. Then in the backward step we can back- track along the path S, (S), (S)), .. to recover the optimal partition (p)
We propose Algorithm 1 as our TreePiece lokenizer, a Viterbi-type (Viterbi, 1967) forward- backward (Nagata, 1994a) algorithm which
WW adopt the decoupled form proposed in (Aghajanyan et al., 2020), which simplifies compositional representations by ignoring text spans that are not utterance leaves.

---

Algorithm 1 Forward--bckkwa algorithm
Algorithm 2 EM algorithm
Input: TreePiece vocabulary V, TreePiece sim- plex p, and skeleton S.
6 , Choose No E N
0; initialize <- O,
A + +00, Lprev + -cc. while < No and A > én do Leurs +- 0 + Zero function on V for S E y do
Output: Partition (p) and probability p)):
<- All subtrees of with the same root.
L +- (pg(p)
9 < Constant map from T to BOS token
Compute ( (p,),) Leurt Ceur log p;)
and P(S:p,) > E-step
dmax < Depth of S
for d =
dmax do // Forward begins
for E Ts( do
for t E Ta do
F*(t) Ft) +1
for d' = 2,2. dd do
for E V do
for t' Filter(Te:: do
(t)
Pit Pi+1 Erey (r())
M-step
A L'At
1, (1) + +EEEs logp(r)
i 1-i+1,40 t- Leurr - Lprev
if > (t) then
Lprev + Lour
((t c L-, t -
P(S:P) + exp(. (5)) Forward ends fourr <- S, Ts (p) <- 0 // Backward begins while fourr + BOS token, do (prev s- 9 (faurr) A (prev Mearr
To solve (1) in polynomial time, we propose Al- gorithm 2 (whose E-step uses Algorithm 1) and impose the following assumption on the joint dis- tribution of S and
Tp(p) t (p) UA*, feur fprey
Tp) (P) U(feum) // Backward ends return (p). p)
Trr =
= Tp(pp)
IPSS, T. p) x
(3)
0
otherwise,
where (p) = e
Applying (3), we see that all but one summand in (2) vanish.
2.2.2 Tokenizer training
The following Theorem claims that Algorithm 2 solves for (1) under assumption (3):
The performance of Algorithm 1 relies on the qual- ity of TreePiece vocabulary V and TreePiece sim- plex p. To improve the quality of V and p, propose a two-stage training procedure:
Theorem 2.6. Let Po. Pi. be TreePiece sim- plices obtained from Algorithm 2. If (3) is true, then (1) holds. Moreover, Esc, log (P(Spp)) is monotonically non-decreasing in
Stage 1, Generate V: Let y represent all skele- tons of given training corpus. Similar to Byte Pair Encoding (BPE) (Gage, 1994; Sennrich et al., 2015), we obtain the TreePiece vocabulary V and map Fo between TreePiece units and their frequen- cies in S. For details see Appendix A.
For proof of Theorem 2.6, Appendix B.
2.3 Modeling
We describe the model that generates parse tree components and the method to piece them together.
Stage 2, Update p: initialize the TreePiece simplex Po as the normalized frequency Po(l)= Fo(t)/Erey Fo(r) for all V and then solve for P++1 iteratively as follows:
2.3.1 Modeling mechanism
As illustrated in Figure 1, an encoder computes the hidden states of given utterance, then an AR de- coder consumes the encoder hidden states and gen- erate TreePiece units autoregressively. The tech- nique in Subsection 2.3.2 will allow us to put these units together and obtain full skeleton. The skele- ton then uniquely determines the number (denoted by N) and positions of all utterance leaves (see Figure 2), which offers us the convenience use an NAR decoder to generate utterance leaves within one step. For NAR utterance decoder, we closely follow (Ghazvininejad et al., 2019): first
Σ Ens log S: SC.
Pi+1 argmax, p
(1)
In general, problem (1) is NP-hard as it involves summing over IIs, the set of all possible partitions и of skeleton S:
Ens log ((S, T: S;ps]
IP(S, T.
Σ rells
log r))
P(S:p:)

---

CPU Decoding
CPU Inference time (ms)
GPU Decoding time (ms)
GPU Inference time (ms)
EM (%)
EM-S (%)
time (ms)
Baselines
AR NAR
86.99
89.13
45.53
63.81
44.87
55.77
86.29
88.56
7.00
25.21
6.42
17.56
Our method
TreePiece- 200
86.51
89.05
7.61
25.89
6.66
17.75
TreePiece- 800
86.73
89.13
7.79
26.04
7.09
18.12
PreePiece600 86.86
89.26
7.85
26.14
7.34
18.45
TreePiece-500 86.65
89.10
7.94
26.53
7.81
19.84
TreePiece 86.56
89.02
7.86
26.21
7.91
19.97
TreePiece-300 86.47
89.04
8.09
26.79
7.94
19.83
TreePiece-22 86.51
89.02
8.09
26.57
8.19
20.18
TreePiece-100 86.57
89.05
8.51
27.19
8.65
20.60
TreePiece-O 86.31
88.56
11.57
29.73
12.01
24.02
Table 1: Quality and latency of all models on TOPv2. We train each model with random seeds, and report the averaged EM/EM-S scores and latency test split of TOPv2 dataset. We measure the decoding and overall inference latency all models on both CPU and NVIDIA V100 32 GB GPU, and report the averaged milliseconds all test samples. The number suffix for TreePiece model represents the expansion size when creating TreePiece vocabulary. The best entry for each metric is bolded.
prepare the NAR decoder's input by concatenating the embeddings of the predicted TreePieces and N mask tokens. Then each decoder layer performs self-attention as well as cross attention with en- coder hidden states. Lastly the decoder generates utterance predictions at these N masked positions.
TreePiece-100
TreePiece-200
TreePiece-300
4
TreePiece-400
#steps
TreePiece-500 -500
TreePiece-800
2.3.2 Assemble TreePiece units
TreePiece-2200
NAR
Unlike hetwoordtookeizatiin where original sen- tence can be trivially recovered from subword units via string concatenation, there no canonical way reassemble TreePiece units. To overcome this issue, allow TreePiece units have placehold- ers?, and require that two units can only be joined at a placeholder node. This design provides a unique way to glue a sequence of ordered (e.g. pre/level- ordered) TreePiece units, as shown in Figure 2.
1
2
4
10
12
14
16
18
20
#AR steps
Figure 3: Plot of averaged TreePiece decoding steps against AR decoding steps for skeleton generations.
ments, we the training split train the models, the validation split for earlystopping, model check- pointing, and hyperparameter tuning, and the test split to report the best model's performance.
3 Experiments
3.1 Datasets
We train, validate, and test our approach on the publicly available benchmark TOPv2 (Chen et al., 2020), multi-domain task-oriented seman- tic parsing dataset. The dataset provides train- ing/validation/test split. Throughout our experi-
3.2 Metrics
We evaluate the model performance on metries: Exact Match (EM) respectively Exact Match of Skeleton (EM-S), defined to be the percentage of terances whose logical forms respectively skeletons are correctly predicted (Shrivastava al., 2022).
FFinding all possible placcholder patterns is NP-hard and unnecessary. In Appendix D we provide practical solution.

---

3.3 Baselines
We compare our approach against 2 baselines: AR and NAR. Both baselines are Sgquence-t-ssquueee (seq2seq) that produces subword units of serialized logical forms. Their output space consists of on- tologies (prefixed by left bracket "T"), utterance leaves?, and right bracket "J"
#Intents
1
3
TreePiece
EM
88.10
83.21
69.46
46.31
-600
EM-S
90.01
87.23
72.73
50.00
EM
87.72
80.95
67.60
23.26
NAR
EM-S
89.65
84.81
69.93 24.42
AR baseline admits standard AR structure. has an autoregressive decoder that generates serialized logical forms by producing one token at a time.
Table Comparison on TOPv2 tasks with different level of complexity in terms of number of intents.
NAR baseline adopts mask-p mask-predict (Ghazvininejad et al., 2019) with beam size 1, which predicts the output length first and then generates all tokens in step using non-autooregressive decoder.
Figure 3, we compare the decoding steps needed to generate full skeletons between TreePiece decoder (of 7 different expansion sizes) and AR decoder. The plot illustrates the acceleration effects of our approach, showing that TreePiece with just 200 expansion-size can already reduce the averaged decoding steps by 83.3% compared to AR.
3.4 Experiment setup
For TreePiece models, we experiment with 9 dif- ferent expansion sizes (used Stage 1, Subsection 2.2.1) varying from 0 to 1200. We optimize the hyperparameters for both baselines and TreePiece- 600, and apply the same hyperparameters from TreePiece-600 to all other TreePiece models. We defer the model configurations, training details, hy- perparameter choices Appendix E.
Related work Autoregressive modeling have been used in range of Semantic Parsing works (Tai et al., 2015; Cheng et al.. 2017b; Dong and Lapata. 2018). Especially, the Sequence-to-Tie -ree scheme was adopted by (Dong and Lapata, 2016). To speed up the inference time, Non von-auutorereessvve modeling were introduced to the field of Machine Translation (Gu et al., 2017; Lee et al., 2018; Libovický and Helcl, 2018), and later become pop- ular in Semantic Parsing as well (Ghazvininejad et al., 2019; Babu et al., 2021; Shrivastava et al., 2021). However, to match the quality of AR, extra training stages necessary such Knowledge Distillation from AR models (Gu al., 2017: Lee et al., 2018; Wei al., 2019; Stern al., 2019). On the other hand, (Rubin and Berant, 2020) improves AR decoding's 's efficiency via Bottom- Up Parsing (Cheng et al., 2017a). Our paper takes a completely different path from all previous work by extending the subword tokenization algorithms (Nagata, 1994b; Scott, 2002; Sennrich et al., 2015; Kudo, 2018; Kudo and Richardson, 2018) to trees.
4 Results
4.1 Quality
As shown in Table 1, TreePiece model sees up to 0.7% relative improvements over NAR and less than 0.15% degradation from AR in terms of EM, while achieving the best EM-S score among all approaches, especially showing 0.8% relative im- provement over NAR. We attribute TreePiece's high quality on skeleton predictions to its ability to respect the tree structure of logical forms and gen- erating 100% valid outputs by design so that the model can better focus on utterance-understandd without being distracted by any structure issue.
Table further shows TreePiece's privilege over NAR in handling tasks of higher complex- ity, achieving > 2% improvements for frames with more than intents.
Conclusion
4.2 Latency
This paper proposes novel way to model and speed up Semantic Parsing via tokenizing parse trees into subtrees. We provide thorough elucida- tions and theoretical supports for our technique, and demonstrate significant improvements terms of speed and quality over common AR and NAR baselines on the TOPy2 benchmark.
Table1 indicates that TreePiece makes decoding 6.1%,588 times faster and overall inference 3.0) 2.5 times faster than AR on GPU CPU, with only 5% inference latency growth compared to NAR. In
We represent ufterance leaves in span- pointers (Shrivas- tava et al., 2021) form to simplify the parsing task.

---

Limitations
compositional task-oriented dialog. In North Amer- ican Chapter of the Association for Computational Linguistics.
The proposed TreePiece technique, while evaluated on TOPv2 dataset, is not intrinsically bound to it. Indeed, our approach requires only two conditions on a dataset for applicability:
Jonathan Berant, Andrew K. Chou, Roy Frostig, and Percy Liang. 2013. Semantic parsing on frrehhase from question-answe answer pairs. In Conference on Em- pirical Methods in Natural Language Processing.
offers a closed vocabulary of ontologies;
Xilun Chen, Asish Ghoshal, Yashar Mehdad, Luke Zettlemoyer, and S. Gupta. 2020. Low- Low-resource do- main adaptation for compositional task-oriented se- mantic parsing. Conference on Empirical Methods in Natural Language Processing.
logical forms inherently carry tree structures.
As a matter of fact, TreePiece can seamlessly adapt to a broad range of datasets, including Wik- isQL (Zhong et al., 2017), WEBQUESTIONS (Berant et al., 2013), SequentialQA (lyyer et al., 2017), GEOquery (Davis and Meltzer, 2007), Spi- der (Yu et al., 2018), ATIS (Hemphill et al., 1990), etc. Despite this, we solely focused on showcas- ing its effectiveness in the specific case of "task- oriented natural language understanding based on intent and slots". Additionally, our approach em- ploys standard autoregressive decoding for sub- tree generation, neglecting the exploration of even more efficient decoding techniques. Lastly, our current tokenization algorithm may introduce out- of- of-vocabulary (OOV) tokens; while we proposed effective ways to reduce OOV rates, it however cannot fully eliminate the OOV phenomena.
Jianpeng Cheng, Siva Reddy, Vijay A. Saraswat, and Mirella Lapata. 2017a. Learning an executable neural semantic parser. Computational Linguisties, 45:59-94.
Jiampeng Cheng, Siva Reddy, Vijay A. Saraswat, and Mirella Lapata. 201 Learning structured natural language representations for semantic parsing, ArXiv, abs/ 104.08774
S. Davis and Paul S. Meltzer. 2007. Geoquery: a bridge between the gene expression omnibus (geo) and bio- conductor. Bioinformatics. 23 14:1846-7.
Jacob Devlin, Ming-Was Meig Chang, Kenton Lee, and
Kristina Toutanova. 2019. Bert: Pre-training of deep bidirectional transformers for language understand- ing, ArXiv, abs/ htw//81000444 10.04400
Li Dong and Mirella Lapata. 2016. Language to logical form with neural attention. ArXiv, abs/1601 01280.
Ethics Statement
Li Dong and Mirella Lapata. 2018. Coarse-to-fine de- coding for neural semantic parsing. In Annual Meet- ing of the Association for Computational Linguistics.
Our proposed method presents a novel tokenization operation for tree-like data, yielding substantial practical implications in semantic parsing domains such as natural language understanding, SQL gen- eration, code generation, etc. However, it is crucial to acknowledge that, similar to many other tok- enization algorithms, our approach may introduce biases from the training data into vocabulary and tokenization patterns. Consequently, practitioners needs to be mindful of this when curating the train- ing corpus before utilizing our method.
Philip Gage. 1994. A new algorithm for data compres- sion. The C Users Journal archive, 12:23-38.
Marjan Ghazvininejad. Omer Levy, Yinhan Liu, and Luke Zettlemoyer. 2019. Constant-ting time machine translation with conditional masked language models. ArXiv, abs/1994.09924
Jiatao Gu, James Bradbury, Caiming Xiong, Victor O. K. Li, and Richard Socher. 2017. Non-autoreeressive neural machine translation. ArXiv, abs/1711.022811
S. Gupta, Rushin Shah, Mrinal Mohit, Anuj Kumar, and Mike Lewis. 2018. Semantic parsing for task ori- ented dialog using hierarchical representations. In Conference Empirical Methods in Natural Lan- guage Processing.
References
Armen Aghajanyan, Jean Maillard, Akshat Shrivastava, Keith A. Diedrick, Mike Haeger, Haoran Li, Yashar Mehdad, Ves Stoyanov, Anuj Kumar, Mike Lewis, and S. Gupta. 2020. Conversational semantic pars- ing. In Conference on Empirical Methods in Natural Language Processing.
Charles T. Hemphill. John J. Godfrey, and George R. Doddington. 1990. The atis spoken language systems pilot corpus. In Human Language Technology - The Baltic Perspectiv.
Mohit lyyer, Wen tau Yih, and Ming- Wei Chang 2017. Search-based neural structured learning for sequen- tial question answering. Annual Meeting of the Association for Computational Linguistics.
Arun Babu, Akshat Shrivastava, Armen Aghajanyam, Ahmed Aly, Angela Fan, and Marjan Ghazvinine- jad. 2021. Non-autoregressive semantic parsing for

---

Diederik Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. CoRR, abs/1412.6980.
Rico Sennrich, Barry Haddow, and Alexandra Birch. 2015. Neural machine translation of rare words with subword units. ArXiv, abs/1508. 100.09999..
Taku Kudo. 2018. Subword regularization: Improv- ing neural network translation models with multiple subword candidates. In Anmual Meeting of the Asso- ciation for Computational Linguistics.
Akshat Shrivastava, Pierce 1-Jen Chuang, Arun Babu. Shrey Desai, Abhinav Arora, Alexander Zotov, and Ahmed Aly. 2021. Span pointer networks for non- autoregressive task-oriented semantic parsing, In Conference on Empirical Methods in Natural Lan- guage Processing.
Taku Kudo and John Richardson. 8. Sentencepiece: simple and language independent subword tok- enizer and detokenizer for neural text processing. In Conference on Empirical Methods in Natural Lan- guage Processing.
Akshat Shrivastava, Shrey Desai, Anchit Gupta. Ali Mamdouh Elkahky, Aleksandr Livshits, Alexan- der Zotov, and Ahmed Aly. 2022. Retrieve-and-fl for scenario-basee trientriented semantic parsing. ArXiv, abs/2202.0001..
Jason Lee. Elman Mansimov, and Kyunghyun Cho. 2018. Deterministic non-autoregressive neural se- quence modeling by iterative refinement. In Con- ference on Empirical Methods in Natural Language Processing.
Mitchell Stern, William Chan, Jamie Ryan Kiros, and Jakob Uszkoreit. 2019, Insertion transformer: Flexi- ble sequence generation via insertion operations. International Conference on Machine Learning.
Jindfich Libovický and Jindřích Helel. 2018. End-to- end non-autoreereesivee neural machine translation with connectionist temporal classification. In Pro- ceedings of the 2018 Conference on Empirical Meth- ods in Natural Language Processing, pages 3016- 3021, Brussels, Belgium. Association for Computa- tional Linguistics.
Yixuan Su, Deng Cai, Yan Wang. David Vandyke, Si- mon Baker, Piji Li, and Nigel Collier. 2021. Non- autoregressive text generation with pre-trained lan- guage models. Conference of the European Chap- ter of the Association for Computational Linguistics.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Man- dar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019. Roberta: A robustly optimized bert pretraining ap- proach. ArXiv, 11w/1907.11660
Ilya Sutskever, Oriol Vinyals, and Quoe V. Le, 2014. Sequence sequence learning with neural networks. In NIPS.
Kai Sheng Tai, Richard Sacher, and Christopher D. Man- ning. 2015. Improved semantic representations from tree-structured long short-term memory networks. ArXiv, abs/1503.00077
Xuezhe Ma, Chunting Zhou, Xian Li, Graham Neu- big, and Eduard H. Hovy. 2019. Flowseq: Non- autoregressive conditional sequence generation with generative flow, ArXiv, abs/1909.02448.
Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. ArXiv, abs/1706.00766)
Masaaki Nagata. 1994a. A stochastic japanese mor- phological analyzer using forward-dp backward-at n-best search algorithm. In International Conference on Computational Linguistics.
Andrew J. Viterbi. 1967. Error bounds for convolutional codes an asymptotically optimum decoding algo- rithm. JEEE Trans. Inf. Theory, 13:260-269.
Masaaki Nagata. 1994b. A stochastic Japanese morpho- logical analyzer using forward-DP backward-A* n-best search algorithm. In COLING 1994 Volume I: The 15th International Conference Computational Linguistics, Kyoto, Japan.
Chunqi Wang, Ji Zhang, and Haiqing Chen. 2018. Semi- autoregressive neural machine translation. In Con- ference on Empirical Methods in Natural Language Processing.
Ohad Rubin and Jonathan Berant. 2020. Smbop: Semi- autoregressive bottom-up semantic parsing. In North American Chapter of the Association for Computa- tional Linguistics.
Yiren Wang. Fei Tian, Di He, Tao Qin, ChengXiang Zhai, and Tie-Yan Liu. 2019. Non-autoregressin machine translation with auxiliary regularization. In AAAI Conference on Artificial Intelliencee
Steven Scott. 2002. Bayesian methods for hidden markov models. Journal of the American Statistical Association, 97(457)3337-351
Bingzhen Wei, Mingxuan Wang, Hao Zhou, Junyang Lin, and Xu Sun. 2019. Imitation learning for non- autoregressive neural machine translation. ArXiv. abs/ 92041.
Andrew W. Senior, Georg Heigold, Marc' Aurelio Ran- zato, and Ke Yang. 2013. An empirical study of learning rates in deep neural networks for speech recognition. 2013 IEEE International Conference on Acousties, Speech and Signal Processing, pages 6724-6728.
Yuk Wah Wong. 2005. Learning semantic parsing using statistical machine translation techniques.

---

Tao Yu, Rui Zhang, Kai-Chou Yang, Michihiro Ya- sunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir R. Radev. 2018. Spider: large- scale human-labeled dataset for complex and cross- domain semantic parsing and text-lo-sql task. ArXiv, abs/I 009.0
where X IIs x (0, 11 + {0, 13 is locally smooth almost everywhere (under Lebesgue measure on [0, I)). In other words, for a.c. p E [0,1] 10 and every x E ly there exists a neighborhood Be(p) where x( is constant.
Remark B.1. Assumption (3) is special case of hypothesis B.I, where x( if Ts( and O otherwise.
Luke Zettlemoyer and Michael Collins. 2005. Learning map sentences to logical form: Structured classifi- cation with probabilistic categorial grammars. ArXiv, abs/1207. 207. 1420.
Remark B.2. Without loss of generality, in equa- tions (3) and (4) we replace the symbol "xx with "=", which otherwise complicates all formulae ex- pressions with a non-essential scalar constant.
Victor Zhong, Caiming Xiong, and Richard Socher. Generating structured queries from natural language using reinforcement learning. ArXiv, abs/I 709.001033.
2017. Seq2sql:
Jiawei Zhou and Phillip Keung. 2020. Improving non- autoregressive neural machine translation with mono- lingual data. In Annual Meeting of the Association for Computational Linguistics.
Lemma B.1. Under Hypothesis B.1, Pk+1 is a solution to (1) iff the following holds VT E VV:
Pk+i(T')= ESEr EnggII(T T T*)[S:
Appendix: Vocabulary generation
Σrev Esey Bng [M( r) PM] (5)
This stage resembles the merging operation in Byte Pair Encoding (BPE) (Gage, 1994; Sennrich et al.. 2015). Given training corpus, denote its skeletons by L.. We initialize the TreePiece vocabulary V as the set of ontologies extracted from 9 and Fo as the map between ontologies and their frequencies in y Now repeat the steps below until reaches a pre-determined size:
proof of Theorem 2.6 assuming Lemma B. holds. By following the E-step of Algorithm 2, we express the frequency F²( as
Σ SC rEas(P,)
1 = Σ [)(Ts(Passt) (6)
SEY
Count the frequencies of all adjacent but un- merged TreePiece unit pairs in . Find the most frequent pair p' and its frequency n".
Assumption 3 says that the probability measure PT is supported on the singleton Tp(,,), therefore the following holds for all E V:
Merge p" in every S I that contains p². add p* to V, and update Fo with Folp") = =n"
(TT(p))), r) = Eng (n( r)SS; (7)
Appendix: Proof of Theorem 2.6
For convenience we adopt the following notations.
Now inserting the identity (7) to the right hand side of equation (6) we obtain
Notation B.1. Let be a TreePiece simplex and π = [TI, TK]] be partition where each is TreePiece unit. Define p(T)) IIrc= p(r).
F'(1) Σ
Ens (S::p))
(8)
Notation B.2. Let = [T,,-.. Thl be partition and T be any TreePiece unit. Define n( 7) Ener T In other words, n(T, r) is the num- ber of appearances of in ..
SEF
Next, Inserting (8) to the M-step in Algorithm 2, we have
Now we introduce a general hypothesis and will prove a key lemma under this hypothesis.
Eser [ngg[n(T, ()[S:pp] ΣtCY
Pa+i(t) = - Eser Eng (n(,, T) Pk]
Hypothesis B.1. The joint distribution of skeleton S and partition π satisfies the following rule,
(9)
Invoking Lemma B.1, we see that P&11 is the solu- tion to problem (1), which proves the first conclu- sion in Theorem 2.6.
P(S,T:p) x {
Irre p(T) x(T, if Ils 0 ottherwise,
(4)
Secondly, the monotonicity of log PPS:p,)) can

---

be achieved as follows:
Inserting equation (13) to the following identity:
Σ SEV
log PP5:))
p.a 0,
(14)
Σ
log
P(g, (s(k:
we obtain for each T E that
SE
Σ niT, p(r*)
P(T S: + = 0. (15)
Σ
Pk+1 (Piti))))
SE.Y nElls
SE.
Σ
Pk+ (TS((p))
Note the locally constant assumption in Hypothesis B.I makes the derivative of term II vanishes a.e..
SC
Identity (15) then allows us to solve for p(T*):
Σ SE.
log (S, Px+1)
(10)
p(T*)
1
Σ Σ SEP sllls
n(m,
IP( PP(T) Pp.)
Σ
Ellog P(S,
=
SEV
(16)
2
Σ
Ellog P(lss
Next, using the simplex property ΣrEv and summing up (16) over V, we find
SE.
Σ
(T(()(
SE
ΣrEv ESEr Enengy ((T P( Px
Σ SE.7
log PS,, TP(p)):
(17)
Plugging the above value of X back to (16), we obtain the final expression of p(T*):
Σ SE
log pp):
EsEr Exenl n(T, r*) S
Here, all equalities are consequences of Assump- tion 3, the first incquality follows from the defini- tion of (P(++1)). and the second inequality uses the maximization property of Ps+1:
Erev Eser Exen, n(T,T) P(T S: Pk)
(18)
ESEr B[[(TT, 7 S:
Evev Eser E [n(T, S:P]
Pa+1 = argmax, p
Σ SEY
ny
which is precisely (5). This proves the if direction of the Lemma. Indeed, maximizer p must be critical point of the Lagrange multiplier and sat- isfy (14), therefore identity (18) holds. Conversely, identity (18) for arbitrary 7" fully characterize P, and by the if direction can only be the unique maximum. This proves the opposite direction, and completes the proof of Lemma B.I.
(11)
Thus concludes Theorem 2.6.
To complete the proof of Theorem 2.6 it suffices to prove Lemma B.1.
proof of Lemma B. Consider the following La- grange multiplier of problem (1):
C Appendix: An FFBS algorithm
A(p,A) = Σ
E log (SS Sppk]
We propose Algorithm 3, Forward-Filtering Backward-Sampling (FFBBS (Scott, 2002: Kudo, 2018: Kudo and Richardson, 2018) algorithm un- der the setting of TreePiece. We highlight those lines in Algorithm 3 that differ from Algorithm 1.
SE
(12)
X - 1).
TEV
Plugging (4) into the above equation, we get
Σ Σ
logp(m) Sp)))
Their main distinctions lie in (1) update formula for probabilities, (2) backward strategy.
SE.7 sells
to initialize probability function on the Cartesian (13) product space T T (BOS) as follows:
Before forward, we call
Σ Σ
log ((T p) P( S:pp)
SEF nells
+ +A() Σ p(T) 1)
((1) if E V and t' = BOS token, otherwise.
TCV
(t,
-I+1+ III.

---

During backward, call Sampling randomly sample a previous subtree of with respect to the following distribution:
(I) requires computing Eig (n(T, T)]S; pxl. which now becomes NP-hard. But we can utilize Algo- rithm to obtain an approximate solution. Indeed, if we iteratively rum Algorithm 3 in place of the E-step in Algorithm K times to obtain a partition sequence (p(p) (T(
exp(0 log 9 (t',
(19)
2OET(1) exp(0 ( log (s, Q) PETw FETT
(k) and use the averaged partitions update the frequency Ft, then following similar lines in Appendix B, can prove asymptotic version of Theorem 2.6 under Assumption 20, by showing that the av- eraged frequency over K partitions converges E ( S) Pk. as K tends to infinity, a direct consequence of Law of Large Numbers. We omit the details.
where T(t) (t' E T (L, > 0}. Here smaller leads to more uniform sampling distri- bution among all partitions, while larger 0 tend select the Viterbi partition picked by Algorithm (Kudo, 2018).
Algorithm 3 Forward-Filtering Backward Sam- pling (FFBS) Algorithm
Input: TreePiece vocabulary V. TreePiece sim-
D Appendix
plex p, skeleton S, sampling coefficient O.
Output: Partition (p) and probability P(S:p).
As discussed in Subsection 2.3.2, placeholder structure is necessary for well-defined assembly of TreePiece units. However, adding all possible placeholder patterns vocabulary is impractical for both time and memory. Instead, we shall in- clude only those patterns that most likely to occur. To do so, we tokenize every training skeleton and add the results to the TreePiece vocabulary. As illustrated by the "Tokenize" direction in Figure 2. when node loses child during tokenization, we attach a placeholder to the missing child's position.
T All subtrees of S with the same root.
L f- Lp)( 2 < expo.
< GetIni (Pairrrobs))
dmax < Depth S
for d = 1,2, dmax do // Forward begins
for t E Ta do
for d' = -1,2,
do t' E F.lFite((Tpp (Tar, .)) do
for
A t'At
Q' f 2(V)- 1LEA p(T)
(1) (1) + Q"
Remark D.1. There may exist new placeholder patterns that are Out-Of- Vf-aauuular (OOV) at in- ference time. To mitigate OOV, we apply Algo- rithm 3 (in place of Algorithm 1) to tokenize each training skeleton Ko times. Both Ko and the sam- pling coefficient Op will be specified in Appendix 1.1.2. Intuitively, with larger Ko and smaller l. Algorithm able to generate more abundant placeholder patterns cover as many OOV place- holders as possible.
(t, (t,t))+Q?
P(S:)) - 2(S) // Forward ends feurr + S. TT(p) (p) + 0 // Backward begins while teurr * BOS token, do
peecy Sampling(
leurr:
A fprev At Meur
(p) + (p) UA+, feurr f 4prev
TD( < TT U(teum) Backward ends return T. (p). P(S:))
E Appendix
Algorithm 3 allows us to sample from all possi- ble partitions rather than generating fixed patterns. In practice, this version is used in place of Algo- rithm 1 to reduce the OOV rates; see Appendix D for further discussions.
E.1 Model configurations
E.1.1 Model architectures
Across all of our experiments, we use RoBERTa- base encoder (Liu et al., 2019) and transformer (Vaswani et al., 2017) decoders. For encoder archi- tecture, refer the readers to (Liu al., 2019). All models' decoder have the same multi-head- transformer-layer architecture (embedding dimen- sion 768, 12 heads). Both AR and NAR's decoders have 2 layers. For TreePiece archtecture, TreePiece decoder and Utterance decoder has 1 layer each.
Remark C.1. Let us assume the following holds in place of Assumption (3):
I P(T) E P(S,T;p) & { [Tren
(20) otherwise,
another special case of Hypothesis B.I with x(T.p) = 1. By Lemma B.I, solving problem

---

TreePiece model
NAR baseline
AR baseline
TreePiece decoder
Utterance decoder
Length predictor
Modules
Encoder
Encoder
Decoder
Encoder
Decoder
Learning rates
4 10-6
10-5
10-5
2 10-3
10
10-3
10
10-5
Decay
0.999
0.999
0.9999
coefficients
Table 3: Optimization hyperparameter choices for all models
iintent create reminder [slot person reminded ] [slo todo [ [missing iittent
send message [ slot recipient slot content exact (missing [
intent get event | slot category event slot date time 11111111
Figure Scrializing the skeleton in Figure (LHS) using the "placeholder nest" design.
Note for faimess of comparisons, we let each model have exactly 2 decoder layers in total.
and train for up to 20 epochs until convergence.
E.2.2 Hyperparameter choices
E.1.2 TreePiece vocabulary
Across all experiments, we set the batch size to be 256, and total number of epochs to be 100 with early stopping when validation EM (ref. Subsec- tion 3.2) stops improving. For optimization, we use Adam optimizer (Kingma and Ba, 2014) with weight decay 0.01 and 10-$, In addition, we warm up the learning rate in epochs and then exponentially decay (Senior et al., 2013) at the end of every epoch.
We extract from the TOPv2 dataset 162 ontologies in total, and TOP22 training split training corpus to iteratively run vocabulary generation (ref. Appendix A) 0, 100, 200, 300, 400, 500, 600 times to obtain vocabularies of size 162, 262, 362, 462, 562. 762 respectively. Since we only optimize for TreePiece-600 let us only focus on its vocabulary (of size 762). We then apply the Algorithm 2 with No 30 and 6o 0.01 to train the tokenizer and arrive at vocabulary of 2153 different TreePiece unit patterns with placeholders, Finally, we follow Appendix (with Ko = 10, Gg = 0.15) and ex- pand the TreePiece vocabulary to size 3817. Note the vocabulary obtained this way has less than 0. % OOV rate on test dataset, compared to 0.45% were we not using the sampling trick in Remark D.I.
We also observe that each module favors learn- ing rates with different magnitude, learning among the interval [10-6, 1,10-4) For exponen- tial decay coefficients we optimize them among {0.9, 0.99, 0.999, 0.9999). Table summarizes our final choices of these hyperparameters.
do search separately for each module
E.2 Training details
E.2.1 TreePiece embedding
Within the TreePiece decoder, tie the classifer head's weight to the TreePiece unil embedding ma- trix, and found beneficial to pretrain this weight rather than randomly initializing it. We take inspira- tions from (Shrivastava et al., 2022) and create the pretraining corpus by serializing all skeletons in the training dataset. To let the placcholder information blend into the corpus, we introduce placeholder nest structure and add it the serialized logical forms, as illustrated by Figure 4. Finally, we use the masked language model (MLM) (Devlin et al., 2019) pre-training objective with mask-rate 0.15


Reviews:
[{"review_id": "F1g2B1QCVL", "reviewer": "Reviewer_5cvo", "summary": "", "questions": "* How much is the proposed tree tokenization method restricted to TOPv2-style semantic representations? (which are based on the notion of intents and slots).\n* Can you clarify the difference between AR and TreePiece-0 in Table 1? Is the main difference the utilization of NAR decoding for utterance predictions? There seems to a big speed and accuracy difference between the two.\n* Are there any recommendations on setting the number of expansion size? Table 1 seems to suggest that a larger number always leads to better accuracy and faster speed. If the expansion size continues to grow, does the accuracy start dropping? Figure 3 contains TreePiece-2200, but its performance is not reported in Table 1.", "limitations": "", "rating": 4, "confidence": 2, "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 appreciate the reviewer’s constructive feedback and thoughtful questions. We address each point as follows.\n\n> How much is the proposed tree tokenization method restricted to TOPv2-style semantic representations? (which are based on the notion of intents and slots).\n\nThe proposed TreePiece technique, while tested on TOPv2, is not intrinsically bound to it. Our approach requires **only two** conditions for applicability:\n* The dataset offers a closed vocabulary of ontologies.\n* The logical forms inherently carry a tree structure.\n\nGiven these conditions, TreePiece can seamlessly adapt to a broad range of datasets. The following are some examples:\n\n1. GeoQuery Dataset\n2. Spider Dataset (text to SQL)\n3. ATIS (Air Travel Information System) Dataset\n4. WebQuestions dataset\n5. SQA (Sequential Question Answering) Dataset\n6. WikiSQL Dataset\n\nTo exemplify with the WikiSQL Dataset:\n\n**Utterance**: List books written by authors from the USA that were published after 2000 and have more than 100 pages.\n\n**Logical form:**\n```\n[SELECT: books\n    [AUTHOR_ORIGIN: USA]\n    [CONDITION:\n        [PUBLICATION_DATE: [AFTER: 2000]]\n        [PAGE_COUNT: [GREATER_THAN: 100]]\n    ]\n]\n```\nTreePiece can tokenize the Skeleton (containing 7 ontologies) of this logical form into three TreePiece units:\n```\n1. [SELECT: [AUTHOR_ORIGIN: ][CONDITION: [MISSING][MISSING]]]\n2. [PUBLICATION_DATE: [AFTER:]]\n3. [PAGE_COUNT: [GREATER_THAN: ]]\n```\nThis demonstrates the adaptability of TreePiece beyond just task-Oriented semantic parsing. We thank the reviewer for bringing up this important aspect, and we will clarify this in our next revision.  \n\n> Can you clarify the difference between AR and TreePiece-0 in Table 1? Is the main difference the utilization of NAR decoding for utterance predictions? There seems to a big speed and accuracy difference between the two.\n\nYou've accurately observed that both AR and TreePiece-0 generate one ontology at a time, but there are crucial differences:\n* In AR, logical forms are serialized and tokenized at the word level. Ontologies, utterances, and closing brackets are generated in their serialized order. \n* TreePiece-0, on the other hand, generates all ontologies first (in pre-order) and then completes the utterances using NAR decoding (as you've mentioned).\n\nIn light of these, let's try to understand the performance difference:\n* **Skeleton Accuracy**: AR has higher accuracy due to the intermingling of ontologies and utterances during generation, which, compared to TreePiece-0, provides more contextual hints for ontology prediction. However, as TreePiece vocabulary size grows and decoding steps decrease, this advantage diminishes (as shown in Table 1).\n\n* **Speed**: TreePiece-0 is twice faster than AR not just because of NAR-utterance-decoding but also due to its more efficient ontology generation. For example, AR requires two steps to complete an ontology (\"[IN: CREATE_CALL\" and \"]\"), whereas TreePiece-0 accomplishes this in one step.\n\n> Are there any recommendations on setting the number of expansion size? Table 1 seems to suggest that a larger number always leads to better accuracy and faster speed. If the expansion size continues to grow, does the accuracy start dropping? Figure 3 contains TreePiece-2200, but its performance is not reported in Table 1.\n\nWe have indeed conducted experiments on larger sizes beyond Table 1, including 2200. As the table below shows, accuracy begins to decline once the size exceeds 600. \n\nThe primary culprit is OOV (Out-Of-Vocabulary) issues. When we encounter frames in test datasets whose TreePiece units contain unseen MISSING placeholder patterns, accuracy is negatively impacted. This is elaborated on in Limitation Section, Section 2.3.2, and Appendix F.\n \nTheoretically, a larger vocabulary means fewer steps to generate a skeleton, leading to higher overall accuracy. However, increasing vocabulary size means more MISSING patterns must be left out (see Footnote 1), which escalates OOV rates, impacting accuracy negatively. There's a balance point where accuracy is optimized. In our experience, this sweet spot lies around 600. \n\nIn general, for any given dataset, it is necessary to conduct comprehensive experiments across a range of vocabulary sizes to identify the optimal setting. Nonetheless, this optimal size has an upper limit and won't increase indefinitely.\n\nWe will clarify this for better understanding.\n\n| |TreePiece-600 | TreePiece-700 | TreePiece-800 | TreePiece-1200 | TreePiece-2200 | \n|---|---|---|---|---|---|\n| EM |**$86.86$** | $86.79$| $86.73$| $86.51$| $86.44$ | \n| EM-S |**$89.26$** | $89.20$| $89.13$| $89.05$| $88.99$ |\n| OOV (%) |**$0.12$** | $0.18$| $0.26$| $0.34$| $0.40$ |\n\n> Figure 3 is blocking some texts on the left column on page 3.\n\nThank you for bringing this layout issue to our attention. We will rectify this in the revised manuscript and ensure that all text is visible.\n\n> The NAR utterance decoder does not seem to be fully described in the paper.\n\nWe appreciate your observation. To clarify, our utterance NAR decoding mechanism directly builds upon the standard NAR baseline, as detailed in reference [1]. The decoder consists of multi-layer Transformer architecture and operates as follows:\nAfter generating Skeleton, the requisite number of utterances are determined, denoted as $N$ (refer to lines 112-116). The NAR decoder's input is formed by concatenating the embeddings of the predicted TreePieces and $N$ mask tokens. Each decoder layer performs self-attention as well as cross attention with encoder hidden states. Lastly the decoder generates utterance predictions at these $N$ masked positions.\n\nWe hope this clarifies any ambiguity and will incorporate this expanded explanation in the revised paper for comprehensiveness.\n\n[1] Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. 2019. Constant-time machine translation with conditional masked language models.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* This paper makes a focused contribution on reducing the number of decoding steps required through tree tokenization. The method appears to be novel and sound. The idea of decoding one subtree at a time instead of one token at a time is quite intuitive and likely interesting many researchers in the field of semantic parsing.\n* The paper provides empirical evidence that the proposed tree tokenization method support much faster inference comparable to non-autoregressive decoder, while maintaining similar accuracies as the baseline autoregressive decoder.", "reasons_to_reject": "* The proposed tree tokenization method is only tested on a single semantic parsing benchmark TOPv2 and its corresponding semantic representation. It is not clear whether the method is applicable to other semantic parsing tasks and representations.\n* A lot of relevant technical details in this paper is put in the appendix (e.g., the main algorithms), making the main paper somewhat less self-contained.\n\nEdit:\nAuthors have addressed the first point in their responses (though only theoretically and without empirical evidence).", "questions_to_authors": "* How much is the proposed tree tokenization method restricted to TOPv2-style semantic representations? (which are based on the notion of intents and slots).\n* Can you clarify the difference between AR and TreePiece-0 in Table 1? Is the main difference the utilization of NAR decoding for utterance predictions? There seems to a big speed and accuracy difference between the two.\n* Are there any recommendations on setting the number of expansion size? Table 1 seems to suggest that a larger number always leads to better accuracy and faster speed. If the expansion size continues to grow, does the accuracy start dropping? Figure 3 contains TreePiece-2200, but its performance is not reported in Table 1.", "paper_topic_and_main_contributions": "This paper proposes a tree tokenization method that allows autoregressive models to generate one subtree at a time instead of one token at a time. This allows significant speed up during model inference, since the output sequences become much shorter with the proposed tree tokenization.\n\nThe authors conducted experiments on TOPv2, a semantic parsing benchmark, and reported much faster decoding time (more than 6x faster than a baseline autoregressive decoder) which is comparable to a non-autoregressive decoder in terms of decoding speed, while maintaining similar levels of accuracy to the autoregressive decoder baseline.", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "Figure 3 is blocking some texts on the left column on page 3.\n\nThe NAR utterance decoder does not seem to be fully described in the paper."}, "extra_text": {}}, {"review_id": "nWqec6N5d8", "reviewer": "Reviewer_7MJZ", "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": "Thank you for your feedback. \n\n> The improvement in performance and speed is not substantial. When compared to non-autoregressive (NAR) methods, the system exhibits similar performance but operates at a slower pace\n\nWe would like to clarify a few points regarding the perceived performance improvement over NAR:\n1. The task distribution in TOPv2 is skewed towards simplicity: about 85% of samples are **easy tasks** with only 1 intent, an average of 2.65 ontologies, and a tree-depth of at most 3. As models are trained extensively, performance on these tasks tends to saturate, leading to minimal performance differences between methods.\n\n\n2. The strength of our TreePiece tokenization lies in handling tasks of higher complexity. We provide two tables below to illustrate this: the first segments test samples by the number of intents, and the second by number of ontologies. Notably, while the performance gap is small for simpler tasks, it widens considerably for complex ones, already reaching improvements of 2% for 2-intent frames and 4% for 6-ontology frames.\n\n| #Intents| |1 | 2 | 3 | 4 | 5 | \n|---|---|---|---|---|---|---|\n| TreePiece-600 | EM |$88.10$ | $83.21$| $69.46$| $46.51$| $0.0$ | \n| | EM-S |$90.01$ | $87.23$| $72.73$| $50.00$| $0.0$ | \n| NAR | EM  |$87.72$ | $80.95$| $67.60$| $23.26$| $0.0$ |\n| | EM-S| $89.65$ | $84.81$| $69.93$| $24.42$| $0.0$ | \n\n| #Ontologies| |1 | 2 | 3 | 4 | 5 | 6|7|8|9|10|11|12|\n|---|---|---|---|---|---|---|---|---|---|---|---|---|---|\n| TP | EM |$85.72$ | $90.37$| $88.27$| $86.36$|$80.33$| $83.22$ | $77.04$ | $68.47$ | $58.64$ | $47.73$ | $48.89$ | $41.47$ | \n| | EM-S |$85.72$ | $91.71$| $90.31$| $89.54$| $84.31$ | $76.86$ | $82.55$ | $74.63$ | $65.45$ | $50.00$ | $51.11$ | $50.00$ | \n| NAR | EM  |$85.51$ | $89.89$| $87.82$| $85.01$| $78.62$ |$79.26$ | $73.25$ | $66.75$ | $56.16$ | $43.18$ | $26.67$ | $0.0$ | \n| | EM-S| $85.51$ | $91.37$| $90.00$| $88.68$| $82.96$ | $82.89$ | $78.65$ | $69.95$ | $63.35$ | $46.59$ | $31.11$ | $0.0$ | \n\n\n3. Historical improvements on TOPv2 in existing literature are of similar scale, such as [1] with an improvement of ~1.2% and [2] less than 0.25%. The difference between models like RoBERTa base and RoBERTa large is often less than 0.4%. Given this context, our improvements of 0.67% on frames and 0.7% on skeletons are significant.\n\nIn light of the above, we believe our method leads to substantial improvements and offers meaningful advantages, especially in handling complex tasks.\n\nWe thank the reviewer for the observation. In upcoming versions of our paper, we'll articulate the complexity skew of the TOPv2 dataset more clearly, elaborate on our model's proficiency in addressing complex tasks, and incorporate the stratified results to better support our main claims on performance improvements.\n\n[1] Akshat Shrivastava, Pierce Chuang, Arun Babu, Shrey Desai, Abhinav Arora, Alexander Zotov, Ahmed Aly, Span Pointer Networks for Non-Autoregressive Task-Oriented Semantic Parsing\n\n[2] Akshat Shrivastava, Shrey Desai, Anchit Gupta, Ali Elkahky, Aleksandr Livshits, Alexander Zotov, Ahmed Aly, Retrieve-and-Fill for Scenario-based Task-Oriented Semantic 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 novel approach (TreePiece) addresses a significant problem in semantic parsing: the slow speed of autoregressive models. By predicting multiple sub-trees simultaneously, TreePiece greatly reduces the prediction steps and, consequently, the computation time.", "reasons_to_reject": "The improvement in performance and speed is not substantial. When compared to non-autoregressive (NAR) methods, the system exhibits similar performance but operates at a slower pace", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper presents a novel Tree Tokenization technique called \"TreePiece\" for semantic parsing. The traditional approach uses autoregressive (AR) encoder-decoder neural networks, which can be slow due to their sequential prediction process. The authors propose TreePiece as a solution to accelerate this process. The main contribution of the paper is to use the TreePiece technique, which tokenizes a parse tree into multiple sub-trees and predicts them simultaneously. This method reduces the number of prediction steps and, thus, accelerates the semantic parsing process.", "excitement": 2, "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": "VbEe7AGZqH", "reviewer": "Reviewer_JKxP", "summary": "", "questions": "- Do you have statistics about the average length before and after applying the TreePiece method?\n- What do you think of the reasons that NAR methods perform worse than AR methods in semantic parsing tasks?", "limitations": "", "rating": 3, "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 constructive feedback. We address each point as follows:\n\n> Content needed for understanding the paper heavily relies on the one from appendix.\n\nWe recognize the inconvenience of referring to the appendix for core content. To improve clarity, we'll reorganize the manuscript, integrating essential appendix materials into the main text.\n\nTo answer your questions:\n\n> Do you have statistics about the average length before and after applying the TreePiece method?\n\nThe following table compared average lengths (measured in generation steps) before and after applying TreePiece (i.e., AR vs. TreePiece-600) for both logical forms and skeletons. \n\n| | |Avg. lengths | \n|---|---|---|\n| TreePiece-600 | Logical form  |$2.2$ | \n| | Skeleton| $1.2$ | \n| AR | Logical form |$9.6$ | \n| | Skeleton |$6.2$ | \n\nAdditionally, to showcase TreePiece's efficacy in reducing lengths, we include two more tables below. The first table segments test samples by the number of intents, and the second by number of ontologies, both presenting average lengths within each category.\n\n| #Intents| |1 | 2 | 3 | 4 | 5 | \n|---|---|---|---|---|---|---|\n| TreePiece-600 | Logical form  |$2.1$ | $2.4$| $3.4$| $4.2$| $5.0$ |\n| | Skeleton| $1.1$ | $1.4$| $2.4$| $3.2$| $4.0$ | \n| AR | Logical form |$8.4$ | $15.0$| $21.7$| $29.8$| $37.0$ | \n| | Skeleton |$5.2$ | $10.5$| $15.9$| $21.9$| $27.5$ | \n\n| #Ontologies| |1 | 2 | 3 | 4 | 5 | 6|7|8|9|10|11|12|\n|---|---|---|---|---|---|---|---|---|---|---|---|---|---|\n| TreePiece-600 | Logical form  |$2.0$ | $2.0$| $2.2$| $2.2$| $2.4$ |$2.5$ | $2.7$ | $3.2$ | $3.6$ | $4.1$ | $4.1$ | $4.1$ | \n| | Skeleton| $1.0$ | $1.0$| $1.2$| $1.4$| $1.5$ | $1.7$ | $2.2$ | $2.6$ | $3.1$ | $3.1$ | $3.1$ | $3.1$ | \n| AR | Logical form |$2.0$ | $6.0$| $9.9$| $13.0$|$15.0$| $18.2$ | $21.0$ | $23.0$ | $26.2$ | $29.2$ | $30.9$ | $34.3$ | \n| | Skeleton |$2.0$ | $4.0$| $6.0$| $8.0$| $10.0$ | $12.0$ | $14.0$ | $16.0$ | $18.0$ | $20.0$ | $22.0$ | $24.0$ | \n\n> What do you think of the reasons that NAR methods perform worse than AR methods in semantic parsing tasks?\n\nOne of the most significant strengths of AR modeling is its ability to capture temporal dependencies by allowing each token to rely on the entire past contexts. This is essential for NLP tasks because word meanings can be deeply influenced by their preceding context. In contrast, **NAR loses this chain of dependencies**, making predictions without full sequence's context, leading to higher error rates. Another crucial factor is Length Prediction: NAR needs to predict output length, which, if incorrect, can lead to completely wrong outputs.", "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 terms and algorithms are thoroughly defined\n- Advantages seem to be promising", "reasons_to_reject": "- Content needed for understanding the paper heavily relies on the one from appendix.", "questions_to_authors": "- Do you have statistics about the average length before and after applying the TreePiece method?\n- What do you think of the reasons that NAR methods perform worse than AR methods in semantic parsing tasks?", "paper_topic_and_main_contributions": "This paper is about improving inference speed of semantic parsing models based on autoregressive (AR) encoder-decoder setting.\nDue to their autoregressive property, AR models tend to have slower inference speed compared to non-AR models.\nAt the same time, non-AR approaches perform considerably worse than AR approaches.\nTo address this issue, the authors propose to tokenize parse trees into larger units, called TreePiece units. As a result, the average length of each logical form becomes shorter and the inference speed could be made faster.\nThe core part of the work comes from obtaining high-quality TreePiece vocabulary (which is a minimal vocabulary of a Treepiece tokenizer) and TreePiece simplex (probability assignment for each token in TreePiece vocabulary).\nInspired by Byte Pair Encoding, TreePiece vocabulary is obtained by merging high-frequency units, and the simplex is obtained from frequencies of those.\nFrom experiments, the authors empirically prove that the method accelerates the decoding and inference time needed for AR models both in CPU and GPU settings, while maintaining performance degradation minimal.", "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": {}}]

Author rebuttal:

Meta-review: This article proposes a tree tokenization method that provides a substantial speed up of autoregressive semantic parsing strategies. The method provides a way to do faster autoregressive semantic parsing with comparable accuracy, with comparable speed and higher accuracy compared to non-autoregressive methods.

Reviewers agree that some substantial information is contained in the appendix, but argue that this can be resolved within the extra page for a final revision. One reviewer was a bit more negative than the others, based on a claim that has been verified to be false after inspecting the paper. Since no response from said reviewer was received, this has been taken into account in the recommendation.
Decision: Accept-Findings