Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper introduces a novel positional encoding that improves transformers' systematic (length) generalization capabilities on a set of algorithmic tasks, including copying, reversing, sorting, and grouping. Concretely, the paper replaces the learnable position embedding method with random labels from longer sequences, thus allowing the model to encode the longer sequences with familiar labels. The paper empirically demonstrates that the proposed method achieves better length generalization performance than learnable and sinusoidal position embeddings. Finally, the paper analyzes the attention matrices of the trained models and shows that they implement the algorithmic operations required to solve the corresponding tasks.
strength_and_weaknesses: **Strengths**

The paper proposes a novel position embedding method that increases length generalization on a series of algorithmic tasks compared to learnable and sinusoid position embeddings. To that end, the paper introduces a new suite of algorithmic tasks and considers the single-task and multi-task settings, which are interesting. Moreover, the paper conducts an in-depth analysis of the model behavior on the different tasks and shows that, e.g., a two-layered transformer trained on the sorting task learns to first sort shapes and then the other features.

**Weaknesses**

The paper fails to discuss and compare to relevant related work:
* The paper does not compare its position embedding method to ALiBi encodings (Press et al., 2021), which were proposed to increase the length generalization capabilities of transformers on natural language processing tasks.
* The paper does not compare its position embedding method to the Neural Data Router (Csordás et al., 2022), which is an extension of the transformer architecture (consisting of shared layers, gating, geometric attention, and directional encodings) that significantly improves the systematic generalization capabilities of transformers on a wide range of algorithmic tasks.
* The paper does not discuss the length generalization benchmark introduced by Delétang et al. (2022), which evaluates transformers on a highly related set of tasks, including reversing, copying, and sorting. In particular, Delétang et al. (2022) assess the length generalization capabilities on significantly longer sequences (training on lengths up to 40 and evaluating on lengths 41 to 500). Given the accuracy decrease over sequence lengths (see Figures 2 D) and 6 C)), I am not convinced that the proposed encodings meaningfully increase length generalization for substantially longer sequence lengths.
* It would be interesting if the paper would discuss recent work showing that transformers can learn positional information without position embeddings (Haviv et al., 2022). 

Moreover, while the paper shows that its proposed position embedding increases the transformer's length generalization on a set of algorithmic tasks, it does not evaluate its effectiveness on natural language processing tasks. In particular, it would be interesting to see if the proposed embedding can also be used to "train short and test long", as demonstrated by the ALiBi encoding (Press et al., 2021).

clarity,_quality,_novelty_and_reproducibility: **Clarity**

The paper is generally well-written and easy to follow. However, several aspects of the paper are unclear:
* Is there a quantitative difference between multi-hot and one-hot encodings of the input sequence? In principle, the multi-hot encodings could be reformulated as one-hot encodings. To the best of my knowledge, using multi-hot encoding is quite nonstandard.
* How do the grouping and sorting tasks differ? Is the order of the grouped items irrelevant? If yes, how is that evaluated?
* Are the labels randomized at every training step or just once per sequence?
* Does the label-based encoding correspond to the original learned encoding for sequences of length 50, given that the item labels range only from 0 to 49?
* Why does the paper consider item *and* label prediction, which is quite nonstandard, as the paper states itself? Also, why does the model have to predict the task token in the multi-task setting if the task is provided as input?

Moreover, there are a few minor mistakes:
* Abstract: analysis -> analyses
* Figure 5: cross -> across

**Quality**

As mentioned in the weaknesses section above, the paper fails to discuss and compare to a series of highly related works, which calls into question the practicality and validity of the results.

**Novelty**

To the best of my knowledge, label-based encodings have not been proposed by prior work.

**Reproducibility**

The paper does not provide sufficient details of the experimental setup to reproduce the results. In particular, the sampling process used for label assignment is not specified. Code is not provided.

summary_of_the_review: Given the insufficient comparison to related work, which calls into question the practicality and validity of the results, I do not recommend accepting the paper in its current form.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: In this paper, the authors explore Transformer's systematic generalization in algorithmic tasks, including copy, reverse, and hierarchical group or sort operations on an input sequence. The authors create a set of tasks and show that a two-layer Transformer successfully learns these tasks and generalizes to sequences longer. Particularly, a random label-based order encoding method, in place of the positional encoding, improves the systematic generalization of Transformer on the studied tasks.
strength_and_weaknesses: # Strengths
The paper provides a thorough analysis of a small Transformer on a set of algorithmic tasks.

# Weaknesses
1. The paper is of limited novelty. The major technical novelty is the proposed random label-based order encoding method. However, there lacks an explanation and insights why it works.

2. The authors do not conduct any experiment on the well established datasets, like SCAN. Besides, there is no baseline in this work. The authors should have comapred with Transformers using relative positional encoding (Csordas et al, 2021).
clarity,_quality,_novelty_and_reproducibility: The paper has limited novelty.
summary_of_the_review: The paper is of limited novelty and lacks comparison with previous methods. Therefore, I recommend rejection.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an encoding method that replaces the standard positional encoding in transformers. The label-based order encoding method achieves strong generalization to sequences longer than training ones.

This paper also analyzes two-layer causal transformers to learn multiple algorithmic operations. It finds that multi-level task learning improves when more attention heads at deeper layers.

The paper also finds that these models have signs of systematic decomposition within tasks and exploitation of shared structure across tasks.
strength_and_weaknesses: ***Strength***

- This paper proposes a simple yet effective new method that has improved over a state-of-the-art and widely used method.
- It analyzes how transformers address the generalization problem.
- It finds how to improve the performance (e.g., putting attention heads at deeper layers) and signs of systematic phenomenons.

***Weakness***

**The weakness mainly comes from the concern of whether the results and findings in the particular setting still hold in more complicated cases.**

**1. The advantage over conventional positional encoding**

The conventional positional encoding was designed for natural language inputs.
For example, it contains information on relative position or distance in input, as the context window is helpful for natural language.
The experiment in this paper does not have natural language input, and the tasks are not much related to relative position or distance in input.
So it is not very convincing that the advantage still exists in other tasks, e.g., natural language processing.

**2. Disentangled item representation**

The items contain shape, color, and texture.
However, the item units indicate the value in each feature dimension.
So the item representations are already disentangled, e.g., color and shape values are in different input nodes.
Addressing entangled data (e.g., the images of the items) is a critical expectation for systematic generalization.
The model behavior on disentangled data may not be the same as on entangled data.

**3. Model design**

It is not very convincing that findings in two-layer transformers will naturally extend to deeper transformers.
The limit of depth may prevent the model from having complicated behaviors.
clarity,_quality,_novelty_and_reproducibility: Clarity:

This paper is clear to read.
However, the words in the figures are too small.

Quality:

There are concerns about the task, data representation, and model designs (mentioned above).

Novelty:

There are novelties in proposing a new encoding method, analyzing with two-layer transformers and multiple findings.
However, whether they are still valid in more complicated cases is unclear.

Reproducibility:

The paper does not mention (anonymized) source codes.
summary_of_the_review: This paper proposes a new encoding method that outperforms a widely used one and has informative analyses and findings.

However, the reviewer does not recommend acceptance because of the abovementioned weaknesses.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies the length generalization abilities for Transformers on algorithmic tasks, particularly when a new learnable position embedding method with random labels is used in place of relative position encodings. Both length generalization and Transformer's performance on algorithmic tasks are interesting and timely topics to study. However, several of the reviewers pointed out that both the models and the tasks considered here are relatively simple, which makes it difficult to assess whether the insights here would also hold for more realistic applications of Transformers.
justification_for_why_not_higher_score: Several of the reviewers pointed out that both the models and the tasks considered here are relatively simple, which makes it difficult to assess whether the insights here would also hold for more realistic applications of Transformers.
Decision: Reject