A new preprint reports that an artificial-intelligence pipeline correctly classified all 54 tested pairs of mixed-integer linear programming reformulations while producing machine-checkable certificates. The pipeline, called FLARE, combines a language model with Lean-based automated theorem proving, which checks whether a mathematical statement follows from formally written rules.
A companion version called FLARE-NL reached the same 100% benchmark accuracy but produced no formal certificate. The authors report that it ran 30 times faster and cost 25 times less than FLARE, presenting it as a rapid screening tool rather than a proof method.
What the system was checking
The task concerns reformulations: different mathematical versions of an optimization model. The study uses a constructive definition that requires explicit forward and backward mappings between the two feasible regions, preservation of the ordering of objective values, and a strictly increasing transformation of the objective. In practical terms, the test asks whether one formulation can be converted into the other while preserving the relevant optimization structure.
FLARE first converts the formulations and a fixed parameter map into Lean. It then attempts to generate a theorem-proving certificate and checks whether a reformulation certificate was produced. FLARE-NL instead presents the definition, assumptions, reasoning and a structured answer to a language model, without a verifiable guarantee.
The full FormulationBench benchmark contains 20 optimization problems, 109 mixed-integer linear programming formulations and 89 formulation pairs, including 63 positive and 26 negative examples. The main evaluation narrowed that material to 54 pairs from 16 NP-hard problems: 42 positive pairs and 12 negative pairs.
A strong result with a sharp distinction
On that main subset, FLARE and FLARE-NL both recorded 100% accuracy. The difference was what counted as evidence. FLARE was the only method that produced machine-checkable reformulation certificates, whereas FLARE-NL supplied a classification but no certificate.
The comparison methods were less consistent. An execution-based objective comparison recorded 83.3% accuracy, while EquivaMap recorded 81.5%. In the breakdown by transformation category, FLARE and FLARE-NL were the only methods with 100% worst-case accuracy; both comparison methods had 0% worst-case accuracy.
During benchmark preparation, FLARE failed to generate certificates for five cutting planes and four formulations, and manual inspection confirmed that those cases were invalid. But a missing certificate alone is not a definitive diagnosis: failure to generate one is inconclusive under the study's framework.
The result depends on the formalization
The formal guarantee is conditional. A Lean-verified certificate proves the reformulation claim under the constructive definition only if the original formulations and the parameter map were formalized faithfully. Conversely, failure to generate a certificate does not by itself prove that a reformulation is invalid or rule out another parameter mapping.
The paper reports that all 109 Lean formalizations were reviewed line by line by an operations-research PhD student, who found no autoformalization errors. Even with that review, the formal guarantee remains conditional on faithful formalization of the formulations and parameter map.
Performance also varied with the model and software harness surrounding FLARE. Claude Code with Opus 5 reached 100.0% accuracy, compared with 98.1% for Codex with GPT-5.6 Sol and 79.6% for OpenCode with DeepSeek V4 Pro. Across those configurations, 11 false negatives were attributed to automated theorem-proving failure, including eight linked to timeouts.
Prompt design mattered for the natural-language proxy. Across model families, the complete FLARE-NL prompt performed best. Removing the reformulation definition consistently reduced accuracy, while allowing implicit assumptions was associated with the largest degradation.
What the benchmark cannot settle
For readers assessing language models that generate optimization models, the distinction is central: FLARE offers formal certificates under stated conditions, while FLARE-NL offers faster screening without a formal guarantee. Its perfect benchmark score should not be read as proof that the proxy is formally correct.
The evaluation remains a computational benchmark result, not a universal test of automated reformulation checking. The main test used 54 pairs from 16 NP-hard problems, and the analysis does not establish scalability to larger industrial formulations. No inferential statistical testing or confidence intervals were reported.
The Lean proof obligation also omits the requirement that the backward mapping be computable in polynomial time, although the authors report that the backward map was polynomial-time computable in each construction they tested. The constructive definition may also reject weaker reformulations that preserve only optimal solutions because it requires mappings over the entire feasible region.
A preprint with public implementation details
The manuscript is a preprint identified as arXiv:2608.25220v1 and dated 25 August 2026. It states that FLARE is implemented in the milp-flare Python package, FormulationBench is available through the formulation-bench Python package, and the experimental code is available on GitHub.
Paper data and sources
Original title: FLARE: Verifying MILP Reformulations with LLM-Based Theorem Proving
Authors: Henry Robbins, Connor Lawless, Madeleine Udell, Ellen Vitercik
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text