Large language models offer a promising technique for translating natural-language optimization problems into solver code, but their reliability remains constrained by the quality of template retrieval. While recent structured methods improve over flat prompting through hierarchical taxonomy search, their traversal rules remain fixed or LLM-driven at inference time, leaving retrieval unable to improve from past successes and failures. This motivates treating template retrieval as a policy that can be learned from modeling experience, rather than as a static inference-time rule. We propose COMPASS, a policy-amortized framework for retrieving optimization templates in LLM-based solver modeling, which represents the template library as a directed acyclic graph and formulates retrieval as a sequential decision process over template nodes. A deep Q-network learns a reusable traversal policy from template-level judgments and execution feedback, reducing reliance on fixed heuristic traversal through feedback-driven graph navigation. To support extensible retrieval, COMPASS embeds problem descriptions and template nodes in a shared semantic space, allowing newly inserted templates to be scored from their text descriptions without redefining the action space. Experiments across multiple LLM backbones and optimization-modeling benchmarks demonstrate that COMPASS consistently improves over heuristic structured retrieval, with the largest gains on complex and mixed-category problems.
Figures & tables
Figure 1: Overview of COMPASS. The template library is represented as a DAG, and retrieval is performed through a learned traversal policy guided by semantic priors and execution feedback.
Model
Method
NL4Opt
MAMO
MAMO
LPWP
IndustryOR
OptMATH
EasyLP
ComplexLP
Reasoning LLMs
Reasoning
DeepSeek-R1
91.8
80.8
57.3
69.4
72.0
50.0
LLMs
OpenAI-o1
92.7
85.4
57.8
70.5
74.0
47.6
Prompt-based Methods
DeepSeek-V3
Direct
89.4
78.8
53.1
67.7
54.0
40.9
Table 1: Comparison of modeling accuracy (%) between COMPASS and existing baselines. Best results are shown in bold ; second-best results are underlined .
NL4Opt
MAMO-Easy
MAMO-Complex
IndustryOR
Models
Acc / CER
Acc / CER
Acc / CER
Acc / CER
Qwen-32B (COMPASS)
80.8 / 100.0
76.2 / 100.0
29.9 / 100.0
48.0 / 100.0
Qwen-32B (Direct)
72.7 / 100.0
65.3 / 100.0
20.4 / 100.0
32.0 / 98.0
LLaMA-8B (COMPASS)
55.9 / 100.0
66.9 / 100.0
24.2 / 100.0
15.0 / 98.0
LLaMA-8B (Direct)
51.4 / 100.0
16.1 / 98.6
10.4 / 97.2
10.0 / 96.0
DeepSeek-R1 (COMPASS)
93.8 / 100.0
90.4 / 100.0
66.8 / 100.0
75.0 / 100.0
Table 2: Accuracy (Acc) and code execution rate (CER, %) of COMPASS across different LLM backbones.
Method
NL4Opt
MAMO-E
MAMO-C
LPWP
IndustryOR
OptMATH
DAG-Greedy
93.9
82.4
54.5
71.5
63.0
48.8
COMPASS
95.1
85.9
61.6
72.6
66.0
50.6
Table 3: Accuracy (%) comparison between COMPASS and DAG-Greedy using DeepSeek-V3.
Split
Wins
Losses
p -value
MAMO-Easy
33
10
< 0.001
MAMO-Complex
17
2
< 0.001
Combined
50
12
< 0.001
Table 4: McNemar tests for COMPASS versus DAG-Greedy on MAMO. Wins and losses denote discordant pairs only.
Difficulty
# Problems
DAG-Greedy
COMPASS
Δ
Easy
39
30/39 (76.9%)
29/39 (74.4%)
− 1
Medium
41
20/41 (48.8%)
21/41 (51.2%)
+1
Hard
20
11/20 (55.0%)
16/20 (80.0%)
+5
All
100
61/100 (61.0%)
66/100 (66.0%)
+5
Table 5: IndustryOR accuracy stratified by problem difficulty using DeepSeek-V3. Fractions indicate correct/total instances within each stratum.
IndustryOR
MAMO-Easy
MAMO-Complex
OptMATH
Method
Acc / CER
Acc / CER
Acc / CER
Acc / CER
COMPASS
66.0 / 100.0
85.9 / 100.0
61.6 / 100.0
50.6 / 100.0
DAG-Greedy
63.0 / 99.0
82.4 / 100.0
54.5 / 98.0
48.8 / 98.8
Table 6: Accuracy (Acc) and code execution rate (CER, %) for COMPASS and DAG-Greedy on four datasets using DeepSeek-V3.
Variant
MAMO-Complex
OptMATH
IndustryOR
Full COMPASS
61.6
50.6
66.0
w/o learned traversal (DAG-Greedy)
54.5
48.8
63.0
w/o soft LLM prior ( λ=0 )
58.3
48.2
63.0
w/o beam retrieval ( K=1 )
59.2
49.4
64.0
w/o guarded DAG expansion
58.8
48.2
65.0
Table 7: Component ablations on three diagnostic datasets using DeepSeek-V3 (accuracy, %).
Dataset
λ=0.0
λ=0.1
λ=0.3
λ=0.5
λ=1.0
MAMO-Complex
58.3
59.2
61.6
59.7
57.3
OptMATH
48.2
49.4
50.6
48.8
49.4
IndustryOR
63.0
65.0
66.0
61.0
62.0
Table 8: Effect of the soft-prior weight λ on accuracy (%) across three datasets using DeepSeek-V3.
Dataset
K=1
K=2
K=3
K=4
MAMO-Complex
59.2
61.6
59.7
42.2
OptMATH
49.4
50.6
48.8
37.3
IndustryOR
64.0
66.0
61.0
43.0
Table 9: Effect of beam width K on accuracy (%) across three datasets using DeepSeek-V3.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
RQ
Evaluation focus
Reported results
RQ1
End-to-end effectiveness against direct prompting, structured retrieval, search-based autoformulation, and reasoning-oriented LLM baselines across the six main benchmarks
Table 1
RQ1
Cross-backbone generalization with Qwen-32B, LLaMA-8B, DeepSeek-R1, and DeepSeek-V3
Table 2
RQ2
Effect of learned traversal relative to DAG-Greedy under the same DAG, template library, generator, and executor
Table 3
RQ2
Paired statistical significance for COMPASS versus DAG-Greedy on MAMO
Table 4
RQ2
Difficulty-stratified analysis and execution-reliability diagnostics
Tables 5 and 6
RQ3
Component ablations on learned traversal, LLM prior, beam retrieval, and guarded DAG expansion
Table 7
Appendix
Table 10: Evaluation matrix organized by research question.
Hyperparameter
Value
Encoder
all-MiniLM-L6-v2
Embedding dimension
384
Projection dimension
64
MLP hidden width
256
Discount factor γ
0.95
Soft-prior weight λ
0.3
Appendix
Table 11: Core hyperparameters used by COMPASS.
Dataset
# Inst.
Problem structure
Modeling hardness
OR-Instruct train
1731
Heterogeneous OR instruction problems used for policy learning and guarded DAG updates.
Provides broad supervision over formulation families and long-tail linguistic patterns; excluded from held-out benchmark evaluation.
NL4Opt
245
Natural-language linear optimization problems with compact business-style statements.
Primarily shallow LP structure, but requires accurate extraction of variables, coefficients, inequality directions, and objective sense.
MAMO-Easy
652
LP-style allocation problems with explicit variables, bounds, and linear constraints.
Longer linear or mixed-integer modeling statements with multiple constraints, ratios, equalities, bounds, and implicit integrality.
High modeling hardness due to interacting constraint families; early retrieval errors are difficult for the code generator to correct.
LPWP
288
Linear-programming word problems from everyday domains such as production, transportation, staffing, and resource allocation.
Moderate hardness arising from prose-to-math translation, ratio constraints, minimum/maximum requirements, and objective ambiguity.
IndustryOR
100
Industrial OR scenarios involving routing, scheduling, facility location, capacity, and logistics variants.
High compositional complexity; instances may combine multiple OR substructures with data tables, indexing requirements, and side constraints.
Appendix
Table 12: Dataset characteristics. Instance counts are computed from the repository files. Hardness refers to modeling hardness rather than solely to algorithmic solver complexity.
Large language models (LLMs) can translate natural-language optimization problems into solver programs, but reliably producing correct formulations and implementations remains challenging. Existing approaches improve optimization modeling through agentic workflows or task-specific post-training. This raises a practical question: can a lightweight harness using a single model role achieve competitive performance without additional training? We introduce OPTICYCLE and OPTISTATE, two lightweight inference harnesses for optimization modeling, and evaluate them on nine benchmarks comprising 2,634 problems using 11 Qwen variants spanning 0.6B-27B parameters. Our results show that execution-guided revision consistently improves macro accuracy over direct generation for all evaluated models, with gains of up to 49.46 percentage points. Despite their simplicity, both harnesses outperform six adapted agentic workflows in same-model comparisons and four evaluated post-trained optimization models at comparable model sizes, without additional training. Explicit formulation state provides further but model-dependent improvements, suggesting that additional structure is not universally beneficial.
Yunxiang Luo, Xin Xu, Tianhao Chen +7
The Hong Kong University of Science and Technology · Huawei
Large language models (LLMs) typically approach combinatorial optimization as an inference-time procedure, solving each instance separately through sampling, search, or repeated prompting. We ask whether reinforcement learning can instead shift part of this reasoning cost into the weights of a code LLM, so that the model synthesizes a reusable solver for an entire problem family. We study this question on Synergistic Dependency Selection (SDS), a controlled variant of constrained Quadratic Knapsack designed to expose a specific failure mode: local signals and strict feasibility constraints make greedy heuristics attractive but unreliable. Under identical scaffolding, Best-of-64 base-model sampling saturates at an approximately 28.7% gap to the global Virtual Best Solver (VBS); code audits show that the base model often retrieves Simulated Annealing templates but misimplements the Metropolis acceptance rule. We fine-tune Qwen2.5-Coder-14B-Instruct with Group Relative Policy Optimization (GRPO) using a feasibility-gated reward and light structural scaffolding. The resulting policy converges to a constraint-aware Simulated Annealing template in 99.8% of feasible SDS outputs, achieves a 5.0% gap to that VBS, and is 91 times cheaper in post-generation execution/search cost than cumulative Best-of-64 evaluation. A compile-once check shows that one best frozen solver per seed remains highly competitive when reused unchanged across the SDS test set, while an additional-domain evaluation on Job Shop Scheduling provides narrower but positive evidence that the scaffold transfers beyond SDS. Negative ablations reveal the limits of this recipe: standard stabilizers degrade performance, a soft feasibility gate fails, and results remain sensitive to reward normalization and domain-specific design choices.
Soheyl Massoudi, Gabriel Apaza, Milad Habibi +1
ETH Zürich Zürich, Switzerland · University of Maryland College Park, MD, USA
Optimization modeling is the process of translating real-world decision problems, often described in natural language, into formal mathematical formulations and executable solver code. While recent advances in large language models have shown promise in automating this process, many approaches focus on one-shot generation or rely on predefined execution-and-repair workflows, without explicitly learning a policy for tool use and revision. This stands in sharp contrast to real-world optimization modeling, which is inherently interactive and proceeds through repeated solve-debug-revise cycles. We introduce PEARL, a system for multi-turn solver-interactive optimization modeling that uses Python execution and mathematical programming solvers inside this loop. Rather than relying on a fixed repair workflow, PEARL learns when to test partial models, how to revise from solver diagnostics, and when to stop. It operates in a multi-turn tool-integrated setting where intermediate execution results, feasibility signals, and solution checks are used to improve both formulations and solver code before finalization. Across diverse optimization benchmarks, PEARL substantially improves executable objective agreement over the same-scale base model and is competitive with strong one-shot and tool-augmented baselines. Notably, PEARL-Qwen3-4B outperforms the much larger DeepSeek-V3.2-685B baseline under direct prompting on both macro- and micro-averaged Pass@1. Code and datasets are provided at https://github.com/AuroraLHL/PEARL.
Hongliang Lu, Zhong Li, Yuxuan Chen +3
Peking University · Great Bay University · Huawei Technologies Co., Ltd