MinMax Recurrent Neural Cascades

• URL: http://arxiv.org/abs/2605.06384v2
• Date: Fri, 08 May 2026 08:53:33 GMT
• Title: MinMax Recurrent Neural Cascades
• Abstract summary: We show that the MinMax algebra provides a form of recurrence that is expressively powerful, efficiently implementable.<n>We call MinMax Recurrent Neural Cascades (RNCs) the models obtained by cascading several layers of neurons that employ such recurrence.
• Score: 57.70637726519403
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We show that the MinMax algebra provides a form of recurrence that is expressively powerful, efficiently implementable, and most importantly it is not affected by vanishing or exploding gradient. We call MinMax Recurrent Neural Cascades (RNCs) the models obtained by cascading several layers of neurons that employ such recurrence. We show that MinMax RNCs enjoy many favourable theoretical properties. First, their formal expressivity includes all regular languages, arguably the maximal expressivity for a finite-memory system. Second, they can be evaluated in parallel with a runtime that is logarithmic in the input length given enough processors; and they can also be evaluated sequentially. Third, their state and activations are bounded uniformly for all input lengths. Fourth, at almost all points, their loss gradient exists and it is bounded. Fifth, they do not exhibit a vanishing state gradient: the gradient of a state w.r.t. a past state can have constant value one regardless of the time distance between the two states. Finally, we find empirical evidence that the favourable theoretical properties of MinMax RNCs are matched by their practical capabilities: they are able to perfectly solve a number of synthetic tasks, showing superior performance compared to the considered state-of-the-art recurrent neural networks; also, we train a MinMax RNC of 127M parameters on next-token prediction, and the obtained model shows competitive performance for its size, providing evidence of the potential of MinMax RNCs on real-world tasks.

Related papers

• A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory [3.0120086446979877]
  We consider the problem of exact computation of the maximum function over $d$ real inputs using ReLU neural networks.<n>We show that a sufficiently narrow network cannot capture the non-linearities of the maximum.<n>This suggests that despite its simple nature, the maximum function possesses an inherent complexity.
  arXiv  Detail & Related papers  (2026-01-04T07:40:42Z)
• When Bayesian Tensor Completion Meets Multioutput Gaussian Processes: Functional Universality and Rank Learning [53.17227599983122]
  Functional tensor decomposition can analyze multi-dimensional data with real-valued indices.<n>We propose a rank-revealing functional low-rank tensor completion (RR-F) method.<n>We establish the universal approximation property of the model for continuous multi-dimensional signals.
  arXiv  Detail & Related papers  (2025-12-25T03:15:52Z)
• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  Recent developments have given rise to various models, such as Gated Linear Attention (GLA) and Mamba.<n>This raises a natural question: can we characterize the full class of neural sequence models that support near-constant-time parallel evaluation and linear-time, constant-space sequential inference?
  arXiv  Detail & Related papers  (2025-06-12T17:32:02Z)
• Stuffed Mamba: Oversized States Lead to the Inability to Forget [53.512358993801115]
  We show that Mamba-based models struggle to effectively forget earlier tokens even with built-in forgetting mechanisms.<n>We show that the minimum training length required for the model to learn forgetting scales linearly with the state size, and the maximum context length for accurate retrieval of a 5-digit passkey scales exponentially with the state size.<n>Our work suggests that future RNN designs must account for the interplay between state size, training length, and forgetting mechanisms to achieve robust performance in long-context tasks.
  arXiv  Detail & Related papers  (2024-10-09T17:54:28Z)
• Capacity of the treelike sign perceptrons neural networks with one hidden layer -- RDT based upper bounds [0.0]
  We study the capacity of emphsign perceptrons neural networks (SPNN) We focus on 1-hidden layer emphtreelike committee machine (TCM) architectures.
  arXiv  Detail & Related papers  (2023-12-13T16:06:18Z)
• On the Representational Capacity of Recurrent Neural Language Models [56.19166912044362]
  We show that a rationally weighted RLM with computation time can simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions. We also provide a lower bound by showing that under the restriction to real-time computation, such models can simulate deterministic real-time rational PTMs.
  arXiv  Detail & Related papers  (2023-10-19T17:39:47Z)
• Bridging Discrete and Backpropagation: Straight-Through and Beyond [62.46558842476455]
  We propose a novel approach to approximate the gradient of parameters involved in generating discrete latent variables. We propose ReinMax, which achieves second-order accuracy by integrating Heun's method, a second-order numerical method for solving ODEs.
  arXiv  Detail & Related papers  (2023-04-17T20:59:49Z)
• Softmax-free Linear Transformers [90.83157268265654]
  Vision transformers (ViTs) have pushed the state-of-the-art for visual perception tasks. Existing methods are either theoretically flawed or empirically ineffective for visual recognition. We propose a family of Softmax-Free Transformers (SOFT)
  arXiv  Detail & Related papers  (2022-07-05T03:08:27Z)
• Breaking the Limits of Message Passing Graph Neural Networks [6.175401630947573]
  Graph Neural Networks (MPNNs) have a linear complexity with respect to the number of nodes when applied to sparse graphs. In this paper, we show that if the graph convolution supports are designed in spectral-domain by a non-linear custom function of eigenvalues, the MPNN is theoretically more powerful than the 1-WL test.
  arXiv  Detail & Related papers  (2021-06-08T13:26:56Z)
• ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation [5.35599092568615]
  This paper studies the power of artificial neural networks with rectified linear units. We show that two fundamental optimization problems can be solved with neural networks of size $mathcalO(m2n2)$.
  arXiv  Detail & Related papers  (2021-02-12T17:23:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.