Laziness Is a Virtue When It Comes to Compositionality in Neural Semantic Parsing (2023)

Abstract: Nearly all general-purpose neural semantic parsers generate logical forms in a strictly top-down autoregressive fashion. Though such systems have achieved impressive results across a variety of datasets and domains, recent works have called into question whether they are ultimately limited in their ability to compositionally generalize. In this work, we approach semantic parsing from, quite literally, the opposite direction; that is, we introduce a neural semantic parsing generation method that constructs logical forms from the bottom up, beginning from the logical form’s leaves. The system we introduce is lazy in that it incrementally builds up a set of potential semantic parses, but only expands and processes the most promising candidate parses at each generation step. Such a parsimonious expansion scheme allows the system to maintain an arbitrarily large set of parse hypotheses that are never realized and thus incur minimal computational overhead. We evaluate our approach on compositional generalization; specifically, on the challenging CFQ dataset and two other Text-to-SQL datasets where we show that our novel, bottom-up semantic parsing technique outperforms general-purpose semantic parsers while also being competitive with semantic parsers that have been tailored to each task.

## introduction compositionality is inherent to natural language, with the meaning of complex text or speech understood through the composition of constituent words and phrases @xcite . for instance, having observed the usage of phrases like "edited by" and "directed by" in isolation, a human would be able to easily understand the question "was toy story edited by and directed by john lasseter?". the ability to take individual components and combine them together in novel ways is known as compositional generalization, and is a key feature of human intelligence that has been shown to play a significant role in why humans are so efficient at learning @xcite . compositional generalization has been identified as a major point of weakness in neural methods for semantic parsing @xcite . accordingly, this deficiency has been taken up as a challenge by the machine learning community, leading to a slew of methods @xcite @xcite and datasets @xcite targeted towards compositional generalization. however, while there has been progress in determining factors that allow systems to compositionally generalize @xcite , there yet remains gaps in our understanding as to why these neural models fail. in this paper, we posit that the failure of traditional neural semantic parsers to compositionally generalize is in part due to how they build logical forms. most commonly, neural semantic parsers treat parsing as an encoder-decoder problem, where the decoder generates logical forms from the top down in an autoregressive fashion @xcite @xcite @xcite . that is, these systems output a linearization of the target logical form's abstract syntax tree, beginning from the root of the tree, where the generation of each token is conditioned on both the input text as well as the entire sequence of previously generated tokens. such an entirely autoregressive decoding scheme, wherein the production of each new token is conditioned on all previously generated tokens, could result in models that assume invalid dependencies to exist between tokens and thus overfit to their training data (as observed in @xcite ). we hypothesize that this overfitting problem would lessen the ability of these models to generalize to unseen compositions. here we introduce an alternative decoding approach that eschews the top-down generation paradigm, and instead uses a bottom-up mechanism that builds upwards by combining entities and subexpressions together to form larger subexpressions (figure 1 demonstrates this distinction). unlike top-down approaches, our decoder generates logical forms by conditioning on only the relevant subexpressions from the overall graph, hence improving compositional generalizability. contributions: (a) we introduce a novel, bottom-up semantic parsing decoder that achieves strong results, specifically with respect to compositional generalization. (b) we evaluate our approach on cfq @xcite , three text-to-sql @xcite @xcite , and find that it outperforms general-purpose semantic parsers while also being competitive with comparable neural parsers that have been designed for each task. (c) we demonstrate the flexibility of our architecture by testing our approach with multiple encoders, showing that our architecture almost always leads to a significant performance improvement. (d) we show how the bottom-up paradigm can result in a combinatorial explosion in the number of subexpressions created at each decoding step and propose a lazy evaluation scheme that mitigates this by selectively expanding the logical form in a way that minimizes computational overhead. ## representing logical forms our parser is intended to be task-agnostic, with as few as possible assumptions made regarding the particular formalism (e.g., sql, sparql, etc.) a logical form may instantiate. we assume only that we have access to a vocabulary v that defines the set of all symbols a logical form could be constructed from (with no restrictions imposed as to the label or arity of any particular symbol) and that the logical form is given as an s-expression. s-expressions are a representation formalism that expresses trees as nested lists (e.g., (count @xmath00)) as a query for the question "how many rivers are there?"). their use dates back to the earliest days of artificial intelligence research @xcite as the main unit of processing of the lisp programming language @xcite . in this work, their main purpose is to simplify the structure of logical forms into binary trees. importantly, the transformation of logical forms into s-expressions requires no knowledge beyond the syntax of the target formalism. traditionally, logical forms are generated as trees; however, we instead represent them as directed acyclic graphs (dags). this is a logically equivalent representation that is created by collapsing all identical subtrees into a single subgraph that maintains connections to each of the original parent nodes. figure 2a provides an example of how an s-expression would initially be converted into a tree representation, while figure 2b shows how two overlapping trees would be merged into a single dag form. within a graph all nodes will either have 1) one argument and a label drawn from the vocabulary of symbols v or 2) two arguments and connect an incomplete list (its left argument) with (a) internal conversion of the logical form (count @xmath10)) into a tree-based s-expression for the question "how many rivers are there?" (b) dag representation of an s-expression where identical subtrees have been mapped to the same nodes a complete list (its right argument). the nodes with two arguments will always use a special pointer symbol "•" as their label. as the final preprocessing step, each logical form is wrapped in a special root sexpression. for instance, the logical form (count @xmath20)) would become (root (count @xmath30))). this step provides a signal to the model to stop generating new extensions to the logical form. during decoding, only those s-expressions that begin with a root token may be returned to the user. ## model given a question q, our method is tasked with producing a graph representation g of a logical form using symbols drawn from a vocabulary v . at the highest level, our approach follows the traditional encoder-decoder paradigm. it first parses the input with a neural encoder (e.g., lstm @xcite ) to produce real-valued vector representations for each word in q. those representations are then passed to a neural decoder, which iteratively takes decoding actions to generate g. our approach is agnostic to the choice of encoder, and thus in the following sections we will describe only the decoding process. an important desideratum of this work was architectural simplicity. thus, when using a pretrained large language model as the base to our approach, (e.g., t5 @xcite ), the model was left largely as is. none of the modifications described in the following sections involve changes to the internal parameters or architecture of the neural model itself (i.e., all additions are kept to the output layer). consequently, when our approach is instantiated with a pretrained language model, that model is applied entirety off-the-shelf. ## experiments in our experiments, we aimed to answer the following questions: 1) is bottom-up a more effective decoding paradigm than top-down with respect to compositional generalization and 2) how well does our approach generalize to different domains and formalisms. to answer these questions, we evaluated our approach on several datasets: 1) cfq @xcite , 2) the sql versions of geoquery (zelle and mooney, 1996), atis @xcite , and scholar @xcite , each of which were curated by @xcite , and 3) the version of geoquery (zelle and mooney, 1996) used by @xcite which maps questions to a variant of typed lambda calculus @xcite . to save space, we provide all hyperparameters used for our experiments in the appendix. our main experiments investigating compositional generalization were performed on the cfq and text-to-sql datasets. in cfq, the distribution of train and test data in each split is designed to exhibit maximum compound divergence (mcd) @xcite . in the mcd setting, data is comprised of a fixed set of atoms, i.e., the primitive elements to a question. but while each atom is observed in training, the compositions of atoms between train and test sets will vary significantly (an example of a cfq question is provided in figure 7 ). in the text-to-sql datasets, the train and test sets are constructed by using separate template splits @xcite , where the train and test sets have questions involving different sql query templates. ## related work while the overall parsing approach of @xcite ) is quite different from ours (as they propose a transition-based semantic parser), several aspects of our work were inspired from their ideas. for instance, as mentioned in section 3.3, they proposed the use of two types of decoding actions to expand the target graph. bottom-up neural semantic parsers are a relatively recent development. most related to our work is that of @xcite , which introduced a bottom-up system that achieved near state-of-the-art results on the spider dataset @xcite while being significantly more computationally efficient than its top-down, autoregressive competitors. there are three significant differences between their approach and ours. first, they generate trees rather than dags and thus assume a many-to-one correspondence between input spans in the question and tokens in the logical form (which does not hold for datasets like cfq). second, they use an eager evaluation scheme (i.e., nodes are generated at each decoding step and not actions), and thus enforce a beam-size hyperparameter k that must be defined a priori and places a hard limit on the number of subtrees that can be considered at a given time. third, they use a highly customized decoder which limits how tightly integrated their approach can be with off-the-shelf language models. in contrast, when using a pretrained large language model as the base to our approach, we reuse the entirety of the language model as is to instantiate our model. another similar work is @xcite , which introduced a method that learned to predict span trees over the input question that could be composed together to build complete logical forms. their method achieves strong performance on the geoquery sql dataset @xcite ; however, similar to @xcite , their approach differs from ours in that they assume a one-to-one correspondence between disjoint spans of the question and disjoint subtrees of the logical form. further, their method can only handle inputs whose parse falls into a restricted class of non-projective trees, where the authors note that extending their method to all classes of non-projective trees would prohibitively increase the time complexity of their parser. such assumptions make it unclear how it would directly apply to a more complex dataset like cfq. there are several works targeted specifically towards compositional generalization @xcite @xcite @xcite . though these systems have proven to be quite effective on compositional generalization datasets, they make significant task-specific assumptions that limit how they might be applied more broadly. ## limitations the main limitation to our work lies in the handling of unordered n-ary relations. we hypothesize that the bottom-up paradigm performs best when there is one unambiguous logical form to generate for a particular question. while this is quite often true for semantic parsing, in our experience, unordered n-ary relations (e.g., where) can quickly cause this not to be the case. with such relations, there tends to be a large number of correct logical forms for a particular question. in these situations, having so many candidate logical forms can cause significant issues in terms of runtime. a second limitation of our work is that it assumes the logical form will be given as a graph. thus, there is an annotation burden on the users of this system that would not be present in systems that treat semantic parsing as a text-to-text problem (e.g., fine-tuned large language models). ## conclusions in this work, we introduced a novel, bottom-up decoding scheme that semi-autoregressively constructs logical forms in a way that facilitates compositional generalization. key to our method was a lazy generation process designed to address the computational efficiency issues inherent to bottomup parsing. we demonstrated our approach on five different datasets covering three logical formalisms and found that our approach was strongly competitive with neural models tailored to each task.