# Falsification-Based Verification of LLM-Generated Optimization Models: Sound Test Batteries and Their Detection Limits

arXiv: https://arxiv.org/abs/2607.16646 · HTML: https://mlsanity.com/paper/2607.16646/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 36 references that are in the map.
- First posted on arXiv 18 Jul 2026.

## Builds on (most cited first, 22 of 22)

- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions](https://mlsanity.com/paper/2303.08233/) (2023)
- [ORLM: A Customizable Framework in Training Large Models for Automated Optimization Modeling](https://mlsanity.com/paper/2405.17743/) (2024)
- [LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch](https://mlsanity.com/paper/2410.13213/) (2024)
- [OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling](https://mlsanity.com/paper/2407.09887/) (2024)
- [OptMATH: A Scalable Bidirectional Data Synthesis Framework for Optimization Modeling](https://mlsanity.com/paper/2502.11102/) (2025)
- [Solver-Informed RL: Grounding Large Language Models for Authentic Optimization Modeling](https://mlsanity.com/paper/2505.11792/) (2025)
- [Optimization with Constraint Learning: A Framework and Survey](https://mlsanity.com/paper/2110.02121/) (2021)
- [ORGEval: Graph-Theoretic Evaluation of LLMs in Optimization Modeling](https://mlsanity.com/paper/2510.27610/) (2025)
- [ReLoop: Structured Modeling and Behavioral Verification for Reliable LLM-Based Optimization](https://mlsanity.com/paper/2602.15983/) (2026)
- [ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization](https://mlsanity.com/paper/2602.22465/) (2026)
- [Validating LLM-Generated Programs with Metamorphic Prompt Testing](https://mlsanity.com/paper/2406.06864/) (2024)
- [Opt-Verifier: Unleashing the Power of LLMs for Optimization Modeling via Dual-Side Verification](https://mlsanity.com/paper/2605.29556/) (2026)
- [Strategy-Aware Optimization Modeling with Reasoning LLMs](https://mlsanity.com/paper/2605.02545/) (2026)
- [Metamorphic Relation Generation: State of the Art and Visions for Future Research](https://mlsanity.com/paper/2406.05397/) (2024)
- [An Agent-Based Framework for the Automatic Validation of Mathematical Optimization Models](https://mlsanity.com/paper/2511.16383/) (2025)
- [OptArgus: A Multi-Agent System to Detect Hallucinations in LLM-based Optimization Modeling](https://mlsanity.com/paper/2605.11738/) (2026)
- [Execution-Verified Reinforcement Learning for Optimization Modeling](https://mlsanity.com/paper/2604.00442/) (2026)
- [TriVAL: A Tri-Validation Framework for Faithful Automatic Optimization Modeling](https://mlsanity.com/paper/2605.23966/) (2026)
- [OptiLoop: Coordination-in-the-Loop Verification and Repair for LLM-Generated Optimization Agents](https://mlsanity.com/paper/2605.27630/) (2026)
- [Beyond Objective Equivalence: Constraint Injection for LLM-Based Optimization Modeling on Vehicle Routing Problems](https://mlsanity.com/paper/2606.04816/) (2026)
- [MiniOpt: Reasoning to Model and Solve General Optimization Problems with Limited Resources](https://mlsanity.com/paper/2606.25832/) (2026)

## Built on by (most cited first, 1 of 1)

- [Admission Without Answers: Label-Free Certification and Experience Learning for LLM-Based Optimization Modeling](https://mlsanity.com/paper/2608.15565/) (2026)

## Abstract (arXiv)

Large language models now translate natural-language descriptions of decision problems into solver-ready optimization models, and they fail silently. A generated model often runs and still encodes the wrong problem, while standard evaluation compares optimal values against labeled answers that deployment does not provide. How to certify such a model without any reference is the question this paper addresses. We develop falsification-based verification. Every numeric quantity in a problem description plays a role that the text itself states, such as a capacity, a requirement, or a unit cost, and any correct model must respond to changes in these quantities as the stated roles dictate. From duality and sensitivity analysis we derive a battery of solver-based tests that are individually sound, so a violation certifies a faulty model and the false-positive rate is zero by design. We characterize the errors that no test of this kind can see, give conditions under which each canonical error class is detected with certainty, and prove that perturbation testers with tuned thresholds cannot be simultaneously sound and nontrivial. Across 326 ground-truth models, a synthetic family, and four public benchmarks with two generators, the battery flags 0.0% of faithful models while a threshold tester flags 54.9%; it detects 56.1% of core formulation errors, 70.0% under certified preconditions, and 40.4% of the errors that value-based scoring provably cannot see, and it reproduces the predicted detectability pattern including its blind spots. Every flag carries a machine-checkable certificate that localizes the defect, and a full audit costs about 25 millisecond-scale solver calls per model. Classical sensitivity analysis and duality thus offer a rigorous, label-free audit that complements existing evaluation of AI-generated optimization models.