On the Expressivity of Recurrent Neural Cascades with Identity

Nadezda A. Knorozova, Alessandro RoncaarXiv 2024 · DOI · OpenReview

Introduction

Recurrent Neural Networks (RNNs) are the workhorses of sequence modeling, yet understanding their exact computational limits remains a significant theoretical challenge. This paper investigates Recurrent Neural Cascades (RNCs), a specific architecture where neurons are arranged in a sequence such that each neuron only depends on its predecessors, precluding cycles. Specifically, the authors focus on RNC+, a subclass where recurrent weights are restricted to positive values.

Previous research established that RNC+ can capture all "star-free" regular languages—the same class of patterns described by Linear Temporal Logic (LTL). However, it remained unclear whether these networks could recognize complex, non-regular sequences that traditional finite automata cannot. This research aims to close that gap by showing that under common conditions, RNC+ is strictly limited to the star-free regular domain.

Methodology: From Neurons to Automata

The authors employ a formal mathematical approach, treating RNCs as dynamical systems and comparing them to semiautomata cascades. A pivotal concept in this analysis is the identity element: an input (such as a "no-op" or "stay" command) that allows the system to remain in its current state regardless of how many times it appears.

By analyzing the dynamics of the tanh activation function, the researchers demonstrate a structural correspondence between continuous neural states and discrete logic. They show that a single neuron with positive weights behaves essentially like a three-state semiautomaton, capable of being in a "low," "high," or "transition" state, but unable to oscillate or count in a way that exceeds simple regular logic.

Analysis of the tanh activation function's dynamics, illustrating the fixed points $p_-$ and $p_+$ that define the three-state behavior.

The core of the proof relies on homomorphic representations, proving that an entire cascade of $n$ neurons is functionally equivalent to a cascade of these three-state machines. This provides a clear bridge between neural sequence modeling and algebraic automata theory.

Key Results and Expressivity Boundaries

The primary contribution of this work is Theorem 5, which provides a definitive boundary for the power of RNC+. The theorem states that any language with an identity element recognized by an RNC+ is a star-free regular language.

Expressivity map showing the containment of star-free languages within the intersection of regular languages and those with an identity element.

This result has several profound implications for the field:

  • The Power of "Nothing": The existence of an identity element is a powerful constraint. In many real-world sequences (like sensor logs or grid-world agents with a "stay" action), there are neutral events. The authors show that if a language has such an element, RNC+ cannot "cheat" its way into non-regular complexity.
  • Succinctness Limits: The paper proves that RNC+ is not "magically" more efficient than classical automata. An RNC+ with $n$ neurons can be replaced by an automaton with at most $3^n$ states, providing a hard limit on architectural efficiency.
  • Characterization of Arithmetic: While RNC+ can handle some arithmetic (e.g., checking if a sum of bits equals a specific constant), it fails at others (e.g., sum modulo 7). The latter requires "counting" behavior that is not star-free, which these networks cannot replicate.

Limitations and Future Work

The authors identify three major frontiers for future research:

  1. The "White Area": The paper leaves open the possibility that RNC+ could recognize non-regular languages if no identity element exists (i.e., every input forces a state change).
  2. Negative Weights: This study focused on positive weights. Allowing negative weights introduces oscillations, which likely extends expressivity beyond the star-free class, though a precise characterization is missing.
  3. Activation Functions: The proofs are specific to the tanh function. Exploring how ReLU, Sigmoid, or GeLU change these expressivity boundaries is a logical next step.

By establishing these limits, the paper provides a rigorous foundation for understanding the relationship between neural architectures and formal language theory.

Summary updated

Abstract

Recurrent Neural Cascades (RNC) are the class of recurrent neural networks with no cyclic dependencies among recurrent neurons. Their subclass RNC+ with positive recurrent weights has been shown to be closely connected to the star-free regular languages, which are the expressivity of many well-established temporal logics. The existing expressivity results show that the regular languages captured by RNC+ are the star-free ones, and they leave open the possibility that RNC+ may capture languages beyond regular. We exclude this possibility for languages that include an identity element, i.e., an input that can occur an arbitrary number of times without affecting the output. Namely, in the presence of an identity element, we show that the languages captured by RNC+ are exactly the star-free regular languages. Identity elements are ubiquitous in temporal patterns, and hence our results apply to a large number of applications. The implications of our results go beyond expressivity. At their core, we establish a close structural correspondence between RNC+ and semiautomata cascades, showing that every neuron can be equivalently captured by a three-state semiautomaton. A notable consequence of this result is that RNC+ are no more succinct than cascades of three-state semiautomata.
BibTeX
@misc{knorozova2024expressivity,
  author = {Nadezda A. Knorozova and Alessandro Ronca},
  title = {{On the Expressivity of Recurrent Neural Cascades with Identity}},
  year = {2024},
  eprint = {2405.11657},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.11657},
}
Figure