Source-linked AI summary
A comparison of Vector Symbolic Architectures
Kenny Schlegel, Peer Neubert, Peter Protzel
TL;DR
VSAs offer multiple vector spaces and operator implementations, but evidence for choosing among them for particular tasks has been limited. The paper systematizes eleven implementations, classifies their binding operations, and evaluates them across synthetic and real applications. Its results expose trade-offs among exact binding, bundling capacity, and computational demands that can guide VSA selection.
Problem
Different VSA vector spaces and operator implementations have different properties, while the question of which VSA best suits a given task has received relatively little attention.
Method
The paper reviews and benchmarks eleven VSA implementations, introduces a binding-operation taxonomy, and evaluates bundling, unbinding, binding with bundling, and two practical applications.
Results
The comparison reveals trade-offs between exact binding and bundling capacity, while sparse binary BSDC performs well in bundling and VSA approaches can approximate SeqSLAM performance in visual place recognition.
Takeaways & Limitations
The taxonomy and experiments provide evidence for selecting an appropriate VSA for new applications and may support development of new architectures.
Takeaways & Limitations
Memory and computational demands were not evaluated in depth, and BSDC performance depends on the chosen sparsity.
Abstract
from arXiv · showhide
Vector Symbolic Architectures combine a high-dimensional vector space with a set of carefully designed operators in order to perform symbolic computations with large numerical vectors. Major goals are the exploitation of their representational power and ability to deal with fuzziness and ambiguity. Over the past years, several VSA implementations have been proposed. The available implementations differ in the underlying vector space and the particular implementations of the VSA operators. This paper provides an overview of eleven available VSA implementations and discusses their commonalities and differences in the underlying vector space and operators. We create a taxonomy of available binding operations and show an important ramification for non self-inverse binding operations using an example from analogical reasoning. A main contribution is the experimental comparison of the available implementations in order to evaluate (1) the capacity of bundles, (2) the approximation quality of non-exact unbinding operations, (3) the influence of combining binding and bundling operations on the query answering performance, and (4) the performance on two example applications: visual place- and language-recognition. We expect this comparison and systematization to be relevant for development of VSAs, and to support the selection of an appropriate VSA for a particular task. The implementations are available.
1 Introduction
VSAs use high-dimensional vectors and structured operators to perform symbolic computation while preserving graded similarity and tolerating fuzziness. This paper compares available implementations to help select a VSA for a task.
- 1 Introduction: VSAs combine a vector space with mathematical operations that encode, compose, and query symbolic representations using large numerical vectors.Atomic vectors can be assigned meanings, while operations determine the meanings of derived vectors.
- 1 Introduction: Redundant, distributed representations let VSAs store compositional structures while making individual representation errors less disruptive.The representation uses more dimensions than symbol discrimination alone requires.
- 1 Introduction: Binding creates role-filler structures, while unbinding can recover queried fillers even with noise, ambiguity, or related query vectors.The country example represents USA with role-filler pairs and retrieves Dollar using the currency role.
- 1 Introduction: Different vector spaces and operator implementations give rise to VSAs with different properties, making architecture selection for a task an underexplored question.The paper frames this selection problem as its central motivation.
- 1 Introduction: The paper benchmarks eleven VSA implementations, develops a binding-operator taxonomy, and compares bundling, unbinding, binding-bundling interference, and practical applications.The evaluation includes visual place recognition and language recognition on real-world data.
2 VSAs and their properties
VSAs share high-dimensional representations and core operators but differ in vector spaces, similarity measures, and binding implementations. These differences shape capacity, exactness, computational requirements, and analogical reasoning behavior.
- 2 VSAs and their properties: A VSA typically includes bundling, binding, unbinding, similarity, and permutation operators, but this comparison emphasizes differences among the first four components.Permutations are excluded because they work similarly across VSAs.
- 2 VSAs and their properties: Compared architectures use real, binary, sparse binary, or complex vector spaces, with vector-generation choices tied to their similarity metrics and operations.Examples include MAP-C in [−1, 1], normally distributed real vectors in HRR, MBAT, and VTB, and complex unit-circle vectors in FHRR.
- 2 VSAs and their properties: Similarity metrics decode noisy representations by finding related or nearest elementary vectors; compared choices include cosine similarity, complementary Hamming distance, and overlap.Cosine similarity is used by MAP-C, MAP-B, MAP-I, HRR, MBAT, and VTB, while binary architectures use metrics suited to density.
- 2 VSAs and their properties: Binding operations approximate tensor-product representations while preserving dimensionality, and the taxonomy distinguishes quasi-orthogonal from non-quasi-orthogonal bindings.Quasi-orthogonal bindings produce outputs dissimilar to their inputs; non-quasi-orthogonal bindings require additional computation to obtain that property.
- 2.5 Ramifications of non self-inverse binding: Self-inverse binding supports direct analogical reasoning, whereas non-self-inverse binding can answer the same query only by storing both country representations and using additional computation.The example asks for Mexico’s currency given the USA–Dollar relation and Mexico–Peso representation.
3 Experimental Comparison
The paper experimentally compares eleven VSA implementations across bundling capacity, approximate unbinding, and bundled-pair retrieval. Results show strong differences among representations and operators, with FHRR and sparse binary architectures often requiring fewer dimensions, while binding can substantially increase requirements for sparse binary VSAs.
- Evaluation setup: The evaluation compares required dimensions rather than physical memory or computation, because memory and effort per dimension vary substantially across VSAs.The authors identify a more comprehensive evaluation of memory and computational demands as future work.
- 3.1 Bundling Capacity: BSDC bundling shows a sharp transition from low to near-perfect accuracy, attributed to increased density without thinning; thinning broadens this transition range.The heat-maps encode accuracy across bundled-vector counts and dimensionalities, with FHRR and BSDC showing large near-perfect regions.
- 3.1 Bundling Capacity: FHRR and BSDC architectures achieve the most efficient bundling, requiring fewer dimensions for correct retrieval than dense binary representations.Dense binary spaces require the most dimensions, real-valued vectors somewhat fewer, and complex-valued vectors the fewest; sparse binary and FHRR perform best.
- 3.2 Performance of approximately invertible binding: VTB provides the highest similarity after approximate sequential unbinding, while MAP-C performs slightly worse than HRR.The comparison evaluates normalized similarity between the initial vector and the recovered vector across increasing sequence lengths.
- 3.3 Unbinding of bundled pairs: Binding and bundling impose the largest dimensionality increase on sparse binary VSAs, reaching up to 44%, whereas several dense and complex VSAs change only marginally.Segmental shifting increases requirements by 22%, less than shifting the whole sparse vector; FHRR has the best overall minimum-dimensional performance and increase.
- 3.3 Unbinding of bundled pairs: FHRR achieves the overall best minimum-dimensional performance for bundled pairs, while Gaussian continuous-space VSAs produce very similar results.The results also indicate that matrix binding does not significantly improve binding and unbinding for MBAT and VTB.
4 Practical Applications
The paper compares VSA implementations on language recognition and visual place recognition, using common-dimensionality experiments and real-world image data. Language recognition benefits from higher dimensions and selected bindings, while VSA-based place recognition can approximate SeqSLAM, with real-valued spaces performing especially well.
- 4.1 Language Recognition: The language experiment represents letters as hypervectors, binds position-permuted letters into 3-grams, bundles training n-grams by language, and classifies queries by nearest-neighbor comparison.The setup covers 21 languages and uses 3-grams; matrix-binding VSAs were evaluated on a reduced dataset because the current implementation required substantial learning time.
- 4.1 Language Recognition: Language-recognition accuracy generally increases with dimensionality, with MBAT, VTB, and FHRR reaching high accuracy at fewer dimensions than other architectures.VTB is considerably more effective than HRR's original circular-convolution binding, while FHRR approaches matrix-binding accuracy using element-wise binding.
- 4.2 Visual Place Recognition: Visual place recognition uses standardized AlexNet convolutional descriptors, random projections, VSA-specific encodings, and sequence length d = 5.The experiments use 4,096-dimensional vectors, except for sLSBH encodings, which use twice that number.
- 4.2 Visual Place Recognition: Encoding dense real-valued descriptors as sparse binary vectors causes approximately 22% performance loss, whereas HRR, VTB, and MBAT encodings do not affect performance.The loss is attributed mainly to comparing dense vectors with sparse binary vectors having only twice as many dimensions; increasing sparse-vector dimensionality improves encoding quality.
- 4.2 Visual Place Recognition: The VSA SeqSLAM approach binds neighboring image descriptors to fixed position vectors and bundles them before pairwise comparison, replacing SeqSLAM's costly similarity-matrix post-processing.This preprocessing preserves sequence information in each descriptor and makes the inner-loop averaging step unnecessary.
- 4.2 Visual Place Recognition: MAP-C achieves 100% AUC on Nordland, while VTB and MBAT produce results very similar to original SeqSLAM across the evaluated datasets.The VSA approaches generally approximate SeqSLAM with essentially the same AUC; MAP-C has no considerable AUC reduction on other datasets.
5 Summary and Conclusion
The evaluation reveals substantial diversity among VSAs and provides evidence for selecting architectures according to task requirements. It also identifies important trade-offs and scope boundaries for interpreting the comparisons.
- Self-inverse binding benefits analogical reasoning, but MAP-B and MAP-C trade exact binding against bundling capacity.Binary vector spaces support exact binding, whereas real-valued vectors provide higher bundling capacity.
- BSDC performed well in bundling capacity with relatively few dimensions, but binding substantially increased its dimensionality requirements.Adding thinning did not improve this result.
- Sparse VSAs performed less well in place recognition, although alternative encoding or more dimensions may improve them.The paper identifies these as plausible ways to improve sparse-VSA performance.
- The taxonomy and experiments expose broad VSA diversity and support architecture selection for new applications.The authors also position the findings as potentially useful for developing new VSAs.
- Resource-consumption comparisons remain limited because memory and computational costs per dimension vary across VSAs and hardware settings.The experiments used a common dimension count, while a deeper resource evaluation is left for future work.
- Permutation differences were not separately evaluated because permutations are applied similarly across VSAs, despite their importance.Simple permutations were nevertheless used in the language-recognition task.