SCRAM: Spatially Coherent Randomized Attention Maps

Dan Andrei Calian, Peter Roelants, Jacques Calì, Ben Carr, Krishna Dubba, John E. Reid, Dell ZhangarXiv 2019 · OpenReview

Abstract

Attention mechanisms and non-local mean operations in general are key ingredients in many state-of-the-art deep learning techniques. In particular, the Transformer model based on multi-head self-attention has recently achieved great success in natural language processing and computer vision. However, the vanilla algorithm computing the Transformer of an image with $n$ pixels has $O(n^2)$ complexity, which is often painfully slow and sometimes prohibitively expensive for large-scale image data. In this paper, we propose a fast randomized algorithm — SCRAM — that only requires $O(n \log n)$ time to produce an image attention map. Such a dramatic acceleration is attributed to our insight that attention maps on real-world images usually exhibit (1) spatial coherence and (2) sparse structure. The central idea of SCRAM is to employ PatchMatch, a randomized correspondence algorithm, to quickly pinpoint the most compatible key (argmax) for each query first, and then exploit that knowledge to design a sparse approximation to non-local mean operations. Using the argmax (mode) to dynamically construct the sparse approximation distinguishes our algorithm from all of the existing sparse approximate methods and makes it very efficient. Moreover, SCRAM is a broadly applicable approximation to any non-local mean layer in contrast to some other sparse approximations that can only approximate self-attention.

Introduction

Transformers have revolutionized deep learning, but their core mechanism—multi-head self-attention—scales quadratically with the input sequence length. When applied to images, where the sequence length $n$ is the number of pixels, this becomes prohibitively expensive. Computing a full attention map for a high-resolution image requires comparing every single pixel to every other pixel.

Existing workarounds either restrict attention to fixed local windows, which loses global context, or use rigid, predefined sparse patterns. SCRAM (Spatially Coherent Randomized Attention Maps) addresses this by dynamically constructing sparse attention maps, reducing the complexity to $O(n \log n)$ without sacrificing the model's ability to capture global, long-range interactions.

The SCRAM Algorithm

The core innovation of SCRAM is adapting PatchMatch, a highly efficient randomized correspondence algorithm originally developed for computer graphics, to the neural attention mechanism. Instead of computing the full dot-product between all queries and keys, SCRAM uses PatchMatch to quickly pinpoint the most compatible keys for each query.

This approach relies on two fundamental assumptions about visual attention:

  1. Spatial coherence: Neighboring pixels (queries) tend to attend to similar areas in the key space.
  2. Sparse structure: A query's attention is usually concentrated in a few small local areas, rather than spread evenly across the whole image.
Figure 1: SCRAM leverages (a) spatial coherence and (b) sparse structure to efficiently approximate attention maps.

SCRAM introduces two variants for searching compatible keys:

  • top-$\kappa^{(\max)}$: Finds the absolute best matching keys regardless of location.
  • top-$\kappa^{(\text{mode})}$: Finds the best matching keys while enforcing spatial separation, ensuring the model captures multimodal attention distributions (e.g., attending to multiple distinct objects).

Once these best keys are found, SCRAM expands them into small local neighborhoods and computes a sparse softmax only over these specific regions. To ensure the approximation remains unbiased, the authors employ Monte Carlo estimators, specifically Self-Normalized Importance Sampling and Metropolis-Hastings.

Results and Performance

SCRAM demonstrates significant theoretical and empirical improvements over standard attention mechanisms:

  • Complexity: SCRAM reduces computational complexity from $O(n^2)$ to $O(n \log n)$, outperforming the $O(n\sqrt{n})$ complexity of the Sparse Transformer.
  • Empirical Scaling: In forward-pass inference tests on an RTX 2080 GPU, SCRAM demonstrated log-linear scaling. For a $256 \times 256$ image, SCRAM remained highly efficient (under 15ms), whereas full $O(n^2)$ attention typically exceeds memory or compute limits at such resolutions.
  • Qualitative Accuracy: Visualizations confirm that SCRAM’s sparse maps consistently capture the true peaks (maxima) of full dot-product attention maps, maintaining high fidelity to the original mechanism.

Conclusion and Future Work

While SCRAM presents a promising path for scaling Transformers to high-resolution imagery, it is currently in a preliminary stage. Future research will focus on evaluating the memory and time usage for the backward pass (gradient computation) and testing the algorithm on end-to-end training for tasks like image classification, object detection, and video recognition. Additionally, while optimized for visual data, the general principles of SCRAM may be extended to other modalities that exhibit similar coherence properties.

Summary updated

Abstract

Attention mechanisms and non-local mean operations in general are key ingredients in many state-of-the-art deep learning techniques. In particular, the Transformer model based on multi-head self-attention has recently achieved great success in natural language processing and computer vision. However, the vanilla algorithm computing the Transformer of an image with n pixels has O(n^2) complexity, which is often painfully slow and sometimes prohibitively expensive for large-scale image data. In this paper, we propose a fast randomized algorithm --- SCRAM --- that only requires O(n log(n)) time to produce an image attention map. Such a dramatic acceleration is attributed to our insight that attention maps on real-world images usually exhibit (1) spatial coherence and (2) sparse structure. The central idea of SCRAM is to employ PatchMatch, a randomized correspondence algorithm, to quickly pinpoint the most compatible key (argmax) for each query first, and then exploit that knowledge to design a sparse approximation to non-local mean operations. Using the argmax (mode) to dynamically construct the sparse approximation distinguishes our algorithm from all of the existing sparse approximate methods and makes it very efficient. Moreover, SCRAM is a broadly applicable approximation to any non-local mean layer in contrast to some other sparse approximations that can only approximate self-attention. Our preliminary experimental results suggest that SCRAM is indeed promising for speeding up or scaling up the computation of attention maps in the Transformer.
BibTeX
@misc{calian2019scram,
  author = {Dan Andrei Calian and Peter Roelants and Jacques Calì and Ben Carr and Krishna Dubba and John E. Reid and Dell Zhang},
  title = {{SCRAM: Spatially Coherent Randomized Attention Maps}},
  year = {2019},
  eprint = {1905.10308},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.10308},
}
Figure