What Algorithms can Transformers Learn? A Study in Length Generalization

Thank you for your time and effort in reviewing our paper! We are delighted that you found our conjecture well-motivated and experimental results compelling. We are grateful that you support the acceptance of this work. We would like to address the comments and questions you’ve raised, and we’d be very open to further discussion.

The scratchpad designs for parity and decimal addition, though effective, are a bit different from the RASP format. For example, it seems that the proposed scratchpad for addition is motivated by correcting the failure modes discussed in section 4.3. It would be nice if the author could clarify the connection between the scratchpad designs and the RASP.

Thank you for pointing this out. We have restructured Section 5 to better explain the connection with RASP conjecture. To summarize, one consequence of the RASP conjecture is that by converting the task into one that has a simple RASP-L solution, we can improve length generalization performance. We can do so by changing the task format, adding a scratchpad, or both. For addition, the standard format does not have a RASP-L solution because it requires index arithmetic, which is forbidden in RASP-L (see Appendix F.2). However, if we add index hints, we can then replace the operations that require index arithmetic (forbidden) with ones that use induction heads (easy to write in RASP-L) to perform indexing. Thus, the new task format can now admit RASP-L solutions. Similarly, this gives us a perspective on why scratchpad has often been found helpful for reasoning problems. In the case of parity, we cannot represent the parity algorithm because RASP-L does not allow arbitrary loops for constant depth Transformers. However, the autoregressive nature of Transformers gives us a way to simulate a simple loop by using a scratchpad. With the scratchpad format, there now exists a RASP-L program that produces the next-scratchpad-token, without requiring any loops. We hope that this clarifies the connection between the proposed designs and the RASP conjecture.

As a general question, can the author recommend the possible directions to solve the hard ones? The proposed scratchpad solution requires a detailed understanding of the failure modes for each hard task, which doesn't seem quite scalable.

This is indeed a challenging aspect of the framework. Currently predicting or improving length generalization entails finding a RASP-L program that solves the task. We provided a few examples that can be generally more applicable, such as adding index hints for tasks that require complex indexing operations, and scratchpad for unrolling loops in the algorithm. Nonetheless, one promising future direction is to identify “unnatural operations” as suggested by RASP-L, but which are common subroutines for a large class of algorithms, and increase the training data coverage for those operations. This may help the model to perform these operations through memorization, and leverage this to learn other algorithms in a more generalizing way.

Missing citations

Thank you for the suggestions, we’ve added a more thorough discussion in Appendix A.

Conclusion:

Thank you for taking the time to read our rebuttal. If our response addresses your concerns, we kindly ask that you consider raising your score. Otherwise, please let us know about your remaining concerns/questions so we can make further improvements.

the metric as "median among 20 runs" is not enough to fully characterize the transformers' performance, given their non-convex optimization nature. Other metrics, such as "maximum" or "ratio of almost perfect," could be more informative and practical.

In Fig 3, 7b, and 8, we show the individual test performance of all 20 runs (plotted as points). For brevity we default to reporting the median, but most experiments follow the same pattern as those in Fig 3. We hope these plots can give you a fuller picture of Transformer’s performance. If there is a specific additional metric you would like to see, we are happy to compute it on the 20 runs shown.

The tasks are simple: from count to addition/parity.

On the positive side (length-generalizing tasks), we agree that it would be interesting to demonstrate more complex tasks which length-generalize. We focused our paper on simple tasks for exposition purposes, and to better connect with the existing literature on length generalization (where such simple tasks are standard). However, our RASP-L framework is more general, and can indeed express more complex tasks than we presented here due to space constraints (such as sorting and finite state automata). We can consider adding such tasks into the full version of this paper.

On the negative side, we could have included a large number of complex tasks, because most tasks will not length-generalize and will also not have a RASP-L program. A number of more complex tasks have been tested in the literature, where they were shown to fail at length-generalization. These tasks include: dynamic programming, multiplication, and certain kinds of logic puzzles (as tested in Dziri et al. 2023). We thought about these tasks, and could not devise RASP-L programs for them (even for e.g. multiplication), suggesting that they are unlikely to have simple RASP-L solutions. In general, Transformers only seem to length-generalize on very particular types of tasks, and so we focused on identifying positive instances of length generalization, since negative instances abound.

Ablation studies on "without the index hints" are needed.

We mention briefly in Section 4.3 that no generalization is observed on standard addition or parity (no index hints) under our experimental setting. We evaluate different lengths in increments of 5, and all 20 runs for all length showed a test EM of ~0% on these tasks. For brevity we do not include a plot, but we have added this detail to the updated pdf for better clarity.

The learnable constraints are interesting, but there are no reasoning/proof/experiments to support their choices, such as which operators are "learnable" in which sense, how to find and choose them, and if the current set of operators can represent all "learnable" operations.

We agree that our work does not provide a theoretical justification for the definition of RASP-L. However, we do consider the experiments in the paper as evidence that our RASP-L constraints are meaningful (though not conclusive of course). Specifically, we gave RASP-L programs for all the “symbolic tasks” which were known to length-generalize in the literature (to the best of our knowledge) — this shows our definition is expressive enough to capture positive instances. Conversely, for tasks which do not length-generalize, we were unable to devise RASP-L programs to solve them: we view this as heuristic evidence that RASP-L is not “too expressive.” We’ve added a table in Figure 1 which summarizes all our experiments, to show the RASP-L evidence more clearly.

We acknowledge that we do not have proofs that tasks (such as Parity) cannot be written in RASP-L, but we note that similar statements about computational complexity classes are notoriously difficult to prove (they amount to circuit-complexity lower-bounds). However, our claims are at least falsifiable: one simply has to give a RASP-L program that solves e.g. Parity, if such a program exists.

Regarding whether the current set of operators can produce all “learnable” operations: Thank you for bringing up this point. We have added a more thorough discussion of this in Appendix G, paragraph “Limitations of RASP-L.” Briefly, we believe RASP-L captures most “symbolic” learnable programs, but it certainly does not capture all learnable programs. A large class of learnable but non-RASPable tasks are numerical algorithms, such as linear regression, which involve high-dimensional matrix and floating-point operations. One could imagine extending RASP-L to encompass numerical algorithms as well — we consider this an interesting direction for future work.

There is no characterization of the function space represented by the "RASP-L" programs.

We agree that it is an important open question, so we have added this discussion explicitly in Appendix G, paragraph “On Formal Language Characterizations.” This is also an open question even for the original RASP language of Weiss et al. (2021).

Thank you for your time and effort in reviewing our paper! We are delighted by your appreciation for the importance of this line of work and for our generalization improvements on addition and parity. We would like to address the comments and questions you’ve raised, and we’d be very open to further discussion.

The definition of RASP-L programs is also vague and unclear.

We want to highlight our formal definition of RASP-L programs in Appendix F (Section F.1 defines RASP, and then Section F.2 defines RASP-L based on RASP). There we specify the allowed types and the allowed program syntax for the RASP-L language. We include an informal presentation of RASP-L in the main body for brevity and accessibility, but appreciate that this may require more clarification. We would welcome any specific pointers regarding unclear aspects of the definition as we work to improve the presentation.

Regarding OOD vs IID performance:

In all of our experiments except for parity, we only evaluate models that achieve ~100% accuracy on in-distribution test samples. This includes addition on all training lengths. Parity without scratchpad is a special case as it is well known that Transformers cannot even fit the training set for long parity sequences (e.g. Chiang & Cholak and Bhattamishra et al). All parity with scratchpad experiments are trained to convergence. We hope this fully addresses your concern.

There is no proof or reasoning for the conjecture. There is little evidence saying that transformers actually learned or have any relationships with the "RASP-L" program in general. According to the experimental results where "transformers mostly generalize to length at most 50 when trained with length<=40", it is also hard to believe that the true "RASP-L" programs have been learned. Can you explain why the length generalization performance of transformers is still limited (e.g., from length<=40 to length=50) even when the conjecture conditions are fulfilled?

We agree that our work has no theoretical justification for the conjecture; it is currently a purely empirical claim. Nonetheless, we view such empirical work as an important first step towards understanding new phenomena -- a step upon which theory can be built. We hope that our conjectures can eventually be formalized and proven, but we leave this (significant) endeavor for future work.

(As an aside, the reviewer may be interested in our new Appendix H, where we added a theoretical example from boolean function analysis that illustrates our conjecture in a simple case).

We wish to clarify the scope of our main claims. Our Main Conjecture (Section 2) only characterizes which tasks Transformers are likely to length-generalize on, and not why or how they do so. Specifically, our Main Conjecture only claims that RASP-L is a useful predictive tool: empirically, if a task can be solved by a simple RASP-L program, then it is likely to exhibit strong length generalization, and vice versa. This is a phenomenological claim, as opposed to a mechanistic one. Nonetheless, we believe that the toy model in our introduction suggests a plausible mechanism for Transformer learning, and could guide new lines of mechanistic investigations in future work.

Re. degradation at longer lengths:

There are a number of factors that could influence how robustly the correct solution is learned, if indeed it is. We do not expect (and indeed do not observe) perfect length generalization over arbitrary lengths. Some level of degradation is likely fundamental due to issues trying to approximate a discrete program with a continuous space (e.g. noisy optimization, finite precision, etc).

One other possible explanation, compatible with the RASP conjecture, is that there exists other “shortcut” solutions which do not generalize, but are simple enough to compete with the true RASP-L program during training. Since it is likely intractable to determine the minimum RASP-L program that fits a given training set, we cannot predict a priori what forms of “data diversity'' are required to rule out such ”shortcuts“, even if our conjecture holds true. Nonetheless, our study focuses on the relevant characteristics of tasks that influence generalization performance, thus even good albeit imperfect generalization lends strong signal to the usefulness of this perspective. We have added several new paragraphs in the revised pdf (in Section 2, and Appendix G), which highlights these limitations for the reader.

Thanks for the clarification question! We actually do mean there is also a RASP-L program for forward-order addition. We've expanded a discussion of this in the updated Section 5.1, which we think you will find interesting. Forward addition can in fact generalize when we try harder, e.g. be more clever with the data diversity of the training distribution. The RASP-L programs for reverse and forward addition can be found in Listings 7 and 8. It is unintuitive that forward addition has such a solution, since the natural algorithm is done in reverse order to do the carry dependencies. However, it turns out that we can represent a similar algorithm that computes carry chains through parallel and constant step computations. We think that this is a great illustration of the usefulness and flexibility of the RASP-L perspective. The RASP-L code is hard to parse, so we'll follow up with some more intuition to help guide you through it, but hopefully this answers your question in the meantime.

We also attach a code sample for the example generation part of the addition task. We removed some unnecessary components that had to do with other ablations but still apologize for the code being more complex than it needs to be.

def generate_instance(self):

    if self.hard_carry:
        # hard carry generates questions with carry chains e.g. 9999 + 0003 = 10002
        num1_len = np.random.randint(self.min_range, self.max_range+1, size=1)[0]
        num2_len = num1_len
    else:
        num1_len = np.random.randint(self.min_range, self.max_range+1, size=1)[0]
        num2_len = np.random.randint(self.min_range, self.max_range+1, size=1)[0]

    num1 = [np.random.randint(self.min_num, 10, size=1)[0]]
    if num1_len > 1:
        num1 = num1 + list(np.random.randint(self.min_num, 10, size=num1_len-1))                
        
    if self.hard_carry:
        num2 = [9-x for x in num1]
        num2[-1] = np.random.randint(num2[-1]+1, 10, 1)[0]
    else:
        num2 = [np.random.randint(self.min_num, 10, size=1)[0]]
        if num2_len > 1:
            num2 = num2 + list(np.random.randint(self.min_num, 10, size=num2_len-1))      

    num1 = ''.join(map(str, num1))
    num2 = ''.join(map(str, num2))

    ndigits = max(len(num1), len(num2)) + 1 # add one to the max (for the carry to be easier)
    s1, s2 = list(map(lambda q: q.rjust(ndigits, '0'), (num1, num2)))  # padding

    start_id = np.random.randint(0, len(list(self.tokenizer.count_id.values()))-ndigits+1)
    ids = list(self.tokenizer.count_id.values())[start_id : start_id + ndigits] # contiguous sequence of ids


    if self.index_hints:
        s1_sequence = ' '.join([f'{a} {b}' for a, b in zip(s1, ids)])            
        s2_sequence = ' '.join([f'{a} {b}' for a, b in zip(s2, ids)])
    else:
        s1_sequence = ' '.join(list(str(s1)))            
        s2_sequence = ' '.join(list(str(s2)))    

    prompt_sequence = f'{s1_sequence} {self.tokenizer.ADD_TOKEN} {s2_sequence}'

    carry = 0
    sumpairs = []
    i = 0
    for d1, d2 in zip(s1[::-1], s2[::-1]): # for all digits (LSB first)
        n1, n2 = int(d1), int(d2)
        ans = (carry + n1 + n2) 
        dAns = ans % 10
        newCarry = 1 if ans >= 10 else 0

        id = ids[ndigits-i-1]
        sumpairs.append((id, str(dAns)))
        i += 1
    
    if not self.reversed_ans:
        sumpairs = sumpairs[::-1]

    if not self.answer_index_hints:
        sumstr = [c for (id, c) in sumpairs]
    else:
        sumstr = [c for pair in sumpairs for c in pair] # flatten id, digit
    answer_sequence = ' '.join(sumstr)

    final_sequence = f'{prompt_sequence} {self.tokenizer.SEP_TOKEN} {answer_sequence}'            
    return final_sequence

I appreciate the authors' efforts in the thorough and long rebuttals. Unfortunately, I haven't been able to find time to read all the rebuttals and the appendix referred to in the rebuttal. Here, I will try to frame my current thoughts in case they are useful for the authors' further rebuttal. I will try to read all the rebuttals and the referred appendix before the deadline.

For concerns regarding experiments, one wield thing for me to believe is that the authors claim to achieve "perfect" or "~100%" performances for addition with 20/40-digit numbers using a six-layer transformer. The task may even be out of the representation power of the models in the reviewer's understanding. It would be great if the authors could share codes to reproduce these results for double-checking.

• Also, my main concerns regarding the experiments are whether or not they are strong enough to support the authors' claims without more theoretical analysis. Unfortunately, the concerns still stand for e.g., the only +10 length generalization, the tasks are still simple, and some confusing points as stated above. For the metrics, just for what it's worth, I would recommend plotting figures like Fig. 3 for all experiments, or using more metrics like percentage of "perfect generalization" or maximum to show how likely the models can successfully generalize instead of the average/median performances. In some sense, we are characterizing how many local minimums are "good" instead of their averaged performances.

For the definition and formulation of RASP-L, I agree it is difficult to formalize "learnable" for neural networks, but this is an important concern from my perspective, given the claims of this paper. I have not checked Appendix G yet. Hopefully, it can help alleviate some of these concerns.

Overall, I appreciate the authors' efforts in studying this important and challenging problem. On the other hand, I would also like to make sure the claims and results are precise and solid. Hopefully, my concerns could be alleviated by reading more of the rebuttals and appendix.

Thank you for your time and effort in reviewing our paper! We are delighted that you find our approach to understanding Transformers novel and well-supported by our experiments. We are grateful that you support the acceptance of this work. We would like to address the comments and questions you’ve raised, and we’d be very open to further discussion.

Some concepts are not clearly defined, making their meanings obscure and the statements less rigorous. For example, there is no reference or definition for the "causal Transformer" and "causal masking"; how to identify whether a RASP-L program is "simple" or "difficult".

Thanks for point this out. “Causal Transformers” are also often known as “decoder-only Transformers” in the literature. We have added a clarification in the updated manuscript. Essentially, with causal masking, self attention modules can only attend to tokens that came before the current token, similar to other unidirectional models.

A proxy for RASP-L program simplicity is the lines of code or lines of operations in the program. We illustrate this concretely with an expanded comparison of forward vs reverse addition in Section 5.1, where we compared the lines of code in the RASP-L program for each, and showed that this corresponds to generalization performance.

The correlation between RASP-L representable and the generalization of Transformer need further discussions. Are the selected cases representative enough? Is there any task which can be represented by RASP-L but Transformers hard to generalize, or vise-versa? These answers are needed to make a stronger statement on the correlation between the two.

This is a fair question. Although we cannot prove conclusively that RASP-L covers all cases of generalization success and failures, and in fact there are likely exceptions due to the complex nature of learning and generalization, we have considered most empirical analyses of Transformer length generalization on algorithmic tasks in the literature to the best of our knowledge. We have not observed exceptions in these cases. See Figure 1a for a clearer summary.

Given that most studies in the literature focus on highlighting length generalization failures, we introduced a number of new tasks to showcase that Transformers do in fact have the ability to show strong length generalization. We have identified more of these positive examples than we had room for in the manuscript, such as sorting and finite state automata. We can consider adding such tasks into the full version of this paper. On the negative side, it is easy to find tasks which do not admit RASP-L programs. Dziri et al. 2023 studied a number of tasks (e.g. dynamic programming, multiplication, and certain kinds of logic puzzles), and showed failures in length generalization. We could not devise RASP-L programs for these algorithms, suggesting that they are unlikely to have simple RASP-L solutions. Nonetheless, RASP-L only covers a subset of possible programs that could be represented by a Transformer. In particular, RASP-L focuses on symbolic tasks. A large class of learnable but non-RASPable tasks are numerical algorithms, such as linear regression, which involve high-dimensional matrix and floating-point operations. We have added a discussion of the limitations in Appendix G.

No discussions on the limitations of this work.

Thank you for pointing this out. We have added substantial discussions on limitations of this work. Please see end of Section 2 and Appendix G.

Empirical results show that the max train length has a great impact on the generalization ability of Transformers. Is the proposed method helpful in analyzing this phenomenon?

In this work, we used max train length as a measure of training data diversity. As proposed by our Main Conjecture, one condition on length generalization is diversity--- the training data should be sufficiently diverse, such that there does not exist any shorter RASP-L program which agrees with the task in-distribution but not out-of-distribution. Intuitively, a dataset containing only 5 different lengths is more likely to have shortcut solutions than a dataset that contain 50 possible lengths. We have expanded Section 5 to include a deep dive on addition, which includes a section on how increasing data diversity by changing the sampling procedure also leads to improved performance. The Main Conjecture can be used to understand both phenomena (max train length and improved sampling procedures).

Conclusion:

Thank you for taking the time to read our rebuttal. If our response addresses your concerns, we kindly ask that you consider raising your score. Otherwise, please let us know about your remaining concerns/questions so we can make further improvements.

Dziri et al: Faith and Fate: Limits of Transformers on Compositionality

Some experiments have been covered in prior work. The shifted position experiments are also included in Liu et al. 2023(a) [...] The scratchpad experiments are similar to those in Liu et al. 2023(a).

We first emphasize that the primary contribution of our work is not in the experiments, but in the conceptual framework which captures the results of those experiments (the RASP-L definition and conjecture). Indeed, our goal is to help understand the various experimental phenomena that have been observed in the past. Many papers, including Liu et al. 2023(a), have noticed the benefits of scratchpads — these papers motivate our work.

As a technical detail, note that the shifted-position experiments are not identical to Liu et al. 2023(a). Our paper does not propose a new shifting scheme — it simple replicates the standard practice in large-scale LLMs of training on random intervals from an iid stream of examples, and using learnt positional encodings for the entire context (e.g. Karpathy, 2023; Brown et al., 2020). Nevertheless, we agree that there is a structural similarity, so we have added a note about this in Section 3, Footnote 5.

it’s not true that omitting positional encodings may lead to "arbitrary length" generalization, due to failures in both MLP and attention

Thank you for flagging this; we will clarify the statement in the paper. Note that the issue is subtle: there exist certain tasks where arbitrary-length generalization is provably possible, and such failures of MLP and attention do not manifest. For example, consider the simple Transformer that solves the boolean conjunction task in Appendix H. (The limitations of Hahn 2020 do not apply in our setting, since we allow weights to take values in the extended real line, as described in Footnote 3).

It would be better to include discussions on prior work that relate algorithmic reasoning tasks to formal languages.

We have added more discussion of such works in Appendix G, and we also have added a footnote about uniformity to Section 2 as suggested.

The paper studies length generalization, though it's unclear what is considered as successful length generalization in the paper.

Thank you for this question. In this paper, we consider successful length generalization to mean near perfect test EM on length that is at least 10 longer than the maximum training length, and we consider failures of length generalization to mean near 0 test performance on +10 length. We have added this clarification in a new figure (see Fig 1a) that summarizes the different tasks.

The specific choice of 10 is somewhat arbitrary. It reflects the level that all tasks which demonstrates non-trivial generalization can readily achieve without significant changes to model / data size and training strategy. Certain tasks such as count also exhibit significantly stronger length generalization than +10. However, it is also a reasonable proxy for capturing the differences between the set of tasks that are amenable to RASP-L solutions and the set that is not. Existing literature on length generalization reports many failure cases, including addition and parity, and in these cases performance starts to degrade as soon as the length goes out-of-distribution (see e.g. Nye et al Figure 3 and Anil et al). Being able to generalize perfectly for length of +10 or more suggests a qualitative difference from the failures cases reported in the literature. Nevertheless, how to predict the exact level of length generalization for a given task is still an open question.

Fig 3: How many test sequences are there for each trial?

The test data size is 5 * batch size for each task, which is typically 5 * 128 = 640 examples.

Fig 6(b): this is not really about length generalization, but more a failure of optimization?

Indeed, for parity without scratchpad we see the difficulty of optimization, which has also been noted in prior work (e.g. Chiang & Cholak and Bhattamishra et al). We focus on comparing parity with different scratchpads, based on how simple the scratchpads are according to RASP-L. We observe that the tasks with simpler RASP-L solutions also show faster optimization, which lends some support to the intuition that simple RASP-L programs are “easier-to-learn”.

Conclusion:

Thank you for taking the time to read our rebuttal. If our response addresses your concerns, we kindly ask that you consider raising your score. Otherwise, please let us know about your remaining concerns/questions so we can make further improvements.

Thank you for your time and effort in reviewing our paper! We would like to address the comments and questions you’ve raised, and we’d be very open to further discussion. We've updated the pdf and highlighted key changes in blue.

We first focus on clarifying our contribution, and its differences with prior work.

The paper proposes to use the difficulty of RASP-L programs as an indicator for length generalization performance. However, I'm not sure what this view can teach us. [...] I'm not sure whether these criteria provide new insights beyond findings in the existing literature.

We emphasize that our work focuses on the empirical learnability of tasks, rather than their theoretical representability. While there is a long line of work on the latter question (we have included more references in Appendix G), the former question is very much still open --- it is essentially about understanding the inductive bias of Transformers. Our work does not resolve this question, but we believe it takes an important and significant step forward.

To be concrete, we have added an explicit theoretical example (Appendix H) where our conjecture’s prediction differs significantly from prior work. We consider the popular “minimum-degree-interpolator” conjecture proposed by Abbe et al (ICML 2023 Outstanding Paper: https://openreview.net/forum?id=3dqwXb1te4). We give a simple theoretical setting (learning boolean conjunction) where our RASP-L conjecture correctly predicts successful length-generalization, but the min-degree conjecture does not. This simple example is emblematic of the value in our perspective.

Moreover, as we discuss in the Intro (paragraph 2), the prior literature did not have a consistent answer to whether Transformers length-generalize. Most works found that standard Transformers typically fail catastrophically on even mild length-generalization, e.g. Delétang et al. 2023, Abbe et al 2023, and Liu et al. 2023(a). However, it was also known that Transformers can sometimes length-generalize on particular tasks. Our contribution sheds light on which tasks: what is special about these length-generalizing tasks, that separates them from non-length-generalizing ones? We claim RASP-L representation is an empirically good heuristic for answering this question.

We hope these remarks help clarify the contribution of this work in the context of prior literature and address your concern regarding contribution. Please let us know if there are further concerns regarding this point.

It's unclear how to convert a task into RASP-L except for applying the definition directly, i.e. checking for whether certain criteria are satisfied. For example, two criteria provided in the paper are 1) whether the operation is non-causal and 2) whether precise index arithmetic is required. Hence one could also say that these criteria are indicative of length generalization performance, without resorting to the RASP-L language.

These two criteria you mentioned are implications of our RASP-L conjecture, but our conjecture is significantly stronger. To give a simple example, the Parity task satisfies the two criteria you mentioned, but cannot be written in RASP-L.

We acknowledge that “It's unclear how to convert a task into RASP-L” without actually trying to write the RASP-L program. This is however generally true of many computational complexity classes — for example, it's unclear whether how to determine if a task is in Polynomial time, without exhibiting a poly-time algorithm for the task. (Of course, certain well-studied complexity classes have structural features which help us determine membership. We do not yet have such a structural understanding of RASP-L, but we view the definition as an important first step). We have added a discussion of these limitations in Appendix H in the revised pdf.

It is well known that auto-regressive generation cannot uncover non-causal information.

We are unaware of a formalization of this claim in the literature. This claim has been made in informal/imprecise ways, but note that it is tricky to formally define what it means for a task to “require non-causal operations” without a model of computation such as RASP-L.

For example, prior works postulated that forward-order addition would not length-generalize because the naive algorithm, on a von Neumann computer, involves non-causal operations. However, Transformers empirically actually can length generalize on forward-addition, and we show there exists a RASP-L algorithm which solves this task. This algorithm is not the naive one; it is specific to the Transformer architecture (not the von Neumann architecture), and it is thus able to “work around” the causality restrictions by taking clever advantage of parallelism.

Thank you for the further discussions!

• Re Liu et al. 23(b): I agree that improving data diversity will likely help, which Liu et al. 23(b) also pointed out (their R4) as well as Jelassi et al. 23 ("priming"). Note though this might be considered as a "cheating" solution, since introducing more data reduces the OOD problem into an in-distribution problem.

• Chiang & Cholak 21's results are based on aggressive length generalization: I agree, and I think this again showcases the ambiguity in the definition of "length generalization". I hope this definition could be further highlighted in the paper since it will better clarify the implication/scope of the results; currently it seems that the only place that mentioned the "generalizing to 10 more length" is the caption of Figure 1 which I think is easy to miss.

• Re counterexamples: It would be great if the authors could include this comment in the limitation or the conclusion as well.

Given these changes, I'm happy to raise my score to lean on the side of acceptance. The main reason for my rating is that I think the paper provides an interesting concept, and I hope it could be better tested out and the paper should discuss the limitations and relations to prior work more carefully.