GraphAlignCoder: Aligning Program and Proof Graphs for Code Generation

A training framework that transfers explicit correctness structure from formal proof traces into code LLMs, outperforming CodeRL by up to 43.8% relative on hard benchmarks.

Yueke Zhang; Zihan Fang; Kevin Leach; Yu Huang· 2026· DOI 10.48550/arXiv.2608.11394

The core problem

Code large language models (LLMs) can generate syntactically plausible programs that nevertheless violate hidden semantic constraints. Existing execution-feedback training methods identify whether a completed program fails, but provide limited supervision about how a correct solution should be organized. This gap motivates GraphAlignCoder, a training framework that transfers explicit correctness structure into code generation. Rather than relying solely on binary pass/fail execution signals, GraphAlignCoder constructs an implementation graph that captures control and dependence among program regions. In parallel, a constrained Lean pipeline produces proof traces, from which the authors extract a formal proof-flow graph. The central hypothesis is that aligning these two graphs gives the model richer, region-level supervision about *why* a program is correct, not merely *whether* it is correct. The work is positioned against base models, code-only supervised fine-tuning (SFT), and CodeRL, and is evaluated on LiveCodeBench v6, BigCodeBench Hard, and BigCodeBench Full.

GraphAlignCoder consistently outperforms the base model, code-only SFT, and CodeRL across all benchmarks. Compared with CodeRL, it increases the solved count from 38 to 50 on LiveCodeBench v6 and from 16 to 23 on BigCodeBench Hard, corresponding to relative gains of 31.6% and 43.8%. On BigCodeBench Full, it improves from 359 to 363 tasks. These numbers indicate that the largest relative benefit appears on the hardest benchmark, where hidden semantic constraints are most likely to defeat execution-feedback-only training. The consistent direction of improvement across three benchmarks of differing difficulty suggests the gains are not an artifact of a single evaluation set. The reported deltas are summarized below. | Benchmark | CodeRL | GraphAlignCoder | Relative Gain | |---|---|---|---| | LiveCodeBench v6 | 38 | 50 | 31.6% | | BigCodeBench Hard | 16 | 23 | 43.8% | | BigCodeBench Full | 359 | 363 | ~1.1% | The pattern is consistent with the claim that region-level correctness structure provides supervision that binary execution feedback cannot supply.

Code large language models (LLMs) can generate syntactically plausible programs that nevertheless violate hidden semantic constraints. Existing execution-feedback training methods identify whether a completed program fails, but provide limited supervision about how a correct solution should be organized. This gap motivates GraphAlignCoder, a training framework that transfers explicit correctness structure into code generation. Rather than relying solely on binary pass/fail execution signals, GraphAlignCoder constructs an implementation graph that captures control and dependence among program regions. In parallel, a constrained Lean pipeline produces proof traces, from which the authors extract a formal proof-flow graph. The central hypothesis is that aligning these two graphs gives the model richer, region-level supervision about *why* a program is correct, not merely *whether* it is correct. The work is positioned against base models, code-only supervised fine-tuning (SFT), and CodeRL, and is evaluated on LiveCodeBench v6, BigCodeBench Hard, and BigCodeBench Full.

GraphAlignCoder operates in two stages. First, it constructs an **implementation graph** G_{impl} = (V_{impl}, E_{impl}) where nodes represent program regions and edges encode control-flow and data-dependence relations among them. Second, a constrained Lean pipeline produces proof traces for candidate solutions; from these traces the framework extracts a **formal proof-flow graph** G_{proof} = (V_{proof}, E_{proof}) whose nodes correspond to proof obligations and whose edges capture logical dependency.

The ablation study further shows that verification-graph injection produces the initial reasoning gain, while verification-to-code consolidation is essential for robust cross-benchmark transfer. This decomposition is important: it implies that merely exposing the model to proof structure yields a local improvement, but that the durable, transferable benefit comes from the second stage that consolidates verification knowledge back into the code generator. The relatively modest gain on BigCodeBench Full (359 to 363) alongside the large gain on BigCodeBench Hard (16 to 23) suggests that the method's advantage concentrates on tasks where semantic constraints are the binding difficulty rather than on tasks already largely solved. A limitation is that the approach depends on a constrained Lean pipeline to produce proof traces, which may restrict applicability to domains where formalization is feasible. The taxonomy candidates listed for this work—Architecture, Cybersecurity, Network, and Cryptography—are plausible downstream domains, since each involves hidden semantic constraints (protocol invariants, access-control rules, cryptographic correctness) that execution feedback alone may not expose. Future work could examine whether the implementation-graph and proof-flow-graph alignment generalizes to non-Lean proof assistants and to larger model scales.

CS practitioners and researchers

Opening member content…