Analyze attention complexity and improvements
Company: Amazon
Role: Machine Learning Engineer
Category: Machine Learning
Difficulty: easy
Interview Round: Technical Screen
In the context of Transformer-style models, analyze the **computational complexity of self-attention**.
Assume a sequence length of \(n\) and hidden dimension \(d\).
- Derive the time and space complexity of standard scaled dot-product self-attention.
- Explain why this becomes a bottleneck for long sequences.
- Describe at least three classes of methods that reduce the complexity (e.g., sparse attention, low-rank or kernel-based approximations, chunking/segmenting), including their high-level ideas and trade-offs.
Quick Answer: This question evaluates understanding of Transformer self-attention in the Machine Learning domain, testing the ability to analyze time and space complexity, memory–computation trade-offs, and the role of approximation strategies for efficiency.
