Grammars are written in characters. Models emit tokens.

I am about to spend several weeks building a constrained decoding engine, so I started by reading a paper from 2019. Section 2.2 of the GPT-2 paper is about half a page long. It sits between the training dataset section and the model architecture section, and it is easy to skim past. It is also, as far as I can tell, the origin of the single hardest problem in the field I am about to work in. Here is what it says, what I verified by running the tokenizer myself, and the thing I found at the end…