Value-aware Approximate Attention

Ankit Gupta, Jonathan Berant

Abstract

Following the success of dot-product attention in Transformers, numerous approximations have been recently proposed to address its quadratic complexity with respect to the input length. However, all approximations thus far have ignored the contribution of the $\textit{value vectors}$ to the quality of approximation. In this work, we argue that research efforts should be directed towards approximating the true output of the attention sub-layer, which includes the value vectors. We propose a value-aware objective, and show theoretically and empirically that an optimal approximation of a value-aware objective substantially outperforms an optimal approximation that ignores values, in the context of language modeling. Moreover, we show that the choice of kernel function for computing attention similarity can substantially affect the quality of sparse approximations, where kernel functions that are less skewed are more affected by the value vectors.

Introduction

The standard Transformer architecture relies on "dot-product attention," which exhibits a quadratic complexity $O(L^2)$ relative to the input sequence length $L$. To mitigate this bottleneck for long sequences, researchers have developed various "efficient Transformers" utilizing sparse attention patterns or dense kernel-based approximations.

However, a major blind spot exists in current literature: almost all existing methods are value-oblivious. They attempt to identify the most "important" keys by looking solely at the similarity between Queries ($Q$) and Keys ($K$), ignoring the Values ($V$)—the actual information being aggregated. This paper argues that the true objective should be approximating the final output of the attention layer ($H = \text{softmax}(QK^T)V$), rather than just the intermediate similarity matrix.

Theoretical Framework

The authors compare two theoretical "oracle" approaches to sparse attention:

  1. Optimal-v-oblivious-r: Selects the $r$ keys with the highest attention scores (the standard approach in most sparse Transformers).
  2. Optimal-v-aware-r: Selects the $r$ keys that, when combined, result in an output closest to the true full-attention output.

Using Carathéodory’s Theorem, the authors prove that in a head with dimension $d$, one only needs $d+1$ value vectors to perfectly reconstruct the full attention output, regardless of sequence length. For a standard BERT-base model where $d=64$, this implies that only 65 specific keys are required for 100% accuracy. Current sparse models often use more than this but perform worse because they select keys based on the "Top-K" fallacy: a key with a high attention score may contribute less than a "weaker" key if its corresponding value vector has a small norm or is redundant.

Experimental Results

The claims were evaluated on Masked Language Modeling (MLM) using a RoBERTa-4096 model and Causal Language Modeling using a 6-layer Transformer on WikiText-103.

Comparison of MLM error across different selection strategies. The value-aware approach (orange) reaches the exact attention baseline significantly faster than value-oblivious or sliding-window methods.

Massive Performance Gap

In the RoBERTa-4096 MLM task, the "optimal-v-oblivious" approach with 65 keys resulted in an error of 43.5. In contrast, the "optimal-v-aware" approach with the same number of keys achieved an error of 24.2—matching the performance of full, exact attention. Standard "sliding window" attention, commonly used in models like Longformer, significantly underperformed compared to value-aware selection.

Kernel Sensitivity

The paper also investigates how different kernel functions (like ELU or polynomial kernels) affect approximation. As the field moves toward "Linear Transformers," the value-oblivious error worsens. Because these kernels do not "peak" as sharply as softmax, the influence of the value vectors' magnitudes becomes a dominant factor in the final output.

Evaluation loss for different kernel functions as a function of the number of keys $r$. Flatter kernels like ELU and polynomial show higher sensitivity to the selection method.

For the Causal LM task, using a degree-2 polynomial kernel with oblivious selection caused the perplexity to explode, whereas value-aware selection remained stable and accurate.

Conclusion and Future Work

The primary limitation of this study is that the "optimal-v-aware" selection used is an oracle; calculating the best $r$ keys currently requires computing the full attention matrix first. However, this work serves as a theoretical "call to arms," proving that a massive optimization gap exists. Future research should focus on developing practical, low-cost algorithms or lightweight heuristics to predict "value-important" keys before full attention computation, potentially marking the next frontier in efficient NLP.

Summary updated

Abstract

Following the success of dot-product attention in Transformers, numerous approximations have been recently proposed to address its quadratic complexity with respect to the input length. However, all approximations thus far have ignored the contribution of the $\textit{value vectors}$ to the quality of approximation. In this work, we argue that research efforts should be directed towards approximating the true output of the attention sub-layer, which includes the value vectors. We propose a value-aware objective, and show theoretically and empirically that an optimal approximation of a value-aware objective substantially outperforms an optimal approximation that ignores values, in the context of language modeling. Moreover, we show that the choice of kernel function for computing attention similarity can substantially affect the quality of sparse approximations, where kernel functions that are less skewed are more affected by the value vectors.
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