# Linear Codes for Hyperdimensional Computing

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2024.

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

- [Distributed Representations Enable Robust Multi-Timescale Symbolic Computation in Neuromorphic Hardware](https://mlsanity.com/paper/2405.01305/) (2024)
- [Linearithmic Clean-up for Vector-Symbolic Key-Value Memory with Kroneker Rotation Products](https://mlsanity.com/paper/2506.15793/) (2025)
- [Bridging Silicon and the Hippocampus: Algebro-Deterministic Memory "VaCoAl" as a Substrate for Vector-HaSH and TEM](https://mlsanity.com/paper/2605.15652/) (2026)
- [Efficient Vector Symbolic Architectures from Histogram Recovery](https://mlsanity.com/paper/2511.01838/) (2025)

## Abstract (arXiv)

Hyperdimensional Computing (HDC) is an emerging computational paradigm for representing compositional information as high-dimensional vectors, and has a promising potential in applications ranging from machine learning to neuromorphic computing. One of the long-standing challenges in HDC is factoring a compositional representation to its constituent factors, also known as the recovery problem. In this paper we take a novel approach to solve the recovery problem, and propose the use of random linear codes. These codes are subspaces over the Boolean field, and are a well-studied topic in information theory with various applications in digital communication. We begin by showing that hyperdimensional encoding using random linear codes retains favorable properties of the prevalent (ordinary) random codes, and hence HD representations using the two methods have comparable information storage capabilities. We proceed to show that random linear codes offer a rich subcode structure that can be used to form key-value stores, which encapsulate most use cases of HDC. Most importantly, we show that under the framework we develop, random linear codes admit simple recovery algorithms to factor (either bundled or bound) compositional representations. The former relies on constructing certain linear equation systems over the Boolean field, the solution to which reduces the search space dramatically and strictly outperforms exhaustive search in many cases. The latter employs the subspace structure of these codes to achieve provably correct factorization. Both methods are strictly faster than the state-of-the-art resonator networks, often by an order of magnitude. We implemented our techniques in Python using a benchmark software library, and demonstrated promising experimental results.