ICML 2026 Papers

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.

While heavy-tailed synaptic weight distributions are pervasive in biological neural networks, their computational role---particularly in relation to generalization---remains poorly understood. To address this, we develop a novel optimal-transport-based optimization algorithm that incorporates key biological constraints, including Dale’s principle and heavy-tailed synaptic statistics, to train recurrent neural networks (RNNs) on a wide range of cognitive tasks. We show that these biologically constrained, heavy-tailed RNNs exhibit substantially improved generalization, which we further characterize within a PAC-Bayes framework. Our theoretical analysis and numerical experiments reveal two complementary mechanisms underlying this generalization enhancement. Topologically, heavy-tailed connectivity induces an effectively low-rank structure, which in turn yields low-dimensional neural dynamics. Geometrically, heavy-tailed connectivity intrinsically shapes task variable representations to lie near a linear manifold, thereby improving generalization for a linear readout strategy. Together, these results identify heavy-tailed connectivity as a biologically grounded intrinsic mechanism that promotes low-rank structure and favorable representational geometry, leading to improved generalization in flexible cognitive tasks.