Skip to content

How Reliable are AMR Parser Outputs? Uncertainty Estimation for AMR Parsing

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/naist-nlp/UE_Method_AMR_Parser
Area: LLM Reasoning
Keywords: Abstract Meaning Representation, Uncertainty Estimation, Beam Search, Prediction Rejection Ratio, Model Reliability

TL;DR

Addressing the lack of confidence calibration in neural semantic parsing, this work presents the first black-box uncertainty estimation framework for AMR parsers by constructing graph-spectral and lexical estimators over pairwise beam candidate similarities and evaluating reliability via the Prediction Rejection Ratio.

Background & Motivation

Abstract Meaning Representation (AMR) captures the sentence-level semantic backbone by structuring concepts and predicate-argument relations into rooted, directed graphs beyond surface syntax. This rich semantic formalization serves as a foundational component for meaning-centric downstream NLP tasks such as information extraction, multi-hop question answering, text summarization, and multilingual semantic parsing. With the introduction of modern pretrained language models and graph linearization techniques, neural AMR parsers like SPRING, IBM Transition Parser, and HMG-AMR have achieved remarkable performance on benchmark datasets when measured by traditional corpus-level metrics such as Smatch and Smatch++. However, downstream symbolic reasoners and high-stakes decision-making pipelines are highly sensitive to graph inaccuracies; a single hallucinated edge or missing core predicate can trigger catastrophic logical failure cascades.

In practical deployment, practitioners require more than just aggregate benchmark numbers—they need to know whether a specific predicted AMR graph generated for a given input is trustworthy. Unfortunately, current evaluation paradigms rely exclusively on comparing model outputs against gold-standard reference annotations, which offers zero guidance during inference when references are unavailable, and fails to reveal whether a parser's internal confidence aligns with its true structural accuracy. While uncertainty estimation (UE) has recently gained substantial traction in large language models using token-level likelihoods, entropy, or free-form verbalization, the problem of evaluating uncertainty for structured, non-Euclidean symbolic AMR parsing under a black-box setting—where internal model probabilities and latent states are inaccessible—remains completely unexplored.

This paper tackles this gap by observing that in standard black-box decoding, the top-\(k\) beam candidate distribution inherently reflects the consensus and dispersion of the model's decision space. When candidate graphs exhibit tight semantic agreement, the parser is decisively certain; conversely, severe divergence across candidates indicates heightened structural confusion. Core idea: under a strictly black-box setting without access to model probabilities or internal activations, this work constructs pairwise similarity matrices over top-\(k\) beam candidates to formulate normalized Laplacian graph-spectral and lexical uncertainty estimators, establishing the first comprehensive benchmark evaluating AMR parser reliability via the Prediction Rejection Ratio (PRR).

Method

Overall Architecture

The proposed black-box uncertainty estimation and reliability evaluation pipeline operates across three interconnected phases. First, given an input sentence \(s\), a black-box AMR parser decodes a candidate set of \(k\) beam outputs \(C = \{g^{(1)}, \dots, g^{(k)}\}\) via standard beam search, where \(g^{(1)} = \hat{g}\) represents the top-1 primary prediction. A pairwise semantic or lexical graph similarity metric computes similarities between candidate graphs to construct a symmetric affinity matrix \(S \in \mathbb{R}^{k \times k}\). Second, an uncertainty estimator \(U\) maps the matrix \(S\) into a scalar uncertainty score \(u \in \mathbb{R}\), where larger values indicate lower parser confidence. Third, across the test corpus, predictions are sorted by estimated uncertainty in ascending order, and the Prediction Rejection Ratio (PRR) is computed against gold graph qualities to measure the performance improvement achieved by rejecting high-uncertainty outputs.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input sentence s and black-box AMR parser"] --> B["Pairwise candidate similarity matrix construction<br/>Top-k beam graphs compared via Smatch/SEMA/ROUGE-L"]
    B --> C["Graph-spectral and lexical uncertainty estimators<br/>EigV / Ecc / DegMat / LexSim compute scalar score u"]
    C --> D["Prediction Rejection Ratio reliability evaluation<br/>Rank and reject uncertain samples to compute PRR curve"]

Key Designs

1. Pairwise candidate similarity matrix construction: capturing discrete structural consensus In a realistic black-box setting where token log-probabilities and internal hidden representations cannot be inspected, the model's uncertainty must be inferred entirely from the distribution of its discrete output graphs. Given \(k\) beam search candidate graphs \(C_i = \{g^{(1)}_i, \dots, g^{(k)}_i\}\), the framework computes pairwise graph similarities using an AMR similarity function \(F_{\text{sim}}\), forming a sentence-level affinity matrix \([S_i]_{jl} = F_{\text{sim}}(g^{(j)}_i, g^{(l)}_i)\) with identity self-similarity \([S_i]_{jj} = 1\). The similarity functions encompass classic Smatch triple overlap, modern Smatch++ alignment, embedding-enhanced \(S^2\text{Match}\), bipartite-matching-based SEMA, and Weisfeiler-Lehman graph kernels (WLK). Invalid candidates (<1% of generations) receive zero similarity, successfully projecting discrete graph structures into a dense, continuous affinity matrix.

2. Graph-spectral and lexical uncertainty estimators: quantifying structural dispersion Given affinity matrix \(S_i\), the core challenge is designing scalar reduction operators that monotonically correlate with structural parsing errors. The paper introduces two families of estimators spanning four techniques. The graph-based family interprets \(S_i\) as a weighted undirected graph with symmetrized adjacency \(A = (S_i + S_i^\top)/2\) and degree matrix \(D\), deriving the normalized symmetric Laplacian \(L = I - D^{-1/2} A D^{-1/2}\). By spectral graph theory, candidate agreement concentrates non-zero eigenvalues near 1, while structural fragmentation shifts eigenvalues toward 0. Accordingly, the Eigenvalue Deviation estimator (EigV) accumulates deviations from unity \(u^{\text{EigV}}_i = \sum_{j=1}^k \max(0, 1 - \lambda_j)\); the Eigenspace Eccentricity estimator (Ecc) projects candidates into the Laplacian eigenvector space \(e_j \in \mathbb{R}^k\) and computes the Frobenius norm of mean-centered embeddings \(u^{\text{Ecc}}_i = \sqrt{\sum_{j=1}^k \|e_j - \bar{e}\|^2}\) to capture geometric spread; and the Degree Matrix estimator (DegMat) computes the complement of normalized total edge weights \(u^{\text{DegMat}}_i = 1 - \frac{1}{k^2} \sum_{j,l} A_{jl}\). In addition, the lexical baseline estimator (LexSim) calculates the complement of pairwise ROUGE-L overlaps across linearized graph strings \(u^{\text{LexSim}}_i = 1 - \frac{1}{k(k-1)} \sum_{j \neq l} [R_i]_{jl}\) without graph parsing.

3. Prediction Rejection Ratio reliability evaluation: benchmarking quality gains under selective filtering A dependable uncertainty estimator must assign high scores to inaccurate predictions and low scores to accurate ones, satisfying \(u_i \propto (1 - q_i)\). To evaluate this property without arbitrary classification thresholds, the framework employs the Prediction Rejection Ratio (PRR). Test predictions are ordered by ascending uncertainty \(\pi = \text{argsort}(u)\). At rejection rate \(\alpha \in [0, 1]\), the \(\lfloor \alpha n \rfloor\) most uncertain instances are discarded, and the mean quality of the retained predictions is calculated as \(Q(\alpha) = \frac{1}{n - \lfloor \alpha n \rfloor} \sum_{r=1}^{n - \lfloor \alpha n \rfloor} q_{\pi_r}\). Integrating \(Q(\alpha)\) over \(\alpha \in [0, 1]\) yields the area under the prediction-rejection curve (\(\text{AUCPR}\)). Normalizing against random rejection and an ideal oracle yields the final metric: $\(\text{PRR} = \frac{\text{AUCPR}_{\text{unc}} - \text{AUCPR}_{\text{random}}}{\text{AUCPR}_{\text{oracle}} - \text{AUCPR}_{\text{random}}}\)$ Under this formulation, \(\text{PRR} = 1\) denotes an optimal oracle ranking, \(\text{PRR} = 0\) corresponds to uninformative random rejection, and \(\text{PRR} < 0\) flags actively harmful uncertainty estimates that erroneously discard high-quality predictions before poor ones.

Key Experimental Results

Main Results

Experiments were conducted on the AMR 3.0 test set (1,898 sentence-graph pairs) across six prominent AMR parsers (SPRING, MBSE, HMG-AMR-BART, IBM-Parser, IBM-Neural, HMG-AMR-T5) across four beam sizes (\(k \in \{3, 5, 8, 10\}\)), four uncertainty estimator families, and three reference evaluation metrics (Smatch++, S2Match, SemBLEU).

Parser Architecture Top-1 Smatch Top-1 Smatch++ Mean PRR (Smatch++) Mean PRR (\(S^2\text{Match}\)) Mean PRR (SemBLEU)
SPRING (Bevilacqua et al., 2021) Seq2Seq (BART) 0.8449 0.8438 0.291 0.269 0.236
MBSE (Lee et al., 2022) Ensemble Distill 0.8374 0.8378 0.204 0.211 0.128
HMG-AMR-BART (Sataer et al., 2024) Hierarchical BART 0.8358 0.8380 0.154 0.191 0.120
IBM-Parser (Astudillo et al., 2020) Stack-Transformer 0.8128 0.8181 0.239 0.264 0.136
IBM-Neural (Drozdov et al., 2022) Alignment Transition 0.8115 0.8174 0.225 0.225 0.127
HMG-AMR-T5 (Sataer et al., 2024) Hierarchical T5 0.7693 0.7797 0.100 0.191 0.073
Qwen3-32B (Direct Generation) Instruction LLM 0.1214 - - - -
Ministral-14B (Direct Generation) Instruction LLM 0.0897 - - - -

Note: General-purpose LLMs without task-specific fine-tuning achieve very low Smatch (<0.13) on AMR 3.0, confirming the necessity of specialized structural parsers; they were excluded from downstream PRR evaluation.

Ablation Study

The following table details the PRR performance of individual uncertainty estimators across all parsers at the large beam limit (\(k = 10\)) using Smatch++ as the prediction quality evaluation metric:

Estimator Configuration SPRING IBM-Parser HMG-AMR-T5 HMG-AMR-BART MBSE IBM-Neural All-Parser Mean (\(k=10\)) All-Parser Mean (\(k=3\))
LexSim 0.2209 0.2660 -0.0395 0.0858 0.2294 0.2659 0.171 0.149
EigV-Smatch 0.1956 0.2218 -0.0838 0.0756 0.1871 0.2325 0.138 0.288
EigV-S2Match 0.1912 0.2319 -0.0794 0.0751 0.1931 0.2448 0.143 0.301
EigV-SEMA 0.2504 0.1919 0.0334 0.1080 0.1666 0.1945 0.157 0.252
DegMat-Smatch 0.1971 0.2220 -0.0826 0.0776 0.1878 0.2328 0.139 0.288
DegMat-SEMA 0.2709 0.1984 0.0685 0.1369 0.2061 0.2104 0.182 0.256
Ecc-Smatch 0.1853 0.2051 -0.1136 0.0268 0.1101 0.1768 0.098 0.308
Ecc-S2Match 0.1817 0.2034 -0.1117 0.0231 0.1085 0.1850 0.098 0.319
Ecc-WLK 0.1821 0.1601 -0.0089 0.0168 0.0824 0.0000 0.072 0.274

Key Findings

  • Parsing accuracy correlates positively with reliability, but architectural decoupling exists (RQ1): Top-1 Smatch exhibits moderate positive Spearman correlations with PRR (\(\rho = 0.388\) under Smatch++, \(\rho = 0.317\) under \(S^2\text{Match}\), and \(\rho = 0.360\) under SemBLEU). However, parsers with almost identical accuracy exhibit sharp reliability disparities: MBSE and HMG-AMR-BART both achieve ~0.836-0.838 Smatch, but MBSE records a mean PRR of 0.204 compared to just 0.154 for HMG-AMR-BART, demonstrating that decoding dynamics and model structure govern reliability independently of raw accuracy.
  • Beam expansion weakens uncertainty reliability, favoring moderate beam sizes (RQ2): As beam size expands from \(k=3\) to \(k=10\), PRR degrades across nearly all graph-based estimators (e.g., Ecc-S2Match plummets from 0.319 to 0.098). Larger beams introduce semantic outliers that distort graph consensus; for HMG-AMR-T5, PRR drops below zero at \(k=10\) (e.g., Ecc-Smatch drops to -0.1136), indicating actively harmful rejection rankings. LexSim is the sole exception whose PRR slightly rises (0.149 to 0.171). Moderate beam sizes (\(k \in \{3, 5\}\)) deliver the best trade-off between candidate diversity and calibration quality.
  • Multi-metric evaluation is critical as reliability depends heavily on metric definitions (RQ3): Transition-based parsers (IBM-Parser) show substantially higher PRR under semantic embedding metric \(S^2\text{Match}\) than under Smatch++ (0.264 vs 0.239), whereas SemBLEU lowers all PRR scores by 40-50%. Furthermore, graph-based estimators correlate strongly with each other (\(\rho > 0.87\)), but correlate weakly or negatively with LexSim (e.g., -0.16 between LexSim and EigV-WLK under Smatch++), revealing that surface string overlap captures a fundamentally different uncertainty signal than structural graph matching.
  • SPRING leads overall balance, while IBM-Parser offers maximum beam stability (RQ4): SPRING achieves the highest overall PRR (0.291) while sustaining positive reliability across all beam sizes and metrics, attributable to its graph-isomorphic linearization that preserves candidate coherence. Conversely, IBM-Parser exhibits virtually flat PRR across beam sizes, making it the superior choice when beam robustness is paramount.

Highlights & Insights

  • Spectral graph theory applied to black-box structured uncertainty: By treating candidate graphs as affinity networks, normalized Laplacian eigenvalue deviations (EigV) and geometric eccentricity (Ecc) successfully quantify semantic dispersion without access to model parameters or token probabilities.
  • The "high accuracy \(\neq\) high reliability" caveat: The study reveals that top benchmark performers on Smatch can fail drastically in selective prediction settings. In safety-critical applications, evaluating both Smatch accuracy and PRR reliability is essential.
  • The paradox of beam search diversity in semantic parsing: While larger beam sizes are conventionally thought to improve candidate coverage, in graph parsing they rapidly introduce erratic outlier structures that destabilize spectral estimators, providing fresh insights for constrained decoding design.

Limitations & Future Work

  • Exploration limited to deterministic beam decoding: The study evaluates beam search as the sole candidate generator; stochastic decoding strategies (e.g., nucleus sampling, temperature scaling, or diverse beam search) remain unexamined and may alter candidate distributions.
  • Quadratic scaling of pairwise graph comparisons: Computing \(O(k^2)\) pairwise Smatch alignments is computationally expensive (requiring ~25 CPU hours per parser across beam configurations, totaling 150 hours), presenting latency bottlenecks for high-throughput online serving.
  • Post-hoc nature without training intervention: The framework operates strictly after decoding without modifying training loss functions or architectures; integrating uncertainty regularization directly into parser objectives represents a promising next step.
  • vs LLM Semantic Uncertainty (Kuhn et al., 2023; Lin et al., 2024): While prior work clustered free-text generations using bidirectional NLI or lexical graphs, this paper generalizes black-box uncertainty estimation to formal, directed, rooted graphs, identifying unique structural failure modes under beam scaling.
  • vs AMR Parser Paradigms (SPRING vs IBM-Parser vs HMG-AMR): Seq2Seq parsers (SPRING) preserve global semantic coherence through sequence modeling, transition-based stack parsers (IBM-Parser) offer unmatched beam stability due to structural action constraints, and hierarchical multi-granularity models (HMG-AMR-T5) suffer severe dispersion collapse at higher beam sizes.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ Pioneering black-box uncertainty quantification framework tailored specifically to structured AMR semantic graphs.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive 150 CPU-hour empirical evaluation spanning 6 parsers, 4 beam sizes, 4 estimator families, and 3 benchmark metrics.
  • Writing Quality: ⭐⭐⭐⭐⭐ Rigorous mathematical formulation with clear, intuitive research questions and detailed empirical findings.
  • Value: ⭐⭐⭐⭐⭐ Crucial baseline and methodology for deploying trustworthy, failure-aware semantic parsing systems in high-stakes reasoning pipelines.