Path-complete stable routed SSM

(1) Integration point: use a linear recurrent or state-space backbone inside a small language model or sequence model. Let the hidden state be \(h_t\in\mathbb R^n\), let a router choose mode \(i_t\in\{1,\ldots,M\}\), and update \(h_{t+1}=A_{i_t}h_t+B_{i_t}u_t\). Apply the certificate only to the homogeneous transition \(A_i h_t\); keep the input/output projections and nonlinear readout unconstrained. Initialize a graph with one node and edges labeled by every mode, or with a manually chosen small graph. (2) Pseudocode: repeat every K optimizer steps: collect current A[i]; solve min gamma subject to P[a] >= eps*I, trace(P[0])=n, gamma^2*P[a] - A[i].T@P[b]@A[i] >= 0 for every edge; compute slack[a,b,i] = lambda_min(gamma^2*P[a] - A[i].T@P[b]@A[i]); compute score[a] = sum_edges exp(-slack[a,b,i]/tau); if max(score) exceeds threshold, split the highest-score node v into clones indexed by its successor nodes, copy P[v] into every clone, redirect the local incoming and outgoing edges according to the lifted graph, and re-solve. During network training either project each \(A_i\) back into the feasible set after an optimizer step, or add a penalty \(\lambda\sum_e\|[A_i^\top P_bA_i-\gamma^2P_a]_+\|_F^2\) between exact SDP refreshes. (3) The SDP solver computes \(P_a\) and the smallest certified \(\gamma\); the eigenvalue slack and node scores are computed directly from the solved matrices. Estimate the empirical growth rate separately by running random and adversarial router sequences and measuring \(\|h_T\|/\|h_0\|\). If full-dimensional SDPs are too expensive, use state spaces of dimension 32 to 128, diagonal or low-rank-plus-diagonal \(P_a\), and refresh only every 500 to 2000 training steps. (4) First experiment: compare a one-layer routed SSM with shared quadratic \(P\), a fixed multi-node path-complete graph, and the adaptive lifting method on CIFAR-10 sequential pixels or the WikiText-2 language-modeling task. Use identical parameter counts and transition spectral-radius initialization. Measure maximum hidden-state norm over long random and adversarial routing sequences, certified \(\gamma\), validation loss, gradient-norm variance, and wall-clock overhead. A successful result is a substantially smaller certified \(\gamma\) or stable training at transition matrices whose common-\(P\) baseline is infeasible, with no validation-loss degradation and fewer graph nodes than a uniformly expanded history graph.