Lune

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

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 onCited byLeft to right by year; the more cited, the higher.

Builds on13

  1. Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
  2. Training language models to follow instructions with human feedbackLong Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida et al.NeurIPS 2022 · 24,707 citations
  3. Active Retrieval Augmented GenerationZhengbao Jiang, Frank F. Xu, Luyu Gao, Zhiqing Sun et al.EMNLP 2023 · 315 citations
  4. Measuring and Narrowing the Compositionality Gap in Language ModelsOfir Press, Muru Zhang, Sewon Min, Ludwig Schmidt et al.EMNLP Findings 2023 · 296 citations
  5. Decomposed Prompting: A Modular Approach for Solving Complex TasksTushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu et al.ICLR 2023 · 94 citations

Related papers

  1. 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
  2. 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
  3. GRIL: Knowledge Graph Retrieval-Integrated Learning with Large Language ModelsJialin Chen, Houyu Zhang, Seongjun Yun, Alejandro Mottini et al.EMNLP Findings 2025 · 3 citations
  4. Structure Guided Retrieval-Augmented Generation for Factual QueriesMiao Xie, Xiao Zhang, Yi Li, Chunli LvACL 2026 · 1 citation
  5. SeaKR: Self-aware Knowledge Retrieval for Adaptive Retrieval Augmented GenerationZijun Yao, Weijian Qi, Liangming Pan, Shulin Cao et al.ACL 2025
Dusk over the sea between two cliffs drawn in fine vertical lines