Constructing a BPE Tokenization DFA

• URL: http://arxiv.org/abs/2405.07671v1
• Date: Mon, 13 May 2024 11:59:24 GMT
• Title: Constructing a BPE Tokenization DFA
• Authors: Martin Berglund, Willeke Martens, Brink van der Merwe,
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many natural language processing systems operate over tokenizations of text to address the open-vocabulary problem. In this paper, 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. This makes it possible to apply many existing techniques and algorithms to the tokenized case, such as pattern matching, equivalence checking of tokenization dictionaries, and composing tokenized languages in various ways.

Related papers

• Enhancing LLM Character-Level Manipulation via Divide and Conquer [108.6908427615402]
  Large Language Models (LLMs) have demonstrated strong generalization capabilities across a wide range of natural language processing (NLP) tasks. They exhibit notable weaknesses in character-level string manipulation, struggling with fundamental operations such as character deletion, insertion, and substitution. We propose Character-Level Manipulation via Divide and Conquer, a novel approach designed to bridge the gap between token-level processing and character-level manipulation.
  arXiv  Detail & Related papers  (2025-02-12T07:37:39Z)
• Flexible and Efficient Grammar-Constrained Decoding [5.671312847528642]
  Grammar-constrained decoding (GCD) can guarantee that LLM outputs matches such rules. Existing GCD algorithms require tens of minutes to preprocess common grammars. We present a new GCD algorithm together with an implementation that offers 17.71x faster offline preprocessing than existing approaches.
  arXiv  Detail & Related papers  (2025-02-07T17:35:17Z)
• Enhancing Item Tokenization for Generative Recommendation through Self-Improvement [67.94240423434944]
  Generative recommendation systems are driven by large language models (LLMs) Current item tokenization methods include using text descriptions, numerical strings, or sequences of discrete tokens. We propose a self-improving item tokenization method that allows the LLM to refine its own item tokenizations during training process.
  arXiv  Detail & Related papers  (2024-12-22T21:56:15Z)
• Tokenization as Finite-State Transduction [24.19959327497118]
  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.
  arXiv  Detail & Related papers  (2024-10-21T07:10:07Z)
• 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)
• Identifying and Analyzing Task-Encoding Tokens in Large Language Models [55.03191279766383]
  In this paper, we identify and analyze task-encoding tokens on whose representations the task performance depends. We show that template and stopword tokens are the most prone to be task-encoding. Our work sheds light on how large language models (LLMs) learn to perform a task from demonstrations, deepens our understanding of the varied roles different types of tokens play in LLMs, and provides insights for avoiding instability from improperly utilizing task-encoding tokens.
  arXiv  Detail & Related papers  (2024-01-20T20:55:21Z)
• Tokenization with Factorized Subword Encoding [2.538209532048867]
  We propose a novel tokenization method that factorizes subwords onto discrete triplets using a VQ-VAE model. Results indicate that this method is more appropriate and robust for morphological tasks than the commonly used byte-pair encoding (BPE) tokenization algorithm.
  arXiv  Detail & Related papers  (2023-06-13T13:27:34Z)
• Better Than Whitespace: Information Retrieval for Languages without Custom Tokenizers [48.036317742487796]
  We propose a new approach to tokenization for lexical matching retrieval algorithms. We use the WordPiece tokenizer, which can be built automatically from unsupervised data. Results show that the mBERT tokenizer provides strong relevance signals for retrieval "out of the box", outperforming whitespace tokenization on most languages.
  arXiv  Detail & Related papers  (2022-10-11T14:32:46Z)
• Improving Tokenisation by Alternative Treatment of Spaces [7.596737214110957]
  We experiment with an alternative tokenisation approach where spaces are always treated as individual tokens. We find that our modified algorithms lead to improved performance on downstream NLP tasks.
  arXiv  Detail & Related papers  (2022-04-08T13:22:30Z)
• Byte Pair Encoding is Suboptimal for Language Model Pretraining [49.30780227162387]
  We analyze differences between unigram LM tokenization and byte-pair encoding (BPE) We find that the unigram LM tokenization method matches or outperforms BPE across downstream tasks and two languages. We hope that developers of future pretrained LMs will consider adopting the unigram LM method over the more prevalent BPE.
  arXiv  Detail & Related papers  (2020-04-07T21:21:06Z)

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.