A DEPTH–WIDTH SEPARATION FOR QUADRATIC IN-CONTEXT LEARNING WITHPROTECTED-LABEL BILINEAR TRANSFORMERS

Quadratic in-context regression has $\Theta (d^2)$ task coefficients for inputs in ${\mathbb{R}}^d$, although each prediction is a scalar. Can depth reduce the token width needed to predict these tasks? We study quadratic regression with Gaussian inputs using a bilinear Transformer whose attention can access labels but whose feed-forward maps cannot read or modify them. For one or two blocks at width $w=o(d^2)$, the minimum achievable relative risk converges to one, uniformly over context length. Three blocks suffice at width $2d+5$: an explicit network reaches relative risk at most $\epsilon$ with $O(d^2/\epsilon )$ context examples. Thus the minimum width for fixed relative risk below one falls from $\Theta (d^2)$ to $\Theta (d)$ between two and three blocks. The construction evaluates the quadratic projection-kernel estimator without storing all quadratic features. Attention applies a context-dependent matrix to the query, and a later block completes the prediction using $O(d)$-dimensional states. This shows that sequential computation through context can replace explicit storage of a quadratic feature representation.