Research map / Learning theory and algorithms / Kernels and regression theory

Length Generalization for Transformers via Compression

NeurIPS 2026 · Learning theory and algorithms › Kernels and regression theory · approach: Empirical generalization measures · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that C-RASP+ and C-RASP_1 tasks admit polynomial compressed (power-word) length generalization bounds, giving exponential sample-size bounds, and uses this to explain the PARITY_k vs COUNT_k/MAJ_k length generalization gap.

Problem

Length generalization theory for transformers via C-RASP gives only doubly exponential sample-size bounds for C-RASP+ and C-RASP_1, and there are apparent contradictions between theory and experiments (e.g., PARITY_k fails to length-generalize at small k).

Approach

Measure length complexity over compressed strings (power words); show every satisfiable C-RASP+/C-RASP_1 formula is satisfied by a polynomial-length power word, via translation to reversal-bounded counter automata and Z-VASS cycle-removal with Eisenbrand-Shmonin and von zur Gathen-Sieveking bounds.

Key results

• Theorem: compressed length complexity of C-RASP+ and C-RASP_1 is polynomial, implying exponential sample size (improving the prior double-exponential bound).
• COUNT_k length generalization: accuracy on t2 at least 93.8% for all k, 98.4% at k=64.
• PARITY_k accuracy on t2 falls to 84.2% at k=8 and 74.2% at k=64, versus near-perfect at k=2.

Surprising findings

• Bounded PARITY_k does not length-generalize even for small k (e.g., k=50 in intro), seemingly contradicting C-RASP; the paper attributes this to exponentially large required sample size.

Limitations

• Results apply only to C-RASP_1 and C-RASP+ fragments, not full C-RASP
• Upper bounds only; PARITY_k lower bound is size-based and sample-size tightness is not established
• Experiments use a single small transformer architecture and task family

Experimental setup

Datasets: synthetic binary strings over {a,b} for COUNT_k, MAJ_k, PARITY_k

Benchmarks: COUNT_k length generalization MAJ_k length generalization PARITY_k length generalization

Metrics: accuracy on in-distribution and out-of-distribution length t

Baselines: C-RASP+ prior exponential/double-exponential bounds

Builds on: C-RASP hypothesis C-RASP+ C-RASP_1 Z-VASS reversal-bounded counter automata

Closest papers by meaning

• What Algorithms can Transformers Learn? A Study in Length Generalization (ICLR 2024 · similarity 0.94)
• A Formal Framework for Understanding Length Generalization in Transformers (ICLR 2025 · similarity 0.92)
• Universal Length Generalization with Turing Programs (ICML 2025 · similarity 0.90)
• Non-Asymptotic Length Generalization (ICML 2025 · similarity 0.89)
• Looped Transformers for Length Generalization (ICLR 2025 · similarity 0.89)
• Arithmetic Transformers Can Length-Generalize in Both Operand Length and Count (ICLR 2025 · similarity 0.88)