SmBoP: Semi-autoregressive Bottom-up Semantic Parsing

By Ohad Rubin, Jonathan Berant. 2020

193 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Information Extraction

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Extraction

Citations in the corpus

Jigsaw: Large Language Models meet Program Synthesis (2021, background): “Spider [5, 45] is a text-to-SQL competition where many tools compete [38, 42].”
Value-Agnostic Conversational Semantic Parsing (2021, methodology): “Finally, bottom-up models with similarities to ours include SMBOP (Rubin and Berant, 2020) and BUSTLE (Odena et al., 2020).”
RESDSQL: Decoupling Schema Linking and Skeleton Parsing for Text-to-SQL (2023, methodology): “Some works also employ PLM encoders to initialize the representation of nodes on the graph (Cao et al. 2021; Wang et al. 2020a; Rubin and Berant 2021).”
Unlocking Compositional Generalization in Pre-trained Models Using Intermediate Representations (2021, methodology): “SQL Previous work has proposed various IRs for SQL, such as SemQL (Guo et al., 2019), SQL UF (Suhr et al., 2020), and an extension of relational algebra (Rubin and Berant, 2020).”
OpenAGI: When LLM Meets Domain Experts (2023, methodology): “In the case of RLTF, we employ the fine-tuning checkpoint as a reasonable initialization for LLMs and use constrained beam search [8, 29] to reduce the likelihood of producing infeasible solutions (details can be found in Sec.”
Prefix-to-SQL: Text-to-SQL Generation from Incomplete User Questions (2021, background): “Our results show that both generative and retrieval models can predict SQL queries that match the user’s intention, but the scores are much lower than the original text-to-SQL task (Finegan-Dollak et al., 2018; Dong and Lapata, 2018a; Yin and Neubig, 2018; Cao et al., 2019; Rubin and Berant, 2021; H”
PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models (2021, methodology): “The models, T5-Base, -Large, and -3B, did not have access to any database content, only to the database schemas. paradigm have been proposed (Rubin and Berant, 2021).”