4 ms·

I'm glad they gave up on their "fine-tuning is all you need" approach to structured output. It's possible fine-tuning will work in the long term, but in the sho

I'm glad they gave up on their "fine-tuning is all you need" approach to structured output. It's possible fine-tuning will work in the long term, but in the short-term, people are trying to build things, and fine-tuning wasn't cutting it. Surprised it took them so long — llama.cpp got this feature 1.5 years ago (actually an even more general version of it that allows the user to provide any context free grammar, not just JSON schema)

chhabraamit 2y ago
How does llama.cpp’s grammar adherence work? Does it keep validating the predicted tokens and backtrack when it’s not valid?
- gamegoblin 2y ago
  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 https://en.wikipedia.org/wiki/Earley_parser
  - jules 2y ago
    Earley parsers should not need more than O(n^2) memory.
  - orlp 2y ago
    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.
    - gamegoblin 2y ago
      Yes, the llama.cpp work supports arbitrary CFGs, not just JSON
tcdent 2y ago
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?
- gamegoblin 2y ago
  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.
  - nickreese 2y ago
    Thank you for this explanation. A few things just clicked for me.
BoorishBears 2y ago
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
Der_Einzige 2y ago
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-poets-too-an-ai-1 https://paperswithcode.com/paper/most-language-models-can-be...

chhabraamit 2y ago

How does llama.cpp’s grammar adherence work? Does it keep validating the predicted tokens and backtrack when it’s not valid?

gamegoblin 2y ago
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 https://en.wikipedia.org/wiki/Earley_parser
- jules 2y ago
  Earley parsers should not need more than O(n^2) memory.
- orlp 2y ago
  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.
  - gamegoblin 2y ago
    Yes, the llama.cpp work supports arbitrary CFGs, not just JSON

tcdent 2y ago

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?

gamegoblin 2y ago
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.
- nickreese 2y ago
  Thank you for this explanation. A few things just clicked for me.

BoorishBears 2y ago

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

Der_Einzige 2y ago

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-poets-too-an-ai-1 https://paperswithcode.com/paper/most-language-models-can-be...