Petri nets, ReLU neural networks and tropical algebra meet at one operation, max. A timed event graph fires a transition when the last of its inputs arrives, which is a max over arrival times, and a ReLU unit is max(0, x). Each side has a published theorem behind it — Baccelli et al. for event graphs, Zhang, Naitzat and Lim for ReLU networks — and the two theorems land in the same algebra. The code that checks our end of this is pflow-tropical, a crate in pflow-rs. The connection between nets and networks reaches further than either theorem does, so this post marks where the theorems stop.
In tropical arithmetic, the sum of two numbers is their maximum, and the product of two numbers is their ordinary sum:
The tropical semiring (ℝ ∪ {−∞}, max, +) keeps associativity, commutativity and distributivity, with −∞ playing zero and 0 playing one. What it gives up is subtraction — nothing undoes a max — which is why it is a semiring and not a ring. It shows up wherever optimization meets discrete structure: shortest paths, scheduling, phylogenetics, and, as below, both Petri nets and neural networks.
Consider a timed Petri net: each place holds tokens, each transition fires when all its input places are ready. The key word is all. A transition with three inputs doesn't fire when the first token arrives, or the second — it waits for the last one. The firing time is the maximum of the arrival times.
That max is tropical addition.
After firing, a transition deposits tokens in output places. The arrival time at an output place is the firing time plus the transition's duration. That + is tropical multiplication.
The behavior of a timed event graph (a Petri net where every place has exactly one input and one output transition) can be written as a tropical matrix equation:
x(k+1) = A ⊗ x(k)
where x(k) holds the k-th firing time of each transition and ⊗ is tropical matrix multiplication. A is transition-by-transition, and it is not the incidence matrix: A[i][j] is the delay on the place that carries tokens from transition j to transition i, and −∞ where no place connects them. It is built from the same arcs C is built from, but C (places × transitions, signed) drops the producer-to-consumer routing that A needs. The equation is the simple case; initial markings with empty or multiply-marked places add lagged terms, which reduce to this form by closing over A or enlarging the state. Within those conditions the net's dynamics are linear over (max, +) rather than over ordinary arithmetic.
This is the core result of Baccelli, Cohen, Olsder and Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems (Wiley, 1992): timed event graphs are max-plus linear systems. Much of linear algebra has a tropical counterpart — eigenvalues and eigenvectors above all — and it applies directly to event-graph analysis.
In pflow-tropical, NetMatrix::tropical_adjacency builds this A from a net's arcs, using the consumer's input-arc weight as the delay. conjecture1.rs checks it against the discrete firing rule: on a two-transition loop and a three-transition cycle, the transitions with a finite entry in A^k ⊗ x(0) are exactly the ones enabled at step k. Those are the smallest cycles there are, and the test says nothing more general than that.
Now consider the most common activation function in deep learning:
ReLU(x) = max(0, x)
That max is, again, tropical addition. ReLU(x) is a tropical polynomial in one variable.
The observation extends well past a single neuron. Zhang, Naitzat, and Lim (ICML 2018) proved that a feedforward ReLU network computes a tropical rational function — a tropical quotient, which is an ordinary difference, of two tropical polynomials (exactly so for integer weights; real weights need real exponents). A ReLU classifier's decision boundary lies inside a tropical hypersurface. That is a theorem about what these networks compute.
ReLU networks have been doing tropical arithmetic all along.
Two edges of the triangle are theorems. Petri nets meet tropical algebra through Baccelli et al.: timed event graphs are max-plus linear. Hameed et al. (MDPI 2025) go the other way and present a max-plus perceptron as a Petri net. Neural networks meet tropical algebra through Zhang et al.: ReLU networks are tropical rational, and the polytopes attached to their tropical polynomials bound how many linear regions a network can carve its input into. The third edge, between Petri nets and neural networks, is ours and it is weaker. Where the theorems apply — event graphs on one side, ReLU networks on the other — both compute over (max, +), and we read the net as the structured case and the network as the learned one. A general Petri net, with choice and shared places, is not max-plus linear, so the edge holds for the event-graph fragment and no further.
We can arrange computational models along a spectrum, and tropical algebra says something about what the spectrum measures:
Petri net: We know the causal structure. We write it down as a net. Arc weights are small integers. For a timed event graph, computation is tropical-linear — a matrix-vector multiply over (max, +) — and the cycle time comes out of Karp's algorithm in polynomial time. A general net keeps the interpretability but not the complexity bound: reachability for unrestricted Petri nets is decidable but Ackermann-complete. The model is interpretable because the structure is the explanation. conjecture2.rs checks the structure/parameter split on small nets: across arc weights from 1 to 10, the P- and T-invariant supports, the sign pattern of each transition's effect and the enabling sequence stay fixed, while the tropical eigenvalue scales with the weight.
Recurrent neural network: We don't know the structure. We learn it via backpropagation. A dense weight matrix compensates for missing topology, and the weights are floats where, for a domain whose causal structure is known, we expect integers would do. A ReLU RNN unrolled over a fixed horizon is a feedforward ReLU network, so Zhang et al. apply and the computation is tropical-rational — still tropical, but without the structural guarantees that make the event-graph analysis tractable. (A tanh RNN, like the one in pflow-tropical's tests below, is outside the theorem.)
Large language model: We don't even know the task. We massively overparameterize — billions of weights trained on internet-scale data, through softmax and GELU layers that are not tropical, so the algebra has nothing to say at this tier. Our claim here is the argument of the small models thesis: for a problem with known causal structure, those billions of parameters approximate what a small structured model could compute exactly, if we knew what model to build.
Each step down the hierarchy trades domain knowledge for parameters. Tropical algebra makes the top two tiers precise — event graphs are tropical-linear, ReLU networks tropical-rational — and stops there.
If this framing sounds familiar, it's because Declarative Differential Models (DDM) and integer reduction already exploit the same insight from a different angle.
DDM's continuous relaxation converts a Petri net's discrete dynamics into ODEs. The system flows to an equilibrium that reveals structural quantities without enumerating the state space: accumulator places settle at x* = 1/n for n attached drain transitions (the decoupling lemma in The Incidence Reduction; the tests that assert it are linked from the paper post), and conservation laws hold along the whole trajectory. Integer reduction then recovers exact discrete structure from these continuous trajectories.
Tropical analysis does something similar. The tropical eigenvalue of a max-plus matrix (the maximum circuit mean, computed in pflow-tropical by Karp's algorithm) gives the asymptotic cycle time of a timed event graph — throughput is its inverse, and at λ = 1 the two coincide — a global structural quantity extracted from local topology, no state-space search required. It is only defined where the event-graph property holds, which is what makes it a boundary detector later on: the transitions it cannot see are the ones with ρ > 1. DDM's ODE equilibrium and the tropical eigenvalue are siblings: both extract invariants from structure rather than from exhaustive search.
The categorical perspective gives the kinship a frame, though not yet a theorem. Petri nets are morphisms in a symmetric monoidal category, and tropical algebra puts a weight on those morphisms — but the weight does not compose cleanly. Gluing two nets creates cycles that belong to neither, so the composite's λ is only bounded below by its components' (The Category Settle has the bound and the Karp-on-the-glue repair). DDM gives us a continuous relaxation. All three are tools for extracting meaning from structure.
The practical claim is the small models thesis: if you know your domain, build a Petri net, not a neural network, and expect the small net analyzed over the tropical semiring to be exact where the network is approximate. Nothing we have built measures that head to head — no parameter-count-versus-accuracy benchmark exists — so it stands as an argument. What pflow-tropical does have is narrower. rnn_petri.rs trains a small tanh RNN on random legal tic-tac-toe games generated from the net and checks that it beats a uniform guess over transitions. On the 18-transition core board with turn places, alternation holds in 50 of 50 self-play games because the net will not enable an out-of-turn move. On the same board without turn places, the test's own comment records the reward-seeking policy learning to let X move twice in a row; that count is printed, not asserted. It shows the kind of work structure does that a learned policy can't be trusted with, and it is not a benchmark.
The Lottery Ticket Hypothesis (Frankle and Carbin, 2018) found that dense networks contain sparse subnetworks that match the full network's performance. Our guess, untested, is that the winning tickets may have Petri-net-like topology — a tropical-linear substructure inside a tropical-rational network. TropNNC (Fotopoulos et al., 2024) works from the opposite end to the one Petri nets start from: it simplifies a trained network by reducing its tropical polynomial. Whether the reduced network looks like a Petri net is our question; TropNNC doesn't claim it. If it did, mechanistic interpretability could ask "does this network implement a Petri net?", and a yes — a tropical polynomial that factors into sparse, integer-weighted structure — would hand back the causal model the network learned to approximate.
Tropical decomposition of trained networks. Can we extract Petri net structure from a trained ReLU network by factoring its tropical polynomial? We have a first, small result. conjecture3.rs trains a one-hidden-layer ReLU network on next-marking data from a two-place loop and a three-place cycle, thresholds and rounds the learned per-transition deltas, and gets the incidence matrix's sign pattern back exactly on both. Two limits: the extraction reads the network's input–output deltas rather than factoring its weights (the test on the output weight matrix only checks that it factors to something sparse), and the nets have two and three transitions. TropNNC compresses networks but doesn't (yet) produce Petri nets. The gap between "simplified tropical polynomial" and "Petri net with named places and transitions" is a gap of interpretation, not algebra.
Tropical DDM. DDM uses ODE integration to find continuous equilibria. The max-plus half already runs — pflow-tropical computes the eigenvalue from the net's arcs with Karp — but the two compute different quantities, and the open part is whether one computation could give both. That would unify the ODE approach with the max-plus approach, and might be faster for large nets.
Maslov dequantization. The tropical semiring is a limit of ordinary arithmetic: define a ⊕ₕ b = h·log(e^{a/h} + e^{b/h}), keep ⊗ as +, and as h → 0 the sum becomes max. Maslov and Litvinov read h as Planck's constant — as it goes to zero the path integral concentrates on the classical path, and superposition becomes optimization (max). See Maslov's observation. Petri nets already have a discrete/continuous duality (DDM exploits it). Does the tropical connection extend this to a discrete/continuous/quantum triad?
For readers of the March version (revised 2026-10-14):
A is not the incidence matrix. The max-plus matrix is transition-by-transition and carries delays; C is places × transitions and signed. Said so, and linked the construction in pflow-tropical.x* = 1/n is the equilibrium of an accumulator place with n drains, not "the token distribution", and the ODE does not reveal reachable states.conjecture1–3, rnn_petri) as evidence; none were re-run for this revision. The online copy of Baccelli et al. no longer resolves, so the citation is now unlinked.For how tropical analysis combines with ODE and zero-knowledge proofs — three independent formalisms discovering the same structural boundary: Earned Compression
For the tropical semiring as the left context of a zipper — past accumulation meeting predicate future at the marking boundary: The Zipper Whose Hole Is a Universe
Related: The Pflow Square · The Category Settle · Structuralism, Not Objects