{"id":"496022ca-98e1-4b80-923c-c7546fe40343","arxiv_id":"2412.20195","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"One-layer infinite-precision softmax transformers need at least polynomial embedding dimension or output MLP size to compute function composition or SUM2.","lead":"Using VC dimension bounds, the paper proves the first lower bounds against one-layer softmax transformers with infinite precision: such transformers cannot compute function composition or the SUM2 task unless their embedding dimension or output MLP size is polynomially large. This is a theoretical step toward understanding what attention-based models cannot do, even with unlimited numerical precision.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof's upper-bound engine relies on an unstated exact form of the Goldberg–Jerrum VC bound; division by p+q is undefined when p+q=0, so the hypothesis class needs totalization, though a one-branch patch repairs it.","rationale":"The reader's conditional verdict is well aligned with the manuscript: the two missing arguments are real but readily repairable. I agree that the more consequential missing piece is the precise applicability of the Goldberg-Jerrum VC bound. The computation defining h_{ybar,q} is short and parameterized by only d+1 real numbers, so the bound is almost certainly valid, but the text neither states the theorem nor handles the p+q=0 case. Since the shattering constructions in both theorems only use points with p>0 and parameters with q>0, the undefined region does not affect the lower bound; a simple totalization restores the upper bound. The distinctness issue is also absent from the text, but it follows immediately from correctness of the transformer, so I do not see it as independently threatening the result. The reductions from Comp_n and Sum_{n,n}^2 to shattering are clever and essentially sound: the parametrized family is exactly the transformer's output viewed as a function of the first-block contribution, and the contexts realize all labelings. The paper deserves credit for the core idea, and the proof should be accepted once the Goldberg-Jerrum application and the distinctness argument are stated explicitly. My read does not change the reader's conditional verdict.","tokens_in":5160,"tokens_out":24307,"duration_ms":262710,"concrete_test":"Check the exact statement of Goldberg-Jerrum Theorem 2.3 to confirm that a program using division by p+q is in scope even when p+q can be zero, or that totalizing the class by adding the branch 'if p+q = 0 then output 0' keeps the theorem applicable with operation count O(d+s). If the theorem requires the program to be total before applying it, verify that the patched program has at most d additions, d divisions, one branch, and O(d s) operations for the ReLU network, so the VC dimension bound is still n^{o(1)}. This single check settles whether the upper-bound half of the contradiction is valid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the VC-dimension upper bound for the hypothesis class H = { h_{ybar,q} : h_{ybar,q}(xbar,p) = sign(N(h+(xbar+ybar)/(p+q))) }. This is the only step that prevents H from having VC dimension large enough to shatter the n-1 points constructed in Theorem 1 (or n/2 in Theorem 2). The proof applies Goldberg-Jerrum Theorem 2.3 by counting d+1 parameters and n^{o(1)} arithmetic operations and conditional jumps, but it does not state the theorem's exact hypotheses. In particular, h is undefined when p+q=0, and the theorem as usually stated applies to total functions decided by a finite computation over the reals. The shattering points all have p>0 and the realizing parameters have q>0, so the undefined set is irrelevant to the lower bound; however, the upper-bound argument as written is not fully justified. A one-line patch exists: add a comparison 'if p+q = 0 then output 0' before the division, which adds one branch and leaves the n^{o(1)} operation count unchanged. This makes the Goldberg-Jerrum bound applicable. A smaller related gap is that Theorem 1 does not explicitly prove the points (xbar(a),p(a)) are pairwise distinct; correctness of the transformer forces distinctness, but the argument is omitted. These gaps are fixable, but the VC-applicability issue is the load-bearing one because the contradiction depends entirely on the polynomial-in-(d+s) upper bound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":5489,"tokens_out":7170,"duration_ms":76585,"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":[{"comment":"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":"Section 3, Proof of Theorem 1, VC upper-bound paragraph and hypothesis class (1)"},{"comment":"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.","section":"Section 3, Proofs of Theorem 1 and Theorem 2, shattering steps"}],"minor_comments":[{"comment":"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":"Section 3, Theorem 2"},{"comment":"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":"Section 3, Proof of Theorem 1 and Theorem 2"},{"comment":"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":"Section 3, Proof of Theorem 1"},{"comment":"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.","section":"Section 3, Theorem 3, proof sketch"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a short note with a clean idea, and the two load-bearing gaps are readily closable. I would encourage the editor to request that the authors state the exact Goldberg--Jerrum theorem they rely on and add the missing distinctness arguments; after that, the paper should be publishable. There are no concerns about novelty or citation practices."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nSoft 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.\n\nOne 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.\n\nWho 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.\n\nRecommendation: 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.","headline":"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.","tokens_in":5970,"tokens_out":2032,"would_cite":true,"duration_ms":23780,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T07","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"One-layer softmax transformers need polynomial size even with infinite precision.","keywords":["transformers","lower bounds","VC dimension","softmax attention","infinite precision","function composition","SUM2","ReLU networks"],"falsifier":"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).","tokens_in":4971,"feed_emoji":"🤖","tokens_out":9217,"duration_ms":88293,"temperature":0.7,"pith_summary":"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.","feed_headline":"No small infinite-precision transformer solves composition or SUM2","feed_subtitle":"Either the embedding or the output ReLU network must grow polynomially in input length.","key_machinery":"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.","core_discovery":"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)}$.","pith_inferences":["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$."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the VC-dimension bound for concept classes parameterized by real numbers, which converts the small parameter and operation counts into a small VC dimension.","marker":"[3]"},{"why":"Defines the function-composition task $\\mathrm{Comp}_n$ whose hardness is the paper's first target.","marker":"[6]"},{"why":"Introduces the SUM2 task $\\mathrm{Sum}_{n,n}^2$ and its precision-based lower bound, which the paper extends to infinite precision.","marker":"[7]"}],"fun_headline_variants":["No tiny infinite-precision transformer solves composition or SUM2","Infinite precision doesn't help: composition and SUM2 need polynomial size","Polynomial size required for infinite-precision transformers on composition/SUM2","Tiny infinite-precision transformers can't do composition or SUM2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["No tiny infinite-precision transformer solves composition or SUM2","Infinite precision doesn't help: composition and SUM2 need polynomial size","Polynomial size required for infinite-precision transformers on composition/SUM2","Tiny infinite-precision transformers can't do composition or SUM2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000684,"raw_usage":{"total_tokens":3063,"prompt_tokens":865,"completion_tokens":2198,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":481,"completion_tokens_details":{"reasoning_tokens":2123}},"tokens_in":481,"tokens_out":2198,"duration_ms":17091,"temperature":1.0,"reasoning_tokens":2123,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:28:07.188413+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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).","supporting_citations":[{"cited_title":"W., and Jerrum, M","cited_arxiv_id":null,"evidence_quote":"Supplies the VC-dimension bound for concept classes parameterized by real numbers, which converts the small parameter and operation counts into a small VC dimension."},{"cited_title":"J., and Telgarsky, M","cited_arxiv_id":null,"evidence_quote":"Introduces the SUM2 task $\\mathrm{Sum}_{n,n}^2$ and its precision-based lower bound, which the paper extends to infinite precision."}],"review_version":1}