acceptodds
Under review as a conference paper at ICLR 2027

Token Boundaries and the Width of Shallow Transformers

Abstract

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.

Primary area:
learning theory
Keywords:
Tokenization, Transformer expressivity, communication complexity, computational lower bounds, depth–width trade-offs, finite-precision computation. Tokenization, finite-precision computation.

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_Mg1MOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper uses communication complexity to study how token-boundary placement affects shallow Transformer width. It derives boundary-load formulas for fixed-chunk tokenizers, constructs a matched tokenizer family τS\tau_S, and reports one-layer/two-layer experiments on complementary intersection tasks. Empirically, one-layer models fail under misaligned tokenizers at n≥64n\ge64, while depth-two repair does not hold at n=64n=64.

Critical strengths
  1. Well-controlled paired experiments. Sharing data, initialization, parameters, and optimization isolates boundary placement as the intervention.
  2. Novel theoretical lens. Communication complexity gives a fresh formal angle on tokenizer-induced expressivity costs.
Critical weaknesses
  1. Theory–experiment mismatch. At n=64n=64, width 128 is far above the one-layer lower-bound scale, so chance accuracy is better read as a trainability failure than width evidence. The exact two-layer construction gives an O(log⁡n)O(\log n)-width solution, yet learned depth-two models stay at chance at n=64n=64. The authors acknowledge this but give no mechanism. This undercuts the learned-model narrative.

  2. The metric is task-dependent. Moving a boundary transfers load between complementary tasks, so boundary load cannot rank tokenizers globally like vocabulary size or compression. The authors acknowledge this, but the broad framing still suggests a general account of token boundaries and width. Acknowledgment does not resolve the practical-value gap.

  3. Scope is too narrow for the claims. Exact results require full product domains, fixed exact-substring chunks, deterministic fixed-length tokenization, and exact finite precision. Proposition 1 weakens with large state counts; the BPE corollary covers only two synthetic endpoints. The main lower-bound engine is prior work, so the contribution is a specialization rather than a new principle.

  4. Presentation obscures the contribution. The main text is dense, lacks a glossary and intuitive explanation of τS\tau_S, and depends heavily on a long appendix; the 8.5-page body does not stand alone. Related Work relies on repeated “We do not claim…” positioning, making the positive novelty hard to identify. This is a clarity and positioning problem, not merely a length issue.

Questions for authors
  1. At n=64n=64, width 128 is above the one-layer lower-bound scale. What evidence supports a width interpretation rather than a trainability failure?
  2. Depth-two stays at chance at n=64n=64 despite the exact O(log⁡n)O(\log n)-width construction. Please report diagnostics—training accuracy, loss, gradients, learning-rate sensitivity, Track B results—to distinguish optimization failure from finite-width or implementation mismatch.
  3. Given the task-dependent metric and narrow theoretical scope, what practical conclusion should the NLP community draw? Can you provide a boundary-load profile for a deployed tokenizer beyond the digit-grouping correspondence?
Reviewer_pFRNOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies how token boundary placement affects the width required by shallow Transformers, even when vocabulary size, sequence length, and token-length distributions are fixed. The authors introduce a communication-complexity framework based on boundary load and construct synthetic tasks where changing token boundaries leads to a separation between constant width and Ω(n/log⁡n)\Omega(n/\log n) width for one-layer Transformers. They also provide two-layer upper bounds and experiments supporting the importance of token alignment, although the empirical depth advantage is not consistently observed.

Critical strengths

The paper establishes a formal separation showing that token boundary placement alone can significantly affect Transformer expressivity.

The authors carefully match tokenizer and model resources, isolating the effect of boundary placement. The task-reversal and control experiments further support the central claim.

Critical weaknesses

The paper suffers from serious presentation issues. The writing is unnecessarily dense, with excessive technical terminology, repeated qualifications, and awkward phrasing (e.g., “adaptive ownership is not cosmetic”). Many paragraphs read more like lists of technical claims than explanations, with little intuition connecting the results. The frequent references to appendices further interrupt the flow, making it difficult to follow the main arguments. There are also noticeable formatting problems, particularly on page 3, where the Related Work section is poorly laid out.

More importantly, the paper spends considerable effort formalizing a relatively intuitive observation, without sufficiently explaining what additional insight the technical framework provides. Overall, the presentation makes it unnecessarily difficult to assess the significance of the contribution.

Questions for authors

Can the authors give a concrete example of how the boundary-load framework could be useful for practical tokenisers such as BPE, beyond the synthetic structures considered?

Reviewer_AjAROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The language modeling community is used to thinking about tokenizers through a narrow lens: scalar budgets such as vocabulary size, sequence length, and compression, the assumption being that all fixing these aspects of a tokenizer, all else becomes equal. The authors show this to be false: all of these metrics can be matched exactly yet still require very different transformers to solve a given task. More specifically, they study the amount of communication needed to materialize token values across a partition of the raw input coordinates. They show that for complementary intersection tasks, there is no universally superior tokenizer. Consequently, they establish two bounds: with misaligned token boundaries, a one-layer transformer must have width Ω(n/log⁡n)\Omega(n/\log n), whereas with aligned boundaries, a one-layer transformer can solve the same task with constant width.

Critical strengths
  • The paper demonstrates that two tokenizers with identical scalar budgets can require substantially different width requirements for shallow transformers, with the gap being n/log⁡nn/\log n between the two end points.

  • The paper develops a potentially reusable theoretical framework for transferring communication complexity lower bounds through tokenization, with an exact characterization of tokenization cost for fixed-chunk tokenizers.

  • I found the complementary intersection tasks to be very useful pedagogical devices to get the authors main points across.

Critical weaknesses
  • I generally would've appreciated slightly more hand holding throughout the exposition and "padding" surrounding the theorems as the paper did read quite terse at various points.

  • The authors show that carefully grouping task-relevant variables into the same tokens can dramatically reduce the required width of a shallow transformer, but it's not clear what, if anything, we learn beyond this particular, toyish construction. Consequently, it's not very clear to me how significant this finding is.

  • Relatedly, it is not clear how interesting, or relevant this separation is for realistic architectures and tokenizers. First, the authors show that two layers suffice with (Olog⁡n)(O\log n) width under the misaligned tokenizer, which weakens how interesting the separation could be for realistic architectures that tend to be quite deep. And second, it is my understanding that proposition 1 suggests the framework can extend to more realistic tokenizers, but falls short of actually establishing a comparable separation for content-dependent tokenizers.

Questions for authors

Please address the concerns in the critical weaknesses section

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.