Automating QUBO Formulation Generation from Natural Language with a Multi-Agent Framework

Paper Overview

Field: Machine Learning Authors: Niloy Kumar Mondal, Md Rizwan Parvez Published: 2026-09-11 arXiv: 2509.05827

Summary

Quadratic Unconstrained Binary Optimization (QUBO) is a central formulation for combinatorial optimization and has gained increasing attention due to its compatibility with quantum, hybrid quantum-classical, and quantum-inspired solvers. However, translating natural-language problem descriptions into correct QUBO formulations remains difficult, requiring the identification of binary variables, constraints, objective functions, penalty terms, and suitable penalty weights. This process is time-consuming and often demands substantial domain expertise.

To address this challenge, the authors propose an end-to-end multi-agent framework that automatically generates QUBO formulations from natural-language problem descriptions, supported by structured or unstructured test cases.

Key Contributions

• Multi-agent framework: An end-to-end pipeline that converts natural-language problem descriptions into QUBO formulations, handling both structured and unstructured inputs.
• QUBOBench: A new benchmark of 100 combinatorial optimization problems spanning 12 application domains, curated from peer-reviewed literature, competitions, and classic NP-hard problems.
• Results: The framework achieves 68% accuracy on QUBOBench, outperforming a direct single-shot baseline by 22 percentage points.
• Ablation insight: Iterative self-repair is identified as the most important component driving performance improvements.

Data and code are open-sourced by the authors.

--- *Auto-collected on 2026-09-12*