PAT-Agent: Autoformalization for Model Checking
Xinyue Zuo, Yifan Zhang, Hongshu Wang, Yufan Cai 1, Zhe Hou, Jing Sun, Jin Song Dong · 2025
Read PAT-Agent: Autoformalization for Model Checking by Xinyue Zuo, Yifan Zhang, Hongshu Wang, Yufan Cai 1, Zhe Hou, Jing Sun, Jin Song Dong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-23675.txt.
Introduction
Writing a formal model that a checker can verify is expert work, slow and error-prone by hand. Xinyue Zuo and 6 co-authors built PAT-Agent to automate that path from plain words to verified models. A planning model first pulls out key elements and drafts a plan. A code model then writes the formal model, and the PAT checker tests it against the user's properties.
When the check fails, a repair loop uses counterexamples to fix the model step by step. A web interface lets non-experts describe and verify system behavior through chat. On forty systems, the agent beat baselines on success and speed, and a user study found the interface accessible.
Catalog record
| CREATOR | Xinyue Zuo, Yifan Zhang, Hongshu Wang, Yufan Cai 1, Zhe Hou, Jing Sun, Jin Song Dong |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-23675
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
PAT-Agent: Autoformalization for Model Checking Xinyue Zuo, Yifan Zhang, Hongshu Wang, Yufan Cai 1, Zhe Hou, Jing Sun, Jin Song Dong Abstract Recent advances in large language models (LLMs) offer promising potential for automating formal methods. However, applying them to formal verification remains challenging due to the complexity of specification languages, the risk of hallucinated output, and the semantic gap between natural language and formal logic. We introduce PAT-Agent, an end-to-end framework for natural language autoformalization and formal model repair that combines the generative capabilities of LLMs with the rigor of formal verification to automate the construction of verifiable formal models. In PAT-Agent, a Planning LLM first extracts key modeling elements and generates a detailed plan using semantic prompts, which then guides a Code Generation LLM to synthesize syntactically correct and semantically faithful formal models. The resulting code is verified using the Process Analysis Toolkit (PAT) model checker against user-specified properties, and when discrepancies occur, a Repair Loop is triggered to iteratively correct the model using counterexamples. To improve flexibility, we built a web-based interface that enables users, particularly non-FM-experts, to describe, customize, and verify system behaviors through user-LLM interactions. Experimental results on 40 systems show that PAT-Agent consistently outperforms baselines, achieving high verification success with superior efficiency. The ablation studies confirm the importance of both planning and repair components, and the user study demonstrates that our interface is accessible and supports effective formal modeling, even for users with limited formal methods experience. 1 1 footnotetext: 1 corresponding author I Introduction Formal methods provide mathematically rigorous techniques for specifying and verifying the correctness of software and hardware systems. Despite their well-established benefits in safety-critical and concurrent domains, their broader adoption remains limited due to the steep learning curve, lack of accessible tooling, and the complexity of formal languages. Recent advances in large language models (LLMs), such as OpenAI o3 [ 26 ] and LLaMA [ 13 ] , have demonstrated strong capabilities in natural language understanding and code generation. These models present a promising opportunity to bridge the gap between informal requirements and formal specifications, particularly for users without formal methods expertise. By leveraging LLMs, it becomes feasible to lower the barrier to entry for formal modeling and make correctness assurance more broadly accessible. Challenges. However, applying LLMs to formal model synthesis introduces significant challenges. LLMs are prone to hallucinations and logical inconsistencies [ 17 , 39 ] , especially when generating complex artifacts such as process algebra models or temporal logic specifications. Their outputs may violate syntactic rules, diverge from user intent, or overlook critical correctness properties. Existing works on synthesizing formal specifications from natural language instructions have a focus on fine-grained formulae, such as temporal logic [ 8 , 11 ] . There are emerging attempts to synthesize system-level models using LLMs, but these works [ 5 , 16 ] focus on simpler systems and exhibit limited success, relying solely on direct generation from natural language. In contrast, PAT-Agent integrates structured planning and verification-guided repair, enabling the synthesis of more complex and verifiable models. Meanwhile, traditional rule-based synthesis pipelines are labor-intensive and difficult to generalize across diverse systems and domains. These limitations underscore the need for a unified framework that combines the flexibility and automation capacity of LLMs with the rigor of formal verification to produce reliable, verifiable models at scale. Our Solution. We propose PAT-Agent , a novel framework for natural language autoformalization and formal code repair. PAT-Agent combines the generative power of LLMs with the rigor of formal verification to automate the construction of verifiable system models. Built on top of the Process Analysis Toolkit (PAT), our approach differs from direct natural language–to–code generation and instead adopts a structured intermediate representation based on semantic prompts. These prompts capture reusable modeling constructs, such as variables and guarded actions, and are parameterized to guide code generation in a controlled, interpretable manner. The pipeline operates in modular stages. A Planning LLM first analyzes the natural language description and extracts the modeling elements. These elements are further used to populate the structured semantic prompt that guides the generation of a detailed plan for formal code synthesis. A Code Generation LLM then converts the plan into syntactically valid, semantically aligned PAT models. The resulting model is verified using the PAT model checker, and if any user-defined requirements are not satisfied, a Repair Loop is triggered to iteratively revise the model based on counterexamples and failure traces. This decomposition of tasks across multiple LLMs is motivated by prior works [ 18 , 9 ] , which show that breaking down complex generation into several sub-tasks can improve effectiveness. To support usability, accessibility, and iterative development, we further develop a web-based interface that supports guided modeling, verification, and repair. Users can input natural language descriptions, inspect and edit the extracted intermediate representations, review verification results, and apply automatic corrections through a seamless feedback loop. All code, datasets, and the interface are publically available 1 1 1 https://github.com/ZuoXinyue/PAT-Agent . This paper makes the following contributions: • We propose PAT-Agent, a fully automated end-to-end framework for natural language autoformalization and formal code repair. It uses a semantic prompt-based decomposition strategy to extract structured modeling elements and incorporates a verification-guided repair loop to iteratively correct invalid models based on model checker feedback. An ablation study confirms the effectiveness of both components in achieving high verification success. • We conduct a comprehensive evaluation of PAT-Agent on 40 diverse modeling tasks curated from three sources, demonstrating its high effectiveness and efficiency in generating correct and verifiable models compared to direct LLM baselines and alternative model combinations. • We design a user-centric interface that enables human-in-the-loop development, complementing the automated pipeline. It allows non-experts to build and verify formal system models with minimal effort. A user study confirms the usability and accessibility of the interface. II Preliminary This section gives an overview of the Process Analysis Toolkit (PAT) and its modelling language CSP# . II-A The PAT Framework Model checking is a method for checking whether a finite-state model of a system meets a given specification. We build our autoformalization framework on PAT (Process Analysis Toolkit [ 33 ] ), an existing extensible model checker that supports state-space exploration and LTL verification for concurrent and real-time systems. Its underlying formalism, CSP# , is a dialect of Communicating Sequential Processes (CSP) enriched with imperative C# statements and typed variables. PAT has been successfully applied in domains such as industrial protocols, real-time controllers, and cyber-physical systems [ 32 , 2 ] . Nevertheless, building a correct model remains an expertise-intensive task. Our method tackles this bottleneck by prompting large language models (LLMs) to synthesize CSP# code directly from informal descriptions, and then verifying it against requirements. II-B Syntax and Semantics of CSP# The subset of CSP# used in our study can be generated by the grammar: \begin{array}[]{lcl}P&::=&\textbf{Stop}\mid\textbf{Skip}\mid e\,\rightarrow P\mid e\{\textit{prog}\}\,\rightarrow P\mid P\,\Box\,Q\\[2.0pt] &\mid&\textbf{if}(b)\{P\}\ \textbf{else}\{Q\}\mid P;Q\mid P\parallel_{A}Q\mid P\;|||\;Q\\[2.0pt] \end{array} A process is a labelled transition system (LTS) \langle S,\ \mathit{Act},\ \rightarrow,\ s_{0}\rangle,\text{ where} • S is the set of program states—valuations of a finite set of typed variables; • \mathit{Act} is the alphabet of observable events ; internal (silent) actions are denoted \tau and excluded from \mathit{Act} ; • \rightarrow\subseteq S\times(\mathit{Act}\cup\{\tau\})\times S