An Amortized Efficiency Threshold for Comparing Neural and Heuristic Solvers in Combinatorial Optimization

Sohaib Afifi · 2026

Read An Amortized Efficiency Threshold for Comparing Neural and Heuristic Solvers in Combinatorial Optimization by Sohaib Afifi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14624.txt.

Introduction

Afifi defines an amortised efficiency threshold for comparing neural and heuristic solvers in combinatorial optimisation. Training a neural solver costs a large fixed sum of GPU energy. A heuristic costs a little CPU energy per instance. The two become comparable only once deployment volume is fixed. The threshold marks the volume above which the neural solver breaks even on energy or carbon at fixed solution quality. For vehicle routing it is measured near forty-five hundred instances.

Catalog record

CREATORSohaib Afifi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39745
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.14624

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Amortized Efficiency Threshold for Comparing Neural and Heuristic Solvers in Combinatorial Optimization Sohaib Afifi Abstract A common critique of neural combinatorial-optimization solvers is that they are less energy-efficient than CPU metaheuristics, given the operational energy cost of training them on GPUs. This paper examines the inferential step from training is expensive to neural solvers are net-inefficient , which is where the critique actually goes wrong. Training the network costs a large fixed amount of GPU energy; running the metaheuristic costs a small amount of CPU energy on every instance, repeated as long as the solver is deployed. The two are not commensurable until a deployment volume is fixed. We define the Amortized Efficiency Threshold (AET) as the deployment volume above which a neural solver breaks even with a heuristic baseline in total energy or carbon, under an explicit constraint on solution quality. We show that the cumulative-energy ratio between the two solvers tends to a constant strictly below one whenever the network wins per-instance, and that this limit does not depend on how the training cost was measured. An embodied-carbon term amortizes hardware fabrication symmetrically on both sides. We instantiate the framework on the CVRP environment at n = 50 n=50 customers with the attention-based autoregressive solver of Kool et al. [ 10 ] , trained for 100 epochs on 20,000 instances over five random seeds, and HGS via PyVRP as the heuristic baseline. The measured operational crossover sits near 4.6 × 10 3 4.6\times 10^{3} deployed instances at the median of the sensitivity surface; the per-instance neural-to-heuristic ratio is 2.29 × 10 − 3 2.29\times 10^{-3} . The contribution is the framework, the open instrumentation, and the end-to-end measurement protocol. 1 Introduction This paper takes a single critical question seriously: are neural CO solvers less energy-efficient than metaheuristics, given the energy cost of training them on GPUs? The question is the literal form of an objection frequently raised against learned solvers in operations research, and the conditional clause (the energy cost of GPU training) is the part the objection actually rests on. Training a competitive policy involves multiple GPU-hours per run, multiplied by hyperparameter sweeps and discarded prototypes that the published checkpoint hides. Translated into kilowatt-hours on a hardware tier that draws on the order of 300\,\mathrm{W} , the argument goes, the neural solver pays an upfront cost that the heuristic incumbent never incurs and never amortizes against. We deliberately keep the question in this critical form, rather than its laudatory inverse ( are neural solvers more efficient? ), because the critical form places the burden of proof on the learned method and makes the heuristic the default, which matches how the question is actually asked at conferences. We will show that the inferential step is wrong: the upfront training cost is real, but the per-instance inference cost is small and amortizes the training investment in finite deployment volume; above that volume the heuristic is the method whose marginal cost compounds without bound. Neural and heuristic solvers spend energy on fundamentally different schedules. A state-of-the-art metaheuristic for vehicle routing, such as Hybrid Genetic Search (HGS) [ 23 , 22 ] or Lin-Kernighan-Helsgaun (LKH-3) [ 5 ] , spends a roughly constant amount of CPU time, and therefore CPU energy, on each instance it solves. The solver carries no fixed cost and no per-deployment amortization. A learned neural solver inverts the structure: a substantial training budget is paid once, and the per-instance inference energy is small and, crucially, divisible across a batch executed in parallel on a graphics accelerator. The two cost profiles are not comparable as scalars. Yet practitioners must decide between them, and the decision has measurable environmental consequences. The Green-AI literature [ 19 , 15 , 6 ] has produced rich tooling for the training-side accounting but does not address the comparison. Carbon-footprinting work on large language models [ 14 , 13 ] likewise treats training in isolation. Embodied-carbon analyses of computing hardware [ 4 , 26 ] expose a third component, fabrication, that scales with utilization on both sides of the comparison and is routinely omitted from operational reports. Within neural combinatorial optimization [ 24 , 2 , 10 , 11 , 3 ] , the question of how a learned solver compares to a heuristic on energy has, to our knowledge, not been formalized. This paper proposes a framework with three pieces. The first piece is a threshold: the Amortized Efficiency Threshold (AET) is the deployment volume at which a neural solver’s cumulative energy or carbon breaks even with that of a baseline, under an explicit feasibility constraint on solution quality. The threshold makes the fixed/marginal asymmetry between training and per-instance solving quantitative rather than rhetorical. The second piece is a lifecycle correction: hardware fabrication carbon is amortized linearly over a configurable lifetime and applied symmetrically to both sides, making operational-only accounting refutable. The third piece is an asymptotic structural argument: whenever the neural solver wins marginally, the ratio of cumulative energies converges to a constant strictly below one that does not depend on training cost, datacenter overhead, or regional carbon intensity. The structural argument decouples the qualitative verdict (“at large scale the neural solver wins”) from the calibration disputes that move the threshold’s numerical value. Contributions. We (i) formalize AET with a quality-feasibility constraint that forecloses fast-but-incorrect solvers winning by being fast (§ 3 ); (ii) extend the accounting with embodied-carbon amortization (§ 4 ); (iii) prove the asymptotic-ratio identity (§ 5 , Proposition 1 ); (iv) characterize AET as a five-axis sensitivity surface and identify which axes move the threshold versus only its calibration (§ 6 ). Scope. This version reports a single configuration end-to-end: CVRP at n=50 , the attention-based autoregressive solver of Kool et al. [ 10 ] trained for 100 epochs on 20,000 instances with five random seeds, HGS via PyVRP as baseline. Extension to other CO problems, other neural architectures, and other hardware tiers is mechanical given the open instrumentation and is left to future work. 2 Per-Instance Comparison Misleads A single-threaded CPU metaheuristic solves instances in series. Its per-instance energy cost is E_{\text{base}}^{\text{inst}}=\frac{P_{\text{CPU}}\cdot t_{\text{meta}}}{3600}\quad[\text{Wh}], (1) independent of how many instances are solved. A neural solver, by contrast, exploits batched inference: a batch of B instances is processed in parallel inside one forward pass. The correct quantity to compare is not the wall time of a single instance, but the per-instance throughput-amortized energy E_{\text{NN}}^{\text{inst}}=\frac{P_{\text{GPU}}}{3600\cdot\tau_{\text{NN}}(B)},\qquad\tau_{\text{NN}}(B)\;=\;\frac{B}{t_{\text{batch}}(B)}. (2) Equation ( 2 ) captures the inference cost the accelerator was designed to deliver. The throughput \tau_{\text{NN}}(B) is monotonically non-decreasing in B up to a hardware-dependent plateau, after which further enlargement adds only memory pressure without improving per-instance energy. For the regime of interest, plugging back-of-envelope figures (Table 1 ) yields a per-instance neural cost in the \mu Wh range and a heuristic cost in the 10^{-1}\,\mathrm{Wh} range: four to five orders of magnitude apart in favor of the network. Quantity Value Per-instance NN energy ( B=512 ) \boldsymbol{3.53\times 10^{-5}\,\mathrm{Wh}} Per-instance baseline energy (HGS, mono, t{=}60 s) \boldsymbol{5.50\times 10^{-1}\,\mathrm{Wh}} Per-instance baseline (HGS, multi, t{=}10 s) 1.20\times 10^{-2}\,\mathrm{Wh} Per-instance baseline (HGS, multi, surface median) 2.31\times 10^{-2}\,\mathrm{Wh} Training energy E_{\text{train}} (median, 5 seeds) 105.2\,\mathrm{Wh} Training IQR [104.8,\,105.2]\,\mathrm{Wh} Ratio NN / baseline (multi, surface median) \boldsymbol{2.29\times

Read the complete text