Abstract: Ankit Gupta, Jonathan Berant. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing.
2021.
Introduction
The standard dot-product attention mechanism is the engine of the Transformer architecture, yet its quadratic complexity ($O(L^2)$) relative to sequence length ($L$) remains a significant bottleneck for processing long-form content. To mitigate this, the research community has developed numerous "efficient Transformers" utilizing sparse attention or low-rank approximations. However, these methods typically focus on approximating the attention weights—the similarity between queries and keys—while ignoring the value vectors themselves. This paper argues that this "value-oblivious" approach is fundamentally sub-optimal.
The Value-Aware Paradigm
The primary goal of an attention layer is not merely to calculate weights, but to produce an output vector $H = \text{softmax}(QK^T)V$. Current sparse Transformers (like Longformer or Reformer) employ a value-oblivious selection strategy, choosing the $r$ keys with the highest attention weights. The authors propose a value-aware alternative: selecting the $r$ keys that minimize the error in the final output vector.
As shown in Figure 1, the ranking of "important" keys changes significantly when value vectors are considered. If a key has high similarity but its corresponding value vector is small or redundant, it may be less critical than a lower-scoring key with a highly significant value vector. Ignoring these dynamics can lead to an unbounded approximation error.
Kernel Sensitivity and Linear Transformers
The importance of value-awareness is amplified in modern "Linear Transformers" that replace the standard exponential (softmax) kernel with alternative functions like ELU or Polynomial kernels. Because these kernels often produce "flatter" attention distributions compared to the peaky nature of softmax, the influence of the value vectors becomes the deciding factor in preserving information. Theoretical analysis suggests that these alternative kernels are even more sensitive to value-oblivious errors.
Experimental Performance
The researchers evaluated these concepts using a RoBERTa-4096 model trained on a massive multi-domain corpus. The results demonstrate a stark performance gap between value-oblivious and value-aware selection.
In Masked Language Modeling (MLM) tasks, selecting the top 65 keys via a value-oblivious oracle (OVO-65) resulted in an error of 43.5%. In contrast, the value-aware oracle (OVA-65) achieved an error of 24.2%, effectively matching the performance of full, quadratic attention. Furthermore, existing methods like LSH Attention and Sliding Window consistently underperform compared to the value-aware benchmark, indicating substantial room for algorithmic improvement.
Conclusion
This research identifies a fundamental gap in efficient Transformer design: we have been approximating the proxy (weights) rather than the target (output). While the "Optimal-v-aware" method currently serves as an oracle—requiring full attention to compute—it establishes a theoretical ceiling for future efficiency research. The challenge for the field is now to develop $O(L \log L)$ algorithms, such as value-aware hashing or clustering, that can approximate the output vector directly without computing the full attention matrix.
Summary updated