expressivity

The paper introduces a common layer equation that unifies graph neural networks into seven components, enabling architectural comparison, theoretical analysis, and insights into issues like oversmoothing and expressivity.

This theoretical paper proves that ReLU-based message-passing GNNs are strictly more expressive than GNNs using any eventually constant activation functions (e.g., truncated ReLU) with respect to Boolean queries, even on Boolean-featured graphs.

This paper provides a theoretical analysis of deep transformers' ability to model hierarchical structures using bounded-depth context-free grammars, constructing explicit positional-attention transformers that encode grammatical states in linearly separable subspaces.

This theoretical paper analyzes the expressivity of padded transformers, showing that attention type, width, and uniformity have little impact compared to numeric precision and model depth. It establishes equivalences between transformer variants and circuit complexity classes like AC0 and TC0, providing a robust characterization.

TBP-mHC introduces a novel parameterization for manifold-constrained hyper connections in residual networks, achieving full expressivity of the Birkhoff polytope with O(n^2) degrees of freedom and improved stability and scalability.

This paper proposes LAD-inspired pre-pretraining using a formal language called MP-Struct that encodes natural-language-like structures. It shows that this approach improves token efficiency and imparts human-like resistance to structurally implausible languages, challenging prior hypotheses about effective pre-pretraining languages.

This paper presents Olmo Hybrid, a 7B-parameter language model that combines attention and Gated DeltaNet recurrent layers, demonstrating both theoretical and empirical advantages over pure transformers. The work shows that hybrid models have greater expressivity, scale more efficiently during pretraining, and outperform comparable transformer baselines.