How does the computation of Transformer self-attention grow with input sequence length n?

Answer: B. In proportion to n squared

In self-attention, each token's query is dotted with the keys of all tokens, producing an n × n table of weights. Computation, and the memory for that intermediate table if built naively, therefore scale with the square of sequence length. Doubling the length quadruples the attention part, so attention efficiency increasingly dominates performance for long contexts.

• A. Parts such as fully connected layers scale with n, but attention scales with n squared.
• B. Correct. Every pair of tokens is compared.
• C. It grows with length.