$$B_{s_{\bullet}} \sim \mathbf{m} \approx \sum_{i, s_{\bullet} = s_i} \mathbf{o}_i + \text{unknown},$$

where **unknown** $\stackrel{\text{def}}{=} \sum_{s_{\bullet} \neq s_i} B_{s_{\bullet}} B_{s_i} \mathbf{o}_i$ is an “unknown” vector, i.e., a vector that has, in the general case, no similarity with the other vectors.

In other words, the unbinding operation makes it possible to retrieve up to an orthogonal vector **unknown** the set, i.e., the additive superposition of all objects $\mathbf{o}_i$ associated with a given subject $\mathbf{s}_{\bullet}$, while $B_{s_{\bullet}} \sim \mathbf{m} = \text{unknown}$ if none.

Then using a similarity operation:

$$B_{s_{\bullet}} \sim \mathbf{m} \cdot \mathbf{o}_{\bullet} = \delta_{s_{\bullet} \to \mathbf{o}_{\bullet}} + \nu(O(1/d^{1/4}))$$

allows to check whether the value $\mathbf{o}_{\bullet}$ is associated to the key $\mathbf{s}_{\bullet}$. Here $\nu(O(1/d^{1/4}))$ comes from the unbinding operation uncertainty.

This is done up to a level of noise of $O(1/d^{1/4})$, as derived in Appendix C (while the dot-product with the unknown vector is of negligible magnitude with respect to the former source of uncertainty), which is rather high with respect to the similarity precision, which is $O(1/d)$, as observed numerically [443]; however, in biological neuronal networks, where the dimension is an order of magnitude higher, this is no longer a limitation because $d$ is high.

This allows us to detect if the information is in the table in one step if this is the case. However, as in the previous case, no mechanism allows to explicitly retrieve the value of $\mathbf{o}_i$, or to generate the enumeration of the map subjects or objects.

In the literature, the notion of clean-up memory corresponds to auto-associative memory that retrieves an exact “clean-up” value of an existing symbol, given an approximate or noisy input of this symbol [472]. A step further, the notion of hetero-associative memory corresponds to storing input-output relation ships [505]. It must be noted that in the NENGO simulator of the Neural Engineering Framework (NEF) hetero-associative memory the biologically plausible implementation is not directly based on the present binding/bundling algebraic mechanism but an input/output architecture with suitable connections is used instead. Each input unit has an encoding vector in which input weights are tuned to fire for a specific key and drive a connected output vector that is optimized to estimate the value associated with the related key [505]. An associative memory of structured knowledge has been studied in details, for an holographic reduced representation by [469], quantifying, depending on the design parameters, the memory performances.

This algebraic construction also makes it possible to retrieve the subjects associated with a given object, because of the commutator $\mathbf{B}_{\leftrightarrow}$, such that

$$\mathbf{B}_{\leftrightarrow} \mathbf{B}_{\mathbf{o}_i} \mathbf{s}_i = \mathbf{B}_{\mathbf{s}_i} \mathbf{o}_i,$$

yielding

$$\mathbf{m}_{\leftrightarrow} \stackrel{\text{def}}{=} \mathbf{B}_{\leftrightarrow} \mathbf{m} = \sum_i B_{\mathbf{o}_i} \mathbf{s}_i,$$

which is now the numerical grounding of the reciprocal map $\{\mathbf{o}_1 \to \mathbf{s}_1, \dots, \mathbf{o}_i \to \mathbf{s}_i, \dots, \mathbf{o}_N \to \mathbf{s}_N\}$.

The algebraic construction also offers the notion of the identity vector $\mathbf{i}$, with $\mathbf{B}_{\mathbf{i}} = \mathbf{I}$, so that

$$\mathbf{s}_i = \mathbf{i} \to B_{\mathbf{s}_i} \mathbf{o}_i = \mathbf{o}_i.$$

In other words, the binding reduces to a superposition. Theoretical details underlying the implementation of such associative memories are available in [472].

As for the previous structure, this obviously generalizes to weighted symbols $\hat{s}_i$ and an approximate input $\mathbf{s}_{\bullet} \approx \hat{s}_i$, allowing us to retrieve the object $\mathbf{o}_i$ weighted by either the modality weighting or the input approximation, indistinctly.

There are several solutions used to define such binding, unbinding, and commutator operators. A proposed solution is developed in Appendix C after the work in [203], which was completed by [335]. This design choice is guided by the fact that we need to avoid spurious inferences: With a binding commutative operator (such as the convolution operator), $\mathbf{B}_{\mathbf{o}_i} \mathbf{s}_i$ would equal $\mathbf{B}_{\mathbf{s}_i} \mathbf{o}_i$, which could generate nonsense deductions (e.g., for a driver-vehicle map, this would mean that if Ming-Yue drives a bicycle, then the bicycle drives Ming-Yue unless some additional mechanism is considered to avoid such nonsense). The proposed VTB algebra avoids such caveats (see [443] for a
recent comparison of different VSAs)$^{26}$. A commutative binding operator can be used for auto-associative memory [472] or if key and values do not belong to the same symbol set, e.g., considering "symbol id'' and "symbol value '' [122].

This associative memory mechanism has an interesting biological interpretation: It implements an associative
memory in the biological sense, with the association stored in a distributed way, and activating the associative
memory with an input **s**<sub>•</sub> allows us to retrieve the associated symbol. This is what happens in several biological
mechanisms, as reviewed, for instance, in [159].

In particular, a structure of the form

$$
\mathbf{m} \stackrel{\text{def}}{=} \sum_n B_{s_i} s_i
$$

that maps an object onto itself allows the retrieval of an exact symbol from an approximate input, solving the caveats
induced by using only a superposition mechanism that was presented previously. This is exactly what is expected in
an associative encoder (e.g., a Hopfield network); if a symbol is close to an existing symbol, the associative memory
will output a weighted version of the symbol.

At the computer programming level, this corresponds to a “map” container (e.g., a Map in JavaScript or a dictionary() in Python), again with only insertion and retrieval methods, and without intrinsic iterators.

To take this a step further, we can propose a complementary functionality, defining an additional symbol “some-
thing” whose numerical grounding is fixed to any new random vector σ that is never used elsewhere. This allows
us to enhance the information to be obtained as follows: Each time a piece of information **s**<sub>*i*</sub> → **o**<sub>*i*</sub> is added, we also
add **s**<sub>*i*</sub> → σ and σ → **o**<sub>*i*</sub>, i.e., we make explicit the fact that **s**<sub>*i*</sub> and **o**<sub>*i*</sub> are defined in this table, which can be retrieved
in one step, without the need to enumerate the different elements. In such a case,

$$
\mathbf{m}_{s_j} \stackrel{\text{def}}{=} \sum_{i, s_j = s_i} \mathbf{o}_i = P_{\sigma \perp} B_{s_j} \mathbf{m} + \mathbf{unknown},
$$

where $P_{\sigma \perp} \stackrel{\text{def}}{=} \mathbf{I} - \sigma \sigma^T$ is the projection onto the orthogonal of $\sigma$, i.e., we must eliminate the symbol "something" from the expected values.

B.3. Associative network

We also can consider for *N* correspondences {**s**<sub>1</sub> → **o**<sub>1</sub>, ..., **s**<sub>*i*</sub> → **o**<sub>*i*</sub> ... **s**<sub>*N*</sub> → **o**<sub>*N*</sub>} between subjects and objects, an associative network of the form:

$$
\mathbf{M} \stackrel{\text{def}}{=} \sum_i \mathbf{o}_i \mathbf{s}_i^T,
$$

which is no more a vector, but a matrix, allowing one to explicitly retrieve the object since:

$$
\mathbf{M} \mathbf{s}_i = \|\mathbf{s}_i\|^2 \mathbf{o}_i + \nu((N-1)/d),
$$

as obtained from obvious algebra.

This corresponds to a macroscopic implementation of associative networks, as proposed, e.g. in [122]. With
respect to the previous associative map we recover directly the object value up to a scale and additive noise, beyond
only testing if it is in the map or not.

It is worth noticing that **M**^T allows to retrieve keys associated with a given value, while we also can consider a
"multi-map" i.e. associate the bundling of several values to a given key.

B.4. Indexed and chained list

B.4.1. Construction of indexes

In order to define an indexed list, we need indexes, i.e., a mechanism that generates ordinal values. Our main
purpose here is to make explicit that what has been developed using convolution operators [275] still holds with
VTB. We fix the symbol grounding of the "zero" symbol $v_0$, which is never used elsewhere, and define the following
recursively:

<footnote n="26"><sup>26</sup>An alternative to VTB algebra is called MBAT algebra; it requires matrix inversion instead of transposition, and thus it is less efficient.</footnote>
$$v_{n+1} \stackrel{\text{def}}{=} B_{v_0} v_n,$$

i.e., the $(n+1)$-th ordinal value is obtained by binding the n-th, and we easily obtain, from a few algebra operations,

$$B_{v_p} v_q = B_{v_q} v_p = B_{v_{p+q}} v_0, \quad B_{v_p} v_q \stackrel{\sim}{=} B_{v_q} v_p \stackrel{\sim}{=} B_{v_{p-q}} v_0.$$

In particular, $v_{n-1} \stackrel{\sim}{=} B_{v_0} v_n$, so that the definition holds for $n \in \mathcal{Z}$.

Here, we only consider the minimal material needed to build an indexed list; numerical information in the brain is a much more complex subject [365] beyond the scope of this work.

In fact, what has not been noticed previously is the fact that the accumulation of binding operations leads to an important increase of noise, more precisely:

$$v_n = (B_{v_0})^n v_0 + v(O(n/d^{1/4}))$$

so that for as soon as $n^4 > d$ the noise order of magnitude is higher than 1, i.e., the value order of magnitude. However, this is not a problem in practice because as soon as we do not repeat the calculation twice, i.e., we do not redraw the values, but keep trace of the previous pre-calculated values, so that each “number” has a unique vector as identifier.

### B.4.2. Indexed list

We can now define an indexed list or array, often called a vector, since the previous mechanism allows us to generate a “counter” that can be incremented or decremented using the binding or unbinding operator.

To this end, an associative map indexed by these ordinals can be managed as a list whose values can be enumerated. Such a representation is also present at several cognitive levels when considering temporal sequences, actions, or any enumeration. This is also the tool that allows us to enumerate all elements of a symbol set $S$, which was defined previously, or the subjects of an associative map.

To make this mechanism explicit, let us consider a list $l \stackrel{\text{def}}{=} \sum_i B_{v_i} l_i$, and a variable index $k$. A construct of the form

for $k \leftarrow v_0$; while $\|B_k l\| > 0$; next $k \leftarrow B_{v_0 k}$ do

$l_i \leftarrow B_k \sim l$

...

end for

allows us to enumerate$^{27}$ all elements, this being indeed only an algorithmic ersatz to illustrate the mechanism beyond the biologically plausible implementation of sequential memory organization.

At the biological plausibility level, following [159], we may consider that the brain can have three kinds of memory: associative, sequential, and hierarchical (called schematic by the author of [159]) memory. All three memory types are present and required for cognitive processes. The VSA approach provides both associative and sequential memory. Let us consider the third type of memory, which has not, to the best of our knowledge, been addressed with regard to VSAs.

At the computer programming level, this corresponds to an extensible “array” (e.g., a `std::vector` in C++ or `java.util.AbstractList` in Java), with basic edition and retrieval methods available.

### B.4.3. Chained list

We can also define a chained list using an associative memory of the form

first $\rightarrow$ second
second $\rightarrow$ third
...
last $\rightarrow$ END + first

where every value of the list acts as a key to the value of its successor in the list, thus enumerating the values. END

<footnote>$^{27}$In fact, considering $l \stackrel{\text{def}}{=} \sum_i B_{v_i} l_i + B_{v_{-1}} \lambda$, where $\lambda$ is the list length, which is updated when an element is added or deleted, would improve the algorithmic ersatz implementation, which is not the issue here.</footnote>
is a predefined specific symbol that makes it possible to know when the list ends that we can superpose to a pointer to the first value in case we need to iterate through the entire list again.

We also could have considered multiple binding<sup>28</sup>, as proposed in [335].

## Appendix C. Using VTB algebra

At the mesoscopic level, symbols represent a numerical grounding to real or complex vectors of dimension *d*, with each numerical grounding corresponding to some distributed activity of a spiking neuronal assembly and each algebraic operation corresponding to some transformation of this activity.

Let us review and further develop one of the algebras used to manipulate such symbols at an abstract level in this paper: vector-derived transformation binding (VTB) algebra. We follow [203] and complete the developments in that paper by deriving the different operations at the component level, yielding an optimal implementation and making explicit the computational complexity and related first-order noise. This is in particular used in section 4 to derive the macroscopic computations.

We also have to reconsider the binding output magnitude since vector magnitudes correspond to a belief value, as discussed in section 2.2.

We consider that $d \stackrel{\text{def}}{=} (d')^2$ for some integer $d'$; thus, it is a quadratic number and we start from the standard definition of the VTB binding operation:

$$ \mathbf{z} \stackrel{\text{def}}{=} \mathbf{B}_y \mathbf{x}, $$

where $\mathbf{B}_y$ is a block-diagonal matrix defined as follows:

$$ \mathbf{B}_y \stackrel{\text{def}}{=} \begin{bmatrix} \mathbf{B}'_y & 0 & \dots & 0 \\ 0 & \mathbf{B}'_y & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & \mathbf{B}'_y \end{bmatrix}, \quad \text{with } \mathbf{B}'_y \stackrel{\text{def}}{=} \sqrt{d'} \begin{bmatrix} y_1 & y_2 & \dots & y_{d'} \\ y_{d'+1} & y_{d'+2} & \dots & y_{2d'} \\ \vdots & \vdots & \ddots & \vdots \\ y_{d-d'+1} & y_{d-d'+2} & \dots & y_d \end{bmatrix}, $$

or equivalently<sup>29</sup>, for $i = 1 \dots d$,

$$ \left\{ \begin{array}{l} [\mathbf{z}]_i \stackrel{\text{def}}{=} \mathbf{B}_y \mathbf{x} = \sqrt{d'} \sum_{k=1}^{k=d'} [\mathbf{y}]_{k+\beta(i)} [\mathbf{x}]_{k+\alpha(i)}, \\ [\mathbf{B}_y]_{ij} = \sqrt{d'} \delta_{i \le d'} \text{ and } j \le d' [\mathbf{y}]_{k+\beta(i)-\alpha(i)}, \end{array} \right. \quad (1) \\ \text{written} \quad \left\{ \begin{array}{l} \alpha(i) \stackrel{\text{def}}{=} d' ((i-1) \text{ div } d'), \\ \beta(i) \stackrel{\text{def}}{=} d' ((i-1) \text{ mod } d'), \end{array} \right. $$

with the matrix multiplication explicitized as a sum, which can be easily verified. Here, $[\mathbf{z}]_k$ stands for the k-th coordinate of the vector $\mathbf{z}$, and $\delta_P$ is 1 if $P$ is true; otherwise, it is 0. This is our basic definition, and reformulating the VTB operation using (1) will allow us to better understand its properties.

This operation is bi-linear in $\mathbf{x}$ and $\mathbf{y}$, and thus it is distributive with respect to addition and the scalar product.

Since $\mathbf{y}$ and $\mathbf{x}$ are random vectors $[\mathbf{z}]_i$, in (1) is estimated up to a standard-deviation<sup>30</sup> of $O(1/d^{1/4})$ which is an order of magnitude higher than for similarity estimation, which related standard-deviation was of $O(1/d)$. This also

$$ l = B_{\text{value}} v_1 + B_{\text{next}} (B_{\text{value}} v_2 + B_{\text{next}} (\dots + B_{\text{next}} (\text{list-end}))), $$

<footnote n="28"><sup>28</sup>In such a case, a list of the form $l = [v_1, v_2, \dots]$ is encoded without associative memory as</footnote>

<footnote>allowing us to obtain by unbinding the list's head value and its tail value, and allowing us to detect its end. This corresponds, for instance, to the `rdf:first`, `rdf:rest`, and `rdf:nil` symbols of the RDF representation. However, as discussed in Appendix C, chaining unbinding operations is not numerically very robust due to the additional residual noise.</footnote>

<footnote n="29"><sup>29</sup>All algebraic derivations reported here are straightforward and were verified using a piece of symbolic algebra code available at https://raw.github.com/vthierry/onto2spa/main/figures/VTB-algebra.mpl.</footnote>

<footnote n="30"><sup>30</sup>Each component $[\mathbf{z}]_i$ corresponds to the computation of a dot-product between two $d'$ dimensional vectors, yielding a standard-deviation of $O(1/d')$, renormalized by $\sqrt{d'} = d^{1/4}$, leading to the final order of magnitude. As for similarity estimation, chi-square distribution is approximated by a normal distribution of the same standard-deviation, which is known as a conservative choice.</footnote>
explains the relatively limited numerical performances of simulations with $d < 10^3$, as reported, for instance, in [443].

The $\sqrt{d'}$ renormalization factor allows $\mathbf{z}$ to have a unary order of magnitude$^{31}$. However, the magnitude is not exactly one, but$^{32}$:

$$ \|\mathbf{B}_{\mathbf{y}} \mathbf{x}\| \approx \begin{cases} \|\mathbf{y}\| \|\mathbf{x}\| & \text{if } \mathbf{y} \perp \mathbf{x} \\ \sqrt{2} \|\mathbf{y}\| \|\mathbf{x}\| & \text{if } \mathbf{y}\|\mathbf{x} \end{cases} $$

which is of importance in our context since the magnitude of the vector corresponds to the $\tau$ value.

At the algorithmic implementation level, the calculation of $\mathbf{z}$ is performed in$^{33}$ $O(d^{3/2})$ operations, and the $\mathbf{y}_{k+\beta[i]}$ and $\mathbf{x}_{k+\alpha[i]}$ indexing can be tabulated in two fixed look-up tables $\beta[i]$ and $\alpha[i]$, avoiding any additional calculations. Furthermore, the fact that $\sqrt{d'}$ is an integer makes it possible to limit numerical approximations in order to improve numerical conditioning. This will be verified for all other explicit formulae later in this paper. We make explicit these formulae in detail not to re-implement these operations, which are already available in the NENGO simulator, but to study in detail their complexity and their precision, with the goal of proposing a macroscopic algorithmic ersatz of these operations.

This can be compared to the fastest binding operation, which is convolution implemented via the fast Fourier transform [443], and thus it has a complexity of $O(d \log(d))$:

<table><thead><tr><th></th><th>d = 10</th><th>d = 100</th><th>d = 500</th><th>d = 1000</th><th>d = 10000</th></tr></thead><tbody><tr><td>VTB</td><td>10<sup>1.5</sup></td><td>10<sup>3</sup></td><td>10<sup>4</sup></td><td>10<sup>4.5</sup></td><td>10<sup>6</sup></td></tr><tr><td>Convolution</td><td>10<sup>1.4</sup></td><td>10<sup>2.6</sup></td><td>10<sup>3.5</sup></td><td>10<sup>3.8</sup></td><td>10<sup>5</sup></td></tr><tr><td>Ratio = <sup>√d</sup>/<sub>log(d)</sub></td><td>≈ 1</td><td>≈ 2</td><td>≈ 3.5</td><td>≈ 4.5</td><td>≈ 10</td></tr></tbody></table>

However, at the implementation level, we are going to observe that due to compiler and on-line processor optimization, the average computation time is an order of magnitude lower, because the VTB binding formula in eq. (1) is easy to optimize.

As stated in [203] and reviewed in [335], the key point is that this binding operation generates a new vector $\mathbf{z}$ that is almost orthogonal to $\mathbf{x}$ and $\mathbf{y}$:

$$ (\mathbf{B}_{\mathbf{y}} \mathbf{x}) \cdot \mathbf{x} \approx 0, $$

and this operation is neither commutative,

$$ (\mathbf{B}_{\mathbf{x}} \mathbf{y}) \cdot (\mathbf{B}_{\mathbf{y}} \mathbf{x}) \approx 0, $$

nor associative$^{34}$, in the following sense:

$$ (\mathbf{B}_{(\mathbf{B}_{\mathbf{z}} \mathbf{y})} \mathbf{x}) \cdot ((\mathbf{B}_{\mathbf{z}} \mathbf{B}_{\mathbf{y}}) \mathbf{x}) \approx 0. $$

$$ \begin{aligned} \|\mathbf{B}_{\mathbf{y}} \mathbf{x}\|^2 &= d' \sum_{i=1}^{d} \left( \sum_{k=1}^{k=d'} [\mathbf{y}]_{k+\beta(i)} [\mathbf{x}]_{k+\alpha(i)} \left( \sum_{l=1}^{l=d'} [\mathbf{y}]_{l+\beta(i)} [\mathbf{x}]_{l+\alpha(i)} \right) \right) \\ &= d' \sum_{ik} [\mathbf{y}]_{k+\beta(i)} [\mathbf{x}]_{k+\alpha(i)} [\mathbf{y}]_{l+\beta(i)} [\mathbf{x}]_{l+\alpha(i)} \\ &= d' \sum_{ik} ([\mathbf{y}]_{k+\beta(i)} [\mathbf{x}]_{k+\alpha(i)})^2 + \text{noise}, \end{aligned} $$

<footnote>$^{31}$ More precisely, two random normalized vectors of dimension $d$ drawn from a random normal distribution of independent samples verify that $\mathbf{x} \cdot \mathbf{y} \sim \mathcal{N}(0, 1/d')$, as described in subsection 2.1. Then, applying a permutation on all indices on a random vector $\mathbf{x}$ yields another random vector, which is not correlated with any vector $\mathbf{y}$ if $\mathbf{x}$ is not. Thus, when computing the components $[\mathbf{z}]_i$ in (1) for two general random vectors $\mathbf{x}$ and $\mathbf{y}$, we compute the dot product of two random vectors of dimension $d'$ renormalized by $\sqrt{d'}$, and thus this dot product comes from the distribution $\mathcal{N}(0, 1)$; this corresponds to drawing a random vector unary on average.</footnote>

<footnote>$^{32}$ We can easily derive:</footnote>

<footnote>the 1st line being obtained by substitution from the definition, the 2nd line by expansion, and the 3rd line being obtained by considering that if $k \neq l$ we are multiply four almost independent random distribution which product expectation cancel in average (i.e., formally: $E[Y_k X_k Y_l X_l] = E[Y_k] E[X_k] E[Y_l] E[X_l] \approx 0$ by construction). If $\mathbf{y} \perp \mathbf{x}$ we are left with numerically approximating the mean of the square of normal distribution. i.e., its second momentum, equal to 1. If $\mathbf{y} \| \mathbf{x}$ we are left with numerically approximating the mean of the fourth power of a normal distribution, i.e., its fourth momentum, equal to 2 (it is known that if $\mathbf{X}$ is centered normal variable of unary standard deviation, then $E[X^{2n}] = (2 - 1)!!$ where !! denotes the double factorial, i.e., the product of all numbers down to 1 which have the same parity as the argument.)</footnote>

<footnote>$^{33}$ Each of the $d$ components $[\mathbf{z}]_i$ requires a dot product of size $d' = \sqrt{d}$ that is not factorizable in the general case, since involving different elements of the vectors as readable on the matrix form.</footnote>

<footnote>$^{34}$ Of course, as a product of matrices, the combination of three bindings or two bindings operations and a vector is associative, but the operator $\mathbf{B}$ itself is not, as made explicit in the formula.</footnote>
These properties ensure that we do not infer spurious derivations.

To take this a step further, in the real case, the random matrix is almost orthogonal, i.e.,

$$ \mathbf{B}_y^\top \mathbf{B}_y \approx \mathbf{I}, $$

for the same reasons evoked above<fnref n="35" />.

We thus define

$$ \mathbf{B}_{y} \stackrel{\text{def}}{=} \mathbf{B}_{y}^{\top} \text{ with } [\mathbf{y}^{\sim}]_{i} \stackrel{\text{def}}{=} [\mathbf{y}]_{\sigma(i)}, $$

with

$$ \sigma(i) \stackrel{\text{def}}{=} 1 + d' ((i - 1) \mod d') + (i - 1) \text{div } d'. $$

In other words, $\mathbf{B}_y^\top$ has the same structure as $\mathbf{B}_y$, except that the vector coordinates are subject to a permutation $\sigma(i)$, which is idempotent ($\sigma(\sigma(i)) = i$) and thus its own inverse, so that if $\mathbf{z}' \stackrel{\text{def}}{=} \mathbf{B}_y \sim \mathbf{x}$, we obtain

$$ [\mathbf{z}']_i = \sqrt{d'} \sum_{k=1}^{k=d'} [\mathbf{y}]_{\sigma(k+\beta(i))} [\mathbf{x}]_{(k+\alpha(i))} $$

(where $\beta(i)$ and $\alpha(i)$ are the indexing defined to calculate $\mathbf{B}_y \mathbf{x}$ explicitly), and this makes it possible to define a left unbinding operation:

$$ \mathbf{B}_{y} \sim (\mathbf{B}_{y} \mathbf{x}) = \mathbf{B}_{y}^{\top} \mathbf{B}_{y} \mathbf{x} = \mathbf{x} + \text{noise} \approx \mathbf{x}. $$

From similar derivations as detailed in footnote³², also verified at the numerical level, we obtain for the magnitude:

$$ \| \mathbf{B}_{y} \sim \mathbf{B}_{y} \mathbf{x} \| \approx \begin{cases} \sqrt{2} \| \mathbf{y} \|^2 \| \mathbf{x} \| & \text{if } \mathbf{y} \perp \mathbf{x} \\ \sqrt{5} \| \mathbf{y} \|^2 \| \mathbf{x} \| & \text{if } \mathbf{y} \| \mathbf{x}, \end{cases} $$

which is to be considered to properly normalize unbinding operations at the mesoscopic level.

The right identity vector $\mathbf{i}$ such that $\mathbf{B}_i = \mathbf{I}$ can be written explicitly as follows:

$$ [\mathbf{i}]_i = \frac{1}{\sqrt{d'}} \delta_{i=\sigma(i)}. $$

In other words, we get $i_B$ by “unfolding” the identity matrix $I'_d$ line by line, writing a 1, then $d$ times 0, then another 1, and so on.

Considering the mirroring matrix $\mathbf{B}_{\leftrightarrow}$, which is defined as

$$ [\mathbf{B}_{\leftrightarrow}]_{ij} \stackrel{\text{def}}{=} \delta_{j=\sigma(i)} $$

(which is thus not block-diagonal in the way that a matrix of the form $\mathbf{B}_y$ is), so that:

$$ \mathbf{B}_{\leftrightarrow} \mathbf{x} = \mathbf{x}^{\sim}, $$

we obtain

$$ \mathbf{B}_{\leftrightarrow} \mathbf{B}_y \mathbf{x} = \mathbf{B}_x \mathbf{y}, \text{ while } \mathbf{B}_{\leftrightarrow} \mathbf{B}_{\leftrightarrow} = \mathbf{I} \text{ and } \mathbf{B}_{\leftrightarrow}^{\top} = \mathbf{B}_{\leftrightarrow}, $$

which makes it possible to define a right unbinding operation:

$$ (\mathbf{B}_x \sim \mathbf{B}_{\leftrightarrow}) (\mathbf{B}_y \mathbf{x}) = \mathbf{B}_x \sim \mathbf{B}_x \mathbf{y} \approx \mathbf{y}, $$

and expand nested binding operations:

$$ \mathbf{B}_{\mathbf{B}_y} \mathbf{x} = \mathbf{B}_{\leftrightarrow} \mathbf{B}_x \mathbf{B}_y. $$

$$ \begin{align*} [\mathbf{B}_y^\top \mathbf{B}_y]_{ij} &= \sum_{k=1}^{d'} [\mathbf{B}_y]_{ki} [\mathbf{B}_y]_{kj} \\ &= d' \sum_{k=1}^{d'} [\mathbf{y}]_{k+\beta(i)-\alpha(i)} [\mathbf{y}]_{k+\beta(j)-\alpha(j)} \\ &= d' \sum_{l=1}^{d'} [\mathbf{y}]_l [\mathbf{y}]_{k+(\beta(j)-\beta(i))-(\alpha(j)-\alpha(i))} \\ &= d' \sum_{l=1}^{d'} [\mathbf{y}]_l [\mathbf{y}]_{k+d' ((j-i) \text{ div } d') - ((j-i) \text{ div } d')} \end{align*} $$

<footnote n="35">³⁵From (1), we derive</footnote>

<footnote>- $[\mathbf{B}_y^\top \mathbf{B}_y]_{ii} = \sum_{l=1}^{d'} [\mathbf{y}]_l^2 = 1 + \text{noise}$; and</footnote>

<footnote>- $[\mathbf{B}_y^\top \mathbf{B}_y]_{ij, i \neq j} = 0 + \text{noise}$, because it is easy to verify that $((j-i) \text{ div } d') - ((j-i) \text{ div } d') \neq 0$ when $i \neq j$, so that the dot product of $d'$ random components of $[\mathbf{y}]_l$ with $d'$ other random components yields approximately normal noise.</footnote>
This could extends the actual binding algebra considering the dual operator $\sim$.

Unfortunately, $\mathbf{B}_{\leftrightarrow}$ is not a binding matrix, i.e., it is not of the form $\mathbf{B}_z$ for some vector $z$, which is easily verified by the fact that some components that must be equal to 0 for a binding matrix are equal to 1 in $\mathbf{B}_{\leftrightarrow}$. Furthermore, the left or right multiplication of a binding matrix by this mirroring matrix does not yield a binding matrix, because of the same observation; components that must be equal to 0 for a binding matrix are equal to 1 in $\mathbf{B}_{\leftrightarrow}$.

Beyond [203], the authors of [335] introduced a vector composition operator $\otimes$ to make explicit the composition of two binding operations, namely,

$$ \mathbf{B}_v = \mathbf{B}_y \mathbf{B}_x \Leftrightarrow \mathbf{v} \stackrel{\text{def}}{=} \mathbf{y} \otimes \mathbf{x}, $$

which can be explicitly written as follows<fnref n="36" />:

$$ [\mathbf{v}]_i = \sqrt{d'} \sum_{k=1}^{k=d'} [\mathbf{y}]_{(i-1)d'+k} [\mathbf{x}]_{1+d' (k-1)+(i-1)} \mod d'. $$

At the algebraic level, the key point is that the product of two binding matrices is still a binding matrix. As a consequence, this composition operator is bi-linear, and thus it is distributive with respect to addition; it is not commutative, but it is associative and commutes with the inversion as follows:

$$ (\mathbf{y} \otimes \mathbf{x}) \sim = \mathbf{x} \sim \otimes \mathbf{y} \sim, $$

while $\mathbf{x} \sim \otimes \mathbf{x} \simeq \mathbf{i}$; all these results can be easily derived by considering usual matrix properties. This allows us to combine two binding matrices without an explicit matrix product in $O(d^{3/2})$ operations only. At the numeric level, since $\mathbf{v}$ is up to a $\sqrt{d'}$ factor, the dot product of segments of random vectors of dimension $d'$, we obtain the same order of magnitude of noise level, as discussed previously. Altogether this can enrich the actual binding algebra to obtain more elegant formulas, in particular when combinations of binding operations are used.

## Using VTB algebra in the complex case

All of the developments described in this section generalize to complex numbers. Although it is not directly used here, such a generalization is of general interest because complex implementations of VSA frameworks have also been considered [443]. Furthermore, it is also of interest to see if our macroscopic implementation could be easily adapted to the complex case.

Stating that two resources are semantically equivalent if the unary vectors are aligned can be written in the complex case as follows<fnref n="37" />:

$$ [\mathbf{B}_v]'_{ij} = \sqrt{d'} \sqrt{d'} \sum_{k=1}^{d'} [\mathbf{y}]_{k+(i-1)} \operatorname{div} [\mathbf{x}]_{(k-1)d'+j}, $$

from which we obtain the desired formula.

$$ \mathbf{x} = \mathbf{y} \Leftrightarrow \mathbf{x} \cdot \mathbf{y} = \sum_i x_i y_i = \cos(\overrightarrow{\mathbf{x}} \cdot \overrightarrow{\mathbf{y}}) = 1 \Leftrightarrow \overrightarrow{\mathbf{x}} \cdot \overrightarrow{\mathbf{y}} = 0 \pmod{2\Pi}, $$

i.e., both unary vectors have the same direction; in other words, they are aligned. If we are in the complex case $\mathbf{x}$ and $\mathbf{y} \in \mathbb{C}^d$, let us consider the canonical embedding in $\mathbb{R}^{2d}$, i.e., we consider the real (Re) and imaginary (Im) parts as two real coordinates, denoting by $\overrightarrow{\mathbf{x}}$ the corresponding vector:

$$ \mathbf{x} \stackrel{\text{def}}{=} (x_1, x_2, \dots)^T \Leftrightarrow \overrightarrow{\mathbf{x}} \stackrel{\text{def}}{=} (\operatorname{Re}(x_1), \operatorname{Im}(x_1), \operatorname{Re}(x_2), \operatorname{Im}(x_2), \dots)^T, $$

where $z^*$ is the conjugate of a complex number $z$, while $<\mathbf{x}|\mathbf{y}>$ stands for the complex inner product:

$$ \begin{aligned} <\mathbf{x}|\mathbf{y}> & \stackrel{\text{def}}{=} \sum_i x_i y_i^* \\ &= \sum_i (\operatorname{Re}(x_i) \operatorname{Re}(y_i) + \operatorname{Im}(x_i) \operatorname{Im}(y_i)) + I (\operatorname{Re}(x_i) \operatorname{Im}(y_i) - \operatorname{Im}(x_i) \operatorname{Re}(y_i)) \\ &= \overrightarrow{\mathbf{x}} \cdot \overrightarrow{\mathbf{y}} + I \overrightarrow{\mathbf{x}}^* \cdot \overrightarrow{\mathbf{y}}, \end{aligned} $$

so that $\operatorname{Re}(<\mathbf{x}|\mathbf{y}>) = \overrightarrow{\mathbf{x}} \cdot \overrightarrow{\mathbf{y}}$ and $\|\mathbf{x}\| = \sqrt{<\mathbf{x}|\mathbf{x}>} = \|\overrightarrow{\mathbf{x}}\| - 2 = \sqrt{\overrightarrow{\mathbf{x}} \cdot \overrightarrow{\mathbf{x}}}$, and since vectors are unary,

$$ <\mathbf{x}|\mathbf{y}> = 1 \Leftrightarrow \overrightarrow{\mathbf{x}} \cdot \overrightarrow{\mathbf{y}} = 1 \Leftrightarrow \overrightarrow{\mathbf{x}} = \overrightarrow{\mathbf{y}} \Leftrightarrow \mathbf{x} = \mathbf{y}, $$

making explicit the obvious fact that unary real or complex vectors are equal if and only if their inner product equals one, while we consider the “angle” of two complex vectors as the angle of their $2d$ real embedding, i.e.,

<footnote n="36">³⁶Since $\mathbf{B}_y$ and $\mathbf{B}_x$ are block-diagonal matrices, it is easy to verify that $\mathbf{B}_v$ is a block-diagonal matrix with a $d' \times d'$ block $\mathbf{B}_{v'} = \mathbf{B}_{y'} \mathbf{B}_{x'}$ using the notation from the beginning of this section, and we can explicitly write that</footnote>

<footnote n="37">³⁷If we are in the real case $\mathbf{x}$ and $\mathbf{y} \in \mathbb{R}^d$, with $\|\mathbf{x}\|_2 = \|\mathbf{y}\|_2 = 1$, then the equality is written as</footnote>
$$x \approx y \Leftrightarrow \langle x | y \rangle \approx 1,$$

while the orientation is usually defined as

$$\hat{xy} \stackrel{\text{def}}{=} \arccos(\text{Re}(\langle x | y \rangle)),$$

as explained in the previous footnote.

Provided that the space dimension *d* is large enough, two randomly chosen different complex vectors **x** and **y**³⁸ will also be approximately orthogonal in the sense that

$$x \neq y \Leftrightarrow \langle x | y \rangle \approx 0.$$

As a consequence, the VTB matrix is almost a unitary matrix, i.e.,

$$B_y^* B_y \approx I,$$

considering the conjugate transpose.

All other algebraic operations are common to both real and complex linear algebra, and this is also the case for other VSA binding operators.

More than just a confirmation, these derivations allow us to observe that using a complex representation would be interesting if the conjugate of a vector could have a semantic interpretation. In that case, if, say, **x** and **y**\* are similar, then $\langle x | y \rangle \approx I$, as easily verified from the previous derivations.

$$\hat{xy} \stackrel{\text{def}}{=} \arccos(\text{Re}(\langle x | y \rangle)).$$

³⁸Considering again the canonical embedding in $\mathbb{R}^{2d}$ and the fact that

$$\langle x | y \rangle = \vec{x} \cdot \vec{y} + I \vec{x}^* \cdot \vec{y},$$

because $\vec{x}$ and thus $\vec{x}^*$ and $\vec{y}$ are random vectors, their dot product almost vanishes; thus, the real and imaginary parts of $\langle x | y \rangle$ also almost vanish.
<table><caption>Table 2: Four symbolic reduction examples.</caption><tr><td>I]:</td><td>{b y: c x: [a b]} {b y: c x: [b a]}]</td></tr><tr><td>P]:</td><td>[ B_(c) ([ a b ]_&lt;1.4±0&gt;)_&lt;1.4±0.044&gt; B_(c) ([ a b ]_&lt;1.4±0&gt;)_&lt;1.4±0.044&gt; ]_&lt;2±0.088&gt;</td></tr><tr><td>R]:</td><td>[ B_(c) (a)_&lt;2±0.062&gt; B_(c) (b)_&lt;2±0.062&gt; ]_&lt;2.8±0.12&gt;</td></tr><tr><td>I]:</td><td>[ {name: a tau: 0.5 sigma: 0.1} [ ] ] {name: a tau: 0.5 sigma: 0.1}]</td></tr><tr><td>P]:</td><td>[ a_<1±0.2&gt; ]_&lt;1±0.2&gt;</td></tr><tr><td>R]:</td><td>a_<1±0.2&gt;</td></tr><tr><td>I]:</td><td>{b y: a x: {u y: a x: [ {name: c tau: 2 sigma: 0.1} ]}</td></tr><tr><td>P]:</td><td>B_(a) (B_(a^) ([ c_<2±0.1&gt; ]_&lt;2±0.1&gt;)_&lt;2±0.066&gt;)_&lt;2±0.065&gt;</td></tr><tr><td>R]:</td><td>c_<8±0.23&gt;</td></tr><tr><td>I]:</td><td>{b y: c x: {b y: c x: {b y: c x: {u y: c x: {u y: c x: a}}}}}</td></tr><tr><td>P]:</td><td>B_(c) (B_(c) (B_(c^) (B_(c^) (a)_&lt;1±0.031&gt;)_&lt;1±0.032&gt;) _&lt;1±0.032&gt;) _&lt;1±0.032&gt;)_&lt;1±0.032&gt;</td></tr><tr><td>R]:</td><td>a_<1±0.19&gt;</td></tr></table>

- The [I] line corresponds to the Input of the symbolic expression in weak JSON syntax.
- The [P] line corresponds to the Parsed expression.
- The [R] line corresponds to the Reduced expression.
Bundlings are represented as a list between [ ], Binding using the usual syntax, while the < τ ± σ > construct allows to specify the belief value, when not equal to the default < 1 ± 0 > value.

<table><tr><td>1</td></tr><tr><td>2</td></tr><tr><td>3</td></tr><tr><td>4</td></tr><tr><td>5</td></tr><tr><td>6</td></tr><tr><td>7</td></tr><tr><td>8</td></tr><tr><td>9</td></tr><tr><td>10</td></tr><tr><td>11</td></tr><tr><td>12</td></tr><tr><td>13</td></tr><tr><td>14</td></tr><tr><td>15</td></tr><tr><td>16</td></tr><tr><td>17</td></tr><tr><td>18</td></tr><tr><td>19</td></tr><tr><td>20</td></tr><tr><td>21</td></tr><tr><td>22</td></tr><tr><td>23</td></tr><tr><td>24</td></tr><tr><td>25</td></tr><tr><td>26</td></tr><tr><td>27</td></tr><tr><td>28</td></tr><tr><td>29</td></tr><tr><td>30</td></tr><tr><td>31</td></tr><tr><td>32</td></tr><tr><td>33</td></tr><tr><td>34</td></tr><tr><td>35</td></tr><tr><td>36</td></tr><tr><td>37</td></tr><tr><td>38</td></tr><tr><td>39</td></tr><tr><td>40</td></tr><tr><td>41</td></tr><tr><td>42</td></tr><tr><td>43</td></tr><tr><td>44</td></tr><tr><td>45</td></tr><tr><td>46</td></tr><tr><td>47</td></tr><tr><td>48</td></tr><tr><td>49</td></tr><tr><td>50</td></tr><tr><td>51</td></tr></table>

<table><tr><td>1</td></tr><tr><td>2</td></tr><tr><td>3</td></tr><tr><td>4</td></tr><tr><td>5</td></tr><tr><td>6</td></tr><tr><td>7</td></tr><tr><td>8</td></tr><tr><td>9</td></tr><tr><td>10</td></tr><tr><td>11</td></tr><tr><td>12</td></tr><tr><td>13</td></tr><tr><td>14</td></tr><tr><td>15</td></tr><tr><td>16</td></tr><tr><td>17</td></tr><tr><td>18</td></tr><tr><td>19</td></tr><tr><td>20</td></tr><tr><td>21</td></tr><tr><td>22</td></tr><tr><td>23</td></tr><tr><td>24</td></tr><tr><td>25</td></tr><tr><td>26</td></tr><tr><td>27</td></tr><tr><td>28</td></tr><tr><td>29</td></tr><tr><td>30</td></tr><tr><td>31</td></tr><tr><td>32</td></tr><tr><td>33</td></tr><tr><td>34</td></tr><tr><td>35</td></tr><tr><td>36</td></tr><tr><td>37</td></tr><tr><td>38</td></tr><tr><td>39</td></tr><tr><td>40</td></tr><tr><td>41</td></tr><tr><td>42</td></tr><tr><td>43</td></tr><tr><td>44</td></tr><tr><td>45</td></tr><tr><td>46</td></tr><tr><td>47</td></tr><tr><td>48</td></tr><tr><td>49</td></tr><tr><td>50</td></tr><tr><td>51</td></tr></table>
<table><caption>Table 3: Mesoscopic versus macroscopic noise estimation.</caption><thead><tr><th>Dimension:</th><th>100</th><th>400</th><th>1024</th><th>2500</th><th>4096</th><th>10000</th></tr></thead><tbody><tr><td colspan="7">Mesoscopic bias and standard-deviation estimation over 1000 samples</td></tr><tr><td>B<sub>y</sub>x · x</td><td>0.00041±0.1</td><td>-0.002±0.052</td><td>-7.9e-05±0.031</td><td>-0.00014±0.02</td><td>-0.00062±0.015</td><td>0.00061±0.0097</td></tr><tr><td>B<sub>y</sub>~B<sub>y</sub>x · x</td><td>-0.0007±0.24</td><td>-0.0068±0.11</td><td>0.004±0.071</td><td>0.0016±0.042</td><td>-0.0002±0.035</td><td>0.0013±0.022</td></tr><tr><td>B<sub>y</sub>y · y</td><td>0.0005±0.14</td><td>0.0014±0.072</td><td>0.0011±0.045</td><td>0.00016±0.028</td><td>0.00025±0.023</td><td>0.0006±0.014</td></tr><tr><td>B<sub>y</sub>~B<sub>y</sub>y · y</td><td>-0.0007±0.24</td><td>-0.0068±0.11</td><td>0.004±0.071</td><td>0.0016±0.042</td><td>-0.0002±0.035</td><td>0.0013±0.022</td></tr><tr><td colspan="7">Macroscopic prediction of τ ± σ (i.e. standard-deviation)</td></tr><tr><td>B<sub>y</sub>x · x</td><td>1±0.11</td><td>1±0.081</td><td>1±0.063</td><td>1±0.051</td><td>1±0.045</td><td>1±0.036</td></tr><tr><td>B<sub>y</sub>~B<sub>y</sub>x · x</td><td>1±0.23</td><td>1±0.16</td><td>1±0.13</td><td>1±0.1</td><td>1±0.09</td><td>1±0.072</td></tr><tr><td>B<sub>y</sub>y · y</td><td>1±0.11</td><td>1±0.081</td><td>1±0.063</td><td>1±0.051</td><td>1±0.045</td><td>1±0.036</td></tr><tr><td>B<sub>y</sub>~B<sub>y</sub>y · y</td><td>1±0.23</td><td>1±0.16</td><td>1±0.13</td><td>1±0.1</td><td>1±0.09</td><td>1±0.072</td></tr><tr><td colspan="7">Standard-deviation over-prediction</td></tr><tr><td>B<sub>y</sub>x · x</td><td>1.1</td><td>1.5</td><td>2</td><td>2.6</td><td>2.9</td><td>3.7</td></tr><tr><td>B<sub>y</sub>~B<sub>y</sub>x · x</td><td>0.98</td><td>1.5</td><td>1.8</td><td>2.4</td><td>2.6</td><td>3.2</td></tr><tr><td>B<sub>y</sub>y · y</td><td>0.82</td><td>1.1</td><td>1.4</td><td>1.8</td><td>2</td><td>2.5</td></tr><tr><td>B<sub>y</sub>~B<sub>y</sub>y · y</td><td>0.98</td><td>1.5</td><td>1.8</td><td>2.4</td><td>2.6</td><td>3.2</td></tr></tbody></table>

- The 1st bloc corresponds to mesoscopic bias and standard-deviation estimation over 1000 samples, of basic expression similarities, at different vector space dimensions. The mesoscopic noise standard-deviation is estimated by computing dot-products over $N = 1000$ samples.

- The 2nd bloc corresponds to the macroscopic prediction of the mesoscopic standard-deviation estimation, as developed in this paper.

- The 3rd bloc shows the ratio between macroscopic / mesoscopic standard-deviation, showing the overestimation, while the order of magnitude is preserved.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
<table><caption>Table 4</caption><thead><tr><th>Dimension:</th><th>100</th><th>400</th><th>1024</th><th>2500</th><th>4096</th><th>10000</th></tr></thead><tbody><tr><td>||<b>B</b><sub>y</sub><b>x</b>||<sup>2</sup></td><td>1±0.14</td><td>1±0.073</td><td>1±0.043</td><td>1±0.027</td><td>1±0.023</td><td>1±0.014</td></tr><tr><td>||<b>B</b><sub>y</sub>~<b>B</b><sub>y</sub><b>x</b>||<sup>2</sup></td><td>2.1±0.51</td><td>2±0.25</td><td>2±0.15</td><td>2±0.095</td><td>2±0.081</td><td>2±0.049</td></tr><tr><td>||<b>B</b><sub>y</sub><b>y</b>||<sup>2</sup></td><td>2.1±0.2</td><td>2±0.1</td><td>2±0.059</td><td>2±0.039</td><td>2±0.033</td><td>2±0.02</td></tr><tr><td>||<b>B</b><sub>y</sub>~<b>B</b><sub>y</sub><b>y</b>||<sup>2</sup></td><td>5.3±1.2</td><td>5.2±0.64</td><td>5.1±0.36</td><td>5.1±0.25</td><td>5.1±0.2</td><td>5.1±0.13</td></tr></tbody></table>

Mesoscopic computation of VTB binding magnitudes, over $N = 1000$ samples: mean ± standard-deviation is shown. This allows to verify what has been derived in Appendix C, regarding this aspect.

<table><tbody><tr><td>28</td><td>29</td><td>30</td><td>31</td><td>32</td><td>33</td><td>34</td><td>35</td><td>36</td><td>37</td><td>38</td><td>39</td><td>40</td><td>41</td><td>42</td><td>43</td><td>44</td><td>45</td><td>46</td><td>47</td><td>48</td><td>49</td><td>50</td><td>51</td></tr></tbody></table>