A parallel version of a gradient-based solver for multi-objective MaxCut reached 99.9999% of the reference hypervolume on a three-objective test and 99.9963% on a four-objective test, with each run taking 0.9 seconds before refinement, according to an arXiv preprint. After refinement, the reported hypervolume reached 100% on both instances. The main benchmark consisted of two cases, and the method does not guarantee that every possible trade-off has been found.
Hypervolume is the study's measure of how much of the desirable trade-off space the final solution set covers. The solver keeps nondominated cuts, meaning cuts that are not beaten across all objectives. The near-full scores were recorded before optional one-bit-flip refinement, and that refinement has its own runtime, especially when the archive of retained cuts is large.
How the solver searches
MO-QUCO first turns each set of preferences into a weighted sum of the objectives, a step known as linear scalarization. It then samples starting points and applies adjacency-based projected-gradient ascent. The outputs are converted into binary cuts, nondominated solutions are archived, and the solver can inspect each cut's one-bit-flip neighbors.
The default setup used 100,000 preferences, batches of 64 starting points, 150 projected-gradient steps, a step size of 0.05 and at most five refinement passes. Runs used fixed seeds 0, 1 and 2. In pMO-QUCO, the preference sweep ran on one NVIDIA H200 NVL GPU and refinement on one CPU core.
The timing comparison
On the CPU, MO-QUCO took 118.0 seconds for the three-objective case and 117.7 seconds for the four-objective case, while reaching 99.9999% and 99.9954% of the reference maximum. For the four-objective case, the reported speedups were 57 times for CPU MO-QUCO and 101 times for GPU pMO-QUCO versus DPA-a. Against the QAOA simulation, the corresponding figures were 37 and 65 times. The QAOA comparison used an idealized 10 kHz sampling clock, not a measured hardware runtime.
The solver also reached high scores early. MO-QUCO reached 99% of the reference maximum within 0.3 seconds on the three-objective case and 1.4 seconds on the four-objective case. It reached 99.9% after 1.5 and 12 seconds, respectively, while pMO-QUCO exceeded 99.99% in about 0.9 seconds. When refinement was included, pMO-QUCO reached 100% in 2.7 seconds for three objectives and 154.2 seconds for four.
The theory is local
For signed edge weights, a fixed point of the binary adjacency formulation is exactly a cut with no improving one-bit flip. The paper also gives a nesting of solution classes: supported cuts sit inside preference-conditioned fixed-point cuts, which sit inside cuts with no Pareto-dominating one-bit neighbor.
In plain terms, the analysis describes stability under a one-bit change. It does not guarantee recovery of the global Pareto front, the full set of best trade-offs. Results depend on the sampled preferences and starting points, and one-bit-flip refinement may become costly when the archive is large.
The tests used different reference points
The main evaluation used two instances from the public QAMOO benchmark: one with three objectives and one with four, both on a graph with 42 nodes and 46 edges. The layer weights were sampled from a normal distribution written N(0, 1). The comparison tracked final hypervolume, the number of nondominated points and measured wall-clock time. MO-QUCO and epsilon-CM were run with three seeds, QAOA with five repetitions, and the other baselines were deterministic.
On strongly conflicting instances with 20 vertices and three objectives, MO-QUCO with five one-bit-flip passes recovered more than 99.9% of the exact Pareto front and nearly 100% of its hypervolume. The reported results were averaged over independently generated instances by topology. Exact WSM recovered only a negligible fraction in that comparison.
For larger conflict instances with 100 and 200 vertices, pMO-QUCO without refinement had higher hypervolume than NI-dSB in every reported configuration. After five passes, mean hypervolume reached at least 99.96% of the hypervolume of a union front. This was a union-front comparison rather than an enumerated exact-front comparison.
What the component test showed
An ablation compared the full method with random cuts. The random configuration reached 78.74% of the reference maximum for three objectives and 72.82% for four, while full MO-QUCO reached 99.9999% and 99.9954%, respectively. The same analysis reported about 97% for bit-flip alone on random cuts.
A result bounded by its test set
The study uses the public QAMOO benchmark and an adapted conflict-instance generator. Its generation procedures are provided in the paper and supplementary code.
The supplied document is an arXiv preprint, version 1, dated 25 August 2026. Its results show how the solver performed on the reported configurations, while the study leaves guaranteed global-front recovery unresolved.
Paper data and sources
Original title: Parallelizable Gradient-Based Optimization For Multi-Objective MaxCut
Authors: Jingjuan Huang, Alvaro Velasquez, Jia Liu, Ismail Alkhouri
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text