1 Introduction↩︎

Large language models (LLMs) have advanced rapidly toward agent-style code execution and tool use [1]–[6]. This shift has created a need to measure not the surface quality of LLM output but the end-to-end problem-solving capability of an LLM-driven agent on concrete tasks. A growing body of agent-style benchmarks targets this need across different task families [7]–[9].

Linear programming (LP) is one such task family. An LP-from-text agent [10]–[13] receives a problem description in natural language, builds the mathematical formulation, generates solver code, executes it, and reports the optimum. Formulation, code generation, and numerical fidelity must all be correct simultaneously, which makes LP-from-text a strict end-to-end test of LLM-agent capability. Reliable evaluation of these agents demands a test set of problem–answer pairs whose answers are verified correct. Producing such pairs is laborious: benchmarks such as NL4OPT [10] and MAMO [11] each assembled hundreds of human-authored word problems whose gold answers were labeled by hand, a process that is slow, costly, and difficult to scale.

Beyond their production cost, these benchmarks share a deeper structural disadvantage: they are all released as static corpora, a fixed set of human-authored word problems with gold answers attached. This design has four structural limitations that no amount of careful curation can remove: (i) Each item requires human authoring and validation, so the benchmark size is bounded by the annotator budget. (ii) Every released item enters subsequent training corpora; once a model is trained on the public release, the benchmark becomes a memorization probe rather than a capability test. (iii) The difficulty distribution is fixed at release time and cannot be re-targeted as model capability changes. (iv) Evaluation is run by hand or with paper-specific harnesses; there is no agent-runnable surface that an LLM-driven agent can plug into out of the box.

We address all four limitations by shipping a generator instead of a corpus, together with an agent-runnable evaluation surface. 1 contrasts the traditional human-in-the-loop construction with our automated pipeline. A\(^{2}\)utoLPBench has two parts, Auto and Agent. The Auto part is the inverse-KKT generator: given dimensions \((n, m)\) and a random seed, it draws a primal-dual-coefficient triple \((x, \lambda, A)\) and reverse-derives the LP \((c=A^{\top}\lambda,\, b=Ax)\) whose optimum is, by KKT, exactly \(\phi = c^{\top} x\), with no solver invocation and no human annotator in the loop. The Agent part is the bundled evaluation surface: a solver-critic baseline (3.2) and a Docker environment with agent-readable documentation (13) whose declared tool-use skills any tool-use-capable agent can register and run plug-and-play. The two parts are designed together. The generator addresses limitations (i)–(iii) by producing fresh, parametrically-tunable, contamination-free items on demand. The agent surface addresses limitation (iv) by giving downstream agents a single docker run entry point. Re-framing the LP benchmark as a generator rather than a corpus yields structural properties that fixed benchmarks cannot have. These properties follow from the generator-versus-corpus design choice rather than from any empirical difficulty claim. 1 summarizes them. Our main contributions are summarized as follows:

1. Unlimited supply at low LLM-side cost: the generator produces LP instances in closed form from sampled triples \((x,\lambda,A)\) via \(b=Ax\) and \(c=A^{\top}\lambda\), plus a single LLM drafter call. Per-item cost is dominated by that drafter call rather than human author or annotator labor (cf.NL4OPT [10] and MAMO [11]), so benchmark size decouples from annotator budget. We ship a \(256\)-instance reference snapshot; the procedure scales to any size and seed range (3.4).

2. Parametric, reproducible difficulty: difficulty is set by the generator’s \((n,m)\) knobs and coefficient ranges, not fixed at release time. The generator traces a sol-rate curve over eight strata from \((2,3)\) to \((40,40)\) on which existing benchmarks appear as isolated points; independently sampled batches with the same parameters agree to within \(3\)pp off-cliff, turning the benchmark from a single score into a measurement instrument, illustrated by 4 in 10).

3. Mathematically certified ground truth: for each instance, the optimum \(\phi=c^{\top}x\) is established by the KKT theorem (2) before any solver is invoked, removing both solver-precision drift and human-annotator transcription error. The certificate covers the algebraic LP \((A,b,c)\); the natural-language rendering \(T\) is checked by a string-level coefficient match, with the limits of single-pass rendering discussed in 8.

4. Contamination resistance by construction: any batch drawn from a seed range chosen after a model’s training cutoff cannot have appeared in that model’s training corpus. The released snapshot can itself leak into future training data once published, but downstream evaluators can always draw fresh seed ranges to obtain contamination-free batches; the guarantee is structural, tied to the generator-vs-corpus distinction, rather than an empirical claim about any particular file.

In addition to the generator itself, the Agent part of A\(^{2}\)utoLPBench provides two pieces of agent-side tooling for plug-and-play deployment. The first is a dual-agent solver-critic baseline (3.2) organized around three actions, Propose, Audit, and Refine, that on external LP benchmarks where models score well below ceiling recovers up to \(+15.1\)pp on Kimi-K2.5 and \(+11.3\)pp on Claude-Sonnet-4.6 over MAMO complex through a bounded-iteration loop. The second is an agent-friendly Docker environment (13) that bundles the generator, verifier, dual-agent runtime, and an AGENTS.md usage manual targeted at LLM-driven agents, so that a downstream agent can attach to the image and obtain a calibrated LP score with a single docker run.

1.0.0.1 Related work.

Existing LP-from-text benchmarks [10], [12]–[14] are static corpora in the sense of 12 : \(\mathcal{D}\) is fixed at release time and each \(\phi_i\) is obtained from a solver run or a human annotator, exposing them to training-corpus contamination [15], [16] and a frozen difficulty distribution as models improve [17]. Generator-based reasoning benchmarks [18], [19] address contamination by parameterising instance generation; A\(^{2}\)utoLPBench extends that idea to LP-from-text and pairs it with a closed-form KKT certificate (2) that also removes solver dependence. The bundled solver-critic protocol of 3.2 is closely related to self-refinement [20]–[22], sharing the documented caveat that internal self-correction can degrade on already-saturated tasks [23]. 12 expands these comparisons and adds the verifiable-reasoning, OR-LLM agent, and tool-use-benchmark literatures.

2 Preliminaries↩︎

2.1 Linear programming and KKT optimality↩︎

A linear program (LP) optimizes a linear objective subject to linear inequality and non-negativity constraints. We consider the standard maximization form \[\label{eq:lp} \begin{align} \max_{x} \quad & c^\top x, \\ \text{s.t.} \quad & Ax \le b, \\ & x \ge 0, \end{align}\tag{1}\] where \(c \in \mathbb{R}^n\), \(A \in \mathbb{R}^{m \times n}\), and \(b \in \mathbb{R}^m\). The optimal objective value is denoted \(\phi = \max_{x} c^{\top}x\) subject to the constraints in 1 , and a maximizer is denoted \(x^{\star}\). Every primal LP of the form 1 admits a dual problem \(\min_{\lambda \ge 0} b^{\top}\lambda\) subject to \(A^{\top}\lambda \ge c\), and strong duality holds whenever both primal and dual are feasible.

2.1.0.1 KKT optimality.

For LPs, the Karush–Kuhn–Tucker (KKT) conditions are both necessary and sufficient for optimality: a feasible point \(x\) achieves the optimum of 1 if and only if there exist dual variables \(\lambda\in\mathbb{R}_{\ge 0}^{m}\) and \(\mu\in\mathbb{R}_{\ge 0}^{n}\) such that \[\tag{2} \begin{align} Ax &\le b, \qquad x\ge 0, \tag{3}\\ A^\top \lambda - \mu &= c, \tag{4}\\ \lambda_i\bigl(b_i-(Ax)_i\bigr) &= 0 \;\;\forall i,\qquad \mu_j x_j = 0 \;\;\forall j. \tag{5} \end{align}\] 3 is primal feasibility, 4 is stationarity (equivalent to dual feasibility under our sign convention on \(\mu\)), and 5 is complementary slackness on the inequality constraints and non-negativity bounds, respectively. These conditions provide the algebraic identities that we exploit in 3.1 to construct LP instances directly from a sampled optimum, rather than solving for one.

2.2 Agent formalization for LP-from-text↩︎

We model an LP-from-text agent \(\mathcal{A}\) as a stochastic mapping that takes a natural-language description \(T\) and produces a numerical answer \(\hat{z}\in\mathbb{R}\): \[\label{eq:agent95def} \mathcal{A}: T \;\longmapsto\; \hat{z}.\tag{6}\] \(T\) describes an underlying LP \((A, b, c)\) in the form of 1 , with every coefficient of \(A\), \(b\), and \(c\) stated explicitly in the text and the optimization sense (maximize/minimize) and variable bounds named in plain language. Internally an agent typically realizes \(\mathcal{A}\) as a multi-stage pipeline, \[\label{eq:agent95pipeline} T \;\xrightarrow{f_{\text{parse}}}\; F \;\xrightarrow{f_{\text{code}}}\; \pi \;\xrightarrow{f_{\text{exec}}}\; \hat{z},\tag{7}\] where \(F = (\widehat{A}, \widehat{b}, \widehat{c}, \text{sense}, \text{bounds})\) is the formulation extracted from \(T\), \(\pi\) is an executable solver program (typically Python that calls scipy.optimize.linprog or pulp), and \(\hat{z}\) is the final printed objective value. In this paper, we treat \(\mathcal{A}\) as a black box and score only \(\hat{z}\); 3.2 reuses the decomposition 7 to characterize the failure modes the bundled solver-critic protocol is designed to catch.

2.2.0.1 Benchmark and score.

An LP-from-text instance is a pair \((T,\phi)\) where \(\phi\) is the ground-truth optimum of the LP underlying \(T\), and a benchmark is a finite collection \(\mathcal{D}=\{(T_i,\phi_i)\}_{i=1}^{N}\). Existing LP-from-text benchmarks are static-corpus benchmarks: \(\mathcal{D}\) is fixed at release time and each \(\phi_i\) is obtained from a solver invocation or a human annotation, so \(|\mathcal{D}|\) is bounded by the annotator budget. We instead construct a generator-based benchmark, a randomized procedure \(\mathcal{G}: s \mapsto (T,\phi)\) that produces fresh instances on demand from a random seed \(s\) and yields \(\mathcal{D}_{\mathcal{G}}(S)=\{\mathcal{G}(s):s\in S\}\) on any chosen seed range \(S\), with \(|S|\) controllable at evaluation time and each \(\phi\) established by the KKT theorem rather than by a solver run (3.1). Formal definitions and the equations underlying these notations are given in 7.

For an agent \(\mathcal{A}\) on a benchmark \(\mathcal{D}\) we report the sol-rate \[\label{eq:solrate} S(\mathcal{A}, \mathcal{D}) = \frac{1}{|\mathcal{D}|}\sum_{i=1}^{|\mathcal{D}|} \mathbb{1}\bigl[\,\text{correct}(\hat{z}_i, \phi_i)\,\bigr],\tag{8}\] where \(\hat{z}_i = \mathcal{A}(T_i)\) and \(\text{correct}(\hat{z}, \phi)\) is a relative-error judgment whose tolerance is fixed throughout the paper and stated in 4.1. The notation \(\mathcal{A}\), \(T\), \(\hat{z}\), \(\phi\), \(\mathcal{D}\), \(\mathcal{D}_{\mathcal{G}}(S)\), \(S(\cdot,\cdot)\) is used consistently from this point on.

3 Method↩︎

This section presents the four components of A\(^{2}\)utoLPBench: the inverse-KKT generator (3.1, the Auto part), the bundled solver-critic baseline and the agent-runnable Docker runtime (3.2 and 3.3, the two halves of the Agent part), and the released 256-instance reference snapshot (3.4). 2 gives an end-to-end overview. Three LLM-driven agents appear across these components: the natural-language drafter that converts each LP triple into a word problem (system and user prompts in 6.4), the solver agent that proposes a candidate Python program (system prompt in 9.1), and the critic agent that audits the candidate and decides whether to refine (system prompt in 9.2). Notation follows 2.

3.0.0.1 What makes LP-from-text hard.

Recall the agent pipeline of 7 : \(T \to F \to \pi \to \hat{z}\). For the final \(\hat{z}\) to be correct, three independent capabilities must hold simultaneously. (i) The formulation \(F\) extracted by \(f_{\text{parse}}\) must agree with the LP underlying \(T\). (ii) The program \(\pi\) produced by \(f_{\text{code}}\) must respect the solver’s calling convention (maximize-vs-minimize sign, row-vs-column matrix layout, default variable bounds). (iii) The executed value \(\hat{z} = f_{\text{exec}}(\pi)\) must survive both the solver’s internal precision and the agent’s output formatting. The typical failure modes correspond directly to violations of these three: \(\widehat{A}\) transposed row-by-row instead of column-by-column, a “\(\le\)” constraint silently recorded as “\(\ge\)”, a maximization passed to a minimization solver without coefficient negation, a single constraint dropped from \(\widehat{b}\), or \(\hat{z}\) overflowing when \(n\) and \(m\) are large. 11 traces representative instances of each failure mode, and 10 shows that the cumulative failure rate climbs sharply as \((n,m)\) grow. The four components below address these failure modes from complementary angles: a generator with mathematically certified ground truth (3.1), an inference-time solver-critic runtime that audits and refines candidate outputs (3.2), a Docker environment that lets any LLM-driven agent run the benchmark end-to-end (3.3), and a released reference dataset (3.4).

3.1 Auto Part: LP Pair Construction via Inverse-KKT↩︎

We refer to \((A, b, c)\) as the LP instance, \((x, \phi)\) as its ground truth (GT), and the combination of the LP instance and its ground truth as an LP pair, which is \((A, b, c, x, \phi)\).

A central challenge in scalable benchmark construction is ground-truth reliability: pipelines that sample random instances and certify the optimum with an external solver inherit solver dependence and floating-point fragility, while pipelines that rely on human annotation inherit annotation errors and cannot be cheaply regenerated. A\(^{2}\)utoLPBench instead constructs instances from the optimality conditions themselves, focusing on candidate points \(x > 0\) that we will certify optimal by KKT. At such an interior point, complementary slackness on the non-negativity constraints forces \(\mu = 0\), so the KKT system of 2 reduces to the two linear equations \(A^{\top}\lambda = c\) and \(Ax = b\), together with strict positivity \(x > 0\) and \(\lambda > 0\). We sample \(x \in \mathbb{Z}_{>0}^{n}\), a full-rank \(A \in \mathbb{Z}^{m\times n}\) with \(\operatorname{rank}(A) = \min(m,n)\) (a numerical-diversity guard described in 6; not required for the optimality proof), and strictly positive \(\lambda \in \mathbb{R}_{>0}^{m}\) (Algorithm 3), and set \[\label{eq:inverse-def} b = A x, \qquad c = A^{\top} \lambda,\tag{9}\] and record the ground-truth optimum \[\label{eq:invkkt95optval} \phi = c^{\top} x.\tag{10}\] By construction, all primal constraints are tight at \(x\) and dual feasibility holds with equality, which is exactly what is needed for the KKT optimality conditions.

By construction, \((A, b, c, x)\) with \(x > 0\) and \(\lambda > 0\) satisfies every KKT condition of the LP in 1 (taking the multiplier \(\mu = 0\) on the non-negativity block), so \(x\) is an optimal solution with optimal value \(\phi = c^{\top} x\). The formal statement and its full block-by-block KKT verification are given as 2 in 6.1.

The generator exposes three knobs as parameters of 3: \((n, m)\), the coefficient ranges of \(A\) and \(x\), and the scaling of \(\lambda\). 10 sweeps the \((n, m)\) axis while holding the other two fixed at the defaults of 6, tracing out the difficulty curve we report there. The full pseudocode is given as 3 in 6.

3.1.0.1 Natural-language rendering.

Each LP pair is converted into a natural-language word problem \(T\) via a single-shot LLM drafter (the prompt is given in 6.4). The drafter is instructed to use every coefficient verbatim, name the optimization direction, and state every constraint explicitly; we verify numerical fidelity by string-matching every coefficient against the rendered text and resampling if any coefficient is missing. This single-pass procedure suffices for the difficulty regimes evaluated in this paper; we discuss the limits of single-pass NL rendering in 8.

3.2 Agent Part: Bundled LP Solver↩︎

A static dataset can surface the failure modes characterized at the start of 3 only after the fact. The Agent part of A\(^{2}\)utoLPBench instead provides an inference-time runtime that audits candidate outputs against those failure modes and refines them on the fly, shipped as a bundled solver-critic baseline alongside the dataset, so that any downstream evaluation has a stronger reference point than vanilla LLM zero-shot inference.

The protocol involves two agents and three actions. The solver agent \(\mathcal{A}\) (system prompt in 9.1) takes the natural-language specification \(T\) and produces an executable Python program whose final printed line is the candidate optimum \(\hat{z}\). The critic agent \(\mathcal{C}\) (system prompt in 9.2) takes \(T\), the candidate program, and its standard output, and emits a verdict \(V \in \{\mathrm{\small Agree}, \mathrm{\small Disagree}\}\) together with a short rationale. Each round of the loop consists of one or more of three actions.

3.2.0.1 Propose.

The solver \(\mathcal{A}\) reads \(T\) and produces an initial candidate \(y_{1}\). This action runs once per item and corresponds, in isolation, to vanilla LLM zero-shot inference.

3.2.0.2 Audit.

The critic \(\mathcal{C}\) reads \((T, y_{k})\) and emits \((V_{k}, r_{k})\): a binary verdict and a textual rationale. This action runs once per round.

3.2.0.3 Refine.

If the audit returns Disagree and the budget is not exhausted, the solver re-enters the loop conditioned on the rationale \(r_{k}\) and produces a new candidate \(y_{k+1}\). This action runs at most \(K-1\) times per item.

With budget \(K \in \mathbb{N}_{>0}\), the round-\(k\) outputs are \[\label{eq:dualagent95loop} \begin{align} y_{1} \;&\sim\; p_{\mathcal{A}}(\cdot\mid T) && \text{(Propose)}, \\[2pt] (V_{k}, r_{k}) \;&\sim\; p_{\mathcal{C}}(\cdot\mid T, y_{k}) && \text{(Audit)}, \\[2pt] y_{k+1} \;&\sim\; p_{\mathcal{A}}(\cdot\mid T, r_{k}) && \text{(Refine, if } V_{k} = \mathrm{\small Disagree}\text{ and } k < K\text{)}. \end{align}\tag{11}\] The loop terminates at the smallest \(k\) with \(V_{k} = \mathrm{\small Agree}\), or at \(k = K\). An optional LP-modeling skill, a curated tutorial that names canonical failure modes, can be prepended to the solver’s system prompt; we treat skill and critic as orthogonal axes. Full system prompts and the coverage analysis \(P_{K} \ge 1 - (1 - \pi_{1})^{K}\) are deferred to 9. 4.2 reports its empirical effect: a meaningful uplift on benchmarks where models are well below ceiling (notably MAMO complex), and near-zero uplift on already-saturated benchmarks.

3.3 Agent Part: Docker Runtime↩︎

Beyond the solver-critic baseline of 3.2, the Agent part of A\(^{2}\)utoLPBench ships an agent-runnable evaluation surface as a self-contained Docker image (autolpbench:latest) that preloads the inverse-KKT generator, KKT verifier, scipy/PuLP solvers, and the bundled solver-critic runtime. Inside the image, an AGENTS.md manual declares four tool-use skills (problem fetch, solver invocation, KKT verification, batch generation), each described in the JSON-schema format consumed by current tool-use APIs (OpenAI function calling, Anthropic tools, etc.). Any LLM-driven agent that supports tool use can read AGENTS.md, register the declared skills, and run the benchmark plug-and-play, without further glue code or environment setup.

This packaging closes the four static-corpus limitations (i)–(iv) listed in 1: the bundled generator addresses (i)–(iii), and the AGENTS.md manifest addresses (iv) by giving downstream agents a single docker run entry point. Full image specification, the tool-use skill schema, and a sample AGENTS.md excerpt are in 13.

3.4 Dataset Construction in Practice↩︎

A\(^{2}\)utoLPBench is a generator, not a corpus: we ship a 256-instance reference snapshot stratified into eight size classes \((n,m)\) from \((2,3)\) to \((40,40)\) at 32 instances per class, but the same generator produces additional instances at any size and seed, so a downstream evaluator can draw a fresh contamination-free batch at any time (per-stratum seed ranges, JSON schema, and per-item wall-time in 6). Each instance is produced by the inverse-KKT procedure of 3 followed by a single LLM-drafter call. Ground truth is correct by construction via 2 and does not depend on a solver; as a redundant sanity check we also re-run scipy’s linprog on every released \((A, b, c)\) and confirm that its numerical solution matches \(\phi\) within relative tolerance \(\tau=10^{-4}\) (all 256 pass). For comparison, NL4OPT [10] releases 287 human-authored word problems and MAMO [11] releases 211 complex + 652 easy items, both as fixed crowdsourced corpora. The released snapshot, the generator, and the solver-critic runtime are bundled in the Docker image of 3.3.

4 Experiments↩︎

4.1 Experimental Setup↩︎

The experiments come in two pieces. (i) Calibration: we sweep DeepSeek-V4 across all eight strata of A\(^{2}\)utoLPBench in three independent seed ranges, then re-run three additional solvers (MiMo-V2.5, Qwen3.5, Kimi-K2.5) on the same instances. To flip the drafter side, that is, to vary the LLM that authors the natural-language description \(T\) in 3.1, we additionally evaluate all four solvers on a batch in which DeepSeek-V4 (rather than the default MiMo-V2.5) drafts the descriptions; we refer to these two batches as “MiMo-drafted” and “DS-drafted” below. The per-stratum DeepSeek-V4 sol-rate runs from \(100\%\) on the small strata to \(8.3\%\) at s40x40 with batch-to-batch noise \(\le 3\)pp off the cliff, supporting the parametric-difficulty and cross-batch claims of 1. Full curve, four-solver figure, and cross-distribution findings are in 10. (ii) External-benchmark transfer: we evaluate the bundled solver-critic baseline on NL4OPT and the two MAMO subsets under DeepSeek-V4 / MiMo-V2.5 cross-pairings, then extend to a six-solver leaderboard with a fixed MiMo-V2.5 critic; this is also where token-cost auditing lives (4.2).

Every solver runs in two inference modes: vanilla (direct generation of solver code, no critic) and A\(^{2}\)utoLPBench (the bundled solver-critic baseline of 3.2, configured at \(K=3\) critic rounds). All models are queried at temperature \(0.3\) for reproducibility; reasoning-capable solvers (Qwen3.5, Kimi-K2.5, OpenAI-GPT5.4, Claude-Sonnet-4.6) run with thinking / extended-reasoning modes disabled to match the deployment regime that downstream agent users typically face. The executor sandbox imports scipy.optimize.linprog and pulp and verifies output against \(\phi\) via the relative-error criterion \(|\phi - \hat{z}|/(|\phi| + 10^{-8}) < 10^{-2}\). Per-item logs and aggregate summaries are released alongside the dataset.

4.2 External-Benchmark Transfer↩︎

We further evaluate A\(^{2}\)utoLPBench’s bundled solver-critic baseline on two external static-corpus benchmarks. Across each of NL4OPT and the two MAMO subsets (easy and complex), we use a fixed prefix of \(53\) items per cell, the largest equal-size subset that fits the cross-product of solver-critic configurations within our compute and rate-limit budget; using a fixed prefix rather than a random subsample keeps comparisons reproducible across cells, and we acknowledge the fixed-prefix choice as a sampling limitation that a random-subsample sensitivity check would tighten. With this subset fixed, we pair two solver families (DeepSeek-V4 and MiMo-V2.5) under four configurations: vanilla, A\(^{2}\)utoLPBench with the same-model critic, and A\(^{2}\)utoLPBench with each cross-model critic combination. 2 reports per-cell sol-rate.

5pt

Three patterns appear consistently. (a) On NL4OPT, vanilla DeepSeek-V4 and MiMo-V2.5 are already saturated at \(98.11\%\), leaving no room for the solver-critic loop to add value; the only configuration that meaningfully deviates is MiMo-V2.5+MiMo-V2.5, which loses \(7.5\)pp because a same-distribution critic occasionally over-disagrees on already-correct code. (b) On MAMO complex, the underlying benchmark has substantial headroom (vanilla \(13.2\)–\(26.4\%\)); every A\(^{2}\)utoLPBench configuration yields a positive delta, with the largest uplift coming from cross-model pairings of the weaker solver: MiMo-V2.5+DeepSeek-V4 reaches \(28.3\%\) from a \(13.2\%\) vanilla baseline (\(+15.1\)pp). (c) On MAMO easy, gains are smaller and direction-dependent.

Comparing this transfer pattern to the calibration sweep, where same-model A\(^{2}\)LPBench (abbreviated as A\(^{2}\)LP) DeepSeek-V4+DeepSeek-V4 lifts the s40x40 sol-rate from \(8.3\%\) to \(33.3\%\) (\(+25\)pp; numerical bound check in 9, full curve in 10), we observe that the preferred critic-pairing depends on which failure mode dominates. When failures are dominated by formulation errors (e.g.MAMO complex), a cross-model critic catches errors the solver’s own distribution does not flag. When failures are dominated by numerical precision (e.g.A\(^{2}\)utoLPBench s40x40), same-model critics produced fewer harmful disagreements on numerically delicate instances; 11 gives trace-level evidence. The bundled solver-critic baseline therefore generalizes across benchmarks but its preferred critic-pairing is benchmark-dependent.

4.2.0.1 Multi-solver leaderboard with a fixed cross-model critic.

To check that the cross-model A\(^{2}\)utoLPBench protocol generalizes beyond DeepSeek-V4 and MiMo-V2.5, we run vanilla and “\(X\) + MiMo-V2.5 critic” configurations across six solver families on the same MAMO complex subset. 3 reports per-cell sol-rate.

Of the five solvers paired with a cross-model MiMo-V2.5 critic (MiMo-V2.5 itself is excluded since it is the critic), four gain, with the largest uplift on Kimi-K2.5 (\(+15.1\)pp) and Claude-Sonnet-4.6 (\(+11.3\)pp). The sole regression among these five is OpenAI-GPT5.4 (\(-1.9\)pp). Inspecting its A\(^{2}\)utoLPBench traces shows that the critic disagreed on \(14\) items at the Audit stage, but the solver successfully Refined only \(2\) of them (about \(14\%\)); on the remaining \(12\) items the Refined output either repeated the same error or executed an unrelated formulation that produced an empty stdout. The traces suggest that, under reasoning_effort=none in this configuration, OpenAI-GPT5.4 Proposes a single LP formulation efficiently but does not robustly incorporate critic feedback into a corrective Refine step. The bundled solver-critic loop therefore acts as a capability amplifier that requires the underlying solver to act on critic feedback at the Refine stage; when the solver is below that threshold, the loop does not help and can occasionally regress on items vanilla would have solved. The full failure analysis with traces is in 11.1. We treat this as a limitation of the bundled solver-critic baseline rather than a property of the benchmark, and recommend reporting both vanilla and A\(^{2}\)utoLPBench scores by default (as we do throughout 3) so that the loop’s contribution is visible per solver. The structural properties of 1 (parametric difficulty, KKT-certified ground truth, contamination resistance) follow from the inverse-KKT generator (3.1) and hold for any inference protocol, regardless of whether the loop adds or subtracts on a particular solver.

4.2.0.2 Inference-time token cost.

We log every API call’s prompt and completion token counts directly from the OpenAI / Anthropic SDK usage field, then aggregate to per-item totals. 4 reports per-item mean tokens (summed across all iterations \(k = 1, \dots, K\)) on the same MAMO complex subset for the configurations of 3. The aggregate uses every cell’s actual dc_avg_iter, so the totals are directly comparable across solvers without normalising to a fixed \(k\).

3pt

4.2.0.3 Pricing the loop and the dataset.

Vanilla cells run at \(1.2\)–\(3.1\)K tokens per item and A\(^{2}\)utoLPBench cells at \(5.8\)–\(12.1\)K tokens per item, so the solver-critic loop costs roughly \(3\)–\(5\times\) a single vanilla call. We monetise the token totals from 4 at the publicly listed per-token list prices on each provider’s official site (May 2026): one A\(^{2}\)LP DeepSeek-V4+MiMo-V2.5 item costs \(\sim \$0.0023\) at DeepSeek-V4 list pricing, and one A\(^{2}\)LP Claude-Sonnet-4.6+MiMo-V2.5 item costs \(\sim \$0.030\) at Anthropic’s Claude-Sonnet-4.6 rate.

Dataset construction is cheaper still: each new instance costs one LLM-drafter call, with median per-item cost \(\sim\$0.0015\) at DeepSeek-V4 list rate and \(\sim\$0.019\) at Claude-Sonnet-4.6 list rate. The savings come from removing the human author and annotator from the loop entirely; full token breakdowns, per-stratum drafter cost, and the largest-instance prices are in 6.3.0.7.

5 Conclusion↩︎

In this paper, we presented A\(^{2}\)utoLPBench, an LP-from-text benchmark that pairs an inverse-KKT generator (KKT-certified ground truth, parametric difficulty across eight strata, contamination-resistant under fresh seed ranges) with an agent-runnable solver-critic baseline and a Docker image. The bundled loop transfers to external LP benchmarks with up to \(+15.1\)pp uplift on Kimi-K2.5 over MAMO complex; together, the two parts move LP evaluation from static corpora toward calibrated, contamination-resistant generators.

6 Auto-Part Implementation Details↩︎

3 below describes the high-level construction; the main-text discussion (3.1) summarizes the same procedure in prose. This appendix documents the concrete sampling distributions, rank safeguards, coefficient ranges, the natural-language drafter prompt, and the per-stratum composition of the 256-instance reference snapshot used in all experiments of 4. The same procedure scales to arbitrary instance counts: downstream evaluators can call the generator with new seed ranges to obtain fresh, contamination-free batches at any size.

6.1 Proof of the Ground-Truth Guarantee↩︎

6.1.0.6 Remark on uniqueness.

The theorem certifies that \(x\) is one optimal solution, not the unique one: LPs can admit multiple optima when the objective is parallel to a face of the feasible polytope. We claim no uniqueness of the maximizer in the construction, only of the optimal value \(\phi\), which is unique under strong duality whenever an optimum exists.

6.1.0.7 Remark on the interior assumption.

The construction restricts to interior optima \(x > 0\) so that \(\mu = 0\) is admissible by inspection. For boundary optima with \(x_j = 0\) for some \(j\), the corresponding \(\mu_j\) would need to be chosen to satisfy stationarity, complicating the closed-form derivation. Restricting to \(x > 0\) does not meaningfully narrow the structural diversity of the LP family, since every LP with a finite optimum can be reformulated with positive offsets into an equivalent interior-optimum instance.

6.2 Reference Snapshot Composition↩︎

5 records the composition of the initial \(256\)-instance batch we ship as a convenience reference. The release size \(256\) is a starting point for cross-paper comparison, not a cap on dataset size: the generator produces additional batches of any size, dimension, and seed range on demand, and the per-stratum item counts shown below can be increased arbitrarily without further engineering.

6.3 Inverse-KKT Sampling↩︎

6.3.0.1 Primal solution \(x\).

Each entry \(x_j\) is drawn independently and uniformly from \(\{1,2,3,4,5\}\) (positive integers). Integer values keep the natural-language description readable and ensure \(x>0\) so the interior-optimum condition (2) holds without further checks.

6.3.0.2 Constraint matrix \(A\).

Entries \(a_{ij}\) are drawn independently and uniformly from \(\{1,2,3,4,5\}\) (positive integers, no zeros). We then verify \(\operatorname{rank}(A)=\min(m,n)\); if not, we resample up to \(100\) attempts. After \(100\) rejections we fall back to a deterministic full-rank backbone (an identity-like pattern with random non-zero filler) so the generator never blocks indefinitely. In practice we have not observed the fallback firing for any \((n,m)\) in \(\{(2,3),\ldots,(40,40)\}\).

6.3.0.3 Dual multipliers \(\lambda\).

Entries \(\lambda_i\) are drawn independently and uniformly from \([0.5, 3.0]\) (real-valued, strictly positive). Setting \(b = Ax\) in the next step makes every primal inequality active at \(x\), after which any strictly positive \(\lambda\) satisfies complementary slackness \(\lambda_i (b_i - (Ax)_i) = 0\) trivially (the parenthetical is zero); we use \(\lambda > 0\) rather than \(\lambda \ge 0\) for numerical-diversity reasons rather than for the proof.

6.3.0.4 Derived quantities.

Given \((x, A, \lambda)\), we set \(b = Ax\), \(c = A^{\top}\lambda\), \(\phi = c^{\top} x\). By construction \(b\) is integer-valued and \(c\) is real-valued (a positive linear combination of integer columns of \(A\) weighted by real \(\lambda\)). We do not round \(c\) or \(\phi\); the natural-language drafter is asked to use every coefficient verbatim (6.4).

6.3.0.5 Per-trial artifact format.

Each instance is serialized as one JSON line with the following keys: instance_id, split, n, m, lp_form, A, b, c, ground_truth \(\{\)x_star, phi_star, lambda_star, active_set\(\}\), nl_description, generation \(\{\)seed, drafter_model, all_constraints_tight, lambda_positive\(\}\), and verification \(\{\)tau, eps, verified\(\}\). This schema mirrors the 256-instance reference snapshot at our anonymous repository.

6.3.0.6 Construction throughput.

The full pipeline (numerical sampling, KKT verification, NL drafting, and fidelity check) takes approximately \(0.1\) s of compute per item, excluding LLM-drafter latency, which is dominated by network IO and amortizes to \(\sim 1\) s per item under standard parallelism. Producing the 256-instance reference snapshot took approximately 12 minutes of wall time on a single workstation; the corresponding NL4OPT and MAMO collection efforts are crowdsourced human-authored corpora and require human-author plus annotator labor per item [10].

6.3.0.7 Drafter token usage and per-item cost.

4.2 prices the solver-critic loop and the dataset-construction call at headline rates. We provide the underlying token counts here. Counting the drafter prompt and the rendered description with the tiktoken gpt-4o encoding over all 256 v1.0 instances, the per-item drafter cost has a median of \(1.6\)K input plus \(0.9\)K output tokens, ranging from \(0.7\)K total at \((2,3)\) to \(18\)K total at \((40,40)\) as the matrix grows. Pricing the median item gives \(\sim\$0.0015\) at DeepSeek-V4 list rate and \(\sim\$0.019\) at Claude-Sonnet-4.6 list rate; the largest \((40,40)\) items reach \(\sim\$0.012\) and \(\sim\$0.16\) respectively. Producing fresh batches at scale is therefore bounded by drafter latency rather than monetary cost. We report only LLM-side costs and avoid putting a specific number on annotator labor since published per-item annotation rates are not consistently reported across NL4OPT and MAMO.

6.4 Natural-Language Drafter↩︎

The drafter is a single-shot LLM call that receives the LP triple \((A,b,c)\) together with sense and bounds and emits a self-contained natural-language word problem. We use temperature \(0.6\) and the prompts below.

6.4.0.1 System prompt.

6.4.0.2 User prompt template.

The user message embeds the LP coefficients and demands numerical fidelity:

6.4.0.3 Fidelity check.

After drafting, we string-match every coefficient in \(A\), \(b\), \(c\) against the rendered text. If any coefficient is missing, we resample the drafter at the same temperature. On the 256-instance reference snapshot, the first-pass fidelity rate is \(100\%\) (\(256/256\)); no resampling was triggered.

7 Benchmark Formalization↩︎

This appendix expands the benchmark notation summarized in 2.2. The two design patterns we distinguish, static-corpus and generator-based, differ in how \(\mathcal{D}\) is sourced and in how each \(\phi_i\) is established.

7.0.0.1 Items, ground truth, and benchmarks.

An LP-from-text instance is a pair \((T, \phi)\) in which \(T\) is the natural-language description from 6 and \(\phi\) is the ground-truth optimum of the underlying LP in 1 . A benchmark is a finite collection \[\label{eq:benchmark95def} \mathcal{D} \;=\; \{(T_i, \phi_i)\}_{i=1}^{N}, \qquad |\mathcal{D}| = N,\tag{12}\] together with the implied LP coefficients \((A_i, b_i, c_i)\) that underlie each \(T_i\). Two design choices distinguish benchmarks: how \(\mathcal{D}\) is sourced, and how each \(\phi_i\) is established.

7.0.0.2 Static-corpus and generator-based benchmarks.

A static-corpus benchmark fixes \(\mathcal{D}\) at release time as a distributed file; the size \(|\mathcal{D}|\) is bounded by the annotator budget invested during curation, and each \(\phi_i\) is typically obtained from a solver invocation or a human annotation. A generator-based benchmark replaces the fixed file with a generator \(\mathcal{G}\colon s \mapsto (T, \phi)\) that produces fresh instances on demand from a random seed \(s\); the realized benchmark on a chosen seed range \(S\) is \[\label{eq:generator95benchmark} \mathcal{D}_{\mathcal{G}}(S) \;=\; \{\,\mathcal{G}(s) : s \in S\,\}, \qquad |\mathcal{D}_{\mathcal{G}}(S)| = |S|,\tag{13}\] with \(|S|\) controllable at evaluation time. We construct one such \(\mathcal{G}\) in 3.1 where each \(\phi\) is established directly by the KKT theorem without solver invocation.

8 Limits of Single-Pass Natural-Language Rendering↩︎

The single-pass drafter is sufficient for the difficulty regimes evaluated in this paper. Two limitations are worth flagging.

Layout-level difficulty. Different drafter models produce different \((A,b)\) layouts in prose. Two common patterns are (i) a separated b-vector at the end of the description (“the total available capacity is \([b_1, \ldots, b_m]\)”) and (ii) inline RHS interleaved with each row (“Resource \(i\) usage: \([\ldots]\), availability \(= b_i\)”). At larger \((n,m)\) the inline pattern is materially harder for a downstream solver agent to parse correctly. A more careful drafter that controls layout explicitly, or a specification of NL style as part of the dataset card, would let evaluators isolate this from problem-size difficulty.

Single-domain scenarios. The current drafter prompt biases toward generic OR scenarios (production planning, resource allocation, diet). Domain-specific styles (e.g., supply-chain logistics with named locations, energy dispatch with grid topology) are not represented in the release. Specializing the drafter prompt is straightforward but is left to future work.

9 Dual-Agent Solver-Critic: Full Specification↩︎

3.2 gives the high-level loop of 11 . Here we provide the full system prompts of the solver agent (9.1) and the critic agent (9.2), together with the coverage analysis. The third agent in our pipeline, the natural-language drafter, has its system and user prompts in 6.4.

9.1 Solver Agent: System Prompt↩︎

9.2 Critic Agent: System Prompt↩︎

9.2.0.1 LP-modeling primer prepended to the solver prompt.

In addition to the solver and critic prompts above, we prepend a short curated primer to the solver’s system prompt by default. The primer names canonical failure modes (matrix transposition, sign errors, missing bounds), shows a worked example, and demonstrates the FINAL_ANSWER: output contract. The primer is part of the bundled A\(^{2}\)utoLPBench inference mode and is enabled in all experiments unless stated otherwise; ablations isolating its effect are out of scope for this paper.

9.2.0.2 Coverage analysis.

Let \(\mathcal{S}\) denote the success region (candidates within the verifier’s relative-error tolerance), and let \(\pi_{1} = \Pr_{y \sim p_{\mathcal{A}}(\cdot \mid T)}[\,y \in \mathcal{S}\,]\) be the solver’s single-shot success rate. We adopt three assumptions on the dual-agent protocol. (i) Critic faithfulness: when \(y_k \in \mathcal{S}\), \(\Pr[V_k = \mathrm{\small Agree} \mid y_k] = 1\). (ii) Critic conservatism: when \(y_k \notin \mathcal{S}\), \(\Pr[V_k = \mathrm{\small Disagree} \mid y_k] = 1\). (iii) Round non-degradation: conditional on rounds \(1,\ldots,k-1\) all failing, \(\pi_k \geq \pi_1\).

Under these assumptions, the \(K\)-round dual-agent protocol satisfies \[P_K = \Pr[y_{\mathrm{final}} \in \mathcal{S}] \;\geq\; 1 - \prod_{k=1}^{K}(1-\pi_k) \;\geq\; 1-(1-\pi_1)^K. \label{eq:coverage95app}\tag{14}\] The proof follows from (i) and (ii) jointly: \(V_k = \mathrm{\small Agree}\) holds if and only if \(y_k \in \mathcal{S}\), so the verdict is a faithful indicator of correctness. The loop therefore terminates at round \(k\) with \(y_{\mathrm{final}} \in \mathcal{S}\) exactly when \(y_k\) is the first round-\(k\) candidate inside \(\mathcal{S}\), and \(y_{\mathrm{final}} \notin \mathcal{S}\) holds if and only if every round produces \(y_k \notin \mathcal{S}\). Under (iii) the joint failure probability factorizes into per-round factors each at most \(1-\pi_1\), yielding \(\Pr[y_{\mathrm{final}} \notin \mathcal{S}] \le (1-\pi_1)^K\).

9.2.0.3 Empirical check against the bound.

We anchor the bound at two regimes from the main experiments.

Low-saturation regime. On AutoLPBench s40x40 with DeepSeek-V4 (10), we measure \(\pi_1 = 0.083\), so \(K=3\) gives a theoretical lower bound of \(1-(1-0.083)^3 \approx 0.229\). The observed dual-agent success rate is \(0.333\), which satisfies the bound with \(10.4\)pp of margin and is consistent with the picture that the bundled solver-critic loop has substantial room to lift when the underlying solver is well below ceiling.

High-saturation, same-distribution regime. On MAMO complex with MiMo-V2.5 paired same-model (2), we measure \(\pi_1 = 0.132\), so \(K=3\) gives a bound of \(0.346\), and the observed dual-agent success rate is \(0.245\), \(10.1\)pp below the bound. The bound is therefore not satisfied here. Both assumptions (i) and (ii) of 14 are meaningfully strained when the solver and critic share a distribution. Assumption (i) (faithfulness) fails when the critic disagrees on candidates that are already within tolerance, and these false-negative disagreements pull the realized success rate down; assumption (ii) (conservatism) fails when the critic agrees on candidates that are not within tolerance, and these false-positive agreements terminate the loop with an incorrect \(y_{\mathrm{final}}\). 11, item mamo_complex_43, contains a concrete trace of the false-positive failure mode (the critic returns Agree on an empty stdout). The combined effect is consistent with the \(7.5\)pp regression of A\(^{2}\)LP MiMo-V2.5+MiMo-V2.5 versus vanilla MiMo-V2.5 on saturated NL4OPT in 2.

We accordingly treat 14 as a design heuristic for choosing \(K\) given a target \(\pi_1\) and a deployment regime, and recommend reporting the realized \(P_K\) alongside the bound for any deployment rather than substituting the bound for the realized number.

9.2.0.4 Verdict-stratified output distribution.

A second consequence of the critic-faithfulness assumption is that the final verdict \(V\) stratifies outputs: cases ending in Agree have markedly higher success rate than those that reach the budget cap with Disagree. This calibration signal is reported as a runtime confidence indicator and is consistent with the trace-level evidence in 11.

10 Parametric Difficulty Envelope: Full Curve↩︎

4 of the main text reports the headline calibration numbers; here we provide the full per-stratum curve and the cross-distribution analysis across four solvers.

Four observations follow from the curves.

First, on DeepSeek-V4 the sol-rate is saturated at \(100\%\) for the four small strata (s2x3 through s10x12), degrades to \(\sim 95\%\) through the mid range (s15x15–s30x30), and falls to \(8.3\%\) at s40x40, an \(\sim 87\)pp cliff between adjacent strata. This is the kind of capability boundary that fixed benchmarks cannot surface: NL4OPT corresponds to the saturated easy end and MAMO complex sits in the mid range for current SOTA models, but no public LP benchmark contains items at the s40x40 size class.

Second, the 3-batch envelope widths for DeepSeek-V4 and MiMo-V2.5 are \(0\)pp at saturation, \(\le 3\)pp through the mid range, and widen to \(12\)–\(16\)pp around the s30x30–s40x40 cliff. This shape tracks the binomial standard deviation \(\sigma_{\hat{p}}=\sqrt{p(1-p)/32}\) and is therefore a property of the per-stratum sample size we chose to release, not an artifact of any particular seed range.

Third, on the cliff stratum (s40x40, MiMo-drafted) the four solvers split into two clusters: MiMo-V2.5 (\(91.7\%\)) and Qwen3.5 (\(87.5\%\)) versus DeepSeek-V4 (\(8.3\%\)) and Kimi-K2.5 (\(0\%\)). The split does not track simple drafter-equals-solver alignment, since Qwen3.5 (which did not draft these instances) is in the high cluster while Kimi-K2.5 is in the low cluster. One hypothesis consistent with the split is deployment-stack or prompt/tokenization proximity between the drafter and the high-cluster solvers (MiMo-V2.5 drafted these instances, and Qwen3.5 shares the Aliyun deployment stack with MiMo-V2.5). We do not attempt to formalize this from a single experiment, and we cannot rule out alternative explanations including training-data-family proximity, tokenizer convention, drafter-style memorization, or prompt-template artifact; the observation is reported as evidence that solver identity at the difficulty cliff matters and that the cliff is not a fixed property of \((n,m)\).

Fourth, on the DS-drafted batch the four solvers are essentially indistinguishable at every stratum. All four reach \(100\%\) at s15x15 and s20x20, all four sit at \(75\%\) at s30x30, and all four collapse to \(0\%\) at s40x40. Drafter style at large \((n,m)\) therefore swamps solver identity. Combined with the third observation, this gives us two complementary mechanisms by which the s40x40 cliff manifests, both of which a fixed-corpus benchmark cannot probe because it cannot vary either the drafter or the seed range.

11 Case Study: Critic-Driven Rescues↩︎

To understand why and when the bundled solver-critic loop helps, we examine the items on which a vanilla solver produces an incorrect answer but the A\(^{2}\)utoLPBench loop with the same solver-base recovers the correct answer (a “rescue”), and the converse (a “regression”). 6 summarizes the rescue/regression counts on the MAMO complex subset across the four A\(^{2}\)utoLPBench configurations from 2.

Two patterns are visible. First, all four configurations have non-negative net rescue: the bundled loop never makes more items wrong than it fixes. Second, on the weaker solver baseline (MiMo-V2.5, where vanilla sol-rate is \(13.2\%\)), pairing with a different-distribution critic (DeepSeek-V4) yields the largest net rescue (\(+8\), with zero regressions); on the stronger solver baseline (DeepSeek-V4, where vanilla sol-rate is \(26.4\%\)), the cross-model critic introduces some regressions (\(-2\)), and the same-model critic gives the cleanest net result.

11.0.0.1 Qualitative walkthroughs.

Below we trace the critic’s intervention on four representative rescues, using the MiMo-V2.5 \(\rightarrow\) MiMo-V2.5+DeepSeek-V4 configuration (which gave the largest net rescue) and the DeepSeek-V4 \(\rightarrow\) DeepSeek-V4+DeepSeek-V4 configuration (which yielded clean same-model rescues).

1. Empty output (item mamo_complex_46): the vanilla MiMo-V2.5 solver returned a code block whose execution produced no FINAL_ANSWER line; the candidate stdout was empty. The DeepSeek-V4 critic flagged this on iteration \(1\) (“the candidate code produced no output, so no final answer is provided”), the solver re-derived the formulation, and the second iteration printed \(\phi = 4813\), matching the certified ground truth.

2. Missing constraint (item mamo_complex_23): the problem statement listed two protein requirements (\(88\)g and \(144\)g, modeled as a maximum constraint plus a minimum constraint). The vanilla MiMo-V2.5 solver retained only the binding constraint and dropped the other. The DeepSeek-V4 critic disagreed twice with increasingly precise feedback (“the candidate enforces only one protein constraint and adds an unnecessary zero variable bound”), and the solver’s third attempt produced \(\phi \approx 23.84\) (within the \(1\%\) tolerance of the certified \(\phi = 24\)).

3. Wrong constraint type (item mamo_complex_41): the vanilla MiMo-V2.5 solver modeled a flow-balance constraint as \(\sum_{out} - \sum_{in} = \text{net}\) when the problem allowed slack on either side. The DeepSeek-V4 critic flagged that “total surplus (\(674\)) exceeds total deficit (\(398\)), making strict equality infeasible”; the solver switched to inequality constraints and produced \(\phi = 2114\).

4. Semantic gap (item mamo_complex_53): the vanilla MiMo-V2.5 solver assumed direct surplus-to-deficit transfers only, while the problem statement allowed indirect routes through intermediate regions. The DeepSeek-V4 critic caught the assumption explicitly (“the model restricts shipments to direct transfers from surplus to deficit regions only, but the problem allows arbitrary transfers including indirect routes”). The solver expanded the variable set on iteration \(2\) and produced \(\phi = 13079\).

The critic’s interventions cluster into three failure modes: (i) execution failure (item 1), (ii) constraint completeness or type errors (items 2 and 3), and (iii) high-level formulation gaps (item 4). Cross-model pairings appear to be especially strong on (ii) and (iii), where the critic catches semantic mismatches that the solver’s own distribution would judge as in-distribution. This is consistent with the rescue counts in 6 and with the asymmetry observed on A\(^{2}\)utoLPBench s40x40, where failures are dominated by numerical precision (a regime where same-distribution agreement is more reliable than cross-distribution disagreement).

11.1 Failure Analysis: OpenAI-GPT5.4 Regression Under A\(^{2}\)utoLPBench↩︎

The multi-solver leaderboard in 3 identifies one regression: OpenAI-GPT5.4 drops from \(15.09\%\) vanilla to \(13.21\%\) under A\(^{2}\)utoLPBench with the MiMo-V2.5 critic. To understand why, we audit the per-item iteration history.

11.1.0.1 Aggregate behaviour.

On the 53-item MAMO complex subset, the MiMo-V2.5 critic disagreed at least once on \(14\) items. Of those, only \(2\) (\(14\%\)) were eventually returned correctly by OpenAI-GPT5.4 after the disagreement; the remaining \(12\) either executed but produced the same numerical answer as the disagreed code, or produced new code that crashed with empty stdout. The iteration distribution skews toward \(K{=}1\) (\(39\) items, no disagreement) with a long tail of \(K{=}2\) (\(7\)) and \(K{=}3\) (\(7\)). OpenAI-GPT5.4 thus rarely engages the Refine path, and when it does not robustly incorporate the critic’s feedback.

11.1.0.2 Item-level pattern.

7 summarises three representative failure modes; see the listed instance IDs for full traces in the released JSONL log.

4pt

11.1.0.3 Interpretation.

Two structural observations are visible across these traces. First, OpenAI-GPT5.4 with reasoning_effort=none produces sound Propose-stage formulations efficiently but Refines them shallowly: the second iteration tends to perturb numerical coefficients without changing the constraint structure, even when the critic identifies a structural defect. Second, the prepended LP-optimization specification adds \(\sim 1{,}200\) tokens to the system prompt, and on mamo_complex_43 this shift was sufficient to push OpenAI-GPT5.4 onto a different (incorrect) Propose-stage code path even before the critic engaged.

The bundled solver-critic loop therefore exposes a capability threshold: the loop only adds value when the underlying solver can correctly act on a critic’s structural diagnosis. When the solver’s Refine policy is shallow (numerical perturbation rather than structural correction), critic feedback either fails to fix the error or, in rare cases, perturbs an already-correct vanilla Propose output. This finding is consistent with the rescue/regression asymmetry of 6: stronger solvers (DeepSeek-V4, Claude-Sonnet-4.6, Kimi-K2.5) yield larger net rescue counts, while weaker or low-reasoning configurations yield near-zero net effect or, in the OpenAI-GPT5.4 case, a small negative.

12 Extended Related Work↩︎

1 sketches A\(^{2}\)utoLPBench’s relationship to four lines of prior work: LP-from-text benchmarks, contamination-resistant evaluation, generator-based reasoning benchmarks, and solver-critic / self-refinement protocols. We expand each line here.

12.0.0.1 LP-from-text and OR-LLM benchmarks.

Early work in LP-from-text introduced human-curated word-problem collections paired with hand-labeled mathematical formulations or optimal values. NL4OPT [10] popularised the natural-language-to-LP formulation task on a \(1{,}101\)-item corpus; MAMO [11] and OptiBench [12] extended evaluation to end-to-end solver-code generation on similar-scale corpora, with OptiBench measuring an LLM’s ability to call an external solver and return the numerical optimum. The OPTIMUS series [13], [14], [25] packages a multi-agent pipeline that develops a model, writes solver code, evaluates the candidate, and self-improves; OptiMUS-0.3 reports state-of-the-art accuracy on (mixed-integer) LP from natural-language descriptions. Recent reasoning-LLM agents, including OR-LLM-Agent [26] and OptimAI [27], push this line by combining stronger solver agents with explicit reasoning traces. All of these systems evaluate against static-corpus test sets in the sense of 12 : the released \(\mathcal{D}\) is a fixed file with \(\phi_i\) obtained from a solver run or a human annotator. A\(^{2}\)utoLPBench differs in two structural respects: it ships a generator rather than a corpus, and it certifies \(\phi\) directly by the KKT theorem (2) without any solver invocation or human annotation step.

12.0.0.2 Generator-based and contamination-resistant evaluation.

DyVal [18] samples directed acyclic graphs of varying sizes, converts each graph to a natural-language reasoning task, and evaluates an LLM by querying the value of a designated node; difficulty is controlled by the graph parameters. NPHardEval [19] runs the same recipe on classical NP-hard problems (TSP and others), parameterizing by problem size and complexity class. Both demonstrate that fresh seed ranges chosen after a model’s training cutoff cannot have leaked into the training corpus, which is the structural guarantee A\(^{2}\)utoLPBench inherits. The broader contamination literature [15], [16], [28]–[31] documents inflated accuracy on memorised test items; recent surveys synthesise this evidence with detection and decontamination protocols [32]. Among prior systems, A\(^{2}\)utoLPBench is closest in spirit to DyVal and NPHardEval (parameterized generation, contamination-by-construction), and closest in subject to NL4OPT/MAMO/OptiBench (LP-from-text); the two threads have not previously been combined.

12.0.0.3 Solver-critic and self-refinement protocols.

The solver-critic loop of 3.2 is closely related to a line of self-refinement work. Self-Refine [20] and Reflexion [21] have a single LLM iteratively generate, critique, and revise its own output, using verbal feedback in place of weight updates; CRITIC [22] replaces the self-feedback with tool-grounded feedback (code interpreters, search engines), and multi-agent debate [33] replaces it with peer agents arguing different positions. Our protocol uses a separate critic agent on the same problem statement, which is most similar to multi-agent debate restricted to two participants. Importantly, recent critical surveys [23], [34] document that internal self-correction often fails or even degrades performance when the underlying task is already saturated for the solver, with success requiring some form of grounded external signal. 2’s same-distribution A\(^{2}\)LP MiMo-V2.5+MiMo-V2.5 underperforming vanilla on saturated NL4OPT (a \(7.5\)pp regression) is precisely an instance of that pattern; the empirical bound check in 9 formalises both directions of critic noise (false negatives and false positives) as the mechanism behind the gap.

12.0.0.4 Verifiable reasoning and process supervision.

A complementary line treats correctness as a property to be verified step-by-step. Math-Shepherd [35] trains a process reward model that scores each intermediate reasoning step on math problems, breaking the reliance on outcome-only reward; rStar-Math [36] pairs process supervision with Monte Carlo Tree Search to elicit deep reasoning in small models. Faithful chain-of-thought [37], Program-of-Thoughts [38], and program-aided language models [39] delegate the verifiable computation to a deterministic interpreter rather than the language model. A\(^{2}\)utoLPBench’s KKT certificate is a structural counterpart of these mechanisms in the LP setting: the optimum is verified once, in closed form, at construction time rather than as a learned reward. Inverse optimization [40] provides the mathematical foundation for the construction direction we use; our inverse-KKT generator instantiates the duality / complementary-slackness route to recovering an LP from a chosen optimum (see 3.1).

12.0.0.5 Agent-runnable benchmarks and tool-use.

Recent agent benchmarks pair concrete environments with end-to-end task evaluation: AgentBench [7] spans eight environments (OS, database, web, etc.); SWE-bench [9] evaluates GitHub-issue resolution; ToolBench/ToolLLM [8] measures large-scale API selection and invocation; WebArena [41], OSWorld [42], and \(\tau\)-bench [43] push toward realistic web, OS, and tool-agent-user interaction settings. These benchmarks inherit static-corpus structure on the task side: tasks are released once and become fixed targets. A\(^{2}\)utoLPBench’s Docker runtime (13) is most directly comparable to the agent-runnable surface these benchmarks ship; the difference is that the underlying tasks themselves are generator-produced, so a downstream evaluator can request fresh contamination-free batches at any time without coordinating with the benchmark authors.

13 Agent-Friendly Docker Environment and Usage Guide↩︎

To make A\(^{2}\)utoLPBench convenient for downstream agents and researchers, we ship a self-contained Docker image (autolpbench:latest) built on Ubuntu 22.04. The image bundles the inverse-KKT generator, scipy/PuLP solver libraries, the bundled solver-critic runtime, the 256-instance reference snapshot, and an AGENTS.md usage manual targeted at LLM-driven agents. A downstream agent can attach to the image with one command:

docker run --rm \;
  -e LLM_PROVIDER=deepseek \;
  -e LLM_API_KEY=$YOUR_KEY \;
  autolpbench:latest \;
  --mode autolpbench --strata s5x6,s10x12

The container exposes four entry points: (i) generating fresh batches with arbitrary \((n,m,\text{seed-range})\) for contamination-free evaluation; (ii) running vanilla or AutoLPBench-mode inference against any OpenAI- or Anthropic-compatible API; (iii) re-verifying any released item with scipy; (iv) returning per-item logs in JSONL alongside an aggregate summary. The image is built with Python 3.11 and pinned versions of numpy, scipy, pulp, openai, and anthropic; total size is approximately \(500\) MB.

13.0.0.1 AGENTS.md and tool-use skill plug-and-play.

The image ships its own usage manual at /workspace/AGENTS.md. The manual is written for LLM-driven agents to consume directly: it declares a fixed set of tool-use skills that the container exposes, each described in the JSON-schema format consumed by current tool-use APIs (OpenAI function calling, Anthropic tools, etc.). Any agent that supports tool use can read this manifest, register the skills, and run the benchmark without writing new glue code.

The four declared skills are: fetch_problem(stratum, index) which returns the natural-language description \(T\) and the matrix-shape hints \((n, m)\); solve(code) which executes a candidate Python program against the sandbox and returns its stdout and a parsed FINAL_ANSWER; verify(answer) which compares a candidate answer to the certified \(\phi\) and returns a Boolean plus the relative error; and generate_batch(n, m, seed_range) which produces fresh contamination-free instances on demand. A representative excerpt of the manifest is shown below; the full manifest is included in the released image and at the anonymous repository URL.

# AGENTS.md: A^2utoLPBench tool-use manifest

## Available skills
The Docker image exposes the following tool-use skills.
Any agent that supports tool use can register them directly.

- name: fetch_problem
  description: Return the next LP word problem in the chosen stratum.
  parameters:
    type: object
    properties:
      stratum: { type: string, enum: [s2x3, s3x4, ..., s40x40] }
      index:   { type: integer }
    required: [stratum, index]
  returns: { text: string, n: integer, m: integer }

- name: solve
  description: Execute candidate Python code in the sandbox.
  parameters:
    type: object
    properties:
      code: { type: string }
    required: [code]
  returns: { stdout: string, final_answer: number }

# ... verify, generate_batch follow the same schema.

This makes the deployment self-describing: an agent that has never seen A\(^{2}\)utoLPBench before can pull the image, read AGENTS.md, register the four skills, and complete the benchmark without external glue code or manual configuration.

13.0.0.2 Why the Docker integration matters for a generator-based benchmark.

A static-corpus benchmark only needs to ship a JSONL file. A generator-based benchmark must ship the generator together with a deterministic execution environment, otherwise downstream evaluators cannot reproduce the cross-batch calibration property. By packaging everything into a single image with pinned dependencies, we make the freshness and reproducibility guarantees of 1 actually obtainable in practice rather than promised in principle. The same image powers the cross-batch calibration experiment in 10: anyone with the image can regenerate the figure by running the entry-point with three different seed ranges.

References↩︎