Token Boundaries and the Width of Shallow Transformers

Tokenizers are usually compared through scalar budgets such as vocabulary size, sequence length, and compression. We show that all of these can be matched exactly while the placement of token boundaries still determines how wide a shallow Transformer must be. The central quantity is the communication needed to materialize token values across a partition of the raw input coordinates. For input-independent exact-substring chunks on a full binary product domain, this cost equals a combinatorial boundary load, and composing it with a one-layer simulation argument carries raw communication lower bounds through the tokenizer. Tokenizers with the same chunk-length multiset have the same mean load over raw cuts, so matched tokenizers cannot dominate one another uniformly; they redistribute cost across cuts. We make this concrete with a family τ_S of tokenizers for strings a₁b₁c₁⋯aₙbₙcₙ that share active vocabulary, sequence length, and per-input token-length histogram. Each moved boundary transfers one unit between lower-bound certificates n−|S| and |S| for two complementary intersection tasks. At the endpoints, a finite-precision softmax Transformer computes the aligned task in one layer of constant width, while under the misaligned tokenizer every one-layer model, including models with residual connections and normalization, needs width Ω(n/log n) at fixed head count and O(log n)-bit precision. Swapping the task reverses the preferred tokenizer, two layers restore O(log n) width, and a token-local control is easy under both. In paired training runs, one-layer models reach near-perfect in-distribution accuracy under the aligned tokenizer and stay at chance under the misaligned one for n ≥ 64. The gap reverses with the task and is absent for the control; a second layer closes it at n = 16 but not at n = 64.