Document: Cecka, "CuTe Layout Representation and Algebra", arXiv:2603.02298 (v2), §3.3.3 "Intuition and Divisibility", Violations of Divisibility Conditions and Apparent Violations. Reference implementation: NVlabs/CuTe 111253d17e2f0f8631f43999b43ac4afa5954b04 (pycute).
What the section says
It gives one example per divisibility condition and states that no layout exists for each:
(4,6,8):(2,3,5) ∘ 6:3 violates the stride divisibility condition (20): "There is no layout that can represent every third element of the layout (4, 6, 8) : (2, 3, 5)."(4,6,8):(2,3,5) ∘ 6:1 violates the shape divisibility condition (21): "There is no layout that can represent the first 6 elements."
It concludes that "CuTe layouts are not strictly closed under group composition", and Apparent Violations explains that some violations disappear once A is coalesced and truncated. A reader takes from this that a violation that survives coalescing and truncation means the composition has no layout.
Where that reading breaks
That holds for the shape divisibility condition, but not for the stride divisibility condition. Both of the following As are already coalesced, both compositions are rejected for stride divisibility (by the whitepaper's condition and by pycute), and yet each has a layout:
(4,6,8):(2,3,5) ∘ 4:5. Here S_0 = 4 and d = 5 divide neither way, so Eq. (20) fails, and pycute raises ValueError: Stride divisibility condition violated. But every fifth element of A below 4 · 5 is A(0), A(5), A(10), A(15) = 0, 5, 10, 15, which is 4:5.(6,6):(5,12) ∘ 12:9. Here S_0 = 6 and d = 9 divide neither way, and pycute raises the same error. But (2,6):(27,36) equals i ↦ A(9i) on every natural number, not only on B's domain, so it is the composition even on the extended domain.
from pycute import *
A, B = Layout((4, 6, 8), (2, 3, 5)), Layout(4, 5)
# composition(A, B) raises ValueError: Stride divisibility condition violated
R = Layout(4, 5)
assert all(R(i) == A(B(i)) for i in range(size(B)))
A, B = Layout((6, 6), (5, 12)), Layout(12, 9)
# composition(A, B) raises ValueError: Stride divisibility condition violated
R = Layout((2, 6), (27, 36))
assert all(R(i) == A(B(i)) for i in range(1000))
The whitepaper's own examples are correct: (4,6,8):(2,3,5) ∘ 6:3 and ∘ 6:1 really have no layout. The issue is only the implied general statement.
What we proved
We formalized the layout algebra in Lean 4 and proved the following for the base case A ∘ s:d with d ≠ 0:
- Shape divisibility is necessary. If the base case fails with the shape divisibility condition, no layout
R of size s satisfies R(i) = A(i·d) for i < s.
- Stride divisibility is not necessary. A base case can fail it and still have a layout. Both examples above are machine-checked theorems: the first is decided by computation, and the second holds for all natural numbers
i.
Suggestion
- In §3.3.3, say that a stride-divisibility violation means the base-case construction of Eq. (19) cannot produce the layout, not that none exists. Keep "there is no layout" for the shape-divisibility example, where it holds in general.
- In Apparent Violations, note that coalescing and truncating do not remove every stride violation that has a representation, and give an example such as
(4,6,8):(2,3,5) ∘ 4:5.
- Optionally, characterize exactly which stride-violating base cases still have a layout, so that an implementation can accept them instead of rejecting them. We have not found a simple characterization. In the first example the elements
A(5i) sit at coordinates (0,0), (1,1), (2,2), (3,3), spanning two modes of A, and they happen to form an arithmetic progression.
Related: #6 (pycute composition does not check Eq. 23).
Document: Cecka, "CuTe Layout Representation and Algebra", arXiv:2603.02298 (v2), §3.3.3 "Intuition and Divisibility", Violations of Divisibility Conditions and Apparent Violations. Reference implementation: NVlabs/CuTe
111253d17e2f0f8631f43999b43ac4afa5954b04(pycute).What the section says
It gives one example per divisibility condition and states that no layout exists for each:
(4,6,8):(2,3,5) ∘ 6:3violates the stride divisibility condition (20): "There is no layout that can represent every third element of the layout (4, 6, 8) : (2, 3, 5)."(4,6,8):(2,3,5) ∘ 6:1violates the shape divisibility condition (21): "There is no layout that can represent the first 6 elements."It concludes that "CuTe layouts are not strictly closed under group composition", and Apparent Violations explains that some violations disappear once
Ais coalesced and truncated. A reader takes from this that a violation that survives coalescing and truncation means the composition has no layout.Where that reading breaks
That holds for the shape divisibility condition, but not for the stride divisibility condition. Both of the following
As are already coalesced, both compositions are rejected for stride divisibility (by the whitepaper's condition and by pycute), and yet each has a layout:(4,6,8):(2,3,5) ∘ 4:5. HereS_0 = 4andd = 5divide neither way, so Eq. (20) fails, and pycute raisesValueError: Stride divisibility condition violated. But every fifth element ofAbelow4 · 5isA(0), A(5), A(10), A(15) = 0, 5, 10, 15, which is4:5.(6,6):(5,12) ∘ 12:9. HereS_0 = 6andd = 9divide neither way, and pycute raises the same error. But(2,6):(27,36)equalsi ↦ A(9i)on every natural number, not only onB's domain, so it is the composition even on the extended domain.The whitepaper's own examples are correct:
(4,6,8):(2,3,5) ∘ 6:3and∘ 6:1really have no layout. The issue is only the implied general statement.What we proved
We formalized the layout algebra in Lean 4 and proved the following for the base case
A ∘ s:dwithd ≠ 0:Rof sizessatisfiesR(i) = A(i·d)fori < s.i.Suggestion
(4,6,8):(2,3,5) ∘ 4:5.A(5i)sit at coordinates(0,0), (1,1), (2,2), (3,3), spanning two modes ofA, and they happen to form an arithmetic progression.Related: #6 (pycute composition does not check Eq. 23).