Training Method Aligns Formal Proofs with Code to Improve LLM-Generated Solutions

Researchers have introduced GraphAlignCoder, a training approach that strengthens code generation by embedding formal verification logic into large language model learning. The method addresses a persistent challenge: LLMs can produce syntactically valid code that still contains logical errors or violates implicit constraints.

How It Works#

GraphAlignCoder combines two graph structures during training. First, an implementation graph maps the control flow and data dependencies within a program. Second, a proof-flow graph is derived from formal proof traces generated by Lean, a theorem-proving framework. By extracting the reasoning steps that justify why different program sections are correct, the approach gives models explicit guidance about proper solution structure.

The training process unfolds in two stages: the model initially learns to generate executable code while also learning graph-based explanations of correctness for each program region, then transfers that understanding into improved code generation.

Benchmark Performance#

Testing across multiple evaluation suites shows consistent gains over existing baselines:

• LiveCodeBench v6: improved from 38 to 50 solved problems (a 31.6% relative increase over CodeRL)
• BigCodeBench Hard: 16 to 23 problems solved (43.8% relative improvement)
• BigCodeBench Full: 359 to 363 tasks completed

The method outperformed both a code-only fine-tuning approach and CodeRL, an execution-feedback training baseline.

What Sets It Apart#

Earlier execution-feedback methods can detect when a program fails, but they offer limited information about how correct solutions should be organized. By grounding the training in formal proof structures—which capture the deep reasoning behind correctness—GraphAlignCoder provides richer supervision that helps models generalize better across different problems and domains. Ablation studies confirmed that injecting verification-graph information yields initial improvements, while consolidating that verified reasoning back into code generation is crucial for robust performance transfer.