Length Generalization for Transformers via Compression

We study when transformers can generalize from short training inputs to longer sequences. For restricted forms of C-RASP, we improve known sample-size bounds by an exponential factor. A connection to compressed strings yields polynomial length generalization bounds in the compressed setting and helps reconcile experimental results about the C-RASP hypothesis.

Preprint, submitted to arXiv on September 8, 2026.