PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jacob Pfau, William Merrill, Samuel R. Bowman

arXiv:2404.15758v1cs.CLcs.AI

TL;DR

The paper asks whether chain-of-thought gains come from meaningful task decomposition or simply additional computation. It studies repeated filler tokens on synthetic algorithmic tasks and finds that they can solve tasks beyond immediate-answer performance, while learning this behavior requires dense supervision and is theoretically useful for sufficiently deep quantifier structure.

  • Problem

    It is unclear whether chain-of-thought improves language-model performance through human-like decomposition or merely by allowing additional computation across intermediate tokens.

  • Method

    The paper evaluates repeated-dot filler tokens on 3SUM and 2SUM-Transform, analyzes their computational expressivity, and studies the supervision needed to learn their use.

  • Results

    Filler tokens enable 100% accuracy on 3SUM and 94% on 2SUM-Transform, while no-filler models fail on these tasks.

  • Takeaways & Limitations

    Intermediate tokens can provide computational benefits independent of token choice, making observed chain-of-thought potentially detached from the computation performed.

  • Takeaways & Limitations

    Filler-token computation is difficult to learn because dense supervision is unavailable and standard chain-of-thought data encourages incompatible serial, instance-adaptive computation.

Abstract

from arXiv · show

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 characterization of 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.

1 Introduction

The paper tests whether intermediate tokens improve transformer computation because of their meanings or simply because they provide additional forward passes. On synthetic algorithmic tasks, filler tokens can match chain-of-thought performance, but exploiting them requires targeted supervision.

  • Motivation: Filler tokens replace chain-of-thought tokens with arbitrary repeated symbols while their hidden representations still carry task-relevant computation.The strict setting uses repeated dots, but the authors frame it as a minimal case of more general filler sequences.
  • Empirical result: Commercial LLMs such as Claude 2 and GPT-3.5 show no filler-token benefit on common QA and mathematics benchmarks.They achieve the same performance with filler tokens as with direct responses.
  • Theory: Filler tokens remain within TC0, yet the experiments show they can add computational power within that class.This contrasts their computational effect with the broader expressivity expansion associated with chain-of-thought tokens.
  • Learning: The authors find that learning filler-token computation is difficult and requires specific, dense supervision; standard chain-of-thought data is insufficient.The contribution summary identifies this learning requirement as a central result.

2 Related Work

Related work characterizes transformers without additional reasoning tokens as computationally limited, while chain-of-thought can expand their expressivity. This paper focuses on whether blank or arbitrary tokens can provide computation without conveying an instruction or decomposition.

  • Transformer expressivity: Log-precision transformers without additional reasoning tokens are placed in TC0, corresponding to problems definable in first-order logic with majority quantifiers.This framework captures the highly parallelizable problems solvable by such transformers.
  • Transformer expressivity: Problems outside first-order majority logic, including permutation composition and graph connectivity, cannot be solved by transformers without additional reasoning tokens.These examples illustrate the expressivity limits discussed in prior theoretical work.
  • Chain-of-thought: Sufficiently long chain-of-thought sequences can let transformers solve problems outside TC0 by adding generated tokens to the input.Prior results treat chain-of-thought as both a decomposition hint and a source of additional computational power.
  • Filler tokens: With polynomially many filler tokens, transformers remain in TC0, so filler tokens do not expand expressivity beyond that class.The theoretical simulation argument applies when the number of filler tokens is polynomial in input size.
  • Filler tokens: Filler tokens may nevertheless solve TC0 problems requiring many nested quantifiers simultaneously, with a quantifier-depth-k problem expressible using n^k filler tokens.The proposed benefit concerns problems that no-filler transformers may not express despite remaining within TC0.
  • Empirical studies: Prior empirical studies find that commercial LLMs generally gain nothing from filler tokens on NLP and mathematics QA benchmarks.The paper positions its synthetic-task results as complementary evidence rather than a replication of those benchmark findings.
  • Adjacent approaches: Other work studies non-myopic token representations and adaptive computation mechanisms, whereas this paper examines coordinated computation using token-agnostic filler sequences.The comparison distinguishes the paper’s focus from probing studies and architectural or objective modifications.

3 Synthetic data: 3SUM and 2SUM

The paper constructs synthetic 3SUM and 2SUM-Transform tasks to test when filler tokens provide computational benefits, focusing on parallelizable or delayed-information settings. It defines multiple intermediate-token sequences, including repeated dots and chain-of-thought decompositions, and examines how these tasks relate to transformer expressivity and training constraints.

  • 3SUM: 3SUM asks whether distinct input triples sum to the zero vector modulo 10, requiring O(n^3) candidate summations in the worst case.The task is motivated as likely exceeding a standard transformer’s capacity for large n because attention layers induce only quadratic dependencies.
  • 3SUM: 3SUM is chosen because it is parallelizable despite having quantifier depth greater than 2, making it a candidate for filler-token computation.The paper uses learnability with filler tokens as evidence of an expressivity gap between filler and no-filler settings for nested quantifier resolution problems.
  • 2SUM-Transform: 2SUM-Transform matches pairs summing to zero after applying a transformation specified only by a final token, preventing in-place computation over the obfuscated inputs.The task uses randomly sampled digit-shifting permutations and appends the permutation identifier to the transformed input sequence.
  • Intermediate-token sequences: The study compares filler, parallelizable chain-of-thought, and instance-adaptive chain-of-thought sequences across varying input complexity and tuple dimensionality.Instance-adaptive chains reduce multidimensional 3SUM to serial one-dimensional problems and can require O(n^3) sequence length, unlike the parallelizable decomposition.
  • 3SUM: Filler sequences replace these intermediate chain-of-thought tokens with repeated dots, allowing the model to perform the same token-positioned computation without explicit intermediate results.The dataset mixes chain-of-thought and filler sequences, with additional positional encoding information used to simplify the task.
  • 3SUM: The parallelizable 3SUM chain of thought reduces the cubic problem to pairwise sums, followed by checking whether each sum matches a third input.Individual pairwise results can be computed with one attention layer, while a subsequent layer checks matching third inputs.

4 3SUM: transformers converge with filler tokens and fail without

On synthetic 3SUM tasks, filler tokens let a small transformer solve longer or more complex inputs that no-filler models cannot solve, while learning this computation requires suitable supervision.

  • The experiments use a scaled-down 34M-parameter Llama model and compare immediate-answer, filler-token, and chain-of-thought conditions.Training uses 10,000,000 samples and reports per-run maximum validation performance across epochs.
  • 100% accuracy persists with filler tokens on length-12, dimension-3 3SUM inputs, while no-filler models reach only 66%.
  • Additional filler tokens improve predictions from frozen representations, indicating that filler positions encode task-relevant hidden computation.The first 60% of filler tokens achieves 98% performance in the reported setup.
  • Increasing tuple dimension creates performance gaps even for fixed length-8 inputs, though the small model requires at least six-dimensional inputs.The no-filler baseline uses a 50/50 mixture of filler-token and instance-adaptive chain-of-thought data.
  • Filler-token computation is difficult to learn without dense, parallelizable supervision: filler-only training remains around 71% accuracy, and instance-adaptive CoT does not transfer.

5 2SUM Experiments

In 2SUM experiments, no-filler models learn little beyond label statistics, whereas filler-token performance approaches that of chain-of-thought models.

  • No-filler 2SUM models perform above random but significantly below models trained with filler tokens.
  • The no-filler condition only narrowly exceeds the 75% majority-class baseline, indicating little learned algorithmic structure beyond label statistics.
  • Filler-token performance recovers 90% of the chain-of-thought benefit over the immediate-answer baseline.The comparison uses the same model but disjoint test subsets for chain-of-thought and filler-token results.

6 Conclusion

The paper argues that intermediate tokens can supply computation independently of their meaning, making chain-of-thought outputs potentially uninformative or misleading about hidden processing.

  • For certain parallelizable problems, filler tokens improve performance without representing human-like serial problem decompositions.
  • If token-parallelizable TC0 problems and suitable parallelizable supervision occur in natural language, filler-token use may emerge in future language models.

A Instance-Adaptive Chain of Thought

Instance-adaptive chain of thought computes later steps conditionally on results cached in earlier output tokens, unlike parallelizable filler-token computation.

  • A Instance-Adaptive Chain of Thought: Instance-adaptive computation caches subproblem solutions in token outputs for use by later chain-of-thought steps.In 3SUM, later dimension-wise sums are computed only when earlier dimensions sum to zero.

A.1 Data Generation Details

The data-generation process constructs chain-of-thought sequences by enumerating triples, copying their coordinate values, and recording dimension-wise sums before predicting the answer.

  • A.1 Data Generation Details: Each example lists triples whose first-coordinate sum is zero.For example, the sequence includes the triple identifiers before their values and computed sums.
  • A.1 Data Generation Details: The generator copies each selected triple’s coordinate values from the input.These copied values appear as an intermediate sequence before the dimension-wise results.
  • A.1 Data Generation Details: It records the triple’s sums across dimensions, such as 2 for (15 + 75 + 22) mod 10.The example shows A B C summing to 0 then 2, while B C D sums to 0 in both dimensions and satisfies 3SUM.
  • A.1 Data Generation Details: Dimensions may be randomly dropped to shorten the generated sequence.The post-drop example retains only dimension-0 coordinates.
  • A.1 Data Generation Details: Instance-adaptive training fails to transfer to filler-token sequences in 8/9 random initializations.The experiment used identical hyperparameters to the parallel-CoT setting, except for 10 training epochs; tuple dimensionality was fixed at 3.
  • A.1 Data Generation Details: Figure 7 varies tuple dimensionality for length-10 data, whereas Figure 8 reports length-8 data from models trained only on immediate-answer sequences.Figure 7’s no-filler models used a 50/50 mixture of instance-adaptive CoT and immediate-answer sequences.

B Dimension Scaling Further Results

Increasing input length and tuple dimensionality both affect the performance gap between filler-token and no-filler settings, with the gap emerging at lower dimensionality for longer inputs.

  • B Dimension Scaling Further Results: At length 10, a filler-token performance gap appears at three dimensions, whereas Figure 5 required six dimensions.This supports a relationship between increased input length and reduced dimensionality needed to observe the gap.
  • B Dimension Scaling Further Results: The length-8 subset uses no-filler models trained only on immediate-answer sequences, without instance-adaptive chain-of-thought examples.These results are distinct from the other dimension-performance plots.

C Validation loss curves

Validation-loss curves track final-token prediction for filler-trained and no-filler models, using five and 25 training epochs respectively.

  • C Validation loss curves: Figure 9 plots validation loss for the final True-or-False prediction token in filler-trained models after five epochs.Five epochs suffice for the most complex data.
  • C Validation loss curves: Figure 10 plots validation loss for the 3SUM final prediction token in no-intermediate-token models trained for 25 epochs.Twenty-five epochs are sufficient for evaluating no-filler performance in most cases.
Loading 2404.15758v1…