# Recasting Self-Attention with Holographic Reduced Representations

arXiv: https://arxiv.org/abs/2305.19534 · HTML: https://mlsanity.com/paper/2305.19534/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 72 references that are in the map.
- First posted on arXiv 31 May 2023.

## Builds on (most cited first, 30 of 35)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers](https://mlsanity.com/paper/2110.13985/) (2021)
- [HiPPO: Recurrent Memory with Optimal Polynomial Projections](https://mlsanity.com/paper/2008.07669/) (2020)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [FNet: Mixing Tokens with Fourier Transforms](https://mlsanity.com/paper/2105.03824/) (2021)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [Synthesizer: Rethinking Self-Attention in Transformer Models](https://mlsanity.com/paper/2005.00743/) (2020)
- [Holographic Embeddings of Knowledge Graphs](https://mlsanity.com/paper/1510.04935/) (2015)
- [It's Raw! Audio Generation with State-Space Models](https://mlsanity.com/paper/2202.09729/) (2022)
- [EMBER: An Open Dataset for Training Static PE Malware Machine Learning Models](https://mlsanity.com/paper/1804.04637/) (2018)
- [Adaptive Attention Span in Transformers](https://mlsanity.com/paper/1905.07799/) (2019)
- [Malware Detection by Eating a Whole EXE](https://mlsanity.com/paper/1710.09435/) (2017)
- [Learning long-range spatial dependencies with horizontal gated-recurrent units](https://mlsanity.com/paper/1805.08315/) (2018)
- [H-Transformer-1D: Fast One-Dimensional Hierarchical Attention for Sequences](https://mlsanity.com/paper/2107.11906/) (2021)
- [Associative Long Short-Term Memory](https://mlsanity.com/paper/1602.03032/) (2016)
- [Self-Attentive Associative Memory](https://mlsanity.com/paper/2002.03519/) (2020)
- [Learning to Reason with Third-Order Tensor Products](https://mlsanity.com/paper/1811.12143/) (2018)
- [Learning with Holographic Reduced Representations](https://mlsanity.com/paper/2109.02157/) (2021)
- [Classifying Sequences of Extreme Length with Constant Memory Applied to Malware Detection](https://mlsanity.com/paper/2012.09390/) (2020)
- [KiloGrams: Very Large N-Grams for Malware Classification](https://mlsanity.com/paper/1908.00200/) (2019)
- [Scaling SVM and Least Absolute Deviations via Exact Data Reduction](https://mlsanity.com/paper/1310.7048/) (2013)

## Built on by (most cited first, 14 of 14)

- [MIMONets: Multiple-Input-Multiple-Output Neural Networks Exploiting Computation in Superposition](https://mlsanity.com/paper/2312.02829/) (2023)
- [Holographic Global Convolutional Networks for Long-Range Prediction Tasks in Malware Detection](https://mlsanity.com/paper/2403.17978/) (2024)
- [Towards Generalization in Subitizing with Neuro-Symbolic Loss using Holographic Reduced Representations](https://mlsanity.com/paper/2312.15310/) (2023)
- [A Walsh Hadamard Derived Linear Vector Symbolic Architecture](https://mlsanity.com/paper/2410.22669/) (2024)
- [Benchmarking Neural Decoding Backbones towards Enhanced On-edge iBCI Applications](https://mlsanity.com/paper/2406.06626/) (2024)
- [Linearithmic Clean-up for Vector-Symbolic Key-Value Memory with Kroneker Rotation Products](https://mlsanity.com/paper/2506.15793/) (2025)
- [Cybersecurity is the True Frontier for Generative AI Success or Failure](https://mlsanity.com/paper/2606.28929/) (2026)
- [Multi-label Learning with Random Circular Vectors](https://mlsanity.com/paper/2407.05656/) (2024)
- [FoGE: Fock Space inspired encoding for graph prompting](https://mlsanity.com/paper/2507.02937/) (2025)
- [Efficient Vector Symbolic Architectures from Histogram Recovery](https://mlsanity.com/paper/2511.01838/) (2025)
- [A Vector Symbolic Approach to Multiple Instance Learning](https://mlsanity.com/paper/2511.16795/) (2025)
- [Reinforcement Learning Enhancement Using Vector Semantic Representation and Symbolic Reasoning for Human-Centered Autonomous Emergency Braking](https://mlsanity.com/paper/2602.05079/) (2026)
- [Disentanglement with Holographic Reduced Representations](https://mlsanity.com/paper/2606.09725/) (2026)
- [Learning Holographic Reduced Representations with Clifford Variational Autoencoders](https://mlsanity.com/paper/2609.28409/) (2026)

## Abstract (arXiv)

In recent years, self-attention has become the dominant paradigm for sequence modeling in a variety of domains. However, in domains with very long sequence lengths the O(T2) memory and O(T2 H) compute costs can make using transformers infeasible. Motivated by problems in malware detection, where sequence lengths of T ≥ 100,000 are a roadblock to deep learning, we re-cast self-attention using the neuro-symbolic approach of Holographic Reduced Representations (HRR). In doing so we perform the same high-level strategy of the standard self-attention: a set of queries matching against a set of keys, and returning a weighted response of the values for each key. Implemented as a ``Hrrformer'' we obtain several benefits including O(T H log H) time complexity, O(T H) space complexity, and convergence in 10× fewer epochs. Nevertheless, the Hrrformer achieves near state-of-the-art accuracy on LRA benchmarks and we are able to learn with just a single layer. Combined, these benefits make our Hrrformer the first viable Transformer for such long malware classification sequences and up to 280× faster to train on the Long Range Arena benchmark. Code is available at urlhttps://github.com/NeuromorphicComputationResearchProgram/Hrrformer