Attention Is Only as Good as Its Witnesses: When Higher-Order Layers Help, and When They Do Not

Mostafa 'Neo' MohsenvandarXiv 2026 · arXiv

TL;DR

Standard Transformers often fail at algorithmic tasks like graph search because their attention mechanism is designed to sum over single tokens, whereas these problems require reasoning over pairs, walks, or subsets. This paper introduces a "witness" framework and two fundamental laws—the Depth Law and the Size Law—to design specialized layers that generalize perfectly to much larger problems than they were trained on.

What Problem Does This Paper Address?

While Transformers are the powerhouse of modern AI, they exhibit surprising failures in simple algorithmic domains. For instance, as graphs grow larger, Transformers struggle to learn pathfinding, and they require massive amounts of data to learn combinatorial games like SET.

The authors argue that the root cause is a mismatch between what a layer "sums over" (its witnesses) and what the task requires. Standard softmax attention focuses on single tokens. However, finding a path in a graph requires looking at "walks," and SET requires looking at "triples" of cards. Without layers explicitly designed to handle these higher-order structures, models fail to generalize when the problem scale increases.

Methods

The paper proposes building layers based on the "partition function" of a family of witnesses. Key innovations include:

  • The Depth Law: Drawing from mathematical logic, the authors show that $L$ layers of two-step walks can only "see" exactly $2^L - 1$ steps ahead. This represents a hard logical limit for stacked architectures.
  • The Size Law: A new theorem (formally verified in the Lean theorem prover) stating that for a model to correctly detect the "existence" of a solution as the number of candidates grows, the inverse temperature ($\beta$) times the margin ($\Delta$) must be at least the logarithm of the number of candidates ($|F|$).
  • Propagator Layer: A novel layer that uses a closed-form matrix inverse $(I - G)^{-1}$ to compute reachability for walks of any length in a single step, effectively bypassing the Depth Law.
  • Exponential Newton: A layer that efficiently computes exact softmax over pairs or subsets using Newton's identities and Fourier series, specifically tailored for combinatorial rules.

Datasets

The authors evaluated their approach on several challenging benchmarks:

  • Graph Search: A benchmark of directed acyclic graphs (DAGs) from Saparov et al. (2025).
  • SET: A card game used to test the learning of complex attribute-based rules.
  • CLRS-30: A standard suite of 30 classic algorithms (e.g., BFS, DFS, Dijkstra, Kruskal's).
  • FineWeb-Edu & Lichess: Used to test the impact of these layers on large-scale language modeling and chess.

Key Insights and Ideas

  • Match the Family: A layer learns a task easily only if its summation family matches the task's "witnesses." If a task's answer is a sum over pairs, a single-token attention layer will struggle.
  • Closed Forms are Parallel Shortcuts: Instead of stacking many layers to "reason" through a graph, using a mathematical closed form (like a matrix inverse) allows the model to solve the problem in one step with better generalization.
  • Softmax Dilution: Standard softmax normalization "dilutes" the signal as the number of tokens increases. The Size Law provides the mathematical recipe for adjusting model temperature to maintain performance at scale.
Figure 1: Visualizing different "witness" families: single towns, two-step walks, and every walk at once.

Key Results

  • Super-Generalization in Search: A single propagator layer trained on 49-vertex graphs achieved 100% accuracy on 250-vertex graphs. Standard Transformers failed to generalize to these larger sizes.
  • Efficiency in SET: The Exponential Newton layer learned the game SET from 64 times fewer examples than a large Transformer and transferred perfectly from 8-card to 20-card tables.
  • SOTA on CLRS-30: A tiny model with only 186,000 parameters matched or outperformed a state-of-the-art model (FloydNet) with over 73 million parameters on 9 out of 12 graph tasks.
  • Targeted Gains: In language modeling and chess, where most witnesses are single tokens, the authors found that higher-order layers added very little, confirming that specialized layers are only helpful when they "match the family" of the problem.
Figure 2: A trained propagator layer successfully navigating a 250-vertex graph, far larger than its training set.

Limitations and Future Work

  • Computational Cost: Some specialized layers, like Exponential Newton, can be computationally expensive ($3^d n$ operations) depending on the number of "clocks" (attributes) used.
  • Scope: While highly effective for algorithmic and synthetic tasks, the gains in broad natural language processing were modest.
  • Future Directions: The authors suggest that the next step is identifying the right "witnesses" for language—such as tree structures in parsing—and applying appropriate closed-form layers to them.

Summary updated

Abstract

Transformers stop learning graph search as graphs grow, and learn the card game SET only after many distinct questions, although attention can represent both. We read these failures, and the uneven record of higher-order attention, from what a layer sums over: each layer we study computes the partition function of a family of witnesses and reads it at a temperature. Two laws follow. The depth law is a known result of logic, which we state for these layers: L layers over two-step walks reach exactly 2^L - 1 steps, just as a logical statement with L nested clauses of the form "there is a vertex such that" sees exactly that far. We build a construction that reaches this far, checked in Lean, and, when vertices carry no names, no such network reaches further. The size law is the cost of reading at a temperature, which logic does not have: existence is read correctly at every size, in the worst case, if and only if inverse temperature times margin is at least the logarithm of the number of candidates. Layers built on these laws, and on two principles that we test, learn where Transformers fail. One propagator layer trained on 49-vertex graphs answers every question at every search depth on 250-vertex graphs. Given the modulus 3, exponential Newton computes the softmax of 2-simplicial attention over pairs exactly in 3^d n operations for d clocks; with six clocks it learns SET from as few deals as 2-simplicial attention and transfers from 8- to 20-card tables. On CLRS-30 without hints, a 186,000-parameter block of OR-join and power-mean channels matches (within half a point) or beats a model of at least 73 million parameters on 9 of 12 graph tasks of the official test set, and on 8 of 12 with freshly drawn test graphs. The same account explains where pair layers did not help and where parallel layers must loop.
BibTeX
@misc{mohsenvand2026attention,
  author = {Mostafa 'Neo' Mohsenvand},
  title = {{Attention Is Only as Good as Its Witnesses: When Higher-Order Layers Help, and When They Do Not}},
  year = {2026},
  eprint = {2611.11937},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.11937},
}
Figure