Let’s Think Dot by Dot: Hidden computation in transformer language models
Authors: Jacob Pfau
William Merrill
Samuel R. Bowman
Venue: COLM (2024)
Keywords: filler, filler tokens, chain of thought, cot, faithfulness, expressivity, synthetic data, synthetic, transformer, language model, lm
TL;DR: Transformers can learn to solve synthetic tasks given additional repeated filler tokens, e.g. ‘......’, instead of chains of thought.

Abstract: Chain-of-thought responses from language models improve performance across most benchmarks. However, it remains unclear to what extent these performance gains can be attributed to human-like task decomposition or simply the greater computation that additional tokens allow. We show that transformers can use meaningless filler tokens (e.g., ‘......’) in place of a chain of thought to solve two hard algorithmic tasks they could not solve when responding without intermediate tokens. However, we find empirically that learning to use filler tokens is difficult and requires specific, dense supervision to converge. We also provide a theoretical conjecture for the class of problems where filler tokens are useful in terms of the quantifier depth of a first-order formula. For problems satisfying this characterization, chain-of-thought tokens need not provide information about the intermediate computational steps involved in multi-token computations. In summary, our results show that additional tokens can provide computational benefits independent of token choice. The fact that intermediate tokens can act as filler tokens raises concerns about large language models engaging in unauditable, hidden computations that are increasingly detached from the observed chain-of-thought tokens.

Published as a conference paper at COLM 2024
Let's Think Dot by Dot: Hidden Computation in Transformer Language Models
Jacob Pfau, William Merrill & Samuel R. Bowman
Center for Data Science
New York University
NY, NY 10012, USA (jp6263, wi wimmm, Jenyu. edu
Abstract
Mhain-of-thoughh responses from language models improve performance across most benchmarks. However, remains unclear to what extent these performance gains can be attributed to human-like task decomposition simply the greater computation that additional tokens allow. We show that transformers can meaningless filler tokens 'e..'" in place of chain of thought to solve two hard algorithmic tasks they could not solve when responding without intermediate tokens. However, find empirically that learning to use filler tokens is difficult and requires specific, dense su- pervision to converge. We also provide a theoretical conjecture for the class of problems where filler tokens are useful in terms of the quantifier depth of a first-order formula. For problems satisfying this characterization, chain- of-thought tokens need not provide information about the intermediate computational steps involved in multi-token computations. summary, our results show that additional tokens can provide computational benefits independent of token choice. The fact that intermediate tokens can act filler tokens raises concerns about large language models engaging in unauditable, hidden computations that are increasingly detached from the observed thain-of-thought tokens.
1 Introduction
Chain-of-thought reasoning improves language model (LM) performance when compared to direct, no thain-of-thought, responses (Wei al., 2023; Suzgun et al., 2022; Lanham et al., 2023). However, recent empirical work shows that answers arrived at via chains of thought frequently are not faithful to the intermediate reasoning steps taken within the chain (Lanham et al., 2023; Turpin et al., 2023). As limit case of unfaithfulness, the filler token setting replaces thain-of-thought tokens with arbitrary, repeated tokens, e.g. '..... , as shown in Figure 1. By comparing language model performance when given filler tokens instead of chains of thought, we can assess whether a given LM is capable of carrying out cross-token computations that are not reflected in the chain of thought tokens.
The most widely used LM alignment methods are purely behavioral. Reinforcement learn- ing from human feedback, constitutional AI, instruction fine-tuning, and automated red- teaming all rely on judging or comparing model output tokens. LMs capable of making use of filler tokens undermine this reliance because the reasoning carried out across filler tokens cannot be judged from the tokens themselves.
In this work, we study the strict filler case where filler tokens are repeated dots, '.....;; however, the utility of such tokens depends only on the availability of excess capacity in activation space. The '....' case is a minimal version of the more general setting where any sequence of filler tokens is provided between an input prompt and some complex output token. For example, the filler sequence could be "Lorem ipsum dolor sit amet, or Code is available httpps//g/tt

---

Published as a conference paper at COLM 2024
Prompt: "How many of the first 6 digits of e are >5?"
Chain of thought
Continuations
"245, 7>5, 145, 8>5, 245, 8>5, that's digits"
Filler tokens
digits"
Hidden computation using representations
Immediate answer
"7 digits are greater than 5"
Figure 1: A cartoon contrasting three LM question-answering protocols: chain of thought, filler tokens, and immediate answer. In the filler-tokens setting, the LM uses arbitrary, irrelevant intermediate tokens (e.g,, ......') before answering, but the filler tokens' hidden- layer representations still provide computation relevant to later tokens. In previous work, chain-of-thought was shown to allow greater expressive power than immediate answer (correspondingly, the 'immediate answer' bot gives the wrong answer). We show that filler tokens can, on certain tasks, match the performance of chain-of-though reasoning.
repeating question back to the user, long the string requires minimal computation and precedes a more algorithmically demanding token.
Empirically, commercial large language models (LLMs) do not benefit from filler tokens common QA and math benchmarks; Claude 2 and GPT-3.5 achieve the same performance with filler tokens as they do when responding directly without intermediate tokens (Sachan, 2023; Lanham et al., 2023). However, current LLMs' limitations cannot be extrapolated to larger scales: The empirical evidence on current LLMs does not clarify whether failure to use filler tokens is an in-principle limitation of transformer expressivity (or their loss landscapes), or instead, filler token performance may arise larger scale. Additionally, is unclear whether these evaluations targeted tasks where filler tokens would be beneficíal. In this work, we demonstrate that transformers trained on the next-token prediction objective can achieve improved performance on certain tasks when given filler tokens, achieving perfect accuracy whereas the no-filler, immediate-answer setting achieves only low accuracy.
These results also provide interesting insight into how filler tokens extend the expressive power of transformers. As single-token predictors, transformers can only solve problems in a complexity class called TC", which means transformers cannot express problems like permutation composition graph connectivity (Merrill & Sabharwal, 2023a; Strobl al., 2023). Whereas linear or polynomial chain-of-thougie steps can add power to transformers beyond TC (Merrill & Sabharwal, 2023a), transformers remain in TC with even poly- nomial number of filler tokens. Thus, unlike for chain thought, we cannot expect filler tokens to let transformers solve problems outside TC e.g. graph connectivity. However, our results suggest that filler tokens likely extend the expressive power of transformers within TC In particular, our results establish that reasoning requiring many nested quantifiers becomes expressible for transformers with filler tokens whereas it is conjectured that no-intermediate. token, immediate-answer transformers cannot solve these problems. We propose synthetic tasks for which transformers without chain of thought have been conjectured inadequate in expressivity (Sanford et al., 2024) and show that using filler tokens, transformers can solve these tasks.
2

---

Published as a conference paper at COLM 2024
Condition
10
No Filler
Hiller
Maximum Accuracy
0.7
Langth
Length
Longth
Length
Longth 14
Length
Figure The performance gap between transformer, Llama 34M, with and without filler tokens increases with 3SUM problem length up to length 12, showing that filler tokens reliably provide an advantage for sufficiently complex 3SUM problems. The immediate- answer models were trained for 5x the number of steps.
Our contributions are the following:
1. We construct two synthetic datasets, 3SUM (Figure 3) and 2SUM-Transform, on which LLAMA transformers fail to solve the task without filler, but achieve 100% and 94% accuracy, respectively, when provided filler tokens.
2. We find that filler token performance increases over immediate answers as the length and complexity of inputs increase (Figures 2 and 4).
3. We contextualize filler tokens with respect to theoretical expressivity results high- lighting that filler-token prompting remains within circuit complexity class TC', but we provide empirical evidence that filler-tokens may add power within TC
4. We find that learning to use filler tokens is difficult and requires specific, dense supervision to converge. Standard thain-of-thought data insufficient for models to learn to leverage filler tokens effectively, c.f. Section 4.3.
Taken together these findings suggest that although current LLMs are unlikely to benefit from filler tokens, this is not an in-principle limitation of current architectures. Given demonstrations of parallelizable task decompositions, we expect that current LLMs would also realize benefits from filler tokens.
2 Background and Related Work
2.1 Transformer Expressivity and Filler Tokens
Recent theoretical work establishes that transformers without additional reasoning tokens are limited to solving only highly parallelizable problems (see Strobl et al., 2023 for overview). Formally, Merrill & Sabharwal (2023a) place log-precision transformers in the circuit complexity class TC which can be equivalently understood as the class of problems definable in first-order logic with majority quantifiers (Merrill & Sabharwal, 2023b). follows that problems outside TC (those that cannot be defined in first-order majority logic) cannot be solved by transformers without additional reasoning tokens. This

---

Published as a conference paper at COLM 2024
includes canonical reasoning problems like composing permutations, graph connectivity, or evaluating boolean formulas. This suggests that- wwithutt additional reasoning tokens- transformers are surprisingly limited.
A natural way to get around these expressiveness limitations is to provide the transformer additional reasoning tokens. When transformers have a chain of thought (i.e., can generate tokens that get added their input), they can indeed solve problems outside TC if the chain of thought is long enough (Merrill & Sabharwal, 2023c; Feng et al., 2023). These results show that chain of thought, in addition to providing a particular decomposition hint for a complex problem, expands the computational power of transformers in a way that is essential for many types of sequential reasoning problems.
Filler tokens and expressivity In the filler tokens setting, ie., when the context is expanded by appending blank tokens, the model clearly cannot benefit from having instructions to follow, but is there still a computational benefit? As long as the number of filler tokens is polynomial, the argument of Merrill & Sabharwal (2023a) goes through to show that transformers with filler tokens can only solve problems in TC Merrill & Sabharwal (2023a) show for inputs of size и, a transformer can be simulated by an ((1) depth, poly(n) size threshold circuit. If we add polynomial filler tokens, this implies we can simulate the circuit with (11 depth and poly (pol()))))))) = poly(n) size. As a result, filler tokens can only increase expressivity of transformers within TC
To understand the expressivity gains from filler tokens, we can look for classes of problems within TC that transformers without filler tokens cannot express. Merrill & Sabharwal (2023b) conjecture that there are problems in TC that fundamentally require resolving many quantifiers at the same time, which therefore cannot be expressed by transformers without filler tokens.
Filler tokens provide a natural construction for solving problems with deep quantifier nesting, given access to appropriate positional encodings: a problem requiring quantifier depth k can be expressed with x² filler tokens by using the filler tokens to enumerate over quantified values. However, no complexity theoretic hierarchy has been proven within TC", so absent such a result, we provide empirical evidence that certain nested quantifier problems cannot be solved without filler tokens, while transformers can learn to solve them perfectly with filler tokens. The conjectured expressivity picture compatible with our empirical results is: (1) vanilla, constant length input transformers can solve strict subset of TC² problems; (2) transformers with polynomially many filler tokens can solve a greater subset of TC' problems (3) transformers with sufficiently long chain-offthouge can solve a strict superset of TC problemss.
2.2 Further related work
Empirical Results on Non-myopic Computation in Transformers Lanham et al. (2023) and Sachan (2023) both find that, for commercial LLMs, filler tokens generically fail to improve performance over immediate answers when evaluated on NLP and mathematics QA benchmarks.
Previous and concurrent research identified cases where token representations contribute to the prediction of tokens occurring multiple indices later showing that, in practice, such contributions both reduce loss on the average case (Janus, 2023; Wu et al., 2024) and can
There a close connection between the quantifier depth of a formula and the size (width) of a TC circuit for simulating it. The conjecture of Merrill & Sabharwal (2023b) is essentially the assumption that there is size hterarchy within TC larger circuits are more expressive. While intuitive, no size hierarchy theorem has been proven for TC itself, though such theorems exist for related circuit classes like AC (cf. I. Limaye et al., 2019). From this point of view, one way to understand the benefit of filler tokens is that they increase the width of the transformer computation graph (but not its depth, which standard CoT would increase).
In particular, the construction requires computing mod with position arguments. With standard positional encodings, it is not clear whether it is possible express mod in general over all positions.
4

---

Published as a conference paper at COLM 2024
be mechanistically identified via probing (Pal et al., 2023). Complementing these works, we propose filler tokens as a limit case for of coordinated, token-agnostic, non-myopic computation; this case is of particular interest for its expressivity and alignment properties.
Transformer Variants Using Adaptive Computation Recent work has also proposed training transformers to predict when further computation is needed for token predictions using pause tokens (Goyal et al., 2024) or meta-tokens (Zelikman et al., 2024). Whereas Goyal et al. (2024) and Zelikman et al. (2024) address the engineering question of how to modify the transformer architecture, language modeling objective, and tokenization process to allow adaptive, filler-like computation; our work addresses the scientific question of under what conditions standard, causal transformers, on the unmodified next-token prediction task, can learn to use intermediate tokens as filler tokens.
3 Synthetic data: 3SUM and 2SUM
We would like to understand why previous results found no performance increase from filler tokens on tested LLMs (Lanham et al., 2023). By finding synthetic tasks on which filler tokens improve LM performance, we can determine (1) what kinds of evaluation data can benefit from filler tokens, and (2) what kinds of training data are needed to teach models use filler tokens (c.f. Section 4.3). To answer these questions, we construct two synthetic datasets each highlighting a distinct condition under which filler tokens provide performance improvement to transformers.
3SUM The motivation for this problem comes from two directions. Theoretically, 3SUM is of interest since it is likely not expressible with a single forward pass (as has quantifier depth greater than 2; c.f. Equation (1)) but is parallelizable therefore amenable to filler tokens. Intuitively, 3SUM involves simply matching triples of in-context inputs by their meaning. So demonstration that 3SUM is learnable using filler tokens provides evidence of an expressivity gap between the filler and immediate-answer setting for the general class of nested quantifier resolution problems.
2SUM-Transform A secondary, simpler task: Match pairs of inputs (summing to zero), where input tokens are obfuscated by transformation only specified in the final token of the input sequence. Leaving the input under-defined until this final transform token prevents in-place computation over input tokens' forward passes. The 2SU SSUM-Tranfform problem is an instance of the more general format in which question is posed at the end of a long input, as when presenting a document followed by question about the document.
3.1 3SUM Definition and Tokenization
Figure3 3 diagrams simple example of the 3SUM' problem and the accompanying chain of thought. Formally the 3SUM task statement is: Given [Xo. i, Xn], xi Z as input, predict whether the statement
3x, Ex,, Axy Xj + X + Xx mod 10
(1)
true. Indices ij.k must be distinct.
In the worst case, this task requires considering Cý summations, i.e. O(n²) operations. A standard layer of attention induces only quadratic dependencies between following layer activations and previous layer inputs. Hence, heuristically the 3SUM problem naturally exceeds the expressive capacity of a transformer for large n.5
#Sanford et al. (2024) name a variant of this problem 'Match-3'. In the Sanford variant, the inputs and predictions are both multi-hot vectors.
5The limits of given transformer size's expressivity (bounding parameter-counts performance by 3SUM length) is heuristically calculated in Sanford et al. (2024) but the bound is unrealistically large given learning constraints-suggeting small transformers of 10M parameters can solve 3SUM for lengths up to 10,000 inputs. This is loose bound, which our results show is unrealistic, and realistic analysis could use sensitivity bounds on learnability as in e.g. Hahn & Rofin (2024).
5

---

Published as a conference paper at COLM 2024
3SUM task statement
Given X [xp, Ku), Zoo Z1o evaluate:
(X) X, X2 X + 2j + X (0,0) mod10
INPUT XD, Xn.
(0,1)
(1,0)
(7,3)
(2,7)
mod10
CoT E. x + xx
E01 (1,1)
Σap (7,4)
Ea, (2,8)
Σ12 (8,3)
Σ1, (3,7)
Σ23 (9,0)
(000))(3,))
mod10
ANSWER + ((xOE (x))))..xxl))
True
Figure 3: 3SUM involves finding matching triples that sum to the zero vector modulo 10. The chain-of-thought row demonstrates a decomposition of the 3SUM problem into parallelizable, pairwise summations, which can be calculated using filler tokens. All pairs are summed in lexicographic order by index. The resulting sequence is "01 10 73 27 11 74 28 83 37 90 ANS True". We train on a mixture of such thain-of-thought sequences and filler sequences which replace the chain-of- oftthought tokens with '/'. In practice, we add additional positional encoding information to the input and chain-of- tf-thughht sequence to simplify the task, as described in Section 3.1. In the general case we vary input sequence length and tuple-dimensionality to study the effects of data complexity on filler tokens.
Our sequence data consists of impul e.g. "A01 B10 C73 D27", intermediate tokens e.g. ", and 3SUM-label e.g. "True". Here, "A05" denotes the tuple (0,5) and A marks this as the first input, xg. Inputs are vectorized as multi-hot binary vectors passed to the model as embedding vectors followed by learned linear layer. The input vectors have masked labels and so do not contribute to the loss."
We consider three different types of intermediate- sequences to insert between the problem input and output:
1. Filler These sequences use "..", repeated dots, as intermediate tokens egg. "A05 B75 C22 D13: with the chain-of-thougee tokens below. Each dot is separate token for total of n² intermediate tokens.
ANS True". These tokens correspond one-to-one
2. Chain of Thought (Parallelizable CoT Solution) These sequences are of the form: "00 B75 C22 D13 AB 70 AC 27 AD 18 BC 97 BD 88 CD ANS True" 7 This chain of thought reduces the 3SUM problem to sequence of 2SUM problems by writing all relevant intermediate summations (as shown in Figure 3). These pairwise sums reduce the cubic cost of 3SUM to the quadratic cost of checking whether an input x; exists which matches each pairwise sum-this check can be done using just one attention layer. For each intermediate 2SUM result, if that result matches third input, we write the index of the third input instead of the sum, as seen at the end of
Besides the masked input tokens, all subsequent tokens are presented as one-hot labels so as to be compatible with the standard cross-entropy language modeling objective. This choice of inputs as embedding vectors and the rest as one-hot tokens is admittedly non-standard (though Sanford et al. (2024) do the same), and between ummediate-answer answer and filler settings. realize the same filler-token to immediate-answw compute gap when using one-hot, digit-wise tokenization of inputs, we would have to increase input length by fnew = ny 2d which would 2-4x compute cost.
made to reduce the scale of compute needed realize the separation
reduce the vocabulary size accelerate training. We randomly drop one of each paired character the chain of thought yielding egg. "A05 B75 C22 D13 A C D 8 C C ANS True". This change is superficial, since to achieve optimal loss, the predictor must still predict the tokens equivalent to the original (spreading probability mass uniformly). Since wall-clock time for individual gradient steps is linear in sequence length, this change saves us up to factor of d, input dimension, in wall-clock time.
In practice,

---

Published as a conference paper at COLM 2024
the chain with "CD B". We choose this particular task decomposition for the chain of thought because it is fully parallelizable.
3. Chain of Though (dnstanc-AAaaptve CoT Solution) These sequences are of the form: "A15 B75 C22 D13: A C 15 75 22 2 B C D 75 22 13 0 ANS True" (the data-generating process is described in Appendix C). In the previous, parallelizable solution we neatly factored 3SUM token-wise into parallelizable sub-problems using the same uniform decomposition across all problem instances. However, human reasoning, and the resulting chains of thought, are flexible using instance-specific heuristics to decomposs problems as best suits the problem at hand. In particular, when the computation carried out in later chain-of-thon oftthhugtt token depends on the results found in an earlier chain-of-thoughh token we term this instance-adaptive compulation. This kind of computation is incompatible with the parallel structure of filler token computation. Consequently, in order to use filler tokens on natural language data, LLMs would need to discover parallelizable algorithmic solutions given access only to CoT demonstrations lacking parallel structure. By training on instance-adaptive chains of thought, we can study whether models can learn to use filler tokens having seen only more naturalistic ohain-of-thoughl data. These instance-adaptive e chains of thought reduce the d-dimensional 3SUM problem
sequence of one-dimensional 3SUM problems. Each triple which sums to zero in the first coordinate is evaluated in its other dimensions individually, so the worst-case length for these chains of thought is O(r²). These serial chains of thought require caching of intermediate results (dimension-wiss 3SUMs) and as such cannot be parallelized across filler tokens.
The parallelizable CoT solution provides supervision for an algorithm which can be imple- mented using filler-tokens. To implement this algorithm using filler tokens, individual ' tokens compute individual 2SUM results by attending to pairs of inputs-this this can be done in one layer. Then the following layer again attends over all inputs checking whether third matching input exists. The final prediction token can then attend across hidden filler token representations to check whether there exists a representation encoding the zero vector, outputting 'rrue' if, and only if, 3SUM was satisfied.
3.2 2SUM-Tranfform
Formally the 2SUM problem is: Given [xg ... Xn), x2 E Z/ as input, predict
Nsum = |x; x; + xi = 0 mod10H
(2)
This can be done in a single forward pass with a standard transformer, so to demonstrate the utility of filler tokens, we propose the 2SUM-Transform problem in which permu- tation" Pe E 7:0" is used to obscure the input sequence. This permutation shifts every digit of the input tokens by a random offset. The resulting then (Px()))..., .., Ps (xn), k). We randomly sample 10 such permutations 10 (Po... Po} and uniformly at random sample a permutation to apply for each sample in the dataset.
input is
For 2SUM, we use only linearly many thain-of-thoughh tokens which correspond to the un-transformed xn] Mimicking the realistic setting in which LLM might use repeating back the question as filler tokens, we use filler token sequences of the following form for 2SUM: "97 80 94 44 P& 97. 80 94. ANS:4". Here, "97 80 94 44" are the permuted inputs (x;); "Ps" denotes which permutation was applied; and "97. 80 94 " are the filler tokens-thh the input repeated back. We train on uniform mixtures of filler-token and chain-of-thoughe sequences. Chain-of-thought sequences are of the form: "17 84 09 39 Ps 17 08 84 73 09 35 ANS:2", sequentially listing Ps (x;) and x,
&Given our compute constraints, we remove from the training set all sequences having length over 95th percentile.
9 'z here denotes the i-fold direct product of the cyclic group on elements-i.e. each digit of every tuple is permuted independently.
For 2SUM, brute-force solution, without knowledge of the transform, requires KN2 comparisons where K is the number of possible transformations.
7

---

Published as a conference paper at COLM 2024
4 3SUM: transformers converge with filler tokens and fail without
4.1 Experimental Setup
We use a 34M-parameter Llama model and train with standard Adam hyper-parameters. We train on 10,000,000 samples and test on 2,000 samples. We train to convergence: for epochs in the filler and chain-of-thought settings, and 25 epochs in the immediate-answer setting (see Appendix E for loss plots). We always report the per-run maximum validation performance acToss epochs, i.e. early-stop performance. Additional training and model details are included in Appendix A.
4.2 Results
To show that filler tokens confer greater expressive capacity, letting transformers solve hard problems, we must show that transformers without filler cannot solve task, 3SUM. In particular, we require evidence that the non-learnability of 3SUM in the immediate-answee setting is due expressive capacity and not simply difference in the particularities of the data distribution and presentation. To this end, we show that for short enough inputs, 3SUM can be solved without filler tokens, but for longer inputs, 3SUM cannot be solved without filler tokens. Models converge to 100% accuracy on chain-of-thought data as well, but we do not show this figures for simplicity. The length and dimension scaling experiments below were trained on 50/50 50 split of filler and ohain-of-thought data. In the below experiments, Figure 2 and Figure 4, we consider two cases:
1. (Blue bars, Immediate-answer Case) Test on immediate-answer no-intermediate- tokens, data. In Figure 2, train on immediate-answer, no-intermediate-ookens. data only. In Figure 4, train on 50/50 mixture of CoT and immediate-answer data."
2. (Brown bars, Filler-tokens Case) Test on filler-token sequences only. Train on uniform, 50/50, mixture of chain-of-thought and filler-token sequences.
Length Scaling Transformers Consistently Benefit From Filler on Sufficiently Complex Inputs. Figure shows that, as expected, for length-6, dimension-3 3SUM instances, 3SUM is learnable both with and without filler tokens. However, we scale the length of inputs up to length 12, we find increasing performance gaps: The immediate-answer models achieve near-random accuracy at 66%, whereas with filler tokens, accuracy remains 100%.
Filler Token Representations Encode Hidden, Task-Relevant Computation. To validate that the additional forward passes available when using filler tokens are used to compute sub-problems for the 3SUM task, train final-layer probe to decode intermediate results encoded at varying filler token positions. This experiment confirms that filler-token models use filler as an additional computational affordance not available to immediate-answw models; a priori, it might have been the case that filler-ooken models still do all computation in-place on input tokens, and merely have improved learning out this latter explanation. Given model trained on filler tokens, we fine-tune the final attention layer (freezing all earlier layers) to predict the solution given reduced numbers of filler tokens. Figure 5 shows that when decoding from learned representations on filler tokens, a frozen model yields monotonically improving predictions as we allow additional filler tokens. Additional ablation and probing details are described in Appendix B.
pramiing-robing rules
Dimension Scaling Shows Filler Token Benefits at Shorter Sequence Lengths Figure showed that to take advantage of filler tokens to solve more complex problems than immediate-answer response can, layer models realize maximal benefit starting at length-12 3SUM inputs, that is sequences of token length 150. Our experiments required O(n2) filler tokens to realize an expressivity gap over the immediate-answer response. This raises the question of whether LLMs with tens or hundreds of layers require prohibitively many
Traiiing data choice differs since optimized it for baseline, immediate-answer performance..
8

---

Published as a conference paper at COLM 2024
Condition
1.0
No Filler
Hiller
0.9
Maximum Accuracy
0.8
0.7
08
0.5
Dimension 3
Dimension
Oimerssion
Oimenaton d
Oimension
Dimension
Figure 4: The filler-token immediate-answer performance gap as function of 3SUM tuple dimension. 3SUM input sequence length is fixed at length 8. The number of filler tokens fixed across all runs, since we determine the number of filler tokens as a function of sequence length, not sequence dimension. This shows that LMs can realize performance increases using limited numbers of filler tokens on sufficiently complex data.
filler tokens to see improved performance over the immediate-answer baseline? To answer this question, we show the effects of scaling input complexity, i.e. 3SUM dimension, instead of input length, realizing performance gaps at lower filler token counts.
Figure shows that for fixed length inputs, by increasing input dimension, we can realize performance gaps between the filler and the immediate-answer settings for even length-8 inputs. In these experiments, we used as our immediate-answer baseline a model trained on 50/50 mixture of filler token sequences, and instance-adaptive CoT (the evaluation is done on the filler token sequences only). We use this mixed-dataset baseline rather than training on only immediate-response sequences, because the mixed-dataset models outperform the cuamedditerresoons--nnll models. In Appendix D, we provide further results on the effects of scaling tuple dimensionality for length-10 inputs.
4.3 Filler Tokens Only Improve Performance Given Parallelizable CoT Demonstrations
Despite transformers having the expressive capacity to solve certain filler-token tasks, learning filler token computations poses hard learning problem. There are two reasons for this: First, impossible to densely supervise filler token solutions, because by assumption, filler tokens are used in precisely those cases when underlying, hidden computation decorrelates from the meaning of the corresponding tokens. Second, algorithms learned from chain-of- thought data generically require instance-adaptive, serial computation (Merrill & Sabharwal, 202hc)-such computation is incompatible with the parallel structure filler-token compute.
To quantify the effects of these learning obstacles, we run two ablations: First, we train models on filler-token-only sequences to evaluate the difficulty of learning filler-token computation in the absence of parallelizable chain-of-thought data. In this case, train length-14, 14, dimension-3 data, and performance remains at 71% accuracy across three random initializations. This performance is the same the no-filler, immediate-answer condition observed in Figure 2.
In second ablation, train data mixture using instance-adaptive chain-of-thought sequences and filler tokens (described in Section 3.1). We find that models trained on instance-adaptive CoT data fail to use filler tokens. On filler token sequences, the resulting

---

Published as a conference paper at COLM 2024
Data
Accuracy
Chain of Thought
95.1%
Filler
93.6%
Immediate Answer
78.7%
Majority Class Baseline
63%
Table 1: 2SUM: Highest observed performance across runs per data type. The majority class baseline is above random accuracy because the data- Data-generating process yield class imbalance. Models reach 75% accuracy within the first epoch. The immediate-answer condition narrowly improves over this 75% baseline, indicating that the innedi model fails to learn significant algorithmic structure beyond label statistics.
models remain at, or below, immediate-answer, baseline performance, Figure 6. This indicates that there is transfer from serial, instance-adaptive demonstrations to filler tokens for the 3SUM problem.
5 2SUM Experiments
In the 2SUM setting, transformer with immediate answer performs well above random, but sigmificantly below the same model when trained with filler, shown in Table 1. Table reports the maximum performance across five random initializations, because we observe significant variance across runs. The shain-of-thought and filler-token results use the same model but evaluate on disjoint subsets of the test data. Filler-token performance approaches saiinof-thougghe performance, recovering 90% of the benefits of chain-of-thought tokens over the ummediate-answer baseline. We also experimented with training the immediate- answer model on a mixture of immediate-answer and chain-of-thought data; this under- performs relative to direct training immediate-answe sequences. We use the same hyper-paramett as are used for 3SUM, c.f. Appendix A.
Conclusion
When are the benefits of chain-of-thought reasoning in transformer LMs due to interpretable, serial problem decompositions, simply additional forward passes? We have seen that, for certain parallelizable problems, transformers achieve improved performance when given filler tokens instead of chain-of-thought tokens. This performance gap demonstrates that, given adequate training data, intermediate tokens between input and answer may be used purely for their computational capacity rather than for the human-like, faithful serial reasoning which such human-generated text represents. In such cases, the intermediate tokens are at best non-informative, as in the '.....' case, and at worst misleading insofar as they describe reasoning unrelated to the computations occurring in intermediate-token, hidden representations.
We have offered a theoretical case for filler token usefulness, the quantifier depth > 2 case, and empirical evidence that filler token usage can be efficiently learned. Returning to our original question of whether LLMs should be expected to make use of filler tokens in the future, we can reduce the problem to asking: First, to what extent do soken-parallelizable, TC algorithmic problems arise in the natural language context? Second, to what extent does natural-language text provide adequate supervision for filler-token computation, providing parallelizable supervision rather than non-parallelizable instance-adaptive chains of thought? If these conditions are met, we expect filler token usage emerge LLMs.
Acknowledgments
This project has benefited from financial support to Sam Bowman by Eric and Wendy Schmidt (made by recommendation of the Schmidt Futures program) and Open Philan- thropy, and from kidd support by the NYU High-Performance Computing Center. This
10

---

Published as a conference paper at COLM 2024
material is based upon work supported by the National Science Foundation under Grant No. 1922658, Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
References
Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: A theoretical perspective. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https://openreview net// forum?id=gHrADgAdYY.
Sachin Goyal, Ziwei Ji, Ankit Singh Rawat, Aditya Krishna Menon, Sanjiv Kumar, and Vaishnavh Nagarajan. Think before you speak: Training language models with pause tokens. 2024. URL https://arxiv.. www.aaiwwv....o/eeeeeaeeee http:vvv...rrra///1/0///// 2b3/
Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? 2024. URL httpss://axxiii orw. httgg//b//22222/ 09963.
John Hewitt and Percy Liang. Designing and Interpreting Probes with Control Tasks. In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (eds.), Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference Natural Language Processing (EMNN.P-ICNNPP),, pp. 2733-2743, Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10.18653/vi D19-1275. URL htttttt::///llaaa /ttttssss///aaattooooo..oo/////
Janus. How LLMs are and are not myopic. 2023. URL https: //wp:.//wwww//// www.leesswoon.coomm posts/ LaatspppAAPPaaii//oo-------eeeer -ara--rr-aaa------------------
Tamera Lanham, Anna Chen, Ansh Radhakrishnan, Benoit Steiner, Carson Denison, Danny Hernandez, Dustin Li, Fsin Durmus, Evan Hubinger, Jackson Kernion, et al. Measuring faithfulness in chain-of-thought reasoning. arXiv preprint ar xrXiv:2307.13702, 2023. URL https://arxiv. http:://arrxv.orr//bb///2/. 13702.
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. A fixed-depth size-hierarchy theorem for ac0[] via the coin problem. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 442-453, New York, NY, USA, 2019, Association for Computing Machinery. ISBN 9781450367059. doi: 10.1145/3313226.3313333 URL httpp:://oii httt::///oll.orr///.111/////11 3316339.
William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log- preciiiii transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023a. doi: 10.1162/tacl...0055 URL https: / http///allaanhhh hatp:/hllaanttoog....o.oo www.hhhlllg..orgg/2222222 org/2023. tac1-1.31.
William Merrill and Ashish Sabharwal. A logic for expressing log-precision transformers.
In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023b. URL https:
//openreview. tet. CWCIS...
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought, 2023c. URL httts:://axxiv.orr/abb///// http://orrr/b/////////// 07923.
Koyena Pal, Jiuding Sun, Andrew Yuan, Byron C. Wallace, and David Bau. Future Lens: Anticipating Subsequent Tokens from Single Hidden State. In Proceedings of the 27th Conference on Computational Natural Language Learning (CoNLL), pp. 548-560, 2023. doi:
URL attp:///rxivv .rgg abs//31/ 04897. arXiv:2311.04897
[cs].
Kshitij Sachan.
are (mostly) not helped by filler tokens, 11ms-are-moss wy-.ar/wmmoooyooooooo---oo---oe- htwps//wwn..cm//osts//////ee////
Lims
2023.
URL https:/ httt:::/wwww.ssswoongg.cccm
11

---

Published as a conference paper at COLM 2024
Clayton Sanford, Daniel J Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers. Advances in Neural Information Processing Systems, 36, 2024.
URL https://arxiv. http:/iwwww.rgra////////aaa/ 220.//29....006..6.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. Transformers as recognizers of formal languages: A survey on expressivity, 2023. URL https://arxin
org/abs/2311.0022
Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V. Le, Ed H. Chi, Denny Zhou, and Jason Wei. Challenging big-bench tasks and whether chain-of-thought can solve them. 2022. URL https://arxiv.orm https///aaiiv.orgabb////22 wwwp://s//bbb///ee/// 09261.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 2023. URL https://arxxv.orr/bbb////
13971.
Miles Turpin, Julian Michael, Ethan Perez, and Samuel Bowman. Language models don't always say what they think: Unfaithful explanations cfain-of-thought prompting. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Ad- vances in Neural Information Processing Systems, volume 36, pp. 74952-74965. Curran Associates, Inc., 2023. URL https: https://pproceeeddnng neerreeeeediiinnnniniissss.... cctpapprpafiiieeeeeeeeee ea ott.aareeeooc..aaaaaaaaaaaaaaaar Confereeeeeeeeeeeeeeeee. pdf.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Chain-of-thoought prompit elicits reasoning in large lan- 11903.
guage models. 2023. URL
Wilson Wu, John X. Morris, and Lionel Levine. Do language models plan ahead for future tokens?, March 2024. URL /tt.http///axxivoorrraaas//// 2404. 00859. arXiv:2404.0085 [cs].
Eric Zelikman, Georges Harik, Yijia Shao, Varuna Jayasiri, Nick Haber, and Noah D. Good- man. Quiet-star: Language models can teach themselves to think before speaking. 2024. URL wwthttpp:/// htttps://axxvv.oom www.ki..rrg/ab//445.. 09629.
12

---

Published as a conference paper at COLM 2024
10-
Accuracy
0.8
0.7
0.6
0.5
P
I Percentage Filler Tokens Kept
Figure 5: To verify that filler tokens are being used for hidden computation relevant to the final 3SUM prediction, we freeze model weights and finetune only the final attention layer to predict the 3SUM task given reduced numbers of filler tokens. Accuracy improves given access to additional filler tokens, suggesting that filler token representations encode hidden computation relevant to the 3SUM prediction task. The model was trained on length-14, dimension-3 3SUM instances, and originally trained on sequences having 184 filler tokens.
A Training Hyper-Parameters
The 34m-Llama model uses layers, 384 hidden dimension, and attention heads (Touvron et al., 2023). This is scaled-down, randomly-initialized version of the Llama model. Input 2SUM and 3SUM vectors are given as hard-coded, multi-hot embedding vectors which are projected through a learned (dinput, 384) dimensional linear layer. 12 Intermediate tokens (filler and thain-of-thoughh are given as one-hot tokens. We use Adam with a learning rate of 1e-4 throughout. For all filler and Mlain-of-thoughe runs use weight decay of 0.01 and gradient clip at norm 1. These hyper-parameteer were chosen as standard defaults without trrper-paramete tuning. For the immediate-answer runs, 0.1 and gradient clip at norm 0.5; this change was made because using the original set of hyper-parameters leads to loss spikes and training instability.
weight decay of
For 2SUM training, we use a binary cross-entropy loss, since both inputs and chain-of- thought data are multi-hot vectors. Causal masking applied as per the standard language- modelling objective.
B Probing Experiment
In this experiment, we validate that the effects of filler tokens training are indeed caused by a difference in expressive capacity and not a difference in learning dynamics. To do so, we probe final-layer representations confirm that filler-tokens are used for their additional computational capacity. This hypothesis is confirmed in Figure 5 where the first half of the filler tokens appear crucial, achieving 98% performance while using only 60% of the total filler tokens. Here each point represents a different final-layer fine tune varying the total filler-tokens available hyper-parameter This early convergence given half the total filler tokens is to be expected for an efficient algorithm solving 3SUM, since each pair of inputs
For 3SUM, dinput ~ 10d + n following the notation of Equation (1). These dimensions correspond to tuple digits and hard-coded positional values.
13

---

Published as a conference paper at COLM 2024
Maximum Accuracy
0.80
0.75
Length 10
Length 14
Length
Length
Figure 6: When training on mixtures of filler-token and instance-adaptive sequences, filler token sequences remain at baseline performance for lengths 12 and 14. For the length-10 seed showing 95% accuracy, we found this model achieved 93.0% accuracy given only 10% of the original filler tokens, suggesting that the model makes minimal use of filler tokens. Points in this plot correspond to different random initializations.
needs to be summed only once for a total of N2/2 comparisons-wheres the total number of filler tokens we provide is N2.
Given the possibility of non-linear, learned probes confounding the interpretation of repre- sentations with the probes' own computation, we compare to the following control condition (Hewitt & Liang, 2019). This ensures that the observed filler-token vs accuracy scaling (Fig- ure 5) reflects the frozen model layers' representations and not the probe itself. For the control task, we take a model trained with filler tokens on sufficiently simple 3SUM se- quences for which immediate, no-filler, solutions tractable: length-10, dimension-1 data. 13 To confirm that the probe results in Figure reflect filler-token utility, we must confirm that the baseline probe on the dimension-1 control data does not find filler-token representations to be useful. As expected, we find that this length-10, dimension-1 model can achieve 100% accuracy given only 2% of the original number of filler tokens." 14 In effect, our probe finds filler token representations are redundant in models which have the expressive capacity to solve problems without filler tokens.
C Instance-Adaptiee Chain of Thought
These chains of thought differ from parallelizable CoT that they require caching sub- problem solutions in token outputs. When the computation carried out in later chain- of-thought token depends on the results found an earlier chain-of-thought token, we term this instance-adaptive computation. In these 3SUM chains of thought, the 3SUM problem decomposed into dimension-wise 3SUMs: for each triple, a given dimension- wise summation is only computed if the previous dimension summed to zero-thi this is instance-adaptive dependency. Instance-adaptive computation is incompatible with the parallel structure of filler token computation.
This was determined by training another model without any intermediate tokens and observing that model achieved 100% accuracy. 142% was the minimum number tested, it is likely no filler tokens necessary.
14

---

Published as a conference paper at COLM 2024
C.1 Data Generation Details
Inputs are drawn identically in the parallelizable and serial cases. The chain-of-thought generating process is as follows: Given input e.g. e.g. "A15 B75 C22 D13", the chain of thought
is ": A B C. 15 75 22 2 B C 75 22 13 0 ANS True". For each triple egg. "ABC" and "B C D", the generating process is follows:
1. List individual triple if it sums to zero in the first coordinate (e.g. the ABC' substring).
2. List the values of the triples, copying from the input (e.g. the '15 75 22' substring).
3. List the result summinn the given triple in the dimensions (e.g. the '2' substring, since 2 (15 + 75 22 mod10)2).
In our example, 'A B C' sum to in the first dimension, but sum to 2 in the second dimension;
'B C D' sums to 0 in both dimensions meaning 3SUM satisfied for this input.
C.2 Results
Figure 6 shows that in 8/9 random intializations, instance-adaptive training fails transfer to filler-token sequences. For these runs we use identical hyper-parameters to the parallel CoT setting, except we increase the number of epochs to 10 (this choice was arbitrary). In all settings, tuple dimensionality was fixed at 3.
Condition
1.-
Filler
Filler
0.9
Maximum Accuracy
0.7
0.6
Dimersion
Dimersion
Dimension
Dimmmision
Dimension
Figure 7: Performance on dimension-varied, length-110 data as function of tuple dimension- ality. The immediate-answe models were trained on a 50/50 mixtures of instance-adaptive CoT and immediate-answer sequences.
in practice, as in the parallel case, we randomly drop dimensions to reduce sequence length, the post-drop sequence might be ": A B 1,70, 2 C 1g 0 ANS True" if only the dimension 0 coordinates were kept.
15

---

Published as a conference paper at COLM 2024
Condition
No Filler
Hiller
0.9
Maximum Accuracy
0.8
0.7
08
0.5
Dimersion
Oimensien
Dimension
Dimerstonn
Dimension
Figure Performance on dimension-varied, length-8 data as a function of tuple dimension- ality. These immediate-anssw models were trained on no-intermediate-toeen sequences only. Note that these results under-perform relative to the mixed immediate-answer data models shown in Figure 4.
D Dimension Scaling Further Results
In Section 4.2, we saw that for length-8 inputs, scaling 3SUM dimensionality resulted performance gap between the filler-token and immediate-answer settings. In Figure 7, we show that this gap occurs at length-10 as well, but the emergence occurs at lower dimension: ttree-dimensional inputs show filler-token performance gap, whereas six were required for Figure 4. Intuitively it is clear that 3SUM input length and dimensionality both contribute to the parameters required to solve problem instances in single forward pass. Hence, the decrease in dimensionality required to realize a performance gap as we increase length.
For completeness, also include subset of length-8 results when using models trained only on immediate-response sequences. Unlike the other pepennioon-efformmnn plots, the immediate-anse models trained for Figure 8 do not any instance-adaptive chain-of- thought examples.
E Validation Loss Curves
We plot the validation loss curves for final-token, 'True' or 'False', prediction. Figure shows that five epochs suffice for the most complex data. Figure 10 shows that 25 epochs are sufficient for evaluating immediate-answer performance in most cases. It is likely that the accuracy on the length-8 data shown in Figure 2 underestimates the unbounded computt, limiting performance in this particular case. Given compute constraints, and the fact that none of our claims depend on the performance of this particular length-8 case, we did not explore this further.
16

---

Published as a conference paper at COLM 2024
Iaan Curiit
Length:
Length: 8, Dimension
3SUM Prediction Loss
0.15
0.10
0.56
0.00
25000
50000
75002
100000
125200
150030
175200
200000
Step
Figure 9: Validation loss on 3SUM final prediction token for models trained with filler. These models were trained for 5 epochs.
0.6
3SUM Predictton Loos
Run Confg
0.4
Length: Dimension:
Length: 12, Dimension.
Length: 10, Dimension:
Length: Dmaansio:
Length. Dimension:
8.1
Step
Figure 10: Validation loss 3SUM final prediction token for models trained on no- intermediate-tokens, immediate-answer sequences. These models were trained for 25 epochs.
17


Reviews:
[{"review_id": "rid4DAIWgf", "reviewer": "Reviewer_zMzE", "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. \nThey 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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](https://arxiv.org/abs/2307.13702),[2](https://www.lesswrong.com/posts/oSZ2xTxEMZh9f3Yaz/llms-are-mostly-not-helped-by-filler-tokens)). \n\nTo go through point-by-point:\n\n- “learning to use filler tokens requires dense, task-specific supervision which may not be practical or scalable in many contexts.” \nOur 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.\n- 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.\n- “AB70” is correct since (0,5)+(7,5)%10=(7,0). \n- To clarify the serial CoT controls, we will include an additional appendix figure showing detailed results for sec 4.3. \n- 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "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.\n2. It combines theoretical characterizations with empirical evidence, offering a robust examination of the utility of filler tokens.\n3. 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.\n2. The experiments are conducted on relatively small transformer models, which may not fully capture the behavior and potential of larger, more advanced models\n3. 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?\n2. In Table 1, does chain-of-thought include both parallelizable and serial tokens, or only parallelizable tokens?\n3. In Table 1, if the \"No Intermediate Tokens\" is the same as no-filler, refer to it as no-filler to avoid misunderstanding. \n4. Section 4.3 is quite ambiguous; the authors should provide detailed experimental tables and prove their claims for a better explanation.\n5. 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\"?", "extra_scores": {}}, {"review_id": "BkVAjzqc6Y", "reviewer": "Reviewer_KfHS", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. This paper explores a very important problem, which provides insights into understanding how chain-of-thought (CoT) works for LLMs. \n2. 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.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s7fjtKSm0n", "reviewer": "Reviewer_7L8q", "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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](https://arxiv.org/abs/2307.13702)), whereas our results establish a specific case where they can help.\n\nRegarding 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. \n\n> “I believe more sets of problems should be explored to verify the effects of filler tokens as CoT\"\n\nIn contrast to broad benchmarking work as in e.g. [BigBench](https://github.com/google/BIG-bench), 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. This work addresses an interesting problem of how filler tokens can be used as a useful chain-of-thought method. \n\n2. 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. \n\n1. 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. \n\n2. Experiments should be improved to be more thorough in multiple dimensions. \n- More variants of 3SUM problems may be tested with different lengths, dimension, etc. \n- More baselines of CoT may need to be compared.", "questions_to_authors": "Please refer to the Weakness above.", "extra_scores": {}}, {"review_id": "5KPEfRRExD", "reviewer": "Reviewer_f5kZ", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": true, "final_justification": "", "rebuttal": "Thank you for engaging with our work! \n\n#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.\n\n#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:\n\n    (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.\n\n    (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).\n\n#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.”\nWe 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:\n> “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.” \n\nSo the performance hierarchy is:\timmediate-answer < filler tokens << chain of thought\n\nFor 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "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.\n\n1. 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. \n\n2. 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. \n\n3. 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. \n\nOverall, I do not understand the authors' main points, but I am happy to revise if they point out my misunderstandings.", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper explores the impact of filler tokens in transformer language models, particularly in improving computational capabilities independently of meaningful chain-of-thought (CoT) tokens. The authors present empirical and theoretical insights into how these tokens can benefit transformer models in solving complex algorithmic tasks. Key findings demonstrate that filler tokens can enable hidden computation, improving performance on tasks like the 2Sum and 3Sum problems as sequence length and dimensionality scale.

The authors had adequate discussions with AC and the reviewers. Although the general claim has not been rigorously proved, the empirical findings are interesting. Addressing the noted weaknesses and expanding the scope of experiments would significantly enhance its contributions to the field.

[comments from the PCs] Please follow up on the AC and reviewer comments to refine the claims of the paper and experiments.
Decision: Accept