5.7.1 Krohn–Rhodes shortcuts and the identification gap

5.7.1 Krohn–Rhodes shortcuts and the identification gap

Liu et al. [ 2023 ] make the connection between Transformers and Krohn–Rhodes decomposition precise. Let \(\mathcal A=(Q,\Sigma ,\delta )\) be a finite semiautomaton. Reading a length \(T\) word normally appears to require the recurrent computation

A shallow Transformer can instead represent each symbol by the induced transformation \(\delta (-,\sigma _t):Q\to Q\) and compose these transformations hierarchically. This replaces temporal iteration by a parallel computation over the transition semigroup.

Their first result gives every finite semiautomaton an exact Transformer simulator of depth \(O(\log T)\) with resources polynomial in the sequence length and automaton size. Krohn–Rhodes theory identifies a broader constant-depth class. When every group appearing in the transition semigroup is solvable, the semiautomaton decomposes into reset memories and solvable group factors that admit constant-depth Transformer implementations in \(T\), although the dependence on \(|Q|\) may be large. Conversely, a constant-depth simulator for semiautomata containing non-solvable group structure would imply the unexpected circuit-complexity collapse \(\mathsf{TC}^{0}=\mathsf{NC}^{1}\). Thus prime algebraic structure predicts which recurrent computations possess shallow parallel shortcuts.

This result supplies a concrete mechanism for compositional performance. Attention can implement prefix aggregation and memory lookup; feedforward blocks implement transformations of the prime factors; residual connections carry information through their cascade. A Transformer need not store and update the visible automaton state in the manner of an RNN. It can reparameterize the global dynamics into a different but behaviorally equivalent computation.

The same result exposes the distinction central to ORACLE. The theorem is a simulation theorem: for a specified automaton and horizon, suitable Transformer parameters exist. It does not say that interaction identifies the transition semigroup, recovers a minimal Krohn–Rhodes cascade, or chooses the same factors under an equivalent presentation. The paper’s experiments show that gradient training can find shortcut solutions, but also that these solutions can be brittle under incomplete supervision, distribution shift, and extrapolation to unseen sequence lengths. Behavioral agreement on a training horizon therefore need not reveal a persistent compositional model.

This suggests a diagnostic program rather than an architectural verdict. Given a trained sequence model, probe for the reversible group factors, irreversible reset factors, and cascade dependencies predicted by the smallest observational automaton. Then change the presentation or extend the horizon and ask whether the same factors continue to explain behavior. A stable match would be evidence of categorical identification; a newly learned shortcut with the same input–output accuracy would witness performance without persistence.