{"id":"b243f4cd-9c6d-4516-9543-37bde115a753","arxiv_id":"2608.12671","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":0.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey compiling known results that place transformer language recognizers in circuit classes AC0, TC0 and, with chain-of-thought, up to DTIME[n^2], PTIME, and Turing machines.","lead":"This paper is a survey that maps known results on what languages transformers can recognize, using circuit complexity classes as the measuring stick. It is a useful entry point for researchers, but it contains no new theorems and several of its summary statements are internally inconsistent.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The theorem statements in Section 4 are not tied to the formal model of Section 2, so the headline calibration is not established for the survey's own architecture; footnote 3 concedes the unbounded-Co T bullets are outside the formal definition.","rationale":"The reader's weakest assumption identifies exactly the same risk: the survey transfers results from cited papers without stating the exact architectural hypotheses each theorem requires. My read agrees and adds that this is not merely a presentation issue: the paper defines a precise architecture in Sections 2.3–2.4, then states theorems that are not proven for that architecture and, in the unbounded-Co T bullets, are not even expressible under the formal definition because f(n) must be given in advance. This is a genuine correctness risk for the survey's central calibration claim, since a reader cannot verify the map without going to the primary sources for every bullet. It is not a fatal flaw: the paper is a survey, it openly defers to primary sources, and the discrepancies are likely fixable by adding the missing hypotheses and correcting the UHAT/AHAT slip. The concrete test would settle whether any specific bullet actually fails under the paper's own definitions; until then, conditional acceptance remains the right verdict, so the reader's judgment stands unchanged.","tokens_in":11863,"tokens_out":11346,"duration_ms":118724,"concrete_test":"Take the first bullet of Theorem 4.1 and instantiate the Section 2.3 encoder definition with multi-head attention, residual connections, ReLU feedforward, and sigmoid output; then re-run Hao et al.'s AC0 containment construction from [10, Section 7] on that model. If the construction assumes a single attention head, no residual connections, a different output gate, or exact real arithmetic, record where the proof breaks. If it breaks, the bullet is not supported by the cited source for the paper's architecture; if it goes through, the transfer concern is weakened for at least the core AC0 part of the map.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that transformer expressivity is accurately calibrated by circuit classes; Theorems 4.1 and 4.2 are the evidence. The load-bearing problem is that those theorems are not stated for the formal architecture defined in Sections 2.3–2.4. In Section 2.4, a decoder with chain-of-thought is defined only for a pre-specified number f(n) of intermediate tokens, yet the last two bullets of Theorem 4.2 assert Turing completeness with unbounded CoT. Footnote 3 concedes that this requires an acceptance-token stopping model 'we have not formalized.' The tightness discussion later introduces a poly(n) embedding-dimension condition that is absent from the theorem statements, and the theorem statements never specify the rounding or arithmetic model behind O(1)/O(log n) precision. Consequently, as written, the containments are not derived from the survey's own definitions; they are imported from sources whose exact assumptions the survey explicitly declines to state. The post-theorem summary's UHAT/AHAT slip is a symptom of this imprecision. The concern is not that the literature is wrong, but that the survey's calibration claim cannot be checked without re-deriving every bullet.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper surveys recent results on the expressive power of transformer encoders and decoders as formal language recognizers, organized around a parameterized architecture (attention type, precision, chain-of-thought length) and compared against circuit and classical complexity classes. The main claims are Theorem 4.1, that UHAT encoders with arbitrary rational precision recognize only AC0 and that SMAT/AHAT encoders with O(1) or O(log n) precision recognize only AC0 or TC0 respectively, and Theorem 4.2, that chain-of-thought decoders range from AC0 up to PTIME and Turing completeness. The survey explicitly presents itself as a compilation of known results rather than a source of new derivations, but it asserts that circuit complexity has by and large emerged as the correct framework for calibrating transformer expressivity.","tokens_in":11894,"tokens_out":4906,"duration_ms":49432,"significance":"If the compilation is accurate, the paper provides a useful map of a rapidly moving literature, connecting transformer variants to AC0, TC0, DTIME[n^2], PTIME, and Turing completeness. Its strengths are a clean organization of the parameter space (attention mode, precision, chain-of-thought length, masking), a helpful descriptive-complexity section linking circuit classes to logical formalisms, and an honest acknowledgment that the reader must consult the primary sources for exact architectural assumptions. The paper ships no new proofs, code, or machine-checked artifacts; its value is as a literature survey. The significance of the central calibration claim is high, but only if the theorem statements are tied to the model formalized in Section 2; as written, the formal gaps discussed below prevent the paper from establishing that claim on its own terms.","major_comments":[{"comment":"The sentence \"The fourth and fifth bullet points are equivalences: every recursively enumerable language is computable by a UHAT decoder with an unbounded amount of chain-of-thought\" contradicts the bullet points it refers to: bullet 4 concerns AHAT decoders and PTIME, and bullet 5 concerns AHAT decoders and simulation of arbitrary Turing machines, not UHAT decoders or recursively enumerable languages. This is not a harmless slip: footnote 3 concedes that the unbounded-CoT Turing-completeness statement requires a stopping-token model \"we have not formalized,\" whereas Section 2.4 defines chain-of-thought only for a pre-specified number f(n) of intermediate tokens. The strongest bullets of Theorem 4.2 are therefore not stated for the architecture formally defined in Section 2.4, and this undermines the paper's headline claim that the expressivity of transformers is calibrated by circuit and classical complexity classes.","section":"§4.2 (discussion after Theorem 4.2)"},{"comment":"The theorem statements omit the exact architectural hypotheses required to transfer the cited results to the architecture defined in Sections 2.3-2.4: the precision model (whether O(1) or O(log n) means fixed-precision arithmetic with specific rounding conventions, or exact rational arithmetic with bit-length bounds), the role of positional encodings, and the growth of the embedding dimension as a function of n. The sentence \"we encourage the reader to refer to the relevant work for the exact assumptions on the architecture\" makes the containments in Theorem 4.1 unverifiable from the paper's own definitions. Since these containments are the central evidence for the survey's calibration claim, the compilation is not yet a self-contained statement of the results it surveys.","section":"§4.1 (Theorem 4.1 and preceding paragraph)"},{"comment":"The tightness discussion introduces a condition absent from Theorem 4.1: \"when one allows poly(n) embedding dimension, transformers with O(1) precision and O(log n) precision capture all of AC0 and TC0.\" The theorem statements and the parameter discussion in Section 2.2 do not specify any growth rate for the embedding dimension d, and the earlier text only says d \"is allowed to depend on the context length n.\" As written, the \"essentially tight\" claim is not connected to the theorem it is meant to qualify, and the reader cannot tell whether the containments in Theorem 4.1 hold for the same parameter regime as the converse statements.","section":"§4.1 (tightness discussion)"}],"minor_comments":[{"comment":"The sentence \"The evolutions of LLMs has seen a shift from encoder models\" should be \"The evolution of LLMs has seen a shift,\" and a few other grammatical slips suggest the manuscript would benefit from a light copyedit.","section":"§2.1"},{"comment":"The typesetting of the attention formula is inconsistent: the inner product q_i^T k_j / sqrt(d_key) is shown with the division inside the scalar product, and the display of Eq. (1) is malformed. This makes the definition of attention scores unnecessarily hard to read.","section":"§2.3, Eq. (1)-(2)"},{"comment":"The discussion before Theorem 4.1 says \"allowing this precision to arbitrary real numbers\" can increase expressivity, but Theorem 4.1's first bullet restricts the claim to \"arbitrary (rational) precision.\" The distinction between real and rational precision should be stated consistently, since the architecture in Section 2.3 uses real-valued vectors throughout.","section":"§4 (precision discussion)"},{"comment":"In the decoder definition, the sentence \"the output layer takes the d-dimensional vector x^{(L)}_{n+f(n)-1}\" is correct but slightly confusing because it describes converting the final timestep to a probability; a brief pointer to the fact that this is the vector that would otherwise produce the final token would improve readability.","section":"§2.4"},{"comment":"The reference for Chen, Peng, and Wu lists both 2024 and 2025 (FOCS) identifiers; please unify the citation to the published version.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is best evaluated as a survey, not as an original contribution, and that is an acceptable mode for the venue. The central problem is that the authors' own formal definitions in Section 2 are not the ones used by the theorem statements in Section 4; the sentence before Theorem 4.1 explicitly defers to external sources for exact assumptions, and footnote 3 concedes that the unbounded-CoT claim uses a model not formalized in the paper. These issues are fixable by rewriting the theorem statements with explicit hypotheses and aligning them with the formal architecture, or by softening the survey's calibration claim to match what is actually stated. There is no evidence of citation misconduct; the errors appear to be imprecision in compilation rather than misattribution of results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a survey, not a research paper, and it should be read as one. The authors compile known results on transformer expressivity into a convenient map: UHAT encoders land in AC0; SMAT and AHAT encoders with O(1) precision stay in AC0; with O(log n) precision they reach TC0; and with chain-of-thought they jump to DTIME[n^2], PTIME, and Turing completeness. The abstract's claim that circuit complexity is the right lens for this literature is defensible, and the survey makes that case clearly.\n\nWhat the paper does well: the architecture section is careful and readable. Treating attention type, precision, and chain-of-thought as explicit resources is exactly the right framing, and the discussion of why one might prefer circuit classes over the Chomsky hierarchy is sensible. The survey is honest about deferring to primary sources for exact hypotheses, and I see no self-citations or invented entities. For a newcomer, this is a genuinely useful entry point.\n\nThe soft spots are real but not fatal. After Theorem 4.2, the text says the fourth and fifth bullet points are equivalences and attributes them to UHAT, but bullet four is about AHAT with poly(n) CoT recognizing PTIME, and bullet five is about AHAT with unbounded CoT simulating Turing machines. \"Simulate\" is one direction, and \"every recursively enumerable language is computable\" requires the acceptance-token stopping rule that footnote 3 admits was never formalized. That footnote is important and should be elevated, because the formal definition in Section 2.4 fixes f(n) in advance while the theorem statement allows unbounded CoT. The other issue is that the tightness discussion introduces a poly(n) embedding-dimension condition that is absent from the theorem statements. The authors do point readers to the sources, so this is a presentation defect, but it matters for anyone trying to use the survey without reading the originals.\n\nFor a survey, this is a solid piece. It is not ground-breaking, but it does not need to be. The errors are fixable, and the core compilation appears faithful. I would send it to peer review with the expectation of minor revision: fix the UHAT/AHAT slip, qualify the \"equivalence\" language, and either formalize the acceptance-token model or explicitly mark the Turing-completeness bullet as informal.","headline":"A compact, clearly written survey of transformer expressivity that maps known results onto circuit classes, with a few fixable presentation defects rather than any load-bearing flaw.","tokens_in":12677,"tokens_out":2948,"would_cite":false,"duration_ms":30634,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Transformer expressivity is calibrated by circuit classes, and chain-of-thought lifts decoders from AC0/TC0 to PTIME and Turing completeness.","keywords":["transformers","models of computation","circuit complexity","AC0","TC0","chain-of-thought","numerical precision","language recognition"],"falsifier":"A single counterexample under the survey's stated assumptions would refute the calibration: exhibit a language computed by a constant-depth, $O(\\log n)$-precision softmax-attention encoder, as defined in Section 2, that is provably not in $\\mathsf{TC}^0$. Alternatively, re-derive the third bullet of Theorem 4.1 from its cited sources and check whether any source tacitly requires polynomial embedding dimension; if the inclusion fails without that condition, the theorem as printed is false.","tokens_in":11468,"feed_emoji":"⚙️","tokens_out":12895,"duration_ms":120653,"temperature":0.7,"pith_summary":"Transformers are usually judged by what they do in practice, but this paper treats them as formal language recognizers and asks which traditional complexity classes contain them. Its central claim is that circuit complexity supplies the right scale: constant-depth uniform circuits with AND/OR/NOT gates ($\\mathsf{AC}^0$) and with majority gates ($\\mathsf{TC}^0$) contain every transformer equipped with hard or soft attention, depending on numerical precision, when no chain-of-thought is allowed. Once a decoder can emit intermediate tokens, the same architectures climb through deterministic quadratic time, polynomial time, and, with unbounded chain-of-thought, can simulate arbitrary Turing machines. If this map is right, it tells a practitioner which tasks are structurally impossible for a given architecture, no matter how much data or training is used.","feed_headline":"Chain-of-thought lifts transformers to PTIME and Turing power","feed_subtitle":"Attention type and precision fix the circuit class; CoT length acts like computation time.","key_machinery":"The mechanism that carries the argument is the simulation of a constant-depth transformer by a constant-depth uniform circuit family. A transformer with a constant number of layers composes attention and feed-forward blocks whose computations on a fixed input length can be replaced by Boolean circuit gadgets; because the number of layers is constant, stitching the gadgets layer by layer yields a circuit of constant depth. Attention type and precision decide which gate basis the simulation needs: unique hard attention can be rendered with AND, OR, and NOT gates ($\\mathsf{AC}^0$), while average-hard or softmax attention with enough precision must compute averages, which requires majority gates ($\\mathsf{TC}^0$). For the chain-of-thought results, the decoder's generated tokens encode the state history of a Turing machine or finite-state machine, and the autoregressive loop plays the role of time, so the chain-of-thought length $f(n)$ acts as a time bound.","core_discovery":"The paper assembles existing results into a single claim: transformer expressivity is not one point on a complexity scale but a family of points indexed by three architectural choices—attention type (unique hard, average hard, softmax), numerical precision (constant vs. $O(\\log n)$), and chain-of-thought budget. Without chain-of-thought, unique-hard-attention encoders with arbitrary rational precision recognize only $\\mathsf{AC}^0$ languages; softmax and average-hard encoders with $O(1)$ precision recognize only $\\mathsf{AC}^0$; and softmax and average-hard encoders with $O(\\log n)$ precision recognize only $\\mathsf{TC}^0$, with the bounds nearly tight when embedding dimension is allowed to grow polynomially. With chain-of-thought, softmax decoders with $O(\\log n)$ chain-of-thought stay in $\\mathsf{AC}^0$ or $\\mathsf{TC}^0$ depending on precision, average-hard decoders with $O(n)$ chain-of-thought reach $\\mathsf{DTIME}[n^2]$, with polynomial chain-of-thought they recognize exactly $\\mathsf{PTIME}$, and with unbounded chain-of-thought they can simulate arbitrary Turing machines. The intended upshot is that these containments, taken together, justify circuit complexity—rather than the Chomsky hierarchy—as the right yardstick for transformer power.","pith_inferences":["The map implies a design rule the authors do not state: if a target task is outside $\\mathsf{AC}^0$, a fixed-precision encoder cannot learn it, and the only architectural levers that move the boundary are chain-of-thought or a jump to $O(\\log n)$ precision.","The tightness discussion suggests a testable hypothesis: with constant embedding dimension rather than polynomial, log-precision transformers may fail to capture all of $\\mathsf{TC}^0$, which would make deployed fixed-width models strictly weaker than the clean asymptotics suggest.","A natural neighboring program is to measure a trained model's effective precision and chain-of-thought budget empirically, then read off the complexity class the model actually occupies on the scale this survey lays out."],"forward_implications":["Any task that cannot be decided by a constant-depth $\\mathsf{TC}^0$ circuit is beyond every constant-depth, $O(\\log n)$-precision softmax or average-hard attention encoder when no chain-of-thought is used, regardless of training.","Chain-of-thought is a resource that changes the complexity class: raising the budget from $O(\\log n)$ to $O(n)$ to polynomial moves a decoder from $\\mathsf{AC}^0$/ $\\mathsf{TC}^0$ to $\\mathsf{DTIME}[n^2]$ and then to exactly $\\mathsf{PTIME}$.","With unbounded chain-of-thought, hard-attention decoders can simulate arbitrary Turing machines, so there is no formal upper bound on what such decoders can compute given enough intermediate tokens.","Precision is as decisive as attention: changing encoder precision from $O(1)$ bits to $O(\\log n)$ bits is the difference between $\\mathsf{AC}^0$ and $\\mathsf{TC}^0$."],"supporting_citations":[{"why":"Supplies the layer-by-layer Boolean circuit simulation showing unique-hard-attention encoders with arbitrary rational precision lie in AC0.","marker":"[10]"},{"why":"Gives the O(1)-precision softmax/average-hard encoder AC0 containment, the chain-of-thought AC0/TC0 containments, and the poly(n)-embedding-dimension tightness results.","marker":"[14]"},{"why":"Places fixed-precision softmax encoders in TC0 via an extension of first-order logic.","marker":"[7]"},{"why":"Shows saturated transformers compute constant-depth threshold circuits, supporting the softmax/average-hard to TC0 route.","marker":"[21]"},{"why":"Places log-precision transformers in uniform TC0, directly supporting the third bullet of Theorem 4.1.","marker":"[6]"},{"why":"Proves the parallelism tradeoff that log-precision transformers lie in TC0.","marker":"[18]"},{"why":"Shows average-hard attention transformers are constant-depth uniform threshold circuits.","marker":"[24]"},{"why":"Provides the chain-of-thought upper bounds for average-hard decoders reaching DTIME[n^2] and exactly PTIME, including the layernorm-hash technique.","marker":"[19]"},{"why":"Shows softmax transformers with unbounded chain-of-thought and log precision simulate arbitrary Turing machines.","marker":"[13]"},{"why":"Shows the UHAT containment is not tight and characterizes the logical languages such encoders do recognize.","marker":"[2]"}],"fun_headline_variants":["Transformers' power: circuits without CoT, Turing with it","Circuit complexity explains what transformers can't do","Chain-of-thought makes transformers Turing-complete","Three choices set transformer expressivity bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The map is only as solid as the assumption that every cited upper-bound theorem was proved under the same architectural conventions—how precision is counted, whether embedding dimension may grow polynomially, what uniformity means, and whether the chain-of-thought length $f(n)$ is fixed in advance—that the survey uses in Theorems 4.1 and 4.2; the survey itself says to check the original papers for those details.","fun_headline_variants_meta":{"raw":{"variants":["Transformers' power: circuits without CoT, Turing with it","Circuit complexity explains what transformers can't do","Chain-of-thought makes transformers Turing-complete","Three choices set transformer expressivity bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000208,"raw_usage":{"total_tokens":1410,"prompt_tokens":956,"completion_tokens":454,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":572,"completion_tokens_details":{"reasoning_tokens":394}},"tokens_in":572,"tokens_out":454,"duration_ms":4715,"temperature":1.0,"reasoning_tokens":394,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:53:29.405253+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A single counterexample under the survey's stated assumptions would refute the calibration: exhibit a language computed by a constant-depth, $O(\\log n)$-precision softmax-attention encoder, as defined in Section 2, that is provably not in $\\mathsf{TC}^0$. Alternatively, re-derive the third bullet of Theorem 4.1 from its cited sources and check whether any source tacitly requires polynomial embedding dimension; if the inclusion fails without that condition, the theorem as printed is false.","supporting_citations":[{"cited_title":"Chainofthoughtempowerstransformerstosolveinherentlyserialprob- lems","cited_arxiv_id":null,"evidence_quote":"Gives the O(1)-precision softmax/average-hard encoder AC0 containment, the chain-of-thought AC0/TC0 containments, and the poly(n)-embedding-dimension tightness results."},{"cited_title":"Chiang, P","cited_arxiv_id":null,"evidence_quote":"Places fixed-precision softmax encoders in TC0 via an extension of first-order logic."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Places log-precision transformers in uniform TC0, directly supporting the third bullet of Theorem 4.1."},{"cited_title":"Merrill and A","cited_arxiv_id":null,"evidence_quote":"Provides the chain-of-thought upper bounds for average-hard decoders reaching DTIME[n^2] and exactly PTIME, including the layernorm-hash technique."},{"cited_title":"Jiang, M","cited_arxiv_id":null,"evidence_quote":"Shows softmax transformers with unbounded chain-of-thought and log precision simulate arbitrary Turing machines."},{"cited_title":"Barceló, A","cited_arxiv_id":null,"evidence_quote":"Shows the UHAT containment is not tight and characterizes the logical languages such encoders do recognize."}],"review_version":1}