Grammars of Formal Uncertainty: When to Trust LLMs in Automated Reasoning Tasks
Debargha Ganguly, Vikash Singh, Sreehari Sankar, Biyao Zhang, Xuecen Zhang, Srinivasan Iyengar, Xiaotian Han, Amit Sharma, Shivkumar Kalyanaraman, Vipin Chaudhary · 2025
Read Grammars of Formal Uncertainty: When to Trust LLMs in Automated Reasoning Tasks by Debargha Ganguly, Vikash Singh, Sreehari Sankar, Biyao Zhang, Xuecen Zhang, Srinivasan Iyengar, Xiaotian Han, Amit Sharma, Shivkumar Kalyanaraman, Vipin Chaudhary (2025) 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-2505-20047.txt.
Introduction
Ganguly and co-authors ask when to trust chat tools in proof-based task work. Chat tools can draft proof specs and open such work to more hands. Yet tools run on odds, while proof needs firm vows of truth. That clash is the core strain the work probes in full. Five top chat tools took a set test of proof drafts. SMT-based drafts swayed truth by field in the test runs.
Logic tasks gained 34.8 percent, while fact tasks lost 44.5 percent. Stock doubt marks, like word odds spread, missed those flaws. A chance grammar frame, PCFG, models tool outs in the work. That frame gives a more fine doubt sort for the outs. Doubt marks prove task-tied: grammar spread fits logic best. A light fuse of marks lets pick checks cut flaws a lot.
Catalog record
| CREATOR | Debargha Ganguly, Vikash Singh, Sreehari Sankar, Biyao Zhang, Xuecen Zhang, Srinivasan Iyengar, Xiaotian Han, Amit Sharma, Shivkumar Kalyanaraman, Vipin Chaudhary |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-20047
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Grammars of Formal Uncertainty: When to Trust LLMs in Automated Reasoning Tasks Debargha Ganguly, Vikash Singh, Sreehari Sankar, Biyao Zhang, Xuecen Zhang, Srinivasan Iyengar, Xiaotian Han, Amit Sharma, Shivkumar Kalyanaraman, Vipin Chaudhary Abstract Large language models (LLMs) show remarkable promise for democratizing automated reasoning by generating formal specifications. However, a fundamental tension exists: LLMs are probabilistic, while formal verification demands deterministic guarantees. This paper addresses this epistemological gap by comprehensively investigating failure modes and uncertainty quantification (UQ) in LLM-generated formal artifacts. Our systematic evaluation of five frontier LLMs reveals Satisfiability Modulo Theories (SMT) based autoformalization’s domain-specific impact on accuracy (from +34.8% on logical tasks to -44.5% on factual ones), with known UQ techniques like the entropy of token probabilities failing to identify these errors. We introduce a probabilistic context-free grammar (PCFG) framework to model LLM outputs, yielding a refined uncertainty taxonomy. We find uncertainty signals are task-dependent (e.g., grammar entropy for logic, AUROC>0.93). Finally, a lightweight fusion of these signals enables selective verification, drastically reducing errors (14-100%) with minimal abstention, transforming LLM-driven formalization into a reliable engineering discipline. 1 Introduction Formal methods offer robust mathematical guarantees for system reliability ( Huth and Ryan 2004 ) , but their widespread adoption is impeded by high expertise and labor demands, traditionally limiting their application to safety-critical domains where failures have catastrophic consequences ( Clarke et al. 2018 ; Woodcock et al. 2009 ) . Concurrently, Large Language Models (LLMs) have emerged with a remarkable ability to generate formal artifacts such as code, proofs, and specifications ( Brown et al. 2020 ; Chen et al. 2021 ; Jiang et al. 2023a ) , potentially democratizing formal methods ( Hou et al. 2023 ) and finding new roles in formally correct reasoning and LLM verification ( Ganguly et al. 2024 ; Pan et al. 2023 ) . However, these two approaches embody fundamentally different epistemological paradigms. Formal methods are rooted in deterministic logical calculi, where conclusions derive necessarily from premises via unambiguous inference rules. LLMs, in contrast, operate probabilistically, representing knowledge as distributions over tokens where multiple, even contradictory, outputs can possess non-zero probability ( Wei et al. 2022a ) . This inherent tension presents a core challenge: how can we harness the generative power of LLMs for formal reasoning while upholding the rigorous guarantees that define formal verification’s value? The central thesis of this paper is that the inherent probabilistic uncertainty in LLM outputs for formal reasoning tasks, particularly when generating formal artifacts like SMT-LIB programs, is not a mere nuisance but a valuable source of information for guiding verification. Existing methods often ignore this by selecting only the highest-probability output ( Chen et al. 2022 ) , a simplification that we argue undermines the rigorous standards required for formal reasoning. In contrast, we demonstrate how to systematically capture and analyze this output uncertainty by modeling LLM-generated SMT-LIB program distributions with Probabilistic Context-Free Grammars (PCFGs). Instead of focusing on a single output, we analyze ensembles of LLM-generated SMT-LIB programs, treating these as samples from the model’s internal probability distribution ( Kadavath et al. 2022 ) , which we then approximate by applying PCFGs to the ensembles. This approximation not only identifies the most likely solutions but also reveals strategic diversity, common structural motifs, and areas of high model uncertainty. Deriving a comprehensive suite of metrics from this structured, quantifiable understanding of uncertainty can then directly guide the verification workflow—for instance, by assessing artifact reliability, focusing human review on more ambiguous or structurally complex candidates, and improving error detection strategies. The core contributions of this paper are: • We systematically evaluated frontier LLMs on four formal reasoning datasets, finding SMT-based autoformalization significantly boosted accuracy on tasks like ProofWriter (+34.8%) but harmed others like FOLIO (-44.5%), thus quantifying LLM-driven formal verification’s failure modes. We then demonstrate that known uncertainty quantification techniques do not capture enough information to identify errors in FV artifacts. • Introduce a probabilistic framework using probabilistic context-free grammars to model LLM-generated SMT-LIB programs, enabling mathematically sound uncertainty quantification and bridging neural models with formal verification. • Developed and evaluated 25 uncertainty metrics, revealing a refined taxonomy (epistemic-knowledge, epistemic-procedural, recursive-complexity, capacity-limited) that offers a more nuanced understanding of uncertainty in neurosymbolic systems than the traditional epistemic/aleatoric dichotomy. • Demonstrated that formal reasoning uncertainty is task-dependent and introduced a lightweight, model-agnostic fusion of these varied uncertainty signals. This approach outperforms individual metrics, improves calibration, enables selective verification to cut error rates by 14-100% with minimal abstention, and suggests modality-aware architectures for enhanced reliability. 2 Methodology Generating formal artifacts using ad-hoc Domain-Specific Languages (DSLs) introduces significant engineering friction. This friction arises from the need to redesign generators, models, and parsers for syntax changes, and it also complicates debugging erroneous outputs (e.g. syntactically incorrect FV artifacts). To mitigate this overhead, we adopt the stable, widely supported SMT-LIB standard as a common intermediate representation targeting SMT solvers. In this section, we consequently present a theoretical framework linking language models and verification to analyze LLM-generated SMT-LIB program distributions, enabling principled reasoning about their uncertainty. Problem Setup We formalize the probability space over SMT-LIB programs. Let \Sigma be a finite alphabet. The set of all finite strings \Sigma^{*} forms a measurable space (\Sigma^{*},\mathcal{F}) , where \mathcal{F} is the \sigma -algebra generated by cylinder sets (strings sharing a common prefix w ). The SMT-LIB language L_{SMT}\subseteq\Sigma^{*} , approximated by its standard context-free grammar G_{SMT} , is measurable in \mathcal{F} . For a task T and an LLM with parameters \theta , the LLM induces a probability measure \mu_{T,\theta} on (\Sigma^{*},\mathcal{F}) . The measure over valid SMT-LIB programs is then the conditional measure \mu_{T,\theta,SMT}(A)=\frac{\mu_{T,\theta}(A\cap L_{SMT})}{\mu_{T,\theta}(L_{SMT})} for A\in\mathcal{F} . This definition requires \mu_{T,\theta}(L_{SMT})>0 , a reasonable assumption that is empirically validated, as LLMs are generally trained to generate syntactically valid code and formal specifications. Modeling Background: To model distributions over structured programs like \mu_{T,\theta,SMT} , we employ Probabilistic Context-Free Grammars (PCFGs). PCFGs extend standard Context-Free Grammars (CFGs) by associating probabilities with their production rules. Formally, a PCFG is a 5-tuple G=(V,\Sigma,R,S,p) , where V is a finite set of non-terminals; \Sigma is a finite set of terminals disjoint from V ; R\subseteq V\times(V\cup\Sigma)^{*} is a finite set of production rules; and S\in V is the start symbol, such that (V,\Sigma,R,S) collectively form a CFG. The fifth component, p:R\rightarrow[0,1] , is a probability function assigning a probability p(r) to each rule r\in R . For each non-terminal A\in V , these probabilities must satisfy \sum_{r\in R_{A}}p(r)=1 , where R_{A} denotes the set of rules with A as their left-hand side. The probability of a derivation \pi that applies rules r_{1},\ldots,r_{k} in sequence is p(\pi)=\prod_{i=1}^{k}p(r_{i}) . Consequently, for any terminal string w\in L(G) , where L(G) is the language generated by the underlying CFG, its probability under G is \mu_{G}(w)=\sum_{\pi\in\Pi(w)}p(\pi)=\sum_{\pi\in\Pi(w)}\prod_{r\in\pi}p(r) , where \Pi(w) represents the set of all leftmost derivations of w from S . It is important to note that a PCFG G defines a consistent probability measure (i.e., \sum_{w\in L(G)}\mu_{G}(w)=1 ) if and only if the spectral radius of its moment matrix M_{G} is less than or equal to 1. This condition ensures that probabilities are well-defined and sum to one across the entire language generated by G . Figure 1: Analysis