PaperlayerView exact revision on arXiv

Source-linked AI summary

Automating Quadratic Unconstrained Binary Optimization (QUBO) Formulation Generation from Natural Language

Niloy Kumar Mondal, Md Rizwan Parvez

arXiv:2609.10629v1cs.AI

TL;DR

Correctly translating natural-language combinatorial optimization problems into QUBO formulations requires substantial modeling work and domain expertise. This paper introduces a multi-agent framework with iterative validation and QUBOBench, achieving 68% accuracy and outperforming a direct single-call baseline by 22 percentage points, while identifying iterative self-repair as the most critical component.

  • Problem

    Translating natural-language optimization descriptions into correct QUBOs requires identifying variables, constraints, objectives, penalties, and penalty weights, making the process difficult and time-consuming.

  • Method

    The paper decomposes QUBO generation across specialized agents for planning, formulation, judging, debugging, coding, and testing, with feedback-driven retries.

  • Results

    68% accuracy on QUBOBench outperforms the direct single-call baseline by 22 percentage points, with iterative self-repair identified as the most critical component.

  • Takeaways & Limitations

    QUBOBench provides a 100-problem, 12-domain evaluation, and the framework’s iterative self-repair is associated with its strongest reported performance improvement.

  • Takeaways & Limitations

    Future work includes fine-tuning separate agents for specific tasks and incorporating an Ising Formulator with quantum-hardware feedback.

Abstract

from arXiv · show

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, we 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. To evaluate its performance, We also introduce QUBOBench, a benchmark containing 100 combinatorial optimization problems across 12 application domains, curated from peer-reviewed literature, competitions, and canonical NP-hard problems. Experimental results show that our framework achieves 68% accuracy on QUBOBench, outperforming a direct single-call baseline by 22%. Further analysis identifies iterative self-repair as the most important component contributing to improved performance. The data and code are open-sourced at https://quitttcat.github.io/QuantumQUBOAgent.

1. Introduction

QUBO reformulates combinatorial optimization for quantum and related solvers, but translating natural-language descriptions into correct formulations is demanding. The paper addresses this bottleneck with an automated multi-agent framework and evaluates it on QUBOBench.

  • 1. Introduction: QUBO is an NP-hard combinatorial optimization formulation used across domains and compatible with quantum, hybrid quantum-classical, and quantum-inspired methods.Examples include quantum annealing and QAOA.
  • 1. Introduction: Generating a correct QUBO requires identifying binary variables, constraints, objectives, penalty terms, and penalty weights before solving the formulation.The process demands domain expertise, mathematical rigor, and experimental feedback.
  • 1. Introduction: 68% accuracy on QUBOBench exceeds the direct single-call baseline by 22 percentage points, with iterative self-repair identified as the most critical component.The benchmark contains 100 problems across 12 application domains.
  • 1. Introduction: The framework generates QUBO formulations from natural-language descriptions supported by structured or unstructured test cases.This directly targets the formulation bottleneck described in the introduction.

2. Related Work

Prior work applies language models to optimization modeling, but QUBO formulation from natural-language research descriptions remains comparatively underexplored. Existing approaches provide limited end-to-end executable validation and feedback-driven correction across diverse domains.

  • 2. Related Work: Earlier work includes NL4Opt for natural-language optimization formulation and Chain-of-Experts for decomposing complex operations-research tasks across specialized language-model agents.These systems establish related directions in language-model-assisted optimization modeling.
  • 2. Related Work: Prior LLM optimization-modeling systems mainly target LP, MILP, or general solver-ready formulations, while natural-language QUBO generation remains less explored.AutoQUBO assumes precise programmatic problem descriptions rather than natural-language research descriptions.
  • 2. Related Work: LLM-QUBO focuses mainly on MILP-to-QUBO conversion and structural checks rather than mutual consistency across specifications, implementations, and small-instance optima.It also lacks feedback-driven reformulation when errors occur.

3. Methodology

The methodology decomposes natural-language-to-QUBO generation into specialized planning, formulation, judging, debugging, coding, testing, and writing stages. Feedback loops and deterministic test execution support iterative correction of both mathematical and implementation errors.

  • 3. Methodology: The framework assigns distinct stages to specialized agents instead of asking one language model to perform the entire QUBO-generation process.The architecture includes six LLM agents: Planner, Formulizer, Coder, Debugger, Writer, and Judge.
  • 3.1.1. THE PLANNER AGENT: The Planner extracts variables, optimization direction, and constraints into structured JSON, then revises its analysis using Judge feedback when inconsistencies are found.Constraints are represented by type and hardness.
  • 3.1.2. THE FORMULIZER AGENT: The Formulizer converts the planner’s specification into a simplified QUBO with variable mappings, objective and penalty terms, penalty-weight justification, and constant offset.It can regenerate the formulation using Judge feedback and failed-test feedback.
  • 3.1.3. THE JUDGE AGENT: The Judge checks planner consistency and formulation correctness, returning targeted issues to the originating agent for retry.Its formulation checks include constraint encodings, penalty forms, and objective sign.
  • 3.1.4. THE DEBUGGER AGENT: The Debugger parses natural-language test cases and ground truth into structured records and encodes ground-optimal selections as bitstrings without seeing generated code.The Coder likewise does not receive ground-truth bitstrings.
  • 3.1.5. THE CODER AGENT: The Coder translates the formulation into executable Python, while the deterministic Test Runner routes coding errors to the Coder and formulation errors to the Formulizer.The Writer produces a visual representation and summary of the output.

4. QUBOBench

QUBOBench evaluates QUBO generation on a diverse collection of domain-specific problems and small natural-language test instances. Its construction combines peer-reviewed sources, competitions, hackathons, and canonical NP-hard problems.

  • 4. QUBOBench: QUBOBench contains 100 combinatorial optimization problems and 200 small-instance test cases spanning 12 application domains.Each sample includes a hand-curated problem description and small instance test cases in natural language.
  • 4. QUBOBench: The benchmark draws 76 problems from peer-reviewed venues, 5 from competitions and hackathons, and 19 canonical NP-hard problems primarily adapted from Lucas.These sources provide complementary coverage for domain-specific evaluation.

5. Experimental Setup

The evaluation measures QuantumQUBO Agent on QUBOBench using accuracy and token consumption, with comparisons against a direct single-call baseline and ablated pipelines.

  • Accuracy measures the fraction of benchmarks whose generated QUBO matches all ground-truth optimal solutions, while total token consumption is also recorded.
  • The direct baseline presents each natural-language problem directly to an LLM with one prompt and uses structured instance dictionaries with a fixed function signature for automated scoring.
  • All reasoning agents use qwen/qwen3-235b-a22, the Coder uses qwen/qwen3-coder-next, and the direct evaluation uses qwen/qwen3-coder-next.
  • The study compares the full pipeline with variants removing iterative feedback once or removing both the Judge and feedback.

6. Results and Discussions

The full QuantumQUBO Agent outperforms ablated variants on QUBOBench, while error analysis shows that failures shift from formulation toward code implementation.

  • 68% accuracy is achieved by the full pipeline, compared with 35% without iterative feedback and 36% without the Judge and feedback.Removing iterative feedback produces the largest decline, while removing the Judge yields a nearly identical result to the no-retry setting.
  • A formulation error means the objective, penalties, variable mapping, or encoded energy landscape is incorrect, whereas a coding error occurs when correct mathematics is implemented incorrectly.
  • 79.3% of QuantumQUBO Agent errors originate from coding, whereas 15.5% are formulation failures.Coding errors involve implementation problems such as index bugs, incorrect array shapes, or faulty NumPy operations.
  • The direct method instead has 66.0% of failures classified as formulation errors.This contrasts with the multi-agent pipeline’s error distribution, where formulation failures are less frequent than coding failures.

7. Future Work

Future work proposes specializing agents and incorporating an Ising Formulator with quantum-hardware feedback, while the pipeline currently uses staged retries and verification outputs.

  • Future work includes fine-tuning separate agents for specific tasks and adding an Ising Formulator with quantum hardware feedback.
  • The pipeline accepts a natural-language problem, test cases, stage-specific retry budgets, and a pass threshold for solution acceptance.
  • Its outputs include a verified QUBO formulation, a correctness-verified builder function, a worked example, and a compiled PDF write-up.
  • The algorithm plans and judges a structured specification, retries failed planning, formulates the QUBO, and performs later verification with additional retries.

B. Details of Dataset

QUBOBench evaluates natural-language QUBO formulation across 100 problem instances and 200 test cases spanning 12 application domains.

  • QUBOBench contains 100 problem instances and 200 test cases across 12 application domains.
  • The benchmark includes graph-theoretic and combinatorial problems such as Max-Cut, Maximum Independent Set, Graph Coloring, and Hamiltonian Path.
  • It also covers logistics and scheduling problems, including Vehicle Routing and Job Shop Scheduling.

B.2. Dataset Structure

QUBOBench uses hand-curated natural-language problem descriptions and test cases drawn from peer-reviewed research, competitions, and canonical NP-hard problems. Its format evaluates whether LLMs can derive valid QUBO formulations from domain-specific language without pre-structured inputs.

  • B.2. Dataset Structure: QUBOBench evaluates QUBO formulation from natural-language descriptions using problem prompts and concrete natural-language test cases.Each test case specifies a problem instance, optimal solution configuration, and ground-truth objective value.
  • B.2. Dataset Structure: The dataset preserves domain-specific terminology so LLMs must identify decision variables and constraints while deriving valid QUBO formulations.This design avoids relying on pre-structured inputs.
  • B.2. Dataset Structure: The benchmark draws 100 problems from peer-reviewed venues, competitions and hackathons, and canonical NP-hard problems.The sources contribute 76, 5, and 19 problems, respectively.
  • B.2. Dataset Structure: Authors hand-curated all prompts and test cases to ensure clarity, consistency, and faithful representation of source problems.The benchmark includes sources such as the D-Wave Examples Repository, Fixstars Amplify Benchmark Suite, and canonical problems drawn primarily from Lucas (2014).

B.4. Domain-wise Distribution

QUBOBench distributes problems across application domains, with graph theory dominating and Robotics and Electronics & VLSI comparatively sparse. The accompanying table summarizes the distribution of both problems and test cases.

  • B.4. Domain-wise Distribution: Graph theory dominates QUBOBench, whereas Robotics and Electronics & VLSI are comparatively sparse.The imbalance reflects the relative centrality and scarcity of published QUBO formulations across these domains.
  • B.4. Domain-wise Distribution: Table 3 summarizes the per-domain distribution of problems and test cases in QUBOBench.The supplied table passage identifies the visual's scope but does not provide individual cell values.
Loading 2609.10629v1…