Geometric Capacity of Transformers: A Tropical Geometry Perspective

Ye Su; Yong Liu

REVIEW 4 major objections 4 minor 1 cited by

Geometric Capacity of Transformers: A Tropical Geometry Perspective

T0 review · 4 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that a transformer's spatial partition capacity is governed by sequence length: in the saturated-head regime the number of linear regions scales as N^(d_model L), with multi-head per-layer complexity O(N^H).

desk verdict Correct single-head Voronoi observation and standard stability bounds; the headline tight-count theorem is unsupported because the lower-bound construction is impossible for a bias-free linear query projection. read the letter →

arxiv 2604.14727 v2 pith:DQAQH6FF submitted 2026-04-16 cs.LG

Ye Su , Yong Liu This is my paper · ORCID

classification cs.LG MSC 14T0552B0568T07

keywords transformerslinearregionstropicalgeometrypowerVoronoidiagrammulti-headattentionNewtonpolytopesequencelengthgeometricexpressivity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to measure transformer expressivity by counting how many linear pieces the network cuts in the query space. Its central claim is that in the zero-temperature limit, self-attention is exactly a power Voronoi diagram, and multi-head attention corresponds to the Minkowski sum of the heads' Newton polytopes. From this, it derives that multi-head per-layer complexity is O(N^H), and across L layers the saturated regime (H ≥ d_model) yields a tight Θ(N^(d_model L)) bound. The abstract states the bound as Θ(N^(min{H, d_model−1}L)); the body proves the saturated version. The paper further claims that finite-temperature softmax preserves these boundaries exponentially well away from ties, so the combinatorial skeleton is not a zero-temperature artifact.

What carries the argument

Power Voronoi diagram: a weighted nearest-site partition with cells {q : ∥q−k_j∥² − ∥k_j∥² ≤ ∥q−k_l∥² − ∥k_l∥²}. Log-lifting: representing values as e^(ṽ/τ) to avoid the zero-temperature collapse of value information. Newton polytope: the convex hull of exponent/key vectors whose normal fan is the routing partition. Minkowski sum: the multi-head potential's Newton polytope, whose normal fan equals the common refinement of the heads' fans. Tropical rational map: a difference of two tropical polynomials, giving the piecewise-linear structure. The chain of identities — argmax ↔ power distance, and fan(Minkowski sum) ↔ common refinement — carries the argument from single-head routing to deep tra

What would settle it

Set d_model=1, H=1, d_k=2, and N=3 and instantiate the Appendix F construction with W_Q an arbitrary linear map x ↦ (w1 x, w2 x) and keys k_j=(p_j, −p_j²/2). Compute max_j ⟨q,k_j⟩ for scalar x. Because q scales linearly with x, the max of the three linear functions switches at most at x=0, giving at most two intervals, not the three congruent cells claimed by Lemma F.1. This calculation settles whether the lower bound holds for the architecture as defined.

Watch

Extended reading notes

Core claim

The central discovery is a dictionary between attention and classical computational geometry. Taking the temperature to zero, argmax_j ⟨q,k_j⟩ equals argmin_j (∥q−k_j∥² − ∥k_j∥²), so the routing cells are exactly the cells of a power Voronoi diagram, with key vectors as sites and squared key norms as weights. The value matrix becomes a piecewise-constant vector field on these cells. For multi-head attention, the joint partition is the common refinement of the heads' normal fans, whose Newton polytope is the Minkowski sum of the individual head polytopes; that gives O(N^H) vertices per layer when H ≤ d_model. Across depth, combined with FFN hyperplanes, the paper claims a tight Θ(N^(d_model L

Load-bearing premise

The load-bearing premise is that each head's query projection can emit a vector with a constant coordinate — q=(x,1) — so the parabolic-lifting construction in the lower-bound proof partitions the input into N^d grid cells; under the bias-free linear query maps the architecture actually defines, that constant coordinate is not available.

Editorial extensions

If this is right

Sequence length is a genuine expressivity parameter: increasing N raises the number of linear regions, not merely the amount of context memory.
With a fixed parameter budget, splitting attention into H heads raises per-layer partition complexity from O(N) to O(N^H), giving a concrete combinatorial explanation for multi-head attention.
Depth compounds the gain multiplicatively; in the saturated-head regime the number of linear regions is Θ(N^(d_model L)).
Finite-temperature softmax leaves the partition intact: away from tie boundaries, value error, gradient deviation, and Hessian norm all decay like e^(−δ/τ), so the regions persist as robust, approximately affine cells.
If keys are normalized to equal length, the power Voronoi diagram degenerates to a standard Euclidean Voronoi diagram, making routing angular nearest-neighbor search; the complexity framework still applies.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Inference: The abstract's min{H, d_model−1} exponent and the body's saturated d_model exponent are not the same statement; readers applying the result to H < d_model should check which theorem governs, since the tight N^(d_model L) lower bound is proved only for H = d_model.
Inference: The constructive lower bound's query q=(x,1) assumes a constant coordinate that a bias-free linear projection W_Q cannot produce; if the architecture prohibits appended constants, the N^d grid construction is not realizable and a modified argument (biases, positional embeddings, or a nonlinear query map) would be needed.
Inference: A direct empirical test on trained transformers would count distinct attention-routing and FFN signatures over random queries; the framework predicts per-layer growth exponent H in N and depth exponent d_model L, sharper than the small-scale Monte Carlo slopes reported in the paper.
Inference: Because the finite-temperature deviation is exponentially small in margin/τ, the theory suggests the geometric skeleton survives quantization or pruning of the softmax band; whether this persists in trained models is a testable engineering question.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague — short version: the single-head Voronoi story is correct but old, and the finite-temperature bounds are standard softmax calculus. The advertised tight bound, Θ(N^{min{H,d−1}L}), is not supported. The abstract and body disagree, and the constructive lower bound in Appendix F uses q=(x,1) from a query projection W_Q that is defined to be a linear map with no bias. No such W_Q exists for the architecture described, and the proof later contradicts itself by setting W_Q^{(h)}=e_h^T, which gives a scalar query. So the N^d Cartesian grid that drives the recurrence is unrealizable. The upper bound may be fine—O(N^{d L}) for H≥d—but the matching lower bound is what makes the Θ claim, and it collapses.

What the paper does well: Theorem IV.3 (top-1 attention = power Voronoi) is correct, though it is just the polarization identity for dot products. The LSE stability estimates in Theorem VI.1 are standard and correctly derived. The experiments are honest enough for what they are: small Monte Carlo counts and exact vertex counts.

Soft spots in order of importance. First, the lower-bound bug above is load-bearing. Second, Theorem V.2's vertex bound for MHSA cites a true Minkowski-sum formula but then reads off O(N^H); for H=2, d=2 that formula gives O(N^2) while the true maximum is O(N), so the “maximally complex” reading is wrong in cases that matter. Third, the abstract's Θ(N^{min{H,d−1}L}) is not what the body proves (the body's tight claim appears only for H=d, as Θ(N^{d L})). Fourth, the log-lifting parameterization is a formal workaround that changes the asymptotic regime; the paper admits the topology is independent of it, so it adds little beyond vocabulary.

I don't think the central argument holds up. The paper is not a clear reject because it is incoherent on its own terms; it is a reject because the headline theorem is unproven and the stated construction is impossible. That said, the single-head Voronoi observation and the stability bounds are correct and could be recycled into a shorter, honest paper. My recommendation: don't send this to referees in its current form. If the authors fix the lower bound—or restrict the claims to upper bounds—it might deserve a look later. For now, desk.

Referee Report

4 major / 4 minor

Summary. The paper develops a Maslov-dequantization (zero-temperature) framework for self-attention and uses it to count linear regions of transformer blocks. The main claimed contributions are: (i) a proof that zero-temperature top-1 attention is exactly a power Voronoi diagram in query space; (ii) a combinatorial rationale for multi-head attention via Minkowski sums of headwise Newton polytopes, with vertex-count bounds O(N^H) and a saturated-regime bound; (iii) tight asymptotic bounds on the number of linear regions, stated in the abstract as Θ(N^{min{H,d_model−1}L}) and in the body as Θ(N^{d_model L}); and (iv) finite-temperature stability bounds showing that softmax preserves the piecewise-linear structure away from routing boundaries. The paper also includes visual experiments illustrating the Voronoi limit and growth of polytope vertex counts.

Significance. If the stated tight bounds were correct, the paper would provide a new, clean geometric explanation of why sequence length drives transformer expressivity, and the connection between zero-temperature attention and power Voronoi diagrams is a useful observation. The single-head Voronoi equivalence (Theorem IV.3) and the finite-temperature LSE inequalities (Theorem VI.1) are standard and correctly derived. However, the central tightness claim is not established: the constructive lower bound in Appendix F relies on a query projection that the architecture defined in the paper cannot produce, and there are internal inconsistencies between the abstract's exponent, Theorem V.2's saturated bound, and the upper-bound proof in Appendix E. As a result, the advertised Θ(N^{d_model L}) result is currently unsupported, and the paper's main contribution does not yet survive scrutiny.

major comments (4)

[Appendix F, Lemma F.1 and Theorem V.7] The lower-bound construction is not realizable in the architecture defined in Section III.D. Lemma F.1 requires q=(x,1)^T, i.e., a query with a constant second coordinate, but Q=XW_Q is bias-free and homogeneous. The proof of Theorem V.7 then sets W_Q^{(h)}=e_h^T, which produces a scalar query, not the 2D q=(x,1) used in the lemma. With a homogeneous query q=(a x,b x), the scores are x(a p_j − (b/2)p_j^2); for x>0 the argmax is independent of x, so the N-cell nearest-site partition of [0,1] is not realized. Consequently the Cartesian grid that starts the recurrence N_L=(N^d(2w)^d)^L is unattainable, and the Θ(N^{dL}) lower bound collapses.
[Abstract vs. Theorem V.7 / Corollary V.9] The headline claims are mutually inconsistent. The abstract states Θ(N^{min{H,d_model−1}L}) and a sharpened per-layer bound O((HN)^{d_model−1}); the body's Theorem V.7 and Corollary V.9 state Θ(N^{d_model L}) with upper bound O(N^{d_model L}); and Theorem V.2's saturated regime states O((NH)^{⌊d_model/2⌋}). These are different asymptotic exponents. Since the abstract is the paper's central advertised contribution, this is not a cosmetic inconsistency: the reader cannot tell which theorem is being claimed, and the abstract's version is not proved anywhere in the text.
[Theorem V.5 and Appendix E] The upper-bound proof does not follow from Theorem V.2 as stated. Theorem V.5 says it substitutes V_multi=O(N^{d_model}) in the saturated regime H≥d_model, but Theorem V.2's saturated-regime bound is O((NH)^{⌊d_model/2⌋}), which for fixed H=d_model is O(N^{⌊d_model/2⌋}), not O(N^{d_model}). Appendix E silently introduces a different bound C_d N^{min(H,d)} without deriving it from Theorem V.2. The bound itself may be salvageable by a direct Minkowski-sum argument, but the written chain from Theorem V.2 to Theorem V.5 is broken.
[Section V.B, Theorem V.5, Remark IV.5] The paper counts linear regions in the 'conditioned input space' R^{d_model} with the context keys K fixed, but the actual transformer input is X∈R^{N×d_model} and the keys also depend on X. Remark IV.5 explicitly states that the pullback of the partition to the input space is coupled and not a Cartesian product. Therefore the headline statement about the number of linear regions of transformers as functions of their input is not directly established by the conditioned query-space counting. The paper should either prove the corresponding statement for the full input space or consistently state its results as conditional on fixed keys.

minor comments (4)

[Throughout] Typos: 'Defination' in Theorem V.2; 'SAH' instead of 'SHA' in Corollary V.4; 'he originally smooth curves' in Figure 5's caption; inconsistent spacing in 'V oronoi'.
[Figure 6(a)] The measured Monte Carlo slopes for d=2, L=1 are ≈0.13, far below the theoretical exponent 2 claimed in Theorem V.7. The text attributes this to random initialization, but it would be helpful to state explicitly that the experiment measures average-case lower bounds, not the worst-case construction of Theorem V.7.
[Example V.3] 512^8 is about 4.7×10^21, not 1.1×10^21; the numerical value is not essential, but it should be corrected.
[Appendix D] The application of the McMullen bound O((NH)^{⌊d/2⌋}) is presented as the saturated-regime answer, but the earlier Gritzmann–Sturmfels sum gives O(N^d) for fixed H≥d. The proof should identify which bound is being used for which asymptotic regime and justify the fixed-H versus growing-H distinction.

Circularity Check

1 steps flagged · score 6.0 of 10

Multi-head O(N^H) bound is definitional via Ψ; tight Θ(N^{dL}) lower bound rests on an unrealizable query projection.

self definitional [Definition III.13; Theorem V.2 and Appendix D]
"Algebraically, the aggregate routing is governed by the tropical potential Ψ := ⊙_{h=1}^H f_h ... The resulting Newton polytope is the Minkowski sum of the constituent polytopes ... Theorem V.2 ... Following the Defination III.13, the effective Newton polytope of the aggregated representation corresponds to the Minkowski sum of the H individual single-head polytopes."

The paper defines the multi-head aggregate potential Ψ as the tropical product of head potentials and immediately identifies Newt(Ψ) with the Minkowski sum. Theorem V.2 then 'proves' the O(N^H) vertex bound by invoking this definitional identity. Thus the claimed multi-head complexity is a property of the paper's own definition of Ψ, not a consequence derived from the actual MHSA concatenate-and-project operation. The real operation is a linear combination of head outputs; an independent argument would be needed to connect its partition to the Minkowski-sum fan. As written, the O(N^H) bound reduces to the definition.

full rationale

The single-head Power Voronoi equivalence (Theorem IV.3) is self-contained and follows from the polarization identity, so that part is not circular. The finite-temperature stability bounds are standard LSE estimates and also independent. However, the central multi-head complexity claim is definitional: Definition III.13 defines Ψ as the tropical product and then Theorem V.2 treats the Minkowski-sum vertex count as the multi-head polytope complexity, making the O(N^H) bound true by construction rather than by analysis of the actual MHSA aggregation. Separately, the advertised tightness Θ(N^{dL}) is not established: Lemma F.1 requires q=(x,1)^T, but the architecture defines Q=XW_Q with no bias, so no homogeneous linear projection can emit a constant second coordinate; Theorem V.7 further sets W_Q=e_h^T, giving a scalar query, so the N^d Cartesian grid is unrealizable. This is a missing-support/correctness issue rather than a circular reduction, but it compounds the definitional circularity of the upper bound. No load-bearing self-citation was found; the citation to Su et al. [30] is not the core argument. Overall: partial circularity in the multi-head bound, with the tightness claim additionally unsupported.

Assumptions & free parameters 3 free parameters · 5 assumptions · 2 invented entities

The central quantitative claims require several assumptions beyond standard transformer definitions: the tropical limit as a proxy, the MHSA-as-tropical-product identification, a questionable vertex-count theorem application, an unstated constant-coordinate query projection, and omission of normalization layers. Log-lifting adds free degrees of freedom. These together make the headline bounds depend on significant ad-hoc scaffolding.

free parameters (3)

log-lifted values \tilde v_{j,c} = unspecified (arbitrary reals)
Introduced in Def. III.10 via v_{j,c}=e^{\tilde v_{j,c}/τ}; the tilde values are free and never determined by standard attention weights, giving the tropical representation extra degrees of freedom.
Voronoi grid sites p_j = p_j=(j-0.5)/N
Chosen in Lemma F.1 to force N congruent cells; construction-specific, not a general parameter of the architecture.
Sawtooth teeth w = w=⌊d_ff/(2d)⌋
Chosen in Theorem V.7's lower-bound construction to realize (2w)^d folds; depends on FFN width and is not learned or measured.

assumptions (5)

domain assumption Zero-temperature Maslov dequantization of softmax is a valid proxy for standard attention's spatial partitions.
Section III-C: the entire counting is done in the tropical limit, then asserted to persist at finite temperature via Theorem VI.1.
ad hoc to paper Newt(⊗_h f_h)=Σ_h Newt(f_h), so actual MHSA aggregation is represented by the tropical product of head potentials.
Definition III.13 defines Ψ as the tropical product rather than deriving it from concatenation and W_O; this makes the Minkowski-sum picture true by construction.
standard math The cited Gritzmann-Sturmfels bound on Minkowski-sum vertices with f_0(P_h)≤N yields O(N^H).
Appendix D cites [44], but the application appears incorrect: the Minkowski sum of two planar N-gons has O(N) vertices, not O(N^2), so the bound as used is not a valid vertex bound.
ad hoc to paper Query projections may emit q=(x,1) with a constant coordinate, or equivalently biases / appended constant features are allowed.
Lemma F.1 and the proof of Theorem V.7 require q=(x,1), but W_Q^{(h)}=e_h^T alone cannot produce a 2D query with a constant second coordinate; this assumption is never stated.
domain assumption LayerNorm / RMSNorm can be ignored in the strict theoretical limit.
Footnote 1 in Section III-E; standard practice for piecewise-linear counting, but it means the bounds apply to an idealized block rather than the full transformer.

invented entities (2)

Log-lifting parameterization
purpose: Preserve value information in the tropical limit by writing v_{j,c}=e^{\tilde v_{j,c}/τ}.
A formal algebraic device; Remark III.11 admits it defines a different asymptotic regime than a fixed value matrix, so it has no direct falsifiable content outside the paper.
Approximately linear regions at finite temperature
purpose: Claim the tropical skeleton persists under softmax.
A qualitative notion; Theorem VI.1 proves gradient/Hessian decay inside δ-stable regions but does not produce exact linear regions at any positive temperature.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Geometric Capacity of Transformers: A Tropical Geometry Perspective." pith.science (2026). https://pith.science/paper/DQAQH6FF

@misc{pith2026260414727,
  author       = {Pith},
  title        = {Pith review of: Geometric Capacity of Transformers: A Tropical Geometry Perspective},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DQAQH6FF}},
  note         = {Machine review of arXiv:2604.14727}
}

abstract

To quantify the geometric capacity of transformers, we develop a tropical-geometric framework for analyzing the spatial partitions induced by conditioned self-attention. In the zero-temperature limit, we show that fixed-key top-$1$ routing is exactly represented by a power diagram in query space, while an auxiliary log-lifted value parameterization yields a vector-valued tropical rational representation. For Multi-Head Self-Attention (MHSA) with sequence length $N$ and $H$ attention heads, the joint routing geometry is encoded by Minkowski sums of headwise Newton polytopes, giving an $\mathcal{O}(N^H)$ universal bound that sharpens to $\mathcal{O}((HN)^{d_{\mathrm{model}}-1})$ once the number of heads reaches the intrinsic dimension $d_{\mathrm{model}}$. Extending this analysis across depth $L$, we derive the first tight asymptotic bounds on the number of linear regions in transformers ($\Theta\!\left(N^{\min\{H,d_{\mathrm{model}}-1\}L}\right)$). We further show that finite-temperature softmax preserves the top-$1$ routing structure and admits exponentially decaying local approximation and differential bounds away from routing boundaries.

Figures

Figures reproduced from arXiv: 2604.14727 by the authors.

**Figure 1.** Combinatorial Explosion of Linear Regions in Transformers. Visualizing the exact spatial partitioning of a query space (dmodel = 2) by a tropical transformer with sequence length N = 4. As the network depth L increases from 1 to 3, the number of maximal linear regions N undergoes a staggering geometric expansion, strictly following our derived Θ(NdmodelL) bound. This topological metric demonstrates how deep composit… view at source ↗

**Figure 2.** Recursive spatial partitioning in a 2-layer MLP (d = 2). (Bottom) Layer 1 (n = 3 neurons) induces N1 = 7 linear regions via Definition III.2. (Middle) Structural space-folding: the ReLU activation enables subsequent hyperplanes to intersect the pre-activated regions. (Top) Layer 2 (n = 3) achieves a multiplicative expansion, yielding a theoretical maximum of N2 = 49 regions. The Obstruction in Transformers: While th… view at source ↗

**Figure 3.** , the introduction of these weights shifts the decision boundaries H away from standard midplanes, where the fulldimensional cells are defined by: Cj = q ∈ R dk | ∥q − kj∥ 2 − wj ≤ ∥q − kl∥ 2 − wl , ∀l ̸= j [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Visualizing the Geometric Rationale of Multi-Head Self-Attention via Minkowski Sums. To illustrate the combinatorial polytope gain from Theorem V.2, we construct 3D Newton polytopes for self-attention with sequence length N = 6. (Left) A single head yields a simple pol…

**Figure 5.** Figure 5: Visualizing the Power Voronoi Limit of Self-Attention via Maslov Dequantization. The attention routing in a 2D query space (q1, q2) is shown for temperatures τ ∈ 1.0, 0.5, 0.1, 0.001, with white stars marking keys and colors showing aggregated values. (Left) At τ = 1.0…

**Figure 6.** Figure 6: shows log–log plots under random Gaussian weight initialization. In [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]

**Figure 7.** Figure 7: Visualizing the Common Refinement of MHSA and FFN (PMHSA ∧PF F N ). To illustrate the geometric mechanism driving the complexity bounds in Theorem V.5, we present a simplified case with 2 tokens and 2 FFN neurons. (Plot A) The MHSA layer performs input-dependent routin…

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Laguerre Geometry for Interpreting Large Language Models
cs.AI 2026-07 conditional novelty 6.0 of 10

LLM concepts are Laguerre–Voronoi cells; Geometric Lens reads the exact cell of any hidden vector by isolating residual piecewise-linear flow from cross-token attention transport.

Reference graph

Works this paper leans on

54 extracted references · 5 linked inside Pith · cited by 1 Pith paper

[1]

Attention is all you need,

A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,”Advances in neural information processing systems, vol. 30, 2017

2017
[2]

A comparative survey of instance selection methods applied to non-neural and transformer-based text classification,

W. Cunha, F. Viegas, C. Franc ¸a, T. Rosa, L. Rocha, and M. A. Gonc ¸alves, “A comparative survey of instance selection methods applied to non-neural and transformer-based text classification,”ACM Computing Surveys, vol. 55, no. 13s, pp. 1–52, 2023

2023
[3]

Transformers and large language models for efficient intrusion detection systems: A comprehensive survey,

H. Kheddar, “Transformers and large language models for efficient intrusion detection systems: A comprehensive survey,” Information Fusion, vol. 124, p. 103347, 2025

2025
[4]

Explainability of vision transformers: A comprehensive review and new perspectives,

R. Kashefi, L. Barekatain, M. Sabokrou, and F. Aghaeipoor, “Explainability of vision transformers: A comprehensive review and new perspectives,”Multimedia Tools and Applications, vol. 85, no. 2, p. 115, 2026

2026
[5]

Are transformers universal approximators of sequence- to-sequence functions?

C. Yun, S. Bhojanapalli, A. S. Rawat, S. J. Reddi, and S. Kumar, “Are transformers universal approximators of sequence- to-sequence functions?” inInternational Conference on Learning Representations, 2020

2020
[6]

Attention is turing-complete,

J. P ´erez, P. Barcel ´o, and J. Marinkovic, “Attention is turing-complete,”Journal of Machine Learning Research, vol. 22, no. 75, pp. 1–35, 2021

2021
[7]

Statistically meaningful approximation: a case study on approximating turing machines with transformers,

C. Wei, Y . Chen, and T. Ma, “Statistically meaningful approximation: a case study on approximating turing machines with transformers,” vol. 35, 2022, pp. 12 071–12 083

2022
[8]

Theoretical limitations of self-attention in neural sequence models,

M. Hahn, “Theoretical limitations of self-attention in neural sequence models,”Transactions of the Association for Computational Linguistics, vol. 8, pp. 156–171, 2020

2020

Show all 54 references

[9]

Saturated transformers are constant-depth threshold circuits,

W. Merrill, A. Sabharwal, and N. A. Smith, “Saturated transformers are constant-depth threshold circuits,”Transactions of the Association for Computational Linguistics, vol. 10, pp. 843–856, 2022

2022
[10]

On the number of linear regions of deep neural networks,

G. Mont ´ufar, R. Pascanu, K. Cho, and Y . Bengio, “On the number of linear regions of deep neural networks,” vol. 27, 2014

2014
[11]

Bounding and counting linear regions of deep neural networks,

T. Serra, C. Tjandraatmadja, and S. Ramalingam, “Bounding and counting linear regions of deep neural networks,” in International conference on machine learning. PMLR, 2018, pp. 4558–4566

2018
[12]

Complexity of linear regions in deep networks,

B. Hanin and D. Rolnick, “Complexity of linear regions in deep networks,” inInternational Conference on Machine Learning. PMLR, 2019, pp. 2596–2604

2019
[13]

On the number of linear regions of convolutional neural networks with piecewise linear activations,

H. Xiong, L. Huang, W. J. Zang, X. Zhen, G.-S. Xie, B. Gu, and L. Song, “On the number of linear regions of convolutional neural networks with piecewise linear activations,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 46, no. 7, pp. 5131–5148, 2024

2024
[14]

Tropical geometry of deep neural networks,

L. Zhang, G. Naitzat, and L.-H. Lim, “Tropical geometry of deep neural networks,” inInternational Conference on Machine Learning. PMLR, 2018, pp. 5824–5832

2018
[15]

Tropical geometry and machine learning,

P. Maragos, V . Charisopoulos, and E. Theodosis, “Tropical geometry and machine learning,”Proceedings of the IEEE, vol. 109, no. 5, pp. 728–755, 2021

2021
[16]

Tropical attention: Neural algorithmic reasoning for combinatorial algorithms,

B. Hashemi, K. Pasque, C. Teska, and R. Yoshida, “Tropical attention: Neural algorithmic reasoning for combinatorial algorithms,” 2025

2025
[17]

The geometry of thought: Disclosing the transformer as a tropical polynomial circuit,

F. Alpay and B. Senturk, “The geometry of thought: Disclosing the transformer as a tropical polynomial circuit,”arXiv preprint arXiv:2601.09775, 2026

2026
[18]

Universal approximation bounds for superpositions of a sigmoidal function,

A. R. Barron, “Universal approximation bounds for superpositions of a sigmoidal function,”IEEE Transactions on Information theory, vol. 39, no. 3, pp. 930–945, 2002

2002
[19]

Transformers are expressive, but are they expressive enough for regression?

S. Nath, H. Khadilkar, and P. Bhattacharyya, “Transformers are expressive, but are they expressive enough for regression?” arXiv preprint arXiv:2402.15478, 2024

2024 arXiv
[20]

The expressive power of transformers with chain of thought,

W. Merrill and A. Sabharwal, “The expressive power of transformers with chain of thought,”arXiv preprint arXiv:2310.07923, 2023

2023 arXiv
[21]

Exact expressive power of transformers with padding,

——, “Exact expressive power of transformers with padding,”arXiv preprint arXiv:2505.18948, 2025

2025
[22]

The power of hard attention transformers on data sequences: A formal language theoretic perspective,

P. Bergstr”aßer, C. K”ocher, A. W. Lin, and G. Zetzsche, “The power of hard attention transformers on data sequences: A formal language theoretic perspective,”Advances in Neural Information Processing Systems, vol. 37, pp. 96 750–96 774, 2024

2024
[23]

Expressive power of graph transformers via logic,

V . Ahvonen, M. Funk, D. Heiman, A. Kuusisto, and C. Lutz, “Expressive power of graph transformers via logic,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 40, no. 24, 2026, pp. 19 569–19 579

2026
[24]

Inductive biases and variable creation in self-attention mechanisms,

B. L. Edelman, S. Goel, S. Kakade, and C. Zhang, “Inductive biases and variable creation in self-attention mechanisms,” inInternational Conference on Machine Learning. PMLR, 2022, pp. 5793–5831

2022
[25]

Understanding the expressive power and mechanisms of transformer for sequence modeling,

M. Wanget al., “Understanding the expressive power and mechanisms of transformer for sequence modeling,”Advances in Neural Information Processing Systems, vol. 37, pp. 25 781–25 856, 2024

2024
[26]

Theoretical constraints on the expressive power of rope-based tensor attention transformers,

X. Li, Y . Liang, Z. Shi, Z. Song, and J. Zhang, “Theoretical constraints on the expressive power of rope-based tensor attention transformers,” 2024

2024
[27]

On the expressive power of transformers for maxout networks and continuous piecewise linear functions,

L. Gu, L. Yang, and F. Zhou, “On the expressive power of transformers for maxout networks and continuous piecewise linear functions,”arXiv preprint arXiv:2603.03084, 2026. UNDER REVIEW 15

2026
[28]

Analysis on the number of linear regions of piecewise linear neural networks,

Q. Hu, H. Zhang, F. Gao, C. Xing, and J. An, “Analysis on the number of linear regions of piecewise linear neural networks,”IEEE transactions on neural networks and learning systems, vol. 33, no. 2, pp. 644–653, 2020

2020
[29]

On the number of linear regions of convolutional neural networks,

H. Xiong, L. Huang, M. Yu, L. Liu, F. Zhu, and L. Shao, “On the number of linear regions of convolutional neural networks,” inInternational Conference on Machine Learning. PMLR, 2020, pp. 10 514–10 523

2020
[30]

Sparsity is combinatorial depth: Quantifying moe expressivity via tropical geometry,

Y . Su, H. Tang, Z. Gong, and Y . Liu, “Sparsity is combinatorial depth: Quantifying moe expressivity via tropical geometry,” arXiv preprint arXiv:2602.03204, 2026

2026 arXiv
[31]

On the decision boundaries of neural networks: A tropical geometry perspective,

M. Alfarra, A. Bibi, H. Hammoud, M. Gaafar, and B. Ghanem, “On the decision boundaries of neural networks: A tropical geometry perspective,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 4, pp. 5027–5037, 2022

2022
[32]

Morphological perceptrons: geometry and training algorithms,

V . Charisopoulos and P. Maragos, “Morphological perceptrons: geometry and training algorithms,” inInternational Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing. Springer, 2017, pp. 3–15

2017
[33]

A tropical approach to neural networks with piecewise linear activations,

——, “A tropical approach to neural networks with piecewise linear activations,”arXiv preprint arXiv:1805.08749, 2018

2018 arXiv
[34]

What do graph neural networks learn? insights from tropical geometry,

T. A. Pham and V . Garg, “What do graph neural networks learn? insights from tropical geometry,”Advances in Neural Information Processing Systems, vol. 37, pp. 10 988–11 020, 2024

2024
[35]

Tropnnc: Structured neural network compression using tropical geometry,

K. Fotopoulos, P. Maragos, and P. Misiakos, “Tropnnc: Structured neural network compression using tropical geometry,” arXiv preprint arXiv:2409.03945, 2024

2024
[36]

Zaslavsky,Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes: Face-count formulas for partitions of space by hyperplanes

T. Zaslavsky,Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes: Face-count formulas for partitions of space by hyperplanes. American Mathematical Soc., 1975, vol. 154

1975
[37]

Mikhalkin and J

G. Mikhalkin and J. Rau,Tropical geometry. MPI for Mathematics, 2009, vol. 8

2009
[38]

Maclagan and B

D. Maclagan and B. Sturmfels,Introduction to tropical geometry. American Mathematical Soc., 2015, vol. 161

2015
[39]

On basic concepts of tropical geometry,

O. Y . Viro, “On basic concepts of tropical geometry,”Proceedings of the Steklov Institute of Mathematics, vol. 273, no. 1, pp. 252–282, 2011

2011
[40]

D. E. Speyer,Tropical geometry. University of California, Berkeley, 2005

2005
[41]

G. M. Ziegler,Lectures on polytopes. Springer Science & Business Media, 2012, vol. 152

2012
[42]

Fulton,Introduction to toric varieties

W. Fulton,Introduction to toric varieties. Princeton university press, 1993, no. 131

1993
[43]

The maslov dequantization, idempotent and tropical mathematics: a brief introduction,

G. L. Litvinov, “The maslov dequantization, idempotent and tropical mathematics: a brief introduction,”arXiv preprint math/0507014, 2005

2005 arXiv
[44]

Minkowski addition of polytopes: computational complexity and applications to gr ¨obner bases,

P. Gritzmann and B. Sturmfels, “Minkowski addition of polytopes: computational complexity and applications to gr ¨obner bases,”SIAM Journal on Discrete Mathematics, vol. 6, no. 2, pp. 246–269, 1993

1993
[45]

Dynamic voronoi diagrams,

I. Gowda, D. Kirkpatrick, D. Lee, and A. Naamad, “Dynamic voronoi diagrams,”IEEE Transactions on Information Theory, vol. 29, no. 5, pp. 724–731, 1983

1983
[46]

V oronoi cells, probabilistic bounds, and hypothesis testing in mixed integer linear models,

P. Xu, “V oronoi cells, probabilistic bounds, and hypothesis testing in mixed integer linear models,”IEEE Transactions on information theory, vol. 52, no. 7, pp. 3122–3138, 2006

2006
[47]

Power diagrams: properties, algorithms and applications,

F. Aurenhammer, “Power diagrams: properties, algorithms and applications,”SIAM journal on computing, vol. 16, no. 1, pp. 78–96, 1987

1987
[48]

Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition,

T. M. Cover, “Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition,”IEEE Transactions on Electronic Computers, vol. EC-14, no. 3, pp. 326–334, 1965. ACKNOWLEDGMENTS This research was supported by Beijing Natural Scie...

1965
[49]

Network Configurations and Global Dimensions NSequence length (number of tokens / keys / V oronoi sites)Z + dmodel Ambient embedding dimension of the transformerZ + dk, dv Projected dimensions for Query/Key and Value vectorsZ + Continued on next page UNDER REVIEW 16 TABLE I – ...
[50]

Input, Projections, and Feature Spaces XInput sequence embedding matrixR N×d model x, qSingle query embedding vector or query pointR dmodel WQ, WK Learnable linear projection matrices for Queries and KeysR dmodel×dk WV Learnable linear projection matrix for ValuesR dmodel×dv W...
[51]

Temperature, Log-Lifting, and Stability Variables τTemperature parameter for Maslov dequantizationR >0 s, sj Attention logit vector and componentss j =⟨q, kj⟩R N ,R Sl Inner product score for thel-th token in proofsR P (τ) (s)Smoothed LogSumExp (LSE) potential functionR P (0)(...
[52]

Tropical Geometry and Topological Structures T,⊕,⊗Tropical semiring (max-plus) and its addition and multiplication - ⊘,⊗ τ ,⊕ τ Tropical division and deformed smooth operations - P(x)Tropical polynomialP(x) = max j(⟨αj, x⟩+cj)R d →R Newt(P)Newton polytope: convex hull of expon...
[53]

Defined as:R(n, d) := Pd j=0 n j Z+ f0(P)Vertex counting function (number of 0-dimensional faces)Z + AΩ, bΩ Local affine mapping parameters within regionΩR d×d,R d

Computational Geometry, Hyperplane Arrangements, and Voronoi Notations S, ˆSGeneric sets of unweighted and weighted geometric sitesR d,R d ×R cj A generic geometric generator point (site)R d Continued on next page UNDER REVIEW 17 TABLE I – continued from previous page Symbol D...
[54]

Concept Standard DL Domain Tropical Domain (T) Geometric Interpretation Addition LogSumExp (A⊕ τ B) Max (A⊕B) Convex Hull / Supremum Multiplication Standard Add

Proof-Specific Constants and Auxiliaries (Appx B - G) PMHSA,P FFN Space partitions induced by MHSA and FFN respectively - MMHSA,M FFN Region counts in MHSA and FFN sub-layersZ + Cd Complexity constant for Minkowski sums inddimensionsR >0 Sl,R l Induced total partition and set ...

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.

[1] [1]

Attention is all you need,

A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,”Advances in neural information processing systems, vol. 30, 2017

2017

[2] [2]

A comparative survey of instance selection methods applied to non-neural and transformer-based text classification,

W. Cunha, F. Viegas, C. Franc ¸a, T. Rosa, L. Rocha, and M. A. Gonc ¸alves, “A comparative survey of instance selection methods applied to non-neural and transformer-based text classification,”ACM Computing Surveys, vol. 55, no. 13s, pp. 1–52, 2023

2023

[3] [3]

Transformers and large language models for efficient intrusion detection systems: A comprehensive survey,

H. Kheddar, “Transformers and large language models for efficient intrusion detection systems: A comprehensive survey,” Information Fusion, vol. 124, p. 103347, 2025

2025

[4] [4]

Explainability of vision transformers: A comprehensive review and new perspectives,

R. Kashefi, L. Barekatain, M. Sabokrou, and F. Aghaeipoor, “Explainability of vision transformers: A comprehensive review and new perspectives,”Multimedia Tools and Applications, vol. 85, no. 2, p. 115, 2026

2026

[5] [5]

Are transformers universal approximators of sequence- to-sequence functions?

C. Yun, S. Bhojanapalli, A. S. Rawat, S. J. Reddi, and S. Kumar, “Are transformers universal approximators of sequence- to-sequence functions?” inInternational Conference on Learning Representations, 2020

2020

[6] [6]

Attention is turing-complete,

J. P ´erez, P. Barcel ´o, and J. Marinkovic, “Attention is turing-complete,”Journal of Machine Learning Research, vol. 22, no. 75, pp. 1–35, 2021

2021

[7] [7]

Statistically meaningful approximation: a case study on approximating turing machines with transformers,

C. Wei, Y . Chen, and T. Ma, “Statistically meaningful approximation: a case study on approximating turing machines with transformers,” vol. 35, 2022, pp. 12 071–12 083

2022

[8] [8]

Theoretical limitations of self-attention in neural sequence models,

M. Hahn, “Theoretical limitations of self-attention in neural sequence models,”Transactions of the Association for Computational Linguistics, vol. 8, pp. 156–171, 2020

2020