PaperlayerView exact revision on arXiv

Source-linked AI summary

DecompGym: Benchmarking LLM Agents on Designing Decomposition Algorithms

Sikai Cheng, Tinghan Ye, Arnaud Deza, Xiaonan Qi, Miao Li, Litong Liu, Changkun Guan

arXiv:2610.38175v1cs.AImath.OC

TL;DR

Coding agents must implement decomposition methods whose interacting master problems, subproblems, and stopping rules are difficult to get right. DecompGym tests prescribed Benders and column-generation solvers, finding that many first attempts succeed but output checks miss method failures; reflection more often repairs retries than regeneration.

  • Problem

    Benders and column-generation solvers are difficult to implement correctly because their master–subproblem information flow and stopping rules must support what the final solution certifies.

    Source: §1 · p. 2

  • Method

    DecompGym evaluates 12 coding-agent models on 81 instances from nine problem families, checking execution, numerical feasibility and method conformance, and objective quality across up to ten attempts.

    Source: §1 · p. 2

  • Results

    87.8% of first attempts succeed, but 93 of 108 method-audit rejections pass every output check, while reflection turns 66% of retries into successes versus 39% for regeneration.

    Source: §1.1 · p. 2, §6 · p. 11

  • Takeaways & Limitations

    Decomposition agents need checks on how solvers reach answers and feedback that locates errors, such as bounds or gaps reported at termination.

    Source: §6 · p. 12

    The study uses moderate-size synthetic instances with prescribed decompositions, and does not test scaling to larger instances.

    Source: §6 · p. 11

Abstract

from arXiv · show

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.

1 Introduction

The paper examines whether coding agents can correctly implement prescribed Benders and column-generation methods, and how they fail. DecompGym evaluates these solvers on execution, feasibility and method conformance, and objective quality; the results motivate checks on how an answer is reached and feedback that locates errors.

1 Introduction

  • Benders fixes complicating decisions in a master and adds subproblem cuts, while column generation adds priced columns using master dual values; both are difficult to implement correctly.Formulations, information passed between master and subproblems, and stopping rules must align with what the final solution certifies.Source: §1 · p. 2
  • DecompGym tests 81 instances across nine problem families, with execution, numerical feasibility and an LLM method audit, and objective-within-1% checks.Agents receive a prescribed method contract and write a standalone solver; the paired retry protocol compares independent regeneration with reflection.Source: §1 · p. 2

1.1 Main findings

  • Among first attempts, 87.8% met all three criteria; GPT-6 Astra and GPT-6.1 Sol passed every instance, and seven models exceeded 90% first-attempt success.Most Benders failures (48 of 62) involved missing or suboptimal solutions; the most common column-generation failure was method-audit rejection, in 26 of 57 failed first attempts.Source: §1.1 · p. 2
  • 93 of 108 method-audit rejections passed every output check, so output-only evaluation would credit solvers that failed to follow or prove the prescribed method.Of these 108 rejections, 96 claimed optimality without proof; Claude Sonnet 5 produced 92.Source: §1.1 · pp. 2–3
  • Reflection turns 66% of retries into successes, compared with 39% for regeneration, and has 5 method-audit rejections versus 64 under regeneration.After method-audit rejection, reflection's next attempt met all three criteria in 41 of 44 cases; objective-gap feedback was less informative.Source: §1.1 · p. 3, §1.2 · p. 3

1.2 Implications for decomposition agents

  • Decomposition agents need checks on how a solver reaches its answer and feedback that locates errors, such as reported bounds or termination gaps.The judge's rationale can locate method-audit failures, whereas objective-gap feedback only reports that the target is unmet.Source: §1.2 · p. 3

2 Related Work

Prior optimization benchmarks commonly evaluate models, solver components, or chosen algorithms through their outputs or performance. DecompGym instead prescribes a decomposition method and audits whether the solver code implements it.

Optimization modeling benchmarks

  • Optimization-modeling benchmarks use general-purpose solvers, so they test formulation rather than whether an agent implements an algorithm.These benchmarks compare objectives or statuses with references; output alone decides success.Source: §2 · p. 3

Agents that write optimization algorithms and solver code

  • DecompGym prescribes a decomposition and checks solver code against it, addressing a gap in benchmarks where agents choose the method and output or performance determines success.PaperBench and ResearchCodeBench prescribe methods for machine-learning research code, but DecompGym brings that evaluation approach to optimization algorithms.Source: §2 · p. 3

Decomposition methods and their automation

  • Existing decomposition tools automate parts of the process when users supply or solvers detect model structure, whereas DecompGym agents write the master, subproblems, and coordination.Learned models also decide whether to decompose or which columns to add, but those tools use fixed implementations.Source: §2 · pp. 3–4

Specification conformance, false success, and judge validity

  • Prior coding-agent studies show that passing tests can fail to establish specification conformance, while DecompGym measures missed method failures on ordinary tasks using a source-code judge.LLM judges can exhibit position, verbosity, and self-preference biases; the DecompGym judge reads solver source, closer to code-level cheating assessments.Source: §2 · p. 4

Reflection and repair

  • Reflection's benefit depends on feedback source and cost accounting; DecompGym compares it with regeneration from the same first attempt and records attempts, time, and tokens.Reflection receives execution and method-audit feedback, while regeneration repeats sampling with the benchmark evaluation as verifier.Source: §2 · p. 4

3 The DecompGym Benchmark

DecompGym asks coding agents to write solvers for prescribed decomposition methods across nine optimization problem families. Its instances and contracts are designed to assess correct implementation within a shared time limit.

3 The DecompGym Benchmark

  • Each task supplies an application description, structured instance data, a prescribed method family, and an output contract; the agent writes all solver code in Python.Permitted libraries are Gurobi's Python interface, NumPy, and the Python standard library.Source: §3 · p. 4
  • DecompGym comprises 81 moderate-dimension instances across nine families: 45 Benders and 36 column-generation instances, each family instantiated at three size levels with three seeds.The families cover facility location, transportation, routing, stochastic planning, packing, assignment, and scheduling.Source: §3 · p. 4
  • The method contract requires consistent master–subproblem information flow and decisions, prohibits monolithic solves, and requires an optimal label only when optimality is proved.Benders must return feasibility or optimality cuts; column generation must pass restricted-master dual information to pricing and reuse resulting columns.Source: §3 · p. 5

4 Evaluation Protocol

The evaluation scores each solver through ordered execution, verification, and quality criteria, with method conformance assessed by a judge reading source code. Retry policies share a first attempt, and the protocol records attempt counts and costs.

4 Evaluation Protocol

  • The study evaluates five GPT models through Codex, six Claude models through Claude Code, and Gemini 3.8 Flash through Antigravity; agent time and provider-accounted tokens measure cost.Runs use fresh containers and a 60-second solver limit; a separate GPT-6 Astra query judges method use.Source: §4 · pp. 5–6
  • Both retry policies share the first attempt; regeneration starts each retry anew, while reflection diagnoses the failed code and rationale and passes advice to the next attempt.When the objective misses the target, reflection is told only that the objective must improve; each policy stops at success or ten attempts.Source: §4 · p. 5
  • Execution requires running without error within the time limit and writing an output file; attempts are scored in order as execution, verification, then quality.Each model attempts all 81 instances under two retry policies.Source: §4 · pp. 5–6
  • Verification requires a finite objective, problem-specific numerical checks, and method-judge acceptance; quality additionally requires an objective within 1% of the stored optimum.The judge checks whether the prescribed decomposition produces the reported solution, and the agent never sees the stored optimum.Source: §4 · pp. 5–6
  • Failures are assigned to the first failed check, and method rejections are manually classified from judge rationales as unproven optimality, inactive decomposition, or solution bypass.Table 1 covers nine task families with nine instances per family; its decomposition-structure column summarizes master decisions and subproblem returns.Source: Table 1 · p. 5, §4 · p. 6

5 Results

Across 12 coding-agent models, first-attempt success was high, and retries brought pooled success close to full coverage. The results also reveal distinct failure patterns, show how reflection affects recovery, and compare the costs of reaching success.

5.1 Can agents design and implement decomposition algorithms?

  • 87.8% of first attempts succeeded; with up to ten attempts, pooled success reached 99.1% under regeneration and 99.8% under reflection.GPT-6 Astra and GPT-6.1 Sol met all three criteria on every instance at their first attempt.Source: Table 2 · p. 6, §5.1 · p. 6

5.2 Where do agents fail?

  • 48 of 62 Benders failures were missing or suboptimal solutions, while method-audit rejection was the largest column-generation failure category, at 26 of 57.Fixed-charge transportation accounted for 19 of 30 missing objectives and 9 of 18 objective gaps.Source: Figure 3 · p. 7, §5.2 · p. 7
  • 93 of 108 method-audit rejections would pass output-only checks; 96 involved unproven optimality claims, 92 from Claude Sonnet 5.In 95 of the 96, a column-generation solver optimized only over generated columns before claiming global optimality.Source: §5.2 · pp. 7–8, Table 3 · p. 8

5.3 A case study: unproven optimality in column generation

  • For cutting stock, the integer restricted-master status alone does not prove global optimality; the case study’s accepted retry checks zIP(K) = ⌈zLP⌉ after pricing converges.Both attempts returned 87 pieces, but only the retry’s code proved the optimality it reported.Source: §5.3 · p. 8

5.4 When does reflection help?

  • 66% of reflection retries succeeded, compared with 39% under regeneration; after method rejection, the next reflection attempt passed the audit in 42 of 44 cases versus 40 of 101.The protocol gives reflection retries the previous solver as well as the judge’s rationale and advice, so their separate effects are not isolated.Source: §5.4 · pp. 8–9, Figure 4 · p. 9

5.5 What does success cost?

  • Among models solving every instance without reflection, mean agent time to success ranged from 21.5 to 228.2 seconds.Reflection reduced mean agent time for GPT-5.6 Luna from 82.5 to 70.8 seconds and Claude Sonnet 5 from 121.4 to 107.9 seconds.Source: Table 4 · p. 9, §5.5 · p. 9, Figure 5 · p. 10
  • Recorded tokens rank models differently from time: the Luna GPT models consume 2.2 to 3.2 times as many tokens as GPT-6 Astra and GPT-6.1 Sol.Token comparisons cover eleven models with comparable totals and use provider-specific accounting.Source: §5.5 · p. 10, Figure 6 · p. 11

5.6 Robustness of the findings

  • Counting unproven-optimality rejections as passes raises Claude Sonnet 5 Q@1 from 46 to 66 of 81; first-attempt success varies little by size (289 small, 283 medium, 281 large of 324 pairs).The change in scoring raises no other model’s Q@1 by more than one instance.Source: §5.6 · p. 11

6 Conclusion

Current coding agents often implement both decomposition methods correctly, but many failures require checking how a solver reached its answer. The benchmark’s reference decompositions and scoring criteria make method conformance, objective quality, and execution part of the evaluation.

6 Conclusion

  • 853/972 (87.8%) first attempts met all three criteria; two models solved every instance, and seven exceeded 90%.The authors conclude that decomposition agents need checks on how solvers reach answers and feedback that locates errors.Source: §6 · p. 11
  • Method audits rejected 93 of 108 output-valid attempts, motivating checks on solver process and feedback that locates errors.The judge’s rationale names defects in audit failures; after such a rejection, reflection succeeded in 41 of 44 next attempts.Source: §6 · pp. 11–12
  • The study uses a fixed synthetic inventory of moderate-size instances, so scaling to larger instances is untested; one GPT-6 Astra judge assessed method use, and accepted attempts were not hand-reviewed.The rate at which the judge accepts solvers that depart from the prescribed method is therefore unmeasured.Source: §6 · pp. 11–12

A Problem Formulations and Reference Decompositions

  • Agents received natural-language tasks and method contracts, not reference formulations; reference solvers met all criteria on 81 instances within 60 seconds.Stored optimal objectives were obtained by solving the original models to optimality.Source: A Problem Formulations and Reference… · p. 16

A.1 Benders families

  • Benders masters update structural decisions and cost estimates using subproblem cuts, stopping when bounds meet within tolerance; continuous recourse can leave integer incumbents uncertified.For location routing, the reference’s integer incumbent was optimal by the monolithic model, but the decomposition bounds remained apart.Source: §A.1 · p. 17

A.2 Column-generation families

  • Across column-generation families, restricted masters use generated columns and pricing uses master duals; integer optimality is proved only when the integer solution attains the rounded linear bound.Source: §A.2 · p. 18

B Instance Inventory

C Scoring Definitions

  • Scoring requires execution, numerical checks, a method-audit pass, and objective quality; policy comparisons pair the same instances, with one saved trajectory per model–instance–policy.Source: C Scoring Definitions · p. 19

D Execution, Verification, and Quality

Across 972 model–instance pairs, execution, verification, and quality are distinct success thresholds; retries close the execution gap before the quality gap.

D Execution, Verification, and Quality

E Method-Audit Findings

The method audit rejects solvers that do not establish the prescribed decomposition or overstate what their algorithm proves. Its largest rejection category is an unproven optimality claim.

E Method-Audit Findings

  • 96 of 108 audit rejections involve an unproven optimality claim, including 95 column-generation solvers and one Benders solver.Claude Sonnet 5 accounts for 92; typical cases treat an optimal integer restricted-master status or a stopped pricing loop as proof of global optimality.Source: E Method-Audit Findings · pp. 20–21, Table 7 · p. 21
  • 8 rejections involve inactive decomposition, such as terminating before a subproblem runs or allowing cuts to have no effect on the search.Examples include an infinite-bound convergence test that evaluates true immediately and a Benders master missing its recourse variable in the objective.Source: E Method-Audit Findings · p. 21
  • 4 rejections involve a reachable fallback that produces the reported solution outside the decomposition.Examples include first-fit-decreasing packing and enumeration of every admissible shift.Source: E Method-Audit Findings · p. 21

E.1 Unproven optimality claims

  • A feasible status is permitted when the solver has an incumbent but no global optimality proof; an unproven “optimal” label is rejected even if the objective is optimal.The quality criterion checks objective value, not status; 115 attempts meeting all three criteria reported “feasible.”Source: §E.1 · pp. 21–22
  • An integer restricted-master optimum certifies optimality only over generated columns; global proof requires the lower and upper bounds to meet.For cutting stock, pricing that proves no negative reduced-cost pattern gives zLP ≤ z★, while the integer restricted master gives zIP(K) ≥ z★; equality with ⌈zLP⌉ proves optimality, otherwise the gap may require branch-and-price.Source: §E.1 · pp. 21–22

F Problem Families and Instance Size

At budget three, reflection yields 27 net additional quality successes, with gains varying across problem families and instance sizes.

F Problem Families and Instance Size

G Retries and Reflection

Reflection produces more retry successes than regeneration, with its advantage concentrated in named models and problem families. Its method-audit feedback is associated with fewer audit rejections on retries.

G Retries and Reflection

  • Claude Sonnet 5 contributes 17 of reflection’s 27 net additional successes at both budgets two and three.At budget three, GPT-5.6 Luna gains six instances; Claude Opus 5 and Gemini 3.8 Flash each gain between two and four.Source: G Retries and Reflection · p. 24, Figure 11 · p. 25
  • After a method-audit rejection, 101 regeneration rejections and all 44 reflection rejections have a subsequent attempt included in the comparison.Tenth-attempt rejections are omitted, and shared first-attempt rejections are counted for both policies.Source: G Retries and Reflection · p. 24, Table 11 · p. 25
  • Among unsuccessful retries, FCTP accounts for 54 of 61 objective gaps under regeneration, while FCTP and TSSO together account for 39 of 43 under reflection.These counts classify retries by the first check they fail.Source: G Retries and Reflection · p. 24, Table 12 · p. 25

H Time and Token Accounting

The section defines how agent and stage times are counted and explains which token totals are comparable. Gemini has separate raw usage reporting because its records do not support a comparable total.

H Time and Token Accounting

  • Agent time averages generation and reflection calls through first success or attempt ten across all 81 instances; Figure 12 adds audit and solver execution durations.Recorded durations exclude user pauses and scheduling or provider-limit waits; parallel stages mean their sum differs from experiment wall-clock time.Source: H Time and Token Accounting · p. 26, Figure 12 · p. 26
  • Token totals combine tool-specific input, cache, and output accounting across turns, but provider tokenizers differ, so comparable totals cover eleven models.Codex cached input is included in input; Claude totals include cache reads and writes, while reasoning tokens are already part of output.Source: H Time and Token Accounting · p. 26
  • Gemini’s raw usage fields may overlap and must not be summed; its provider total is reproduced directly from the tool.Gemini’s records do not show how cache reads relate to input, preventing a comparable total, though it remains in attempt and time comparisons.Source: H Time and Token Accounting · p. 26, Table 13 · p. 27

I Configuration and Reproducibility

The experiment specifies its agent, solver, and resource configuration and combines two runs over the same instances and protocol. Released analysis records outcomes and checks plotted counts against paired results.

I Configuration and Reproducibility

  • The setup used Codex 0.162.1, Claude Code 2.1.296, Antigravity 1.3.1, Python 3.12.11, Gurobi 11.0.3, and macOS 26.4.1.Each solver had a 60-second limit and one numerical solver thread; agent calls ran in fresh, resource-limited containers with tool-specific persistence restrictions.Source: I Configuration and Reproducibility · p. 27
  • The results combine two runs with identical instances, prompts, scoring code, and resource limits, covering all 972 complete model–instance pairs for twelve models.The second run added four Claude models; the released records identify each run’s protocol.Source: I Configuration and Reproducibility · p. 27
  • Released analysis records first success, success counts by attempt budget, time, and tokens, and checks plotted counts against paired outcomes.Figures use consistent model styles and matched axes for policy comparisons, with regeneration on the left and reflection on the right.Source: I Configuration and Reproducibility · p. 27

J Prompt Examples

The prompt examples show how agents receive task context and method contracts, how a judge audits solver code, and how reflection diagnoses failures. The examples include a cutting-stock column-generation attempt rejected for reporting restricted-master optimality as global optimality.

J Prompt Examples

  • The example prompts are for Claude Sonnet 5 on a medium cutting-stock instance; Codex receives identical text, while Antigravity receives merged workspace rules.The judge prompt is the one GPT-6 Astra received; displayed colors are reader-added, and gray marks elided context.Source: J Prompt Examples · p. 27

J.1 Generation

  • Generation prompts specify the task, output format, runtime rules, and a method-specific contract followed by three shared contract paragraphs.The example output requires a column-generation method and a solution represented through pattern usage and item counts.Source: §J.1 · pp. 27–28
  • The column-generation contract requires iterative restricted-master optimization using pricing information, while prohibiting a separate full-original-model solve on any reachable solution path.Direct seed columns and heuristic initialization are allowed, but must not obtain a solution from that separate full model.Source: §J.1 · p. 29
  • The contract permits immediate convergence and requires consistent incumbent decisions and objective values; an integer restricted-master optimum alone does not establish global optimality.The Benders example instead requires fixed-decision subproblems to generate cuts that update later master solves.Source: §J.1 · p. 29

J.2 Method judge

  • The judge assesses substantive algorithm use from source paths and information flow, not a full mathematical proof, and does not execute the solver.It traces reachable calls and output-writing code; numerical execution, feasibility, consistency, and objective quality are checked separately.Source: §J.2 · p. 30
  • In the example audit, the judge rejected a column-generation solver that labeled an optimal integer restricted master as globally optimal without a global proof.The rationale found the decomposition structurally sound and identified the unsupported status assignment as the defect.Source: §J.2 · pp. 29–30

J.3 Reflection

  • Reflection diagnosis receives failed code, execution output, and judge rationale; when the objective misses its target, the prompt only says it must improve.The next attempt receives the prior code and advice; the example reflection recommends reporting the restricted-master incumbent as feasible absent a global certificate.Source: §J.3 · pp. 30–31
  • The example revision reused the generation instructions with the solver and its advice, and the resulting attempt met all three criteria.The advice distinguished optimality of the restricted master from global optimality and recommended a feasible status without a genuine certificate.Source: §J.3 · pp. 31–32

Related papers

Loading 2610.38175v1…