Research map / Large language models / Reasoning and chain of thought

Argument Graph Uncertainty: Quantifying Uncertainty from the Logical Structure of Reasoning Chains

NeurIPS 2026 · Large language models › Reasoning and chain of thought · approach: Efficient and adaptive thinking

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Argument Graph Uncertainty (AGU), a post-hoc UQ method that segments a single chain-of-thought into propositional nodes, scores NLI relations to build argument graphs, and maps them to a Dirichlet posterior whose normalized entropy gives uncertainty for MCQA.

Problem

Uncertainty estimation for reasoning models on multiple-choice QA is either costly (multi-sample consistency) or shallow (token-level entropy), and both ignore the logical structure of the reasoning trace.

Approach

Treat a single chain-of-thought as an argument graph: segment it into propositions, use an NLI model to get segment-segment and segment-option edges, aggregate contradiction-adjusted support with coherence weights into Dirichlet evidence, and take normalized entropy as uncertainty. The signal is complementary to consistency-based UQ.

Key results

• On GPQA Diamond, AGU achieves the highest PRR in eight of nine reasoning models (e.g., 0.65 for Nemotron-3 Nano 30B vs 0.24 for consistency).
• Equal-weight blending of AGU and consistency uncertainty gives the best PRR for every model (e.g., 0.68 for Nemotron-30B).
• Windowed segment graph (w=10) matches all-to-all PRR (0.42 vs 0.42 mean) while cutting segment pairs by about 18x.

Surprising findings

• Token-level uncertainty yields negative PRR for GPT-OSS-120B and DeepSeek-R1-Llama-70B, inverting the rejection ordering.
• A deterministic paragraph split matches the LLM segmenter in mean PRR (0.47 vs 0.46).

Limitations

• Depends on quality of segmenter and general-domain NLI scorer, which may misclassify specialized scientific text.
• Evaluated only in the MCQA setting on three benchmarks; generalization to open-ended generation is untested.
• Robustness analysis uses only synthetic perturbations of a single NLI scorer.

Experimental setup

Datasets: GPQA Diamond MMLU-Pro TruthfulQA MC4

Benchmarks: GPQA Diamond MMLU-Pro TruthfulQA MC4

Metrics: PRR Spearman correlation

Baselines: UConsistency (consistency-based vote entropy) UToken (token-probability entropy) segment count (trace length)

Builds on: Dung's abstract argumentation framework evidential deep learning (Sensoy et al.) semantic entropy DeBERTa NLI

Closest papers by meaning

• Towards Trustworthy Knowledge Graph Reasoning: An Uncertainty Aware Perspective (AAAI 2025 · similarity 0.90)
• Diagnosing Multi-step Reasoning Failures in Black-box LLMs via Stepwise Confidence Attribution (ICML 2026 · similarity 0.89)
• Debate on Graph: A Flexible and Reliable Reasoning Framework for Large Language Models (AAAI 2025 · similarity 0.88)
• Sample Smart, Not Hard: Correctness-First Decoding for Better Reasoning in LLMs (ICLR 2026 · similarity 0.88)
• TokUR: Token-Level Uncertainty Estimation for Large Language Model Reasoning (ICLR 2026 · similarity 0.88)
• AbstentionBench: Reasoning LLMs Fail on Unanswerable Questions (NeurIPS 2025 · similarity 0.88)