Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper presents theoretical and empirical results supporting an exponential gap between a sequence-to-sequence task and its decomposition into many smaller subtasks. In this study, the authors consider a bit parity task where the objective is to determine if the number of ones in a subset of a 0/1 array of length d is odd or even. This is formulated as a binary classification task. 

With this setup, the authors show the following main result:

1) When a task is decomposed into subtasks, a seq2seq model can get a get arbitrarily low zero-one loss (\epsilon) with a number of gradient updates that is polynomial in d.
2) When no supervision over subtasks is provided, for any polynomial time learning algorithm, the zero-one loss will be > ½ - \epsilon.
strength_and_weaknesses: Strengths:

1. The paper proves a useful result shedding light on the effectiveness of breaking down sequence-to-sequence problems into supervised subtasks.
2. The paper is well structured - it studies a well-defined problem, proves theoretical results, and verifies them empirically (albeit in a slightly different setting).

Weaknesses

1. As the authors point out, all of their results hold only when the number of subtasks is O(d) rather than O(1) and in most practical cases, O(1) subtasks are more likely.
2. The theoretical and empirical results use different model architectures.

Questions:

1. Since most of your theoretical claims are for recurrent networks, did you attempt to empirically validate them with RNNs? How do your conclusions hold for RNNs with activations besides ReLU? Is this assumption mostly a result of the setting used in Wang et al. 2021? ReLU RNNs.
2/ Why did you leave the input embeddings and initial hidden states untrained?
clarity,_quality,_novelty_and_reproducibility: Clarity - The paper is well-structured and motivated. The theorems are summarized clearly in the main body of the paper.

Quality - The paper is of sufficiently high quality.

Novelty - The main novelty of this paper is in proving the exponential gap in the learnability of sequence-to-sequence tasks with and without intermediate supervision. The paper builds on Wang et al 2021, Shalev-Schwartz et al. 2017 and Shalev-Schwartz & Shashua 2016.
summary_of_the_review: The main novelty of this paper is in proving the exponential gap in the learnability of sequence-to-sequence tasks with and without intermediate supervision. While there are some limitations on the number of sub-tasks with supervision required, it is still a good starting point for future work that seeks to understand why ideas like “chain-of-though” prompting of language models are so effective.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper aims to address the compounded natural language problems required by introducing sub-task decomposition and concatenating intermediate supervision to the input and training the sequence-to-sequence model on this modified input. 
The contribution of this paper can be concluded as:
* proving a positive theoretical result on decomposing compounded tasks with neural networks in an end-to-end manner
* The above theoretical results can apply to a broad family of tasks, and currently including SOTA  language models on complex multi-hop tasks in NLP
* generalizing the above results, and demonstrating that sequence-to-sequence tasks with sufficient intermediate supervision  allow learning any function in the P time complexity class


strength_and_weaknesses: #Strength
* The paper address a valuable problem: the compounded natural language problems requiring introducing sub-task decomposition and concatenating intermediate supervision
* Sufficient proofs are provided in the appendix

#Weaknesses
* The theoretical analysis of sequence-to-sequence models seem not strong enough, and many of first-mentioned symbols in equations have inadequate explanation. Maybe it is because you have moved many details to appendix. Analogously, the experiments face the same problem.
* The inspiration from this paper is limited, and it seems that the theoretical and experimental results are apparent
* The structure of the paper can be improved. BTW, I think it would be more legible to organize the sequence (1,2,3,4) in a vertical way in Figure 1.

clarity,_quality,_novelty_and_reproducibility: * Clarity: somewhat clear. The paper is easy to follow, but some important details are missing or unclear.
* Quality: somewhat technically sound. 
* Novelty: somewhat good. The inspriation is limited. 
* Reproducibility: key resources (e.g., proofs) are available and it would be better if sufficient details (e.g., experimental setup) are described such that an expert should be able to reproduce the main results.

summary_of_the_review: This paper has addressed a valuable problem: sub-task decomposition in sequence-to-sequence learning, and provided theoretical analysis, applied it to tasks and analyzed the time complexity. The paper is easy to follow but the inspiration is imited.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper analyzes the learnability of sequence-to-sequence tasks, based on whether or not the answers to sub-tasks are provided as part of the input sequence. It proves a rather general result: That *any* function in the P time complexity class is efficiently learnable by a neural network when sub-task supervision is provided, but there exists functions in P which are not learnable (in polynomial time) without sub-task supervision.

The paper gives significant attention to the “bit-subset parity” problem: this is the problem of determining whether a bit-string of length d has an even or odd number of ones in an unknown subset of d/2 indices. It shows that this problem is efficiently learnable by an RNN when sub-task supervision is provided, but is not learnable (under standard cryptographic or computational hardness assumptions) in polynomial time without this supervision. In this case, the sub-task supervision is the parity of pairs of the unknown indices, recursively followed by the parity of these sub-task parity answers in a binary-tree like structure: $par(x_i1, x_i2), par(x_i3, x_i4), …, par(par(x_i1, x_i2), par(x_i3, x_i4)), …$ (see Figure 2, Section 5). The paper then uses the hardness results regarding this bit-subset parity problem from Shalev-Shwartz et al. (2017) to prove it is not efficiently learnable.

Although the primarily contributions of this paper are theoretical, this paper also provides experiments showing that a powerful transformer network (BERT-base architecture) is unable to learn the bit-subset parity problem for $d \geq 32$ (within ~2M gradient steps), but can easily learn it when the sub-task supervision is provided (e.g., can learn $d=128$ in  $< 100k$ steps).

strength_and_weaknesses: Strengths
- I was impressed by the generality of their positive results: that any function in P is learnable when suitable sub-task supervision is provided. Their use of boolean circuits to prove this result was very clever.
- Their use of the bit-subset parity problem throughout the paper was effective at making their theoretical result more concrete and easier to digest.
- Although the primary results are theoretical, I do feel that these results have important empirical implications regarding the limits of sequence-to-sequence models in solving complicated tasks that require multiple intermediate reasoning steps, when intermediate sub-task supervision is not provided. It also serves as encouragement for empirical work that provides this intermediate supervision to large language models.

Weaknesses
- It is not immediately clear how the theoretical constructions presented in this paper can be applied to solve real problems in NLP/ML. Perhaps the authors could comment further on how they believe intermediate supervision can be provided in these practical settings.
- NIT: I felt that the clarity could be improved in a few places. For example, I felt that the hypothesis class defined by equation (6) could have been more carefully explained (for example, what is e_z, and what is w?).


clarity,_quality,_novelty_and_reproducibility: In general the paper is quite clear, of high-quality, novel, and reproducible (full proofs provided, source-code for experiments is provided). 
summary_of_the_review: This paper provides important theoretical results regarding the learnability (or unlearnability) of sequence-to-sequence tasks by neural networks, depending on whether or not sub-task supervision is provided. These results are quite general, and provide important insights for future empirical research in sequence to sequence learning.  As a result, I definitely recommend acceptance for this paper (although my review is only medium confidence, given that I am not super familiar with the related work).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies how intermediate supervision (i.e. breaking a task down into steps) can theoretically increase the power of learning complex tasks.

The authors give a real world motivating example of math problems i.e. 
"John and I split 12 apples between us, and he gave 1 to his son. How many apples does he have now?" (5)

which can be broken down into:

1. John and I split 12 apples between us. How many apples does he have now (6)
2. John had 6 apples and he gave 1 to his son. How many apples does he have now? (5)

This has been empirically observed in the past and has gained recent prominence due to impressive results with large language models (i.e. chain of thought prompting)

The authors assume a particular model (a simple RNN) and theoretically prove the following:

There exists a binary classification problem of size d such that with intermediate supervision it is possible for seq2seq model to get an arbitrary low error with a polynomial number of gradient updates in d. However, without intermediate supervision, then for any polynomial time learning algorithm the error will be higher than 1/2 - epsilon. 

They then explore the specific case of bit subset parity, showing learning curves for BERT that demonstrate that without intermediate supervision the number of training steps required grows very rapidly as the size of the problem increases, whereas with intermediate supervision the number of training steps grows at a much more favorable rate.

strength_and_weaknesses: Strengths
-Well written and interesting. 
-Studies a phenomenon that is of great interest to the community right now. 

Weaknesses
-The theory is interesting but does not lead to any new methods. 
clarity,_quality,_novelty_and_reproducibility: The paper is written clearly, is high quality and is novel. 
summary_of_the_review: I support accepting the paper. It is well motivated, well-written and sheds theoretical insight onto an interesting and relevant problem.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper theoretically proves that sub-task decomposition can facilitate training of an elmon RNN by reducing the number of gradient updates to polynomial order while undecomposed tasks can't be learned with polynomial updates.
strength_and_weaknesses: Strengthes:
1. Decomposing complexe reasoning tasks into subtasks is currently very popular in NLP, and some theoretically analysis of this paradigm can be helpful.
2. The paper is overall well written and the proofs/theorems looks good to me.

Weaknesses:
1. The authors motivate their research problem by sub-task decomposition of LLMs. However, most current practice of using sub-task decomposition with LLMs are using in-context learning without gradient updates, which is very dissimilar with the settings analyzed in the paper.
2. The model architecture analyzed in the paper is elmon RNN, which is also very different in nature compared with Transformer models (i.e., sequential computation in RNN v.s. parallel encoding with Transformers). The paper could be made more interesting if the proof can be generalized to Transformer architectures. 
clarity,_quality,_novelty_and_reproducibility: Clarity: Good
Quality: Ok
Novelty: Ok
Reproducibility: Good
summary_of_the_review: The paper provides some interesting theoretical analysis of the usefulness of sub-task decomposition for seq2seq tasks. However, the settings are somewhat oversimplified and deviate significantly from the main motivation of the paper (sub-task decomposition for NLP/reasoning tasks with LLMs.)
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper provides some theoretical results on sub-task decomposition for sequence-to-sequence learning problems. All reviewers appreciate the positive theoretical results, which are indeed novel in the context of this line of work. The paper is also well-written and well-organized. Even though there was a question about choosing the fine-tuning vs. in-context learning settings, the area chair still thinks this paper has strong merits to help us understand sequence-to-sequence learning in an earlier setup: Commonly, theoretical results in NLP are behind algorithmic developments. Overall, there was a clear consensus from reviewers that this paper should be accepted. 
justification_for_why_not_higher_score: Subtasks are limited, and the new theoretical results have not led to newly proposed algorithms.
justification_for_why_not_lower_score: There is a clear consensus that this paper should be accepted as a poster, because theoretical results on this topic are rare and novel in the field.
Decision: Accept: poster