Let's Think Dot by Dot: Hidden Computation in Transformer Language Models

Summary

This paper proposes two experiments to show that transformers benefit from longer sequences to make implicit computations for tasks that require stepwise computations where intermediate results depend on previous results. The main experiment is the 3-sum problem, where models need to find if there exist three elements in the list that sum to 0 mod ten on all dimensions. The authors create a synthetic dataset that supervises this task with meaningful CoT sequences and filler non-meaningful sequences. Using a model trained on this data, the authors show that the model improves significantly with non-meaningful filler tokens compared to no filter tokens. They use this to suggest that models benefit from filler tokens to perform implicit computations for better reasoning.

Rating

6

Confidence

3

Ethics flag

1

Reasons to accept

The overall experiment is interesting and provides empirical evidence on whether intermediate, meaningful, or tokens can be beneficial for the models to perform implicit sequential computations.

Reasons to reject

I am not fully convinced by the main conclusions presented in this paper. 1. The authors claim to draw a conclusion between TC^0 complexity class and the need for filler tokens as intermediate computations. However, I do not see how the 3-sum and 2-sum-transform experiments are connected with this complexity class in general and why this conclusion can be generalized based on these two experiments. 2. The authors claim that models use filler tokens to perform more computation, but if I am not mistaken, this conclusion is directly suggested by how the experiment is set up, so I am not sure what point the authors are trying to make on top of it. With the filler tokens during the training stage, the model literally performs more computation based on the representation of the filler tokens and the positional embeddings; more computation usually equals more overfitting to the task and sometimes better performances. Especially given the actual CoT sequences in the training stage, the model may learn to generalize based on positional embeddings of how the actual computation should be, hence making the filler tokens not "non-meaningful" anymore. I suggest the authors remove the meaningful CoT tokens in training, freeze the filler word representations, and experiment with #layers v. fillers. 3. The authors argue that transformers do not produce human-like, faithful serial reasoning, as the experiments suggest. I think this claim is overall true, but the experiments cannot derive this logically. The proposed experiments show that the transformers CAN benefit from non-interpretable implicit computations, but they do not show that they CANNOT achieve the same performance with human-like reasoning. Overall, I do not understand the authors' main points, but I am happy to revise if they point out my misunderstandings.

Summary

This work studies how seemingly meaningless filler tokens can be used as a kind of zero-shot chain-of-thought to solve algorithmic problems. For example, it can empirically identify some classes of problems where filter tokens are useful.

Rating

4

Confidence

4

Ethics flag

1

Reasons to accept

1. This work addresses an interesting problem of how filler tokens can be used as a useful chain-of-thought method. 2. This work makes several interesting empirical observations on the filler tokens as CoT, as highlighted with bold text or titles in section 4.2-4.3.

Reasons to reject

My major impression toward this work is that although it tackles an interesting problem, it is still largely preliminary and requires more in-depth study to fully materialize its key idea. This submission could be acceptable to a relevant workshop but is still below the bar of a conference paper. 1. 3SUM and 2SUM are interesting problem but still preliminary. I believe more sets of problems should be explored to verify the effects of filler tokens as CoT. 2. Experiments should be improved to be more thorough in multiple dimensions. - More variants of 3SUM problems may be tested with different lengths, dimension, etc. - More baselines of CoT may need to be compared.

Questions to authors

Please refer to the Weakness above.

Summary

This paper discusses whether adding dummy tokens for LLMs can enhance their expressive power. The authors design two synthetic datasets for the evaluation. Results show that even if adding dummy tokens the circuit complexity class remains TC0, but extra power is indeed added.

Rating

7

Confidence

4

Ethics flag

1

Reasons to accept

1. This paper explores a very important problem, which provides insights into understanding how chain-of-thought (CoT) works for LLMs. 2. The synthetic tasks are well-designed. Results are quite interesting, and can support the proposed claim pretty well.

Reasons to reject

I’m afraid the gap between practical LLMs on real data and the toy model on synthetic data cannot be ignored. The pretraining corpus and pattern are quite simple and clean. However, in practice, the LLM is pretrained on massive data with various hidden structures. The analysis conclusions as well as hidden assumptions may not hold in practice. However, considering that it’s extremely difficult to implement analysis for real LLMs. I would still think this is a pretty good work.

Summary

This paper investigates the role of filler tokens in transformer language models, particularly in enhancing computational capabilities independently of meaningful chain-of-thought tokens. The authors show that transformers can solve complex algorithmic tasks using meaningless filler tokens, "......" in this work, and provide empirical and theoretical insights into the conditions where these tokens are beneficial. They build new synthetic datasets for nested quantifier resolution and training on LLAMA-34M from scratch. Compared with vanilla inference, it demonstrates that filler tokens can enable hidden computation and improve results, especially when scaling the length and dimension of 2 and 3Sum tasks.

Rating

6

Confidence

3

Ethics flag

1

Reasons to accept

1. The paper provides a unique perspective on how filler tokens, often considered meaningless, can enhance the computational capabilities of transformer models. 2. It combines theoretical characterizations with empirical evidence, offering a robust examination of the utility of filler tokens. 3. The findings have provided valuable insights for designing and interpreting chain-of-thought reasoning in large language models, potentially impacting future model training and evaluation strategies.

Reasons to reject

1. The authors note that learning to use filler tokens requires dense, task-specific supervision, which may not be practical or scalable in many contexts. 2. The experiments are conducted on relatively small transformer models, which may not fully capture the behavior and potential of larger, more advanced models 3. The naming of different methods is messy and needs to be unified (Filler, No filler, No Intermediate Tokens, CoT...), especially in Table 1.

Questions to authors

1. How do you anticipate the findings would scale with much larger pre-trained transformer models? 2. In Table 1, does chain-of-thought include both parallelizable and serial tokens, or only parallelizable tokens? 3. In Table 1, if the "No Intermediate Tokens" is the same as no-filler, refer to it as no-filler to avoid misunderstanding. 4. Section 4.3 is quite ambiguous; the authors should provide detailed experimental tables and prove their claims for a better explanation. 5. In the example “A05 B75 C22 D13 : AB 70 AC 27 AD 18 BC 97 BD 88 CD B ANS True”, shouldn't the "AB 70" be "AB 80"?

One More Question from AC

To the best of my knowledge, there are several **consistent theoretical investigations** regarding the expressiveness of Transformer models, including both encoder setting and autoregressive decoder setting: [1]. The parallelism tradeoff: Limitations of log-precision transformers [2]. Transformers learn shortcuts to automata [3]. Towards Revealing the Mystery Behind Chain of Thought: A Theoretical Perspective [4]. The Expressive Power of Transformers with Chain of Thought All these theoretical findings collectively contribute to understanding the representational capabilities and limitations of Transformers. They suggest that while a Transformer encoder may never surpass TC0 complexity, an autoregressive model equipped with Chain of Thought (CoT) exhibits significantly greater power. However, your empirical observations **appear to contradict** certain aspects of these theoretical assertions. Could you explain this problem? And what is your new insight in this direction compared to these already-known results? Thanks,

Thanks for the rebuttal

Thanks for providing the rebuttal. Let me clarify my first point: I understand that 3-sum and 2-sum are TC0 problems, but I do not understand how the conclusions derived from experiments on these two problems can be generalized to the TC0 class in general. The authors seem to be drawing too strong a conclusion based on limited empirical evidence, which I suggest the authors clarify in the final version. Let me clarify my second point: I suggested that the models only learn meaningful representations for the filler tokens because the training data contains meaningful tokens (CoTs), so the models can assign a meaningful representation based on actual CoT semantics through positional relations. For example, if the model sees both "the weather is good" and "the weather is .", the last dot could be semantically related to "weather." Could you please clarify if this could be the case? If this happens, the overall contribution will be less interesting because the model relies more on positional embeddings and performs CoT implicitly in the filler-token settings. I am happy with the last point and willing to change my score if the previous question can be answered.