Guiding LLM-Based Loop Invariant Synthesis via Feedback on Local Reasoning Errors

Tianchi Li, Zhenyu Yan, Junhao Liu, Peng Di, Xin ZhangACM Transactions on Programming Languages and Systems 2026 · OpenReview

TL;DR

This paper introduces LORIS, a novel framework that guides Large Language Models (LLMs) in synthesizing loop invariants by providing fine-grained feedback on their reasoning process. By formalizing an LLM's natural language proof steps into first-order logic, LORIS can pinpoint subtle logical errors, leading to significantly improved accuracy and reliability in loop invariant synthesis.

What Problem Does This Paper Address?

Synthesizing loop invariants is a crucial but challenging task in program verification. While Large Language Models (LLMs) show promise in generating candidate invariants, they often struggle with correctness guarantees, producing erroneous solutions. Existing "guess-and-check" paradigms lack effective feedback mechanisms to guide LLMs when they fail. Specifically, when an LLM's proposed invariant is incorrect, current methods can only offer coarse-grained feedback (like "it's wrong"), which is insufficient to help the LLM refine its reasoning and correct subtle logical flaws. This paper addresses this gap by developing a system that provides detailed, constructive feedback based on the LLM's own thinking process.

Methods

LORIS employs a "guess-and-check" paradigm enhanced with a formal feedback loop.

  1. Guess: An LLM (Synthesizer LLM) generates candidate loop invariants for a given C program and assertion.
  2. Check: A formal verification tool (Frama-C) checks the inductiveness of these invariants.
  3. Feedback Generation (if check fails):
    • Structured Natural Language Proof: The Synthesizer LLM is prompted to generate a step-by-step natural language proof of its reasoning for the failed verification condition.
  4. Formalization and Checking: Another LLM (Formalizer LLM) translates these natural language reasoning steps into a series of first-order logic implications. These implications are then automatically checked by an SMT solver (Z3).
  5. Targeted Feedback: Any invalid implications identified by the SMT solver pinpoint specific logical errors in the LLM's thinking process. This precise feedback, including the context, location, and nature of the flaw, is then provided back to the Synthesizer LLM.
  6. Refinement: The Synthesizer LLM uses this feedback to refine its invariants and the process repeats until a correct set is found.

This approach focuses on local reasoning errors, which are common in LLMs, rather than attempting to verify the entire proof script, making it more robust and actionable.

Datasets

The paper evaluates LORIS on two benchmark suites:

  • Main Benchmark Suite: 460 C programs requiring numerical invariants for verification. This suite is an aggregation of problems from various sources, including Microsoft loop invariant generation experiments, Code2Inv, Accelerating Invariant Generation, LinearArbitrary-SeaHorn, and the SV-COMP repository. It primarily contains linear properties, with 313 programs from previous benchmarks.
  • Non-linear Benchmark Suite: 50 C programs that involve non-linear properties, sourced from the CLAUSE2Inv paper.

Key Insights and Ideas

  • Feedback on Reasoning is Key: Simply telling an LLM its output is wrong is ineffective. Providing feedback on why it's wrong, by analyzing its internal reasoning process, is crucial for guiding it to correct solutions.
  • Local Reasoning Errors are Common and Addressable: LLMs often make subtle logical errors in specific steps of their reasoning, rather than having a complete misunderstanding. LORIS's focus on these local errors makes its feedback highly effective.
  • Auto-formalization as a Bridge: Translating natural language reasoning into formal logic (first-order implications) provides a lightweight yet powerful way to detect logical flaws without the complexity of generating full proof scripts.
  • LLM Capabilities Matter: The effectiveness of LORIS scales with the capability of the LLM. More powerful models benefit more significantly from the structured feedback.
  • Generalizability: The core feedback mechanism is agnostic to the specific program domain and can be extended to more complex scenarios like nested loops and heap manipulation by adapting the formalization and verification backends.

Key Results

  • High Success Rate: LORIS achieved a 93.1% success rate on the main benchmark suite (445 out of 460 programs) using GPT-4.1.
  • Strong Performance on Non-linear Properties: On the challenging non-linear benchmark suite, LORIS solved 47 out of 50 programs.
  • Outperforms Baselines: LORIS consistently outperformed baseline methods (LaM4Inv and CLAUSE2INV) in the number of solved benchmarks across various LLMs.
  • Feedback is Crucial: For many problems, feedback was essential for achieving a solution, significantly boosting consistency and enabling the LLM to solve problems it would otherwise fail. Table 4 shows that for GPT-4.1, 41.2% of successful runs were "Feedback-Driven Success."
  • Constructive Refinement: The feedback mechanism leads to more accurate invariants, with an average refinement success rate of 72.9% (percentage of feedback iterations resulting in an invariant closer to the correct answer).

Limitations and Future Work

  • Global Reasoning: LORIS's feedback mechanism is highly effective for local reasoning errors but struggles with problems requiring a deep understanding of the "big picture" or global program constraints (e.g., identifying unreachable code).
  • Ineffective Refinement: In some cases, LLMs might weaken invariants instead of strengthening them when faced with preservation failures, requiring further research into guiding refinement strategies.
  • Tool Limitations: The performance can be affected by the limitations of the underlying verification tool (Frama-C) and SMT solver (Z3), especially with specific C features or complex logic.
  • Future Work:
    • Extend LORIS to handle nested/multiple loops and complex data structures/heap manipulations by adapting the logical framework (e.g., Separation Logic) and verification backends.
  • Explore generalizing the feedback paradigm to other "guess-and-check" problems like automated theorem proving.
  • Investigate more sophisticated refinement strategies to address LLMs weakening invariants.

Summary updated

BibTeX
@article{li2026guiding,
  author = {Tianchi Li and Zhenyu Yan and Junhao Liu and Peng Di and Xin Zhang},
  title = {{Guiding LLM-Based Loop Invariant Synthesis via Feedback on Local Reasoning Errors}},
  journal = {ACM Transactions on Programming Languages and Systems},
  year = {2026},
  url = {https://openreview.net/forum?id=a6cWvstMEk},
}
Figure