Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms

• URL: http://arxiv.org/abs/2505.17190v1
• Date: Thu, 22 May 2025 18:01:25 GMT
• Title: Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms
• Authors: Baran Hashemi, Kurt Pasque, Chris Teska, Ruriko Yoshida,
• Abstract summary: We introduce Tropical attention, a novel attention function that operates in the max-plus semiring of tropical geometry.<n>We demonstrate that Tropical attention restores the sharp, scale-invariant reasoning absent from softmax.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dynamic programming (DP) algorithms for combinatorial optimization problems work with taking maximization, minimization, and classical addition in their recursion algorithms. The associated value functions correspond to convex polyhedra in the max plus semiring. Existing Neural Algorithmic Reasoning models, however, rely on softmax-normalized dot-product attention where the smooth exponential weighting blurs these sharp polyhedral structures and collapses when evaluated on out-of-distribution (OOD) settings. We introduce Tropical attention, a novel attention function that operates natively in the max-plus semiring of tropical geometry. We prove that Tropical attention can approximate tropical circuits of DP-type combinatorial algorithms. We then propose that using Tropical transformers enhances empirical OOD performance in both length generalization and value generalization, on algorithmic reasoning tasks, surpassing softmax baselines while remaining stable under adversarial attacks. We also present adversarial-attack generalization as a third axis for Neural Algorithmic Reasoning benchmarking. Our results demonstrate that Tropical attention restores the sharp, scale-invariant reasoning absent from softmax.

Related papers

• Self-Supervised Coarsening of Unstructured Grid with Automatic Differentiation [55.88862563823878]
  In this work, we present an original algorithm to coarsen an unstructured grid based on the concepts of differentiable physics.<n>We demonstrate performance of the algorithm on two PDEs: a linear equation which governs slightly compressible fluid flow in porous media and the wave equation.<n>Our results show that in the considered scenarios, we reduced the number of grid points up to 10 times while preserving the modeled variable dynamics in the points of interest.
  arXiv  Detail & Related papers  (2025-07-24T11:02:13Z)
• Quantum and classical correlations in shrinking algorithms for optimization [0.0]
  We use quantum computing to solve optimization problems (COPs)<n>In this work, we extend and analyze algorithms that solve COPs by recursively shrinking them.<n>We compare the performance of the algorithms equipped with correlations from the quantum approximate optimization algorithm (QAOA) as well as the classical linear programming (LP) and semi-definite programming (SDP) relaxations.
  arXiv  Detail & Related papers  (2024-04-26T08:29:04Z)
• Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
  We design algorithms for Robust Component Analysis (A) It consists in decomposing a matrix into the sum of a low Principaled matrix and a sparse Principaled matrix.
  arXiv  Detail & Related papers  (2023-07-12T03:48:26Z)
• EM's Convergence in Gaussian Latent Tree Models [22.987933817370305]
  We show that the unique non-trivial point of the population log-likelihood is its global maximum. We establish that the expectation-maximization algorithm is guaranteed to converge to it in the single latent variable case.
  arXiv  Detail & Related papers  (2022-11-21T23:12:58Z)
• Langevin dynamics based algorithm e-TH$\varepsilon$O POULA for stochastic optimization problems with discontinuous stochastic gradient [6.563379950720334]
  We introduce a new Langevin dynamics based algorithm, called e-TH$varepsilon$O POULA, to solve optimization problems with discontinuous gradients. Three key applications in finance and insurance are provided, namely, multi-period portfolio optimization, transfer learning in multi-period portfolio optimization, and insurance claim prediction.
  arXiv  Detail & Related papers  (2022-10-24T13:10:06Z)
• Neural Basis Functions for Accelerating Solutions to High Mach Euler Equations [63.8376359764052]
  We propose an approach to solving partial differential equations (PDEs) using a set of neural networks. We regress a set of neural networks onto a reduced order Proper Orthogonal Decomposition (POD) basis. These networks are then used in combination with a branch network that ingests the parameters of the prescribed PDE to compute a reduced order approximation to the PDE.
  arXiv  Detail & Related papers  (2022-08-02T18:27:13Z)
• 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)
• Polygonal Unadjusted Langevin Algorithms: Creating stable and efficient adaptive algorithms for neural networks [0.0]
  We present a new class of Langevin based algorithms, which overcomes many of the known shortcomings of popular adaptive vanishing algorithms. In particular, we provide a nonasymptotic analysis and full theoretical guarantees for the convergence properties of an algorithm of this novel class, which we named TH$varepsilon$O POULA (or, simply, TheoPouLa)
  arXiv  Detail & Related papers  (2021-05-28T15:58:48Z)
• Intermediate Layer Optimization for Inverse Problems using Deep Generative Models [86.29330440222199]
  ILO is a novel optimization algorithm for solving inverse problems with deep generative models. We empirically show that our approach outperforms state-of-the-art methods introduced in StyleGAN-2 and PULSE for a wide range of inverse problems.
  arXiv  Detail & Related papers  (2021-02-15T06:52:22Z)
• Algorithmic Complexities in Backpropagation and Tropical Neural Networks [0.0]
  We introduce artificial neural networks in terms of tropical arithmetics and tropical algebraic geometry. We verify the algorithmic complexity is substantially lower than the usual backpropagation as the tropical arithmetic is free of the complexity of usual multiplication.
  arXiv  Detail & Related papers  (2021-01-03T22:19:17Z)
• 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)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

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.