Benchmarks and limitations¶

All numbers come from the raw data in research/experiments/results/ of the repository (reproduction commands in research/REPRODUCE.md). Timings were taken on one shared Apple-silicon machine (8 threads); load was recorded but not controlled, so treat factors below 2 as noise. Instances are mostly single random draws.

Dense order-2 MAX-CUT on random 3-regular graphs¶

\(n\)	block size \(s\)	ours: value, time, memory	MOSEK: value, time, memory
10	56	12.0002, 0.5 s, 0.13 GiB	12.0000, 0.1 s, 0.14 GiB
14	106	19.0000, 1.7 s, 0.17 GiB	19.0000, 0.4 s, 0.21 GiB
20	211	26.0010, 8.7 s, 0.21 GiB	26.0000, 3.9 s, 0.99 GiB
26	352	36.0000, 26.3 s, 0.32 GiB	36.0000, 43.0 s, 5.41 GiB
30	466	40.0026, 61.6 s, 0.44 GiB	40.0000, 252.6 s, 13.27 GiB
40	821	54.0065, 241 s, 1.04 GiB	killed (memory; Schur matrix ≳ 39 GiB)
50	1276	68.0040, 583 s, 1.89 GiB	not attempted
60	1831	81.0195, 2037 s, 2.49 GiB	not attempted

Reading it. Below \(n\approx26\) the interior-point solver is faster. Above it, ours is faster and uses a small fraction of the memory. The cut found equals \(\lfloor U\rfloor\) at every size, i.e. optimality is proved.

Optimality proofs on Biq Mac-style and real instances¶

60 order-2 MAX-CUT instances drawn from the Biq Mac distributions (g05, pm1s, pm1d, torus Ising; 5 seeds, \(n\le40\)): all 60 certified optimal (best cut equals \(\lfloor U\rfloor\)).
5 real library instances g05_60.0–g05_60.4 (downloaded from the Biq Mac library, \(n=60\)): all 5 certified optimal, after 794–1223 s (median 1102 s).
Larger library instances (\(n=80,100\)) and the complete-graph ising instances do not fit the dense order-2 model and were not run.

Comparison with other solvers¶

solver (class)	speed vs. ours	memory	bound returned
MOSEK / TSSOS / CS-TSSOS (interior point)	faster for \(n\lesssim26\); slower above	large (13 GiB at \(n=30\))	dual objective, accurate to solver tolerance
Burer–Monteiro ALM (low rank)	faster (4.7 s vs 62 s at \(n=30\))	small	none; multipliers are poor dual points
SCS (ADMM)	faster for \(n\le30\) at \(10^{-5}\)	up to 1.1 GiB at \(n=40\)	none; at \(10^{-3}\) the error is \(2\times10^{-3}\)–0.45
CGAL (conditional gradient)	faster	small	none
moment-sos	—	1.0 GiB at \(n=40\)	valid at every iterate

At every size we tried, at least one non-certified first-order method reached \(10^{-3}\) faster than we did; the price of having a bound at every iterate was a factor of 5–15 in time at \(n\ge20\). Not compared: ManiSDP, SketchyCGAL with a sketch, RiNNAL-POP, CDCS, COSMO, SDPNAL+.

TSSOS (Julia 1.13.3, MOSEK) returns the same values as the interior-point reference on the dense instances \(n=10\)–30 and takes 12, 12, 16, 58 and 264 s (each including about 12 s of Julia start-up).

Limitations — read these before using the package¶

Not faster than interior point on small problems. If the relaxation fits in memory and you need accuracy of \(10^{-8}\), use an interior-point solver.
Moderate accuracy of the smoothing solver (\(10^{-3}\)–\(10^{-4}\)). solve_alm is more accurate but slower to a first useful bound.
Dense block limit. Blocks beyond \(s\approx2500\) are out of reach (dense eigh); no partial eigensolver, no GPU path tested.
Sparse library instances. On the Biq Mac torus instance t2g10 (\(n=100\), weights up to \(10^5\)) the correlative-sparsity relaxation has 73 blocks of size ≤ 301; CS-TSSOS reaches the order-2 value \(6.0495\times10^6\) in 42 s using 11 GB, while our smoothing solver stops at \(6.197\times10^6\) (\(2.4\%\) higher) in 109 s using 0.7 GiB, and solve_alm is slow here: with warm start it did not leave the order-1 plateau in 400 s, and with default settings it reaches only \(6.76\times10^6\) (12% above) in 980 s (about 70 s per outer iteration). The gap is smoothing bias, not a different relaxation: etas=po.PRECISE_ETAS reaches \(6.04969\times10^6\) (relative difference \(3.8\times10^{-5}\) from TSSOS) in 264 s. Term sparsity is implemented but weaker (see the sparsity guide).
Neural networks. Order 2 matches interior point to \(10^{-5}\) up to about 14 variables. At 38–40 variables solve_alm had not converged after 25 min (78–94% of the order-1 → exact gap closed); at 60 it fails. On a small MNIST classifier order 1 already certified every robust point.
Rigorous certificate was run for blocks up to size 821; it assumes IEEE arithmetic without under/overflow and certifies the stored (normalized) floating-point problem.
Engineering limits. Monomials are 64-bit encoded: spin mode supports \(n\le63\) and continuous mode \(n\le26\) at order 2.
Julia and the command line run a Python process; there is no native Julia solver.