Tropical Attention: Neural Algorithmic Reasoning for Combinatorial
  Algorithms
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.
6836cd5bc65dcde2f95d674f
Baran Hashemi
extracted_confirmed
2025-05-28T08:54:13.357Z
67ee9e42c4ff6510f47b8c29
https://cdn-avatars.huggingface.co/v1/production/uploads/no-auth/Sl0EyXleUwjSFHLa1qsve.png
Baran Hashemi
user
Baran47
6836cd5bc65dcde2f95d6750
Kurt Pasque
6836cd5bc65dcde2f95d6751
Chris Teska
6836cd5bc65dcde2f95d6752
Ruriko Yoshida
Tropical Attention: Neural Algorithmic Reasoning for Combinatorial
  Algorithms
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.
Tropical attention, a novel attention mechanism operating in the max-plus semiring, enhances Neural Algorithmic Reasoning models by improving out-of-distribution performance and robustness to adversarial attacks compared to softmax attention.
tropical attention max-plus semiring tropical geometry tropical circuits Neural Algorithmic Reasoning out-of-distribution adversarial attacks