Matching-Controllable Recurrent State Space

1. Integration point: use this as a structural design and initialization procedure for a linear recurrent layer, S4-like state-space layer, or residual RNN. Let the hidden update be \(h_{t+1}=Ah_t+Bu_t\), optionally followed by a nonlinear readout. Choose binary masks \(M_A,M_B\) before training; \(A=M_A\odot\Theta_A\) and \(B=M_B\odot\Theta_B\). 2. Pseudocode: build the directed graph from \(M_A,M_B\); run graph reachability from all input nodes; compute symbolic path products for \([B,AB,\ldots,A^{n-1}B]\) using Boolean matrix multiplication; construct the core pattern; run Hopcroft-Karp maximum matching on its row-column bipartite graph. Reject or repair the mask unless all hidden rows are matched. Initialize the matched entries with independent nonzero values, initialize remaining allowed edges with smaller random values, and optionally resample until the numerical controllability score is adequate. During training, periodically sample contexts \(\sigma_k\), form the local/Jacobian transition matrices \(A(\sigma_k)\), approximate \(W_T(\sigma_k)\) by discretized recursion, and add \(\lambda[-\log(\lambda_{\min}(\bar W_T)+\epsilon)]\) to the loss. 3. Computed exactly from the paper: accessibility, symbolic controllability-core construction, maximum matching, and the structural accept/reject test. Estimated empirically: Jacobians, finite-horizon Gramians, condition numbers, and averaged minimum eigenvalues. 4. First cheap experiment: compare a 64-dimensional tanh residual RNN on sequential MNIST or permuted sequential MNIST against the same parameter-count model with a random sparse mask, an accessible-but-unmatched mask, and a matching-controllable mask. Use four input channels and 20% transition sparsity. Measure validation accuracy, gradient propagation, \(\lambda_{\min}(\bar W_T)\), and the numerical rank of \(\bar W_T\) over 32 sampled input/context conditions. The quantitative prediction is a sharp structural boundary: masks failing accessibility or matching should yield rank-deficient Gramians and near-zero \(\lambda_{\min}\), whereas matching-controllable masks should have full rank for generic weights; after random initialization, the latter should show a substantially larger minimum eigenvalue and less degradation of input-to-hidden gradients at long horizons. A secondary prediction is that adding the Gramian penalty increases \(\lambda_{\min}(\bar W_T)\) monotonically until optimization becomes ill-conditioned, revealing a measurable tradeoff rather than an unconstrained benchmark effect.