Loading
Life sciences · Preprint
arXiv · September 8, 2026
Raises a question worth testing. It does not answer one.
This preprint refines the C-RASP hypothesis for transformer length generalization by introducing a connection to compressed strings and power words, achieving an exponentially tighter bound on sample size compared to prior results. The work addresses an open theoretical question about the tightness of prior bounds and provides a fine-grained analysis that reconciles contradictory experimental evidence, but remains a theoretical contribution without new empirical validation of the refined bounds.
Preprint.
Prior worst-case sample size bounds for C-RASP fragments were double exponential; this work provides an exponentially tighter bound A polynomial length generalization bound for transformers is shown when using compressed strings via connection to power words Fine-grained analysis of C-RASP conjecture resolves contradicting experimental evidence against it
Safety was not reported in the material analysed. Check the source before drawing any conclusion about harm.
The source did not state who this applies to in practice.
This is a theoretical computer science contribution that refines an existing hypothesis about transformer behavior through mathematical analysis and resolves contradictions in prior experiments, but does not report empirical validation of the refined bounds on real tasks.
Quoted from the source exactly as published.
Graded across the dimensions that decide whether you should act, each from what the source actually supports. There is no single score, and where a dimension was not assessed it says so.
Recent advancements in transformer length generalization theory enable us to reliably predict when a transformer can learn to solve a task. In particular, the C-RASP hypothesis (a formalized version of the so-called RASP-l conjecture) posits that transformers length-generalize on a task if and only if a solution is expressible in the C-RASP language. While this hypothesis has strong empirical validation, theoretical problems arise from the fact that no computable length generalization bounds exist for C-RASP, alongside the discovery of seemingly contradictory experiments. To address these problems, we refine the C-RASP hypothesis utilizing the recently-proposed fragments C-RASP+ and C-RASP1. These fragments have computable length generalization bounds, though in the worst case requiring an extremely large (double exponential) sample size. It is an open question whether these sample size bounds are tight. In this paper, we resolve this open question by providing an exponentially tighter bound. In doing so, we show a polynomial length generalization bound for transformers if we adopt compressed strings, via a novel connection to power words. As an application, we show how this yields a fine-grained analysis of the C-RASP conjecture that resolves contradicting experimental evidence against it.
Taken from the source record, never inferred. Follow any of these and new work involving them reaches your briefing.