💻 computer science

Can Large Language Models Model Programs Formally?

This paper introduces Model-Bench, a benchmark and pipeline comprising 400 Python programs designed to evaluate and improve Large Language Models' ability to automatically generate verification-ready model checking specifications, revealing significant current limitations in this capability.

Original authors: Zhiyong Chen, Jialun Cao, Jiarong Wu, Chang Xu, Shing-Chi Cheung

Published 2026-04-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhiyong Chen, Jialun Cao, Jiarong Wu, Chang Xu, Shing-Chi Cheung

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very talented, super-fast translator who speaks every human language and can write code in Python. You ask this translator to take a complex Python program and rewrite it into a completely different language called TLA+.

But here's the catch: TLA+ isn't just another programming language for building apps. It's a mathematical language for proving truth. It's like asking a translator to turn a novel into a rigorous mathematical proof that guarantees the story cannot have a plot hole.

This paper, titled "Can Large Language Models Model Programs Formally?", asks a simple but tough question: Can AI (like the translator) actually do this job?

Here is the breakdown of their journey, using some everyday analogies.

1. The Problem: The "Blueprint" Gap

In the world of software, there are two ways to check if a program is safe:

Testing: Driving a car on a few different roads to see if it breaks. (Good, but you might miss a hidden cliff).
Formal Verification: Building a perfect mathematical blueprint of the car and proving, with math, that it cannot fall off a cliff, no matter what.

The "blueprint" part is called Model Checking. It's incredibly hard to do automatically because turning messy, flexible code (like Python) into a rigid, mathematical blueprint (TLA+) is like trying to turn a free-flowing jazz improvisation into a strict military marching order.

Until now, AI has been great at helping with the "math proof" part (Theorem Proving), but it has struggled with the "blueprint" part (Model Checking) because the AI gets confused by the messy details of real-world code.

2. The Solution: Model-Bench (The Training Gym)

The authors built a new gym called Model-Bench.

The Workout: They took 400 Python programs (from popular coding challenges) and asked various AI models to turn them into TLA+ blueprints.
The Goal: To see if the AI can create a blueprint that a "Model Checker" (a strict referee) can verify without errors.
The Twist: They didn't just throw the code at the AI. They tried two different coaching methods:
1. Direct Translation: "Here is the Python code, turn it into TLA+."
2. The "Pre-Processing" Trick: Before asking the AI, they ran the code through a robot that simplified it. They stripped away complex features (like fancy loops or weird libraries) and turned the code into a simple "state machine" (like a flowchart). This made the code look more like the TLA+ language the AI needed to speak.

3. The Results: The AI is Trying, But It's Stumbling

The results were a mix of "Not bad!" and "Oh no."

The Good News: The best AI models (like DeepSeek-V3) could successfully create a working blueprint about 50% of the time when given a few examples to learn from. That's a start!
The Bad News: When the AI had to do it alone (without examples), it failed almost 100% of the time.
The "State Similarity" Issue: Even when the AI got the blueprint to run, it often didn't match the original program perfectly. It was like the AI built a car that looks like the original and drives, but the engine parts are slightly different. It passed the "runnable" test but failed the "exact match" test.

4. The "Pre-Processing" Trick: A Double-Edged Sword

The authors tried that "Pre-Processing" trick (simplifying the code first).

What happened? The blueprints became much more accurate (better similarity). The AI understood the logic better.
The Catch: The blueprints were slightly less likely to run without crashing. Why? Because the simplified code was longer and more complex to type out, causing the AI to get "lost in the middle" of its own sentence.
The Takeaway: Using both the original code and the simplified code together gave the best results. It's like having a human translator check the AI's work; they complement each other.

5. Why Did It Fail? (The "Bad Cases")

The authors looked at the errors and found three main reasons the AI got stuck:

The "Dictionary" Problem: Python has built-in tools (like sort()) that TLA+ doesn't have. The AI tried to use them anyway, causing a crash. It's like asking a chef to "use a blender" in a kitchen that only has a mortar and pestle.
The "Counting" Problem: Python counts starting at 0 (0, 1, 2...), but TLA+ counts starting at 1 (1, 2, 3...). The AI kept forgetting this rule, leading to "off-by-one" errors.
The "Too Faithful" Problem: Sometimes the AI was too loyal to the original code. It tried to copy every single detail, including things that shouldn't be in a mathematical proof, causing the logic to break.

The Big Picture

This paper is a reality check. It tells us that while AI is amazing at writing code, it is not yet a master of formal mathematical modeling.

Analogy: Think of AI as a brilliant apprentice carpenter. It can build a beautiful chair (write code) very fast. But asking it to draw the engineering schematics that prove the chair will never collapse under any weight (Formal Modeling) is still too hard for it. It needs more training, better tools, and perhaps a human supervisor to double-check the math.

The Future: The authors hope this "Model-Bench" will help train the next generation of AIs to become not just code writers, but code verifiers, ensuring our critical software (like self-driving cars or medical devices) is mathematically proven to be safe.

1. Problem Statement

Formal verification is critical for ensuring software correctness, safety, and reliability, particularly in critical infrastructure. It primarily consists of two approaches: Theorem Proving and Model Checking.

Theorem Proving has seen significant advances driven by Large Language Models (LLMs) in areas like autoformalization and proof generation.
Model Checking, however, remains underexplored by LLMs. The primary bottleneck is automatic program modeling: the difficulty of automatically deriving accurate, tractable behavioral models from source code.
The Gap: Dynamic languages like Python possess rich runtime behaviors (mutable aliasing, higher-order functions, async/await) that are difficult to abstract into a finite state space required by model checkers (like TLA+). Existing benchmarks focus on translating natural language to formal specs, not source code to formal specs.

2. Methodology: Model-Bench

The authors introduce Model-Bench, a benchmark and pipeline designed to evaluate and improve LLMs' ability to model Python programs into TLA+ (Temporal Logic of Actions) specifications, which are verifiable by the TLC model checker.

A. Data Construction

Sources: 400 Python programs derived from three standard benchmarks: HumanEval, MBPP, and LiveCodeBench.
Preprocessing Pipeline:
1. Normalization: Deduplication and standardization of code and test cases.
2. Simplification & Rewriting:
  - Libraries: Removed complex dependencies; retained only typing and math.
  - Language Features: Rewrote complex features (recursion, list comprehensions, classes, generators) into simpler constructs to ensure compatibility with TLA+.
  - Types: Excluded complex types beyond basic primitives (None, Number, String, List, Tuple, Dict).
3. Execution Verification: Ensured all filtered programs passed their original test cases.
Prompt Strategies: Three prompt variants were tested:
1. Original code + 2 examples (Few-shot).
2. Original code only (Zero-shot).
3. Transformed Code + 2 examples (Few-shot).

B. Code Transformation Strategy

To bridge the gap between Python's execution model and TLA+'s state-machine model, the authors developed a Code Transformation technique:

Mechanism: Converts Python code into a Control-Flow Graph (CFG) and then rewrites it into a state-machine pattern.
Implementation:
- Introduces a program counter (pc) variable to track the current state.
- Wraps logic in a while True loop with if statements controlled by pc.
- Converts Python strings to integer arrays (ASCII) to handle TLA+ immutability constraints.
Goal: To make the code structure more similar to TLA+ actions, aiding LLM pattern recognition.

C. Evaluation Metrics

Runnable@k: The proportion of generated models that pass the TLC model checker without errors at least once within $k$ generated samples (similar to Pass@k).
State Similarity: A formal metric measuring the overlap between the state traces of the generated model ( $M_g$ ) and the oracle (ground truth) model ( $M_o$ ). It calculates the proportion of states in $M_o$ that are also present in $M_g$ , ensuring semantic alignment rather than just syntactic correctness.

3. Key Contributions

Model-Bench: The first general-purpose benchmark for LLM-based automatic modeling from source code (Python) to formal specifications (TLA+).
Code Transformation Pipeline: A novel method to lower-level Python code into a state-machine representation, demonstrating that structural alignment improves modeling quality.
Comprehensive Evaluation: Extensive experiments across 8 LLMs (including DeepSeek, Qwen, Gemma, Llama) using multiple metrics and prompt settings.
Insightful Analysis: Identification of specific failure modes (compilation, runtime, assertion errors) and the correlation between code complexity and modeling success.

4. Experimental Results

The study evaluated 8 LLMs across different prompt settings. Key findings include:

Overall Performance (RQ1):
- Top Performers: DeepSeek-V3, DeepSeek-V2.5, and Qwen3-32B achieved the best results.
- Best Metric: DeepSeek-V3 achieved a Runnable@1 of 51.75% and an Average Similarity of 49.55% (with few-shot prompting).
- Zero-Shot vs. Few-Shot: Few-shot learning provided a massive boost. Zero-shot performance was near zero for many models (e.g., Llama-3.1-8B-Instruct had ~1% Runnable@1), while few-shot improved this significantly.
Effectiveness of Code Transformation (RQ2):
- Trade-off: Using transformed code decreased the Runnable@k rate (due to increased code length and "lost in the middle" issues) but significantly increased State Similarity.
- Example: DeepSeek-V3's similarity jumped from 49.55% (Original) to 68.54% (Transformed).
- Ensemble: Combining results from original and transformed prompts yielded the highest total number of runnable models.
Impact of Complexity (RQ3):
- Negative Correlation: Higher syntactic complexity (Cyclomatic complexity, loop depth, variable count) correlates with lower success rates.
- Algorithmic Difficulty: Interestingly, the algorithmic difficulty (e.g., "Hard" vs. "Easy" problem ratings) did not reliably predict modeling difficulty; structural complexity was the dominant factor.
Bad Case Analysis (RQ4):
- Compilation Errors: Caused by missing built-in functions (e.g., sort) or unknown operators.
- Runtime Errors: Often due to language-specific differences, such as 1-based array indexing in TLA+ vs. 0-based in Python.
- Assertion Errors: Caused by excessive fidelity to source code (e.g., omitting necessary function calls like .lower()) or incorrect loop bounds (using constants instead of dynamic lengths).

5. Significance

Bridging the Gap: This work addresses the critical bottleneck in formal verification by shifting focus from natural language to source code, enabling automated verification of existing software.
Practical Utility: The findings suggest that while LLMs struggle with complex modeling, code transformation and few-shot prompting are viable strategies to improve semantic fidelity.
Future Directions: The paper highlights that future LLMs need better reasoning capabilities regarding language semantics (e.g., indexing rules) and state management to fully automate formal model checking. Model-Bench provides a standardized platform to drive this progress.