Google

The overall time complexity for the self-attention mechanism when generating a sequence of length $$len$$ with an $$L$$-layer Transformer is $$O(L \times len^2)$$. This quadratic complexity arises from summing the linear computational cost ($$O(i')$$) for each of the $$len$$ generation steps. The total complexity is then multiplied by $$L$$, as this entire process is repeated for each layer in the Transformer stack.

Time Complexity of Self-Attention in Autoregressive Generation

When an autoregressive model generates a sequence of text, the computational cost for the self-attention mechanism at each step is linear relative to the number of tokens already generated. However, the *total* computational cost for generating the entire sequence grows quadratically with the final sequence length. Explain precisely why this is the case, and how the number of layers in the model affects this total cost.

Derivation of Quadratic Complexity in Autoregressive Attention

A developer is profiling a text-generation model that uses a multi-layer Transformer architecture. They observe the following performance characteristics during autoregressive generation, where the time measured is dominated by the self-attention computations. Based on this data, identify the mathematical relationship between the generated sequence length and the computation time, and explain why this relationship occurs.

Performance Bottleneck in a Generative Model

During a single step of standard autoregressive generation, attending a position $$i'$$ to all previous context positions requires exactly $${}2 i'$$ vector products. This total is comprised of $$i'$$ products needed for the query-key dot product ($$\mathbf{q}_{i'} \mathbf{K}^{\mathrm{T}}$$), plus an additional $$i'$$ products to multiply the Softmax-normalized attention scores with the value matrix ($$\mathrm{Softmax}(\frac{\mathbf{q}_{i'} \mathbf{K}^{\mathrm{T}}}{\sqrt{d}}) \mathbf{V}$$).

Vector Products per Self-Attention Step

A team is optimizing a text-generation model where the computational cost is dominated by the self-attention mechanism during autoregressive decoding. They need to decide between two potential upgrades: 

1.  **Upgrade A:** Doubling the number of layers in the model while keeping the maximum sequence length the same. 
2.  **Upgrade B:** Doubling the maximum sequence length the model can handle while keeping the number of layers the same. 

Assuming the model generates a sequence that fills its m

Learn Before

Related