Compare a Transformer with an RNN for sequence modeling. Derive the time and memory complexity of computing self-attention scores for sequence length (n), key/query dimension (d_k), and model width (d). Discuss training parallelism, long-range dependencies, streaming inference, and when either architecture is preferable. ### Constraints & Assumptions - Analyze standard dense self-attention, not a sparse or linear-attention variant. - Separate projection cost from the (QK^\top) score matrix and value aggregation. - Distinguish training-time parallelism from autoregressive generation. ### Clarifying Questions to Ask - Is the comparison for an encoder, decoder, or encoder-decoder system? - Must inference be online with bounded memory? - How large are sequence length, model width, and batch size? - Is exact global attention required? ```hint Track matrix shapes With (Q,K\in\mathbb{R}^{n\times d_k}), the attention-score matrix has shape (n\times n). ``` ### What a Strong Answer Covers - (O(n^2d_k)) score computation and (O(n^2)) score storage per head. - Projection, value-aggregation, and full-layer costs where relevant. - RNN serial recurrence and its linear sequence-memory profile. - Parallel training, path length, long context, and streaming trade-offs. - Autoregressive caching and the limits of blanket complexity comparisons. ### Follow-up Questions - How does key-value caching change decoder generation cost per token? - What is the complexity of cross-attention with input lengths (n) and (m)? - When can a state-space or linear-attention model be preferable? - Why can an RNN still be attractive on a small streaming device?