# SmBoP: Semi-autoregressive Bottom-up Semantic Parsing

arXiv: https://arxiv.org/abs/2010.12412 · HTML: https://mlsanity.com/paper/2010.12412/

## Key facts

- Cited by 97 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2020.

## Built on by (most cited first, 30 of 97)

- [DIN-SQL: Decomposed In-Context Learning of Text-to-SQL with Self-Correction](https://mlsanity.com/paper/2304.11015/) (2023)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [UnifiedSKG: Unifying and Multi-Tasking Structured Knowledge Grounding with Text-to-Text Language Models](https://mlsanity.com/paper/2201.05966/) (2022)
- [OpenAGI: When LLM Meets Domain Experts](https://mlsanity.com/paper/2304.04370/) (2023)
- [RESDSQL: Decoupling Schema Linking and Skeleton Parsing for Text-to-SQL](https://mlsanity.com/paper/2302.05965/) (2023)
- [CodeS: Towards Building Open-source Language Models for Text-to-SQL](https://mlsanity.com/paper/2402.16347/) (2024)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [LGESQL: Line Graph Enhanced Text-to-SQL Model with Mixed Local and Non-Local Relations](https://mlsanity.com/paper/2106.01093/) (2021)
- [Graphix-T5: Mixing Pre-Trained Transformers with Graph-Aware Layers for Text-to-SQL Parsing](https://mlsanity.com/paper/2301.07507/) (2023)
- [Exploring Underexplored Limitations of Cross-Domain Text-to-SQL Generalization](https://mlsanity.com/paper/2109.05157/) (2021)
- [RASAT: Integrating Relational Structures into Pretrained Seq2Seq Model for Text-to-SQL](https://mlsanity.com/paper/2205.06983/) (2022)
- [Natural SQL: Making SQL Easier to Infer from Natural Language Specifications](https://mlsanity.com/paper/2109.05153/) (2021)
- [A Survey on Employing Large Language Models for Text-to-SQL Tasks](https://mlsanity.com/paper/2407.15186/) (2024)
- [How to Prompt LLMs for Text-to-SQL: A Study in Zero-shot, Single-domain, and Cross-domain Settings](https://mlsanity.com/paper/2305.11853/) (2023)
- [Don't Generate, Discriminate: A Proposal for Grounding Language Models to Real-World Environments](https://mlsanity.com/paper/2212.09736/) (2022)
- [A Survey of Text-to-SQL in the Era of LLMs: Where are we, and where are we going?](https://mlsanity.com/paper/2408.05109/) (2024)
- [Unlocking Compositional Generalization in Pre-trained Models Using Intermediate Representations](https://mlsanity.com/paper/2104.07478/) (2021)
- [Dr.Spider: A Diagnostic Evaluation Benchmark towards Text-to-SQL Robustness](https://mlsanity.com/paper/2301.08881/) (2023)
- [OpenSearch-SQL: Enhancing Text-to-SQL with Dynamic Few-shot and Consistency Alignment](https://mlsanity.com/paper/2502.14913/) (2025)
- [A Survey on Text-to-SQL Parsing: Concepts, Methods, and Future Directions](https://mlsanity.com/paper/2208.13629/) (2022)
- [ArcaneQA: Dynamic Program Induction and Contextualized Encoding for Knowledge Base Question Answering](https://mlsanity.com/paper/2204.08109/) (2022)
- [Recent Advances in Text-to-SQL: A Survey of What We Have and What We Expect](https://mlsanity.com/paper/2208.10099/) (2022)
- [SADGA: Structure-Aware Dual Graph Aggregation Network for Text-to-SQL](https://mlsanity.com/paper/2111.00653/) (2021)
- [Large Language Model-Aware In-Context Learning for Code Generation](https://mlsanity.com/paper/2310.09748/) (2023)
- [S2SQL: Injecting Syntax to Question-Schema Interaction Graph Encoder for Text-to-SQL Parsers](https://mlsanity.com/paper/2203.06958/) (2022)
- [Benchmarking and Improving Text-to-SQL Generation under Ambiguity](https://mlsanity.com/paper/2310.13659/) (2023)
- [PURPLE: Making a Large Language Model a Better SQL Writer](https://mlsanity.com/paper/2403.20014/) (2024)
- [Importance of Synthesizing High-quality Data for Text-to-SQL Parsing](https://mlsanity.com/paper/2212.08785/) (2022)
- [Natural Language Interfaces for Tabular Data Querying and Visualization: A Survey](https://mlsanity.com/paper/2310.17894/) (2023)
- [HIE-SQL: History Information Enhanced Network for Context-Dependent Text-to-SQL Semantic Parsing](https://mlsanity.com/paper/2203.07376/) (2022)

## Abstract (arXiv)

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.