# Graph-Certified Switching SSM

- ID: 949
- Canonical URL: https://synthcore.org/idea/949/graph-certified-switching-ssm
- API JSON: https://synthcore.org/api/idea/949.json
- API Markdown: https://synthcore.org/api/idea/949.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.15055](https://arxiv.org/abs/2607.15055)
- Category: dynamics
- Solves: stability, generalization, accuracy
- ML areas: ssm, rnn, training-dynamics, regularization
- Math tags: dynamical-systems, graph-theory, control-theory, linear-algebra, optimization
- Ratings: usefulness 7/10; difficulty 6/10; novelty 8/10

## Idea description

Turn a path-complete graph into a stability regularizer for a recurrent or state-space neural network whose update can switch among M learned operators. Maintain a neural quadratic or positive scalar certificate V_alpha for each graph node and penalize every graph edge that violates contraction under its corresponding operator. The resulting architecture is designed to remain stable even when the mode sequence is arbitrary rather than generated by a trained gate.

## Mathematical statement

The paper's construction associates functions V_alpha with nodes of a labeled graph G=(S,E) and requires inequalities along all labeled edges. For a recurrent update z^+=F_i(z), adapt the cost inequality to a contraction certificate by requiring V_alpha(z) >= rho^{-1}V_beta(F_i(z)) for every edge (alpha,beta,i), with 0<rho<1. Equivalently, V_beta(F_i(z))-rho V_alpha(z) <= 0. Here z is the recurrent hidden state, F_i is mode-i state transition, V_alpha(z)>=0 is a node-specific certificate, and rho is the desired per-step contraction factor. A reachability graph H over subsets A of graph nodes supplies a valid min-max envelope W(z)=min_A max_{alpha in A}V_alpha(z), with the paper's condition that every beta in a successor set B has a predecessor alpha in A carrying the same label i. For a simple and trainable certificate, use V_alpha(z)=z^T P_alpha z with P_alpha=L_alpha L_alpha^T+epsilon I, or a positive neural scalar V_alpha(z)=softplus(g_alpha(z))+epsilon||z||^2. The edge loss is the positive part of V_beta(F_i(z))-rho V_alpha(z).

## Key formulas

- $$V_{\alpha}(x)\geq c\bigl(x,\pi_A(x)\bigr)+V_{\beta}\bigl(f_i(x,\pi_A(x))\bigr),\quad (\alpha,\beta,i)\in\mathcal E.$$
- $$V_{\beta}\bigl(F_i(z)\bigr)-\rho V_{\alpha}(z)\leq 0,\qquad 0<\rho<1,\qquad (\alpha,\beta,i)\in\mathcal E.$$
- $$\mathcal{L}_{\mathrm{contract}}=\sum_{(\alpha,\beta,i)\in\mathcal E}\mathbb{E}_{z}\left[\operatorname{softplus}\left(\frac{V_{\beta}(F_i(z))-\rho V_{\alpha}(z)}{\tau}\right)\right].$$
- $$W(z)=\min_{A\in\mathcal S_{\mathcal H}}\max_{\alpha\in A}V_\alpha(z),\qquad \forall\beta\in B\ \exists\alpha\in A:(\alpha,\beta,i)\in\mathcal E.$$

## Implementation notes

1. Integration point: modify a gated recurrent model, diagonal SSM, or small recurrent core. Let z_t be the hidden state and let each mode i have its own update F_i(z_t,x_t), for example F_i(z,x)=tanh(A_i z+B_i x+b_i). The gate may choose modes from inputs, but training must evaluate all modes because deployment permits arbitrary switching. Add one certificate head V_alpha(z) for each graph node. Share the recurrent parameters or certificate trunk where possible; use quadratic certificates first because they are cheap and interpretable. 2. Pseudocode: for a batch of hidden states z, compute z_i=F_i(z,x) for all i; for each edge (alpha,beta,i), compute e=V_beta(z_i)-rho*V_alpha(z); accumulate softplus(e/tau); add lambda_contract times this loss to the task loss. Parameterize P_alpha=L_alpha L_alpha^T+epsilon I when using V_alpha(z)=z^T P_alpha z. Optionally choose the active envelope W(z)=min_A max_alpha V_alpha(z) as an auxiliary regularizer, but do not use hard argmin during backpropagation; use softmin temperature annealing. 3. The graph edge enumeration, positivity parameterization, and contraction target rho are known exactly. Empirical quantities are the hidden-state samples; for stronger evidence evaluate the maximum edge violation on held-out states and on long random mode sequences. For linear F_i and quadratic V_alpha, replace sampled training with semidefinite constraints P_alpha-rho A_i^T P_beta A_i >= 0 whenever the edge exists. 4. First experiment: compare a 1-layer switching SSM and an unconstrained GRU on permuted sequential MNIST or a synthetic long-memory sequence, with M=4 update operators and random mode switching at every time step. Match parameter count and train both at equal FLOPs. Track task accuracy, hidden-state norm over 10,000 unrolled steps, gradient norm, edge violation rate, and performance under unseen switching distributions. Success is no exploding hidden state, lower long-horizon gradient variance, and equal or better accuracy under adversarially chosen mode sequences.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built a graph-certified switching scalar SSM with quadratic certificate V(z)=z², all-mode self-edges, softplus contraction penalty, CUDA execution with fallback, and a reproducible mini-experiment. The mechanism checks passed: the observed contraction boundary was |a|=0.901 versus predicted sqrt(0.81)=0.900, worst-switching log norm matched the product prediction to numerical precision, and the quadratic violation slope was within 10.6% of the predicted boundary slope. In the tiny learning comparison, regularization reduced max mode magnitude from 0.495 to 0.391 and improved MSE negligibly (2.32133 to 2.32117); this is a stability signal, not a meaningful task-performance win.

### Mechanism check

- Verdict: Built a graph-certified switching scalar SSM with quadratic certificate V(z)=z², all-mode self-edges, softplus contraction penalty, CUDA execution with fallback, and a reproducible mini-experiment. The mechanism checks passed: the observed contraction boundary was |a|=0.901 versus predicted sqrt(0.81)=0.900, worst-switching log norm matched the product prediction to numerical precision, and the quadratic violation slope was within 10.6% of the predicted boundary slope. In the tiny learning comparison, regularization reduced max mode magnitude from 0.495 to 0.391 and improved MSE negligibly (2.32133 to 2.32117); this is a stability signal, not a meaningful task-performance win.
- Confidence: 8/10
- Limitations: Only a scalar linear recurrence and one-node graph were tested, rather than a multi-node reachability envelope or neural/quadratic matrix certificates. The task experiment was very small and both models learned stable modes, so long-horizon adversarial switching, accuracy generalization, parameter-matched GRU comparison, and statistically repeated runs were not tested.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.23195
- Paired wins: 3/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_experiment.py](https://synthcore.org/code/401/bench_experiment.py)
- [bench_report.json](https://synthcore.org/code/401/bench_report.json)
- [experiment.py](https://synthcore.org/code/401/experiment.py)
- [report.md](https://synthcore.org/code/401/report.md)
- [report_bench_2026-08-31T113157.md](https://synthcore.org/code/401/report_bench_2026-08-31T113157.md)
- [results.json](https://synthcore.org/code/401/results.json)
- [Download all files as ZIP](https://synthcore.org/download/401)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.