Relational Composition as Parallel Transport: What Per-Entity Frames Force in Attention

Aakash Sarkar; Ananya Mukherjee; Motoshige Sato

cs.LGOct 26, 2026

Relational Composition as Parallel Transport: What Per-Entity Frames Force in Attention

Authors: Aakash Sarkar, Ananya Mukherjee, Motoshige Sato

Organizations: University of California, San Francisco · Brigham and Women’s Hospital

Abstract

A dot product means something only when both vectors share a coordinate system. Content words have one; a fresh entity does not: rotating its coordinates alone changes nothing. We take this per-entity frame freedom as a symmetry and ask what it forces in attention. For orthogonal transports, invariant scores depend only on norms and the transported inner product $\langle x_i,T_{ij}x_j\rangle$ ; equivariant messages lie in the span of $x_i$ and $T_{ij}x_j$ . Endpoint channel count bounds transport rank, so with one vector per entity relations must be supplied; standard attention is the flat sector of a shared frame. Representation theory attaches an integer to each mechanism; the readout decides which. With orthogonal transitions, a convex-cell readout composes a finite group exactly only at or above its smallest faithful real representation dimension. At this minimum, exactness forces a faithful representation. An even readout can decode a cover at smaller width, and the gap is unbounded. Below its threshold, the part of the group a mechanism cannot see sets an accuracy ceiling computable before training. 17/17 fitting seeds at minimal width passed tests through length 1000, versus 7/18 at twice the width; 12 models carry correctness certificates to explicit lengths, from the weights alone. On $C_3\times A_4$ (faithful width 5), descent at width 4 learned the 72-state double cover under sign-blind attention (6/48 seeds; monotone 0/48); on a frozen cover the cross-entropy-optimal affine head is uniform, a quadratic head exact. On parsed CLUTRR, transported composition beats a matched transformer by 41 points at 4-10 hops, but forcing isometries costs 65 points; on StepGame's commutative algebra, isometries help. Static embeddings gave each word one vector; contextual models gave each occurrence its own; per-entity frames make each relation an operator, the unit in which relations compose.

Figures & tables

Figure 1: Frames, loops and covers. (a) Under per-entity frames, with the relation data transformed consistently, an invariant score can depend on the pair only through the norms and the transported inner product

\langle x_{i},\,T_{ij}x_{j}\rangle

: transport, then compare (Theorem 1 ). (b) A spanning-tree gauge makes every tree transport

I

; only the loop products

H_{1},H_{2}

survive, up to one common conjugation, and the connection is flat iff they are all

I

(Section 2.3 ). (c) An exact memory need not represent

G

itself: a finite

H\to G

with kernel

\pm I

, acting freely on a generic initial state, has two states

\pm z_{g}

per label; a convex decision cell owning both owns their midpoint

0

, so no convex-cell readout decodes the cover, while a quadratic readout, which reads

zz^{\top}

and so cannot tell

z

from

-z

, decodes it (Theorem 4 ).

group	$\|G\|$	commutative ceiling $1/\|[G,G]\|$	derived length	nilpotency class	$d_{\min}^{O}$	$d_{\min}^{SO}$	$d_{\mathrm{proj}}$	$d_{\mathrm{cov}}$
$D_{4}$	8	$0.5$	$2$	$2$	$2$	$3$	$2$	$2$
$D_{50}$	100	$0.04$	$2$	— (cap $0.04$ )	$2$	$3$	$2$	$2$
$A_{4}$	12	$0.25$	$2$	— (cap $0.25$ )	$3$	$3$	$3$	$3$
$S_{4}$	24	$0.083$	$3$	— (cap $0.083$ )	$3$	$3$	$3$	$3$
$A_{5}$	60	$0.0167$	never (perfect)	— (cap $0.0167$ )	$3$	$3$	$3$	$3$
$Q_{8}$	8	$0.5$	$2$	$2$	$4$	$4$	$4$	$4$

Table 1: Selection rules , computed from each group’s Cayley table before training: the limiting ceiling of any commutative or order-blind mechanism; the depth at which a commutative cascade becomes exact; the signature level at which a signature readout becomes exact (a dash: not nilpotent, every level capped); the minimal faithful width over

O(d)

and

SO(d)

(convex-cell readouts);

d_{\mathrm{proj}}

, the width at which a quadratic or sign-blind readout can decode a double cover (

C_{2n}/\pm I\cong C_{n}

and

D_{2n}/\pm I\cong D_{n}

give

2

for cyclic and dihedral groups; an order-

16

subgroup of

O(4)

gives

4

for

Q_{8}

; for

S_{5}

the standard representation has trivial centre and

PO(3)\cong SO(3)

has no

S_{5}

); and

d_{\mathrm{cov}}

(arbitrary readouts). The three widths first separate at

d_{\min}=5

. The last row is CLUTRR’s kinship composition rules (Section 5.3 ), which contain idempotents and so need non-invertible transports.

Figure 2: Left: readout parity and optimization on

C_{3}\times A_{4}

; fit is

\geq 0.99

at length ten, evaluation success is

1.000

2{,}000

words at every length through

1{,}000

. The registered prototype-attention cells failed to fit; exploratory cells use cosine scores, initial scale ten and doubled training; confirmatory cells re-run them with byte-identical code on seeds

24

–

47

declared in advance. Every successful width-four even cell is a certified double cover (Appendix B.2 ). Right: observed errors occur beyond the computed horizons. Certified horizon of the raw weights (Theorem 6 , record radius) against the first observed error on a random walk, one point per certified run of Table 7 with a positive horizon (

39

runs); every point lies above the diagonal, by a factor of

9

2{,}711

(median

201

) over the

35

uncensored runs; arrows mark walks that found no error.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Group	$\|G\|$	$d_{\min}^{O}$	Raw, in distribution	Raw, $L=300$
$C_{10}$	10	2	1.000	1.000
$D_{4}$	8	2	1.000	1.000
$D_{50}$	100	2	0.898	0.549
$A_{4}$	12	3	1.000	1.000
$S_{4}$	24	3	1.000	0.998–1.000
$A_{5}$	60	3	1.000	1.000

Appendix

Table 2: All eight reported ladder rows. Widths refer to

O(d)

, whereas the controlled

A_{4}/D_{4}

grid below uses

SO(d)

. These are the recorded row summaries; they are not means over a common number of successful seeds.

Figure 3: Exactness at the minimal width, on the seeds of the scripts of record. Accuracy against test length (training words

\leq 10

, polish

\leq 40

) for

A_{4}

and

D_{4}

at the minimal

SO(d)

width

d=3

(seeds

0

–

5

) and at twice it,

d=6

(seeds

0

–

2

of the matched protocol). Every

d=3

seed is exact to length

1000

(blue), and its snapped generators close to a Latin square of

|G|

elements with homomorphism defect at most

6\times 10^{-13}

(Table 7 ); the tick on each curve is its certified horizon under the record radius (

71

–

276

for

A_{4}

100

–

222

for

D_{4}

), one to two orders of magnitude before the first observed error. At

d=6

one seed per group is exact and the others fit the training lengths and alias beyond them (orange), some falling through the abelian ceiling (dotted) to chance (dashed).

Group, width	Readout	Fit	Eval. success	Extracted structure
Registered protocol
$C_{3}\times A_{4}$ , 4	quadratic	2/12	2/12	double cover, 72 states
$C_{3}\times A_{4}$ , 4	affine	0/12	0/12	—
$C_{3}\times A_{4}$ , 4	monotone prototype	0/12	0/12	—
$C_{3}\times A_{4}$ , 4	even prototype	0/12	0/12	—
$C_{3}\times A_{4}$ , 5	affine	6/12	0/12	3 faithful, 36 states

Appendix

Table 3: All fourteen spinor cells. Fit and evaluation success concern raw learned matrices. The final column describes the extracted candidate models and orbit sizes; it is not a statement that the raw matrices generate a finite group. Zero finite-evaluation successes are empirical outcomes, not consequences forced by an all-word impossibility theorem.

Readout	Reported accuracy	Reported cross-entropy
Affine, fitted by cross-entropy	near chance ( $1/36$ )	3.5835 ( $\log 36$ )
Nearest selected lift, affine	0.500	not the optimized objective
Full quadratic	1.000	$\leq 10^{-5}$
Squared prototype	1.000	$\leq 10^{-5}$

Appendix

Table 4: Readout intervention with fixed states. The fitted affine loss is reported to four decimals. The exact theorem applies to the balanced antipodal cover; raw approximate states are a separate empirical test. A selected-lift affine head demonstrates achievable one-half accuracy, not optimal affine classification accuracy.

Task	Mechanism	Train fit	Mean OOD
StepGame	transformer, sinusoidal PE	0.889	0.481
	additive transport, difference readout	—	0.753
	additive transport, probe readout	0.63	0.36
	general linear transport, probe readout	—	0.73
	rotation transport, probe readout	—	0.82
	exact lattice, period 12, probe readout	—	0.84

Appendix

Table 5: Complete reported public-benchmark controls. Transformers have three layers and width 64. StepGame trains on

k\leq 5

and tests on

k=6

–

10

; CLUTRR trains on

k\in\{2,3\}

and tests on

k=4

–

10

. The composer and probe rows use different readouts and cannot be treated as consecutive one-variable interventions. The CLUTRR orthogonal control reports three seeds.

target $G$	constructed $H\leq O(4)$	$\|H\|$	labels	readout separation
$C_{3}\times A_{4}$ ( $d_{\min}=5$ )	$C_{3}\times 2T$ , $x\mapsto q_{1}x\bar{q}_{2}$	72	36	quadratic (min $0.176$ ); $R_{b}^{2}=-I$
$A_{4}\times A_{4}$ ( $d_{\min}=6$ )	$2T\times 2T/\pm(1,1)$	288	144	quadratic
$A_{5}\times A_{5}$ ( $d_{\min}=6$ )	$2I\times 2I/\pm(1,1)$	7200	3600	quadratic

Appendix

Table 6: Constructed cover witnesses at width

4

, verified numerically (closure, kernel

\{\pm I\}

, label count, quadratic separation of the antipodal-pair labels).

run	prot.	fit/ex/ $10^{4}$	orbit	$\epsilon$	$\eta$	cert. $L$	first err.	closure	ker.	defect	$m$	snapped eval
A4A4-6-lin-s2	rec	y/y/1.00	144 (1)	0.1531	2.23/2.23/2.23	14/14/14	14268	144	1	3e-15	3.8	1/1/1
A4A4-6-lin-s9	rec	y/y/0.47	144 (1)	0.2560	1.84/1.84/1.84	7/7/7	2546	144	1	3e-15	2.6	1/1/1
C3A4-4-quad-s1	rec	y/y/0.00	72 (2)	0.0218	0.342/0.471/0.831	15/21/38	1737	72	$\pm I$	3e-13	7.7	1/1/1
C3A4-4-quad-s4	rec	y/y/0.00	72 (2)	0.0216	0.341/0.479/0.784	15/22/36	2872	72	$\pm I$	3e-13	7.6	1/1/1
C3A4-5-lin-s1	rec	y/n/0.05	36 (1)	0.0641	2.58/2.58/2.58	40/40/40	457	36	1	2e-15	6.1	1/1/1
C3A4-5-lin-s2	rec	y/n/0.04	36 (1)	0.0393	2.45/2.45/2.45	62/62/62	533	36	1	2e-15	6.9	1/1/1

Appendix

Table 7: Evidence table, one line per certified or snap-certified run. Run: group (C3A4

=C_{3}\times A_{4}

, A4A4

=A_{4}\times A_{4}

, C3A4 ∗ the 4-letter pilot alphabet), width, readout (lin, quad, pm/pe

=

prototype attention monotone/sign-blind, cm/ce

=

cosine attention monotone/sign-blind), seed; protocol (rec

=

record, exp

=

exploratory, conf

=

confirmatory). Finite evaluation : fit (

\geq 0.99

L=10

) / exact (

1.000

2000

words at

L=1000

) / raw accuracy at

10^{4}

. Raw model : orbit states (cover index), residual

\epsilon

, radius

\eta

(record / operator-norm / exact where computed), certified horizon (same three), first observed error (minimum over the walks run;

\dagger

=

none within the walk, a lower bound). Snapped model : latent closure (LS

=

Latin-square closure of the snapped generators), kernel of the cover (ord. 2

=

order two on a padded block, not

\pm I

), homomorphism defect (floating point), margin

m

on every orbit state, finite evaluation at

10^{3}/10^{4}(/10^{5})

Group	$k=1$	$k=2$	$k=3$	First exact constructed tower
$D_{4}$	$1/2$	1	1	depth 2
$A_{4}$	$1/4$	1	1	depth 2
$S_{4}$	$1/12$	$1/4$	1	depth 3
$A_{5}$	$1/60$	$1/60$	$1/60$	none in this class

Appendix

Table 8: Derived-series limiting ceilings for the finite cascade setting. A finite test length requires the corresponding mixing correction. Constructed witnesses and learned scans are evaluated separately.

Relational Reasoning

Relational reasoning studies how AI systems represent and infer relationships among objects, entities, events, and facts.

See all 35 papers

Sep 1, 2026

Scaled Idempotence in Transformer Attention: Paired OV Geometry and Shared-Value Algebras

We identify a recurrent algebraic regularity in Transformer attention: a sparse subset of effective OV operators

T=OV^\top

nearly closes under composition,

T^2\approxαT

. Across six pretrained endpoints spanning 2.8B--235B parameters, 3.98--8.00% of heads reach squared closure alignment

\mathcal{P}\geq0.9

, while no matched within-layer O/V mismatch does. An exact principal-coordinate factorization,

T=Q_OKQ_V^\top

and

T^2=Q_O(KDK)Q_V^\top

, separates within-support transport from read--write return geometry. Across all 7,304 heads in nine MHA/GQA models, scrambling only the orientation of

K

while preserving singular values, norms, factor spans, and principal angles reduces median closure from 0.336 to

1.04\times10^{-4}

; trained orientation wins for 98.64% of heads and in every layer. Constructive searches show that high closure is feasible in every surveyed layer, but usually not attained. Retrospective trajectories in three independently trained lineages further separate broadly available capacity from the orientations attained by final strong heads. Under exact value sharing, headwise closure extends to a right-action algebra,

T_iT_j=α_jT_i

. Seven-model experiments verify the approximate law and reveal distinct oblique projections with a shared value-defined kernel. These results characterize scaled idempotence as a sparse trained orientation within broadly available geometric capacity and show how value sharing extends a headwise relation into a local operator algebra.

Jiming Feng, Junliang Li

College of Computer Science, Beijing University of Technology Beijing, China · School of Mathematics, Statistics and Mechanics, Beijing University of Technology Beijing, China

Attention Head Analysis Transformer Attention Attention Mechanisms Multi-Head Attention

Ask PDF

May 21, 2026

Structured-Sparse Attention for Entity Tracking with Subquadratic Sequence Complexity

Entity tracking requires maintaining and updating latent states for entities and attributes over long sequences. Recent task-specific attention operators can compress deep Transformer stacks into a few layers by performing multi-hop state propagation within a single layer, but their dense evaluation remains expensive. We show that in this setting, learned attention is strongly structured: most mass concentrates in local block-diagonal neighborhoods with a light cross-block residue. Exploiting this, we derive a blockwise evaluation of a resolvent-style operator that keeps within-block interactions exact and routes cross-block interactions through a reduced system. The resulting evaluation is subquadratic in sequence length

O(n^{4/3}d)

(and

O(n^{7/3})

when

d\approx n

). On controlled tracking benchmarks, our method matches the dense operator's accuracy while reducing wall-clock time by

12-29\%

under a standardized measurement protocol, and is up to

2.4 \times

faster than a compact dense Transformer at comparable exact-match accuracy. We further provide ablations over block size and model capacity, and identify a limitation: performance collapses when the number of simultaneously evolving properties exceeds the number of attention heads.

Hangyue Zhao, Paul Caillon, Erwan Fagnou +1

ESPCI PSL, Paris, France · LAMSADE, Université Paris Dauphine - PSL, Paris, France

Self-Attention Structured Sparsity Transformer Attention Efficient Attention Sparse Attention State Tracking

Ask PDF

Feb 2, 2026

Poly-attention: a general scheme for higher-order self-attention

The self-attention mechanism, at the heart of the Transformer model, is able to effectively model pairwise interactions between tokens. However, numerous recent works have shown that it is unable to perform basic tasks involving detecting triples of correlated tokens, or compositional tasks where multiple input tokens need to be referenced to generate a result. Some higher-dimensional alternatives to self-attention have been proposed to address this, including higher-order attention and Strassen attention, which can perform some of these polyadic tasks in exchange for slower, superquadratic running times. In this work, we define a vast class of generalizations of self-attention, which we call poly-attention mechanisms. Our mechanisms can incorporate arbitrary higher-order (tensor) computations as well as arbitrary relationship structures between the input tokens, and they include the aforementioned alternatives as special cases. We then systematically study their computational complexity and representational strength, including giving new algorithms and matching complexity-theoretic lower bounds on the time complexity of computing the attention matrix exactly as well as approximately, and tightly determining which polyadic tasks they can each perform. Our results give interesting trade-offs between different desiderata for these mechanisms, including a tight relationship between how expressive a mechanism is, and how large the coefficients in the model may be so that the mechanism can be approximated in almost-linear time. Notably, we give a new attention mechanism which can be computed exactly in quadratic time, and which can perform function composition for any fixed number of functions. Prior mechanisms, even for just composing two functions, could only be computed in superquadratic time, and our new lower bounds show that faster algorithms for them are not possible.

Sayak Chakrabarti, Toniann Pitassi, Josh Alman

Computer Science, Columbia University, New York, NY 10027.

Self-Attention Compositional Reasoning Transformer Attention Attention Mechanisms Neural Network Expressivity

Ask PDF

Abstract

Relational Reasoning

Explore similar work

Scaled Idempotence in Transformer Attention: Paired OV Geometry and Shared-Value Algebras

Structured-Sparse Attention for Entity Tracking with Subquadratic Sequence Complexity

Poly-attention: a general scheme for higher-order self-attention