Reservoirs as Existence Certificates: Measuring How Much Recurrent Networks Fail to Learn What They Can Represent

When a recurrent network trained by gradient descent fails at a task, we usually cannot tell why. The architecture may be unable to represent a solution, or a solution may exist that the optimizer never finds. Approximation theory rarely settles the question. Its constructions are brittle, use idealized widths, and say nothing about the particular network a practitioner trained. This proposal uses reservoir computing to answer the question directly. In reservoir computing, the recurrent weights are left fixed and only a linear output layer is fit. An echo state network with $N$ units is itself a recurrent network of width $N$: it simply has frozen recurrent weights. Fitting its readout is a convex problem, so we can solve it to global optimality. Any loss the reservoir reaches is therefore a constructive, checkable proof that the width-$N$ architecture contains a solution at least that good. If backpropagation through time (BPTT) — the standard method that unrolls the network and differentiates through every step — then lands above that loss in the same architecture, the shortfall is a certified failure of optimization, not of capacity.

The opportunity is that recent reservoir work has made these certificates much tighter than a random matrix would give. Configured pole distributions, structured linear memory, and spectral designs all improve fixed-weight networks by large margins. That turns reservoirs into a practical lower bound on what exists. With it we can map the existence-trainability gap of vanilla and gated recurrent networks task by task and width by width. We can also ask whether gradient descent started at a certificate improves it or degrades it.

Core Claim

The key quantity is the certified trainability gap at width $N$. For a task and width $N$:

$$G(N, B) = L_{\text{BPTT}}(N, B) - \min_{\phi \in \Phi} L^{\star}_{\text{readout}}(N, \phi)$$

The terms are defined as follows. $L_{\text{BPTT}}(N, B)$ is the best test loss reached by BPTT on a width-$N$ network of a given cell type with hyperparameter-search budget $B$. $\Phi$ is a small family of reservoir designs (pole distributions, memory structures, scalings). $L^{\star}_{\text{readout}}$ is the globally optimal convex readout loss for a fixed reservoir drawn from design $\phi$.

A positive $G$ means gradient descent failed to find a solution that provably exists in its own hypothesis class. We claim three things. First, $G$ is large and positive for vanilla tanh networks on long-memory tasks. Second, $G$ grows with the memory horizon. Third, gated cells shrink but do not eliminate it.

Prior work only argued this indirectly. Capacity and Trainability in Recurrent Neural Networks separated capacity from trainability by showing that parameter-matched architectures store about 5 bits per parameter, while vanilla networks often fail to converge on parenthesis counting and arithmetic. Its evidence that a solution existed was the success of other architectures; it never exhibited a solution inside the failing architecture. When Learning Hurts: Fixed-Pole RNN for Real-Time Online Training showed that learning poles creates permutation symmetries and ill-conditioned Hessians, with a condition number around $10^3$ versus about 2.5 for fixed poles. Its proofs are restricted to linear single-input networks and one online wireless benchmark.

Our proposal differs from both in two ways. Comparisons are width-matched within one architecture class rather than parameter-matched across classes. The tasks are nonlinear and algorithmic, where neither paper's theory applies.

Research Program

Building certificates. For each task we build fixed-weight networks whose structure lies inside the architecture that BPTT will train. The certificate family $\Phi$ draws on three lines of reservoir work, all reused as methods rather than as competitors.

The first is the configured pole density of Universal Approximation of Linear Time-Invariant (LTI) Systems through RNNs. That paper shows a linear reservoir is equivalent to a diagonal one. It derives a pole density that improves the error scaling from $O(M^{-2})$ for uniform poles to $O(M^{-4})$, where $M$ is the reservoir size. We use it as a diagonal recurrent block before a tanh nonlinearity. Its optimality is no longer guaranteed there, which is exactly what we want to measure.

The second is the decoupled linear memory of Reservoir Memory Networks. There, an untrained Legendre or shift-register memory drives an untrained nonlinear reservoir.

The third is the vectorized leak rates used in Syntactic Learnability of Echo State Neural Language Models at Scale.

Searching over $\Phi$ means choosing a handful of global scalars, such as spectral radius, input scaling and pole-density parameters, on validation data. This is cheap because each candidate requires only one ridge or logistic regression.

Keeping comparisons honest. Three constraints keep the certificate inside the trained class.

First, the readout sees only what the trained network's output layer sees. For classification that is the final hidden state; for prediction it is the per-step state. Feature concatenation across time and bidirectional reading, as in Spectral-Aware Reservoir Computing, are forbidden.

Second, when the certificate uses a linear memory block feeding a tanh block, the BPTT comparator is the same mixed linear/tanh block-structured network with all weights free.

Third, the comparison is width-matched rather than parameter-matched. A width-$N$ reservoir has $N^2$ recurrent weights that are fixed but nonzero, and the trained network has the same $N^2$ slots. Parameter matching in the style of Collins et al. answers a different question, so we report it separately.

Analyzing the gap. We trace $G(N, B)$ against width, memory horizon and tuning budget, for vanilla tanh, GRU and LSTM cells. We then start BPTT exactly at the best certificate and track loss, the recurrent condition number and eigenvalue drift during training. This tests whether the pathologies Morgan et al. derived for linear networks — pole collisions, narrow valleys and drift toward the unit circle — also appear in nonlinear ones. If gradient descent started at a certificate worsens it, that is direct evidence that learning hurts beyond the linear regime. Finally, we freeze subsets of the certificate's recurrent weights and train the rest. This locates which parameters are responsible for the optimization breakdown.

Baselines

Naive reference: uniform random reservoir. This is a standard echo state network with a uniform random recurrent matrix rescaled below unit spectral radius, with a convex readout. It is the "do nothing" certificate and the ablation that isolates our key ingredient, which is the configured design family $\Phi$. On sequential MNIST, Reservoir Memory Networks reports about 77% accuracy for a standard echo state network. Configured certificates must clearly exceed this at matched width. Otherwise the method gives weak certificates that only reveal trivial gaps.

Strongest existing fixed-weight method: Legendre reservoir memory network. This is the Legendre memory network of Gallicchio and Ceni, which reports 95% accuracy on sequential MNIST in Reservoir Memory Networks. We reimplement it under our final-state readout constraint at the same total width. Some loss relative to 95% is expected, and we will report it rather than quote the original figure as our own.

Strongest trained competitor: BPTT with Adam on vanilla, GRU and LSTM cells. Each gets Gaussian-process hyperparameter search following the protocol of Capacity and Trainability in Recurrent Neural Networks. That paper reports vanilla networks "often failed to converge entirely" on parenthesis counting and arithmetic, but gives no single accuracy figure. No reported result was found on Lacuna for a width-matched vanilla RNN on those tasks, so we produce our own. The tuning budget $B$ is swept from a few to several hundred trials, against a certificate search that is also given $B$ readout fits.

"Beating" means two things. Either BPTT at the largest budget remains above the certificate, which is a positive gap, or it falls below it, which shows gradient descent found something reservoirs cannot. Both outcomes are informative. The claim is falsified if vanilla networks close the gap at moderate budget on long-horizon tasks.

On the LTI benchmark, the configured-pole result to reproduce is the $O(M^{-4})$ scaling and the up-to-four-to-six orders of magnitude improvement over uniform poles at $M=100$. This serves as a sanity check that our certificate pipeline recovers known linear behavior before we move to nonlinear tasks.

Why not just…?

Why not just train an LSTM? Gating does reduce trainability failures. Collins et al. show gated cells converge where vanilla cells fail, and on BLiMP a trained LSTM reaches 67.8% versus 60.5% for a 65,536-unit echo state network (Syntactic Learnability of Echo State Neural Language Models at Scale). But using a better architecture does not tell you whether the original one was trainable. We include gated cells as comparators and also certify their gap, since a reservoir is a degenerate gated network with constant gates. If LSTMs show zero gap everywhere, that is a real finding and narrows our claim to vanilla cells.

Why not just compare BPTT with an ordinary echo state network? That is the obvious experiment suggested by the literature gap. A uniform random reservoir gives a loose lower bound, so a small measured gap could simply mean the certificate is weak. The uniform-versus-configured ablation in the Baselines section measures how much tightening matters. If configured designs never beat uniform ones on the nonlinear tasks, we report that the Jere et al. gains do not transfer past linearity, which is itself an open question the file identifies.

Why not just tune BPTT harder or restart more? This is the main threat. The apparent gap might be an artifact of an under-tuned optimizer. Collins et al. needed thousands of runs to reach capacity limits. We therefore report $G$ as a function of budget $B$ rather than at one setting, and we also start BPTT at the certificate itself, which removes the "bad starting point" explanation. If the gap vanishes with enough budget, the honest conclusion is that the failure is a search-cost problem rather than a landscape barrier, and the budget curve quantifies that cost.

Why not just fine-tune the reservoir with gradient descent? This is part of the program rather than an alternative. Its outcome — whether the loss drops, stalls or rises from a certified start — is our test of whether the Morgan et al. pathologies extend to nonlinear networks.

Proposed Experiments

The first experiment is a pipeline check on the synthetic LTI identification benchmark of Jere et al.. It must reproduce the $M^{-2}$ versus $M^{-4}$ scaling, and BPTT on the matching linear network should show the ill-conditioning reported by Morgan et al..

The core experiment uses the parenthesis-counting and character-arithmetic tasks from Collins et al. We vary nesting depth and string length to control the memory horizon, with widths from 32 to 1024. Counting is a natural test because a linear integrator with a pole near one, followed by a tanh readout, can represent bounded counts. Certificates should therefore exist even where vanilla BPTT is known to fail.

Next is sequential MNIST at 784 steps, plus the 12 UCR datasets used by Reservoir Memory Networks. These test whether the gap persists on real long-horizon classification, using the final-state readout constraint throughout.

The decisive checks are three. First, $G$ should be positive and increase with nesting depth for vanilla cells at the largest tuning budget. Second, BPTT started at the best certificate should show measurable loss increase or eigenvalue drift in nonlinear networks. Third, the configured-versus-uniform ablation should show certificates tight enough that the gap is not explained by a weak lower bound. If all three hold, we will have the first width-matched, constructive demonstration that nonlinear recurrent networks routinely fail to learn solutions provably contained in their own parameter space.