The Expressivity Limits of Transformers

Summary

The paper studies "how many different token sequences a transformer can generate" as a packing-number problem on the finite-precision embedding space. The conceptual move is to identify each accessible sequence with a cell in a finite $\varepsilon$-partition of a bounded embedding region and to count: the cardinality of that partition upper-bounds the number of distinguishable inputs, and therefore of accessible outputs. From this the authors derive (i) a bound on accessible sequences exponential in the prompt length $m$, giving a linear-in-$m$ threshold on maximal accessible sequence length; (ii) an $m$-independent finiteness result via a mean-field / Wasserstein extension; and (iii) an explicit predicted slope constant depending only on the embedding dimension $d$, radius $r$, precision $\varepsilon$, and vocabulary $|V|$, refined by anisotropy of the support (Ball → Cone → Ellipsoid) and non-uniform decoder cell volumes. Experiments on seven pretrained models across four families (Pythia, Qwen-2.5, Llama-3.2, Gemma-3) test the qualitative prediction (a sharp sigmoid drop past a critical length) and place the tightest theoretical slope within a factor of $\approx 5{-}11$ of empirical estimates.

The reframing is elegant and links prior empirical observations (cramming, length generalization, copying failures) to a single small set of geometric constants. The main conceptual limitation sits between theory and empirics: the accessibility bound applies to arbitrary soft prompts, whereas the empirical slope comes from a cramming procedure that identifies "inaccessible" with "not found by a 3000-step Adam optimizer" and estimates the support from random-token embeddings rather than from optimized soft prompts. Several internal inconsistencies (Corollary 4.10's factor 4 vs Theorem 4.9's factor 2; a shared $\varepsilon$ symbol for two distinct precisions; a Table 2 radius $\sim 100\times$ larger than the Figure 5 curve for Qwen-2.5-1.5B; competing definitions of the fp16 machine epsilon) and headline overstatements ("tight up to a factor less than 10" vs Table 1 rows above 20; "closely matches across architectures" vs sigmoid $R^2 = 0.46$ on Qwen-2.5-1.5B) blunt the quantitative story. Independent inspection of the released code found a faithful implementation of the pipeline but was unable to execute it end-to-end in this environment; a partial re-run of the Table 2 support constants matched the paper's magnitudes but was systematically low (7.8%–47%), consistent with the manuscript's 10K-vs-100K sample-count inconsistency between Section 5.2 and Appendix G.4.

Strengths

• Conceptual contribution. Framing "how many outputs can a transformer generate" as a packing-number problem on a finite-precision, bounded embedding space is clean, memorable, and connects prior observations (cramming, copying-length generalization) to a single small set of geometric constants.
• Progressive refinement of the bound. Moving from Ball to Cone to Ellipsoid support, and then to the non-uniform decoder-cell distribution, is a well-motivated sequence of relaxations that visibly tightens the reported slope constants for every model.
• Prompt-length-independent finiteness. The mean-field extension (Section 4.2 / Theorem 4.9) generalizes the fixed-$m$ result to arbitrary prompt length via a Wasserstein packing argument, with a strong assumption (Assumption 4.8) that Appendix E replaces by a much weaker elementary-operation assumption.
• Broad model sweep. Seven pretrained models across four families (Pythia, Qwen-2.5, Llama-3.2, Gemma-3) are analyzed, and the qualitative shape (sigmoid drop past a critical $n$; near-linear $n_{50}(m)$) reproduces across architectures.
• Careful decoder-side analysis. The empirical study of cell volumes in Section 5.3 and Table 3 (largest-volume cells align with whitespace and punctuation) is a nice sanity check that grounds the abstract cell partition in observable model behavior.
• Available code. A public repository accompanies the paper and, on inspection, provides a faithful implementation of the pipeline described in the manuscript, including the $D^n$ Monte Carlo and the Dirac-mass sanity check for Remark 5.1.

Weaknesses

• Cramming is not accessibility. The empirical benchmark treats a target as inaccessible whenever a fixed Adam schedule (3000 steps, lr 0.01, weight decay 0.01) fails to find a memory vector; this conflates optimization difficulty with fundamental accessibility. Because Table 1's ratio uses this optimization-derived slope as the denominator, systematic optimizer pessimism inflates the tightness numbers.
• Support estimated on the wrong distribution. Section 5.2 estimates $r$, per-coordinate ranges, and the cone angle from embeddings of random-token prompts, but the accessibility bound concerns arbitrary soft prompts. Kuratov et al.'s optimized memories sit in regions unlike natural-text embeddings; if the estimated support does not enclose the soft-prompt-reachable region, the "refined" slope is no longer a valid upper bound on accessibility.
• "Tight up to factor 10" overclaim. Table 1 contains many entries above 10 (Qwen: 14.1, 20.4, 15.30, 18.81; Llama: 14.3, 13.98; Gemma: 11.52) and the abstract's "factor less than 10" only holds when one always picks the tightest enclosure per model and discards the variable-$\varepsilon$ row. Similarly, Section 5.1's "factor is between 5 and 10" holds for Pythia in row 1 but is falsified by the Qwen and Llama entries in that row.
• Sharp-threshold story is not architecture-uniform. The copying-length experiment (Figure 4) reports sigmoid $R^2 = 0.46$ for Qwen-2.5-1.5B and $R^2 = 0.70$ for Llama-3.2-1B, so the "sharp / abrupt transition" narrative and the "closely matches empirical performance" abstract claim are undermined by two of the seven models. The paper does not discuss why.
• Corollary 4.10 vs Theorem 4.9 constant. Theorem 4.9 uses $(1 + 2r/\varepsilon)$ in the outer exponent; Corollary 4.10 uses $(1 + 4r/\varepsilon)$ in both the threshold and the rate. The parallel Corollary 4.6 propagates the "2" cleanly, so the "4" here is either an unexplained substitution or a typo.
• Silent overload of $\varepsilon$. Theorem 4.9 reuses the symbol $\varepsilon$ but refers to the Wasserstein precision of Assumption 4.8, not the $\ell_\infty$ precision of Assumption 4.3. The two precisions are numerically distinct and the switch is not flagged where it happens.
• Decoding-strategy corollary. Remark 3.2 claims that greedy-inaccessibility implies $<50\%$ generation probability under "any stochastic decoding strategy (e.g., beam search or Top-$K$ sampling)". Beam search is deterministic and can select non-argmax tokens, so it is not covered by the argument.
• Cross-step independence of $D^n$ is implicit in the main text. Section 5.3's multiplicative-convolution derivation of $D^n$ assumes per-step cell volumes are i.i.d. across positions. Remark F.1 acknowledges this in the appendix, but the main-text passage — on which Table 1's "Non-uniform Cells" row depends — does not.
• Section 5.4 only qualitatively tests Corollary 4.10. The section promises to "evaluate Corollary 4.10 through the copying task" but never compares the corollary's numerical threshold to Figure 4's empirical inflection lengths, so the arbitrary-$m$ regime is validated only qualitatively.
• "Solely on embedding-space geometry" overclaim. The conclusion invites the reader to attribute the characterization to the embedding matrix alone, whereas the cell partition $\{E_t\}$ is induced by the unembedding matrix $\mathbf{F}$ and the argument depends on the final-layer representation and the decoder-side partition.
• Bounded-embedding recursion is asserted, not derived. Appendix A.2's inequality $\|\mathbf{X}^l\|_\infty \le (I + kl(A+M))\|E_f\|$ is stated "therefore" with no derivation; the constant $k$ is not defined, and how $I$, per-layer increments, and $\|E_f\|$ combine into a single product is not evident.
• Soft-to-hard extension only transfers the upper bound. The remark "all of our results directly extend to Definition 2.3" is true for the counting bound but not for the tightness / linear-slope claims, which are lower-bound-flavored on the strictly smaller hard-prompt set.
• fp16 machine-epsilon convention is inconsistent. Appendix G.2.1 derives the fp16 spacing at exponent $k$ as $2^{k-p}$ with $p = 11$, giving $2^{-11}$ at $k = 0$, but then sets $\varepsilon = 2^{-10}$; G.2.2 uses $\varepsilon_j = 2^{j-12}$, contradicting the fixed value at $j = 0$ by another factor of 2. Different rows of Table 1 may end up computed with different implicit $\varepsilon$.
• Test-time-training extension over-claims. Section 7 states the results "characterize how the size of $h$ must scale with the length of the context in order to preserve accessibility." The bounds count sequences, not information content of a compressed source context; the missing bridge is not shown.

Reproducibility & code

• Table 2 support constants — partial reproduction, systematically low. The one stage of the pipeline for which prior-attempt artifacts survived reproduces $r$ and $\theta$ within the right order of magnitude but systematically below the paper. Reproduced radii vs Table 2: Pythia-160M 58.66 vs 63.62 (−7.8%), Pythia-410M 42.28 vs 54.90 (−23%), Pythia-1B 51.54 vs 65.68 (−22%), Qwen-2.5-0.5B 242.37 vs 309.00 (−22%), Qwen-2.5-1.5B 81.85 vs 153.62 (−47%); cone angles are also uniformly 0.32–0.48 rad smaller. Both $r$ and $\theta$ are extreme-order statistics, and the manuscript reports two different sample counts (Section 5.2 says 10K prompts, Appendix G.4 says $N = 10^5$); the observed deflation is exactly what a 10× smaller sample would produce.
• Table 2 vs Figure 5 numerical mismatch. Table 2 lists Qwen-2.5-1.5B radius $r = 153.62$ and Qwen-2.5-0.5B $r = 309.00$, but the corresponding Figure 5 max-radius curves plateau around $1.53$ and similar order. This $\sim100\times$ mismatch is nowhere reconciled, making it impossible to verify whether Table 1's Ball row was computed from the Table 2 or the Figure 5 values.
• Bounded-embedding recursion definition-dependent. Environment notes from the partial replication indicate that under the natural implementation (max over all layers including the input embedding), Pythia-160M plateaus at $R \approx 300$, not the $\approx 52$ shown in Figure 5. Combined with the unproved recursion in Appendix A.2, this makes the Figure 5 sanity check ambiguous to reproduce without knowing which layer(s) enter the $R$ maximum.
• Central rows of Table 1 could not be exercised end-to-end. The released code covers cramming, cell-volumes, and copying (src/cramming.py, src/cell_volumes.py, src/copying.py) and appears faithful in intent — the $D^n$ Monte Carlo and Remark 5.1 Dirac-mass sanity check are implemented — but the replication harness could not run these stages in this environment. Consequently the Cone, Ellipsoid, Ellipsoid + Non-uniform Cells, and Ellipsoid + variable-$\varepsilon$ rows, plus the empirical PG19 denominators that Table 1 divides by, were not independently reproduced. Shipping precomputed intermediates (per-model cramming JSONs, cell-volume distributions, a canonical Table 1 CSV) alongside the code would make Table 1 verifiable without re-running the full sweep.
• Cramming setup under-documented. The manuscript does not specify the grid of target lengths $n$, the seed for target sampling or soft-prompt initialization, the "subset of the model vocabulary" used for random targets, or the number of restarts per $(n,m)$. All are load-bearing for the reported minimum $R^2 = 0.88$ and for the Table 1 denominators.
• Copying-task setup under-documented. Section 5.4 states only the training format and stopping rule. Optimizer, learning rate, batch size, fine-tuning method (full vs adapter), training corpus size, length distribution, evaluation grid, and seed are omitted. Given the per-model $R^2$ range 0.46–0.97, these details are load-bearing for Figure 4.
• Sigmoid family unspecified. Neither Section 5.1 nor Section 5.4 states which sigmoid parameterization is fit; the reported aggregate $R^2$ values (min 0.88, median 0.95) and the near-degenerate low-$R^2$ cases depend on this choice.
• Two Table 1 rows lack self-contained formulas. The "Ellipsoid + Non-uniform Cells" and "Ellipsoid + variable $\varepsilon$" rows are defined procedurally; reproducing them requires re-implementing a 50M-sample Monte Carlo (with unstated seed) and separately fixing how $r_{\min}, r_{\max}$ are set per coordinate.
• Code URL rendering. The Section 1 footnote's URL is broken by strike-through / spacing artifacts, so a reader cannot click or copy it as-is.

Recommended Changes

Essential

• Requalify "tight up to a factor less than 10." Either restrict the abstract's claim to the tightest enclosure row per model, or update the wording to match Table 1's actual range (e.g., "$\le 11$ for the Ellipsoid + Non-uniform Cells enclosure, and $\le 21$ for the Ball baseline"). This addresses the "tight up to factor 10 overclaim" weakness above.
• Reconcile Corollary 4.10's factor 4 with Theorem 4.9's factor 2. Either correct one, or show the step in the proof of Corollary 4.10 that turns $(1+2r/\varepsilon)^d$ into $(1+4r/\varepsilon)^d$.
• Give the mean-field precision its own symbol. Rename $\varepsilon$ in Theorem 4.9 / Corollary 4.10 (e.g., $\varepsilon_W$) so it cannot be conflated with the $\ell_\infty$ precision of Assumption 4.3.
• Fix or explain the Table 2 vs Figure 5 radius mismatch. State the exact extraction procedure that produced Table 2's $r$ (which layer, which norm, and whether Section 5.2's "10K prompts" or Appendix G.4's "$N = 10^5$" was used), confirm whether the Ball row of Table 1 uses $r \approx 1.53$ or $r \approx 153.62$ for Qwen-2.5-1.5B, and recompute Table 1 if the wrong value was used.
• Distinguish optimization failure from fundamental inaccessibility in Section 5.1. Report cramming success under multiple restarts and/or longer schedules, or explicitly hedge the empirical slope as an upper bound on optimizer-found accessibility rather than accessibility itself.
• Justify or replace the random-token support estimator. Empirically check that cramming-optimized memories from Section 5.1 lie inside the estimated Ball/Cone/Ellipsoid, or estimate the support directly from optimized memories.
• Report the missing copying-task hyperparameters. Optimizer, learning rate, batch size, fine-tuning method (full vs adapter), training-corpus size, length distribution, evaluation grid, and seed for Section 5.4 / Figure 4.
• Add a numerical Corollary-4.10 comparison in Section 5.4. Place the predicted threshold from Corollary 4.10 next to Figure 4's empirical inflection lengths, per model, so the "closely matches" claim is quantitatively substantiated for the arbitrary-$m$ regime.
• Reconcile fp16 $\varepsilon$. Make Sections G.2.1 and G.2.2 use a single, consistent machine-epsilon and per-octave spacing convention, and re-derive the "Ellipsoid + variable $\varepsilon$" row.
• Ship canonical intermediates alongside the code. To make Table 1 reproducible without executing the full sweep, release per-model cramming/cell-volume JSONs, the estimated support constants for all seven models, and a canonical Table 1 CSV. This targets the "central rows of Table 1 could not be exercised end-to-end" reproducibility weakness.
• State the sampling count that generated Table 2. Unify Section 5.2's "10K prompts" with Appendix G.4's "$N = 10^5$" and report per-seed variability on $r$ and $\theta$, so downstream Table 1 rows are reproducible — the partial replication of Table 2 came in 7.8%–47% low, in the direction consistent with the smaller sample count.

Suggested

• Restrict Remark 3.2 to i.i.d. per-step sampling. Treat beam search separately; it is deterministic and can select non-argmax tokens.
• State the $D^n$ independence assumption in Section 5.3. Move Remark F.1 forward to the main text at the point of use.
• Report per-condition sigmoid $R^2$ and specify the sigmoid family. State the parameterization used for both cramming (min $R^2 = 0.88$) and copying (median $R^2 = 0.95$), and report per-$(n,m)$ or per-model values rather than aggregates.
• Acknowledge weak $R^2$ for Qwen-2.5-1.5B and Llama-3.2-1B copying fits. Qualify the "sharp / abruptly" language in Section 5.4 as model-dependent, and discuss whether the deviation is fine-tuning failure or a genuinely gradual decay.
• Rephrase "relies solely on the geometry of the embedding space." Include the unembedding matrix $\mathbf{F}$ and the decoder-induced partition $\{E_t\}$ in the description.
• Qualify "first rigorous theoretical explanation." Explicitly acknowledge Huang et al.'s impossibility result for copying, and describe the contribution as removing their idealized assumptions and providing a quantitative match.
• State which direction of the soft-to-hard extension transfers. Clarify that the counting bound extends but that tightness / linear-slope claims do not automatically transfer to the hard-prompt setting.
• Provide self-contained slope formulas or pseudocode for the last two Table 1 rows. Cover "Ellipsoid + Non-uniform Cells" and "Ellipsoid + variable $\varepsilon$", including how $r_{\min}, r_{\max}$ are set per coordinate.
• Fix the code URL rendering and confirm the exact repository name is transformers-accessibility (or the actual URL).
• Derive the bounded-embedding recursion in Appendix A.2. State how $I$, the per-layer increments $A + M$, and $\|E_f\|$ compose to $(I + kl(A+M))\|E_f\|$, and define $k$; also state which layer(s) enter the Figure 5 $R$ maximum so the sanity check is unambiguous to reproduce.
• Soften the test-time-training extension in Section 7. Downgrade "characterize how the size of $h$ must scale" to "inform", or spell out the missing step tying source-context information content to memory-vector capacity.
• Re-typeset the packing-number definition. In Definition 4.2 and Definition C.1, the radius should render as $\varepsilon/2$, not "$2\varepsilon$".
• Add a forward pointer to Remark 2.5 at the "duplicating the input leaves the per-token output unchanged" statement in Section 2.2, or restrict it to the encoder-free case.