Argument Graph Uncertainty: Quantifying Uncertainty from the Logical Structure of Reasoning Chains
Reliable uncertainty quantification for reasoning LLMs is expensive when it requires sampling multiple long chain-of-thought traces, and token-level signals collapse or mis-calibrate on deep reasoning. This paper introduces Argument Graph Uncertainty (AGU), a post-hoc framework for multiple-choice QA that segments a single reasoning trace into propositional nodes, scores pairwise and node-to-option relations with a small NLI model, and aggregates the resulting evidence into a Dirichlet posterior over answer options. The concentration of that posterior, expressed as normalized entropy $U_{\mathrm{AGU}}(R) = H_{\mathrm{norm}}$, yields an uncertainty estimate that is cheap to compute and structurally grounded.
AGU is a thoughtful, well-motivated framework for logical-structure-aware uncertainty estimation. Its strongest empirical result is not standalone dominance but complementarity: an equal-weight blend of AGU and consistency-based uncertainty improves over each individual method on every model tested. However, the paper sometimes oversells its standalone wins: while AGU achieves the highest PRR on eight of nine models on GPQA Diamond, consistency-based uncertainty wins on the ninth and often attains stronger Spearman correlation. The method is also strictly limited to multiple-choice settings because the evidence model $e_{i,k} = \max(0, p_E(v_i, h_k) - p_C(v_i, h_k))$ requires a fixed set of answer hypotheses. Overall, AGU is a valuable ensemble ingredient rather than a general replacement for consistency-based UQ.
The structural design of AGU is elegant. Treating a reasoning trace as a directed argument graph and mapping NLI-based edge scores into Dirichlet evidence parameters $\alpha_k = \alpha_0 + \kappa_{\mathrm{eff}} E_k$ gives a principled way to fuse local step coherence with global consistency. The ablations are notably useful for practitioners: a deterministic paragraph split matches the learned segmenter in mean calibration while removing all segmentation cost, and a windowed segment graph ($w=10$) cuts the NLI stage from quadratic to linear in trace length with essentially no loss in PRR. The framework also degrades gracefully under synthetic NLI corruption.
The headline claims of broad superiority mask important exceptions and scope limits. First, AGU is confined to MCQA: the Node-Option graph assumes a closed set of answer hypotheses $h_k$, so the framework cannot directly handle open-ended generation or free-form reasoning. Second, the default hyperparameter set—while convenient—is not universally optimal; Appendix C.1 shows that four of nine models achieve higher PRR with tuned $\kappa$ and $\alpha_0$ (e.g., GPT-OSS-20B improves from 0.55 to 0.66), meaning reproduction with the stated defaults may underperform on some models. Third, the robustness analysis is purely synthetic: random class flips and Gaussian logit noise do not substitute for evaluation with genuinely out-of-domain or low-quality NLI scorers, which is especially relevant for specialized scientific language.
The evidence supports AGU as a useful structural signal, but the baseline hierarchy matters. Token-level uncertainty is shown to be essentially broken on reasoning models—'Token entropy (top) collapses to near-zero across all models, rendering it uninformative'—so outperforming it is expected rather than impressive. The meaningful competitor is consistency-based uncertainty, and here the evidence is mixed: AGU wins on PRR for eight of nine models, yet consistency wins on Spearman correlation for several models and is the single best signal for DeepSeek-R1-Llama-70B. The paper fairly notes that 'The single exception is DeepSeek-R1-D.-Llama-70B, where $U_{\mathrm{Cons}}$ attains the highest PRR', but that exception undermines claims of uniform dominance. The combination analysis is the most compelling evidence: it provides a clear, reproducible demonstration that logical-structure uncertainty and sample-consistency uncertainty capture different failure modes.
Reproduction is feasible in principle but hampered by the absence of released code, data, or precomputed outputs; the arXiv page lists no associated code repository. The paper does report a fixed hyperparameter set ($\alpha_0=1.0$, $\kappa=12.0$, $\gamma_{\mathrm{conflict}}=1.2$, $\gamma_{\mathrm{asymm}}=1.0$, $\lambda=0.5$) and includes the segmentation prompt in Appendix D, which helps. Still, replicating the exact graph construction, evidence aggregation, and per-option Dirichlet conversion requires careful reinterpretation of Equations (2)–(11). Additionally, the NLI scorer (DeBERTa) and segmenter (Qwen-8B Instruct) choices are specified, but subtle prompting and preprocessing details—such as the exact hypothesis template—must be copied exactly to match reported numbers. The computational cost is low enough that independent groups can likely verify the core claims, yet the lack of a code release adds unnecessary friction.
Reliable uncertainty estimation is essential for deploying large language models in high-stakes reasoning tasks, yet most existing approaches rely on expensive sampling strategies or shallow token-level signals that ignore the internal logical structure of model outputs. We introduce Argument Graph Uncertainty, a post-hoc framework for multiple choice question tasks, that estimates model confidence directly from the logical structure of a single chain-of-thought reasoning trace. Our method uses either a lightweight instruction-tuned model or a simple deterministic rule to segment the reasoning chain into propositional units, then applies a NLI model to infer relational edges and construct two complementary argument graphs over these segments. The resulting edge scores are aggregated into a Dirichlet posterior over answer options, whose concentration yields calibrated uncertainty estimates reflecting both local step-to-step coherence and global logical consistency across the reasoning trace. Evaluated on GPQA, MMLU-Pro and TruthfulQA, our method consistently surpasses token-based and consistency-based uncertainty baselines across multiple reasoning models. We further demonstrate through extensive combination analyses that argument graph uncertainty captures an orthogonal signal to existing approaches, making it a complementary component in uncertainty ensembles. Crucially, our framework requires no additional calls to the evaluated model and relies entirely on small, efficient auxiliary models, producing fully interpretable, per-node uncertainty attributions at low computational cost.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.