A Walsh Hadamard Derived Linear Vector Symbolic Architecture
Authors: Mohammad Mahmudul Alam
Alexander Oberle
Edward Raff
Stella Biderman
Tim Oates
James Holt
Venue: NeurIPS 2024 poster (2024)
Keywords: Vector Symbolic Architectures
Holographic Reduced Representations
Hadamard Transformation
HRR
VTB
MAP
HLB
Primary area: deep_learning_architectures
TL;DR: Starting from the Hadamard transform we develop a simple method for neuro-symbolic manipulation of vectors that has desirable properties for deep learning.

Abstract: Vector Symbolic Architectures (VSAs) are one approach to developing Neuro-symbolic AI, where two vectors in $\mathbb{R}^d$ are 'bound' together to produce a new vector in the same space. VSAs support the commutativity and associativity of this binding operation, along with an inverse operation, allowing one to construct symbolic-style manipulations over real-valued vectors. Most VSAs were developed before deep learning and automatic differentiation became popular and instead focused on efficacy in hand-designed systems. In this work, we introduce the Hadamard-derived linear Binding (HLB), which is designed to have favorable computational efficiency, and efficacy in classic VSA tasks, and perform well in differentiable systems.

A Walsh Hadamard Derived Linear Vector Symbolic Architecture
Mohammad Mahmudul Alam', Allexnndrr Oberle'
Edward Raff :2, Stella Biderman', Tim Oates James Holt
University of Maryland, Baltimore County, 2 Booz Allen Hamilton, LLaboratory for Physical Sciences m256@umbc. edu, aoberlel @umbc. edu, _aff_Edward@ba... com, biderman_stell com, oates0es. umbc. holt@lps und edu
Abstract
Vector Symbolic Architectures (VSAs) are one approach to developing Neuro- symbolic AI, where two vectors in IR are 'bound' together to produce new vector in the same space. VSAs support the commutativity and associativity of this binding operation, along with inverse operation, allowing to construct symbolic- style manipulations over real real-valued vectors. Most VSAs were developed before deep learning and automatic differentiation became popular and instead focused on efficacy in hand-designed systems. In this work, we introduce the Hadamard- derived linear Binding (HIB), which is designed to have favorable computational efficiency, and efficacy in classic VSA tasks, and perform well in differentiable systems. Code available atttp:///ithii: com com//utuureeCompttnng4./11 Hadamard-deri Linear- Binding
Introduction
Vector Symbolic Architectures (VSAs) are unique approach to performing symbolic style AL Such methods use a binding operation B Idd Rdt Rd where B(x, = 2 denotes that two concepts/vectors: and y are connected to each other. In VSA, any arbitrary concept is assigned to vectors in Rd (usually randomly). For example, the sentence "the fat cat and happy dog" would be represented as Bffat, eat) + B (happyy, dog) S. One can then ask, "what was happy" by unbinding the vector for happy, which will return noisy version of the vector bound to happy. The unbinding operation is denoted 1 (xx y), and applying 8 (S, happy) z dog.
Because VSAs are applied over vectors, they offer an attractive platform for neuro-symbolie methods by having natural symbolic Al-style manipulations via differentiable operations. However, current VSA methods have largely been derived for classical AI tasks or cognitive science-inspired work. Many such VSAs have shown issues in numerical stability, computational complexity, or otherwise swwer-than-desired performance in the context of a differentiable system.
As noted (39 most VSAS can be viewed as a linear operation where B(a, b) - a TG and (a, b) = Fb, where and F are d x d matrices. Hypothetically, these matrices could be learned via gradient descent, but would not necessarily maintain the neuro-symbolic properties of VSAs without additional constraints. Still, the framework is useful as all popular VSAs we are aware fit within this framework. By choosing G and F with specified structure, computational complexity from (d2)) down to ((d) for a diagonal matrix.
change the
In this work, we derive a new VSA that has multiple desirable properties for both classical VSA tasks, and in deep-learning applications. Our method will have only O(d) complexity for the binding step, is numerically stable, and equals improves upon previous VSAs multiple recent deep
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

learning applications. Our new VSA is derived from the Walsh Hadamard transform, and so we term our method the Hadamard-derive linear Binding (HLB) as it will avoid the O log d) normally associated with the Hadamard transform, and has better performance than more expensive VSA alternatives.
Related work to our own will be reviewed in section 2 definitions. Our new HLB will be derived in section 3 showing it theoretically desirable properties. section 4 will empirically evaluate HLB in classical VSA benchmark tasks, and in two recent deep learning tasks, showing improved performance in each scenario. We then conclude in section 5
including our baseline VSAs and their
2 Related Work
Smolensky 38 started the VSA approach with the Tensor Product Representation (TPR), where d
dimensional vectors (each representing some concept) were bound by computing an outer product. Showing distributivity (B( æx + z) B(x,, y) + Bix, =)) and associativity, this allowed specifying logical statementss/truucturees [13. However, for p total items be bound together, it was impractical due to the (dd)) complexity. [36, 25, 24] have surveyed many of the VSAs available today, but our work will focus on three specific alternatives,
outlined in Table
The Vector-Derived
Transformation Binding (VTB) will be primary comparison because it is one of the most recently developed VSAs, which has shown improvements in what we will call "classic" tasks, where the VSA's symbolic like properties are used to manually construct a series of binding/unbinding operations that accomplish a desired task. Note, that the VTB unique in it is -on-symmetiic (B(x,,) y) * B( Ours, and most others, are symmetric.
Table I: The binding and initialization mechanisms for our new HLB with baseline methods. HLB is related to the HRR being derived via a similar approach, but replacing the Fourier transform F()) with the Hadamard transform (which simplifies out). The MAP is most similar to our approach in mechanics, but the difference in derived unbinding steps Ieads to dramatically different performance.
The VTB is the most recently developed VSA in modern use. The matrix V, of VTB is block- diagonal matrix composed from the values of the y vector, which we refer the reader to 12] for details. The TorchHD library [15] is used for implementations of prior methods.
METHOD
BIND B(x,U) v)
UNBIND B*t (1,9)
INIT I
HRR
F (Fx) O F(y))
(F @ F(y)) V x xO y
23 ~ 1/0, 3. N(0,
VTB
Vy
// 0/|1012
MAP-C
I O y
2; ~ 1(-1,1)
MAP-B
I T y
x 2 x + y
I, ~ 1-1,1]
HLB
x T
Fy ~ (W (M, 1/d))
Next is the Holographic Reduced Representation (HRR) 32), which can be defined via the Fourier transform F(-). One derives the inverse operation of the HRR by defining the one vector as the We will use a similar approach to deriving HLB but replacing the Fourier Transform with the Hadamard transform. making the HRR a key baseline. Last, the Multiply Add Permute (MAP) [00 is derived by taking only the diagonal of the tensor product from 38 s TPR. This results in a surprisingly simple representation of using element-we wise multiplication for both binding/unbinding, making it key baseline. The MAP binding is also notable for its continuous (MAP-C) and binary (MAP-B) forms, which will help elucidate the importance of the difference in our unbinding step compared to the initialization avoiding values near zero. HLB differs in devising for the unbinding step, and we will later show an additional corrective term that HLB employs for different items bound together, that dramatically improve performance.
identity vector and then solving F(a") F((a))F(())
Our motivation for using the Hadamard Transform comes from its parallels to the Fourier Transform (FT) used to derive the HRR and the HRR's 's relatively high performance. The Hadamard matrix has a simple recursive structure, making analysis tractable, and its transpose is its own inverse, which simplifies the design of the inverse function B* Like the FT, WHT can be computed log-linear time, though in our case, the derivation results in linear complexity as an added benefit. The WHT is already associative and distributive, making less work to obtain the desired properties. Finally, the WHT involves only (-1,1) values, avoiding numerical instability that can occur with the HRR/FT.
2

---

This work shows that these motivations are well founded, as they result in binding with comparable or improved performance in our testing.
Our interest in VSAs comes from their utility in both classical symbolic tasks and as useful priors in designing deep learning systems. In classic tasks VSAs popular for designing power-efficient
systems from a finite set of operations [4 23
[7]
30). HRRs, in particular, have shown biologically
plausible models of human cognition 21 5
40
6 and solving cognitive science tasks [8]
In deep
learning the TPR has inspired many prior works in natural language processing 34
16
35
To wit,
The HRR operation has seen the most use in differentiable systems
28
To
study our method, we select two recent works that make heavy use of the neuro- peuro-symbolic capabiliites of HRRs. First, an Extreme tens to hundreds of thousands of classes C' in a smaller dimension d < C [9] and an information privacy task that uses the HRR binding as a kind of "encrypt/decrypt" mechanism for heuristic security 3 We will explain these methods in more detail in the experimental section.
(XML) task that uses HRRs represent an output space of
3
Methodology
First, we will briefly review the definition of the Hadamard matrix H and its important properties that make it strong candidate from which derive VSA. With these properties established, will begin by deriving a VSA we term HIB where binding and unbinding are the same operation in the same manner as which the original HRR can be derived [32] Any VSA must introduce noise when vectors are bound together, and we will derive the form of the noise term as 17". Unsatisfied with the magnitude of this term, we then define projection step for the Hadamard matrix in similar spirit to 'I''s is complex-unit magnitude projection to support the HRR and derive an improved operation with a new and smaller noise term 17 This will give us the HLB bind/unbind steps as noted Table
Hadamard H. is a square matrix of size d x of orthogonal rows consisting of only +1 and - 1s given in Equation where d 2n E N n > 0. Bearing in mind that Hadamard or Hadamard Transformation (WHT) can be equivalent to discrete multi-dimennional Fourier Transform (FT) when applied to d dimensional vector [26), it has additional advantages over Discrete Fourier Transform (DFT). Unlike DFT, which operates on complex C numbers and requires irrational multiplications, WHT only performs calculations on real I numbers with addition and subtraction operators and does not require any irrational multiplication.
1
Hgn lgg--1
Hgn
H [1]
H₂ =
Hnn
- -gg--1
Vector symbolic architectures (VSA), for instance, Holographic Reduced Representations (HRR) em- ploys circular convolution to represent compositional structure which is computed using Fast Fourier Transform (FFT) [32]. However, it can be numerically unstable due to irrational multiplications of complex numbers. Prior work 9 devised a projection step to mitigate the numerical instability of the FFT and it's inverse, but we instead ask if re-deriving the binding/unbinding operations may yield favorable results if we use the favorable properties of the Hadamard transform as given in Lemma 3.1
Lemma 3.1 (Hadamard Properties). Let H be the Hadamard matrix of size d d that holds the following properties for x, IR., First, H (Hr) = dr, and second H + y) = Hr + Hy.
The bound composition of two vectors into a single vector space is referred to as BINDING. The knowledge retrieval from a bound representation is known as UNBINDING. We define the binding function by replacing the Fourier transform in circular convolution with the Hadamard transform given in Definition 3.1 We will denote the binding function four specific method by B and the unbinding function by B*
Definition 3.1 (Binding and Unbinding). The binding of vectors x. y E Rd in Hadamard domain is defined in Equation 2 where is the elementwise multiplication. The unbinding function is defined in similar fashion, i.c., B = B* In the context of binding, B(x, y) combines the vectors x and whereas in the context of unbinding 8* (z, y) refers to the retrieval of the vector associated with y from x.
1 d
B(x,y) v)
H(H Hy)
(2)
3

---

Now, we will discuss the binding of different representations, which will become important later in our analysis but is discussed here for adjacency to the binding definition. Composite representation in vector symbolic architectures is defined by the summation of the bound vectors. We define parameter p E N > that denotes the number of vector pairs bundled in a composite representation. Given p. we can define the composite representation x as
vectors 4 U/ E Rd and V ie N:
Xp Σ
X p=1
X = (( + ((22, 9/2
Ba Ui)
(3)
Next, we require the unbinding operation, which defined via an inverse function via the following theorem. This will give a symbolic form of our unbinding step that retrieves the original component being searched for, as well necessary noise component 77, which must exist whenever p items are bound together without expanding the dimension d.
Theorem 3.1 (Inverse Theorem). Given the identity function Hx. Hx
where x² is the inverse
x2 + n
if p = 1 else > 1
of x in Hadamard domain, then B* (B(z), 11))) + ... + B(x Up).
where Fi. Vr I2 and ni is the noise componens.
Proof of Theorem 3.7] We start from the identity function Hx Hxt 1 and thus Hat using Equation we get,
H= Now
1 H[(HH O Hyn .... Hx, C Hy)) O Hy: B (B((), + ....4 Blxr Mp), w.
1 H(H Hys
HHx O Hy,)) Is + H
Hay + Hy,))
Lemana 3.1
d
Hy:
[ [ + m
P= = clse p > 1
To reduce the noise component and improve the retrieval accuracy, (9 32 proposes projection step to the input vectors by normalizing them by the absolute value in the Fourier domain. While such identical normalization not useful in the Hadamard domain since will only transform the elements to +1 and lss we will define projection step with only the Hadamard transformation without normalization given in Definition 3.2
Definition 3.2 (Projection). The projection function of æ is defined by x(x) 1 Hr.
If we apply the Definition 3.2 to the inputs in Theorem 3.1 then we get
2, up), 1 y1
8 (B((((())) BB( ((,T(,,,, (v,)*) 8 H
On
1 H L ā 1/4
t, O yp))
The retrieved value would be projected onto the Hadamard domain as well and to get back the original data we apply the reverse projection. Since the inverse of the Hadamard matrix is the Hadamard matrix itself, in the reverse projection step we just apply the Hadamard transformation again which derives the output to
H
11
... Up))
(x) On
+ xp 3 Up)
1/1
y1
x2
if
p
(5)
r xz
if p= else p > 1
34
#39; 20
else p >>1
where v/. is the noise component due the projection step. expectation, 1/ < n (see Appenddi A). Thus, the projection step diminishes the accumulated noise. More interestingly, the retrieved output

---

term does not contain any Hadamard matrix. Therefore, we can recast the initial binding definition by multiplying the query vector y to the output of of[Equation 5] which makes the binding function as the sum of the slement-wise product of the vector pairs and the compositional structure linear time ((n) representation. Thus, the redefinition of the binding function is (1x,, y) x O y and p bundle of the vector pairs is X = - (2, O v.). Consequently, the unbinding would be a simple element- wise division of the bound representation by the query vector, i.e, B (ar, v) x where and y are the bound and query vector, respectively.
3.1 Initialization of HLBB
For the binding and unbinding operations to work, vectors need to have an expected value of zero. However, since we would divide the bound vector with query during unbinding, values close to zero would destabilize the noise component and create numerical instability. Thus, we define a Mixture of Normal Distribution (MiND) with expected value of zero but an absolute mean greater than zero given in Equation where // is the Uniform distribution. Considering half of the elements are sampled for a normal distribution of mean -μ and the rest of the half with mean of μu, the resulting vector has a zero mean with an absolute mean of p. The properties of the vectors sampled from MiND distribution are given in Properties 3.1]
l(p 1/d) = [N((H,, 1/d) (N( μr, 1/d)
if u(0, > 0.5
else (1, < 0.5
Properties 3.1 (Initialization Properties). Let x Bd sampled from from Siy,, 1/d) holds the the following properties. F[x:] = 0, F[ - 14, and | v12d
3.2 Similarity Augmentation
In VSAs, it is common to measure the similarity with an extracted embedding & with some other vector æ using the cosine similarity. For our HLB, we devise correction term when it is known that items have been bound together to extract ă, i.e., B* (xp. z) L. Then if & is the noisy version of the true bound term æ, we want cossim @ x) 1, and cossim( a. y) = 0, Vy # x. We achieve this by instead computing cossim(á; (ūr x) /p. and the derivation of this corrective term is given by
Theorem 3.2
Theorem 3.2 (Ó - Relationship). Given Ty Us ~ 1(1,1/d) VieN:
the cosine
similarity & between the original I; and retrieved vector á; is approximately equal to the inverse square root of the number of vector pairs in a composite representation p given by & x To
Proof of Theorem 3.2
We start with the definition of cosine similarity and insert the value of f.. The step-by-ster breakdown is shown in Equation
Iz
30
Σ x
x4 + >
x4
3
Σ a4 |arell2
24
j j=1, +#1
|=1,
21.
(7)
|,,,112
|xi122
|| +
E
2, ll2
| ||ar +
Σ
0
Mi
j-1, jri
j- 1,4
jti
Employing Properties 3.1
we can derive that ||0r|12
Σ
Vu²d and
v
2,
Thus, the square of the ||
+
Σ
*,1o llz can be expressed as
j-
1,
j
2
d
p- p-1
=|1g
+
2
1=1, f#1
Vi
12
j=1,
J#t
Vi
y1
y4
J#l 1z)
(8)
-22 (p- 1). 1dd + 2x + 2 p- 2d + 2a + 2B
Therefore, using Equation 7 and Equation 8 we can write that
1
1²dd
1d2d
1
E Vi2d vp.1p 2a + 23
udd vp pdd
vP.12d
12d
VP
5

---

The experimental result of the o - p relationship closely follows the theoretical expectation provided in|Appendix Cjwhich also indicates that the approximation valid. Since, know from Toeorem 3.2 that similarity score & drops by the inverse square root of the number of vector pairs in composite representation p, in places where p known can estimated from Xpll2 s u pp (proof in Appendix B), it can be used to update the cosine similarity multiplying the scores by vp. Equation 9 shows the updated similarity score where positive case (+), Φ would be close to 1/ and in negative case (-), & would be close to zero.
6 Ø VP
0(+) = = 2
x v
% 000 VP 20
= -1== vpxl
10
1.0
8
logo
6
-0.8
4
2
5
10
15
20
25
30
35
40
45
50
-.6
No. of bundled pairs p
o/ p vp
-0.
-logg
8
0.2
0.0
10
25
35
50
No. of bundled pairs p
Figure I: Empirical comparison of the corrected cosine similarity scores between & (on top) and &[=; (on bottom) for varying and shown in heatmap. The dimension, i.e., d = 2 is varied from 2 to 1024 (n {1, 2, 103) and the number of vector pairs bundled is varied from shows that we can accurately identify when vector has been bound to a VSA or not when we keep track of how many pairs of terms are included.
50. This
Empirical results ø' for varying n and are visualized and verified by heatmap. In a composite
representation Xa Σi= (I, Oy:), when unbinding is applied using the query y,, i.e., B (X'= yi) = E positive case similarity between 2; and 2,. On the contrary, similarity between á, and any Iy where j e 21 ... Pp} and j * i, is negative case. Mean cosine similarity scores of 100 trials for both positive and negative cases in presented in Figure where the scores for the positive cases are the red (+ 1) shades and the scores for the negative cases are in the blue (* 0) shades.
4 Empirical Results
4.1 Classical VSA Tasks
A common VSA task is, given bundle (addition) of pairs of bound vectors Σ Bi x y.). given a query F. E 8, C can the corresponding vector y, be correctly retrieved from the bundle. To test this, perform experiment similar random vectors, then sample (with replacement) p pairs of vectors for p (1.2.-.. 25). The pairs bound together and added to create a composite representation s. Then, iterate through all left pairs E, in the composite representation and attempt to retrieve the corresponding yg Vg e [1. A retrieval is considered correct if 8* (s, xx,) y (** x T y Vj # g. The total accuracy score for the bundle is recorded, and the experiment is repeated for 50 trials, Experiments are performed to
in [37]. We first create a pool P of N 1000
'erre and 3 the noise terms and in expectation bi[]] 0 and B| 0.

---

compare HRR [2), VTB [2]. MAP [0.. and our HLB VSAs. For each VSA, at each dimension of the vector, the area under the eurve (AUC) of the accuracy vs. the no. of bound terms plot is computed, and the results are shown in Figure 2 In general, HLB has comparable performance to HRR and VTB, and performs better than MAP.
HRR
0.9
VTB
AUC (%6
0.7
0.6
12
162
20
24
282
32
36
Dimension d
Figure The area under the accuracy curve due the change of no. of bundled pairs p for dimensions d. All the dimensions are chosen to be perfect squares due to the constraint of VTB.
The scenario we just considered looked at bindings only two items together, summed of many pairs of bindings. [12 proposed addition evaluations over sequential bindings that we now consider. In the random case we have an initial vector by, and for p rounds, we will modify it by a random vector such that 1 B(b,, x,,,, after which we unbind each to see how well the previous b, recovered. In the auto binding case, we use a single random vector ar for all rounds.
In this task, we are concerned with the quality of the similarity score in random/auto uundom/auto-bndding binding, we want 8 (b b, 1. For VSAs with approximate unbinding procedures, such as HRR, VTB, and MAP-C, the returned value will be I if p 1 but will decay as increases. HLBuses an exact unbinding procedure so that the returned value expected be V p. We are also interested in the magnitude of the vectors | (b,+1, 22,) 12, where ideal VSA has constant magnitude that does explode/vanish as p increases.
Random
Auto
1.0
1.0
0.8
0.8
Similarity
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
10
25
10
20
25
Magnitude
109
10
10a
10
10
20
No. of
No. of
HRR
VTB
MAP
Figure 3: When repeatedly binding different random (left) or single vector (right), HLB consistently returns the ideal similarity score of for present item (top row) and has a constant magnitude (bottom row), avoiding exploding/vanishie values.
Figure shows that HLB maintains stable magnitude regardless the number of bound vectors in both cases. This property arises due to the properties of the distribution shown in in/rrpertiess 3.1 As all components have an expected absolute value of the product of all components also has an expected absolute value 1. Thus, the norm of the binding is simply vd. also shows HL.B maintains desired similarity score increases. Combined with Figure Thaa shows the scores are near-zero when an item is not present, HLBB significant advantages consistency for designing VSA solutions.

---

4.2 Deep Learning with Hadamard Linear Binding
Two recent methods that integrate HRR with deep learning are tested to further validate our approach and briefly summarized in the two sub-sections below. In each case, we run all four VSAs and see that HLB either matches or exceeds the performance of other VSAs. In every experiment, the standard method of sampling vectors from each VSA is followed as outlined Table I] All the experiments are performed on a single NVIDIA TESLA PH402 GPU with 32GB memory.
4.2.1 Connectionist Symbolic Pseudo Secrets
When running on low-power computing environments, it is often desirable offload the computation to a third-party cloud environment to get the answer faster and use fewer local resources. However, this may be problematic if one does not fully trust the available cloud environments. Homomorphic encryption (HE) is the ideal means to alleviate this problem, providing cryptography for computations. HE is currently more expensive to perform than rumning neural network itself [II, defeating its own utility in this scenario. Connectionist Symbolic Pseudo Secrets (CSPS) B provides a heuristic means of obscuring the nature of the input (content), and output (number of classes/prediction), while also reducing the total local compute required.
CSPS mimics "one-time-pad" by taking random VSA vector the secret and binding it to the input æ. The value ((s, e, x) obscures the original æ, and the third-party runs the bulk of the network on their platform. A result is returned, and a small local network computes the final answer after unbinding with the secret 3* (y. s). Other than changing the VSA used, we follow the same training, testing, architecture size, and validation procedure of [3].
CSPS experimented with datasets MNIST, SVHN, CIFAR-10 (CR10), CIFAR- 100 (CR 100) and Mini-ImageNet (MIN). First, we look at the accuracy of each method, which is lower due to the noise of the random vector 8 added at test time since no secret VSA is ever reused. The results are shown in Table 2] where HLB outperforms all prior methods significantly. Notably, the MAP VSA is second best despite being one of the older VSAs, indicating its similarity to HLB in using a simple binding procedure, and thus simple gradient may be an important factor in this scenario.
Table 2: Accuracy comparison of the proposed HLB with HRR, VTB, MAP-C, and MAP-B in CSPS. The dimensions of the inputs along with the no. of classes are listed in the Dims/Labels column. The last row shows the geometric mean of the results.
DIMS/ LABELS
CSPS + HRR
CSPS + VTB
CSPS MAP-C
CSPS MAP-B
CSPS + HLB
DATASET
Top$1
Topo5
Top81
Top25
Top01
Top05
Top01
Top65
Top01
Top05
MNIST
28 28²/10 /10
98.51
98.44
98.46
98.40
98.73
SVHN
322/10
88.44
19.59
79.95
92.43
94.53
CR10
322/10
78.21
74.22
76.69
82.83
83.81
RR000
322/100
48.84
75.82
35.87
61.79
56.77
81.52
57.76
84.63
58.82
87 55.
MIN
842/100
40.99
66.99
45.81
73.52
52.22
78.63
57.91
82.81
59.48
83.35
GM
67.14
71.26
47.24
67.40
70.89
80,06
75.90
83.72
77.17
85.40
However, improved accuracy is not useful in this scenario if more information is leaked. The test in this scenario, as proposed by 33 is to calculate the Adjusted Rand Index (ARI) after attempting cluster the inputs and the outputs ÿ. which are available/visible to the snooping third-party. To be successful, the ART must be near zero (indicating random label assignment) for both inputs and outputs.
We use K-means, Gaussian Mixture Model (GMM), Birch 45 and HDBSCAN 7 as the clustering algorithms and specifyy the true number of classes to each method to maximize attacker success (information they would not know). The results can be found in Table 3] where the top rows indicate the clustering of the input B(x, s), and the bottom rows the clustering of the output ÿ. All the numbers are percentages (%). showing all methods do a good job at hiding information from the adversary (except the MNIST dataset, which is routinely degenerate).
The MNIST result is a good reminder that CSPS security is heuristic, not guaranteed. Nevertheless, see HLB has consistently close-to-zero scores for SVHN, CIFARs, and Mini-ImageNet indicating
8

---

Table Clustering results of the main network inputs (top rows) and outputs (bottom rows) in terms of Adjusted Rand Index (ARI). Because CSPS is trying to hide information, scores near zero are better. Cell color corresponds to the cell absolute value, with blue indicating lower ART and red indicating higher ARI. All numbers in percentages, and show HLB is better at information hiding.
CLUSTERING METHODS
HRR
VTB
MNIST
SVHN
CR10
CR100
MIN
MNIST
SVHN
CR 10
CR100
100
MIN
K-MEANS
-0.02
-0.01
0.18
0.54
0.42
-0.00
00.01
-0.01
0.02
0.00
1.0
GMM
0.01
0.00
0.44
4.67
1.37
0..01
0.02
0.01
BIRCH
0.20
0.00
0.14
0.45
0.35
0.03
0.08
0.03
HDBSCAN
0.00
-0.24
1.23
0.01
0.02
0.00
0.00
0.00
0.00
0.00
0.8
K-MEANS
1.28
0.06
0.21
0.03
0.08
8.52
0.13
1.11
0.05
0.12
GMM
1.28
0.06
0.17
0.04
0.09
8.63
0.14
1.63
0.05
0.00
BIRCH
1.51
0.03
0.13
0.05
0.07
3.24
0.00
0.64
0.06
0.17
HDBSCAN
0.00
0.00
0.00
0.00
0.00
0.00
0.09
0.00
0.00
0.00
0.6
CLUSTERING METHODS
MAP
HLB
MNIST
SVHN
CR10
CR 100
MIN
MNIST
SVHN
CR 10
CR
MIN
K-MEANS
0.17
0.01
0.01
0,00
0.00
0.09
0.00
0.00
0.00
0.00
0.4
GMM
3.39
0.01
0.01
0.00
0.00
2.53
0.00
0.00
0.00
0.00
BIRCH
0.84
-0.00
0.00
0.01
0.00
0.00
0.00
0.01
0.00
HDBSCAN
0.00
0.00
0.00
0.00
0.00
0.00
0.2
K-MEANS
15.91
0.09
0.00
0.03
0.01
13.67
0.04
0.01
0.02
-0.00
GMM
42.43
0.11
0.00
14.96
0.02
0.00
BIRCH
7.09
-0.07
-0.02
0.01
-0.00
18.44
-0.07
0.00
0.01
0.02
HDBSCAN
0.48
0.00
0.00
0.00
0.00
7.60
0.01
0.00
0.00
0.00
0.0
that its improved accuracy with simultaneously improved security. This also validates the use of the VSA in deep learning architecture design and the efficacy of our approach.
4.2.2 Xtreme Multi-Label Classification
Extreme Multi-label (XML) is the scenario where, given single input of size d, C >>> d classes are used to predict. This is common in e-commerce applications where new products need be tagged, and an input on the order of d 5000 is relatively small compared to C > 100,000 or more classes. This imposes unique computational constraints due to the output space being larger than the input space and is generally only solvable because the output space is sparse often less than 100 relevant classes will be positive for any one input. VSAs have been applied to XML by exploiting the low positive class occurrence rate to represent the problem symbolically [9]
While many prior works focus on innovative strategies cluster/make hierarchies/compres. the penultimate layer 19 20 31 18 44 (22, neuro-symbolic approach was proposed by (9. Given K total possible classes, they assigned each class vector Cj. to be each class's representation, and the set of all classes a Σk= Ck-
The VSA trick used by [9] was to define an additional "present" class p and a "missing" class m. Then, the target output of the network f() is itself a vector composed of two parts added together. First, B(p, >x C+) represents all presen/ classes, and so the sum is over finite smaller set. Then the absent classes compute the missing representing B(m, a Σ. G2). which again only needs to compute over the finite set of present classes, yet represents the set of all non-present classes by exploiting the symbolic properties of the VSA.
For XML classification, we have a set of K classes that will be present for a given input, where K is the norm. Yet, there will be L total possible classes where L > 100, 000 is quite common. Forming normal linear layer to produce L. outputs is the majority of computational work and memory use in standard XML models, and thus the target for reduction. VSA can be used to side-step this cost, as shown by (9. by leveraging the symbolic manipulation of the outputs. First, consider the target label as vector E Rd such that d << By defining VSA vector to represent "present" and "missing" classes as p and m, where each class is given its own vector Ci.... we can shift the computational complexity form (I)) to OKK) by manipulating the "missing" classes as the compliment of the present classes shown in Equation 10

---

Similarly, the loss to calculate the gradient can be computed based on the network's prediction by taking the cosine similarity between each expected class and one cosine similarity for the representation of all missing classes. The excepted response of I or () for an item being present/absent from the VSA used to determine if we want the similarity to be (1-co8) (just cos), as shown in Equation 11
Labels Present(Odd K)
Lahels (d)))
Labels Preseni((dK)
Lahels (ds.)t((dL)
Σ B(p.c) +
Σ
B(m,
aaa
P.
a=
Σ
C
+
Σ
C
sE -1
JEU; --1
15 1-
iE
(10)
Absent classes Old K)
Present Classes (dd K)
loss
Σ (1 - cos (p. c;)) tEy.
cos B (*,, 8),
Σ iEM; -1
C;
(11)
The details and network sizes of [9] are followed, except we replace the original VSA with our four candidates. The network is trained on 8 datasets listed in Table from [4] and evaluated using normalized discounted cumulative gain (nDCG) and propensity-scored (PS) based normalized discounted cumulative gain (PSnDCG) as suggested by [19]
Table 4: XML classification results in dense label representation with HRR, VTB, MAP, and HLB in terms of nDCG and PSnDCG. The proposed HLB has attained the best nDCG and PSnDCG scores on all the datasets setting new SOTA.
DATASET
BIBTEX
DELICIOUS
MEDIAMILL
EURLEX-4K
METRICS
nDCG
PSnDCG
nDCG
PSnDCG
nDCG
PSnDCG
nDCG
PSnDCG
HRR
60.296
45.572
66.454
30.016
83.885
63.684
77.225
30.684
VTB
57.693
45.219
63.325
31.449
87.232
66.948
76.964
31.180
MAP-C
59.280
46.092
65.376
31.943
87.255
66.886
72.439
26.752
MAP-B
59.412
46.340
65.431
32.122
86.886
66.562
71.128
26.340
HLB
61.741
48.639
67.821
32.797
88.064
67.525
77.868
31.526
DATASET
EURLEX-4.3K
WIKI10-31K
AMAZON- 13K
DELICIOUS- 200K
METRICS
nDCG
PSnDCG
nDCG
PSnDCG
nDCG
PSnDCG
nDCG
PSnDCG
HRR
84.497
38.545
81.068
9.185
93.258
49.642
44.933
6.839
VTB
84.663
38.540
78.025
9.645
92.373
49.463
44.092
6.664
MAP-C
85.472
39.233
80.203
10.027
92.013
48.686
45.373
6.862
MAP-B
85.023
38.820
80.238
10.035
92.307
48.812
45.459
6.870
HLB
88.204
43.622
83.589
11.869
93.672
50.270
46.331
6.952
The classification result in terms of nDCG and PSnDCG in all the eight datasets is presented in Table 4 where the top four datasets are comparatively easy with maximum no. of features of 5000 and no. of labels of 4000. The bottom four datasets are comparatively hard with the no. of features and labels on the scale of 100K. The proposed HLB has attained the best results in all the datasets on both metrics. In contrast to the prior CSPS results, here we see that the performance differences between HRR, VTB, and MAP are more varied, with no clear "second-place" performer.
5 Conclusion
In this paper, novel linear vector symbolic architecture named HLB presented derived from Hadamard transform. Along with an initialization condition named MiND distribution is proposed for which we proved the cosine similarity é is approximately equal the inverse square root of the no. of bundled vector pairs p which matches with the experimental results. The proposed HLB showed superior performance in classical VSA tasks and deep learning compared to other VSAs such as HRR, VTB, and MAP. In learning tasks, HLB is applied to CSPS and XML classification tasks. In both of the tasks, HIBB has achieved the best results terms of respective metrics all the datasets showing diverse potential of HLB in Neuro-symbolic AI.
10

---

References
[1] Mohammad Mahmudul Alam, Edward Raff, Stella Biderman, Tim Oates, and James Holt. Recasting self-attention with holographic reduced representations. Proceedings of the 40th International Conference on Machine Learning. (CML'23, JMLR.org. 2023.
[2] Mohammad Mahmudul Alam, Edward Raff, and Tim Oates. Towards generalization in subitiz- ing with neuro-symbolic loss using holographic reduced representations. Neuro-Symbolic Learning and Reasoning in the era of Large Language Models, 2023.
[3] Mohammad Mahmudul Alam, Edward Raff, Tim Oates, and James Holt. Deploying convo- lutional networks on untrusted platforms using 2D holographic reduced representations. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 367-393, PMLR, 17-23 Jul 2022.
[4] K. Bhatia, K. Dahiya, H. Jain, P. Kar, A. Mittal, Y. Prabhu, and M. Varma. The extreme classification repository: Multi-label datasets and code, 2016.
[5] Peter Blouw and Chris Eliasmith. A neurally plausible encoding word order information into a semantic vector space. 35th Annual Conference of the Cognitive Science Society, 35:1905-1910, 2013.
[6] Peter Blouw, Eugene Solodkin, Paul Thagard, and Chris Eliasmith. Concepts as semantic pointers: A framework and computational model. Cognitive Science, 40(5): 1000)11228111,,,, 2016.
[7] Ricardo JGB Campello, Davoud Moulavi, and Jörg Sander. Density-based clustering based on hierarchical density estimates. In Pacific-Asia conference on knowledge discovery and data mining, pages 160-172. Springer, 2013.
[8] C. Fliasmith, T. C. Stewart, X. Choo, T. Bekolay, T.. DeWolf, Y. Tang, and D. Rasmussen. A large-scale model of the functioning brain. Science, 318(6111):1202-11
11 2012.
[9] Ashwinkumar Ganesan, Hang Gao, Sunil Gandhi, Edward Raff, Tim Oates, James Holt, and Mark McLean. Learning with holographic reduced representations. Advances in neural information processing systems, 34:25606-25620, 2021.
[10] Ross W. Gayler. Multiplicative binding, representation operators & analogy (workshop poster), 1998.
[11] Ran Gilad -atad-BBacrrch, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Nachrig, and John Wernsing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International conference on machine learning, pages 201-210. PMLR, 2016.
[12] Jan Gosmann and Chris Eliasmith. Vector-derived transformation binding: An improved binding operation for deep symbol-likk processing in neural networks. Neural Comput., 31(5):849-83) -899,999,99-- 2019.
[13] Klaus Greff, Sjoerd van Steenkiste, and Jürgen Schmidhuber. On the binding problem in artificial neural networks. arXiv, 2020.
[14] Robert Guirado, Abbas Rahimi, Geethan Karunaratne, Eduard Alarcón, Abu Sebastian, and Sergi Abadal. Whype: scale-out architecture with wireless over-the-air majority for scalable in-memory hyperdimensional computing. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 13(1):137 2023.
[15] Mike Heddes, Igor Nunes, Pere VergÄ@s, Denis Kleyko, Danny Abraham, Tony Givargis, Alexandru Nicolau, and Alexander Veidenbaum. Torchhd: An open source python library to support research on hyperdimensional computing and vector symbolic architectures. Journal of Machine Learning Research, 24(255):1-10, 2023.

---

[16] Qiuyuan Huang, Paul Smolensky, Xiaodong He, Li Deng, and Dapeng Wu. Tensor product generation networks for deep nlp modeling. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lunguage Technologies, Volume (Long Pupers), pages 1263-1273. Association for Computational Linguistics, jun 2018.
[17] Mohsen Imani, Deqian Kong, Abbas Rahimi, and Tajana Rosing. Voicehd: Hyperdimen- sional computing for efficient speech recognition. In 2017 IEEE International Conference on Rebooting Computing (ICRC), pages 1-8. IEEE, nov 2017.
[18] Himanshu Jain, Venkatesh Balasubramanian. Bhanu Chunduri, and Manik Varma. Slice: Scal- able linear extreme classifiers trained on 100 million labels for related searches. In Proceedings of the twelfth ACM international conference on web search and data mining, pages 528-55 536, 2019.
[19] Himanshu Jain, Yashoteja Prabhu, and Manik Varma. Extreme multi-label loss functions for recommendation, tagging, ranking & other missing label applications. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 935-944, 2016.
[20] Ankit Jalan and Purushottam Kar. Accelerating extreme classification via adaptive feature agglomeration. arXiv preprint 1rXiv:1905.11769 2019.
[21] Michael N. Jones and Douglas J.K. Mewhort. Representing word meaning and order information composite holographic lexicon. Psychological Review, 114(1):1-37, 2007.
[22] Armand Joulin, Moustapha Cissé, David Grangier, Hervé Jégou, al. Efficient softmax approximation for gpus. In International conference on machine learning, pages 1302-1310. PMLR, 2017.
[23] Denis Kleyko, Mike Davies, Edward Paxon Frady, Pentti Kanerva, Spencer J. Kent, Bruno A. Ol- shausen, Evgeny Osipov, Jan M. Rabaey, Dmitri A. Rachkovskij. Abbas Rahimi, and Friedrich T. Sommer. Vector symbolic architectures as a computing framework for emerging hardware. Proceedings of the IEEE, 1 10(10))158--157, 2022.
[24] Denis Kleyko, Dmitri Rachkovskij, Evgeny Osipov, and Abbas Rahimi. A survey hyperdi- mensional computing aka vector symbolic architectures, part ii: Applications, cognitive models, and challenges. ACM Comput. Surv., 55(9). jan 2023.
[25] Denis Kleyko, Dmitri A. Rachkovskij, Evgeny Osipov, and Abbas Rahimi. survey on hyperdi- mensional computing aka vector symbolic architectures, part Models and data transformations. ACM Comput. Surv., 55(6), dec 2022.
[26] Kunz. On the equivalence between one-dimensional discrete walsh-hadamard and multidi- mensional discrete fourier transforms. IEEE Transactions on Computers, 100(3):267-268, 1979.
[27] Siyu Liao and Bo Yuan. Cireconv: A structured convolution with low complexity. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01))4287-4294, Jul. 2019.
[28) Mohammad Mahmudul Alam, Edward Raff, Stella R Biderman, Tim Oates, and James Holt. Holographic global convolutional networks for long-range prediction tasks in malware detection. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 4042-4050. PMLR, 02-04 May 2024.
[29] Nicolas Menet, Michael Hersche, Geethan Karunaratne, Luca Benini, Abu Sebastian, and Abbas Rahimi. Mimonets: haltiple-inuutmmuliile-----e
neural networks exploiting computation in superposition. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardr, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 39553-39565. Curran Associates, Inc., 2023.
12

---

[30] Peer Neubert, Stefan Schubert, and Peter Protzel. Learning vector symbolic architectures for reactive robot behaviours. In Proc. of Intl. Conf. on Intelligent Robots and Systems (IROS) Workshop on Machine Learning Methods for High-Level Cognitive Capabilities in Robotics, 2016.
[31] Alexandru Niculescu-Mins and Ehsan Abbasnejad. Label filters for large scale multilabel classification. In Artificial intelligence and statistics, pages 1448-1457. PMLR, 2017.
[32] Tony A Plate. Holographic reduced representations. IEEE Transactions Neural networks, 6(3):623-641, 1995.
[33] Rebecca Saul, Mohammad Mahmudul Alam, John Hurwitz, Edward Raff, Tim Oates, and James Holt. Lempel-ziv networks. In Proceedings on "I Can't Believe It's Not Better! Understanding Deep Learning Through Empirical Falsification" at NeurlPS 2022 Workshops, volume 187 of Proceedings of Machine Learning Research, pages 1-11. PMLR, 03 Dec 2023.
[34] Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear transformers are secretly fast weight programmers. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th Inter- national Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 9355-9366. PMLR, 2021.
[35] Imanol Schlag and Jürgen Schmidhuber. Learning to reason with third order tensor products. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[36] Kenny Schlegel, Peer Neubert, and Peter Protzel. A comparison of vector symbolic architectures. arXiv, 2020.
[37] Kenny Schlegel, Peer Neubert, and Peter Protzel. A comparison of vector symbolic architectures. Artificial Intelligence Review, 55(6):4523-4555 Aug 2022.
[38] Paul Smolensky, Tensor product variable binding and the representation of symbolic structures in connectionist systems. Artificial Intelligence, 46(1):159-216, 1990.
[39] Julia Steinberg and Haim Sompolinsky. Associative memory of structured knowledge. Scientific Reports, 12(1), December 2022.
[40] Terrence C. Stewart and Chris Eliasmith. Large-scale synthesis of functional spiking neural circuits. Proceedings of the IEEE, 102(5):881-89) 2014.
[41] Yi Tay, Luu Anh Tuan, and Siu Cheung Hui. Learning to attend via word-aspect associative fusion for aspect-based based sentiment analysis. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018.
[42] Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, Nilesh Agrawal, and Partha Talukdar. In- teracte: Improving convolution-base knowledge graph embeddings by increasing feature interactions. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pages 3009-3016. AAAI Press, 2020.
[43] Ryosuke Yamaki, Tadahiro Taniguchi, and Daichi Mochihashi. Holographic CCG parsing. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics ( (Volume I: Long Papers), pages 262-276, Toronto, Canada, July 2023. Association for Computational Linguistics.
[44] Ronghui You, Zihan Zhang, Ziye Wang, Suyang Dai, Hiroshi Mamitsuka, and Shanfeng Zhu. Attentionxml: Label tree-based attention- aware deep model for high-performance extreme multi-label text classification. Advances in neural information processing systems, 32, 2019.
[45] Tian Zhang, Raghu Ramakrishnan, and Miron Livny. Birch: an efficient data clustering method for very large databases. ACM sigmod record, 25(2): 1996.
13

---

A Noise Decomposition
When a single vector pair is combined, one of the vector pairs can be exactly retrieved with the help of the other component and the inverse function, recalling the retrieved output does not contain any noise component for a single pair of vectors, i.e., P = However, when more than one vector pairs are bundled, noise starts to accumulate. In this section, we will uncover the noise components accumulated with and without the projection to the inputs and analyze their impact on expectation. We first start with the noise component without the projection step ni
Th d
H Hy
Hay о Hÿ,)
(12)
Let, set the value of n to be 1 thus, = 2 2 and the number vector pairs = 2, i.e., Xp=2 (( (22,, 12)- We want to retrieve J, using the query Y1, thereby, the expression of Hi is uncovered step by step for p = 2 shown in Equation 13
1
1
Th H1( p-2
(Hæg O Hv2))
Hyn
1
Vd. H
Vi 10)
yi
(I
+
(12 + /0
d
v1
10)
2
(0)
12
(y/
(0)
1/2 (1)
(0)
(1)
(m
(2) (2/2 (2) (0) (
1
d.
(8h
(0)
(13)
d
(2) 4.2
(0) (1)
19/2
+
2/
(1)
(u
91
(8
my
(1)
(91
(0) (1) (0) tyy
(n
(9)
12
1 (Hu))e on
(Hul)
P(22, 122 31)
I (Hy))
Here, PP V 1 d the polynomials comprises of (z2, 12), and the query vector V1- P is the vector of polynomials consisting of Pa. From the noise expression, we can observe that the numerator is polynomial and the denominator the product of all the elements of the Hadamard transformation of the query vector. This is true for any value of n and p. Thus, in general, for any query y, we can express ni shown in Equation
P 1. jei (a Uy
n
(14)
11 (Hy))
The noise accumulated after applying the projection to the inputs is quite straightforward as given in Equation 15)
E j-1, iti
(z,0,,)
(15)
y/
Although the vectors 2, V VieN::a 1 i are sampled from a MiND with an expected value of O given in Equation 6, the sample mean of 2; y, would be j 0 but 0. Both the numerator of of and vi are the polynomials thus the expected value would be very close to O. However, the expected value of the denominator of of would be E[[ (Hy:)
I E[(Hu:)a] ad whereas the expected value of the denominator of ni is Ely:] f.. Since, fd P. hence, in
14

---

expectation my < n.. This is also verified by an empirical study where i.e., the dimension d = 2" varied along with the no. of bound vector pairs p and the amount of absolute mean noise in retrieval is estimated.
Figure 4 shows the heatmap visualization of the noise for both oi and oi in natural log scale. The amount of noise accumulated without any projection to the inputs is much higher compared to the noise accumulation with the projection. For varying and p. the maximum amount of noise accumulated when projection is applied is 7.18 and without any projection, the maximum amount of noise is 19.38. Also, most of the heatmap of i7 remains in the blue region whereas as n and p increase, the heatmap of 17 moves towards the red region. Therefore, is evident that the projection the inputs diminishes the amount accumulated noise with the retrieved output.
Noise component without any projection T/f
20.0
logo (d)
17.5
6
4
15.0
2
12.5
5
10
15
20
25
30
35
40
45
50
No. of bundled pairs p
10.00
Noise component due to the projection 1/.
10
7.5
loga (d)
8
5.0
6
2.5
2
0.0
5
15
25
30
35
40
45
50
No. of bundled pairs p
Figure 4: Heatmap of the empirical comparison of the noise components vy and nf." for varying and p shown natural logarithm scale. The dimension, i.e., d 2 is varied from to 1024 (n E (1.2.-.., 10}) and the number of vector pairs bundled is varied from 2 to 50.
B Norm Relation
Theorem B.1 (x Relationship). Given 2, ~ -2(,, 1/d) ViiiN:1ii the norm of the composite representation Xp is proportional to vp and approximately equal to the 1 Vp Vp.v. d.
Given Xp is the composite representation of the bound vectors, i.e., the summation no. individual bound terms. First, let's compute the norm of the single bound term as shown in Equation 16
Proof of Theorem B.7
[B, (12111112 = ||,; Vil2
= -V (1) 1; 1))² (z (2) (2) ... (1)
ui (2))
=v(tpp22 + (2/2222 2 [[T((1) (l tu- t +
-Vpld
(16)
15

---

Now, let's expand and compute the square norm of the composite representation given in Equation 17
|xol 2 [8(z,,81 v1) B M2) Blx Up)l1
11 v1)1 [B v2)
[B 1n)ll +
where & is the rest of the terms of square expansion.
-1+'d ptd +.dt... +
(17)
1xol2 vp. 4 5
w.d n² Vp
[ is the noise term and discarded to make an approximation
Thus, given the composite representation and the mean of the MiND distribution, we can estimate the no. of bound terms bundled together by = |1x/l///(0 AtA.
Figure 5] shows the comparison between the theoretical relationship and actual experimental results where the norm of the composite representation is computed for 0.5 and p {1, 2, ... 200 The figure indicates that the theoretical relationship aligns with the experimental results. However, as the number of bundled pair increases, the variation in the norm increases. This is because of making
the approximation by discarding [Equuttton 17
120
Theoretical IIxoll2 12 p
X!x
100
Experimental ||xal 2 vd
Norm of composite representation
80
40
20
40
80
120
140
160
180
200
No. bundled pairs p
Figure 5: Comparison between the theoretical and experimental relationship Theorem B.1 The norm of the composite representation of the bound vectors is computed for no. of bundled vectors from to 200 of dimension = 1024. The figure shows how the experimental value of the norm closely follows the theoretical relation between ||xpl22 and p.
16

---

C Cosine Relation
Theorem 3.2 shows how the cosine similarity between the original 2; and retrieved vector d; is approximately equal to the inverse square root of the number of vector pairs in a composite representation p. In this section, we will perform an empirical analysis of the theorem and compare it with the theoretical results. For {1, 2, ... 50), similarity score 6 is calculated for vector dimension 512. Additionally, the theoretical cosine similarity score is also calculated using the value of following the theorem. Figure shows the comparison between the two results where the experimental result closely follows the theoretical result. The figure also shows the standard deviation for 100 trials, indicating minute change from the actual value.
Theoretical
Experimental Fz
I do
0.8
Cosine Similarity
0.6
0.4
0.2
10
20
30
40
45
No. of bundled pairs P
Figure 6: Comparison between the theoretical and experimental dimension d = 512 are combined and retrieved with varied number of vectors from 1 to 50. The zoom portion shows how closely experimental results match with the theoretical conclusion.
p relationship. Vectors of
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The paper claims to present new Hadamard-derived linear vector symbolic architecture in the abstract and introduction which accurately reflects the contribution and scope of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are described in the paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
18

---

Answer:
[Yes]
Justification: All the theoretical results and proofs are provided the Methodology section. (See section 3
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The experimental setup is based on previous papers. All the used parame- ters discussed in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
19

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: All the code is provided with the supplemental material. Data publicly available and instruction is provided on how to get the data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
public/guides/ Staalees//ooeSSuummsisiiiiiii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
Cooee//mdeeeSbmmmaia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental details and their sources are cited in the Empirical results section. (see deelssecionn& 4)
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: See Figure 2
Figure
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
20

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Seelsection
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We followed the NeurlPS code of conduct.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work has no negative socictal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
21

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No high-risk data or models are used.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Original paper and code are cited in the paper.
Guidelines:
existing assets. The authors should cite the original paper that produced the code package or dataset.
The answer NA means that the paper does
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
22

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Documentation of the code is provided.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No Crowdsourcing and Research with Human Subjects are used.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No participants are used.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "sAFVnqInnN", "reviewer": "Reviewer_xpT1", "summary": "The paper proposed HLB, a vector symbolic architecture derived from the Hadamard transform, reminiscent of holographic reduced representation, to mitigate the challenges that classical VSAs face in deep learning tasks such as numerical stability. Results show comparable memorization capability from alternative models and improved performance on two practical tasks, CSPS and XML.", "questions": "1.\tIs there a way to compute or estimate $\\rho$ (number of bound items) given the vector? Many VSA can estimate via its norm and subsequent processing does not need to actively track the number of bound items in practice.  \n2.\tHow does HLB compare to other VSAs in computational complexity? \n3.\tIs MAP or MAP-C used in the experiment? They seems to be used interchangeably, but the C (which I assume to stand for “continuous” base vectors as opposed to bipolar) in MAP-C was never explained. \n4.\tAlthough the VSAs in comparisons are selected well, all three approaches leverage approximate unbinding while HLB leverages exact unbinding. How would HLB compare with alternative approaches in general, especially MAP (with bipolar vector initialization) and FHRR (HRR in the Fourier domain)? Both support exact unbinding (due to vectors having exact inverses).", "limitations": "No limitation section is present.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper is well-presented and delineates the design principles of HLB in the context of other VSA methods, making the position of the HLB clear. \n2.\tHLB is original in the sense that WH transform has not been leveraged directly to derive a VSA before (to the best of my knowledge); although the main design change from HRR is that the Fourier transform is replaced with the Hadamard transform, subsequent derivations of HDC properties and additional technique (the correction term, and the choice of sampling distribution of the hypervectors) is novel. \n3.\tThe paper presents reasonably rigorous (see weakness) proof for its claim and supports it with empirical results. Experiments cover fundamental analytical properties desired from a VSA model as well as some applications of VSA in DL. \n4.\tThe paper is significant in the field of vector symbolic architecture as a novel VSA model that may address some of the existing challenges in VSA, particularly the numerical stability problem.", "weaknesses": "1.\tSeveral typos in the draft (line 87 it’s, 95 four, 150 dervise, 197 HLBuses, 260)\n2.\tAlthough the key parameter selection is explained in the experimental section, the authors defer the main experimental details to the referenced work. The authors are encouraged to briefly summarize each experiment and how HRR is used. \n3.\tSee questions for additional concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1:** Thank you for the typo catches, they have been fixed! \n\n**W2:** For CSPS each network has four (convolutional) U-Net rounds in every\nexperiment and doubles from 64 filters after each round,\nhalving in size for the decode. The local prediction network has 4 convolutional layers, with max-pooling after each round, followed by three linear layers of 2048, then 1024, and finally, the $K$ classes of neurons. \n\nFor XML, two hidden layers on a fully connected input for each dataset are used. The dimension $d=400$ for the smaller datasets and $d=3000$ for  Amazon-13K and larger datasets. This is significantly less memory than a $d \\times L$ matrix for normal BCE where $L$ is up to 200k in our experiments. \n\nEach of 4.2.1 and 4.2.2 included this briefly in text, but was clearly not sufficient. For 4.2.1, we will add a new figure to help summarize (see one-page PDF). For 4.2.2., we will add a brief explanation, please see the one-page PDF again as the equations don't render properly in markdown/OpenReview.\n\n**Q1:** The 2-norm of the composite representation $\\chi$ can be approximated as $\\sqrt{d \\cdot \\rho}$.  Thus solving $\\|\\chi\\|\\_2 = \\sqrt{d \\cdot \\rho}$ gives $\\rho = \\|\\chi\\|\\_2^2 \\cdot d^{-1} $. This is a good estimate of $\\rho$ with a R-square value of $0.9865$, please see the rebuttal 1-page PDF for a plot of this relationship. \n\n**Q2:** HLB and MAP have $\\mathcal{O}(d)$ complexity, whereas HRR is $\\mathcal{O}(d \\log d)$ (for an FFT), and VTB has $\\mathcal{O}(d \\sqrt{d})$ (for $\\sqrt{d}$ matrix-vector products of $\\sqrt{d}^2$ cost each). We will add this to the manuscript. \n\n**Q3:** MAP-C is used because it is the version of MAP that allows continuous vector values. Other variants of MAP require integer values, and thus can't be differentiated. So MAP-C is the logical point of comparison and is shortened to \"MAP\" in the manuscript. We will explain this in the revision; thank you. \n\n**Q4:**  For FHHR, we clarify that our experiments use the projected HRR of [8], which enforces complex unit magnitude -- and is thus equivalent to FHHR and uses an exact unbinding operation. Given that [8] and [1] both found the projection step necessary for good performance, we did not see value in running the original unprotected HRR. \n\nFor MAP-B (MAP with binary initialization), we were able to run the CSPS experiment, which still shows MAP-B performing worse than our HLB. The result is below, and we are still running the XML experiments during the rebuttal phase. Once completed they will go into the main paper. Still, it is clear that MAP-B does not outperform MAP-C, let along our HLB, indicating the initialization was not a singularly important difference. \n\nMNIST: 98.40\\%\n\nSVHN: 92.43\\%\n\nCIFAR-10: 82.83\\%\n\nCIFAR-100: 57.76\\%, 84.63%\n\nMiniImageNet: 57.91\\%, 82.81%\n\nGM: 75.90\\%, 83.72%\n\nThe XML results thus far:\n\n| Dataset | nDCG | PSnDCG |\n|---|---|---|\n| Bibtex | 59.412 | 46.340 |\n| Delicious | 65.431 | 32.122 |\n| Mediamill | 86.886 | 66.562 |\n| EURLex-4K | 71.128 | 26.340 |\n| EURLex-4.3K | 85.023 | 38.820 |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "82dIZXJ2Cc", "reviewer": "Reviewer_6ktE", "summary": "The authors propose a new form of Vector Symbolic Architecture (VSA), which leverages the Walsh Hadamard transform for vector binding. The new binding is named Hadamard-derived linear binding (HLB), and it achieves comparable or better performance than existing VSAs when performing classic VSA tasks and combined with deep learning.", "questions": "1. Is there any connection between the performance improvements in section 4.2 and the numerical stability of HLB?\n2. Is there any benefit of having a symmetric binding?\n3. In Definition 3.1, what does B=B* mean? Could you provide a more detailed proof of Theorem 3.1?\n4. What are the differences between 'the proof of theorem 3.1' and equation (5)?", "limitations": "The limitations are not provided in the paper. The main limitation is that the merit of the new VSA is unclear in practice as the baselines only involve VSA.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The new binding method is developed with solid mathematical support. With the Hadamard-derived linear binding, the complexity of binding remains at O(d) while also providing some intriguing properties like the stability of similarity scores under the binding of multiple items. In the experiments, the new VSA is able to achieve better or comparable performance than existing VSAs such as MAP and HRR.", "weaknesses": "1. The motivation behind using WHT to derive the binding operation is missing.\n2. Section 3 (the part before subsection 3.1) is rather hard to follow due to possible typos and poor organization.\n3. It is unclear why the proposed method improves the performance in deep learning related tasks (in section 4.2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1:** We will add the below explanation motivating the choice of the WHT to the manuscript:\n\n> Our motivation for using the WHT comes from its parallels to the FFT used to derive the HRR and the HRR's relatively high performance. The Hadamard matrix has a simple recursive structure, making analysis tractable, and its transpose is its own inverse, which simplifies the design of the inverse function $\\mathcal{B}^*$. Like the FFT, WHT can be computed in log-linear time, though in our case, the derivation results in linear complexity as an added benefit. The WHT is already associative and distributive, making less work to obtain the desired properties.  Finally, the WHT involves only $\\{-1,1\\}$ values, avoiding numerical instability that can occur with the HRR/FFT. This work shows that these motivations are well founded, as they result in a binding with comparable or improved performance in our testing. \n\n**W2:** We have corrected all noted typos and done another editing pass to make sure none remain. \n\nFor the flow of Section 3, we will add the following content into the intro/starting paragraphs to help ease the reader through the section. \n\n>First, we will briefly review the definition of the Hadamard matrix $H$ and its important properties (see W1 above) that make it a strong candidate from which to derive a VSA.  With these properties established, we will begin by deriving a VSA where binding and unbinding are the same operation in the same manner as which the original HRR can be derived[30]. Any VSA must introduce noise when vectors are bound together, and we will derive the form of the noise term as $\\eta^\\circ$. Unsatisfied with the magnitude of this term, we then define a projection step for the Hadamard matrix in a similar spirit to [8]'s complex-unit magnitude projection to support the HRR and derive an improved operation with a new and smaller noise term $\\eta^\\pi$. This will give us the HLB bind/unbind steps as noted in Table 1. \n\n**W3:** We believe HLB performs better in deep learning tasks because it avoids exploding/vanishing gradients. This can be observed in Figure 3 where HLB has a consistent magnitude norm under multiple operations, and the avoidance of numerical instability with the FFT or other operations. We will add this note to the paper. \n\n**Q1:** We believe so; see W3 note. In particular, the low performance of MAP-C despite similar mechanical operation points to a primary difference being the scale-sensitivity based on the number of bound/bundled terms. \n\n**Q2:** There are pros/cons to symmetry in binding, as noted in [11]. Non-symmetric VSAs have an apparent advantage in representing hierarchical structures (e.g., a stack) with lower noise. However, they may not be as easy to use in certain symbolic contexts due to the lack of symmetry and the inability to unbind multiple values in a single operation. This will be added to the manuscript, though we note that we make no claim on a preference for one vs the other. We pursued a symmetric VSA in our work simply because we thought we could build one effectively. \n\n**Q3:** $\\mathcal{B}=\\mathcal{B}^*$ was stating that in the context we used the same function for both binding and unbinding. This will be clarified in the revision. \n\nThis is the detailed step by step breakdown of the Theorem 3.1 \n\n$\\mathcal{B}^{*}(\\mathcal{B}(x\\_1, y\\_1) + \\cdots + \\mathcal{B}(x\\_\\rho, y\\_\\rho), y\\_i^\\dagger)$\n\n$= \\mathcal{B}^{*}(\\frac{1}{d} \\cdot H (H x\\_1 \\odot H y\\_1)  + \\cdots + \\frac{1}{d} \\cdot H (H x\\_\\rho \\odot H y\\_\\rho), y\\_i^\\dagger) $\n\n$= \\frac{1}{d} \\cdot H ((H x\\_1 \\odot H y\\_1 + \\cdots + H x\\_\\rho \\odot H y\\_\\rho) \\odot \\frac{1}{H y\\_i})$\n\n$= \\frac{1}{d} \\cdot H (H x\\_1 \\odot H y\\_1 \\odot \\frac{1}{H y\\_i} + \\cdots + H x\\_i \\odot H y\\_i \\odot \\frac{1}{H y\\_i} + \\cdots + H x\\_\\rho \\odot H y\\_\\rho \\odot \\frac{1}{H y\\_i}) $\n\n$= \\frac{1}{d} \\cdot H (H x\\_1 \\odot H y\\_1 \\odot \\frac{1}{H y\\_i} + \\cdots + H x\\_i + \\cdots + H x\\_\\rho \\odot H y\\_\\rho \\odot \\frac{1}{H y\\_i})$\n\n$= \\frac{1}{d} \\cdot H (H x\\_i + \\frac{1}{H y\\_i} \\odot \\sum\\_{\\substack{j=1,j \\neq i}}^{\\rho} (H x\\_j \\odot H y\\_j))$\n\n$= x\\_i + \\frac{1}{d} \\cdot H (\\frac{1}{H y\\_i} \\odot \\sum\\_{\\substack{j=1, j \\neq i}}^{\\rho} (H x\\_j \\odot H y\\_j) )$  Applying Lemma 3.1\n\nThen we get $= x\\_i $ if $\\rho = 1$, but otherwise we have the noise term for $\\rho > 1 $ where $x\\_i + \\eta\\_i^\\circ $. Where $\\eta\\_i^\\circ = \\frac{1}{d} \\cdot H (\\frac{1}{H y\\_i} \\odot \\sum\\_{\\substack{j=1, j \\neq i}}^{\\rho} (H x\\_j \\odot H y\\_j) )$\n\n**Q4:** Equation (5) has the same operations as theorem 3.1, except Equation (5) includes a projection step when theorem 3.1 does not. It shows that we end up with a different description of the error term $\\eta$ when adding a projection step that is easier to analyze and work with. This will be added to the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hK2mlT689a", "reviewer": "Reviewer_rBtB", "summary": "This work describes a novel vector-symbolic architecture with linear-complexity binding/unbinding operations which includes the following components:\n- A novel binding/unbinding scheme based on the Walsh-Hadamard transform, which reduces to element-wise multiplication and division due to the self-inverse properties of the Hadamard matrix, the definition of the binding operation, and the proposed projection step.\n- Initialization of hypervector entries following a bimodal Gaussian distribution for purposes of numerical stability.\n- A hypervector projection step which in expectation reduces the amount of noise which is incurred by unbinding a vector from a sum of bindings of pairs of vectors. It also simplifies the final form of the bind/unbind operations.\n- A correction factor that is applied to augment the similarity score when retrieving from a sum of bound vectors, when the number of terms in the sum is known.\n\nThe authors experimentally test the effectiveness of their novel VSA scheme in several tasks including pure synthetic VSA tasks, as well as two tasks in which VSA schemes have previously been combined with deep neural networks.", "questions": "- It would be great to elaborate on other trainable biding schemes discussed in (1) weaknesses \n- If time and compute resources allow, it would be interesting to have more results based on the VSA neuro-symbolic architectures pointed out in (2) weaknesses, especially since the first two works have code repositories publically available. \n- What is the reason behind the blue horizontal strip at the top of Figure 4?\n- I did not fully understand what the hyperparameter search procedure for experiments in Section 4.2 was. Did the authors re-use the hyperparameters from the experiments in the referenced papers?\n- In which scenarios is the discussion in section 3.2 relevant? The proposed factor only scales the similarity values, it does not modify the rankings of similarity scores, so it is not entirely clear to me in which context this matters.", "limitations": "This work has no negative societal impact.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper is written clearly.\n- The experimental results in section 4.2 are convincing.\n- The noise-reducing projection step is an interesting idea. Although the idea is not novel in itself, the definition of the specific projection step is novel as it is well applied in this novel context of Hadamard-derived binding. \n- This VSA is highly efficient, including only element-wise operations.\n- The final HLB bind/unbind operations are trivially simple, but there is a novelty and potentially useful insight in their derivation.", "weaknesses": "1) Perhaps, it is worth mentioning and if possible elaborating/comparing with other parameterizable binding schemes such as \"Steinberg and Sompolinsky, Associative memory of structured knowledge. Sci Rep 12, 21808 (2022)\". This binding scheme is based on a trainable matrix. In fact, this parameterized binding scheme is generic by providing a continuum choice from d (VSA) to d^2 (TPR) for d-dimensional embeddings.\n\n2) Besides the synthetic VSA tasks, out of the studied VSA+deep-learning applications, the XML classification results look very promising and practical (although CSPS looks interesting, it is a pseudo-encryption and hence heuristic). The reviewer was wondering if the proposed HLB binding and unbinding operators could have an edge in other hybrid VSA+deep-learning architectures such as:\n    - [27] where MIMOConv used HRR-based binding and MBAT-based unbinding, and MIMOFormer used MAP-based binding and unbinding\n    - Another neuro-symbolic capability of HRRs was studied in \"M. Hersche, et al. A neuro-vector-symbolic architecture for solving Raven’s progressive matrices. Nat Mach Intell 5, 363–375 (2023)\". Particularly, fractional power encoding was used to describe a set of arithmetic rules with binding and unbinding for abductive reasoning.\n    - Another closely related work to XML classification in which the number of classes C is larger than dimension (d << C) is \"M. Hersche, et al. Factorizers for Distributed Sparse Block Codes. Neurosymbolic Artificial Intelligence, 2024\". Would be interesting to see how HLB can handle sparse (block-wise) codes.\n\n3) The other key issue with the paper is flaws in its presentation. Some of them are:\n    - The sentences starting at lines 39 and 40 are fully out of place.\n    - Line 107 mentions an “unburdening” operation, clearly referring to “unbinding”.\n    - Line 197 \"HLBuses\" needs spacing\n    - In Theorem 3.1, the \\cdot multiplication notation was used in place of the \\odot for element-wise multiplication used otherwise in the paper.\n     - Properties 3.1 is formulated in a weird way: “Let x sampled from omega holds the following properties…”\n     - In properties 3.1, it seems that an expectation operator is missing in the final property concerning the L2-norm of x sampled from MiND.\n\n4) The blue horizontal strip at the top of Figure 4 is a weird anomaly which was not addressed by the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1:** The noted work is indeed valuable, though we can not implement it's experiments in the short rebuttal time. We will add the following paragraph to the manuscript. \n\n> As noted in (Steinberg and Sompolinsky), most VSAs can be viewed as a linear operation where $\\mathcal{B}(a,b) = a^\\top G b$ and $\\mathcal{B}^*(a,b) = a^\\top F b$, where $G$ and $F$ are $d \\times d$ matrices. Hypothetically, these matrices could be learned via gradient descent, but would not necessarily maintain the neuro-symbolic properties of VSAs without additional constraints. Still, the framework is useful as VTB, HRR, MAP, HLB, and the original TPR all fit within this generalized representation. By choosing $G$ and $F$ with specified structure, we can change the computational complexity from $\\mathcal{O}(d^2)$ (like TPR) to log-linear (like HRR), or $\\mathcal{O}(d)$ for HLB and MAP. \n\n**W2** We will add a discussion of all these relevant related works to the paper and the wide and growing interest and applicability of VSAs in deep learning. \n\nWe have experiments for MAP-B in progress answering a question of reviewer xpT1. Our available computing resources are limited as we are trying to work through the MIMOConv code and make sure that we have altered it correctly and scheduled an experiment. \n\n\n\n\n**W3:** Thank you for the typo identifications, they have been corrected! \n\n**W4:** We were not able to determine why the non-projected Hadamard binding seems to work well for seemingly random and arbitrary dimension sizes of $d$ (not for a lack of trying, we spent about a month trying to understand what was happening without success). In all cases, our projected Hadamard ($\\eta^\\pi$ noise term) has lower error and behaves consistently across $\\rho$ and $d$, and resolved the asperity we saw with the projection-less Hadamard. For this reason, our final HLB is superior to the intermediate method, so we did not consider it further. We will add this context to that appendix section. \n\n**Q1:** see W1\n\n**Q2:** see W2\n\n**Q3:** see W4\n\n**Q4:** Yes, we re-used the hyper-parameters from the prior papers. These were primarily the network architecture size and number of layers. All were trained with Adam and used the standard recommended learning rate. \n\n**Q5:** The rescaling is useful as it allows the designing of a larger system to easily reason about their architecture. For example, if the unscaled dot product went into a softmax or other non-linearity, the expected behavior would change when the number of neurons/dimension $d$ changed. Having the scaling factor means that one can always (subject to noise) expect near-zero/one values for missing/present inputs. This is also critical to avoid vanishing gradients in the backward pass of a differentiable system.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cc4vqkG8bu", "reviewer": "Reviewer_FSGF", "summary": "The paper introduces a new Vector Symbolic Architecture (VSA) termed Hadamard-derived Linear Binding (HLB), aimed at enhancing computational efficiency and performance in both classical VSA tasks and deep learning applications. VSAs involve binding two vectors to create a new vector in the same space, supporting symbolic operations like binding and unbinding, which is crucial for neuro-symbolic AI.\n\nTraditional VSAs, such as Tensor Product Representation (TPR) and Holographic Reduced Representation (HRR), have limitations like computational complexity or numerical stability issues. In contrast, HLB leverages the Hadamard transform, ensuring linear complexity for binding and addressing these drawbacks.", "questions": "Since I am not familiar with this VSA domain, I'm eager to understand the problem setting in the experiment sections 4.2.1 and 4.2.2. Could the author elaborate with simple example on these tasks?", "limitations": "The work has no negative societal impacts.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well organized and the concepts are clearly explained.\n- The paper details theoretical foundations, derivation processes, and empirical evaluations demonstrating HLB's efficacy across various tasks. It concludes with implications for both classical symbolic AI and modern deep learning systems.", "weaknesses": "I do not observe a clear weakness", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We will add the explanations below to the manuscript to provide motivating reasons for each approach. \n\n**4.2.1:**\n> When running on low-power computing environments, it is often desirable to offload the computation to a third-party cloud environment to get the answer faster and use fewer local resources. However, this may be problematic if one does not fully trust the available cloud environments. Homomorphic encryption (HE) is the ideal means to alleviate this problem, providing cryptography for computations. HE is currently more expensive to perform than running a neural network itself, defeating its own utility in this scenario. CSPS provides a heuristic means of obscuring the nature of the input (content), and output (number of classes/prediction),  while also reducing the total local compute required. \n\n**4.2.2:**\n>Extreme Multi-label  (XML) is the scenario where, given a single input of size $d$, $C >> d$ classes are used to predict. This is common in e-commerce applications where new products need to be tagged, and an input on the order of $d \\approx 5000$ is relatively small compared to $C \\geq $ 100,000 or more classes. This imposes unique computational constraints due to the output space being larger than the input space and is generally only solvable because the output space is sparse --- often less than 100 relevant classes will be positive for any one input. VSAs have been applied to XML by exploiting the low positive class occurrence rate to represent the problem symbolically.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We are pleased all reviewers are interested in the paper and found it novel and significant in its results. All feedback was valuable and has been incorporated into a revised manuscript, with responses inline to each reviewer's individual questions. xpT1 please note your answers can be found in the one-page PDF due to formatting limitations of OpenReview. 

In summary, reviewers identified some typos and sections where additional wording/content would help the reader understand the work better and follow the paper without having to refer to additional resources. Assuming the historical extra camera-ready page for NeurIPS, this space was used to add such additional text. 

Two reviewers noted that other deep learning+ VSA architectures have been proposed, which could benefit from our VSA being applied to them. We are attempting to test some of these but coding/compute time is limited in the rebuttal window. All of these noted works will be added to the manuscript. In addition, additional results have been included in the rebuttal on MAP with binary initialization that shows our method's improvement over the MAP VSA is due to more than just the binary initialization.

Meta-review: ## Summary of the paper
This paper proposes a novel vector symbolic architecture (VSA) called Hadamard-derived Linear Binding (HLB) inspired by previous works on tensor product representations (TPR) and addresses some of their challenges with the deep learning architectures. The paper leverages the Walsh Hadamard transform for vector binding to learn vector symbolic representations. The paper empirically shows superior results on the typical VSA benchmark datasets and tasks.

## Verdict

Overall, the paper is well-written, and the approach proposed is novel and relevant to the broader AI/ML community. It touches upon an interesting problem of learning better VSAs. The results are convincing and show significant improvements over the previous TPR approaches. This work reduces the computational complexity of binding and unbinding from log-linear (HRR) to linear (HLB), which can be impactful. The reviewers had some concerns and questions, but the authors did a very good job addressing them during the rebuttal. Thus, I recommend this paper for acceptance.

There are some fixes I would recommend the authors to do for the camera-ready version of the paper:
1. Further clarification of the motivation, mathematical derivation, and experiments have strengthened this paper as pointed out by the reviewers. 
2. (Minor) There are some typos in the paper, please fix them, for example, the sentence at the end of line 61 seems unfinished.
Decision: Accept (poster)