Higher-Order Attention for Compositional Reasoning

This direction is split into other directions: pairwise attention bottleneck. Its last version stays readable and citable here.

Version 1 of 131 papers45 conceptsfrozen 2026-10-04

Standard Transformer models are built on a fundamental operation: the pairwise dot-product attention. While this mechanism has powered the current era of AI, it possesses a structural "blind spot." It can only compute interactions between two tokens at a time. This pairwise constraint creates a bottleneck for tasks requiring compositional reasoning, where the relationship between three or more elements must be evaluated simultaneously.

The Pairwise Bottleneck

In a standard attention layer, the model calculates a score for how much token $A$ should attend to token $B$. Mathematically, this is a second-order interaction ($Q \cdot K^T$). If you imagine the tokens as nodes in a graph, standard attention can only "see" the edges between them.

However, many logical and mathematical problems are not reducible to simple pairs. As Alexander Kozachinskiy and colleagues demonstrate in Strassen Attention, Split VC Dimension and Compositionality in Transformers, certain functions require simultaneous interactions between three or more tokens. For example, finding a triplet of numbers $(x, y, z)$ that satisfies a specific condition (like $x + y = z$) is fundamentally a "triple-wise" problem.

Clayton Hendrick Sanford and Daniel Hsu prove in Representational Strengths and Limitations of Transformers that for a single standard attention layer to resolve these higher-order dependencies, the model's width or head count must scale polynomially with the sequence length. This makes standard architectures computationally prohibitive for complex reasoning over long contexts.

From Edges to Simplices

To overcome this, researchers are moving from "edge-based" attention to "simplicial" or "tensor" attention. Instead of looking at pairs (edges), these models look at triangles (2-simplices) or even higher-dimensional structures.

In Logic and the 2-Simplicial Transformer, James Clift and Daniel Murfet introduce an architecture that natively captures 3-way interactions. By using Clifford algebras to compute attention over triples, the model gains an inductive bias for logical conjunctions—tasks where an outcome depends on the simultaneous presence of multiple distinct entities.

This isn't just a theoretical curiosity. Sai Surya Duvvuri and Manzil Zaheer recently implemented 2-Simplicial Attention in Triton, showing that this higher-order approach improves the fundamental scaling law exponents for mathematics and reasoning tasks. By allowing a single layer to "see" triples, the model avoids the need for excessive depth to simulate complex logic.

Scaling Higher-Order Interactions

The primary challenge with higher-order attention is computational complexity. If standard attention is $O(n^2)$ for a sequence of length $n$, a naive triple-wise attention would be $O(n^3)$.

Recent breakthroughs have found ways to capture these correlations without the cubic cost:

  1. Kronecker Computation: Josh Alman and Zhao Song propose generalizing matrix softmax attention to Kronecker products in How to Capture Higher-order Correlations?. They prove that provided input entries are bounded, this expressive attention can be computed in near-linear time.
  2. Tensor Factorization: In Higher Order Transformers, Soroush Omranpour and Guillaume Rabusseau use factorized attention to process multiway data. By representing attention as a sum of mode-wise matrices, they capture cross-dimensional dependencies with significantly lower memory costs.
  3. Poly-attention: Sayak Chakrabarti and Toniann Pitassi introduced Poly-attention, identifying a "Tree-attention" variant that performs multi-token reasoning in quadratic time—matching the efficiency of standard attention while providing the expressivity of higher-order models.

Why It Works: The Expressivity Gap

The intuition behind this shift is that standard Transformers are "shallow" in their interaction logic. To solve a 3-way dependency, a standard Transformer must use one layer to create a composite representation of tokens $A$ and $B$, and a second layer to compare that composite to token $C$.

Higher-order mechanisms like those in Training Tensor Attention Efficiently by Yang Cao and Zhao Song allow the model to fuse information across multiple views or tokens simultaneously. This is particularly vital in multi-modal reasoning or complex entity tracking, where Erwan Fagnou shows in ChaCAL that treating attention as a more complex relational structure allows a single layer to traverse multi-step dependency chains that would otherwise require logarithmic depth.

By explicitly modeling $n$-wise interactions, these architectures bridge the gap between simple pattern matching and true compositional reasoning.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_higher_order_attention_for_compositional_0b6c3103,
  title = {Higher-Order Attention for Compositional Reasoning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/higher-order-attention-for-compositional-reasoning/rdr_0b6c31031c964d809ba165fb507f89aa},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_higher_order_attention_for_compositional_0b6c3103_v1,
  title = {Higher-Order Attention for Compositional Reasoning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/higher-order-attention-for-compositional-reasoning/rdr_0b6c31031c964d809ba165fb507f89aa/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}