Indexing: the Beginning and the End
The paper uses a simple indexing task to separate what several sequence architectures can and cannot compute in constant depth.
Kozachinskiy, Opazo, and Urrutia define “causal complexity” for masked architectures and prove that low-complexity models cannot solve indexing in a constant number of layers when the index comes at the end. The limitation covers low-parameter RNNs, state-space models, and masked linear-attention transformers, even with infinite-precision arithmetic. Softmax transformers solve that case in one layer, and non-masked linear attention in two. When the index comes first, small RNNs solve it in one layer, while the other architectures need two. ArXiv · AI/CL/LG's note
Kozachinskiy, Opazo, and Urrutia define “causal complexity” for masked architectures and prove that low-complexity models cannot solve indexing in a constant number of layers when the index comes at the end. The limitation covers low-parameter RNNs, state-space models, and masked linear-attention transformers, even with infinite-precision arithmetic. Softmax transformers solve that case in one layer, and non-masked linear attention in two. When the index comes first, small RNNs solve it in one layer, while the other architectures need two. ArXiv · AI/CL/LG's note
score 5