Grammars of Formal Uncertainty: When to Trust LLMs in Automated Reasoning Tasks
Authors: Debargha Ganguly
Vikash Singh
Sreehari Sankar
Biyao Zhang
Xuecen Zhang
Srinivasan Iyengar
Xiaotian Han
Amit Sharma
Shivkumar Kalyanaraman
Vipin Chaudhary
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Models
Formal Verification
Uncertainty Quantification
Stochastic Context-Free Grammars
Automated Reasoning
SMT-based Autoformalization
Selective Verification
Primary area: probabilistic_methods
TL;DR: PCFG-based framework characterizes uncertainty in LLM formal reasoning, enabling selective verification that reduces errors while minimally abstaining.

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.

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
CCase Westem Reserve University "Microsoft Corporation "Microsott Research
{debargha, vikash, sreehari, bwz297, wxweeerrr,,xz297,,, xxz1037, xhan, vipin)@case edu
(sriyengar, amshar, www.alaaaemmiiraeeaeeeaae crwsoft.
https://github. com www./ooo///eeee www.areaaaggrraeeeeeeeeeeee commmars-formaae uncertainty (Quantify uncertainty)
https:// bttpp://giihub.... www www/Deeargaaaee./...oo.oo/. htwpaaa///poooofffoooooooo (Auto formalization library)
Abstract
Large language models (LLMs) show remarkable promise for democratizing automated reasoning by generating formal specifications. However, 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 's domain-specifie impact 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 probabilistic context- grammar (PCFG) framework to model LLM outputs, yielding a refined uncertainty taxonomy. We find uncertainty signals task-dependent (c.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 L-d-rrieen formalization into a reliable engineering discipline.
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 al., 2018, Woodcock et al., 2009]. Concurrently, Large Language Models (LLMs) have emerged with remarkable ability to generate formal artifacts such as code, proofs, and specifications [Brown et al., 2020, Chen 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 approaches embody fundamentally different epistemological paradigms. Formal methods are rooted in deterministic logical calculi, where conclusions derive necessarily from premises via unambiguous inference rules. L.Ms,, in contrast, operate probabilistically, representing knowledge as distributions over tokens where multiple, even contradictory. outputs can possess non-zero probability (Wei al., 2022a]. This inherent tension presents core challenge: how can 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-probabile output [Chen et al., 2022], a simplification that we argue undermines the deterministic correctness guarantees required for formal verification. In contrast,
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

demonstrate how to systematically capture and analyze this output uncertainty by modeling LLM-generrin SMT-LIB program distributions with Probabilistic Context-Free Grammars (PCFGs). Instead of focusing on a single output, we analyze ensembles of L.LM-generatdd 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 high model uncertainty. Deriving 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 tasks like ProofWriter (+34.8%) but harmed others like FOLIO (-4,.5%), thus quantifying LLM-driven formal verification's 's failure modes. We then demonstrate that known uncertainty quantification techniques do not capture enough information to identify errors in FV artifacts.
Introduce framework using probabilistic context-free grammars to model LLM-generate, 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 mobistmic-knowledee epistemic
recursive-compleee complexity, sapacity-limited) that offers more nuanced understanding procedural, epistemie-proceeuraal of uncertainty in neurosymbolic systems than the traditional epistemic/aleatoric dichotomy.
Demonstrated that formal reasoning uncertainty is task-dependent and introduced a lightweight, model-agmostic fusion of these varied uncertainty signals. This approach outperforms individual metrics, improves calibration, enables selective verification 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-Speeifit Languages (DSL.s) 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 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 uncertainty quantification.
We formalize the probability space over SMT-LIB programs. Let Σ be a finite alphabet. The set of all finite strings Σ* forms measurable space (F",F), where F is the a-aleerra generated by cylinder sets (strings sharing a common prefix w). The SMT-LIB language LSMr C Σ', approximated by its standard context-free grammar GSMT, measurable in F. For task T and an LLM with parameters 0, the LLM induces probability measure 1TT on (Σ* F). The measure over valid SMT-LIB programs is then the conditional measure (T. >>00 0, reasonable assumption that is empirically validated, as LLMs are generally trained to generate syntactically valid code and formal specifications.
Problem Setup:
(An (iLss)///ur/// ( for A F. This definition
requires
Modeling Background: To model distributions over structured programs like p.S.T 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.,, P.S.p) where V is a finite set of non-terminals; Σ is a finite set of terminals disjoint from V: R V x (VUE)* is a finite set of production rules; and S E V is the start symbol, such that (V.E, collectively form a CFG. The fifth component, p: R + [0, is probability function assigning a probability p(r) to each rule r R. For each non-terminal AE V, these probabilities must satisfy rules with as their left-hand side. The probability of a derivation и that applies rules ri,...,T in sequence p(r:).
((r) where RA denotes the set of
is p(T ( i Consequently, for any terminal string w E L(G), where L(G) is the language gen- erated by the underlying CFG, its probability under G is μa(w) = -
P()))))) where (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.c., En EweL(cyHo(u)) = 1) if and only if the spectral radius of

---

Exemple Premisei "Everyote who studies nath or physics and works hard will succeed'
Samplng Generated SUT-LIB Programa
Systzs (AST))
Tack brm
Rute Usuge Statitics
Vee The
22 Uid) staplic
Deetediie oear (13
maiig
Uscetabryy Gxartfication (U3)
10
PCFG Mesrio
04407
Prrsen y
1//00
Specha Raatux
6.0079
PORD--RAAN LUD acchimand (1-0 AUROC (Prootiotttr GUNTEAN PEETEDSS
Figure 1: Empirical analysis of L.M--generate SMT-LIB formalizations for the statement "Everyone who studies math or physics and works hard will succeed." " The figure illustrates (left) syntactic and logical forms in SMT-LIB, (center) multiple LLM-generated formal programs and their parsed Abstract Syntax Trees (ASTs), and (right) rule-usage statistics learned by Probabilistic Context-Free Grammar (PCFG). With sufficient sampling, ruleooccurrence frequencies define a probability distribution from which structural uncertainty metrics entropy, perplexity, KL divergence, and spectral radius are computed. These PCFG-derived uncertainty measures correlate strongly with correctness and formalization reliability, achieving AUROC = 0.93 on ProofWriter (grammar entropy), with ensemble signals reducing 14- 14-100% errors through selective verification. The analysis uses only observed LLM outputs (i.e., no synthetic or simulated data) to quantify uncertainty formal reasoning.
its moment matrix Mg 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.
Note: Constrained decoding with deterministic CFGs zeroes out grammar- invalid tokens at inference to enforce syntax (e.g., JSONcodee). Unlike our PCFG-based UQ. these methods (i) ensure syntax validity rather than quantify uncertainty among already well-formed but potentially semantically wrong SMT-LIB outputs; and (ii) require white-box token probabilities, or modifications to the LM head, unsuited to black-box frontier API. We analyze valid outputs without changing model internas..
To connect the theoretical LLM distribution PTA..M with a tractable prob- abilistic model, we estimate parameters for PCFG. We use the SMT-LIB v2 grammar GSNT = (VSMT, ESMT, RSMT, SSMT) as its structural basis. We now generate N SMT-LIB program samples PN= = (PP...,PP' from the target LLM (parameterized by 6) and parse them using GSMT. This yields a set of parse trees II(P,v from the successfully parsed programs. From each parse tree π e II(,N) we identify and record every applied production rule r= (A- ((A+))) +) RRMT.. This record typically includes the rule itself, its source program identifier, structural context (such as depth). and optionally, the corresponding source text mapping for qualitative analysis. This data collection also allows for extracting richer contextual features than those used by standard Maximum Likelihood Estimation for estimating the rule probability function p: RSAr [0.1] from these rule application frequencies.
Approximation:
Maximum Likelihood Estimation (MLE) is used to estimate rule probabilities p(r) using counts from I((x)). (Note that MLE itself is not an uncertainty quantification metric; rather, it is the method used to estimate the PCFG rule probabilities from which our uncertainty metrics are subsequently calculated.) Given total application counts C(r) for a rule r=
r= (A- 3) and C(A) = (([A)=EEER, EMER, C(r') for its left-hand side (LHS) nonmtnaminal A (where RA= (r' E ReMr left(r")= = A}), the MLE is its relative frequency (aaee(rr)((r/(())) defined if C(A) > 0. If C(A)= =0, rules in RA are assigned a uniform probability R/ For independent and identically distributed (i.idd) samples Py from pr,,,,sar these estimated probabilities (r) converge almost surely (a.s.) to (r) as N 00. The limits p (r) are the parameters of the -asrr-baed PCFG that is closest Kullback-Leiblerr (KL. divergence to the true distribution UT. (i.e., p" argmin, DrL. D (UT, |l (c(P))). For finite N, additive (Lidstone) smoothing with B, > 0 (e.g.. 8, = 1 for Laplace smoothing) addresses problematic zero counts where C(r) =0 but ((8.)
C(A)> 0. yielding PN (r) = (()())))))((((()+))))))))))
Theorem 1 (Coverage Guarantee). Let n be distribution on discrete sample space Σ", with Shannon entropy H()) = --E -E M(z) log logzH(z). Suppose we draw N i.i.d samples from p. Then, for any measurable subset ACE with (u(A) (A))=,, the probability that none of the N samples land in A is at most No
exp
provided N is sufficiently large. Equivalently, the probability failing to sample at least ( -
3

---

one point in every region of mass is at most (NNe--N//" Moreover, the largest e for which this "miss probability" is üself at most satisfies N
where W-) is the Lambert W W-function. which vanishes at rate on the order of In(N)/N. This result
2(((e) W
N
2
As N grows large, x builds upon foundational principles of information theory and typical set arguments |Cover, 1999). Proof is provided in the appendix.
2B(u) N
N 2
This theorem guarantees N samples can represent the LLM's implicit uncertainty via the output distribution, thereby providing the first formal bridge linking the sample count (N), the distribution's 's Shannon entropy, and the probabilistic bound on covering the space of possible formal programs.
Our PCFG construction and uncertainty quantification N= 100 SMT programs and induce a question-specific PCFG from that ensemble alone. Metrics from this PCFG (as described in next paragraphs) are then used to predict correctness for that same question. Our method therefore naturally adapts to each reasoning problem's 's unique characteristics without training.
instance-level. For each question, generate
2.1 Probabilistic Context-Free Grammar (PCFG) Derived Metries
We derive several PCFG metrics to quantify different facets of uncertainty, using established notation (e.g., RA for the set of rules expanding non-terminal A). These metrics can be organized into five conceptual categories that capture complementary aspects of uncertainty in the presence of formal well-defined grammar for the language: (1) Static grammar structure metries describe the grammar's 's architectural scale; (2) information-theoreee measures quantify probabilistic uncertainty through entropy and divergence; (3) Spectral properties characterize recursive structure and derivation complexity; (4) Self-consistency measures assess agreement across multiple LLM generations; and (5) Ensemble methods combine signals for robust prediction. We detail each category below.
(1) Static Metrics for Grammar Structure and Complexity Basic structural properties of the grammar GSMT provide a foundational understanding of its scale and potential complexity. These include the number of non-terminals ( (VsMr) and rules (RsMrT), the average number of rules per non-terminal [Rswrr)) ) and the average right-hand side (RHS) length [RRArr -A-SEReeMI 138. where |@] denotes the [Vaur
length of 3). Further metrics cover the maximum branching factor (TaXAEVEMT RAD. and the detection of various forms of recursion (e.g., left-recursion A - Ay or right-recursion A)). These metrics collectively characterize the grammar's ' static architecture.
Beyond static metrics, analyzing the set of all rule probabilities pute descriptive statistics such as mean, median, minimum, maximum, standard deviation (P)).. skewness (?a (P)), and kurtosis (72(P)). These statisties characterize the shape and spread of the leamed probabilities.
(1p(A++)) BE RSMr} we com-
(2) Cifrmattion-Thorrett Measures Information theory provides principled ways to measure the uncertainty associated with probabilistic choices within the grammar. The Shannon Entropy per Non-terminal, for each AE VSMT,, quantifies the average uncertainty (in bits) in selecting a production rule from RA: (A)= (A)==EAAAPER) EA-BER, P(A 3))08=p(A + -3) A higher H(A) indicates greater uncertainty or variability in the expansions of A. The Rényi Entropy per Non-terminal, (A),), generalizes Shannon entropy and is parameterized by an order a a22 0. For a 1: (A) = I-a log, EA- A- R. pl - 3) Key special cases include Shannon entropy (A) (A) as a - 1), max entropy (Ho = log, R. for a a= 0, reflecting the number of choices), collision entropy (A2 = = log, EA- 3) for a= 2, sensitive to rule choice repetition), and min-entropy (A)) = max-
for a co, determined by the most probable rule). Calculating Rényi entropy for different values (c.g.. 0.5.2) provides a richer characterization of the uncertainty profile than Shannon entropy alone.
The Overall Grammar Eutropy is typically defined as the weighted average of the Shannon entropies of its nontterminals, H (A), where weights π (A) correspond the stationary distribution or expected frequency of non- monnteeminal A in derivations starting from Ssarr:
- π (AA) The frequencies (A) can be estimated iteratively. HG)) represents the average uncertainty per derivation step across the entire grammar. Perplexity, PP( measures how well the PCFG predicts derivations and the exponen- tiated grammar entropy: PP(G)=2 It can be interpreted as the effective average number of choices the grammar presents at each derivation step, weighted by likelihood; lower perplexity indicates a more pre- dictable grammar. The KI. divergence, PKI(pp. | loog Ral- H (AA, quantifies the inefficiency (in bits) of assuming uniform rule distribution (U 8)= 1/ [RA) for a non-terminal A compared to using
4

---

the true PCFG probabiliities
The overall grammar KL divergence from uniform, (G]() quantifies the PCFG's deviation from maximum uncertainty.
EvEVS ASV TI (A))
Finally, we hypothesize novel composite metric, NS) for probabilistic uncertainty and structural complexity. This metric, which ranges from O to 1, combines normalized grammar entropy with a factor reflecting the grammar's recursive structure (via its spectral radius B(B) is calculated as NSU I (G) Eratio X KS factor. The entropy ratio Eratio = H()) (mxx(G) E [0,1] uses the maximum grammar entropy Hmax (G) = EAEVeMr (AA)logy)RA (assuming uniform rule choices). The spectral
factor Sfcter = pl /(BBB(/ (1++
(0.1). The motivation was to link higher NSUI values indicate greater probabilistic uncertainty via structural/recursive complexity.
(3) Spectral Properties The spectral radius of the grammar's mean matrix (often referred to the Jacobian matrix in this context). B E RR/vrrr Ix kiVsrrl offers insights into its recursive structure and complexity. An element By, is the expected number of times non-terminal A, appears on the right-hand side (RHS) of production chosen for A.: By -A.BBERA P(A, ++ B) x (oouu((AA where count (A, is A,
occurrences in B. The spectral radius (( = max[[>] det(B - XI) = 0} is B's maximum absolute eigenvalue. Typically, p(B) < 1 indicates 'proper' grammar with finite expected derivation lengths, while pl B) 2 suggests potentially unbounded derivations or higher complexity, contributing to structural uncertainty. This spectral radius is also key component of the NSUI metric (introduced later in this section).
(4) Self-Consistency (SC) metries quantify agreement across multiple generations from the L.M. Text SC reflects solution consistency (e.g., via majority vote) across multiple LLM textual outputs, while SMT SC measures it (c.g.. via SMT solver agreement) across diverse LLM-ggnerated SMT-LIB programs for the same prompt, adapting principles from [Wang et al., 2022].
(5) Ensemble Predictors We also implement four distinct ensemble predictors for enhanced uncertainty quantification. These are: (1) Ensemble Simple, an unweighted average of a key subset of metrics; (2) Ensemble Average, a comprehensive unweighted average of all metric scores; (3) Ensemble Weighted, where individual metric contributions are varied based on validation performance or theoretical importance; and (4) Ensemble MI., a meta-maching learning model (e.g., logistic regression) trained on the vector of metric scores to predict errors. This approach aims to improve overall predictive accuracy, calibration, and robustness by combining varied uncertainty signals.
3 Results
We have evaluated five frontier LLMs, namely 03-mini, DeepSeekR1 (with CoT enabled [Wei et al., 2022b)), DeepSeek-v3-04-211 Gemini Flash 2.0 & Lite (non-reasoning), on four datasets which are widely adopted reasoning tasks; StrategyQA [Geva al., 2021], ProntoQA. [Saparov and He, 2023], ProofWriterTTffoon et al., 2021] and FOLIO [Han et al., 2024]. Our experimental setup involves two distinct sampling configurations: For the initial benchmarking comparison of Text versus SMT reasoning approaches (Tab. 1), we generate N = 5 samples per question. For our core uncertainty quantification analysis (Tables 4 and 5), we generate a much larger corpus of N = 100 SMT-LIB program samples per question to induce statistically meaningful PCFGs for each reasoning instance (as detailed in Appendix A.2). From these samples, answers were derived via: 1) Text: direct LLM output (intrinsic reasoning over text); 2) SMT: LLM--genratee SMT-LIB solved by Z3 (autoformalization)) Notably, SMT-LIB generation required significantly less effort (more syntactically valid programs in fewer attempts) and used dramatically fewer tokens per prompt compared to [Ganguly et al., 2024], while also offering multi-solver interoperability.
3.1 Benchmarking SMT based Formal Reasoning
Table 1: Benchmarking accuracy of frontier LLMS using direct text output (Text) versus SMT-LIB generation solved by Z3 (SMT). No approach universally outperforms the other across all models and datasets. Finer grained results are available in the supplementary material.
ACCURACY
Strategr SMT
ProntoQA
ProofWriter SMT
FOLIO SMT
Text
Text
03-mini
0.7828
0.7980
.001522
1.0000
0.9950
0.0020
0.8893
0.9418
-0.0244
0.4450
0.5000
0.4450
DeepSSeelv33
0.8292
0.6720
0.1572
1.0000
0.450]
0.5499
0.8057
0.5800
0.2257
0.9333
0.5961
0.3372
DeepSeekk RI
0.8580
0.7760
0.0820
0.9939
0.7440
0.2499
0.9423
0.4935
0.4488
0.9252
0.5200
0.4052
Flash 2.0
0.7188
0,5360
0.1828
0.9820
0.9000
0.0820
0.6660
-0.1760
0.5625
0.3385
Flash 2.0 Lite
0.6760
0.4500
0,2260
0.9980
0.9980
0.0000
0.4060
0,7540
-0.4480
0.9017
0.7321
0.1696
5

---

On ProofWriter, a task closely aligned with symbolic logic, SMT-based methods yielded substantial improvements for three models, particularly benefiting those that struggle with direct formal reasoning. Conversely, on ProntoQA and FOLIO, direct textual reasoning consistently outperformed SMT across most models, suggesting that for these QA tasks, the overhead introduced during autoformalization outweighs potential benefits. StrategyQA showed mixed results, with 03-mini slightly benefiting from SMT while other models performed better with direct reasoning.
The SMT approach systematically alters error profiles compared to direct reasoning, often trading precision for recall. For struggling models, autoformalization often increases recall at the cost of precision, yielding more formal answers but also more false positives, tendency consistent with LLMs' documented proclivity toward proving satisfiability in [Ganguly al., 2024]. On ProofWriter, where SMT generally helped. performance gains stemmed from simultaneous improvements in both precision and recall, indicating the approach successfully addressed fundamental reasoning errors. Conversely, on datasets where direct reasoning excelled, SMT's underperformance typically manifested as reduced recall, suggesting failures in the formalization process resulted in missed correct answers.
Our results reveal predominantly epistemic uncertainty in both reasoning approaches. Direct reasoning fails through knowledge gaps and procedural errors, while SMT introduces formalization errors when translating to formal specifications. This explains task-dependent performance: SMT benefits tasks with explicit premises (ProofWriter) by isolating deductive reasoning, while knowledge-intenee expose formalization bottlenecks. These findings highlight the critical need for Uncertainty Quantification on LLM-ggeerated formal artifacts to prevent upstream formalization errors from propagating through otherwise sound solvers.
tasks (StrategyQaa QA)
3.2 Benchmarking Uncertainty Quantification Techniques
Experiment Setup To evaluate uncertainty quantification (UQ) methods for identifying prediction erros, we examine several facets: Error Discrimination utilizes the Area Under the Receiver Operating Characteristic Curve (AUROC) to assess uncertainty scores distinguish correct from incorrect predictions; a higher AUROC signifies better uncertainty error aligmment. Selective Prediction Utility employs the Area Under the Risk-Coverage Curve (AURC) to measure practical risk mitigation via abstention (including analysis of optimal abstention percentages, associated error rates, and relative eтror reduction); lower AURC indicates effective error identification, improving performance on retained samples. Finally, Calibration Assessment evaluates the probabilistic reliability of confidence scores using metries like Expected Calibration Error (ECE), Reliability Diagrams, and the Brier Score; lower ECE and Brier scores denote better calibration, where predicted confidence accurately reflects empirical correctness rates.
Table 2: Token-level baseline uncertainty quantification techniques and their results at detecting autoformalization errors w.r.. ground truth for DeepSeek-v3-03224 across reasoning datasets. While conventional metrics (AUROC, ECE, Brier) show moderate performance, they inadequately capture the distinct epistemic uncertainties formalization versus reasoning processes. Notably, no UQ method consistently excels across tasks The uncertainty-awarc abstention metrics reflect how the model can selectively answer questions by applying an optimal uncertainty threshold (Opt. (ht.Threeh) that minimizes error rate (Err@1 I`) and maximizes eтror reduction (RelEmrRed) compared to answering all questions. This suggests the need for specialized UQ approaches that explicitly model the distribution of formal artifacts. DeepSeekv3 is the only model we examined that provides token logprobs.
AUROC
Brier
Opt
EreT
RelEimRed
Strategy QA
Entropy
0,5872
0.1415
0.2433
0.2399
0,0500
0.3221
0.0180
Peplexity
0.6179
0.08012
0.2218
0.2218
0.5000
0,2520
0.2317
Kurtosis
0.6227
0,3038
0.3075
0.2236
0.5000
0,2440
0.2561
ProntoQA
Entropy
0.5622
0.1395
0,2685
0.4585
0,0500
0.5408
0.0166
Peplexity
0.6118
0.1009
0.2522
0,4218
0,0500
0.5365
0.0244
Kurtosi
0.6078
0,2390
0.2990
0.4265
0.2000
0.5102
0.0722
ProotWriter
Entropy
0.1666
0.2761
0.3938
0,0500
0.4105
0.0226
Perplxiit
0.5893
0,2430
0,3021
0.3214
0L4000
0.3633
0.1349
Kurtosis
0.1657
0.2705
0.4500
0.3564
0.1515
FOLIO
Entroyy
0.7001
0,2101
0.2465
0.4737
0.5000
0.4767
0.2679
Perplxiit
0,5609
0.2385
0.2926
0.5514
0,0500
0.6380
0.0202
Kurtosis
0,5548
0.1761
0.2428
0.5560
0.0500
0.6319
0.0296

---

We benchmarked our syntactic PCFG approach against semantic entropy and clustering [Kuhn et al., 2023, Farquhar et al., 2024] using entailment checking with independent prompts to DeepScek-v330333 comparing each generated SMT program with the original question as context to determine semantic e
equivalence classes. Table presents results across all four datasets. We evaluated: (1) Discrete Entropy over
semantic clusters, (2) Continuous Entropy using Monte Carlo sampling (MC), (3) Continuous Entropy using Rao-Blackwellizer estimator (RAO), and (4) the raw number of semantic clusters as an uncertainty signal. The semantic methods failed to provide superior uncertainty signals, yielding near-random performance (AUROC s 0.5-0.6) and no practical error reduction (poor AURC). Computationally, semantic clustering is inefficient, requiring (MM)) undecidable comparisons, whereas PCFG method is efficient. We also confirmed that standard NLI models (DeBERTa) fail completely, as they cannot parse formal SMT artifacts.
Table 3:
Baseline semantic entropy based uncertainty quantification techniques for detecting auto- formalization errors with respect to ground truth using DeepSeck-v3-0325 While moderate performance is observed in limited configurations, semantic uncertainty does not distinctly capture epistemic uncertainties in autoformalization The artificially high AUROC on FOLIO reflects disproportionate error rates rather than effective uncertainty quantification, as evidenced by high AURC values indicating poor risk-coverage
tradcoffs.
Datasel
Metric
AUROC
ECE
Brier
AURC
OpL'
Err@T
RelEarReed
StratgyQAA Discrete Entropy
0.5341
0,2345
0,3517
0,2724
0,0500
0.3263
0:0051
Continuous Entropy MC
0.5502
0,2050
0.2669
0.2555
0.0000
0,3280
0,0000
Continuous Entropy RAO
0,5801
0.2744
0,2987
0.2432
0,0000
0.3280
0,0000
Num. semantic chusters
0,5331
0,2160
0.3410
0,2681
0.0500
0.3263
0.0051
ProntoQA
Discrete Entropy
0.6273
0.0788
0.2955
0.4453
0,0000
0.5507
0,0000
Continoous Entropy MC
0,5015
0,2900
0.3459
0.4910
0.1000
0.5461
0.0084
Continuous Entropy RAO
0.5779
0,4340
0,4515
0,4609
0,0500
0.5480
0:0049
Num. semantic clusters
0.5453
0.1258
0.3195
0.4585
0,1000
0.5507
0,0001
ProofWriser Discrcte Entropy
0,5717
0.2256
0,3316
0.3254
0,0000
0,4200
0,0000
Continous Entropy MC
0,5127
0.2340
0.3091
0.3611
0.3500
0.01
Continuous Entropy RAO
0.5966
0,3053
0,3469
0,3178
0,0000
0,4200
0.0000
Num. semantic clusters
0.5645
0.1775
0.3251
0.3522
0.0000
0,4200
0,0000
POLIO Discrete Entropy
0,7542
0,2508
0.2541
0,4506
0,0500
0.6584
0.0007
Continuous Entropy MC
0,6811
0.4571
0,4186
0,4790
0.0030
0.6588
Continuous Entropy RAO
0.7564
0.5383
0.5194
0.4364
0.0000
0.65888
0.0000
Num. semantic clusters
0.3132
0.2886
0.4496
0.0000
We expanded and evaluated our uncertainty metrics in two distinct prediction tasks: (1) whether LLM-generated SMT programs, when executed by Z3, would yield the correct ground truth answer (as prior baselines), and (2) whether the SMT output would be consistent with the model's own natural language reasoning.
Evaluation tasks:
Experiments for model and dataset combinations were chosen where performance gap was observed, with N=100 samples, thereby making UQ analysis meaningful, but where the SMT performance was not close to random guessing. Our argument here is that because we are relying on information within the FV artifacts, and those artifacts are not well-calibrated for the task (i.e., operating at the level of random guessing), we cannot extract information about failure from them. We also employed temperature sampling with values uniformly distributed between 0.1 and 2.0 to ensure diverse exploration of the LLM's output distribution
Task- Desk-Dependent Signal Dominance in SMT vs Ground Truth Prediction:
Knowledge-Intensinn Reasoning: For Strategy QA, cross-modal agreement metrics consistently dominated. 03-mini showed strong performance with grammar entropy AA740C=0.7448, AURC=0.1113) and text consistency (AUROC=0.736) 3.669,,,....... AURC=0. 1081). For DeepSeek-R1, R1, text consistency substantially outperformed all pure PCFG metrics (AUROC=0.7835 certainty in world knowledge as the primary correctness bottleneck as these cross-modal metrics effectively gauge if the SMT formalization aligns with the I.LM's initial (potentially flawed) semantic interpretation.
AURC=0.0983). This indicates epistemic un-
Premise-Explicti Reasoning: For ProofWriter, PCFG-derived metrics demonstrated exceptional discriminative power for ground truth prediction. 03-mini achieved near-perfect performance with grammar entropy (AUROC=0,930) AURC=0.0008) and perplexity (AUROC=0.91 194, AURC=0.0009), This confirms procedural epistemic uncertainty dominates in formal reasoning tasks, where an LLM's primary challenge shifts from knowledge recall to the correct application of formal rules. Thus, PCFG metrics assessing structural variance in the SMT-LIB output identify such deductive missteps with
7

---

high precision-ose -inm' ' AURC of 0.0008 using grammar entropy, for instance, enables filtering nearly all errors by abstaining on a minute fraction of outputs.
Table 4: Uncertainty quantification metrics for predicting ground truth correctness via PCFGs of LL - SMT programs. Results show AUROC, ECE, Brier, and AURC across models and reasoning tasks, with ensemble methods consistently outperforming individual metrics. Color intensity indicates performance strength (darker green better)
StralegyQA
ProwWWiter
a3-mnini
03-minn
Gemini 2.0
Flash Tilee
Metric
AUROC
ECE
Brier
AURC
AUROC
ECE:
Brrke
AURC
AUROC
ECE
Bitker
AURC
AUROC
ECE
Brier
AURC
Grammrr Entropy
0.7448
0.3058
0.2340
0.1115
0.7087
0.1575
0.2302
0,2097
(L9391
0.4419
0.2500
0.0008
0.5380
0.3185
0.2669
0.1405
Perplesity
0,5589
0.3107
0.2562
0.1811
0.6122
0.1601
0.2641
0.219
0.9194
0.5358
0.3515
0.0008
0.5931
0,3888
0,3182
0.1267
Divergence
0.6428
0,2485
0.2385
0.1421
0.5123
0.135
0:2322
0.2878
015108
05167 0,3264
0,0074
0,5164
0.300
0.1575
NSLI
0/334
0.2436
0,2539
0.125
0.297
0
0.1191
0.2672
0.5455
05710 0.3545
0.004
0.534
0.318
0.2642
0.1114
Renyi Eat (2)
0,5175
0,3308
0.2997
0,1977
0.6955
0.1622
0.2679
0.3429
0.877
0.5405 0.35%
0.0013
0.99%
04402 0,3368
0.1285
Renyi Bar (0.5)
0.9975
0,3298 0,5042
0.1634
0.6136
0,1623
0.2625
0:2517
01330
014724
0.2879
0.008
0.5933
0.4401
0,3581
0.1258
Max
0,6649
0,3555
0.2925
0.1297
0.681
0.2099
0.2271
019006
0.7198
0.0013
0.5417
03503
0,3045
0,1420
Ratio
0,5385
0,3385
0.9028
0.1834
0.511
0.13%
0,2538
0.3805
0,580
0.5714
0,3764
0.0055
0,5177
0,5943
0,3426
0.1548
Spectral Factor
0.0334
0,2175
0,2164
0.1319
0,680
0,0992
0.2236
0.2366
0.7473
0.3488
0,2247
00002
0.5011
0.5068
0,4157
0.1578
Spectral Radius e Nooteriinals
0/6344
0,2892
0.2747
0.1319
0.6800
0,0686
02118
0.2365
0,7473
0.3545
0,2305
0.002
0,5011
0,3930
0.3172
0.1578
0,5111
0,3540 0.5188
0,2006
0.0155
0.132
02249)
0.2547
0
014267
0,2997
0.0019
0.5167
0.4858
0.4215
0.1672
e Rtllss
0,5548
0.2117 0,2385
0.1855
0.6197
0.1109
012252
0:2583
0.3108
0.4186
0.2201
0.0064
0.5549
0:2022
0,2315
0.1370
Aug Rules/ /TT
0.5737 0,2400 0.2415
0.1752
0.6021
0,0902
0.2200
0.2616
00930
0,338
0,3198
0.0008
0.38-0
0.7790
0,2656
0,130]
Aug KHS Lon
0,5550
0.6141 0,5611
0.1929
01122
0:175
022212
0:229
016555
0,5666
0.003
0.2906
0,1480
Max Branch Factor
0 0,1500 0,1997
0.1990
0,0090
0.1030 02200
0.2688
03914
0.2999
0,1577
0.005
037455
0:219
0:2295
0,1255
Rule Dist Meon
0.5740 0.3161 0,2836
0,1752
0/6021
0,1811 02551
0:2616
004301
0.:945
0.304
0.0008
0:3838
0:136
0,3713
0.1301
Rale Dist SulDey
0.5291 0,3595 0,3817
0:5281
015573
0:3116
(15118
0,0074
0.5144
0,4474
0.1559
Rude Sazw
0,5833
0.3178 0.2550
0.1089
0.0036
0.1431
02489
0:2610
01300
0.9923
0.2967
0.0008
0,5844
0.3779
0.1213
Rule Dor Kurteeis
0,5659
0,304% 0.5420
0,1785
0.5787
0.1720
(.2600
0:2754
0.5844
0.5107
0,3115
0.0055
0.5044
0.1437
0,1915
0.1726
Self Consistency Test
0,1605
0.1601
0.1081
0.6017
0.2874
0,3048
01286]
019950
(10423
0,02200
0,0020
0,5525
0.2228
0,2419
0.1276
Sell Coniistency SMT
0,7415
0,1523
0.1609
0,1061
0,620
0:2318
0.7155
0,2513
0,7121
0.800
0,7764
0.0025
0.7361
0,3535
0,2751
0.1031
Fasemble Average
0.7632
0.3724
0.2916
0.1108
0.6795
0.21R2
(L994)
0J0065
06140
0,3922
0.1240
Easembie Wäighed
0.7657
0.1738
0.1617
0.1099
0.221
0.1257
021155
0.1989
0.9785
04412
0.2566
0.0033
0.7235
0.3327
0.2599
0.1035
Ensemble ML.
0,7850
0,2990
0.1756
0,1013
0.7709
0.6777
0.1968
0.1847
0.9892
0.0572
0.0280
0.0003
0.7631
0,2897
0.2229
0,6623
Fasemble Simple
0,6702
0,2055
0,2104
0,1410
0.640
0.1763
0.2514
0.3483
0.9355
01419
0,2522
0.000
0.6476
0:3667
0,3039
0,1071
Table 5: Uncertainty metrics based on PCFGs for predicting consistency between LLM's SMT formalization and its natural language reasoning. Task-specific uncertainty patterns emerge: rule distribution kurtosis dominates for StrategyQA (AUROC=0,669) while different metrics excel for each model-task combination, highlighting the multifaceted nature of formalization uncertainty.
StrategeQA
ProdWriier
DrepSeck RI
DeepSecks3-4134
Gemini 2.0
Plash Lite
ud-mini
Metric
AUROC
ECE
Brier
AURC
AUROC
ECE
Brier
AURC
AUROC
ECE
Brier
AURC
AUROC
ECE
Brier
AURC
Grammar Entropy
0.7609
0.4617
0.296
0/0216
0.7354
0,3058
0.2511
D13700
0.6022
(L1277
0,2055
0.5089
0.8602
0.4419
0,2542
0.0013
Perplexity
0,6211
0,3789
0,2640
0.0361
0.621
0.3282
0.7188
0.1218
0.7212
0.3255
0,2849
0.5273
0,9032
0.4429
0,2616
0.0013
Divergence
0,5776
0,2555
00415
0.335
0.1780
0.1633
0.556
02387
06341
0,6677
0,5167
0,3238
0.0099
NSUI
0,9965
0,2529
0.1435
00462
0.3973
0.1708
0.1919
0.3411
0.6741
(11195
0.1024
05221
09955
0,4077
0.2172
0:0008
Remyi Eat (2)
0/6242
0,3980
0.2746
0/078
0.6799
0,340
0.888
0.1150
0.7624
03192 0.2624
0,5037
0,9022
0.4382
0.2590
0:0013
Renei Ent (0.5)
0.6119
0,3912
0,2755
0.0376
0.6667
0.333
0.7551
0.1221
0.691
02766 0,2619
0,5138
0.8925
0.5063
0,3245
0,0013
Max
077174
0,359 0,2341
0.0262
04353
0.130)
0.1738
0.1247
015922
013401
0,3063
0.5900
05955
0.2589
0.1029
0:0088
Emt Ratio
0,2217
0,5047
0.3529
0,0543
0.6154
0,4091
0.300
0.1446
0,5511
01541
0,2511
0.6346
0,9677
0,4074
0,2082
0,0003
Spectaal Fictorr
0,5481 0.1533
0,0400
0.7034
0.1251
0.1206
06518
0.5316
0.5069
06029
0.0044
Spectral Radius 4 Nonterminals
0,5481
0.2067 0.1106
0,0640
0.0034
0.1896
0.1752
0.1206
066338
011648
0,1203
0.5316
0,5269
0,6243
0,4953
0,0084
0.5264
0,5679 0:4237
0,0557
0.5519
0.2271
02455
0.1480
0,5166
0.1500
0.3958
0.6509
06505
0,5520
0,3650
0,0017
4 Rules
0.6077
0,3083
0.1839
0.0396
0.5673
0.2025
0.2077
0.1465
0.5749
04256
0,3818
06233
0.3088
0,4186
0,220]
0.0064
Jug Rales/ /NT
0,0034
0.4068
0,2532
0.0273
0,0044
0.1393
0,1854
0.139
0.6565
0,9133
0,2761
0.5923
0,4244
0.2554
0,0025
Aog RUS Len
0.5637
0,2191
0.1566
0,0544
0.5208
0.1251
0,1818
0,1972
0.601
0.4855
0,6120
0.6088
0.5054
0,633
0,5116
0,0074
Mox Franch Factor
0.6001 0,3325 0.2042
0.1344
0.5057
0.1930
0.1457
0,5618
0.4747
06631
61:4:9
0/0009
0.5100
D0002
Rule Dis, Moa
0,7034 0,5352
0,3733
0.0233
0,6034
0.3210
02742
0.1399
0.665
0.2197
0,2280
0.9923
0.001
0/4822
0.2971
0,0026
Rule Die SulDey
0,6056
0.6755
0,5361
0,0413
0/361
0.2226
0.2221
0.1445
071183
0.3166
0.2907
0.5455
08310
0:4232
0,2392
0:0013
Rule Die Skew
0.6848
0,4800
0,3260
0,7399
0.5996
0.3057
0.2619
0.140K
0,676
01788
0.2199
0.5731
08872
0.4864
0,2566
0.0019
Rule Kurtonis
0,531
0,2521
0,158
0.0344
0,6600
0.0731
0.1576
0.1256
0.8095
03187
0,2412
0.4448
09462
0.5107
0,3056
0,0008
Self Consistency Test
0,8245
6,1012
64751
0.0155
0.5778
0.1874
1,2008
0.1754
0.5300
017788
0.26166
0.6044
0.7090
0.9522
0,5025
0.0000
Self Consistency SMT
0,1375
0.1268
0.1054
0,7100
0,6000
0,0090
Ensemble Average
038183
0,4045
0,3058
0,0180
0.7064
0.1876
0.1831
01963
0.7927
01531
0,1702
0.4548
053300
03560
0,1341
0:0007
Ensemble Weighted
0,8494
0.3256
0,1711
0.0155
0.779
0.7786
0.8070)
0.4718
1.000
0.4211
0.0005
Ensemble ML
0.8345
0,3064
0.2005
0.0170
0.8517
0.1861
0,1743
0.8573
0.7946
0.138
0.1592
0.4784
D049
0.0199
0:0005
Ensemble Simple
0,6957
0,6363
0,2748
0.0316
0.6721
0
0.567
0.1119
0L7584
0.0756
0.1568
0,8929
0,006/
0,4419
0.2061
0,0099
Predicting Text Consistency:
Arithmetic Reasoning: On ProntoQA with Gemini Flash 2.0. SMT consistency achieved remarkable performance in predicting text-SMT alignment (AUROC=0.9291, AURC=0.0084), while spectral radius (AUROC=0.6425, AURC=0.0379) emerged as the only effective structural metric. This isolates recursive complexity as a distinct source of uncertainty in arithmetic formalization, as excessively convoluted SMT structures, indicated by high spectral radius, risk diverging from the model's more direct textual reasoning on numerical problems.
8

---

Model-Specific Patterns: For Gemini Flash 2.0 Lite on StrategyQA, kurtosis of the rule distribution was the strongest predictor of SMT-Text consistency (AUROC=08695), Analysis revealed a distinctive "switching" behavior between minimal and verbose SMT patterns, producing a bimodal distribution with heavy tails-a novel diagnostic for capacity limitations in formalization, wherehy such stylistic oscillations between overly terse or verbose SMT, captured by kurtosis, make the resulting formal artifact more prone to misalign with the intended textual meaning.
Ablation Study: PCFG spectral radius from LLM-generated SMT-LIB programs consistently decreases with sampling temperature (In App B), as broader exploration diversifies rule selections, reducing fixation on recursive productions that heavily influence moment matrix eigenvalues. Probability mass spreads more uniformly across production alternttvess diminishing single recursive pattern dominance and thus lowering the mean matrix's 's maximum absolute eigenvalue. Notably, grammatical properties lack sharp phase transitions across temperature ranges; derived PCFGs show smooth, monotonic changes in spectral and information-theerrti characteristics, implying continuous, rather than abrupt, generative response to temperature. Non-terminal expansion distributions shift from concentrated to broader with increasing temperature, though this plateaus, indicating finite exploration capacity, possibly constrained by inherent model biases or the grammar's finite structure. The striking consistency of these opectral-temperaan curves across diverse LLMs points to fundamental, universal mechanism by which these models navigate trade-off when generating structured formal languages. Finally, our fine- tme-grained
the voherence-diversse localized entropy within PCFG production rules surpasses global or non -ongamamati standard techniques in error prediction, confirming that granular structural uncertainty in specific grammatical constructs directly flags component-level semantic error likelihood, offering more precise diagnostics.
4 Discussion
Our analysis reveals fundamental insight: the syntactic atypicality (c.g., in PCFG rule entropy or usage kurtosis) of LLM-generated formal artifacts serves as a powerful signal for semantic errors, reminiscent of OOD detection [Ganguly et al., 2025]. When LLMs correctly understand logical relationships, they consistently produce high high-probabbilty rule sequences, whereas semantic misunderstandings manifest as statistical anomalies cromalies-creatingg distinctive "syntactic fingerprints" of reasoning failure that enable our exceptional error detection (AUROC=0,9301 on ProofWriter). This typicality- approach transcends architectures, its PCFG metric rankings consistently capturing intrinsic difficulties like formalizing ambiguous language across diverse models.
However, the relationship between typicality and correctness isn't straightforward; metrics with superior discriminative ability often exhibit poor calibration (HCF=004419), indicating anomaly magnitude doesn't t linearly predict error bubability-nnceestttiie consistency signals. Even more revealing is asymmetric celf-consistency (c.g.. Gemini/ProntoQA:: SMT AUROC=0,9291 vs. text AUROC=0.5108) suggesting LLMs may use distinct, imperfectly aligned formal versus textual reasoning pathways, not just translate a unified process. Such insights shift neurosymbolic design from translation-focus to aathway-alignment and grounding, e.g., via joint training, as SMT syntactic typicality alone insufficient if its pathway misaligns with textual reasoning.
calibration-awar fusion, perhaps by integrating
5 Related Works
Formal Reasoning with LLMS LLMs show proficiency in formal reasoning [Welleck et al., 2022a, Chen et al., 2022], but face challenges including hallucination, uncertainty expression [Lin et al., 2022a], self- verification [Hou al., 2023], and reasoning opacity [Wei et al., 2022b]. Hybrid approaches combine LLMs with formal tools but often overlook model uncertainty. For autoformalization, early sequence-to-sequeee models [Wang al., 2018, 2020] evolved into ---Me approaches (Wu et al., 2022, Agrawal et al., 2022, Gadgil et al., 2022, Murphy et al., 2024], with structured methods [Jiang et al., 2023b, Zhao et al., 2024] combining I.MMs with ATPs, and various applications [Liu al., 2023, Pan et al., 2023, Olausson et al., 2023, Ye et al., 2023, Zhou et al., 2024, Huang et al., 2024a, Xin et al., 2024a, Jiang et al., 2024, Quan et al., 2024, Xin et al., 2024b]. Proofstep generation advanced from classification [Whalen, 2016, Huang et al., 2019, Bansal et al., 2019] to language modeling [Polu and Sutskever, 2020, First et al., 2023, Wang et al., 2024, Welleck et al., 2022b, Jiang et al., 2022], with recent work exploring zero-shot capabilities [Zhang et al., 2023, Yousefzadeh and Cao, 2023, Scheidt, 2023, Frieder et al., 2023a,bcc, Zhang et al., 2024a] and formal proof generation [Zheng al.. 2024, Xin et al., 2024a, Huang et al., 2024a. Thakur et al., 2024]. Proof search strategies include supervised learnnng [Loos et al., 2017, Chvalovský et al., 2019], reinforcement

---

learning [Kusumoto et al., 2018, Crouse et al., 2021, Piepenbrock et al., 2021], MCTS [Wu et al., 2021, Lample al., 2022, Wang et al., 2023a], and language-ager agent methods [Thakur et al., 2024, An et al., 2024).
Uncertainty in LLM Reasoning Research explores various uncertainty estimation approaches in language models: information-theoretii methods using entropy [Kadavath et al., 2022, Kuhn et al., 2023, Duan et al., 2024], perplexity [Mora-Cross and Calderon-Ramirez 2024, Margatina et al., 2023], and mutual information [Malinin, 2019, Wimmer al., 2023, Depeweg, 2019, Ash, 1965]; ensemble strategies like MC Dropout [Srivastava et al., 2014, Gal and Ghahramani, 201 6a. Lakshminarayanan et al., 2017], Deep Ensembles [Fadeeva et al., 2023, Lakshminarayanan et al., 2017]. and BatchEnsemble [Gal and Ghahramani, 2016b, Lakshminarayanan et al., 2017, Wen et al., 2020] for hallucination detection [Arteaga et al., 2024]: consistency techniques evaluating output agreement [Wang et al., 2023b, Cole al., 2023, Huang et al., 2024b, Zhang et al., 2024b, Lakshminarayanan et al., 2017, Gawlikowski et al., 2023, Manakul et al., 2023, Chen and Mueller, 2024]: similarity- methods [I.in et al., 2024]; Bayesian approaches including BNNs [Shridhar et al., 2019, Blundell et al., 2015], variational inference [Graves, 2011, Jordan et al., 1999, Kullback and Leibler, 1951], Gaussian processes [lwata and Ghahramani, 2017, Liu et al., 2020]. and MCMC [Xiao and Wang, 2018]; and language-based methods extracting uncertainty from verbalizations [Cosmides and Tooby, 1996, Lin et al., 2022b, Tian et al., 2023, Xiong al., 2024, Kojima et al., 2022, Groot and Valdenegro-Tore 2024]. Our work models implicit uncertainty in distributions over multiple formal outputs rather than relying on individual response signals.
Formal Grammars for Language Model Outputs Context- Fontext-Free Grammars (CFGs) have been employed to constrain language model generation at inference time, ensuring syntactically valid outputs for structured formats like JSON [Sengottuvelu, 2023]. SQL. and programming languages Melcer et al., 2024]. These constrained decoding methods modify token probability distributions by masking invalid tokens according to grammar rules. Probabilistic Context-Free Grammars (PCFGs) extend CFGs by associating probabilities with production rules, finding applications in natural language parsing [Manning and Schutze, 1999], bioinformatics [Durbin et al., 1998], and program analysis [Alur et al., 2014]. Recent work [Li et al., 2024] applies PCFGs to guide enumerative program synthesis by learning probability distributions over production rules from successful synthesis traces. While their application domain differs (synthesis guidance vs. uncertainty quantification), it demonstrates the power of PCFGs for reasoning about structured program spaces. HySynth [Barke et al., 2024] similarly enables probabilistic analysis for LLM LLM-generated DSL programs. Our work represents the first application of PCFGs to uncertainty quantification for ILMM-diven autoformalizatio..
Verification and Reasoning Uncertainty DTV [Zhou et al., 2024], SAT-LM [Ye et al., 2023], and related approaches [Quan et al., 2024] connect LLMs with formal verification, while latent space methods [Lee et al., 2020, Wu and Wu, 2021] complement uncertainty estimation research [Kadavath et al., 2022, Lin et al., 2022b]. Our work extends PCFG inference [De la Higuera, 2010] to uncertainty quantification formal verification artifacts, representing the first systematic framework for diagnosing LLM autoformalization reliability through grammatical uncertainty analysis.
Conclusion
Our research presents a PCFG-based framework for SMT-LIB UQ, establishing that syntactic atypicalities in I.LM-generated formal artifacts, previously underexploited, serve as potent, quantifiable signals of underlying semantic errors. Our evaluations revealed nuanced L.M taaaiioos-tssk-deeeeddeee uncertainty responses, localized PCFG entropy's diagnostic power, and asymmetric self-consistency suggesting distinct, imperfectly aligned formal versus textual reasoming pathways. Building on these discoveries, we introduced a novel uncertainty taxonomy and lightweight, model-agnostic signal fusion technique that improves metric synergy and calibration. Applied together, this PCFG framework and fusion strategy achieve substantial error rate reductions via selective verification, offering an empirically validated methodology to significantly enhance LLM reliability in formal verification workflows.
10

---

Acknowledgment
This work was supported in part by the NSF research grant #21 12606, #2117439, #2320952, #2137603.
References
Michael Huth and Mark Ryan. Logic in Computer Science: Modelling and reasoning about systems. Cambridge university press, 2004.
Edmund M Clarke, Thomas A Henzinger, Helmut Veith, Roderick Bloem, et al. Handbook of model checking, volume 10. Springer, 2018.
Jim Woodcock, Peter Gorm Larsen, Juan Bicarregui, and John Fitzgerald. Formal methods: Practice and experience. ACM computing surveys (CSUR), 41(4):1-36, 2009.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 202. 2020.
Mark Chen, Jenry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained code. arXiv preprint arXiv:2107.055: 03374, 2021.
Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b, 2023a. URL https: //axxiv org//bs///////eeeoooooo 2b////b//330.....///// 0top//23100682. 06825.
Bairu Hou, Yujian Liu, Kaizhi Qian, Jacob Andreas, Shiyu Chang, and Yang Zhang. Decomposing uncertainty for large language models through input clarification ensembling. arXiv preprint
vrXhv:2311.08//6 2023.
Debargha Ganguly, Srinivasan Iyengar, Vipin Chaudhary, and Shivkumar Kalyanaraman. PROOF OF THOUGHT Neurosymbolic program synthesis allows robust and interpretable reason- ing. In The First Workshop on System-2 Reasoning Scale, NeurlPS'24, 2024. URL
https://openreview wwt.:eetttooooeeeee http::///pppeeeeeeeeeeee//rtrrdp
Liangming Pan, Alon Albalak, Xinyi Wang, and William Yang Wang. Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning. In Findings of the Association for Computational Linguistics: EMNLP. 2023.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint arXiv:2206.0760 2022a.
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. Program of thoughts prompting: Disen- tangling computation from reasoning for numerical reasoning tasks. arXiv preprint arXiv:2211.12500 2022.
Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodde Nova DasSarma, Eli Tran-Johnson, et al. Language models (mostly) know what they know. arXiv preprint 27X7v2220..05221, 2022.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Xuezhi Wang, Jason Wei, Dale Schuummans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2003. 1117,, 2022.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thouglee prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022b.

---

Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. Did aristotle use a laptop? a question answering benchmark with implicit reasoning strategies. Transactions of the Association for Computational Linguistics, 9:346-360 361, 2021. doi: 10.1 _a _00300 URL.
attps://acllattoollo org/ wrg//0222 tac1-1.21/.
Abulhair Saparov and He He. Language models are greedy reasoners: A systematic formal analysis of chain-of-thought. In The Eleventh International Conference on Learning Representations, 2023. URL
https://openrevierr met/forrumiiie 1oo.uuunndidFFFF333322222
Oyvind Tafjord, Bhavana Dalvi Mishra, and Peter Clark. ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Language. In Findings of the Association for Computational Linguistics: ACI-IJCNLP, 2021.
Simeng Han, Hailey Schoelkopf. Yilun Zhao, Zhenting Qi, Martin Riddell, Wenfei Zhou, James Coady, David Peng, Yujie Qiao, Luke Benson, Lucy Sun, Alexander Wardle-Solane Hannah Szabó, Ekaterina Zubova, Matthew Burtell, Jonathan Fan, Yixin Liu, Brian Wong, Malcolm Sailor, Ansong Ni, Linyong Nan, Jungo Kasai, Tao Yu, Rui Zhang, Alexander Fabbri, Wojciech Maciej Kryseinski, Semih Yavuz, Ye Liu, Xi Victoria Lin, Shafiq Joty. Yingbo Zhou, Caiming Xiong, Rex Ying, Arman Cohan, and Dragomir Radev. FOLJO: Natural language reasoning with first-order logic. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen, editors, Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 22017-22031, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: httpp:://allanthooogg org//rg/// emnlp mamllp-main... main.1229/.
1229.,, URL
Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation. arXiv preprint 2026642302.09664, 2023.
Sebastian Farquhar, Jannik Kossen, Lorenz Kuhn, and Yarin Gal. Detecting hallucinations in large language models using semantic entropy. Nature, (008001):625-63,) 2024.
Debargha Ganguly, Warren Richard Morningstar, Andrew Seohwan Yu, and Vipin Chaudhary. Forte: Finding outiees with representation typicality estimation. In The Thirteenth International Conference on Learning Representations, 2025. URL http:::t:/:///t h/tp//:://////////////// wttpw/wwwwweeeettnweeeeee www.:e/orrmmdddd//gggee......
Sean Welleck, Jiacheng Liu, Ximing Lu, Hannaneh Hajishirzi, and Yejin Choi. Naturalprover: Grounded mathematical proof generation with language models. Advances in Neural Information Processing Systems, 35:4913-444 -9247734427,, 2022a.
Stephanie Lin, Jacob Hilton, and Owain Evans. Teaching models to express their uncertainty in words. arXiv preprint arXiv:2205.143:: 2022a.
Qingxiang Wang, Cezary Kaliszyk, and Josef Urban. First Experiments with Neural Translation of Informal to Formal Mathematics. In Proceedings of the International Conference on Intelligent Computer Mathematics, 2018
Qingxiang Wang, Chad Brown, Cezary Kaliszyk, and Josef Urban. Exploration of Neural Machine Translation in Autoformalization of Mathematics in Mizar. In Proceedings of the ACM SIGPLAN International Conference Certified Programs and Proofs, 2020.
Yuhuai Wu, Albert Q Jiang, Wenda Li, Markus Rabe, Charles Staats, Mateja Jamnik, and Christian Szegedy. Autoformalization with Large Language Models. In Proceedings of the International Conference on Neural Information Processing Systems, 2022.
Ayush Agrawal, Siddhartha Gadgil, Navin Goyal, Ashvni Narayanan, and Anand Tadipatri. Towards Math- ematics Formalisation Assistant using Large Language Models. arXiv preprint a7Xiv:2211.07524, 2022.
Siddhartha Gadgil, Anand Rao Tadipatri, Ayush Agrawal, Ashvni Narayanan, and Navin Goyal. Towards Automating Formalisation of Theorem Statements using Large Language Models. In International Conference on Neural Information Processing Systems Workshop MATH-AI, 2022.
Logan Murphy, Kaiyu Yang, Jialiang Sun, Zhaoyu Li, Anima Anandkumar, and Xujie Si. Autoformalizing Euclidean Geometry. In Proceedings of the International Conference on Machine Learning, 2024.
12

---

Albert Q Jiang, Sean Welleck, Jin Peng Zhou, Wenda Li, Jiacheng Liu. Mateja Jamnik, Timothée Lacroix, Yuhuai Wu, and Guillaume Lample. Draft, Sketch, and Prove: Guiding Formal Theorem Provers with Informal Proofs. In Proceedings of the International Conference on Learning Representations, 2023b.
Xueliang Zhao, Wenda Li, and Lingpeng Kong. Subgoal- Based Demonstration Learning for Formal Theorem Proving. In Proceedings of the Interationaal Conference on Machine Learning, 2024.
Chengwu Liu, Jianhao Shen, Huajian Xin, Zhengying Liu, Ye Yuan, Haiming Wang, Wei Ju, Chuanyang Zheng, Yichun Yin, Lin Li, al. FIMO: A Challenge Formal Dataset for Automated Theorem Proving. arXiv preprint (i:::i0399.0023999 2023.
Theo X Olausson, Alex Gu, Benjamin Lipkin, Cedegao E Zhang, Armando Solar-Lezama, Joshua B Tenenbaum, and Roger Levy. LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2023.
Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. SATLM: Satisfiabiliy--Aieedd Language Models using Declarative Prompting. In Proceedings of the International Conference on Neural Information Processing Systems, 2023.
Jin Peng Zhou, Charles E Staats, Wenda Li, Christian Szegedy, Kilian Q Weinberger, and Yuhuai Wu. LLM Quantitative Reasoning with Autoformalization. In Proceedings
Don't Trust: of the International Conference on Learning Representations, 2024.
Yinya Huang, Xiaohan Lin, Zhengying Liu, Qingxing Cao, Huajian Xin, Haiming Wang. Zhenguo Li, Linqi Song, and Xiaodan Liang. MUSTARD: Mastering Uniform Synthesis of Theorem and Proof Data. In Proceedings of the International Conference on Learning Representations, 2024a.
Huajian Xin, Haiming Wang, Chuanyang Zheng, Lin Li, Zhengying Liu, Qingxing Cao, Yinya Huang, Jing Xiong, Han Shi, Enze Xie, et al. LEGO- Neural Theorem Proving with Growing Libraries. In Proceedings of the International Conference on Learning Representations, 2024a.
Dongwei Jiang, Marcio Fonseca, and Shay B Cohen. LeanReasoner: Boosting Complex Logical Reasoning with Lean. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2024.
Xin Quan, Marco Valentino, Louise A Dennis, and André Freitas. Verification and Refinement of Natural Language Explanations through LLM-Symbolic Theorem Proving, arXiv preprint a7X 2024.
Huajian Xin, Daya Guo, Zhihong Shao, Zhizhou Ren, Qihao Zhu, Bo Liu, Chong Ruan, Wenda Li, and Xiaodan Liang. DeepSeek- Advancing Theorem Proving in LLMs through Large-Scale Synthetic Data. arXiv preprint 2405::2230..133333. 2024b.
Daniel Whalen. Holophrasm: A Neural Automated Theorem Prover for Higher-Order Logic. arXiv preprint arXiv:1608.02644, 2016.
Daniel Huang. Prafulla Dhariwal, Dawn Song, and Ilya Sutskever. GamePad: A Learning Environment for Theorem Proving. In Proceedings of the International Conference Learning Representations, 2019.
Kshitij Bansal, Sarah M. Loos, Markus Norman Rabe, Christian Szegedy, and Stewart Wilcox. HOList: An Environment for Machine Learning of Higher Order Logic Theorem Proving. In Proceedings of the International Conference on Machine Learning, 2019.
Stanislas Polu and Ilya Sutskever. Generative Language Modeling for Automated Theorem Proving. arXiv preprint arXiv:2009.0333 03399, 2020.
Emily First, Markus Rabe, Talia Ringer. and Yuniy Brun. Baldur: Whole-Proof Generation and Repair with Large I Language Models. In Proceedings of the ACM Joint European Software Engineering Conference and Symposiun on the Foundations of Software Engineering, 2023.
Haiming Wang, Huajian Xin, Zhengying Liu, Wenda Li, Yinya Huang, Jianqiao Lu, Zhicheng Yang. Jing Tang, Jian Yin, Zhenguo Li, et al. Proving Theorems Recursively. arXiv preprint arXiv:2405. 14414, 2024.
13

---

Sean Welleck, Jiacheng Liu, Ximing Lu, Hannanch Hajishirzi, and Yejin Choi. NaturalProver: Grounded Mathematical Proof Generation with Language Models. In Proceedings of the Interaational Conference on Neural Information Processing Systems, 2022b.
Albert Q Jiang, Wenda Li, Szymon Tworkowski Konrad Czechowski, Tomasz Odrzygóćdú, Piotr Miłoš, Yuhuai Wu, and Mateja Jamnik. Thor: Wielding Hammers to Integrate Language Models and Automated Theorem Provers. In Proceedings of the International Conference on Neural Information Processing Systems, 2022.
Shizhuo Dylan Zhang, Talia Ringer, and Emily First. Getting More out of Large Language Models for Proofs. In Proceedings of the Conference on Artificial Intelligence and Theorem Proving, 2023.
Roozbeh Yousefzadeh and Xuenan Cao. Large Language Models' Understanding of Math: Source Criticism and Extrapolation. arXiv preprint arXiv:331.006118 2023.
Gregor Scheidt. Experimental Results from Applying GPT-4 An Unpublished Formal Language.
arXiv preprint arXiv:2305. /2/96, 2023.
Simon Frieder, Julius Berner, Philipp Petersen, and Thomas Lukasiewicz. Large Language Models for Mathematicians. arXiv preprint arXiv:23/2.04556, 2023a.
Simon Frieder, Luca Pinchetti. Alexis Chevalier, Ryan- Rhys Griffiths, Tommaso Salvatori, Thomas Lukasiewicz, Philipp Christian Petersen, and Julius Berner. Mathematical Capabilities of ChatGPT In Proceedings of the International Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023b.
Simon Frieder, Martin Trimmel, Rashid Alawadhi, and Klaus Gy. LLM vs ITP. International Conference on Neural Information Processing Systems Workshop MATH-AI, 2023c.
Lichen Zhang, Shuai Lu, and Nan Duan. Selene: Pioneering Automated Proof in Software Verification. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, 2024a.
Chuanyang Zheng, Haiming Wang, Enze Xie. Zhengying Liu, Jiankai Sun, Huajian Xin, Jianhao Shen, Zhenguo Li, and Yu Li. Lyra: Orchestrating Dual Correction in Automated Theorem Proving. Transactions on Machine Learning Research, 2024.
Amitayush Thakur, George Tsoukalas, Yeming Wen, Jimmy Xin, and Swarat Chaudhuri. An In- In-Context Learning Agent for Formal Theorem-Proving. arXiv preprint arXiv:2310.04353 2024.
Sarah Loos, Geoffrey Irving, Christian Szegedy, and Cezary Kaliszyk. Deep Network Guided Proof Search. In Proceedings of the International Conference on Logic for Programming, Artificial Intelligence and Reasoning, 2017.
Karel Chvalovský, Jan Jakubiiv, Martin Suda, and Josef Urban. ENIGMA-NG: Efficient Neural and Gradient-Booster Inference Guidance for E. In Proceedings of the International Conference on Automated Deduction, 2019.
Mitsuru Kusumoto, Keisuke Yahata, and Masahiro Sakai. Automated Theorem Proving in Intuitionistic Propositional Logic by Deep Reinforcement Learning. arXiv preprint 1 1.00766. 2018.
Maxwell Crouse, Ibrahim Abdelaziz, Bassem Makni, Spencer Whitehead, Cristina Comelio, Pavan Kapanipathi, Kavitha Srinivas, Veronika Thost, Michael Witbrock, and Achille Fokoue. A Deep Reinforcement Leaming Approach to First-Order Logic Theorem Proving. In Proceedings the AAAI Conference on Artificial Intelligene, 2021.
Jelle Piepenbrock, Tom Heskes, MikoláS Janota, and Josef Urban. Learning Equational Theorem Proving.
In Proceedings of the Conference Artificial Intelligence and Theorem Proving, 2021.
Minchao Wu, Michael Norrish, Christian Walder, and Amir Dezfouli. TacticZero: Learning to Prove
Theorems from Scratch with Deep Reinforcement Learning. Proceedings of the International Conference on Neural Information Processing Systems, 2021.
Guillaume Lample, Timothee I Lacroix, Marie-Anne Lachaux, Aurelien Rodriguez, Amaury Hayat, Thibaut Lavril, Gabriel Ebner, and Xavier Martinet. Hypertree Proof Search for Neural Theorem Proving. In Proceedings of the International Conference on Neural Information Processing Systems, 2022.
14

---

Haiming Wang, Ye Yuan, Zhengying Liu, Jianhao Shen, Yichun Yin, Jing Xiong, Enze Xie, Han Shi, Yujun Li, Lin Li. et al. DT-Solver: Automated Theorem Proving with Dynamic- Treee Sampling Guided by Proof-level Value Function. In Proceedings of the Annual Meeling of the Association for Computational Linguistics, 2023a.
Chenyang An, Zhibo Chen, Qihao Ye, Emily First, Letian Peng, Jiayun Zhang, Zihan Wang, Sorin Lemnr, and Jingbo Shang. Learn from Failure: Fine-Tumne Tuning LLMs with shal-and-Eer -nr-rrror Data for Intuitionistic Propositional Logic Proving. arXiv preprint arXiv:2404.077 07382, 2024.
Jinhao Duan, Renming Zhang, James Diffenderfer, Bhavya Kailkhura, Lichao Sun, Elias Stengel- -sskin, Mohit Bansal, Tianlong Chen, and Kaidi Xu. Gtbench: Uncovering the strategic reasoning limitations of Iims via thenrete evaluations. arXiv preprint arXiv:2402. /2344 2024.
Maria Mora-Cross and Saul Calderon- Uncertainty estimation in large language models to support biodiversity conservation. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 6: Industry Track), pages 368-378, 2024.
Katerina Margatina, Timo Schick, Nikolaos Aletras, and Jane Dwivedi Yu. Active learning principles for in-context learning with large language models, 2023. URL https: org/ ab35/305. 14264.
Andrey Malinin. Uncertainty estimation in deep learning with application to spoken language assessment. PhD thesis, University of Cambridge, 2019.
Lisa Wimmer, Yusuf Sale, Paul Hofman, Bernd Bischl, and Eyke Hüllermeier. Quantifying aleatoric and epistemic uncertainty in machine learning: Are conditional entropy and mutual information appropriate measures? In Robin J. Evans and Ilya Shpitser, editors, Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, volume 216 of Proceed- ings of Machine Learning Research, pages 2282-2292. PMLR, 31 Jul-04 Aug 2023. URL http::s//proocediigg..oo mlr. paat.preess///i httwmmmr222ee html.
Stefan Depeweg, Modeling epistemic and alcatoric uncertainty with bayesian neural networks and latent variables. 2019. URL http::ttpp::/att httppp////appssssmniscseseeee www.etiissoolle.ee.o Targ/CorpusIiii : 208224494
Robert B Ash. Information theory. Dover Publications, 1965.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout:
simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929-199 2014.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning volume 48 of Proceedings of Machine Learning Research, pages 1050-1059, New York, New York, USA, 20-22 Jun 2016a. PMLR. URL mlr, www..pree///eee wwwpps///////eeppppppt. hesr//gal1..... 6hmml
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncer- tainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
Ekaterina Fadeeva, Roman Vashurin, Akim Tsvigun, Artem Vazhentsev, Sergey Petrakov, Kirill Fedyanin, Daniil Vasilev, Elizaveta Goncharova, Alexander Panchenko, Maxim Panov, et al. Lm-polygraph: Uncertainty estimation for language models. arXiv preprint arXiv:2311.0738. 2023.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. international conference on machine learning, pages 1050-1059. PMLR, 2016b.
Yeming Wen, Dustin Tran, and Jimmy Ba. Batchensemble: An altemative approach efficient ensemble and lifelong learning, 2020. URL taattps://arstin httttt/s//aarii.org/aba/////////
Gabriel Y. Arteaga, Thomas B. Schön, and Nicolas Pielawski. Hallucination detection in Ilms: Fast and memory-efficient finetuned models, 2024. URL https: wwwaaaaww.....rrarrrrara.aeaeeee org/abs/24093 org//bbs/209.00977
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Fd Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models, 2023b. URL https:/ //tp///avvvvv.///////ee///aaa/l/ orgg abs///bb/200 11171.
15

---

Jeremy R. Cole, Michael J. Q. Zhang. Daniel Gillick, Julian Martin Eisenschlos, Bhuwan Dhingra, and Jacob Eisenstein. Selectively answering ambiguous questions, 2023. URL
htttps://axiv> wtg//bs/////ae 230///bb//3.... 14613.
Hsiu- Yuan Huang, Zichen Wu, Yutong Yang. Junzhao Zhang, and Yunfang Wu. Une-tip: A method for classifying Ilm uncertainty improve in-context example selection, 2024b. URL
https: /ttpivrxivvvv.a///////a../.a.av. org/ httgg//b//400/// 09172.
Jiaxin Zhang, Zhuohang Li. Kamalika Das, Bradley A. Malin, and Sricharan Kumar. Sac3: Reliable hallucination detection black-box language models via semantic-aware cross-check consistency, 2024b. URL httpt::////aaeeeee www.vv.rrg/bbba. wwtpaaas../a..ee// 01740.
Jakob Gawlikowski, Cedrique Rovile Njieutcheu Tassi, Mohsin Ali, Jongseok Lee, Matthias Humt, Jianxiang Feng, Anna Kruspe, Rudolph Tricbel, Peter Jung, Ribana Roscher, et al. A survey of uncertainty in deep neural networks. Artificial Intelligence Review, 56(Suppl 1):1513-1589, 2023.
Potsawee Manakul, Adian Liusie, and Mark J. F. Gales. Selfcheckgpt: Zero-resource black-box hallucination detection for generative large language models, 2023. URL
https://arxix httpp/////axi..o//abbbba.. 2ttp//233.000888
Jiuhai Chen and Jonas Mueller. Quantifying uncertainty in answers from any language model and enhancing their trustworthiness. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), pages 5186-5200, Bangkok, Thailand, August 2024. Association for Computational Linguistics. URL https: tettttss:/aclaatttooot aal/aacooaooooyyyyyooooo wtg//004..00222020/
Zhen Lin, Shubhendu Trivedi, and Jimeng Sun. Generating with confidence: Uncertainty quantification for black-box large language models, 2024. URL httpt://aaa/ii...ooooo org/ abs// 19187.
Kumar Shridhar, Felix Laumann, and Marcus Liwicki. A comprehensive guide to bayesian convolutional neural network with variational inference, 2019. URL https://arxiv..o org.abs..r../bb//b// awwaaa//......///// 1901.02731.
Charles Blundell, Julien Comebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International conference on machine learning, pages 1613-1622. PMLR, 2015.
Alex Graves. Practical variational inference for neural networks. Advances in neural information processing systems, 24, 2.1
Michael I Jordan, Zoubin Ghahramani, Tommi S Jaakkola, and Lawrence Saul. An introduction to variational methods for graphical models. Machine learning. 37:183-233 1999.
S. Kullback and R. A. Leibler. On information and sufficiency. The Annals of Mathematical Statistics, 22(1):79-86, 86, 1951. ISSN 00034851. URL http://www. jstorr arg/stable//2et 22236733
Tomoharu Iwata and Zoubin Ghahramani. Improving output uncertainty estimation and generalization in deep learning via neural network gaussian processes, 2017. URL
hittss///axivv wwtpxiiivoog/bbbb. www./ogg/////... awwpaa//a/..//////.///////////aa 059922.
Jeremiah Zhe Liu, Zi Lin, Shreyas Padhy, Dustin Tran, Tania Bedrax-Weiss and Balaji Lakshminarayanan. Simple and principled uncertainty estimation with deterministic deep learning via distance awareness, 2020. URL https:
Yijun Xiao and William Yang Wang. Quantifying uncertainties in natural language processing tasks, 2018.
URI. httttt:s////tttti htattp:://aaxiv.or//ab/////////e wwgg/bs/////teo /tt///1811..7.7.. .02253.
Leda Cosmides and John Tooby. Are humans good intuitive statisticians after all? rethinking some conclusions from the literature on judgment under uncertainty. cognition, 58(1):1-73, 1996.
Stephanie Lin, Jacob Hilton, and Owain Evans. Teaching models to express their uncertainty in words. 2022b. URL https: www.aaiwww....aaaaae..o.oeoo abs/ 2205. 14334.
Katherine Tian, Eric Mitchell, Allan Zhou, Archit Sharma, Rafael Rafailov, Huaxiu Yao, Chelsea Finn, and Christopher D. Manning. Just ask for calibration: Strategies for eliciting cali- brated confidence scores from language models fine-tuned with human feedback, 2023. URL
https: / /aaxiv..v.. www.i..ogg/aa..eeeo.......owoerr www//oog////e/eeee aba/2305 14975.
16

---

Miao Xiong, Zhiyuan Hu, Xinyang Lu, Yifei Li, Jie Fu, Junxian He, and Bryan Hooi. Can llms express their uncertainty? an empirical evaluation of confidence elicitation in llms, 2024. URL https://arxiv. org/ abo/ 13063.
Takeshi Kojima, Shixiang (Shane) Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 22199- 222133. Curran Associates, Inc., 2022. URL http://////prrooceenng... neurips cc/ cc/paper_.. saapperffieee/pppetee 2022/file/ https//ssaooaooaaaaaaoaooo000010
large language and vision-language models, 2024. URL Confer--oooeeeeeeee .dr..
Tobias Groot and Matias Valdenegro-Towe Overconfidence is key: Verbalized uncertainty evaluation in
org/ wwrgg/ba//20 aatp 02917.
Rahul Sengottuvelu. Jsonformer: A bulletproof way to generate structured json from language models, 2023.
Daniel Melcer, Nathan Fulton, Sanjay Krishna Gouda, and Haifeng Qian. Constrained decoding for code language models via efficient left and right quotienting of context-sensitive grammars. CoRR, 2024.
Christopher Manning and Hinrich Schutze. Foundations of statistical natural language processing. MIT press, 1999.
Richard Durbin, Sean R Eddy, Anders Krogh, and Graeme Mitchison. Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge university press, 1998.
Rajeev Alur, Milo Martin, Mukund Raghothaman, Christos Stergiou, Stavros Tripakis, and Abhishek Udupa. Synthesizing finite-state protocols from scenarios and requirements. In Hardware and Software: Verification and Testing: 10th International Haifa Verification Conference, HVC 2014, Haifa, Israel, November 18- 20, 2014. Proceedings 10, pages 75 75-91. Springer, 2014.
Yixuan Li, Julian Parsert, and Elizabeth Polgreen. Guiding enumerative program synthesis with large language models. In International Conference Computer Aided Verification, pages 280-301. Springer, 2024.
Shraddha Barke, Emmanuel Anaya Gonzalez, Saketh Ram Kasibatla, Taylor Berg- Kiin-K-kkkatrick, and Nadia Polikarpova. Hysynth: Context-free Ilm approximation for guiding program synthesis. Advances in Neural Information Processing Systems, 37:15612-15645, 2024.
Dennis Lee, Christian Szegedy, Markus N Rabe, Sarah M Loos, and Kshitij Bansal. Mathematical Reason- ing Latent Space. In Proceedings of the International Conference Learning Representations, 2020.
Minchao Wu and Yuhuai Wu. Latent Action Space for Efficient Planning in Theorem Proving. In Proceedings of the Conference on Artificial Inielligence and Theorem Proving, 2021.
Colin De la Higuera. Grammatical inference: learning automata and grammars. Cambridge University Press, 2010.
17

---

A
Appendix: Proofs
A.1 Coverage Guarantees
Theorem 1 Coverage Guarantees
Proof. Step Construct "high-probabillty" set. By definition of Shannon entropy in bits, there can be at most (8()) points x Ex each having probability p(z) 2 2 H(,), Gather all such points into set
Suigh frrE" [xx) (=<=":;(=)>2 H
A standard "typical-set" argument shows that yu (u(Snigh) 2 11/2 (or at least a fixed positive constant).
Step 2: Missing Suigh The probability that one sample X μ does not land in Suigh is at most 1 1- ((((ttig)) 1/2 Hence the probability that none of N i.i.d. draws land in Shigh is most (1/2)~=2-1) -2- Thus any set of measure at least 1/2 is missed with exponentially small probability.
Step 3:
Missing a smaller-mass region A. If (((A) = = 1/2, the probability that one draw misses A 6, so the probability all N draws miss (1-c)* ((0_=c)===x((----00
if Ne not too large.
However, we need a uniform guarantee over all possible A of measure c. By representing Σn as composed of at most 2 "atoms" each of probability at least 2 2-H((), the number distinct subsets is at most (xp(2H(()))) union bound then modifies the exponent by about a factor of 1 1/22(()) so large
N one has
Pr (e)=:p(A)==andddd N samples miss A] S exp
Ne
This is the desired exponential coverage bound.
Step 4: Inverting the bound with the Lambert W-function. We have
Pr miss some set of mass $ I exp
No. 2010
We want to find such that this probability itself at most
exp
Nr 2
Rearrange as
exp
Ns 2
cexp
201
Then (p))
Let x 20(0
H, and the above becomes
H(4
N 2H)
N rexp(x) =1
re
By definition of Lambert W-function, x= W
N 2
Substituting back, we get
(1))
W
N mm
N
Thus e decreases to as N oo, roughly like
g!Gw) N
In
N (
Hence, the probability of missing any set of mass at least is E, E, with e scaling on the order of In(N) This completes the proof.
N
A.2 Temperature Sampling & Ablations
Sampling from an LLM at higher temperatures effectively "flattens" its probability distribution over next-token choices, increasing the entropy of the samples and thus encouraging exploration of lower-probability (more diverse) regions of the program space. Conversely, sampling lower temperatures sharpens the distribution, concentrating probability mass the model's highest-confidence predictions
18

---

and yielding lower-entropy (more conservative) samples. In other words, wwwteeppeaature sampling focuses on the most likely, canonical SMT-LIB programs (small effective support), while high-temperature sampling ventures into rarer, more varied comnrr of the output space (large effective support). If instead of smoothly varying temperature schedule you simply draw many samples fixed temperatures say 0.5, 1.0, 1.5, and 2.0-you will still span low- to high-entropy regimes, but less systematically. You risk oversampling similar outputs at each temperature (especially near the extremes) and undersampling the intermediate entropy levels that lie between 0.5->1.0 1.0 and 1.5->2.0. A continuous schedule allocates exactly one sample per intermediate temperature, guaranteeing uniform coverage entropy levels; ixxe-teemeeaature repetition may require substantially more draws to approximate that coverage, potentially leaving gaps in the distribution of generated programs.
Definition (Gaussian Temperature Schedule). To smoothly explore the distribution over SMT-LIB programs, can define a temperalure schedule for N samples
T Tmin (Tmax TTmin -exp (i-N/2)2
(1)
20
where Tmin = 0.1, Tmax 1.5, and controls the spread of the Gaussian.
We can also skew this gaussian towards lower temperatures.
Definition 2 (Exponential Temperature Schedule). We can define schedule that emphasizes sampling at lower temperatures using:
Ts Tmin (Tmax -minn) -emmn))expppxi
where x O controls the decay rate, and i 0.,1,..,NN11.
From a purely ewverage-guaranter standpoint (i.e. our goal of hitting every "significant" region of the SMT-LIB output distribution at least once), the Systematic uniform schedule remains the most theoretically justified. It uniformly samples every temperature exactly once, from low to high. Provably minimizes the worst-case "miss probability" by evenly covering the full entropy range. Gaussians concentrates samples near the middle temperature; fewer at extremes. It does provide smooth transitions; and avoids extreme high-entropy noise. However undersamples both very low-entropy (conservative) and very high-entropy (creative) regions resulting in weaker uniform coverage. The exponential decay schedule heavily biases toward low temperatures (low entropy), and therefore quickly focuses on high-confidence outputs. However, there is almost no exploration rare programs; poor coverage of tail regions.
Comparison:
B Temperature- Varied SMT Generation and PCFG Analysis
To empirically investigate the influence of LLM sampling temperature on the characteristics of generated formal artifacts, we performed SMT-LIB v2 program generation across a defined temperature spectrum (e.g.. T = 0.0 to T Max 2.0). Distinct Probabilistic Context-Free Grammars (PCFGs) were induced from the SMT program ensembles parsed at each temperature point T, modeling the LLM's syntactic and structural tendencies under each generative condition.
Our analysis of these per-temperature PCFGs revealed distinct and significant trends as sampling temperature was varied. Notably, the PCFG spectral radius generally trended upwards with increasing temperature. This intriguing behavior suggests that higher temperatures, while fostering diversity, may also enable the LLM access and generate SMT structures with more pronounced or varied recursive complexity, perhaps by activating a broader range of complex production rules rather than simplifying structural choices. Consistent with expectations of increased diversity, grammar entropy and its associated perplexity also demonstrated an upward trend, quantifying the heightened uncertainty and the expanded set of effective choices exercised by the LLM at higher temperatures.
particularly interesting observation was that the KL divergence from a uniform distribution also tended to increase with temperature. This implies that as the LLM explores wider variety of production rules (evidenced by increased entropy). its choices within this expanded repertoire become, in a relative sense, more specifie structured, deviating further from a purely random uniform selection over the increasingly diverse set of utilized rules. Correspondingly. the entropy ratio generally decreased, which could occur the maximum possible entropy (based on the growing set of observed rules and non-terminals higher temperatures) increases at faster rate than the actual grammar entropy. The composite metric NSUI showed
19

---

Overall fug gramtarsthattre
sww.ttue spectral redlus Terppereture
Overal feg Information theoohogammmmeee. entrroy vs. Ter remperatur
6.00
8.00
6.60
8.500
Impeerture
Repperature
Figure 2: Spectral Radius VS Temperature
Figure 3: Grammar Entropy VS Temperature
Overall Avg Information.teees theory M, divergence from... vs. Temperature
Overall Aug nftrmation theoyyyhehhtttt pneeryrroil.compeentsss components.oncc en.. Tempertture
BATS
2.80
Tempensure
Pepperature
Figure 4: KLD vs Temp
Figure Entropy Ratio vs Temp
the componetcs. Temperature
Aug thecry.nsu components Temperature
Infermsttoon
6.00
3.15
135 1.3
1.5
0.34
0.5
512
1.20
1.29
Figure 6: NSUI vs Temp
Figure 7: Spectral Factor Temp
fluctuating behavior without a clear monotonic direction, reflecting the complex interplay of its underlying components. The spectral factor, linked to the spectral radius, also exhibited slight upward trend.
Metrics related to the observed grammar structure, such the average number of rules utilized per non-terminal, the maximum observed branching factor, and the average right-hand side (RHS) length of applied rules, all generally increased with temperature. This supports the notion that higher temperatures lead the L.M to explore and employ more extensive and potentially more elaborate subset of the SMT-LIB grammar. Regarding the shape the rule probability distributions, kurtosis consistently decreased, indicating that these distributions become flatter (less peaked) as temperature promotes more uniform rule selection among the actively used rules. Conversely, the skew of these distributions tended to increase, suggesting shift in the asymmetry of rule preferences temperature changes.
These ablation studies meaningful they reveal nuanced picture of the LLM's generative process for formal languages. The trends suggest that increasing temperature doesn't 't merely lead to random, uniform outputs. but rather allows the LLM to explore richer, potentially more complex, and structurally diverse portion of the language space defined by GsMT. This expansion, however, may also come with its own emergent structural specificities, as indicated by the KL divergence, These findings are crucial for
20

---

Overall frg information phrepppetteeyyyyppetttt vs. Tempersture
Overal gammmr_aee structuree
eng, rites gomttustuuturee Temperature
Imppertuure
Temperature
Figure 8: Perplexity vs Temp
Figure 9: Average Rules per Non-terminal vs Temp
Overall Aug grammor, structure max grammer_ttuccure
aranching_fattor vs. Temperature
Overa Ang grommar stw www.cttre.wwgg..t...ooo www.eeee__.sseeegiii vs. Tempersture
C0mTE shurtug Dranchirgg fetto
Temperoture
Temporoture
Figure 10: Max Branching Factor vs Temp
Figure II: Average RHS Length vs Temp
fug analysicrule
fog janalysksruke
62
sbatestccll
020
635
6.0
1.55
1.30
223
635
411
1.00
1.5
1.29
Figure 12: Kurtosis Temp
Figure 13: Skew Temp
understanding the doherence-diversity trade-off, for validating the sensitivity of PCFG-derived metrics, and for interpreting uncertainty scores, the baseline characteristics of generated artifacts are systematically altered by temperature in complex ways. The observed responses underscore the value of empirical studies in characterizing LLM behavior for formal code generation.
21

---

Detailed Results
C.1
Benchmarking Autoformalization
The performance benchmarks detailed in 6, 7. 8, 9. 10 were generated by evaluating five Large Language Models (o3-mini, DeepSeekRI with Chain-of-Thoughh DeepSeck-v3-04-21, Gemini Flash 2.0, and Gemini Flash 2.0 Lite) on four reasoning datasets. For each question, five samples were generated, and answers were derived either directly from the LLM's textual output or by solving LLM-gennrated SMT-LIB programs using the Z3 solver. The "medium effort" designation for 03-mini indicates specific prompting or iteration level for that model. In Table 6, the SMT approach for models like Deepseek v3 not only altered precision and recall but also resulted in substantial numbers of both False Positives (144) and True Positives (199), suggesting that while it attempted more proofs, a large fraction these new attempts were erroneous. This contrasts with its text performance (42 FP, 174 TP). For the ProntoQA training set, with only true answers (Table 7). the SMT Precision of 1.0000 across all models is a direct consequence of the experimental design (no false statements to misclassify as true if TN is inherently 0): the variance in False Negatives (e.g.. 270 for Deepseek v3 SMT) thus purely reflects the inability to successfully formalize and prove statements known to be true, direct measure of formalization completeness for affirmatives.
Table 6: LLM Performance on StrategyQA (Text vs. SMT): SMT often boosts recall (e.g.. Deepseek v3 from 0.81 to 0.91) but can reduce precision and overall accuracy for several models, highlighting medee-de autoformalization success on knowledge-intensive tasks.
StmnagyyQ
Text
SMT
Accurazy
Precsion
Recall
F1
TP
TN
FP
EN
Accuncy Precision
Recall
F1
TP
FP
EN
03-mink (mediiu effiot)
0,7628
0,8699
0,0077
0,7104
130
250
21
80
0.7980
03658
016347
07335
199
260
21
30
Despeeck v3 0024
0,6292
0,8055
0,9055
0,8065
0.6220
0.5801
0.9086
0.7081
DeepSock R]
0.380
0.3664
0,8402
0,8085
184
245
36
35
0.730
0.154
018577 0.756
176
212
69
43
Gemini Flash 2.0
0,7188
0,6880
0,670 0,6720
144
214
65
75
0.330
0.1840
0.269 0.363
203
65
216
16
Genini Flash
0.6660
06670
110
0,4000
0.4499
0.7766
12
Table 7: LLM Performance on ProntoQA Train (True Statements Only; Text vs. SMT): SMT exposes significant failures in formalizing and proving known true statements for models like Deepseek v3 (Accuracy 0,45 vs. Text 1.00), indicating critical autoformaliza- tion recall deficiencies rather than precision issues (SMT Precision remains 1.00 for all).
PionteQAA Trin ONLY TRUE Ansoes
Tel
SMT
Accuncy
Precision:
Recall
TN
PN
Accuney
Precison
Recall
Fl
PP
o3-mini (mediam effort)
1,000)
10000
1000 1,0000
409
0
0
0
019900 100000 01960 (1959
409
0
0
Deepseek 0334
10000
10000
11000 10000 450
0
0
0.500
11000
0.450 0.600
0
270
Deepphiiit RI
0,9930
1,0000
0.993)
0.909 480
0
0
3
0.440 19000
0 14440 08532
372
0
128
Gemini Placa 210
0.8330
10000
(1982)
(19000
491
0
0
9
05000 10000
(19000 09470
450
0
0 50
Gemini Flzsh 201.
019980
1X000
(19980
(19980
499
0
(19980 10000
019900
0
The ProofWriter results Table 8 are notable. We advise the reader to ignore DeepSeek R1's SMT performance, since it is based on a "Partial Run," because of poor model ability to autoformalize, due to the overuse of thinking tokens, thereby causing an intractable timeline for converging to any solution and API call explosion. Here, 03-mini (medium effort) showcases a successful SMT application, where its accuracy improved to 0.9418 with reduction in both False Positives (from 34 to 19) and False Negatives (from 21 to 10) compared to its text output. On the FOLIO dataset (Table 9), a common pattern observed in the SMT condition, beyond just low precision, was the significant reduction in True Negatives compared to the Text condition for several models (e.g., Deepseek v3 dropped from 34 TN via Text to 5 TN via SMT; Gemini Flash 2.0 from 37 TN TN). This suggests systemic challenge in generating SMT formulas that correctly evaluate to unsatisfiable for statements that are indeed false within the FOLIO logical structure. Finally, the ProntoQA test set which includes both true and false statements (Table 10) revealed extreme model-specific behaviors under SMT. DeepSeek Rl's SMT output, for instance, correctly identified all 242 false statements (0 FP, 242 TN) but failed to correctly identify any of the 258 true statements (0 TP, 258 FN), indicating a systematic bias in its SMT generation towards unsatisfiability or an inability to complete proofs for satisfiable formulas in a mixteddistributtin context, a stark contrast to its perfect text performance and its SMT performance on true-only statements.
22

---

Table 8: LLM Performance on ProofWriter (Text vs. SMT): SMT substantially improves models struggling with formal logic (e.g., Gemini Flash 2.0 Lite accuracy from 0.41 to 0.75). yet can degrade performance for models already strong textual formal reasoning (e.g., DeepSeek RI accuracy from 0.94 to 0.49), showcasing task- susk-specifie SMT utility.
Prou/Writer
Teut
SMT
Accurscy
Rocall
03--mini (medium (neddumettiii
0,883
0.8097
09153
03919
227
215
34
21
03418
09251
0.9997
03426
238
231
19
10
Deepseck (134
03057
0,8066
0,225
0,110
47
0.500
0.330
0.414
277
167
DeepSeek (Panall
0 0.2005
125
Gemini Flash 2.)
049000
(1496))
0.5710
0.500
140
106
142
105
0/660
B1844
016100 0:5313
154
106
71
96
0.2440 0.2911
0.7674
208
Table 9: LLM Performance on FOLIO (Text vs. SMT): Textual reasoning largely outperforms SMT. For many models, SMT results in high recall but poor precision (e-g.- Gemini Flash SMT F1 0.72 vs Text 0.92) and a failure to identify false statements (e.g.. 0 SMT True Negatives for Gemini Flash 2.0), indicating issues with formalizing negation or complex FOL conditions.
Foãe
Accuracy
Precision
Recall
Fl
TP TN
FP
EN
Aucurayy
Precison
Recil
F1
TP
TN
FP
IN
oletini (mediam effort)
0.0632
0,094
09531
0,000
0,6990
0L585
04166
Drepseek v3 0524
0,933
0.9259
0,9615 0.433
50
2
0,561
0,605
0.198
0.707
TragSook RI
D.252
0.6600
0,0090
09974
60
39
2
6 0.530
016363
0.530
0U5785
21
30
31
0.6000
Gamini Flash 2,0-ine
B5017
(1914
0,9422
0.923
66
35
4 0.321 0.
0.235
12
Table 10: LLM Performance ProntoQA Test (True/False Mix; Text vs. SMT): SMT shows divergent outcomes: catastrophic failure for some (c.g., DeepSeck RI SMT Fl 0.00 vs. Text 1.00). yet significant improvement for others (Gemini Flash 2.0 Lite SMT Accuracy 0.78 vs. Text 0.56), highlighting inconsistent SMT reliability on mixed arithmetic statements.
PremotJA TEST BOTH TRL
Text
SMT
Aocuacy
Procision
Rocall
FN
Acmmey
Precision
Recill
03-mini (medium effoot)
100000
1,0000
1,0000
1,0000
258
240
1,0000
1,0000
1,000 1,000
258
242
0
Teepscek vi (P34
0.7200
0.7138
0.7635 07578
197
163
79
61
0.5141
0.5484
0.3205
64116
85 172
70
171
DeepSeek RT
1,0000
Gemira Flssh 2.0
0.180
018232
0.5700
0.6780)
210
32
109
0.460
D.753
05252
0,4981
155
91
149
123
Gemira Fush Lite
0.5630
0.58IT
0,533
0,562
98
119
0.7820
0.7210
09418
08168
243
23

---

C.2 Detailed Performance of Uncertainty Metrics for Ground Truth Prediction
This section provides a granular view of the performance of various Probabilistic Context-Free Grammar (PCFG) derived metries, confissnsst measures, and ensemble methods in predicting the correctness of SMT-LIB outputs (with respect to ground truth) for specific LLM and dataset combinations. The metrics evaluated include AUROC (Area Under the Receiver Operating Characteristic Curve) for discrimination, ECE (Expected Calibration Error) and Brier score for calibration, and AURC (Area Under the CoverCoeee Curve) along with optimal threshold (Opt. T), error rate at threshold (Err@1 T), and relative error reduction (RelEntRed) for selective prediction utility.
The UQ results for 03-mini on StrategyQA demonstrate moderate success in distinguishing correct SMT out- puts from incorrect ones. While Grammar Entropy shows good individual discriminative power (AUROC 0.7448, AURC 0.1 11).. achieving a 13.88% relative error reduction by abstaining on just 5% of samples, many other standalone PCFG metries exhibit weaker performance. The self- consisteeyyyyy metrics (Text and SMT) also perform well (AUROC 0.74), indicating that agreement between the LLM's own reasoning modalities a key signal. Notably, the Ensemble MI. method achieves the highest AUROC (0. (0.7850) and a significant relative error reduction (29.29% by abstaining on 10% of samples), underscoring the benefit of integrating diverse uncertainty signals through a learned model. The comparatively higher ECE for many metrics suggests that while discriminative, their raw scores may not always be well-calibrated probabilities.
Table 11: Uncertainty Quantification for 03-mini on StrategyQA: Ensemble ML (AUROC 0.7850) and Ceff-Consistency metries (Tex/SMT AUROC 0.74) outperform most individual PCFG metries (Grammar Entropy AUROC 0.7448 being a strong contender). This suggests that for 03-mini on this knowledge-intensive task, learned combinations or behavioral consistency signals are more potent than isolated SMT structural properties for error detection.
StrateggQA -33-mii
Metric
AUROC
ECE
Brier
AURC
Opt.I
Err@T
RelErrRed
Grammur Entropy
0.7448
0.3058
0.2340
0.1113
0.0500
0.1895
0.1388
Perplexity
0,5589
0.3107
0,2862
0,1811
0.2000
0.1750
0,2045
KL. Divergence
0,6428
0.2485
0.2385
0.1471
0,3000
0.1429
0.3506
NSUI
0.6334
0.436
0,2539
0,1250
0.1500
0,1882
0,1444
Renyi Eat (2)
0,5175
0.3303
0.2997
0.1977
0.3000
0. 1857
0,1558
Renyl Ent (0.5)
0,5973
0.3398
0,3042
0.1634
0.2500
0.1600
0,2727
Max Ent
0.6649
0.3553
0.2435
0,1297
0,0500
0.1895
0,1368
Ent Ratio
0,5385
0.3283
0,3028
0,1834
0.3000
0.1857
0,1558
Spectral Factor
0.6334
02173
0.2364
0,1319
0.1500
0,1882
0,1444
Spectral Radius
0,6334
0.2892
0.7747
0.1319
0.1500
0.1882
0,1444
Nonterminals
0,5111
0.3540
0,188
0,2006
0.2000
0.2125
0.0341
# Rules
0,5548
021177
0.2385
0.1855
0.2000
0,17
0,2045
Arg Rules/ /NT
0.2400
0.2415
0,1752
0.2000
0.1625
0.2614
Aug RHS Len
0,5350
0.6141
0.5651
0.1979
0.0500
0.2105
0.0431
Max Branch Factor
0,5181
0.1500
0.1997
0.1990
0.1500
0882
1414
Rule Dist Mean
0.5740
0.3161
0.2836
0,1752
0.2000
0.1625
0,2614
Rule Dist StdDev
0,5291
0.3995
0,3517
0.1811
0,0500
0.2105
0.0431
Rule Dist Skew
0,5833
0.3178
0,2850
0,1689
0.1500
0.17
0.79
Rule Dist Kurtosis
0,5659
0.3948
0.3420
0,1785
0.0500
0,2000
0.0909
Sell Consistency Text
0.7369
0.1604
0.1605
0.1081
0.1500
0.1529
0.3048
Sell Consisteccy SMT
0.7416
0,1523
0,1609
0,1051
0.1500
0.1529
0.3048
Ensemble Average
0.7622
0.3724
0.2916
0,1103
0.1000
0.1556
0.2929
Ensemble Weighted
0.7657
0,1738
0,1617
0,1099
0.0500
0,1895
0,1388
Ensemble MI.
0.7850
0.2090
0.1756
0,1013
0.1000
0.1556
0.2979
Ensemble Simple
0.6702
0.2065
0.2104
0.1410
0.2000
0.1500
0,3182
For D on Strategy UQ metrics show somewhat different pattern compared 03-mini. Ensemble ML again provides the best overall discrimination (AUROC 0.7709), achieving a relative error reduction of 8.96% by abstaining on 5% of the samples. Interestingly, several individual PCFG-derived metrics, such as Grammar Entropy (AUROC 0.7087). Max Entropy (AUROC 0.6851). and Spectral Factor/Radius (AUROC 0.6800), demonstrate better discriminative power than the self-consistency metries (AUROCs 0,60-0.22). This suggests that for DeepSeck-v3 on this task, intrinsic structural characteristics of the generated SMT are more indicative of correctness than its consistency with textual outputs. While Ensemble Simple yields the highest relative error reduction (35.14%), this comes at the cost of high abstention rate (Opt.T 0.50), indicating practical trade-offss in selective prediction.
The UQ performance for o3-mini on Proo/Writer is remarkably high, demonstrating the strong potential of PCFG-based metrics in formal reasoning contexts. Numerous individual metrics, including Grammar Entropy, Perplexity (AUROC 0,9194), Renyi Entropy (0.5) (AUROC 0.9301), Average Rules / NT
24

---

Table 12: Uncertainty Quantification for DeepSeek-v3 v3 on StrategyQA QA: Ensemble ML leads with an AUROC of 0.7709. Several individual PCFG-based metrics like Grammar Entropy (AUROC O. 0.7087) and Max En- tropy (AUROC 0.6851) show reasonable efficacy, outperforming self-consistency measures for this model.
Metric
AUROC
ECE
Brier
AURC
Opt.
Ere@T
RelEarRed
Grammar Entropy
0,7087
0.1575
0.2302
0.2097
0.05
0.3474
0.0612
Perplexity
0.6122
0.1601
0.2641
0.2497
0.5
0.28
0.2432
KL Divergence
0.5723
0.1393
0.2322
0.2878
0.05
0.3579
0.0227
NSUI
0.5997
0.7781
0.2191
0.2672
0.1
0.3222
0.1291
Renyi Ent (2)
06195
0.1622
0,2679
0,2429
0.45
0.2727
0,2629
Renyl Eut (0.5)
0,6126
0.1623
0.2626
0,2517
0.5
0.28
0.2432
Max Ent
0,2099
0.2271
0.1
0.3222
0.1291
Ent Ratio
0
0.1336
0.2538
0.3306
0.05
0.3684
0,043
Spectral Factor
0.68
0,0922
0.2236
0.2365
0.05
0.3474
0.0612
Spectral Rudius
0.68
0.0686
0.2148
0.2365
0.05
0.3474
0.6122
Nonterminals
06115
0.1329
0.2469
0.2547
045
0.2909
0.2138
Rules
06197
0.1109
0,2252
0,2583
0.3176
0,1415
Avg Rules/ / NT
0.6021
0,0922
0.226
0.2616
0.05
0.3579
0.0327
Avg RHS
0,5122
0,2712
0.3279
0.1
0.0691
Max Branch Factor
0.618
0.145
0.227
0 0.2688
0.05
0,3474
0,6122
Rule Dist Mean
0.6021
0.1811
0.2534
0.26166
0.05
0.3579
0.0327
Rule Dist StdDey
0.5281
0.1251
0,2573
0.3116
0.5
0.32
0.1351
Rule Dist Skew
0.6036
0.1431
0.2489
0.261
0.1
0.3444
0.0691
Rule Dist Kurtosis
0,7787
0.172
0,26
0,2754
0.3579
0.0327
Self Consistency Text
0.6017
0,2874
0,3048
0,2882
0.1
0.3444
0.0691
Consistency SMT
0.6003
0.2745
0,2513
0.1
0.3444
0.0691
Ensemble Average
0.6795
0,1214
0.2077
0,2182
0.1
0.3222
0.1291
Ensemble Weighted
0.7211
0.1257
0.2135
0.1989
0.05
0.3474
0.0612
Easemble MI.
0,7709
0.0877
0.1968
0.1847
0.05
0.3368
0.0896
Ensemble Simple
0.6401
0,1763
0,2514
0,2483
0.5
0,24
0.3514
(AUROC 0,9301), and various rule distribution statistics, achieve AUROC scores exceeding 0.90. More impressively, their AURC values are exceptionally low (e.g., 0.0008 for Grammar Entropy), translating to a 100% relative error reduction by abstaining on a small fraction of samples (e.g.. 10%). This strongly supports the hypothesis that syntactic irregularities in generated formal artifacts are highly indicative of underlying semantic errors when the task aligns well with the formal language. Ensemble methods elevate this performance to near- near-perfection (Ensemble Average AUROC 0.9949). Despite the excellent discrimination, some metrics show high ECE values (e.g., Grammar Entropy ECE 0.4419), suggesting that while they can effectively rank outputs by correctness likelihood, their raw scores may not be perfectly calibrated across the entire probability spectrum.
The UQ results for Gemini 2.0 Flash Lite on Proo/Writer present mixed picture, contrasting with 03-mini's strong performance on the same task. Many individual PCFG-derived metrics demonstrate weak discrimi- native ability, with AUROC scores often between 0.50 and 0.59 (e.g.. Grammar Entropy at 0.5380, Spectral Radius at 0.501 1). However, SMT Self Consistency stands out as significantly stronger individual per- former with an AUROC of 0.7364. Ensemble methods, particularly Ensemble ML. achieve the best overall performance (AUROC 0.7631, AURC 0.0823), leading to a 14.61 % relative error reduction when abstaining on 5% of the samples. This suggests that for Gemini 2.0 Flash Lite on ProofWriter. the structural variations in its SMT outputs are less consistently tied to semantic correctness compared to o3-mini. Instead, behavioral consistency (specifically, how its SMT outputs align with each other across multiple generations) and learned patterns across a combination of (often individually weaker) signals provide more reliable error detection.
25

---

Table 13: Uncertainty Quantification for 03-mini on ProofWriter: PCFG-derived metrics achieve exceptional discriminative power (e.g., Grammar Entropy AUROC 0.9301, AURC 0.0008), enabling near-perfect error detection with minimal abstention (100% RelEmred at Opt.T 0.10). Ensemble methods (e.g,, Ensemble Average AUROC 0.9949) further refine this, confirming that SMT structural properties are extremely strong predictors of correctness for 03-mini on this formal reasoning task.
ProofWriter Brier
Metric
AUROC
ECE
AURC
Opt.I
Err@T
RetErrRed
Grammir Entropy
0,9301
0,4419
0.25
0.0088
0.1000
0.0000
1,0000
Perplesity
0,9194
0.5358
0,3515
0.0088
0.1000
0.0000
1,0000
KL. Divergence
0,5108
0.1667
0.326
0.0074
0.0000
0.0106
0,0000
NSUI
0.5645
0,571
0,3843
0,0084
0,0000
0.0106
0,0000
Renyi Ent (2)
0,8571
0.5405
0.3598
0.0013
0.1500
0.0000
1,0000
Renyl Ent (0.5)
0.9301
0.4724
0.2879
0.0008
0.1000
0.0000
1,0000
Max Ent
0.9086
0.719%
0.555
0.0013
0.1000
0,0000
1,0000
Ratio
0.586
0.5714
0.3764
0,0055
0.5000
0.0000
1,0000
Spectral Factor
0,7473
0.3458
0.2247
0,0032
0.3000
0.0000
1,0000
Spectral Radius
0,7473
0.3545
0.2305
0.0032
0,3000
0.0000
1,0000
# Nonterminals
0.8011
0.4267
0.2397
0,0019
0.2000
0,0000
1,0000
# Rules
0,5108
0
0.2201
0,0084
0.0000
0.0106
0,0000
Arg Rules/ /NT
0.9301
0.5393
0,3499
0,0008
0.1000
100000
Avg RHS Len
0
0.6535
0.5086
0.0036
0,2500
0.0000
1,00000
Max Branch Factor
0.5914
0.2979
0.1377
0,0055
0.5000
0,0000
1,0000
Rule Dist Mean
0.9301
0.4945
0,3034
0,0008
0,1000
0,0000
1,0000
Rule Dist StdDev
0,5108
0.5555
0.3723
0.0074
0.5000
0.0000
1,0000
Rule Dist Skew
0:9301
0,4923
0.2987
0,0008
0.1000
0,0000
1,0000
Rule Dist Kurtosis
0.586
0.5107
0,3115
0,0055
0,4500
0.0000
1,0000
Self Consistency Text
0.899
0.0423
0,002
0,05000
0.0105
0.4684
Self Consistency SMT
0.7121
0.8501
0.7764
0.0025
0.1500
0.0000
1,00000
Ensemble Average
0,9949
0.3356
0,1414
0,0005
0,0500
0.0000
1,0000
Ensemble Weighted
0:9785
0.4612
0.2566
0,0003
0.0500
0,0000
1,0000
Ensemble ML.
0,9892
0.0572
0,028
0.000S
0,0500
0.0000
1,0000
Ensemble Simple
0.9355
0.4419
0,2582
0.0008
0.1000
0,0000
1,0000
Table 14: Uncertainty Quantification for Gemini 2.0 Flash Lite on ProofWriter: Performance is moderate; SMT Self Consistency (AUROC 0.7364) and Ensemble ML. (AUROC 0.7631) are the strongest UQ signals. Most individual PCFG structural metrics show weak discriminative power (many AUROCs 0.50-0.59), indicating that for this model on ProtfWriter, behavioral consistency (SMT-based) and learned combinations are more indicative of correctness than raw SMT syntactic properties alone.
Metric
AUROC
ECE
Brier
AURC
Opt.T
Ere@
RelErrRed
Grammar Entropy
0.5380
0.3185
0,2869
0,1405
0.4500
0.1667
0,1081
Perplesity
0,5934
0.3888
0.3182
0.1267
0,1000
0.1742
0.0680
KL. Divergence
0,5164
0.3000
0,2797
0,1573
0.0000
0,1869
0,0000
NSUI
0.5243
0.3166
0.2642
0,1514
0,1500
0.1845
0.0125
Renyl Ent
0,5996
0-4022
0.3368
0,1285
0.1000
0.1742
0.0680
Renyi Ent (0.5)
0,5933
0.4401
0.3581
0,1258
0.1000
0.42
0.0680
Max Ent
0,5417
0.3505
0.3045
0.1420
0.5000
0.1717
0.0811
Ent Ratio
0.5177
0.3943
0.3426
0,1548
0.2000
0.1835
0,0178
Speciral Factor
0
0.5048
0.157
0.1578
0.0000
0. 0.1869
0.0000
Spectral Radius
0.5011
0.3930
0,3122
0,1578
0.0000
0.1869
0.0000
# Nonterminals
0,5167
0.4838
0.4215
0.1672
0.1000
0,14
0.0079
Kules
0,5549
0.2422
0.2315
0.137U
0.1610
0.1383
Avg Rules/N /NT
0,5840
0.2790
0.2656
0,1301
0.3000
0,17
0,2632
Avg RHS Len
0,5631
0.3413
0.2906
0.1480
0.1000
0.1685
0.0981
Mux Branch Factor
0.5745
021899
0,2293
0,1355
0.3000
0.1522
0,1857
Rule Dist Mean
0,5838
0.4368
0.3713
0.1301
0.3000
0.1377
0.2632
Rule Dist StdDDy
0,5144
0.4474
0.3795
0,1559
0.3500
0.97
0.0384
Rule Dist Skew
0,5844
0.4511
0.3779
0.1313
0.3000
0.1522
0.1857
Rule Dist Kurtosis
0.5044
0.1437
0.1913
0.1726
0.4000
0.1610
0,1383
Self Consistency Text
0.5525
0.2283
0,2419
0,1376
0.4500
0,1545
0,1866
Sell Consistency SMT
0,7364
0.3535
U.2751
U.1031
0.2000
0.1062
0.4408
Ensemble Average
0.6140
0.3922
0,5192
0,1240
0.1000
0.1722
0.0936
Ensemble Weighted
0.7235
0.3327
0.2539
0.1035
0,1000
0. 14404
0.2484
Ensemble ML
0.7631
0.2897
0.2229
0.0823
0.0500
0.1596
0,1461
Ensemble Simple
0.6476
0.3867
0.3039
0.1071
0.2000
0.1519
0.1871
26

---

C.3 Detailed Performance of SMT-Based Uncertainty Metrics for Text-Answer Prediction
This section evaluates the efficacy of uncertainty quantification (UQ) metries derived from SMT-LIB generations in predicting the correctness of the SMT results with the corresponding textual answers. The goal is to identify when the formalization (SMT output) aligns or diverges from the model's natural language reasoning output (textual answer). On StrategyQA, o3 mini had 100% agreement between SMT and text answers, so UQ analysis for SMT-Text consistency prediction was not applicable for that specific model-dataset pair as there were no disagreements to predict. Results for other cases are detailed below.
For DeepSeek RI on StrategyQA, we assesses how well metries derived from its SMT generations can predict alignment with its textual answers. The results are strong: ensemble methods integrating these SMT features, such as Ensemble Weighted (AUROC 0.8494) and Ensemble Average (AUROC 0.8183), are highly effective. Notably, Text Self Consistency (AUROC 0. 0.8245) is top individual performer, suggesting that instability in textual outputs often correlates with Sex- divergence. Among metrics purely derived from SMT structure, Grammar Entropy (AUROC 0.7609) is noteworthy, achieving 100% relative error reduction in identifying SeT--Txt disagreements one abstains on 45% of cases. This performance in predicting SMT-Text consistency is robust and highlights that both SMT structural integrity and textual stability are key indicators. The AURC values are generally very low for top performers (e.g.. 0.0155 for Ensemble Weighted), indicating high utility in selectively flagging potential cross-modal disagreements.
Table 15: UQ for SMT--Text Consistency (DeepSeek R1, Strategy QA): SMT-derived metrics, especially ensembles (Ensemble Weighted AUROC 0.8494), effectively predict SMT-Text answer agreement. Text Self Consistency (AUROC 0.8245) is strong predictor, while SMT-derived Grammar Entropy (AUROC 0. 0.7609) also shows good utility, enabling high error reduction (100% RelEmreed Opt.T 0.45) in identifying SeT-Text divergences.
Metric
AUROC
ECE
Brier
AURC
Opt.T
Ere@T
RelErrRed
Grammar Entropy
0.7809
0.4617
0.2968
0.0216
0.4500
0.0000
1,0000
Perplesity
0.6211
0.3789
0.2640
0.0361
0,5000
0.0204
0,7114
KL Divergence
0.5776
0.4408
0.2855
0,0443
0.3000
0,0580
0,1801
NSUI
0,5963
0.2529
0.1433
0.0462
0,1000
0.0562
0,2055
Renyi Eat
0.6242
0.3980
0.2746
0,0378
0,5000
0,0204
0,7114
Renyi Ent (0.5)
0.6149
0.3942
0.2755
0.0376
0,5000
0.0408
0.4227
Max Ent
0.7174
0.3994
0.2341
0,0622
0.0500
0.0638
0.0973
Ent Ratio
0,5217
0.50M7
0.3529
0.0543
0.3000
0.0580
0,1801
Spectral Factor
0,5481
0.1533
0.0927
0,0640
0.1500
0.0476
0.3265
Spectral Radius
0.5481
0,2067
0,1166
0,0640
0.1500
0.0476
0,3265
# Nonterminals
0,5264
0.5679
0.4237
0,0557
0,5000
0.0408
0.4227
Rules
0,6087
0.3083
0,1839
0,0396
0,4000
0,0088
0. 0,2809
Avg Rules/
0,7034
0.4068
0,2532
0.0273
0,0500
0.0638
0,0973
Arg RHS
0,5637
0.2491
0.1566
0,0544
0.0562
0.2055
Mux Branch Factor
0,6801
0.3325
0.2042
0.0324
0.0500
0.0638
0.0973
Rule Mean
0,7034
0.5352
0,3733
0,2773
0,0500
0.0638
0.0973
Rule Dist StdDDe
0.6056
0.6755
0.3361
0,0413
0.2000
0,0506
0,2839
Rule Dist Skew
0,6848
0.4800
0.3260
00000
0,0000
0.0638
0.0873
Rule Dist Kurtosis
0,5311
0,2521
0,1588
0.0534
0.1000
0.0674
0,0465
Self Consistency Text
0.8245
0.1002
0.0751
0.0155
0.0500
0.0319
0,5486
Self Consistency SMI
0.2062
0.1373
0,0268
0,0500
0.2477
Ensemble Average
0,8183
0.4695
0.3058
0.0180
0,2500
0.0135
0,8089
Ensemble Weighted
0,8494
0.3256
0.1711
0.0155
0,0500
0.0319
0.5486
Ensemble MI.
0.8245
0.3084
0.2003
0,0170
0.2000
0.0380
0.4629
Ensemble Simple
0.6957
0.4363
0.2748
0,0316
0.1000
0.0562
0.2055
When predicting SMT--Txt consistency for DeepSeek v3 on StrategyQA, UQ metrics based on SMT gener- ations prove highly effective. The Ensemble MI. approach, which learns from various SMT-derived features, achieves an impressive AUROC of 0.8517 7 and offers a 55.56% relative error reduction in spotting SMT- Text disagreements when abstaining on 25% of samples. Good individual predictors include S.MT-derived Grammar Entropy (AUROC 0.7354) and SMT Self Consistency (AUROC 0.71 This demonstrates that for DeepSeek v3, deviations from typical SMT structure (signaled by grammar entropy) or inconsistencies in the SMT generation process itself are strong indicators that the SMT output might not align with the model's textual answer. The low AURC (0.0573) for Ensemble ML highlights its practical utility. This task of predicting internal consistency (SMT-Text) shows strong signals, comparable to or even clearer (e.g. for Ensemble MI.) than predicting SMT-Ground Truth correctness for this model on the same dataset.
For Gemini Flash 2.0 Lite on StrategyQA, the task of predicting SMT-Text consistency reveals a standout individual metrie: Rule Distribution Kurtosis from the SMT generations achieves very high AUROC of 0.8695. This is particularly interesting finding, as it suggests that the "tailedness" or outlier presence
27

---

Table 16: UQ for SMT-Text Consistency (DeepSeek v3, StrategyQA): Ensemble ML using SMT-derived features shows excellent performance (AUROC 0.8517) predicting Sex- agreement, with a 55.56% relative error reduction. SMT-derived Grammar Entropy (AUROC 0.7354) and SMT Self Consistency (AUROC 0.7116) also serve as solid individual predictors, indicating that atypical SMT structures and generation instability can flag potential Tex- divergences.
Metric
AUROC
ECE
AURC
Opt.T
Err@T
RellirRRed
Grammar Entropy
0.7354
0.3058
0.2551
0.097
0.0500
0.1789
0.1479
Perpledit
0,6721
0.3282
0.2718
0.1208
0,3000
0.1143
0.4558
KL Divergence
0.5335
0.1195
0.178
0,1633
0,0500
0.2000
0,0476
NSUI
0,5973
0.1768
0.1919
0,1411
0,0500
0.1895
0.0977
Reuyi Ent
0.3403
0.2808
0.3000
0.1000
0.5238
Renyi Ent (0.5)
0,6667
0.3333
0.2751
0.1223
0.3500
0.1077
0.4872
Max Ent
0.1309
0,1738
0,1247
0.1000
1,00
Ent Ratio
0.6154
0,409]
0,3307
0,1446
0.5000
0,0000
0,5238
Spectral Factor
0,7034
0.1254
0.158
0.1206
0.1000
0.1667
0,2063
Spectral Radius
0.7034
0.1896
0,1752
0.1206
0.1000
0.1667
0,2063
# Nonterminals
0,5549
0.2271
0.2455
0.148
0,0500
0,2000
0.0476
Rules
0.2025
0.2077
0.1485
Avg Rules/ NNT
0,6034
0.1393
0.1854
0,1399
0,0500
0.18
0.0977
Avg RTS
0,5208
0.1254
0,1818
0,1972
0.2000
0.0476
Max Branch Factor
0.5937
0.1563
0,192
0,1457
0,1000
0,1889
0,10
Rule Dist Mean
0,6034
0.321
U.2742
U.1399
0,0500
0.1895
0,0677
Rule Dist SldDev
0.6281
0.2226
0.2221
0,1445
0.3000
0.1571
0,2517
Rule Dist Skew
0,5986
0.3057
0.26199
0,1406
0,0500
0,1895
0,0077
Rule Dist Kurfosás
0.07.3
0.1576
0,1256
0.1895
0,0977
Self Convistency Text
0,5778
0.1874
0.2008
0.1754
0.1500
0.1766
0.97
Self Consistency SMT
0,71
0.1662
0,1900
0,1054
0.1000
0.17778
0,1534
Ensemble Average
0.7064
0.1876
0,1831
0,0983
0.1000
0.1667
0,2063
Ensemble Weighted
0,7709
0,234
0.1971
0,07988
0.0500
0.1895
0.0877
Ensemble MI.
0.8517
0.1861
0.1703
0,0573
0.2500
0.0933
0.5556
Ensemble Simple
0.6727
0
0.2567
0.1119
0.1500
0.1765
0,1597
in the distribution of PCFG rules used during SMT generation is a very strong signal of whether the SMT output will align with the textual answer for this model. This metric's performance surpasses many other individual PCFG metrics (e.g., Grammar Entropy AUROC 0.6622, Perplexity AUROC 0.7212). Ensemble methods, like Ensemble Weighted (AUROC 0.8070) and Ensemble Average (AUROC 0.7927), provide robust overall performance, leveraging combinations of signals. The strong performance of kurtosis aligns with the our discussion about "syntactic fingerprints" and how atypical SMT patterns (like bimodal distributions captured by kurtosis) can signal reasoning issues or misalignments. The AURC for Kurtosis (0.4448) suggests that while discriminative, its practical utility in terms of risk reduction might require careful thresholding, achieving 30.56% error reduction at 50% abstention rate.
The results for 03-mini on ProofWriter for predicting SMT-Text consistency are exceptional. Ensemble ML and Ensemble Weighted methods achieve perfect AUROC scores of 1.0000, signifying an ability to flawlessly distinguish SMT outputs that align with textual answers from those that diverge. This allows for a 100% relative error reduction with very low 5% abstention rate. Beyond ensembles, many individual PCFG metries derived from the SMT generations show extremely high predictive capabilities. For instance, Ent Ratio (AUROC 0.9677), Rule Dist Kurtosis (AUROC 0.9462), Max Ent (AUROC 0.9355), and NSUI (AUROC 0.9355) are all remarkably strong predictors, each achieving 100% relative error reduction at their respective optimal thresholds. This indicates that for o3-mini, particularly on formal reasoning task like ProofWriter, the structural and probabilistic characteristics of its SMT generations are almost perfectly indicative of whether its formal and textual reasoning pathways are aligned. The exceptionally low AURC values (e.g., 0.0003 for Ensemble ML) further emphasize the practical certainty offered by these UQ measures in this context. This level of predictability for Tex- consistency is even more pronounced than some of the SMT-Ground Truth prediction results for this model, demonnttrting the power of SMT features for diagnosing internal reasoning coherence.
28

---

Table 17: UQ for SMT-Text Consisteney (Gemini Flash 2.0 Lite, StrategyQA): Rule Distribution Kurtosis (AUROC 0.8695) from SMT generations is an exceptionally strong individual predictor of Sex--Text agreement, significantly outperforming other PCFG metrics. Ensemble methods (e.g. Ensemble Weighted AUROC 0,8070) also perform well. This highlights a specific SMT structural feature as a key indicator of cross-modal alignment for this model.
Metric
AUROC
ECE
Brier
AURC
Opt.T
Err@T
RelErrRed
Grammar Entropy
0,6622
0.1277
0.2095
U.5689
0.1000
0.6889
0,0432
Perplexity
0.7212
0.3255
0.2849
0.5273
0,0500
0.7053
0.0205
KT. Divergence
0,5486
0.2387
0.263
0.6341
0.1000
0.7000
0.0278
NSUI
0.6741
0.1195
0,1624
0,5221
0.5000
0.0600
0,0833
Renyi Ent (2)
0.7624
0.3192
0.2624
U.50337
0.1000
0.6889
0.0432
Renyi Eat (0.5)
0.6994
0.2766
0,2619
0,5438
0,0500
0.7053
0.0205
Max Ent
0.5982
0,3401
0,3083
0.59
0.3000
0,6714
0,0675
Ent Ratio
0
0.1641
0.2511
0.3366
0.2500
0.6667
0.0741
Spectral Factor
0.6538
0.0943
0,1677
0,5316
0.5000
0.6600
0,0833
Spectral Radius
0,6538
0.1648
0.1703
0.5316
0,5000
0.6600
0.0833
Nonterminals
0.5166
0.418
0,3958
0.6509
0.3500
0.6769
0.0598
# Rules
0,5749
0.4256
0.3818
0.6252
0.1000
0.6889
0,0432
Avg Rules/
0.2913
0.2761
0,5925
0,2500
0.6400
0.1111
Avg RHS Len
0.6014
0,4855
0,442
0.6038
0,0500
0.7053
0,0205
Max Branch Factor
0,5818
0.5167
0.4747
06611
0,0500
0.7053
0.0205
Rule Dist Mean
0.6565
0,2197
0,228
0,5923
0.2500
0,6400
011111
Rule Dist StdDee
0,7183
0,3136
0.2807
0,5455
0.1500
0.6706
0,0686
Rule Dist Skew
0.1783
0.2199
0,572
0.1111
Rule Dist Kurtosis
0,8695
0.3187
0.2412
0,4448
0,5000
0.5000
0.3055
Consistency Text
0.535
0,2788
0.2616
0,6064
0,3500
0.6462
0. 1,266
Self Consistency SMT
0.7505
0.538
0.4357
0,4822
0.5000
0.5600
0,2222
Ensemble Average
0.7927
0.1531
0.1702
0.4848
0,4000
0.5833
0.1898
Ensemble Weighted
0.807
0.1673
0,1632
0,4718
0.3000
0.6143
0, 0,1468
Ensemble ML
0.7946
0.1308
0,1592
0.4784
0.5000
0,5400
0,2500
Ensemble Simple
0.0796
0.1568
0,4929
0.1500
0.6824
0,0523
Table 18: UQ for SMT-Text Consistency (o3-mini, ProofWriter): S.TT-derived UQ metrics demonstrate outstanding performance, with Ensemble ML and Ensemble Weighted achieving perfect AUROC (1.0000) in predicting SMT- agreement. aggreeeetn Numerous individual PCFG metrics, such as Ent Ratio (AUROC 0.9677) and Rule Dist Kurtosis (AUROC 0.9462), are also exceptionally effective, enabling complete identification of SMT-Text inconsistencies with minimal abstention. This underscores a very strong link between SMT formalization properties and cross-modal reasoning alignment for 03-mini on this formal task.
Metric
AUROC
ECE
Brier
AURC
Opt.T
E
RelErrRed
Granmar Eutropy
0,8602
0.4419
0.2542
0.0013
0.00
1.00
Perplesity
0.9032
0.4429
0.2616
000113
0.10
0.00
1.00
Divergence
0.6667
0,5167
0.3238
0.0099
0.00
1.00
NSUI
0.9355
0.4077
0,2172
0.0008
0.10
0.00
1.00
Renyi Ent (2)
0.9032
0.4382
0.2580
0.0013
0.10
0.00
1.00
Renyi Eut (0.5)
0.8925
0.5063
0.3246
0.0013
0.15
0.00
1.00
Max Ent
0.9355
0,2589
0.1029
0.0008
0.10
0.00
1.00
Ratio
0.9677
0.4074
0,2082
0,003
Spectral Factor
0,5269
0.6329
0.5061
0.0084
0.00
0.01
0.00
Spectral Radius
0.5269
0.6243
0.4953
0.0844
0.01
0.00
# Nonterminalss
0.6505
0,5520
0,3650
0.0047
0.40
0.00
1.00
Rules
0,5108
0.4186
0.2201
0.0064
0.50
0.00
1.00
Avg Rules/ /NT
0
0.4394
0,2554
0.0026
0.25
0.00
1,00
Avg RHS Len
0.5084
0.6535
0,5116
0.0074
0.50
0.00
1.00
Max Branch Factor
0.7419
0.6809
0,5100
010322
1,00
Rule Dist Mean
0,8011
0.4842
0.2971
0.0026
0.25
0.00
1.00
Rule StdDey
0.8710
0.4232
0.2392
0.0013
0.00
1,00
Rule Dist Skew
0.8122
0,4864
0.2 0,2964
0.0019
0.20
0.00
1.00
Rule Dist Kurtosis
0.9462
0,5107
0.3056
0.0008
0.10
0.00
1.00
Self Consistency Text
0,7050
0.9352
0.9023
0.0030
0.30
0.00
1.00
Self Consistency SMT
0,7100
0.8600
0,7863
0.0030
0.30
0.00
1.00
Ensemble Average
0.1741
0.0007
1.00
Easemble Weighted
1.0000
0.4231
0.2375
0.0003
0.05
0.00
1.00
Ensemble ML
1.0000
0.0496
0.0199
0.0003
0.00
1,00
Ensemble Simple
0.6667
0,4419
0.2661
0.0039
0.35
0.00
1,00
29

---

D Supplementary Experimental Details
The comprehensive PCFG analysis underpinning our uncertainty quantification was conducted on focused set of benchmarks. Specificallyy, for 100 questions each from the StrategyQA, ProofWriter, and ProntoQA datasets, corpus of NswT 100 SMT-LIB v2 program samples per question was generated. The FOLIO dataset was excluded from this detailed PCFG study due to challenges in obtaining consistently robust SMT formalizations from the evaluated LLMs. Each SMT program within these corpora was parsed using ANTLR-based parser to extract its constituent production rules. For the generation of these primary SMT samples used in uncertainty quantification (distinct from the temperature ablation study), LLM sampling temperature
maintained its default setting to promote more deterministic outputs, with up to 10 generation attempts per SMT sample to ensure corpus completeness.
For each of the selected questions, a unique PCFG was induced from its conresponding 100 SMT samples. Rule probabilities within these per-question PCFGs were estimated via Maximum Likelihood Estimation (MLE), incorporating Lidstone smoothing (specifically, Laplace smoothing with 3, = 1) to manage unseen production rules. Beyond the metries detailed in the main methodology, specific configurations included the computation of Rényi entropy for orders 0.5 and a 2.0 (Collision Entropy).
The evaluation framework for the derived uncertainty metrics incorporated specific settings. Expected Calibration Error (ECE) was calculated using 10 discretization bins for confidence scores. In the analysis of selective prediction utility (eπror vs. abstention), optimal abstention thresholds were determined by targeting maximum relative eπrоr reduction while considering abstention levels to practical maximum of 50%. For our Ensemble ML predictor, Logistic Regression model was employed, configured with balanced class weights and trained for up to 10,000 iterations on scaled features derived from the suite of PCFG uncertainty metries.
E
SMT Error Ratios vs Text Error Ratios
Nat SMI Error natlos with Marginals
Nut vs. SMI Error Ratios with Marginals
02
Figure 14: SMT vs. Text Error Ratio Analysis for 03-mini: Illustrates well-calibrated SMT generation, indicated by strong correlation between SMT and Text emror patterns.
Figure 15: SMT vs. Text Error Ratio Analysis for Gemini Flash 2.0: Depicts less-calibrated SMT generation, evidenced by a weaker correlation between SMT and Text error patterss.
The figures juxtapose SMT versus Text error ratios (with marginals) for o3-mini (Fig. 14) and Gemini Flash 2.0 (Fig. 15); the Text enror ratio is defined as the proportion of incorrect direct textual answers from the LLM per question out of the many samples, while the SMT error ratio the proportion of incorrect answers derived from its SMT-LIB formalizations. 03-mini exhibits notable correlation between its SMT and Text error distributions, characteristic of well-calibrated SMT generation process where formalization enrors tend to align with textual reasoning emror.. In contrast, Gemini Flash 2.0 shows weaker correlation,
30

---

suggesting its SMT generations may introduce enrors or exhibit patterns less consistently coupled with its textual output, indicative of poorer calibration. This comparative error ratio analysis valuable for assessing the fidelity of an LLM's 's autoformalization. Strong SMT-Text error correlation implies that the SMT modality can be more reliable indicator of the I.LM's general reasoning tendencies for problem, making SMTT-derived uncertainty metries potentially more transferable. Poor correlation, however, signals a divergence between textual reasoning and formalization, cautioning against using SMT outputs as direct proxies without careful consideration of modality-specific error sources and motivating efforts towards better SMT-Text reasoning alignment.
F
Qualitative Analysis
Beyond quantitative uncertainty metrics, the PCFG framework, by its nature of parsing and structuring program ensembles, lends itself to a nuanced qualitative analysis of LLM-generated formal artifacts. Initial explorations can focus broad characteristics such as the distributtinn of SMT-LIB sorts (datatypes) employed or the prevalent logical fragments (e.g., 'QF_LIA', 'QF_ (QF_AUBVV) selected by the LLM for a given problem class. However, more profound understanding of an LLM's formalization strategy emerges from a detailed examination of substructures, like the assert statements, which constitute the semantic core of an SMT program by stipulating the conditions and axioms for the solver. Our PCFG-based analysis of these assertions, and the logical architectures therein, reveals critical patterns in how LLMs attempt to translate natural language problem specifications into rigorous, machine-interpretabll logic.
When an LLM generates multiple SMT program samples for a single natural language input, the per- probleo induced PCFG captures a distribution over grammatical structures. This distribution inherently models the LLM's normative formalization pathways alongside its idiosyncratic variations, particularly in the construction of assert statements and their nested logical terms -innud-ncluuingg quantifiers (forall, exists), logical connectives (=>, and, or, not), and predicate applications. Analyzing the probabilities and diversity of production rules within these PCFGs allows for the identification and interpretation of several key types of divergences and tendencies in formal specification:
Formalization Aliasing and Representational Stability A core aspect of a problem specification may elicit syntactically diverse, yet ideally logically equivalent, assert statements across an ensemble of LLM generations. For instance, implication A B might be directly asserted or rendered as -AV B. The PCFG reflects such syntactic polymorphism through multiple, lower-probability rule sequences mapping to the same underlying semantic constraint. A high degree of such variability for asserting fundamental problem axioms often signals the LLM's lack a converged or canonical fornalization strategy, potentially indicating uncertainty or representational underspecification for that particular logical construct.
Variance in Logical Decomposition and Structural Complexity The PCFG rule sets unveil the LLM's implicit preferences regarding the structural complexity and granularity of asserted logical terms. For a given problem, some SMT samples might employ deeply nested quantifiers and connectives within monolithic assert statement. In contrast, other samples might exhibit preference for flatter, more direct assertions or decompose a complex axiom into several simpler, conjoined assert statements. This divergence in logical decomposition strategies is captured by differing rule probabilities and derivation depths within the PCFG, pointing to variations in the LLM's approach to abstraction and information chunking during the formalization process.
Identification of Atypical or Anomalous Assertions Occasionally, an LLM may generate assert statements possessing highly unusual or infrequent syntactic structures relative to the typical formalizations observed for given problem context or across a dataset. The PCFG methodology inherently highlights these as low-probability production rules or derivations. Qualitative inspection of the SMT code corresponding to these rare assertion patterns can uncover unique, potentially innovative, or conversely, flawed and overly convoluted ways the LLM attempts to axiomatize specific constraints, offering insights into its error modes or its capacity for novel formal expression.
Semantic Divergence in Axiomatization More critically, divergences can be semantic rather than merely syntactic, leading to logically distinct problem formalizations from the same natural language input. Such semantic drift often manifests as significantly different asserted terms within assert statements, pointing to L.IM misinterpretation, unresolved ambiguity, or flaws in its inferential reasoning. For example, if an input "All engineers use LaTeX" is ambiguously formalized, one SMT sample might correctly
31

---

assert (forall ((x Engineer)) (usesLaTeX x)), while semantically divergent sample might erroneously assert (forall ((x User)) (implies (usesLaTeX x) (isEngineer x))). The PCFG rules governing the predicates, variables, and logical structure of terms within these assertions would markedly differ, directly reflecting this semantic incongruity and providing a diagnostic trace.
Fidelity in Representing Ground Facts For declarative factual statements present in the input (e.g.. "Constantine a logician"), the LLM is expected to consistently assert the corresponding ground fact in stable manner. If the PCFG reveals multiple, conflicting, unstable rule applications for asserting properties of specific entities (e.g., some derivations asserting "iisLogician constantine) while others, for the same conceptual imput fact, generate (isPhilosopper constantine) vary the predicate structure), this indicates a deficiency in the LLM's fidelity in extracting and consistently formalizing clementary factual information, pointing potential grounding issues.
Program
Program
Program
Program
Logic QF
logic
logic
logic
(declare-const rela-
(declare-cont 02 Int)
(declare-fun people.groghte Int.)
(declare-comet KN Int)
moo_tot Int:)
(declare-conat JC Tnt.)
(declare-comt CA Tnt)
(declare rela-
(sssert (> 02 03)
(declare-tee -un peoplo_caeear
(assert ( KB GA33
tion_comt__J Int)
(sczers
(ansert:
(assort (> relation, count,
(sscers (> 32 2003
(ansert (tm people_gesghe
(azsert (+ ca 13)
relation,comm count,.))
(sccers (>+ 02 103)
033
(chock-sat)
(sssert (>= molatiio_.comm....
(sssers (>m JC 133
(aneert: (- people.coene 03)
(get-moddl))
())
eat)
(assert people. googheg peo
(ssport (> relation,comt,,
(get soot-zodel)
plo plo_caerar))
0))
(anmert: O- people.genghte
(chock cas) (get-podde)
100000))
people,caecar
500000))
(chock sat) (get-sodel))
Table 19: Divergent LLM Formalizations of a StrategyQA Problem: Sample SMT-LIB outputs illustrating varied axiomatization strategies, with assert statements highlighted (blue). Such variations are central to the qualitative PCFG analysis discussed.
G Computational Efficiency
The overhead of our uncertainty quantification pipeline is minimal and does not constitute performance bottleneck. Table 20 presents comprehensive runtime and memory profiles for the key computational com- ponents. Z3 solver execution individual SMT programs averages 10ms with minimal memory footprint (24.7MB mean). PCFG construction from 100 SMT samples requires approximately 1.3 seconds, while sub- sequent uncertainty metric calculation adds only 0.4 seconds. These measurements confirm that our experi- mental pipeline is dominated by LLM inference time rather than formal verification or uncertainty quantifica- tion overhead. All experiments employed a 30-second timcout for Z3 execution to handle edge cases where malformed SMT programs might cause solver delays, though such timcouts were rarely triggered in practice.
Table 20: Runtime and memory profiles for uncertainty quantification pipeline components. All
measurements represent averages across thousands of executions on our experimental infrastructure.
Component
Mean
Median
P90
P95
Std Dev
Peak Mem
Z3 per SMT program
10ms
10ms
11ms
11ms
Ims
26.4MBB
PCFG construction (100 SMT)
1.297s
1.286s
1.454s
1.527s
0.131s
161.9MB
UQ metrics calculation
0.408s
0.402s
0.423s
0.431s
0.023s
118.9MB
H Discussion around Risk Thresholds
Calibration and Risk Management: The relationship between typicality and correctness isn't straightforward; metrics with superior discriminative ability often exhibit poor calibration, indicating anomaly magnitude doesn't tt linearly predict emor probability. This calibration challenge necessitates careful deployment considerations. Our evaluation explicitly addresses this through multiple complementary metrics: Expected Calibration Error (ECE) measures how well predicted confidence scores align with
32

---

empirical accuracy; Brier scores quantify probabilistic prediction quality; and the Area Under the Curve (AURC) evaluates practical risk mitigation through selective abstention. For instance, Priterriter with 03-mini, our Ensemble MI. method achieves both excellent discrimination (AUROC=0.9892) and strong calibration (FCF=000572, Brier=0.0280), demonstrating that well-calibrated uncertainty estimates are achievable through careful metric fusion.
The selective verification framework inherently provides risk management: engineers can adjust abstention thresholds along the Risk-Coverage curve based on application gqquirements-chosiiee low error rates with higher abstention for safety- critticll domains, higher coverage with moderate enror rates for less critical applications. Our AURC metric summarizes this tradeoff across all possible thresholds, with our ensemble methods consistently achieving lower AURC values than individual metrics, indicating superior cove-coe profiles. Importantly, our approach is conservative by design, erring toward caution by abstaining when uncertain rather than providing false confidence. When our UQ metries themselves exhibit miscalibration, the multi-metric evaluation strategy (AUROC, ECE, Brier, AURC) provides redundancy catch such cases- no single metric failure can compromise the entire uncertainty quantification pipeline.
I Extensibility to Prolog: Pilot Study
To demonstrate that our PCFG-base uncertainty quantification framework generalizes beyond SMT-LIB other formal languages, we conducted pilot study applying our methodology to Prolog programs. This extensibility validation is critical for establishing that our approach addresses fundamental aspects of LLL --geerrttee formal artifacts rather than being narrowly tailored SMT-specific properties.
L11 Methodology
Our implementation leverages the modular design of our framework: the PCFG construction pipeline uses ANTLR for parsing, which supports any language with defined grammar specification. We utilized the Prolog-g4 grammar from the ANTLR-vv public repository, requiring only minimal adapter code integrate Prolog parsing into existing uncertainty quantification pipeline. This demonstrates that extending to new formal languages requires engineering effort proportional to grammar complexity rather than fundamental algorithmic redesign.
1.2 Example: Logical Statement Translation
We converted the example from Figure of the main paper--"Fxeryone who studies math or physics and works hard will succeed" five semantically distinct Prolog formalizations that mirror the logical variations observed in SMT-LIB generation:
Program
% Facts person (alice), person(bob) person(charlie)
studies, studies_math ww..aathhhalli (alice) studies_physicee swtpssssppssscsce (bob).
works (bobb works hard haw.harrrrhharha (charlie).
% Rule
succeeds (X)
studies_matee (X).
succeeds (X)
studies_physicsdde
works_hard
% On load: print all solutions and exit
33

---

:- initialization (main).
main
forall (succeeds (X), writeln (X)),
halt.
Program 2
% Facts
person person(alice). (alice).
person (bob) person(charliag
studies_nme pundies_mathhliieee (alice). studies_physsica (bob).
works (hakss works_harde (arkh__erd(caarlee))
Rule
succeeds (X)
( studies_mathh (X)
studies_physicas
works_hare (x)
% On load: print all solutions and exit :- initializationnmain))
main :-
forall (succeeds (X), vriteln(X)), halt.
Program 3
% Facts person (alice). person person (charllc).
studies_math (alicce)) studies_phyeee hatss__physccssse (bob). works (badd works (ttaaaarr(chrri))
% Toggle which implication you want: option (math). % comment this and uncomment the next to switch % option (physics). option(physicss).
% Branch 1: (tudiesMathxx) Succeeds (x)
succeeds (X) :-
option(math)
studies__ate Siciiis_mathhh (x)
% Branch 2: (StudiesPhysicssx) WorksHard(xx) -> Succeeds (x)
succeeds (X) option (physics), studies_physiics(M works_hand (xrd
% On load: print all solutions and exit
34

---

:- initialization (main).
main
forall (succeeds (X), writeln (X)),
halt.
Program 4
% Facts
person(alice) person(bob) person(charlie).
studies (aliee__ma((aaice)))) studies__hyyee cttpiieesppyyiccsscccc (bob). works (bbbd works htr.
Nested implication expands two rules succeeds (X) :-
works_harde
studies_mate satess_mahhhheh (X)
succeeds (X)
works_hard(C) studies_physicee
% On load: print all solutions and exit :- initializatioonmaiinn main
forall (succeeds (x), (X)) halt.
Program
% Facts person (alice). berson(bob) person(charlie).
studies_matee (aliccc studies_phyeiie (bob) works (bodd works hard (charlleeee)))
% Forward direction succeeds (X) :- studies_man pacees_aathhhee (X).
succeeds (X) :-
studies_physics works (X)
% Backward direction to enforce
crudies_mathle (X)
succeeds (X),
\+ (studies_physiiss()) works_hard (X)).
studies (rrdiees_physice($ (X) :- succeeds(X))
35

---

works har__harddh
% On load: print all solutions and exit :- initialization (main).
main :-
forall (succeeds (X), writeln (X)),
halt.
I.3 PCFG Analysis Results
From these five programs, our pipeline successfully constructed PCFG with the following characteristics:
Table 21: PCFG statistics for Prolog pilot study programs.
Metric
Value
Total rule applications
560
Unique production rules
Non-terminal symbols
7
Maximum rule probability
1.0
Minimum rule probability
0.0086
Average rule probability
0.2121
Rules per non-terminal
4.7
Maximum branching factor
16
Grammar entropy
0.0
KL divergence (from uniform)
1.34
Spectral radius
0.83
The successfully computed uncertainty metrics (grammar entropy. spectral radius, KL divergence, etc.) demonstrate that our framework's core algorithms operate seamlessly on Prolog programs without modification. The low grammar entropy (0.0) correctly captures that these five programs, while semantically distinct, share highly similar syntactic structure-4t scenario our framework is designed to detect as potential formalization uncertainty masked by superficial similarity.
L,4 Implications for Framework Generality
This pilot study establishes three key results:
(1) Minimal Engineering Overhead: Extending our framework to Prolog required approximately 2-3 hours of engineering time integrate the existing ANTLR Prolog grammar and write adapter code. No modifications to core PCFG algorithms were necessary.
Cross-Language Language Applicability: The fundamental insight- that syntactic typicality in L-gggeeerated formal artifacts signals semantic uncertainty- mmcertainty-ttaasseendd transcends specific formal languages. The same PCFG- derived metrics (entropy, spectral radius, rule distributions) computed for SMT-LIB apply equally to Prolog.
(2) Cross-
(3) Future Directions: This extensibility opens exciting possibilities for uncertainty quantification in ceneral-purposs programming languages (Python, Java) and other verification languages (Coq, Isabelle, Lean), provided context-free grammars are available. The framework's generality positions a universal tool for assessing --geeerrtee structured artifacts across domains.
Limitation:
Conducting full-scale empirical evaluation of Prolog-bast based uncertainty metrics on reasoning benchmarks (cquivalent to our SMT-LIB experiments) would require substantial additional resources and beyond the scope of this work. However, the successful technical integration and metric computation provide strong evidence of feasibility for future research.
1.5 Implementation Notes
All metrics are computed per-instance from the PCFG induced from N 100 SMT-LIB samples. Normalization for ensemble methods uses min-max scaling to [0,1] based on training set statistics. Code for all metric computations will be released with our open-source implementation.
36

---

166 Example PCFG Characteristics
To provide concrete understanding of the PCFGs induced from LLM -aMM-geeerteed SMT programs, we present detailed statistics from representative example. The following measurements come from a single question in the ProofWriter dataset, which produced the longest SMT programs in our corpus, analyzed using 100 samples from 03-mini:
Table 22: Detailed PCPG statistics for a representative ProofWriter instance with 100 SMT-LIB samples.
Property
Value
Total rule applications across corpus
63,202
Unique production nules observed
42
Number of non-terminal symbols
24
Maximum probability (any rule)
1.0
Minimum probability (any rule)
0.00035
Average probability (across unique rules)
0.5714
Interpretation: Despite 100 diverse samples generating over 63,000 rule applications, only 42 unique production rules from the SMT-LIB grammar were utilized. This demonstrates that LLMs, even when sampling with temperature, explore relatively constrained subset of the full grammar a key insight enabling our tractable PCFG-based uncertainty quantification. The wide range of nule probabilities (spanning nearly four orders of magnitude from 0.00035 to 1 1.0) provides rich distributional information for our entropy-based and statistical metrics.
Scalability: These statistics confirm that PCFG construction remains computationally efficient even for complex reasoning tasks. The grammar remains manageable in size (24 non-terminals, 42 unique rules) while capturing meaningful structural variation across the 100-sample ensemble.
37

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: These claims are supported by the experimental results presented throughout the paper, particularly in Tables 1-4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made
the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We present all known limitations in the discussion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "I "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to viola- tions of these assumptions (e.g., independence assumptions, noiseless settings, model well- specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken low lighting. Or speech- to provide closed captions for online lectures because it fails to handle technical jargon.
system might not used reliably
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Proof Theorem (presented in the methodology section) is in the appendix due to lack of space.
38

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross-refernneed.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Sufficient details are provided in both the main text of the paper and the appendix. Moreover, we will release key pieces of code that require non-trivial engineering effort at the time of acceptance, for example our PCFG creation pipeline.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may he necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reprodueibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e-g., to registered users), but should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
39

---

Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines hattps://hipss.ccpubbll
guides /CodeSebmissii ossonncyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines
http//uudese/ee/ee Leteee///ooobbeiiiiceeeeee ssissssinsssss ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All details have been provided, between the methodology and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and conrectly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Our comprehensive evaluation framework, representing substantial resource investment in frontier model sampling, was meticulously designed with robust statistical protocols ensure all observed performance differentials reflect meaningful and actionable insights.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confidence intervals, or statistical significance tests, least the experiments that support the main
claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI. the hypothesis of Normality of errors is not verified.
40

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [No]
Justification: The majority of computational resources were consumed by API credits. However, our algorithm is sufficiently efficient that the paper's results can be replicated using the processing power of standard laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:/ /teeer///eeursspp http://trpp..pppppliiii/ee/c/eee htcppullic/Ebhcccuuudeee ines?
Answer: [Yes]
Justification: Yes. No issues.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our motivation for problem-solving stems from the imperative for verifiable LLM reasoning.
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance). fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will foundational research and not tied to par- ticular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point out. For example, is legitimate to point out that an improvement in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm op- timizing neural networks could enable people to train models that generate Deepfakes faster.
41

---

The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system lears from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification; Does not apply.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse dual-use should be released with neces- sary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recogmize that providing effective safeguards is challenging, and many papers do not require this, we encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have cited all relevant authors, and related work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswi thcode. com/coooo/oooo /atastss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
At the time of submission, we do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/coodemoodel as part of their submis- sions via structured templates. This includes details about training. license, limitations, etc.
42

---

The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) obtained?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMss if it is important, original, non-standard component of the core methods in this research? Note that the I.LM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification: We use LLMs component of our verifiable reasoning pipeline.
Guidelines:
The answer NA means that the core method development in this research does not involve
LLMs as any important, original, or non-standard components.
Please refer to our LLM policy what should or should not be described.
wwweeeep...//ooaeeeeeeeeeeeeeeee Crc.offereneee22225.5. for
43


Reviews:
[{"review_id": "s4PuPbRplB", "reviewer": "Reviewer_sS7b", "summary": "The work addresses the problem of uncertainty quantification for LLMs when used to generate formal artifacts like SMT-LIB programs. For this purpose, it introduces a sampling-based method to estimate a probabilistic CFG for the model's underlying distribution for SMT-LIB programs. They also come up with a taxonomy of uncertainty and evaluate how various UQ metrics based on their methodology perform on four on four datasets commonly used for reasoning tasks: StrategyQA, ProntoQA, ProofWriter and FOLIO.", "questions": "* Do you have any comments on the lack of a comparison with uncertainty measures considering semantic clustering (e.g., Kuhn et al., ICLR'23)? \n\n* In the Approximations section (lines 94-103) there is a description about how the N samples are used to infer the various production rules for the pCFG. I wonder how reliant this technique is on the quality of samples produced? For instance, would increasing the temperature to get more diverse samples harm the accuracy of the estimated pCFG?\n\n* Just to make sure I got it right, you use 5 samples per question to construct the grammar? Did you try to vary this number, maybe increase it?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n* I think the problem addressed by the paper is important. There seem to be a few recent works that rely on the LLM formlasing certain logical tasks, and then using some type of solver to get an answer. However, many of the works don't clearly address the issue of the formalization not being accurate. That's a weak spot that may invalidate all the benefits of the subsequent formal reasoning.\n\n* Although prior work (e.g., Li et al., CAV’24) has explored using pCFGs to model LLM outputs (which should be clearer acknowledged in the related works), I think this paper is the first to apply pCFGs specifically for uncertainty estimation.\n\nWeaknesses:\n\n* The approach is limited to syntactic variations between candidates and does not consider semantic equivalence. For instance, the authors should check out the work on semantic uncertainty in Kuhn et al., ICLR'23 and Farquhar et al, Nature'24. This is for me a serious issue with this paper. In this paper, I think that syntactically different but semantically equivalent samples will result in a high grammar entropy. However, intuitively and according to Kuhn at al., that scenario should lead to low entropy.\n\n* Clarity wise, Figure 1 is difficult to read, which undermines its usefulness as an overview. Given the large number of derived metrics introduced in the paper, a better organised by using some sort of abstraction would be helpful. The same issue also made it challenging at times to interpret the results in Tables 3 and 4.", "was_revised": true, "final_justification": "The authors’ response addressed my main concerns regarding the comparison with semantic uncertainty and, to some extent, the large number of required samples, leading me to increase my score. \n\nWhile I appreciate their point that the sample count could be reduced from the current 100, I expect this would likely lead to a drop in performance.", "rebuttal": "We thank you for your thoughtful and constructive comments. We are happy to hear that you recognise the importance of the problem we address, and the novelty of applying PCFGs for uncertainty estimation. We find the questions you have raised to be very insightful and have ultimately led us to strengthen our paper. \n\nWe address each point below: \n\n**1\\. On Syntactic vs. Semantic Uncertainty (Weakness 1 & Question 1\\)**\n\n**Our Response:** Thanks for pointing this out. We conducted the experiments you requested, and here are the results.\n\n|  |  | AUROC | ECE | Brier | AURC | Opt.T | Err@T | RelErrRed |\n| :---- | :---- | ----- | ----- | ----- | ----- | ----- | ----- | ----- |\n| **StrategyQA** | Discrete Entropy | 0.5341 | 0.2345 | 0.3517 | 0.2724 | 0.0500 | 0.3263 | 0.0051 |\n|  | Continuous Entropy MC | 0.5502 | 0.2050 | 0.2669 | 0.2555 | 0.0000 | 0.3280 | 0.0000 |\n|  | Continuous Entropy RAO | **0.5801** | 0.2744 | 0.2987 | 0.2432 | 0.0000 | 0.3280 | 0.0000 |\n|  | Number of semantic clusters | 0.5331 | 0.2160 | 0.3410 | 0.2681 | 0.0500 | 0.3263 | 0.0051 |\n| **ProntoQA** | Discrete Entropy | **0.6273** | 0.0788 | 0.2955 | 0.4453 | 0.0000 | 0.5507 | 0.0000 |\n|  | Continuous Entropy MC | 0.5015 | 0.2900 | 0.3459 | 0.4910 | 0.1000 | 0.5461 | 0.0084 |\n|  | Continuous Entropy RAO | 0.5779 | 0.4340 | 0.4515 | 0.4609 | 0.0500 | 0.5480 | 0.0049 |\n|  | Number of semantic clusters | 0.5953 | 0.1258 | 0.3195 | 0.4585 | 0.1000 | 0.5507 | 0.0001 |\n| **ProofWriter** | Discrete Entropy | 0.5717 | 0.2256 | 0.3316 | 0.3254 | 0.0000 | 0.4200 | 0.0000 |\n|  | Continuous Entropy MC | 0.5127 | 0.2340 | 0.3091 | 0.3611 | 0.3500 | 0.4154 | 0.0110 |\n|  | Continuous Entropy RAO | **0.5966** | 0.3053 | 0.3469 | 0.3178 | 0.0000 | 0.4200 | 0.0000 |\n|  | Number of semantic clusters | 0.5645 | 0.1775 | 0.3251 | 0.3322 | 0.0000 | 0.4200 | 0.0000 |\n| **FOLIO** | Discrete Entropy | 0.7542 | 0.2508 | 0.2541 | 0.4506 | 0.0500 | 0.6584 | 0.0007 |\n|  | Continuous Entropy MC | 0.6811 | 0.4571 | 0.4186 | 0.4790 | 0.0000 | 0.6588 | 0.0000 |\n|  | Continuous Entropy RAO | **0.7564** | 0.5383 | 0.5194 | 0.4364 | 0.0000 | 0.6588 | 0.0000 |\n|  | Number of semantic clusters | 0.7523 | 0.3132 | 0.2886 | 0.4496 | 0.0000 | 0.6588 | 0.0000 |\n\n**Additional results for Table 2: Semantic uncertainty quantification metrics for detecting autoformalization errors with respect to ground truth using DeepSeek-v3-0324 across datasets.** Entailment checking was performed using independent prompts to DeepSeek-v3-0324, comparing the generated SMT code with the question as prior context. The uncertainty-aware abstention metrics reflect how the model can selectively answer questions by applying an optimal uncertainty threshold (Opt.Thresh) to withhold answers on uncertain questions, minimizing error rate (Err@T) and maximizing error reduction (RelErrRed) compared to answering all questions.\n\nWhile we observe moderate performance on a few configurations, and near-random performance on the rest, **we *can conclude that semantic uncertainty does not distinctly capture the epistemic uncertainties in autoformalization.*** We would also note that the artificially high AUROC on FOLIO comes from the fact that the LLM autoformalizations are disproportionately composed of errors. To better contextualize the understanding of high AUROC, but poor performance here, we must observe the high AURC value, corresponding with a high risk, in spite of holding out on most uncertain decisions. \n\nWe would also like to note here that we ran the same experiments with \\`nli-deberta-v3-large\\` as the model, similar to Kuhn et al, and all performance metrics, across all datasets, were close to random guessing. This is because \\`nli-deberta-v3-large\\` models have not seen formal structured artifacts, such as SMT code in their training data, and therefore, cannot appropriately judge entailment over them.\n\n**Intuition on why our technique works :** As we mentioned in our paper, our central thesis is that syntactic typicality is itself a powerful, computationally tractable, and previously underexplored signal for identifying semantic errors (pg 8). When an LLM is confident and \"understands\" a problem, it tends to generate programs from a narrower, canonical part of the grammar. When it is uncertain, it explores more varied and statistically anomalous syntactic structures. This \"syntactic fingerprint\" of failure is what our PCFG framework is designed to detect, and our results prove that this works well.\n\nWe also believe that although LLMs have learnt to generate passable syntactically correct structures in SMT, they still make mistakes in autoformalization, akin to early LLMs generating valid but logically unsound python code. **These same mistakes hold for LLMs judging formal artifacts for entailment** too (hence semantic entropy captures low signal about the uncertainty towards incorrectness). We believe that as these models get better over time, these mistakes will be reduced, and UQ methods such as semantic entropy will start working better.\n\n**Efficiency:**\n\nAnother key advantage of our method is its efficiency when there is large-scale sampling of formal artifacts from the LLM. With semantic-entropy based metrics, there need to be (M choose 2)-comparisons between generated autoformalizations to check entailment, which combinatorially explodes at large values of M. Similarly, verifying semantic equivalence between two arbitrary SMT programs is, in general, an undecidable problem. While approximations exist, they are often computationally expensive. Our approach, based on parsing and frequency counts, is lightweight and can be applied at scale on a per-instance basis. \n\n**2\\. On Clarity of Figures and Tables (Weakness 2\\)**\n\n**Our Response:** We appreciate this constructive feedback. We acknowledge that the initial version of Figure 1 was dense. In response, we have redesigned it to be more intuitive and readable. *Due to the text-only format of this rebuttal this year, we cannot display the new figure here or update the PDF,* but we have implemented the following improvements for the final version:\n\n- There is now a clearer layout, and the figure is now structured into distinct stages (LLM Sampling \\> PCFG Parsing & Learning \\> Uncertainty Calculation \\> Prediction), guiding the reader through our pipeline.  \n- The (confusing) pie chart has been removed, and the bar chart showing rule frequencies is simplified now uses a consistent and explicitly labeled color-coding scheme We have also enlarged all text elements for readability.\n\nWe have also noted your concern about the need for abstraction of uncertainty metrics, and have incorporated the following simplified abstracted taxonomy : (1) Information-theoretic Measures (2) Structure based measures/ Spectral properties (3) Static measures of grammar structure (4) Self consistency based measures (5) Ensemble-based measures. Moreover, adding this additional clarity was easy since the camera-ready version allows us one additional content page.\n\n**3\\. On Sample Quality and Temperature (Question 2\\)**\n\n**Our Response:** This is a great question. We investigated this in our ablation studies, the results of which are detailed in **Appendix B (Temperature-Varied SMT Generation and PCFG Analysis, pages 18-20)** available in the supplementary material zip file. Our empirical analysis shows that our PCFG-derived metrics are robust across the temperature spectrum. We found that **grammatical properties exhibit smooth and predictable changes in response to temperature,** rather than chaotic behavior or sharp phase transitions. \n\nFor example, as shown in Figure 3 (Page 19), grammar entropy increases predictably with temperature, reflecting the increased diversity of the samples. This also helps confirm that our metrics are sensitive and correctly capture the changing nature of the LLM's output distribution with respect to temperature.\n\n**Varying parameters like temperature do not harm the quality of the PCFG.** The PCFG merely probabilistically models the production rules from the grammar, irrespective of temperature, or distribution of temperatures samples are drawn from. In fact, all our UQ experiments involve SMT & Text generation by sampling (N=100 times) with a uniform distribution at temperatures between 0.1 and 2.0, a detail we will add to our appendix.\n\n**4\\. On the Number of Samples Used (Question 3\\)**\n\n**Our Response:** Thanks for bringing this up, because it highlights a point we must make more explicit. We do mention 5 samples, but this was for a different part of our analysis. Our experimental setup has two stages:\n\n1. **Initial Benchmarking (N=5):** In Section 3 (Page 6), we first establish the baseline performance of Text vs. SMT reasoning. For this high-level comparison (Table 1 and appendix tables 5-9), we used N=5 samples per question.  \n2. **UQ Analysis (N=100):** For our core contribution, the PCFG-based uncertainty quantification, we used a much larger corpus of **N=100 SMT samples per question**. This larger ensemble is necessary to induce a statistically meaningful PCFG for each reasoning instance. This is explicitly stated in **Appendix D (Page 29\\)**: *\"a corpus of* NSMT​\\=100 *SMT-LIB v2 program samples per question was generated.\"*\n\nWe apologize for the confusion and have added a sentence in Section 3.1 to explicitly differentiate the sample sizes used for the initial benchmarking versus the main UQ analysis.\n\nAdditional note on **Strength 1:** Thank you for pointing out Li et al 2024,”Guiding enumerative program synthesis..” we have highlighted that paper in our related works section. \n\n## **Concluding Request**\n\nWe believe we have addressed all identified weaknesses and questions in detail. May you please increase our rating upwards towards an accept or strong accept? We are happy to answer any more questions you may have. Thank you for your review."}, {"review_id": "xeaAPRfNBz", "reviewer": "Reviewer_JEhf", "summary": "Many recent studies have focussed on how to exploit LLMs to solve reasoning tasks (for example, basic logical reasoning). When solving such a task, LLMs can be used in at least two ways: (1) to directly reason on textual representation, or (2) to translate to a format that can then be fed into a specialized reasoning tool (also called \"autoformalization\"). The current paper proposes to study the second approach by using LLM to translate a given reasoning task to SMT-LIB, for which many solvers have been developed. That is, after the translation, one may invoke an SMT-solver (e.g. Z3) to solve the reasoning task. Owing to potential ambiguity in texts, the authors proposed to quantify \"uncertainty\" in the translation by getting LLMs to output the top N formalizations of the sentence in SMT-LIB and extrapolate a Probabilistic Context-Free Grammar (PCFG) out of these, based on which CFG rules in the SMT-LIB grammar that were used in generating these formalizations. That is, the authors studied how SMT solution consistency (e.g. the results of Z3 on the 100 formalizations) correlates to ground truth and that compares to textual based reasoning. The authors tested this on four reasoning benchmarks: ProofWriter, FOLIO, StrategyQA and ProntoQA. The results are mixed: on ProofWriter, the SMT-based approach helped, but for FOLIO it performed worse than direct textual-based reasoning. For this reason, the authors developed many (25) uncertainty metrics, based on these they introduced a lightweight uncertainty signal whether an error has been introduced in the autoformalizations. They have systematically evaluated these on the four benchmarks.", "questions": "Please address the questions above \"in Strengths and Weaknesses\". In addition, can you clarify the following?\n- Can it happen that LLM produce the correct translation if you ask for one translation, but because you ask for 100 translations, it might produce a lot of wrong ones? In this case, it seems that the approach puts way more weights on translations that are wrong.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper attacks a highly timely and relevant problem. Turning a reasoning task using LLM into a format that can be handled by a formal verification tool is not new, e.g., in [Wu et al. 2022]. To the best of my knowledge, this is the first time PCFG has been used in the context of quantifying uncertainty of autoformalizations. Finally, based on this, the authors have developed and systematically evaluated multiple uncertainty metrics, based on them signals for telling whether or not the LLM+SMT-solver approach should be trusted. \n\nNow I would like to mention the weaknesses. \n\nPresentation: I found the presentation to be unclear and rather difficult to follow in many places.\n- Some sentences in the introduction I found rather misleading, including \"rigorous standards required for formal reasoning\" since I do not see how the current work addresses this. \n- In approximation (p. 3-4): some of the technical descriptions get quite dense, esp. for non-experts (e.g. spectral radius, Kullback-Leibler, etc.). In particular, Theorem 1 is mentioned there (proof in the appendix), but is never mentioned again in the paper and it's not clear how it ties to the rest of the paper.\n- Some parts of the experiments are full of very long sentences that are very hard to understand (e.g. l 282 to 286 is one full sentence with lots of breaks!!). \n- I also feel that some concrete, usable signal is hard to extract from the paper. It would be good if the authors concentrate on simplifying this signal from the sea of statistical data from Section 3.\n- You mentioned you developed 25 uncertainty metrics. Can you enumerate them?\n- Sec 3.1: the simplest metric (MLE) works best, which seems to defeat the purpose of discussing other metrics.\n\nSome missing data: \n- Since SMT-solvers can be quite expensive, I think the authors should also report on the running time of Z3 on the 100 formulas that LLM produce. In particular, how does it contrast to other approaches and why for some benchmarks the cost of running SMT-solver was claimed to outweigh the benefits?\n- Is there a reason to use N=100? Would it work better if I use N=50 or less?\n- How large is the PCFG that is generated? \n\nSome additional remarks:\n- some shorthands were not defined in the paper (e.g. SC, line 189). Does it mean \"Self-Consistency\"?", "was_revised": true, "final_justification": "Author's response clarified my concerns. I assume that the authors incorporate the clarification in the camera ready version (if accepted).", "rebuttal": "Thank you for your thorough evaluation of our manuscript and constructive feedback. We appreciate your recognition of the strengths, including the timeliness of the problem, the novelty of using PCFGs for UQ in autoformalization, and the systematic nature of our evaluation. We incorporated your feedback to improve our paper.\n\n**1\\. On Presentation and Clarity**\n\nWe have addressed the readability concerns by:\n\n**On \"Rigorous Standards\":** Thank you. We agree this phrase requires more context; therefore, we will remove that part of the sentence while maintaining the citation to Chen et al. (2022) that describes selecting only the highest-probability output. The sentiment of our original statement was not that we are improving formal verification itself, but rather providing a missing piece: *insight into the quality of autoformalizations generated due to the probabilistic nature of LLMs.*\n\n**On Technical Density, consolidating signals from data, and Theorem 1:** We acknowledge the dense writeup and have addressed this as follows:\n\n1\\. **Theorem 1:** Theorem 1 provides the theoretical underpinning for our sampling-based approach. It connects the number of samples (N) to the grammar's entropy, providing a probabilistic bound that our 100 samples are sufficient to cover the meaningful regions of the LLM's vast output space. It justifies why our method is sound. We have added the following explicit sentence in Section 2 to connect the theorem back to our methodology: *\"This theorem provides the theoretical guarantee that a sufficiently large sample set N can effectively represent the LLM's output distribution, justifying our use of samples to infer a representative PCFG.\"*\n\n2\\. **Technical density and consolidating signals:** We have adopted a simplified taxonomy with additional details to make the measures section more accessible: (1) Information-theoretic Measures, (2) Structure-based measures/Spectral properties, (3) Static measures of grammar structure, (4) Self-consistency-based measures, (5) Ensemble-based measures. Lines 282-286 have been restructured for clarity.\n\n3\\. **We have also more explicitly defined and enumerated our key takeaways from our result tables in the writeup.** Adding this additional clarity was easy since the camera-ready version allows us one additional content page.\n\n**Enumeration of Metrics & MLE:** We apologize for the confusion regarding MLE. MLE is not a UQ metric; it is the method used to estimate the probabilities of the PCFG rules from the sample set. The UQ metrics are then calculated from this estimated PCFG. We will clarify this distinction. Bayesian and neural approaches to PCFG estimation are useful when incorporating contextual information, such as in low-data paradigms, expert information encoded via Bayesian priors, or natural language semantics obtained via text embeddings. While we explored these techniques and mentioned them briefly, we decided not to run extensive experiments as it would detract from the core focus of UQ in this paper. We have removed the sentence, as you noted it adds unnecessary complexity to the narrative. It will still be available to users, when we open-source the code.\n\n**2\\. On Missing Experimental Details**\n\n* **Z3 Solver Runtime:** We added these performance details\n\n|  | Mean Time | Median (P50) Time | P90 Time | P95 Time | Std Dev (Time) | Mean Memory | Peak Memory |\n| :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- |\n| Z3 Execution Time \u000b(per SMT program) | 0.010s | 0.010s | 0.011s | 0.011s | 0.001s | 24.7MB | 26.4MB |\n\n|  | Mean Time | Median (P50) Time | P90 Time | P95 Time | Std Dev (Time) | Mean Memory | Peak Memory |\n| :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- |\n| SMT to PCFG creation runtime  (per 100 sampled SMT programs) | 1.297s | 1.286s | 1.454s | 1.527s | 0.131s | 144.2MB | 161.9MB |\n| PCFG to UQ Metrics Calc  (from 1 PCFG i.e. 100 sampled SMT) | 0.408s | 0.402s | 0.423s | 0.431s | 0.023s | 117.3MB | 118.9MB |\n\nThe overhead of using Z3, PCFG extraction, and analysis is minimal, as it primarily involves efficient parsing (using ANTLR) and frequency counting (Maximum Likelihood Estimation) over a fixed set of 100 samples. Our experiment pipeline is dominated by LLM inference time, not solver time or UQ calculations. We also implemented a 30-second timeout for Z3 while running our experiments, so for those anomalous cases where the LLM writes faulty SMT programs that run too long (none of our questions across all 4 datasets should require that much time), they are terminated, and the LLM is asked to generate a new program.\n\n**Choice of N=100 and PCFG Size:** \n\nWe chose to generate N=100 samples because that was heuristically the maximum number of samples we could afford within our compute budget. We needed to sample extensively because we did not constrain the LLM-based SMT generation. We made this choice because we wanted to observe how LLMs behave with minimal prompt engineering while generating valid SMT code.\n\nThis approach should work at N=50 or fewer samples as well. As you reduce the number of samples, you may want to constrain: (1) the theories that can be used in your SMT programs (LIA, RA, etc.), (2) use multi-stage autoformalization pipelines, where the first stage is variable definition generation. This way, generated SMT constraints will only use previously defined variables in the pipeline, reducing the need for extensive sampling. Without these constraints, a smaller N (e.g., 5-10) would likely result in less stable estimates of rule probabilities, potentially weakening the UQ signal.\n\n**Regarding the size of the PCFG:** Here are some summary metadata statistics of a generated PCFG on ProofWriter, which had the longest SMT programs generated from 100 SMT programs in response to a single question: Total Rules \\= 63,202, Unique rules \\= 42, Non-terminals \\= 24, Maximum probability observed among unique rules \\= 1.0, Minimum probability observed for a unique rule \\= \\~0.00035, Average probability across unique rules \\= 0.5714.\n\n**Shorthand 'SC':** Yes, 'SC' stands for Self-Consistency, and we have now ensured it is defined upon its first use. Thank you for pointing this out.\n\n**3\\. On the Nature of Sampling-Based UQ**\n\n**Reviewer's Question:** *\"Can it happen that LLM produce the correct translation if you ask for one translation, but because you ask for 100 translations, it might produce a lot of wrong ones? In this case, it seems that the approach puts way more weights on translations that are wrong.\"*\n\nThis is an excellent question\\! We want to clarify that we do not ask the LLM to generate 100 translations in one prompt. We repeatedly sample one translation 100 times to obtain our 100 SMT programs. No context from the previous LLM call are carried forward to the next LLM call for the sake of fair and distinct autoformalization generations.\n\nWe would like to describe the intuition as follows: imagine running inference on a CNN with the same image 100 times. If you get 10 different answers, you would conclude that there is significant uncertainty in the model output, correct? Similarly, our goal is to assess the LLM's confidence. If a model produces one correct translation but 99 syntactically diverse (and potentially incorrect) alternatives, our PCFG will capture this high diversity, resulting in high grammar entropy. This high entropy signals low model confidence or high uncertainty.\n\nA confident, reliable model would generate 100 programs that are generally syntactically equivalent or very similar and canonical, leading to low entropy. Therefore, our approach does not \"overweight\" wrong translations; it correctly interprets a scattered, diverse output distribution as a sign of unreliability. This is the risk we aim to flag for the user.\n\n4\\. **Enumeration of all measures**\n\nYou can find an enumeration of all 25 uncertainty measures we benchmarked in the 25 rows of Tables 3, 4, etc. For your reference, in case you have detailed questions about how we implemented and/or calculated these measures, we describe them shorthand below. We will also add these details to the appendix:\n\n1. **Grammar Entropy** (nonterminals)  \n2. **Perplexity** (from \\#1)  \n3. **KL Divergence**(vs uniform)  \n4. **NSUI**: grammar\\_entropy/max\\_entropy) \\* (spectral\\_radius/(1+spectral\\_radius))  \n5. **Renyi Ent (2)**   \n6. **Renyi Ent (0.5)**  \n7. **Max Ent**: weighted Σlog2(num\\_rules) per nonterminal  \n8. **Ent Ratio**: grammar\\_entropy/max\\_entropy (normalized entropy in NSUI)  \n9. **Spectral Factor**: spectral\\_radius/(1+spectral\\_radius) (normalized spectral in NSUI)  \n10. **Spectral Radius**: largest eigenvalue of dependency graph Jacobian  \n11. **\\# Nonterminals**: unique LHS symbols  \n12. **\\# Rules**: total count  \n13. **Avg Rules / \\# NT**:  \n14. **Avg RHS Len**  \n15. **Max Branch Factor**: max alt rules per nonterminal  \n16. **Rule Dist Mean**  \n17. **Rule Dist StdDev**  \n18. **Rule Dist Skew**  \n19. **Rule Dist Kurtosis**  \n20. **Self Consistency Text**: fraction agreeing with majority text ans  \n21. **Self Consistency SMT**: fraction agreeing with majority SMT ans  \n22. **Ensemble Average**: arithmetic mean of normalized uncertainty  \n23. **Ensemble Weighted**: correlation-weighted avg (squared correlations)  \n24. **Ensemble ML**:LogisticRegression on scaled features \\[negated grammar\\_entropy, perplexity, spectral\\_radius, nsui, spectral\\_factor, kl\\_divergence, max\\_entropy, smt\\_consistency\\]  \n25. **Ensemble Simple**: (1-norm\\_grammar\\_entropy)\\*0.33 \\+ (1-norm\\_spectral\\_radius)\\*0.33 *\\+* smt\\_consistency*\\**0.34\n\nRebuttal word limits restrict our description length, but we are happy to discuss further!\n\n## **Concluding Request**\n\nWe believe we have comprehensively addressed all identified weaknesses. **Given these detailed responses and improvements, would you please consider increasing your rating to accept or strong accept?** We're happy to address any additional questions."}, {"review_id": "Y57u9rN7Mj", "reviewer": "Reviewer_FQaS", "summary": "The paper introduces probabilities to the idea of using grammars for modeling LLM outputs, and then employs them as a means for uncertainty quantification (UQ) in SMT generation tasks. The results are demonstrated using o3-mini, DeepSeek-R1, DeepSeek, Gemini Flash 2.0 and Gemini Lite.", "questions": "1. Please put Theorem 1 in context of known results with citations, if possible.\n2. Please clarify if the probabilities for the PCFG are computed from the same data distribution as used for the UQ metrics.\n3. Discuss the novelty in the paper in context of related work on formal grammars and LLMs.", "limitations": "The effiicacy of UQ metrics and risk of incorrect applications may be better discussed.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. A key strength of the paper is the inclusion of probabilities into the formal grammar being used for further UQ analysis.\n2. The paper seeks to bring formal methods and LLMs together, which is an interesting direction to pursue.\n3. The UQ metrics are obtained from the spectral and information theoretic measures related to the Jacobian and the non-terminals/rules of the grammar, which is interesting.\n\nWeaknesses:\n1. There is a rich body of work that uses formal grammars at inference time without probabilities. The paper does not adequately discuss these approaches or builds the results of this work in context of these earlier methods. \n2. The title \"Grammars of Formal Uncertainty\" is not apt as the paper does not build grammars of formal uncertainty. Similarly, the broad mention of automated reasoning tasks leaves the strong ties that the paper has to SMT methods, which are only one set of automated reasoning methods.\n3. Theorem 1 (first two results) on page 4 is a straightforward result that can be proved directly from the definition of entropy and it can be included in the text of the paper. Appropriate citations should be provided for each of the steps, such as T. M. Cover and J. A. Thomas, Elements of Information Theory.\n4. It is not clear if the probabilities in the PCFG are obtained from a different data set than the UQ measures obtained during analysis. If the train and test set come from the same data set, the UQ methods will not generalize and will be reliant on the data set distribution.", "was_revised": true, "final_justification": "1. The rebuttal has clearly pointed out again that PCFGs are different from CFGs and that API-level access to output distribution is not needed for this specific approach to UQ using PCFGs. \n\n2. The key technical result in the paper did not come with adequate citation in my opinion. I had factored this oversight strongly in my original review. However, the authors clearly state that the theorem's contribution is not a claim of inventing a new mathematical principle, but its novel application and contextualization.\n\n3. The preliminary results on Prolog will help ensure the the approach is indeed applicable for more than one automated reasoning task.", "rebuttal": "Thank you for your feedback and for recognizing the key strengths of our work, including our novel use of probabilistic formal grammars for uncertainty quantification and the valuable integration of formal methods with LLMs. We appreciate your acknowledgment of our innovative spectral and information-theoretic measures, which validates the core novelty of our approach.\n\nWe hope to address your concerns and demonstrate the value of our contribution through this rebuttal. We welcome further engagement as we work to convey the novelty of our approach to all readers.\n\n**1\\. On Novelty and Relation to Prior Work (Weaknesses 1 & 3\\)**\n\n**Concern:** *\"There is a rich body of work that uses formal grammars at inference time without probabilities. The paper does not adequately discuss these approaches or builds the results of this work in context of these earlier methods.\"*\n\n**Our Response:** Our paper's core novelty lies not in merely using a grammar, but in using a Probabilistic Context-Free Grammar (PCFG) to model the LLM's entire output distribution for a given question for the purpose of UQ. This is a fundamental departure from prior work that uses grammars deterministically for constrained decoding. Although we believe these areas are not directly related, **as per your suggestion we are adding a paragraph on known usage of grammars at inference time to our related works section.**\n\n**Here is why we are different from prior work:** Constrained decoding modifies the LM head by zeroing out probabilities of tokens that are invalid based on the known language (e.g., JSON) grammar. This is not feasible with commercially available, non-open-weight frontier LMs that we focus on in this paper. Furthermore, **this approach is not related to our task of UQ,** since LLMs can reliably generate syntactically valid SMT in our experiments. To clarify our position:\n\n* **Our Contribution is Probabilistic UQ, Not Constrained Decoding:** As stated in our central thesis (Page 1), \"*Existing methods often ignore this \\[probabilistic uncertainty\\] by selecting only the highest-probability output \\[token\\]... a simplification that we argue undermines the rigorous standards required for formal reasoning*.\" Our work directly addresses this simplification. We do not merely ensure outputs are syntactically valid; we analyze the statistical patterns within an ensemble of valid outputs to quantify the model's uncertainty.\n\n* **Explicit Discussion in Related Works:** Our Related Works section (Section 4\\) currently situates our work appropriately within the task of UQ. We discuss the use of PCFGs in various domains and explicitly state, \"Our work extends PCFG inference... to verification artifacts\" (Page 9). **The novelty lies in applying this probabilistic framework to diagnose LLM reasoning failures, which, to our knowledge and according to all three other reviewers, represents a completely new direction.**\n\n**2\\. On the Aptness of the Title and Scope (Weakness 2\\)**\n\n**Reviewer's Concern:** *\"The title 'Grammars of Formal Uncertainty' is not apt as the paper does not build grammars of formal uncertainty. Similarly, the broad mention of automated reasoning tasks leaves the strong ties that the paper has to SMT methods...\"*\n\n**Our Response:** We believe the title is both apt and evocative of our contribution.\n\n* **On the Title:** The grammar serves as the instrument through which we structure, model, and measure the uncertainty inherent in the LLM's formal outputs. The PCFG, with its rule probabilities learned from the LLM's own generations, becomes a \"grammar of formal uncertainty\", **a formal object that describes the LLM's autoformalization confidence and confusion. This is not merely semantic.**\n\n* **On the Scope:** We are transparent that our experiments are instantiated using the SMT-LIB standard. We state this explicitly in our methodology (Section 2): *\"...we adopt the stable, widely supported SMT-LIB standard as a common intermediate representation...\"* This is a methodological choice to ground our framework in SMT, a powerful, standardized, and representative sub-domain of automated reasoning used in real-world automated reasoning production systems and prior publications that employ SMT solvers.\n\n  To illustrate our point, please see: *A billion SMT queries a day, Amazon Science, FLOC 2022\\.*\n\n  **The framework itself is general.** The PCFG-based UQ approach can be applied to any formal language for which a grammar can be defined, as **we demonstrate in our rebuttal pilot study to reviewer yS8U, where we show our method is easily extensible to Prolog** (similar to first-order logic). SMT is our primary case study, not a fundamental limitation of the method**.**\n\n**3\\. On the Contribution of Theorem 1 (Weakness 3 & Question 1\\)**\n\n**Reviewer's Concern:** *\"Theorem 1... is a straightforward result that can be proved directly from the definition of entropy... Appropriate citations should be provided for each of the steps, such as T. M. Cover and J. A. Thomas, Elements of Information Theory.\"*\n\n**Our Response:** We agree that Theorem 1 builds upon foundational principles of information theory, and we thank the reviewer for the suggestion. We have gladly added a citation to Cover and Thomas to acknowledge the classical roots of typical set arguments.\n\nHowever, by dismissing this as \"straightforward\" you are overlooking its important role in our paper. The theorem's contribution is not a claim of inventing a new mathematical principle, but its novel **application and contextualization**. It provides the first formal, theoretical bridge, to our knowledge, between:\n\n1. The **number of samples (N)** drawn from an LLM.  \n2. The **Shannon entropy (H(µ)**) of the LLM's output distribution.  \n3. The **probabilistic bound of covering the space of possible formal programs.**\n\n**This theorem provides the theoretical justification for our sampling-based UQ methodology.** It demonstrates *why* analyzing an ensemble of outputs is a principled way to understand the model's uncertainty over the entire generation space. Its value is in its application, not its elementary nature. We will make this more clear in the paper.\n\n**4\\. On the Experimental Methodology (Weakness 4 & Question 2\\)**\n\n**Reviewer's Concern:** *\"It is not clear if the probabilities in the PCFG are obtained from a different data set than the UQ measures obtained during analysis. If the train and test set come from the same data set, the UQ methods will not generalize...\"*\n\n**Our Response:** We believe this concern stems from a misunderstanding of our experimental design, which we will make more explicit in our methodology. Our methodology operates at the instance level, not through a traditional train/test split, and this is a core feature of our contribution.\n\nAs detailed in Appendix D, \"For each of the selected questions, a unique PCFG was induced from its corresponding 100 SMT samples.\"\n\nTo be unequivocally clear:\n\n1. For a **single input question**, we prompt the LLM to generate an ensemble of N=100 formal (SMT) programs.  \n2. From this specific ensemble of 100 programs, we induce a **per-question PCFG**.(each PCFG is independent of other PCFGs).  \n3. The UQ measures (entropy, spectral radius, etc.) are calculated from this instance-specific PCFG. **For 21 of these measures (Table 3, rows 1-21), no learning occurs.** Only our 4 ensemble-based techniques (Table 3, rows 22-25) **learn how to weight each of these 21 measures to produce a better uncertainty signal** and understand the total signal present among the metrics.  \n4. These UQ metrics are then used to predict the correctness of the answer for that **same single input question**.\n\nThere is no \"training set\" from which PCFG probabilities are learned and a \"test set\" on which they are applied. Your concern about generalization is misplaced because the goal is not to build a global PCFG model,, but to assess the LLM's uncertainty on a **case-by-case basis**. This instance-specific analysis is allows our method to provide confidence scores for each new autoformalization problem an LLM encounters.\n\n**5\\. On the Discussion of Efficacy and Risk (Limitations)**\n\n**Reviewer's Concern:** *\"The effiicacy of UQ metrics and risk of incorrect applications may be better discussed.\"*\n\n**Our Response:** \n\n* **Efficacy:** We are puzzled by the limitation comment on efficacy, as a significant portion of our Results section (Section 3\\) and Appendix is dedicated to a rigorous, multi-faceted evaluation of efficacy and risk. **We evaluate 25 different metrics using AUROC, ECE, AURC, Brier scores and more across multiple models and datasets (Tables 3, 4, and 10-17). This constitutes a direct and comprehensive assessment of efficacy.**\n\n* **Risk of Incorrect Applications:** We’d love to clarify this. **The entire premise of our selective prediction analysis is to manage this risk. We use the Area Under the Risk-Coverage Curve** (AURC) and explicitly report the error rate at **optimal abstention thresholds** (Err@T) and the resulting **Relative Error Reduction** (RelErrRed). For instance, for 03-mini on ProofWriter, we demonstrate that our method enables **\"filtering nearly all errors by abstaining on a minute fraction of outputs\"** (Page 7), achieving a **100% error reduction** (Table 12). This is not a peripheral point; it is a central result of our paper and a direct, quantitative discussion of managing the risk of incorrect application.\n\n## Concluding Request\n\n**We believe we have addressed all identified weaknesses and questions in detail. In light of these comprehensive responses, would you please consider increasing your rating to an accept?**\n\nWe would be happy to address any additional questions you may have. Thank you for your thorough review."}, {"review_id": "ZuMPMwiOAn", "reviewer": "Reviewer_yS8U", "summary": "The paper investigates how to quantify and manage formal-logic uncertainty that arises when large language models (LLMs) automatically translate natural-language problems into symbolic formats (specifically SMT-LIB). \nThe authors diagnose failure modes by benchmarking five state-of-the-art LLMs on four reasoning datasets, showing that symbolic translation can both help and hurt depending on task structure.\nThey also model the space of LLM-generated programs with PCFG, treating each generated SMT string as a sample from an (unknown) distribution and fitting a PCFG to recover rule-level probability mass.\nThey introduce a taxonomy of 25 uncertainty signals derived from the fitted grammar (entropy, spectral radius, rule sparsity, self-consistency, etc.) and show that different tasks prefer different signals.\nThey also propose a lightweight fusion strategy that combines the best signals into a model-agnostic selective-verification policy, reducing downstream logical errors by 14 – 100 % while abstaining on only a small fraction of cases.", "questions": "Have you tried the pipeline on a markedly different formal language (e.g., Coq proofs)? Even a small pilot study would strengthen the claim of broad applicability.\n\nWith 25 handcrafted signals, how did you avoid overfitting to the chosen datasets? \n\nEngineers need a threshold to decide when to abstain. A decision-curve or cost-benefit analysis would make the selective-verification story more actionable.", "limitations": "Adding quantitative overhead measurements and a scalability/extensibility discussion would improve the paper.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths \n- Comprehensive evaluation across multiple models, tasks and metrics; theory and experiments align\n- Elevates uncertainty estimation in neurosymbolic pipelines; practical recipe for safer auto-formalisation\n- Novel use of fitted PCFGs to harvest uncertainty features; fusion policy yields state-of-the-art selective-verification gain\n\nWeaknesses\n- The paper should be clearer. For example, figure 1 is not very clear. Explain more about the colors. Better split the pie chart. \n- No runtime/memory profile for PCFG extraction\n- Lack of scalability/extensibility discussion", "was_revised": true, "final_justification": "I think the authors answered my questions.", "rebuttal": "We are grateful for your positive and encouraging assessment of our work. We also sincerely appreciate the \"accept\" recommendation and recognition of our paper's evaluation, novelty, and potential for impact. We have incorporated your feedback to make our paper even stronger:\n\n**1\\. On Presentation, Scalability, and Overhead**\n\n***Clarity of figure 1:*** We appreciate this constructive feedback. We acknowledge that the initial version of Figure 1 was dense. In response, we have redesigned it to be more intuitive and readable. Due to the text-only format of this rebuttal this year, we cannot display the new figure here or update the PDF, but we have implemented the following improvements for the final version:\n\n- There is now a clearer layout, and the figure is structured into distinct stages (LLM Sampling \\> PCFG Parsing & Learning \\> Uncertainty Calculation \\> Prediction), guiding the reader through our pipeline.  \n- The confusing pie chart has been removed, and the bar chart showing rule frequencies has been simplified and now uses a consistent and explicitly labeled color-coding scheme. We have also enlarged all text elements for readability.\n\n***Runtime/Memory Profile*****:** This is an excellent point. We conducted this experiment to address your concern.\n\n|  | Mean Time | Median (P50) Time | P90 Time | P95 Time | Std Dev (Time) | Mean Memory | Peak Memory |\n| :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- |\n| SMT to PCFG creation runtime  (per 100 sampled SMT programs) | 1.297s | 1.286s | 1.454s | 1.527s | 0.131s | 144.2MB | 161.9MB |\n| PCFG to UQ Metrics Calc  (from 1 PCFG i.e. 100 sampled SMT) | 0.408s | 0.402s | 0.423s | 0.431s | 0.023s | 117.3MB | 118.9MB |\n\n|  | Mean Time | Median (P50) Time | P90 Time | P95 Time | Std Dev (Time) | Mean Memory | Peak Memory |\n| :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- |\n| Z3 Execution Time (per SMT program) | 0.010s | 0.010s | 0.011s | 0.011s | 0.001s | 24.7MB | 26.4MB |\n\nAs you can see, the overhead of our PCFG extraction and analysis is minimal, as it primarily involves efficient parsing (using ANTLR) and frequency counting (Maximum Likelihood Estimation) over a fixed set of 100 samples. Our experiment pipeline is dominated by LLM inference time, not UQ calculations.\n\n**2\\. On Methodology and Practical Application**\n\n**Applicability to other formal languages** \n\nThis is a fantastic suggestion. **We were able to perform this pilot study to demonstrate the framework's generality.**\n\nOur parser and PCFG construction logic uses ANTLR under the hood; therefore, we can use any of the grammar files in the ANTLR-v4 repository on Github. There is no g4 file for Coq, Isabelle, or Lean, but there is one for Prolog, which is remarkably similar to first-order logic in construction. We were able to quickly adapt our PCFG analysis pipeline to work with Prolog programs without major engineering changes to our codebase, generating PCFGs and consequently the uncertainty measures. The fundamentals of our technique remain the same across programming languages with well-defined grammars. This also opens up the exciting possibility of using our tool to quantify uncertainty in general-purpose programming code generated by LLMs as future work. We converted the SMT code in Figure 1 of the paper into Prolog as follows:\n\n```\n% program1.pl\n% ∀x. (StudiesMath(x) ∨ (StudiesPhysics(x) ∧ WorksHard(x))) → Succeeds(x).\n\n% Facts\nperson(alice).\nperson(bob).\nperson(charlie).\n\nstudies_math(alice).\nstudies_physics(bob).\nworks_hard(bob).\nworks_hard(charlie).\n\n% Rule\nsucceeds(X) :-\n    studies_math(X).\n\nsucceeds(X) :-\n    studies_physics(X),\n    works_hard(X).\n\n% On load: print all solutions and exit\n:- initialization(main).\nmain :-\n    forall(succeeds(X), writeln(X)),\n    halt.\n```\n\n```\n% program2.pl\n% ∀x. ((StudiesMath(x) ∨ StudiesPhysics(x)) ∧ WorksHard(x)) → Succeeds(x).\n\n% Facts\nperson(alice).\nperson(bob).\nperson(charlie).\n\nstudies_math(alice).\nstudies_physics(bob).\nworks_hard(bob).\nworks_hard(charlie).\n\n% Rule\nsucceeds(X) :-\n    ( studies_math(X)\n    ; studies_physics(X)\n    ),\n    works_hard(X).\n\n% On load: print all solutions and exit\n:- initialization(main).\nmain :-\n    forall(succeeds(X), writeln(X)),\n    halt.\n```\n\n```\n% program3.pl\n% (∀x. StudiesMath(x)→Succeeds(x))  ∨  (∀x. (StudiesPhysics(x)∧WorksHard(x))→Succeeds(x))\n\n% Facts\nperson(alice).\nperson(bob).\nperson(charlie).\n\nstudies_math(alice).\nstudies_physics(bob).\nworks_hard(bob).\nworks_hard(charlie).\n\n% Toggle which implication you want:\noption(math).      % ← comment this and uncomment the next to switch\n% option(physics).\n\n% Branch 1: StudiesMath(x) -> Succeeds(x)\nsucceeds(X) :-\n    option(math),\n    studies_math(X).\n\n% Branch 2: (StudiesPhysics(x) ∧ WorksHard(x)) -> Succeeds(x)\nsucceeds(X) :-\n    option(physics),\n    studies_physics(X),\n    works_hard(X).\n\n% On load: print all solutions and exit\n:- initialization(main).\nmain :-\n    forall(succeeds(X), writeln(X)),\n    halt.\n```\n\n```\n% program4.pl\n% ∀x. WorksHard(x) → (StudiesMath(x) ∨ StudiesPhysics(x)) → Succeeds(x)\n\n% Facts\nperson(alice).\nperson(bob).\nperson(charlie).\n\nstudies_math(alice).\nstudies_physics(bob).\nworks_hard(bob).\nworks_hard(charlie).\n\n% Nested implication expands to two rules\nsucceeds(X) :-\n    works_hard(X),\n    studies_math(X).\n\nsucceeds(X) :-\n    works_hard(X),\n    studies_physics(X).\n\n% On load: print all solutions and exit\n:- initialization(main).\nmain :-\n    forall(succeeds(X), writeln(X)),\n    halt.\n```\n\n```\n% program5.pl\n% ∀x. Succeeds(x) ↔ (StudiesMath(x) ∨ (StudiesPhysics(x) ∧ WorksHard(x)))\n\n% Facts\nperson(alice).\nperson(bob).\nperson(charlie).\n\nstudies_math(alice).\nstudies_physics(bob).\nworks_hard(bob).\nworks_hard(charlie).\n\n% Forward direction\nsucceeds(X) :-\n    studies_math(X).\nsucceeds(X) :-\n    studies_physics(X),\n    works_hard(X).\n\n% Backward direction to enforce ↔\nstudies_math(X) :-\n    succeeds(X),\n    \\+ (studies_physics(X), works_hard(X)).\n\nstudies_physics(X) :-\n    succeeds(X),\n    works_hard(X).\n\n% On load: print all solutions and exit\n:- initialization(main).\nmain :-\n    forall(succeeds(X), writeln(X)),\n    halt.\n```\n\nHere are some summary statistics of the generated PCFG with the following programs: Total Rules \\= 560, Unique rules \\= 33, Non-terminals \\= 7, Maximum probability of a rule \\= 1.0, Minimum probability \\= 0.0086, Average probability \\= 0.2121. There are 4.7 rules per non-terminal, with a maximum branching factor of 16\\. The grammar entropy is 0, KL divergence from uniform is 1.34, and spectral radius is 0.83.\n\nThe core strength of our framework is its generality. Because it is built on the standard formalism of context-free grammars, it is not tied to SMT-LIB. In the revised manuscript, we will add a dedicated discussion on extensibility and how this can adapt to other formal languages or general programming languages, provided a base grammar is available.\n\nPlease note that conducting a new large-scale empirical study on the efficacy of Prolog-based uncertainty metrics on our datasets would be beyond the time scope of the current rebuttal period, but we see this as a clear and exciting next step.\n\n**How to avoid overfitting with 25 signals**\n\nThis is a good question. Let us clarify:\n\n- In our approach, 21 out of the 25 metrics (i.e., non-ensemble methods) have no chance of overfitting since there is no \"learning\" happening apart from basic PCFG construction. UQ analysis is performed on a per-instance basis: for each reasoning problem, we generate 100 samples of programs and induce a new, problem-specific PCFG. There is no global \"training set\" of PCFGs.  \n- The 21 metrics are used to create a \\[21,1\\]-dimensional feature vector for each single instance, and our ensemble methods are essentially simple regularized logistic regression models that operate on top of this. The performance of the ensemble methods is evocative of the upper bound of information present within these signals if they were combined optimally. \t\t\n\n  *Bridle, John. \"Training stochastic model recognition algorithms as networks can lead to maximum mutual information estimation of parameters.\" Advances in neural information processing systems 2 (1989).*\n\n**Actionable Thresholds for engineering**\n\nThis is an excellent point, and engineers looking to deploy this in production have raised this concern with us previously. This is indeed a challenging problem that has been extensively studied in selective decision making regarding how to choose the appropriate risk threshold.\n\nOur use of the Area Under the Risk-Coverage Curve (AURC), Error at threshold, and associated metrics are specifically designed to address this. The Risk-Coverage curve itself provides a visualization of the trade-off between risk (error rate) and coverage (percentage of problems answered). An engineer can use this curve directly as a decision-making tool:\n\n- For safety-critical domains, an engineer could choose a point on the curve with a very low error rate, accepting a higher abstention rate (and thus more human oversight).  \n- For less critical applications (e.g., a programming assistant), they could select a point with higher coverage to maximize automation, tolerating a moderately higher error rate.\n\nTo present the complete picture in our evaluations, we evaluate our method in a threshold-agnostic manner using AURC. The AURC score summarizes the quality of this trade-off across all possible thresholds, with our scores consistently outperforming all known methods.\n\n## **Concluding Request**\n\nOnce again, we thank you for your highly positive and constructive review. In light of these clarifications and new experiments, would you please consider improving your rating to a strong accept? This would allow us to highlight this work in a spotlight or oral presentation. Please let us know if there are any concerns we have not addressed in sufficient depth. We would be happy to provide further clarification."}]

Author rebuttal:

Meta-review: The paper studies the problem of generating a formal representation that allows for calling a solver, such as SMT or Prolog programs. It introduces a framework based on PCFGs to model uncertainty and derive a variety of metrics.

Reviewers were all positive on this paper, ranging from borderline accept to strong accept. The problem is particularly timely since it has potential implications for LLM reasoning, applications such as mathematical formalization or software verification, and appears in a variety of contexts. The focus on incorporating uncertainty into autoformalization is underexplored, especially in the context of recent methods based on LLMs. The use of PCFGs to derive uncertainty metrics is creative and seems effective.

The main weakness in my opinion is the writing. As noted by a reviewer, it is often exceedingly dense. Moreover, sentences are frequently long and complicated (e.g., most of 304-320). There are also 25 proposed metrics and the tables are massive, which can make it difficult to extract the important or interesting insights. In sum, the paper could be written more clearly so that the main messages, results, and takeaways from the paper are accessible to a wider audience.

That said, given the strengths and the positive reviews, I recommend its acceptance.
Decision: Accept (poster)