Span-based Semantic Parsing for Compositional Generalization
SpanBasedSP predicts span trees to improve compositional generalization, boosting accuracy from 61.0 to 88.9 on key datasets.
Key Findings
Methodology
This work introduces SpanBasedSP, a span tree-based semantic parser that explicitly models how partial programs compose over input spans. It predicts categories for each span—constants, join, or null—using a BERT encoder for contextual features. The model constructs span trees via an extended CKY algorithm capable of handling non-projective structures, with training based on latent variable optimization through a hard EM approach. The architecture leverages a type system to ensure semantic consistency during composition, and the training process involves searching for the highest scoring latent tree that maps to the target program, without access to gold trees. This approach emphasizes explicit structural modeling over soft attention, aiming to enhance compositional generalization.
Key Results
- On GeoQuery, SCAN, and CLOSURE datasets, the model performs comparably to strong seq2seq baselines on random splits, achieving near-perfect accuracy (>99%). On compositional splits, accuracy improves from 61.0 to 88.9, a substantial gain of nearly 28 percentage points, demonstrating enhanced generalization.
- In GeoQuery's template split, accuracy reaches 96.7%, surpassing baseline models' 64.2%. On CLOSURE, the accuracy increases by 13.5 points to over 80%. Despite training on only 10K examples, the model maintains high performance, highlighting its data efficiency and robustness.
- Ablation studies reveal that explicit lexicon features and non-projective tree support are crucial for optimal performance, especially on small datasets like GeoQuery. The model's ability to handle non-projective structures significantly contributes to its superior generalization.
Significance
This research advances semantic parsing by explicitly modeling the compositional structure of language, addressing the core challenge of structural outside generalization. By integrating a span tree approach with latent variable learning, it overcomes the limitations of traditional seq2seq models that rely solely on soft attention. The method's robustness in low-data regimes and its ability to generalize to unseen structures have profound implications for natural language understanding, enabling more reliable and interpretable systems in real-world applications such as question answering, program synthesis, and knowledge base querying.
Technical Contribution
The key technical contributions include: 1) the formulation of a span tree-based semantic parser that predicts categories for each span, 2) the extension of CKY decoding to support non-projective trees, 3) a latent variable training framework employing hard EM to learn from programs without gold trees, and 4) the incorporation of a type system to enforce semantic validity. These innovations collectively enable the model to explicitly encode compositional structure, improve generalization, and handle complex input-output mappings more effectively than prior seq2seq or grammar-based models.
Novelty
This work is the first to combine span tree modeling with latent variable training in neural semantic parsing, particularly supporting non-projective structures via an extended CKY algorithm. Unlike prior models that rely on implicit attention or rule-based decoding, this approach explicitly encodes compositionality, leading to significant improvements in generalization to unseen structures. Its integration of a type system and non-projective parsing within a neural framework marks a novel contribution to the field.
Limitations
- The computational complexity of the extended CKY algorithm, especially for non-projective trees, limits scalability to very long or highly complex inputs. Training and inference may become prohibitively expensive in such cases.
- The reliance on a predefined type system may restrict flexibility, potentially failing in scenarios with ambiguous or complex semantic relations not well captured by the current types.
- The model's performance on extremely long or deeply nested structures remains uncertain, and further optimization is needed to handle such cases efficiently.
Future Work
Future directions include developing more scalable algorithms for non-projective parsing, integrating reinforcement learning to improve structure prediction, and extending the model to handle richer semantic phenomena such as quantification and negation. Additionally, exploring multi-modal inputs and semi-supervised training could further enhance the model's applicability in real-world, low-resource scenarios.
AI Executive Summary
Semantic parsing, the task of translating natural language into executable programs, has seen significant progress with sequence-to-sequence models. However, these models struggle with compositional generalization, often failing to correctly interpret novel structures composed of familiar components. This limitation hampers their ability to understand complex or unseen language patterns, which are common in real-world applications like question answering and program synthesis.
To address this, the authors propose SpanBasedSP, a novel neural semantic parser that explicitly models the compositional structure of input utterances through span trees. Unlike traditional seq2seq models that rely on soft attention mechanisms, SpanBasedSP predicts categories for each span—such as constants, join operations, or null—forming a tree that captures how partial programs combine. This approach leverages a modified CKY algorithm capable of handling non-projective trees, which are prevalent in natural language semantics.
The training process employs a latent variable framework with a hard EM algorithm, allowing the model to learn from programs alone without requiring gold-standard trees. This weakly supervised setup, combined with a type system to ensure semantic validity, enables the model to learn effective structural representations. Experiments across datasets like GeoQuery, SCAN, and CLOSURE demonstrate that SpanBasedSP achieves comparable performance to strong baselines on standard splits, while dramatically improving accuracy on compositional splits—from 61.0 to 88.9—highlighting its superior generalization capabilities.
These results underscore the importance of explicit structural modeling in semantic parsing. The approach not only advances theoretical understanding but also opens avenues for more robust, data-efficient systems capable of understanding complex language structures. Future work aims to enhance scalability, incorporate richer semantics, and extend to multi-modal inputs, promising a significant leap forward in natural language understanding technology.
Deep Analysis
Background
Semantic parsing has evolved from rule-based symbolic methods to neural models, with early works like Zelle and Mooney (1996) emphasizing explicit syntax. Deep learning approaches, especially seq2seq models (Jia and Liang, 2016), have achieved high accuracy but lack structural interpretability and struggle with unseen combinations. Recent efforts incorporate grammar constraints or structured decoders to improve generalization, yet they often depend on gold trees or rule-based components. The core challenge remains: how to enable models to generalize compositionally, understanding novel structures built from familiar parts, which is crucial for real-world language understanding where data is limited and language is highly variable.
Core Problem
The main issue addressed is the poor ability of existing neural semantic parsers to generalize to unseen compositional structures. Standard seq2seq models, relying on soft attention, lack explicit structural biases, leading to failures in extrapolating learned patterns to novel combinations. This limits their applicability in scenarios requiring robust understanding of complex, unseen language constructs. The challenge is to design a model that explicitly encodes the compositional structure, supports flexible tree representations, and can be trained without relying on gold-standard annotations, thus improving generalization in low-resource and complex settings.
Innovation
The paper introduces several key innovations: 1) a span tree-based neural parser that predicts categories for each span, explicitly modeling composition; 2) an extension of CKY decoding capable of handling non-projective trees, common in natural language semantics; 3) a weakly supervised training paradigm using hard EM, which searches for the most probable latent tree matching the target program; 4) integration of a type system to enforce semantic consistency during composition. These innovations collectively enable the model to learn explicit structural representations, significantly improving its ability to generalize compositionally compared to prior seq2seq or grammar-based methods.
Methodology
- �� Input: natural language utterance and target program.
- �� Encoder: BERT-based contextual embedding for each token.
- �� Span classification: For each span (i,j), concatenate start and end embeddings, then predict category (constant, join, φ) via a multi-layer perceptron.
- �� Tree construction: Use an extended CKY algorithm to find the highest scoring span tree, supporting non-projective structures.
- �� Training: Minimize negative log-likelihood of latent trees with a hard EM approach, searching for the best tree that can generate the target program, constrained by a type system.
- �� Program generation: Bottom-up traversal of the predicted span tree, composing sub-programs according to categories.
- �� Handling invalid trees: Assign -∞ score to semantically invalid trees based on a domain-specific type system.
- �� Support for non-projective trees: Add ternary join rules, increasing complexity but capturing more natural language structures.
Experiments
- �� Datasets: GeoQuery, SCAN, CLOSURE, with both IID and compositional splits.
- �� Baselines: seq2seq, BERT2SEQ, grammar-based models.
- �� Metrics: accuracy on test sets, especially on compositional splits.
- �� Training: limited samples (10K for our model), multiple random splits, ablation studies removing lexicon and non-projective support.
- �� Implementation details: use of hard EM, type constraints, and extended CKY decoding.
- �� Evaluation: compare accuracy, analyze impact of each component, test robustness across datasets.
Results
- �� Achieved near-perfect accuracy (>99%) on IID splits across datasets.
- �� On compositional splits, accuracy improved from 61.0 to 88.9, a 27.9-point increase, outperforming seq2seq baselines.
- �� GeoQuery template split accuracy reached 96.7%, far above baseline (64.2%).
- �� Ablation results confirmed that lexicon features and non-projective parsing significantly boost performance.
- �� The model demonstrated high data efficiency, maintaining performance with only 10K training examples versus hundreds of thousands for baselines.
Applications
- �� Immediate: Enhancing question answering systems, automating program synthesis, improving knowledge base querying, especially in low-resource or complex domain scenarios.
- �� Long-term: Developing more robust natural language understanding systems capable of generalizing to unseen language structures, enabling more flexible AI assistants, and advancing interpretability in neural models.
Limitations & Outlook
- �� Computational cost of extended CKY decoding, especially for non-projective trees, limits scalability.
- �� Dependence on a predefined type system may restrict flexibility in handling ambiguous or complex semantics.
- �� Performance on very long or deeply nested structures remains uncertain, requiring further optimization.
Plain Language Accessible to non-experts
想象你在搭建一座复杂的积木城堡。每一块积木代表一个小部分，比如门、窗、墙。传统的方法就像随便堆积木，虽然可以搭出城堡，但如果想搭出特别复杂或新颖的城堡，就很难。这个研究提出了一种聪明的搭建方式，就像有一份详细的蓝图，告诉你每一块积木应该放在哪个位置，怎么组合成城堡。它会预测每个积木块的类别（比如墙、门、窗），然后用一种特别的拼装工具（改进的CKY算法）把所有积木合理拼在一起，确保城堡既漂亮又符合设计。这样一来，即使遇到以前没见过的城堡样式，也能拼出正确的样子。这让搭建变得更聪明、更有创意，也更容易应对新设计。
ELI14 Explained like you're 14
想象你在玩拼图游戏，每块拼图都有不同的形状和颜色。以前的方法就像随便拼，可能拼出个乱七八糟的图案，但如果遇到新拼图，就不知道怎么拼了。这个研究就像设计了一套聪明的拼图规则，告诉你每块拼图应该放在哪个位置，怎么拼成完整的图案。它用一种特别的“树”结构，把每块拼图都标记好，然后用一种“拼图算法”把它们组合起来，确保拼出来的图案既漂亮又符合规则。这种方法让拼图变得更聪明、更会应变，就像让你的脑袋变得更厉害一样！
Abstract
Despite the success of sequence-to-sequence (seq2seq) models in semantic parsing, recent work has shown that they fail in compositional generalization, i.e., the ability to generalize to new structures built of components observed during training. In this work, we posit that a span-based parser should lead to better compositional generalization. we propose SpanBasedSP, a parser that predicts a span tree over an input utterance, explicitly encoding how partial programs compose over spans in the input. SpanBasedSP extends Pasupat et al. (2019) to be comparable to seq2seq models by (i) training from programs, without access to gold trees, treating trees as latent variables, (ii) parsing a class of non-projective trees through an extension to standard CKY. On GeoQuery, SCAN and CLOSURE datasets, SpanBasedSP performs similarly to strong seq2seq baselines on random splits, but dramatically improves performance compared to baselines on splits that require compositional generalization: from $61.0 \rightarrow 88.9$ average accuracy.