Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks

By Noam Wies, Yoav Levine, Amnon Shashua. 2022

54 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Nick Haber
2. Noah D. Goodman
3. Eric Zelikman
4. Di He
5. Qian Huang
6. Gabriel Poesia
7. Haotian Ye
8. Liwei Wang

In Natural Language Processing

1. Di He
2. Noah D. Goodman
3. Haotian Ye
4. Liwei Wang
5. Yuhuai Wu
6. Eric Zelikman
7. Tao Qin
8. Tie-Yan Liu

Citations in the corpus

• STaR: Bootstrapping Reasoning With Reasoning (2022, background): “In addition, works have aimed to explain why rationales help: some have analyzed their impact from the perspective of latent variable models [19] while others have provided formal proofs of the benefit of intermediate task supervision [20].”
• Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective (2023, background): “Practically, this can be achieved by either adding special phrases such as “let’s think step by step” or by giving few-shot CoT demonstrations [29, 56, 51, 38, 63, 58].”
• Parsel: A Unified Natural Language Framework for Algorithmic Reasoning (2022, background): “Moreover, Wies et al. (2022) presents a theoretical argument showing problems that can be learned effi-ciently when decomposed but require exponentially many examples w.r.t. length if not decomposed.”