Caracal: Noncommuting rotations in state-space models

State-space models (SSMs) combine parallel training with fixed-memory decoding, but diagonal transitions limit their state-tracking capacity: these models cannot solve ${\mathrm{NC}}^1$-complete problems. Non-diagonal transitions expand this capacity in models such as block-diagonal SLiCE and DeltaProduct, but dense block composition and repeated per-token updates increase training cost. The central design problem is to combine non-diagonal state transitions with the efficient parallel training of state-space duality (SSD). We resolve this tension with Caracal, a non-diagonal SSM whose noncommuting $\mathrm{SO}(3)$ rotations compose through quaternions. This structure yields SO3SSD, combining hard state tracking with SSD's efficiency. Caracal provably exceeds the state-tracking capacity of diagonal SSMs and solves the $A_5$ benchmark with a single layer. On finite-state automata, it achieves the highest mean accuracy among evaluated parallel models. We also obtain the lowest measured test perplexities in our language-model comparison, competitive zero-shot accuracy, and leading MAD compression and selective-copying results. Including control preparation, SO3SSD trains faster than every tested baseline at 512K tokens and batch one, outperforming the fastest by $1.44\times$ even when recurrent baselines use smaller states.