Lower bounds on transformers with infinite precision

Alexander Kozachinskiy

REVIEW 2 major objections 4 minor 2 cited by

Lower bounds on transformers with infinite precision

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read One-layer softmax transformers need polynomial size even with infinite precision.

desk verdict First infinite-precision lower bound for one-layer transformers, via a VC-dimension technique; proof is basically sound with two small gaps that are easy to patch. read the letter →

arxiv 2412.20195 v1 pith:DUSVJ37Q submitted 2024-12-28 cs.LG cs.AIstat.ML

Alexander Kozachinskiy This is my paper · ORCID

classification cs.LGcs.AIstat.ML MSC 68Q3268T0768Q17

keywords transformerslowerboundsVCdimensionsoftmaxattentioninfiniteprecisionfunctioncompositionSUM2ReLUnetworks

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves the first lower bounds against one-layer softmax transformers that are allowed unlimited numerical precision. It shows that for two simple tasks—composing a function written as a lookup table, and deciding whether two numbers in a list sum to zero—any such transformer needs either an embedding dimension that grows polynomially in the input length or an output MLP with polynomially many ReLU neurons. This means that infinite precision alone cannot make a small one-layer transformer solve these tasks. The proof works by splitting the attention output into two weighted sums, one from each half of the input, and applying a VC-dimension argument to the resulting parametric family of classifiers.

What carries the argument

The central object is the parametric family $F(\bar{x},p;\bar{y},q)=\mathrm{sign}\bigl(N(h+(\bar{x}+\bar{y})/(p+q))\bigr)$, obtained by writing the softmax attention output on a split input as the ratio $(\bar{x}+\bar{y})/(p+q)$. The proof reads this as a hypothesis class on inputs $(\bar{x},p)$, with $(\bar{y},q)$ as parameters. The two tasks are encoded so that one block supplies $(\bar{x},p)$ and the other supplies $(\bar{y},q)$: for $\mathrm{Comp}_n$ the first token is separated from the remaining $n-1$ tokens, and for $\mathrm{Sum}_{n,n}^2$ the first $n/2$ tokens are separated from the last $n/2$. The mechanism is the contradiction between the shattering forced by the task and the upper bound on VC dimension for classes computed by few parameters, operations, and comparisons.

What would settle it

Construct an explicit family of 1-layer single-token output transformers with embedding dimension $n^{o(1)}$ and output ReLU networks of size $n^{o(1)}$ that compute $\mathrm{Comp}_n$ (or $\mathrm{Sum}_{n,n}^2$) exactly for every $n$; the existence of even one such family for infinitely many $n$ would refute Theorem 1 (or Theorem 2).

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is that a 1-layer single-token output transformer with infinite precision cannot compute $\mathrm{Comp}_n$ or $\mathrm{Sum}_{n,n}^2$ unless its embedding dimension $d$ or its output ReLU-network size $s$ is $n^{\Omega(1)}$. Theorems 1 and 2 rule out the regime $d=n^{o(1)}$ and $s=n^{o(1)}$. The argument rewrites the post-attention vector as $(\bar{x}+\bar{y})/(p+q)$, where $(\bar{x},p)$ are determined by one block of input tokens and $(\bar{y},q)$ by the complementary block, and treats the output $\mathrm{sign}(N(h+(\bar{x}+\bar{y})/(p+q)))$ as a hypothesis class on $(\bar{x},p)$ parameterized by $(\bar{y},q)$. If the transformer computed the task, this class would shatter $n-1$ points for $\mathrm{Comp}_n$ and $n/2$ points for $\mathrm{Sum}_{n,n}^2$, so its VC dimension would be at least linear in $n$. But the class is representable with $n^{o(1)}$ parameters, arithmetic operations, and comparisons, which forces its VC dimension to be $n^{o(1)}$.

Load-bearing premise

The load-bearing premise is that a hypothesis class computed with polynomially many parameters, arithmetic operations, and comparisons has VC dimension polynomial in those counts; if the cited bound does not apply to this class, the argument gives no contradiction.

Editorial extensions

If this is right

Any 1-layer softmax transformer computing $\mathrm{Comp}_n$ must have embedding dimension $n^{\Omega(1)}$ or output MLP size $n^{\Omega(1)}$, even with unbounded precision.
The same dichotomy holds for $\mathrm{Sum}_{n,n}^2$, so the existing precision-based lower bounds for this task cannot be evaded by allowing more bits.
$\mathrm{Palindrome}_n$ is not subject to the same obstruction: a constant-embedding, constant-ReLU transformer with infinite precision can decide palindromes, so the VC-dimension wall is task-specific rather than architecture-wide.
The paper explains the difference by noting that the communication matrix for disjointness (behind $\mathrm{Sum}_2$) has VC dimension linear in $n$, while the equality matrix (behind palindrome) has VC dimension 1.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Inference: the same split-ratio argument should apply to any pairwise property whose communication matrix has linear VC dimension, giving infinite-precision lower bounds for a family of tasks that includes set-disjointness variants.
Inference: the result reframes precision as just another resource; because the obstruction is VC-theoretic, it would likely survive in neural networks with smooth activations as long as the output head is a constant-depth threshold circuit of bounded size.
Inference: one could test the bound empirically by training 1-layer transformers with growing embedding dimension and ReLU output heads on $\mathrm{Comp}_n$ and $\mathrm{Sum}_{n,n}^2$; the theorem predicts a sharp phase transition around embedding or width $n^{c}$ for some constant $c>0$.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Two things to know. First, this is the first lower bound against one-layer softmax transformers that does not assume limited precision. The technique is genuinely new to this area: it uses VC dimension of arithmetic hypothesis classes (Goldberg–Jerrum) to show that any transformer solving Comp_n or Sum_2 needs either embedding dimension n^{Omega(1)} or an output MLP with n^{Omega(1)} ReLU neurons, even with infinite precision. Second, the proof is right in its bones. The two gaps I was told about are real, but both are trivial to fix, and neither threatens the main claim.

What the paper does well: the reduction of the transformer's output to a parametric family of functions on (xbar, p) is clean and the shattering arguments are correct. The two lower bounds follow the same template and each is explicit enough to reconstruct. The palindrome example is a nice honesty check, and the short remark about why VC dimension of the communication matrix separates Sum_2 from palindrome is perceptive. The paper is also careful to position itself against prior work; the citations to Peng et al. and Sanford et al. are appropriate, and the novelty is clear.

Soft spots, in proportion: the proof applies Goldberg–Jerrum Theorem 2.3 without stating its exact form. In particular, the hypothesis class is defined with a division by p+q, which is undefined when p+q=0. The shattering uses points with p>0 and parameters with q>0, so a one-line totalization patch (compare p+q to 0 first, output 0) fixes it without changing the operation count. The paper should state that patch. Second, in both theorems the shattered points are asserted to be n-1 or n/2 distinct inputs without proof. Distinctness follows from correctness of the transformer, but it should be argued. Both gaps are exactly what the stress-test note says; they are fixable and the central argument holds.

One framing point: the lower bound is for single-token output transformers with the output computed in one token after one layer. That is the same model as the cited prior work, so it is a fair comparison, but it is a narrow setting. The paper does not overclaim; it says the result is limited to this architecture.

Who is this for? People working on theoretical limits of transformers, especially those who care about precision-free tradeoffs. It is a short note, not a survey, and it reads like one. The proof sketch is compact but sufficient. I would bring it to a reading group and I would cite it if I were writing in this area.

Recommendation: this deserves a serious referee. The result is novel, the proof is plausible and fixable, and the exposition is honest. I would recommend acceptance with minor revisions, mainly the two patches above.

Referee Report

2 major / 4 minor

Summary. The paper proves lower bounds for one-layer, single-token-output softmax transformers with infinite precision. For the function composition task Comp_n and the SUM2 task Sum_{n,n}^2, it claims that any such transformer must have either embedding dimension n^{Omega(1)} or output MLP size n^{Omega(1)}. The argument assumes a transformer with dimension d and MLP size both n^{o(1)}, defines a parametric hypothesis class from the attention output, applies the Goldberg--Jerrum VC-dimension bound to show the class has VC dimension n^{o(1)}, and then shows that solving the task forces the class to shatter n-1 (respectively, n/2) points. The paper also sketches an O(1)-size transformer for palindrome recognition.

Significance. If the proof is completed, the results constitute a notable advance: they provide the first lower bounds for one-layer softmax transformers with infinite precision, bypassing the bit-precision assumption common in earlier communication-complexity arguments. The idea of using VC-dimension bounds on the hypothesis class induced by the attention output is elegant and likely adaptable to other tasks. The shattering constructions are explicit and concrete. However, the proof as written has two gaps that are load-bearing for the central claim: the Goldberg--Jerrum bound is invoked without stating its exact hypotheses and without totalizing the hypothesis class, and the shattering arguments do not prove that the constructed points are pairwise distinct. Both gaps are fixable with short additions, so the central claim appears defensible.

major comments (2)

[Section 3, Proof of Theorem 1, VC upper-bound paragraph and hypothesis class (1)] The proof invokes Goldberg--Jerrum Theorem 2.3 to conclude that the hypothesis class (1) has VC dimension n^{o(1)}, but it does not state the theorem's exact hypotheses, and the class is not total: h_{y,q}(x,p) is undefined when p+q = 0. As written, the upper bound does not follow. The authors should state the version of the theorem they use and add an explicit totalization rule (e.g., set the output to 0 if p+q = 0) before computing h_{y,q}; since the shattering arguments use p_i > 0 and q > 0, the contradiction is unaffected. This is a load-bearing point because the entire proof relies on the polynomial VC upper bound.
[Section 3, Proofs of Theorem 1 and Theorem 2, shattering steps] The proof asserts that the n-1 points (xbar(2),p(2)), ..., (xbar(n),p(n)) are shattered by class (1), but it does not verify that these points are pairwise distinct. If two of them coincided, shattering would be impossible. The same issue occurs for the k points in Theorem 2. The missing argument is short: for a1 != a1' in {2,...,n}, choose a context b with b_{a1} = 1 and b_{a1'} = 2; correctness of the transformer then forces the outputs to differ, so (xbar(a1),p(a1)) and (xbar(a1'),p(a1')) must be distinct. For Theorem 2, one uses beta vectors with a single 1 in distinct positions to separate the points. Please include these justifications.

minor comments (4)

[Section 3, Theorem 2] The proof sets k = n/2, which requires n to be even. The theorem statement quantifies over n without this restriction; the authors should either state the result for even n or explain how odd n is handled (e.g., by padding).
[Section 3, Proof of Theorem 1 and Theorem 2] The expressions for h_{y,q} omit the fact that the fixed transformer parameters K, Q, h, and the weights of N enter the computation; clarifying this notation would make the parameter counting in the Goldberg--Jerrum application easier to follow.
[Section 3, Proof of Theorem 1] The phrase 'VC dimension is polynomial in these quantities' is imprecise; the authors should state the specific polynomial dependence (or at least that it is O(d s) for the relevant circuit model) to make the upper bound checkable.
[Section 3, Theorem 3, proof sketch] The proof sketch is quite terse; providing the actual positional encoding and the key/query matrices (even in a sentence) would make the O(1)-size transformer construction verifiable.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is a self-contained VC-dimension lower bound with no fitted parameters, no predictions, and no load-bearing self-citations.

full rationale

The paper derives lower bounds by contradiction: it assumes a transformer with small embedding dimension and small output MLP solves a task, defines a parametrized hypothesis class from the transformer's computation, upper-bounds its VC dimension via the external Goldberg--Jerrum theorem, and then shows the class must shatter many points if the transformer were correct. This is a standard lower-bound structure and does not reduce to its inputs by definition. There are no fitted parameters, no empirical predictions, and no self-citations; the only cited technical engine is the independent Goldberg--Jerrum VC-dimension bound. The shattering arguments use the assumption that the transformer computes the task to select realizing parameters, which is the normal contradiction method rather than circularity. The manuscript does contain a small rigor gap: the hypothesis class is undefined when p+q=0, and the exact hypotheses of the Goldberg--Jerrum theorem are not stated, but this is a fixable correctness or formality issue, not a circular step. No equation is shown to be equivalent to an input by construction, and no known result is merely renamed. Hence the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no free parameters or invented entities. It relies on the standard infinite-precision model, the Goldberg-Jerrum VC dimension bound, and a distinctness condition that is not stated explicitly but is needed for the shattering argument.

assumptions (4)

domain assumption Real arithmetic with infinite precision, including exact exponentials and division, is available in the model.
The model in Section 2 defines the transformer with real-valued embeddings and exact softmax; the lower bound is for infinite precision.
domain assumption The hypothesis class sign(N(h+(xbar+ybar)/(p+q))) has VC dimension polynomial in the number of parameters d+1 and the number of arithmetic operations and conditional jumps (Goldberg-Jerrum Theorem 2.3).
This is the crux of the n^{o(1)} upper bound; the paper cites [3] but does not state the theorem's conditions, so it is an assumed background result.
ad hoc to paper The n-1 (or k) points used in the shattering arguments are pairwise distinct.
The proofs in Section 3 silently assume this; it follows from correctness of the transformer on the task, but the implication is not written down.
domain assumption An output MLP with s ReLU neurons can be evaluated using n^{o(1)} arithmetic operations and conditional jumps when s = n^{o(1)}.
This is standard for ReLU networks and is used to apply the VC dimension bound.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Lower bounds on transformers with infinite precision." pith.science (2026). https://pith.science/paper/DUSVJ37Q

@misc{pith2026241220195,
  author       = {Pith},
  title        = {Pith review of: Lower bounds on transformers with infinite precision},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DUSVJ37Q}},
  note         = {Machine review of arXiv:2412.20195}
}

abstract

In this note, we use the VC dimension technique to prove the first lower bound against one-layer softmax transformers with infinite precision. We do so for two tasks: function composition, considered by Peng, Narayanan, and Papadimitriou, and the SUM$_2$ task, considered by Sanford, Hsu, and Telgarsky.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Attention-based representations for multi-task computation
cs.LG 2026-08 accept novelty 7.0 of 10

For min/max readout, two attention heads beat one head by an exponential resource gap, and for n-bit parity and symmetric Boolean functions, heads times polynomial degree must reach the threshold degree, with matching...
Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
cs.LG 2025-02 conditional novelty 7.0 of 10

In the unique-hard-attention transformer model, chain-of-thought length must grow linearly with input size for parity, multiplication, median, and reachability.

Reference graph

Works this paper leans on

7 extracted references · 4 canonical work pages · cited by 2 Pith papers

[1]

Sep- arations in the representational capabilities of transformers and recurrent architectures

Bhattamishra, S., Hahn, M., Blunsom, P., and Kanade, V. Sep- arations in the representational capabilities of transformers and recurrent architectures. arXiv preprint arXiv:2406.09347 (2024). 6

arXiv 2024
[2]

Theoretical limitations of multi-layer transformer

Chen, L., Peng, B., and Wu, H. Theoretical limitations of multi-layer transformer. arXiv preprint arXiv:2412.02975 (2024)

arXiv 2024
[3]

W., and Jerrum, M

Goldberg, P. W., and Jerrum, M. R. Bounding the vapnik- chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning 18 (1995), 131–148

work page 1995
[4]

Theoretical limitations of self-attention in neural sequence mod- els

Hahn, M. Theoretical limitations of self-attention in neural sequence mod- els. Transactions of the Association for Computational Linguis tics 8 (2020), 156–171

work page 2020
[5]

Formal language recognition by hard attention transformers: Perspectives from circuit complex ity

Hao, Y., Angluin, D., and Frank, R. Formal language recognition by hard attention transformers: Perspectives from circuit complex ity. Transac- tions of the Association for Computational Linguistics 10 (2022), 800–810

work page 2022
[6]

On limitations of the transformer architecture

Peng, B., Narayanan, S., and Papadimitriou, C. On limitations of the transformer architecture. arXiv preprint arXiv:2402.08164 (2024)

arXiv 2024
[7]

J., and Telgarsky, M

Sanford, C., Hsu, D. J., and Telgarsky, M. Representational strengths and limitations of transformers. In Advances in Neural Infor- mation Processing Systems 36: Annual Conference on Neural I nformation Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA , Decem- ber 10 - 16, 2023 (2023), A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S...

work page 2023

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Sep- arations in the representational capabilities of transformers and recurrent architectures

Bhattamishra, S., Hahn, M., Blunsom, P., and Kanade, V. Sep- arations in the representational capabilities of transformers and recurrent architectures. arXiv preprint arXiv:2406.09347 (2024). 6

arXiv 2024

[2] [2]

Theoretical limitations of multi-layer transformer

Chen, L., Peng, B., and Wu, H. Theoretical limitations of multi-layer transformer. arXiv preprint arXiv:2412.02975 (2024)

arXiv 2024

[3] [3]

W., and Jerrum, M

Goldberg, P. W., and Jerrum, M. R. Bounding the vapnik- chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning 18 (1995), 131–148

work page 1995

[4] [4]

Theoretical limitations of self-attention in neural sequence mod- els

Hahn, M. Theoretical limitations of self-attention in neural sequence mod- els. Transactions of the Association for Computational Linguis tics 8 (2020), 156–171

work page 2020

[5] [5]

Formal language recognition by hard attention transformers: Perspectives from circuit complex ity

Hao, Y., Angluin, D., and Frank, R. Formal language recognition by hard attention transformers: Perspectives from circuit complex ity. Transac- tions of the Association for Computational Linguistics 10 (2022), 800–810

work page 2022

[6] [6]

On limitations of the transformer architecture

Peng, B., Narayanan, S., and Papadimitriou, C. On limitations of the transformer architecture. arXiv preprint arXiv:2402.08164 (2024)

arXiv 2024

[7] [7]

J., and Telgarsky, M

Sanford, C., Hsu, D. J., and Telgarsky, M. Representational strengths and limitations of transformers. In Advances in Neural Infor- mation Processing Systems 36: Annual Conference on Neural I nformation Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA , Decem- ber 10 - 16, 2023 (2023), A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S...

work page 2023