HoarePrompt: Structural Reasoning About Program Correctness in Natural Language

Dimitrios Stamatios Bouras, Yihan Dai, Tairan Wang, Yingfei Xiong, Sergey Mechtaev · 2025

Read HoarePrompt: Structural Reasoning About Program Correctness in Natural Language by Dimitrios Stamatios Bouras, Yihan Dai, Tairan Wang, Yingfei Xiong, Sergey Mechtaev (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-2503-19599.txt.

Introduction

Dimitrios Bouras and co-authors present HoarePrompt, a way to check code against needs written in plain words. Their twenty twenty-five paper notes that language models often miss even plain bugs when asked to verify a program. Requirements live in natural language, which makes checking hard.

The method borrows from classic Hoare logic and strongest postcondition work. A model writes plain-word accounts of the states a program can reach at key points. Loops are handled by a few-shot form of k-induction, a known model-checking trick. Step-by-step state accounts help the model catch faults it would gloss over in one pass.

Catalog record

CREATORDimitrios Stamatios Bouras, Yihan Dai, Tairan Wang, Yingfei Xiong, Sergey Mechtaev
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE134 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-19599

Browse the full library · About the Tower of Babel

Full text

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

HoarePrompt: Structural Reasoning About Program Correctness in Natural Language Dimitrios Stamatios Bouras, Yihan Dai, Tairan Wang, Yingfei Xiong, Sergey Mechtaev Abstract . While software requirements are often expressed in natural language, verifying the correctness of a program against such requirements is a hard and underexplored problem. Large language models (LLMs) are promising candidates for addressing this challenge, however, our experience shows that they are ineffective in this task, often failing to detect even straightforward bugs. To address this gap, we introduce HoarePrompt, a novel approach that adapts fundamental ideas from program verification to natural language artifacts. Inspired by the strongest postcondition calculus, HoarePrompt employs a systematic, step-by-step process in which an LLM generates natural language descriptions of reachable program states at various code points. To manage loops, we propose few-shot-driven k-induction, an adaptation of the k-induction method widely used in model checking. Once program states are described, HoarePrompt leverages the LLM to assess whether the program, annotated with these state descriptions, conforms to the natural language requirements. For evaluating the quality of classifiers of program correctness with respect to natural language requirements, we constructed CoCoClaNeL, a challenging dataset of solutions to programming competition problems. Our experiments show that HoarePrompt improves the MCC by 61% compared to directly using Zero-shot-CoT prompts for correctness classification. Furthermore, HoarePrompt outperforms a classifier that assesses correctness via LLM-based test generation by an MCC increase of 106%. The inductive reasoning mechanism contributes a 26% boost to MCC, underscoring its effectiveness in managing loops. \tl_set:Ne \highlight highlight \tl_set:Ne \highlightblue highlightblue Conference: 2026 IEEE/ACM 48th International Conference on Software Engineering; April 12–18, 2026; Rio de Janeiro, Brazil 2026 IEEE/ACM 48th International Conference on Software Engineering (ICSE ’26), April 12–18, 2026, Rio de Janeiro, Brazil DOI: 10.1145/3744916.3773206 ISBN: 979-8-4007-2025-3/2026/04 † † cc-license: by 1. Introduction Assessing whether a program meets its requirements is a key part of software quality assurance. In practice, these requirements are often written in natural language, geared towards human-to-human communication or designed as prompts for LLMs. Verifying program correctness against such requirements is an inherently difficult and unexplored challenge. One approach is address it is to generate tests based on requirements using an LLM, and use these tests to check program correctness ( Chen et al., 2022 ) . More generally, natural language requirements can be translated in formal ones, and then used in conjunction with verification tools ( Endres et al., 2024 ) . Despite the promise of these approaches, our experiments show that LLMs tend to generate incorrect or incomplete assertions when handling complex requirements, which reduces their accuracy. Another option is to directly employ LLMs to assess a program’s conformance to requirements, relying on LLMs’ ability to reason about both natural language and code ( Liu et al., 2024c ) . Our experiments show that the state-of-the-art LLMs struggle with this task, often failing to identify even simple bugs. We attribute this limitation to the models’ inability to reason about the intricacies of program semantics. To address this gap, we introduce HoarePrompt, a program analysis approach for reasoning about program correctness w.r.t. natural language requirements that synergizes LLM reasoning techniques with ideas from program verification. In its core is the natural Hoare triple , a variant of the traditional Hoare triple ( Hoare, 1969 ) with pre- and postconditions expressed in natural language; for example, \color[rgb]{0.2539,0.4102,0.8828}\{\text{x is a full name}\}\,\mathtt{x=x.split()[0]}\,\color[rgb]{0.2539,0.4102,0.8828}\{\text{x is a first name}\}. Inspired by the strongest postcondition calculus ( Dijkstra et al., 1976 ) , HoarePrompt employs a step-by-step process to generate natural language descriptions of reachable program states at various points in the code. This is achieved by sampling natural strongest postconditions (NSP) from \mathcal{SP} , our LLM-based natural Hoare triple completion model defining the conditional probability distribution \mathcal{SP}(\color[rgb]{0.2539,0.4102,0.8828}\mathrm{Post}\,\mid\,\color[rgb]{0.2539,0.4102,0.8828}\mathrm{Pre},C), where \color[rgb]{0.2539,0.4102,0.8828}\mathrm{Pre},\color[rgb]{0.2539,0.4102,0.8828}\mathrm{Post} are natural pre- and postconditions, C is a program fragment. Inspired by methods to enhance LLM reasoning about program execution ( Ni et al., 2024 ) , HoarePrompt uses these state descriptions to annotate a program, and then prompts an LLM to assess if the annotated program aligns with the given requirements. Figure 1 . Annotating code with natural language descriptions of reachable program states, which are automatically inferred by HoarePrompt, enables an LLM to find a bug that is missed by the straightforward Vanilla prompt. HoarePrompt’s key novelty in comparison with traditional program analysis and verification is in using natural language as the medium of reasoning about program semantics, as opposed to, e.g., first-order logic ( Filliâtre and Paskevich, 2013 ) or monotonic functions over lattices ( Cousot and Cousot, 1977 ) . This enables a direct application of HoarePrompt to assessing program correctness w.r.t. natural language requirements without hard and time-consuming formal modeling. In comparison to previous techniques for reasoning about code with LLMs ( Ni et al., 2024 ; Liu et al., 2024c ; Jiang et al., 2024 ) , HoarePrompt reasons about all reachable states simultaneously instead of individual concrete states. This enables HoarePrompt to operate statically, without executing the program and without reliance on provided failing tests. In comparison with directly prompting LLMs to analyze programs, HoarePrompt simplifies this task by decomposing it into small, independent subtasks, which are solved step-by-step in the spirit of chain-of-thought reasoning ( Wei et al., 2022 ) . Loops pose a fundamental challenge in program analysis and verification because they give rise to infinite execution paths ( Si et al., 2018 ) . Our experiments demonstrate that LLMs also struggle to summarize the semantics of complex loops, producing incorrect natural postconditions. To address this problem, we introduce a novel method, few-shot-driven k-induction , synergizing few-shot learning ( Brown et al., 2020 ) with the idea of k-induction ( Donaldson et al., 2011 ) widely used in model checking. This method starts with iteratively unwinding a loop k times to compute natural postconditions after each iteration. After that, it performs an induction inference step by prompting an LLM to compute the postcondition for the entire loop, using the computed natural Hoare triples for individual iterations as few-shot examples. Table 1 . Success rates for detecting the bug in Figure 1 via prompts with and without state annotations, using four LLMs, across 60 responses for each, with the temperature 0.5. Model Not Annotated Annotated Qwen2.5-7B 0% 11.7% Qwen2.5-Coder-32B 15% 85% Qwen2.5-72B 35% 85% Llama3.1-70B 50% 100% Figure 2 . Few-shot-driven k -induction unrolls the loop three times, computes the natural strongest postconditions (NSP) for each iteration sequentially, and uses the resulting natural Hoare triples as few-shot examples for inductively inferring the postcondition for the entire loop, which enhances precision compared to non-inductive inference, or only a single unrolling. To evaluate HoarePrompt, we created CoCoClaNeL, a dataset of program and natural language requirement pairs, where some programs meet the requirements and others do not due to human-introduced bugs. All programs and requirements were published since January 2024, after the training cut-off date of many SOTA LLMs to prevent data leakage. We formulated program correctness assessment as a binary classification problem. Our experiments show that HoarePrompt, at the expense of a higher token use, improves the Matthews Correlation Coefficient (MCC) by 61% compared to directly using Zero-shot-CoT prompts. Furthermore, HoarePrompt outperforms a classifier that assesses correctness via LLM-generated tests by increasing

Read the complete text