Paper ID: 2501.02535

A completely uniform transformer for parity

Alexander Kozachinskiy, Tomasz Steifer

We construct a 3-layer constant-dimension transformer, recognizing the parity language, where neither parameter matrices nor the positional encoding depend on the input length. This improves upon a construction of Chiang and Cholak who use a positional encoding, depending on the input length (but their construction has 2 layers).

Submitted: Jan 5, 2025