TL;DR
Frontier large language models (LLMs) like GPT-5 and Claude Sonnet-4.5 can predict program termination with an accuracy that rivals top-tier, specialized symbolic verification tools. However, a stark "classification-proof gap" remains: while these models excel at intuitively identifying whether a program will halt, they frequently fail to generate the formally verifiable graph-based proofs (witness automata) required by automated verifiers.
What Problem Does This Paper Address?
Program termination—determining whether a piece of code will eventually stop running or loop forever—is famously undecidable, a fundamental truth established by Alan Turing’s Halting Problem. Because no universal algorithm can solve it, the software verification community has spent decades building highly complex, language-specific symbolic tools to approximate termination analysis.
With the rapid rise of LLMs in coding tasks, the authors of this paper ask a natural question: To what extent can general-purpose frontier LLMs reason about program termination? If LLMs can successfully tackle this problem, they could offer a simpler, language-agnostic alternative or complement to traditional heavy-duty verification pipelines.
Methods
The authors evaluated several frontier models—including OpenAI's GPT-5, Claude Sonnet-4.5, Qwen3-32B, and CWM (a code world model)—alongside a non-reasoning baseline (GPT-4o).
To maximize the models' performance, they implemented a Test-Time Scaling (TTS) with Consensus Voting pipeline. Instead of relying on a single answer, the system generates multiple predictions and uses a strict consensus voting mechanism (requiring a unanimous vote among sampled outputs) to determine the final verdict. If the models disagree, it outputs "Unknown" to avoid the heavy scoring penalties associated with incorrect answers.
Furthermore, recognizing that the standard graph-based proof format used in formal verification is highly complex for text-based models, the authors introduced a novel divergence-precondition formulation. Instead of generating a state-transition graph, the LLM is asked to directly output a logical expression (e.g., x < 0 and y == 0) defining the exact input conditions that will cause the program to run indefinitely. These expressions are then mathematically validated using the Z3 theorem prover.
Datasets
The study utilizes two primary datasets:
- SV-COMP 2025 (Termination Category): The community-standard benchmark for software verification, containing 2,328 C programs spanning bit-precise arithmetic, complex control flows, and dynamic heap manipulation.
- Divergence Precondition Dataset: A newly introduced dataset created by the authors, consisting of 40 linear and 40 non-linear non-terminating programs from SV-COMP, manually annotated with ground-truth logical expressions that define their non-termination domains.
Key Insights and Ideas
- The Classification-Proof Gap: LLMs possess strong semantic intuition; they can often correctly guess if a program terminates. However, they struggle with symbolic precision, frequently failing to construct the exact syntactical graph structure required to prove why it doesn't terminate.
- Undecidable vs. Decidable Strengths: Interestingly, while LLMs often underperform classical solvers on decidable tasks like SAT solving (which require exhaustive, brute-force search), they are remarkably competitive on undecidable problems like termination. This suggests that undecidable problems, which rely heavily on heuristic reasoning and pattern recognition, are a more natural fit for LLM capabilities.
- Format Matters for Proofs: Shifting the proof requirement from a complex graph-based automaton to a logical precondition formula significantly boosted model accuracy, showing that traditional verification formats may be an artificial bottleneck for language models.
Key Results
When boosted by Test-Time Scaling, frontier LLMs achieved performance levels that directly challenge state-of-the-art symbolic verifiers.
- Top-Tier Performance: GPT-5 achieved an SV-COMP score of 3,520 and Claude Sonnet-4.5 scored 3,448, effectively placing them 2nd and 3rd in the global competition rankings, trailing only the specialized tool PROTON (3,685) and outperforming the runner-up UAutomizer (3,334).
- Open-Weights Success: CWM scored 3,129, performing competitively just below UAutomizer.
- The Length Bottleneck: Across all models, performance degraded significantly as the complexity and length of the code increased, highlighting a vulnerability in long-context global reasoning.
- Precondition Accuracy: On the newly proposed domain witness task, Claude Sonnet-4.5 achieved an impressive 87% Pass@1 accuracy on linear conditions and 77% Pass@1 on complex, non-linear polynomial conditions.
Limitations and Future Work
- Language Scope: The evaluation was strictly limited to C programs within the SV-COMP benchmark.
- Opaque Architectures: The highest-performing model, GPT-5, is proprietary, meaning its internal reasoning tokens and exact scale remain unknown.
- Prompt Sensitivity: Like most LLM tasks, performance can fluctuate based on minor prompt adjustments, though the authors mitigated this by using a simple, unoptimized standardized prompt.
- Future Directions: The authors advocate for neuro-symbolic approaches—combining the intuitive, language-agnostic reasoning of LLMs with the rigorous, absolute correctness of symbolic proof checkers—and expanding benchmarks to evaluate real-world, repository-level codebases.
Summary updated