DecompGym: Benchmarking LLM Agents on Designing Decomposition Algorithms

Large Language Models (LLMs) struggle to solve complex combinatorial problems through direct reasoning, so recent neuro-symbolic systems increasingly use them to synthesize executable solvers. A central design question is how the LLM should represent the solver, and whether it should also attempt to optimize search. We introduce CP-SynC-XL, a benchmark of 100 combinatorial problems (4,577 instances), and evaluate three solver-construction paradigms: native algorithmic search (Python), constraint modeling through a Python solver API (Python + OR-Tools), and declarative constraint modeling (MiniZinc + OR-Tools). We find a consistent representational divergence: Python + OR-Tools attains the highest correctness across LLMs, while MiniZinc + OR-Tools has lower absolute coverage despite using the same OR-Tools back-end. Native Python is the most likely to return a schema-valid solution that fails verification, whereas solver-backed paths preserve higher conditional fidelity. On the heuristic axis, prompting for search optimization yields only small median speed-ups (1.03-1.12x) and a strongly bimodal effect: many instances slow down, and correctness drops sharply on a long tail of problems. A paired code-level audit traces these regressions to a recurring heuristic trap. Under an efficiency-oriented prompt, the LLM may replace complete search with local approximations (Python), inject unverified bounds (Python + OR-Tools), or add redundant declarative machinery that overwhelms or over-constrains the model (MiniZinc + OR-Tools). These findings support a conservative design principle for LLM-generated combinatorial solvers: use the LLM primarily to formalize variables, constraints, and objectives for verified solvers, and separately check any LLM-authored search optimization before use.

LLM-based agents are increasingly deployed to solve optimization problems, yet existing benchmarks evaluate them on pre-structured mathematical formulations that bypass the most critical challenge: translating complex business requirements into correct models and solve efficiently. We introduce Opti-Agent-Bench, an end-to-end benchmark that evaluates Large Language Models (LLMs) across the complete optimization R&D pipeline, from understanding business-language descriptions through mathematical modeling, algorithm selection, and code implementation, to solution report generation. Our design rests on three pillars: (1) businesssemantic authenticity with anti-template traps that defeat pattern matching; (2) modular evaluation with cross-module consistency checking across Problem Understanding, Formal Modeling, Implementation, and Reporting; and (3) the ORAC bi-level validity framework that simultaneously ensures task quality and scoring integrity. Across several industrialscale tasks spanning integer programming, robust optimization, stochastic programming, and non-convex optimization, we expose critical failure modes of current models, including constraint omission, model-code inconsistency, and report-implementation divergence, that remain invisible under conventional single-metric evaluation.

Many optimization problems are solved repeatedly on instances drawn from the same underlying distribution. In this setting, a system can begin with a general-purpose solver and use experience from previous instances to learn a cheaper way to solve future ones. We formalize this as distribution-aware programming: samples from an unknown deployment distribution are used to produce executable solver code whose quality and runtime generalize to new instances. A simple analysis shows how sample access interpolates between distribution-oblivious and distribution-informed algorithm design, and when the offline cost of specialization is recovered through lower deployment cost. We instantiate this framework with an LLM agent that proposes structural hypotheses, analyzes training instances, and synthesizes specialized solver code; the LLM is used only before deployment. Across $21$ structured combinatorial-optimization distributions, the synthesized solvers achieve high quality while often replacing generic search or optimization with smaller distribution-specific computations. Against released PACE competition solvers, our method remains competitive while using substantially less runtime: $75$--$125\times$ less on PACE 2025 Dominating Set, $80$--$96\times$ less on Hitting Set, and more than $34{,}000\times$ less on the PACE 2024 OCM exact track. More broadly, the results suggest using AI not only to solve optimization problems, but to learn how recurring distributions should be solved.