TL;DR
This paper introduces OptiBench, a comprehensive new benchmark for evaluating Large Language Models (LLMs) on end-to-end optimization problems, and ReSocratic, a novel "reverse" data synthesis method. By training on the resulting ReSocratic-29k dataset, open-source models like Llama-3-8B see massive performance gains, jumping from 13.6% to 51.1% accuracy and narrowing the gap with closed-source giants like GPT-4.
What Problem Does This Paper Address?
While LLMs have shown impressive chops in basic math, solving real-world optimization (OPT) problems—like supply chain management or energy scheduling—is a much higher bar. These problems require translating messy natural language into precise mathematical formulations and then writing code to solve them.
Existing benchmarks have two major flaws:
- Lack of Complexity: Most focus only on simple linear programming, ignoring the nonlinear constraints and tabular data formats common in industry.
- Data Scarcity: High-quality optimization data is hard to find and expensive to annotate, as it requires domain expertise in Operations Research.
Consequently, there is a massive performance chasm between top-tier closed models (GPT-4) and smaller open-source models that lack specific tuning for these complex reasoning tasks.
Methods
The authors tackle the data scarcity problem with ReSocratic, a data synthesis framework inspired by the Socratic method but executed in reverse.
Standard "forward" synthesis usually asks an LLM to "write a question and then solve it," which often leads to logical errors. ReSocratic flips the script:
- Seed Formalization: It starts with human-curated "seed" demonstrations that are formatted step-by-step (variables, objective, constraints).
- Reverse Synthesis: An LLM generates new, complex mathematical formulations first.
- Back-Translation: These formal models are then "back-translated" into natural language questions and paired with automatically generated Python code (using the
pyscipoptlibrary) to find the numerical answer.
To evaluate models, they use an end-to-end pipeline where the LLM must read a problem, generate solver code, and then extract the final numerical results from the code's output.
Datasets
- OptiBench (New): A high-quality evaluation benchmark consisting of 605 manually verified problems. It covers four categories: linear/nonlinear problems, both with and without tabular data.
- ReSocratic-29k (New): A large-scale synthetic dataset of 29,000 samples generated via the ReSocratic method for supervised fine-tuning (SFT).
- Existing Benchmarks: The paper compares against NL4OPT, ComplexOR, and NLP4LP, noting that OptiBench is significantly larger and more diverse.
Key Insights and Ideas
- Tables and Nonlinearity are the "Final Bosses": LLM performance drops sharply when problems involve tables or nonlinear equations. For instance, GPT-4's accuracy falls from ~75% on linear problems to ~32% on nonlinear ones with tables.
- Logic-First Synthesis Wins: Synthesizing the mathematical logic before the natural language question (the ReSocratic approach) produces much more reliable training data than traditional methods like WizardLM.
- Coding is the Bottleneck: A major source of failure isn't just the math; it's the LLM's inability to write bug-free code for specific solvers. Small models often fail to execute their own generated code (low "Code Pass" rate).
- Reasoning-then-Coding isn't a Silver Bullet: Interestingly, prompting models to "reason first, then code" did not significantly improve performance over direct code generation in this domain, suggesting the challenge lies deeper in the model's internal representation of the problem.
Key Results
The results demonstrate that targeted fine-tuning can make small models punching way above their weight class:
- Llama-3-8B-Instruct: Its accuracy on OptiBench soared from 13.6% (few-shot) to 51.1% after SFT with ReSocratic-29k, nearly matching GPT-3.5-Turbo (49.1%).
- Llama-2-7B-Chat: Improved from a literal 0% success rate to 30.6%.
- State-of-the-Art: GPT-4o remains the leader with an overall accuracy of 66.1%, though the fine-tuned Llama-3-8B actually outperformed GPT-4 in the specific category of "linear problems with tables."
Limitations and Future Work
The authors acknowledge that their benchmark currently focuses on "Explicit" problems—those where all numerical values are provided in the text. Real-world scenarios sometimes involve "Implicit" problems where models must infer values or handle abstract variables.
Future directions include extending the ReSocratic method to other types of mathematical word problems and testing the benchmark against an even wider array of emerging large language models. They also aim to improve the "self-correction" abilities of models when their generated solver code fails to run.
Summary updated