GPT is still a language model, so at some point it's still just tokens.

Is this just a schema validation layer on their end to avoid the round trip (and cost) of repeating the call?

Language models like GPT output a large vector of probabilities for the next token. Then a sampler decides which of those tokens to pick.

The simplest algorithm for getting good quality output is to just always pick the highest probability token.

If you want more creativity, maybe you pick randomly among the top 5 highest probability tokens or something. There are a lot of methods.

All that grammar-constrained decoding does is zero out the probability of any token that would violate the grammar.

Thank you for this explanation. A few things just clicked for me.

For many things, fine-tuning as we know of it will NEVER fully solve it, there's no hope. Even fine-tuning a model to not use the letter "e" to an overwhelming degree doesn't entirely prevent it, only reduces its chances to increasingly small amounts. Shamesless self plug, and from before the ChatGPT era too! https://paperswithcode.com/paper/most-language-models-can-be...

How does llama.cpp’s grammar adherence work?

Does it keep validating the predicted tokens and backtrack when it’s not valid?

It's essentially an Earley Parser[0]. It maintains a set of all possible currently valid parses, and zeroes out the probability of any token that isn't valid in at least 1 of the current potential parse trees.

There are contrived grammars you can give it that will make it use exponential memory, but in practice most real-world grammars aren't like this.

[0] https://en.wikipedia.org/wiki/Earley_parser

[delayed]

You don't even need that for JSON. JSON can be expressed using a LR(1) grammar, so you can do it in linear time and space.

Yes, the llama.cpp work supports arbitrary CFGs, not just JSON

I was surprised it took so long until I reached this line:

> The model can fail to follow the schema if the model chooses to refuse an unsafe request. If it chooses to refuse, the return message will have the refusal boolean set to true to indicate this.

I'm not sure how they implemented that, maybe they've figured out a way to give the grammar a token or set of tokens that are always valid mid generation and indicate the model would rather not continue generating.

Right now JSON generation is one of the most reliable ways to get around refusals, and they managed not to introduce that weakness into their model