Problem Reductions at Scale: Agentic Integration of Computationally Hard Problems

Xi-Wei Pan; Shi-Wen An; Jin-Guo Liu

cs.AIApr 13, 2026

Problem Reductions at Scale: Agentic Integration of Computationally Hard Problems

Authors: Xi-Wei Pan, Shi-Wen An, Jin-Guo Liu

Organizations: HKUST (GZ) · Institute of Science Tokyo · RIKEN AIP

Abstract

Solving an NP-hard optimization problem often requires reformulating it for a specific solver -- quantum hardware, a commercial optimizer, or a domain heuristic. A tool for polynomial-time reductions between hard problems would let practitioners route any supported problem to any supported solver through a single interface. Building such a library at scale, however, has remained out of reach. We show that harness engineering, the practice of designing constraints, verification systems, and feedback loops that channel AI coding agents, can overcome this barrier. Our harness combines a no-code contribution route for domain experts, a multilayer verification stack ranging from type-level checks to agentic feature tests (AI agents role-playing as end users), and a fully automated implementation-review-integration pipeline. In about three months, we built a command-line tool backed by a library of 100+ problem types and 200+ reduction rules in over 170k lines of Rust. The result suggests that a well-engineered harness lets agents build well-tested software at a scale and pace beyond prior reduction-library efforts. Because the reduction graph composes transitively, a new solver registered for any single problem type instantly becomes available to every problem connected by a reduction path. The source code is available at https://github.com/CodingThrust/problem-reductions.

Figures & tables

Figure 1: The reduction graph. Two anchor problems are highlighted: 3-SAT at the top and Integer linear programming (ILP) at the bottom right. Edge labels are reduction overheads

r_{\cdot\leftarrow\cdot}

; node labels like

t_{S}

t_{I}

denote the time complexity of the node’s best known solver.

Figure 2: The integration problem. (a) A new reduction does not fit the library’s conventions and cannot be integrated without learning the codebase. (b) The contributor files a structured issue; an agent handles implementation, review, and documentation.

Figure 3: Overview. (a) Many solvers exist, and a problem can usually reach several of them through different reductions, but this knowledge is scattered across the literature without a unified executable framework. (b) A harness-engineered agentic workflow turns a structured GitHub issue into validated code through implementation and review agents under a layered verification stack (the four main layers shown; Section 3.4 lists all six). (c) Three months of this pipeline produced a reduction graph with 190 problem types and 265 rules; the inset shows growth over time.

Figure 4: System architecture. Three layers separate concerns: the interface layer (top) is what users and agents touch, the library layer (middle) holds the reduction graph itself, and the infrastructure layer (bottom) provides the computational backends: solvers for instances and a symbolic engine for overhead and complexity.

Figure 5: Skills architecture. (a) The two skill kinds: advisor skills keep humans in the loop with the agent throughout, while automation skills run end-to-end once invoked. Other interactions with agents are omitted for clarity. (b) The skill catalogue, grouped by invoker (user, contributor, maintainer, or agent). Blue boxes are advisor skills; white boxes are automation skills.

Figure 6: Delegation spectrum. Tasks sorted from fully human (top) to fully automated (bottom); bars show the human–agent split.

Figure 7: Contribution pipeline as a state machine on the GitHub project board. Each box is a board column (state); arrows show the single allowed transition direction. Four roles drive the flow: a domain expert files issues (brown), a maintainer triages and merges (orange), an implementation agent picks issues and creates PRs (blue), and a review agent runs parallel reviews and posts verdicts (teal). If any stage fails, the item moves to On Hold (not shown) for human triage.

Configuration	Mean obj. $\uparrow$	Min obj. $\uparrow$	Best-match	Mean AI tokens	Mean solver time (s)
Bare AI	12,306	9,966	7/10	37,379	37.1
Bare AI + web	10,014	0	8/10	41,504	26.1
+ pred	12,603	12,187	10/10	70,523	12.9
+ pred + web	12,603	12,187	10/10	80,592	6.5

Table 1: Outcomes on the team-split instance class (10 instances per configuration; 90 s solver-wall cap). Agent: Claude Opus 4.7 with extra-high reasoning effort. Higher objective is better; Best-match reports how many of the ten instances each configuration achieves the best-of-four objective.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Work	Form	Scope
Karp [ 33 ] ; Garey and Johnson [ 20 ] ; Lucas [ 36 ]	Paper catalogue	Reduction sketches and Ising formulas; not executable
Karp DSL [ 61 ]	Executable per-rule	25 reductions from a textbook; isolated rules, no reusable graph
REDNP [ 10 ]	Executable per-rule	DSL for student exercises; new problems bootstrap via reduction to SAT
PyQUBO [ 60 ] ; qubovert [ 31 ] ; QUBO.jl [ 56 ] ; D-Wave Ocean [ 11 ]	Executable library	Many problems to single endpoint (QUBO/Ising)
ProblemReductions.jl [ 19 , 35 ]	Executable graph	18 types; inter-type reduction graph; manually maintained
This work	Executable graph	190 types, 265 rules; composable inverse maps; AI-assisted maintenance

Appendix

Table 2: Reduction libraries and tools, ordered by executability and scope.

Figure 8: Trait hierarchy and compile-time validation. The Problem trait defines a universal evaluation interface; ReduceTo<T> requires both forward and inverse maps; procedural macros validate overhead expressions and variant registrations at compile time.

Wrapper	Class	Witness	Example
Max<W>	NP optimization	Yes	Max. Indep. Set
Min<W>	NP optimization	Yes	Min. Vertex Cover
Or	NP decision	Yes	$k$ -Satisfiability
Sum<W>	#P counting	No	$k$ -th Largest $m$ -Tuple
And	co-NP decision	No	(reserved)
Extremum<V>	NP optimization †	Yes	Integer Lin. Prog.

Appendix

Table 3: Aggregation wrappers and their complexity classes.

Problem	Hops	$r_{\text{QUBO}\leftarrow A}$	Application
GraphPartitioning	1	$O(V)$	VLSI partitioning
3-Satisfiability	1	$O(C+V)$	Verification, planning
Knapsack	1	$O(n+b)$	Resource allocation
TravelingSalesman	1	$O(V^{2})$	Logistics, PCB drilling
KColoring	1	$O(V^{2})$	Register allocation
Partition	2	$O(n+b)$	Load balancing

Appendix

Table 4: Ten problems reaching QUBO within three hops, sampled from 138 reachable variants. A QUBO-capable solver inherits all of them via one command.

Panel of Figure 9 — Figure 9: Two skills that bookend the contribution pipeline. propose (left) gates issue creation by domain experts: the hard gate enforces no-code contribution, topology analysis guides experts toward strategic reduction-graph gaps, and pre-validation checks four quality dimensions before the issue enters the pipeline. add-rule (right) drives implementation from a validated issue: the checklist encodes the mathematical knowledge every reduction requires, reference implementations prevent convention drift, and the paper entry ensures visual verifiability by human reviewers.

Panel of Figure 10 — Figure 10: A representative agent profile used in agentic feature testing. The persona’s domain knowledge (logistics optimization) lets the agent judge whether reduction results are plausible without access to ground-truth labels.

Panel of Figure 11 — Figure 11: Shared user-facing prompt rendered to all four configurations.

Seed	Bare AI	Bare AI + web	+ pred	+ pred + web
7	SA	SA	SA	SA
11	SA	SA	SA	SA
13	CP-SAT	Tabu	SA	SA
17	MILP	SA	SA	SA
19	SA	SA	SA	SA
23	SA	SA	SA	SA

Appendix

Table 5: Solver picked on each instance by each configuration. SA = simulated annealing on the Ising / QUBO reduction ( dwave-neal or dwave-samplers ); MILP = mixed-integer linear program (HiGHS or PuLP+CBC); CP-SAT = OR-tools constraint programming; Tabu = D-Wave TabuSampler ; SDP = Goemans–Williamson semidefinite relaxation (PICOS+CVXOPT). Bold cells are the largest gaps to the best-of-four.

Seed	Obj.	Time (s)	Obj.	Time (s)	Obj.	Time (s)	Obj.	Time (s)	Best of 4
	Bare AI		Bare AI + web		+ pred		+ pred + web
7	12,962	13.0	12,962	25.3	12,962	1.3	12,962	1.2	12,962
11	12,641	6.5	12,641	6.4	12,641	15.3	12,641	11.9	12,641
13	12,552	75.0	0	90.0	12,944	6.1	12,944	11.7	12,944
17	9,966	83.0	12,326	3.2	12,326	2.9	12,326	1.2	12,326
19	12,915	12.5	12,915	3.0	12,915	14.7	12,915	5.9	12,915

Appendix

Table 6: Raw per-instance objective and solver wall-time for each configuration. Bold objectives fall below the best-of-four (right column). The 90 s OS-enforced kill cutoff bounds wall-times; entries near 80–90 s indicate the solver was running until killed.

Seed	reads $\times$ sweeps	time (s)	reads $\times$ sweeps	time (s)
	+ pred		+ pred + web
7	$200\times 2{,}000$	1.3	$200\times 2{,}000$	1.2
11	$1{,}000\times 5{,}000$	15.3	$400\times 10{,}000$	11.9
13	$200\times 10{,}000$	6.1	$400\times 10{,}000$	11.7
17	$1{,}000\times 1{,}000$	2.9	$200\times 2{,}000$	1.2
19	$1{,}000\times 5{,}000$	14.7	$200\times 10{,}000$	5.9

Appendix

Table 7: Simulated-annealing budget chosen by each pred -enabled run and the resulting solver wall-time. Each cell shows num_reads

\times

num_sweeps .

Automated Software Engineering

Automated Software Engineering uses AI, search, and verification methods to automate tasks across the software development lifecycle.

See all 81 papers

Humanize: Judgement Engineering for Agentic Coding
Oct 6, 2026Sihao Liu, Ligeng Zhu, Zijian Zhang +6Multi-Agent Coding LLM Agent Orchestration
NVIDIA · UCLA · Tsinghua University +2
Distribution-Aware Programming: Learning Specialized Solvers from Experience
May 13, 2026Saharsh Koganti, Priyadarsi Mishra, Pierfrancesco Beneventano +1Large Language Model-Guided Optimization LLM-Based Program Synthesis
Texas A&M University · Massachusetts Institute of Technology
PluginRSI: Recursive Improvement of Agent Harnesses with Reusable Plugins
Sep 26, 2026Yaorui Shi, Yuchun Miao, Yuxin Chen +5Agent Harness Optimization LLM Agent Harnesses
University of Science and Technology of China · Meituan · Wuhan University +1

Oct 6, 2026J/K move · Enter open · S save

Humanize: Judgement Engineering for Agentic Coding

Sihao Liu, Ligeng Zhu, Zijian Zhang, Dongyun Zou+5

NVIDIA · UCLA · Tsinghua University+2

Multi-Agent Coding LLM Agent Orchestration LLM Agent Reliability Human-in-the-Loop AI Runtime Enforcement for AI Agents

Open paper AskPDF arXiv

Agentic coding makes code generation cheap, but reliable completion remains difficult: the agent that writes the code is a weak judge of whether it is done. We present Humanize, a multi-agent orchestration workflow for agentic coding built around judgement engineering: explicit, mechanically enforced decisions at the boundaries between planning, implementation, review, and learning. A human approves a plan contract, a builder agent implements it in rounds, and a reviewer agent from another vendor decides completion; deterministic hooks, not a model, route work between these roles and enforce 72 mechanical gates. Viewed as a Markov chain over repository states, alternating builder and reviewer samples jointly from two models, so a defect survives only if both miss it. We study Humanize through its deployment, 118 public postmortems of real loops, and its applications. Over 68 versions in 108 days, it gathered 1,468 GitHub stars. Applications include a 567-file gem5 build-system migration under upstream review; Kernel Design Agents, which extend the loop with a kernel knowledge base and profiling feedback and placed in the top three of all three Full-Agent tracks of the MLSys 2026 FlashInfer contest; and, through Humanize Olympiad Agents (HOA), full scores in IOI 2026, IMO 2026, IPhO 2026, and IBO 2024, 418.5/437 in IChO 2026 (gold-medal). Humanize also achieves 672/672 on PutnamBench and ranks first (251/303) on Lean-Eval's leaderboard even competiting with professional mathematicians. The postmortems show that independent review catches unsupported builder claims, but stopping remains a key weakness. In reports that separate rounds by phase, two thirds of rounds occurred after implementation was accepted. This evidence is observational, not a controlled comparison of workflows.

Abstract

Automated Software Engineering

Explore similar work

Humanize: Judgement Engineering for Agentic Coding

Distribution-Aware Programming: Learning Specialized Solvers from Experience

PluginRSI: Recursive Improvement of Agent Harnesses with Reusable Plugins