KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems

• URL: http://arxiv.org/abs/2509.15239v1
• Date: Wed, 17 Sep 2025 15:44:25 GMT
• Title: KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems
• Authors: Stjepan Požgaj, Dobrik Georgiev, Marin Šilić, Petar Veličković,
• Abstract summary: We build a neural algorithmic reasoner that can solve Knapsack, a pseudo-polynomial problem bridging classical algorithms and optimisation.<n>Our neural algorithmic reasoner is designed to closely follow the two-phase pipeline for the Knapsack problem.
• Score: 2.0952603334062436
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural algorithmic reasoning (NAR) is a growing field that aims to embed algorithmic logic into neural networks by imitating classical algorithms. In this extended abstract, we detail our attempt to build a neural algorithmic reasoner that can solve Knapsack, a pseudo-polynomial problem bridging classical algorithms and combinatorial optimisation, but omitted in standard NAR benchmarks. Our neural algorithmic reasoner is designed to closely follow the two-phase pipeline for the Knapsack problem, which involves first constructing the dynamic programming table and then reconstructing the solution from it. The approach, which models intermediate states through dynamic programming supervision, achieves better generalization to larger problem instances than a direct-prediction baseline that attempts to select the optimal subset only from the problem inputs.

Related papers

• Primal-Dual Neural Algorithmic Reasoning [14.433843795079083]
  Neuralic Reasoning (NAR) trains neural networks to simulate classical algorithms, enabling structured and interpretable reasoning over Algorithm data.<n>We introduce a framework grounded in the primal-dual paradigm, a classical approximation algorithms.<n>Our results demonstrate that our model not only simulates but also outperforms approximation algorithms for multiple tasks.
  arXiv  Detail & Related papers  (2025-05-29T23:20:07Z)
• Deep Equilibrium Algorithmic Reasoning [18.651333116786084]
  We study neurally solving algorithms from a different perspective. Since the algorithm's solution is often an equilibrium, it is possible to find the solution directly by solving an equilibrium equation. Our approach requires no information on the ground-truth number of steps of the algorithm, both during train and test time.
  arXiv  Detail & Related papers  (2024-10-19T10:40:55Z)
• Neural Algorithmic Reasoning with Multiple Correct Solutions [15.142344738357064]
  In some applications, it is desirable to recover more than one correct solution.<n>We demonstrate our method on two classical algorithms: Bellman-Ford (BF) and Depth-First Search (DFS)<n>This method involves generating appropriate training data as well as sampling and validating solutions from model output.
  arXiv  Detail & Related papers  (2024-09-11T02:29:53Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Unfolded proximal neural networks for robust image Gaussian denoising [7.018591019975253]
  We propose a unified framework to build PNNs for the Gaussian denoising task, based on both the dual-FB and the primal-dual Chambolle-Pock algorithms. We also show that accelerated versions of these algorithms enable skip connections in the associated NN layers.
  arXiv  Detail & Related papers  (2023-08-06T15:32:16Z)
• Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
  We propose leveraging recent advancements in neural reasoning to improve the learning of CO problems. We suggest pre-training our neural model on relevant algorithms before training it on CO instances. Our results demonstrate that by using this learning setup, we achieve superior performance compared to non-algorithmically informed deep learning models.
  arXiv  Detail & Related papers  (2023-05-18T13:59:02Z)
• A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms [64.3064050603721]
  We generalize Runge-Kutta neural network to a recurrent neural network (R2N2) superstructure for the design of customized iterative algorithms. We demonstrate that regular training of the weight parameters inside the proposed superstructure on input/output data of various computational problem classes yields similar iterations to Krylov solvers for linear equation systems, Newton-Krylov solvers for nonlinear equation systems, and Runge-Kutta solvers for ordinary differential equations.
  arXiv  Detail & Related papers  (2022-11-22T16:30:33Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  This paper presents a critical analysis on the incorporation of algorithms based on neural networks into the classical optimization framework. A comprehensive study is carried out to analyse the fundamental aspects of such algorithms, including performance, transferability, computational cost and to larger-sized instances.
  arXiv  Detail & Related papers  (2022-05-03T07:54:56Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  This work considers a large family of bandit problems where the unknown underlying reward function is non-concave. Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality. We show that the standard optimistic algorithms are sub-optimal by dimension factors.
  arXiv  Detail & Related papers  (2021-07-09T16:04:24Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  We propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed. An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed. We show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity.
  arXiv  Detail & Related papers  (2020-06-15T02:57:57Z)

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.