ReLoop: Structured Modeling and Behavioral Verification for Reliable LLM-Based Optimization

Junbo Jacob Lian, Yujun Sun, Huiling Chen, Chaoyu Zhang, Chung-Piaw TeoarXiv 2026 · DOI

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:

  1. Structured Generation: This method decomposes the LLM's code generation process into a four-stage chain-of-thought prompt:
  2. Understand: Extract the problem's objective, variables, constraints, and parameters.
  3. Formalize: Create a mathematical specification, explicitly deciding variable types (continuous, integer, binary) based on context.
  4. Synthesize: Generate executable code (e.g., GurobiPy) from the specification, ensuring data access is structured for later perturbation.
  5. Verify Completeness: A self-check within the generation process to catch formulation errors before external verification.
  6. Behavioral Verification: This layer detects errors that slip through structured generation. It uses two sub-layers:
  7. L1: Execution Verification: Checks for syntax errors, runtime completion, solver status (infeasibility, unboundedness), and duality gaps. Fatal errors trigger regeneration with diagnostic feedback.
  8. 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

BibTeX
@misc{lian2026reloop,
  author = {Junbo Jacob Lian and Yujun Sun and Huiling Chen and Chaoyu Zhang and Chung-Piaw Teo},
  title = {{ReLoop: Structured Modeling and Behavioral Verification for Reliable LLM-Based Optimization}},
  year = {2026},
  eprint = {2602.15983},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.15983},
}
Figure