PaperlayerView exact revision on arXiv

Source-linked AI summary

Memristive-Friendly Hadamard Reservoir Computing: Structured, Multiplier-Free Recurrences at Scale

Andrea Ceni, Gianluca Milano, Carlo Ricciardi, Claudio Gallicchio

arXiv:2608.28295v1cs.AI

TL;DR

Dense recurrent matrices limit the physical scalability of conventional and memristive-friendly reservoir computing. The paper replaces them with structured orthogonal Hadamard operators in standard and memristive-friendly ESNs, obtaining benchmark parity with dense orthogonal reservoirs while reducing recurrent cost and memory.

  • Problem

    Dense recurrent coupling in reservoir computing requires O(N^2) storage and operations, limiting physically realizable large reservoirs.

  • Method

    The paper uses M = D2 bHN Π D1 as a multiplier-free recurrent operator in H-ESN and MF-H-ESN models, with one binary input connection per unit.

  • Results

    Across twenty classification and seven regression benchmarks up to N = 8192, Hadamard reservoirs match dense orthogonal reservoirs and outperform cycle reservoirs increasingly with size.

  • Takeaways & Limitations

    The structured recurrence preserves the relevant orthogonality and mixing behavior while providing O(N log N) computation and O(N) parameters without matrix materialization.

  • Takeaways & Limitations

    The global Lipschitz echo state condition is sufficient but far from necessary, and sharper local conditions remain future work.

Abstract

from arXiv · show

Reservoir Computing (RC) designs Recurrent Neural Networks around a fixed, i.e., untrained, recurrent layer, and is a natural candidate for neuromorphic hardware. Memristive-friendly reservoirs derive the neuron dynamics from memristive-device kinetics, but still rely on dense recurrent matrices, which are expensive to realize physically. In this paper, we replace the dense matrix with a structured orthogonal operator, built from sign diagonals, a permutation, and a fast Walsh-Hadamard transform. The operator is multiplier-free, requires $O(N)$ parameters and $O(N\log N)$ operations per step, and is never materialized as a matrix. We instantiate it in a standard and in a memristive-friendly Echo State Network, with one binary input connection per unit. Our mathematical analysis shows that exact orthogonality yields an echo state condition that is tight in the recurrent scaling, and a noise response that is predictable at design time. Moreover, the operator mixes the whole state in a single application. Experiments on twenty classification and seven regression benchmarks, at reservoir sizes up to $N = 8192$, show that the structured models match dense orthogonal reservoirs, and achieve better mean performance than the cycle reservoir by a margin that widens with size. Furthermore, we time the recurrent step on three hardware platforms, where it is up to $50\times$ faster than a dense product and $10^4\times$ smaller in memory. Finally, we ablate the operator and measure the response to noise, quantization, device mismatch and discrete faults.

1. Introduction

The paper addresses the cost of dense recurrent coupling in reservoir computing by introducing structured Hadamard recurrences for standard and memristive-friendly reservoirs. The models retain orthogonality and broad evaluation while reducing computational and hardware requirements.

  • Motivation: Dense ESN coupling requires O(N^2) weights, multiply-accumulate operations, and programmable conductances, becoming least affordable as reservoir size increases.Hardware-oriented alternatives range from minimal cycle topologies to dense orthogonal recurrences, with different trade-offs in cost, memory, and mixing.
  • Contribution: The H-ESN and MF-H-ESN replace dense recurrence with a structured orthogonal operator and use one binary input connection per unit.The MF-H-ESN preserves memristive-device neuron dynamics while changing only the recurrent coupling.
  • Analysis: The analysis derives a tight echo state condition in recurrent scaling, a design-time noise gain, and separate roles for the operator’s randomization elements.The study also examines spectral and mixing properties.
  • Evaluation: Experiments cover twenty classification and seven regression benchmarks, comparing the proposed models with dense, cycle, dense-orthogonal, and gated recurrent baselines up to N = 8192.A critical-difference analysis is included.
  • Robustness: The paper evaluates operator ablations and robustness to state noise, quantization, device mismatch, and discrete faults.The ablation attributes memory preservation near instability to permutation and nonlinear-state richness to sign diagonals.

2. Background and related work

The background frames ESNs as fixed nonlinear reservoirs with trainable linear readouts and introduces a memristive-friendly variant based on device kinetics. It positions structured orthogonal operators between local cycle reservoirs and expensive dense orthogonal recurrences.

  • Echo State Networks: ESNs use an untrained recurrent nonlinear layer and a trainable linear readout, with stability constrained by the Echo State Property.The leaky rate α controls the speed of reservoir updates relative to the input dynamics.
  • Echo State Networks: The conventional ESN uses recurrent and input matrices plus biases, whose initialized weights remain untrained after stability-constrained initialization.Input and bias scales, recurrent scaling, and leak rate shape the dynamics.
  • Memristive-friendly reservoirs: The memristive-friendly ESN derives state updates from potentiation-depression kinetics governed by voltage-dependent rates.Its conductance-like state is driven by a rescaled pre-activation within the device operating window.
  • Memristive-friendly reservoirs: The parameters ε and γ jointly determine retention by combining the kinetics integration step with device volatility.γ = 1 represents ideal non-volatile behavior, while smaller values represent self-decaying states.
  • Related work: Cycle reservoirs provide minimal deterministic connectivity, whereas dense orthogonal recurrences provide strong short-term memory at dense storage and application cost.Structured fast-transform operators occupy an intermediate design space with O(N log N) multiplier-free projections and had not been systematically used as recurrent operators.

3. Hadamard reservoirs

Hadamard reservoirs replace dense recurrent matrices with an exactly orthogonal composition of sign flips, routing, and a normalized Walsh-Hadamard transform. The same substitution supports standard and memristive-friendly models while enabling multiplier-free, scalable implementation.

  • Structured orthogonal recurrence: The proposed operator M = D2 bHN Π D1 combines random sign diagonals, a random permutation, and a normalized Walsh-Hadamard transform.Because its factors are orthogonal, M preserves norms exactly; the scaled recurrence ρM M has eigenvalues of modulus ρM.
  • Model definitions: The recurrent pipeline applies sign flips, fixed routing, and a fast Walsh-Hadamard transform instead of a dense analog matrix-vector product.This changes the recurrent computation to additions, subtractions, sign changes, and routing.
  • Model definitions: The H-ESN and MF-H-ESN substitute the scaled structured operator for dense recurrence while leaving the memristive neuron update unchanged.In the MF-H-ESN, the operator mixes the previous state before the potentiation-depression kinetics and leaky integration.
  • Hardware-oriented input: The simplified-input variant gives each unit one randomly chosen input connection with binary weight and binary bias, removing analog-valued parameters from the input path.Together with the structured recurrence, the design uses discrete patterns and global gains rather than floating-point input weights.
  • Computational cost: The fast Walsh-Hadamard transform reduces recurrent cost from O(N^2) to O(N log N) operations and storage from O(N^2) to O(N).The full matrix is never stored or materialized.
  • Physical implementation: The decomposition replaces dense analog conductances with structured interconnects and polarity-controlled summations, simplifying physical memristive implementation.The operator’s global scaling is handled by a single gain.

4. Computational cost and memory footprint

The structured recurrence reduces asymptotic computation and memory costs relative to dense coupling, while practical speedups depend on hardware and reservoir size. Its compact, mostly discrete representation substantially improves physical instantiability.

  • Computational cost: O(N log N) additions and subtractions replace O(N^2) dense multiply-accumulates in the recurrent step.
  • Wall-clock time: N ≈1024 is the crossover on the Apple M3 Pro CPU and NVIDIA T4, while the A100 crossover moves to N ≈8192.The crossover therefore depends on device throughput rather than operation count alone.
  • Wall-clock time: About 50× speedup is reached at N = 32768 on the Apple M3 Pro CPU and T4, whereas the A100 reaches 3.5× at N = 16384.Below the A100 crossover, the structured step remains within about ten percent of dense matmul because fixed per-call overhead dominates.
  • Memory footprint: At N = 8192, dense coupling requires 268 MB and 6.7 × 10^7 independently programmed analog values, compared with 15.4 kB for the structured operator.The structured representation uses 2N signs, N routing indices and one gain.
  • Memory footprint: The structured memory reduction reaches 1.7 × 10^4 at N = 8192 and grows essentially linearly with reservoir size.Global hyper-parameters such as the leaking rate are excluded because they do not grow with N.
  • Physical realization: The analog programmable values drop from N^2 for dense coupling to one gain, or to three global scalars with the simplified input pathway.The remaining components are discrete signs, routing indices and unit-gain butterfly connections.

5. Theoretical analysis

Exact orthogonality makes the structured reservoir’s stability analysis tight in recurrent scaling and supports predictable noise behavior. The same operator matches dense orthogonal memory while mixing the full state in one step, unlike the cycle reservoir.

  • Echo state property: If C < 1, the MF-H-ESN satisfies the echo state property.Orthogonality makes the recurrent contribution to the contraction bound exactly ρM and keeps contraction uniform in the input.
  • Echo state property: For the leaky-tanh H-ESN, any ρM < 1 guarantees the echo state property, while ρM > 1 is excluded by the necessary condition.This holds because tanh is 1-Lipschitz and the structured recurrence has norm ρM.
  • Echo state property: The sufficient MF-H-ESN bound guarantees the ESP only for ρM ≲0.09 under the illustrated parameters, although experiments remain stable across the explored hyper-parameter range.The authors attribute the conservativeness to a global Lipschitz bound dominated by an upper-end potentiation rate visited sporadically.
  • Spectral and memory properties: At ρ = 0.99, memory capacity is 148 for Hadamard, 151 for dense random orthogonal, and 45 for the dense random ESN.The ordering holds across ρ ∈[0.80, 0.99].
  • Mixing properties: The Hadamard operator reaches PR = N = 256 after one step, whereas the SCR preserves PR = 1 without spreading the impulse.Participation ratio measures the effective number of active units and is independent of ρ.
  • Overall interpretation: The Hadamard operator combines dense-orthogonal memory with dense-random one-step mixing while retaining structured multiplier-free hardware costs.The operator’s sign diagonals and permutation prevent the bare transform’s involutive, two-state behavior.
  • Noise response: Orthogonal recurrences have noise gain governed by ρ, while MF-model gain is essentially flat in ρM because neuron kinetics set state decay.

6. Experimental evaluation

Across classification and regression, Hadamard recurrences generally preserve the performance of dense reservoir counterparts while scaling competitively. Ablations and robustness tests clarify the distinct roles of operator components and the costs of runtime and permanent perturbations.

  • Fixed-size comparison: Hadamard variants attain the two best mean classification accuracies over twenty tasks and are best on eleven datasets at N = 256.The dense orthogonal baseline is best on one dataset, whereas the cycle reservoir collapses on Epilepsy.
  • Fixed-size comparison: Hadamard recurrences preserve standard and memristive-friendly reservoir performance across classification and regression, with simplified-input variants showing greater variability.MF-H-ESN matches or slightly improves MF-ESN on most datasets, while H-ESN remains close to conventional ESN.
  • Scaling with reservoir size: 3.1–4.2 accuracy points: every model improves by a comparable amount from N = 256 to N = 8192, while Hadamard variants remain competitive across sizes.A Hadamard model is best on twelve of twenty benchmarks at N = 256 and thirteen at N = 8192; MF-H-ESN is second-ranked at N = 8192.
  • Fixed-size comparison: Three of four Hadamard variants rank among the first three models and are statistically indistinguishable from dense baselines.The Nemenyi analysis separates the trained GRU from the four best-ranked reservoirs, while reservoir-model differences remain within one critical distance.
  • Operator ablation: The bare Hadamard transform collapses memory capacity to approximately 2 and effective rank to approximately 2, showing that randomization is indispensable.The full operator combines global mixing, permutation-based memory preservation, and sign-diagonal nonlinear diversity.
  • Operator ablation: At ρM = 0.95, removing the permutation lowers memory capacity from 198.1 ± 1.1 to 190.8 ± 4.4 and increases seed spread.At ρM = 0.99, memory capacity likewise falls from 247.9 ± 3.1 to 238.0 ± 8.1; sign diagonals do not affect memory curves.
  • Robustness: 0.3% state noise reduces short-task accuracy from about 0.92 to 0.50–0.72 in deployment, while 8-bit quantization costs at most 4.4 points with an on-device readout.At 20% mismatch, Hadamard models lose at most 2.3 points.

7. Discussion

The structured recurrence preserves key properties and benchmark accuracy while sharply reducing dense-coupling cost; versus the cycle reservoir, it trades modestly higher storage for global mixing and better rankings.

  • Dense references: The structured operator matches dense-coupling accuracy while replacing N^2 analog values with N log2 N additions and a tens-of-kilobytes description.At N = 8192, dense couplings require 268 MB, whereas the structured recurrence uses one programmed gain and tens of kilobytes.
  • Dense references: The best Hadamard variant ranks first among eight models on twenty classification benchmarks, while dense couplings rank behind it.
  • Dense references: The dense orthogonal reservoir remains the closest theoretical competitor, sharing exact orthogonality but requiring O(N^3) factorization and dense storage and application.
  • Cycle reference: The cycle reservoir remains cheaper, using N shifts per step and kilobytes, but requires N steps to spread a coordinate impulse through the state.
  • Cycle reference: The cycle ranks 5.1 on classification and 5.4 on regression, versus 3.4 and 3.7 for the simplified-input Hadamard models.
  • Implementation cost: At N = 8192, the recurrent operator stores fifteen bits per unit and 15.4 kB overall, while requiring N log2 N additions per step.

8. Conclusions

The paper concludes that Hadamard reservoirs offer dense-like accuracy and theoretical behavior with linear parameter storage and multiplier-free computation. Their global mixing and hardware-oriented robustness distinguish them from cycle reservoirs, while physical deployment and aging remain open.

  • Conclusions: Hadamard reservoirs use a multiplier-free structured orthogonal recurrence with O(N log N) operations, O(N) parameters, and no materialized matrix.
  • Conclusions: Across twenty classification and seven regression benchmarks up to N = 8192, they stay within one accuracy point of dense random orthogonal recurrences and outperform cycle reservoirs by a widening margin.
  • Conclusions: Permutation, sign diagonals, and the transform contribute differently: permutation protects edge-of-stability memory, sign diagonals protect nonlinear-state richness, and the bare transform is degenerate on both.
  • Conclusions: The structured step is about 50× faster than dense multiplication at N = 32768 on laptop CPUs and entry-level GPUs, with crossover near N ≈1024 there and N ≈8192 on an A100.
  • Conclusions: At N = 8192, the recurrent operator occupies 15.4 kB versus 268 MB for a dense counterpart.
  • Conclusions: Exact orthogonality makes the echo state condition tight, while simulations tolerate 20% mismatch, corrupted signs, or faulty routing at a cost of about two accuracy points.
  • Open directions: A physical memristive butterfly realization and aging study remain open, including how long a once-calibrated readout remains valid under analog drift.

Appendix A. Implementation of the structured recurrent step

The appendix compares three implementations of the structured recurrent step, differing mainly in how the Walsh-Hadamard butterfly stages are executed and fused.

  • Implementations: The pure TensorFlow FWHT executes log2 N butterfly stages as separate elementwise passes, launching log2 N kernels per step.
  • Implementations: The XLA implementation fuses the stages into a small number of specialized GPU kernels, while a third version uses a dedicated CUDA kernel.
  • Measurements: Tables A.1–A.3 report recurrent-step timing for the three platforms separately, with software and hardware versions specified in Appendix D.

Appendix B. Memory and parameter accounting

The appendix separates stored model description from trained parameters and counts digital storage, physical analog values, and recurrent-step operations. Structured recurrence sharply reduces recurrent storage, but input pathways and readouts can dominate complete models.

  • Accounting conventions: The accounting distinguishes what is stored from what is trained, counting the recurrent operator, input matrix, and bias while keeping the common readout separate.
  • Accounting conventions: Real-valued parameters count as 32 bits, signs as one bit, and coordinate and input indices as log2 N and ⌈log2 d⌉ bits.
  • Operation counts: A Walsh-Hadamard butterfly network requires N log2 N additions and no multiplications, versus N^2 multiply-accumulates for dense multiplication.
  • Timing: On an Apple M3 Pro CPU, structured implementations cross dense matmul near N ≈1024 with fusion and N ≈4096 without fusion.
  • Timing: On an NVIDIA A100, the crossover moves to N ≈8192 because the dense baseline is substantially faster than on a T4.
  • Accounting conventions: Global model scalars are omitted from stored totals but counted as analog values; simplified-input models use three analog values.
  • Memory footprint: At N = 8192, the H-ESN stores 80.9 kB, of which 15.4 kB is the operator and 65.5 kB is the real-valued input pathway and bias.
  • Memory footprint: On MindReading with d = 204 and N = 8192, the input matrix costs 6.7 MB in the dense pathway and 10 kB in the simplified one.

Appendix C. Proofs

Appendix C establishes forward invariance and a uniform contraction criterion for the memristive-friendly Hadamard dynamics, then records how exact orthogonality removes norm-estimation slack. It also shows that the full operator spreads a constant input direction across units rather than concentrating it.

  • Invariant set: Under γ ≤ 1 and εS+ ≤ γ, the state cube [0, H]^N is forward-invariant for MF-H-ESN dynamics under any input.The proof bounds the state-update coefficient componentwise and uses the model’s gain bound.
  • Echo state property: The echo state proof decomposes state differences into leak, state-dependent decay, and production terms before bounding their pre-activations.Input and bias contributions cancel when comparing trajectories driven by the same input.
  • Echo state property: Exact orthogonality makes the recurrent norm step an equality, removing the slack that would arise from a looser operator-norm bound.This is the point where the structured operator’s orthogonality enters the contraction proof.
  • Echo state property: If C < 1, the update map is a uniform contraction, yielding a unique state sequence independent of initial conditions with convergence rate C^t.The contraction is uniform in the input because C depends only on model constants and activation-range bounds.
  • Input degeneracy: The diagonal-free operator maps the constant direction onto one coordinate, whereas the full Hadamard operator spreads its energy across all units in expectation.For the full operator, the resulting coordinates have zero mean and unit variance because they are normalized sums of independent signs.

Appendix D. Experimental protocol: search spaces and baseline training

Appendix D describes a heterogeneous benchmark suite, randomized reservoir hyperparameter search, and training procedures for the GRU baseline. It also documents validation-based size selection and the learning-rate adjustment needed to avoid constant regression predictions.

  • Datasets: Twenty classification and seven regression tasks span 2–37 classes, 8–500 time steps, univariate to 963-dimensional inputs, and hundreds to tens of thousands of sequences.The datasets come from the UEA/UCR and Monash TSER archives and include sensor and biomedical recordings.
  • Execution protocol: Experiments use TensorFlow, with model evaluations on an NVIDIA A100 and timing measurements across Apple M3 Pro, NVIDIA T4, and NVIDIA A100 platforms.Timings are post-warm-up medians in single precision, advancing 256 states per call.
  • Reservoir search: The reservoir search samples 500 configurations over recurrent scaling, input and bias scales, leak, and memristive-model parameters, with ridge regularization from 10^-5 to 10^2.The MF models additionally search ε, γ, and s; physics-related constants are fixed from prior work.
  • GRU baseline: The GRU is trained with Adam for up to 500 epochs, using early stopping and three evaluation seeds after retraining the selected configuration.Hidden size is selected from 32, 64, 128, and 256; classification and regression use different learning-rate grids.
  • GRU baseline: Regression requires extending the GRU learning-rate grid above 10^-3 because lower rates converge to a constant predictor, while η = 10^-2 fits the training set to less than one hundredth of theThe supplied passage ends before the final quantity is stated.
  • Baseline comparison: Reservoir models use N = 256, while the GRU selects hidden size up to 256, matching state dimension in a comparison described as favoring the trained network.The critical-difference analysis also selects reservoir size and GRU hidden size on the same validation split.

Appendix E. Per-dataset scaling curves

Per-dataset scaling curves reveal substantial heterogeneity behind aggregate results. Classification accuracy often saturates before N = 8192, while regression error is usually flat across reservoir size and differences on Covid3Month are small.

  • Classification: Classification accuracy saturates well before N = 8192 on several benchmarks and degrades at the largest sizes on a few others.Model spreads are wider on harder tasks than aggregate averages suggest.
  • Classification: The spread between classification models is much wider on the hardest tasks than the average performance summaries indicate.The per-dataset curves expose variation hidden by aggregate reporting.
  • Regression: Regression error is essentially flat in reservoir size on most tasks, and Covid3Month spans less than 6% of the error across models.The narrow vertical range means apparent separations on Covid3Month are not meaningful.
Loading 2608.28295v1…