PaperlayerView exact revision on arXiv

Source-linked AI summary

SmBoP: Semi-autoregressive Bottom-up Semantic Parsing

Ohad Rubin, Jonathan Berant

arXiv:2010.12412v2cs.CL

TL;DR

Semantic parsing has predominantly used top-down autoregressive tree decoding, motivating a more efficient and semantically meaningful alternative. SmBoP builds program sub-trees bottom-up and semi-autoregressively, achieving faster decoding and training while retaining strong Spider performance. It reaches state-of-the-art denotation accuracy, with exact match comparable to the autoregressive baseline.

  • Problem

    Semantic parsing has largely relied on top-down autoregressive decoding, whose intermediate hidden states represent partial trees without clear semantics.

  • Method

    SmBoP semi-autoregressively constructs the top-K sub-trees of increasing height in parallel using grammar-based bottom-up parsing.

  • Results

    71.1 denotation accuracy establishes a new Spider state of the art, while 69.5 exact match is comparable to 69.6 for autoregressive RAT-SQL+GRAPPA.

  • Takeaways & Limitations

    Bottom-up parsing is a promising direction that combines semantically meaningful sub-tree representations with logarithmic theoretical runtime.

  • Takeaways & Limitations

    SMBOP cannot generate database values absent from the input question, and executing sub-queries during training causes a training slow-down.

Abstract

from arXiv · show

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 $\leq 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 $\sim$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.

1 Introduction

Semantic parsing has largely relied on top-down autoregressive decoding, while SmBoP introduces a semi-autoregressive bottom-up alternative that combines efficiency with meaningful sub-tree representations. On Spider, it substantially accelerates decoding and training while achieving strong accuracy.

  • Method: SmBoP generates the top-K program sub-trees of depth ≤t in parallel at each decoding step, yielding logarithmic rather than linear runtime complexity.The procedure scores frontier trees formed from the current beam, retains the top K, and builds the next beam.
  • Method: Bottom-up parsing represents meaningful executable sub-programs, unlike top-down decoding states that represent semantically unclear partial trees.The learned representations correspond to sub-trees computed during search.
  • Results: 2.2x decoding speed-up and ∼5x training speed-up are achieved versus autoregressive semantic parsing.For long SQL queries, decoding speed-up is reported at 5x–6x.
  • Results: 71.1 denotation accuracy is obtained on Spider, while exact match reaches 69.5 versus 69.6 for autoregressive RAT-SQL+GRAPPA.The denotation result improves performance from 68.3 to 71.1.
  • Evaluation: The parser evaluates a challenging zero-shot text-to-SQL benchmark using a RAT-SQL+GRAPPA encoder and replaces its autoregressive decoder with SmBoP.At each step, the beam is contextualized with the input question before frontier scoring and pruning.

2 Background

The paper frames text-to-SQL as mapping utterance–schema pairs to SQL queries and reviews encoder and decoder components used in semantic parsing. Its background centers on RAT-SQL’s joint utterance–schema representations and grammar-based top-down decoding.

  • Task: Text-to-SQL maps a question and database schema to the correct SQL query, with schemas containing tables, columns, and foreign-key relationships.Schema tables and columns are treated as schema constants.
  • RAT-SQL encoder: RAT-SQL jointly contextualizes utterance tokens and schema constants using Transformer layers and aggregation over schema elements.This produces representations intended to improve utterance–schema representation and alignment.
  • RAT-SQL encoder: Relational-aware self-attention adds embeddings that represent relations between token pairs, such as foreign-key links or utterance–column string matches.The relation embedding augments the usual query–key interaction and is also used for self-attention values.
  • Pretraining: RAT-SQL is commonly combined with pretrained language models, and this work uses GRAPPA, which is fine-tuned on synthetic utterance–query pairs.GRAPPA is based on RoBERTa and uses an objective aligning utterances and queries.
  • Decoding background: Grammar-based autoregressive top-down decoding represents a target program as an abstract syntax tree and linearizes it into a sequence of rules or actions.The approach guarantees syntactically valid programs.

3 The SMBOP parser

SMBOP parses relational-algebra query trees bottom-up with a semi-autoregressive beam, balancing trees and composing sub-trees across decoding steps. It uses typed tree scoring and contextualized representations, offering logarithmic theoretical runtime and representations useful for contextual parsing.

  • Overview: SMBOP encodes utterances and schemas with RAT-SQL, then initializes a beam with the K highest-scoring height-0 schema constants or database values.All trees are scored independently and in parallel.
  • Bottom-up decoding: At step t, attention contextualizes the beam, scores all grammar-constructible frontier trees of depth ≤t + 1, retains the top K, and represents them for the next step.The search returns the highest-scoring returnable tree after the final decoding step.
  • Query representation: Relational algebra represents queries as trees whose leaves are schema constants or database values and whose internal nodes are operations aligned more closely with natural language than SQL.The parser transpiles SQL queries to relational algebra for parsing and back to SQL for evaluation.
  • Tree balancing: A unary KEEP operation preserves sub-tree semantics while increasing height, allowing training trees to be balanced with all leaves equidistant from the root.Balanced trees contain constants and values at height 0, supporting fixed-height beams.
  • Discussion: SMBOP theoretically reduces decoding complexity from linear to logarithmic in tree size and naturally produces representations for meaningful sub-trees that can support contextual semantic parsing.The paper gives multi-turn question answering as an example, where a later pronoun refers to a prior SQL sub-tree.

4 Experimental Evaluation

The evaluation on SPIDER shows that SMBOP combines competitive parsing accuracy with faster decoding and training, while analysis identifies remaining search and schema-related errors.

  • Experimental setup: SPIDER evaluates text-to-SQL parsing in a challenging zero-shot setting with schemas unseen during training.The official evaluation reports exact match and, for models outputting database values, denotation accuracy.
  • Results: 69.5% EM is comparable to RAT-SQL+GRAPPA at 69.6%, while SMBOP reaches state-of-the-art denotation accuracy of 71.1.SMBOP outputs executable database values, unlike models producing anonymized queries.
  • Results: 2.23x faster decoding is achieved on average, with 4x-6x speed-ups for long queries; including the encoder, average speed-up is 1.55x.The decoder comparison uses RAT-SQLv3+BERT because RAT-SQLv3+GRAPPA code was unavailable.
  • Results: After 120K examples, SMBOP reaches 67.5 EM versus 47.6 for RAT-SQL+GRAPPA, while processing 20.4 versus 3.8 examples per second.The resulting training time is slightly more than one day for SMBOP versus 5-6 days for RAT-SQL.
  • Analysis: Oracle schema matching improves EM from 74.7 to 79.1, indicating that schema matching and search remain performance bottlenecks.Initial detection of relevant schema constants and database values is already 96.6%-98.3%.
  • Analysis: BEM is 8%-9% higher than EM, suggesting that a reranker over SMBOP's generated trees could improve performance.The paper leaves reranking for future work.
  • Analysis: A beam can recover from early decoding errors when relevant subtrees remain through the KEEP operation and are expanded later.Z_t recall measures whether all gold subtrees of height t were generated at step t.
  • Analysis: 52% of sampled errors are search errors and 34% are schema encoding errors, while 62% involve an incorrectly expanded child indicating a composition error.The search errors mainly involve extra or missing JOIN or WHERE conditions.

5 Conclusions

The paper presents semi-autoregressive bottom-up parsing as a promising direction that preserves state-of-the-art performance while improving decoding and training efficiency.

  • 5 Conclusions: SMBOP is the first semi-autoregressive bottom-up semantic parser with logarithmic theoretical runtime.It constructs representations for semantically meaningful subtrees during decoding.
  • 5 Conclusions: 2.2x faster decoding and approximately 5x faster training are reported while maintaining state-of-the-art performance.The paper identifies contextual semantic parsing and execution at training time as future settings that may benefit from bottom-up parsing.

A Computing supervision through tree hashing

SmBoP uses recursive tree hashing to identify gold sub-trees during decoding. Frontier hashes are computed and checked against gold hashes in parallel.

  • At each decoding step, the parser checks whether every frontier tree belongs to the gold-tree set.This determines membership for each tree in the frontier F_t+1.
  • Gold hashes are precomputed for every height from the gold tree’s sub-trees using a recursive Merkle tree hash.The hash values hgold_t represent gold sub-trees of height t.
  • Each tree hash combines the node label with the hashes of its left and right children.Here, g is the hash function, while label(·) identifies the node type and z_l, z_r are the children.
  • During training, frontier hashes are recursively computed from the current beam and looked up in the corresponding gold-hash set.The hash computation and lookup run in parallel for all frontier trees on the GPU.

B Examples for Relational Algebra Trees

The paper illustrates relational algebra trees alongside their corresponding SQL queries. The examples cover ordering, joins, filtering, counting, and distinct aggregation.

  • Examples for Relational Algebra Trees: Examples pair relational algebra trees with SQL queries to clarify the mapping between the two representations.The examples are provided for better understanding of this mapping.
  • Examples for Relational Algebra Trees: A flight-counting example joins flights with airports and filters destinations to Aberdeen.The SQL query counts all matching flights where airports.city is ’Aberdeen’.
  • Examples for Relational Algebra Trees: A transcript example orders transcript dates ascending and returns the first date with additional details.The SQL query uses ORDER BY transcripts.transcript_date ASC and LIMIT 1.
  • Examples for Relational Algebra Trees: A pet-counting example joins students, pets, and ownership records before filtering female students and dog pets.The SQL query counts records satisfying student.sex = ’F’ and pets.pettype = ’dog’.
  • Examples for Relational Algebra Trees: A loser-name example counts distinct values from the matches relation.The SQL query computes COUNT(DISTINCT matches.loser_name).
Loading 2010.12412v2…