Characterizing the Expressivity of Local Attention in Transformers

• p. 2 Section 2.1, alphabet definition

  An alphabet is a finite, non-empty set of tokens.

• p. 4 Theorem 2.9

  For any k ≥ 1

• p. 18 Section C.4, proof of Theorem 2.9

  However, Lk is not a left-deterministic polynomial

Only the authors can say what is right here.

Judge's note: Checked p.2 (alphabet definition), p.4 (Theorem 2.9) and p.18 (§C.4 proof, Lemma C.1); semantics evaluated at N+1 per §A.3 (Eq. 16). I reworked the unary case myself. For a P-only formula, its truth at in-string positions t ≤ N depends only on t, and at N+1 P ψ means 'ψ holds at some t ≤ N'. That is monotone in N and so eventually constant. Boolean combinations keep this, so only finite or cofinite unary languages arise. A Y≤k formula of depth d looks back at most kd positions, so for N > kd its value at N+1 is constant. Conversely P^jπa and (Y≤k)^jπa each hold at N+1 iff N ≥ j, so both fragments give every finite or cofinite unary language. Hence they coincide, and the theorem fails as printed when |Σ|=1. Lemma C.1 explicitly assumes distinct tokens a, b, but Theorem 2.9 does not. Adding |Σ| ≥ 2 would repair it. No statement in the text excludes unary alphabets (searched).

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 6 Theorem 4.2, proof sketch

  bounded counting, which is expressible in LTL [Y≤k] using bounded nesting of Y≤k

• p. 4 Equation (3a)

  Y≤kψ

Only the authors can say what is right here.

Judge's note: Checked p.4, Eq. (3a): Y≤kψ is a disjunction over the last k positions. Checked p.5, Eq. (11): the k-local mask at N+1 covers positions N+1−k..N. Checked p.6: Theorem 4.2 and its proof sketch. No fuller proof is in the appendix (searched), and §3.4 gives no rounding rule that would merge values such as 1/4 and 3/4. I reworked the counterexample with k=4, u_r=(aaab)^(r+1), v_r=(abbb)^(r+1). By induction on depth d, at in-string positions n > 4d a depth-d formula depends only on the current token. The 4-window lies inside the string at positions > 4(d−1), and every 4-window in either string contains both a and b. At N+1=4r+5 the window N−3..N also lies above 4(r−1) and atoms are false, so no depth-≤r formula separates u_r from v_r. A single uniform 4-local head (Q=K=0) with values 1 for a and 0 for b outputs 3/4 versus 1/4 at EOS. After the residual and LN these give distinct vectors, and the classifier c is an arbitrary function. So one transformer separates u_r from v_r for every r, and the language it recognizes is not LTL[Y≤4]-definable. This rests on F containing 1/4 and 3/4, which the theorem does not exclude. Only the authors can say which restriction, if any, is intended.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 2 Section 2.2, suffix convention

  If m > |w|, we set Pm(w) = Sm(w) = w.

• p. 16 Section C.1, implication (2⇒1), Equation (33)

  where u ∈ Σm.

Only the authors can say what is right here.

Judge's note: Checked p.2: m-definite means a Boolean combination of {w | Sm(w)=u}, with Sm(w)=w when m>|w|, and u is unrestricted. Checked p.16, Eq. (33): the proof restricts to u ∈ Σ^m, and claim (36) is proved only for n ≥ |u|+1. I reworked it. With u ∈ Σ^m, every string shorter than m lies in none of the basic languages, so ε, a and b cannot be separated when m ≥ 2, and for m=1, Σ*a contains aa. So {a}, which is 2-definite under §2.2, is not reachable by the printed reduction. The theorem still holds, because short-u languages are exact-word tests definable in LTL[Y] (e.g. Yπa ∧ ¬YY(πa∨πb)). So this is a faulty proof step and the stated result stands. Both reviewer notes describe the same gap.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 3 §2.4.1, last paragraph

  cause they are not right-deterministic

• p. 3 Proof of Proposition 2.4

  show that LTL [P] defines exactly the class of left-deterministic polynomials, and Σ∗a is not a left-deterministic polynomial

• p. 18 §C.4, proof of Theorem 2.9

  Lk is not a left-deterministic polynomial, and therefore is not definable in LTL [P]

• p. 14 §B.1 Monomials

  right-deterministic if for every k ∈{1,... , n}, ak /∈Σk

Judge's note: Checked p.3: Prop. 2.4 proof says LTL[P] defines exactly the left-deterministic polynomials and Σ∗a is not left-deterministic. §2.4.1 (same page) gives 'not right-deterministic' as the reason. §B.1 (p.14) defines left-deterministic as a_k ∉ Σ_{k−1} and right-deterministic as a_k ∉ Σ_k. Σ∗a = Σ0∗ a1 Σ1∗ with Σ0 = Σ, Σ1 = ∅ satisfies a ∉ Σ1, so it is right-deterministic, and it fails a ∉ Σ0, so it is not left-deterministic. §C.4 (p.18) also argues from left-determinism. §5.1 (p.7) calls {a,b,d}∗a{c,d}∗ a right-deterministic polynomial outside LTL[P,Y]. The stated reason is false as printed; the conclusion is unaffected.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 8 §5.3.1, paragraph 'Beyond LTL[P, Y]'

  hybrid attention yields the strongest partial generalization on these tasks

• p. 22 Table 4 (NoPE, longest perfect length), row (a(ab)*b)*

  136.5 ± 57.0

• p. 22 Table 4, row (a(ab)*b)*, max, Global column

  320.0

• p. 21 Table 1 (NoPE accuracy), row (a(ab)*b)*

  98.4 ± 4.1

Only the authors can say what is right here.

Judge's note: Checked Table 4 and Table 1 on the page images, and the Fig. 3 NoPE panel. Dyck, longest perfect length: global mean 136.5 and max 320.0 exceed every hybrid setting; in Fig. 3 the G cell of the top row is the brightest. Dyck, accuracy (Table 1): local k=4 has the highest mean (98.4 ± 4.1, against hybrid 89.7/87.4/83.5) and global the highest max (99.8, against hybrid 99.5). The claim holds for {a,b,d}*a{c,d}* (hybrid k=2: 203.1 mean, 455.0 max, 99.9% accuracy). No metric is named and no explanatory statement was found, so the sentence overstates the data for one of the two tasks.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 18 §C.6, proof of Lemma C.1, definition of s-close

  positions n ∈{1,... , N + 1} and n′ ∈{1,... , N}

• p. 19 §C.6, s-close condition 1 and base case

  If n = n′, the claim is immediate

• p. 18 Lemma C.1, Equation (50)

  w′

• p. 19 Definition of s-close, cases 1 and 3

  n > ks and n′ = n − k.

Only the authors can say what is right here.

Judge's note: Checked p.18 (Eq. 50, N = kr+1, ranges n ∈ {1..N+1}, n′ ∈ {1..N}) and p.19 (s-close conditions, base case, Cases 1–2). First, the pair (N,N) satisfies condition 1. Take k=2, r=1: w=aba, w′=ab, N=3. Then w,3 ⊨ πa, but position 3 is past the end of w′, so w′,3 ⊭ πa, which contradicts (52) at s=0. Second, take k=2, r=2, s=1, w=ababa, w′=abab, n=3, n′=1. Since 3 > 2·1, case 3 applies. Then w,3 ⊨ Y≤2πa because position 1 is a, while w′,1 ⊭ Y≤2πa because there is no earlier position. In Case 2 item 3, t′=t−k can be ≤ 0. So the proof's steps are faulty as printed. Restricting case 1 to n=n′<N and case 3 to n > k(s+1) leaves the needed pairs available: the final pair (N+1,N) uses case 2, and (N, N−k) needs N=kr+1 > ks. So Lemma C.1 still stands. This is a faulty proof step, and all three reviewer notes describe it.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 19 Appendix C.6, Lemma C.1, s-close item 3 and base case

  If n′ = n − k, then the token at position n of w is the same as the token at position n′ of w′

Only the authors can say what is right here.

Judge's note: Checked p.19. N+1 = kr+2 > ks for all s ≤ r, and N+1−k ∈ {1,…,N}, so (N+1, N+1−k) is s-close at every level. Position k(r−1)+2 of w′ = (ab^{k−1})^r lies inside w′ for k ≥ 2 and is ≢ 1 mod k, so it holds b. Example: k=2, r=1, w = aba, w′ = ab, pair (4,2): w,4 ⊭ πb but w′,2 ⊨ πb, so (52) fails. The induction never generates this pair from (N+1, N), because Case 1/2 item 2 handles n = N+1 separately. Adding n ≤ N to condition 3 repairs the step, and the result stands.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 19 Appendix C.6, Lemma C.1, s-close item 3 and Case 2 (Y≤k), Eq. (54)–(55)

  3. If n > ks and n′ = n − k, let t′ = t − k.

• p. 19 Appendix C.6, Lemma C.1, Case 2

  and (t, t′) is (s − 1)-close

Only the authors can say what is right here.

Judge's note: Checked p.19. With k=2, r=1, w = aba, w′ = ab, N = 3, the pair (3,1) is 1-close by condition 3 (3 > 2·1, 1 = 3−2). φ = Y≤2 πa has depth 1. At w,3 the window t ∈ {1,2} includes w_1 = a, so φ is true. At w′,1 the window t ∈ {−1,0} has no tokens, so φ is false, and (52) fails. In the proof, t = 1 gives t′ = −1 ∉ {1,…,N}, so (t, t′) is not s-close. The pairs actually reached from (N+1, N) satisfy a stronger bound, so strengthening condition 3 (e.g. n > k(s+1), n ≤ N) appears to repair the proof. The step is faulty, but the stated result is not shown false.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send