Does Heat Diffusion Change How Hard Problems Scale, or Only How Fast Each Step Runs?

Many hard combinatorial problems, such as splitting a graph into two groups to cut as many edges as possible (Max-Cut) or satisfying a logical formula (3-SAT), are solved in practice by heuristics. A heuristic is a fast method with no guarantee of finding the best answer. These methods are usually sold on two numbers: the cost of one iteration and the quality reached under some fixed time budget. Neither number says what happens as instances get larger. A method whose steps cost linear time can still need a rapidly growing number of steps. A method that wins at one budget and size can lose at the next. We propose to measure the quantity that matters for scaling: the number of iterations and the wall-clock time needed to reach a fixed quality target, as a function of instance size and a tunable hardness knob. We then ask whether the key ingredient of a recent smoothing heuristic changes the growth exponent of that quantity, or only its constant factor.

The concrete target is Heat Diffusion Optimization. Efficient Combinatorial Optimization via Heat Diffusion relaxes binary variables to probabilities and blurs the objective with the heat equation, gradually reducing the blur. Blurring here means averaging the objective over nearby points so that small traps disappear, much like annealing. The authors prove the blur does not move the global optimum. They report linear cost per iteration and wins over Ising machines on Max-Cut, over second-order Ising machines on 3-SAT, and over FastVC on vertex cover. The claim can be stated in two sentences. Smoothing is only worth its complexity if it bends the scaling curve, meaning it changes the power law or the rate of exponential blow-up in time-to-target. If it only shifts that curve down, a well-tuned simpler method will eventually match it. We will measure which of these is true, and we will test whether scaling curves fitted on small instances correctly predict which heuristic wins at sizes several times larger.

Core Claim

Define $T_A(n, \varepsilon, h)$ as the median iterations that algorithm $A$ needs to reach within relative gap $\varepsilon$ of the best known value. Here $n$ is instance size and $h$ is a hardness parameter, for example clause density in planted 3-SAT or planted-partition strength in Max-Cut. We report the same quantity in wall-clock seconds as $W_A$. We hypothesize that, away from the hardness threshold, the fit $T_A \approx c_A n^{\beta_A}$ is stable. We further hypothesize that the heat-diffusion schedule lowers $\beta$ relative to the same gradient method with diffusion turned off, but that this advantage shrinks as $h$ approaches the threshold. Near the threshold, the growth should look exponential for every method.

The hypothesis that diffusion damps high-order variable interactions faster than low-order ones is an analogy to the noise operator in Boolean Fourier analysis, not a derived result. It predicts a larger exponent benefit on degree-2 objectives (Max-Cut) than on degree-3 objectives (3-SAT). A clean negative result, where diffusion changes $c_A$ but not $\beta_A$, would be equally informative. It would reframe landscape smoothing as a constant-factor engineering gain.

Relation to Prior Work

Three papers motivate this work by showing that single-size or single-budget evaluations mislead.

How Good Is Neural Combinatorial Optimization? audits learned TSP solvers against classical ones. It finds that the gap of the constructive model POMO grows from 0.02% at 50 nodes to over 25% at 100 nodes. It also finds that much of the neural advantage disappears once the classical solver LKH is tuned. We import both lessons: extrapolation must be tested, and baselines must be tuned. We apply them to training-free continuous heuristics, which that audit did not cover.

Complexity Scaling Laws for Neural Models using Combinatorial Optimization supplies the fitting methodology. It fits power laws to trained pointer networks on TSP and finds gap exponents of about 1.86 for reinforcement learning and 1.69 for supervised training. That paper studies suboptimality at fixed model capacity on $n \le 50$. We study time-to-target of non-learned iterative methods, on problems where their exponents are unknown.

The (Un)Scalability of Informed Heuristic Function Estimation in NP-Hard Search Problems constrains our theoretical ambitions. It shows, assuming $NP \not\subseteq P/\text{poly}$, that accurate learned estimates of the exact search heuristic need parameter counts that grow super-polynomially. The same logic makes a worst-case analysis of diffusion trivial: a polynomial-per-step method cannot solve all instances in polynomially many steps. That is why we study instance families with controllable hardness rather than proving worst-case bounds.

Direction 2's broader complaint also applies. Methods claim "efficiency" without quantitative runtime evidence, and asymptotic statements hide constants and memory effects. HeO's linear per-iteration claim is exactly such a statement. We therefore report iterations and wall-clock separately.

Research Program

The first piece is a generator of instance families with a hardness dial and a known optimum at the planted-solution scale, so gaps can be computed without exact solvers at large $n$. The families are planted Max-Cut, planted 3-SAT across clause-to-variable ratios, and random binary quadratic programs in the style of the ADMM paper. We anchor them to the fixed benchmarks in the file: the Biq Mac library for Max-Cut, SATLIB 3-SAT instances with 175–250 variables, and the massive real-world vertex-cover graphs used for HeO. Where true optima are unknown on these fixed benchmarks, we use the best value found by any method under a long budget. Exact solvers establish ground truth where they finish.

The second piece is a single harness that runs every method under identical hardware. It logs objective value against iteration and wall-clock, and extracts $T_A$ and $W_A$ at $\varepsilon \in \{1\%, 0.1\%, 0\}$. We fit exponents by least squares on log-log data with bootstrap confidence intervals over instances. We also fit an exponential-in-$n$ alternative and let held-out likelihood choose between the two forms. Fitting uses only small sizes. Larger sizes are reserved for testing the fits' predictions.

The third piece is a small analysis. For multilinear objectives, we compute how the diffused gradient weights terms of each degree along the schedule. This checks whether the degree-damping analogy holds for HeO's actual closed-form, error-function-based gradient.

Baselines

The naive reference point is uniform random assignment followed by a single greedy pass, repeated with restarts until the budget runs out. It needs no tuning and sets the floor any exponent claim must beat. EHOP found that simple greedy heuristics outperform strong language models beyond roughly 9 nodes. Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs found that randomized greedy with 400 restarts reaches the known optimum on all its path-disjoint instances. Randomized greedy is therefore a real competitor, not a strawman. Beating it means a strictly smaller $\beta$ with non-overlapping confidence intervals on at least one family.

The ablation that isolates the key ingredient is HeO with the diffusion schedule removed. This leaves the identical Bernoulli relaxation, identical gradient steps and identical rounding, with zero blur. This is effectively gradient-based relax-and-round. If HeO's $\beta$ is not lower than this ablation's, smoothing is not what drives the scaling.

The strongest general-purpose competitor on binary quadratic forms is the ADMM heuristic of A simple effective heuristic for embedded mixed-integer quadratic programming. It applies directly to Max-Cut and random binary quadratic programs, and has the same flavor of cheap iteration: after one offline factorization, each step costs a matrix-vector multiply. The best reported numbers for it are solutions typically within 1.3% of the global optimum on random MIQPs, and wins over relax-and-round in 95% of MIMO decoding cases (same paper).

On vertex cover, the domain competitor is FastVC, which HeO is reported to beat. On Max-Cut, the competitors are the Coherent Ising Machine and Simulated Bifurcation. For HeO's own margins over these, no reported result was found on Lacuna for numerical relative loss on Biq Mac or for absolute cover sizes. Our harness will therefore re-measure all of them rather than quote them.

Fairness follows the lesson of the NCO audit. Every method gets the same random-search tuning budget on small development instances; Fair Benchmark for Unsupervised Node Representation Learning found random search competitive with tree-structured Bayesian tuning under fixed time. The tuned settings are frozen before any larger size is run. Every method also gets the same restart policy, the same hardware and the same wall-clock cap.

Why not just…?

Why not just report quality at a fixed time budget, as the HeO paper does? A fixed budget measures one point on a curve and cannot distinguish a lower exponent from a lower constant. The NCO audit shows how a method that looks excellent at one size can collapse at twice that size. We will still report fixed-budget numbers, and we will show whether the fixed-budget ranking at small $n$ agrees with the ranking our fits predict at large $n$. If fixed-budget rankings extrapolate as well as fitted exponents do, our extra machinery is unnecessary, and we will say so.

Why not just derive complexity bounds instead of measuring? Worst-case bounds are uninformative here. Under standard assumptions, any polynomial-per-step heuristic needs super-polynomially many steps on some instances. This is the same structure as the (Un)Scalability result, and it says nothing about typical or planted instances where the methods differ. Our modest analytical piece targets a narrower, testable question: how diffusion reweights terms of different degree. The measured exponent differences between Max-Cut and 3-SAT will confirm or refute it.

Why not just tune a strong classical solver and conclude that it wins? This is a genuine threat. The NCO audit found tuned classical solvers reaching optimality on nearly all TSP instances. It is plausible that ADMM with restarts, or FastVC, matches HeO's exponent everywhere. We include them under equal tuning precisely so this outcome can be seen. If they match, the finding that smoothing does not change scaling is itself the result. The question we ask is not which method wins but whether smoothing changes the exponent, and the ablation answers that regardless of the ranking.

Why not just reuse the neural scaling-law results? Those exponents describe trained pointer networks at fixed capacity on small TSP instances. They describe learned constructive policies, not iterative relaxations, and nothing implies they transfer. We reuse their fitting protocol, not their numbers.

Proposed Experiments

The first decisive check is the exponent contrast. On planted Max-Cut and random binary quadratic programs at moderate hardness, estimate $\beta$ for HeO and for its zero-diffusion ablation over a range of sizes spanning at least a factor of 16. The smoothing hypothesis survives only if HeO's interval lies strictly below the ablation's. We expect the gap to be larger on Max-Cut than on 3-SAT.

The second check is extrapolation. Fit all methods on the smaller half of sizes, predict $W_A$ and the method ranking on sizes 4–8 times larger, and score both rank correlation and median prediction error. Validation extends to Biq Mac instances, SATLIB instances and the million-node vertex-cover graphs. A prediction that fails there, the way POMO's small-size performance failed at 100 nodes, would show that small-size fits cannot be trusted for these heuristics.

The third check is the hardness sweep. At fixed $n$, vary clause density in planted 3-SAT across the satisfiability threshold and track each method's time-to-solution. The question is whether HeO's reported advantage over second-order Ising machines on 175–250 variable instances persists or vanishes near the threshold. It also tells us whether the growth becomes exponential there for all methods, as the core hypothesis predicts.

Throughout, we report iterations and wall-clock separately. This shows whether HeO's linear per-step cost survives memory effects on the largest graphs, which directly tests Direction 2's concern that asymptotic claims hide practical costs.