4 ms·

This also applies to LLM constrained generation. Instead of outputting something that promised to be a JSON (but maybe it's not, or maybe it's an incomplete JSO

This also applies to LLM constrained generation. Instead of outputting something that promised to be a JSON (but maybe it's not, or maybe it's an incomplete JSON, or maybe it's a JSON but doesn't conform to your JSON schema), just use CFGs (e.g., GBNF) to guide the model to generate the exact JSON you want. It's guaranteed, and you don't have to send lengthy JSON schemas to the LLM.

hansvm 2y ago
With the caveat that you significantly change the distribution of the output. Picking on JSON with current-gen LLMs, consider (1) Retry till the output passes the grammar (2) Only generate tokens passing the grammar Assuming (2) actually runs (not guaranteed for all grammars and distributions theoretically, basically never a problem in practice), one of many common failure modes is forcing the generation of grammar-valid tokens after an error has been made. E.g., one sort of "truncation" error happens when the LLM is producing an object with metadata around a transcription (e.g., an author, timestamp, and blob of text). A common incorrect result looks like {"author": "John Doe", "timestamp": "20:23:58", "transcript": "My name is John Doe, and ... Those ellipses weren't just cutting off my description of the invalid data. The model will produce ellipses after the string carries on for too long. If you greedily produce tokens adhering to a grammar, your only options at that point are continuing the string and ending it, and both options are very wrong. Contrast that with option (1). Empirically, if the model is willing to actually produce those tokens rather than cut off its answer, it's much more likely to be correct (i.e., the presence of that ellipses bug will tend to cut off the entire response, not just truncating the string and still generating a valid object). If you just retry till the model succeeds then you have a substantially higher accuracy in that task. That particular example may or may not apply to your favorite problem and favorite model, but it highlights the problem that constraining to a grammar forces a large skew in your result distribution. A large part of the power of an LLM is its autoregressiveness, and other sampling algorithms only tend to perform well when there's some outside knowledge relevant to the real-world problem being solved (e.g., if the LLM has >50% accuracy on a task with a small, finite number of outputs, then you might want to drop the temperature to 0 and just sample repeatedly, selecting the most likely option), but messing with the result distribution without a rationale for why you're still likely to get good results is risky.
- behnamoh 2y ago
  Let's say the grammar forces a JSON like this: {"transaction_number": <number>} Is this also problematic? My understanding is that the model is first forced to generate "transaction_number", which then hints to the model that it must generate the number of the transaction, not something else. I understand that maybe the model didn't want to start writing "transaction_number" without enforcing the grammar, but after being forced to, it has to only continue the generation.
  - hansvm 2y ago
    In general, all bets are off. The model has a certain auto-regressive property (a factoring of conditional probabilities), and every other sampling should be examined with extreme suspicion. At a bare minimum, a lot of real-world problems in your desired domain should be spot-checked. For more constrained examples like that, you're probably a lot safer than with completely unconstrained strings. Even for very simple constraints like that, it's not terribly hard to imagine exactly the same ellipses problem (especially if your chosen JSON grammar isn't very careful with unbounded vs 53-bit integers). You really want a non-negative integer, you're using JSON and don't want to roll your own grammer so you use an off-the-shelf JSON LLM CFG toolkit of some flavor, and you allow _numbers_ in that field. I haven't personally seen ellipses bugs after only a few dozen characters in current-gen LLMs, but to have something concrete talk about let's say your model "tries" to write a transaction_number of 3141592635.... They want to truncate the actual result with an ellipsis. On the first period, the only allowable results include more digits (the grammar prevents the actual ellipsis from happening). You successfully adhere to the grammar and have garbage in that field, where a simple retry loop would have likely completed correctly. Assuming the grammar actually correctly restricts to just a non-empty contiguous sequence of digits in that spot, that's _harder_ to force a bug into, but it's not impossible. For starters, the whole thing is probabilistic. Suppose the model uses "0" as the first digit. The only remaining valid (integer) JSON is finishing the field. Multiple leading zeros's aren't allowed. If for _any_ reason the model is more likely to produce invalid JSON after incorrectly using a "0" for the first digit, the grammar-constrained implementation will have more errors than a basic retry loop. You can probably do something clever with changing the sampling temperature based on which part of the grammar you're in to side-step some of those issues. You might also find that for a particular problem my theoretical complaints don't seem to apply in practice. Maybe, for business reasons, past a certain accuracy rate you value being able to write simpler code (i.e., assume valid JSON) even if you dip down from 99% to 98% accuracy on a task. Nothing I've outlined says "don't guide an LLM with grammars." Do be careful with it though and consciously consider the task at hand and your proposed solution. It's not a free lunch.

hansvm 2y ago

With the caveat that you significantly change the distribution of the output. Picking on JSON with current-gen LLMs, consider (1) Retry till the output passes the grammar (2) Only generate tokens passing the grammar Assuming (2) actually runs (not guaranteed for all grammars and distributions theoretically, basically never a problem in practice), one of many common failure modes is forcing the generation of grammar-valid tokens after an error has been made. E.g., one sort of "truncation" error happens when the LLM is producing an object with metadata around a transcription (e.g., an author, timestamp, and blob of text). A common incorrect result looks like {"author": "John Doe", "timestamp": "20:23:58", "transcript": "My name is John Doe, and ... Those ellipses weren't just cutting off my description of the invalid data. The model will produce ellipses after the string carries on for too long. If you greedily produce tokens adhering to a grammar, your only options at that point are continuing the string and ending it, and both options are very wrong. Contrast that with option (1). Empirically, if the model is willing to actually produce those tokens rather than cut off its answer, it's much more likely to be correct (i.e., the presence of that ellipses bug will tend to cut off the entire response, not just truncating the string and still generating a valid object). If you just retry till the model succeeds then you have a substantially higher accuracy in that task. That particular example may or may not apply to your favorite problem and favorite model, but it highlights the problem that constraining to a grammar forces a large skew in your result distribution. A large part of the power of an LLM is its autoregressiveness, and other sampling algorithms only tend to perform well when there's some outside knowledge relevant to the real-world problem being solved (e.g., if the LLM has >50% accuracy on a task with a small, finite number of outputs, then you might want to drop the temperature to 0 and just sample repeatedly, selecting the most likely option), but messing with the result distribution without a rationale for why you're still likely to get good results is risky.

behnamoh 2y ago
Let's say the grammar forces a JSON like this: {"transaction_number": <number>} Is this also problematic? My understanding is that the model is first forced to generate "transaction_number", which then hints to the model that it must generate the number of the transaction, not something else. I understand that maybe the model didn't want to start writing "transaction_number" without enforcing the grammar, but after being forced to, it has to only continue the generation.
- hansvm 2y ago
  In general, all bets are off. The model has a certain auto-regressive property (a factoring of conditional probabilities), and every other sampling should be examined with extreme suspicion. At a bare minimum, a lot of real-world problems in your desired domain should be spot-checked. For more constrained examples like that, you're probably a lot safer than with completely unconstrained strings. Even for very simple constraints like that, it's not terribly hard to imagine exactly the same ellipses problem (especially if your chosen JSON grammar isn't very careful with unbounded vs 53-bit integers). You really want a non-negative integer, you're using JSON and don't want to roll your own grammer so you use an off-the-shelf JSON LLM CFG toolkit of some flavor, and you allow _numbers_ in that field. I haven't personally seen ellipses bugs after only a few dozen characters in current-gen LLMs, but to have something concrete talk about let's say your model "tries" to write a transaction_number of 3141592635.... They want to truncate the actual result with an ellipsis. On the first period, the only allowable results include more digits (the grammar prevents the actual ellipsis from happening). You successfully adhere to the grammar and have garbage in that field, where a simple retry loop would have likely completed correctly. Assuming the grammar actually correctly restricts to just a non-empty contiguous sequence of digits in that spot, that's _harder_ to force a bug into, but it's not impossible. For starters, the whole thing is probabilistic. Suppose the model uses "0" as the first digit. The only remaining valid (integer) JSON is finishing the field. Multiple leading zeros's aren't allowed. If for _any_ reason the model is more likely to produce invalid JSON after incorrectly using a "0" for the first digit, the grammar-constrained implementation will have more errors than a basic retry loop. You can probably do something clever with changing the sampling temperature based on which part of the grammar you're in to side-step some of those issues. You might also find that for a particular problem my theoretical complaints don't seem to apply in practice. Maybe, for business reasons, past a certain accuracy rate you value being able to write simpler code (i.e., assume valid JSON) even if you dip down from 99% to 98% accuracy on a task. Nothing I've outlined says "don't guide an LLM with grammars." Do be careful with it though and consciously consider the task at hand and your proposed solution. It's not a free lunch.