Toward a Theory of Tokenization in LLMs

• URL: http://arxiv.org/abs/2404.08335v1
• Date: Fri, 12 Apr 2024 09:01:14 GMT
• Title: Toward a Theory of Tokenization in LLMs
• Authors: Nived Rajaraman, Jiantao Jiao, Kannan Ramchandran,
• Abstract summary: We study tokenization from a theoretical point of view by studying the behavior of transformers on simple data generating processes. We show that even the simplest unigram models (over tokens) learnt by transformers are able to model the probability of sequences drawn from $ktextth$-order Markov sources near optimally.
• Score: 26.516041872337887
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While there has been a large body of research attempting to circumvent tokenization for language modeling (Clark et al., 2022; Xue et al., 2022), the current consensus is that it is a necessary initial step for designing state-of-the-art performant language models. In this paper, we investigate tokenization from a theoretical point of view by studying the behavior of transformers on simple data generating processes. When trained on data drawn from certain simple $k^{\text{th}}$-order Markov processes for $k > 1$, transformers exhibit a surprising phenomenon - in the absence of tokenization, they empirically fail to learn the right distribution and predict characters according to a unigram model (Makkuva et al., 2024). With the addition of tokenization, however, we empirically observe that transformers break through this barrier and are able to model the probabilities of sequences drawn from the source near-optimally, achieving small cross-entropy loss. With this observation as starting point, we study the end-to-end cross-entropy loss achieved by transformers with and without tokenization. With the appropriate tokenization, we show that even the simplest unigram models (over tokens) learnt by transformers are able to model the probability of sequences drawn from $k^{\text{th}}$-order Markov sources near optimally. Our analysis provides a justification for the use of tokenization in practice through studying the behavior of transformers on Markovian data.

Related papers

• Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning? [69.4145579827826]
  We show a fast flow on the regression loss despite the gradient non-ity algorithms for our convergence landscape. This is the first theoretical analysis for multi-layer Transformer in this setting.
  arXiv  Detail & Related papers  (2024-10-10T18:29:05Z)
• Unsupervised Representation Learning from Sparse Transformation Analysis [79.94858534887801]
  We propose to learn representations from sequence data by factorizing the transformations of the latent variables into sparse components. Input data are first encoded as distributions of latent activations and subsequently transformed using a probability flow model.
  arXiv  Detail & Related papers  (2024-10-07T23:53:25Z)
• Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers [54.20763128054692]
  We study how a two-attention-layer transformer is trained to perform ICL on $n$-gram Markov chain data. We prove that the gradient flow with respect to a cross-entropy ICL loss converges to a limiting model.
  arXiv  Detail & Related papers  (2024-09-09T18:10:26Z)
• Transformers on Markov Data: Constant Depth Suffices [25.83132046480226]
  We study the behavior of transformers on data drawn from kth Markov processes. We find that a transformer with a fixed depth and $1$ head per layer is able to achieve low test loss on sequences drawn from kth Markov sources.
  arXiv  Detail & Related papers  (2024-07-25T01:07:09Z)
• Transformers need glasses! Information over-squashing in language tasks [18.81066657470662]
  We study how information propagates in decoder-only Transformers. We show that certain sequences of inputs to the Transformer can yield arbitrarily close representations in the final token. We also show that decoder-only Transformer language models can lose sensitivity to specific tokens in the input.
  arXiv  Detail & Related papers  (2024-06-06T17:14:44Z)
• Transformers Can Represent $n$-gram Language Models [56.06361029539347]
  We focus on the relationship between transformer LMs and $n$-gram LMs, a simple and historically relevant class of language models. We show that transformer LMs using the hard or sparse attention mechanisms can exactly represent any $n$-gram LM.
  arXiv  Detail & Related papers  (2024-04-23T12:51:37Z)
• The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains [28.41876902994335]
  We introduce a simple Markov Chain sequence modeling task to study how this in-context learning (ICL) capability emerges. Transformers trained on this task form emphstatistical induction heads which compute accurate next-token probabilities. We show how successful learning results from the interaction between the transformer's layers, and uncover evidence that the presence of the simpler unigram solution may delay formation of the final bigram solution.
  arXiv  Detail & Related papers  (2024-02-16T18:28:36Z)
• How do Transformers perform In-Context Autoregressive Learning? [76.18489638049545]
  We train a Transformer model on a simple next token prediction task. We show how a trained Transformer predicts the next token by first learning $W$ in-context, then applying a prediction mapping.
  arXiv  Detail & Related papers  (2024-02-08T16:24:44Z)
• Transformers meet Stochastic Block Models: Attention with Data-Adaptive Sparsity and Cost [53.746169882193456]
  Recent works have proposed various sparse attention modules to overcome the quadratic cost of self-attention. We propose a model that resolves both problems by endowing each attention head with a mixed-membership Block Model. Our model outperforms previous efficient variants as well as the original Transformer with full attention.
  arXiv  Detail & Related papers  (2022-10-27T15:30:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.