OptiSkill: A Hierarchical and Evolving SkillBank for LLM-Based Optimization Modeling¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/rachhhhing/OptiSkill
Area: LLM Reasoning
Keywords: Operations Research Modeling, Hierarchical SkillBank, Trajectory-to-Skill Distillation, Batch-Level Test-Time Evolution, Reliability-Aware Retrieval
TL;DR¶
OptiSkill establishes a hierarchical and evolving SkillBank for frozen LLMs—combining global formulation strategies with local step-level error-prevention experiences distilled from solver-verified trajectories and safely updated via batch-level admission checks—achieving superior formulation accuracy across eight diverse OR benchmarks.
Background & Motivation¶
Automated operations research (OR) modeling is essential for industrial decision systems such as logistics routing, supply-chain management, production scheduling, and resource allocation. In practice, decision problems are articulated in ambiguous, narrative natural language, whereas mathematical optimization solvers (e.g., Gurobi, CPLEX) demand strictly specified, mathematically sound program formulations spanning decision variables, objectives, and linear/non-linear constraints. Although large language models (LLMs) demonstrate significant potential in parsing problem requirements and translating natural language into solver code, domain fine-tuned models (e.g., ORLM, LLMOPT, SIRL) incur heavy computational overhead and expensive dataset synthesis whenever mathematical domains expand. Conversely, prompt-based agentic workflows (e.g., OptiMUS, Chain-of-Experts) tackle each problem instance in isolation without retaining reusable modeling experience, causing models to commit the same subtle formulation blunders repeatedly across different problems.
The core tension behind these persistent modeling failures lies in the representation of external memory: effective OR formulation cannot rely merely on full-problem few-shot demonstrations or unstructured narrative reflections, but requires modular, reusable, and composable modeling skills that decouple from superficial problem narratives while dictating concrete mathematical decisions. Prior retrieval-augmented OR frameworks—such as LEAN-LLM-OPT with few-shot exemplars, OptiTree with high-level thought trees, or AlphaOPT with unstructured insight records—primarily store passive reference materials. When facing error-prone formulation steps such as discrete variable domain specifications, Big-M parameter bounds, or subtour elimination constraints, such passive references either fail to provide exact procedural guidance or introduce irrelevant contextual noise that misleads the LLM into generating infeasible programs.
This paper tackles the challenge by converting solver-verified positive and negative modeling trajectories into structured, actionable skill units organized in a two-level hierarchy. To capture problem-level abstractions, the framework extracts Global Strategies that provide reusable procedural skeletons; to guard against fragile local pitfalls, it extracts Step Experiences that specify high-risk trigger contexts and corrective modeling guidance. Core idea: OptiSkill establishes a hierarchical and evolving non-parametric SkillBank that distills dual-level skills from verified modeling trajectories and continually refines knowledge at test time through a buffered, batch-validated evolution mechanism with strict support, repair, and regression safeguards.
Method¶
Overall Architecture¶
The OptiSkill framework consists of three integrated modules: offline trajectory-to-skill distillation, skill-augmented formulation generation, and stable test-time SkillBank evolution. During offline construction, a teacher model generates multiple candidate formulation trajectories over a diverse corpus of optimization problems, each validated via Gurobi solver execution. Successful trajectories and paired counter-trajectories are distilled into structured Global Strategies and Step Experiences, followed by semantic deduplication and merging into category-specific sub-banks. During inference, OptiSkill routes the input problem to its dominant OR category, conducts semantic matching to retrieve at most one strategy and two experiences, and injects them as structured guidance into the frozen LLM formulator. During test-time execution, failed formulations trigger solver-guided self-refinement; successful repairs are diagnosed by error type and accumulated in an inactive candidate pool. At the end of each test batch, candidates undergo rigorous support, repair, and regression verification before entering the active SkillBank alongside dynamic reliability score updates.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Natural-Language Problem Input"] --> B["Category Routing & Hierarchical Skill Retrieval<br/>Coarse Category Filtering + Top-K Semantic Matching"]
B --> C["Dual-Level Skill-Augmented Formulation<br/>Global Strategy Skeleton + Step Experience Guardrails"]
C --> D{"Backend Solver Execution & Correctness Verification"}
D -->|Correct Solution| E["Output Final Program Formulation & Optimal Solution"]
D -->|Failure / Infeasibility| F["Solver-Guided Self-Refinement & Failure Diagnosis<br/>Missing vs Misleading Skill Attribution"]
F --> G["Candidate Buffering & Batch-Level Stable Evolution<br/>Support Threshold + Repair & Regression Rate Validation"]
G --> H["Dynamic Reliability Scoring & SkillBank Update"]
H -.->|Continual Knowledge Enhancement| B
Key Designs¶
1. Category Routing & Hierarchical Skill Retrieval: Partitioning Knowledge Granularity to Suppress Cross-Domain Noise
When retrieving across an unstructured, flat knowledge base, models frequently retrieve inappropriate domain rules (e.g., imposing flow conservation constraints on a standard knapsack selection problem). OptiSkill mitigates this by defining eight coarse OR problem categories \(\mathcal{C}\) (allocation, assignment, selection, flow, time_planning, routing, scheduling, and special mathematical structures), maintaining an independent sub-bank \(\mathcal{B}_c\) for each category \(c \in \mathcal{C}\) such that the full SkillBank is \(\mathcal{B} = \{\mathcal{B}_c\}_{c \in \mathcal{C}}\). Given an input problem \(q\), OptiSkill first prompts the LLM to identify the dominant category \(\hat{c}\), strictly restricting subsequent retrieval to \(\mathcal{B}_{\hat{c}}\). Within the target sub-bank, semantic matching computes similarity over the strategy procedure field and experience trigger field via \(\phi(s)\):
$\(S_q(\mathcal{B}) = \text{TopK}_{s \in \mathcal{B}_{\hat{c}}} \text{sim}(q, \phi(s))\)$
The retrieval imposes a strict cap of at most 1 strategy and at most 2 experiences, permitting empty sets if no candidate shows sufficient semantic affinity, thereby preventing irrelevant memory injection.
2. Dual-Level Skill-Augmented Formulation: Synchronized Macro-Skeleton and Micro-Check Guidance
Relying exclusively on high-level procedures leaves models vulnerable to low-level algebraic oversights, whereas isolated rule fragments fail to provide holistic structure. OptiSkill addresses this by coupling complementary knowledge representations. A Global Strategy encapsulates problem-level structure via summary (applicable conditions) and procedure (ordered high-level modeling sequence, e.g., defining period-indexed decision variables, establishing state-transition inventory balance, and formulating cost objectives). A Step Experience targets local, high-risk error scenarios through trigger (contextual alert signal) and guidance (corrective formulation action, such as applying MTZ subtour elimination constraints exclusively to pairs excluding the starting node in a TSP). The frozen LLM consumes these retrieved skills within prompt wrappers instructing it to output reasoning chains under <think>, complete mathematical specifications under <model>, and executable Gurobi Python code under <python>, significantly reducing fragile modeling lapses.
3. Solver-Guided Self-Refinement & Failure Diagnosis: Isolating Knowledge Defects from Transient Code Errors
When an initial formulation fails verification against ground-truth solver solutions, OptiSkill engages a self-refinement loop for up to 3 turns leveraging raw solver diagnostics. When a problem is successfully resolved through refinement, the system executes an automated diagnostic prompt to categorize the failure into six mutually exclusive classes: experience_misleading (overly broad trigger or invalid corrective guidance), strategy_misleading (ill-fitting or incomplete global procedure), experience_miss (absence of a necessary local check), strategy_miss (absence of an overarching procedural skeleton), code_error_only (implementation flaw with correct mathematical modeling), or unresolved. Only knowledge-attributable failures produce candidates: repair candidates (\(\mathcal{A}^r_b\)) for misleading skills and new candidates (\(\mathcal{A}^n_b\)) for missing skills. Crucially, all candidates are buffered into an inactive candidate pool \(\mathcal{A}_b = \mathcal{A}^n_b \cup \mathcal{A}^r_b\), completely preventing volatile instant updates caused by single-instance noise.
4. Candidate Buffering & Batch-Level Stable Evolution: Strict Multi-Barrier Admission and Reliability Tracking
To ensure that test-time updates genuinely expand capabilities without inducing catastrophic regression, OptiSkill schedules updates in fixed batches of 200 evaluation problems. At batch boundaries, candidates are clustered and deduplicated. A new candidate is admitted to the active SkillBank only if it achieves a minimum support threshold across multiple distinct questions \(\text{supp}(s) \ge \delta_s\) (default \(\delta_s=5\)) and is confirmed non-redundant with existing active skills:
$\(\mathcal{V}^n_b = \{s \in \mathcal{A}^n_b : \text{supp}(s) \ge \delta_s, s \not\sim \mathcal{B}_b\}\)$
Similarly, a repair candidate is merged and admitted only if it satisfies both a repair success rate \(\rho_{\text{rep}}(s) \ge \delta_r\) (default 0.6 on historically failed instances) and an anti-regression rate \(\rho_{\text{reg}}(s) \ge \delta_g\) (default 0.8 on instances previously solved by the parent skill). In parallel, active skills track operational statistics to maintain a dynamic reliability score:
$\(\text{score}(s) = \text{pos}(s) - \alpha \cdot \text{neg}(s)\)$
where \(\text{pos}(s)\) increments upon correct initial formulations, \(\text{neg}(s)\) penalizes misleading diagnoses (\(\alpha=1.5\)), and skills are classified into High, Medium, Low, or Risky tiers. Skills persistently categorized as Risky without successful remediation are pruned from the SkillBank.
Benchmark & Evaluation Protocol¶
The framework is rigorously evaluated across eight prominent operations research modeling benchmarks spanning linear programming (LP), integer programming (IP), mixed-integer linear programming (MILP), non-linear programming (NLP), and second-order cone programming (SOCP): - NL4Opt: 213 standard natural-language linear programming word problems; - MAMO: Stratified into EasyLP (545 instances) and ComplexLP (111 instances) testing structural complexity; - NLP4LP: 178 human-authored optimization problems spanning classical LP, MILP, and MINLP formulations; - ComplexOR: 18 challenging real-world industrial optimization problems requiring intricate integer logic; - IndustryOR: 42 practical optimization problems from diverse industrial supply-chain and operations domains; - OptiBench: 403 comprehensive optimization problems covering broad structural distributions; - OptMATH: 166 complex, long-context optimization problems featuring non-linear and conic constraints.
Evaluations measure Pass@1 accuracy (%) against exact reference objective values verified by Gurobi 12.0.3 with an error tolerance of 0.05. Experiments run on an 8-GPU NVIDIA H20 (96GB) cluster.
Key Experimental Results¶
Main Results¶
OptiSkill demonstrates substantial performance gains over zero-shot base models, domain fine-tuned models, and competitive agentic architectures across eight benchmarks. The table below presents the primary comparative Pass@1 results (%):
| Category / Model | NL4OPT | MAMO Easy | MAMO Cpx. | NLP4LP | OptiB. | CpxOR | IndOR | OptM. | Macro Avg. |
|---|---|---|---|---|---|---|---|---|---|
| Zero-shot LLMs | |||||||||
| GPT-5 | 71.8 | 92.7 | 48.6 | 87.6 | 76.4 | 61.1 | 71.4 | 35.5 | 68.1 |
| DouBao-Seed-2.0 | 73.2 | 84.2 | 56.8 | 87.1 | 79.4 | 44.4 | 66.7 | 33.1 | 65.6 |
| DeepSeek-V4 | 78.4 | 93.6 | 52.3 | 92.1 | 86.6 | 55.6 | 69.1 | 39.8 | 70.9 |
| DeepSeek-R1 | 76.1 | 89.7 | 48.6 | 90.4 | 78.9 | 55.6 | 64.3 | 34.9 | 67.3 |
| Qwen2.5-72B | 74.6 | 95.2 | 41.4 | 88.2 | 54.6 | 44.4 | 54.8 | 15.1 | 58.5 |
| Fine-tuned LLMs | |||||||||
| ORLM | 73.8 | 90.4 | 59.5 | 76.4 | 61.8 | 50.0 | 42.9 | 2.6 | 57.2 |
| LLMOPT | 80.3 | 89.5 | 44.1 | 73.4 | 53.8 | 35.3 | 29.0 | 12.5 | 52.2 |
| SIRL | 94.8 | 98.0 | 81.1 | 96.6 | 89.6 | 44.4 | 50.0 | 27.1 | 72.7 |
| StepORLM | 96.7 | 95.4 | 79.3 | 97.2 | 88.6 | 50.0 | 52.4 | 13.9 | 71.7 |
| Agentic Methods (DouBao-Seed-2.0) | |||||||||
| CoE | 78.4 | 91.6 | 63.1 | 94.3 | 84.4 | 50.0 | 64.3 | 34.9 | 70.1 |
| OptiMUS | 75.1 | 88.4 | 45.9 | 89.9 | 84.6 | 44.4 | 61.9 | 31.9 | 65.3 |
| OptiTree | 76.5 | 92.1 | 62.2 | 91.0 | 83.1 | 44.4 | 69.0 | 38.6 | 69.6 |
| AlphaOPT | 75.6 | 91.4 | 55.0 | 93.3 | 85.1 | 55.6 | 66.7 | 36.1 | 69.9 |
| ReLoop | 76.1 | 91.2 | 62.2 | 92.7 | 84.9 | 50.0 | 59.5 | 32.5 | 68.6 |
| OptiSkill (Static) | 78.9 | 90.8 | 64.0 | 93.8 | 85.4 | 61.1 | 71.4 | 40.4 | 73.2 |
| Agentic Methods (DeepSeek-V4) | |||||||||
| CoE | 78.9 | 96.1 | 57.7 | 92.1 | 82.6 | 50.0 | 66.7 | 39.2 | 70.4 |
| OptiMUS | 77.5 | 88.4 | 38.7 | 88.2 | 83.1 | 44.4 | 59.5 | 31.3 | 63.9 |
| OptiTree | 80.3 | 93.9 | 60.4 | 93.8 | 86.9 | 50.0 | 71.4 | 41.0 | 72.2 |
| AlphaOPT | 76.1 | 95.8 | 54.1 | 90.4 | 80.6 | 55.6 | 64.3 | 39.2 | 69.5 |
| ReLoop | 74.7 | 91.6 | 56.8 | 89.3 | 79.9 | 55.6 | 66.7 | 27.1 | 67.7 |
| OptiSkill (Static) | 80.8 | 94.3 | 56.8 | 94.9 | 87.6 | 61.1 | 73.8 | 41.6 | 73.9 |
Ablation Study¶
To dissect the individual contributions of the dual-level skill components and the necessity of solver-verified admission checks, systematic ablations were conducted as reported below:
| Configuration / Variant | NL4OPT | MAMO Easy | MAMO Cpx. | NLP4LP | OptiB. | CpxOR | IndOR | OptM. | Avg. | Note |
|---|---|---|---|---|---|---|---|---|---|---|
| DouBao-Seed-2.0 Backbone | ||||||||||
| OptiSkill (Full Static) | 78.9 | 90.8 | 64.0 | 93.8 | 85.4 | 61.1 | 71.4 | 40.4 | 73.2 | Full static SkillBank |
| w/o strategy | 76.5 | 86.1 | 57.7 | 88.8 | 80.2 | 50.0 | 69.1 | 36.1 | 68.0 | Severe loss of macro skeleton (-5.2%) |
| w/o experience | 82.6 | 92.7 | 61.3 | 96.6 | 84.9 | 55.6 | 64.3 | 32.5 | 71.3 | Performance degrades on complex tasks (-1.9%) |
| Evolved SkillBank | 79.81 | 95.41 | 67.57 | 94.38 | 87.34 | 61.11 | 73.81 | 48.80 | 76.03 | Test-time evolution gain (+2.83%) |
| Evolved w/o Checks | 73.24 | 93.58 | 62.16 | 96.63 | 88.83 | 44.44 | 71.43 | 48.19 | 72.31 | Noise contamination without admission checks (-3.72%) |
| DeepSeek-V4 Backbone | ||||||||||
| OptiSkill (Full Static) | 80.8 | 94.3 | 56.8 | 94.9 | 87.6 | 61.1 | 73.8 | 41.6 | 73.9 | Full static SkillBank baseline |
| w/o strategy | 80.3 | 94.1 | 55.9 | 93.3 | 83.1 | 55.6 | 71.4 | 43.4 | 72.1 | Lack of global guidance drops avg by 1.7% |
| w/o experience | 79.3 | 94.7 | 52.3 | 91.0 | 84.1 | 55.6 | 78.6 | 39.2 | 71.8 | Drops on complex datasets (-2.0% avg) |
| Evolved SkillBank | 84.98 | 95.05 | 57.66 | 96.07 | 91.32 | 61.11 | 76.19 | 48.80 | 76.39 | Gains on OptMATH (+7.2%) and NL4OPT (+4.2%) |
| Evolved w/o Checks | 84.04 | 94.50 | 53.15 | 92.70 | 90.82 | 50.00 | 69.05 | 50.60 | 73.11 | Unguarded evolution drops avg by 3.28% |
Key Findings¶
- Global strategies govern foundational modeling stability: Removing strategies (
w/o strategy) induces an immediate drop across virtually every benchmark, reducing DouBao-Seed-2.0 performance from 73.2% to 68.0% (-5.2%) and causing an 11.1% drop on ComplexOR. This highlights the indispensable role of global procedural steps in complex mathematical formulation. - Step experiences prevent critical failures in complex scenarios: Removing experiences (
w/o experience) yields slight gains on simpler LP benchmarks (e.g., +3.8% on NL4OPT) by eliminating benign retrieval noise, but triggers catastrophic regressions on challenging real-world industrial benchmarks: -7.1% on IndustryOR and -7.8% on OptMATH under DouBao-Seed-2.0, confirming that specific anti-error guardrails are pivotal for fragile constraint formulation. - Solver-verified admission safeguards are essential against memory contamination: Discarding admission checks during evolution (
w/o Checks) plummets performance by 3.28% on DeepSeek-V4 and 3.72% on DouBao-Seed-2.0, dropping below static SkillBank baselines. Unchecked LLM-generated rules introduce subtle hallucinated constraints that corrupt downstream retrieval. - Superior computational and token efficiency: OptiSkill achieves a far superior efficiency profile compared to multi-agent alternatives like CoE or ReLoop. Under DeepSeek-V4, static OptiSkill requires only 34.13 seconds and 5,964 tokens per problem (36.57s and 6,176 tokens with test-time evolution), delivering higher accuracy at a fraction of the computational footprint.
Highlights & Insights¶
- Structured trajectory-to-skill distillation: OptiSkill moves beyond storing whole few-shot exemplars or unstructured linguistic reflections by contrasting successful and failed solver trajectories to extract discrete, actionable, and reusable rule units.
- Disciplined two-level knowledge anatomy: Factoring formulation knowledge into macro Global Strategies (procedural order) and micro Step Experiences (trigger-to-action warning rules) perfectly reflects the dual cognitive demands of operations research modeling.
- Safeguarded test-time evolution paradigm: The introduction of an inactive candidate pool, batch-level cross-problem support thresholds, and non-regression checks provides a robust template for self-evolving agent memory without parameter fine-tuning.
Limitations & Future Work¶
- Initial coverage bias toward LP/MILP: The distillation corpus is primarily centered around linear and mixed-integer linear programming; specialized non-linear paradigms such as MINLP remain sparse due to insufficient repeated evidence required by batch support thresholds.
- Sensitivity to single-label category misrouting: The framework currently employs deterministic single-label routing; empirical error audits show an 8.3% classification error rate, of which 60.0% directly result in downstream formulation failures.
- Future directions: Investigating soft multi-label routing for multifaceted industrial models, expanding non-linear skill synthesis, and incorporating solver runtime and numerical conditioning metrics into the feedback loop.
Related Work & Insights¶
- vs Domain-Tuned Models (ORLM / LLMOPT / SIRL / StepORLM): Fine-tuned models internalize OR syntax into model weights, excelling on standard LP benchmarks but suffering from high retraining costs and catastrophic forgetting; OptiSkill maintains frozen LLMs and provides transparent, interpretable, and continually expandable external knowledge.
- vs Multi-Agent Workflow Frameworks (CoE / OptiMUS): Multi-agent pipelines rely on heavy multi-turn conversational consensus, accumulating massive token overhead while discarding learned experience upon session completion; OptiSkill crystallizes verified experience into reusable assets, lowering latency while achieving superior accuracy.
- vs Memory-Augmented OR Systems (LEAN-LLM-OPT / OptiTree / AlphaOPT): Exemplar-based and tree-based memory frameworks lack fine-grained anti-error rules or test-time evolution safety checks; OptiSkill combines explicit trigger-guidance pairs with regression-tested batch evolution, delivering state-of-the-art robustness.
Rating¶
- Novelty: ⭐⭐⭐⭐⭐ [Pioneering integration of contrastive trajectory distillation, hierarchical strategy-experience decomposition, and regression-safeguarded batch evolution for OR modeling]
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ [Extensive evaluation across 8 benchmarks, diverse model backbones, full component ablations, sensitivity analyses, and error audits]
- Writing Quality: ⭐⭐⭐⭐⭐ [Exemplary clarity, rigorous mathematical formulation, and thorough transparency regarding algorithmic design and implementation details]
- Value: ⭐⭐⭐⭐⭐ [Delivers an immediately applicable, high-efficiency, and transparent architectural pattern bridging frozen foundation models and rigorous industrial optimization]