🤖 machine learning

Sutra: Tensor-Op RNNs as a Compilation Target for Vector Symbolic Architectures

The paper introduces Sutra, a purely functional programming language that compiles symbolic Vector Symbolic Architecture operations into fused PyTorch tensor graphs, enabling programs to achieve perfect decoding accuracy across diverse frozen embedding substrates and to be trained via backpropagation while remaining fully legible and recompilable as source code.

Original authors: Emma Leonhart

Published 2026-05-21✓ Author reviewed ⓘ

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Emma Leonhart

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 by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, frozen library of knowledge. In this library, every concept (like "apple," "justice," or "protein") isn't a word on a page, but a unique, multi-dimensional color or shape. This library is built by a giant AI that has read the entire internet, and it's "frozen," meaning the colors and shapes never change once the library is built.

The problem is: How do you do math or logic with these colors? If you try to mix them using standard rules (like the "Hadamard product" mentioned in the paper), the colors get muddy and you can't tell them apart anymore. It's like trying to mix red and blue paint to get purple, but instead, you just get a muddy brown that looks like every other color in the room.

Sutra is a new tool that solves this. It's a programming language that lets you write logic rules, but instead of running on a normal computer processor, it compiles those rules into a single, super-efficient machine that operates directly on these "colors" (vectors) inside the frozen library.

Here is how Sutra works, broken down into simple concepts:

1. The "Magic Rotation" (Binding)

In the old way of doing this, mixing two concepts was like smashing them together, which caused a mess. Sutra uses a trick called Rotation Binding.

The Analogy: Imagine every concept has a unique "key" (a role). To attach a specific detail (a "filler") to that key, Sutra doesn't smash them; it rotates the detail like a key turning in a lock.
Why it works: Because the library is frozen and the rotation is mathematically perfect, you can always turn the key back to get the original detail out, even if you've mixed it with other details. The paper proves this works perfectly on text and even on protein sequences (biology), whereas the old "smashing" method failed completely.

2. The "Smooth Logic" (Fuzzy Math)

Usually, computers think in strict "Yes/No" or "On/Off" switches. But the "colors" in the library aren't perfect; they are a bit fuzzy.

The Analogy: Imagine a dimmer switch instead of a light switch. Sutra uses a special kind of math (polynomials) that treats logic like a smooth slider. It can handle "Maybe" (0), "True" (+1), and "False" (-1) without breaking.
The Magic: The paper shows that Sutra turns these fuzzy logic rules into a single, smooth mathematical formula. This means a computer can not only run the logic but also learn from it.

3. The "One-Step Machine" (Compilation)

Normally, if you write a program with loops (repeating steps) or "if-then" decisions, the computer has to check those rules one by one, which is slow.

The Analogy: Sutra is like a master chef who takes your recipe (the program) and pre-cooks the entire meal into a single, ready-to-eat block before you even sit down.
The Result: When you run the program, there are no "if" checks or "while" loops happening in real-time. The computer just performs one giant, continuous flow of math. It's like a train that never stops at stations; it just glides from start to finish.

4. Learning and "Legible" Code

One of the most surprising things Sutra does is learn.

The Analogy: Usually, when a neural network learns, it becomes a "black box"—a blob of numbers that no human can read. Sutra is different. It can adjust a single number (a "gain" or volume knob) to make the logic work better.
The Twist: After the computer learns the perfect setting for that knob, Sutra takes that number and writes it back into the original code as a simple number.
Why it matters: You don't get a mysterious black box; you get a clean, readable program that says, "Do this logic, but multiply the result by 1.43." The trained model is still a piece of human-readable text.

5. The "Dictionary" (Codebook)

Since the computer only understands "colors" (vectors), how does it talk to humans?

The Analogy: Sutra carries a built-in dictionary (a codebook). When you type a word like "apple," the compiler instantly translates it into its "color" before the program starts. When the program finishes, it looks at the resulting "color" and finds the closest word in the dictionary to give you back a human-readable answer.

What the Paper Actually Proved

The paper doesn't claim Sutra can cure diseases or predict the stock market yet. It proves three specific things:

It works on different libraries: It successfully ran the same logic program on text (like books) and biology (like proteins) without changing the code.
It beats the old methods: On these frozen libraries, Sutra's "rotation" method could retrieve information with 100% accuracy, while the old "smashing" method failed miserably (dropping to near-random guessing).
It can learn and stay readable: They trained a simple classifier (a program that sorts words into categories) from scratch. It started with random guesses, learned to be 100% accurate, and the final result was a clean, readable piece of code with a specific number baked into it.

In short, Sutra is a bridge that lets us write logical rules that run directly inside the "frozen brains" of modern AI, turning them into fast, learnable, and human-readable machines.

Technical Summary: Sutra: Tensor-Op RNNs as a Compilation Target for Vector Symbolic Architectures

Problem Statement

Vector Symbolic Architectures (VSA) traditionally rely on high-dimensional vectors drawn from controlled random distributions, using operations like the Hadamard product (element-wise multiplication) or circular convolution for binding. However, modern "frozen" Large Language Model (LLM) embeddings do not conform to these assumptions. They are anisotropic, concentrating in narrow cones within the vector space, which compresses cosine similarity and causes standard binding operations (like Hadamard) to fail due to destructive crosstalk when bundling multiple items.

Furthermore, existing neuro-symbolic systems often follow a two-stage architecture: a neural model extracts discrete symbols, which are then processed by a separate symbolic reasoner. This creates a disconnect between the continuous embedding space and the discrete logic layer. There is a lack of a system that treats the continuous embedding space as the primary substrate for a full programming language, where control flow, logic, and I/O are all compiled into a single, differentiable tensor operation graph.

Methodology

The paper introduces Sutra, a typed, purely functional programming language designed specifically to compile down to a PyTorch neural network operating over a frozen embedding substrate. The core methodology involves four consolidated primitives that replace standard VSA operations and control flow mechanisms:

Polynomial Fuzzy Logic: Instead of non-differentiable min/max operators (Gödel t-norms) used in standard fuzzy logic, Sutra employs Lagrange-interpolated polynomials for Kleene's three-valued logic (Truth values: $+1, 0, -1$ ). These polynomials are exact on the discrete $\{-1, 0, +1\}$ grid but are $C^\infty$ (smooth) elsewhere, enabling gradient flow through logical connectives (AND, OR, NOT) within a tensor graph.
Beta-Reduction to Tensor Graphs: The Sutra compiler performs aggressive beta-reduction, inlining standard library definitions and simplifying algebraic expressions. The result is a substrate-pure tensor-op graph containing no named bindings, function calls, or Python control flow. Conditionals are lowered to soft-mux polynomials, and loops are compiled into soft-halt RNN cells.
Rotation Binding: To address the anisotropy of frozen LLM embeddings, Sutra replaces the Hadamard product with Haar-orthogonal rotation binding. A role-specific orthogonal matrix $R_{role}$ is generated via a content hash and applied to the filler vector ( $bind(role, filler) = R_{role} \times filler$ ). This operation is invertible and well-conditioned even on anisotropic substrates.
Tail-Recursive Loops as RNNs: Loops are expressed as tail-recursive function declarations. The compiler lowers these into soft-halt RNN cells where the state vector is fixed-width. A "halt" signal is computed via a cumulative monotone sum of a Heaviside condition, allowing the loop to freeze state without Python-level branching.

The system utilizes a compile-time codebook (stored as a .sdb file) to map string literals to embeddings and decode nearest-neighbor strings at the output, closing the loop on string I/O without requiring host-side dictionary lookups during the forward pass.

Key Contributions

The paper presents four specific technical contributions:

Differentiable Logic via Lagrange Interpolation: The derivation of polynomial connectives that are exact on the Kleene grid but differentiable everywhere else, resolving the gradient flow issues associated with standard fuzzy logic operators in neural-symbolic contexts.
Substrate-Pure Compilation: A compiler pipeline that reduces a high-level functional language into a single fused tensor graph (matmul, element-wise, non-linear) with no host-side control flow, ensuring the entire program is a differentiable function of its inputs and learnable parameters.
Rotation Binding for Anisotropic Substrates: Empirical validation that rotation-based binding outperforms Hadamard binding on frozen LLM embeddings (text and protein models), maintaining 100% decode accuracy at bundle widths where Hadamard binding collapses to chance levels.
Legible, Recompilable Trained Models: A demonstration that trained parameters (specifically scalar gains) can be baked back into the source code as numeric literals. This allows a trained model to be represented not as an opaque checkpoint, but as a recompilable, human-readable Sutra program that reproduces the trained behavior with high precision.

Results

The paper validates the approach through two primary experimental axes:

Cross-Substrate Capacity: Experiments were conducted on four frozen substrates: three text encoders (nomic-embed-text, all-minilm, mxbai-embed-large) and one protein language model (ESM-2).
- Rotation Binding: Achieved 100% accuracy in decoding bundled records at width $k=8$ across all substrates.
- Hadamard Binding: Collapsed significantly, with accuracy dropping to 2.5% on mxbai-embed-large and 7.5% on all-minilm at the same width.
- Noise Accumulation: Accuracy remained at 100% for single-cycle records but degraded to chance levels by chain length $L=8$ , defining the validated regime for the current implementation.
End-to-End Differentiable Training:
- A fuzzy-rule classifier written in Sutra was trained from random initialization (accuracy $\approx 18.7\%$ , chance $= 20\%$ ) to 100.0% accuracy over 30 epochs using standard PyTorch backpropagation.
- Gradients were verified to flow through the compiled tensor graph (similarity $\to$ Lagrange-Kleene polynomials $\to$ cross-entropy) without reimplementation.
- A weighted variant trained a scalar gain $w$ to counteract embedding anisotropy. The trained model was successfully "baked" back into the source code (e.g., 1.431431 * similarity(...)), and recompiling this source reproduced the trained logits with a maximum difference of $\approx 2 \times 10^{-7}$ .

Significance and Claims

The paper claims that Sutra represents a novel position in the landscape of neuro-symbolic computing and differentiable programming. Its significance lies in the unification of logic and learning within a single artifact:

Artifact Shape: Unlike libraries (e.g., TorchHD) that expose primitives to Python scripts, or neuro-symbolic languages (e.g., Scallop, DeepProbLog) that separate perception from reasoning, Sutra compiles the entire program—including control flow and string I/O—into a single fused tensor-op graph.
Substrate Agnosticism: The architecture is not tied to a specific embedding model; it can target any network producing dense vector representations, as demonstrated by the successful porting of the same source code to both text and protein embeddings.
Legibility: By training parameters that can be written back as source literals, the system bridges the gap between black-box neural weights and interpretable logic programs. The trained model is not a "blob" but a recompilable program.

The authors explicitly state that the work is a verification of the "source-training round-trip" and gradient flow through the compiled graph, rather than a generalization benchmark against other systems. The system is currently bounded to single-cycle records and specific frozen substrates, with deep nested records and arbitrary embedding models identified as future work.