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.

本文提出一种 Semi-autoregressive Bottom-up Parser （SmBoP）的方法，与 top-down autoregressive parsing 方法相比，SmBoP 具有更高效的时间复杂度和使用 meaningful semantic sub-programs 训练的先进性，应用于 Spider 数据集的测试表明，SmBoP 取得了新的最佳 denotation accuracy，并且在 exact match 方面与 RAT-SQL+GraPPa 的结果相当。