Skip to content

EvoOptiGraph: Weakness-Driven Coevolution via Graph-Based Structural Generation for Optimization Modeling

🕒 Published (v1): 2026-06-25 03:57 UTC · Source: Arxiv · link

Why this paper was selected

Weakness-driven coevolution loop for LLM optimization modeling; self-improving agentic pipeline with structural diversity generation

Ask a follow-up

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

💬 Ask ChatGPT✦ Ask Claude

TL;DR

EvoOptiGraph is a closed-loop coevolution framework that jointly adapts training data and model parameters for natural-language-to-optimization (MILP) modeling. It represents MILPs as attributed bipartite graphs, applies genetic operators to generate structurally diverse instances, then uses SHAP-based weakness profiling to steer further generation toward the model's current failure modes, followed by RLVR fine-tuning. An 8B model trained this way surpasses larger generalist models and multi-agent baselines on six OR benchmarks.

Problem

Training data for NL→MILP modeling lacks structural diversity — existing pipelines perturb coefficients/text within fixed templates rather than altering problem topology — and training pipelines are static, providing no mechanism to identify or target structural regimes where the model currently fails.

Method

Each MILP is encoded as an attributed bipartite graph \(G = (V, E, A)\) with nodes \(V = V_{\text{con}} \cup V_{\text{var}}\), where edge weights store constraint coefficients and nodes store bound/type metadata. Starting from 53 expert-designed seed families, crossover (subgraph exchange between compatible parent instances) and mutation (parameter, structural, and scale edits) generate a diverse candidate pool; each candidate is validity-checked and solver-verified before entering training.

Training is two-stage: 1. SFT warm-up on an initial population \(D_0\) of 5,000 graph-derived instances. 2. Weakness-driven RLVR: the current model is evaluated on a held-out validation set; structural feature vectors \(\phi(G)\) (size, sparsity, topology, coefficient statistics) are extracted and an XGBoost classifier predicts correctness. SHAP values on error cases yield a weakness vector \(w\), where \(w_k = \frac{1}{|E|}\sum_{i \in E} \text{SHAP}_{i,k}\). The evolutionary fitness function \(f(G) = \beta\tilde{f}_{\text{diff}} + \gamma\tilde{f}_{\text{div}} + \delta\tilde{f}_{\text{weak}}\) activates the weakness-alignment term \(\tilde{f}_{\text{weak}} = \text{cosine\_similarity}(\phi(G), w)\) to bias new generation toward failure-prone structures. GRPO optimizes the policy on the resulting \(D_{\text{RL}}\) with a staged reward \(R = R_{\text{process}} + R_{\text{solvable}} + R_{\text{proximity}} + R_{\text{correctness}} \in [0,1]\).

Key Contributions

  • Closed-loop data–model coevolution: training distribution adapts each iteration to the model's evolving failure modes rather than being fixed.
  • Graph-based MILP generator with validity-preserving genetic operators (crossover + three-level mutation), enabling structural-level evolution beyond parameter perturbation.
  • SHAP-driven weakness profiling that maps graph structural features to observed errors and produces a prioritization vector for targeted data synthesis.
  • Multi-stage verifiable reward design for RLVR that rewards executability, feasibility, numerical proximity (\(\text{relerr} < 10\%\)), and exact optimality (\(\text{relerr} \leq 10^{-4}\)).

Results

  • Overall: EvoOptiGraph (8B) achieves 78.1% macro-average Pass@1 across six benchmarks, the best among all compared methods.
  • vs. zero-shot LLMs: outperforms GPT-4o (68.0%), DeepSeek-V3 (73.3%), Qwen3-32B (65.3%), Qwen2.5-72B-Instruct (66.6%).
  • vs. agentic methods: outperforms OptiMUS-v0.3 (70.1%), CoT (51.4%), CoE (64.6%).
  • vs. fine-tuned LLMs: outperforms ORLM-8B (65.5%), LLMOPT-14B (58.6%*), OptMATH-32B (78.1% tied at best, with EvoOptiGraph reaching 96.7/98.0 on MAMO subsets vs. OptMATH's 95.9/89.9).
  • Data diversity: generated instances achieve 66.93% structural similarity to seed families vs. 93.04% for OptMATH (lower = more diverse).
  • Ablation: removing coevolution (All-SFT) drops average to 68.5% (↓9.6%); All-RL without structural evolution drops to 63.4% (↓14.7%).

Limitations

  • Back-translation quality depends on an external LLM (DeepSeek-V3 / Claude-3), introducing cost and a potential quality bottleneck.
  • Weakness analysis requires a held-out validation set with graph representations and ground-truth outcomes; this may not be available in all deployment scenarios.
  • Evaluation is restricted to MILPs solvable by Gurobi; non-linear or stochastic programs are out of scope.
  • SHAP-derived weakness vectors describe correlations between structural features and failures, not causal relationships; the paper explicitly notes this.
  • OptMATH and LLMOPT results come from different (uncleaned) dataset versions, making direct comparison imprecise.

Relevance to Agentic AI / LLM Agents

EvoOptiGraph directly competes with and outperforms multi-agent LLM frameworks (OptiMUS, Chain-of-Experts) on optimization modeling by replacing inference-time orchestration with a data-centric training loop, demonstrating that structured training distribution adaptation can substitute for agentic reasoning scaffolds at lower inference cost. The weakness-driven coevolution pattern — diagnosing model failures, synthesizing targeted training data, and iterating — is a general recipe for self-improving LLM agents beyond this domain. The RLVR + GRPO training loop with verifiable rewards connects directly to the broader line of work on RL-trained reasoning agents (DeepSeek-R1, etc.), showing how solver-based verification can replace learned reward models. For researchers tracking agentic AI, the key takeaway is that adaptive data generation can be more compute-efficient than scaling model size or adding inference-time agent layers.