# The Rank the Task Demands: A Causal Rank Law for Matrix Memories Trained on Group Composition

arXiv: https://arxiv.org/abs/2609.12259 · HTML: https://mlsanity.com/paper/2609.12259/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 29 references that are in the map.
- First posted on arXiv 10 Sep 2026.

## Builds on (most cited first, 23 of 23)

- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [A Toy Model of Universality: Reverse Engineering How Networks Learn Group Operations](https://mlsanity.com/paper/2302.03025/) (2023)
- [Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues](https://mlsanity.com/paper/2411.12537/) (2024)
- [DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products](https://mlsanity.com/paper/2502.10297/) (2025)
- [Understanding Factual Recall in Transformers via Associative Memories](https://mlsanity.com/paper/2412.06538/) (2024)
- [Grokking Group Multiplication with Cosets](https://mlsanity.com/paper/2312.06581/) (2023)
- [Towards a unified and verified understanding of group-operation networks](https://mlsanity.com/paper/2410.07476/) (2024)
- [Sequential Group Composition: A Window into the Mechanics of Deep Learning](https://mlsanity.com/paper/2602.03655/) (2026)
- [The Expressive Limits of Diagonal SSMs for State-Tracking](https://mlsanity.com/paper/2603.01959/) (2026)
- [M2RNN: Non-Linear RNNs with Matrix-Valued States for Scalable Language Modeling](https://mlsanity.com/paper/2603.14360/) (2026)
- [On State Reduction in Linear Attention](https://mlsanity.com/paper/2602.04852/) (2026)
- [When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers](https://mlsanity.com/paper/2607.20594/) (2026)
- [Quantifying Memory Utilization with Effective State-Size](https://mlsanity.com/paper/2504.19561/) (2025)
- [Learning words in groups: fusion algebras, tensor ranks and grokking](https://mlsanity.com/paper/2509.06931/) (2025)
- [State Rank Dynamics in Linear Attention LLMs](https://mlsanity.com/paper/2602.02195/) (2026)
- [Sharp Capacity Thresholds in Linear Associative Memory: From Top-1 Retrieval to Tail-Average Learning](https://mlsanity.com/paper/2605.05189/) (2026)
- [Neural Networks Provably Learn Spectral Representations for Group Composition](https://mlsanity.com/paper/2606.02993/) (2026)
- [Spectral Entropy Collapse as a Phase Transition in Delayed Generalisation: An Interventional and Predictive Framework for Grokkin](https://mlsanity.com/paper/2604.13123/) (2026)
- [An Algebraic View of the Expressivity of Recurrent Language Models](https://mlsanity.com/paper/2606.01765/) (2026)
- [The Gradient Does Not See Rank: Rank-Indifference in Matrix-CODI on ProsQA](https://mlsanity.com/paper/2609.03090/) (2026)
- [How to Tame Grokking: Representation Geometry as a Control Signal](https://mlsanity.com/paper/2607.11666/) (2026)

## Built on by (most cited first, 1 of 1)

- [When the Gradient Sees Rank: Provable Necessity, Causal Recruitment, and Composition in Trained Matrix Memories](https://mlsanity.com/paper/2609.17594/) (2026)

## Abstract (arXiv)

Matrix-valued memories make rank the natural budget of a learned representation: the number of independent directions a state spans bounds what it can bind, compose, and track. We report causal evidence, on a group-composition testbed trained under a hard single-state bottleneck with a fixed decoder that cannot launder rank, that gradient descent recruits precisely the rank the task's algebra demands. A companion paper [Larson, 2026a] establishes the analogous recruitment and causal necessity pattern on a K-pair associative-binding testbed, where exact recovery provably requires state rank at least K; this paper inherits that instrument and extends the rank law from a scalar capacity bound to a representation-theoretic one. We train toward chosen minimal faithful reference representations embedded in larger matrices. On group-composition state tracking over five finite groups spanning the solvable/non-solvable divide, the recruited rank equals the group's minimal faithful real representation dimension dmin (Spearman ρ = 0.9747, the design's tie-capped maximum), the dimension-matched solvable/non-solvable pair S4/A5 is statistically equivalent under a pre-registered test, and a pre-registered force-rank test separates a guaranteed similarity ceiling from empirical recovery at the target dimension: one rank below dmin, cosine similarity is capped by the target's tied unit spectrum at √(dmin-1)/dmin ≤ 0.894, below the 0.9 threshold in every group by construction, with observed cells at 86-95% (mean 91%) of that ceiling; at dmin, not guaranteed a priori, recovery clears the pre-registered anchor-relative bar at four seeds per group in all five groups. Within this testbed, measured effective rank tracks representation dimension; the matched-dimension S4/A5 comparison establishes equivalence within the pre-registered tolerance.