Research map / Large language models / Reasoning and chain of thought

Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory

ICLR 2025 · Large language models › Reasoning and chain of thought · approach: Theory of autoregressive reasoning · 1 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.

Proves that one-layer and finite-precision SSMs are communication-complexity and automata limited at function composition, CoT step counts, and regular languages, and shows empirically that SSMs and Transformers fail on composition, multiplication, DP, and Einstein's puzzle.

Problem

Whether state space models (SSMs) and Transformers can perform function composition and multi-step compositional reasoning efficiently, given limited state size, chain-of-thought steps, and computational class.

Approach

Uses communication-complexity reductions (function composition, pointer chasing) to derive lower bounds on SSM width and CoT steps, shows L-layer SSMs lie in logspace and finite-precision SSMs recognize only regular languages, and tests these predictions empirically on multiple SSM and attention models.

Key results

• GPT-4o reaches only about 27% on 4-by-3-digit multiplication per the introduction, and all tested models fail on 5-by-5-digit multiplication even with CoT.
• On Math-QA, GPT-4o scores 51.8% versus 42.2% for Jamba, 35.0% for Mamba and 28.6% for S4-H3.
• SpaRTUN accuracy is 80.8% for GPT-4o versus 50.8% for Jamba, 42.2% for Mamba and 35.2% for S4-H3.

Measured effects reported in the paper

Surprising findings

• GPT-4o scores only 56.8% on BIG-Bench Hard boolean expressions while Jamba scores 78.2%, below the attention-free baselines' expectations.
• Error analysis suggests SSMs and Transformers learn shortcuts that appear compositional in-distribution but fail on larger inputs.

Limitations

• Theoretical lower bounds are for one-layer SSMs; the multi-layer case is only conjectured.
• Empirical evaluation uses 500 samples per task and a limited set of models, some accessed only via API with a changing GPT-4 version.

Experimental setup

Datasets: Math-QA BIG-Bench Hard Temporal-NLI SpaRTUN

Benchmarks: Math-QA BIG-Bench Hard Temporal-NLI SpaRTUN multi-digit multiplication dynamic programming Einstein's puzzle

Metrics: accuracy

Baselines: GPT-4o GPT-4 Jamba Mamba S4-H3

Builds on: Chain-of-Thought prompting Mamba Jamba pointer chasing lower bounds Transformer function composition analysis

Closest papers by meaning

• Position: A Theory of Deep Learning Must Include Compositional Sparsity (ICML 2025 · similarity 0.88)
• State Space Models are Provably Comparable to Transformers in Dynamic Token Selection (ICLR 2025 · similarity 0.87)
• On the Expressive Power and Limitations of Multi-Layer SSMs (NeurIPS 2026 · similarity 0.87)
• Ask, and it shall be given: On the Turing completeness of prompting (ICLR 2025 · similarity 0.87)
• Longhorn: State Space Models are Amortized Online Learners (ICLR 2025 · similarity 0.87)
• Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality (ICML 2024 · similarity 0.87)