# Linearithmic Clean-up for Vector-Symbolic Key-Value Memory with Kroneker Rotation Products

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 18 Jun 2025.

## Builds on (most cited first, 10 of 10)

- [A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations](https://mlsanity.com/paper/2111.06077/) (2021)
- [A Theoretical Perspective on Hyperdimensional Computing](https://mlsanity.com/paper/2010.07426/) (2020)
- [Associative Long Short-Term Memory](https://mlsanity.com/paper/1602.03032/) (2016)
- [Vector Symbolic Architectures as a Computing Framework for Emerging Hardware](https://mlsanity.com/paper/2106.05268/) (2021)
- [Learning with Holographic Reduced Representations](https://mlsanity.com/paper/2109.02157/) (2021)
- [Understanding Hyperdimensional Computing for Parallel Single-Pass Learning](https://mlsanity.com/paper/2202.04805/) (2022)
- [Recasting Self-Attention with Holographic Reduced Representations](https://mlsanity.com/paper/2305.19534/) (2023)
- [Holographic Global Convolutional Networks for Long-Range Prediction Tasks in Malware Detection](https://mlsanity.com/paper/2403.17978/) (2024)
- [Linear Codes for Hyperdimensional Computing](https://mlsanity.com/paper/2403.03278/) (2024)
- [A Walsh Hadamard Derived Linear Vector Symbolic Architecture](https://mlsanity.com/paper/2410.22669/) (2024)

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

- [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)

## Abstract (arXiv)

A computational bottleneck in current Vector-Symbolic Architectures (VSAs) is the ``clean-up'' step, which decodes the noisy vectors retrieved from the architecture. Clean-up typically compares noisy vectors against a ``codebook'' of prototype vectors, incurring computational complexity that is quadratic or similar. We present a new codebook representation that supports efficient clean-up, based on Kroneker products of rotation-like matrices. The resulting clean-up time complexity is linearithmic, i.e. O(N,log,N), where N is the vector dimension and also the number of vectors in the codebook. Clean-up space complexity is O(N). Furthermore, the codebook is not stored explicitly in computer memory: It can be represented in O(log,N) space, and individual vectors in the codebook can be materialized in O(N) time and space. At the same time, asymptotic memory capacity remains comparable to standard approaches. Computer experiments confirm these results, demonstrating several orders of magnitude more scalability than baseline VSA techniques.