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? figure 1 : an overview of the decoding procedure of smbop. z t is is the beam at step t, z t is the contextualized beam after cross-attention, f t+1 is the frontier (κ, σ, ≥ are logical operations applied on trees, as explained below), f t+1 is the pruned frontier, and z t+1 is the new beam. at the top we see the new trees created in this step. for @xmath2, the beam contains the predicted schema constants and db values. 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. 2 2 background problem definition we focus in this work on text-to-sql semantic parsing. given a training set {(x (i) , y (i) , s (i) )} n @xmath3, where x (i) is an utterance, y (i) is its translation to a sql query, and s (i) is the schema of the target database (db), our goal is to learn a model that maps new question-schema pairs 2 our code is available at https://github.com/ ohadrubin/smbop (x, s) to the correct sql query y. a db schema s includes : (a) a set of tables, (b) a set of columns for each table, and (c) a set of foreign key-primary key column pairs describing relations between table columns. schema tables and columns are termed schema constants, and denoted by s. rat-sql encoder this work is focused on decoding, and thus we implement the state-of-the-art rat-sql encoder @xcite , on top of grappa @xcite , a pre-trained encoder for semantic parsing. we now briefly review this encoder for completeness. the rat-sql encoder is based on two main ideas. first, it provides a joint contextualized representation of the utterance and schema. specifically, the utterance x is concatenated to a linearized form of the schema s, and they are passed through a stack of transformer @xcite layers. then, tokens that correspond to a single schema constant are aggregated, which results in a final contextualized representation (x, s) = (x 1 , . . . , x |x| , s 1 , . . . , s |s| ), where s i is a vector representing a single schema constant. this contextualization of x and s leads to better representation and alignment between the utterance and schema. second, rat-sql uses relational-aware self-attention @xcite to encode the structure of the schema and other prior knowledge on relations between encoded tokens. specifically, given a sequence of token representations (u 1 , . . . , u |u| ), relational-aware self-attention computes a scalar similarity score between pairs of token representa- overall, rat-sql jointly encodes the utterance, schema, the structure of the schema and alignments between the utterance and schema, and leads to state-of-the-art results in text-to-sql parsing. rat-sql layers are typically stacked on top of a pre-trained language model, such as bert @xcite . in this work, we use grappa @xcite , a recent pre-trained model that has obtained state-of-the-art results in text-to-sql parsing. grappa is based on roberta @xcite , but is further fine-tuned on synthetically generated utterance-query pairs using an objective for aligning the utterance and query. autoregressive top-down decoding the prevailing method for decoding in semantic parsing has been grammar-based autoregressive top-down decoding @xcite @xcite , which guarantees decoding of syntactically valid programs. specifically, the target program is represented as an abstract syntax tree under the grammar of the formal language, and linearized to a sequence of rules (or actions) using a top-down depth-first traversal. once the program is represented as a sequence, it can be decoded using a standard sequence-tosequence model with encoder attention @xcite , often combined with beam search. we refer the reader to the aforementioned papers for further details on grammar-based decoding. algorithm 1: smbop 1 input: utterance x, schema s 2 x, s ← encoderat(x, s) 3 z0 ← top-k schema constants and db values 4 for t ← 0 . . . t -1 do 5 z t ← attention(zt, x, x) 6 ft+1 ← score-frontier(z t ) 7 f t+1 ← arg max k (ft+1) 8 zt+1 ← represent-beam(zt, f t+1 ) 9 return arg max z (zt ) ## 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 @xmath4. 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.