Tokenization as Finite-State Transduction

• URL: http://arxiv.org/abs/2410.15696v1
• Date: Mon, 21 Oct 2024 07:10:07 GMT
• Title: Tokenization as Finite-State Transduction
• Authors: Marco Cognetta, Naoaki Okazaki,
• Abstract summary: We introduce a finite-state framework which can efficiently encode all possible tokenizations of a regular language. We show that Byte-Pair. Match (BPE) and MaxPiece (WordPiece) fit within this framework. An application of this is to guided generation, where the outputs of a language model are constrained to match some pattern.
• Score: 24.19959327497118
• License:
• Abstract: Tokenization is the first step in modern neural language model pipelines where an input text is converted to a sequence of subword tokens. We introduce from first principles a finite-state transduction framework which can efficiently encode all possible tokenizations of a regular language. We then constructively show that Byte-Pair Encoding (BPE) and MaxMatch (WordPiece), two popular tokenization schemes, fit within this framework. For BPE, this is particularly surprising given its resemblance to context-free grammar and the fact that it does not tokenize strings from left to right. An application of this is to guided generation, where the outputs of a language model are constrained to match some pattern. Here, patterns are encoded at the character level, which creates a mismatch between the constraints and the model's subword vocabulary. While past work has focused only on constraining outputs without regard to the underlying tokenization algorithm, our framework allows for simultaneously constraining the model outputs to match a specified pattern while also adhering to the underlying tokenizer's canonical tokenization.

Related papers

• Batching BPE Tokenization Merges [55.2480439325792]
  BatchBPE is an open-source pure Python implementation of the Byte Pair algorithm. It is used to train a high quality tokenizer on a basic laptop.
  arXiv  Detail & Related papers  (2024-08-05T09:37:21Z)
• CosyVoice: A Scalable Multilingual Zero-shot Text-to-speech Synthesizer based on Supervised Semantic Tokens [49.569695524535454]
  We propose to represent speech with supervised semantic tokens, which are derived from a multilingual speech recognition model by inserting vector quantization into the encoder. Based on the tokens, we further propose a scalable zero-shot TTS synthesizer, CosyVoice, which consists of an LLM for text-to-token generation and a conditional flow matching model for token-to-speech synthesis.
  arXiv  Detail & Related papers  (2024-07-07T15:16:19Z)
• Understanding and Mitigating Tokenization Bias in Language Models [6.418593476658017]
  State-of-the-art language models are autoregressive and operate on subword units known as tokens. We show that popular encoding schemes induce a sampling bias that cannot be mitigated with more training or data. We propose a novel algorithm to obtain unbiased estimates from any language model trained on tokenized data.
  arXiv  Detail & Related papers  (2024-06-24T17:38:02Z)
• Constructing a BPE Tokenization DFA [0.0]
  Many natural language processing systems operate over tokenizations of text to address the open-vocabulary problem. We give and analyze an algorithm for the efficient construction of deterministic finite automata designed to operate directly on tokenizations produced by the popular byte pair encoding technique.
  arXiv  Detail & Related papers  (2024-05-13T11:59:24Z)
• Tokenization Is More Than Compression [14.939912120571728]
  Existing tokenization approaches like Byte-Pair. (BPE) originate from the field of data compression. We introduce PathPiece, a new tokenizer that segments a document's text into the minimum number of tokens for a given vocabulary.
  arXiv  Detail & Related papers  (2024-02-28T14:52:15Z)
• Object Recognition as Next Token Prediction [99.40793702627396]
  We present an approach to pose object recognition as next token prediction. The idea is to apply a language decoder that auto-regressively predicts the text tokens from image embeddings to form labels.
  arXiv  Detail & Related papers  (2023-12-04T18:58:40Z)
• Lexinvariant Language Models [84.2829117441298]
  Token embeddings, a mapping from discrete lexical symbols to continuous vectors, are at the heart of any language model (LM) We study textitlexinvariantlanguage models that are invariant to lexical symbols and therefore do not need fixed token embeddings in practice. We show that a lexinvariant LM can attain perplexity comparable to that of a standard language model, given a sufficiently long context.
  arXiv  Detail & Related papers  (2023-05-24T19:10:46Z)
• Local Byte Fusion for Neural Machine Translation [19.16966721276286]
  Subword tokenization schemes are the dominant technique used in current NLP models. Byte-based methods i.e. tokenization into byte sequences are an alternative. Experiments on multilingual translation, zero-shot cross-lingual transfer, and domain adaptation reveal a consistent improvement over traditional models.
  arXiv  Detail & Related papers  (2022-05-23T17:49:02Z)
• Charformer: Fast Character Transformers via Gradient-based Subword Tokenization [50.16128796194463]
  We propose a new model inductive bias that learns a subword tokenization end-to-end as part of the model. We introduce a soft gradient-based subword tokenization module (GBST) that automatically learns latent subword representations from characters. We additionally introduce Charformer, a deep Transformer model that integrates GBST and operates on the byte level.
  arXiv  Detail & Related papers  (2021-06-23T22:24:14Z)
• CANINE: Pre-training an Efficient Tokenization-Free Encoder for Language Representation [12.005340904206697]
  CANINE is a neural encoder that operates directly on character sequences without explicit tokenization or vocabulary. CanINE outperforms a comparable mBERT model by >= 1 F1 on TyDi QA, a challenging multilingual benchmark.
  arXiv  Detail & Related papers  (2021-03-11T18:57:44Z)
• Fast End-to-End Speech Recognition via a Non-Autoregressive Model and Cross-Modal Knowledge Transferring from BERT [72.93855288283059]
  We propose a non-autoregressive speech recognition model called LASO (Listen Attentively, and Spell Once) The model consists of an encoder, a decoder, and a position dependent summarizer (PDS)
  arXiv  Detail & Related papers  (2021-02-15T15:18:59Z)

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.