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

• URL: http://arxiv.org/abs/2605.14624v2
• Date: Fri, 15 May 2026 20:33:00 GMT
• Title: An Amortized Efficiency Threshold for Comparing Neural and Heuristic Solvers in Combinatorial Optimization
• Abstract summary: A common critique of neural-optimization solvers is that they are less energy-efficient than CPU metaheuristics.<n>This paper examines the inferential step from "training is expensive" to "neural solvers are net-inefficient"<n>We show that the cumulative-energy ratio between the two solvers tends to a constant strictly below one whenever the network wins per instance.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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 customers with the attention-based autoregressive solver of Kool et al. (2019), 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.56e3 deployed instances at the median of a six-point baseline-budget sweep; the per-instance neural-to-heuristic ratio is 2.29e-3. The contribution is the framework, the open instrumentation, and the end-to-end measurement protocol. Code and benchmark pipeline are available at https://github.com/sohaibafifi/aet.

Related papers

• Model-Free Surrogate-Assisted Neural Architecture Search for Evolving Variable-Length Dense Blocks [2.473241744699909]
  We propose a Model-Free Surrogate PSO Network (MFSPNet) for evolving convolutional neural network architectures.<n>MFSPNet integrates a lightweight model-free surrogate predictor within a particle swarm optimization (PSO) framework, eliminating the need for pre-trained surrogate models.<n>Under a consistent training protocol with ten independent runs, the proposed method attains error rates of 3.91%, 17.68%, and 1.91% on CIFAR-10, CIFAR-100, and SVHN, respectively.
  arXiv  Detail & Related papers  (2026-09-02T11:32:07Z)
• An Embedded RISC-V Evaluation of Kolmogorov--Arnold Networks in Hard-Constrained Recurrent Physics-Informed Models [0.0]
  Kolmogorov--Arnold Networks (KANs) have been proposed as efficient replacements for multilayer perceptrons (MLPs)<n>This paper asks whether that parameter efficiency survives deployment.
  arXiv  Detail & Related papers  (2026-08-01T16:20:24Z)
• Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts [19.540758462427878]
  We propose a learning-augmented framework that accelerates exact assignment solvers while maintaining optimality and worst-case guarantees.<n>We introduce RowDualNet, a lightweight row-independent architecture that avoids the $mathcalO(N2)$ memory bottleneck of graph-based models.
  arXiv  Detail & Related papers  (2026-05-10T07:15:49Z)
• Ge$^\text{2}$mS-T: Multi-Dimensional Grouping for Ultra-High Energy Efficiency in Spiking Transformer [84.8831358775386]
  Spiking Neural Networks (SNNs) offer superior energy efficiency over Artificial Neural Networks (ANNs)<n>Existing paradigms including ANN-SNN Conversion and Spatial-Temporal Backpropagation (STBP) suffer from inherent limitations.<n>We propose Ge$text2$mS-T, a novel architecture implementing grouped computation across temporal, spatial and network structure dimensions.
  arXiv  Detail & Related papers  (2026-04-10T02:58:46Z)
• ODAR: Principled Adaptive Routing for LLM Reasoning via Active Inference [60.958331943869126]
  ODAR-Expert is an adaptive routing framework that optimize the accuracy-efficiency trade-off via principled resource allocation.<n>We show strong and consistent gains, including 98.2% accuracy on MATH and 54.8% on Humanity's Last Exam.
  arXiv  Detail & Related papers  (2026-02-27T05:22:01Z)
• PT$^2$-LLM: Post-Training Ternarization for Large Language Models [52.4629647715623]
  Large Language Models (LLMs) have shown impressive capabilities across diverse tasks, but their large memory and compute demands hinder deployment.<n>We propose PT$2$-LLM, a post-training ternarization framework tailored for LLMs.<n>At its core is an Asymmetric Ternary Quantizer equipped with a two-stage refinement pipeline.
  arXiv  Detail & Related papers  (2025-09-27T03:01:48Z)
• Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines [0.0]
  We develop a tensor network (TN) based algorithm to reveal the low-energy spectrum of Ising spin-glass systems.<n>Our deterministic approach combines a branch-and-bound search strategy with an approximate calculation of marginals via TN contractions.<n>We benchmark our approach on random problems defined on Pegasus and Zephyr graphs with up to a few thousand spins.
  arXiv  Detail & Related papers  (2024-11-25T14:35:14Z)
• Optimal Decentralized Smoothed Online Convex Optimization [9.449153668916098]
  We study the multi-agent Smoothed Online Convex Optimization (SOCO) problem, where $N$ agents interact through a communication graph.<n>We propose the first truly decentralized algorithm ACORD for multi-agent SOCO that provably exhibits optimality.<n>Our results hold even when the communication graph changes arbitrarily and adaptively over time.
  arXiv  Detail & Related papers  (2024-11-13T05:59:04Z)
• FusionLLM: A Decentralized LLM Training System on Geo-distributed GPUs with Adaptive Compression [55.992528247880685]
  Decentralized training faces significant challenges regarding system design and efficiency. We present FusionLLM, a decentralized training system designed and implemented for training large deep neural networks (DNNs) We show that our system and method can achieve 1.45 - 9.39x speedup compared to baseline methods while ensuring convergence.
  arXiv  Detail & Related papers  (2024-10-16T16:13:19Z)
• On the Convergence of Federated Averaging under Partial Participation for Over-parameterized Neural Networks [13.2844023993979]
  Federated learning (FL) is a widely employed distributed paradigm for collaboratively machine learning models from multiple clients without sharing local data. In this paper, we show that FedAvg converges to a global minimum at a global rate at a global focus.
  arXiv  Detail & Related papers  (2023-10-09T07:56:56Z)
• Latency-aware Unified Dynamic Networks for Efficient Image Recognition [72.8951331472913]
  LAUDNet is a framework to bridge the theoretical and practical efficiency gap in dynamic networks. It integrates three primary dynamic paradigms-spatially adaptive computation, dynamic layer skipping, and dynamic channel skipping. It can notably reduce the latency of models like ResNet by over 50% on platforms such as V100,3090, and TX2 GPUs.
  arXiv  Detail & Related papers  (2023-08-30T10:57:41Z)
• Learning a Consensus Sub-Network with Polarization Regularization and One Pass Training [2.895034191799291]
  Pruning schemes create extra overhead either by iterative training and fine-tuning for static pruning or repeated computation of a dynamic pruning graph.<n>We propose a new parameter pruning strategy for learning a lighter-weight sub-network that minimizes the energy cost while maintaining comparable performance to the fully parameterised network on given downstream tasks.<n>Our results on CIFAR-10, CIFAR-100, and Tiny Imagenet suggest that our scheme can remove 50% of connections in deep networks with 1% reduction in classification accuracy.
  arXiv  Detail & Related papers  (2023-02-17T09:37:17Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  We suggest learning the instance-dependent proxies that are supposed to notably increase the efficiency of the search. The first proxy we suggest to learn is the correction factor, i.e. the ratio between the instance independent cost-to-go estimate and the perfect one. The second proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path.
  arXiv  Detail & Related papers  (2022-12-22T14:26:11Z)
• Neural Capacitance: A New Perspective of Neural Network Selection via Edge Dynamics [85.31710759801705]
  Current practice requires expensive computational costs in model training for performance prediction. We propose a novel framework for neural network selection by analyzing the governing dynamics over synaptic connections (edges) during training. Our framework is built on the fact that back-propagation during neural network training is equivalent to the dynamical evolution of synaptic connections.
  arXiv  Detail & Related papers  (2022-01-11T20:53:15Z)
• An Adaptive Device-Edge Co-Inference Framework Based on Soft Actor-Critic [72.35307086274912]
  High-dimension parameter model and large-scale mathematical calculation restrict execution efficiency, especially for Internet of Things (IoT) devices. We propose a new Deep Reinforcement Learning (DRL)-Soft Actor Critic for discrete (SAC-d), which generates the emphexit point, emphexit point, and emphcompressing bits by soft policy iterations. Based on the latency and accuracy aware reward design, such an computation can well adapt to the complex environment like dynamic wireless channel and arbitrary processing, and is capable of supporting the 5G URL
  arXiv  Detail & Related papers  (2022-01-09T09:31:50Z)
• ProgFed: Effective, Communication, and Computation Efficient Federated Learning by Progressive Training [65.68511423300812]
  We propose ProgFed, a progressive training framework for efficient and effective federated learning. ProgFed inherently reduces computation and two-way communication costs while maintaining the strong performance of the final models. Our results show that ProgFed converges at the same rate as standard training on full models.
  arXiv  Detail & Related papers  (2021-10-11T14:45:00Z)
• Efficient Computation Reduction in Bayesian Neural Networks Through Feature Decomposition and Memorization [10.182119276564643]
  In this paper, an efficient BNN inference flow is proposed to reduce the computation cost. About half of the computations could be eliminated compared to the traditional approach. We implement our approach in Verilog and synthesise it with 45 $nm$ FreePDK technology.
  arXiv  Detail & Related papers  (2020-05-08T05:03:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.