Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms
Authors: Baran Hashemi
Kurt Pasque
Chris Teska
Ruriko Yoshida
Venue: NeurIPS 2025 poster ()
Keywords: Tropical Geometry
Neural Algorithmic Reasoning
Combinatorial Algorithms
Softmax
Transformers
Out-of-Distribution
Primary area: deep_learning

Abstract: *Can algebraic geometry enhance the sharpness, robustness, and interpretability of modern neural reasoning models  by equipping them with a mathematically grounded inductive bias?* 
To answer this, we introduce Tropical Attention, an attention mechanism grounded in tropical geometry that lifts the attention kernel into tropical projective space, where reasoning is piecewise-linear and 1-Lipschitz, thus preserving the polyhedral decision structure inherent to combinatorial reasoning. We prove that multi-head Tropical Attention (MHTA) stacks universally approximate tropical circuits and realize tropical transitive closure through composition, achieving polynomial resource bounds without invoking recurrent mechanisms. These guarantees explain why the induced polyhedral decision boundaries remain sharp and scale-invariant, rather than smoothed by Softmax. Empirically, we show that Tropical Attention delivers stronger out-of-distribution generalization in both length and value, with high robustness against perturbative noise, and substantially faster inference with fewer parameters compared to Softmax-based and recurrent attention baselines, respectively. For the first time, we push the domain of neural algorithmic reasoning beyond **PTIME** problems to **NP-hard/complete** problems, paving the way toward  sharper and more expressive Large Reasoning Models (LRMs) capable of tackling complex combinatorial challenges in Phylogenetics, Cryptography, Particle Physics, and Mathematical Discovery. The code is available at https://github.com/Baran-phys/Tropical-Attention/.

Tropical Attention:
Neural Algorithmic Reasoning for Combinatorial Algorithms
Baran Hashemi
Kurt Pasque Naval Postgraduate School
Origins Data Science Lab
Technical University of Munich
Monterey, California kurt. wwwpueansuue..s. edu
Munich, Germany baran. hashemi @tum. de
Chris Teska
Ruriko Yoshida Naval Postgraduate School Monterey, California ryoshi da@nps. edu
Naval Postgraduate School
Monterey, California christopher. teska@nps.edi edu
Abstract
Can algebraic geometry enhance the sharpness, robustness, and interpretabiliity of modern neural reasoning models by equipping them with mathematically grounded inductive bias? To answer this, we introduce Tropical Attention, an atten- mechanism grounded in tropical geometry that lifts the attention kernel into tropical projective space, where reasoning is piecewise-linear and I-Lipschitz, thus preserving the polyhedral decision structure inherent to combinatorial reasoning. We prove that Multi-Head Tropical Attention (MHTA) stacks universally approxi- mate tropical circuits and realize tropical transitive closure through composition, achieving polynomial resource bounds without invoking recurrent mechanisms. These guarantees explain why the induced polyhedral decision boundaries remain sharp and scale-invariant rather than smoothed by Softmax. Empirically, show that Tropical Attention delivers stronger of-dissributtin generalization in both length and value, with high robustness against perturbative noise, and substantially faster inference with fewer parameters compared to Softmax-baad and recurrent attention baselines, respectively. For the first time, push the domain of neural algorithmic reasoning beyond PTIME problems to NP-hard/complete problems, paving the way toward sharper and more expressive Large Reasoning Models (LRMss) capable of tackling complex combinatorial challenges in Phylogenetics, Cryptography, Particle Physics, and Mathematical Discovery. The code is available at https:://ee thub. com/B BBaran -aarann-pyssTrrreeeeeo abyssTrooical--eee wat.cclllltttetioo...omm
1 Introduction
The tropical semiring T = (IR U (-o0), max, +) (or its "min-plus" variant) replaces ordinary addition by maximum and multiplication by addition [1]. Polynomials over this semiring evaluate to piecewise-linead polyhedral functions. These are the main objects of study in tropical geometry that translates algebraic geometry into combinatorics, turning varieties into polyhedral complexes, with wide applications across the intersection of matroid theory, combinatorial optimization, auction theory, enumerative geometry [1-5], and recently Machine Learning [6-13]. Because analyses the entire polyhedral structure of solutions rather than single Euclidean point, tropical geometry is
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

Figure 1: (top) Tropical Attention with sharp attention maps learning the notorious QUICKSELECT algorithm, showcasing a size-invariance and OOD lengths generalization behavior far beyond training (8 - 1024). In contrast, both (middle) adaptive-softmax and (bottom) vanilla-offtma heads dilute and uniformly disperse as sequence length grows, failing to generalize. Each column evaluates the models
batch of independently drawn inputs of increasing length. Since the position of the target k-th element is different each batch, the pattern of attention naturally changes to reflect the new data.
Baseline Transformers Universal Transformers (UT)
Tropical forme
Combinatorial Tasks
Vanilla
Adaptive
Vanilla w/ ACT
Adaptive w/ ACT
CONVEXHULL
42.75 12.75
28.25=0096
43.37
53.83
97.00
KNAPSACK
11.06 1176
39.18
54.57
55.04
60.00
QUICKSELECT
4.66 45598
22.89 42.49 $2.49
37.05
40.44
77.06 1:3.
BINPACKING
60.75
64.25=1.09
64.07
63.28
66.01
SCC
51 51.30
56.50=2.22
74.68
70.81
89.25 43
SUBSETSUM
21.13:42.4
22,75 4:2.5
41.43
42.05
87.50 $7.50 16.45
BALANCEDPARTTTION
80. 80.55 42291
91.90
80.01
91.13
43.55
3SUM
80.00 +..82
79.75 00050
81.12
81.67
82.75 1:1.99
MINCOINCHANGE
9.25 1.36 41.96
17.98 #2229
17.33
23.67
42.52 1:
FLOYD-WARSHALL
12.81 24.03
1.31
7.59
0.97
0.81 #:0.08
FRACTIONALKNAPSACK 0.88
0.86+0008
0.85
0.66
Table I: Out-of-distribution Micro-F, score (top) and MSE for regression tasks (bottom) under Length OOD test. The Tropical Transformer outperforms all baselines, across combinatorial tasks while delivering 3x-9x faster inference and using ~ 20% fewer parameters than Universal Transformer (UT) [17] baselines with iterative attention that approximate the closure.
natural mathematical language for algorithms that must reason over families of inputs, particularly those generating such polyhedral structures. Dynamic programming (DP) exemplifies this connection. It is cornerstone for numerous combinatorial optimization problems. The structure of these problems allows DP value functions to be described as piecewise- linear functions, forming polyhedral structures. They are just recursively constructed circuits over tropical semirings. Each such circuits, namely tropical circuits, compute monomials as feasible solutions over the underlying semiring making the DP update step effectively linear within this algebraic framework [14, 15).
'The challenge by Michael Galkin [16]

---

Many combinatorial optimization problems are specified by family of these optimal solutions. For example, shortest-path algorithms such as Floyd-Warshall explicitly manifest this as tropical matrix products and closures, and their feasible solutions trace the faces of a polyhedral complex in parameter space [18]. More broadly, if candidate solutions to combinatorial algorithms are monomials (linear segments) in tropical space, then the computation is just a circuit of tropical gates. Several combinatorial algorithms like shortest paths [19, 20], change making [21, 22], knapsack [23-25], are nothing but recursively constructed tropical circuits. So the tropical circuit model can give us a bridge between combinatorial optimization and neural architectures to perform sharp, piecewise-linear, and polyhedral computations, offering representation around which we can align the attention mechanism at the core of Transformer reasoning.
However, vanilla Transformers [26] are misaligned to this objective. Softmax deftmax-noriee normalized dot-product attention lives in Fuclidean geometry and produces smooth, quadratic decision boundaries. This smoothness blurs the hard arg max arr min structure on which combinatorial algorithms rely. As input length grows, softmax distributions can disperse, resulting in an increasingly flat probability distribution, a.k.a, dispersion [27] attention fading [28]. Moreover, the exponential sensitivity of softmax makes logits vulnerable to small &o perturbations, harming adversarial robustness. As a result, Transformers equipped with softmax attention fail to extrapolate beyond the training regime of input length or magnitude on combinatorial tasks. For non-algorithmic reasoning tasks, even though injecting positional information [29-31] can alleviate the length extrapolation issue, we believe that the core of the issue lies within the attention mechanism itself.
Our Contribution: As result, we propose Tropical Attention, novel attention mechanism that incorporates tropical algebraic geometry to perform reasoning and information routing in tropical projective space. In tropical projective space, the attention scores are governed by the tropical Hilbert projective metrie; consequently, the induced map is piecewise-linest idempotent in the aggregation, and non-expansive (1 (I-Lipschitz). In particular, Tropical Attention preserves the polyhedral structure characteristic of combinatorial value functions while inheriting the projective invariance and shortest- path geometry captured by the Hilbert metric [5]. Our viewpoint is aligned with Neuroalgebraic Geometry [32], in which neural computations are modeled by algebraic and tropical structures acting on polyhedral complexes. The mechanism is drop-in for standard Transformer blocks where reasoning occurs in tropical projective space and then returns to Euclidean coordinates for subsequent layers, so training and architectures remain unchanged.
We show that multi-head Tropical Attention (MHTA) realizes the target class of dynamic programs and approximates tropical circuits with tropical transitive closure. In particular, our expressivity theorems construct MHTA stacks that simulate tropical circuits without super-polynomen
blow-ups in network size or the requirement for recurrent reasoning [17]. In other words, MHTA has sufficient capacity to approximate closure by absorbing the feasible solutions into its tropical polyhedral stratification, thus avoiding recurrent hidden state refinement [33].
Empirically combinatorial tasks, including NP-hard/complete problems, this alignment translates into stronger out-of distrribitiitn generalization together with substantial inference-tine and parameter efficiencies relative to recurrent-style baselines. This study, also for the first time extends the applicability of Neural Algorithmic Reasoning [34] beyond the polynomial-time solvable problems to No-har//complete combinatorial optimization problems, such as KNAPSACK, BIn PACKING, and Balanced PaRTITION problems.
2 Background and Related Work
2.1 Out-of-Distributian Generalization
An important measure of a supervised learning model's reasoning is its ability to generalize to inputs that differ fundamentally from those encountered during training. This is known as -ittof-diitribution (OOD) generalization. Following [35] notations formally, let X' denote the feature space and y be the label set. A model h X + y is learned from training examples drawn independently and identically distributed from a training distribution Drr over X x D. Given a distinct test distribution
Dte on the same space, we define the OOD risk as, R (h) = B(r,)) ((.()))) v)], where é
3

---

is loss function. Its empirical estimate on finite sample S drawn from Die (i.e., S ~ D.e is. (h) = 1o| (z.))es (h(x),
We say that the model h -OD-generalizes from Dir to Dio if its OOD risk RDD,, (h) remains comparable to its in-distribution risk D. (h), indicating minimal performance degradation despite the distributional shift. In the context neural algorithmic reasoning, three main types of deviation between Dr. and Dio are important in measuring model's capabilities:
Length Generalization Both distributions draw their numerical entries from the same range but the test sequences strictly longer, (X) & (R20) Timax with Tlmax > Mtr-- Here, good performance indicates that the network has learned a parallel or recursive scheme that scales with input size rather than memorizing fixed shallow eircuit.
2. Value generalization The two distributions share the same support with respect to sequence length but supp supp(Dto(XX) (X)) contains magnitudes never encountered during training, i.e. supp(Dto((4 ( * For arithmetic or DP-style tasks, value generalization is the clearest evidence that the model has learned the rule rather than the lookup table of seen inputs.
3. Perturbative-noise generalization Noisy data, whether arising from measurement error, adversarial attack, or any other source, often causes models to make mistakes and must be accounted for in model design. To test noise robustness, Die is obtained from Die by an f--bounded, perturbation map A: X' - X' such that ptt A(x) with | z1I, I ε. Robust generalization demands that the risk remains low even under the worst allowed A. This regime probes the stability and smoothness of the learned function of the architecture. The perturbative noise robustness of Neural Algorithmic Reasoning models is very important for many real-world systems, especially for cryptographic schemes [36].
Length, value, and perturbative noise generalization stress complementary facets of algorithmic competence [37. 38]. Thus, a model as a true reasoning circuit [39, 40] that excels simultancously in all three regimes offers strong evidence of having internalized the underlying combinatorial procedure rather than a brittle statistical surrogate.
2.2 Softmax Self-Attention Mechanism
Given an input sequence X Xi....., XN) E Nxd, , let XW -
XWT,
where the parameter matrices satisfy Wq. WK E Rdxds and Wv E Rddodd, Denote by q. and kJ the i-th and j-th rows of Q and K, respectively, and r > 0 for temperature parameter. Vanilla self-attention computes, for every token i,
N
sxp((a,,k)// Øz = softmax, (lq, = E exp( (qi ki)/T)
h
V 1=1
i= i= (I
where the softmax is applied independently to each row of the score matrix QKT The temperature modulates the sharpness of the resulting probability vector, as T the weights approach a one-hot selection, whereas large т yields an almost uniform mixture. Equation I measures similarity with the Euclidean inner product, which is spherically invariant, meaning that every coordinate contributes equally, regardless of its algorithmic significance. Despite it's success in many tasks [26, 41], its geometric and numerical properties are ill-suited algorithmic reasoning [35, 42]. We summarize the main shortcomings.
Inherent blurriness The exponential map assigns non-zero weight every token; even low temperatures the second-largest term remains strictly positive. As problem size grows, the gap between the top two logits often decreases (e.g. when costs are drawn from common distribution), so the resulting distribution cannot converge to one-hot vector. In practice this leads to soft rather than decisive selections, hampering tasks that require exact order statisties [27, 28]. Recent diagnostic suites show that large language models fail on simple tasks of finding minima and second-minima even within In Distribution (ID) length tests [43, 44]. The attention kernel's inability to sharpen with scale is primary culprit.
2. Sensitivity to small perturbations Because softmax(2) x e², a perturbation of size 8 in the largest logit changes the corresponding weight by multiplicative factor e². An adversary who

---

can alter a single entry of QK' by Ollog N) may invert the ranking of two tokens, propagating an (11) error to downstream activations [45, 46]. This 4x -fragiliyy persists even after common stabilisers such as temperature scaling or normalization layers [45].
3. Mismatch with polyhedral decision boundaries In combinatorial optimization the value function is a tropical polynomial-piccewis linear with faces aligned to coordinate hyperplanes [5, 47]. The quadratic forms generated by Euclidean dot products carve the domain into spherical caps [48] rather than polyhedral cones; reproducing a DP recurrence therefore demands exponentially many heads or layers unless the desired structure is injected by hand.
cemperature-gradiet dilemma Driving the distribution toward a hard arg max necessitates lowering the temperature parameter Yet as - 0 the Jacobian of the softmax grows like 7 causing gradient explosion/vanishing [49]. Careful schedule tuning or gradient clipping becomes mandatory [45], adding prpeer-araamter overhead.
2.3 Neural Algorithmic Reasoning
The problem of bridging symbolic algorithms and differentiable models has become known as Neural Algorithuic Reasoning (NAR). Neural Algorithmic Reasoning involves developing neural models and learning procedures to facilitate the internalization of algorithms directly in models' weights. Starting from early work [34] that aimed to demonstrate the applicability of Graph Neural Networks (GNNs) to approximate classical algorithms [50], the community has subsequently developed and expanded further in different directions [42, 51-58]. Some notable applications are constructing [59] and enumerating [60] combinatorial structures of particular type [59], and dynamic programming [40, 61]. fundamental objective of NAR is to achieve robust oft-o--distriuution (OOD) generalization through algorithmic alignment. Typically, models are trained and validated on small sets/sequences/grapll and tested on larger sets/seqquences/rraphss This is inspired by classical algorithms' size-invare inveiiaaee,eee where correctness of the solution is maintained irrespective of the input size. Our work pursues this objective from a fresh, tropical geometric angle and provides universality guarantees and expressivity for attention within the NAR framework.
Recent work exclusively tried to quantify NAR failures when test sequences are longer [37, 38] or numerically larger [35], but have not assessed noise robustness scenarios. Perturbative noise itself is also of importance since real-world deployments must withstand the worst-case inputs and noise. Robustness in this setting is a test for whether a model has internalized genuine algorithmic structure rather than superficial statistical cues. Hence, we introduce perturbative generulization as a third pillar for NAR benchmarking and show that Tropical Transformer demonstrates systematic gains across all three axes.
Based on the past related works, one can establish demand for an attention mechanism that (i) is expressive and respects the underlying geometric structure of combinatorial algorithms, (ii) mitigates softmax dispersion that hampers OOD generalization, and (iii) delivers OOD noise robustness benefits. Tropical Attention positions itself this intersection, drawing on a decade of tropical geometric insights to advance neural algorithmic reasoning. To best of our knowledge, this level of incorporating Tropical algebraic geometry (not just pre-post processing arithmetic [13, 40, 62]) to define new mathematically grounded reasoning architecture has not been done before.
3 Tropical Attention: Reasoning in Tropical projective space
Tropical Attention arises from combinatorial algorithm alignment, that is information exchange is governed by order statistics, namely maxima, minima, and interval widths rather than absolute magnitudes. These operations live naturally in the tropical semiring, whose idempotence, translation covariance, and projective scale invariance match the properties of tropical geometry and it's computational mirror, tropical circuits. By contrast, the dot-proddut--sofmax kernel depends on absolute scale and temperature, yields smooth (quadratic) decision boundaries, and exhibits dispersion as sequence length grows, thereby blurring the sharp strueture required for decisive reasoning.
Our goal is to replace the dot-product, Softmax- based kernel of vanilla self-attention with a reasoning core that (i) takes place in the tropical polyhedral complex (ii) preserves the piecewise-linear geometry of combinatorial problems, and (iii) inherits the 1-Lisschitz robustness of tropical linear maps. To do so, we perform tropicalization map of queries, keys, and values to piccewise- -eneea projective
5

---

spaces carved out by polyhedral constraints, compute attention weights with the tropical Hilbert projective metric (See Appendix B and [5] for details on tropical algebraic geometry.). aggregate by tropical matrix-vector product, and finally map the result back to Euclidean space so that the rest of the original algorithm (e.g Transformer) modular stack untouched. We present the framework relating robustness and piecewise-linean linearity of maps and show how our proposed scheme offers improvements on OOD generalization tasks.
Let X E IR N xd be the token embedding of the input. We define the tropicalization map by going to an amoeba representation of the input with a learnable valuation map, 4 RRx + (TId-1) 1
@ 2 xX); = U; - max isrdd
Urr where U = -loog (mamm(x(()) X)) E Nxd
(2)
for each row i E 1, ....,, N. The constant shift enforces max; xx(x); e, so the output of ΦΛ always lies in the tropical simplex. A dd-1, == {a E R= max; 2; = e). where every vector is projectively equivalent to exactly one point in the tropical simplex. In other words, is section of the quotient 1Rt /RR.
Lemma 3.1. For every embedded coordinate E [N], the function
(log(z) -
x > 0, A,
(x(x) == [ox(x)],
x S 0, where Φ is a (projecttvv valuation map. Hence the shifted map ((x) = is an Archimedean valuation in the classical sense, and @ is matrix-valued valuation modulo tropical scalars; its image lies in the tropical simplex.
-000
x))
After mapping each input token to tropical projective space, = (X) E TPd-d-1 we compute attention independently across H heads.
Definition 3.1 (Multi-head Tropical Attention (MHTA)). Let d2 = d/H be a fixed head dimension.
Then, for every head (h [H] one choose learnable matrices W-(A) (h) w(t)
(h)
w
Rd
and define the tropical linear projections [7] (h) Z (AJT .K Z @
w
w
(hJT
v(h)
Z O whih where @ denotes max-plus matrix multiplication, (A Q B). max, (A B.j).
Then, using dy the tropical Hilbert projective metric, defined in B.4, we will have the tropical attention score
Sj (1h) = d=( (N)))
[JE,N]
that comes with Projective Invariance and expanssaanss condition (discussed in B.4). Thereafter, the head outputs are aggregated via tropical matrix-vector product,
c
(k)
O
(N) f = max + (N) v
[
The tropical context picks the value that best aligns projectively with the query. Then, the contexts per head, will be mapped to the Euclidean domain via a smooth inverse map (devaluation ((2) = exp(2), and concatenated back to the original dimension, H = (&(C()) || .... |l (C(())) E R Nxd
Why Tropical Attention? Every operation inside MHTA is piecewise linear and aligned with tropical geometry (not just tropical arithmetic). Hence the entire network computes a tropical polygonal map whose cells polyhedral cut out by hyperplanes. This is aligned with combinatorial algorithms, whose solutions correspond to a vertex of a polytope and every decision boundary is a facet. Training a transformer with Tropical attention therefore starts from a hypothesis space that already mirrors the solution structure of a combinatorial algorithms. That is what we call polyhedral inductive bias. By contrast, Euclidean softmax attention inserts an exponential map, blurring the sharp decisions on their input data. Classical transformers modulate the entropy entropy-versus. versus sharpness trade-off through a temperature parameter in the softmax; MHTA sharpness is built in and temperature free. Moreover, since every intermediate representation of MHTA lies in the projective simplex Ad-1 going through arg max is well-defined (no equal maxima except on a set of measure 0) and is stable by global scaling meaning that shifting the entire vector by X Rd does not alter which index attains the maximum. In other words, only relative relations between inputs matter, thus Tropical attention inherently robust against distribution shifts.

---

Furthermore, each MHTA head can function as a tropical gate in tropical circuit. A tropical circuit is finite acyclic digraph whose input vertices store either a variable or a non- non-negative real constant, while every internal vertex has in-degree two and outputs the maximum or the sum of its two predecessors. The circuit's size is the number of internal gates. Classical pure DP algorithms are recursive tropical circuits of this kind; consequently, lower bounds for tropical circuits translate directly into limits for such DP schemes, An MHTA head can also be interpreted as a single tropical gate. A single head implements the composite transformation (u, v) - max; { Sty + oj J. where the score Siz itself obtained through several applications of max and + gates. The outer maximization provides the @b-gate, while the summand v furmishes G-gate acting two variable inputs. Thus every head is a compact, differentiable wrapper around the two tropical primitives, and a full multi-head layer is simply collection of such gates operating in parallel a shared input tape, creating a tropical transitive closure. Training a multi-layer MHTA therefore amounts to discovering how these gates should be wired together, rather than coaxing Euclidean softmax kernel to emulate max-plus algebra indirectly. As a result developing MHTA, we prove that is universal approximator of max-plus dynamic programming for combinatorial optimization with closure (Theorem C.3, Corollary C.3.1, and Theorem 3.2).
Theorem 3.2 (Simulation of max-plus plus dynamic programs). Let (S, E)) be a finite directed acyelic graph with S = N vertices and edge weights {Wav (W,D)a C. T. Fix a source vertex vo E and consider the max-plus Bellman recursion
dt + =
(Wiv O do)())). do(0) 80,101 tEN.
us (M,,)EE
Theorem 3.2, Theorem C.3, and Theorems C.4 and C,5 show upper bounds, i.e. sufficient conditions, of T and N such that stack of T MHTA layers and N heads can approximate any horizon tropical circuit for a dynamic program.
Remark 3.1. A shallow MHTA is sufficiently expressive to approximate the tropical transitive- closure map, and thereby avoids explicit recurrence, to encode a very rich polyhedral geometry of combinatorial algorithmic reasoning into attention and provide non-recurrent (one-shot) solution. However, in the worst-case scenario, the non-recurrent representation requires head-width proportional the number of active path monomials up O(122*). Depth-(T) stacks realize the same computation with polynomial resources by distributing the computation across layers.
In other words, Tropical Attention has sufficient capacity to approximate closure by absorbing the feasible solutions into its tropical polyhedral stratification, thus avoiding explicit recurrence. Consequently, a MHTA module learns the closure directly rather than implementing the recurrence step by step. By contrast, Recurrent Transformers such as the Universal Transformer [17] incorporate depth- recurrence to learn the hidden state representation per token. The recurrent function evolves in parallel across token positions while exchanging information through self-attention. In the next section, Section 4, we show that, Tropical Transformer provides a stronger out-of- distribution generalization than Universal Transformer with Dynamic Halting mechanism, while delivering substantially faster inference with much fewer parameters.
4 Experiments
We evaluate Tropical transformers on eleven combinatorial tasks (see E), several of which are NP- hard/complete problems, and the the Long Range Arena (LRA) benchmark [63], a standard for testing meessoormers on long-sequence tasks across text, image, and math domains. For each combinatorial task we measure three complementary forms of out-of-distribution (OOD) generalization: Length OOD (longer inputs), Value OOD (unseen magnitudes). and noise robustness (perturbed inputs). A procedure to compare between vanilla attention and Tropical Attention is described in Appendix D. For our experiments we custom generated both train and test datasets following procedures from the canonical algorithmic reasoning benchmark CLRS [43]. This decision was due largely to the absence of NP-hard and NP-complete problems in the CLRS benchmark, but also because our framework is designed for sequence and set-based data modalities and our OOD evaluation includes two extra new evaluation pipelines, adversarial perturbations and value generalization. All datasets, generation scripts, and OOD protocols described in Appendix E and F.
For our experiment we consider three variants, (i) Vanilla: Standard transformer encoder with softmax dot-product attention. (ii) Adaptive: Transformer equipped with adaptive softmax attention
7

---

from [27]. (iii) Tropical, which every attention block is replaced by MHTA, For length OOD tests, we also compare with 32-step Universal Transformer (UT) with dynamic halting, as a recurrent attention model, under the vanilla softmax and adaptive-tempeerturee softmax kernels. To ensure a fair comparison, all variants share identical backbone hyperparameters: depth, width, and number of heads. The only architectural difference is the attention kernel. Crucially, no model sees OOD examples during optimization. We follow a uniform procedure in which each model trained from scratch under the same training regime with task specific fixed input sequence lengths and value ranges.
Protocols In order to assess OOD generalization, we construct three stress tests: (i) Length OOD- inputs drawn from the same value range but with longer input sequence lengths. (ii) Value OOD the input sequence lengths are fixed and the values are sampled from an increasingly large range (for example, the models trained on inputs sampled from the range [-5, 5] an out of distribution evaluation would be inputs sampled from the range [-10, 10). (iii) Perturbative noise OOD the input sequence lengths are fixed and the values are from the same input range, but a subset of the input values are perturbed randomly.
Results and Discussion
Section 2.2 elaborated why and how softmax self-attention and its descendants are incapable of generalizing to OOD inputs in combinatorial problems, and Section 3 discussed why Tropical Attention can generalize in the combinatorial regime. With our experimentation, we seek to show if and, if so, how Tropical Attention generalizes in this domain.
To answer if Tropical Attention generalizes, we report the numerical results of our experimen- tation in Tables and 3. The Tropical attention architecture achieves superior OOD performance to both the Vanilla and Adaptive softmax atten- tion. Notably, this out performance can be seen in both regression and classification combinato- rial tasks and across OOD protocols, validating our theoretical results from Section 3. The Trop-
Table 2: Average inference time per sample across all tasks and parameter count.
Model
CPU (ms) GPU (ms) Params.
Vanilla UT w/ ACT
6.285
0.027
50,242
Adaptive UT w/ ACT
7.898
0.018
50,242
Tropical Transformer 1.949
0.003
40,961
ical architecture's s ability to generalize well across OOD protocols and problem sets, especially the notorious Quickselect, suggests that instead of simply learning the specific data it is trained on, these purpose-built models learn the underlying polyhedral structure of the combinatorial algorithm. The results, from Tables and 2, demonstrate two key findings. MHTA shows a strong performance, even when compared against an iterative attention class of transformers with a dynamic Adaptive Computation Time (ACT) mechanism where they can approximate an algorithmic closure, the Tropical Attention model still achieves better OOD performance across all algorithmic tasks. The more interesting results are that our model achieves these results while being on average 3x-9x faster at inference and using 20% fewer parameters than the Universal Transformer baselines. Evaluating on the Long Range Arena (LRA) benchmark as shown in Table 4, Tropical Transformer achieves highly competitive, State-of-te sffte-of-theeart -he- (SOTA) results, placing second overall in average accuracy across the benchmark's 's tasks. This performance shows that the benefits of Tropical Attention stand as a viable and powerful mechanism for general-purpose purpose sequence modeling.
In order to understand how Tropical Attention outperforms, we explore the tropical Attention maps relative vanilla and adaptive attention maps for both Quickselect and Knapsack. On the QUICKSELECY task the goal is to find the k-th smallest elements. For such tasks, maintaining focus means the ability to allocate a high attention score the correct items, creating sharp spikes in the heatmap. Contrarily, losing focus means the attention uniformly disperses across elements, with no single item receiving a high score. Figure 1, which depicts attention maps as sequence length increases for all models, shows that the vanilla and adaptive models exhibit attention fading. In contrast, the Tropical Attention consistently shows bright, distinct bands, indicating it continues to allocate sharp attention even at larger length sequences. Figure 2, replicating visualizations from [27], depicts normalized attentional head for the Quickselect task for a batch of 32 sets, over the 8 items with the largest keys by the norm. If the head operates correctly, it must allocate sharp attention to the position of k-th smallest element. Again, we see that the attention on both softmax models quickly dilute/disperse as sequence length grows OOD while the tropical Attention maintains focus.
8

---

Table 3: outtof--iistibutiinn performance under Value OOD and Perturbative Noise tests. Top:
Micro-F, for classification tasks; Bottom: MSE for regression tasks.
Value OOD
Perturbative Noise
Algorithmic Tasks
Vanil1 a
Adaptive
Tropical
Vani Alailla
Adaptive
Tropical
COnvExHolL
22.75=1.5
23.77#3.0
34.25
90.75+222
91.00
96.00
KNAPSACK
38.87
26.92
49.67
67.85 13.19.1
68.36 13351
74.67
QUICKSELECT
74.22
74.30=1.99
71.10
33.87#7.11
34.82
57.22
BINPACKING
67.26
74.23
78.54
55.38
60.64 +4.22
61.19
SCC
78.51
81.38
74.86
70.00
71.33
69. 69.86=411
SUBSETSUM
34.75 66660
28.50 10.12
79.25 155.3
3.75
3.00 4
72.75 10.00
PATANCEPPARTITION
63.40 cb4299
56.57
55.7645.6
51.064266
37.064108
57.29
3SUM
26.00=t316
26.25
22.16
47.502947
49.25 29.2
65.25 #3.99
MINCOINCHANGE
23.64-407
2,20
33.18
22.12
18.44
33.75 23..59
FLOYD-WARSHALL
87.68-45.65
56.30 +:304
55.30
7.54
5,29
4.39
RRACTIONALKNAPSACC
0.24
0.17
0.08
0.05
0.03
0.02
Similarly, Figure 3 depicts length OOD on the full attention head the KNAPSACK problem, classic dynamic program corresponding to tropical circuits. Each model begins sharp in distribution, but the Tropical Attention head maintains the same activation pattern across each input length, strongly suggesting it has learned and internalized the underlying combinatorial problem and polyhedral structure vice the specific training data indicated by the vanilla and adaptive fading attention patterns.
Figure 2: Stacked attention head representations for QUICKSELECT under (a) Vanilla, (b) Adaptive, and (c) Tropical models. Fach model was trained on length sequences and was evaluated from Left to Right length 16 1024 sequences. Each image generated by batch of 32 inputs. The columns are the 8 largest keys by fg-norm. Heatmap values are the attention of the row item at the column key.

---

Table 4: We report classification accuracy for each task and the average accuracy across all tasks. All results are taken from their respective papers, except for Adaptive Softmax, which we re-implemented and evaluated.
Models
ListOps
Text
Retrieval
Image
Pathfinder
Avg.
Complexity
Transformer [26]
36.37
64.27
57.46
42.44
71.40
54.39
O(n²)
Longformer [64]
35.63
62.85
56.89
42.22
69.71
53,46
((n)
Linformer [65]
35.70
53,94
52.27
38.56
76.34
51.36
(nn)
Performer [66]
18.01
65,40
53.82
42.77
77.50
51,41
(nn)
Elliptical [67]
37.8
65.6
80.3
40.2
73.2
61.24
O(n²)
Fourierformer [68]
40.73
75.02
85.35
53.17
83,43
67.54
On log m)
MEGA [69]
63.14
90.43
91.25
90.44
96.01
86.25
On log m)
AdaptiveSoft. [27]
47.15
75.52
79.56
51.58
80.94
66.95
O(n")
Tropical Transformer
68.65
70.13
64.82
60.04
97.33
72.79
(nn²)
Figure 3: (top) Tropical Attention with sharp attention maps on learning the KNAPSACK algorithm, showcasing size-invariance and OOD lengths generalization behavior far beyond training (16 > 1024). In contrast, both (middle) adaptive-softmax and (bottom) vanilla-softmax heads dilute and disperse as sequence length grows, failing to generalize.
6 Conclusion
We introduced Tropical Attention, replacing noftmax-normalized dot-product attention with an attention mechanism that operates in tropical projective space. On the theory side, showed that multi-head Tropical Attention (MHTA) simulates tropical circuits and realizes tropical transitive closure via finite-depth compositions, with polynomial resource bounds (Theorem C.3, Corollary 1. Theorem 3.2). These guarantees provide principled account of scale-invariance and sharp, polyhedral decision boundaries, properties that essential for reasoning models expected to generalize beyond their training distribution. Empirically, across various combinatorial problems, Tropical transformer achieved SOTA out-of-distributin generalization, and delivered stronger noise robustness, while being much faster at inference with fewer parameters than the recurrent/iteratiee attention baselines. These findings carry an important message for both neural algorithmic reasoning (NAR) and Large Reasoning Model (LRM) communities: tropicalization of reasoning and going beyond softmax only enriches the algorithmic power of attention mechanisms but also yields tangible gains on reasoning tasks. We believe Tropical Attention opens compelling avenues for hybrid semiring architectures and for leveraging tropical geometry to reason over discrete structures within deep learning systems. Future work will explore sparse tropical kernels and applications to graph-theoreti, domains, aiming for ever-stronger generalization guarantees neural algorithm and reasoning synthesis.
10

---

Acknowledgments and Disclosure of Funding
This research was supported by the Excellence Cluster ORIGINS, funded by the Deutsche Forschungs- gemeinschaft (DFG, German Research Foundation) under Germany's s Excellence Strategy EXC- 2094-390733311, B.H extends his gratitude to the organizers and the wonderful instructors, Marta Panizzut and Margarida Melo, of the 2024 Trieste Algebraic Geometry Summer School (TAGSS) on Tropical Geometry, where the idea of the project was sparked. K.P., C.T. and R.Y. are partially supported by NSF Division of Mathematical Sciences: Statistics Program DMS 2409819.
References
Diane Maclagan and Bern Sturfels. Introduction to Tropical Geometry. American Mathematical Society, 2015. B.3
[2] Federico Ardila and Mike Develin. Tropical hyperplane arrangements and oriented matroids, 2007.
[3] Federico Ardila-Mantilla, Christopher Eur, and Raul Penaguiao. The tropical critical points of an affine matroid. SIAM Journal on Discrete Mathematics, 38(2):1930 1942, 2024.
Alex Fink and Felipe Rincón. Stiefel tropical linear spaces, 2015.
[5] Michael Joswig. Essentials Tropical Convexity. American Mathematical Society, 2021. 2,2,
[6] Kurt Pasque, Christopher Teska, Ruriko Yoshida, Keiji Miura, and Jefferson Huang. Tropical decision boundaries for neural networks robust against adversarial attacks, 2024.
[7] Ruriko Yoshida, Georgios Aliatimis, and Keiji Miura. Tropical neural networks and its applications classifying phylogenetic trees. In 2024 International Joint Conference on Neural Networks (IJCNN), pages 1-9, 2024. 3.1
[8] Ruriko Yoshida, Leon Zhang, and Xu Zhang. Tropical principal component analysis and application to phylogenetics, 2017.
[9] Petros Maragos, Vasileios Charisopoulos, and Emmanouil Thendosis. Tropical geometry and machine learning. Proceedings of the JEEE, 109(5):728-755 2021.
[10] Marie-Chard Charlotte Brandenburg. Georg Loho, and Guido Montúfar. The real tropical geometry of neural networks. arXiv preprint arXiv:240.111871 2024.
[11] Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. Tropical geometry of deep neural networks. In Jennifer Dy and Andreas Krause, editors. Proceedings of the 35th International Conference on Muchine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5824-5832. PMLR, 10-15 Jul 2018.
[12] Christoph Hertrich and Leon Sering. Relu neural networks of polynomial size for exact maximum flow computation. In International Conference Integer Programming and Combinatorial Optimization, pages 187-202. Springer. 2023.
[13] Davide Bacciu, Francesco Landolfi, and Danilo Numeroso. A tropical view of graph neural networks. ESANN 2023 proceedings, 2023. 1, 2.3
[14] Stéphane Gaubert. Tropical considerations in dynamic programming. Presentation at Optimization, Games, and Dynamics, Institut Henri Poincaré, Paris, November 2011. Based on joint work with Akian, Guterman, Allamigcon, Katz, Vigeral, McEncaney, and Qu. 1, B
[15] Stasys Jukna. Lower bounds for tropical circuits and dynamic programs. Theory of Computing Systems, 57(1):160-19) 194, October 2014. 1, C.I
[16] Michael Galkin. Graph & Geometric ML in 2024: Where we are and what's next, 2024. Medium Article.
[17] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03811 03889, 2018. 1, 1,
[18] Michael Joswig and Benjamin Schröter. Parametric shortest-path algorithms via tropical geometry. Mathematics of Operations Research, 47(3):2065 August 2022. I
[19] Mehryar Mohri Semiring frameworks and algorithms for shortest-diste distance problems. Journal of Automato, Languages and Combinatorics, 7(3):321-350) 2002.

---

[20] Peter Höfner and Bernhard Möller. Dijkstra, floyd and warshall meet kleene. Formal Aspects of Computing. 24(4):459-476, 2012. 1
[21] Marek Cygan, Marcin Mucha, Karol Węgrzycki, and Michal Wlodarczyk. On problems equivalent to connolt)-onnvolution. ACM Transactions Algorithms (TALG), 15(1):1-25, 2019.
[22] Timothy M Chan and Qizheng Hc. More on change-making and related problems. Journal of Computer and System Sciences, 124:159-169 2022. 1
[23] Silvano Martello, David Pisinger, and Paolo Toth. New trends in exact algorithms for the 0-1 knapsack problem. European Journal of Operational Reseurch, 123(2)3325-333 2000.
[24] Karl Bringmann and Alejandro Cassis. Faster 0-1-0011-- 1-kaassack via near-convex min-plus wwwppplluuooootttiin arXiv preprint arXiv:2305.0154) 2023.
[25] Kyriakos Axiotis and Christos Tzamos. Capacitated dynamic programming: Faster knapsack and graph algorithms. arXiv preprint 1822:1802,006400 2018. 1
[26] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 2023. 1, 2.2, 4
[27] Petar Veličković, Christos Perivolaropoulos, Federico Barbero, and Razvan Pascanu, softmax is not enough (for sharp out-of of-distribution), 2024. 1, 2.2, 4, 5,4
[28] Ken M. Nakanishi. Scalable-softmax superior for attention, 2025. 1,2
[29] Yutao Sun, Li Dong, Barun Patra, Shuming Ma, Shaohan Huang, Alon Benhaim, Vishrav Chaudhary, Xia Song, and Furu Wei. A length-extrapolatable transformer, 2022. 1
[30] Ofir Press, Noah A. Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation, 2022.
[31] Shaoxiong Duan, Yining Shi, and Wei Xu. From interpolation to extrapolation: Complete length generalization for arithmetic transformers, 2024. 1
[32] Giovanni Luca Marchetti, Vahid Shahverdi. Stefano Mereta, Matthew Trager. and Kathlén Kohn. An invitation neuroalgebraic geometry. arXiv e-prints, pages arXiv-2501. 2025.
[33] Matteo Tiezzi. Michele Casoni, Alessandro Betti, Tommaso Guidi, Marco Gori, and Stefano Melacci. On the resurgence of recurrent models for long sequences-survey and research opportunities in the transformer era. arXiv preprint arXiv:2402.088 02312 2024.
[34] Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In International Conference on Learning Representations, 2020. 1,3.
[35] Artur Back de Luca, George Giapitzakis, Shenghao Yang, Petar Veličković. and Kimon Fountoulakis. Positional attention: Expressivity and learnability of algorithmic computation, 2025. 2.1, 2.3
[36] Pawan Kumar Pradhan, Sayan Rakshit, and Sujoy Datta. Lattice based cryptography Its applications, areas of interest & future scope. In 2019 3rd International Conference Computing Methodologies and Communication (ICCMC), pages 988-993, 2019. 2.1
[37] Robert R. Nerem, Samantha Chen, Sanjoy Dasgupta, and Yusu Wang. Graph neural networks extrapolate out-of-distributio for shortest paths, 2025. 2,
[38] Sadegh Mahdavi, Kevin Swersky. Thomas Kipf, Milad Hashemi, Christos Thrampoulidis. and Renjie Liao. Towards better -istt--iistti generalization of neural algorithmic reasoning tasks, 2023. 2.1, 2.3
[39] Xihan Li, Xing Li, Lei Chen, Xing Zhang, Mingxuan Yuan, and Jun Wang. Circuit transformer: A transformer that preserves logical equivalence, 2025. 2.1
[40] Andrew Joseph Dudzik and Petar Veličković. Graph neural networks are dynamic programmers, In Alice H.
Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. 2.1, 2.3
[41] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner. Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly. Jakob Uszkoreit, and Neil Houlsby, An image is worth 16x16 words: Transformers for image recognition scale, 2021. 2.2
[42] Gleb Rodionov and Liudmila Prokhorenkova. Discrete neural algorithmic reasoning, 2025. 2.2, 2.3
12

---

[43] Larisa Markeeva, Sean McLeish, Borja Ibarz. Wilffrid Bounsi, Olga Kozlova, Alex Vitvitskyi. Charles Blundell, Tom Goldstein, Avi Schwarzschild, and Petar Veličković. The clrs-text algorithmic reasoning language benchmark, 2024. 2.2,
[44] Euan Ong and Petar Veličković. Learnable commutative monoids for graph neural networks, 2022. 2.2
[45] Hao Xuan, Bokai Yang, and Xingyu Li. Exploring the impact of temperature scaling in softmax for classification and adversarial robustness, 2025. 2.2
[46] Gihyun Kim, Juyeop Kim, and Jong-Seok Lee. Exploring adversarial robustness of vision transformers in the spectral perspective, 2023. 2.2
[47] Stasys Jukna. Tropical circuit complexity. Limits of Pure Dynamic Programmming/by Stasys Jukna., 2023. 2.2
[48] Stefan K. Nielsen, Laziz Abdullaev, Rachel S. Y. Teo, and Tan M. Nguyen. Elliptical attention, 2024. 2.2
[49] Akhil Kedia, Mohd Abbas Zaidi, Sushil Khyalia, Jungho Jung, Harshith Goka, and Hacjun Lec. Transformers get stable: An end-to-end signal propagation theory for language models, 2024. 2.2
[50] Petar Veličković and Charles Blundell. Neural algorithmic reasoning. Putterns, 2(7): 100273, July 2021. 2.3
[51] Hefei Li, Chao Peng. Chenyang Xu, and Zhengleng Yang. Open-book neural algorithmic reasoning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024, 2.3
[52] Gleb Rodionov and Liudmila Prokhorenkova. Neural algorithmic reasoning without supervision. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[53] Dobrik Georgiev Georgiev, Danilo Numeroso, Davide Bacciu, and Pietro Lio. Neural algorithmic reasoning for combinatorial optimisation. In The Second Learning on Graphs Conference, 2023.
[54] Dobrik Georgiev Georgiev, Wilson, Davide Buffelli, and Pictro Lio. Deep equilibrium algorithmic reasoning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[55] Montgomery Bohde, Meng Liu, Alexandra Saxton, and Shuiwang Ji. On the markow property of neural algorithmic reasoning: Analyses and methods. The Twelfth International Conference on Learning Representations, 2024.
[56] Kaijia Xu and Petar Veličković. Recurrent aggregators neural algorithmic reasoning. The Third Learning on Graphs Conference, 2024.
[57] Wilfried Bounsi, Borja Ibarz, Andrew Joseph Dudzik, Jessica B Hamrick, Larisa Markeeva, Alex Vitvitskyi, Razvan Pascanu, and Petar Veličković. Transformers meet neural algorithmic reasoners, 2025.
[58] Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Joseph Dudzik, Matko Bošnjak, Alex Vitvitskyi, Yulia Rubanova, Andreea Deac, Beatrice Bevilacqua, Yaroslav Ganin, Charles Blundell, and Petar Veličković. A generalist neural algorithmic learner. In The First Learning on Graphs Conference, 2022. 2.3
[59] Yunhui Jang, Dongwoo Kim, and Sungsoo Ahn. Graph generation with Sk^2S-trees. In The Twelfth International Conference on Learning Representations. 2024. 2.3
[60] Baran Hashemi, Roderie Guigo Corominas, and Alessandro Giacchetto. Can transformers do enumerative geometry? In The Thirteenth International Conference on Learning Representations, 2025. 2.3
[61] Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mchdi Bennani, Róbert Csordás, Andrew Joseph Dudzik, Matko Bošnjak, Alex Vitvitskyi, Yulia Rubanova, Andreea Deac, Beatrice Bevilacqua, Yaroslav Ganin, Charles Blundell, and Petar Veličković. A generalist neural algorithmic learner. In Bastian Rieck and Razvan Pascanu, editors, Proceedings of the First Learning on Gruphs Conference, volume 198 of Proceedings of Machine Learning Research, pages 2:1 2:1-2:23, PMLR, 09 12 Dec 2022. 2.3
[62] Andrew Joseph Dudzik, Tamara von Gichn, Razvan Pascanu, and Petar Veličković, Asynchronous algorithmic alignment with cocycles. In Learning on Graphs Conference, pages 3-1. PMLR, 2024. 2.3
[63] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang. Sebastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient transformers. In International Conference on Learning Representations, 2020. 4
[64] Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long- documeetn transformer. arXiv preprint arXi::2004.05/500 2020. 4
13

---

[65] Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint urXiv:2006.04768, 2020.
[66] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint 2iv:990009. 14794, 2020. 4
[67] Stefan Nielsen, Laziz Abdullaev, Rachel SY Teo, and Tan Nguyen, Elliptical attention. Advances in Neural Information Processing Systems, 37: 177:19944-1099 17988999799 2024.
[68] Tan Nguyen, Minh Pham, Tam Nguyen, Khai Nguyen. Stanley Osher, and Nhat Ho. Transformer with fourier integral attentions. arXiv preprint arXiv: 2022. 4
[69] Xuezhe Ma, Chunting Zhou, Xiang Kong, Junxian He, Liangke Gui, Graham Neubig, Jonathan May, and Luke Zettlemoyer. Mega: Moving average equipped gated attention. arXiv preprint arXiv:2209. 10655, 2022. 4
[70] Roan Talbut, Daniele Tramontano, Yueqi Cao, Mathias Drton, and Anthea Monod. Probability metrics for tropical spaces of different dimensions, 2024,
[71] MARIANNE AKIAN, STÉPHANE GAUBERT, and ALEXANDER GUTERMAN. Tropical polyhedra are equivalent to mean payoff games. International Journal of Algebra and Computation, 22(01):1250001, February 2012. B
[72] Roger D. Nussbaum. Convexity and log convexity for the spectral radius, Linear Algebra and its Applications. 73:59- 122, 1986. Department of Mathematics, Rutgers University. B
[73] Michael Joswig and Benjamin Schröter. Parametric shortest-path algorithms via tropical geometry. Mathematics of Operations Research, 47(3):2055-2811, 2022. 2022. C.5.1
[74] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan. Trevor Killeen, Zeming Lin, Natalia Ginelshein, Luca Antiga, Alban Desmaison, Andreas Köpf. Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjic Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library, 2019,
[75] Wes McKinney. Data structures for statistical computing in python. In Proceedings of the 9th Python in Science Conference, SciPy 10, pages 51 - 56. SciPy, 2010. F
[76] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapcau, M. Brucher, M. Perrot, and E. Duchesnay. Seikit-learm Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011. F
[77] Charles R. Harris, K. Jarrod Millman, Stéfan J. der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río. Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585(7825)3357-36 362, September 2020. F
A Limitations
Although Tropical Attention is out performing in almost all algorithmic tasks, this study was conducted on combinatorial algorithms and we have not yet demonstrated how Tropical transformers can scale to perform on generative and autoregressive next-token prediction language tasks. In particular, the computational and memory overhead introduced by tropical operations and the tropical Hilbert metric could incur nontrivial runtime costs or scaling challenges.
B Tropical Geometry
The most fundamental component of tropical algebraic geometry is the tropical semiring T = (RUf-oo), @, O). The two operations @ and @ called tropical addition and tropical multiplication respectively, are defined as follows.
Definition B.I. For x, E R. their tropical sum is 2 = max(æ, y) their tropical product is x oo == + the tropical quotient of is Ø y I y.
14

---

For any E R, we have -00 ( = 0 and -00 : -cc. Thus -oo the tropical additive identity and 0 the tropical multiplicative identity. Furthermore, these operations satisfy the usual laws of arithmetic, namely associativity, commutativity, and distributivity. operations @ and C. While it is not a ring since it lacks an additive inverse, one may nonetheless generalize many algebraic objects over the tropical semiring, the study of these, in nutshell, constitutes the subject of tropical algebra. In order to have transition from classical arithmetic to tropical arithmetic need series of transition maps, which referred to as tropicalization.
set R [-oo} is therefore a semiring under the
Definition B.2. (The valuation map) Let d E N and write Rd the field of real numbers. A valuation on E is function val: R + R U -oo satisfying the following three axioms:
1. val(a)
+ a 0;
2. val(ab) = val(a) + val(b);
3. val(a + b) S max m (val(a), val(b)) V R.
One approach to tropical geometry, is to define tropical variety as shadow of an algebraic variety that involves logarithmic limit sets. Classically, the amoeba of variety its image under taking the coordinate-wise logarithm of the absolute value any point on the variety [14]. The logarithm turns ordinary multiplication into tropical addition:
val(æ = val(x) + val(y), 2, y Ry0. and satisfies the sub-additive inequality val(2 +) I max (ux((va((x) val(u)) +ogg2. Hence val Archimedean log map up to a harmless additive constant. For an input X c R we call
Trop(X) := val(X) T
its rropicalization. All subsequent reasoning, including attention weight computations, will take place in this max-plus space. When X is smooth manifold, Trop(X) is typically a curved domain whose "tentacles" encode asymptotic directions of X. Passing the max-plus algebra straightens those curves into polyhedral pieces. providing the piecewise-linens linear structure which Tropical Attention operates.
Definition B.3. (The tropical projective space (11.) We regard T as semimodule over the tropical semiring by coordinate-vn wise operations. Introduce
1441 == (l...., E R*+1,
T == (RU (-00))) {-o0)uth
Declare two points x. T++1 projectively equivalent, written x y. there scalar X B. such that y = x + Al441. The quotient
TP" =T+++/-
the tropical projective space. See for more details on tropical geometry.
Every class has unique representative with maximal coordinate equal to 0, so TP' identifies with the standard simplex A : (w Rd+ | max; Wt 0}. Attention weights produced by the softmax surrogate live in the
Euclidean simplex; Tropical Attention will instead output points of A interpreted tropically, guaranteeing sharp arg max behavior.
Definition B.4. (The tropical Hilbert projective projectvvee metric.) For := (#i,.... #d+1), y == (yi...., (d+1)...d++)) T put
du(z, v) = (max(z, - w.)) (min(x. vi) = diam 2 v).
where x S y denotes the coordinate-wise tropical quotient (æ1 - y,,... #d41 - (d+1) and diam its range.
The metric descends to TPd and enjoys two key properties:
1. Projective invariance. du(æ + clas1 y + elat1) = da (1r u) for all c E IR
2. Non-expansivveness of max-plus-affine maps [70]. Every tropical linear map A Td+1 4 T is I-Lipschitz: dul Az, Au) < dz)
These facts, due to Nussbaum and further developed by Akian Gauber,, furnish tight robustness guarantees, perturbing the inputs by in Hilbert distance changes the output of any compositional stack of tropical linear layers by most [71, 72].
C Proofs
Proof of lemma 3.1. If ox is valuation map. hence for all b H. have
15

---

1. 00( = -0;;
2. ex(ab) = (a + (b) 2;
3. v2(a + b) < max va(a), (b))
Property is immediate from the definition. For a, b 0, (ii) follows from log(ab) log + log b:
(ab) = log(ab) - À = (log 2) + (log - >) + A = (a) + (b(b) A. If cither factor is non-positive, both sides equal -oc, For (iii), note that when a, b > 0 we have
log(a + b) < max(log a, log b} + log
so subtracting À preserves the inequality; if a < 0 or < 0 the claim is trivial. Adding back the constant À to uy eliminates the offset in (ii) while leaving (i)-iii) unchanged, yielding the classical valuation coordinate-wil wist maps gives the vector-valued projection Φx : 1 + A which is therefore valuation map up to the projective (constant-shins equivalence native to tropical geometry.
V. Collecting the d
The main theorem here establishes that MHTA is an expressive tropically universal approximator max- max-plus dynamic programming for combinatorial optimization such that every function that can he computed by a finite max-plus circuit admits realization by finite-depth MHTA stack. The proof proceeds in three stages. First we show that single head a tropical map by computing finitely many such maxima in parallel. Finally, we prove by structural induction that stacking a finite number of blocks suffices to emulate an arbitrary max-plus circuit. With the first lemma we want to show that a single head can realize a weighted tropical max gate.
tropical max gate. Second, demonstrate that H-head block can realize
Lemma C.1 (eead-level Weighted @ gate). Let be a finite index set let (Zybes C. and {wehieJ C
There exists an attention head h" E [H), a query-token index i" E [N] > (f(5) j E J), and distinct seq indices t(j) E [N] such that, after one forward pass, the context returned at 1" is equal to
2 w3)
max my + JEJ
jEJ
Proof. aor fix h² and for every j E J, let's select distinet token position t(j). Then one can define the value (R')
vectors by v (h")
*())) xzj @ wy and (h") := -o for all r & {1(i)}. To enforce (3) it suffices to make $;- s(f) = 0
for j E J and 8 oo otherwise, because then c-- (h*) DeeJ @ (xy @ wy)) = maxje. J (2y + wx).
One can write every query/ key vector in block form a = (u (2) E Tdx=1 x T. Fix arbitrary first blocks (1)) and arrange
(0..... (o....,,, 0), (h*)
k (h*) (c) = (O......,, 0), JEJ,
so that du(a (b'), ( = and hence 8 t()) 0. For every irrelevant token r & (1()) set
k (h*) (0, 00 -r,): T, O,
so that the last coordinate differs from that of the query by ry; consequently du (g (h*) k(*²)) r, and 83"
( -r, Choosing r, large enough drives the score to oo in the semiring, ensuring that irrelevant tokens
do not influence the context. Equation (3) follows.
Lemma C.2 (Tropical affine layer). Let A E TMN and E TMM Embed (x1, INN T the values of tokens 6(1),-... ...,,(()) and add bias token whose value is fixed There exists MHTA layer with heads and dz such that, for each m E [M],
N
(mm) Ayp
+ j=1
(Am 2 x3)) @ bm.
where im is query token of head m.
Proof. For m E [M] and head h = m, we can apply Lemma C.I with J (I,..,,N,, input zy and weights
Ang to obtain + (Ams ① x2). Let the bias relevant to every head by assigning its key identical to the query, whence (mm) is
all m. Then, we give value bm in head m alone w((m), The context becomes the maximum of + (Amj ① 25) and bm. completing the proof.
L
16

---

Definition C.1 (Tropical circuit [15]). A tropical circuit is a finite directed acyelic graph whose source nodes labelled by variables 21..... Zn. and whose internal nodes labelled either by the operation tropical addition (u, v) + ① v max (u, I or by the operation tropical multipliattion (u.v) 1 u & v u + u. The circuit computes a map f T + T whose m outputs are designated sinks. A circuit is layered if every edge points from layer & to layer E ++1 for some topological layering (Lo...., LL We write depth(C) = and size(C) [C for the number internal gates.
Because tropical multiplication distributes over tropical addition, every such circuit computes a tropical polynomial, namely a tropical sum @ of finitely many monomials, each monomial being a tropical product O (classical summation) of subset of the indeterminates plus constant. A tropical polynomial in variables (21y...,,2)) Zn) has an expression of the form
P(z)
O
Geks
= max ASK
+
Σ
ER )=1
where eg E T and 6kj E N. Thus P is already the maximum of finitely many affine forms in z. Lemma C.2 therefore applies directly.
Theorem C.3 (Single- layer universality for tropical polynomials), Ler P T I a vector-valued tropical polynomial map whose m coordinates are P((z) Dusk, (Arx @ 2) @ bez. There exists a single (=1
MIIA layer with H = Et= Kg heads and dg. 2 whose tropical output (the collection of all head contexts before the de-valuation vo = exp) equals P(z).
Proof. For each output coordinate & one can allocate K2 heads, one per affine term Ars O ① beg. Lemma C.2 shows that affine map in head k), depositing its value at a fresh query token izk. Because the score of an irrelevant head is -o0, the contexts written to those tokens are ignored by all other heads. Finally, putting an aggregation head per output whose query token reads all tokens ie with score 0 and returns their o. namely maxe (Aek @ 2 $ bek) Pr(z). No de-valuation applied inside tropical computation, so the result equals P(=) the max-plus semiring.
Corollary C.3.1 (Depth-L. universality). Let F T -> T. output of a layered tropical circuit of depth L. Then, there exists an MHTA stack of I, successive layers which, on every x E (R>o)", produces
(( = F(val(z)).
Proef. We can apply Theorem C.3 each p()) succession, feeding the contexts of layer i (still tropical form) as the imputs to layer + 1. Because no Euclidean de-valuation occurs after all MHTA layers, the tropical composition is preserved.
Theorem C.4 (Simulation of max-plus Dynamic Programs). Let (S, E) be finite directed acyclic graph with [S| = N nodes and weighted edges {Wwe (U,))E C T. For M define
do + 1)
Wwe C du(()).
(0)
80.
us (u.o)EE
where vo E S is the source node. For every finite horizon T there exists MHTA depth T and N heads per layer such that the token values at layer equal the vector (du(t)) vES for all t T.
Proof. we label the tokens by the vertices of S. at layer i we store (t) the value field token v. To obtain d, + 1) let head = v whose query token is v. Then, one can apply Lemma C.I with index set J = { uu (u, v) E B)} input scalars x. = (t) and weights Wav. thereby producing du (t + 1) as context at token Since every head acts on em disjoint query tokens, all v E S are updated in parallel. Repeating for T layers unrolls the dynamic program, hence layer T realizes the horizon-T value vector.
Let (T (V. E)) be directed graph with (IVI = vz) and tropical weighted adjacency matrix (D E T=Xn). For & 2 0 the tropical power DOA encodes path weights of length k. Fix horizon T' E N and set the finite Kleene star
(T
o E TT
0=
For E 1 the horizon-T value vector is eT (T) co.
17

---

Theorem C.S (MITA learns tropical transitive closure). Given I (V. E) with [V| = n and adjacency D Tax", for every T N there exists MIIA stuck of depth T with heads per layer and head dimension du such that the token values at layer equal vi T and
0++1:=;; & vt (4=0,1.....
1).
particular, the output at layer equals vr (T) @ Uo.
Proef. Indexing tokens by (V) and store (w)) the value on token (u) at depth (4), we fix (v E V) and in layer (t), we assign head (h = v) whose query is token (v). Then, apply Lemma B.1 the index set (Ju u E V (u, v) E) with inputs (Iz vx(u) and weights (wav = Deu). The head returns at its query token
A (War 3 : MEJU
max Deu + (x);; 04 (v) =
u:(H..)EE
All (v E V) update in parallel because heads use disjoint query tokens; thus (n) heads suffice each layer. Iterating overt O...., T yields (UT). and by the path semiring semantics we have (uT D*(()) @vo). O
Corollary C.5.1. In tropical semiring and under the assumption that no negative cycle exist, shortest paths exist and are cycle-free, so their lengths are realized by paths of at most Kleene star truncates at (n 1) [73]. Thus, every shortest path uses at most (n 1) ares, hence
1) ares; consequently the infinite
; 1 ......... ( (
Therefore the MHTA stack of with depth T 2 n learns (D" @ 00)-
In the embedding space of MHTA, the feasible domain is polyhedron in parameter space on which shortest. paths exist and the Kleene is well-defined. The MHTA stack thus implements Bellman steps in the parameter space, thus combinatorics of feasible solutions are absorhed the polyhedral stratification. particular, the map (vo. 0) (0) & is tropical polynomial, and the Tropical Attention has sufficient ability learn such maps without recurrence. Hence, in principle, MHTA can learn closure map itself rather than step-hy-step recurrence.
D Comparison between vanilla attention and Tropical Attention
In this section, we compare the algorithmic view between vanilla attention and Tropical Attention.
Algorithm 1 Comparison between vanilla attention and Tropical Attention
function TRDP ATTENTION(X
d) Q' K', V <- lool ReI. (ecneer(())_anuuull chhunk(3)
A - Parameter (N)
Q + Q' - A, K + K' - A V V V-V-
function ATTENTION(X: n d)
Qaia max( Qui + W11))
Q. K, V linear X) .chunk(3)
À sinsum( id.
(1. Q.
Kyd mux(Ka1j + w
A softmax A/vā, 1)
Van m max(Voc; w.()))
O einsum( ij. jd + id, A, V)
return linear O)
Vi.j Dav + maxi Quii Kaja) mina(Quia Kaja)
function
S
vi,d: Cau +- max, (Saay + Vaja) (C)
return linear O)
end function
E
Dataset Details
Our evaluation suite covers eleven canonical problems?:
MloddWarshall Dataset. Each example is weighted directed graph with nonnegative edge weights; we compute the all pairs shortest-path distances with the Floyd- warshall algorithm and use the resulting distance matrix the regression target. Inputs are the flattened (zero-filled for missing edges) weight matrix with positional indices.
"Code used to generate data can be found in our public repository: https: thub. cwm Hoam/Baran-paaae / Tropical- Tropical-Attentic
18

---

QuickSelect Dataset. Each example is an unsorted list of integers together with order statistic k; the label is token-wise binary mask marking all positions that contain the k-th smallest value. Inputs provide per-element features (value and or a normalized rank proxy) in the original list order.
3SUM-Decision Dataset.
Each example consists a list of integers and target T; the label is any three distinct elements sum to T, and 0 otherwise. Inputs present per-token pairs [as, T) so the model can condition each element the common target.
Guubset-Sum-Decstiee Dataset. Each example is list of integers and target T; the label indicates whether subset sums exactly T. Inputs again use per-token pairs (es, T", and labels computed an exact programmingg subset-sum solver.
Balanced Partition Dataset. Given a multiset of integers, the goal is to split it into two subsets with minimal absolute difference of sums; the label a token-wise 0//1 membership vector for one optimal subset (chosen deterministically). Ground truth is produced via standard DP over achievable partial sums with a traceback canonical solution.
(-1 Knapsack Dataset. Fach instance provides item pains (1x; ur)) and capacity C: the label token-wise 0/1 mask for an optimal item set that maximizes total value under the weight budget. We compute ground truth with an exact synaaic--pogramnin solver and repeat C' on every token as an input feature.
Fractional Knapsack Dataset. Each instance also provides (oi, w.) and a capacity C: the lahel is a
per-item fraction in [0. 1] from the optimal fractional solution. Ground truth is computed by the canonical greedy algorithm that takes items in decreasing value-to- value-to-weight ratio.
of 2-D points; the label is for points on the convex hull and otherwise, Hull membership determined with standard monotone chain construction.
Convex Hull Dataset. Each example
Strongly Connected Components (SCC) Dataset. Each example is a dirccted graph; the label is a flattened n x n matrix where entry (i.j) is 1 iff nodes and j helong to the same strongly connected component. The graphs generated Erdōs-Réng However, make the dataset more challenging, we also added curvature the graph by adding communities to the graph. We ohtain SCC memberships using graph library routine and expose adjacency plus positional indices as inputs.
Bin Packing Dataset. Each example supplies item sizes and a single bin capacity; the label is token-wise 0/1 indicator of whether an item starts a new bin under First-Fit Decreasing applied to the clean sizes. Inputs include each item's 's size, the shared capacity, and normalized position index after sorting.
Minimum Coin Change (0/1) Dataset. Each instance contains multiset of coin values and target amount T; the label tosen-wise 0/1 mask for one optimal solution using the fewest coins (or the all-zero mask if no solution exists). Ground truth is computed with an exact dynamii-programming solver with traceback.
F
Training & Evaluation Protocol
This appendix complements the experimental setup outlined Sec. 4. We focus on the conceptual pipeline. The low-level engineering choices (e.g. logging cadence, file formats) are documented in the public code repository". The primary packages utilized in constructing our experiment is Pytorch [74], Pandas and Scipy [75], SciKitLearn [76], and Numpy [77]. The basic workflow is described below:
Dataset generation. For the selected combinatorial task we generate input and output pairs using the hyperparameters in Table 5
Model instantiation. shallow Transformer hidden width 64-is equipped with one of three attention mechanisms: Vanilla, Tropical, or Adaptive.
configured with 1 layer. 2 attention heads and
3. Optimization. We train for Nepech epechs using AdamW (10-3, constant, no warm-up). We use one NVIDIA Tesla V100 GPU train each model. Models trained with a sufficiently large batch size (500) training over 10M samples, took approximately 2.5 minutes to train. For more memory intensive graph models, our training time was approximately 45 minutes given small batch sizes of 16. The objective is chosen tas-task:
BCE with logits pooled binary tasks,
htttps://gi thub. ctt///b.ooaaaarrr htt.b/////aaaaaapp//rropee.eeee Aateecciinnttttioo//ooooo
19

---

wisen-wise BCE,
squared error regression tasks.
Nquch 100
4. Evaluation. After training reload the final checkpoint, generate test set, and compute (i) for classification tasks on the generated test set. We evaluate our models on in-distribution data (data generated using the same hyperparameters as during training) and on out-of -fft-fddiittibtiion (OOD) data using the hyperparameters described in Table using the OOD protocol described in Section 4. For Length OOD, all models were trained on sequence length of 8 and evaluated them at sequence length of 64, with the exception of the graph problems (FloydWarshall and SCC), which were evaluated on sequence length of 16. Perturbative Noise OOD, each input was perturbed with probability 0.5 with a random integer sampled from the task's perturbative noise range.
mean loss regression tasks and
Table 5: Training hyperparameters and data ranges for each combinatorial task. Each task trained with 10M samples, learning rate of 0.0001, input sequence length of 8, and no perturbations. The ranges in the table are used to draw random integer values for the given parameter within the data generation portion of the training.
Dataset
Epochs
Target Range
Weight Range
Value Range
OOD Value Range
Perturbative Noise Range
SubsetSuunDecssion
(1.10)
N/A
(-5.5)
(-20,20)
(10.30)
Knapsack
100
(10,20)
(1,10)
(1,10)
(11.21)
(10,30)
FractionalKnapsack
(10.20)
(1.10)
(1.10)
(11,21)
(1.5)
MinCoinChange
100
(10,20)
N/A
(1,10)
(11,21)
(1.5)
Quickselect
100
N/A
N/A
(1,10)
(11,21)
(1.5)
BalancedPurtition
100
N/A
N/A
(1,10)
(11,100)
(10,30)
BinPacking
100
(10,30)
N/A
(1.10)
(11,100)
(10,30)
ConvexHull
100
N/A
N/A
(0,10)
(11,21)
(1.5
CarocSumDecisiion
100
(-75,75)
N/A
(-20,20)
(-375,375)
(40,60)
FloydWarshall
100
N/A
N/A
(1,15)
(16,30)
(1.10)
SCC
100
N/A
N/A
0.001
0.1
N/A
*SCC uses a connectivity probability rather than an integer input value, hence the small decimal for Value Ranges and N/A for perturbatiove noise range. For perturbative noise range the connectivity switches with given perturbation probability.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and Introduction (Section 1) state exactly the three contributions that are later substantiated: the Tropical Attention mechanism, its thcoretical guarantees (Section and Appendix C), and the eleven-task OOD evaluation (Sections 4-5). No claims extending beyond those results are made.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not he perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the
results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section 5 acknowledges that our empirical validation is restricted to synthetic combina- torial tasks and that the extra max- max-plus operations and Hopical-Hilbert metric introduce non-trivial memory and runtime overhead, leaving broader domain generalization and scalable efficiency as open issues.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well sell-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated practice what the implications would be.
The authors should reflect the scope the claims made, c.g., if the approach was only tested on a few datasets or with a few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowicdged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory assumptions and proofs
Question: For cach thcoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are stated with each theorem in 3. Complete, formal proof' are given in Appendix C, and every lemma/theorem is numbered and crose-eefeeenced from the main text.
21

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in paper should be numbered cross-referenced.
All assumptions should clearly stated or referenced in statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The model, problem sets evaluated, and processes to produce problem set data are outlined in detail in 4, E, and F. Additionally, code will be provided in the supplementary materials and is maintained in github repository which will be made publicly available after the review period.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access the model. general. releasing code and data often one good way to accomplish this, reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of model checkpoint, other means that appropriate to the rescarch performed.
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reprodueibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily architecture clearly and fully.
model architecture, the paper should describe the
(c) If the contribution is new model (e.g.. a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g.. with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the of closed-sous source models, it may be that access to the model is limited some way (e.g.. to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: All data for experimentation was generated as outlined E, Code for data production. training. and testing will be provided in the supplementary materials. This code is maintained in a github repository which will be made public following the review period.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
22

---

Please see the NeurlPS code and data submission guidelines (https://nips..c/ppbll)
gui Subdee ssionPolicy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" acceptable answer. Papers cannot he rejected simply for including code, unless this is central to the contribution (e.g., . for a new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurlPS code and data submission guidelines (ht http:///nnt //tp://npps....pp cc/ cc/public/ ssi ssionPolli icy) for more details.
guides/ Cods//Coeeuulii
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify the training and test details (e-g.. data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Scction 4 provides a high level overview of training and testing. Appendix F provides details on optimization and data. Table provides full training hyperparameter. Further details provided in the code repository.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does paper report error bars suitably and correctly detined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least the experiments that support the main claims of the paper.
The factors variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap. etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean. is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions. the authors should be careful not to show in tables or figures rates). If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
symmetric bars that would yield results that are of range (e.g. negative
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
23

---

Justification:
Appendix F describes the GPU used to train the models and the training time required.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for cach of the individual experimental runs well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurIPS Code Ethics http://ttt//eeee.......o//t/t/tt
Answer: [Yes]
Justification: All experiments use synthetic; no personal, biometric, or sensitive information processed, and results are released under permissive license with usage guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [No]
Justification: There is direct or implicit socictal impact of our new attention mechanism.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considcrations (c.g., deploy- ment technologies that could make decisions that unfairly impact specific groups), privacy considcrations, and security considerations.
The conference expects that many papers will foundational research and not applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it not needed point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
particular
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitigation strategies gate release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place responsible release data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Released assets operate solely on small synthetic integer sequences and graphs; they have foresecable dual-us risk beyond existing open-source combinatorial libraries.
24

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We rely only on well-known open-source Python libraries (e.g. PyTorch, NumPy). Each is cited in Appendix F and its BSD/MIT license is acknowledged in the supplemental material; all other code and models were written the authors
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or datasct.
The authors should state which version the asset is used and, if possible, include URL..
name of license (e.g.. CC-BY 4.0) should be included each asset.
For scraped data from particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ hen/dataeess has curated licenses for some datasets. Their licensing guide help determine the license of dataset.
For existing datasets that papakagddd both the original license and the license of the derived asset it changed) should be provided.
this information not available online, the authors are encouraged reach out the asset's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The synthetic datasets and trained checkpoints are accompanied by README describing generation parameters, file format, and intended use (see supplemental material).
Guidelines:
The answer means that the paper does not release new assets.
Researchers should communicate details the dataset/codeemmddll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The study involves human subjects crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
25

---

Including this information in the supplemental material is fine. but if the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According the NeurIPS Code of Eahics, workers involved data collection, curation, other labor should be paid at least minimum wage country data collector.
15. Institutional review board (IRB) approvals or equivalent for rescarch with human subjects
Does paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: No human subjects research was conducted.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained TRB approval, you should clearly state this the paper.
We recognize that the procedures this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code Ethics and the guidelines their institution.
For initial submissions, do not include any information that would break anonymity (if applicabll)) such as the institution conducting the review.
Declaration LLM usage
Does the paper describe the usage of LLMs if it an important, original, or non-standard component of the core methods in this rescarch? Note that if the LLM is used only for writing, editing, formatting purposes and does impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Question:
Answer: [NA]
Justification: Large language models are not part the proposed method; any L.M assistance was restricted to writing support and has no bearing on scientific results.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, or non-standard components.
Please refer to our LLM policy should should not be described.
20055LL for what
26


Reviews:
[{"review_id": "24fahl48A4", "reviewer": "Reviewer_ehNV", "summary": "In this work, the authors propose a new attention mechanism to improve the OOD performance of transformers when they are trained to solve certain algorithmic tasks. Motivated by the observation that it is difficult for the standard softmax attention to execute length-independent (or value-independent) argmax/argmin operations that many dynamic programming algorithms rely on, the authors introduce a new attention mechanism based on the tropical semiring arithmetic. The tropical semiring arithmetic consists of binary maximum and binary plus operations, and hence an attention mechanism based on the tropical semiring arithmetic can naturally represent the recurrence structure in a dynamic programming algorithm for solving combinatorial problems. The authors carry out experiments on 11 combinatorial tasks and show that transformers equipped with the tropical attention mechanism achieve significantly better OOD performance.", "questions": "none", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I think that the idea of using a different set of arithmetics in the computation of the attention matrix is definitely interesting. The motivation of this work is clear and intuitive.\n\nHowever, the results of this paper are not surprising at all. Indeed, many of those combinatorial tasks considered in this paper can be solved by dynamic programming, and by construction, the Tropical Transformer architecture naturally represent some basic arithmetic operations (e.g. max-plus) in dynamic programming algorithms for these tasks. Beyond those synthetic combinatorial tasks, it is unclear whether or not the Tropical Transformer architecture will be useful for other more realistic tasks. The authors should really stress test the proposed architecture for more realistic tasks such as sequence modelling and natural language processing. Indeed, if the goal is to train a neural network to solve synthetic combinatorial tasks which can be solved by dynamic programming, why don't we just parameterize a recurrent network to mimic dynamic programming, and why is attention or the transformer architecture even relevant here?\n\nTherefore, even though I think that this work has a clear motivation, the problem setting is very narrow (i.e. restricted to solving simple algorithmic tasks) and I am not sure if the findings in this work add any value to the community. The superior OOD performance might be simply due to a better algorithmic alignment between the Tropical Transformer architecture and the dynamic programming algorithms that solve those synthetic combinatorial tasks. In neural algorithmic reasoning, this benefit of aligning to specific algorithmic structures is pretty well-known already.\n\nIn addition, the presentation of the empirical results is not very clear. For example, Figure 1 is difficult to understand, and I am not sure how the authors reach to the conclusion that Figure 1 shows \"the tropical attention maintains focus\". Based on what I can see, the tropical attention pattern still keeps changing from the left to the right.\n\nFinally, there are many typos in the paper. I recommend the authors spend serious effort to polish the writing, and add additional experiments on tasks beyond simple synthetic settings.\n\n=================\n\nThe authors did a very good job during the rebuttal by providing additional experiments on more complex tasks. I have adjusted my score accordingly.", "was_revised": true, "final_justification": "The authors have addressed my main concerns in my initial review. I increased my score accordingly.", "rebuttal": "> The results of this paper are not surprising at all....\n\nOur contribution extends beyond both DP tasks and \"mere arithmetic.\" Several of our evaluated tasks, such as Quickselect, 3SUM-Decision, Bin-packing and Convex Hull, are not solved by dynamic programming, yet Tropical Attention excels on them as well. More importantly, our work introduces a novel algebrogeometric framework to look at the geometry of reasoning kernels from a fresh perspective. Also, Tropical Attention is not only exchanging arithmetic, every component of it is based on both Tropical Algebra/Geometry, and is beyond mere arithmetic. This geometric perspective is the foundational contribution of our paper.\n\n> Beyond those synthetic combinatorial tasks...\n\nWhile the tasks are synthetically generated, they are far from simple. They represent fundamental combinatorial problems, some of them NP-Hard/Complete, that are notoriously difficult for standard architectures and were chosen specifically to stress-test OOD reasoning capabilities. For instance, prior work (2409.07154) has shown that even a task like Quickselect is extremely challenging for state-of-the-art models (we discussed this in sec. 2.2). By succeeding on these difficult foundational tasks, we demonstrate a core generalization capability that current models lack. Moreover, these algorithms are the core mathematical pillars (hence the neural modeling bottleneck) of many real world combinatorial optimizations tasks, from particle physics (jet reconstruction) and biology (phylogenetics) to routing and logistics (dynamic bandwidth allocation in wireless networks, online electric vehicle charging in smart grids), and Finance (online trading problems in financial markets). Finally, to provide further evidence of its general utility, we also evaluated our model on the **Long Range Arena (LRA)** benchmark, a standard for testing transformers on long-sequence tasks across text, image, and math domains. As shown in the table below, our Tropical Transformer achieves highly competitive, SOTA results, placing second overall in average accuracy across the benchmark's tasks. This strong performance shows that the benefits of Tropical Attention are not only to combinatorial problems and that it stands as a viable and powerful mechanism for general-purpose sequence modeling.\n\n| **Models**      | **ListOps** | **Text** | **Retrieval** | **Image** | **Pathfinder** | **Avg.** | **Complexity**        |\n|:----------------|:-----------:|:--------:|:-------------:|:---------:|:--------------:|:--------:|:----------------------|\n| Transformer     | 36.37 | 64.27 | 57.46 | 42.44 | 71.40 | 54.39 | $\\mathcal{O}(n^2)$ |\n| Longformer      | 35.63 | 62.85 | 56.89 | 42.22 | 69.71 | 53.46 | $\\mathcal{O}(n)$   |\n| Linformer       | 35.70 | 53.94 | 52.27 | 38.56 | 76.34 | 51.36 | $\\mathcal{O}(n)$   |\n| Reformer        | 37.27 | 56.10 | 53.40 | 38.07 | 68.50 | 50.67 | $\\mathcal{O}(n)$   |\n| Performer       | 18.01 | 65.40 | 53.82 | 42.77 | 77.50 | 51.41 | $\\mathcal{O}(n)$   |\n| AdaptiveSoft.   | 47.15 | *75.52* | 79.56 | 51.58 | 80.94 | 66.95 | $\\mathcal{O}(n^2)$ |\n| Elliptical      | 37.8  | 65.6  | 80.3  | 40.2  | 73.2  | 61.24 | $\\mathcal{O}(n^2)$ |\n| Fourierformer   | 40.73 | 75.02 | *85.35* | 53.17 | 83.43 | 67.54 | $\\mathcal{O}(n\\log n)$ |\n| MEGA            | *63.14* | **90.43** | **91.25** | **90.44** | *96.01* | **86.25** | $\\mathcal{O}(n\\log n)$ |\n| **Tropical**    | **68.65** | 70.13 | 64.82 | *60.04* | **97.33** | *72.79* | $\\mathcal{O}(n^2)$ |\n\n\n> Indeed, if the goal is to train a neural...\n\nThis is not the motivation and the goal of our work. We are trying to say that Softmax attention is flawed (2402.08164) and in order to go beyond the limits of it, one has to look at the problem from a different perspective. Our idea is that combinatorial algorithms - whether constructive, enumerative or search algorithms - have an important inductive bias resulting in a *sharp, polyhedral, hyperplane decision boundary*. Also, learning from Algebraic Geometry, where one linearizes the combinatorial computations using tropicalization and also by the fact that tropical circuits do have an expressive nature, we propose to map the reasoning core of Transformers (or any other attention based models), which is the softmax attention computation, to Tropical projective space. Although dynamic programming is a partial motivation, MHTA is motivated by the much broader class of combinatorial optimization problems. We have revised our manuscript to make sure that our message is conveyed properly and clearly.\n\n> In addition, the presentation of the empirical results is not very clear...\n\nFor Figure 1, the key takeaway is that **attention is not uniformly dispersed in tropical attention**. We directly follow the implementation and the discussion of Figure 2 in this recent study, (2410.01104) , which demonstrated that softmax attention disperses to the uniform distribution as the input size increases. We draw samples (per seq. length), and  calculate the attention scores from the correct target item (the query) to the top 8 keys, which are ranked by their vector norms. In Quickselect task the goal is to find the k-th smallest elements. For such tasks, *maintaining focus* means the ability to allocate a high attention score to the correct items, creating sharp spikes in the heatmap. On contrary, *losing focus* means the attention becomes spread out and disperse, across elements, with no single item receiving a high score. Figure 1 shows that the vanilla and adaptive softmax models (top two rows) exhibit attention fading, as sequence length increases, indicating their attention has dispersed. In contrast, the Tropical attention (bottom row) consistently shows bright, distinct bands, proving it continues to allocate sharp attention even at larger length sequences. Moreover, each panel evaluates the model on a new batch of independently drawn inputs of increasing length. Since the position of the target k-th element is different in each batch, the pattern of attention naturally changes to reflect the new data. We have corrected many typos and will make the camera-ready version of the manuscript more clear upon revision based on the comments of the reviewers.\n\nIf our comments resolve your concerns we would appreciate if you would consider raising your score!"}, {"review_id": "ZqQq2UJkzo", "reviewer": "Reviewer_rLzR", "summary": "The paper introduces a radically redesigned attention mechanism, replacing matrix-vector multiplication with a structure in which every sum becomes a max, and every multiply becomes a sum. The authors formally define multi-head tropical attention and prove that it can express any max-plus dynamic program. Empirical results are presented on combinatorial tasks such as Floyd–Warshall and bin packing, demonstrating superior performance compared to standard softmax attention on synthetic data. The paper also investigates out-of-distribution generalization with respect to sequence length, value ranges, and adversarial perturbations, consistently showing strong performance from tropical attention across these scenarios.", "questions": "What avenue do the authors see for tropical attention to become a viable attention alternative in practice?  Are there any issues with optimization with tropical attention?", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper addresses a timely and important question: softmax attention was not originally designed for algorithmic reasoning, but rather for natural language processing. Exploring how to modify attention to better suit algorithmic tasks is a compelling direction. The proposed approach is a truly radical reinvention of attention, challenging the fundamental role of matrix-vector multiplication, which is an extremely bold and ambitious step. Given the magnitude of this proposal, focusing on synthetic experiments seems reasonable at this stage.", "was_revised": true, "final_justification": "The paper proposes a novel idea. It is however written with very difficult to understand mathematical jargon.  The additional experiments in the rebuttal is the reason for increasing the score.", "rebuttal": "> What avenue do the authors see for tropical attention to become a viable attention alternative in practice? Are there any issues with optimization with tropical attention?\n\nThank you for the question. We see Tropical Attention as a strong alternative to the Softmax-family of attention kernels, particularly in problems with a combinatorial nature (searching or enumerating solutions or constructing combinatorial objects) and a length/value extrapolation requirement (reasoning tasks). Beyond the eleven problems evaluated in our work (and the recent LRA Transformer benchmark), We are aware of several teams investigating it's application in Phylogenetic inference in biology, Jet reconstruction in particle physics, logistics routing problems and Video-language models. Our own ongoing work, for instance, involves applying tropical Transformers to a logistic problem in the inventory of the fleet of U.S. Naval aircrafts. Regarding optimization, one issue that we also discussed in the limitations is the computational overhead of Tropical Attention due to the max/min implementation's complexity. We believe that this engineering challenge can be approached via the development of custom kernels or linearization tricks for tropical operations to achieving flash performance. The focus of this foundational paper was to introduce the Tropical Attention mechanism, establish its theoretical expressiveness, and demonstrate its empirical effectiveness on combinatorial (NP-Hard/NP-complete) tasks, thereby motivating future efforts in practical optimization.\n\nIf our comments resolve your concerns we would appreciate if you would consider raising your score!"}, {"review_id": "gOCV6jMcLj", "reviewer": "Reviewer_De71", "summary": "This paper introduces Tropical attention. A new formulation of attention based on strong prior results in Tropical geometry.\nThe authors introduce tropical attention formally in Section 3  in Definition 3.1, after extensively covering background materials in Section 2. To me there are three key points to this new method: 1) replacing matrix multiplication with max-plus matrix multiplication to obtain the Q, K and V matrices, 2) the Hilbert projective metric instead of $QK^T$ and softmax, 3) max-plus matrix multiplication of the V matrix and taking exponent of output.\nThe authors then provide theoretical guarantees on its expressivity and application to dynamic programming problems, which are well motivated in prior sections.\nFinally the authors provide empirical experiments on dynamic programming focused combinatorial tasks. The baselines used in these experiments are sensible and very competitive for these sorts of tasks using softmax attention. Finally, the authors analyse some attention maps for the problems finding tropical-attention scales best OOD.", "questions": "1. Was all data unique and newly generated by the authors for this study or was prior work such as https://arxiv.org/abs/2406.04229 used? If not why was new data required, as this limits comparison to other works?\n2. In Appendix D it is noted that the models are trained for many epochs. As we can generate synthetic data this is an infinite data regime, did the authors experiment with all unique data instead of epoching?\n3. In figure 3 caption it is stated “Left to Right on length 16 to 1024” but the figure titles say 8 to 1024, which is it?\n4. In the limitations it is states the computation and memory overhead of tropical attention is higher, exactly how much higher is it?\n5. What would the loss of a tropical attention model be compared to a softmax attention model when trained on general webtext? I highly recommend this to the authors during the rebuttal period to maximise impact of this work. A positive result here could increase my score, a negative would leave my score unchanged. Please note, “could” not “will”, I will take into account all rebuttal material during the rebuttal.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 4, "strengths_and_weaknesses": "# Strengths\n- The authors throughly introduce the tropical semi-ring and results required to understand their paper. Overall, the paper is very clearly written and results well presented with extensive citations for all claims made that are not presented in this paper.\n- The authors offer many theoretical results which back up their claims about tropical attention.\n- Competitive and often better accuracy results on dynamic programming tasks.\n\n# Weaknesses\n- There isn't too much focus on related works that study reasoning (length/value generalisation) for softmax attention and the tricks deployed to overcome the short comings of softmax attention.\n\n- The loss/perplexity of a model trained on general webtext with tropical attention compared to one trained with softmax attention is not provided.\n\n## Formatting Issues\n- Sometimes there is a space before \\citep and sometimes there isn’t, please be consistent.\n- In the summary of contributions there the bold comments are inconsistently followed by full stops.\n- In the summary of contributions point 3, there is inconsistent spacing between commas.\n- Axis labels on figures 1 and 2 are tiny.\n- A, B and C are referred to in the captions of figures 1 and 2 but not on the figures.", "was_revised": true, "final_justification": "# Why not higher\n- I don't think the novelty of using tropical attention in a transformer has \"groundbreaking impact\" in one or more areas of AI\n\n# Why not lower\n- The paper is or interest to the Algorithmic Reasoning and GNN communities to see their ideas through the lens of tropical attention.\n- A detailed analysis of the impact of different attention mechanisms is of value and novel.\n- The paper is clear, even if a little mathematically overloaded.\n- There is a good level of reproducible evaluation in the paper.\n- No ethical concerns\n\nI would like to note my confidence of a 3 related to some of the mathematical results in the paper, as highlighted in my rebuttal response, however I am more confident in my assessment of the empirical side of this work which I believe to be worthy of acceptance.", "rebuttal": "> There isn't too much focus on...\n\nThank you for this constructive comment. In the camera-ready version, we thoroughly discuss the wider premises of this research field and comment on them.\n\n> The loss/perplexity of a model trained on general webtext with tropical attention compared to one trained with softmax attention is not provided.\n\nWe thank the reviewer for this excellent suggestion. Given the short time we had in rebuttal for experimentation, we have conducted new experiments on the **Long Range Arena (LRA) ** benchmark, a standard for testing transformers on long-sequence tasks across text, image, and math domains. As shown in the table below, our Tropical Transformer achieves highly competitive, SOTA results, placing second overall in average accuracy across the benchmark's tasks. This strong performance shows that the benefits of Tropical Attention are not only to combinatorial problems and that it stands as a viable and powerful mechanism for general-purpose sequence modeling. \n\n| **Models**      | **ListOps** | **Text** | **Retrieval** | **Image** | **Pathfinder** | **Avg.** | **Complexity**        |\n|:----------------|:-----------:|:--------:|:-------------:|:---------:|:--------------:|:--------:|:----------------------|\n| Transformer     | 36.37 | 64.27 | 57.46 | 42.44 | 71.40 | 54.39 | $\\mathcal{O}(n^2)$ |\n| Longformer      | 35.63 | 62.85 | 56.89 | 42.22 | 69.71 | 53.46 | $\\mathcal{O}(n)$   |\n| Linformer       | 35.70 | 53.94 | 52.27 | 38.56 | 76.34 | 51.36 | $\\mathcal{O}(n)$   |\n| Reformer        | 37.27 | 56.10 | 53.40 | 38.07 | 68.50 | 50.67 | $\\mathcal{O}(n)$   |\n| Performer       | 18.01 | 65.40 | 53.82 | 42.77 | 77.50 | 51.41 | $\\mathcal{O}(n)$   |\n| AdaptiveSoft.   | 47.15 | *75.52* | 79.56 | 51.58 | 80.94 | 66.95 | $\\mathcal{O}(n^2)$ |\n| Elliptical      | 37.8  | 65.6  | 80.3  | 40.2  | 73.2  | 61.24 | $\\mathcal{O}(n^2)$ |\n| Fourierformer   | 40.73 | 75.02 | *85.35* | 53.17 | 83.43 | 67.54 | $\\mathcal{O}(n\\log n)$ |\n| MEGA            | *63.14* | **90.43** | **91.25** | **90.44** | *96.01* | **86.25** | $\\mathcal{O}(n\\log n)$ |\n| **Tropical**    | **68.65** | 70.13 | 64.82 | *60.04* | **97.33** | *72.79* | $\\mathcal{O}(n^2)$ |\n> Formatting Issues...\n\nThank you for such a detailed suggestions. We have revised and refined our manuscript accordingly. \n\n> Was all data unique and newly generated ...\n\nIn the beginning, we have started our study with various (**NP-Hard/NP-Complete**) combinatorial family of algorithmic tasks not present in CLRS30. We adapted three common tasks (Quickselect, Floyd-Warshall, and SCC) later in our experiments. For the three algorithms common to both our work and CLRS, we closely followed their implementation. So, all the datasets for this study were newly generated. This was necessary due to two fundamental incompatibilities with the CLRS-30 benchmark. First, there is a mismatch in data modality, our framework is designed for sequence and set-based inputs, while CLRS is exclusively graph-based. Second, our study focus on evaluating all three specific types of out-of-distribution generalizations, Length, Value, and Adversarial OOD, protocols which are not designed in CLRS setup. We will clarify this in the camera-ready version of the paper.\n\n> In Appendix D it is noted that ...\n\nWe appreciate this very constructive comment. Following your suggestion, we conducted new experiments with much larger datasets, 10M samples. These new results, detailed in the table below, reaffirm our original conclusions. In addition, all new experiments were conducted across four random seeds, and several tasks were updated from a predictive (regression) to a constructive (classification) format to provide a more direct assessment of algorithmic learning. We believe these changes, suggested by our valuable feedback, significantly enhance our findings.\n\n### 1. Out-of-distribution Micro-$\\mathrm{F}_1$ score under Length OOD test (top) and MSE for regression tasks (bottom).\n| Algorithm         |    Vanilla   |   Adaptive   |     Tropical     |\n| :---------------- | :----------: | :----------: | :--------------: |\n| ConvexHull        | 42.75 ± 2.06 | 48.25 ± 0.96 | **97.00 ± 1.15** |\n| Knapsack          | 41.06 ± 1.76 | 39.18 ± 2.59 | **60.00 ± 2.09** |\n| Quickselect       |  4.66 ± 5.98 | 22.89 ± 2.49 | **77.06 ± 3.78** |\n| BinPacking        | 60.75 ± 2.49 | 64.25 ± 1.09 | **66.01 ± 1.55** |\n| SCC               | 51.30 ± 3.91 | 56.50 ± 2.22 | **89.25 ± 3.49** |\n| SubsetSum         | 21.13 ± 2.45 | 22.75 ± 5.25 | **87.50 ± 6.45** |\n| BalancedPartition | 80.55 ± 2.91 | 91.90 ± 5.52 | **96.73 ± 3.50** |\n| 3SUM              | 80.00 ± 0.82 | 79.75 ± 0.50 | **82.75 ± 1.59** |\n| MinCoinChange     |  9.25 ± 1.86 | 17.98 ± 2.29 | **42.52 ± 1.47** |\n| :----------------- | :----------: | :---------: | :-------------: |\n| Floyd-Warshall     | 12.81 ± 4.03 | 1.31 ± 0.36 | **0.81 ± 0.08** |\n| FractionalKnapsack |  0.88 ± 0.06 | 0.86 ± 0.08 | **0.66 ± 0.10** |\n\n### 2. Out-of-distribution Micro-$\\mathrm{F}_1$ score under Value OOD test (top) and MSE for regression tasks (bottom).\n\n| Algorithm         |      Vanilla     |     Adaptive     |     Tropical     |\n| :---------------- | :--------------: | :--------------: | :--------------: |\n| ConvexHull        |   22.75 ± 3.59   |   23.77 ± 3.10   | **34.25 ± 1.71** |\n| Knapsack          |   38.87 ± 3.43   |   26.92 ± 1.33   | **49.67 ± 2.01** |\n| Quickselect       |   74.22 ± 2.30   | **74.30 ± 1.99** |   71.10 ± 3.11   |\n| BinPacking        |   67.26 ± 3.70   |   74.23 ± 1.51   | **78.54 ± 1.89** |\n| SCC               |   78.51 ± 3.08   | **81.38 ± 2.62** |   74.86 ± 5.01   |\n| SubsetSum         |   34.75 ± 6.60   |   28.50 ± 10.12  | **79.25 ± 5.38** |\n| BalancedPartition | **63.40 ± 4.29** |   56.57 ± 1.18   |   55.76 ± 5.63   |\n| 3SUM              |   26.00 ± 3.16   | **26.25 ± 3.50** |   22.00 ± 2.16   |\n| MinCoinChange     |   23.64 ± 4.07   |    2.20 ± 1.13   | **33.18 ± 5.64** |\n| :----------------- | :----------: | :----------: | :-------------: |\n| Floyd-Warshall     | 87.68 ± 5.65 | 56.30 ± 3.04 |   55.30 ± 4.36  |\n| FractionalKnapsack |  0.24 ± 0.12 |  0.17 ± 0.03 | **0.08 ± 0.03** |\n\n### 3. Out-of-distribution Micro-$\\mathrm{F}_1$ score under Perturbative Noise test (top) and MSE for regression tasks (bottom).\n\n| Algorithm         |    Vanilla   |     Adaptive     |      Tropical     |\n| :---------------- | :----------: | :--------------: | :---------------: |\n| ConvexHull        | 90.75 ± 2.22 |   91.00 ± 2.16   |  **96.00 ± 2.16** |\n| Knapsack          | 67.85 ± 3.19 |   68.36 ± 3.51   |  **74.67 ± 3.13** |\n| Quickselect       | 33.87 ± 7.11 |   34.82 ± 4.79   |  **57.22 ± 5.01** |\n| BinPacking        | 55.38 ± 5.10 |   60.64 ± 3.92   |  **61.19 ± 4.33** |\n| SCC               | 70.00 ± 5.98 | **71.33 ± 1.96** |    69.86 ± 4.17   |\n| SubsetSum         |  3.75 ± 1.50 |     3 ± 1.63     | **72.75 ± 10.01** |\n| BalancedPartition | 51.06 ± 2.66 |   57.06 ± 1.08   |  **57.29 ± 1.33** |\n| 3SUM              | 47.50 ± 9.47 |   49.25 ± 9.22   |  **65.25 ± 3.59** |\n| MinCoinChange     | 22.12 ± 2.75 |   18.44 ± 4.49   |  **33.75 ± 4.89** |\n| :----------------- | :---------: | :---------: | :-------------: |\n| Floyd-Warshall     | 7.54 ± 3.63 | 5.29 ± 2.56 | **4.39 ± 1.62** |\n| FractionalKnapsack | 0.05 ± 0.02 | 0.03 ± 0.01 | **0.02 ± 0.01** |\n\n> In figure 3 caption it is stated ``Left to Right on length 16 to 1024'' ...\n\nWe apologize for this confusion. The caption is correct. the evaluation was performed on out-of-distribution sequences of length 16 to 1024. The mention of length 8 refers to the training sequence length. We will revise the caption in the final version.\n\n> In the limitations it is states ...\n\nOur results shows that for shorter contexts, 64-128), our method is computationally on par with standard softmax attention, showing some negligible latency overhead. The significant increase in both computational and memory resources for longer sequences, $\\mathcal{O}(1000)$, which is a consequence of the max/min implementation's complexity, that computes the tropical projective distance matrix. We believe that this engineering gap can be filled via the development of custom kernels or linearization tricks for tropical operations to achieving performance parity. Our main focus in this foundational paper was to establish a novel theoretical viability and unique properties of Tropical algebraic geometry for reasoning and combinatorial models, while introducing several NP-hard/complete algorithmic tasks (beyond CLRS30) to the community. To best of our knowledge, this is the first study that not just use Tropical arithmetic, but incorporate deeper Tropical algebraic geometric tools to offer a fresh perspective on Attention mechanism.\n\n> What would the loss of a tropical attention ...\n\nThank you for this comment that made us motivated to push our results. As detailed in our response to your previous question, we run new experiments beyond the paper's original scope and evaluated our Tropical Transformer on the Long Range Arena (LRA) benchmark.\n\nIf our comments resolve your concerns we would appreciate if you would consider raising your score!"}, {"review_id": "27Z5obF0xm", "reviewer": "Reviewer_XE7o", "summary": "Dynamic programming algorithms usually correspond to circuits over a particular semiring -- (max, +), (min, max), etc. Therefore, any neural model that has to execute DP algorithms would need to perform the sharp min/max operations. However, Vanilla transformers relying on scaled dot product attention cannot approximate those operations outside of their training support -- as the size increases, the attention scores \"disperse\" (almost all attention coefficients on a given row become equal). For this reason, the paper proposes modifying the standard attention mechanism to a tropical attention mechanism, operating on the (max,+) semiring.\n\nThe paper also defines the tropical semiring, its associated operations, how a valuation map, to convert from Euclidean to tropical space, should behave, what Tropical projective space is, and what a distance metric on that projective space is. The distance metric possesses projective invariance (adding a constant to each vector's components will not change the distance metric) and non-expansiveness (Any tropical linear map would result in a lower or equal distance metric). Those properties are particularly favourable when it comes to value generalisation.\n\nThe authors proceed to define multi-head tropical attention (MHTA), utilising the above tools (e.g. the distance metric). The particular valuation map and the inverse rely on logarithmization and exponentiation, the attention scores are calculated using the distance metric, and the aggregation is performed on the (max,+) semiring (Imagine standard MHA with $\\sum$ replaced with max and multiplication replaced with +). The authors prove (Theorem 3.2 and Theorem A.3/4) that a stack of $T$ MHTA layers ($N$ heads/layer) can simulate any dynamic programming DAG circuit of $N$ nodes and depth $T$.\n\nThe newly proposed attention mechanism is compared against two baselines (vanilla transformer and adaptive temperature) on 11 algorithms and 3 different Out-of-Distribution (OOD) generalisation scenarios (length OOD/value OOD/adversarial attack). Quantitative results are often improved across the three OOD scenarios. Attention heatmaps suggest that Tropical attention is able to produce sharper attention coefficients even at larger scales.", "questions": "I have left several things in \"Weaknesses\", clearly detailing what is minor and what is major, with clear actionables. Please make sure you address them as well.\n\n   * From Appendix C, I was able to infer that, e.g. for graph problems, the adjacency matrix was flattened, but also that for SCC, the **directed graph is symmetrized**. This, from the POV of the algorithm, doesn't make sense... elaborate. Also, for SCC, does the value generalisation mean we change the edge probability? The appendix also doesn't mention how graphs are generated (Erdos-Renyi/Barabasi-Albert/etc.?) \n      \n      (Here's one good reason to use GDM's benchmarks)\n* When would standard attention be preferred over tropical? Apart from this study being conducted on synthetic data, are there any other limitations to your approach?\n* How does tropical attention perform when producing a solution? Currently, e.g., shortest path distances are provided, but they don't provide the optimal path(s)... In the case of knapsacks, only the optimal value is provided, but not which items to take...\n   \n   (Yet another reason to use GDM's benchmarks is that they evaluate on solutions provided, not on regressing towards the value of the solution, which in NAR is seen as a simpler problem)\n\n* Is the $N$ for the graph size in Theorem 3.2 (L255) the same $N$ as the one used in L257? If not, what's the minimum number of heads/layer?\n* Shouldn't the architecture be a recurrent one? After all, the larger the input problem size, the larger the DP circuit becomes, and the deeper the architecture should be. One way to model variable depth is recurrence.\n* Heatmaps of length 1024 are provided, but results only show 8 to 64 generalisation. Why were other sizes omitted?\n* Vanilla vs adaptive attention heatmaps look almost identical (esp. in Figure 1) Why do we not notice any increase in sharpness, that the original authors observed?\n* If adaptive attention changes the temperature based on **problem size** (N.B. not values), why is it included in Value OOD? In the case of Value OOD, how was the adaptive parameter calculated? Appendix D doesn't report if size is changed for value OOD.\n* For adversarial OOD, do the authors check if the perturbation changes the algorithm's output?\n* Why is the attention map (almost) identical irrespective of size in Figure 2, bottom row? Shouldn't the heatmap be different for different inputs?", "limitations": "yes, although I don't think those are the key limitations...", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Strengths\n* Clear motivation for the paper\n* Theoretically founded architectural change (not a result of random architectural search)\n* Universal approximation guarantees\n\n# Weaknesses\nI'll tag some of the weaknesses as \"minor weakness\" -- if your paper contained **only** minor weaknesses, you would be around \"borderline accept\" with chances for \"accept\" if you are very convincing during the rebuttal, that, e.g., those are not bugs but features. If I don't say explicitly that something is minor, please consider it a major issue.\n\n* **We have gone full circle** (minor) -- It is hard not to notice that head outputs (equation right after L221) are $max$-aggregated and they very much resemble how a graph neural network (GNN) works, particularly a hardcoded one like pDAB [1]. The message function is the value of the neighbouring node minus the Hilbert distance. (btw, the Hilbert distance is piecewise linear, thus, the whole message function is linear and can be reliably approximated via a ReLU-based MLP [2], if you choose to learn it via gradient descent). The GNN aggregation function is the $max$ operator.\n   \n   We started from a transformer, replaced the attention mechanism with a tropical one, and ended up with a GNN with a max aggregator, an architecture known to perform well in NAR settings. I don't mean to diminish any contribution of yours, but I believe that the MHTA layer is very related to a max-aggregated GNN layer and this relationship should be elaborated/explored (and maybe exploited too!).\n* **Missing related work** (maybe a bit less, but still minor) -- Although not published in one of our top 3 conferences (NeurIPS/ICML/ICLR), the relationship between tropical algebra and GNNs has already been *theoretically* explored and accepted at a peer-reviewed venue([3]; I have left a hyperlink to the PDF). In fact, the paper authors also use logarithmization and exponentiation as pre- and post-processing steps. Their proofs focus on GINs, and the \"GNN\" here is slightly different, but I believe the two papers share a lot in common and should be discussed.\n* **Mathematically overloaded** -- I believe that in an effort to look theoretically sound, the authors have overcooked it. Particularly, the terminology could be made a bit more lightweight, in order to make the paper more accessible to a general audience. E.g. did we have to define amoebas of algebraic varieties (the definition of which, mind you, is assumed) in order to make a point that the logarithm makes a perfect valuation map? Please consider what parts are necessary to convey your message, what knowledge is assumed (and not defined) and improve the write-up accordingly.\n* **Unclear plots** -- It is not immediately clear to me what the rows in the attention maps are. Also, it is not clear to me what the authors mean by \"columns are the 8 largest keys by $l_2$ norm\". Please explain how the heatmaps are created in detail.\n* **Poor benchmarking** -- my major concerns lie here. Fixing **all** those is necessary for \"borderline accept\":\n   * To start with, the authors do not use any of the NAR canonical benchmarks (CLRS-30/CLRS-Text), nor do they give an explanation as to why. Both of those benchmarks can be used for data generation (when the algorithms are already implemented, e.g. quickselect or SCC) or expressing new algorithms (e.g. knapsack). Moreover, although the baselines provided there are written in JAX, any algorithm definition/data generation pipelines are framework-independent. \n      \n      The benchmarks allow us, reviewers, to more easily assess your contributions. For example, they define particular length OOD ranges, so one can measure the performance gains even for models/approaches not explicitly included in your baselines. They also include more complicated metrics (predecessor accuracy, etc.), so they can be seen as more challenging than the benchmark seen here. They even fix the test set so that everyone uses the same test dataset.\n\n      I strongly encourage the authors to use either of the two benchmarks -- the different OOD regimes can be achieved by choosing the appropriate sampler parameter. Alternatively, I expect a **very good** justification for why benchmarks released by Google DeepMind have been abandoned in favour of custom ones, particularly clarifying what drawbacks of the GDM's benchmarks we are avoiding here. \"Deep learning framework\" is not accepted as an answer here.\n\n\n    * The authors omit detailing their architecture hyperparameter choice (heads/dimensionality/number of layers) in the main text. They also conveniently omit to specify in the main text whether they use a recurrent MHTA layer or if the depth is fixed. I was surprised to see in Appendix D that:\n       * The architecture is of fixed depth (`experiments.py` confirms it, `SimpleTransformerModel` accepts `num_layers` arguments and loops over that many layers; the class also uses flags to specify if it's using tropical vs classical attention)\n       * The depth is 1, the number of heads is 2 (`jobs_to_do_train/evaluate` confirm it)... **across all architectures**.\n\n       According to the authors' theory, \"For every finite horizon $T \\in \\mathbb{N}$ there exists an MHTA network of *depth $T$*, using exactly $N$ heads [...] whose token values at layer $t$ equal the DP state vector\" ($N$ is the number of vertices in the DP circuit). I understand that the theory says nothing about non-existence, but in order for existence to be guaranteed, we need many more layers, and we would also need number of heads and layers to vary with problem size (If I my knowledge is correct, as the problem size increases the DP DAG's number of vertices increases too). \n\n        **I cannot vote for anything but rejection with such a discrepancy between theory and experimental setup.**\n\n        I also encourage the authors to re-evaluate **all** baselines where at least the number of layers is set to some fraction of the largest sizes observed during test time. None of the architectures should work with 1 layer and 2 heads, esp. when tested in an OOD regime.\n\n    * No standard deviations are provided -- please, include at least a couple of seeds (even 3 is better than 1) and provide aggregate statistics\n    * No GNN baselines are considered. The most powerful NAR models are often in the form of GNNs. Given my initial weaknesses listed, I do not see a reason to omit them.\n\n[1] Ong, E., Huszár, F., Lio, P., & Veličković, P. (2024). Parallelising Differentiable Algorithms Removes the Scalar Bottleneck: A Case Study. In ICML 2024 Workshop on Differentiable Almost Everything: Differentiable Relaxations, Algorithms, Operators, and Simulators.\n\n[2] Xu, K., Zhang, M., Li, J., Du, S. S., Kawarabayashi, K. I., & Jegelka, S. (2021, January). How neural networks extrapolate: from feedforward to graph neural networks. In International Conference on Learning Representations (ICLR).\n\n[3] Landolfi, F., Bacciu, D., & Numeroso, D. (2023). A tropical view of graph neural networks. In Proceedings of the 33rd European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning [(ESANN 2023)](https://www.esann.org/sites/default/files/proceedings/2023/ES2023-27.pdf).", "was_revised": true, "final_justification": "The authors did a strong rebuttal, hence I give weak accept.\n\nI keep it weak because as the authors say, there are conceptual similarities to prior work. As I have not explored the topic of tropical attention myself, I am happy to decrease my confidence.", "rebuttal": ">We have gone full circle...\n\nWe agree that equation you mention shows that a single MHTA head computes $h_i=\\max_j\\{\\,v_j-d_H(q_i,k_j)\\}$, an operation that can be written as message passing on the complete digraph with a max aggregator, yet two acts make this layer richer than a classical max-GNN: (i) the *edge weight* $d_H(q_i,k_j)$ is learned projections of both endpoints, so the effective graph structure is input-dependent rather than geometry dependent (this is also the classical debate that Transformers are special case of Graph Attentions or the other way around); (ii) all calculations are carried out inside the $(\\max,+)$ semiring, thereby preserving projective invariance and 1-Lipschitz continuity in Tropical Geometry, that disappear when one approximates the same score with a conventional ReLU MLP, whose exact replication would demand exponentially many linear regions. In particular, for any two points $q,k\\in\\Bbb R^{d+1}$ with $d_H = \\textrm{diam}(q-k)$ is the difference of the maximum and minimum of the linear forms $z\\mapsto z_i$, it is linear on every cone of the normal fan of the permutohedron, hence $d_H(z)=z_{i_{\\max}}-z_{i_{\\min}}$ is affine there. The permutohedron’s fan decomposes $\\Bbb R^{d+1}\\big/\\langle{\\bf 1}\\rangle$ into $(d+1)!$ such cones, one for each total ordering of the $d+1$ coordinates, so $d_H$ has exactly that many linear regions. A feed-forward ReLU network of depth $L$ and width $w$ can carve out at most $O(w^L)$ regions (Montúfar et al., 2014); therefore matching the factorial growth of $d_H$ with any constant depth forces $w\\ge\\Omega\\!\\bigl((d+1)!^{1/L}\\bigr)$, which is already $\\Omega(2^{d})$ for $L\\le d$ by Stirling’s approximation (see Jukna, Tropical Circuit Complexity). In contrast, a single MHTA head implements $d_H$ with no blow-up in width since $\\max$ and $\\min$ are native primitives of the $(\\max,+)$ semiring: we compute the two extremal coordinates in parallel and subtract, preserving projective invariance and avoiding the exponential cost that an ordinary ReLU-MLP would incur. Ultimately, we believe that the graph-theoretic view here actually complements our analysis, but far from reducing MHTA to a known GNN. Our study provides a fundamental, algebraic-geometric explanation for why max aggregation is so effective for neural algorithmic reasoning. The full tropical parameterization enhances the attention layer with provable expressivity, geometric inductive bias, and practical gains that conventional attention kernels have not been shown to possess.\n \n>Mathematically overloaded...\n\nOur intention in introducing concepts like amoebas was to provide deeper geometric intuition for the valuation map and to motivate the interested reader to explore the rich connections between neural networks and algebraic geometry. We see this work as a bridge between these fields and aimed to provide pointers for a specialized audience. However, we take your point that some of this may be overly specialized for a general ML audience.\n>Unclear plots...\nDue to the lack of space, we kindly refer you to our response to RehNV.\n\n>To start with, the authors do not use...\n\nIn fact we adopted their implementations, samplers and OOD length ranges for the overlapping tasks (Quickselect, Floyd-Warshall and SCC). However, our study ultimately centers on set-based attention and target not only length OOD, but value and adversarial noise OOD generalization setups. Therefore, we target a different and complementary slice of the algorithmic-reasoning landscape than the Google DeepMind benchmarks were designed for. CLRS’s objectives emphasise pointer supervision on graph-structured inputs (predecessor vectors, adjacency tensors, etc.), which is ideal for graph-message-passing models but forces an additional, decoding head that obscures the phenomena we wish to isolate, namely how replacing softmax by Tropical kernels alters the inductive bias inside attention itself. Moreover, eight of the eleven tasks we evaluate are NP-hard/complete optimisation problems (which were our initial targets) absent from CLRS but critical for testing whether a model can extrapolate combinatorial structure rather than execute a fixed polynomial-time routine. These tasks demand global, set-wise aggregation and expose the polyhedral geometry. Implementing them required custom setups, so for methodological consistency we retained a single, unified pipeline, inspired by the paper (2407.02793), instead of stitching two frameworks together. Furthermore, it is very important to emphasize that **our intention is not to beat a specific benchmark but to introduce a new theoretical methodology to the community that tries to resolve a fundamental drawback of softmax attention following tools from algebraic geometry**. Looking ahead and as a sequel paper to this study, we are working on a Tropical Graph model, that then it provides a head-to-head comparison to the SOTA NAR models. For the present paper, restricting to (set) sequence-level tasks, while inheriting CLRS code wherever applicable, allowed us to deliver a clean, controlled test of the theoretical contribution.\n>According to the authors' theory...\n\nThank you for this insightful question, that exactly gets to the heart of our model's expressive power. The theorem 3.2 only gives an **upper bound**, not a lower bound. We only state that depth = T and N heads are *sufficient* to simulate a horizon-T DP circuit; it does not say they are necessary. In fact, we even stress that the construction is without any architectural restriction, i.e. it is merely a capacity guarantee, not a minimal-complexity claim. Consequently, seeing the model work with depth one and two heads is not a contradiction at all. A finite-horizon DP can be expressed as a sequence of max-plus (associative and idempotent) linear updates, $v_{t+1} = M \\otimes v_t$. The entire $T$-step horizon can be collapsed by computing the tropical transitive closure~(Kleene star), $M^* = I \\oplus M \\oplus ... \\oplus M^{(T-1)}$, allowing the final state to be found in one-shot via $v_T = M* \\otimes v_0$ (1904.01082 incorporates this observation to analyze parametric shortest-paths). A single tropical-attention head computes $max_j(S_{ij} + v_j)$, thus it has a sufficient ability to learn a weight matrix that represents the transitive closure. Thus, the entire complexity of the multi-step process (as the solution space of Tropical polyhedron) can be encoded in the geometry of this shallow learned map (multiplexed in the feature dimensions of a single layer). Intuitively, **it is learning to identify the vertices and faces of the polyhedron that defines the combinatorial solution in the Tropical projective space**. Finally, because these operations exist in a geometry naturally described by the projective Hilbert metric, the learned piecewise-linear structure of the map $M^*$ is robust to certain changes in scale and length, providing a strong basis for OOD generalization. Hence, a shallow model has a theoretical justification for its power to approximate DP circuits and generalize beyond its training regime. \n>No GNN baselines are considered...\n\nIn this study we deliberately restricted baselines to softmax and adaptive softmax attention because the scientific question we want to isolate is: **What happens when we replace the softmax kernel of self-attention by a Tropical kernel, keeping everything else unchanged?** To keep that comparison clean and interpretable, we restricted baselines to the two main soft-max variants (standard and it's update, adaptive). As reviewers 2 and 3 also observed, our contribution is primarily fundamental, introducing tropical attention as a novel attention kernel. In this study, we do not intend to break any records on standard benchmarks for SOTA GNNs in NAR. We are interested in using combinatorial algorithmic reasoning tasks to showcase the OOD power of the tropical Attention in comparison to the vanilla and adaptive attention. We agree that evaluating tropical attention inside GNN architectures is a natural next step, and we view this paper as a foundation the community can build on to explore those richer variants.\n>From Appendix C...\n\nYou are correct; symmetrizing the graph for a directed task like SCC is incorrect. This was a remnant of a previous experimental setup that focused on simple connectivity in undirected graphs and was mistakenly carried over. We have now corrected this procedure afterwards. Indeed the value generalization means changing the inclusion an edge probability 0.01 during training and 0.1 during value OOD evaluation. The graphs were generated Erdős–Rényi as well. However, to make the dataset more challenging, we also added curvature to the graph by adding communities to the graph to make the algorithmic task more difficult for the networks. Above (response to R3), we are reporting the updated results from our experiments. \n>Why is the attention map...\n\nThe consistency of the attention map for the Tropical model across different sequence lengths is indeed the intended result and is an evidence for the paper's central claims on OOD generalization. Preserving the underlying geometry inherent to these combinatorial problems, the stable attention pattern demonstrates that the model has successfully learned the the underlying algorithm, structurally independent of the input sequence length. The model is not merely ignoring the input, rather, it has internalized the structure of the algorithm itself. The attention patterns for vanilla and adaptive softmax degraded and dispersed as sequence length increases, showing their inability to generalize algorithmically, whereas the Tropical model's stability provides strong evidence of having learned the sharp, scale-invariant reasoning required for such tasks.\n\n**(We could not finish our answers to your questions due to the insufficient remaining charecters here!)**"}]

Author rebuttal:

Meta-review: This paper proposes a simple and effective idea: by changing the semiring in attention mechanisms to the tropical semiring (rather than the conventional softmax-dot attention), attention-based neural architectures become better suited to represent, process and solve combinatorial optimization problems. The generalization performance of the approach is demonstrated on 11 combinatorial optimization tasks.

The paper's approach is simple, interesting and promising, and the experimental results are compelling. However, the experiments were perceived as somewhat toy by the reviewers. Also, the reviewers and the AC perceived the paper's presentation is somewhat "overloaded": The current exposition relies on a level of abstraction and formality that seems to go beyond what is necessary for the results. This risks obscuring the main ideas and may make the paper harder to follow than it needs to be. I recommend presenting the arguments in a more direct and concrete manner, with simpler notation and fewer technical detours, so that the central contributions are more transparent to the reader.
Decision: Accept (poster)