title: Tropical Attention: Neural Algorithmic Reasoning for Combinatorial
    Algorithms
summary: 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.
paper_authors._id: 6836cd5bc65dcde2f95d674f
paper_authors.name: Baran Hashemi
paper_authors.status: extracted_confirmed
paper_authors.statusLastChangedAt: 2025-05-28T08:54:13.357Z
paper_authors._id: 67ee9e42c4ff6510f47b8c29
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/no-auth/Sl0EyXleUwjSFHLa1qsve.png
paper_authors.fullname: Baran Hashemi
paper_authors.type: user
paper_authors.user: Baran47
paper_authors._id: 6836cd5bc65dcde2f95d6750
paper_authors.name: Kurt Pasque
paper_authors._id: 6836cd5bc65dcde2f95d6751
paper_authors.name: Chris Teska
paper_authors._id: 6836cd5bc65dcde2f95d6752
paper_authors.name: Ruriko Yoshida
paper_title: Tropical Attention: Neural Algorithmic Reasoning for Combinatorial
    Algorithms
paper_summary: 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.
paper_ai_summary: 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.
paper_ai_keywords: tropical attention max-plus semiring tropical geometry tropical circuits Neural Algorithmic Reasoning out-of-distribution adversarial attacks