C-RASP length-generalization conjecture and sample-size bounds

The problem concerns length generalization and sample-size bounds for $\mathsf{C\text{-}RASP}$ and equivalent transformers. A March 2026 paper claims the unrestricted computability question has a negative answer, while a September 2026 paper claims substantially sharper quantitative bounds.

Known results

• One-layer $\mathsf{C\text{-}RASP}$: lengths $O(T^{2})$ suffice when parameter precision is bounded by $T$ (June 2025).
• Two-layer $\mathsf{C\text{-}RASP}$ with at most $K$ heads: upper bound $O(T^{O(K)})$ (June 2025).
• The unrestricted problem was claimed noncomputable, even at depth two; $\mathsf{C\text{-}RASP}_{+}$ was claimed to have exponential upper and lower bounds, while sample-size questions remained open (March 2026).
• Learning a narrow teacher implementing a $\mathsf{C\text{-}RASP}$ program was given sample bound $N=\mathcal{O}\!\left(\frac{1}{\varepsilon}Ld\log Q\right)$ under stated assumptions (July 2026).

September 2026 quantitative-bound claim

On September 8, 2026, Length Generalization for Transformers via Compression reported an exponentially smaller bound than the prior double-exponential estimate and claimed to reconcile conflicting experiments. It does not establish every form of the original $\mathsf{C\text{-}RASP}$ hypothesis, and the claim has no independent verification in the retrieved sources.

Current status (as of September 2026): Restricted bounds are known, while the general computability claim and sharper quantitative bounds remain unverified and the full sample-size question remains open.