Neural Network Expressivity

Follow this topic Ask about this topic

Momentum

7 papers in the last four weeks, up 40% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 92

May 8, 2026cs.LO

Encoder-Decoder Transformers: Logical Characterizations and Periodicity

We give logical characterizations of encoder-decoder transformers, the foundational architecture for LLMs that also sees use in various settings that benefit from cross-attention, in the practical setting of floating-point numbers and soft attention. First, we characterize such transformers via a new temporal logic that extends propositional logic with a counting global modality over the encoder input and a past modality over the decoder input, as well as via a type of distributed automata. We consider three frameworks: with and without a final softmax step in the transformer, and in the setting where each model generates tokens via autoregression. Second, we show that both autoregressive transformers and sentences of counting propositional logic - the fragment of the previous logic obtained by omitting the past modality - recognize exactly the commutative star-free languages. Finally, we find that the sequences of tokens the transformers generate are ultimately periodic (and each token appears in the period at most once). This allows us to characterize autoregressive transformers via sentences of counting propositional logic that generate tokens without autoregression, i.e., we can effectively eliminate recursion from the transformers.

Veeti Ahvonen, Damian Heiman, Antti Kuusisto +2

Mathematics Research Centre, Tampere University, Tampere, Finland

Transformer Expressivity Transformer Autoregressive Language Modeling Neural Network Expressivity

May 8, 2026cs.LG

Diagnosing Spectral Ceilings in Equivariant Neural Force Fields

We introduce a spectral-injection diagnostic for measuring which angular frequencies a trained equivariant force-field backbone preserves: inject a controlled angular-frequency perturbation into a molecular force field, attach a lightweight Spectral Prediction Network (SPN) to the frozen backbone, and read off which frequencies are recoverable. On aspirin, a quadratic SPN attached to an L = 2 NequIP backbone recovers the boundary signal at l = 4 but collapses at l = 5: a 11.7x cliff at the predicted drL boundary, with p dropping from 0.913 to 0.078. The same boundary-vs-above contrast persists across n = 4 independently trained backbones (raw-gain delta contrast, hierarchical cluster bootstrap) and is corroborated by a denominator-free injected-residual metric (R2_inj(4) = 0.374 versus R2_inj(5) = 0.006). A finite-degree span theorem calibrates the diagnostic: for a single marked direction, degree-d polynomials of degree-L spherical-harmonic features span exactly H less than or equal to dL with multiplicity-one saturation at the boundary (scoped to single-direction degree-bounded probes, not a function-class upper bound on multi-atom MPNNs). A synthetic C5 calibration plus capacity, activation, and cross-architecture controls rule out parameter count alone as the explanation.

Hyunmog Kim

Independent Researcher.

Machine Learning Interatomic Potentials Spectral Bias Equivariant Neural Networks Spectral Methods Neural Network Expressivity

May 7, 2026cs.LG

Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networks

Deep networks with continuous piecewise affine activations induce polyhedral partitions of the input space, making the number of realized affine regions a natural measure of expressive capacity and a key determinant of how well the model can approximate nonlinear target functions. In practice, standard training realizes far fewer region refinements in data-visited neighborhoods than the architecture could in principle support, while existing region-count theory is primarily architectural and offers little guidance on how optimization shapes the realized partition near the data. Our theory provides a sufficient condition under which bringing neuron switching surfaces sufficiently close to data points ensures their intersection with local neighborhoods, which in turn implies a strict increase in the local affine-region count, yielding a principled training-time handle for seeding data-relevant partitions early in optimization. Guided by these results, we propose a plug-and-play region-seeding regularizer that encourages early partitioning while allowing task-driven refinement to dominate later in training. Experiments show that the regularizer increases the number of realized affine regions via exact enumeration and improves overall performance on toy datasets, while also improving early-stage accuracy and achieving comparable (or slightly improved) final accuracy on ImageNet-1k for classical models.

Yi Wei, Xuan Qi, Furao Shen

DITEN University of Genoa, Genoa, Italy · State Key Laboratory of Novel Software Technology School of Artificial Intelligence Nanjing University, Jiangsu, China

Neural Network Activation Functions Neural Network Approximation Theory Neural Network Training Dynamics Neural Network Expressivity

May 7, 2026cs.LG

AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networks

Piecewise affine neural networks (PANNs) provide a principled geometric perspective on neural network expressivity by characterizing the input--output map as a continuous piecewise affine (CPA) function whose complexity is governed by the number, arrangement, and shapes of its affine regions. However, existing interpretability and expressivity analyses often rely on indirect proxies (e.g., activation statistics or theoretical upper bounds) and rarely offer practical, accurate tools for enumerating and visualizing the induced region partition under realistic architectures and bounded input domains. In this work, we present AffineLens, a unified framework for computing the hyperplane arrangements and polyhedral structures underlying PANNs. Given a calibrated (bounded) input polytope, AffineLens identifies the subset of neuron-induced hyperplanes that intersect the domain, enumerates the resulting affine sub-regions in a layer-wise manner, and returns provably non-empty maximal CPA regions together with interior representatives. The framework further provides visualizations of region partitioning and decision boundaries, enabling qualitative inspection alongside quantitative region counts. By exploiting the affine restriction property of CPA networks under fixed activation patterns, AffineLens supports a broad class of modern components, including batch normalization, pooling, residual connections, multilayer perceptrons, and convolutional layers. Finally, we use AffineLens to perform a systematic empirical study of architectural expressivity, comparing networks through region complexity metrics and revealing how design choices influence the geometry of learned functions.

Yi Wei, Xuan Qi, Furao Shen +3

State Key Laboratory of Novel Software Technology School of Intelligence Science and Technology Nanjing University, Jiangsu, China · AI for Good Istituto Italiano di Tecnologia, Genoa, Italy · DITEN University of Genoa, Genoa, Italy +2

Neural Network Interpretability Neural Network Approximation Theory Neural Network Expressivity

May 7, 2026cs.LG

Structural Correspondence and Universal Approximation in Diagonal plus Low-Rank Neural Networks

The massive computational costs of scaling modern deep learning architectures have driven the widespread use of parameter-efficient low-rank structures, such as LoRA and low-rank factorization. However, theoretical guarantees for their expressive power are less explored, often relying on restrictive priors like a pretrained base matrix, ReLU activations or non-verifiable singularity conditions. We first investigate the limits of neural networks constrained strictly to low-rank manifolds without pretrained dense priors. We demonstrate a theoretical paradox: while purely rank-1 layers can exactly interpolate arbitrary scalar datasets, they collapse for function approximations. To overcome this bottleneck without surrendering parameter efficiency, we introduce a unified \textit{Structural Correspondence} framework. We prove that augmenting low-rank layers with only a minimal sparse diagonal component, say a Diagonal plus Low-Rank (DLoR) structure, is sufficient to reach Universal Approximation. We show that any full-rank transformation can be exactly reconstructed using these DLoR components by trading off network width (additive decomposition) or depth (multiplicative decomposition). By tracking asymptotic Taylor remainders, we prove that DLoR neural networks fully restore the Universal Approximation Theorem for general activation functions. Finally, we establish that multiplicative depth provides superior parameter-to-expressivity scaling compared to additive width. Our results show that dense matrices and specific activation functions are not topological prerequisites for universal expressivity.

Ying Chen, Aoxi Li, Jihun Kim +1

Department of Industrial Engineering & Operations Research University of California, Berkeley, CA 94720

Low-Rank Matrix Decomposition Low-Rank Approximation Neural Network Approximation Theory Neural Network Expressivity

May 6, 2026cs.CC

Average Attention Transformers and Arithmetic Circuits

We analyse the computational power of transformer encoders as sequence-to-sequence functions on vectors. We show that average hard attention can be used to simulate arithmetic circuits if they are given as an input to an encoder. The circuit families that can be simulated this way have constant depth while using unbounded addition, binary multiplication and sign gates. The transformers we use have arithmetic circuits instead of feed-forward networks. With typical average attention the functions they compute are also computed by the same class of circuit families. Our results hold for transformers over the reals, rationals and any ring in between the two.

Lena Ehrmuth, Laura Strieker

Institute for Theoretical Computer Science, Leibniz University Hanover, Hanover, Germany

Transformer Expressivity Transformer Attention Mechanisms Neural Network Expressivity

May 5, 2026cs.LG

Most ReLU Networks Admit Identifiable Parameters

We study the realization map of deep ReLU networks, focusing on when a function determines its parameters up to scaling and permutation. To analyze hidden redundancies beyond these standard symmetries, we introduce a framework based on weighted polyhedral complexes. Our main result shows that for every architecture whose input and hidden layers have width at least two, there exists an open set of identifiable parameters. This implies that the functional dimension of every such architecture is exactly the number of parameters minus the number of hidden neurons. We further show that minimal functional representations can still have non-trivial parameter redundancies. Finally, we establish a generic depth hierarchy, whereby for an open set of parameters the realized function cannot be represented generically by any shallower network.

Moritz Grillo, Guido Montúfar

Max Planck Institute for Mathematics in the Sciences, Leipzig · Departments of Mathematics and Statistics & Data Science, UCLA

Representation Identifiability Parameter Identifiability ReLU Neural Networks Neural Network Expressivity

May 3, 2026cs.LG

A PyTorch Library of Turing-Complete Neural Networks

We present a PyTorch package that compiles neural networks and their weights from Turing machine descriptions, producing models that exactly simulate the specified machine without any training. Given a transition function and a set of terminal states, the package constructs a model whose forward pass corresponds to one step of the Turing machine. Two architectures are implemented, each realizing a different theoretical result: (1) a transformer with self-attention, cross-attention, and feedforward layers based on Wei, Chen, and Ma (2021), and (2) a recurrent network based on Siegelmann and Sontag (1995) that encodes the stack in a Cantor set. We develop the constructions from first principles, showing how ReLU networks implement Boolean circuits (AND, OR, NOT, XOR gates and their composition into DNF formulas and binary adders) and how hard attention implements positional lookup on the tape. The package serves as a concrete, runnable reference for the symbolic-neural bridge, and as a foundation for future work on the stability of constructed solutions under gradient-based optimization. Code is available at https://github.com/jonrbates/turing.

Jonathan Bates

Neural Network Expressivity

May 1, 2026cs.CL

Characterizing the Expressivity of Local Attention in Transformers

The transformer is the most popular neural architecture for language modeling. The cornerstone of the transformer is its global attention mechanism, which lets the model aggregate information from all preceding tokens before generating the next token. One common variant of attention is called local attention, which restricts each token to aggregating information from a bounded window of predecessors, reducing the quadratic cost of global attention to linear. Although this restriction is usually motivated by efficiency, it has also been found to improve model quality, a phenomenon that has so far lacked a satisfactory explanation. We provide a formal account of this phenomenon in terms of recognizer expressivity. It has been shown that fixed-precision transformers with global attention correspond to a fragment of linear temporal logic containing a single past operator. We additionally prove that adding local attention introduces a second temporal operator, strictly enlarging the class of recognizable regular languages. Moreover, global and local attention are expressively complementary: neither subsumes the other, and combining them yields the richest fragment. Experiments on formal language recognition and natural language modeling corroborate the theory, showing that hybrid global--local transformers outperform their global-only counterparts.

Jiaoda Li, Ryan Cotterell

Transformer Expressivity Transformer Autoregressive Language Modeling Local Attention Attention Mechanisms Neural Network Expressivity

May 1, 2026cs.LG

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Topological neural networks have emerged as effective tools for modeling higher-order relational structures beyond pairwise graphs, including hypergraphs, simplicial complexes, and cell complexes. However, existing Weisfeiler-Leman type expressivity analyses are typically developed on different structural domains and rely on domain-specific neighborhood systems, making their expressive powers difficult to compare within a common formalism. In this paper, we introduce the Combinatorial Complex Weisfeiler-Leman (CCWL) framework, a unified expressive power refinement defined on combinatorial complexes. By exploiting the ability of combinatorial complexes to represent both set-type relations and part-whole hierarchies, CCWL performs topological color refinement through four structural neighborhoods: boundary, co-boundary, lower adjacency, and upper adjacency. We show that, under specified lifting maps, CCWL can simulate several domain-specific WL-type refinements, thereby providing a common theoretical baseline for analyzing topological message passing. We further study the neighborhood sufficiency problem and prove that, under explicit coverage conditions, a reduced refinement using only lower- and upper-adjacent bridge information preserves the distinguishing power of the full four-neighborhood CCWL refinement. Guided by this theoretical result, we instantiate the reduced refinement as the Combinatorial Complex Isomorphism Network (CCIN). Experiments on synthetic and real-world benchmarks demonstrate that CCIN achieves competitive performance against representative graph and topological neural network baselines. Ablation studies and resource-efficiency analyses further support the effectiveness of the proposed lower/upper-neighborhood design.

Jiawen Chen, Qi Shao, Zhiqiang Ge +2

Jiangsu Key Laboratory of Networked Collective Intelligence, School of Mathematics, Southeast University, Nanjing 210096, China

Neural Network Expressivity Topological Data Analysis

Apr 29, 2026cs.LG

Layer-wise Lipschitz-Product Control for Deep Kolmogorov--Arnold Network Representations of Compositionally Structured Functions

We prove that any continuous function f from [0,1]^n to R representable by a finite computation tree with N internal nodes and compositional sparsity s = O(1) admits a deep Kolmogorov-Arnold Network (KAN) representation. Each internal node is realised by a primitive KAN block with controlled block depth and Lipschitz product. The layer-wise Lipschitz product satisfies the primary domain-sensitive bound independent of the input dimension n. It simplifies to P(KAN_f) <= max(C*,1)^L_f with L_f <= c_max * N. For the standard operations {+,-,x,sin,cos} with x nodes on [0,1]-bounded inputs we obtain P(KAN) <= 1. Layer widths satisfy n_l <= n + 2 w_max * N. The uniform approximation error is bounded by N * max(C*,1)^d(f) * epsilon_Op (simplifies when C* <=1). For f in C^m we obtain optimal B-spline rates. Range bounds are also derived (B_f <= N+1 for additive trees). This addresses the gap on Lipschitz control in deep KAN stacks noted by Liu et al. (2024). Experiments confirm P(KAN)=1.0 for several compositionally structured functions.

Aleksander Tankman

Fivestar Europe OÜ, Tallinn, Estonia

Kolmogorov-Arnold Networks Neural Network Approximation Theory Neural Network Expressivity Lipschitz Neural Networks

Apr 28, 2026cs.LG

Barriers to Universal Reasoning With Transformers (And How to Overcome Them)

Chain-of-Thought (CoT) has been shown to empirically improve Transformers' performance, and theoretically increase their expressivity to Turing completeness. However, whether Transformers can learn to generalize to CoT traces longer than those seen during training is understudied. We use recent theoretical frameworks for Transformer length generalization and find that -- under standard positional encodings and a finite alphabet -- Transformers with CoT cannot solve problems beyond

TC^0

, i.e. the expressivity benefits do not hold under the stricter requirement of length-generalizable learnability. However, if we allow the vocabulary to grow with problem size, we attain a length-generalizable simulation of Turing machines where the CoT trace length is linear in the simulated runtime up to a constant. Our construction overcomes two core obstacles to reliable length generalization: repeated copying and last-occurrence retrieval. We assign each tape position a unique signpost token, and log only value changes to enable recovery of the current tape symbol through counts circumventing both barriers. Further, we empirically show that the use of such signpost tokens and value change encodings provide actionable guidance to improve length generalization on hard problems.

Oliver Kraus, Yash Sarrof, Yuekun Yao +2

1Saarland University · 2Ohio State University

Transformer Expressivity CoT Reasoning Length Generalization Neural Network Expressivity

Apr 27, 2026cs.LG

A Functorial Formulation of Neighborhood Aggregating Deep Learning

We provide a mathematical interpretation of convolutional (or message passing) neural networks by using presheaves and copresheaves of the set of continuous functions over a topological space. Based on this interpretation, we formulate a theoretical heuristic which elaborates a number of empirical limitations of these neural networks by using obstructions on such sets of continuous functions over a topological space to be sheaves or copresheaves.

Sun Woo Park, Yun Young Choi, U Jin Choi +1

Message Passing Neural Networks Convolutional Neural Networks Neural Network Expressivity

Apr 27, 2026cs.LG

Nautile-370M: Spectral Memory Meets Attention in a Small Reasoning Model

We present Nautile-370M, a 371-million-parameter small language model designed for efficient reasoning under strict parameter and inference budgets. Nautile-370M uses a hybrid backbone in which two SeqCond Attention (SCA) layers, a linear-time spectral sequence operator inspired by SeqCondenser, alternate with one transformer layer. This design aims to retain the long-context efficiency and state-tracking benefits of structured sequential models while preserving the expressive token-to-token routing of attention. The model was trained on a single Cloud TPU v4-64 pod slice provided through the Google TPU Research Cloud (TRC) program; the subsequent reinforcement learning stage was carried out on a single NVIDIA DGX Spark. We prove that the SCA readout mechanism can exactly retrieve any individual token from the prefix summary and can reproduce any output of softmax attention as a special case, establishing that SCA is at least as expressive as full self-attention in the continuous limit. We also describe the training data pipeline and outline a reinforcement learning stage specialized for reasoning, verification, and response quality.

Maixent Chenebaux

Trickstr

Self-Attention Small Language Models Attention Mechanisms Efficient Language Model Inference Neural Network Expressivity

Apr 26, 2026cs.LG

Necessary and sufficient conditions for universality of Kolmogorov-Arnold networks

We analyze the universal approximation property of Kolmogorov-Arnold Networks (KANs) in terms of their edge functions. If these functions are all affine, then universality clearly fails. How many non-affine functions are needed, in addition to affine ones, to ensure universality? We show that a single one suffices. More precisely, we prove that deep KANs in which all edge functions are either affine or equal to a fixed continuous function

σ

are dense in

C(K)

for every compact set

K\subset\mathbb{R}^n

if and only if

σ

is non-affine. In contrast, for KANs with exactly two hidden layers, universality holds if and only if

σ

is nonpolynomial. We further show that the full class of affine functions is not required; it can be replaced by a finite set without affecting universality. In particular, in the nonpolynomial case, a fixed family of five affine functions suffices when the depth is arbitrary. More generally, for every continuous non-affine function

σ

, there exists a finite affine family

A_σ

such that deep KANs with edge functions in

A_σ\cup\{σ\}

remain universal. We also prove that KANs with the spline-based edge parameterization introduced by Liu et al.~\cite{Liu2024} are universal approximators in the classical sense, even when the spline degree and knot sequence are fixed in advance.

Vugar Ismailov

Kolmogorov-Arnold Networks Universal Approximation Neural Network Approximation Theory Neural Network Expressivity

Apr 26, 2026cs.LG

Can an MLP Absorb Its Own Skip Connection Exactly?

The benefits usually attributed to skip connections are optimization-theoretic: a smoother loss landscape and better gradient propagation. We ask a representational question instead: given a residual block x -> x + MLP(x), does a residual-free MLP of the same width compute the same function? The answer is no, unconditionally and at every depth, for every activation used in current frontier language models (ReLU^2, ReGLU, SwiGLU, GeGLU). For ungated ReLU and GELU absorption is possible, but only on a set of weights of measure zero. The two families are therefore generically disjoint: removing a skip connection and retraining cannot recover exactly the same function at equal width.

Antonij Mijoski, Marko Karbevski

IRMA, Universit´e de Strasbourg, France · Independent Researcher

Multilayer Perceptrons Residual Learning Neural Network Expressivity

Apr 23, 2026cs.LG

Towards Understanding the Expressive Power of GNNs with Global Readout

We study the expressive power of message-passing aggregate-combine-readout graph neural networks (ACR-GNNs). Particularly, we focus on the first-order (FO) properties expressible by this formalism. While a tight logical characterisation remains a difficult open question, we make two contributions towards answering it. First, we show that sum aggregation and readout suffice for GNNs to capture FO properties that cannot be expressed in the logic C2 on both directed and undirected graphs. This strengthens known results by Hauke and Wał{\k e}ga (2026) where aggregation and readout functions are specially crafted for the task. Second, we identify two natural ways of restoring characterisability (with regard to C2) for ACR-GNNs. One option is to limit local aggregation (without imposing restrictions on global readout), whilst the second is to run ACR-GNNs over graphs of bounded degree (but unbounded size). In both cases, the FO properties captured by GNNs are exactly those definable by a formula in graded modal logic with global counting modalities. Our results thus establish an innate lower- and upper-bound in terms of how far (fragments of) C2 can be taken to characterise GNNs, and imply that is indeed the unbounded interaction of aggregation and readout that pushes the logical expressive power of GNNs above C2.

Maurice Funk, Daumantas Kojelis

Leipzig University, Germany

Graph Neural Networks GNN Expressivity Message Passing Neural Networks Neural Network Expressivity

Apr 23, 2026cs.LG

Relocation of compact sets in $\mathbb{R}^n$ by diffeomorphisms and linear separability of datasets in $\mathbb{R}^n$

Relocation of compact sets in an

n

-dimensional manifold by self-diffeomorphism is of its own interest as well as significant potential applications to data classification in data science. This paper presents a theory for relocating a finite number of compact sets in

\mathbb{R}^n

to be relocated to arbitrary target domains in

\mathbb{R}^n

by diffeomorphisms of

\mathbb{R}^n

. Furthermore, we prove that for any such collection, there exists a differentiable embedding into

\mathbb{R}^{n+1}

such that their images become linearly separable. As applications of the established theory, we show that a finite number of compact datasets in

\mathbb{R}^n

can be made linearly separable by width-

n

deep neural networks (DNNs) with Leaky-ReLU, ELU, or SELU activation functions, under a mild condition. In addition, we show that any finite number of mutually disjoint compact datasets in

\mathbb{R}^n

can be made linearly separable in

\mathbb{R}^{n+1}

by a width-

(n+1)

DNN.

Xiao-Song Yang, Xuan Zhou, Qi Zhou

School of Mathematics and Statistics, Huazhong University of Science and Technology, 1037 Luoyu Road, 430074 Wuhan, P.R. China · Hubei Key Laboratory of Engineering Modeling and Scientific Computing, Huazhong University of Science and Technology, Wuhan 430074, P.R. China

Neural Network Expressivity

Apr 22, 2026cs.LG

Layer-wise Geometric Approximation Rates for Deep Networks

Depth is widely viewed as a central contributor to the success of deep neural networks, whereas standard neural network approximation theory typically provides guarantees only for the final output and leaves the role of intermediate layers largely unclear. We address this gap by developing a quantitative framework in which depth admits a precise scale-dependent interpretation. Specifically, we design a single shared mixed-activation architecture of fixed width

2dN+d+2

and any prescribed finite depth such that each intermediate readout

Φ_\ell

is itself an approximant to the target function

f

. For

f\in L^p([0,1]^d)

with

p\in [1,\infty)

, the approximation error of

Φ_\ell

is controlled by

(2d+1)

times the

L^p

modulus of continuity at the geometric scale

N^{-\ell}

for all

\ell

. The estimate reduces to the geometric rate

(2d+1)N^{-\ell}

if

f

is

1

-Lipschitz. Our network design is inspired by multigrade deep learning, where depth serves as a progressive refinement mechanism. For every prescribed terminal depth, the construction yields a finite nested family of prefix readouts whose earlier correction terms remain embedded in later readouts. Thus the approximation may be truncated within the prescribed depth range once the desired certified accuracy is reached.

Shijun Zhang, Zuowei Shen, Yuesheng Xu

Department of Applied Mathematics Hong Kong Polytechnic University · Department of Mathematics National University of Singapore · Department of Mathematics and Statistics Old Dominion University

Neural Network Approximation Theory Neural Network Expressivity

Apr 21, 2026cs.LG

The Logical Expressiveness of Topological Neural Networks

Graph neural networks (GNNs) are the standard for learning on graphs, yet they have limited expressive power, often expressed in terms of the Weisfeiler-Leman (WL) hierarchy or within the framework of first-order logic. In this context, topological neural networks (TNNs) have recently emerged as a promising alternative for graph representation learning. By incorporating higher-order relational structures into message-passing schemes, TNNs offer higher representational power than traditional GNNs. However, a fundamental question remains open: what is the logical expressiveness of TNNs? Answering this allows us to characterize precisely which binary classifiers TNNs can represent. In this paper, we address this question by analyzing isomorphism tests derived from the underlying mechanisms of general TNNs. We introduce and investigate the power of higher-order variants of WL-based tests for combinatorial complexes, called

k

-CCWL test. In addition, we introduce the topological counting logic (TC

_k

), an extension of standard counting logic featuring a novel pairwise counting quantifier

\exists^{N}(x_i,x_j)\, \varphi(x_i,x_j),

which explicitly quantifies pairs

(x_i, x_j)

satisfying property

\varphi

. We rigorously prove the exact equivalence:

\text{k-CCWL} \equiv \text{TC}_{k{+}2} \equiv \text{Topological }(k{+}2)\text{-pebble game}.

These results establish a logical expressiveness theory for TNNs.

Amirreza Akbari, Amauri H. Souza, Vikas Garg

Aalto University · Federal Institute of Cear´a, 2δ AI · YaiYai Ltd

Graph Neural Networks GNN Expressivity Neural Network Expressivity

Apr 16, 2026cs.LG

Expressivity of Transformers: A Tropical Geometry Perspective

To quantify the geometric expressivity of transformers, we introduce a tropical geometry framework to characterize their exact spatial partitioning capabilities. By modeling self-attention as a vector-valued tropical rational map, we prove it evaluates exactly to a Power Voronoi Diagram in the zero-temperature limit. Building on this equivalence, we establish a combinatorial rationale for Multi-Head Self-Attention (MHSA): via the Minkowski sum of Newton polytopes, multi-head aggregation expands the polyhedral complexity to

\mathcal{O}(N^H)

, overcoming the

\mathcal{O}(N)

bottleneck of single heads. Extending this to deep architectures, we derive the first tight asymptotic bounds on the number of linear regions in transformers (

Θ(N^{d_{\text{model}}L})

), demonstrating a combinatorial explosion driven intrinsically by sequence length

N

, ambient embedding dimension

d_{\text{model}}

, and network depth

L

. Importantly, we guarantee that this idealized polyhedral skeleton is geometrically stable: finite-temperature soft attention preserves these topological partitions via exponentially tight differential approximation bounds.

Ye Su, Yong Liu

Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China · University of Chinese Academy of Sciences, Beijing 101407, China · Gaoling School of Artificial Intelligence, Renmin University of China, Beijing 100872, China

Transformer Expressivity Transformer Self-Attention Attention Mechanisms Multi-Head Attention Neural Network Expressivity

Apr 16, 2026cs.LG

Gating Enables Curvature: A Geometric Expressivity Gap in Attention

Multiplicative gating is widely used in neural architectures and has recently been applied to attention layers to improve performance and training stability in large language models. Despite the success of gated attention, the mathematical implications of gated attention mechanisms remain poorly understood. We study attention through the geometry of its representations by modeling outputs as mean parameters of Gaussian distributions and analyzing the induced Fisher--Rao geometry. We show that ungated attention operator is restricted to intrinsically flat statistical manifolds due to its affine structure, while multiplicative gating enables non-flat geometries, including positively curved manifolds that are unattainable in the ungated setting. These results establish a geometric expressivity gap between ungated and gated attention. Empirically, we show that gated models exhibit higher representation curvature and improved performance on tasks requiring nonlinear decision boundaries whereas they provide no consistent advantage on tasks with linear decision boundaries. Furthermore, we identify a structured regime in which curvature accumulates under composition, yielding a systematic depth amplification effect.

Satwik Bathula, Anand A. Joshi

Department of Electrical and Computer Engineering University of Southern California

Information Geometry Neural Representation Geometry Self-Attention Gated Attention Transformer Attention Attention Mechanisms+1

Mar 13, 2026cs.NE

Equivalence of approximation by networks of single- and multi-spike neurons

In a spiking neural network, is it enough for each neuron to spike at most once? In recent work, approximation bounds for spiking neural networks have been derived, quantifying how well they can fit target functions. However, these results are only valid for neurons that spike at most once, which is commonly thought to be a strong limitation. Here, we show that the opposite is true for a large class of spiking neuron models, including the commonly used leaky integrate-and-fire model with subtractive reset: for every approximation bound that is valid for a set of multi-spike neural networks, there is an equivalent set of single-spike neural networks with only linearly more (or less) neurons, in the maximum number of spikes, for which the bound holds. The same is true for the reverse direction too, showing that regarding their approximation capabilities in general machine learning tasks, single-spike and multi-spike neural networks are equivalent. Consequently, many approximation results in the literature for single-spike neural networks also hold for the multi-spike case.

Dominik Dold, Philipp Christian Petersen

Spiking Neural Networks Neural Network Approximation Theory Neural Network Expressivity

Feb 12, 2026cs.LG

Rational Neural Networks have Expressivity Advantages

We study neural networks with trainable low-degree rational activation functions and show that they are more expressive and parameter-efficient than modern piecewise-linear and smooth activations such as ELU, LeakyReLU, LogSigmoid, PReLU, ReLU, SELU, CELU, Sigmoid, SiLU, Mish, Softplus, Tanh, Softmin, Softmax, and LogSoftmax. For an error target of

\varepsilon>0

, we establish approximation-theoretic separations: Any network built from standard fixed activations can be uniformly approximated on compact domains by a rational-activation network with only

\mathrm{poly}(\log\log(1/\varepsilon))

overhead in size, while the converse provably requires

Ω(\log(1/\varepsilon))

parameters in the worst case. This exponential gap persists at the level of full networks and extends to gated activations and transformer-style nonlinearities. In practice, rational activations integrate seamlessly into standard architectures and training pipelines, allowing rationals to match or outperform fixed activations under identical architectures and optimizers.

Maosen Tang, Alex Townsend

Center for Applied Mathematics, Cornell University, United States · Department of Mathematics, Cornell University, United States

Neural Network Activation Functions Neural Network Approximation Theory Neural Network Expressivity

Feb 2, 2026cs.LG

Poly-attention: a general scheme for higher-order self-attention

The self-attention mechanism, at the heart of the Transformer model, is able to effectively model pairwise interactions between tokens. However, numerous recent works have shown that it is unable to perform basic tasks involving detecting triples of correlated tokens, or compositional tasks where multiple input tokens need to be referenced to generate a result. Some higher-dimensional alternatives to self-attention have been proposed to address this, including higher-order attention and Strassen attention, which can perform some of these polyadic tasks in exchange for slower, superquadratic running times. In this work, we define a vast class of generalizations of self-attention, which we call poly-attention mechanisms. Our mechanisms can incorporate arbitrary higher-order (tensor) computations as well as arbitrary relationship structures between the input tokens, and they include the aforementioned alternatives as special cases. We then systematically study their computational complexity and representational strength, including giving new algorithms and matching complexity-theoretic lower bounds on the time complexity of computing the attention matrix exactly as well as approximately, and tightly determining which polyadic tasks they can each perform. Our results give interesting trade-offs between different desiderata for these mechanisms, including a tight relationship between how expressive a mechanism is, and how large the coefficients in the model may be so that the mechanism can be approximated in almost-linear time. Notably, we give a new attention mechanism which can be computed exactly in quadratic time, and which can perform function composition for any fixed number of functions. Prior mechanisms, even for just composing two functions, could only be computed in superquadratic time, and our new lower bounds show that faster algorithms for them are not possible.

Sayak Chakrabarti, Toniann Pitassi, Josh Alman

Computer Science, Columbia University, New York, NY 10027.

Self-Attention Compositional Reasoning Transformer Attention Attention Mechanisms Neural Network Expressivity

Nov 24, 2025math.AG

The Alexander-Hirschowitz theorem for neurovarieties

We study the dimension and identifiability of neurovarieties associated to polynomial neural networks. We give an independent geometric proof that the linear bounds

d_i\geq 2n_i-1

on the activation degrees imply non defectiveness for any number of outputs, a dimension statement previously obtained from finite identifiability. The proof is based on a direct analysis of the differential of the parameterization. We also investigate secant and Grassmann-secant obstructions outside this range and prove global identifiability for multi-output architectures under the same degree bounds.

A. Massarenti, M. Mella

Polynomial Neural Networks Parameter Identifiability Neural Network Approximation Theory Neural Network Expressivity

Oct 5, 2025math.NA

Configuration-Dependent Lower Bounds for Approximation by Shallow ReLU $^k$ Networks on the Sphere

We establish two related but logically distinct results for shallow ReLU

^k

neural networks on the unit sphere

\SS^d

. First, for an arbitrary set of inner neural-network parameters, the best

\mathcal{L}^2(\SS^d)

approximation of a fixed target function with smoothness

r>\tfrac{d+2k+1}{2}

admits an asymptotic lower bound given by a constant multiple of

n^{-1/2}\underline{h}^{k+1/2}

, where

\underline{h}

denotes the antipodal separation distance of the normalized inner-parameter set. This lower bound depends explicitly on the parameter configuration through

\underline{h}

and applies without additional assumptions on the parameters. Second, for antipodally quasi-uniform parameters,

\underline{h}\simeq n^{-1/d}

, and the lower bound establishes the exact saturation order

n^{-\frac{d+2k+1}{2d}}

for such parameter families: a target function with regularity greater than

\frac{d+2k+1}{2}

and satisfying the required parity condition can be approximated at this rate, whereas approximation at any strictly faster rate forces the target function to be zero. Our results therefore place linearized neural-network approximation within the classical saturation framework and show that, although ReLU

^k

network spaces can outperform finite elements of the same degree, this advantage is intrinsically limited.

Tong Mao, Jinchao Xu

Shenzhen Loop Area Institute, Shenzhen 518000, P. R. China · King Abdullah University of Science and Technology, Thuwal 23955, Saudi Arabia.

Shallow Neural Networks Neural Network Approximation Theory Neural Network Expressivity

Jul 11, 2025cs.LG

Understanding Two-Layer Neural Networks with Smooth Activation Functions

This paper aims to understand the training solution, which is obtained by the back-propagation algorithm, of two-layer neural networks whose hidden layer is composed of the units with smooth activation functions, including the usual sigmoid type most commonly used before the advent of ReLUs. The mechanism contains four main principles: construction of Taylor series expansions, strict partial order of knots, smooth-spline implementation and smooth-continuity restriction. The universal approximation for arbitrary input dimensionality is proved and the explanation of training solutions is given. Through the principles proposed, the mystery of ``black box'' of the solution space is largely revealed. The new proofs employed also enrich approximation theory.

Changcun Huang

Shuitu Institute of Applied Mathematics, Chongqing 400700, P.R.C

Neural Network Activation Functions Neural Network Approximation Theory Neural Network Training Dynamics Neural Network Expressivity

Apr 18, 2025cs.NE

Causal pieces: analysing and improving spiking neural networks piece by piece

We introduce "causal pieces", a novel concept for analysing spiking neural networks (SNNs), inspired by "linear pieces" used to study expressivity and trainability in artificial neural networks (ANNs). Causal pieces partition the input and parameter space of a feedforward SNN with single-spike coding into distinct regions where the same subnetwork causes the output spikes. For networks of current-based leaky integrate-and-fire (LIF) neurons with large membrane time constants, we show that within each causal piece, output spike times are locally Lipschitz continuous with respect to inputs and network parameters. We further prove a lower bound on the approximation error that depends on the number of causal pieces. Thus, the number of causal pieces is a measure of the approximation capabilities of SNNs, which is valid despite spike-time discontinuities and applies to networks with both excitatory and inhibitory synapses. Empirically, we find that parameter initialisations yielding more causal pieces on the training set strongly correlate with SNN training success across multiple benchmarks, including Yin-Yang, Fashion-MNIST, and EuroSAT. Moreover, simulations with standard single-spike LIF neurons indicate that our findings extend beyond the theoretically analysed regime. These results establish causal pieces as a powerful and principled tool for analysing and improving the computational capabilities of SNNs.

Dominik Dold, Philipp Christian Petersen

Neural Network Initialization Spiking Neural Networks Neural Network Approximation Theory Neural Network Expressivity

Feb 26, 2025cs.LG

Fourier Multi-Component and Multi-Layer Neural Networks: Unlocking High-Frequency Potential

The architecture of a neural network and the choice of its activation function are both fundamental to its performance. Equally important is ensuring that these two elements are well matched, as their alignment is key to effective representation and learning. In this paper, we introduce the Fourier Multi-Component and Multi-Layer Neural Network (FMMNN), a model that combines sine-type activations with the multi-component and multi-layer structure of MMNNs. In an FMMNN, each component is represented as a trainable linear combination of fixed random sine-type basis functions, while multi-layer composition generates more complex and adaptive high-frequency features. We establish that FMMNNs retain exponential expressive power for function approximation even under a low-rank architectural structure. We also analyze the optimization landscape of FMMNNs and find it to be substantially more favorable than that of standard fully connected neural networks, especially for high-frequency targets. In addition, we propose a scaled random initialization method for the first-layer weights in FMMNNs, which accelerates training and improves final performance when sufficient samples are available. Extensive numerical experiments support our theoretical insights, showing that FMMNNs achieve strong accuracy and favorable convergence behavior on oscillatory function-approximation benchmarks.

Shijun Zhang, Hongkai Zhao, Yimin Zhong +1

Department of Applied Mathematics Hong Kong Polytechnic University · Department of Mathematics Duke University · Department of Mathematics and Statistics Auburn University +1

Fourier Feature Embeddings Neural Network Optimization Neural Network Activation Functions Neural Network Approximation Theory Neural Network Expressivity Modular Neural Networks