Research map / Large language models / Agents, code and math
EquivaMap: Leveraging LLMs for Automatic Equivalence Checking of Optimization Formulations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Quasi-Karp equivalence and EquivaMap, which uses an LLM (GPT-4) to find variable mappings between two MILP formulations, verified by solving and checking optimality, plus the EquivaFormulation dataset of transformed NLP4LP formulations.
Problem
Existing automatic equivalence checks for optimization formulations (canonical accuracy, execution accuracy, WL-test) are heuristic and fail on rescaling, cutting planes, and variable/constraint permutations, which matters for evaluating optimization copilots.
Approach
Define formulation equivalence via a (linear) mapping from decision variables of one formulation to the other such that optimal solutions map to optimal solutions; use an LLM to discover the mapping at the symbolic formulation level and verify by substituting the solver-produced optimal solution, avoiding extra solver calls.
Key results
- EquivaMap reaches 100% accuracy on all equivalent and non-equivalent transformations in EquivaFormulation (worst case 100%).
- Canonical accuracy, execution accuracy and WL-test score 0% on the worst-case equivalent transformations, e.g. execution accuracy and WL-test fail on rescaling and add-valid-inequalities.
- Naive-LLM worst case on equivalent transformations is 3.3%, showing direct LLM judgment is unreliable without mapping and verification.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EquivaMap instead of the strongest baseline | equivalence checking after rescaling · Rescaling | accuracy: 69.9% -> 100% | Helped |
| Use EquivaMap instead of the strongest baseline | equivalence checking after adding valid inequalities · Add Valid Inequalities | accuracy: 100% -> 100% | No clear effect |
| Use EquivaMap instead of the strongest baseline | equivalence checking after replacing variables by linear combinations · Replace by Linear Combinations | accuracy: 100% -> 100% | No clear effect |
| Use EquivaMap instead of the strongest baseline | equivalence checking after substituting objective functions · Substitute Objective Functions | accuracy: 100% -> 100% | No clear effect |
| Use EquivaMap instead of the strongest baseline | equivalence checking after adding slack variables · Add Slack Variables | accuracy: 100% -> 100% | No clear effect |
| Use EquivaMap instead of the strongest baseline | equivalence checking after replacing variables with base-10 representations · Replace by Base-10 Representation | accuracy: 100% -> 100% | No clear effect |
| Use EquivaMap instead of the strongest baseline | equivalence checking after random-order transformation · Random Order | accuracy: 100% -> 100% | No clear effect |
| Use EquivaMap instead of the strongest baseline | equivalence checking after deleting loose constraints · Loose Constraints | accuracy: 100% -> 100% | No clear effect |
| Use EquivaMap instead of the strongest baseline | equivalence checking after converting to feasibility problems · Feasibility | accuracy: 100% -> 100% | No clear effect |
Surprising findings
- Naive LLM equivalence judgment is far less reliable than the mapping-plus-verification pipeline, e.g. 3.3% on add-valid-inequalities worst case cases.
Limitations
- Only relatively simple transformations are covered; complex reformulations such as decomposition are omitted.
- Runtime of about 12 s per check is much higher than execution accuracy or WL-test baselines.
- Evaluation is limited to MILP/LP formulations derived from NLP4LP with linear mappings.
Experimental setup
Datasets: NLP4LP
Benchmarks: EquivaFormulation
Metrics: accuracy of equivalence classification
Baselines: canonical accuracy execution accuracy WL-test naive-LLM EquivaMap (Maj.)
Builds on: Karp reductions NLP4LP Weisfeiler-Lehman test
Closest papers by meaning
- Autoformulation of Mathematical Optimization Models Using LLMs (ICML 2025 · similarity 0.86)
- Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces (NeurIPS 2026 · similarity 0.85)
- OptMATH: A Scalable Bidirectional Data Synthesis Framework for Optimization Modeling (ICML 2025 · similarity 0.85)
- Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.85)
- PEARL: Solver-in-the-Loop Interactive Optimization Modeling from Natural Language (NeurIPS 2026 · similarity 0.85)
- CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization (AAAI 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.