The expressivity ladder: what a parallel scan can and cannot track¶

The question this page answers¶

Every mixer in this library carries a small memory along a sequence and updates it once per token. What makes all of them train in a single parallel pass instead of step-by-step is one shared discipline: the update chosen at step \(t\) depends only on the input at step \(t\), never on the memory the recurrence has already accumulated. That discipline is not a detail. It is the entire reason these models are parallelizable, and it is also the source of a hard ceiling on what they can compute. This article explains why that ceiling exists, what each rung of the minGRU ladder buys against it, and, just as importantly, what each rung measurably cannot do.

For the constructor signatures, keyword arguments, and validation rules of the mixers named below, see Reference: mixers; this page links there rather than restating any signature. For the deepest rung's mechanism and backward-pass design, and for the delta-rule composer's own mechanism, see the Givens & Delta deep dive, which this page summarizes rather than repeats.

Why the discipline caps expressivity: the abelian ceiling¶

The base minGRU (Feng et al., arXiv:2410.01201) removes the hidden-state dependency from the GRU's gates, so the recurrence collapses to a first-order linear scan

with \(a_t\) and \(b_t\) functions of \(x_t\) alone. Because the per-step maps are fixed in advance of seeing any state, they can be composed in any grouping, which is exactly what an associative scan exploits: the log-space variant this library ships runs it through a Heinsen logcumsumexp scan (Heinsen, arXiv:2311.06281), constraining the transition to \(a_t \in (0,1)\) and hidden states to \((0, \infty)\).

Two structural facts follow, and both are representability walls, not optimization difficulties: no width and no depth removes them within a fixed parameterization. First, a transition in \((0,1)\) can only fade memory monotonically toward new input: an input-gated exponential moving average. Second, and deeper, a diagonal transition is a scalar multiplication, and scalars commute. The running product \(a_T \cdots a_1\) is therefore invariant to any reordering of the inputs. Any task whose answer changes when you reorder the inputs is out of reach at any width. This is the abelian ceiling: a commutative transition family cannot track a non-commutative process.

The circuit-complexity statement of the same fact is that fixed-depth stacks of input-dependent, state-independent linear transitions live in \(\mathrm{TC}^0\): the class of problems solvable by constant-depth parallel circuits, depth that does not grow with sequence length, which is exactly what a stack of parallel scans is (Merrill, Petty & Sabharwal, The Illusion of State in State-Space Models, arXiv:2404.08819). This places the whole family (including Mamba/S6 and GLA) below the unbounded state tracking a single nonlinear GRU layer can do. The "illusion of state" is precisely this: a scan appears to carry arbitrary state, but a constant-depth composition of commuting maps cannot realize the sequential dependence that genuine state tracking needs. The strictly-harder class \(\mathrm{NC}^1\) — needing depth logarithmic in input length, with complete problems like composing arbitrary permutations of five elements (\(S_5\)) — is the ceiling on this entire fixed-depth class, and no rung below lifts it.

The ladder: one lifted constraint per rung¶

Each variant answers one question (what is the per-step update allowed to do to the carried memory?), one step more generously than the rung below, and each answer lifts exactly one constraint while preserving the parallel scan.

Rung 1: memory that fades (MinGRU)¶

The base rung keeps a fraction of what it had and blends in some of what it just saw, with the fraction always in \((0,1)\). That is genuinely most of what "context" means in practice, but it can only fade. Asked whether it has seen an even or odd number of ones, an average carries no trace of even-versus-odd. Measured: chance at any depth, on both probe tasks. Base MinGRU sits at \(0.502\) accuracy at \(T=1024\) on parity (chance \(0.5\)) and \(0.171\) on \(S3\) (chance \(\approx 0.167\)), and \(L{=}4\) stacks match the \(L{=}1\) rows within noise (round base-mingru in experiments/lab_results.jsonl). This is the floor every other rung is measured against, and it is a parameterization failure, not a training one.

Rung 2: memory that flips (SignedMinGRU)¶

Let the transition go negative. Switching to a linear-space associative scan lifts the eigenvalue to \(a_t \in (-1, 1)\) and the state to unconstrained reals, so memory can flip sign and cancel rather than only decay. Even-versus-odd becomes trivial: flip on every one, hold on every zero, read the sign. This is the negative-eigenvalue mechanism of Grazzi et al. (arXiv:2411.12537) instantiated in the minGRU gate, motivated by Merrill, Petty & Sabharwal's observation that negative eigenvalues restore the per-layer parity and sign-alternation dynamics a positive-diagonal scan cannot represent at any width. The decoupled default \(a_t = \tanh(W_s x_t)\) holds \(0.994\) mean accuracy at \(16\times\) the training length on parity (n=6, worst seed \(0.984\)), against \(0.592\) for the legacy coupled form whose \(|a_t| \le 1 - z_t\) ceiling makes the eigenvalue \(-1\) cost two simultaneous saturations rather than one.

What this rung cannot do: it is still diagonal, still commutative. Parity is \(\mathbb{Z}_2\) (abelian) and a negative eigenvalue is enough for it; permutation composition, where order matters, remains out of reach at any width. SignedMinGRU can fit the order-sensitive \(S3\) task in-distribution (\(0.999\) at \(T=64\)) through a bounded-depth shortcut, but that shortcut decays with length (\(0.732\) at \(T=1024\), \(L{=}1\); depth does not rescue it, \(0.574\) at \(L{=}4\)), exactly where the abelian ceiling predicts a commuting family must fail. The separation between this rung and the next lives at length generalization, not training fit.

Rung 3: memory that turns (RotationMinGRU)¶

A flip is still multiplication by a number. To break commutativity, make the memory an arrow in a plane and each update a rotation or reflection of it: the per-block map \(M_t = R(\theta_t)\,\mathrm{diag}(1, \tanh u_t)\) ranges over \(O(2)\) and generates the dihedral group, which is non-abelian. Turn-then-flip lands somewhere different from flip-then-turn, so the arrow carries a running composition. Since \(D_3 \cong S_3\) (the smallest non-abelian group) embeds in \(O(2)\), one layer exactly represents the \(S3\) running-product automaton, a result unavailable to any commuting family at any width. Measured: \(0.958\) mean at \(T=1024\) (n=8), and in winning seeds the learned automaton is certifiable directly from the weights: the most homomorphic of the model's \(32\) transition blocks satisfies the \(D_3\) composition table to \(\approx 1.4\times10^{-4}\).

What this rung buys is representability of the solvable groups inside \(\mathrm{TC}^0\); it does not touch the \(\mathrm{NC}^1\) ceiling: \(S_5\) is still unreachable. And it comes with a sharp trainability caveat. Continuous rotation angles have no attractor at the group angles (a third of a turn is a measure-zero interior point), so angle error compounds with length. RotationMinGRU manufactures an attractor by snapping angles to an exact grid via a straight-through estimator, the rotation analogue of \(\tanh\)'s asymptote for the signed eigenvalue. But the exact automaton is reachable, not a stable training attractor: only \(1\) of \(8\) seeds lands it exactly, and the basin is measurably tiny (round hetero-loop-14-basin in experiments/EXPERIMENTS.md). The honest headline is a per-seed lottery averaged over its misses, which is why the shipped recipe pairs the variant with best-validation-at-\(T{=}128\) checkpoint selection and retry-on-flag.

Rung 3, enriched: reading structure before composing (GivensMinGRU)¶

GivensMinGRU occupies the same non-commutative rung with a richer per-token map: each transition is a product of Givens rotations across a block_size-dimensional block (default \(8\)D, three brick-wall rounds), continuous and exactly special-orthogonal, reaching all of \(SO(k)\) in the limit at the same \(64\)-element per-token state. It is emphatically not a fifth rung: an \(8\)D Givens product tracks the same solvable-group automata a \(2\)D rotation does, and both stay below the state-dependent-gate line. The brick-wall mesh is the standard EUNN construction (Jing et al., arXiv:1612.05231) on the interferometer mesh of Clements et al. (arXiv:1603.08788); what is specific here is the input-dependent per-token angles.

What the richer map buys is trainability, measured on the harder extract-then-compose task \(S3\text{-hier}\), where the group operation is hidden inside a pair of sub-tokens via a Latin square verified non-isotopic to both groups of order six, so extraction is genuine work that must precede composition. At matched \(64\)-element state and \(+2.2\%\) full-stack parameters, the \(8\)D Givens composer above a signed extractor fits \(8\) of \(12\) seeds against \(1\) of \(12\) for a continuous \(2\)D rotation composer (Fisher exact \(p \approx 0.009\)). A rounds ablation at fixed block size attributes the gap to the coupling that breaks within-block commutativity, not to block size: with rounds=1 (four disjoint, commuting planes) the composer fits \(0/12\), the single staggered coupling layer of rounds=2 recovers \(6/12\), and rounds=3 reaches \(8/12\) (round hetero-loop-19-rounds). This is the abelian ceiling appearing inside an \(8\)D block: a bigger block of commuting planes buys nothing; only the coupling that makes the planes not commute does. The full mechanism, the seed-0 provenance transfer to the shipped code path, and the backward-pass design are in the Givens & Delta deep dive.

Rung 4: memory that reads itself (a standard GRU)¶

A GRU breaks the shared discipline: it reads its memory before deciding how to change it. That buys genuinely sequential computation (one layer solves both probe tasks at \(1.000\) across every length tested), and it costs exactly the property this library exists to keep, since each step must wait for the one before it. It is the ceiling, not a rung you can climb to and stay parallel.

The trade-off framing: what each rung costs¶

The ladder is not "worse to better." It is a menu of what you can afford, and every rung above the floor is bought with something concrete.

• Parameters and heads. Signing adds a third linear head (\(z, h, s\)) over the base's two; rotation adds a fourth (\(z, h, \theta, u\)); Givens carries three (\(\theta, z, h\)). These matter for parameter-matched comparisons, but they are not where the cost concentrates: the Givens fit-rate advantage over \(2\)D rotation holds at only \(+2.2\%\) full-stack parameters, so it is not a capacity effect.
• Trainability. The higher rungs trade representability for a harder optimization. The rotation family's exact solution is reachable but not an attractor (\(1/8\) exact on \(S3\)), forcing the best-val@128 selection protocol and retries. The continuous Givens map fixes the reliability of finding a working composer (\(8/12\)) but, lacking any attractor, still leaves the exact solution off the table.
• Length generalization has no free attractor for continuous composers. Orthogonality buys norm preservation (no amplitude decay across hundreds of compositions), but continuity means nothing pins a learned angle to the group element it approximates, so small angle errors compound and accuracy still decays by \(T=1024\). The pooled \(\text{signed}\to\text{givens8}\) profile is \(0.949 / 0.885 / 0.787 / 0.613\) at \(T = 64/256/512/1024\). Exactness at length remains unique to the snapped \(2\)D composer's rare exact seed (\(0.983\) at \(T=1024\), the best figure measured on \(S3\text{-hier}\)); no continuous composer, Givens included, reaches it.
• The delta-rule composer, and the two-axis recommendation it earned. The DeltaProduct transition rule (Yang et al., arXiv:2406.06484; Siems et al., arXiv:2502.10297) is shipped in the package as DeltaMinGRU (mixer="delta"), whose forward runs the DeltaNet literature's chunked-WY parallel form rather than a sequential loop or an associative scan. Its per-token state is an independent capacity knob (n_heads, nh, d_k, d_v), not tied to d_model the way the rotation family's is, and both cost and memory stay nearly flat as that state grows (\(0.050\)s/\(419\) MiB at state \(64\) to \(0.077\)s/\(676\) MiB at state \(4096\), against Givens' \(0.984\)s/\(887\) MiB to \(70.6\)s/\(20.0\) GiB over the same range, experiments/bench/scaling_frontier.md). At its native, \(16\times\)-larger state it is now the most reliable composer measured on both hardware strata (CPU, pinned torch 2.5.1: \(12/12\) fits; GPU, torch 2.8.0+cu128: \(35/36\)), which is why it is the promoted default when per-token state is free to grow. At a state matched to Givens' \(64\) elements, GivensMinGRU is decisively more reliable (\(25/36\) against delta's \(10/36\) on the GPU stratum's larger sample, Fisher \(p = 0.00084\)), and the small-state fit cohorts of both mechanisms hold up better at \(16\times\)-length extrapolation than the large-state delta cohort (\(0.679\) givens / \(0.699\) delta@64 vs \(0.570\) delta@1024, fit-only). On GPU, per-seed training cost is parity across all three arms (\(\approx 15\)–\(18\)s). Givens' Triton scan path erases the CPU-side gap, and a hand-written Triton kernel was judged not worth building for delta since torch.compile already recovers \(70\)–\(91\%\) of its fusion headroom. The full mechanism and evidence, including why delta's low matched-state accuracy means are a fit-rate artifact and not a generalization deficit, are in the Givens & Delta deep dive.

Where this leaves the reader¶

The ladder is a map of what parallel training can afford: rungs 1–3 each lift one constraint (fade, then flip, then turn) while keeping the single-pass scan, and rung 4 buys the rest by paying with sequentiality. No parallel variant matches the GRU's exactness at length, and every number above is relative to a \(1600\)-step budget on the repository's own probe tasks, not a claim about natural-language or long-context modeling. The full multi-seed tables, the rounds ablation, and the delta-rule capacity disclosure are in experiments/TECHNICAL_REPORT.md; the round-by-round evidence is in experiments/EXPERIMENTS.md.

To go further: the Givens & Delta deep dive covers both composers' parameterization, the Givens backward pass, and the evidence that separates them; Reference: mixers has the signatures; How-to: choose a mixer turns this expressivity map into a per-task, two-axis decision; and Tutorials: two-layer stacks builds the signed-then-composer extract-then-compose stack the \(S3\text{-hier}\) evidence rests on.