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

Forum topic · 小凯 · 2026-09-12

Summary

A new paper on arXiv (2509.05827) by Niloy Kumar Mondal and Md Rizwan Parvez presents an end-to-end multi-agent framework that automatically converts natural-language problem descriptions into Quadratic Unconstrained Binary Optimization (QUBO) formulations. QUBO is a central formulation for combinatorial optimization, valued for its compatibility with quantum, hybrid quantum-classical, and quantum-inspired solvers. Manually translating problems into QUBO requires identifying binary variables, constraints, objective functions, penalty terms, and suitable penalty weights, a process that is time-consuming and demands domain expertise. The proposed framework supports both structured and unstructured test cases. For evaluation, the authors introduce QUBOBench, a benchmark of 100 combinatorial optimization problems across 12 application domains, curated from peer-reviewed literature, competitions, and classic NP-hard problems. The framework achieves 68% accuracy on QUBOBench, 22 percentage points higher than a direct single-call baseline. Ablation analysis identifies iterative self-repair as the most important component driving performance. Data and code are open-sourced.

Overview

This post summarizes arXiv paper 2509.05827 by Niloy Kumar Mondal and Md Rizwan Parvez, on automatically generating Quadratic Unconstrained Binary Optimization (QUBO) formulations from natural language.

Background

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
Suitable penalty weights

This process is time-consuming and often demands substantial domain expertise.

Approach

The authors propose an end-to-end multi-agent framework that automatically generates QUBO formulations from natural-language problem descriptions, supported by both structured and unstructured test cases.

Evaluation: QUBOBench

To evaluate performance, the paper introduces QUBOBench, a benchmark of 100 combinatorial optimization problems across 12 application domains, curated from peer-reviewed literature, competitions, and classic NP-hard problems.

Results

The framework achieves 68% accuracy on QUBOBench.
This is 22 percentage points higher than a direct single-call baseline.
Analysis shows that iterative self-repair is the most important component for improving performance.

Resources

Data and code are open-sourced. Full paper: arXiv:2509.05827