A Unified Formal Framework To Predict Length Generalization in Linear RNNs, Transformers and Hybrid Models

CRASP-based formal frameworks are currently the best known predictors of length generalization in Transformers. However, similar theoretical generalization guarantees do not yet exist for Linear RNNs (LRNNs) and Hybrid models (which combine LRNNs and Transformers), even though much work has characterized their capabilities empirically. To help explain these phenomena, we introduce a unified RASP variant, different slices of which characterize these models' length generalization behavior. We extend previous length generalization frameworks for Transformers to establish guarantees for both LRNNs and Hybrid models. Using this unified framework, we show that all these sequence models length generalize on different classes of tasks, but globally are constrained to sublinear communication complexity and therefore are unlikely to length generalize on copying, addition, and multiplication. We test our framework on standard task suites and find it to be predictive of empirical performance for all models.