Type-Driven Tokenization for Brahmic Scripts

Abstract:Standard tokenizers used in large language models produce malformed text when applied to Brahmic scripts. They are a family of abugidas, writing systems whose consonants carry an inherent vowel that dependent marks can modify. They include Devanagari, Telugu, Tamil, Kannada, and others. The underlying issue is that these tokenizers violate orthographic constraints that do not arise in alphabetic scripts like English. We observe that while English orthography forms a \emph{semigroup} (any two valid tokens can be freely concatenated), Brahmic orthography forms a \emph{partial semigroup}: not every concatenation yields a valid string. We formalise this distinction in Agda, model valid Brahmic tokens as chains in a transition system, and derive a provably correct \texttt{fixToken} function that extends any candidate token to respect orthographic boundaries. We then show how this formal derivation translates into a practical patch for SentencePiece as well as a standalone Rust-based pre-tokenizer library, eliminating the observed errors across Indic scripts.

Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL)

arXiv:2609.22125 [cs.CL]

(or arXiv:2609.22125v1 [cs.CL] for this version)

https://doi.org/10.48550/arXiv.2609.22125 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.