Abstract:Large language models can generate plausible code, but remain brittle for formal verification in proof assistants such as Lean. A central scalability challenge is that verified synthesis requires consistent artifacts across several coupled domains: executable code, formal specifications, theorem statements, and proof attempts. Existing approaches often treat these artifacts separately. We present BRIDGE, a structured prompting framework for multi-artifact program synthesis. BRIDGE decomposes generation into three interconnected domains: Code, Specification, and Theorem/Proof, and uses domain-specific intermediate reasoning to connect them. In Lean, BRIDGE often follows a code-first workflow, using the generated implementation as a semantic anchor for downstream specification, theorem statement, and proof-attempt generation. Across 178 algorithmic problems and five LLMs, BRIDGE improves Lean executable correctness by up to nearly 1.5x over direct prompting and can be roughly 2x more sample efficient at comparable generation lengths. We further find that specification-oriented prompting improves Python pass rates by up to 17.5 percentage points. Beyond inference-time prompting, supervised fine-tuning on BRIDGE-style reasoning traces yields nearly 1.5x higher Lean pass success than code-only fine-tuning, suggesting that these intermediate representations provide a learnable inductive bias. BRIDGE provides a practical framework for scaling verified synthesis while highlighting the remaining gap between executable correctness and full formal proof generation.
| Comments: | 41 pages, 10 figures, 3 tables. Preprint |
| Subjects: | Machine Learning (cs.LG); Programming Languages (cs.PL) |
| MSC classes: | 68N30, 68Q55, 68T07 |
| ACM classes: | F.3.1; D.2.4; I.2.3 |
| Cite as: | arXiv:2511.21104 [cs.LG] |
| (or arXiv:2511.21104v4 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2511.21104 arXiv-issued DOI via DataCite |
From: Robert Joseph George [view email]
[v1]
Wed, 26 Nov 2025 06:39:19 UTC (955 KB)
[v2]
Wed, 25 Feb 2026 16:45:04 UTC (820 KB)
[v3]
Sun, 10 May 2026 18:08:18 UTC (2,487 KB)
[v4]
Thu, 14 May 2026 05:18:06 UTC (2,487 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。