ENTP: Encoder-only Next Token Prediction

Ethan Ewer, Daewon Chae, Thomas Zeng, Jinkyu Kim, Kangwook Lee

Abstract

Next-token prediction models have predominantly relied on decoder-only Transformers with causal attention, driven by the common belief that causal attention is essential to prevent "cheating" by masking future tokens. We challenge this widely accepted notion and argue that this design choice is about efficiency rather than necessity. While decoder-only Transformers are still a good choice for practical reasons, they are not the only viable option. In this work, we introduce Encoder-only Next Token Prediction (ENTP). We explore the differences between ENTP and decoder-only Transformers in expressive power and complexity, highlighting potential advantages of ENTP. We introduce the Triplet-Counting task and show, both theoretically and experimentally, that while ENTP can perform this task easily, a decoder-only Transformer cannot. Finally, we empirically demonstrate ENTP's superior performance across various realistic tasks, such as length generalization and in-context learning.

Introduction

Modern Large Language Models (LLMs) like GPT-4 and Llama-3 are almost exclusively "decoder-only." They utilize causal attention, ensuring that each token can only attend to the tokens that precede it. This design is highly efficient, enabling techniques like KV-caching to generate sequences in $O(n^2)$ time. However, this architectural constraint raises a fundamental question: is this efficiency a trap? By forcing a strict causal structure on internal representations, are we limiting the model's computational expressivity?

ENTP (Encoder-only Next Token Prediction) investigates whether removing the causal constraint—using an encoder that allows all tokens to attend to each other during the prediction of the next token—unlocks new levels of expressive power. The paper argues that the standard decoder-only choice is one of efficiency rather than necessity.

Methodology: From Causal Decoders to Bidirectional Encoders

In the ENTP framework, an encoder-only Transformer is used for auto-regressive generation. Unlike a standard decoder that maintains a fixed causal mask throughout the process, ENTP performs a full bidirectional attention pass over the entire available context $(x_1, \dots, x_n)$ to predict the next token $x_{n+1}$.

Architectural comparison between standard Decoder-only models and the proposed ENTP.

This approach allows for richer, re-contextualized representations at every step. However, it comes with a significant computational cost. While a decoder generates a sequence in $O(n^2)$ time, ENTP requires $O(n^3)$ because it recomputes the entire sequence representation from scratch for every new token. Using circuit complexity and function expressivity, the authors prove that the sets of functions these architectures can express are not comparable, suggesting that encoders can solve specific complex tasks that decoders theoretically cannot.

The Expressivity Gap: Triplet Counting

To demonstrate this theoretical gap, the researchers introduced the Count3 (Triplet-Counting) task. This synthetic benchmark requires the model to count triplets of integers in a sequence that sum to $0 \pmod n$.

The Triplet-Counting task (Count3) requires identifying sets of three elements that satisfy a specific modular arithmetic condition.

The authors prove that an encoder with a constant number of layers ($L=O(1)$) can solve this task, whereas a decoder-only model requires a number of layers proportional to the sequence length ($L=\Omega(n)$). In a decoder, the representation of an early token is fixed once computed; it cannot be updated based on "future" tokens that might be critical for the final prediction. ENTP allows the entire context to be re-contextualized for every single prediction, effectively "seeing" the necessary future context for earlier tokens.

Empirical Results

ENTP was evaluated against standard decoders across several domains, showing consistent advantages in reasoning and generalization:

  • Count3 Success: ENTP achieved near-perfect accuracy on the Count3 task. In contrast, even massive decoder-only models like Llama-3-8B and GPT-4o (fine-tuned) failed to solve the task.
  • Language Modeling: On OpenWebText, the ENTP model achieved a lower validation perplexity (104.6) compared to the decoder-only baseline (110.5).
  • Reasoning Benchmarks: ENTP outperformed decoders on downstream tasks, reducing the error rate on TinyWinoGrande from 44.0% to 39.0% and on CLUTRR from 0.9% to 0.5%.
  • Arithmetic and Generalization: ENTP showed a much stronger ability to generalize to longer sequences (Out-of-Distribution) than decoders in arithmetic tasks and required significantly fewer training examples to reach high accuracy.
  • In-Context Learning (ICL): ENTP demonstrated superior or competitive performance across all tested function classes, including linear regression and decision trees.

Discussion and Future Work

The primary limitation of ENTP is its computational complexity. The $O(n^3)$ sequence generation time makes it impractical for long-form generation or real-time deployment in its current form.

Future research directions include developing a "compute-efficient ENTP variant" that retains the expressivity of bidirectional attention without the cubic cost, exploring hybrid architectures, and investigating how these expressivity advantages translate when scaled to models with hundreds of billions of parameters. Ultimately, ENTP proves that the causal constraint is not a necessity for learning, but a choice that may be limiting the potential of our most powerful models.

Summary updated

Abstract

Next-token prediction models have predominantly relied on decoder-only Transformers with causal attention, driven by the common belief that causal attention is essential to prevent "cheating" by masking future tokens. We challenge this widely accepted notion and argue that this design choice is about efficiency rather than necessity. While decoder-only Transformers are still a good choice for practical reasons, they are not the only viable option. In this work, we introduce Encoder-only Next Token Prediction (ENTP). We explore the differences between ENTP and decoder-only Transformers in expressive power and complexity, highlighting potential advantages of ENTP. We introduce the Triplet-Counting task and show, both theoretically and experimentally, that while ENTP can perform this task easily, a decoder-only Transformer cannot. Finally, we empirically demonstrate ENTP's superior performance across various realistic tasks, such as length generalization and in-context learning.
BibTeX
@misc{ewer2024entp,
  author = {Ethan Ewer and Daewon Chae and Thomas Zeng and Jinkyu Kim and Kangwook Lee},
  title = {{ENTP: Encoder-only Next Token Prediction}},
  year = {2024},
  eprint = {2410.01600},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.01600},
}
Figure