S m B o P : Semi-autoregressive Bottom-up Semantic Parsing (2021)

Abstract: The de-facto standard decoding method for semantic parsing in recent years has been to autoregressively decode the abstract syntax tree of the target program using a top-down depth-first traversal. In this work, we propose an alternative approach: a Semi-autoregressive Bottom-up Parser (SmBoP) that constructs at decoding step t the top-K sub-trees of height ≤ t. Our parser enjoys several benefits compared to top-down autoregressive parsing. From an efficiency perspective, bottom-up parsing allows to decode all sub-trees of a certain height in parallel, leading to logarithmic runtime complexity rather than linear. From a modeling perspective, a bottom-up parser learns representations for meaningful semantic sub-programs at each step, rather than for semantically-vacuous partial trees. We apply SmBoP on Spider, a challenging zero-shot semantic parsing benchmark, and show that SmBoP leads to a 2.2x speed-up in decoding time and a ~5x speed-up in training time, compared to a semantic parser that uses autoregressive decoding. SmBoP obtains 71.1 denotation accuracy on Spider, establishing a new state-of-the-art, and 69.5 exact match, comparable to the 69.6 exact match of the autoregressive RAT-SQL+Grappa.

## introduction semantic parsing, the task of mapping natural language utterances into programs @xcite @xcite , has converged in recent years on a standard encoder-decoder architecture. recently, meaningful advances emerged on the encoder side, including developments in transformer-based architectures @xcite and new pretraining techniques @xcite @xcite @xcite . conversely, the decoder has remained roughly constant for years, where the abstract syntax tree of the target program is autoregressively decoded in a top-down manner @xcite @xcite . bottom-up decoding in semantic parsing has received little attention @xcite . in this work, we propose a bottom-up semantic parser, and demonstrate that equipped with recent developments in transformer-based @xcite architectures, it offers several advantages. from an efficiency perspective, bottom-up parsing can naturally be done semiautoregressively: at each decoding step t, the parser generates in parallel the top-k program sub-trees of @xmath0. this leads to runtime complexity that is logarithmic in the tree size, rather than linear, contributing to the rocketing interest in efficient and greener artificial intelligence technologies @xcite . from a modeling perspective, neural bottom-up parsing provides learned representations for meaningful (and executable) sub-programs, which are sub-trees computed during the search procedure, in contrast to top-down parsing, where hidden states represent partial trees without clear semantics. figure 1 illustrates a single decoding step of our parser. given a beam z t with @xmath1, we use cross-attention to contextualize the trees with information from the input question (orange). then, we score the frontier, that is, the set of all trees of height t + 1 that can be constructed using a grammar from the current beam, and the top-k trees are kept (purple). last, a representation for each of the new k trees is generated and placed in the new beam z t+1 . after t decoding steps, the parser returns the highest-scoring tree in z t that corresponds to a full program. because we have gold trees at training time, the entire model is trained jointly using maximum likelihood. what are the names of actors over 60? represent-beam autoregressive bottom-up semantic parser), on spi-der @xcite , a challenging zero-shot text-to-sql dataset. we implement the rat-sql+grappa encoder @xcite , currently the best model on spider, and replace the autoregressive decoder with the semi-autoregressive sm-bop. smbop obtains an exact match accuracy of 69.5, comparable to the autoregressive rat-sql+grappa at 69.6 exact match, and to current state-of-the-art at 69.8 exact match @xcite , which applies additional pretraining. moreover, smbop substantially improves state-of-theart in denotation accuracy, improving performance from 68.3 → 71.1. importantly, compared to autoregressive semantic parsing , we observe an average speed-up of 2.2x in decoding time, where for long sql queries, speed-up is between 5x-6x, and a training speed-up of ∼5x. 3 ## the smbop parser we first provide a high-level overview of smbop (see algorithm 1 and figure 1 ). as explained in §2, we encode the utterance and schema with a rat-sql encoder. we initialize the beam (line 3) with the k highest scoring trees of height 0, which include either schema constants or db values. all trees are scored independently and in parallel, in a procedure formally defined in §3.3. next, we start the search procedure. at every step t, attention is used to contextualize the trees with information from input question representation (line 5). this representation is used to score every tree on the frontier: the set of sub-trees of @xmath2. after choosing the top-k trees for step t+1, we compute a new representation for them (line 8). finally, we return the top-scoring tree from the final decoding step, t . steps in our model operate on tree representations independently, and thus each step is efficiently parallelized. smbop resembles beam search as in each step it holds the top-k trees of a fixed height. it is also related to (pruned) chart parsing, since trees at step t + 1 are computed from trees that were found at step t. this is unlike sequence-to-sequence models where items on the beam are competing hypotheses without any interaction. we now provide the details of our parser. first, we describe the formal language ( §3.1), then we provide precise details of our model architecture ( §3.2) including beam initialization ( §3.3, we describe the training procedure ( §3.4), and last, we discuss the properties of smbop compared to prior work ( §3.5). ## experimental evaluation we conduct our experimental evaluation on spider @xcite , a challenging large-scale dataset for text-to-sql parsing. spider has become a common benchmark for evaluating semantic parsers because it includes complex sql queries and a realistic zero-shot setup, where schemas at test time are different from training time. ## conclusions in this work we present the first semiautoregressive bottom-up semantic parser that enjoys logarithmic theoretical runtime, and show that it leads to a 2.2x speed-up in decoding and ∼5x faster taining, while maintaining state-of-the-art performance. our work shows that bottom-up parsing, where the model learns representations for semantically meaningful sub-trees is a promising research direction, that can contribute in the future to setups such as contextual semantic parsing, where sub-trees often repeat, and can enjoy the benefits of execution at training time. future work can also leverage work on learning tree representations (shiv and quirk, 2019) to further improve parser performance.