Skip to content

A\(^{2}\)utoLPBench: An Auto-Generated, Agent-Friendly LP Benchmark via Inverse-KKT Construction

🕒 Published (v1): 2026-07-02 13:18 UTC · Source: Arxiv · link

Why this paper was selected

Auto-generated LP benchmark via inverse-KKT; addresses contamination and difficulty control for LLM evals

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

A²utoLPBench replaces static LP-from-text corpora with an on-demand generator that constructs LP instances via inverse-KKT, yielding mathematically certified ground truth without solver calls or human annotators. A bundled dual-agent solver-critic baseline (Propose/Audit/Refine) and a Docker image with an AGENTS.md manifest let any tool-use-capable LLM agent plug in and score itself in one command. The benchmark's difficulty is a continuous knob set by problem dimensions \((n, m)\), making it a measurement instrument rather than a fixed snapshot.

Problem

Existing LP-from-text benchmarks (NL4OPT: 287 items; MAMO: 211/652 items) are static corpora with four structural limitations: (i) size is bounded by annotator budget, (ii) released items leak into future training corpora, (iii) difficulty is frozen at release and cannot track improving models, and (iv) there is no agent-runnable evaluation surface—each benchmark requires bespoke harness code. These limitations cannot be patched by curation; they follow from the corpus-vs-generator design choice.

Method

Inverse-KKT construction (Auto part). Sample primal \(x \in \mathbb{Z}^n_{>0}\), full-rank \(A \in \mathbb{Z}^{m \times n}\), and dual \(\lambda \in \mathbb{R}^m_{>0}\); then set $\(c = A^\top \lambda, \quad b = Ax, \quad \phi = c^\top x.\)$ Because \(x > 0\) and \(\lambda > 0\), complementary slackness forces \(\mu = 0\) and all KKT conditions are satisfied by construction, so \(\phi\) is the certified optimum with no solver invocation. An LLM drafter converts each \((A, b, c, x, \phi)\) pair into a natural-language word problem; coefficient fidelity is verified by string-matching every entry of \(A\), \(b\), \(c\) against the rendered text, with resampling on mismatch.

Solver-critic baseline (Agent part). A two-agent loop operates over \(K\) rounds: - Propose: solver agent \(\mathcal{A}\) generates candidate Python program \(y_1 \sim p_\mathcal{A}(\cdot \mid T)\). - Audit: critic agent \(\mathcal{C}\) emits verdict \(V_k \in \{\text{AGREE}, \text{DISAGREE}\}\) and rationale \(r_k\). - Refine: if \(V_k = \text{DISAGREE}\) and \(k < K\), solver produces \(y_{k+1} \sim p_\mathcal{A}(\cdot \mid T, r_k)\).

The loop terminates at the first AGREE or at \(k = K\) (default \(K = 3\)).

Docker runtime. A self-contained image (autolpbench:latest) bundles the generator, KKT verifier, solvers, and an AGENTS.md manifest that declares four tool-use skills (problem fetch, solver invocation, KKT verification, batch generation) in JSON-schema format compatible with OpenAI function-calling and Anthropic tools APIs.

Key Contributions

  • Unlimited, contamination-resistant LP instance supply via inverse-KKT generator parameterized by \((n, m)\) and seed range.
  • Mathematically certified ground truth by KKT optimality theorem (Theorem A.2), removing solver-precision drift and human annotation error.
  • Parametric, reproducible difficulty: eight strata from \((2,3)\) to \((40,40)\); independent batches agree to within 3 pp off the performance cliff.
  • Bundled dual-agent solver-critic baseline transferable to external benchmarks (NL4OPT, MAMO).
  • Agent-native Docker image with AGENTS.md enabling plug-and-play evaluation with a single docker run command.
  • 256-instance reference snapshot stratified across eight size classes (32 instances each), with all instances verified against scipy's linprog at \(\tau = 10^{-4}\).

Results

  • Calibration sweep (DeepSeek-V4): sol-rate declines smoothly from 100% at stratum \((2,3)\) to 8.3% at \((40,40)\); batch-to-batch noise \(\leq 3\) pp off the cliff across three independent seed ranges.
  • Same-model critic uplift on A²utoLPBench: DeepSeek-V4+DeepSeek-V4 lifts sol-rate at \((40,40)\) from 8.3% to 33.3% (+25 pp).
  • External transfer — MAMO complex: cross-model pairing MiMo-V2.5+DeepSeek-V4 critic reaches 28.3% from 13.2% vanilla baseline (+15.1 pp); Claude-Sonnet-4.6 gains +11.3 pp.
  • External transfer — NL4OPT: already saturated at 98.11% vanilla; same-model MiMo-V2.5+MiMo-V2.5 loses 7.5 pp due to critic over-disagreement on correct code.
  • External transfer — MAMO easy: gains are smaller and direction-dependent across pairings.

Limitations

  • Single-pass NL rendering may mis-render coefficients for large or complex instances; only string-level coefficient matching is used as a fidelity check, not semantic verification.
  • External-benchmark experiments use a fixed prefix of 53 items per cell rather than a random subsample, which limits generalizability claims.
  • Same-model critic can degrade performance on saturated benchmarks by over-disagreeing on already-correct solver code.
  • The released 256-instance snapshot is itself vulnerable to future training-data contamination; the contamination-resistance guarantee applies only to freshly drawn seed ranges.
  • Difficulty parameterization via \((n, m)\) dimensions may not capture all real-world LP complexity (e.g., degenerate problems, special structure).

Relevance to Agentic AI / LLM Agents

A²utoLPBench directly advances evaluation infrastructure for tool-use agents: its Docker + AGENTS.md design is a concrete template for making any benchmark natively consumable by LLM agents without bespoke harness code, addressing a known bottleneck in agent evaluation pipelines. The inverse-KKT construction solves the ground-truth-certification problem for a class of quantitative reasoning tasks without requiring external oracles, a pattern reusable for other structured optimization domains. The Propose/Audit/Refine solver-critic protocol is an empirically validated instance of multi-agent self-refinement, with clear ablations showing where cross-model critic pairings outperform same-model ones. The contamination-resistance-by-construction property is directly relevant to the benchmarking-under-data-leakage problem that affects all long-lived agent evaluation suites.