formal-uncertainty-llm-reasoning

name	formal-uncertainty-llm-reasoning
title	Grammars of Formal Uncertainty: When to Trust LLMs in Automated Reasoning Tasks
version	0.0.2
engine	skillxiv-v0.0.2-claude-opus-4.6
license	MIT
url	https://arxiv.org/abs/2505.20047
keywords	["Uncertainty Quantification","Verification","Automated Reasoning","Formal Logic"]
description	Predict when LLM outputs are trustworthy for formal reasoning by analyzing domain-specific uncertainty signals.

Know When to Trust Your LLM: Uncertainty for Formal Reasoning

LLMs generate confident-sounding outputs regardless of actual correctness, creating dangerous blind spots in automated reasoning where formal verification demands certainty. This skill teaches selective verification: analyzing uncertainty signals to predict which LLM-generated formalizations are worth verifying versus which are likely correct without checking. The approach discovers that different domains require different uncertainty metrics—entropy-based signals work for logic tasks but fail for factual problems, where token statistics matter more.

By learning task-dependent uncertainty patterns, you can reduce verification costs 14-100% while maintaining accuracy, transforming LLM-driven formalization from unreliable to deployable.

Core Concept

Traditional confidence calibration treats all tasks the same. Formal uncertainty recognition is domain-aware: it learns that logic problems exhibit high uncertainty in specific token positions (decision points where multiple formalizations are valid), while factual reasoning tasks show uncertainty through different statistical patterns. A lightweight meta-model trained on your target domain learns which uncertainty signals reliably predict correctness, enabling selective formal verification that validates only high-risk outputs.

Architecture Overview

• Probabilistic Context-Free Grammar (PCFG) Framework: Models the structure of LLM outputs to identify uncertainty signals at multiple linguistic levels (token, phrase, logical clause)
• Domain-Specific Signal Extraction: Task-dependent metrics including token probability entropy, grammatical complexity, logical branching points
• Signal Fusion Module: Lightweight combination mechanism that weights different uncertainty indicators based on domain
• Selective Verification: Routes high-uncertainty outputs to formal verification, passes low-uncertainty through
• Iterative Calibration: Improves signal weights over time as verification results accumulate

Implementation

This implementation demonstrates uncertainty quantification and selective verification for formal reasoning tasks.

Build a framework to extract uncertainty signals from LLM outputs:

import torch
import numpy as np
from typing import List, Tuple, Dict
from transformers import AutoTokenizer, AutoModelForCausalLM

class UncertaintyAnalyzer:
    """Extract uncertainty signals from LLM reasoning outputs."""

    def __init__(self, model_name: str = "gpt2-medium"):
        self.tokenizer = AutoTokenizer.from_pretrained(model_name)
        self.model = AutoModelForCausalLM.from_pretrained(model_name)

    def get_token_probabilities(self, text: str, tokenized_output: List[int]):
        """
        Get probability of each predicted token given context.
        Returns sequence of log probabilities.
        """
        input_ids = self.tokenizer.encode(text, return_tensors="pt")

        with torch.no_grad():
            outputs = self.model(input_ids, output_hidden_states=True)
            logits = outputs.logits[0]  # [seq_len, vocab_size]

        # Get probabilities for generated tokens
        log_probs = torch.log_softmax(logits, dim=-1)
        token_log_probs = []

        for i, token_id in enumerate(tokenized_output):
            if i < len(log_probs):
                token_log_probs.append(log_probs[i, token_id].item())

         token_log_probs

     () -> :
        
        input_ids = .tokenizer.encode(text, return_tensors=)

         torch.no_grad():
            outputs = .model(input_ids)
            logits = outputs.logits[]

        
        probs = torch.softmax(logits, dim=-)
        entropy = -(probs * torch.log(probs + )).(dim=-)

         (entropy.mean().item())

     () -> [[, ]]:
        
        input_ids = .tokenizer.encode(text, return_tensors=)

         torch.no_grad():
            outputs = .model(input_ids)
            logits = outputs.logits[]

        probs = torch.softmax(logits, dim=-)

        
        entropy = -(probs * torch.log(probs + )).(dim=-)
        entropy_threshold = entropy.mean() + entropy.std()

        branching_points = [
            (i, entropy[i].item())
             i, e  (entropy)
             e > entropy_threshold
        ]

         branching_points


analyzer = UncertaintyAnalyzer()

reasoning_output = 
entropy = analyzer.compute_entropy(reasoning_output)
branching_pts = analyzer.compute_branching_points(reasoning_output)

()
()

Implement domain-specific signal fusion for predicting correctness:

from sklearn.linear_model import LogisticRegression
from sklearn.preprocessing import StandardScaler

class DomainUncertaintyCalibrator:
    """Learn domain-specific mapping from uncertainty signals to correctness."""

    def __init__(self):
        self.signal_weights = {
            "entropy": 0.3,
            "token_probability": 0.2,
            "grammatical_complexity": 0.3,
            "logical_branching": 0.2
        }
        self.calibrator = LogisticRegression()
        self.scaler = StandardScaler()
        self.fitted = False

    def extract_signals(self, text: str, analyzer: UncertaintyAnalyzer) -> Dict:
        """Extract all uncertainty signals from a text."""
        signals = {}

        # Token-level entropy
        signals["entropy"] = analyzer.compute_entropy(text)

        # Average token probability
        tokens = analyzer.tokenizer.encode(text)
        log_probs = analyzer.get_token_probabilities(text[:100], tokens)
        signals["token_probability"] = -np.mean(log_probs) if log_probs else 0.5

        # Grammatical complexity (proxy: length variation)
        token_lengths = [len(analyzer.tokenizer.decode([t])) for t in tokens]
        signals[] = np.std(token_lengths) / (np.mean(token_lengths) + )

        
        branching_pts = analyzer.compute_branching_points(text)
        signals[] = (branching_pts) / ((tokens) + )

         signals

     ():
        
        all_signals = []
         text  texts:
            sig = .extract_signals(text, analyzer)
            all_signals.append([
                sig[],
                sig[],
                sig[],
                sig[]
            ])

        X = np.array(all_signals)
        y = np.array(correctness_labels)

        
        X_scaled = .scaler.fit_transform(X)
        .calibrator.fit(X_scaled, y)

        
        coef_abs = np.(.calibrator.coef_[])
        coef_sum = coef_abs.()
        .signal_weights = {
            : coef_abs[] / coef_sum,
            : coef_abs[] / coef_sum,
            : coef_abs[] / coef_sum,
            : coef_abs[] / coef_sum
        }
        .fitted = 

     () -> [, ]:
        
        signals = .extract_signals(text, analyzer)

        X = np.array([[
            signals[],
            signals[],
            signals[],
            signals[]
        ]])

         .fitted:
            X_scaled = .scaler.transform(X)
            confidence = .calibrator.predict_proba(X_scaled)[, ]
        :
            
            confidence = (
                signals[key] * weight
                 key, weight  .signal_weights.items()
            )
            confidence = (, (, confidence))

         confidence, signals


analyzer = UncertaintyAnalyzer()
calibrator = DomainUncertaintyCalibrator()


train_texts = [
    ,
    ,
]
train_labels = [, ]  


calibrator.fit_to_domain(train_texts, train_labels, analyzer)


test_text = 
confidence, signals = calibrator.predict_correctness(test_text, analyzer)
()
()

Implement selective verification: only formally check low-confidence outputs:

class SelectiveVerifier:
    """Route LLM outputs to verification based on uncertainty."""

    def __init__(self, calibrator: DomainUncertaintyCalibrator,
                 formal_verifier_fn, confidence_threshold: float = 0.7):
        self.calibrator = calibrator
        self.formal_verifier = formal_verifier_fn  # Function that returns correctness
        self.threshold = confidence_threshold
        self.verification_cache = {}

    def process_reasoning(self, text: str, analyzer: UncertaintyAnalyzer) -> Dict:
        """
        Process reasoning output with selective verification.
        High confidence → skip verification, return predicted correct.
        Low confidence → formally verify.
        """
        # Predict correctness from uncertainty signals
        confidence, signals = self.calibrator.predict_correctness(text, analyzer)

        result = {
            "text": text,
            "predicted_confidence": confidence,
            "signals": signals,
            "verified": False,
            "actual_correctness": None
        }

        # Selective verification
        if confidence >= self.threshold:
            # High confidence: skip formal verification
            result["decision"] = "TRUST"
            result["actual_correctness"] = 1  # Assume correct
        else:
            
            result[] = 
            result[] = .formal_verifier(text)
            result[] = 

         result


 () -> :
    
    
          reasoning.lower()  

verifier = SelectiveVerifier(
    calibrator,
    mock_formal_verifier,
    confidence_threshold=
)

test_reasoning = [
    ,
    ,
]

 reasoning  test_reasoning:
    result = verifier.process_reasoning(reasoning, analyzer)
    ()
    ()
     result[]:
        ()
    ()

Practical Guidance

Aspect	Details
Confidence Threshold	Start at 0.7; lower if verification is expensive, raise if cost of errors is high
Domain Calibration Data	100-500 annotated examples sufficient; must be representative of target task
Signal Extraction Cost	~10-50ms per text; negligible vs. formal verification (often seconds)
Verification Backend	Use SMT solvers (Z3), proof assistants (Coq), or domain-specific checkers
Update Frequency	Recalibrate quarterly or when error patterns shift

When to Use:

• Formal reasoning with high cost of errors (code synthesis, theorem proving, policy formalization)
• Limited verification budget (can't check every output)
• Multiple reasoning domains with different uncertainty patterns
• Need transparency about which outputs are trustworthy

When NOT to Use:

• Real-time systems where added latency is critical (verification delay dominates)
• Tasks where all outputs must be verified anyway (no cost savings)
• Insufficient historical correctness data to calibrate domain signals
• Highly novel reasoning tasks where calibration patterns don't transfer

Common Pitfalls:

• Domain shift: uncertainty patterns from logic don't transfer to factual reasoning; recalibrate for each domain
• Overconfident predictions: if LLM is generally unreliable, signals become noise; invest in better base model first
• Verification coverage bias: if verification is biased (easier problems verified), calibration becomes skewed
• Ignoring model updates: retraining LLM changes uncertainty signals; recalibrate whenever base model changes

Reference

Grammars of Formal Uncertainty: When to Trust LLMs in Automated Reasoning Tasks https://arxiv.org/abs/2505.20047