icl-ridge-step-requires-od2-hidden-space
IN premise — summaries/2026/08/24/akyurek-2023-icl-algorithm-s0-abstract.md
Created 2026-08-24T17:10:49+00:00
Theorem 2 in Akyurek et al. (2023) proves that a transformer with constant depth and O(d²) hidden size can compute one Sherman-Morrison rank-one update toward the ridge-regression solution, and N exemplars require O(n) layers.
Summary
A transformer can take one concrete step toward a ridge-regression solution in a single layer, provided its hidden dimension scales quadratically with the problem size, but stacking N examples in context requires N such layers. This sets a firm lower bound on how deep the network must be to handle more data, tying the in-context learning story directly to classical iterative linear algebra.