EMNLP Findings2023
Retrieval-Augmented Parsing for Complex Graphs by Exploiting Structure and Uncertainty
Zi Lin, Quan Yuan, Panupong Pasupat, Jeremiah Z. 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
- Measuring and Narrowing the Compositionality Gap in Language Models cites Decomposed Prompting: A Modular Approach for Solving Complex Tasks
- Decomposed Prompting: A Modular Approach for Solving Complex Tasks cites Measuring and Narrowing the Compositionality Gap in Language Models
- Decomposed Prompting: A Modular Approach for Solving Complex Tasks cites Language Models are Few-Shot Learners
- Decomposed Prompting: A Modular Approach for Solving Complex Tasks cites Training language models to follow instructions with human feedback
- Training language models to follow instructions with human feedback cites Language Models are Few-Shot Learners
- Active Retrieval Augmented Generation cites Measuring and Narrowing the Compositionality Gap in Language Models
- Active Retrieval Augmented Generation cites Decomposed Prompting: A Modular Approach for Solving Complex Tasks
- Active Retrieval Augmented Generation cites Training language models to follow instructions with human feedback
Builds on13
- Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
- Training language models to follow instructions with human feedbackLong Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida et al.NeurIPS 2022 · 24,707 citations
- Active Retrieval Augmented GenerationZhengbao Jiang, Frank F. Xu, Luyu Gao, Zhiqing Sun et al.EMNLP 2023 · 315 citations
- Measuring and Narrowing the Compositionality Gap in Language ModelsOfir Press, Muru Zhang, Sewon Min, Ludwig Schmidt et al.EMNLP Findings 2023 · 296 citations
- Decomposed Prompting: A Modular Approach for Solving Complex TasksTushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu et al.ICLR 2023 · 94 citations
Related papers
- GENUINE: Graph Enhanced Multi-level Uncertainty Estimation for Large Language ModelsTuo Wang, Adithya Kulkarni, Tyler Cody, Peter A. Beling et al.EMNLP Findings 2025 · 1 citation
- Less is More: Making Smaller Language Models Competent Subgraph Retrievers for Multi-hop KGQAWenyu Huang, Guancheng Zhou, Hongru Wang, Pavlos Vougiouklis et al.EMNLP Findings 2024 · 2 citations
- GRIL: Knowledge Graph Retrieval-Integrated Learning with Large Language ModelsJialin Chen, Houyu Zhang, Seongjun Yun, Alejandro Mottini et al.EMNLP Findings 2025 · 3 citations
- Structure Guided Retrieval-Augmented Generation for Factual QueriesMiao Xie, Xiao Zhang, Yi Li, Chunli LvACL 2026 · 1 citation
- SeaKR: Self-aware Knowledge Retrieval for Adaptive Retrieval Augmented GenerationZijun Yao, Weijian Qi, Liangming Pan, Shulin Cao et al.ACL 2025
