# Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks

arXiv: https://arxiv.org/abs/2204.02892 · HTML: https://mlsanity.com/paper/2204.02892/

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 62 references that are in the map.
- First posted on arXiv 6 Apr 2022.

## Builds on (most cited first, 30 of 33)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Scaling Language Models: Methods, Analysis & Insights from Training Gopher](https://mlsanity.com/paper/2112.11446/) (2021)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies](https://mlsanity.com/paper/2101.02235/) (2021)
- [Program Induction by Rationale Generation : Learning to Solve and Explain Algebraic Word Problems](https://mlsanity.com/paper/1705.04146/) (2017)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Explain Yourself! Leveraging Language Models for Commonsense Reasoning](https://mlsanity.com/paper/1906.02361/) (2019)
- [Generated Knowledge Prompting for Commonsense Reasoning](https://mlsanity.com/paper/2110.08387/) (2021)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [Limits of End-to-End Learning](https://mlsanity.com/paper/1704.08305/) (2017)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [Distribution-Specific Hardness of Learning Neural Networks](https://mlsanity.com/paper/1609.01037/) (2016)
- [Measuring and Improving BERT's Mathematical Abilities by Predicting the Order of Reasoning](https://mlsanity.com/paper/2106.03921/) (2021)
- [How Much Coffee Was Consumed During EMNLP 2019? Fermi Problems: A New Reasoning Challenge for AI](https://mlsanity.com/paper/2110.14207/) (2021)
- [Complexity theoretic limitations on learning DNF's](https://mlsanity.com/paper/1404.3378/) (2014)
- [Computational Benefits of Intermediate Rewards for Goal-Reaching Policy Learning](https://mlsanity.com/paper/2107.03961/) (2021)
- [Which transformer architecture fits my data? A vocabulary bottleneck in self-attention](https://mlsanity.com/paper/2105.03928/) (2021)
- [Knowledge Matters: Importance of Prior Information for Optimization](https://mlsanity.com/paper/1301.4083/) (2013)

## Built on by (most cited first, 30 of 41)

- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Goat: Fine-tuned LLaMA Outperforms GPT-4 on Arithmetic Tasks](https://mlsanity.com/paper/2305.14201/) (2023)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions](https://mlsanity.com/paper/2212.10561/) (2022)
- [Roll the dice & look before you leap: Going beyond the creative limits of next-token prediction](https://mlsanity.com/paper/2504.15266/) (2025)
- [Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers](https://mlsanity.com/paper/2502.02393/) (2025)
- [On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning](https://mlsanity.com/paper/2406.14197/) (2024)
- [Language Models Do Hard Arithmetic Tasks Easily and Hardly Do Easy Arithmetic Tasks](https://mlsanity.com/paper/2406.02356/) (2024)
- [Iterated Decomposition: Improving Science Q&A by Supervising Reasoning Processes](https://mlsanity.com/paper/2301.01751/) (2023)
- [On The Specialization of Neural Modules](https://mlsanity.com/paper/2409.14981/) (2024)
- [Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization](https://mlsanity.com/paper/2511.07378/) (2025)
- [Route-and-Reason: Scaling Large Language Model Reasoning with Reinforced Model Router](https://mlsanity.com/paper/2506.05901/) (2025)
- [A Theory for Length Generalization in Learning to Reason](https://mlsanity.com/paper/2404.00560/) (2024)
- [Semformer: Transformer Language Models with Semantic Planning](https://mlsanity.com/paper/2409.11143/) (2024)
- [From Reasoning to Super-Intelligence: A Search-Theoretic Perspective](https://mlsanity.com/paper/2507.15865/) (2025)
- [The Mystery of the Pathological Path-star Task for Language Models](https://mlsanity.com/paper/2410.13779/) (2024)
- [KV Shifting Attention Enhances Language Modeling](https://mlsanity.com/paper/2411.19574/) (2024)
- [Towards Generalizable and Robust Text-to-SQL Parsing](https://mlsanity.com/paper/2210.12674/) (2022)
- [Fine-Tune an SLM or Prompt an LLM? The Case of Generating Low-Code Workflows](https://mlsanity.com/paper/2505.24189/) (2025)
- [Minimalist Softmax Attention Provably Learns Constrained Boolean Functions](https://mlsanity.com/paper/2505.19531/) (2025)
- [To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Models](https://mlsanity.com/paper/2510.14826/) (2025)
- [Progressive Translation: Improving Domain Robustness of Neural Machine Translation with Intermediate Sequences](https://mlsanity.com/paper/2305.09154/) (2023)
- [Compositional Hardness of Code in Large Language Models -- A Probabilistic Perspective](https://mlsanity.com/paper/2409.18028/) (2024)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [Can Vision-Language Models Solve the Shell Game?](https://mlsanity.com/paper/2603.08436/) (2026)
- [Next-Token Prediction Task Assumes Optimal Data Ordering for LLM Training in Proof Generation](https://mlsanity.com/paper/2411.00863/) (2024)
- [Learning with Hidden Factorial Structure](https://mlsanity.com/paper/2411.01375/) (2024)
- [Data Shifts Hurt CoT: A Theoretical Study](https://mlsanity.com/paper/2506.10647/) (2025)
- [Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently](https://mlsanity.com/paper/2511.17852/) (2025)

## Abstract (arXiv)

The field of Natural Language Processing has experienced a dramatic leap in capabilities with the recent introduction of huge Language Models. Despite this success, natural language problems that involve several compounded steps are still practically unlearnable, even by the largest LMs. This complies with experimental failures for end-to-end learning of composite problems that were demonstrated in a variety of domains. An effective mitigation is to introduce intermediate supervision for solving sub-tasks of the compounded problem. Recently, several works have demonstrated high gains by taking a straightforward approach for incorporating intermediate supervision in compounded natural language problems: the sequence-to-sequence LM is fed with an augmented input, in which the decomposed tasks' labels are simply concatenated to the original input. In this paper, we prove a positive learning result that motivates these recent efforts. We show that when concatenating intermediate supervision to the input and training a sequence-to-sequence model on this modified input, unlearnable composite problems can become learnable. We show that this is true for any family of tasks which on the one hand, are unlearnable, and on the other hand, can be decomposed into a polynomial number of simple sub-tasks, each of which depends only on O(1) previous sub-task results. Beyond motivating contemporary empirical efforts for incorporating intermediate supervision in sequence-to-sequence language models, our positive theoretical result is the first of its kind in the landscape of results on the benefits of intermediate supervision for neural-network learning: Until now, all theoretical results on the subject are negative, i.e., show cases where learning is impossible without intermediate supervision, while our result is positive, showing that learning is facilitated in the presence of intermediate supervision.