TL;DR
Large Language Models (LLMs) can generate optimization code from natural language, but often produce "silent failures" – code that runs but is semantically incorrect. This paper introduces ReLoop, a system that uses structured generation and behavioral verification to significantly improve the reliability of LLM-generated optimization code, achieving near-perfect execution and substantial accuracy gains.
What Problem Does This Paper Address?
LLMs are increasingly used to translate natural language descriptions into optimization models. However, a critical issue is "silent failures": the generated code executes without errors and returns a solver-feasible solution, yet it encodes a semantically incorrect formulation. This can lead to drastically wrong decisions in real-world applications. Existing verification methods struggle to detect these failures because they rely on ground truth (unavailable for novel problems), LLM self-critique (which inherits the LLM's own reasoning flaws), or simple execution feedback (which can't distinguish correct from feasible-but-wrong). The paper highlights a massive gap, with up to 90 percentage points difference between solver-feasibility and formulation correctness on complex problems.
Methods
ReLoop tackles this problem with a two-pronged approach:
- Structured Generation: This method decomposes the LLM's code generation process into a four-stage chain-of-thought prompt:
- Understand: Extract the problem's objective, variables, constraints, and parameters.
- Formalize: Create a mathematical specification, explicitly deciding variable types (continuous, integer, binary) based on context.
- Synthesize: Generate executable code (e.g., GurobiPy) from the specification, ensuring data access is structured for later perturbation.
- Verify Completeness: A self-check within the generation process to catch formulation errors before external verification.
- Behavioral Verification: This layer detects errors that slip through structured generation. It uses two sub-layers:
- L1: Execution Verification: Checks for syntax errors, runtime completion, solver status (infeasibility, unboundedness), and duality gaps. Fatal errors trigger regeneration with diagnostic feedback.
- L2: Behavioral Testing (CPT + OPT): This is the core novelty. It tests whether the generated formulation behaves as expected under parameter perturbations. By slightly altering parameters (e.g., reducing capacity to near-zero, increasing demand), ReLoop checks if constraints bind and objective terms change as they should. This external, solver-based signal bypasses LLM self-review limitations. If a perturbation doesn't cause the expected change, it signals a likely missing component.
ReLoop also incorporates Diagnosis-Guided Repair, where identified issues trigger targeted regeneration or rollback mechanisms, with safety guards to prevent regressions.
Datasets
The paper introduces RetailOpt-190, a new benchmark consisting of 190 compositional retail inventory optimization scenarios. These scenarios are designed to stress-test LLMs on multi-constraint interactions where they frequently fail. The benchmark spans eight scenario families, progressively increasing in complexity and compositional reasoning requirements. Existing benchmarks like MAMO-ComplexLP and IndustryOR were also used for cross-benchmark generalization evaluation.
Key Insights and Ideas
- Silent failures are a critical, pervasive problem: The 90-point gap between feasibility and correctness highlights the inadequacy of current LLM evaluation for optimization tasks.
- Behavioral invariants are key to verification: Correct optimization models exhibit predictable behavior under parameter changes. This insight allows for verification without ground truth.
- Structured generation prevents errors at the source: Decomposing the modeling process into expert-like stages significantly reduces formulation errors.
- External signals are crucial for verification: LLMs struggle to self-correct reasoning flaws. Solver-based perturbation provides an independent semantic signal that LLMs cannot ignore.
- Structured generation and behavioral verification are complementary: Each method excels at different types of errors (compositional vs. localized), making their combination powerful.
Key Results
- ReLoop achieves 100% executable code on Claude Opus 4.6.
- On RetailOpt-190, ReLoop significantly improves accuracy: Claude Opus 4.6 sees an +8.5pp accuracy gain from structured generation alone, and ReLoop as a whole achieves 31.1% accuracy (strict, €=10⁻⁴).
- Behavioral verification (L2) provides the largest gains on problems with localized defects, contributing +4.4pp accuracy on MAMO-ComplexLP for Claude Opus 4.6.
- ReLoop consistently improves accuracy across foundation models and benchmarks, demonstrating generalization.
- The paper identifies a limitation of narrowly-tuned SFT models whose output formats are brittle to chain-of-thought prompts.
Limitations and Future Work
- CoT incompatibility with SFT models: Structured generation can disrupt the learned patterns of some fine-tuned models, leading to crashes.
- LLM for constraint extraction: L2 relies on the same LLM for constraint extraction as for code generation, creating a potential for correlated failures.
- Three failure modes beyond scope: Coefficient magnitude errors, formulation equivalence errors, and unrepresented problem structures are not addressed.
- Future work: The authors suggest exploring cross-model verification for L2, and further investigating LLM limitations in handling complex optimization structures.
Summary updated