Linear Attention and Performer Kernels Quiz

Answers and explanations appear as you take the quiz.

1. Why does standard softmax attention scale poorly with sequence length?
   • Its time and memory grow with the square of the sequence length
   • It requires sorting all tokens alphabetically
   • It can only process one token at a time
   • It needs a separate neural network per token
2. What mathematical property lets linear attention avoid the n-by-n matrix?
   • Commutativity of addition
   • Associativity of matrix multiplication
   • The distributive law of softmax
   • Eigenvalue decomposition
3. What does Performer's FAVOR+ mechanism approximate?
   • Gradient descent updates
   • The tokenizer vocabulary
   • The softmax attention kernel
   • Layer normalization statistics
4. Why does Performer use positive random features rather than the earlier trigonometric ones?
   • They run faster on CPUs only
   • They eliminate the need for any randomness
   • They make the model fully interpretable
   • They guarantee non-negative attention weights and improve numerical stability
5. What is the approximate complexity of Performer-style linear attention in sequence length n?
   • O(n)
   • O(n^2)
   • O(n log n)
   • O(2^n)
6. What is a common limitation of pure linear attention compared to full softmax attention?
   • It cannot run on GPUs
   • It often achieves slightly lower modeling quality
   • It only works for images
   • It requires labeled data for every token
7. For attention written as phi(Q)(phi(K)^T V), which multiplication can be done first to avoid creating an n-by-n matrix?
   • Compute QK^T and store every pairwise score
   • Apply softmax to the full n-by-n matrix first
   • Compute phi(K)^T V before multiplying by phi(Q)
   • Multiply the final output by the sequence length
8. What benefit does using orthogonal random features provide in Performer’s FAVOR+ approximation?
   • It guarantees exact softmax for every sequence
   • It removes the need for query and key vectors
   • It makes attention quadratic in sequence length
   • It reduces variance in the random-feature estimate