Graph-Based Transformer with Cross-Candidate Verification for Semantic Parsing

Bo Shao, Yeyun Gong, Weizhen Qi, Guihong Cao, Jianshu Ji, Xiaola LinAAAI 2020 · DOI

Abstract

Semantic parsing is the task of converting natural language into machine-readable logical forms. While sequence-to-sequence (S2S) models are effective, they often fail to capture the hierarchical structure of logical forms or leverage the information present in the candidate pool. This paper proposes a Graph-Based Transformer with Cross-Candidate Verification (GTCV), a two-step approach that combines generative power with a structural reranking system. GTCV achieves state-of-the-art results on the Task Oriented Parsing (TOP) dataset by incorporating graph-aware attention and a novel verification mechanism.

Introduction

Modern AI assistants rely on semantic parsing to interpret user commands like "How far is the coffee shop?". Despite the success of standard S2S models, a significant performance gap remains: the correct logical form is often present in the top-k beam search results but not as the top-1 prediction. Standard models treat these forms as flat text strings, ignoring the rich tree structures they represent. This work addresses this gap by introducing a "judge" model designed to select the optimal candidate from the generated pool by respecting structural constraints and cross-candidate consistency.

The GTCV Architecture

The proposed GTCV pipeline consists of four primary stages:

  1. Candidate Generation: An RNN-based encoder-decoder model with attention and copy mechanisms generates a list of potential logical forms via beam search.
  2. BERT Encoding: Each candidate is paired with the original query and processed through a BERT encoder to obtain high-quality initial representations.
  3. Graph-Aware Matching: To capture the hierarchical nature of logical forms, the authors implement a masking strategy within the Transformer. This forces the attention mechanism to follow the tree structure, where tokens only attend to their parents or children.
  4. Cross-Candidate Verification: Instead of scoring candidates independently, GTCV compares all candidates in the beam. By calculating pairwise similarities, the model identifies sub-components that frequently appear across high-quality candidates, effectively using the "wisdom of the crowd" to verify the correct output.
The GTCV architecture overview, illustrating the flow from candidate generation to final scoring via graph-aware matching and cross-candidate verification.

Experimental Setup

The model was evaluated on three benchmark datasets:

  • TOP (Task Oriented Parsing): Features complex, nested hierarchical structures for navigation and events.
  • ATIS (Airline Travel Information System): A classic dataset for flight booking queries.
  • JOBS: A dataset of Prolog-style logical forms for job listings.

Results and Discussion

GTCV established a new state-of-the-art on the TOP dataset with an exact match accuracy of 82.51%, a significant improvement over the previous best of 78.51% (RNNG) and a standard BERT reranker (80.15%). On ATIS and JOBS, the model remained highly competitive, achieving 87.3% and 92.9% accuracy, respectively.

Accuracy comparison across different beam sizes for BERT, BERT with Graph Matching (GM), and the full GTCV model on the TOP dataset.

Ablation studies confirmed that both Graph-Aware Matching and Cross-Candidate Verification are essential. As shown in the results, increasing the beam size allows GTCV to more effectively leverage the candidate pool, with performance gains scaling more significantly than the baseline BERT reranker.

Conclusion

GTCV demonstrates that structural awareness and cross-candidate interaction are critical for high-accuracy semantic parsing. While the two-step process introduces some latency and depends on the initial generator's quality, the gains in accuracy on complex, hierarchical datasets like TOP are substantial. Future work may explore applying these graph-aware techniques to other structured tasks such as SQL parsing or code generation.

Summary updated

BibTeX
@inproceedings{shao2020graph,
  author = {Bo Shao and Yeyun Gong and Weizhen Qi and Guihong Cao and Jianshu Ji and Xiaola Lin},
  title = {{Graph-Based Transformer with Cross-Candidate Verification for Semantic Parsing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i05.6408},
}
Figure