Efficient Vector Symbolic Architectures from Histogram Recovery

Researchers Zirui Deng and Netanel Raviv have published a paper introducing a novel approach to Vector Symbolic Architectures (VSAs), a family of techniques crucial for neurosymbolic AI. VSAs allow AI systems to create complex information structures by combining atomic vectors through operations called binding and superposition. The team's key innovation is using a concatenation of Reed-Solomon and Hadamard error-correcting codes to create a VSA with strong formal guarantees. This addresses a major limitation of previous random linear code approaches, which struggled with reliable information retrieval under noisy conditions.

Their method centers on solving a new computational problem they term 'histogram recovery.' Given a collection of histograms over a finite field, the system must find Reed-Solomon codewords whose symbol frequencies match those histograms. The researchers present an optimal solution using algorithms related to list-decoding, which significantly improves noise resilience. This results in a VSA that operates at improved parameters compared to similar solutions, offering efficient encoding, quasi-orthogonality (essential for neural processing), and reliable recovery—all without relying on heuristics or any model training. The work, accepted for ISIT 2026, bridges a critical gap between coding theory and practical AI system design.