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

摘要

Large language models (LLMs) can translate natural language into optimization code, but *silent failures* pose a critical risk: code that executes and returns solver-feasible solutions may encode semantically incorrect formulations—a feasibility–correctness gap reaching 90 percentage points on compositional problems. We introduce **ReLoop**, which addresses this gap through two complementary mechanisms. *Structured generation* decomposes code production into a four-stage reasoning chain (understand, formalize, synthesize, verify), preventing formulation errors at their source. *Behavioral verification* detects errors that survive generation by testing whether the formulation responds correctly to solver-based parameter perturbation—an external semantic signal that bypasses LLM self-review and requires no ground truth. The two mechanisms are complementary by error structure: structured generation drives the largest gains on compositional problems (**+8.5pp** accuracy on RetailOpt-190 with Claude Opus 4.6), while behavioral verification dominates on localized defects (**+4.4pp** on MAMO-ComplexLP, its largest contribution across benchmarks). Combined with diagnostic execution recovery, ReLoop reaches **100% executable code** on Claude Opus 4.6 and consistently improves accuracy on chat-tuned foundation models across three benchmarks; we further identify a known limitation of narrowly-tuned SFT models, whose learned output formats are brittle to chain-of-thought prompts—an interaction we document and analyze. We release **RetailOpt-190**, 190 compositional retail optimization scenarios targeting the multi-constraint interactions where LLMs most frequently fail. Code and benchmark will be released upon acceptance.