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

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.Source: §1 · p. 1
• 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.Source: §1 · p. 2
• 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.Source: §1 · p. 2
• 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.Source: §1 · p. 2

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.Source: §2 · p. 2
• 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.Source: §2 · p. 2
• 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.Source: §2 · p. 2

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.Source: §3 · p. 2, §3.1 · p. 2

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.Source: §3.1.1 · p. 2

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.Source: §3.1.2 · p. 3

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.Source: §3.1.3 · p. 3

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.Source: §3.1.4 · p. 3

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.Source: §3.1.5 · p. 3, §3.1.6 · pp. 3–4, §3.1.7 · p. 4

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.Source: §4 · p. 4
• 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.Source: §4 · p. 4

• Accuracy measures the fraction of benchmarks whose generated QUBO matches all ground-truth optimal solutions, while total token consumption is also recorded.Source: §5.1 · p. 4
• 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.Source: §5.2 · p. 4
• All reasoning agents use qwen/qwen3-235b-a22, the Coder uses qwen/qwen3-coder-next, and the direct evaluation uses qwen/qwen3-coder-next.Source: §5.3 · p. 4
• The study compares the full pipeline with variants removing iterative feedback once or removing both the Judge and feedback.Source: §5.4 · p. 4

• 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.Source: §6 · p. 4, Table 1 · p. 4
• 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.Source: §6.1 · p. 4
• 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.Source: §6.1 · p. 4, Table 2 · p. 4
• 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.Source: §6.1 · p. 4, Table 2 · p. 4

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

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

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.Source: §B.2 · p. 8
• 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.Source: §B.2 · p. 8
• 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.Source: §B.3 · pp. 8–9
• 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).Source: §B.3 · pp. 8–9

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.Source: §B.4 · p. 9, Figure 2 · p. 9
• 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.Source: Table 3 · p. 9, §B.4 · p. 9