DecompGym: Benchmarking LLM Agents on Designing Decomposition Algorithms
Abstract
Benders decomposition and column generation solve large optimization problems by passing cuts, columns, and dual values between a master problem and subproblems, and are hard to implement correctly. Large language models now automate parts of algorithm design, which points toward agents that build decomposition solvers for new problems. As a first step toward such agents, we study how well current coding agents design and implement these two algorithms, and how they fail. We introduce DecompGym, 81 instances from nine problem families (five Benders, four column generation), in which an agent writes a solver for a prescribed method. Each solver must meet three criteria: execution within a 60-second time limit; numerical feasibility together with a method audit, in which an LLM judge reads the solver's code; and an objective within 1% of the stored optimal objective. We evaluate 12 GPT, Claude, and Gemini models running in coding-agent tools. Over up to ten attempts, we compare independent regeneration with reflection, which first diagnoses the failure. On the first attempt, two models solve every instance and seven solve more than 90%. Most Benders failures (48 of 62) are missing or suboptimal solutions. The most common column-generation failure is a method-audit rejection. Output checks alone would accept 93 of the 108 attempts that fail the method audit. The most common rejection, an optimalif, occurs 96 times, 92 of them in one model.Reflection turns 66% of retries into successes, compared with 39% for regeneration, and it repairs method-audit failures, for which the judge names the defecective gaps. Agents for decomposition therefore need checks on how a solver reaches its answer and feedback that locates the error. The benchmark is available at https://github.com/SIKAI-C/DecompGym.
Related
- Modified Decomposition Algorithms for Fractional Delay Boundary Value Problems
- Benchmarking Bilevel Derivative-Free Optimization Algorithms
- Recursive Multilevel Decomposition of Pairwise Comparison Matrices: Algorithms and Inconsistency Diagnostics
- Benchmarking Goodness-of-Fit and Calibration Algorithms for Logistic Regression Classifiers: A Large-Scale Simulation Study under Sparse Data
- Order-Specified Quaternion CP Decomposition: Models, Algorithms, and Applications
BibTeX
@misc{cheng2026decompgym,
title = {{DecompGym: Benchmarking LLM Agents on Designing Decomposition Algorithms}},
author = {Sikai Cheng and Tinghan Ye and Arnaud Deza and Xiaonan Qi and Miao Li and Litong Liu and Changkun Guan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38175},
eprint = {2610.38175},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38175},
}
RIS
TY - UNPB
TI - DecompGym: Benchmarking LLM Agents on Designing Decomposition Algorithms
AU - Sikai Cheng
AU - Tinghan Ye
AU - Arnaud Deza
AU - Xiaonan Qi
AU - Miao Li
AU - Litong Liu
AU - Changkun Guan
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38175
UR - https://arxiv.org/abs/2610.38175
AB - Benders decomposition and column generation solve large optimization problems by passing cuts, columns, and dual values between a master problem and subproblems, and are hard to implement correctly. Large language models now automate parts of algorithm design, which points toward agents that build decomposition solvers for new problems. As a first step toward such agents, we study how well current coding agents design and implement these two algorithms, and how they fail. We introduce DecompGym, 81 instances from nine problem families (five Benders, four column generation), in which an agent writes a solver for a prescribed method. Each solver must meet three criteria: execution within a 60-second time limit; numerical feasibility together with a method audit, in which an LLM judge reads the solver's code; and an objective within 1% of the stored optimal objective. We evaluate 12 GPT, Claude, and Gemini models running in coding-agent tools. Over up to ten attempts, we compare independent regeneration with reflection, which first diagnoses the failure. On the first attempt, two models solve every instance and seven solve more than 90%. Most Benders failures (48 of 62) are missing or suboptimal solutions. The most common column-generation failure is a method-audit rejection. Output checks alone would accept 93 of the 108 attempts that fail the method audit. The most common rejection, an optimalif, occurs 96 times, 92 of them in one model.Reflection turns 66% of retries into successes, compared with 39% for regeneration, and it repairs method-audit failures, for which the judge names the defecective gaps. Agents for decomposition therefore need checks on how a solver reaches its answer and feedback that locates the error. The benchmark is available at https://github.com/SIKAI-C/DecompGym.
ER -