Retrieval-Augmented Parsing for Complex Graphs by Exploiting Structure and Uncertainty
Zi Lin, Quan Yuan, Panupong Pasupat, Jeremiah Liu, Jingbo Shang
Abstract
Retrieval augmentation enhances generative language models by retrieving informative exemplars relevant for output prediction. However, in realistic graph parsing problems where the output space is large and complex, classic retrieval methods based on input-sentence similarity can fail to identify the most informative exemplars that target graph elements the model is most struggling about, leading to suboptimal retrieval and compromised prediction under limited retrieval budget. In this work, we improve retrieval-augmented parsing for complex graph problems by exploiting two unique sources of information (1) structural similarity and (2) model uncertainty. We propose Structure-aware and Uncertainty-Guided Adaptive Retrieval (SUGAR) that first quantify the model uncertainty in graph prediction and identify its most uncertain subgraphs, and then retrieve exemplars based on their structural similarity with the identified uncertain subgraphs. On a suite of real-world parsing benchmarks with non-trivial graph structure (SMCalflow and E-commerce), SUGAR exhibits a strong advantage over its classic counterparts that do not leverage structure or model uncertainty.- Anthology ID:
- 2023.findings-emnlp.419
- Volume:
- Findings of the Association for Computational Linguistics: EMNLP 2023
- Month:
- December
- Year:
- 2023
- Address:
- Singapore
- Editors:
- Houda Bouamor, Juan Pino, Kalika Bali
- Venue:
- Findings
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 6330–6345
- Language:
- URL:
- https://aclanthology.org/2023.findings-emnlp.419
- DOI:
- 10.18653/v1/2023.findings-emnlp.419
- Cite (ACL):
- Zi Lin, Quan Yuan, Panupong Pasupat, Jeremiah Liu, and Jingbo Shang. 2023. Retrieval-Augmented Parsing for Complex Graphs by Exploiting Structure and Uncertainty. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 6330–6345, Singapore. Association for Computational Linguistics.
- Cite (Informal):
- Retrieval-Augmented Parsing for Complex Graphs by Exploiting Structure and Uncertainty (Lin et al., Findings 2023)
- PDF:
- https://preview.aclanthology.org/naacl24-info/2023.findings-emnlp.419.pdf