On the Intrinsic Limits of Transformer Image Embeddings in Non-Solvable Spatial Reasoning

Feng Yan; Quan Liu; Siyi Lyu

REVIEW 4 major objections 5 minor 2 references

Under a standard complexity conjecture, constant-depth vision transformers cannot implement a structure-preserving embedding of non-solvable groups such as the 3D rotation group.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 12:27 UTC pith:FWO756OI

load-bearing objection An interesting complexity-theoretic thesis about ViT spatial reasoning, but the formal reduction doesn't close and the trivial-embedding loophole makes the main theorem unproven as stated. the 4 major comments →

arxiv 2601.03048 v2 pith:FWO756OI submitted 2026-01-06 cs.CV cs.AIcs.CC

On the Intrinsic Limits of Transformer Image Embeddings in Non-Solvable Spatial Reasoning

Siyi Lyu , Quan Liu , Feng Yan This is my paper

classification cs.CV cs.AIcs.CC

keywords vision transformersspatial reasoningcircuit complexityTC0 vs NC1word problemnon-solvable groupsmental rotationgroup homomorphism

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper tries to prove that vision transformers fail at spatial reasoning like mental rotation not because of too little data, but because of a hard architectural limit. The authors formalize good spatial understanding as a ''homomorphic spatial embedding''—a mapping from images to vectors that preserves the composition law of the transformation group, such as the 3D rotation group. They argue that any model maintaining such an embedding must implicitly solve the Word Problem, a task that is complete for the circuit class NC1 on non-solvable groups. Since constant-depth transformers with polynomial precision sit in the weaker class TC0, and TC0 is conjecturally strictly weaker than NC1, they conclude that such transformers cannot implement the embedding. They support this with a benchmark showing that frozen supervised and self-supervised vision backbones and a convolutional control all degrade faster on non-solvable rotation sequences than on abelian translations.

Core claim

The paper's central claim is a conditional impossibility theorem: assuming the standard conjecture that TC0 is strictly contained in NC1, no constant-depth vision transformer with polynomial precision can compute a homomorphic spatial embedding for a non-solvable transformation group such as SO(3). The proof has two legs. First, by a classical result, the Word Problem for finite non-solvable groups—for example the icosahedral rotation group A5, a small non-solvable subgroup inside SO(3)—is NC1-complete. Second, constant-depth transformers with polynomial precision are bounded by TC0. If both hold, a vision transformer cannot faithfully encode 3D rotations in the structure-preserving sense; i

What carries the argument

The load-bearing mechanism is the reduction of spatial state-tracking to the Word Problem. A homomorphic spatial embedding makes latent state transitions linear: the final embedding equals the product of operator matrices applied to the initial embedding. Because the representation is faithful—an injective matrix encoding of group elements—computing the final embedding for arbitrary sequences is equivalent to evaluating iterated products in the group. For a non-solvable finite subgroup such as A5, iterated products are NC1-complete, while the transformer's constant-depth, polynomial-precision encoder lies in TC0. The conjectured strict inclusion TC0 ⊊ NC1 then separates the two.

Load-bearing premise

The load-bearing premise is the claimed equivalence between visual state tracking and the group Word Problem: the proof shows a structure-preserving encoder would have to multiply operator matrices, but it never constructs a reduction from word instances to rendered images, nor shows that encoders that are not structure-preserving still face the same requirement; if that equivalence gives way, the barrier reduces to the generic conjecture that TC0 circuits cannot solve NC1-ha

What would settle it

Find a constant-depth, polynomial-precision vision encoder that, on a non-solvable rotation benchmark similar to the paper's Level 3, tracks long sequences (N > 10) with an error ratio close to the abelian level and requires no recurrence or hard-coded equivariant layers. A reproducible result of that kind would either put an NC1-hard task inside TC0 or show the task is not actually NC1-hard.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

If the theorem is correct, increasing data or parameter count in fixed-depth vision transformers cannot fix mental-rotation failures on non-solvable transformations; the limitation is architectural, not statistical.
The same barrier should apply to any constant-depth encoder with polynomial precision, including MLPs and state-space models, not just vision transformers.
Adding recurrence or chain-of-thought could in principle escape TC0, but the paper argues that analog drift and exponential error accumulation will plague continuous visual state tracking in practice.
Equivariant architectures that hardwire rotation structure into fixed kernels may encode the local group table, but the paper claims their learnable dynamics remain within threshold circuits and still cannot solve long group products.
Non-solvable group benchmarks can serve as a targeted test separating genuine compositional geometric reasoning from pattern matching in vision encoders.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Editorial extension: a direct testable prediction is that increasing width, precision, or data on the benchmark's non-solvable level will hit a floor in the Level-3-versus-Level-1 error ratio, whereas equivalent scaling on a solvable group of similar visual complexity should keep improving.
Editorial extension: the 'Abelian Collapse' conjecture implies a measurable signature in latent spaces—linear probes trained on non-solvable sequences should find approximately commuting predicted operators even when the true ground-truth operations do not commute.
Editorial extension: the same group-theoretic lens predicts that any non-solvable finite structure embedded in a scene, not just 3D rotations, will trigger the same collapse; this could be tested with abstract relational inputs whose transformation group is A5 itself rather than SO(3).
Editorial extension: if the word-problem reduction is not established for non-homomorphic encoders, the spatial specificity of the barrier is not yet proven; a construction that maps arbitrary word instances to rendered image sequences would close that gap.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

An interesting complexity-theoretic thesis about ViT spatial reasoning, but the formal reduction doesn't close and the trivial-embedding loophole makes the main theorem unproven as stated.

read the letter

You should know two things about this paper. First, it's worth reading: it frames ViT failures on mental rotation and 3D tracking as an architectural complexity barrier rather than a data-scaling problem, and that framing is genuinely new. Second, the central theorem as stated is not proven, because the formal definition of the embedding admits a trivial constant-zero solution, and the reduction from the spatial task to the Word Problem is asserted rather than constructed.

The paper does several things well. It builds on solid external results: the TC0 bound for transformers (Merrill-Sabharwal, Chiang) and Barrington's theorem on NC1-completeness of word problems for non-solvable groups. It is honest about the conjecture-dependence of TC0 ⊊ NC1 and labels its Abelian Collapse corollary as a conjecture. The LSA benchmark is a reasonable way to probe whether frozen features preserve group structure, and the observation that non-solvable sequences degrade faster than abelian ones is directionally consistent with the thesis.

But the soft spots are load-bearing. Definition 4.1 only requires E(g·I)=ρ(g)E(I); a constant encoder E≡0 satisfies this for any group and any faithful ρ, so a Homomorphic Spatial Embedding trivially exists in TC0. Unless you add injectivity or state-tracking to the definition, Theorem 4.4 is false as stated. Even with injectivity added, Lemma 4.2 does not supply a real reduction: the ViT sees rendered images, not generator words, and the equation z_final = [∏ρ(g_i)]z0 is a constraint on the output, not a computation of the iterated product. For a finite subgroup like A5 with finitely many poses, a constant-depth threshold circuit could implement an equivariant lookup table, so NC1-hardness of the Word Problem does not transfer without an explicit word-to-image encoding whose circuit complexity is shown to be small enough. The paper never gives that encoding. There's also a smaller but real gap in Appendix A.0.3: density of the subgroup generated by 30° rotations in SO(3) does not imply it contains a copy of A5, so the benchmark's NC1-hardness claim is unsupported as written.

The empirical study is confounded in ways the paper partly acknowledges: frozen supervised backbones have training-induced invariance, and the recursive probe error measures repeated composition of the learned linear probe, not the encoder's single-pass capacity. DINOv2 gives a cleaner test, but the single-seed results and the visual difficulty differences between 2D translation and 3D rotation make the numbers suggestive rather than conclusive. The 3.0–3.8× error ratios are consistent with the theory but do not establish it.

Who is this for? Researchers working on understanding why ViTs fail at spatial tasks, and on complexity-theoretic analyses of transformers. The thesis deserves serious referee attention — this is not a desk reject. But it needs major revision: fix Definition 4.1 so the problem is well-posed, construct the reduction in Lemma 4.2 or state what is needed for it, correct the A5/density claim, and soften the empirical conclusions to what the data actually supports. I'd send it to peer review with that expectation.

Referee Report

4 major / 5 minor

Summary. The paper argues that constant-depth Vision Transformers cannot implement structure-preserving (homomorphic) spatial embeddings for non-solvable transformation groups such as SO(3). Its theoretical route combines three ingredients: Definition 4.1 formalizes a spatial embedding as an equivariant map E(g·I)=ρ(g)E(I); Lemma 4.2 claims that such an embedding makes the visual state-tracking task computationally equivalent to the Word Problem for the group; Theorem 4.4 then concludes, under TC0 ⊊ NC1, that a constant-depth ViT with polynomial precision cannot implement such an embedding. The paper also introduces the Latent Space Algebra (LSA) benchmark, where frozen ViT-B/16, DINOv2, and ResNet-50 features are probed with a recursively applied linear map trained on atomic transformations and tested on longer sequences. The empirical claim is that Level 3 (non-solvable) transformations cause faster structural collapse than Level 1 (abelian) transformations.

Significance. If Theorem 4.4 were correct, the paper would supply a crisp complexity-theoretic explanation for the widely observed spatial reasoning failures of ViTs, going beyond data-scale or optimization narratives. The paper correctly invokes standard external results: Barrington's theorem for NC1-completeness of word problems over non-solvable groups, and the TC0 upper bound for log-precision transformers. The LSA benchmark is a reasonable empirical probe of whether frozen features support linear state tracking. However, the central theorem is not established: the formal definition allows vacuous embeddings, the word-to-image reduction is asserted rather than constructed, and even a strengthened single-image formulation is contradicted by a finite-subgroup lookup argument. The empirical study is suggestive but does not isolate the proposed complexity mechanism. Thus the paper's main contribution, as currently written, is not supported.

major comments (4)

[§4.1, Definition 4.1] The equivariance condition E(g·I)=ρ(g)E(I) is satisfied by the constant encoder E≡0 for any faithful ρ, since 0=ρ(g)0. Thus Theorem 4.4 is false as stated: a trivial Homomorphic Spatial Embedding exists in TC0 for every group. Even if one adds injectivity, for a finite non-solvable subgroup such as A5 there are only finitely many orbits of images, and a constant-depth threshold circuit can implement an injective equivariant lookup table from the final image to a one-hot state vector. Therefore the single-image formulation cannot yield the claimed NC1 lower bound via Barrington's theorem.
[§4.2, Lemma 4.2] The proof derives only the identity z_final = [∏ρ(g_i)]z_0 for a homomorphic E. It does not construct a reduction from Word Problem instances to the ViT's inputs. The ViT sees rendered images, not the generator word; for a finite group the final image uniquely identifies the final pose, so the output can be obtained by recognition without computing the iterated product. No word→image encoding is given, and no argument shows that such an encoding lies in a circuit class weak enough to preserve the TC0/NC1 argument. The asserted 'computational equivalence' is therefore unsupported, and Theorem 4.4 collapses to a generic conjecture-dependent statement.
[§5.1 / Appendix A.0.3] The Level 3 benchmark claims that the subgroup generated by 30° rotations about the coordinate axes is dense in SO(3) and contains a subgroup isomorphic to A5. Density of a generated subgroup does not imply that it contains a given finite subgroup; many dense subgroups of SO(3) contain no nontrivial finite subgroups at all. The benchmark must either explicitly use generators of a non-solvable finite subgroup (e.g., the standard A5 generators) or prove that the generated subgroup is non-solvable. Without this, LSA Level 3 does not instantiate the NC1-hard setting used in the theory.
[§5.3–5.4] The experiments do not directly test Theorem 4.4. They train a linear probe on atomic transitions and then recursively apply it; this measures the linearizability of frozen features, not the circuit complexity of a constant-depth ViT. Error accumulation in the recursive probe is a different phenomenon from the TC0/NC1 boundary. No positive control (e.g., a recurrent network or a deeper architecture that succeeds on Level 3) is provided, and no confidence intervals or significance tests are reported. Thus the empirical results are suggestive but do not validate the complexity boundary claimed in the conclusion.

minor comments (5)

[§4.5, Corollary 4.5] Corollary 4.5 is labeled a corollary but is explicitly a conjecture ('We conjecture...'). It should be renamed or clearly marked as a conjecture, not a proved consequence.
[§5.4, Figures 2–3] The text reports '3.0×–3.8×' and '3–3.8×' in different places, and no variance or error bars are shown. Report standard deviations or confidence intervals for all ratios and loss trajectories.
[§4.3, Proposition 4.3] The cited TC0 upper bounds (Merrill & Sabharwal; Chiang) are for log-precision transformers, while the proposition states O(poly(n)) precision. Please clarify the precise precision regime and cite the exact theorem that covers the stated case; otherwise the upper bound is not fully supported by the references given.
[§5.3, Algorithm 1] The action embedding e_s is used in the probe but is not formally defined in the theoretical framework. State how e_s is constructed and whether it is also assumed to satisfy any group-structure condition.
[§6, Impact Statement] The impact statement says the paper 'prov[es] an intrinsic complexity barrier'. Given the issues in Theorem 4.4, this overstates the result. Please temper the language to match what is actually established.

Circularity Check

0 steps flagged

No circular derivation: the barrier is a conditional lower bound assembled from external circuit-complexity theorems; LSA results are an independent empirical check, not fitted inputs.

full rationale

The derivation chain is not circular. Theorem 4.4 is a conditional implication from three external ingredients: Barrington's theorem (word problem for finite non-solvable groups is NC1-complete), Beaudry et al.'s product/decision equivalence for finite groups, and Merrill-Sabharwal/Chiang's result that constant-depth log-precision transformers lie in TC0. None of these are derived from the paper's own definitions or data, and none are self-citations. Definition 4.1 defines homomorphic spatial embeddings by an equivariance equation, not by the word problem; Lemma 4.2 derives the iterated-product form from that equation and then invokes the external hardness results. The empirical section is a validation, not a premise: the linear probe is trained on atomic transitions (N=1) and evaluated on longer recursions, and the reported Level-3 vs Level-1 error ratios are measured outcomes rather than quantities used to prove Theorem 4.4. No fitted parameter is relabeled as a prediction. The only conjecture-like statement, Corollary 4.5, is explicitly labeled a conjecture and is not load-bearing. There are substantive correctness risks in the paper—the Lemma 4.2 reduction does not construct a word-to-image encoding or show it lies in a sufficiently weak circuit class, and Appendix A.0.3 asserts A5-containment from density without proof—but those are mathematical-validity concerns, not circularity.

Axiom & Free-Parameter Ledger

5 free parameters · 7 axioms · 0 invented entities

The theory itself has no fitted degrees of freedom: it composes Barrington's theorem, the Beaudry et al. word/evaluation equivalence, and the proved TC0 upper bound for transformers with the conjecture TC0 ⊊ NC1. The free parameters listed are benchmark-design constants that affect only the empirical validation, plus the unspecified action embedding of the probe. The genuinely load-bearing ad hoc premises are Lemma 4.2's reduction and the claimed density/containment of A5 in the Level-3 generated subgroup, neither of which is rigorously established.

free parameters (5)

Level 3 atomic rotation angle θ = 30° (π/6 rad)
Hand-chosen benchmark constant (Appendix A.0.3) chosen to avoid trivial symmetries (90° excluded) and to generate a dense rotation subgroup; affects the empirical study, not the theorem.
Level 2 scale factor σ = 1.2
Hand-chosen benchmark constant (Appendix A.0.2) defining the solvable-level generators; empirical study only.
Level 1 translation step δ = 20 pixels
Hand-chosen benchmark constant (Appendix A.0.1) defining the abelian-level generators; empirical study only.
Level 3 fixed translation vector v = [0.15, 0.15, 0.0] in normalized camera space
Hand-chosen sixth generator (Appendix A.0.3); empirical study only.
Probe action embedding e_s = unspecified (learned or fixed)
Appendix B.1 describes the probe input [z; e_s] but does not specify how e_s is obtained; if learned it is fitted during probe training and matters for reproduction.

axioms (7)

domain assumption TC0 ⊊ NC1 (circuit complexity separation conjecture)
Theorem 4.4 and the abstract's barrier conclusion are conditional on this unproved conjecture; stated explicitly in Sections 3.2 and 4.4.
standard math Word problem of finite non-solvable groups is NC1-complete (Barrington's Theorem)
Cited as Barrington (1986) and used in Lemma 4.2 and Theorem 4.4; proved theorem, not original to this paper.
standard math Log/poly-precision transformers with softmax attention lie in uniform TC0 (Merrill & Sabharwal 2023; Chiang 2025)
Proposition 4.3 inherits these proved bounds; the additions (NC0 patch embedding, AC0/NC0 positional encodings) are standard closure arguments.
standard math Word-evaluation and word-decision are equivalent for finite groups (Beaudry et al. 1997)
Invoked in Section 3.3 to equate predicting the final state with deciding whether a product is the identity.
ad hoc to paper The visual tracking task is computationally equivalent to the Word Problem, including a word→image encoding within the relevant circuit classes (Lemma 4.2)
Load-bearing unproven premise. The proof only shows z_final = [∏ρ(g_i)]·z0 for homomorphic embeddings; it does not construct the reduction from word instances to ViT image inputs, analyze the circuit complexity of rendering/encoding, or treat non-homomorphic encoders. Section 4.2.
ad hoc to paper The subgroup generated by the Level-3 generators is dense in SO(3) and contains A5
Appendix A.0.3: "the subgroup generated by these rotations is dense in SO(3)—which contains a subgroup isomorphic to A5—this level presents an NC1-hard modeling challenge." Density of G' and A5 ⊆ SO(3) do not imply A5 ⊆ G'; asserted without proof or citation.
domain assumption A linear probe trained on atomic transitions suffices to detect whether a frozen embedding is homomorphic
Section 5.3 assumes success/failure is attributable to the frozen backbone; requires the probe to recover the linear actions ρ(g) from N=1 data if they exist, and depends on the unspecified action embedding e_s.

pith-pipeline@v1.3.0-alltime-deepseek · 13755 in / 42366 out tokens · 379796 ms · 2026-08-03T12:27:06.831644+00:00 · methodology

0 comments

read the original abstract

Vision Transformers (ViTs) excel in semantic recognition but exhibit systematic failures in spatial reasoning tasks such as mental rotation. While often attributed to data scale, this work argues that the limitation arises from the intrinsic circuit complexity of the architecture. By formalizing spatial understanding as learning a Group Homomorphism Problem -- where latent embeddings preserve the algebraic structure of physical transformations acting on images -- we identify a fundamental computational bottleneck. Specifically, for non-solvable groups (e.g., $\mathrm{SO}(3)$), maintaining such structure-preserving embeddings is lowerbounded by the Word Problem, which is $\mathsf{NC^1}$-complete. In contrast, constant-depth ViTs with polynomial precision are strictly bounded by the complexity class $\mathsf{TC^0}$. Under the standard conjecture $\mathsf{TC^0} \subsetneq \mathsf{NC^1}$, a complexity boundary emerges: constant-depth architectures lack the logical depth required to capture non-solvable spatial structures in a single forward pass. To empirically validate this theoretical gap, we propose the Latent Space Algebra (LSA) benchmark, which reveals a significant degradation in ViT representations as the compositional depth of non-solvable tasks increases.

Figures

Figures reproduced from arXiv: 2601.03048 by Feng Yan, Quan Liu, Siyi Lyu.

**Figure 1.** Figure 1: The Homomorphism Alignment Problem. We illustrate our core research inquiry: Given a sequence of input observations transformed by a group G (e.g., a rotating bunny), can a constant-depth ViT encoder map them to a latent sequence where the induced transition dynamics H preserve the group structure (H ∼= G)? We theoretically and empirically demonstrate that for non-solvable groups like SO(3), this isomorphi… view at source ↗

**Figure 2.** Figure 2: Absolute Loss Trajectories. The prediction error (MSE and Cosine) vs. Sequence Length N. A consistent hierarchy (L3 ≫ L2 > L1) is observed across all models before they hit the failure threshold. All models exhibit a trend where error increases with N, but the rate is highly dependent on algebraic structure. Level 3 (Non-Solvable) consistently incurs 3-3.8× higher error than Level 1 (Abelian), validating t… view at source ↗

**Figure 4.** Figure 4: Metric Sensitivity and Divergence Speed. Comparison of MSE vs. Cosine loss growth. Supervised models (ViT-B, ResNet) show a catastrophic divergence in Cosine loss (approx. 6× faster than MSE), indicating a lack of orientation awareness. DINOv2 is more balanced, yet still suffers from rapid degradation on Level 3, confirming the architectural barrier. 6. Conclusion We theoretically establish that spatial r… view at source ↗

**Figure 3.** Figure 3: Structural Collapse relative to Baseline. The loss normalized by the Identity Baseline (Loss/LossIdentity). A ratio ≥ 1.0 (dashed line) indicates the model performs worse than a static guess (zpred = z0). Note that Level 3 (red) consistently approaches this collapse threshold faster than Level 1 (blue), except in supervised Cosine loss where invariance causes immediate failure. 3. Architectural Comparison… view at source ↗

**Figure 5.** Figure 5: Visualizing the Algebraic Hierarchy. We display sample atomic transitions (N = 1) for the Bunny and Dragon objects across the three complexity levels. Left (Level 1): Pure 2D translations preserve orientation and scale. Center (Level 2): Affine transformations introduce scaling centered on the frame, altering size but maintaining 2D planar orientation. Right (Level 3): 3D Rotations introduce outof-plane t… view at source ↗

discussion (0)

Reference graph

Works this paper leans on

2 extracted references · 1 linked inside Pith

[2]

This is particularly relevant for models like DINOv2 where geometry is often encoded in directionality

Cosine Distance:Maximizes the angular similarity, ignoring magnitude variations. This is particularly relevant for models like DINOv2 where geometry is often encoded in directionality. LCos = 1− ˆznext ·z target ∥ˆznext∥∥ztarget∥ (6) B.4. Evaluation Protocol During the recursive evaluation phase, we test the probe’s generalization on sequence lengths N ra...
[235]

Peng, B., Narayanan, S., and Papadimitriou, C

PMLR, 2024. Peng, B., Narayanan, S., and Papadimitriou, C. On limitations of the Transformer architecture. In Proceedings of the Conference on Language Modeling (COLM), 2024. Qi, J., Liu, J., Tang, H., and Zhu, Z. Beyond semantics: Rediscovering spatial awareness in Vision-Language Models, 2025. Romero, D. W. and Cordonnier, J.-B. Group Equivariant Stand-...

Pith/arXiv arXiv 2024

[1] [2]

This is particularly relevant for models like DINOv2 where geometry is often encoded in directionality

Cosine Distance:Maximizes the angular similarity, ignoring magnitude variations. This is particularly relevant for models like DINOv2 where geometry is often encoded in directionality. LCos = 1− ˆznext ·z target ∥ˆznext∥∥ztarget∥ (6) B.4. Evaluation Protocol During the recursive evaluation phase, we test the probe’s generalization on sequence lengths N ra...

[2] [235]

Peng, B., Narayanan, S., and Papadimitriou, C

PMLR, 2024. Peng, B., Narayanan, S., and Papadimitriou, C. On limitations of the Transformer architecture. In Proceedings of the Conference on Language Modeling (COLM), 2024. Qi, J., Liu, J., Tang, H., and Zhu, Z. Beyond semantics: Rediscovering spatial awareness in Vision-Language Models, 2025. Romero, D. W. and Cordonnier, J.-B. Group Equivariant Stand-...

Pith/arXiv arXiv 2024