pith. sign in

arxiv: 2511.01838 · v2 · submitted 2025-11-03 · 💻 cs.IT · cs.AI· cs.NE· math.IT

Efficient Vector Symbolic Architectures from Histogram Recovery

Zirui Deng , Netanel Raviv This is my paper

Pith reviewed 2026-05-18 01:02 UTC · model grok-4.3

classification 💻 cs.IT cs.AIcs.NEmath.IT
keywords vector symbolic architecturesReed-Solomon codesHadamard codeshistogram recoverylist decodingnoise resiliencecoding theorycompositional recovery
0
0 comments X

The pith

Concatenating Reed-Solomon and Hadamard codes reduces VSA recovery to an optimally solvable histogram recovery problem with formal noise guarantees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that vector symbolic architectures can be made more efficient and noise-resilient by using codewords from the concatenation of Reed-Solomon and Hadamard codes. These codewords preserve the quasi-orthogonality needed for binding and superposition operations in VSAs. The key innovation is showing that recovering the atomic vectors from a noisy composition is equivalent to solving a histogram recovery problem, which admits an optimal solution through list-decoding methods. This yields concrete improvements in parameters and formal guarantees compared to using Hadamard codes by themselves. A reader would care because it provides a principled way to design VSAs that work reliably in noisy environments without needing machine learning training.

Core claim

The paper claims that the concatenation of Reed-Solomon and Hadamard codes produces codewords that are mutually quasi-orthogonal and thus suitable for vector symbolic architectures. Compositional recovery then reduces to a histogram recovery problem over a finite field, which can be solved optimally using algorithms related to list-decoding. The resulting VSA has formal guarantees for efficient encoding, quasi-orthogonality, and recovery under noise, and achieves improved parameters relative to Hadamard codes alone.

What carries the argument

The histogram recovery problem: recovering a collection of Reed-Solomon codewords whose entry-wise symbol frequencies match given input histograms, solved using list-decoding techniques.

If this is right

  • The resulting VSA supports recovery of information objects from noisy compositional representations.
  • Encoding and recovery are efficient and come with proven noise-resilience bounds.
  • Parameters such as code length or noise tolerance improve over prior similar solutions based on Hadamard codes.
  • The approach avoids heuristics and training, relying solely on coding-theoretic constructions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This construction could extend to other concatenated codes to further optimize the trade-off between orthogonality and recoverability.
  • Hardware implementations of VSAs might benefit from the deterministic guarantees provided by this method.
  • Applying similar histogram-based recovery to other information representation schemes could lead to new neurosymbolic systems.

Load-bearing premise

The codewords from concatenating Reed-Solomon and Hadamard codes are mutually quasi-orthogonal and the optimal solution to histogram recovery transfers its noise analysis to the VSA recovery task.

What would settle it

Observing that the concatenated codewords do not maintain sufficient quasi-orthogonality for VSA operations, or finding that the list-decoding solution fails to recover under the noise levels predicted by the analysis.

Figures

Figures reproduced from arXiv: 2511.01838 by Netanel Raviv, Zirui Deng.

Figure 1
Figure 1. Figure 1: (Top) Bound on u vs d for different values of δ = K/N (noisy case). (Bottom) Bound on u vs δ = K/N for different values of d (noisy case). V. DISCUSSION In this paper it was shown how coding theoretic techniques give rise to a vector symbolic architecture which subsumes the struc￾tural benefits of linear codes [29]—including efficient encoding, storage, quasi-orthogonality, and binding recovery—in addition… view at source ↗
read the original abstract

Vector symbolic architectures (VSAs) are a family of information representation techniques which enable composition, i.e., creating complex information structures from atomic vectors via binding and superposition, and have recently found wide ranging applications in various neurosymbolic artificial intelligence (AI) systems and hardware systems. Recently, Raviv proposed the use of random linear codes in VSAs, suggesting that their subcode structure enables efficient unbinding, while preserving the quasi-orthogonality that is necessary for neural processing. Yet, random linear codes are difficult to decode under noise, which severely limits the resulting VSA's ability to support recovery, i.e., the retrieval of information objects and their attributes from a noisy compositional representation. In this work we bridge this gap by utilizing coding theoretic tools. First, we argue that the concatenation of Reed-Solomon and Hadamard codes is suitable for VSA, due to the mutual quasi-orthogonality of the resulting codewords (a folklore result). Second, we show that recovery of the resulting compositional representations can be done by solving a problem we call histogram recovery. In histogram recovery, a collection of $N$ histograms over a finite field is given as input, and one must find a collection of Reed-Solomon codewords of length $N$ whose entry-wise symbol frequencies obey those histograms. We present an optimal solution to the histogram recovery problem by using algorithms related to list-decoding, and analyze the resulting noise resilience. Our results give rise to a noise-resilient VSA with formal guarantees regarding efficient encoding, quasi-orthogonality, and recovery, without relying on any heuristics or training, and while operating at improved parameters relative to similar solutions such as the Hadamard code.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper proposes constructing Vector Symbolic Architectures (VSAs) using concatenated Reed-Solomon (outer) and Hadamard (inner) codes. It claims that the resulting codewords are mutually quasi-orthogonal (invoked as folklore), enabling composition via binding and superposition while preserving neural-style retrieval properties. Compositional recovery is reduced to an instance of a new 'histogram recovery' problem (recovering RS codewords whose entry-wise symbol frequencies match given histograms over a finite field), which is solved optimally via list-decoding techniques with a noise-resilience analysis. The construction is asserted to yield formal guarantees on efficient encoding, quasi-orthogonality, and recovery, with improved parameters relative to Hadamard codes alone and without heuristics or training.

Significance. If the quasi-orthogonality bound holds for the concrete parameters and the list-decoding noise analysis transfers to the VSA setting, the work supplies a theoretically grounded alternative to random linear codes or pure Hadamard VSAs, with explicit noise-resilience guarantees derived from standard coding primitives. The reduction to an optimally solvable histogram-recovery problem and the use of list decoding constitute a clean algorithmic contribution that could be reproduced from the stated primitives.

major comments (1)
  1. [Construction / quasi-orthogonality claim] Construction section (around the claim following the abstract's 'folklore result'): the mutual quasi-orthogonality of the RS-Hadamard concatenation is invoked without an explicit inner-product bound for the specific outer length N, field size q, and Hadamard dimension chosen for the VSA. The maximum absolute inner product between distinct codewords must be shown to be o(1) (or sufficiently small relative to the noise level) under these parameters; an asymptotic folklore statement does not automatically guarantee the separation needed for the histogram-recovery reduction to preserve the claimed noise resilience.
minor comments (2)
  1. [Abstract] Abstract: the reference to 'Raviv proposed the use of random linear codes' should include a citation number or arXiv identifier for traceability.
  2. [Histogram recovery formulation] The precise mapping from VSA binding/superposition operations to the histogram-recovery input should be stated with an equation or small example to make the reduction fully explicit.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback on our manuscript. We address the single major comment below and have revised the paper to incorporate an explicit quasi-orthogonality bound as suggested.

read point-by-point responses

  1. Referee: [Construction / quasi-orthogonality claim] Construction section (around the claim following the abstract's 'folklore result'): the mutual quasi-orthogonality of the RS-Hadamard concatenation is invoked without an explicit inner-product bound for the specific outer length N, field size q, and Hadamard dimension chosen for the VSA. The maximum absolute inner product between distinct codewords must be shown to be o(1) (or sufficiently small relative to the noise level) under these parameters; an asymptotic folklore statement does not automatically guarantee the separation needed for the histogram-recovery reduction to preserve the claimed noise resilience.

    Authors: We agree that an explicit inner-product bound for the concrete parameters is needed to make the argument fully self-contained and to rigorously support the noise-resilience claims. Although the quasi-orthogonality is a direct consequence of the minimum-distance properties of Reed-Solomon codes combined with the correlation properties of Hadamard codes, we have added a new lemma in the revised Construction section. The lemma derives the maximum absolute inner product explicitly for the chosen N, q, and Hadamard dimension, showing that it is O(1/sqrt(m)) (where m denotes the Hadamard length) and hence o(1) and sufficiently smaller than the noise levels analyzed in the histogram-recovery procedure. This confirms that the reduction to the histogram-recovery problem preserves the stated noise resilience. The revised text now cites this lemma rather than invoking the folklore result alone. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via new formulation and external coding results

full rationale

The paper's derivation introduces histogram recovery as a fresh reduction of VSA compositional recovery and solves it via list-decoding algorithms whose noise analysis is transferred to the VSA setting. Quasi-orthogonality of the RS-Hadamard concatenation is invoked only as an external folklore result, not derived from or defined in terms of the paper's own VSA performance metrics or fitted quantities. No step equates a claimed prediction to its inputs by construction, renames a fitted parameter as a prediction, or reduces the central claims to a self-citation chain that itself lacks independent verification. The overall argument therefore rests on independent coding-theoretic tools and the novel problem formulation rather than tautological re-labeling of its own assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard coding-theory background and one folklore orthogonality statement; no free parameters or new invented entities are introduced.

axioms (1)
  • domain assumption Concatenation of Reed-Solomon and Hadamard codes produces mutually quasi-orthogonal codewords.
    Invoked in the abstract as a folklore result that justifies suitability for VSA.

pith-pipeline@v0.9.0 · 5844 in / 1247 out tokens · 45196 ms · 2026-05-18T01:02:41.197953+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    M. M. Alam, E. Raff, S. Biderman, T. Oates, and J. Holt. Recasting self-attention with holographic reduced represen- tations. In:International Conference on Machine Learning. PMLR. 2023, pp. 490–507

    work page 2023

  2. [2]

    N. Alon, O. Goldreich, J. H ˚astad, and R. Peralta. Simple constructions of almost k-wise independent random vari- ables. In:Random Structures & Algorithms3.3 (1992), pp. 289–304

    work page 1992

  3. [3]

    Berlekamp, R

    E. Berlekamp, R. McEliece, and H. Van Tilborg. On the inherent intractability of certain coding problems (corresp.) In:IEEE Transactions on Information theory24.3 (1978), pp. 384–386

    work page 1978

  4. [4]

    J. S. Bowers, I. I. Vankov, M. F. Damian, and C. J. Davis. Neural networks learn highly selective representations in order to overcome the superposition catastrophe. In:Psy- chological review121.2 (2014), p. 248

    work page 2014

  5. [5]

    Chuang, C.-Y

    Y .-C. Chuang, C.-Y . Chang, and A.-Y . A. Wu. Dynamic hy- perdimensional computing for improving accuracy-energy efficiency trade-offs. In:2020 IEEE Workshop on Signal Processing Systems (SiPS). IEEE. 2020, pp. 1–5

    work page 2020

  6. [6]

    G. D. Forney. Concatenated codes. In: (1965)

    work page 1965

  7. [7]

    E. P. Frady, S. J. Kent, B. A. Olshausen, and F. T. Sommer. Resonator networks, 1: An efficient solution for factor- ing high-dimensional, distributed representations of data structures. In:Neural computation32.12 (2020), pp. 2311– 2331

    work page 2020

  8. [8]

    Ganesan, H

    A. Ganesan, H. Gao, S. Gandhi, E. Raff, T. Oates, J. Holt, and M. McLean. Learning with holographic reduced repre- sentations. In:Advances in neural information processing systems34 (2021), pp. 25606–25620

    work page 2021

  9. [9]

    R. W. Gayler. Multiplicative binding, representation oper- ators & analogy (workshop poster). In: (1998)

    work page 1998

  10. [10]

    Guruswami, A

    V . Guruswami, A. Rudra, and M. Sudan. Essential coding theory. In:URL https://cse. buffalo. edu/faculty/atri/courses/coding-theory/book(2018)

    work page 2018

  11. [11]

    Guruswami and M

    V . Guruswami and M. Sudan. Improved decoding of Reed- Solomon and algebraic-geometric codes. In:Proceedings 39th Annual Symposium on Foundations of Computer Sci- ence (Cat. No. 98CB36280). IEEE. 1998, pp. 28–37

    work page 1998

  12. [12]

    Hassan, M

    E. Hassan, M. Bettayeb, and B. Mohammad. Advancing hardware implementation of hyperdimensional computing for edge intelligence. In:2024 IEEE 6th International Conference on AI Circuits and Systems (AICAS). IEEE. 2024, pp. 169–173

    work page 2024

  13. [13]

    Hersche, M

    M. Hersche, M. Zeqiri, L. Benini, A. Sebastian, and A. Rahimi. A neuro-vector-symbolic architecture for solving Raven’s progressive matrices. In:Nature Machine Intelli- gence5.4 (2023), pp. 363–375

    work page 2023

  14. [14]

    Hiratani and H

    N. Hiratani and H. Sompolinsky. Optimal quadratic binding for relational reasoning in vector symbolic neural architec- tures. In:Neural Computation35.2 (2023), pp. 105–155

    work page 2023

  15. [15]

    Hoffstein

    J. Hoffstein. An introduction to cryptography. In:An In- troduction to Mathematical Cryptography. Springer, 2008, pp. 1–58

    work page 2008

  16. [16]

    Jensen, D

    D. Jensen, D. Danks, S. Elbaum, W. Regli, M. Turk, A. Wierman, H. Yanco, M. Lou-Maher, and H. Griffin. Envisioning Possible Futures for AI Research. https://cra. org/ccc/wp-content/uploads/sites/2/2025/07/Envisioning- Possible-Futures-for-AI-Research FINAL.pdf. [Accessed 31-10-2025]. 2025

    work page 2025

  17. [17]

    P. C. Kainen and V . Kurkov ´a. Quasiorthogonal dimension of Euclidean spaces. In:Applied mathematics letters6.3 (1993), pp. 7–10

    work page 1993

  18. [18]

    P. Kanerva. Computing with 10,000-bit words. In:2014 52nd annual Allerton conference on communication, con- trol, and computing (Allerton). IEEE. 2014, pp. 304–310

    work page 2014

  19. [19]

    Kautz and R

    W. Kautz and R. Singleton. Nonrandom binary superim- posed codes. In:IEEE Transactions on Information Theory 10.4 (1964), pp. 363–377

    work page 1964

  20. [20]

    S. J. Kent, E. P. Frady, F. T. Sommer, and B. A. Olshausen. Resonator networks, 2: Factorization performance and ca- pacity compared to optimization-based methods. In:Neural computation32.12 (2020), pp. 2332–2388

    work page 2020

  21. [21]

    Kleyko, D

    D. Kleyko, D. Rachkovskij, E. Osipov, and A. Rahimi. A survey on hyperdimensional computing aka vector sym- bolic architectures, part ii: Applications, cognitive models, and challenges. In:ACM Computing Surveys55.9 (2023), pp. 1–52

    work page 2023

  22. [22]

    Kleyko, D

    D. Kleyko, D. A. Rachkovskij, E. Osipov, and A. Rahimi. A survey on hyperdimensional computing aka vector sym- bolic architectures, part i: Models and data transformations. In:ACM Computing Surveys55.6 (2022), pp. 1–40

    work page 2022

  23. [23]

    Koetter and A

    R. Koetter and A. Vardy. Algebraic soft-decision decoding of Reed-Solomon codes. In:IEEE Transactions on Infor- mation Theory49.11 (2003), pp. 2809–2825

    work page 2003

  24. [24]

    C. J. Kymn, S. Mazelet, A. Ng, D. Kleyko, and B. A. Ol- shausen. Compositional factorization of visual scenes with convolutional sparse coding and resonator networks. In: 2024 Neuro Inspired Computational Elements Conference (NICE). IEEE. 2024, pp. 1–9

    work page 2024

  25. [25]

    R. Liu, Q. Qiu, S. Khan, and G. E. Katz. Linearith- mic Clean-up for Vector-Symbolic Key-Value Memory with Kroneker Rotation Products. In:arXiv preprint arXiv:2506.15793(2025)

    work page arXiv 2025

  26. [26]

    Morris, H

    J. Morris, H. W. Lui, K. Stewart, B. Khaleghi, A. Thomas, T. Marback, B. Aksanli, E. Neftci, and T. Rosing. Hy- perspike: hyperdimensional computing for more efficient and robust spiking neural networks. In:2022 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE. 2022, pp. 664–669

    work page 2022

  27. [27]

    T. A. Plate.Holographic Reduced Representation: Dis- tributed representation for cognitive structures. V ol. 150. CSLI Publications Stanford, 2003

    work page 2003

  28. [28]

    T. A. Plate. Holographic reduced representations. In:IEEE Transactions on Neural networks6.3 (1995), pp. 623–641

    work page 1995

  29. [29]

    N. Raviv. Linear Codes for Hyperdimensional Computing. In:Neural Computation36.6 (2024), pp. 1084–1120

    work page 2024

  30. [30]

    Schlegel, P

    K. Schlegel, P. Neubert, and P. Protzel. A comparison of vector symbolic architectures. In:Artificial Intelligence Review55.6 (2022), pp. 4523–4555

    work page 2022

  31. [31]

    A. Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. In:Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 2017, pp. 238–251

    work page 2017

  32. [32]

    Sidorenko and R

    V . Sidorenko and R. Fischer. Low-complexity list decoding of Reed-Solomon coded pulse position modulation. In: SCC 2013; 9th International ITG Conference on Systems, Communication and Coding. VDE. 2013, pp. 1–6

    work page 2013

  33. [33]

    Smolensky

    P. Smolensky. Tensor product variable binding and the rep- resentation of symbolic structures in connectionist systems. In:Artificial intelligence46.1-2 (1990), pp. 159–216

    work page 1990

  34. [34]

    Steinberg and H

    J. Steinberg and H. Sompolinsky. Associative memory of structured knowledge. In:Scientific Reports12.1 (2022), p. 21808

    work page 2022

  35. [35]

    Thomas, S

    A. Thomas, S. Dasgupta, and T. Rosing. A theoretical perspective on hyperdimensional computing. In:Journal of Artificial Intelligence Research72 (2021), pp. 215–249

    work page 2021

  36. [36]

    Verg ´es, M

    P. Verg ´es, M. Heddes, I. Nunes, D. Kleyko, T. Givargis, and A. Nicolau. Classification using hyperdimensional com- puting: A review with comparative analysis. In:Artificial Intelligence Review58.6 (2025), p. 173

    work page 2025

  37. [37]

    Online; accessed 13-10-2025

    Wikipedia contributors.Small-bias sample space. Online; accessed 13-10-2025. 2025.URL: https://en.wikipedia.org/ wiki/Small-bias sample space

    work page 2025

  38. [38]

    Q. Zhao, A. H. Thomas, A. Brin, X. Yu, and T. Rosing. Bridging the Gap Between Hyperdimensional Computing and Kernel Methods via the Nystr ¨om Method. In:Proceed- ings of the 39th AAAI Conference on Artificial Intelligence (AAAI-25). 2025

    work page 2025

  39. [39]

    Z. Zou, H. Alimohamadi, Y . Kim, M. H. Najafi, N. Srini- vasa, and M. Imani. EventHD: Robust and efficient hy- perdimensional learning with neuromorphic sensor. In: Frontiers in Neuroscience16 (2022), p. 858329

    work page 2022