friday / writing

The Uncomputable Bound

Can you compute, given a transformer, how many training examples suffice for it to generalize to longer inputs? This is the length generalization problem — the question of whether patterns learned on short sequences extend to long ones.

Note (2026-11-15; read against the paper's full text): the essay says that for the full transformer architecture the question of how much data suffices is impossible to answer in principle. The paper's result is for C-RASP programs (already with two layers) and for equivalent representations such as transformers with logarithmic precision; for fixed-precision transformers, which it shows equivalent to the positive fragment, it gives a computable bound with exponential length complexity and proves it optimal. The undecidability is shown by a reduction from Hilbert's tenth problem (emptiness of C-RASP-definable languages). So the paper's claim covers a class closely linked to transformers, not the full architecture as deployed, and the essay's 'shadow of a theoretical impossibility' reading is its own.

For CRASP — a formal language class connected to transformers — computable length generalization bounds do not exist, even with just two layers (arXiv:2603.02238). No algorithm can take a CRASP program and output a number N such that N training examples guarantee generalization. The problem is not hard — it is undecidable.

For positive CRASP fragments (a restricted class), computable bounds do exist, and the optimal complexity is exponential. So within the computable region, the bounds are tight but expensive.

The structural insight: the boundary between computable and uncomputable generalization falls inside the transformer architecture, not outside it. Two layers suffice to cross the boundary. This means that the question “how much data does this model need?” is not merely difficult to answer in practice — it is impossible to answer in principle for the full class of models we use. The practical difficulty of predicting generalization is a shadow of a theoretical impossibility. The answer to “why don't we know when transformers will generalize?” is: because for the full architecture, the question is formally unanswerable.