Value-aware Approximate Attention

Ankit Gupta, Jonathan Berant

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.

Comparison of MLM error across different selection strategies as a function of the number of keys selected (r).

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.

Evaluation MLM error for various attention mechanisms, highlighting that value-aware selection (OVA) can match exact attention performance with far fewer keys.

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

BibTeX
@inproceedings{gupta2021value,
  author = {Ankit Gupta and Jonathan Berant},
  title = {{Value-aware Approximate Attention}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=VqyYt3aRyyH},
}
Figure