The expressive power of transformers with chain of thought

The left side of Equation (1) implies that transformer decoders with Θ(n) steps can simulate real-time models of computation like automata or counter machines.

“The left side of Equation ( 1) implies that transformer decoders with Θ(n) steps can simulate real-time models of computation like automata or counter machines (Merrill, 2020).”

• cites Merrill, 2020 sourceCould not verify

  The Definitions (p. 2) and General Counter Machines (p. 3) describe real-time counter automata, but they do not address transformer decoders or whether Θ(n) decoder steps can simulate those machines. Searches for transformer-decoder simulation returned only passages about counter machines and recurrent networks. (LLM, conf=0.77)

  Experimental — accuracy not yet measured

Standard transformers, even with ideal parameters, cannot perfectly solve many sequential reasoning problems at scale, such as simulating finite-state machines, deciding whether nodes in a graph are connected, or solving matrix equalities.

“They have shown that standard transformers, even with ideal parameters, cannot perfectly solve many sequential reasoning problems at scale, such as simulating finite-state machines, deciding whether nodes in a graph are connected, or solving matrix equalities.”

• cites Merrill & Sabharwal, 2023bNot matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites Merrill & Sabharwal, 2023aNot matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites Merrill et al., 2022 sourcePartly supported

  Section 2 (Roadmap) says that saturated transformers with floating-point values can recognize only languages in TC0, supporting a qualified limit on their computational power. But §4 (Circuit Complexity) says it is unknown whether TC0 contains all regular languages, and the paper does not establish that transformers cannot solve the listed finite-state, graph-connectivity, or matrix-equality tasks. The claim turns a model-specific upper bound into categorical impossibility claims about standard transformers. (LLM, conf=0.88)

  Experimental — accuracy not yet measured

Reasoning problems inspired by theoretical limits cannot be solved by cutting-edge transformer language models such as ChatGPT and GPT-4.

“Empirically, reasoning problems inspired by these results cannot be solved by cutting-edge transformer language models such as ChatGPT and GPT-4 (Zhang et al., 2023)”

• cites Zhang et al., 2023 sourcePartly supported

  The Datasets section links the questions to theoretical limits on what transformers can solve in a single generation step, and the Question-answering accuracy section reports low accuracy for ChatGPT and GPT-4 under direct prompting. But “cannot be solved” overstates the empirical finding: both models answered some questions correctly, and §4.1 reports substantially better performance with step-by-step prompting. (LLM, conf=0.90)

  Experimental — accuracy not yet measured

The reasoning performance of GPT-4 negatively correlates with the depth of the problem's computation graph.

“the reasoning performance of GPT-4 negatively correlates with the depth of the problem's computation graph (Dziri et al., 2023).”

• cites Dziri et al., 2023 sourceSupported

Transformers with O(n) decoding steps can solve any problem a Turing machine can solve in O(n) time.

“Thus, simulating an automaton (cf.Theorem 1) is not the only new capability unlocked with O(n) decoding steps: rather, such transformers can solve any problem a Turing machine can solve in O(n) time, such as simulating real-time counter machines (Weiss et al., 2018).”

• cites Weiss et al., 2018 sourceSupported

The layer-norm hash can be implemented with simplified RMS norm.

“As the layer-norm hash is constructed to have mean 0, it does not require a fully general layer-norm implementation and can, in fact, be implemented with simplified RMS norm (Zhang & Sennrich, 2019).”

• cites Zhang & Sennrich, 2019 sourceSupported

Given the TIME(t(n)) lower bound, the tightest possible space upper bound without making fundamental complexity advances would be SPACE(t(n)/ log t(n)).

“Given our TIME(t(n)) lower bound (Theorem 2), the tightest possible space upper bound without making fundamental complexity advances would be SPACE(t(n)/ log t(n)) (Hopcroft et al., 1977).”

• cites Hopcroft et al., 1977 sourcePartly supported

  The Introduction (page unavailable) states that deterministic time t(n) is contained in space t(n)/log t(n), supporting the proposed space upper bound. The paper does not establish that this is the tightest possible upper bound or that improving it would require fundamental complexity advances. (LLM, conf=0.85)

  Experimental — accuracy not yet measured

The layer-norm hash is a simple module for effectively storing memory in decoder-only transformers.

“The key idea behind our more general construction is the layer-norm hash (Section 3.1): a simple module for effectively storing memory in decoder-only transformers.”

A linear number of decoding steps, assuming projected pre-norm, adds the ability to recognize all regular languages under standard complexity conjectures.

“while a linear number of decoding steps, assuming projected pre-norm (a slight generalization of standard pre-norm), adds a clear new ability (under standard complexity conjectures): recognizing all regular languages.”

• AssumptionThe authors state this as an assumption: TC0 = NC1, as written, is assumed for the claim that Theorem 1 gives additional reasoning power.

If t(n) = O(n^c) for some c, the upper bound is P = union over c of TIME(n^c).

“If t(n) = O(n c ) for some c, we get an upper bound of P = ∞ c=1 TIME(n c ).”

The left side of Equation (1) is proven by showing transformer decoders can simulate t Turing machine steps with t intermediate steps.

“The left side of Equation ( 1) is proven by showing transformer decoders can simulate t Turing machine steps with t intermediate steps.”

Polynomial steps with generalized pre-norm make transformer decoders recognize exactly the class of polynomial-time solvable problems.

“and polynomial steps with generalized pre-norm make them recognize exactly the class of polynomial-time solvable problems”

Linear steps keep transformer decoders within context-sensitive languages.

“Our results also imply that linear steps keep transformer decoders within context-sensitive languages”

Transformer decoders with O(log n) intermediate steps can only recognize languages in L = SPACE(log n).

“Transformer decoders with O(log n) intermediate steps can only recognize languages in L = SPACE(log n).”

Transformer decoders with O(n) intermediate steps can only recognize languages that are in both TIME(n^2) and SPACE(n).

“Transformer decoders with O(n) intermediate steps can only recognize languages that are in both TIME(n 2 ) and SPACE(n).”

CoT(t(n)) is contained in SPACE(t(n) + log n).

“Theorem 4. CoT(t(n)) ⊆ SPACE(t(n) + log n).”

For any x ∈ R and i ∈ R>0, φ(x/i, 1/i) = φ_x.

“Lemma 1 (Scale invariance).For any x ∈ R and i ∈ R >0 , φ(x/i, 1/i) = φ x .”

For any regular language L, there is a decoder-only projected pre-norm transformer with strict causal saturated attention, with or without positional encodings, that on input $x checks whether x is in L with |x| + 1 decoding steps.

“Theorem 1 (Regular language recognition).For any regular language L. there is a decoder-only projected pre-norm transformer with strict causal saturated attention (with or without positional encodings) that, on input $x, 7,foot_6 checks whether x ∈ L with |x| + 1 decoding steps.”

• AssumptionThe authors state this as an assumption: Saturated attention is assumed: per head, all attention scores are either 0 or 1/v for some v.
• AssumptionThe authors state this as an assumption: Strict causal masking is assumed: causally masked attention at position i can view tokens at all positions up to i - 1 but not the current token i.
• AssumptionThe authors state this as an assumption: Projected pre-norm is assumed: each sublayer may apply a linear projection before layer-norm.

The construction works with or without positional encodings.

“In contrast, our construction works with or without positional encodings.”

f(i, k) is computable by a single multihead self-attention layer.

“The latter property means it is computable by a single multihead self-attention layer.”

For any i ≥ 2, φ(i, 1) • φ(i - 1, 1) ≤ 1 - 1/(2i^4).

“Lemma 8.For any i ≥ 2, φ(i, 1) • φ(i -1, 1) ≤ 1 -1/(2i 4 ).”

For i ≥ 1, f(i) < 1/(2i^4).

“Lemma 10.For i ≥ 1, f (i) < 1/(2i 4 ) .”

Multi-pre-norm with k norms can be simulated by k + 1 projected pre-norm layers.

“Proposition 1 (Chiang, 2024).Multi-pre-norm with k norms can be simulated by k + 1 projected pre-norm layers.”

• cites Chiang, 2024Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

For any q, k ∈ R, φ_q • φ_k = 1 if and only if q = k.

“Lemma 2 (Equality check via layer-norm hash).For any q, k ∈ R, φ q • φ k = 1 if and only if q = k.”

CoT(t(n)) is contained in TIME(n^2 + t(n)^2).

“Theorem 3. CoT(t(n)) ⊆ TIME(n 2 + t(n) 2 ).”

For any x in R and i in R>0, φ(x/i, 1/i) = φ_x.

“Lemma 1 (Scale invariance).For any x ∈ R and i ∈ R >0 , φ(x/i, 1/i) = φ x .”

If there exists j < i such that h_i = h_j, then δ = δ_j for the greatest such j.

“Lemma 7. If there exists j < i such that h i = h j , then δ = δ j for the greatest such j.”

For i > n, 1 ≤ h_i ≤ n if and only if φ = φ_i.

“Lemma 3. Let i > n.Then, 1 ≤ h i ≤ n if and only if φ = φ i .”

For any k and i > k, f(i, k) = k! / ∏_{j=0}^k (i - j).

“Lemma 9.For any k and i > k, we have f (i, k) = k! k j=0 (i -j) .”

Let M be a Turing machine that on input length 1 + n runs for at most t(n) steps, at most polynomial. There is a decoder-only projected pre-norm transformer with strict causal saturated attention, with or without positional encodings, that on input $x takes t(n) decoding steps and then, with |M(x)| additional steps, outputs M(x).

“Theorem 2 (Turing machine simulation).Let M be a Turing machine that, on input length 1 + n, runs for at most t(n) steps (at most polynomial).There is a decoder-only projected pre-norm transformer with strict causal saturated attention (with or without positional encodings) that, on input $x, 8 takes t(n) decoding steps and then, with |M (x)| additional steps, outputs M (x).”

• AssumptionThe authors state this as an assumption: Saturated attention is assumed: per head, all attention scores are either 0 or 1/v for some v.
• AssumptionThe authors state this as an assumption: Strict causal masking is assumed: causally masked attention at position i can view tokens at all positions up to i - 1 but not the current token i.
• AssumptionThe authors state this as an assumption: Projected pre-norm is assumed: each sublayer may apply a linear projection before layer-norm.

For i > n, if 1 ≤ h_i ≤ n, then σ = σ_{h_i}.

“Lemma 4. Let i > n. Then, if 1 ≤ h i ≤ n, σ = σ hi .”

TIME(t(n)) is contained in CoT(t(n)).

“Corollary 2.1. TIME(t(n)) ⊆ CoT(t(n)).”

The proof shows by induction that at step i ≥ n, the transformer can output δ_{i-n}.

“We show by induction that at step i ≥ n, we can output δ i-n .”

For any q, k in R, φ_q • φ_k = 1 if and only if q = k.

“Lemma 2 (Equality check via layer-norm hash).For any q, k ∈ R, φ q • φ k = 1 if and only if q = k.”

A linear number of steps enables simulating an automaton.

“Specifically, a linear number of steps enables simulating an automaton.”

• AssumptionThe authors state this as an assumption: Saturated attention is assumed: per head, all attention scores are either 0 or 1/v for some v.
• AssumptionThe authors state this as an assumption: Strict causal masking is assumed: causally masked attention at position i can view tokens at all positions up to i - 1 but not the current token i.
• AssumptionThe authors state this as an assumption: Projected pre-norm is assumed: each sublayer may apply a linear projection before layer-norm.

The authors have not identified any concrete reasoning problem where a logarithmic number of steps would help.

“On the other hand, we have not identified any concrete reasoning problem where a logarithmic number of steps would help.”

The layer-norm hash can be used to simulate more complex models of computation such as Turing machines.

“However, this added power does not stop with finite-state machines: the layer-norm hash can be used to simulate more complex models of computation such as Turing machines, which we will turn to next.”

There exists j < i such that h_i = h_j if and only if φ = φ_i.

“Lemma 6.There exists j < i such that h i = h j if and only if φ = φ i .”

The automaton simulation can be extended to simulate t(n) Turing machine steps with t(n) decoding steps.

“We also show this can be extended to simulate t(n) Turing machine steps with t(n) decoding steps.”

• AssumptionThe authors state this as an assumption: Saturated attention is assumed: per head, all attention scores are either 0 or 1/v for some v.
• AssumptionThe authors state this as an assumption: Strict causal masking is assumed: causally masked attention at position i can view tokens at all positions up to i - 1 but not the current token i.
• AssumptionThe authors state this as an assumption: Projected pre-norm is assumed: each sublayer may apply a linear projection before layer-norm.

Let q ∈ Z and k_j ∈ Z for 1 ≤ j ≤ m. Let ≻ ∈ {<, >}. If, for all j, q ≻ k_j, then φ_q = (1/m) Σ_{j=1}^m φ_{k_j}.

“Lemma 5. Let q ∈ Z and k j ∈ Z for 1 ≤ j ≤ m.Let ≻∈ {<, >}.If, for all j, q ≻ k j , then φ q = 1 m m j=1 φ kj .”

SPACE(n) falls within the context-sensitive languages.

“Since SPACE(n) falls within the context-sensitive languages (Kuroda, 1964)”

• cites Kuroda, 1964Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Combined with the lower bound, transformer decoders with a polynomial number of steps recognize exactly the class P.

“Combined with our lower bound, this shows that transformer decoders with a polynomial number of steps recognize exactly the class P.”

Under standard assumptions in complexity theory, transformers with no decoding steps cannot simulate all automata.

“Under standard assumptions in complexity theory, transformers with no decoding steps cannot simulate all automata (Merrill & Sabharwal, 2023b;Merrill, 2023;Liu et al., 2023).”

• cites Merrill & Sabharwal, 2023bNot matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites Merrill, 2023Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites Liu et al., 2023Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Transformer decoders with a logarithmic number of decoding steps with respect to input length push the limits of standard transformers only slightly.

“we find that transformer decoders with a logarithmic number of decoding steps (w.r.t. the input length) push the limits of standard transformers only slightly”

A linear number of decoding steps makes transformers strictly more powerful.

“Thus, a linear number of decoding steps makes transformers strictly more powerful.”

Transformers with linear steps can recognize at most context-sensitive languages.

“transformers with linear steps can recognize at most context-sensitive languages.”

Alongside the lower bound, transformer decoders with Θ(n) steps fall somewhere between regular and context-sensitive languages in the Chomsky hierarchy.

“Alongside our lower bound, this shows transformer decoders with Θ(n) steps fall somewhere between regular and context-sensitive languages in the Chomsky hierarchy.”

The left side of Equation (1) implies transformers with a quadratic number of steps can express a linear-time algorithm for a random access Turing machine to solve directed graph connectivity.

“Similarly, the left side of Equation ( 1) implies transformers with a quadratic number of steps can express a linear-time algorithm (for a random access Turing machine) to solve directed graph connectivity (Wigderson, 1992)”

• cites Wigderson, 1992Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

The paper provides the first exact characterization of a type of transformers in terms of standard complexity classes.

“the first exact characterization of a type of transformers in terms of standard complexity classes.”

Transformers with O(n) steps cannot recognize all context-free languages unless context-free languages can be parsed in soft quadratic time.

“Further, transformers with O(n) steps cannot recognize all context-free languages unless context-free languages can be parsed in soft quadratic time.foot_5”

The amount of additional power is closely related to the number of decoding steps.

“Further, the amount of additional power is closely related to the number of decoding steps.”

The lower bounds do not directly imply transformers can learn to use intermediate steps effectively.

“one caveat is that our lower bounds do not directly imply transformers can learn to use intermediate steps effectively.”

Intermediate decoding steps extend the formal power of transformers well beyond previously known upper bounds, such as TC^0 circuits and FO(M) logic, on transformers without intermediate decoding.

“We have shown that intermediate decoding steps extend the formal power of transformers well beyond previously known upper bounds, such as TC 0 circuits and FO(M) logic, on transformers without intermediate decoding.”

The inner product of the layer-norm hash representations of two scalars q and k, even if computed at different positions i and j, allows checking equality of q and k.

“In other words, the inner product of these representations of two scalars q and k, even if computed at different positions i and j, respectively, allows us to check for the equality of q and k.”

The lower bound can only be tightened to TIME(t(n) log t(n)).

“Conversely, our lower bound can only be tightened to TIME(t(n) log t(n)).”

With O(n^2) steps, transformers can solve directed graph connectivity using standard graph traversal algorithms like depth-first search.

“With O(n 2 ) steps, we can solve directed graph connectivity using standard graph traversal algorithms like depth-first search.”

With only O(log n) decoding steps, intermediate decoding does not increase expressive power much beyond TC^0, because the upper bound simplifies to SPACE(t(n)) = L.

“On the other hand, with only O(log n) decoding steps, intermediate decoding does not increase expressive power much beyond TC 0 , because the upper bound simplifies to SPACE(t(n)) = L.”

The core challenge in simulating an automaton is recurrence, which cannot be done without decoding steps.

“The core challenge in simulating an automaton is recurrence, which cannot be done without decoding steps (Merrill & Sabharwal, 2023b).”

• cites Merrill & Sabharwal, 2023bNot matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

With a log number of decoding steps, such transformers can only recognize languages in L.

“With a log number of decoding steps, such transformers can only recognize languages in L, which is a complexity class relatively close to TC 0 .”

Under standard conjectures in complexity, transformers without intermediate decoding cannot recognize all regular languages.

“Specifically, under standard conjectures in complexity, transformers without intermediate decoding cannot recognize all regular languages.”

• cites Merrill & Sabharwal, 2023aNot matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Theorem 1 shows that a linear number of decoding steps gives additional reasoning power to log-precision transformers with projected pre-norm, assuming TC0 = NC1 as written.

“Theorem 1 shows that a linear number of decoding steps gives additional reasoning power to logprecision transformers with projected pre-norm (assuming TC 0 = NC 1 ).”

• AssumptionThe authors state this as an assumption: TC0 = NC1, as written, is assumed for the claim that Theorem 1 gives additional reasoning power.

With at least Ω(log n) steps, the upper bound can be simplified to SPACE(t(n)).

“With at least Ω(log n) steps, this upper bound can be simplified to SPACE(t(n)).”

The upper bounds directly reveal limitations on what transformers with intermediate generation can learn.

“Whereas our upper bounds directly reveal limitations on what transformers with intermediate generation can learn, one caveat is that our lower bounds do not directly imply transformers can learn to use intermediate steps effectively.”

The t(n) = Θ(n) case establishes the context-sensitive languages as an upper bound for transformers with linear steps.

“The t(n) = Θ(n) case establishes the context-sensitive languages as an upper bound for transformers with linear steps.”