Towards Formal Verification of LLM-Generated Code from Natural Language Prompts DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 8 CCS: Theory of computation Program verification CCS: Software and its engineering Automatic programming CCS: Software and its engineering Domain specific languages

Aaron Councilman, David Fu, Aryan Gupta, Chengxiao Wang, David Grove, Yu-Xiong Wang, Vikram Adve · 2025

Read Towards Formal Verification of LLM-Generated Code from Natural Language Prompts DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 8 CCS: Theory of computation Program verification CCS: Software and its engineering Automatic programming CCS: Software and its engineering Domain specific languages by Aaron Councilman, David Fu, Aryan Gupta, Chengxiao Wang, David Grove, Yu-Xiong Wang, Vikram Adve (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-2507-13290.txt.

Introduction

Aaron Councilman and co-authors build, in a 2025 paper, a system that formally checks code written by language models from plain English requests. Model-written code is handy but far too shaky for critical systems without proof. Their answer is a formal query language that reads almost like natural speech, so users can confirm it captures their intent before any checking starts.

The system, built for a widely used system-setup language, adds a formal model of program behavior, a symbolic runner, and a matching engine. A knowledge base stores machine-specific facts so queries stay simple. On twenty-one tasks, the checker confirmed correct code in most cases. The work aims to make AI coding help safe enough for critical use.

Catalog record

CREATORAaron Councilman, David Fu, Aryan Gupta, Chengxiao Wang, David Grove, Yu-Xiong Wang, Vikram Adve
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-13290

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Towards Formal Verification of LLM-Generated Code from Natural Language Prompts DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 8 CCS: Theory of computation Program verification CCS: Software and its engineering Automatic programming CCS: Software and its engineering Domain specific languages Aaron Councilman, David Fu, Aryan Gupta, Chengxiao Wang, David Grove, Yu-Xiong Wang, Vikram Adve Abstract . In the past few years LLMs have emerged as a tool that can aid programmers by taking natural language descriptions and generating code based on it. However, LLMs often generate incorrect code that users need to fix and the literature suggests users often struggle to detect these errors. In this work we seek to offer formal guarantees of correctness to LLM generated code; such guarantees could improve the experience of using AI Code Assistants and potentially enable natural language programming for users with little or no programming knowledge. To address this challenge we propose to incorporate a formal query language that can represent a user’s intent in a formally defined but natural language-like manner that a user can confirm matches their intent. Then, using such a query we propose to verify LLM generated code to ensure it matches the user’s intent. We implement these ideas in our system, Astrogator, for the Ansible programming language which includes such a formal query language, a calculus for representing the behavior of Ansible programs, and a symbolic interpreter which is used for the verification. On a benchmark suite of 21 code-generation tasks, our verifier is able to verify correct code in 83% of cases and identify incorrect code in 92%. 1. Introduction In recent years, Large Language Models (LLMs) have proven to be surprisingly successful at generating code from natural language prompts ( Rozière et al. 2023 ; Guo et al. 2024 ; Lozhkov et al. 2024 ) . The ability to program using natural language, often called natural language programming , has been a long sought after dream of the programming languages community ( Sammet 1966 ) , though has also received some criticism ( Dijkstra 1979 ) . If natural language programming was achieved it would enable programming a computer without needing to learn a programming language and could therefore help democratize computer programming. The ability to use LLMs for this purpose has led some to speculate that prompting LLMs to generate code will fully replace traditional programming, but as has been pointed out throughout the history of the search for natural language programming, programming in natural language has many challenges and using LLMs for this purpose has even more ( Yellin 2023 ) . For example, LLMs are known to suffer from hallucinations in code generation, including through generating code that uses non-existent APIs and libraries ( Zhang et al. 2025b ) and LLMs have also been shown to struggle with many practical programming tasks that rely on complex functions ( Zhuo et al. 2025 ; Nguyen et al. 2025 ) and involve reasoning about large codebases ( Jimenez et al. 2024 ) . Using an LLM as a coding assistants seems to offer potential benefits to programmers ( Ziegler et al. 2022 ; Liang et al. 2024 ; Barke et al. 2023 ) , including novice programmers ( Kazemitabaar et al. 2023 ) . However, such use is still a significant gap from true natural language programming, as the LLM only generates code fragments that often require modifications and potentially incorporation by the user ( Sahoo et al. 2024 ; Vaithilingam et al. 2022 ) . In the natural language programming setting described above, however, there is no user skilled in that language who can validate the generated code meaning that errors in generated code are unlikely to be caught. Even in the AI Code Assistant setting the literature suggests that users often have a hard time checking LLM generated code ( Liang et al. 2024 ) and that use of AI Coding Assistants can be associated with less secure code ( Perry et al. 2023 ) , suggesting users struggle to check such aspects of generated code. It is therefore essential to Natural Language Programming setting, and would greatly benefit the AI Code Assistant setting, to be able to provide a guarantee that the generated code is correct. In our current work we are particularly interested in providing such guarantees for generating code in Domain-Specific Languages (DSLs). The problem of correctness of LLM generated code is exacerbated in the context of DSLs because due to their often niche use the amount of available data on which models train is significantly lower than for general-purpose languages and due to the smaller user-bases there is a lack of tools for developers and research in DSL code generation ( Gu et al. 2025 ) . Additionally, we believe that the challenge of providing guarantees that generated code is correct may be easier in DSLs because we can use specialized domain knowledge not available in general-purpose programming languages (GPLs). Many DSLs are also not Turing Complete, which can make techniques from program verification more tractable. In this work, we focus on the Ansible programming language, which is used for IT automation; Ansible is an interesting example for us as it has a relatively large user-base and is important enough that it was acquired by Red Hat in 2015. We provide additional background on Ansible in Section 2.1 . Our broad, long-term goal – which may not be fully realizable as a formal proof – is to provide a high degree of confidence that LLM generated code for a given natural language description has the user’s desired functionality . This goal is a step towards true natural language programming, in which we would like to offer complete formal guarantees of correctness, as well as in the AI Code Assistant setting, where this goal could significantly improve the correctness of LLM generated code and help avoid undetected errors. Traditional approaches to offering formal guarantees of correctness, such as program synthesis and verification, are not immediately suitable to this setting because they rely on a formal specification of the problem, not a natural language description which, in general, may be ambiguous, vague, or incomplete. In this paper, we aim to provide formal correctness guarantees that brings us close to this longer-term goal. In particular, we propose the incorporation of a high-level and domain-specific formal query language which is designed to be close to the syntax of natural language but is precisely and formally defined. Moreover, we aim to design this formal query language to be at a similar level of abstraction as we expect the user’s natural language description to be – using similar concepts and actions – so that a user can easily understand this formal query and ensure it reflects their intent. We then propose to use this formal query to verify generated programs which enables us to ensure they match the user’s intent. Even in the context of DSLs this formal verification is very difficult; we propose a particular solution for Ansible using symbolic interpretation of a novel calculus, but this approach is unlikely to work for all languages. Our key contributions in this work are as follows: (1) Formalize our notion of natural language programming. (2) Propose

Read the complete text