🤖 machine learning

Recursive Binding on a Budget: Subspace Carving in Order-p Tensor Memories

This paper introduces Orthogonal Subspace Carving (OSC), a memory architecture that enables deep recursive binding within a constant memory footprint by projecting fillers onto the null space of role bases to enforce geometric orthogonality, thereby overcoming the dimensionality limitations of Tensor Product Representations and the fidelity issues of Vector Symbolic Architectures.

Original authors: Travis Pence, Daisuke Yamada, Vikas Singh

Published 2026-06-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Travis Pence, Daisuke Yamada, Vikas Singh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: Fitting a Library into a Shoebox

Imagine you are trying to build a digital brain that can understand complex sentences, like "The dog chased the cat that was chasing the mouse." To do this, the brain needs to remember who did what to whom, and how those actions are nested inside each other.

In the world of AI, there are two main ways to try to store this kind of information:

The "Perfect but Huge" Method (TPR): This is like building a separate, massive room for every single sentence structure. If you have a simple sentence, you need a small room. If you have a complex sentence with many layers (like a Russian nesting doll), you need a room that is exponentially bigger. Eventually, you run out of space in the universe to build these rooms. It's perfect, but it's too expensive.
The "Small but Noisy" Method (VSAs): This is like trying to fit all your books into a single shoebox. You just throw them all in on top of each other. It fits! But when you try to pull one book out, the pages of the other books get mixed up with it. The more books you add, the harder it is to find the right one without it being covered in "noise" from the others.

The Paper's Goal: The authors, Travis Pence, Daisuke Yamada, and Vikas Singh, wanted to create a system that fits in a small shoebox (low memory cost) but doesn't get messy and noisy when you add too many books.

The Solution: "Orthogonal Subspace Carving" (OSC)

The authors propose a new method called Orthogonal Subspace Carving (OSC). Here is how it works, using a few analogies:

1. The "Forbidden Zone" Analogy

Imagine you are painting a giant wall (the memory).

Old Way: You try to paint every new picture in a brand new, empty corner of the wall. If you have too many pictures, the wall runs out of space.
OSC Way: Instead of finding a new empty corner, you decide that certain parts of the wall are "Forbidden Zones" for specific types of pictures.
- If you are painting a "Subject" (like "The Dog"), you declare that the "Verb" section of the wall is off-limits.
- You then paint the "Dog" only in the remaining empty space.
- If you later paint a "Verb" (like "Chased"), you declare the "Subject" section off-limits and paint only in the space left over.

Because the "Dog" and the "Chased" are painted in different, non-overlapping zones, they don't smudge into each other, even if they are on the same wall.

2. The "Sieve" Analogy

Think of the memory as a giant sieve (a filter).

When you want to store a piece of information (a "filler") with a specific role (a "context"), you first run it through a sieve that blocks out the "forbidden" directions.
This process is called Carving. It literally cuts away the parts of the data that would cause confusion.
What's left is a clean, sharp piece of data that fits perfectly into the remaining space.

3. The "Recognition" vs. "Recall" Shift

The paper makes a clever observation about how we ask questions.

Recall: "What is in this box?" (Hard, because the box is messy).
Recognition: "Is 'The Dog' in this box?" (Easier).

The authors realized that in many AI tasks, we don't need to perfectly reconstruct a messy, blurry image. We just need to check a list of known options (like a vocabulary list) and see which one matches best. OSC is designed to be amazing at Recognition. It makes it very easy to say, "Yes, this matches 'The Dog'," even if the memory is crowded with thousands of other things.

Why This is a Big Deal (The Results)

The paper claims that OSC is a "budget-friendly" genius move:

Tiny Footprint: You can store thousands of complex, nested ideas (like deep sentences) using a tiny amount of computer memory.
No Noise Buildup: In the old "Small but Noisy" methods, adding more items makes everything garbled. In OSC, adding more items doesn't make the signal worse because the "forbidden zones" keep everything separated.
Efficiency: The authors tested this against 14 other popular methods. They found that to get the same level of accuracy, the old methods needed hundreds or even thousands of times more memory than OSC.
- Analogy: If the old methods needed a warehouse to store 1,000 items, OSC could store 1,000 items in a backpack.

What They Tested

The researchers didn't just talk about theory; they built it and tested it:

Synthetic Tests: They created fake memory tasks with thousands of items to see how much the system could hold before it got confused. OSC held its ground while others failed.
Real-World Task: They used it for a task called "Extreme Multi-label Classification." Imagine a system that has to tag a news article with the right topics from a list of 100,000 possible topics, but the article only has about 10 correct tags. OSC performed just as well as the best existing systems but used a fraction of the memory.

Summary

The paper introduces a new way to organize digital memories. Instead of building bigger rooms for every new idea (which is too expensive) or just throwing everything in a pile (which gets messy), they use a "carving" technique. They carve out specific "no-go" areas for different types of information, ensuring that everything stays clean and distinct. This allows computers to understand complex, deep structures using very little memory, making them much more efficient.

Note: The paper focuses strictly on the architecture of memory and its performance in standard AI benchmarks. It does not claim to solve specific medical problems or predict future societal changes, but rather offers a more efficient tool for building AI systems.

Technical Summary: Recursive Binding on a Budget: Subspace Carving in Order-p Tensor Memories

1. Problem Statement

The paper addresses the fundamental tension in neuro-symbolic memory systems between structural fidelity and memory efficiency.

Tensor Product Representations (TPRs) (Smolensky, 1990) offer mathematically rigorous binding of "fillers" (content) to "roles" (structure) via outer products, ensuring perfect orthogonality and lossless retrieval. However, they suffer from exponential dimensionality growth; a structure of depth $k$ requires a tensor space of order $d^k$ , rendering deep recursive binding intractable for even modest dimensions.
Vector Symbolic Architectures (VSAs) (Kanerva, 2009) maintain constant dimensionality by compressing bindings back into the original vector space (e.g., via circular convolution). While efficient, this compression introduces noise. As the number of superposed bindings increases, signal-to-noise ratio (SNR) degrades, leading to interference and unreliable retrieval in high-capacity regimes.

Existing sparse approximations of TPRs mitigate scaling but suffer significant performance degradation on deep structures. The core challenge is to support deep recursive structures and high superposition within a constant memory footprint without sacrificing retrieval accuracy.

2. Methodology: Orthogonal Subspace Carving (OSC)

The authors propose Orthogonal Subspace Carving (OSC), a memory architecture that decouples the tensor order from structural depth by enforcing geometric orthogonality through projection rather than explicit coordinate allocation.

Core Principles

Geometric Exclusion: Instead of assigning roles to specific dimensions, OSC defines contexts as "forbidden" subspaces. Bindings are placed in the orthogonal complement (null space) of these contexts.
Filler Representation: Unlike standard VSAs where fillers are single vectors, OSC fillers are structured objects: ordered tuples of $p$ vectors, $f = (v_1, \dots, v_p) \in (\mathbb{R}^d)^p$ .
Context Definition: A context $C$ is associated with a subspace $S_C$ spanned by $k$ mutually orthogonal directions. Different contexts need not be geometrically related, allowing for local precision within a context and global independence across contexts.

The Binding Mechanism

Carving (Projection): To bind a filler to a context, the carving operator $P^\perp_C = I - B_C^T B_C$ projects each component vector $v_i$ onto the null space of the context basis $B_C$ . This removes any overlap with the context subspace.
Normalization and Fusion: The projected components are normalized and fused via an order- $p$ tensor product:
$T_{bound} = \bigotimes_{i=1}^p \left( \frac{P^\perp_C v_i}{\|P^\perp_C v_i\|} \right)$
This results in an order- $p$ tensor residing entirely in the orthogonal complement of the context.
Superposition: The memory $M$ is formed by the simple addition (superposition) of these bound tensors. Because each binding is orthogonal to its specific context subspace, and contexts define disjoint subspaces, the bindings naturally separate in the memory space without interference.

Querying via Recognition

OSC shifts the retrieval paradigm from algebraic unbinding (reconstructing a vector) to discriminative recognition.

Mechanism: To query, a candidate binding is constructed using the same carving mechanism. The retrieval score is the Frobenius inner product between the memory tensor and the candidate tensor.
Vocabulary Search: The system identifies the stored item by selecting the candidate with the highest similarity score. This approach is compatible with standard "cleanup memory" codebooks used in VSAs.
Theoretical Guarantee: Theorem 4.6 establishes that for $N$ independent bindings, the interference noise scales as $\sqrt{(N-1)/d^p}$ . By increasing the tensor order $p$ or dimension $d$ , the noise can be suppressed, enabling robust retrieval even with high superposition.

Theoretical Connections

Clifford Algebra: The paper demonstrates that TPR is a special case of binding in Clifford algebra. OSC is formulated as a natural extension where roles and fillers are orthogonal subspaces rather than disjoint basis vectors, allowing for a compression of the memory space from $d^{|C|+1}$ to $\binom{d}{|C|+1}$ while maintaining exact recovery properties under specific orthogonality constraints.
Procedural Generation: Contexts can be generated procedurally by hashing role labels to produce random seeds for basis vectors. This decouples the number of representable contexts from memory constraints, avoiding the exponential storage costs of TPRs.

3. Key Contributions

OSC Architecture: A novel memory architecture that uses projection-based binding to decouple component vector dimension from memory capacity.
Sub-linear Scaling: A significant reduction in memory footprint for high-superposition tasks. The authors show that component vectors can be orders of magnitude smaller than the memory tensor while maintaining robust retrieval.
Near-Lossless Retrieval: The ability to achieve near-lossless accuracy in high-superposition regimes by leveraging sub-linear filler scaling, allowing larger superposition spaces within a smaller total footprint compared to TPRs.
Clifford Formulation: A demonstration that TPR is a special case of Clifford algebra binding and providing a Clifford formulation for OSC.

4. Experimental Results

The authors evaluated OSC against 14 existing VSAs (including HRR, VTB, MAP, HLB) and TPRs on synthetic benchmarks and Extreme Multi-label Classification (XML) tasks.

Scalability and Efficiency:
- In synthetic tests with 1,000 bundles, OSC (with $d=200, p=2$ ) achieved 99.77% retrieval accuracy, outperforming the best VSA at $d=4096$ (13.18% accuracy) and $d=8100$ (35.88% accuracy).
- At 10,000 bundles, OSC ( $d=80, p=3$ ) maintained 99.85% accuracy. To match this, the best-performing VSA (HLB) required $d=343,000$ , resulting in a 1,178× larger parameter footprint.
- OSC exhibits favorable logarithmic scaling with codebook size, similar to VSAs, but with significantly lower total memory requirements due to the sub-linear growth of filler dimension.
Comparison to TPR: For role depth 1, OSC achieves 99% accuracy with fewer parameters than TPRs once superposition levels exceed a small threshold. The compression ratio increasingly favors OSC as the number of bundles grows.
Downstream Application (XML): OSC was integrated into a neuro-symbolic model for Extreme Multi-label Classification. It achieved competitive performance (ranking first in 43.75% of metric cases across 8 datasets) compared to VTB, MAP, and HLB, confirming its learnability in gradient-based systems.
Inference Speed: While OSC's per-element operations are more complex than simple element-wise VSA operations, OSC becomes faster at scale because the bottleneck shifts from compute to memory bandwidth. OSC's smaller memory footprint reduces data transfer times, leading to lower wall-clock retrieval times in high-superposition scenarios.

5. Significance and Claims

The paper claims that OSC resolves the "neuro-symbolic gap" by providing a mechanism for deep recursive binding that is both computationally tractable and memory efficient.

Shift in Paradigm: By moving from reconstruction to recognition and utilizing geometric exclusion (carving) rather than explicit dimension expansion, OSC avoids the exponential scaling of TPRs and the noise accumulation of VSAs.
Practicality: The ability to generate contexts procedurally and the sub-linear scaling of filler dimensions make OSC suitable for applications requiring large vocabularies and deep structures without prohibitive memory costs.
Limitations: The authors modestly note that OSC does not support exact algebraic unbinding (reconstruction of arbitrary vectors) without iterating through a vocabulary, though they argue this is a non-issue for symbolic reasoning systems that rely on codebook search anyway. They also acknowledge that while OSC outperforms VSAs in total memory efficiency, VSAs may still hold a slight advantage when the constraint is strictly the size of the superposition memory (not total storage).

The work is presented as a step toward scalable, structured memory systems compatible with modern gradient-based optimization, validated through extensive empirical verification against state-of-the-art baselines.