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

Jun 22, 2026q-bio.NC

Identifying structural design principles shaping the computational abilities of recurrent neural networks

Understanding how the architecture of neural networks shapes the computations they carry is a central challenge in neuroscience and machine learning. While specific circuit architectures have been linked to particular network computations and theoretical bounds on expressivity of broad classes of networks have been found, we are still missing general principles connecting the structure of finite networks to their computational capabilities. Here, we characterize the computational abilities of recurrent neural networks as a function of their connectivity by training a large collection of different networks to compute a large set of Boolean functions. For small networks, we constructed the complete ``catalogs'' of network-function performance, which revealed that computational capacity varies widely across architectures and that most networks show poor performance, and most functions are hard to compute. However, we show that having local 2- and 3-cycles in a network strongly enhances its computational ability, and networks with such cycles are often the minimal architectures that can solve particular functions. We further show that a small set of structural statistics accurately predict networks' performance. Extending our analysis to large networks showed that typical networks fail even to approximate a randomly selected function. Surprisingly, adding a small number of sparsely connected biologically-inspired interneurons to the network dramatically increases computational capacity. As in small networks, adding short cycles improved networks' capacity, outperforming acyclic or reachability-matched controls. Thus, our results identify local cycles as design principles linking neural connectivity to computational power, and offer a general framework to explore structure-function relations in computing networks.

Tom Talpir, Elad Schneidman

Department of Brain Sciences, Weizmann Institute of Science, Rehovot, Israel

Recurrent Neural Networks Neural Network Expressivity

Jun 22, 2026cs.LG

EML Trees Are Universal Approximators

The recently introduced EML (Exp-Minus-Log) function acts as continuous analogue of NAND gates, providing a compositional building block capable of representing elementary functions. In this work, we study the expressive power of tree-structured compositions of EML functions. We show that such trees enjoy a universal approximation property for functions in

W^{k, \infty}

for

k \in \mathbb N

, drawing on classical neural network approximation arguments while exploiting the ability to explicitly construct EML trees that mimic polynomial representations. We further propose a learning algorithm for EML-type trees equipped with fitting parameters, and demonstrate its feasibility in practical optimization problems. Our results establish EML trees as a theoretically grounded framework for function approximation.

Joe Germany, Elie Abdo, Joseph Bakarji

Department of Mathematics American University of Beirut Beirut, Lebanon · Department of Mechanical Engineering American University of Beirut Beirut, Lebanon

Universal Approximation Neural Network Approximation Theory Neural Network Expressivity

Jun 20, 2026cs.LG

On the Expressive Power of Weight Quantization in Large Language Models

In recent years, weight quantization that encodes the learnable parameters of large language models in an

n

-bit format has garnered significant attention due to its potential for model compression and inference acceleration. Many practical techniques have been developed; however, the theoretical understanding of many aspects, especially the approximation and degradation of expressive power as the number of quantization bits decreases, remains unclear. In this paper, we provide a theoretical investigation into the expressive capability of large language models relative to the number of quantization bits. We argue that 1.58-bit is the limiting precision for weight quantization by establishing the universal approximation and expressive collapse properties of weight-quantized models with respect to the number of quantization bits. Additionally, we confirm that weight quantization leads to expressive degradation, in which the expressive capacity of weight-quantized models degrades polynomially as the number of quantization bits decreases. These theoretical findings provide a solid foundation for advancing weight quantization in the context of scaling laws and shed insights for future research in model compression and inference acceleration.

Shao-Qun Zhang

National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210063, China. · School of Intelligent Science and Technology, Nanjing University, Suzhou 215163, China.

LLM Quantization Weight-Only Quantization Neural Network Expressivity Low-Bit Quantization

Jun 19, 2026cs.LG

Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexity

Piecewise-affine neural networks (e.g., with ReLU or LeakyReLU activations) implement continuous piecewise-affine maps, and the number of affine regions provides a natural proxy for expressive capacity. However, the gap between theoretical region capacity and the affine regions realized after training remains insufficiently understood. We study this gap from two complementary perspectives. First, we give a rigorous, architecture-dependent theorem for affine line-segment probes: for multilayer perceptrons with piecewise-affine activations, the number of affine pieces realized along an affine line-segment probe is upper bounded by an explicit product of layer-wise width terms (and activation breakpoint factors). This yields a neuron-threshold lower bound for representing target functions with prescribed one-dimensional piece complexity, formalizing the minimal region budget required for complex signals. Second, we exactly enumerate affine regions realized within bounded 2D and higher-dimensional domains under controlled task complexity. Under fixed architectures and training protocols, increasing input--label complexity yields trained solutions with markedly fewer realized regions in the evaluation domain, even though worst-case architectural capacity is unchanged; we call this reduced region usage expressivity saturation. Moreover, in the most challenging regimes, 2D visualizations show that region-usage collapse often coincides with degraded decision boundaries. Finally, we visualize the training dynamics of affine-region partitions and decision boundaries, revealing a consistent refinement process during optimization.

Xuan Qi, Yi Wei, Fanqi Yu +1

AI for Good (AIGO), Istituto Italiano di Tecnologia · DITEN, University of Genoa · State Key Laboratory of Novel Software Technology +1

Multilayer Perceptrons Neural Network Approximation Theory Neural Network Training Dynamics Neural Network Expressivity

Jun 16, 2026cs.LG

Effects of sparsity and superposition on loss in simple autoencoders

One of the major difficulties in the mechanistic interpretability of neural networks is the occurrence of polysemanticity, which suggests that each neuron is typically responsible for multiple different tasks, impeding a clean interpretation of their function. The seminal paper of Elhage et al. (2022) argues that this occurs due to superposition, a phenomenon where the neural network represents distinct features as non-orthogonal directions in a lower-dimensional space, a strategy that allows much greater compression of the data without sacrificing fidelity due to the feature sparsity of input vectors. Elhage et al. (2022) empirically validates these hypotheses in a rather natural and simple autoencoder with sparse inputs. The contribution of the present work is to analyze the mathematical basis for the occurrence and optimality of superposition, while rigorously corroborating some of their findings. In particular, we provide upper and lower bounds for the L2 reconstruction loss, tight in the very sparse regime, for power activation functions. A short list of interesting open problems are also included at the end.

Mriganka Basu Roy Chowdhury, Eric McLaughlin Weiner

Department of Statistics, UC Berkeley · Department of Materials Science, UC Berkeley

Feature Superposition Activation Sparsity Autoencoders Representation Disentanglement Neural Network Interpretability Neural Network Expressivity

Jun 10, 2026cs.DB

Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data

The conventional approach to deep learning over relational databases applies neural models, such as Graph Neural Networks (GNNs), to a graph representation of the database. Recent approaches instead operate on databases directly, associating tuples with embeddings and extending query mechanisms to jointly process embeddings and relational content. Inspired by these developments, we introduce Neuro-Relational Programs (NRPs), a declarative query language for relational databases whose facts carry numeric vector embeddings. NRPs extend Datalog-style rules with operations that combine, aggregate, and transform embeddings, thereby interleaving relational reasoning and learnable neural components within a single formalism. This yields a general approach to neural computation over relational data: an NRP can be read both as a query plan with trainable components and as a neural architecture with relational structure built in. Natural syntactic fragments of NRPs recover existing architectures and query formalisms. Zero-ary NRPs correspond to non-adaptive query algorithms; monadic NRPs generalize GNN-style message passing and precisely capture Deep Homomorphism Networks, a connection that we extend to frontier-guarded NRPs over databases with row-ids. We characterize the expressive power of unrestricted NRPs with ReLU-FFN transformations by FOCQ, an extension of first-order logic with counting interpreted over real-weighted structures, yielding a precise connection with uniform TC

^0

over ordered databases. Together, these results establish NRPs as a broad declarative framework for querying and neural computation over relational data.

Arie Soeteman, Balder ten Cate, Maurice Funk +3

ILLC, University of Amsterdam, Amsterdam, Netherlands · Leipzig University, Leipzig, Germany · ScaDS.AI Center Dresden/Leipzig, Germany +2

Graph Neural Networks Relational Reasoning Neuro-Symbolic Reasoning Relational Deep Learning Neural Network Expressivity Relational Databases

Jun 5, 2026cs.LG

Characterizing the Discrete Geometry of ReLU Networks

It is well established that ReLU networks define continuous piecewise-linear functions, and that their linear regions are polyhedra in the input space. These regions form a complex that fully partitions the input space. The way these regions fit together is fundamental to the behavior of the network, as nonlinearities occur only at the boundaries where these regions connect. However, relatively little is known about the geometry of these complexes beyond bounds on the total number of regions, and calculating the complex exactly is intractable for most networks. In this work, we prove new theoretical results about these complexes that hold for all fully-connected ReLU networks, specifically about their connectivity graphs in which nodes correspond to regions and edges exist between each pair of regions connected by a face. We find that the average degree of this graph is upper bounded by twice the input dimension regardless of the width and depth of the network, and that the diameter of this graph has an upper bound that does not depend on input dimension, despite the number of regions increasing exponentially with input dimension. We corroborate our findings through experiments with networks trained on both synthetic and real-world data, which provide additional insight into the geometry of ReLU networks. Code to reproduce our results can be found at https://github.com/bl-ake/ICLR-2026.

Blake B. Gaines, Jinbo Bi

Department of Computer Science University of Connecticut

Neural Representation Geometry ReLU Neural Networks Neural Network Expressivity

Jun 2, 2026cs.LG

Rethinking Neural Width for Alternating Current Optimal Power Flow Proxies

Deep learning proxies for Alternating Current Optimal Power Flow (ACOPF) lack systematic methods for determining architectural size. This paper conducts a constructive thought experiment to answer a fundamental inquiry: how wide must a neural network be to almost accurately approximate the ACOPF manifold? We introduce a Loss-Guided Neural Densification (LG-ND) algorithm that incrementally discovers necessary capacity by expanding only when the current deep neural network topology fails to improve further. Empirical results across various IEEE systems show that LG-ND achieves performance parity with literature baselines using up to ten times fewer neurons per layer. Such architectural minimalism is critical for the formal verification required in safety-critical grid operations.

Dhruvi Khandelwal, Anurag Basistha, Ayushi Jolotia +1

Department of Electrical Engineering, National Institute of Technology Kurukshetra, India. · Indraprastha Institute of Information Technology Delhi, India. · Department of Electrical Engineering, Indian Institute of Technology Roorkee, India.

Neural Surrogate Modeling Optimal Power Flow Constrained Optimization Neural Network Approximation Theory Neural Architecture Search Neural Network Expressivity

Jun 1, 2026cs.LG

Expressivity of congruence-based architectures for DNNs on positive-definite matrices

This work studies neural architectures for classifying symmetric positive-definite matrices, focusing on congruence-like layers, in which the input matrix is multiplied on the left and right by a (possibly rectangular) weight matrix

W

and its transpose. Such layers lie at the core of the celebrated SPDNet and have also been employed independently for dimensionality reduction on positive-definite data. We show that the (semi)-orthogonality constraint commonly imposed on

W

limits the expressivity of these layers: for certain activation functions, the resulting architecture collapses to a one-hidden-layer equivalent. This lack of expressivity follows from a loss of spectral diversity in congruence-like layers for semi-orthogonal

W

and is a direct consequence of Poincaré's separation theorem. We then examine the choice of the final classifier, comparing several Riemannian classifiers and discussing their compatibility with the feature maps produced by congruence-like layers.

Antonin Oswald, Estelle Massart

ICTEAM, UCLouvain · Louvain-la-Neuve, Belgium

Neural Network Expressivity

Jun 1, 2026cs.FL

An Algebraic View of the Expressivity of Recurrent Language Models

What formal languages can a recurrent neural language model recognize? Formal results in the literature conflict: some authors report Turing-completeness, while others show equivalence to regular languages. The reason for this discrepancy is that the underlying arithmetic model differs. The paper develops a unified algebraic account of the expressivity of recurrent neural networks, starting with a formal account of various arithmetic models. This account reduces expressivity to an algebraic question, e.g., whether a network's syntactic monoid divides a certain wreath product. As a case study, the paper revisits diagonal state-space models: the same architecture cannot implement an even-modulus counter once floating-point recurrences are enforced, yet realizes every even-modulus counter under unsigned-integer quantization.

Franz Nowak, Ryan Cotterell, Reda Boumasmoud

ETHZürich.

Recurrent Neural Networks Neural Network Expressivity

May 28, 2026cs.LG

Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't

Recent work describes what transformers can and cannot compute through connections to boolean circuits, but existing results lack exact characterizations and are sensitive to modeling choices. Padded transformers -- to whose input filler symbols such as ``...'' are appended -- emerge as a useful gadget for establishing equivalences to circuit classes by providing polynomial space for adaptive parallel computation. However, only a limited set of padded transformer idealizations has been studied, leaving open how robustly these equivalences hold under changes to attention type, model width, and uniformity. We find that, under practical assumptions, padded transformers are surprisingly robust to all of these, and identify numeric precision and model depth as the main factors affecting expressivity. Concretely, we prove that polynomially padded

\text{L-uniform}

constant-precision transformers are equivalent to

\text{L-uniform AC}^0

, while growing-precision ones achieve

\text{L-uniform TC}^0

regardless of width. Furthermore, looping enables sequential processing analogous to circuits:

\log^d N

-looped constant-precision transformers reach

\text{FO-uniform AC}^d

, and growing-precision ones reach

\text{FO-uniform TC}^d

. Interestingly, growing width or precision beyond logarithmic does not increase expressivity, and all our results hold for both softmax and average hard attention transformers.

Anej Svete, William Merrill, Ryan Cotterell +1

1. ETH Zürich · 2. Allen Institute for AI

Transformer Expressivity Transformer Neural Network Expressivity

May 27, 2026cs.LG

Expressive Power of Floating-Point Neural Networks with Arbitrary Reduction Orders and Inexact Activation Implementations

Most existing expressivity theories for neural networks assume exact real arithmetic, whereas practical neural networks are executed under finite-precision floating-point arithmetic with implementation-dependent execution semantics. Recent works have begun studying the expressive power of floating-point neural networks, but existing results are limited to highly restricted activation functions and idealized assumptions such as fixed left-to-right reduction orders and correctly rounded activation implementations. In this work, we study the expressive power of floating-point neural networks under generalized floating-point execution semantics, including arbitrary reduction orders and inexact activation implementations with bounded ulp errors. We investigate when floating-point neural networks can represent arbitrary functions between floating-point domains exactly. To this end, we introduce a general distinguishability framework and show that the ability to distinguish every pair of distinct inputs in the first layer is necessary for universal representability. This characterization yields broad classes of activation implementations that are not universal representators, extending previous isolated counterexamples such as the correctly rounded cosine activation. We further prove that a suitable form of distinguishability is also sufficient for universal representability under mild conditions on the activation implementation. Using this framework, we establish universal representability results for a broad class of practical activation functions, including implementations of

\mathrm{Sigmoid}

,

\tanh

,

\mathrm{ReLU}

,

\mathrm{ELU}

,

\mathrm{SeLU}

,

\mathrm{GeLU}

,

\mathrm{Swish}

,

\mathrm{Mish}

, and

\sin

, under significantly more realistic floating-point execution models than previously known.

Yeachan Park, Geonho Hwang, Wonyeol Lee +1

Neural Network Activation Functions Universal Approximation Neural Network Approximation Theory Neural Network Expressivity

May 26, 2026cs.LG

More Expressive Feedforward Layers: Part I. Token-Adaptive Mixing of Activations

Feedforward network (FFN) layers account for a large fraction of parameters and nonlinear expressivity in Transformer-based large language models (LLMs). Despite the evolution from ReLU and GELU to gated variants such as SwiGLU, most FFN designs still use a single fixed activation function, applying the same nonlinear transformation to all tokens. In this work, we propose Mixture of Activations (MoA), a token-adaptive FFN design that mixes a dictionary of activation functions using lightweight input-dependent gates while sharing the same linear projections. As an input-independent counterpart, we also introduce learnable activations (LA), which form linear combinations of activation functions for both ReLU-type and SwiGLU-type FFNs. Theoretically, we establish strict finite-width expressive separations among fixed-activation FFNs, LA, and MoA: LA strictly contains fixed-activation FFNs, while MoA strictly contains LA, with the additional expressivity arising from input-dependent nonlinear hybridization. Empirically, we evaluate MoA through extensive pre-training experiments on dense and MoE language models ranging from 0.12B to 2B parameters under different token budgets, optimizers, and learning rate schedules. MoA consistently achieves lower terminal loss and exhibits more favorable scaling behavior than well-tuned baselines, with minimal parameter and computational overhead. These results suggest that token-adaptive activation mixing is a simple and effective mechanism for improving FFN expressivity in LLMs.

Mingze Wang, Jinbo Wang, Yikuan Xia +2

ByteDance Seed · Peking University

Transformer FFNs Transformer Expressivity Transformer Neural Network Activation Functions Feedforward Neural Networks Neural Network Expressivity

May 24, 2026math.NA

Random Neural Network Expressivity for Non-Linear Partial Differential Equations

Neural networks with randomly generated hidden weights (RaNNs) have been extensively studied, both as a standalone learning method and as an initialization for fully trainable deep learning methods. In this work, we study RaNN expressivity for learning solutions to non-linear partial differential equations (PDEs). Despite their widespread use in practical applications, a rigorous theoretical understanding of the approximation properties of RaNNs in this context remains limited. Here, we derive error bounds for RaNN approximations to time-dependent Sobolev functions and obtain a dimension-free approximation rate

\frac{1}{2}

for sufficiently regular functions. We apply our results to two important classes of non-linear PDEs: Porous Medium Equations and Compressible Navier-Stokes Equations, showing that RaNNs are capable of efficiently approximating solutions to these complex, non-linear PDEs. Our theoretical analysis is supported by numerical experiments, showing that the obtained convergence rates extend beyond the considered setting.

Muhammed Ali Mehmood, Lukas Gonon

Department of Mathematics Imperial College London UK · School of Computer Science University of St. Gallen Switzerland

Neural PDE Solvers PDE Solving Neural Network Approximation Theory Neural Network Expressivity

May 22, 2026cs.LG

Characterizing the Representational Capacity of Neural Processes

What functions can Neural Processes represent? We analyze the representational capacity of popular NP architectures: Conditional Neural Processes (CNPs), Attentive Neural Processes (ANPs), Transformer Neural Processes (TNPs), and their latent variants. We prove these architectures form a strict hierarchy. CNP-representable functions are exactly those depending on finitely many expected features of the context distribution. ANPs strictly generalize CNPs via query-dependent reweighting, enabling kernel smoothers. ConvCNPs and ANPs are incomparable; each contains functions outside the other, separated by stationarity versus translation equivariance. TNPs with

L

self-attention layers capture

L

-hop context interactions. For latent NPs, we show finite-dimensional latents provide coherent sampling but do not circumvent encoder limitations; matching GP posterior distributions requires latent dimension scaling with context size. These results provide a theoretical foundation for architecture selection based on task structure.

Robin Young

University of Cambridge

Neural Processes Neural Network Expressivity

May 22, 2026cs.LG

Preisach Attention: A Hysteretic Model of Sequential Memory

We introduce the Preisach Attention Layer (PAL), a novel sequence modelling architecture grounded in the classical Preisach hysteresis operator from mathematical physics. PAL replaces the softmax attention mechanism with a binary relay operator parameterised by learned activation and deactivation thresholds, maintaining a stack of local extrema as its internal state. A single-layer PAL-Transformer with O(1) depth is Turing-complete under arbitrary precision arithmetic, achievable through simulation of a two-stack pushdown automaton -- in contrast to the O(log n) depth required by standard hard-attention transformers. Second, we prove that the function classes computable by PAL and by the transformer are incomparable: PAL computes historical range statistics in O(1) layers that require O(log n) layers for transformers, while transformers support random-access retrieval that PAL cannot perform without auxiliary state. The separating property is rate-independence -- PAL responds only to the sequence of local extrema, not to absolute token positions or temporal spacing. Third, we show that the extremum stack constitutes a minimal sufficient statistic of the input history for all rate-independent functionals, providing a formal analogue of the wiping property in classical hysteresis theory. PAL is thus an efficient architecture for tasks with long episodic memory and weak positional dependence, with O(n log n) total inference cost versus O(n^2) for standard attention.

Piotr Frydrych

The Metrology and Biomedical Engineering Institute · Faculty of Mechatronics, Warsaw University of Technology

Transformer Efficient Attention Neural Network Expressivity

May 21, 2026cs.AI

The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems

Large language models now write software, draft legal documents, and produce clinical notes, yet fundamental limits, from Turing and Arrow to the No Free Lunch theorems, shape what computation can do. This thesis turns such impossibility results from curiosities into design rules. Its flagship result proves an accuracy ceiling set by architecture alone: past a critical reasoning depth, no amount of training moves it, at any adapter rank, sample size, or loss function. Computable before deployment from layer count and embedding width, this Deterministic Horizon is measured between nineteen and thirty-one across twelve transformer architectures, and fine-tuning on optimal-length traces recovers under four percentage points. The mechanism is a capacity invariant of the residual stream, and an information-theoretic conversion yields super-exponential accuracy decay past the horizon. An unconditional circuit-complexity lower bound for modular exponentiation against constant-depth prime-modulus circuits complements this result. The same argument recasts across subfields: preference learning under any misspecified model jumps discontinuously in sample complexity; multi-stage retrieval pipelines require at least as many independent metrics as stages; standard truthful auctions fail for agents with prompt-dependent valuations; and zero-knowledge verification of neural inference pays a measured overhead of one hundred ten to one hundred ninety times per non-linear activation. Together these form a catalogue of sixteen specifications, each pairing a computable boundary, a quantified violation cost, and a constructive design rule: two compositions are proved, one pairing is an honest obstruction, and four remain open. The impossibility-specification methodology is offered for the generative research programme that trustworthy AI may need. Every fundamental limit of AI is also a design rule.

Dongxin Guo

UNIVERSITY OF HONG KONG

Transformer Expressivity Trust in AI Neural Network Expressivity

May 21, 2026math.CO

Holographic functions and neural networks

A fuzzy Boolean function is a map

f:\cube^n\to [0,1]

, where

n\in\mathbb N

. We introduce and compare three ways of saying that such a function has bounded complexity. The first is a sampling property: the value

f(x)

can be recovered, up to small error and with high probability, from the values of a bounded number of randomly chosen coordinates of

x

. We call this the holographic property. The second is a structural property:

f

is uniformly close to a bounded-degree polynomial in boundedly many bounded linear coordinate forms. The third is computational:

f

is uniformly close to the output of a neural network with a bounded number of non-input neurons, bounded Lipschitz activation functions and bounded incoming weights. We prove that these three properties are equivalent up to quantitative changes of the parameters. The implication from holography to polynomial structure uses a variant of a weak version of hypergraph regularity.

Balazs Szegedy

Neural Network Approximation Theory Neural Network Expressivity

May 21, 2026cs.LG

Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers

Transformers have become a central architecture for graph learning, but their application to graphs requires first choosing a tokenization: a graph-to-token map that determines which structural information is exposed at the input. In this work, we show that this choice is a fundamental component of transformer expressivity. We examine three tokenizations that serve as building blocks for many existing graph tokenizations: spectral, random-walk, and adjacency tokenizations. We prove that different tokenizations induce distinct depth regimes: the same graph computation may be realizable by a shallow transformer under one tokenization, while requiring substantially larger depth under another. For example, we prove that random-walk tokenization is lossy for any walk length, making it impossible in general to recover the graph from it, and that while spectral tokenization is lossless, it is ill-conditioned for local tasks. We further show that although both random-walk and spectral tokenizations are derived from adjacency information, it is impossible for a limited-depth transformer to convert between tokenization families in general. In particular, we establish lower bounds and impossibility results showing that unfavorable tokenizations may preclude the efficient recovery of more suitable structural representations. Finally, we complement our theory with controlled experiments on synthetic and real-world tasks, validating the predicted separations and showing that different tasks favor different structural views, and combining complementary tokenizations allows the transformer to leverage distinct signals from each representation.

Maya Bechler-Speicher, Gilad Yehudai, Gil Harari +3

Meta AI · John A. Paulson School of Engineering and Applied Sciences, Harvard University · Google Research +2

Transformer Expressivity Graph Representation Learning Neural Network Expressivity Graph Transformer

May 21, 2026cs.LG

How Many Different Outputs Can a Transformer Generate?

We study how we can leverage only a handful of characteristics of a transformer's architecture to closely predict the number of different sequences it can output, both qualitatively and quantitatively. We provide an upper bound depending on the length of the prompt, which we show empirically to be tight up to a factor less than 10, across architectures and model sizes. Our analysis also provides a theoretical explanation for previously observed empirical failures of transformers on simple sequence tasks, such as copying and cramming. Formally, we prove that (i) the maximal length of accessible sequences (those that the transformer can output for some prompt) grows linearly with the prompt length, (ii) beyond a critical threshold, the proportion of accessible sequences decays exponentially with sequence length, and (iii) the linear coefficient relating prompt length to accessible sequence length admits a theoretical upper bound. Notably, these results hold even with unbounded context and computation time.

Maxime Meyer, Mario Michelessa, Caroline Chaux +1

Department of Mathematics, National University of Singapore, Singapore, 117543 · IPAL, IRL2955, Singapore · School of Computing, National University of Singapore, Singapore, 117543 +2

Transformer Expressivity Transformer Neural Network Expressivity

May 20, 2026cs.LG

Approximation Theory for Neural Networks: Old and New

Universal approximation theorems provide a mathematical explanation for the expressive power of neural networks. They assert that, under mild conditions on the activation function, feedforward neural networks are dense in broad function classes, such as continuous functions on compact subsets of

\mathbb{R}^d

,

L^p

spaces, or Sobolev spaces. Over the past four decades, these qualitative universality results have evolved into a rich quantitative theory addressing approximation rates, parameter efficiency, and the role of architectural features such as depth and width. This survey presents several glimpses into this theory. We review classical density results for single-hidden-layer networks, as well as quantitative bounds that relate approximation error to network size and smoothness assumptions on target functions. Particular emphasis is placed on depth--width trade-offs and on results demonstrating that deeper architectures can achieve superior parameter efficiency for structured function classes. In addition to standard feedforward neural networks, we also review recent developments on Kolmogorov--Arnold Networks (KANs), which offer an alternative architectural paradigm and whose approximation-theoretic properties have begun to attract significant theoretical attention.

Soumendu Sundar Mukherjee, Himasish Talukdar

Statistics and Mathematics Unit, Indian Statistical Institute, Kolkata

Universal Approximation Neural Network Approximation Theory Feedforward Neural Networks Neural Network Expressivity

May 19, 2026cs.LG

A Measure-Theoretic Analysis of Reasoning: Structural Generalization and Approximation Limits

While empirical scaling laws for LLM reasoning are well-documented, the theoretical mechanisms governing out-of-distribution (OOD) generalization remain elusive. We formalize reasoning via optimal transport, projecting discrete trajectories into a continuous metric space to quantify domain shifts using the Wasserstein-1 distance. Invoking Kantorovich duality, we bound OOD generalization via architectural Lipschitz continuity and functional approximation limits. This exposes two primary constraints. First, position-dependent attention (e.g., Absolute Positional Encoding) fails to preserve shift invariance, yielding an

Ω(1)

Lipschitz constant and expected risk, whereas shift-invariant mechanisms (e.g., Rotary Embeddings) preserve equivariance and bound the error. Second, by mapping sequential backtracking to a Dyck-

k

language, we establish a strict circuit depth lower bound for

\text{TC}^0

Transformers. Scaling physical layer depth is necessary to avert representation collapse -- a constraint that scaling representation width cannot bypass due to irreducible approximation bounds in Barron spaces. Evaluations across 54 Transformer configurations on combinatorial search corroborate these bounds, demonstrating that generalization risk degrades monotonically with the Wasserstein domain shift.

Yuyang Zhang, Yifu Zhang, Xuehai Zhou +1

McGill University · Mila - Quebec AI Institute · Université de Montréal

Transformer Expressivity OOD Generalization Neural Network Expressivity Generalization Bounds

May 19, 2026cs.NE

Updating the standard neuron model in artificial neural networks

From their inception in the 1950s, artificial neural networks (ANNs) started using the so-called point neuron model then prevalent in neuroscience, hoping that this analogy would allow for a better emulation of brain function. Over the years the neuroscience literature has shown that the point neuron model is too simplistic to properly represent many fundamental neural processes; however, the standard neuron model in ANNs still remains the same. Here we substitute it by a very recent model of cortical cells and demonstrate through theoretical analyses and experimental results how, simply by using a more realistic neural unit element without augmenting the number of parameters, the resulting ANNs offer a number of important advantages that include increases in expressivity, robustness and learning speed, and a reduction in memorization and the amount of training data needed.

Raul Mohedano, Thomas Batard, Erik Velasco-Salido +4

1Spanish National Research Council (CSIC), Madrid, Spain. · Center for Research in Mathematics (CIMAT), Guanajuato, Mexico. · 3Universidad Aut´onoma de Madrid (UAM), Madrid, Spain. +1

Neural Network Robustness Neural Network Expressivity

May 18, 2026cs.LG

The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought

Existing expressivity results for transformers typically rely on hardmax attention, high precision, and other architectural modifications that disconnect them from the models used in practice. We bridge this gap by analyzing standard transformer decoders with softmax attention and rounding of activations and attention weights, while allowing depth and width to grow logarithmically with the context length. As an intermediate step, we construct hardmax transformers with ternary activations and well-separated attention scores that simulate Turing machines using Chain-of-Thought (CoT). This lets us convert the constructions to equivalent softmax transformers without the unrealistic parameter magnitudes or activation precision that prior approaches would require. Using the same technique, we analyze a recently proposed summarized CoT paradigm and show that it simulates Turing machines more efficiently, with model size scaling logarithmically in a space bound rather than a time bound. We empirically test predictions made by our results on a Sudoku reasoning task and find better alignment with learnability than for prior high-precision results. Our code is available at https://github.com/moritzbroe/transformer-expressivity.

Moritz Brösamle, Stephan Eckstein

Department of Mathematics, University of Tübingen, Germany.

Transformer Expressivity Transformer CoT Reasoning Neural Network Expressivity

May 17, 2026cs.LG

Beyond Accuracy: Robustness, Interpretability and Expressiveness of EEG Foundation Models

EEG foundation models (EEG-FMs) have been evaluated predominantly on clean, in-distribution accuracy, demonstrating modest gains over supervised baselines and weak frozen representations. This study examines whether these conclusions hold beyond clean accuracy by evaluating six EEG-FMs and a supervised baseline across ten datasets along three layers of analysis: (i) Robustness: we apply test-time perturbations including additive noise, random and region-based channel dropout and region-specific noise injection. Our analyses show that no single model dominates all failure modes. The most noise-robust model is among the most fragile under channel dropout and much of the dropout fragility disappears when channels are removed rather than zero-padded. (ii) Interpretability: using attribution methods in EEG-FMs, we show that models broadly concentrate relevance on task-appropriate brain regions consistent with known neurophysiology. (iii) Expressiveness: we demonstrate that the poor head-only performance previously attributed to low-quality pre-trained representations is largely explained by the pooling strategy and that EEG-FMs possess sufficient representational capacity when their token-level embeddings are preserved. Furthermore, with block-wise probing and attention analysis we show that late blocks are repurposed during fine-tuning, while early blocks already hold task-related information. Our results show that conclusions about EEG-FMs depend on evaluation choices and we recommend that future evaluation of EEG-FMs should report robustness per perturbation type, produce attribution maps and examine multiple pooling strategies.

Urban Širca, Maryam Alimardani, Stefanos Zafeiriou +1

Vrije Universiteit Amsterdam · Imperial College London

EEG Decoding Neural Network Interpretability Neural Network Expressivity EEG Foundation Models

May 13, 2026cs.LG

The WidthWall: A Strict Expressivity Hierarchy for Hypergraph Neural Networks

Hypergraphs provide a natural framework to model higher-order interactions in scientific, social, and biological systems. Hypergraph neural networks (HGNNs) aim to learn from such data, yet it remains unclear which higher-order structures these models can represent. We show that hypergraph expressivity is governed by which small patterns an architecture can detect and count. We formalize this via homomorphism densities, which measure how often a structural motif appears in a hypergraph. Combining classical homomorphism-count completeness with invariant approximation, we show that homomorphism densities generate all continuous hypergraph invariants and organize them into a strict hierarchy indexed by hypertree width. This yields a Width Wall: a fundamental architectural limit beyond which no hidden dimension, training procedure or fixed-depth HGNN can represent invariants requiring wider patterns. Our framework provides a unified characterization of 15 HGNN architectures, precisely identifies information lost by clique expansion, and motivates density-aware models that extend expressivity beyond bounded-width message passing. We experimentally validate this finding on an APPLICATION NODE CLASSIFICATION SUITE of real-world hypergraphs, where the Width Wall predicts when graph-reduction baselines fail and when density features help.

Fengqing Jiang, Yuetai Li, Yichen Feng +6

University of Washington · Western Washington University · King Abdulaziz City for Science and Technology +1

GNN Expressivity Hypergraph Neural Networks Neural Network Expressivity

May 12, 2026cs.LG

Lower bounds for one-layer transformers that compute parity

This note shows that no self-attention layer post-processed by a rational function can sign-represent the parity function unless the product of the number of heads and the degree of the post-processing function grows linearly with the input length. Combining this lower bound with rational approximation of ReLU networks yields a margin-dependent extension for self-attention layers post-processed by ReLU networks.

Daniel Hsu

Transformer Expressivity Self-Attention Transformer Attention Neural Network Approximation Theory Multi-Head Attention Neural Network Expressivity

May 12, 2026cs.LG

Scaling Laws and Tradeoffs in Recurrent Networks of Expressive Neurons

Cortical neurons are complex, multi-timescale processors wired into recurrent circuits, shaped by long evolutionary pressure under stringent biological constraints. Mainstream machine learning, by contrast, predominantly builds models from extremely simple units, a default inherited from early neural-network theory. We treat this as a normative architectural question. How should one split a fixed parameter budget

P

between the number of units

N

, per-unit effective complexity

k_e

, and per-unit connectivity

k_c

? What controls the optimal allocation? This calls for a model in which per-unit complexity can be tuned independently of width and connectivity. Accordingly, we introduce the ELM Network, whose recurrent layer is built from Expressive Leaky Memory (ELM) neurons, chosen to mirror functional components of cortical neurons. The architecture allows for individually adjusting

N

,

k_e

, and

k_c

and trains stably across orders of magnitude in scale. We evaluate the model on two qualitatively different sequence benchmarks: the neuromorphic SHD-Adding task and Enwik8 character-level language modeling. Performance improves monotonically along each of the three axes individually. Under a fixed budget, a clear non-trivial optimum emerges in their tradeoff, and larger budgets favor both more and more complex neurons. A closed-form information-theoretic model captures these tradeoffs and attributes the diminishing returns at two ends to: per-neuron signal-to-noise saturation and across-neuron redundancy. A hyperparameter sweep spanning three orders of magnitude in trainable parameters traces a near-Pareto-frontier scaling law consistent with the framework. This suggests that the simple-unit default in ML is not obviously optimal once this tradeoff surface is probed, and offers a normative lens on cortex's reliance on complex spatio-temporal integrators.

Aaron Spieler, Georg Martius, Anna Levina

University of Tübingen, Germany · Max Planck Institute for Intelligent Systems, Tübingen, Germany · Max Planck Institute for Biological Cybernetics, Tübingen, Germany

Recurrent Neural Networks Neural Scaling Laws Neural Network Expressivity

May 11, 2026cs.LG

The Polynomial Counting Capabilities of Message Passing Neural Networks

The counting power of Message Passing Neural Networks (MPNN) has been the subject of many recent papers, showing that they can express logic that involves counting up to a threshold or more generally satisfy a linear arithmetic constraint. In this paper, we study the counting capabilities of MPNN beyond linear arithmetic, primarily utilising local and global mean aggregations. In particular, our goal is to tease out conditions required to express extensions of graded modal logic with polynomial counting constraints. We show that global polynomial counting constraints in node-labelled graphs can be checked using mean MPNN under mild assumptions. Checking local constraints is also possible, if we consider formulas with no nested modalities and additionally either (i) permit sum/max aggregations, or (ii) only restrict to regular graphs. We also show how formulas with nested modalities can be captured by mean MPNN over graphs with tree-like structures and similar assumptions.

Marco Sälzer, Pascal Bergsträßer, Anthony W. Lin

1RPTU University Kaiserslautern-Landau · 2Max Planck Institute for Software Systems (MPI-SWS)

Graph Neural Networks Message Passing Neural Networks Neural Network Expressivity

May 10, 2026cs.LG

Minimal Filling Architectures of Polynomial Neural Networks: Counterexamples, Frontier Search, and Defects

We provide counterexamples to the unimodal minimal filling architecture conjecture for polynomial neural networks (PNNs) with power activation functions. Fixing the input and output widths, the conjecture states that any minimal filling architecture has unimodal widths for the hidden layers. We found counterexamples via a frontier search, recursive dimension bounds on neurovarieties, and symbolic computation. Notably, several subarchitectures of our main example exhibit large defect, in contrast with the predominantly small-defect behavior observed in prior literature.

Kevin Dao, Jose Israel Rodriguez

Department of Mathematics, University of Wisconsin-Madison, Wisconsin, USA.

Polynomial Neural Networks Neural Network Approximation Theory Neural Network Expressivity