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
• 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

• A Systematic Analysis of Automatic Differentiation versus Discretization-based Constraints for Physics-Informed PDE Solvers [5.821193246951147]
  Physics-informed neural networks (PINNs) represent a growing frontier using artificial intelligence to solve partial differential equations (PDEs)<n>We conduct systematic experiments across a wide spectrum of problems, from simple linear Poisson to high-Mach hypersonic flows with strong discontinuities.<n>Our results reveal a consistent trend: as nonlinearity strengthens, the accuracy advantage of discretization-based constraints becomes increasingly pronounced.
  arXiv  Detail & Related papers  (2026-09-07T12:44:35Z)
• Adjoint Method versus Physics-Informed Neural Networks in PDE-Constrained Inverse Problems [48.470700002941136]
  Inverse problems governed by partial differential equations (PDEs) are central to computational mechanics and are commonly solved by adjoint-based optimization.<n> physics-informed neural networks (PINNs) have emerged as a flexible alternative.<n>We present a fair comparison of adjoint optimization and PINNs for PDE-constrained inverse problems.
  arXiv  Detail & Related papers  (2026-06-10T17:07:09Z)
• Phylogenetic Tree Inference with Tropical Axial Attention [1.43494686131174]
  We introduce a Tropical Axial Attention neural reasoning architecture that replaces vanilla softmax dot-product attention with max-plus operators.<n>From multi-species sequence alignments, our model learns all possible pairwise distances.<n>We show that tropical attention provides a natural geometric framework for phylogenetic inference.
  arXiv  Detail & Related papers  (2026-05-12T10:54:37Z)
• OMNIFLOW: A Physics-Grounded Multimodal Agent for Generalized Scientific Reasoning [51.33849811496781]
  Large Language Models (LLMs) have demonstrated exceptional logical reasoning capabilities but frequently struggle with the continuous dynamics by Partial Differential Equations (PDEs)<n>We propose OMNIFLOW, a multimodal-symbolic architecture designed to ground frozen LLMs in fundamental physical laws without requiring domain-specific parameter updates.<n>We evaluate it on a benchmark spanning microscopic turbulence, theoretical Navier-Stokes, and macroscopic global weather forecasting.
  arXiv  Detail & Related papers  (2026-03-16T18:29:01Z)
• Emergent Manifold Separability during Reasoning in Large Language Models [46.78826734548872]
  Chain-of-Thought prompting significantly improves reasoning in Large Language Models.<n>We quantify the linear separability of latent representations without the confounding factors of probe training.
  arXiv  Detail & Related papers  (2026-02-23T20:36:17Z)
• The Neurosymbolic Frontier of Nonuniform Ellipticity: Formalizing Sharp Schauder Theory via Topos-Theoretic Reasoning Models [0.0]
  We present the recent breakthrough in nonuniformly elliptic regularity theory and the neurosymbolic large reasoning models (LRMs)<n>By modeling the reasoning process as a categorical colimit in a slice topos, we demonstrate how LRMs can autonomously navigate the Dark Side'' of the calculus of variations.
  arXiv  Detail & Related papers  (2026-02-11T08:24:57Z)
• Anisotropic Tensor Deconvolution of Hyperspectral Images [24.509592365283208]
  Hyperspectral image (HSI) deconvolution is a challenging ill-posed inverse problem, made difficult by the data's high dimensionality.<n>We propose a framework based on a low-parsimonious parameters of Canonical Poly Decomposition (CPD)<n>This approach recasts the problem from recovering a large-scale image with a latent to estimating the factors with $(P+Q+N)R$ variables.
  arXiv  Detail & Related papers  (2026-01-16T16:29:13Z)
• From Universal Approximation Theorem to Tropical Geometry of Multi-Layer Perceptrons [0.0]
  We revisit the Universal Approximation Theorem through the lens of the tropical geometry of neural networks.<n>We introduce constructive, geometry-aware architecture for sigmoidal multi-layer perceptrons.
  arXiv  Detail & Related papers  (2025-10-16T13:15:39Z)
• Less is More Tokens: Efficient Math Reasoning via Difficulty-Aware Chain-of-Thought Distillation [82.2288581878096]
  We present a framework for difficulty-aware reasoning that teaches models to dynamically adjust reasoning depth based on problem complexity.<n>We show that models can be endowed with such dynamic inference pathways without any architectural modifications.
  arXiv  Detail & Related papers  (2025-09-05T16:40:13Z)
• 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)
• Models of Heavy-Tailed Mechanistic Universality [62.107333654304014]
  We propose a family of random matrix models to explore attributes that give rise to heavy-tailed behavior in trained neural networks.<n>Under this model, spectral densities with power laws on tails arise through a combination of three independent factors.<n> Implications of our model on other appearances of heavy tails, including neural scaling laws, trajectories, and the five-plus-one phases of neural network training, are discussed.
  arXiv  Detail & Related papers  (2025-06-04T00:55:01Z)
• 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)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• Interfacing Finite Elements with Deep Neural Operators for Fast Multiscale Modeling of Mechanics Problems [4.280301926296439]
  In this work, we explore the idea of multiscale modeling with machine learning and employ DeepONet, a neural operator, as an efficient surrogate of the expensive solver. DeepONet is trained offline using data acquired from the fine solver for learning the underlying and possibly unknown fine-scale dynamics. We present various benchmarks to assess accuracy and speedup, and in particular we develop a coupling algorithm for a time-dependent problem.
  arXiv  Detail & Related papers  (2022-02-25T20:46:08Z)
• 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)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• 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)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)
• 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.