SymboUQ: Symbolic Uncertainty Quantification for Spatial Reasoning in LLMs

Dahai Yu, Lin Jiang, Rongchao Xu, Guang Wang · 2026

Read SymboUQ: Symbolic Uncertainty Quantification for Spatial Reasoning in LLMs by Dahai Yu, Lin Jiang, Rongchao Xu, Guang Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2608-00417.txt.

Introduction

Yu and co-authors gauge doubt for spatial reasoning in language models with SymboUQ. Fluent traces can hide broken mid-steps. Token-level confidence then fails to gauge final-answer trust. Formal verifiers give stronger proof, but only in part. A parsed claim may yield no firm verdict.

SymboUQ splits two traits apart. One is whether a claim can be stated in the verifier's formal tongue. The other is whether running it gives a firm verdict or an unknown. A Layout Auditor runs ordered spatial claims and pulls feasibility and conflict proof. A label-free profile measures how much of a trace can run at all. A composer merges three score types by verifier reach. On five benchmarks, AUROC rose about 8 percent in relative terms.

Catalog record

CREATORDahai Yu, Lin Jiang, Rongchao Xu, Guang Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2608.00417

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

SymboUQ: Symbolic Uncertainty Quantification for Spatial Reasoning in LLMs Dahai Yu, Lin Jiang, Rongchao Xu, Guang Wang Abstract Although large language models (LLMs) can produce fluent spatial reasoning traces, their intermediate relations may fail to support the final conclusion, making token-level confidence insufficient for final-answer reliability estimation. Existing formal verifiers provide stronger semantic evidence, but their applicability is partial: a parsed claim need not yield a definite semantic verdict. To address this issue, we introduce SymboUQ, a symbolic uncertainty quantification framework that estimates final-answer reliability from reasoning traces by distinguishing symbolizability , whether a claim can be represented in the verifier’s formal language, from semantic determinacy , whether its execution yields an entailed or contradicted verdict rather than an unknown or not-evaluable outcome. SymboUQ comprises (i) a Layout Auditor that executes ordered spatial claims and extracts feasibility, conflict, and repair evidence; (ii) a label-free Determinacy Profile that characterizes effective executable coverage; and (iii) a Determinacy-Aware Reliability Composer that integrates constraint-based, representation-based, and decoding-based scores according to verifier applicability. Extensive experiments on five spatial reasoning benchmarks with four frozen LLM backbones show that SymboUQ achieves approximately an 8 % 8\% relative improvement in AUROC and a 7 % 7\% relative reduction in class-balanced Brier loss over the strongest baseline. Florida State University, Tallahassee, Florida [email protected], [email protected], [email protected], [email protected] Introduction Large language models (LLMs) are increasingly used to reason over textual descriptions of environments, yet a plausible final answer may conceal an invalid chain of relational reasoning. This problem is especially acute in spatial reasoning, where a single incorrect directional relation, containment relation, or state transition can corrupt the inferred spatial configuration while leaving the generated explanation fluent and seemingly coherent. We therefore estimate final-answer reliability using both token-level likelihoods and evidence that the generated reasoning supports its conclusion. Existing uncertainty quantification (UQ) methods estimate reliability from signals such as verbalized confidence, token-level statistics, repeated generations, semantic agreement, and internal representations ( Kadavath et al. 2022 ; Manakul et al. 2023 ; Kuhn et al. 2023 ; Azaria and Mitchell 2023 ) . Moving beyond output-level signals, process supervision and learned step-level verifiers assess intermediate reasoning steps and provide more fine-grained estimates of correctness ( Cobbe et al. 2021 ; Lightman et al. 2024 ) . Formal verifiers provide complementary evidence by explicitly applying predefined rules to generated claims ( Suresh et al. 2025 ; He et al. 2026 ; Manchingal et al. 2026 ) . However, statistical and learned signals may correlate with correctness without directly evaluating the underlying spatial semantics, whereas formal verification applies only when claims can be reliably parsed, grounded, and executed. Even after a spatial relation is successfully extracted, a verifier may be unable to determine whether it is entailed or contradicted because the referenced entities are ungrounded, the available premises are insufficient, or an earlier generated claim has rendered the reasoning context inconsistent. Consequently, parse coverage alone does not indicate how much usable evidence a formal verifier provides. To characterize verifier applicability more precisely, we distinguish between two properties that parse coverage fails to separate: symbolizability and semantic determinacy . Symbolizability refers to whether a generated claim can be translated into the verifier’s formal language, whereas semantic determinacy refers to whether executing the translated claim yields a definite verdict of entailment or contradiction rather than an unknown or not-evaluable outcome. For example, a relation may be translated into a valid spatial constraint but remain semantically indeterminate when the trusted scene provides insufficient information to support or refute it. This distinction identifies two complementary evidence regimes. Constraint-based evidence is most informative when a substantial portion of a reasoning trace is semantically determinate. When many claims cannot be conclusively resolved, even if they are symbolizable, neural and decoding-based signals may provide valuable complementary evidence. Leveraging these complementary evidence regimes to estimate final-answer reliability presents three challenges . First, reliable estimation depends on executing generated claims sequentially while keeping the standing of each claim explicit, so that an unparsed or semantically unresolved claim contributes no positive evidence and any verdict that rests on earlier generated hypotheses is reported as conditional rather than grounded. Second, meaningful use of the execution results calls for a label-free profile that captures symbolizability and semantic determinacy separately from verdict polarity, while explicitly accounting for unresolved claims and claims rendered not evaluable by earlier inconsistencies. Third, the integration of heterogeneous reliability signals should account for variation in the informativeness of symbolic and neural evidence across claims and reasoning traces. To address these challenges, we propose SymboUQ, a symbolic UQ framework for final-answer reliability from spatial reasoning traces. SymboUQ comprises three key components. First, the Layout Auditor compiles the trusted scene description and ordered reasoning trace into a spatial constraint program. It separates the trusted scene from the hypotheses the trace introduces, assigns each generated claim one of four outcomes relative to an explicitly stated context: entailed, contradicted, unknown, or not evaluable, and extracts evidence related to feasibility, conflicts, and possible repairs. Second, the Determinacy Profile summarizes the effective executable coverage of the trace, including the degree of semantic resolution and the loss of coverage caused by an infeasible context. Third, the Determinacy-Aware Reliability Composer (DARC) uses a small labeled target-domain validation split to select useful frozen base scores and align their directions. It integrates constraint-, representation-, and decoding-based evidence through applicability-conditioned interactions to estimate final-answer correctness. Extensive experiments across five spatial reasoning benchmarks and four frozen LLM backbones demonstrate that SymboUQ achieves the strongest overall performance in trace ranking and class-balanced Brier loss under a shared validation-fit protocol. Controlled ablations show that applicability-aware interactions provide consistent improvements beyond score-only target adaptation. Trace-level analyses further show that the utility of constraint-based scores is more closely associated with semantic determinacy than with parse coverage. The key contributions of this work are as follows: • Conceptually, we distinguish textual symbolizability from semantic determinacy, providing a principled basis for determining when verifier-derived evidence from a reasoning trace is informative for estimating final-answer reliability. • Technically, we propose SymboUQ, a symbolic UQ framework comprising three key components: a spatial Layout Auditor, a label-free execution-derived Determinacy Profile, and a Determinacy-Aware Reliability Composer that integrates heterogeneous reliability signals according to effective verifier applicability. • Empirically, across five benchmarks and four LLM families, SymboUQ averages approximately 8\% higher AUROC and 7\% lower class-balanced Brier loss than the strongest external baseline. Problem Formulation Let x=(\eta,q) denote an input consisting of a scene description \eta and a question q . Given x , a frozen language model M generates a reasoning trace r=M(x) containing L tokens. We decompose the trace into an ordered sequence of claims \mathcal{C}(r)=\big((c_{k},t_{k},m_{k})\big)_{k=1}^{K}, (1) where c_{k} is the k -th claim, t_{k}\in\{\textsc{reasoning},\textsc{conclusion}\} indicates its type, and m_{k}\in\{0,1\}^{L} is a binary mask identifying its token span. The final claim is designated as the conclusion. Claim order is essential because the validity and evaluability of c_{k} depend on both the scene description and the preceding claims (c_{1},\ldots,c_{k-1}) . Let y\in\{0,1\} indicate whether the final conclusion matches the benchmark answer after deterministic normalization. Our goal is final-answer reliability estimation, p(r)\approx\Pr(y=1\mid x,r). (2) We consider a target-adapted final-answer reliability setting in which a labeled validation split from the target domain may be used to fit

Read the complete text