DualSchool: How Reliable are LLMs for Optimization Education?
Michael Klamkin, Arnaud Deza †, Sikai Cheng, Haoruo Zhao, Pascal Van Hentenryck · 2025
Read DualSchool: How Reliable are LLMs for Optimization Education? by Michael Klamkin, Arnaud Deza †, Sikai Cheng, Haoruo Zhao, Pascal Van Hentenryck (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21775.txt.
Introduction
Michael Klamkin and co-authors test whether chatbots can do a basic optimization chore: writing the dual of a linear program. Students now meet large language models in class, and the models can recite the conversion recipe by heart. Their 2025 framework, DualSchool, generates primal-dual exercises and grades them by a strict graph distance. The grading avoids the false passes and fails of looser checkers.
The results sting. Top open models fail to produce correct duals with any steadiness. Even two-variable cases trip them, as do judging and error-spotting side tasks. Reciting steps, the team shows, is not doing steps. Teachers should assume fluent talk can hide broken work. The bench gives courses a way to test tools before trusting them.
Catalog record
| CREATOR | Michael Klamkin, Arnaud Deza †, Sikai Cheng, Haoruo Zhao, Pascal Van Hentenryck |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-21775
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
DualSchool: How Reliable are LLMs for Optimization Education? Michael Klamkin, Arnaud Deza †, Sikai Cheng, Haoruo Zhao, Pascal Van Hentenryck Abstract Consider the following task taught in introductory optimization courses which addresses challenges articulated by the community at the intersection of (generative) AI and OR: generate the dual of a linear program . LLMs, being trained at web-scale, have the conversion process and many instances of Primal to Dual Conversion (P2DC) at their disposal. Students may thus reasonably expect that LLMs would perform well on the P2DC task. To assess this expectation, this paper introduces DualSchool , a comprehensive framework for generating and verifying P2DC instances. The verification procedure of DualSchool uses the Canonical Graph Edit Distance , going well beyond existing evaluation methods for optimization models, which exhibit many false positives and negatives when applied to P2DC. Experiments performed by DualSchool reveal interesting findings. Although LLMs can recite the conversion procedure accurately, state-of-the-art open LLMs fail to consistently produce correct duals. This finding holds even for the smallest two-variable instances and for derivative tasks, such as correctness, verification, and error classification. The paper also discusses the implications for educators, students, and the development of large reasoning systems. 1 Introduction Large Language Models (LLMs) have garnered significant interest for their potential to serve as always-available personalized education assistants, automating time-consuming tasks such as tutoring and grading in STEM education. To fully realize this potential, however, LLMs must demonstrate the ability to reliably execute detailed multi-step procedures. In particular, real-world tasks are often nuanced, making attention to detail paramount to success – a higher bar than plausible-looking text. This paper proposes the relatively simple primal-to-dual conversion (P2DC) task as a benchmark to evaluate whether LLMs can execute detailed procedures reliably. P2DC is an interesting task for several reasons. (1) P2DC is commonly taught in introductory optimization courses. (2) LLMs, being trained on a web scale, have the conversion process and many instances of Primal to Dual Conversion (P2DC) in their training corpus. Indeed, when asked directly how to do P2DC, most LLMs respond with a correct strategy. (3) P2DC requires a clear understanding of the procedure, since there are many ways to obtain a dual. (4) P2DC captures several challenges recently articulated at the intersection of (generative) AI and OR, including the verification of optimization models, the availability of datasets, and the design of evaluation criteria and methodologies [ 1 ] . (5) P2DC is also an inherently structured task since the input and output are linear programs which can be represented in different formats (e.g., JSON, XML, MPS files). This makes the P2DC task an attractive test-bed for reasoning models specialized to structured data, a relatively under-studied but extremely valuable competency. Because of the simplicity of P2DC and the availability of the P2DC instructions and instances in the training corpus of LLMs, students in optimization classes may reasonably expect that LLMs would perform well on the P2DC task. To assess this expectation, this paper introduces DualSchool , a comprehensive framework for generating and verifying P2DC instances. To generate P2DC instances, DualSchool leverages automatic symbolic dualization, converting new synthetic and existing primal-only datasets (e.g. NLP4OPT [ 2 ] , ComplexOR [ 3 ] , and EasyLP [ 4 ] ), to P2DC datasets. To enable automatic evaluation, DualSchool includes a graph-based equivalence detection algorithm called Canonical Graph Edit Distance (CGED) . CGED is similar to the NGED algorithm of Xing et al. [5] , but it adds a crucial pre-processing canonicalization step specifically designed to allow for differences in dualization procedure conventions. As such, DualSchool overcomes the limitations of existing validation techniques in the optimization setting which are either overly restrictive or overly permissive. Indeed, existing validations either force particular convention choices or forget much of the problem structure, complicating their use in post-training techniques to improve performance (e.g., [ 6 , 7 ] ). P2DC is illustrated in Figure 1 , which exemplifies the canonical form used for comparing linear programs. Preliminary experimental results with DualSchool reveal interesting findings: they show that the P2DC is surprisingly challenging for leading open LLMs. This discrepancy – being able to recite the procedure but not carry it out reliably – underscores a critical limitation of LLMs: they yield duals with mistakes that may be minor in terms of token count but are clearly wrong (e.g., an unbounded dual for a feasible primal). These findings hold even for the smallest two-variable instances and for derivative tasks, such as error correction, error classification, and verification. In correction , the LLM is asked to correct the error; in classification , the LLM is asked what the error is; and in verification , the LLM is asked if the primal-dual pair is valid. Figure 1: The P2DC task of DualSchool : it illustrates the primal-to-dual conversion, the canonical representation of linear programs and the evaluation using CGED, which is the concatenation of the canonicalization step and the Graph Edit Distance comparison. The main contributions of this paper can be summarized as follows: 1. The paper proposes DualSchool , a comprehensive framework to evaluate the reliability of LLMs for a relatively simple optimization task, whose instructions are widely available. The multi-task framework includes the P2DC (primal to dual conversion) task and derivative tasks correction , classification , and verification . 2. The paper designs a robust automatic evaluation using a Canonical Graph Edit Distance (CGED) algorithm that simultaneously allows for differences in dualization convention while robustly checking the correctness of all problem data. 3. The paper is associated with a repository of open data and code : over 1,300 primal-dual pairs as well as error-injected variants for each are published alongside the paper, including the code to automatically generate more samples if needed. 4. Experimental results show that P2DC is a compelling challenge despite its simplicity, as state-of-the-art open LLMs struggle even for very small instances. P2DC, and its derivative tasks, also address several challenges recently articulated at the intersection of (generative) AI and OR [ 1 ] . The rest of the paper is organized as follows. Section 2 discusses related work. Section 3 introduces the P2DC task and Section 4 introduces the CGED algorithm. Then, Section 5 presents the experimental results and Section 6 concludes the paper. 2 Related Work This section reviews related work at the intersection of large language models and optimization. LLMs for Optimization Recent years have witnessed a surge of interest in leveraging large language models (LLMs) for various optimization tasks (LLM4OPT). Notable examples include natural language modeling [ 8 , 3 , 2 ] , where LLMs are given a natural language description of an optimization problem and are asked to formulate it, conversational interfaces to configure and customize existing models [ 9 , 10 ] , algorithmic configuration for cutting plane subroutines in MILP solvers [ 11 ] , explaining infeasibilities [ 12 ] , and even solving optimization problems directly [ 13 ] . These efforts highlight the growing recognition of LLMs as a versatile tool that can be applied beyond traditional natural language processing tasks and into the realm of mathematical optimization. Evaluation Methods Despite the increasing attention, existing work in this area primarily rely on the optimal