# Capacity Analysis of Vector Symbolic Architectures

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 50 references that are in the map.
- First posted on arXiv 24 Jan 2023.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Dense Associative Memory for Pattern Recognition](https://mlsanity.com/paper/1606.01164/) (2016)
- [A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations](https://mlsanity.com/paper/2111.06077/) (2021)
- [A comparison of Vector Symbolic Architectures](https://mlsanity.com/paper/2001.11797/) (2020)
- [A Theoretical Perspective on Hyperdimensional Computing](https://mlsanity.com/paper/2010.07426/) (2020)
- [Variable Binding for Sparse Distributed Representations: Theory and Applications](https://mlsanity.com/paper/2009.06734/) (2020)
- [Neural Distributed Autoassociative Memories: A Survey](https://mlsanity.com/paper/1709.00848/) (2017)
- [HyperEmbed: Tradeoffs Between Resources and Performance in NLP Tasks with Hyperdimensional Computing enabled Embedding of n-gram Statistics](https://mlsanity.com/paper/2003.01821/) (2020)
- [Streaming Encoding Algorithms for Scalable Hyperdimensional Computing](https://mlsanity.com/paper/2209.09868/) (2022)

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

- [Distributed Representations Enable Robust Multi-Timescale Symbolic Computation in Neuromorphic Hardware](https://mlsanity.com/paper/2405.01305/) (2024)
- [HyperCam: Low-Power Onboard Computer Vision for IoT Cameras](https://mlsanity.com/paper/2501.10547/) (2025)
- [On Design Choices in Similarity-Preserving Sparse Randomized Embeddings](https://mlsanity.com/paper/2501.14741/) (2024)

## Abstract (arXiv)

Hyperdimensional computing (HDC) is a biologically-inspired framework which represents symbols with high-dimensional vectors, and uses vector operations to manipulate them. The ensemble of a particular vector space and a prescribed set of vector operations (including one addition-like for "bundling" and one outer-product-like for "binding") form a *vector symbolic architecture* (VSA). While VSAs have been employed in numerous applications and have been studied empirically, many theoretical questions about VSAs remain open. We analyze the *representation capacities* of four common VSAs: MAP-I, MAP-B, and two VSAs based on sparse binary vectors. "Representation capacity' here refers to bounds on the dimensions of the VSA vectors required to perform certain symbolic tasks, such as testing for set membership i ∈ S and estimating set intersection sizes |X cap Y| for two sets of symbols X and Y, to a given degree of accuracy. We also analyze the ability of a novel variant of a Hopfield network (a simple model of associative memory) to perform some of the same tasks that are typically asked of VSAs. In addition to providing new bounds on VSA capacities, our analyses establish and leverage connections between VSAs, "sketching" (dimensionality reduction) algorithms, and Bloom filters.