Why permutation matters in HDC

In earlier posts, we’ve used binding to associate hypervectors and bundling to collect those associations into a single representation. We connected those operations to the Multiply-Add-Permute (MAP) model and mentioned permutation as the third part of its algebra. This post dives into the details of permutation, and why it exists in the first place.

In the real world, data is often more than just a flat record. It often has deeper structural elements that associations alone don’t fully capture. The same items can describe very different things depending on how they’re arranged, and in the sections below, we’ll see how binding alone loses that information, but permutation helps preserve it.

HDC operation	Question it helps answer
Binding	Which hypervectors are associated with each other?
Permutation	How is each occurrence arranged in the structure?

Let’s first recall two key properties of binding. First, multiplicative binding is commutative:

$$\mathbf{a}\otimes\mathbf{b} = \mathbf{b}\otimes\mathbf{a}$$

With bipolar hypervectors, binding is also self-inverse:

$$\mathbf{a}\otimes\mathbf{a} = \mathbf{1}, \qquad \mathbf{a}\otimes(\mathbf{a}\otimes\mathbf{b}) = \mathbf{b}$$

Together, these properties make binding a simple and powerful way to associate concepts and recover them later. However, these very same properties can be a problem when the arrangement of those concepts matters: commutativity can erase hierarchy, while self-inverse binding can erase repeated occurrences. Let’s look at each failure in turn.

Commutativity erases hierarchy

Consider a product catalogue dataset in which it’s common to have multiple nested labels that describe any given product. As a developer, you have a choice of how to model the data, and there are different ways for you to organize the labels into a single nested record. The two examples below illustrate the same set of labels arranged in two different ways.

Option A: product.features.display.touchscreen

product
└── features
    └── display
        └── touchscreen

Option B: product.display.features.touchscreen

product
└── display
    └── features
        └── touchscreen

Both records contain the same four labels: product, features, display, and touchscreen. However, they’re structurally different, because touchscreen has different immediate parents in each case.

If we wanted to encode these two records into hypervectors, we could use multiplicative binding to combine the labels in the order they appear in each record. This is where the commutative nature of binding loses information.

Because MAP binding uses element-wise multiplication, the order of the labels doesn’t matter, and both records produce the same hypervector representation.

$$\begin{aligned} \mathbf{n}_A &= \mathbf{p}\otimes\mathbf{f}\otimes\mathbf{d}\otimes\mathbf{t} \\ \mathbf{n}_B &= \mathbf{p}\otimes\mathbf{d}\otimes\mathbf{f}\otimes\mathbf{t} \\ \mathbf{n}_A &= \mathbf{n}_B \end{aligned}$$

Unbinding touchscreen from each record shows why its parent can’t be recovered:

$$\begin{aligned} \mathbf{t}\otimes\mathbf{n}_A &= \mathbf{t}\otimes (\mathbf{p}\otimes\mathbf{f}\otimes\mathbf{d}\otimes\mathbf{t}) = \mathbf{p}\otimes\mathbf{f}\otimes\mathbf{d} \\ \mathbf{t}\otimes\mathbf{n}_B &= \mathbf{t}\otimes (\mathbf{p}\otimes\mathbf{d}\otimes\mathbf{f}\otimes\mathbf{t}) = \mathbf{p}\otimes\mathbf{d}\otimes\mathbf{f} = \mathbf{p}\otimes\mathbf{f}\otimes\mathbf{d} \end{aligned}$$

Self-inverse binding successfully removes $\mathbf{t}$, but both records leave the same unordered remainder. We recover that product, features, and display were present, but not whether display or features was the immediate parent of touchscreen.

Binding helps us know which labels are associated, but it doesn’t tell us where each label lives in the hierarchy.

Self-inverse binding erases repeated steps

Commutativity isn’t the only way binding can lose structure. Its self-inverse property (which enables unbinding) also creates a different problem when modeling repeated steps within a path in a graph. The example below shows such a scenario when a journey revisits the same state. Consider a shopper who enters checkout, returns to their cart to change something, then checks out again:

Let’s assign $\mathbf{p}$ to Product, $\mathbf{c}$ to Cart, $\mathbf{h}$ to Checkout, and $\mathbf{b}$ to Purchase. If we try to represent the journey with binding alone, multiplying every state it visits, the path collapses:

$$\begin{aligned} \mathbf{j}_{\text{raw}} &= \mathbf{p}\otimes\mathbf{c}\otimes\mathbf{h} \otimes\mathbf{c}\otimes\mathbf{h}\otimes\mathbf{b} \\ &= \mathbf{p} \otimes (\mathbf{c}\otimes\mathbf{c}) \otimes (\mathbf{h}\otimes\mathbf{h}) \otimes\mathbf{b} \\ &= \mathbf{p}\otimes\mathbf{1}\otimes\mathbf{1}\otimes\mathbf{b} \\ &= \mathbf{p}\otimes\mathbf{b} \end{aligned}$$

Both visits to Cart cancel, as do both visits to Checkout. All that remains is the same product we’d get from binding Product directly with Purchase. From $\mathbf{j}_{\text{raw}}$, we can’t tell whether the shopper moved straight from product to purchase or hesitated, backtracked, and re-entered checkout along the way.

A look at the HDC literature

Across decades of HDC/VSA research, researchers repeatedly encountered the limitations of multiplicative binding. Their solutions eventually converged under the name “permutation”. The table below summarizes some of the key papers that introduced permutation (using different terminologies) to address structural problems in hyperdimensional representations.

Research line	Structural problem	How permutation was used
Tony Plate (1995) 1	Commutative convolution made some nested structures ambiguous	Permute the left and right inputs differently to create a noncommutative form of binding
Dmitri Rachkovskij (2001) 2	The same item needed distinct forms at different places in a relation	Shift or otherwise permute its components according to its role or position
Ross Gayler (2003) 3	A composite needed to remain distinct inside a larger composition	Use a permutation-like operation to “quote” or protect it before further binding
Magnus Sahlgren, Anders Holst, and Pentti Kanerva (2008) 4	Adding word hypervectors preserved context but discarded word order	Apply different powers of the same permutation according to each word’s relative position

Although the approaches varied (some changed the binding operation, some treated position as a role, and others transformed an item before bundling it), they addressed the same underlying need to distinguish each occurrence through a structural form before composing it with the others.

Pentti Kanerva’s 2009 synthesis ⁵ made the connection between the three operations (binding, bundling, and permutation) especially explicit. Commutative, self-inverse binding can lose the order of its inputs or collapse identical ones; permuting an input before binding makes its structural position part of the representation.

It’s worth noting that permutation isn’t the only way to preserve structure. Explicit role–value bindings combined through bundling, noncommutative binding operations, matrices, and other encoder designs can do it in certain scenarios, too. Permutation became a common solution because it provides an operation that resembles “positional binding”, unlike the more general associative binding that can lose structure.

How permutation preserves structure

Binding had no notion of where an input appeared. Features contributed the same hypervector at every nesting depth, just as every visit to Cart contributed the same hypervector at every step.

Permutation adds that missing position before we bind. It rearranges the same concept hypervector differently at depth 1, depth 2, step 3, and so on, so each occurrence contributes a distinguishable form instead of an identical one.

One common implementation is a cyclic shift, which moves every component by a fixed offset and wraps around at the ends. We’ll use that simple case below, but a permutation can be any fixed, one-to-one reordering of the coordinates.

Let’s start with a small bipolar hypervector to illustrate the idea:

$$\mathbf{a} = [+1,-1,+1,+1,-1,-1,+1,-1]$$

We’ll write permutation as $\rho(\mathbf{a})$. In this example, $\rho$ shifts every component one place to the right, and the last wraps around to the front.

Applying $\rho$ once to $\mathbf{a}$ produces:

$$\rho(\mathbf{a}) = [-1,+1,-1,+1,+1,-1,-1,+1]$$

No value was added, removed, or changed; the eight values simply moved to new coordinates. Because the mapping is one-to-one, we can reverse it exactly. We can also apply the same operator more than once, giving the hypervector several positional forms:

Times permuted	Form used by the encoder
0	Original hypervector
1	$\rho(\mathbf{a})$
2	$\rho^2(\mathbf{a})$
3	$\rho^3(\mathbf{a})$

In a high-dimensional encoder, we choose a permutation whose relevant powers produce distinguishable forms. We can then use the number of times $\rho$ is applied to represent a nesting depth or a step in a journey.

Preserving hierarchy

Let’s return to the nested product records from above. We’ll call their encoded hypervectors $\mathbf{h}_A$ and $\mathbf{h}_B$, and name each label hypervector with a matching subscript. The number of shuffles records its depth:

Depth	Option A: $\mathbf{h}_A$	Option B: $\mathbf{h}_B$
0	$\mathbf{h}_{\text{product}}$	$\mathbf{h}_{\text{product}}$
1	$\rho(\mathbf{h}_{\text{features}})$	$\rho(\mathbf{h}_{\text{display}})$
2	$\rho^2(\mathbf{h}_{\text{display}})$	$\rho^2(\mathbf{h}_{\text{features}})$
3	$\rho^3(\mathbf{h}_{\text{touchscreen}})$	$\rho^3(\mathbf{h}_{\text{touchscreen}})$

For each hierarchy, we bind its four depth-specific hypervectors together. We then unbind Touchscreen from depth 3:

$$\begin{aligned} \rho^3(\mathbf{h}_{\text{touchscreen}})\otimes\mathbf{h}_A &= \mathbf{h}_{\text{product}} \otimes\rho(\mathbf{h}_{\text{features}}) \otimes\rho^2(\mathbf{h}_{\text{display}}) \\ \rho^3(\mathbf{h}_{\text{touchscreen}})\otimes\mathbf{h}_B &= \mathbf{h}_{\text{product}} \otimes\rho(\mathbf{h}_{\text{display}}) \otimes\rho^2(\mathbf{h}_{\text{features}}) \end{aligned}$$

We can now answer the question that binding alone could not: which label is the immediate parent of Touchscreen? Unbinding the depth-0 and depth-1 terms isolates $\rho^2(\mathbf{h}_{\text{display}})$ in Option A and $\rho^2(\mathbf{h}_{\text{features}})$ in Option B. Applying the inverse permutation multiple times recovers the underlying label hypervector in a way that distinguishes the two hierarchies.

By making depth part of each label’s form before binding, permutation prevents the commutative property of binding from erasing the hierarchical structure.

Preserving repeated steps

Let’s see how permutation solves the self-inverse failure in the user journey above. The first state is unchanged, the second is permuted once, the third twice, and so on:

Step	State	Form used by the encoder
1	Product	$\mathbf{h}_{\text{product}}$
2	Cart	$\rho(\mathbf{h}_{\text{cart}})$
3	Checkout	$\rho^2(\mathbf{h}_{\text{checkout}})$
4	Cart	$\rho^3(\mathbf{h}_{\text{cart}})$
5	Checkout	$\rho^4(\mathbf{h}_{\text{checkout}})$
6	Purchase	$\rho^5(\mathbf{h}_{\text{purchase}})$

Before permutation, both visits to Cart used the same hypervector, so binding them invoked the self-inverse property, producing the all-ones hypervector that erased the information about Cart. With permutation, one visit uses $\rho(\mathbf{h}_{\text{cart}})$ while the other uses $\rho^3(\mathbf{h}_{\text{cart}})$, so the two forms are different.

Say Cart is the bipolar hypervector below. Applying the same shuffle once and three times gives:

$$\begin{aligned} \mathbf{h}_{\text{cart}} &=[+1,-1,+1,+1,-1,-1,+1,-1] \\ \rho(\mathbf{h}_{\text{cart}}) &=[-1,+1,-1,+1,+1,-1,-1,+1] \\ \rho^3(\mathbf{h}_{\text{cart}}) &=[-1,+1,-1,+1,-1,+1,+1,-1] \\ \rho(\mathbf{h}_{\text{cart}})\otimes\rho^3(\mathbf{h}_{\text{cart}}) &=[+1,+1,+1,+1,-1,-1,-1,-1] \\ &\neq[+1,+1,+1,+1,+1,+1,+1,+1] \end{aligned}$$

Because neither repeated pair produces the all-ones hypervector, those visits remain in the encoded journey. We can now answer the question binding alone could not: did the shopper go straight from Product to Purchase, or did they return to Cart and re-enter Checkout? The step-specific forms record the backtracking path.

By giving each visit a different form before binding, permutation prevents the self-inverse property from erasing repeated steps.

Conclusions

Today, permutation is most often introduced as the HDC operation for preserving order. TorchHD describes it this way↗ , and the Kleyko et al. survey ⁶ covers its use in sequences, text, images, and compositional structures. Familiar examples include word positions, sensor samples, and events ordered in time.

That framing is useful, but ordered sequences are one case of a broader property: permutation models topology and structure. Time gives events a position in a sequence, depth gives labels a position in a hierarchy, and step number gives each visit a position in a traversal. The table below summarizes the structural problems that permutation addresses and how it does so.

What we’re modeling	What must be preserved	A suitable encoding approach
Unordered fields with stable roles	Which value fills each role	Bind role–value pairs, then bundle the associations
A nested hierarchy	Depth and immediate parent	Permute each label by depth, then bind
A traversal that revisits the same state	Visit order and backtracking	Permute each occurrence by step, then bind
A temporal sequence or ordered event stream	Event order and repeated observations	Permute each event by position, then bundle

Binding role–value pairs and bundling them remains the right choice when stable roles already distinguish the associations; the values themselves don’t need to be unique. However, when moving or repeating an occurrence changes the meaning of what we want to represent, permutation gives each position a distinct form before composition. This preserves the topology of the structure, so we can recover the arrangement of the concepts later. In later posts, we’ll see how this works in practice!

Footnotes

1. Tony Plate, “Holographic Reduced Representations”↗ (1995). ↩

2. Dmitri A. Rachkovskij, “Representation and Processing of Structures with Binary Sparse Distributed Codes”↗ (2001). ↩

3. Ross Gayler, “Vector Symbolic Architectures Answer Jackendoff’s Challenges for Cognitive Neuroscience”↗ (2003). ↩

4. Magnus Sahlgren, Anders Holst, and Pentti Kanerva, “Permutations as a Means to Encode Order in Word Space”↗ (2008). ↩

5. Pentti Kanerva, “Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random Vectors”↗ (2009). ↩

6. Denis Kleyko, Dmitri A. Rachkovskij, Evgeny Osipov, and Abbas Rahimi, “A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations”↗ (2022). ↩