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

All topics

Encoder-Decoder Transformers: Logical Characterizations and Periodicity
May 8, 2026Veeti Ahvonen, Damian Heiman, Antti Kuusisto +2Transformer Expressivity Transformer
Mathematics Research Centre, Tampere University, Tampere, Finland
Diagnosing Spectral Ceilings in Equivariant Neural Force Fields
May 8, 2026Hyunmog KimMachine Learning Interatomic Potentials Spectral Bias
Independent Researcher.
Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networks
May 7, 2026Yi Wei, Xuan Qi, Furao ShenNeural Network Activation Functions Neural Network Approximation Theory
DITEN University of Genoa, Genoa, Italy · State Key Laboratory of Novel Software Technology School of Artificial Intelligence Nanjing University, Jiangsu, China
AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networks
May 7, 2026Yi Wei, Xuan Qi, Furao Shen +3Neural Network Interpretability Neural Network Approximation Theory
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
Structural Correspondence and Universal Approximation in Diagonal plus Low-Rank Neural Networks
May 7, 2026Ying Chen, Aoxi Li, Jihun Kim +1Low-Rank Matrix Decomposition Low-Rank Approximation
Department of Industrial Engineering & Operations Research University of California, Berkeley, CA 94720
Average Attention Transformers and Arithmetic Circuits
May 6, 2026Lena Ehrmuth, Laura StriekerTransformer Expressivity Transformer
Institute for Theoretical Computer Science, Leibniz University Hanover, Hanover, Germany
Most ReLU Networks Admit Identifiable Parameters
May 5, 2026Moritz Grillo, Guido MontúfarRepresentation Identifiability Parameter Identifiability
Max Planck Institute for Mathematics in the Sciences, Leipzig · Departments of Mathematics and Statistics & Data Science, UCLA
A PyTorch Library of Turing-Complete Neural Networks
May 3, 2026Jonathan BatesNeural Network Expressivity
Characterizing the Expressivity of Local Attention in Transformers
May 1, 2026Jiaoda Li, Ryan CotterellTransformer Expressivity Transformer
Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks
May 1, 2026Jiawen Chen, Qi Shao, Zhiqiang Ge +2Neural Network Expressivity Topological Data Analysis
Jiangsu Key Laboratory of Networked Collective Intelligence, School of Mathematics, Southeast University, Nanjing 210096, China
Layer-wise Lipschitz-Product Control for Deep Kolmogorov--Arnold Network Representations of Compositionally Structured Functions
Apr 29, 2026Aleksander TankmanKolmogorov-Arnold Networks Neural Network Approximation Theory
Fivestar Europe OÜ, Tallinn, Estonia
Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
Apr 28, 2026Oliver Kraus, Yash Sarrof, Yuekun Yao +2Transformer Expressivity CoT Reasoning
1Saarland University · 2Ohio State University
A Functorial Formulation of Neighborhood Aggregating Deep Learning
Apr 27, 2026Sun Woo Park, Yun Young Choi, U Jin Choi +1Message Passing Neural Networks Convolutional Neural Networks
Nautile-370M: Spectral Memory Meets Attention in a Small Reasoning Model
Apr 27, 2026Maixent ChenebauxSelf-Attention Small Language Models
Trickstr
Necessary and sufficient conditions for universality of Kolmogorov-Arnold networks
Apr 26, 2026Vugar IsmailovKolmogorov-Arnold Networks Universal Approximation
Can an MLP Absorb Its Own Skip Connection Exactly?
Apr 26, 2026Antonij Mijoski, Marko KarbevskiMultilayer Perceptrons Residual Learning
IRMA, Universit´e de Strasbourg, France · Independent Researcher
Towards Understanding the Expressive Power of GNNs with Global Readout
Apr 23, 2026Maurice Funk, Daumantas KojelisGraph Neural Networks GNN Expressivity
Leipzig University, Germany
Relocation of compact sets in $\mathbb{R}^n$ by diffeomorphisms and linear separability of datasets in $\mathbb{R}^n$
Apr 23, 2026Xiao-Song Yang, Xuan Zhou, Qi ZhouNeural Network Expressivity
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
Layer-wise Geometric Approximation Rates for Deep Networks
Apr 22, 2026Shijun Zhang, Zuowei Shen, Yuesheng XuNeural Network Approximation Theory Neural Network Expressivity
Department of Applied Mathematics Hong Kong Polytechnic University · Department of Mathematics National University of Singapore · Department of Mathematics and Statistics Old Dominion University
The Logical Expressiveness of Topological Neural Networks
Apr 21, 2026Amirreza Akbari, Amauri H. Souza, Vikas GargGraph Neural Networks GNN Expressivity
Aalto University · Federal Institute of Cear´a, 2δ AI · YaiYai Ltd
Expressivity of Transformers: A Tropical Geometry Perspective
Apr 16, 2026Ye Su, Yong LiuTransformer Expressivity Transformer
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
Gating Enables Curvature: A Geometric Expressivity Gap in Attention
Apr 16, 2026Satwik Bathula, Anand A. JoshiInformation Geometry Neural Representation Geometry
Department of Electrical and Computer Engineering University of Southern California
Equivalence of approximation by networks of single- and multi-spike neurons
Mar 13, 2026Dominik Dold, Philipp Christian PetersenSpiking Neural Networks Neural Network Approximation Theory
Rational Neural Networks have Expressivity Advantages
Feb 12, 2026Maosen Tang, Alex TownsendNeural Network Activation Functions Neural Network Approximation Theory
Center for Applied Mathematics, Cornell University, United States · Department of Mathematics, Cornell University, United States
Poly-attention: a general scheme for higher-order self-attention
Feb 2, 2026Sayak Chakrabarti, Toniann Pitassi, Josh AlmanSelf-Attention Compositional Reasoning
Computer Science, Columbia University, New York, NY 10027.
The Alexander-Hirschowitz theorem for neurovarieties
Nov 24, 2025A. Massarenti, M. MellaPolynomial Neural Networks Parameter Identifiability
Configuration-Dependent Lower Bounds for Approximation by Shallow ReLU $^k$ Networks on the Sphere
Oct 5, 2025Tong Mao, Jinchao XuShallow Neural Networks Neural Network Approximation Theory
Shenzhen Loop Area Institute, Shenzhen 518000, P. R. China · King Abdullah University of Science and Technology, Thuwal 23955, Saudi Arabia.
Understanding Two-Layer Neural Networks with Smooth Activation Functions
Jul 11, 2025Changcun HuangNeural Network Activation Functions Neural Network Approximation Theory
Shuitu Institute of Applied Mathematics, Chongqing 400700, P.R.C
Causal pieces: analysing and improving spiking neural networks piece by piece
Apr 18, 2025Dominik Dold, Philipp Christian PetersenNeural Network Initialization Spiking Neural Networks
Fourier Multi-Component and Multi-Layer Neural Networks: Unlocking High-Frequency Potential
Feb 26, 2025Shijun Zhang, Hongkai Zhao, Yimin Zhong +1Fourier Feature Embeddings Neural Network Optimization
Department of Applied Mathematics Hong Kong Polytechnic University · Department of Mathematics Duke University · Department of Mathematics and Statistics Auburn University +1

May 8, 2026, cs.LOJ/K move · Enter open · S save

Encoder-Decoder Transformers: Logical Characterizations and Periodicity

Veeti Ahvonen, Damian Heiman, Antti Kuusisto, Miguel Moreno+1

Mathematics Research Centre, Tampere University, Tampere, Finland

Transformer Expressivity Transformer Autoregressive Language Modeling Neural Network Expressivity

Open paper AskPDF arXiv

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.

Momentum

Related topics

Latest papers 92