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 that I did not expect.
The part everybody already knows
A model computes on numbers. Text is characters. Something has to bridge that, and there are three obvious ways to do it.
Word level. Map every word to an id. The vocabulary explodes, because every inflection and typo and compound is a new entry, and anything the model never saw during training becomes <UNK>. The model goes blind on it.
Character level. Map every character to an id. Nothing is ever out of vocabulary, because you can spell anything. But sequences get roughly five times longer, transformer attention cost scales with the square of sequence length, and you have made the model learn spelling before it can learn meaning.
Subword level. Split into pieces. Common words stay whole, rare words break into fragments the model has seen in other contexts. Short sequences, no out of vocabulary hole.
Byte Pair Encoding is the subword method that won. It came from a 1994 data compression algorithm and got repurposed for NLP by Sennrich et al. in 2015. The training loop is four lines of pseudocode:
- Start with a base vocabulary of every individual symbol in your corpus.
- Count every adjacent pair of symbols.
- Merge the most frequent pair into a new symbol and add it to the vocabulary.
- Go back to step 2 until you hit your target size.
That is it. If t h shows up constantly, you get a th token. Then th e shows up constantly, so you get the. Run it 50,000 times and common English words are single tokens while rare ones stay in fragments.
The property worth holding onto: this is greedy, frequency based, and entirely dependent on the corpus. Nothing about the resulting vocabulary is linguistically principled. It is whatever compressed the training data. That is why different tokenizers split the same word differently and why numbers and code often tokenize in ways that look arbitrary.
What GPT-2 actually contributed
Standard BPE at the time ran over Unicode code points. Unicode has more than 130,000 of them, so your base vocabulary is enormous before you have merged anything, and you still have holes for anything outside your set.
GPT-2 runs BPE over UTF-8 bytes instead.
A byte has 256 possible values. That is your entire base vocabulary. And because every possible Unicode string encodes to some sequence of UTF-8 bytes, there is no out of vocabulary case. Not for any language, not for emoji, not for malformed input. Any string at all.
This is the actual point of byte level BPE and I think it usually gets described wrong. It is not primarily an efficiency win. It is a coverage guarantee bought with a tiny base vocabulary.
The paper is also honest about what broke when they first tried it. Applying BPE naively to bytes produced bad merges, because the greedy frequency heuristic learned separate tokens for dog, dog., dog!, and dog?. Four vocabulary slots for one word. So they blocked merges across character categories: letters do not merge with punctuation.
You can check that this worked:
'dog' -> ['dog'] [9703]
'dog.' -> ['dog', '.'] [9703, 13]
'dog!' -> ['dog', '!'] [9703, 0]
'dog?' -> ['dog', '?'] [9703, 30]
Same dog token, id 9703, in all four. The punctuation is separate every time.
Then they carved out an exception for spaces, because blocking every cross category merge fragments ordinary text badly. Spaces get attached to the token that follows them, not the one before:
'hello world' -> ['hello', 'Ġworld']
The Ġ is how GPT-2's vocabulary renders a leading space. It is a prefix, which means hello and hello are two different tokens with two different ids (31373 and 23748). The same five letters, in the same order, are a different symbol to the model depending on whether a space came first.
Hold that thought.
The trade nobody explains cleanly
Vocabulary size is a knob with a real cost on both sides.
Bigger vocabulary means shorter sequences for the same text, so fewer decode steps to say the same thing. But your embedding matrix and your final softmax layer both scale with vocabulary size, so you pay in parameters and in output projection compute.
Smaller vocabulary means a cheaper embedding and softmax, but longer sequences. And since decoding is one sequential forward pass per token, and decoding is the memory bound half of inference, more tokens is directly more wall clock time.
50,257 was GPT-2's answer. It is not a constant of nature.
Now the part I actually came for
Everything above is background. Here is why I was reading it.
Constrained decoding is the technique that forces a model's output to conform to a schema. At every generation step, before sampling, you set the logits of every token that would break the schema to negative infinity. After softmax those tokens have probability exactly zero. The model cannot emit them. Validity stops being something you hope for and becomes something structural.
To do that, you compile the schema into a state machine. At any state you know which characters are legal next, so you know which tokens are legal next, so you know what to mask.
Except the schema is defined over characters and the model emits tokens, and those two things do not line up.
I knew that abstractly before I started. What I did not appreciate is how badly they do not line up. So I ran GPT-2's tokenizer over some JSON.
import tiktoken
enc = tiktoken.get_encoding("gpt2")
print(enc.encode('{"')) # [4895]
print(enc.encode('":')) # [1298]
print(enc.encode('"}')) # [20662]
print(enc.encode('"},{"')) # [11919]
{" is one token. The opening brace and the opening quote of the first key are fused into a single symbol, id 4895.
": is one token. The closing quote of a key and the colon that follows it, fused, id 1298.
"},{" is one token. Id 11919. Five characters: close a string, close an object, comma, open an object, open a string. That is five separate transitions in any JSON grammar you would write, and the model emits all of them or none of them, as one indivisible unit.
A full tool call looks like this:
'{"location": "Jaipur", "unit": "celsius"}'
['{"', 'location', '":', 'Ġ"', 'Ja', 'ip', 'ur', '",',
'Ġ"', 'unit', '":', 'Ġ"', 'cel', 's', 'ius', '"}']
Sixteen tokens. Look at where the boundaries fall. Not one of the structural delimiters sits alone. {", ":, ",, Ġ", "}. The grammar's alphabet and the model's alphabet are different alphabets, and the model's is coarser in exactly the places the grammar cares about most.
Out of 50,257 entries in the vocabulary, 50,001 are longer than a single character. That is 99.5 percent. 311 of them contain at least one of { } [ ] " : , and 92 of those also contain alphanumerics, which means there are almost a hundred single tokens that straddle the line between structure and content.
Why this costs you accuracy
Here is the mechanism, as I currently understand it. I want to be clear that this is the field's leading explanation rather than something settled, and testing it is a large part of what I am about to do.
Say a model is parsing a receipt and the correct total is 0.46. Left alone, it tokenizes like this:
'0.46' -> ['0', '.', '46'] [15, 13, 3510]
Three tokens, and 46 is a single one of them, id 3510. That is the path the model has walked thousands of times in training.
Now constrain it. The grammar is in some state where it expects a number, and depending on how your automaton is built and where the previous token landed you may end up masking in a way that forces the model down a different token path to spell the same string. The output is still valid JSON. It just took a route through the distribution that the model almost never took during training, in this context, and everything it generates after that point is conditioned on a prefix it did not choose.
BAML published a concrete case of this. On a receipt parsing task, constrained decoding returned 1 where the correct value was 0.46. Across the task they measured 91.37 percent accuracy constrained against 93.63 percent with free form parsing.
The 2 point gap is not the interesting part. The interesting part is that 1 is perfectly valid JSON. Your schema validated. Your types checked. Your pipeline reported success. There is no exception, no parse error, no signal anywhere that anything went wrong. The failure is silent by construction, because the entire purpose of the constraint was to make invalid output impossible, and it succeeded.
At the larger end, Tam et al. measured format restrictions degrading reasoning accuracy on benchmarks by as much as 27 points under strict constraints (EMNLP 2024). That number gets quoted a lot without its conditions attached, so treat it as an upper bound under specific settings rather than a headline, but the direction has since been replicated independently.
Token healing, and why it exists
There is a partial fix for the boundary half of this, and it has been sitting in Guidance for a while.
When a constraint truncates in the middle of what would naturally have been a single token, you back up to a clean token boundary and re-constrain from there, so the model gets to pick a token that spans the boundary rather than being forced to spell it out piece by piece.
It is called token healing, and reading GPT-2's section 2.2 is what made me understand why it needs to exist at all. It is not a workaround for a sloppy implementation. It is a direct consequence of a design decision made in 2019 for entirely unrelated reasons: bytes instead of code points, greedy frequency merges, spaces glued to the front of the following word. None of those choices were made with grammars in mind, because grammar constrained generation did not exist yet.
The XGrammar paper puts the same thing more precisely than I can. Their framing is that tokens are fixed strings which may not correspond to complete semantic units and may split Unicode characters, and that this is the fundamental challenge for structured generation. I found that sentence after I had worked out the problem by hand, which was a useful check that I was looking at the right thing.
What I do not know yet
Two things I want to measure rather than assume.
First, how much of the observed degradation is actually the boundary problem versus the other candidate mechanism, which is that a schema forces the model to commit to an answer field before the reasoning that would produce the answer has happened. My prior is that the second dominates on reasoning tasks and the first dominates on extraction tasks, but that is a guess and I have not seen it cleanly separated anywhere.
Second, whether the degradation is size dependent. If small models are hurt more than large ones, or the reverse, the shape of that curve says something about whether this is a capacity problem or a distributional one.
I am reproducing all of this across four model sizes over the next couple of weeks and publishing the harness with the numbers. If you have run into a case where structured output gave you a wrong but valid answer, I would like to see it. I am collecting them.
Reproduce it
Everything above runs in about thirty seconds:
# pip install tiktoken
import tiktoken
enc = tiktoken.get_encoding("gpt2")
def show(s):
ids = enc.encode(s)
toks = [enc.decode_single_token_bytes(i) for i in ids]
print(f"{s!r:45} -> {toks}")
for s in ['dog', 'dog.', 'hello', ' hello',
'{"', '":', '"}', '"},{"',
'0.46', '46',
'{"location": "Jaipur", "unit": "celsius"}']:
show(s)
The GPT-2 paper is Language Models are Unsupervised Multitask Learners, Radford et al. 2019. Section 2.2 is the one to read, and it is shorter than this post.
Top comments (0)