A ReLU neural network is literally a tropical rational map. This post takes that statement seriously and turns it into a working computational essay. We start with the max-plus semiring on its own terms -- defining the operators, building tropical matrices, running shortest-path and project-scheduling algorithms entirely inside the algebra -- and only then cross over to neural networks. By the end, we will have rewritten a trained ReLU classifier as a difference of two tropical polynomials, visualised its decision boundary as a tropical hypersurface, and used the tropical lens to derive three results that go beyond the standard literature: a much sharper, region-enumerated Lipschitz constant; a zero-data detector for dead neurons on any bounded input domain; and a zero-retraining network pruner that is provably exact on the chosen domain.
Every code block below is executable Wolfram Language. The cells have been pre-evaluated so the published notebook is self-contained: the reader sees both the code and its result without having to evaluate anything. Companion repository: https://github.com/mthiel74/TropicalAlgebravsReLU
To re-evaluate the cells yourself in a fresh kernel, place the two companion packages MaxPlus.wl and TropicalReLU.wl (downloadable from the repository above) in the same directory as this notebook and evaluate the cell below. Every analytical tool used later in the post -- TropicalPolynomial, TropicalEval, MPSchedule, MPCycleMean, MPLinearSystemEvolve, TropicalDecomposition, MPExactLipschitz, MPDeadUnits, MPPruneDeadUnits -- is defined in those two files.
SetDirectory[NotebookDirectory[]];Get["MaxPlus.wl"];Get["TropicalReLU.wl"];Needs["MaxPlus`"];
Primary reference: L. Zhang, G. Naitzat, L.-H. Lim, Tropical Geometry of Deep Neural Networks, ICML 2018 (arXiv:1805.07091). This essay extends their picture with concrete WL implementations of the standard tropical machinery (Maclagan-Sturmfels, Butkovic) and with the analytical tools in §18 that follow naturally from the tropical viewpoint but are not in the ICML paper.
Two windows on two algebras. Left: the smooth, continuous world of classical arithmetic (R, +, *). Right: the same landscape under (max, +) -- every operation produces a crisp polyhedral surface. The two are connected by a small bridge.
1. The max-plus semiring in 60 seconds
1. The max-plus semiring in 60 seconds
The tropical (max-plus) semiring is the set of real numbers extended with negative infinity,
R
max
equipped with two operations that look like the addition and multiplication of classical algebra but are:
a⊕bmax(a,b)
a⊗ba+b
The identities flip: the additive identity is (since = ), and the multiplicative identity is (since = ). Apart from the absence of additive inverses ( is a semiring, not a ring), every familiar axiom of a commutative ring carries over. Distributivity in particular:
-∞
max(-∞,a)
a
0
0+a
a
R
"max"
a⊗(b⊕c)a⊗b⊕a⊗c
It is worth pausing on what this re-labelling really buys you. Classical addition and multiplication are continuous and smooth, whereas has a non-differentiable corner. So every identity of ordinary algebra translates into an identity about piecewise-linear convex functions. Polynomials become piecewise-linear functions. Powers become repeated max-with-translation. The distributive law becomes the statement that a classical sum of convex piecewise-linear functions is again a convex piecewise-linear function -- a deeply non-obvious fact in ordinary analysis, but a trivial consequence of the semiring axioms once you have the right operator names. This is the lever the rest of the post pulls on.
Max
Why 'tropical'?
Why 'tropical'?
The name was coined in the 1980s by French computer scientists -- most often attributed to Christian Choffrut, working in the circle of Dominique Perrin, Jean-Éric Pin, and Marcel-Paul Schützenberger -- in honour of Imre Simon, a Brazilian-Hungarian mathematician (born in Budapest 1943, emigrated to Brazil after the 1956 revolution, professor at IME-USP) who pioneered the use of the semiring in formal language theory. There is no deeper geometric meaning -- 'tropical' is simply a tribute to where Simon worked. The algebra itself is as old as operations research: Bellman's dynamic-programming recurrences from the 1950s are implicit max-plus matrix-vector products. What is new is the use of the tropical lens in neural networks, which is the thread we will follow.
R
"max"
Idempotence: a new identity
Idempotence: a new identity
One identity of classical algebra is conspicuously not inherited: has no tropical analogue, because . The tropical sum of anything with itself is itself. This is the idempotence axiom, and it is the algebraic shadow of the fact that the maximum of a set does not change when you repeat its elements. A small numerical check makes the asymmetry concrete:
a+a2a
a⊕amax(a,a)a
(*Side-by-side:samesixnumericalexperimentsinbothalgebras*)GridJoin[{{"classical","=","tropical","=","reading"}},{{"3 + 5",3+5,"3 ⊕ 5",3⊕5,"⊕ picks the larger"},{"3 × 5",3×5,"3 ⊗ 5",3⊗5,"⊗ is the classical sum"},{"3 + 3",3+3,"3 ⊕ 3",3⊕3,"⊕ is idempotent: a ⊕ a = a"},{"3 × 3",3×3,"3 ⊗ 3",3⊗3,"powers become repeated translation"},{"3 + (-∞)",3+-Infinity,"3 ⊕ (-∞)",3⊕-Infinity,"−∞ is the tropical 0"},{"3 × 0",3×0,"3 ⊗ 0",3⊗0,"0 is the tropical 1"}}],
Read the rows top-to-bottom. Three is bigger than itself in neither algebra: classically adds new mass, tropically stays put. The bottom two rows pin down the role of the new identities -- absorbs (so it is the "tropical zero"), and absorbs (so it is the "tropical one"). Anyone meeting max-plus for the first time will want to hand-evaluate a few rows like these until the swap feels natural.
3+3
3⊕3
-∞
Max
0
Plus
Two arithmetic operations as physical actions. Left: three pillars of different heights; the tropical sum a ⊕ b ⊕ c picks the tallest. Right: the same three pillars laid end-to-end; the tropical product a ⊗ b ⊗ c stacks their lengths. No carries, no negative numbers -- max-plus arithmetic is what you would do if all you had was a ruler and the ability to compare lengths.
Operators in WL
Operators in WL
We attach the definitions of , , and to the System` symbols once, so the standard infix syntax just works. The Listable, Flat, OneIdentity, Orderless attributes give us elementwise behaviour, n-ary forms, and the simplifications a commutative associative operator should have.
CirclePlus
CircleTimes
CircleDot
Unprotect[System`CirclePlus,System`CircleTimes,System`CircleDot];System`CirclePlus[a_,b_]:=Max[a,b];System`CirclePlus[a_,b__]:=Max[a,b];SetAttributes[System`CirclePlus,{Listable,Flat,OneIdentity,Orderless}];System`CircleTimes[a_,b_]:=a+b;System`CircleTimes[a_,b__]:=Plus[a,b];SetAttributes[System`CircleTimes,{Listable,Flat,OneIdentity,Orderless}];System`CircleDot[A_?MatrixQ,B_?MatrixQ]:=Inner[Plus,A,B,Max];System`CircleDot[A_?MatrixQ,v_?VectorQ]:=Inner[Plus,A,v,Max];System`CircleDot[v_?VectorQ,A_?MatrixQ]:=Inner[Plus,v,A,Max];Protect[System`CirclePlus,System`CircleTimes,System`CircleDot];{3⊕7,3⊗7,{1,2,3}⊕{4,0,5},{1,2,3}⊗10}
2. Tropical vectors and matrices
2. Tropical vectors and matrices
A tropical vector or matrix is just a real array; what changes is the multiplication. The tropical matrix product replaces the usual "sum of products" with "max of sums":
What is the tropical matrix product computing?
What is the tropical matrix product computing?
The Kleene star
The Kleene star
3. Classical application -- shortest paths
3. Classical application -- shortest paths
is, in min-plus algebra, literally a tropical matrix-vector product. Iterating to a fixed point gives the Kleene star of the cost matrix, hence the entire all-pairs distance matrix.
Our convenience wrapper MPShortestPathDistances negates the cost matrix, runs the max-plus KleeneStar, and negates back:
4. Classical application -- project scheduling
4. Classical application -- project scheduling
5. Tropical polynomials in one variable
5. Tropical polynomials in one variable
A tropical polynomial in one variable is a max of finitely many affine functions:
6. Tropical polynomials in two variables
6. Tropical polynomials in two variables
7. Tropical eigenvalues -- Karp's algorithm (aside)
7. Tropical eigenvalues -- Karp's algorithm (aside)
You can skip this section on a first read -- it is a beautiful classical result inside the tropical algebra, but it is not used in the neural-network sections that follow. Included because the eigenvalue / cycle-mean duality is the prettiest illustration of the algebra's reach. Resume at §8 if you want to head straight for the ReLU connection.
8. ReLU = the tropical sum 0 ⊕ x
8. ReLU = the tropical sum 0 ⊕ x
We have spent half the post inside the tropical semiring with no neural networks in sight. The bridge to neural networks is a single observation: ReLU is the unit operation of the max-plus semiring.
9. The decisive identity
9. The decisive identity
A 1-hidden-layer ReLU network is a classical sum of ReLU units. The identity that turns a classical sum into a single tropical polynomial is
which, read tropically, says
The classical sum of two ReLU units is the tropical product of their tropical polynomials -- each unit contributing two monomials, the product giving four. This identity is the engine behind everything that follows.
Five random draws, two columns of equal numbers. The identity holds pointwise -- it is an algebraic equation, not an approximation.
10. Symbolic derivation: 2 1 1 network
10. Symbolic derivation: 2 1 1 network
Case 1. w > 0
Case 1. w > 0
Case 2. w < 0
Case 2. w < 0
11. Symbolic derivation: 2 2 1 network
11. Symbolic derivation: 2 2 1 network
With two hidden units we can already produce a non-trivial tropical rational (mixed signs) or a tropical polynomial with four monomials (both signs positive). Let
Both output weights positive
Both output weights positive
Apply the identity of §9 to the two ReLU units:
Mixed signs
Mixed signs
A proper tropical rational. Adding more hidden units of the same sign tropical-multiplies into P (or Q), doubling the monomial count in the worst case.
12. Other tropical-compatible layers
12. Other tropical-compatible layers
The ReLU tropical correspondence is not a one-off curio. Many standard deep-learning building blocks are already tropical:
Leaky ReLU
Leaky ReLU
Two monomials of slopes α and 1; for α in (0, 1) the leaky variant simply rotates the negative half of the ReLU off the x-axis. Still a degree-1 tropical polynomial.
MaxPool
MaxPool
A CNN built from convolutions + ReLU + MaxPool is therefore already a tropical rational map -- with no other operations involved.
Hard tanh
Hard tanh
Maxout (Goodfellow et al., 2013)
Maxout (Goodfellow et al., 2013)
Equivalently, a maxout unit IS a tropical polynomial. The hidden layer of a maxout network is a vector of tropical polynomials, and the whole network is a tropical rational map by construction -- no decomposition needed, no positive/negative weight split. From the tropical standpoint, maxout is a more natural activation than ReLU.
Skip connections
Skip connections
13. Train a tiny classifier and verify
13. Train a tiny classifier and verify
The two-moons dataset
The two-moons dataset
Architecture and notation
Architecture and notation
The training block
The training block
Now write the two forward passes explicitly and compare them:
One concrete forward pass, both ways
One concrete forward pass, both ways
14. Decision boundary as a tropical hypersurface
14. Decision boundary as a tropical hypersurface
15. Newton polytope of the trained network
15. Newton polytope of the trained network
16. Linear regions scale like n^2
16. Linear regions scale like n^2
17. A note on Maxout
17. A note on Maxout
18. Beyond standard papers
18. Beyond standard papers
The tropical viewpoint gives us three concrete capabilities that go beyond the standard "ReLU networks are tropical rationals" literature. Each is implementable in a few lines on top of the WL machinery already developed, and each is genuinely useful.
18.1 Lipschitz constant via region enumeration
18.1 Lipschitz constant via region enumeration
Standard upper bounds on the Lipschitz constant of a ReLU network multiply layer-wise norms and become loose -- often by a large factor. The tropical viewpoint replaces that bound with a direct computation: the maximum gradient norm over realised activation patterns.
18.2 Dead-neuron detection
18.2 Dead-neuron detection
A common failure mode of ReLU training is dead neurons: units whose pre-activation never goes positive on the data manifold, so the unit always outputs zero and never gets gradient. The standard detection method is to evaluate on a held-out set and check whether the unit ever fires. The tropical viewpoint gives a zero-data alternative.
18.3 Lossless minimisation
18.3 Lossless minimisation
Combining the two observations above gives a zero-retraining network pruner that is guaranteed exact on any bounded domain. The recipe: drop the never-active units (they contribute zero), and absorb the always-active units into an affine head (their ReLU is the identity on the domain of interest). The resulting smaller network -- plus a constant linear correction stored in the returned association as AffineHead -- computes exactly the same function as the original on the chosen domain. No approximation, no fidelity-vs-size trade-off.
For a wider trained network (say 64 or 128 hidden units), the fraction of always-active or never-active units typically grows. The minimiser above gives a principled, exact way to shrink the network without retraining and without measurable loss of behaviour on the operating domain -- a fundamentally different mechanism from standard distillation or quantization, both of which trade fidelity for size.
What else falls out
What else falls out
Several other results follow immediately from the same picture; we sketch them for completeness:
19. Putting it together
19. Putting it together
The whole story compresses into one table:
Everything that ReLU networks do, max-plus algebra already does -- and the last three rows are gifts that ordinary analysis does not give us.
References
References
L. Zhang, G. Naitzat, L.-H. Lim. Tropical Geometry of Deep Neural Networks. ICML 2018. arXiv:1805.07091.
D. Maclagan, B. Sturmfels. Introduction to Tropical Geometry. AMS GSM 161 (2015).
P. Butkovič. Max-linear Systems: Theory and Algorithms. Springer (2010).
I. Goodfellow, D. Warde-Farley, M. Mirza, A. Courville, Y. Bengio. Maxout Networks. ICML 2013. arXiv:1302.4389.
R. M. Karp. A characterization of the minimum cycle mean in a digraph. Discrete Math. 23 (1978), 309-311.
B. Hanin, D. Rolnick. Complexity of Linear Regions in Deep Networks. ICML 2019. arXiv:1901.09021.
Wolfram Community discussion on max-plus algebra (by the same author): https://community.wolfram.com/groups/-/m/t/162609
Companion repository: https://github.com/mthiel74/TropicalAlgebravsReLU
D. Maclagan, B. Sturmfels. Introduction to Tropical Geometry. AMS GSM 161 (2015).
P. Butkovič. Max-linear Systems: Theory and Algorithms. Springer (2010).
I. Goodfellow, D. Warde-Farley, M. Mirza, A. Courville, Y. Bengio. Maxout Networks. ICML 2013. arXiv:1302.4389.
R. M. Karp. A characterization of the minimum cycle mean in a digraph. Discrete Math. 23 (1978), 309-311.
B. Hanin, D. Rolnick. Complexity of Linear Regions in Deep Networks. ICML 2019. arXiv:1901.09021.
Wolfram Community discussion on max-plus algebra (by the same author): https://community.wolfram.com/groups/-/m/t/162609
Companion repository: https://github.com/mthiel74/TropicalAlgebravsReLU
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Tropical algebra of ReLU neural networks
by Marco Thiel
Wolfram Community, STAFF PICKS, May 28, 2026
https://community.wolfram.com/groups/-/m/t/3723836
by Marco Thiel
Wolfram Community, STAFF PICKS, May 28, 2026
https://community.wolfram.com/groups/-/m/t/3723836