Are Transformers Able to Reason by Connecting Separated Knowledge in Training Data?

Q2: Why does accuracy decrease with more than one few-shot prompt?

A for Q2: While it is typically expected that performance improves with more few-shot examples, it is not rare for performance to fluctuate or even decrease as additional examples are provided (see Figure 4b in [9] and Figures 7, 10 in [10]). Notably, Figure 2 in Agarwal et al. [12] demonstrates that the optimal number of shots for peak performance is often lower than the maximum number they can handle, indicating that performance does not always increase monotonically with the number of shots.

We argue that performance decreases when shots number > 1 because more CoT examples increase the dissimilarity between training and testing data. To explain this, we start by analyzing the difference between one-shot examples from the testing and training data. During testing, one-shot examples typically consist of the longest chains of length $N$. In contrast, one-shot examples during training comprise child chains of length $M < N$. As the number of shots increases, each shot introduces extra instances of these $N-M$ missing vertices, exacerbating the disparity between training and testing prompts. This growing difference makes it harder for the model to recognize testing data patterns, thus reducing performance. In our setup, a single shot during testing already provides ample information about the vertex order needed for generating correct answers. For a $k$-shot testing example, the additional $k-1$ shots do not add valuable information and only exacerbate the divergence between training and testing data. Consequently, we observe that testing performance peaks at 1-shot and diminishes thereafter.

We test the performance of Transformers in reasoning causal chains with varying test lengths in Appendix L [Lines 1613-1673]. The results (Figure 10 [Lines 1653-1673]) show that for tasks where test lengths are close to child chain lengths models are trained on, few-shot performance remains stable without decrease. As the gap between child chain and test lengths widens, the few-shot performance decrease becomes evident. Thus, we conclude that when differences between training and testing data are limited, the expected pattern of in-context learning appears, where performance improves with more shots and does not decline after reaching its peak. As the gap between testing causal chains and training child chains widens, the performance decrease after one shot becomes evident, indicating the influence brought by OOD tasks.

This non-monotonic pattern does not affect our conclusions and contributions, as the performance at the optimal number of shots already sufficiently reflects the compositional reasoning ability.

Q3: In contrast to our successful results, Zhang et al. [11] find that Transformers fail to uncover the underlying program to generalize to different testing data. What explains our different outcomes?

A for Q3: Possible reasons of this difference are as follows.

• CoT prompting: Zhang et al. utilize BERT models to directly generate answers for complex reasoning tasks. In contrast, we employ few-shot CoT prompting to facilitate step-by-step reasoning in GPT2-like Transformers, which has been shown to provably enhance model’s expressivity and generalization ability ([13], [14]). Without the help of few-shot CoT, Transformers also struggle in FTCT (poor zero-shot performance in Figure 2 (left) [Lines 289-308] )
• Statistical Features: Our FTCT dataset contains fewer "statistical features" compared to those in Zhang et al.'s datasets. As per Zhang et al., a statistical feature is a specific statistic of an example that strongly correlates with its label. The presence of numerous statistical features can lead models to learn these correlations rather than the true underlying program. Our dataset’s testing performance is segregated into vertices accuracy and values accuracy. Each vertex token relates solely to the same token in preceding few-shot examples, without obvious statistical features that correlate highly with it. It is the same for the values, which is only related with its corresponding vertices and its parent.

In the revised version, we discuss this work in the related works section [Lines 139-141].

We would like to emphasize that Transformers can not solve every FTCT task successfully. For those tasks with low relative knowledge ratio, Transformers also fail to generalize (Figure 2 (right) [Lines 289-308]). We observe a phase transition of the generalization ability as the relative knowledge ratio increases, indicating the key role played by data structure in eliciting models’ generalization ability.

• Other comprehension/clarity issues:
  • It is correct that addition and subtraction are the only possible operations. We clarify this in the revised version [Line 188].
  • We have illustrated the merge process with a concrete example for clarity [Lines 200-202]. Specifically, for the causal structure in Figure 1 [Lines 162-170], suppose the sampled child chain is [A, B] and the sampled noisy vertices are [Z, H]. We then merge [A, B] and [Z, H] in to a single sequence while preserving the relative order of [A, B]. Potential outcomes include [A, Z, H, B], [A, Z, B, H], and [H, A, B, Z], of which we select [A, Z, B, H]. If the parent vertex A is assigned a value of 100 and the edge [A, B] operation is “+1”, B’s value becomes 101. We randomly sample Z and H values as 3 and 1, resulting in the sequence [A, 100, Z, 3, B, 101, H, 1]. Please refer to Appendix B [Lines 784-798] for the formal merging process description.
  • We have changed the index of few-shot examples from $f$ to $k$, a more standard notation [Lines 208-214, 222-223, 230-243, 255-263 ...].
  • The terminology "downside processing" actually refers to "downstream processing", which denotes the final processing step aimed at adapting sequences into natural language-like sentences. We have updated this terminology [Lines 216-217].
• We also deleted the redundant construction details and add concrete examples in “Downstream processing” part [Lines 220-221].

Q1: Why do all Transformer models attain 1.0 values accuracy, even for small Transformers with low vertices accuracy?

A for Q1: We first clarify the definitions of vertices accuracy and values accuracy [Lines 262-267]:

• Vertices accuracy measures whether the model correctly outputs all vertices included in the label. For instance, with an input like “… C=?:… A=100, … B=101, … C=103 \n C=?: … A=102”, the model is deemed to have accurate vertices if it outputs sentences like “….B=b, …C=c”, regardless of the specific values of b and c.
• Values accuracy assesses whether the model correctly outputs the values of intermediate vertices, given correct reasoning paths. For values accuracy, if the input is “… A=100, … B=”, the model is considered accurate if it outputs “101” as the next token.

Because the values accuracy is tested by prompting models with the reasoning paths that already have accurate vertices, model with low vertices accuracy may still pertain high values accuracy.

Regarding why a one-layer Transformer achieves such performance:

• As mentioned in Section 4.3 [Lines 363-365], the limited vertices accuracy is attributed to the absence of induction heads in a one-layer Transformer. During testing, models need to use generalized in-context learning ability to retrieve and replicate vertices accurately. As discussed in Section 6.1 [Lines 480-503], induction heads are two heads of the Transformer in different layers that facilitate in-context learning. They are unlikely to exist in one-layer Transformers, thus resulting in poor vertices accuracy.
• The High Values Accuracy may be due to the ability of a single-layer attention mechanism to handle parent vertex retrieval and mapping memorization. The precise mechanism of it remains unclear to us and we intend to make further exploration in future research.

Thank you for the thorough reviewing and constructive advice! We address your concerns as follows.

W1: More prominent attribution should be given to the prior work Prystawski et al. [1].

A for W1: To clarify how Prystawski et al.'s work has influenced our research and to outline the fundamental differences between our studies, we have revised the original discussion of their work in the related works section [Lines 107-111].

• We clarify that our FTCT data construction is informed by their task's framework: “Our FTCT structure draws inspiration from their Bayesian networks” [Lines 107-108].
• We specify the structural differences, noting that we introduce additional elements and complicate the dependency: “additionally inserting contextual noise and complicating value relationships” [Line 108].
• Furthermore, we underscore the distinct differences in our research goals and contributions: “While they focus on locality structure's impact on CoT efficacy, we investigate how various training factors influence the emergence of compositional reasoning and conduct an in-depth analysis of the mechanisms within Transformer structures that elicit this capability.”[Lines 109-111].

W2: The generality of our conclusions made by training highly specific model structures on synthetic data is questionable. Analysis on more naturalistic reasoning benchmarks is needed.

A for W2: We would like to state that our main focus and contribution are not about investigating the performance of pre-trained models on natural language tasks. In fact, many empirical works have already demonstrated the symptom that well-pretrained language models do compositional reasoning on complex realistic tasks like question answering, mathematical reasoning and interdisciplinary generation ([2], [3], [4] [5]). They are shown to generate comprehensive content with elements unlikely to co-occur in training data. We aim to scientifically validate such ability within a clear environment and explore its underlying mechanism. To this end, it is necessary to conduct controlled and tunable experiments where reasoning paths in the test data neither appear in the training data nor are they encoded in the models' pre-existing weights. Compared with naturalistic tasks with intractable natural language corpus, we believe that a controllable synthetic task is more appropriate for our research purpose. Doing research on synthetic data is also an approach being widely used by previous interpretability studies ([6], [7], [8]).

To clarify the above argument, we attach a new version of the paper that includes following modifications:

• Refine the research purpose in the introduction: “This paper validates the potential of Transformers in doing compositional reasoning on synthetic dataset and investigates the inner mechanism eliciting such ability. ” [Lines 45-46].
• Pointing out that utilizing models trained on vast natural language is not proper for our research purpose [Lines 42-44].
• Reframe the statement about relative knowledge ratio within the scope of FTCT: “compositional reasoning emerges as the similarity between training and testing data increases. In FTCT, this is measured by the relative knowledge ratio” [Lines 69-70].
• Adjust the conclusion: “Our research validates the potential of Transformers in doing compositional reasoning on synthetic data and investigates the inner mechanism eliciting such ability. ”[Lines 527-528].

Admittedly, conducting comprehensive scientific interpretability studies on large language models trained on complex natural corpora is meaningful. However, such endeavors remain challenging amidst current research advancements. We hope our research makes a contribution to this ultimate goal.

W3: Too many technical details in the Section 3 makes it hard to get the core idea. Problems of Figure 1. Other comprehension/clarity issues in Section 3.

A for W3:

• Issues with Figure 1:
  • A self-explanatory caption has been added in the newly submitted revised version [Lines 176-183].
  • To prevent the distraction caused by blue highlight, in the revised version we distinguish knowledge points and noisy nodes with gray and blue only at the beginning of the “Fragmented at Training” stage and remove all subsequent highlights to avoid confusion [Lines 163-166].

I thank the authors for their detailed response to the issues raised by myself and the other reviewers. I also appreciated the effort that the authors took to taxonomize and label their responses, which made it easy to follow.

I believe that the authors' responses meaningfully addressed all 3 weaknesses I raised (W1-W3) as well as all questions (Q1-Q3). I especially appreciated the tailored responses to the questions -- these were very helpful and clarifying.

At this point I think the decision around acceptance of this work mainly hinges on generality (W2). I tend to agree with Reviewer EQsG that the burden of proof for this work is higher than for analogous work highlighting shortcomings:

Generally, using a simple and singular synthetic dataset is suitable for highlighting the shortcomings of the Transformer architecture. However, since the paper concludes that Transformers possess this capability, the experiments on this task alone are not sufficient to support such a conclusion.

In response, the authors argue that performing more comprehensive experiments would be "valuable" but "challenging amidst current research advancements." I sympathize with the view that asking for more systematic benchmarking of LLMs is one of the easiest things to request from a reviewer standpoint, and one of the most burdensome things to implement from an author standpoint. Moreover, I appreciate that the authors (in response to the reviews) added new benchmarks with GPT-2 small and large. This is sufficient for me.

In response to the authors rebuttals, I have updated the following scores in my review:

• Presentation: 1 → 2
• Overall Rating: 5 → 6

Thank you for your thoughtful and insightful review of our rebuttals, and for your kind adjustments to our scores. These mean a lot to us!

We appreciate the concerns regarding the sufficiency of synthetic data in demonstrating the positive results of Transformers’ capability. It’s noteworthy that while some analogous studies ([1], [2], [3]) focus on demonstrating Transformers' shortcomings with synthetic data, others ([4], [5], [6]) effectively utilize simple yet targeted synthetic data to explore the potential of Transformers and analyze their mechanisms. For instance, Zhou et al. ([4]) investigate factors influencing Transformers' length generalization through experiments on the addition of two integers. The controlled and structured nature of synthetic data indeed enhances the precision and scientific rigor of such investigations, aligning well with our research focus.

To further elucidate the generality of our work, we kindly wish to clarify that empirical works ([7], [8], [9], [10]) have shown the symptom indicating that real LLMs possess the compositional reasoning ability. An example is GPT-4's ability to "write a supporting letter for Electron as a US presidential candidate” ([10]), illustrating a strange combination of fields unlikely to co-occur during training. However, scientific validation and a detailed mechanistic understanding of this ability have been limited by the intractability of natural data. We believe that our experiments and analysis using controlled synthetic data contribute to this understanding. (This research approach parallels methods used in physics. For instance, to investigate the phenomenon of ball lightning observed in nature, physicists have replicated spherical luminous balls through artificial laboratory experiments ([11], [12]), thereby confirming its potential formation and providing explanations through theoretical models.)

Thank you once more for engaging in this meaningful discussion and offering valuable opinions!

[1] Sanford, Clayton, Daniel J. Hsu, and Matus Telgarsky. "Representational strengths and limitations of transformers." Advances in Neural Information Processing Systems 36 (2024).

[2] Abbe, Emmanuel, et al. "Generalization on the unseen, logic reasoning and degree curriculum." Journal of Machine Learning Research 25.331 (2024): 1-58.

[3] Zhang, Honghua, et al. "On the paradox of learning to reason from data." arXiv preprint arXiv:2205.11502 (2022).

[4] Zhou, Yongchao, et al. "Transformers can achieve length generalization but not robustly." arXiv preprint arXiv:2402.09371 (2024).

[5] Bietti, Alberto, et al. "Birth of a transformer: A memory viewpoint." Advances in Neural Information Processing Systems 36 (2024).

[6] Wang, Zixuan, et al. "Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot." arXiv preprint arXiv:2406.06893 (2024).

[7] Press, Ofir, et al. "Measuring and narrowing the compositionality gap in language models." arXiv preprint arXiv:2210.03350 (2022).

[8] Zhou, Denny, et al. "Least-to-most prompting enables complex reasoning in large language models." arXiv preprint arXiv:2205.10625 (2022).

[9] Khot, Tushar, et al. "Decomposed prompting: A modular approach for solving complex tasks." arXiv preprint arXiv:2210.02406 (2022).

[10] Bubeck, Sébastien, et al. "Sparks of artificial general intelligence: Early experiments with gpt-4." arXiv preprint arXiv:2303.12712 (2023).

[11] Paiva, Gerson Silva, et al. "Production of ball-lightning-like luminous balls by electrical discharges in silicon." Physical review letters 98.4 (2007): 048501.

[12] Wu, H-C. "Relativistic-microwave theory of ball lightning." Scientific reports 6.1 (2016): 28263.

Q1: Will the model be able to chain together the values of non-adjacent vertices during testing time?

A for Q1: We've included testing performance for reasoning with incomplete intermediate steps with non-adjacent vertices (reasoning about AC) in the Appendix M [Lines 1722-1744]. The testing results reveal that Transformers trained on FTCT are unable to effectively chain together the values of non-adjacent vertices during testing. This limitation is likely due to a bias in the training dataset, where adjacent vertices invariably appear consecutively in the training sequences. Nevertheless, as elaborated in our response to W3, this limitation does not affect the main conclusions presented in this paper.

Q2: Is there a typo in Figure 1?

A for Q2: There is a typo in Figure 1, and the values of “C”s should be 108 and 105 respectively. We have submitted a correct figure in the revised version [Lines 170-173].

Q3: Are there more than one set of causal chains? It seems that there is only one sequence of length $n$.

A for Q3: Indeed, there is only one set of causal chains, and all different chains with various vertices and lengths are encompassed within this set. As defined in Section 3.1 [Line 187], the set of chains $\mathcal{T}(\mathcal{G})$ includes all sequences of connected vertices. The index $n$ can be any natural number as long as that $[v_1, ..., v_n]$ are connected by edges. For the causal structure shown in Figure 1 [Lines 162-174], $\mathcal{T}(\mathcal{G})$ includes sequences [A, B], [B, C], [A, D], [D, E], [A, B, C], and [A, D, E].

Q4: Why are the noise vertices inserted in a predictable manner?

A for Q4: We interpret "predictable manner" to mean that within a few-shot example, the noise vertices retain the same letters in the same positions across shots. This design is intended to evoke the model's generalized in-context learning ability by encouraging it to replicate the same vertices from prior examples, thereby ensuring high vertex accuracy during testing. While the appearance of noise vertices is predictable, it does not diminish the significance of the observed emergence of compositional reasoning.

Q5: Why is a relative knowledge ratio of 0.3 the threshold of the emergence of compositional reasoning? Could it be that 0.3 is when the probability that there is at least one occurrence for every $(v_i, v_{i+1})$ in the train set reaches close to 1?

A for Q5: Our analysis shows that occurrence probability is not the determining factor for the 0.3 threshold. For every tuple of adjacent vertices and their values $(v_i, q_i, v_{i+1}, `op`(v_i, v_{i+1})\circ q_i)$, we count the number of times that it has been visited in our training data. Results indicate that every tuple is encountered at least 46 times, across tasks with varying knowledge ratios. The large volume of our training data ensures that, even with a low relative knowledge ratio, the probability of each $(v_i, q_i, v_{i+1}, `op`(v_i, v_{i+1}) \circ q_i)$ appearing in the training data is nearly 1. Detailed experiments results are available in the Appendix I [Lines 1452-1500] of the revised paper.

What we can confirm so far is that a higher relative knowledge ratio aligns few-shot CoT prompts more closely with training data, thereby enhancing testing performance. Understanding the precise mechanism behind this specific threshold remains a future research direction.

Q6: Why is there a drop in performance when the relative knowledge ratio reaches 0.25?

A for Q6: The relative knowledge ratio of 0.25 is associated with a training configuration where the graph depth is 8 and the child chain length is 2. Testing curves in Figure 2 (left) [Lines 289-308] and Figure 3 [Lines 1358-1376] show that every training task with a child chain length of 2 performs poorly. That is the reason why the performance drop abruptly at 0.25.

Our empirical findings in Figure 2 (right) [Lines 289-308] indicate a strong correlation between compositional reasoning ability and the relative knowledge ratio; however, this does not imply that compositional reasoning ability increases monotonically with the relative knowledge ratio. Indeed, if we set the relative knowledge ratio to $(M/N)^\alpha$, where $\alpha$ is a tunable parameter, an $\alpha$ can be found that results in an apparently monotonic curve.

Thank you for the thorough and detailed review! Especially for the novel angle in adding extra experiment and careful reading of technical details. We address your concerns as follows.

W1: The clarity of the paper is lacking, especially the notation and writing. There is a typo in Figure 1. Concrete examples are needed to improve readers’ understanding

A for W1: As for the clarity and concrete example, we do the following modification to make the paper more clear and readable:

• Notations in Section 3:
  • In Step 1.1 "Fragmented at Training", we provide a concrete example of the training sequence [A, 100, Z, 3, B, 101, H, 1], where [A, B] is the child chain from the causal structure with values following the ``+1" operation, and [Z, H] are noise with randomly assigned values [Lines 200-202].
  • In Step 3 "Downstream Processing", extraneous notation details have been removed. A concrete example is used to clarify the processed sentence: "H=?: ... A=110, ... Z=1, ... B=111, ... H=5 \n H=?: ... A=102, ... Z=4, ... B=103, ... H=9" [Lines 218-221]. An example of the sentence with complete context information is like “H=?: ARCH Rewards patentsA=102, Pad Influ interfZ=4, google correl latexB=103, treasureFrankH=9”. Such concrete examples are shown in the Appendix C in the revised version [Lines 832-896].
• Notations in Section 5:
  • We replaced the abstract notations $o^{`cm`}$ and $o^{`eq`}$ with the actual symbols, using a comma “,” and an equals sign “=” [Lines 393-394, Lines 396-397].
• Notations in Section 6.1:
  • Similarly, we revised notations $o^{`cm`}$ and $o^{`eq`}$ to their respective symbols “,” and “=”. We also emphasized comma tokens at different positions by enclosing them in boxes and using various colors for improved clarity [Lines 490-491].

There is a typo in Figure 1. We believe that this corresponds to your second question “where B=106 and B=103, should it be C=108 and C=105, respectively?”. The answer is yes. The “C=109” and “C=106” at the lower right corner of Figure 1 should be changed to “C=108” and “C=105” according to the relationship q(C)=q(B)+2 defined by the causal structure. We sincerely appreciate your attention to detail in identifying this typo. A corrected version has now been uploaded [Lines 170-173].

W2: The formal definition of the compositional reasoning should be explicitly written out.

A for W2: We add such formal definition explicitly in the introduction section of the revised version [Lines 34-37]. Specifically, we define the compositional reasoning as “the skill to integrate discrete pieces of knowledge from multiple sources to form a coherent reasoning, even in the absence of explicit examples connecting these pieces during learning.”

W3: Lack of the testing performance of reasoning with incomplete intermediate reasoning steps (reasoning about AC).

A for W3: Our interpretation of "reasoning about AC" refers to reasoning when not all vertices in the reasoning paths are adjacent in the causal structure—essentially the ability to reason with incomplete intermediate steps.

It is true that "reasoning about AC" is an aspect of compositional reasoning. However, our research focus, which is validating compositional reasoning ability and doing mechanism analysis , does not necessarily require testing such performance. A model is deemed to possess compositional reasoning ability as long as it can correctly determine the value of the last vertex in an OOD testing sentence, regardless of how that value is generated. In this study, we choose to elicit Transformers’ compositional reasoning ability by training them for complete step-by-step reasoning, which does not inherently ensure proficiency in handling incomplete intermediate steps. To avoid potential misunderstandings, we have revised the abstract example to: “For example, if someone learns ( B = f(A) ) from one source and ( C = g(B) ) from another, they can deduce the value of ( C ) by reasoning ( C=g(B)=g(f(A)) ) even without encountering ( ABC ) together” [Lines 13-16].

Additionally, we have included an experiment on reasoning with incomplete intermediate steps (reasoning about AC) in Appendix M [Lines 1722-1744]. The results in Figure 11 [Lines 1782-1835] indicate that Transformers trained on FTCT exhibit limited proficiency when reasoning with any level of incompleteness. This limitation likely stems from a bias in the training dataset, where adjacent vertices consistently appear consecutively in the sequences.

Thank you for your explanation and updates to the paper! I lean towards accepting this paper and maintain my score.

Thank you for your thorough review and valuable opinions! We address your concerns as follows.

W1: More diverse, comprehensive and complex real-world tasks are needed to draw the conclusion that Transformers possess the compositional reasoning ability.

A for W1: As for the need of real world tasks, we would like to clarify that our main focus and contribution are not about proving the ability of real pre-trained language models on natural language settings. In fact, many empirical works have already demonstrated the symptom that well-pretrained language models do compositional reasoning on complex realistic tasks like question answering, mathematical reasoning and interdisciplinary generation ([1], [2], [3] [4]). They are shown to generate comprehensive content with elements unlikely to co-occur in training data. We aim to scientifically validate such ability within a clear environment and explore its underlying mechanism. To this end, it is necessary to conduct controlled and tunable experiments where reasoning paths in the test data neither appear in the training data nor are they encoded in the models' pre-existing weights. Compared with realistic tasks with intractable natural language corpus, we believe that a controllable synthetic task is more appropriate for our research purpose. Doing research on synthetic data is also an approach being widely used in previous interpretability studies ([5], [6], [7]).

As for the diversity and comprehensiveness, we argue that the experiments on FTCT is enough for the potential validation and mechanism investigation research purposes. Nonetheless, we acknowledge that incorporating more diverse and comprehensive tasks will enhance the generalizability and impact of our work, which we aim to pursue in future research.

To clarify the above argument, we attach a new version of the paper that includes following modifications:

• Refine the research purpose in the introduction: “This paper validates the potential of Transformers in doing compositional reasoning on synthetic dataset and investigates the inner mechanism eliciting such ability. ” [Lines 45-46].
• Pointing out that utilizing models trained on vast natural language is not proper for our research purpose: “However, the complexity and ambiguity of their natural language training and testing data make it hard to scientifically validate the compositional reasoning ability and explore the underlying mechanisms.” [Lines 42-44].
• Reframe the statement about relative knowledge ratio within the scope of FTCT: “compositional reasoning emerges as the similarity between training and testing data increases. In FTCT, this is measured by the relative knowledge ratio” [Lines 69-70].
• Adjust the conclusion: “Our research validates the potential of Transformers in doing compositional reasoning on synthetic data and investigates the inner mechanism eliciting such ability. ”[Lines 527-528].

W2: More explanation about the motivation and innovation behind our task is needed to demonstrate the novelty and contribution of the FTCT dataset compared with existing tasks.

A for W2: We rewrite the “Compositional generalization” part in related works section in the new submitted version [Lines 124-141], in which we clarify the motivation and innovation of our FTCT tasks compared with existing works. The main logic of the new version is as follows.

• Firstly, a series of works has showcased the potential of Transformers in compositional tasks where the answers are directly output without intermediate reasoning steps ([8], [9], [10], [11], [12]). In contrast, our FTCT dataset with deep causal structure allows exploration of explicit reasoning's impact on compositional generalization ability.
• Further, empirical studies show that step-by-step reasoning enhances large language models' compositional abilities on real-world tasks like question answering and mathematical reasoning ([1], [2], [3]). However, the complexity of natural language corpora used by them complicates scientific validation compared to our synthetic data.
• Recent studies have explored Transformers' generalized reasoning on controllable synthetic tasks ([13], [6], [14]). In contrast, our FTCT task not only ensures controlled experimentation but also introduces measures of training-testing data similarity and establishes a distinct parent-child causal relationship, facilitating analysis of the mechanisms underlying Transformers' compositional abilities concerning data distribution and model structure.

We believe that the above modifications will better demonstrate the novelty and contribution of our FTCT learning task.

Thank you once again for your careful review and constructive questions, which are valuable to us!

Thank you for the thoughtful review and the valuable feedback! We address your concerns as follows.

W1: It is questionable that to what extent the conclusions made by training randomly initialized transformers on synthetic data can be extended to real pre-trained language models.

A for W1: We would like to clarify that our primary focus and contribution are not about investigating the performance of real pre-trained language models. As a matter of fact, many empirical works have already demonstrated that real pre-trained language models exhibit symptoms of compositional reasoning by generating comprehensive content with elements unlikely to co-occur in training data ([1], [2], [3], [4]). We aim to scientifically validate such ability within a clear environment and explore its underlying mechanism. To this end, it is necessary to conduct controlled and tunable experiments where reasoning paths in the test data neither appear in the training data nor are they encoded in the models' pre-existing weights. Compared with investigating real pre-trained LLMs that have learned intractable corpus, we believe that training randomly initialized Transformers on synthetic data is an appropriate method for our research purpose. Doing research on synthetic data is also an approach being widely used in previous interpretability studies ([5], [6], [7]).

To clarify the above points, we attach a new version of the paper that includes following modifications:

• Refine the research purpose in the introduction: “This paper validates the potential of Transformers in doing compositional reasoning on synthetic dataset and investigates the inner mechanism eliciting such ability. ” [Lines 45-46].
• Pointing out that utilizing models trained on vast natural language is not proper for our research purpose: “However, the complexity and ambiguity of their natural language training and testing data make it hard to scientifically validate the compositional reasoning ability and explore the underlying mechanisms.” [Lines 42-44].
• Reframe the statement about relative knowledge ratio within the scope of FTCT: “compositional reasoning emerges as the similarity between training and testing data increases. In FTCT, this is measured by the relative knowledge ratio” [Lines 69-70].
• Adjust the conclusion: “Our research validates the potential of Transformers in doing compositional reasoning on synthetic data and investigates the inner mechanism eliciting such ability. ”[Lines 527-528].

We acknowledge that conducting comprehensive scientific interpretability studies on large language models trained on complex natural corpora is indeed valuable. However, such endeavors remain challenging amidst current research advancements. We hope our research contributes meaningfully towards achieving this ultimate goal.

W2: Complicated notations make the paper difficult to follow.

A for W2: To simplify the notations and make the paper easier to follow, we have made the following changes:

• Notations in Section 3:
  • In Step 1.1 "Fragmented at Training", we provide a detailed example of the training sequence [A, 100, Z, 3, B, 101, H, 1] along with its generation process [Lines 201-202].
  • In Step 3 "Downstream Processing", extraneous notation details have been removed. A concrete example is used to clarify the processed sentence: "H=?: ... A=110, ... Z=1, ... B=111, ... H=5 \n H=?: ... A=102, ... Z=4, ... B=103, ... H=9" [Lines 218-221].
• Notations in Section 5:
  • We replaced the abstract notations $o^`cm`$ and $o^`eq`$ with the actual symbols, using a comma “,” and an equals sign “=” [Lines 393-394, Lines 396-397].
• Notations in Section 6.1:
  • Similarly, we revised notations $o^`cm`$ and $o^`eq`$ to their respective symbols “,” and “=”. We also emphasized comma tokens at different positions by enclosing them in boxes and using various colors for improved clarity [Lines 490-491].

Q1.1: Why in $D_{train}$ we need to add noisy tokens?

A for Q1.1: Noisy tokens are added to simulate the dependencies found in natural language corpora, where related tokens often do not appear consecutively and are interrupted by unrelated tokens. This requires Transformers to extract meaningful information from a noisy context.

Q1.2: Why in $D_{test}$ we do not add noisy tokens?

A for Q1.2: Prompts in $D_{test}$ are designed without noisy tokens to reflect the typical scenario in which users pose questions to language models, where the given prompts are usually of higher quality and contain less noise.

We include the testing results where testing examples are blurred by noise in the same way as the training data are processed. These results, shown in Appendix H.2 [Lines 1401-1451], display the same overall pattern as tests without noisy tokens, indicating the robustness of our conclusions.

Thank you for your constructive opinions and for increasing your confidence score. We are glad to hear that many of your concerns have been addressed by our responses.

The simplifications and refinements we mentioned in response to W2 have been incorporated into the revised version of our paper, corresponding to the lines noted in our response. Additionally, our answer to Q1 can be found in Appendix H.2 [Lines 1401-1451].

We would like to further explain the generality of our work (W1). Empirical studies ([1], [2], [3], [4]) indicate that real LLMs exhibit compositional reasoning abilities. For example, GPT-4 can "write a supporting letter for Electron as a US presidential candidate” ([4]), which logically combines fields not likely to co-occur during training. However, scientific validation and a detailed mechanistic understanding of this capability are limited by the complexity of natural data LLMs are trained on. We believe our experiments and analysis using synthetic data contribute to this understanding. (Same approach has been used in physics research such as the investigation of ball lightning. Physicists have replicated spherical luminous balls through artificial laboratory experiments ([5], [6]), thereby confirming its potential formation and providing explanations through hypothetical models.)

Notably, many studies ([7], [8], [9], [10]) have utilized Transformers trained on synthetic data from scratch to explore their potential and analyze their mechanisms. For instance, Zhou et al. ([7]) investigate factors influencing Transformers' length generalization by training them to predict the addition of two integers. The controlled and structured nature of synthetic data, along with the unbiasedness of randomly initialized models, enhances the precision and scientific rigor of such investigations, aligning well with our research objectives.

Thank you once again for your valuable opinions and insightful discussion—they mean a great deal to us.

[1] Press, Ofir, et al. "Measuring and narrowing the compositionality gap in language models." arXiv preprint arXiv:2210.03350 (2022).

[2] Zhou, Denny, et al. "Least-to-most prompting enables complex reasoning in large language models." arXiv preprint arXiv:2205.10625 (2022).

[3] Khot, Tushar, et al. "Decomposed prompting: A modular approach for solving complex tasks." arXiv preprint arXiv:2210.02406 (2022).

[4] Bubeck, Sébastien, et al. "Sparks of artificial general intelligence: Early experiments with gpt-4." arXiv preprint arXiv:2303.12712 (2023).

[5] Paiva, Gerson Silva, et al. "Production of ball-lightning-like luminous balls by electrical discharges in silicon." Physical review letters 98.4 (2007): 048501.

[6] Wu, H-C. "Relativistic-microwave theory of ball lightning." Scientific reports 6.1 (2016): 28263.

[7] Zhou, Yongchao, et al. "Transformers can achieve length generalization but not robustly." arXiv preprint arXiv:2402.09371 (2024).

[8] Bietti, Alberto, et al. "Birth of a transformer: A memory viewpoint." Advances in Neural Information Processing Systems 36 (2024).

[9] Wang, Zixuan, et al. "Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot." arXiv preprint arXiv:2406.06893 (2024).

[10] Allen-Zhu, Zeyuan, and Yuanzhi Li. "Physics of language models: Part 1, context-free grammar." arXiv preprint arXiv:2305.13673 (2023).

We summarize the main modifications made in the revised version.

Clarifications of the Research Purpose and Contribution

• Refine the research purpose in the introduction: “This paper validates the potential of Transformers in doing compositional reasoning on synthetic dataset and investigates the inner mechanism eliciting such ability. ” [Lines 45-46].
• Pointing out that utilizing models trained on vast natural language is not proper for our research purpose: “However, the complexity and ambiguity of their natural language training and testing data make it hard to scientifically validate the compositional reasoning ability and explore the underlying mechanisms.” [Lines 42-44].
• Reframe the statement about relative knowledge ratio within the scope of FTCT: “compositional reasoning emerges as the similarity between training and testing data increases. In FTCT, this is measured by the relative knowledge ratio” [Lines 69-70].
• Change the title of section 4.2: “The Similarity between Training and Testing Data Determines the Emergence of Compositional Reasoning” [Lines 310-312].
• Adjust the conclusion: “Our research validates the potential of Transformers in doing compositional reasoning on synthetic data and investigates the inner mechanism eliciting such ability. ”[Lines 527-528].

Notification Simplification and Presentation Improvement

• Notations in Section 3:
  • In Step 1.1 "Fragmented at Training", we provide a detailed example of the training sequence [A, 100, Z, 3, B, 101, H, 1] along with its generation process [Lines 201-202].
  • In Step 2 “Few-shot learning”, the index for few-shot examples has been changed from (f) to (k), a more standard notation indicating shot numbers [Lins 208-213].
  • In Step 3, we change the "downside processing" in the original version to "downstream processing" which is a more conventional terminology [Lines 216].
  • In Step 3 "Downstream Processing", extraneous notation details have been removed. A concrete example is used to clarify the processed sentence: "H=?: ... A=110, ... Z=1, ... B=111, ... H=5 \n H=?: ... A=102, ... Z=4, ... B=103, ... H=9" [Lines 218-221].
• Notations in Section 5:
  • We replaced the abstract notations (o^\cm) and (o^\eq) with the actual symbols, using a comma “,” and an equals sign “=” [Lines 393-394, Lines 396-397].
• Notations in Section 6.1:
  • Similarly, we revised notations (o^\cm) and (o^\eq) to their respective symbols “,” and “=”. We also emphasized comma tokens at different positions by enclosing them in boxes and using various colors for improved clarity [Lines 490-491].
• The demonstration of Figure 1:
  • The values of “C”s at the lower right corner of Figure 1 have been changed to 108 and 105 respectively [Lines 170-173] .
  • A self-explanatory caption of Figure 1 has been added in the newly submitted revised version [Lines 176-183].
  • We distinguish knowledge points and noisy nodes with gray and blue only at the beginning of the “Fragmented at Training” stage and remove all subsequent highlights to avoid confusion [Lines 163-166].
• Other improvements
  • We add the formal definition of composition reasoning in the introduction [Lines 34-37].
  • We change the description of the ABC example in the abstract to indicate our focus on step-by-step reasoning skills [Lines 13-16].

More thorough and clear discussions in related works

• In the “Step-by-step reasoning” part (formerly titled “Chain-of-Thought Prompting”), we have expanded on how Prystawski et al.'s work has informed our research and delineated the fundamental differences between our studies [Lines 107-111].
• In the “Compositional generalization” part, we have clarified the motivation and innovations of our FTCT tasks compared to existing works, focusing on step-by-step reasoning, data complexity, and the unique structure that facilitates detailed mechanism analysis [Lines 124-141].

Relaxation of Evaluation Criteria for Compositional Reasoning Ability

In the revised version, we have adjusted the whole chain accuracy standard to assess if the model's output includes all vertices and values in the correct order [Lines 255-258]. Compared to the original version that requires vertices and values to be presented consecutively, this revised approach considers additional valid reasoning paths that are disturbed by noise. We have updated the testing results using these revised criteria in the new version (Figure 2 [Lines 289-302] and Figure 3 [Lines 1358-1376]). The overall pattern remains consistent with the original version which does not affect our conclusions or contributions.