Efficient Vector Symbolic Architectures from Histogram Recovery

• URL: http://arxiv.org/abs/2511.01838v1
• Date: Mon, 03 Nov 2025 18:45:47 GMT
• Title: Efficient Vector Symbolic Architectures from Histogram Recovery
• Authors: Zirui Deng, Netanel Raviv,
• Abstract summary: We present an optimal solution to the histogram recovery problem by using algorithms related to list-decoding, and analyze the resulting noise resilience.<n>Our results give noise-resilient VSA with formal guarantees regarding efficient encoding, quasi-orthogonality, recovery, without relying on any frequencies or training, and while operating at improved parameters relative to similar solutions such as the Hadamard code.
• Score: 7.075842071068846
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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. Recently, Raviv proposed the use of random linear codes in VSAs, suggesting that their subcode structure enables efficient binding, 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.

Related papers

• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• KodCode: A Diverse, Challenging, and Verifiable Synthetic Dataset for Coding [49.56049319037421]
  KodCode is a synthetic dataset that addresses the persistent challenge of acquiring high-quality, verifiable training data.<n>It comprises question-solution-test triplets that are systematically validated via a self-verification procedure.<n>This pipeline yields a large-scale, robust and diverse coding dataset.
  arXiv  Detail & Related papers  (2025-03-04T19:17:36Z)
• Improved Cleanup and Decoding of Fractional Power Encodings [0.20718016474717196]
  High-dimensional vectors have been proposed as a neural method for representing information in the brain using Vector Symbolic Algebras.<n>Previous work has explored decoding and cleaning up these vectors under the noise that arises during computation.<n>We present an iterative optimization method to decode and clean up Fourier Holographic Reduced Representation (FHRR) vectors.
  arXiv  Detail & Related papers  (2024-11-30T14:10:48Z)
• Linear Codes for Hyperdimensional Computing [9.7902367664742]
  We show that random linear codes offer a rich subcode structure that can be used to form key-value stores. We show that under the framework we develop, random linear codes admit simple recovery algorithms to factor (either bundled or bound) compositional representations.
  arXiv  Detail & Related papers  (2024-03-05T19:18:44Z)
• UGMAE: A Unified Framework for Graph Masked Autoencoders [67.75493040186859]
  We propose UGMAE, a unified framework for graph masked autoencoders. We first develop an adaptive feature mask generator to account for the unique significance of nodes. We then design a ranking-based structure reconstruction objective joint with feature reconstruction to capture holistic graph information.
  arXiv  Detail & Related papers  (2024-02-12T19:39:26Z)
• Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models [41.99844472131922]
  Decoding the original signal from the noisy observations is one of the main goals in nearly all HMM based data analyses.<n>We present QATS, a divide-and-conquer algorithm with computational polylogarithmic complexity in the length of the sequence, and cubic in the size of the state space.<n>An implementation of QATS is in the R-package QATS on GitHub.
  arXiv  Detail & Related papers  (2023-05-29T19:37:48Z)
• SC-VAE: Sparse Coding-based Variational Autoencoder with Learned ISTA [0.6770292596301478]
  We introduce a new VAE variant, termed sparse coding-based VAE with learned ISTA (SC-VAE), which integrates sparse coding within variational autoencoder framework. Experiments on two image datasets demonstrate that our model achieves improved image reconstruction results compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-03-29T13:18:33Z)
• Factorizers for Distributed Sparse Block Codes [45.29870215671697]
  We propose a fast and highly accurate method for factorizing distributed block codes (SBCs) Our iterative factorizer introduces a threshold-based nonlinear activation, conditional random sampling, and an $ell_infty$-based similarity metric. We demonstrate the feasibility of our method on four deep CNN architectures over CIFAR-100, ImageNet-1K, and RAVEN datasets.
  arXiv  Detail & Related papers  (2023-03-24T12:31:48Z)
• Efficient Generator of Mathematical Expressions for Symbolic Regression [0.0]
  We propose an approach to symbolic regression based on a novel variational autoencoder for generating hierarchical structures, HVAE. HVAE can be trained efficiently with small corpora of mathematical expressions and can accurately encode expressions into a smooth low-dimensional latent space. Finally, EDHiE system for symbolic regression, which applies an evolutionary algorithm to the latent space of HVAE, reconstructs equations from a standard symbolic regression benchmark better than a state-of-the-art system based on a similar combination of deep learning and evolutionary algorithms.
  arXiv  Detail & Related papers  (2023-02-20T10:40:29Z)
• Hierarchical Sketch Induction for Paraphrase Generation [79.87892048285819]
  We introduce Hierarchical Refinement Quantized Variational Autoencoders (HRQ-VAE), a method for learning decompositions of dense encodings. We use HRQ-VAE to encode the syntactic form of an input sentence as a path through the hierarchy, allowing us to more easily predict syntactic sketches at test time.
  arXiv  Detail & Related papers  (2022-03-07T15:28:36Z)
• Neural Distributed Source Coding [59.630059301226474]
  We present a framework for lossy DSC that is agnostic to the correlation structure and can scale to high dimensions. We evaluate our method on multiple datasets and show that our method can handle complex correlations and state-of-the-art PSNR.
  arXiv  Detail & Related papers  (2021-06-05T04:50:43Z)
• Closed Loop Neural-Symbolic Learning via Integrating Neural Perception, Grammar Parsing, and Symbolic Reasoning [134.77207192945053]
  Prior methods learn the neural-symbolic models using reinforcement learning approaches. We introduce the textbfgrammar model as a textitsymbolic prior to bridge neural perception and symbolic reasoning. We propose a novel textbfback-search algorithm which mimics the top-down human-like learning procedure to propagate the error.
  arXiv  Detail & Related papers  (2020-06-11T17:42:49Z)
• Single-Shot Decoding of Linear Rate LDPC Quantum Codes with High Performance [5.33024001730262]
  We construct and analyze a family of low-density parity check (LDPC) quantum codes with a linear encoding rate, scaling distance and efficient decoding schemes. The code family is based on tessellations of closed, four-dimensional, hyperbolic, as first suggested by Guth and Lubotzky.
  arXiv  Detail & Related papers  (2020-01-10T17:21:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.