Let’s Think Dot by Dot: Hidden computation in transformer language models

Thank you for engaging with our work!

#1, How 3SUM relates to TC0: TC0 can be equivalently defined as first-order logic with majority quantifiers. In Figure 3, we show how 3SUM can be naturally defined in first-order logic and is thus in TC0. Crucially, it also requires three quantifiers, which we propose as the key feature for a TC0 problem that transformers without filler would not be able to express. This is why we are interested in 3SUM. We will add some substantial additional discussion to clarify.

#2 “The authors claim that models use filler tokens to perform more computation, but … this conclusion is directly suggested by how the experiment is set up” To clarify what is and what is not immediate from the experimental setup, we emphasize that there are two separate questions addressed by our work:

(1) Theoretically/Expressivity: Do transformer weights exist which can use filler tokens to solve problems unsolvable via immediate answer? Yes as described above in #1.

(2) Empirically/Learning: when can a transformer learn via SGD to use filler tokens? Theory alone does not tell us whether this solution can be efficiently learned via SGD. This is where our experiments come in, showing empirically that filler tokens pose a hard learning problem (sec 4.3).

#3 We agree with you that “transformers CAN benefit from non-interpretable implicit computations, but they do not show that they CANNOT achieve the same performance with human-like reasoning.” We agree that CoT is generally useful for problems beyond TC0 whereas filler is only useful for a subset of TC0. This sentence from the intro reinforces your point:

“Whereas linear or polynomial chain of thought steps can add power … beyond TC0, transformers remain in TC0 with [filler tokens] … Filler tokens might extend the expressive power … within TC0.”

So the performance hierarchy is: immediate-answer < filler tokens << chain of thought

For 3SUM, in particular, we mention in section 4.2 that human-like CoT achieves perfect performance: “Models converge to 100% accuracy on chain-of-thought data as well, but we do not show this in figures for simplicity”. This is an important point, and so to improve clarity we will move this from footnote 9 to main-text.

Thank you for taking time to engage with our work. Our goal in this paper was to construct an empirical and theoretical existence proof demonstrating conditions under which filler tokens can be useful for transformer LMs. Past work has shown that, for general tasks, LMs fail to benefit from filler tokens. Our contribution is to show that, while filler tokens do not provide a universal computational benefit, they do help on specific algorithmic problems involving parallel search (specifically, first-order logic problems having quantifier depth >2). Our experiments with 3SUM confirm this theoretically motivated hypothesis on a specific instance of such a problem. Our experiments establish that, across data complexity, sequence length and control conditions, filler tokens provide performance improvements on algorithmic problems involving parallel search. This is a significant contribution since previous work had only ever shown LLMs failing to benefit from filler tokens (1), whereas our results establish a specific case where they can help.

Regarding further baselines, we note that our CoT setting achieves 100% accuracy, and so “More baselines of CoT” would not make a difference. Regarding running additional experiments varying 3SUM dimension. Indeed, we have run experiments up through 7 dimensional inputs and have found the results are qualitatively similar. We will include the extended figure in the final version.

“I believe more sets of problems should be explored to verify the effects of filler tokens as CoT"

In contrast to broad benchmarking work as in e.g. BigBench, we aim to focus on specific tasks where theory suggests filler tokens would be useful rather than exhaustively benchmarking LMs across many different, less motivated, tasks.

Thank you for your review! We're glad you found the experiments compelling. We agree that investigating filler tokens with large-scale LMs is an interesting question, although we see it as outside the scope of the current project which is focused on analyzing the benefit of filler tokens in a targeted setting where we expect them to be useful.

Thank you for the interest in our paper! Glad you found the experimental results and theoretical framing on filler tokens robust and valuable! To frame this discussion, our goal with this paper was to identify and explain conditions under which models can learn to use filler tokens, since previous work had only ever shown LLMs failing to use filler tokens (1,2).

To go through point-by-point:

• “learning to use filler tokens requires dense, task-specific supervision which may not be practical or scalable in many contexts.” Our paper aims to advance the science and understanding of LMs and it’s not a methods paper. We set out to identify criteria under which filler tokens can benefit model performance and this is one such criterion (filler requires dense, task-specific supervision). So, the fact that learning to use filler appears difficult is an insight provided by our work, and we do not see it as a drawback.
• On Table 1, the three settings are best described as “Filler tokens”, “Chain of thought” and “Immediate answer”. “Immediate answer” is synonymous with “no intermediate tokens” and “no filler tokens”, to make this point clear we will update to use “immediate answer” throughout.
• “AB70” is correct since (0,5)+(7,5)%10=(7,0).
• To clarify the serial CoT controls, we will include an additional appendix figure showing detailed results for sec 4.3.
• Regarding larger pre-trained transformers, we expect that out-of-place computation will/has emerged, but given our results around the difficulty of learning to use filler tokens such cross-token hidden computation appears less likely absent targeted training.

Thanks for your question! There is no contradiction between those past works and our work. In fact, our results are motivated by and build on the papers you mention, but we investigate filler tokens (blank tokens get added to the input) as opposed to traditional CoT addressed in prior work (where model-generated tokens get added to the input).

[1] shows that transformers, without CoT, can express at most the class TC0. With CoT, i.e. the transformer can generate tokens that get appended to the input, power extends beyond TC0 [3, 4]. As we discuss in Section 2, this is not the case for transformers with filler tokens, which remain in TC0 by the argument from [1]. Applied to filler tokens, [1] implies the following proposition:

Transformers with filler tokens remain in TC0. Proof sketch: For inputs of size n, a transformer can be simulated by a constant depth, poly(n) size threshold circuit (TC). So, if we add polynomial filler tokens, we can still simulate the transformer with a constant depth and poly(poly(n)) = poly(n) size circuit.

Thus, filler tokens will not increase expressive power as much as CoT.

Our argument is that there are likely functions in TC0 that transformers without filler tokens cannot express but which transformers can likely express with filler tokens. Namely, these functions are TC0 functions with >2 quantifier depth, such as 3SUM, which we consider in our experiments. Our experimental results that transformers with filler tokens can express this function are thus consistent with prior work and our hypothesis because a) 3SUM is in TC0 and b) it requires >2 quantifiers to express, so we expect filler tokens to be necessary to express it.

One of the high-level takeaways from this work is that CoT and filler tokens extend the power of transformers in different ways. CoT adds depth to the computation graph, allowing transformers to express functions outside TC0. On the other hand, filler tokens extend the width (or quantifier depth) of the computation graph, likely allowing larger parallel computation within TC0. We will make this clearer in revisions.

The empirical evidence we find complements theory in two ways (1) Our work empirically demonstrates functions in TC0 that transformers without filler tokens fail to learn, but which transformers can learn with filler tokens. These empirical results provide evidence of the above-mentioned hypothesis that there is a finer-grained expressivity distinction within TC0 between transformers with filler tokens and transformers without filler tokens. (2) Our work also complements the prior theoretical work you cite, as expressivity theory results alone do not tell us whether the theoretical transformer constructions used in expressivity proofs can also be efficiently learned via SGD—learnability is a stronger criterion than expressivity. Our experiments on 3SUM demonstrate that without our particular training data (additional, parallelizable CoT sequences) learning to use filler tokens poses an intractable learning problem, see sec 4.3.