# On graph-based reentrancy-free semantic parsing

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 90 references that are in the map.
- First posted on arXiv 15 Feb 2023.

## Builds on (most cited first, 30 of 34)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Deep contextualized word representations](https://mlsanity.com/paper/1802.05365/) (2018)
- [CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning](https://mlsanity.com/paper/1612.06890/) (2016)
- [RAT-SQL: Relation-Aware Schema Encoding and Linking for Text-to-SQL Parsers](https://mlsanity.com/paper/1911.04942/) (2019)
- [Deep Biaffine Attention for Neural Dependency Parsing](https://mlsanity.com/paper/1611.01734/) (2016)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [Language to Logical Form with Neural Attention](https://mlsanity.com/paper/1601.01280/) (2016)
- [Good-Enough Compositional Data Augmentation](https://mlsanity.com/paper/1904.09545/) (2019)
- [Improving Text-to-SQL Evaluation Methodology](https://mlsanity.com/paper/1806.09029/) (2018)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [Data Recombination for Neural Semantic Parsing](https://mlsanity.com/paper/1606.03622/) (2016)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Span-based Semantic Parsing for Compositional Generalization](https://mlsanity.com/paper/2009.06040/) (2020)
- [Grammar as a Foreign Language](https://mlsanity.com/paper/1412.7449/) (2014)
- [Learning to Recombine and Resample Data for Compositional Generalization](https://mlsanity.com/paper/2010.03706/) (2020)
- [CLOSURE: Assessing Systematic Generalization of CLEVR Models](https://mlsanity.com/paper/1912.05783/) (2019)
- [A Minimal Span-Based Neural Constituency Parser](https://mlsanity.com/paper/1705.03919/) (2017)
- [Rearranging the Familiar: Testing Compositional Generalization in Recurrent Networks](https://mlsanity.com/paper/1807.07545/) (2018)
- [Simpler but More Accurate Semantic Dependency Parsing](https://mlsanity.com/paper/1807.01396/) (2018)
- [Improving Compositional Generalization with Latent Structure and Data Augmentation](https://mlsanity.com/paper/2112.07610/) (2021)
- [AMR Parsing as Graph Prediction with Latent Alignment](https://mlsanity.com/paper/1805.05286/) (2018)
- [Compositional Generalization via Semantic Tagging](https://mlsanity.com/paper/2010.11818/) (2020)
- [Don't paraphrase, detect! Rapid and Effective Data Collection for Semantic Parsing](https://mlsanity.com/paper/1908.09940/) (2019)
- [Structured Reordering for Modeling Latent Alignments in Sequence Transduction](https://mlsanity.com/paper/2106.03257/) (2021)
- [SUBS: Subtree Substitution for Compositional Semantic Parsing](https://mlsanity.com/paper/2205.01538/) (2022)
- [A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming](https://mlsanity.com/paper/1804.08544/) (2018)
- [Dependency Parsing as Head Selection](https://mlsanity.com/paper/1606.01280/) (2016)

## Built on by (most cited first, 2 of 2)

- [Compositional Generalization without Trees using Multiset Tagging and Latent Permutations](https://mlsanity.com/paper/2305.16954/) (2023)
- [Structural generalization in COGS: Supertagging is (almost) all you need](https://mlsanity.com/paper/2310.14124/) (2023)

## Abstract (arXiv)

We propose a novel graph-based approach for semantic parsing that resolves two problems observed in the literature: (1) seq2seq models fail on compositional generalization tasks; (2) previous work using phrase structure parsers cannot cover all the semantic parses observed in treebanks. We prove that both MAP inference and latent tag anchoring (required for weakly-supervised learning) are NP-hard problems. We propose two optimization algorithms based on constraint smoothing and conditional gradient to approximately solve these inference problems. Experimentally, our approach delivers state-of-the-art results on Geoquery, Scan and Clevr, both for i.i.d. splits and for splits that test for compositional generalization.