Show HN: LLMs can generate valid JSON 100% of the time (github.com)

We can extend our approach to grammar-based sampling, as explained in the paper linked above. Relevant PR: https://github.com/normal-computing/outlines/pull/178

Our method is much more efficient. llama.cpp loops over the entire vocabulary (~50k tokens) at each step to generate the mask. We generate an index at initialization, and building the masks at each step only requires a dictionary lookup (trade speed for memory). Sampling is just as fast as standard sampling.

We also had an implementation of grammar-driven guidance around the same time: https://github.com/normal-computing/outlines/pull/131. I imagine many others did as well, given all the papers we found on the subject. The point of this and our ongoing work is the availability of very low cost guidance, which was implemented a while ago for the regex case and expanded upon with JSON.

Thanks for bringing this library to my attention! From my understanding, TypeChat proceeds by (1) generating (2) attempting validation (3) if it fails, call the LLM again to fix the output (4) etc.

Our method on the other guarantees that the output will follow the specs of the JSON schema. No need to call the LLM several times.

TypeChat: let's try really hard to try to convince the model to make the highest-scoring tokens follow the grammar we want.

Guidance (and this project?): Let's not even bother with trying to convince the model; instead, we'll only sample from the set of tokens that are guaranteed to be correct for the grammar we want to emit.

That's what we noticed as well, and we were not satisfied with the `guardrails` approach of just rejecting invalid outputs. The method makes the interface robust.

Two differences:

(1) This feature only requires regex-guided generation. We have a PR for BNF sampling that is about to be merged. (2) ggml loops over the entire vocabulary (~50k tokens) at each step, which introduces a noticeable overhead, and makes it unusable for complex grammars. Our method works by building an index at initialization, and build the masks at each step with a dictionary lookup. Once the index is built, generation is just as fast as standard generation. Doesn't depend on the complexity of the grammar, the size of the LLM or its vocabulary size.

It took some iterations but I've managed to get the OpenAI API to give me valid JSON 100% of the time now(based on my testing). I think I put in the prompt to never use newlines because it was causing issues lol.

I've had more luck with getting it to output XML as (1) You can imbue XML with actual language/meaning (which LLMs adore) and (2) parsers can be made to be more forgiving. I get why people want to make JSON, but to me it's a bit like trying to get a cat to swim - you might eventually succeed, but it's not their natural inclination.

I wonder if the next iteration of OpenAI features is something like:

right now you can inject prompts that the LLM takes into consideration before the output

I wonder if you can make it have a "post" generation function that says like "keep re-trying in a loop (aka hallucinating with randomness) until the output message passes XYZ format/checks/scoring"

Yeah same thing. I have done the same with GPT-3.5. Simply ask it to output using provided schema only and give a few examples. Always outputs in provided json format

What about using ChatGPT’s new function calling mechanism?

This is what we do, but for GPT-3.5. And it doesn't need to be system messages either. We even have it emitting only JSON in a specific structure (except for when it fails to produce an output altogether). This is without the function calling model.

What about reprompting with a different temperature value?

If this works, how to select the optimal value? Maybe you can train a model that can excel at the task of querying gpt4 for valid jsons

That re-prompting on error trick is what this new Microsoft library does, too: https://github.com/microsoft/TypeChat

Here's their prompt for that: https://github.com/microsoft/TypeChat/blob/c45460f4030938da3...

I think the approach using grammars (seen here, but also in things like https://github.com/ggerganov/llama.cpp/pull/1773 ) is a much more elegant solution.

With ChatGPT function calling I get valid JSON 100% of the time from GPT-4 unless I have made some error in prompting.

The chief error is not providing escape hatches. LLMs look for a right answer. If you are feeding it some texts and asking it to return structured data about the texts, but then one of the texts is blank, it will be difficult to determine a right answer, so you get hallucinations. The solution is an escape hatch where one of the arguments is a `textIsMissing` boolean or something.

As long as you've accounted for these failure modes, it works flawlessly.

Meh... I asked GPT4 to return a sample PHP code inside of a random JSON. It failed the JSON linter from the very first try. I actually couldn't pass the validation despite many retries, eg follow up corrections. Not a single time it generated a 100% valid JSON, I eventually gave up.

I see grammar constrained generation for 2 major advantages:

1. It consumes fewer tokens, no need to add too many examples into the prompt.

2. It suffers less from the forgetting issue.

Another minor advantage is you can control precisely where your desired output to begin with.

But overall, those are nice perks not too substantial IMO.

>I can make GPT4 return valid JSON simply by providing examples in the system message. This works nine times out of ten

But you can do both. For my current use case of extracting information from articles, I have a json schema + one/two example articles along with their correct answers. This increases token costs but 3.5 is so cheap that it doesn't matter and for 4 you can use batching to decrease token cost per article.

Thanks! We have extended the approach to grammar-based sampling. We describe the approach in the paper linked above. The following PR is relevant: https://github.com/normal-computing/outlines/pull/178

> it's astounding that the first-party platforms haven't done this yet

I was under the impression LLM tech is currently in a breakneck arms race and that things are dramatically changing every few months. It could simply just be a consequence of limited developer resources. It would be "astounding" if decade-old tech were missing such a fundamental feature, but for AI tech in arms-race mode it seems reasonable that they are still missing QoL features.

Hi, the paper at https://arxiv.org/abs/2306.10763 titled "Guiding Language Models of Code with Global Context using Monitors" shows how to have the language models generate code without hallucinated dereferences.

Indeed. And we're able to update the mask with a dictionary lookup instead of looping over the entire vocabulary (slow!).

It’s actually a very old trick. Lots of libraries do this. idk what’s the big deal about this one.

You would also need to keep generating until the whole string is valid. And what if it gets caught in a loop?

Not sure how this can really guarantee 100%

You also need some kind of beam search or rejection sampling since JSON tokens to not exactly correspond to logits.

edit: They describe this more carefully in the paper.

Thank you! Hope this helps and opens many applications :)

This is really great too, I am building self-generating experiments and molecular simulations with https://atomictessellator.com and I am going to try out this framework after work

Thanks for bringing clownfish and relm to my attention! afaik other libraries loop over the entire vocabulary at every step of the generation. We on the other hand build an index at initialization by looping once over the vocabulary. Then generation is just as fast as standard generation.

>OpenAI has this capability built in with functions

From OpenAI's docs:

> note: the model may generate invalid JSON

I would guess they don't use your method - and perhaps they should!

I do the same, just tell Openai to call a parser at the end and wahal.

Indeed, this remains an empirical question.

It can't be less sensible JSON than syntactically invalid JSON. All the tokens higher on the list are syntax errors.

Exactly my concern. If the model isn't sure-footed about the path forward, it seems prudent to take that fact as information and adjust the initial conditions, rather than forcing the model into a potentially hallucinatory idea-space.

More concretely, sometimes it is not enough to simply constrain the next token, backtracking might end up being better.

Each time you run an LLM on a sequence of tokens, it generates a probability distribution giving each token's likelihood of occurring next in the sequence. To actually determine the next token in the sequence, any of various strategies can be used to select from that probability distribution.

The challenge in guided generation is conforming the output sequence with a formal language such as a JSON schema or even a rigorously grammatical version of English; typically in a formal language, most tokens in the vocabulary will be _impossible_ as next token candidates rather than merely unlikely. The authors explain that most guided generation systems are checking each token in the vocabulary to see if it would be a valid continuation of the sequence, filtering the probability distribution according to formal constraints before making the next token selection. The authors improve upon this process by indexing valid next tokens according to a formal language recognizer's possible states, so that the list of valid next tokens can be looked up in constant time rather than testing every token in the vocabulary.

With the valid next token options in hand, the probability distribution for next tokens is filtered and then a selection is made.

This analogy falls apart because the spellchecker is separate from the author, and doesn’t know what the author intended.

Here, the LLM is still dictating the token probabilities, so the content will be as correct as the LLM can make it, given the constraints. AIUI, the sampler is just choosing tokens on a combination of probability and syntactic correctness, instead of strictly on probability.

If the LLM is forced to provide a numeric temperature for Seattle, and the input doesn’t contain that data, then obviously the LLM will be forced by the sampler to provide a random answer if the sampler will accept nothing else, much like a human who is forced to mark “true”/“false” on an online form, with no option to reject the question and explain that the question isn’t even a true/false question.

I don’t know about this specific implementation, but it seems important to design systems like this to always “accept” (sample for) an error response from the LLM so that it can hopefully reject invalid requests.

But, yes, all the usual caveats about LLMs apply. It can’t provide correct answers to things it doesn’t know. Forcing it to respond with the answer to the life, the universe, and everything is not going to provide a meaningful response. Even things it “knows”, it can still get wrong sometimes.

This isn't really an interesting question is it? Everyone knows that chatgpt is not an oracle. It doesn't need to output the correct information 100% of the time.

You can go pretty deep once you get context free grammars. For example, I'm using torch-grammar (but outlines should be able to do the same thing once CFG support is merged) to not just restrict the format of a generation to a DSL's syntax, but to restrict the keys it updates to valid keys in a known set.

e.g.:

    int_key ::= DQUO ("f" ("e" ("atured-" ("b" ("log." ("p" ("ost_limit" | "a" ...

Obviously, yeah, it doesn't "understand" the content, but that's what the LLM is for. It's remarkable how plausible the generations you can get out of random noise are with a sufficiently-restrictive grammar. Bolting that onto a well-trained LLM is pretty powerful.

I just left a comment along these lines, but realistically it's probably cheaper to just re-emit than to add the machinery that enables this to their existing architecture.

At most I could have seen them maybe running a schema validator against the output and re-requesting on your behalf, but even that's probably cheaper for them to do client side (I will say, I'm surprised their API wrapper hasn't been updated to do this yet)

I think this is likely a consequence of a couple of factors:

1. Fancy token selection w/in batches (read: beam search) is probably fairly hard to implement at scale without a significant loss in GPU utilization. Normally you can batch up a bunch of parallel generations and just push them all through the LLM at once because every generated token (of similar prompt size + some padding perhaps) takes a predictable time. If you stick a parser in between every token that can take variable time then your batch is slowed by the most complex grammar of the bunch.

2. OpenAI appears to work under the thesis articulated in the Bitter Lesson [i] that more compute (either via fine-tuning or bigger models) is the least foolish way to achieve improved capabilities hence their approach of function-calling just being... a fine tuned model.

[i] http://www.incompleteideas.net/IncIdeas/BitterLesson.html

IANA{LLM}, but if you're only sampling from a "correct" grammar, you are potentially (very potentially) forgoing what might otherwise have been a more desirable and more semantically useful token. Most of the models have been trained on myriads of human language, not structured data necessarily, and so I'd rather elect for a more semantically enriched format (e.g. XML or YAML) because those are designed to be ~more human readable. Or perhaps more preferably: have the boss LLM pump out what it excels at (strings of prose most of the time) and have a secondary model with a stricter grammar convert that to JSON.

With our indexing approach, it only costs a dictionary lookup to get the next valid tokens during each sampling step, so very little latency.

The underlying approach can improve the performance of anything that requires the set of non-zero probability tokens at each step, and anything that needs to continue matching/parsing from a previous state.

Generating valid JSON that conforms to a given schema is pretty useful, although not impressive by itself. If the model can deduce field values from schema alone though, I think it's pretty neat.

Or JSON that correctly answers what the prompt is asking.

"" valid!

There are already models generating useful JSON. Sometimes they generate what would be useful JSON, but it’s not valid. This makes sure it’s always valid. It’s an improvement.

jsonformer uses a template rather than a DFA. The logit masking seems to be identical, though.

Figure 2 in our paper (https://arxiv.org/abs/2307.09702) shows the difference between guidance and outlines to generate a sequence that is valid to a regex. Jsonformer uses the same technique as guidance. Extrapolate this to several fields.

Note that we still need to manage the KV cache in outlines. It’s a small interface change that will be made this week hopefully, but we’ve been focusing on constrained generation so far.

Ha, yeah, in a distant, but really fun, past!

It can be used with any open source model (if you can get the logits), and to some extent with OpenAI's API. Here is an example with `transformers`: https://github.com/normal-computing/outlines#efficient-json-...

We plan on adding more model integrations, but it is completely decoupled from the method implementation.

I'm not sure of why you would want to use raw llama-2 though when there is a million super strong instruction fine-tuned versions of llama-2 on HF hub that would do the job a million times better? Like Stability-AI's Beluga-2. See https://huggingface.co/spaces/HuggingFaceH4/open_llm_leaderb...

About your second point, the goal is that the model can only generate JSON (for example), which can 100% be done by constraining which output token can and cannot be used.

> ...given an instruction-tuned model, post-hoc masking of the state-space during generation then amounts to just changing the generation distribution...

Isn't that what we did with test driven development?

The primary difference was our generator functions were human instead of LLM. Why not cut out the middle-human?

>you do need a fair bit of instruction-tuning for specific use cases to actually get things to work.

The instruction tuning part is "trivial"...it's the dealing with edge cases part that gets me.

With classic code edge cases are well insignificant edge cases. With LLM you never know what will make it go off on a tangent & the parsing code needs to deal with that chaos.

Or put differently the % of cases that are edge cases seems to have gone up dramatically

I'm quite impressed with Llama 2 13B - the more time I spend with it the more I think it might be genuinely useful for more than just playing around with local LLMs.

I'm using the MLC version (since that works with a GPU on my M2 Mac) via my https://github.com/simonw/llm-mlc plugin.

In our experience, at least for code generation, the experience has been that base models can be improved significantly by guiding token level generation.

In our paper titled "Guiding Language Models of Code with Global Context using Monitors" (https://arxiv.org/abs/2306.10763), we propose Monitor Guided Decoding, which interfaces LLMs to static analysis, and guides the model to generate type-consistent code. Without any kind of fine-tuning, we show that using static analysis to guide token level generation at specific points leads to significantly improved quality of generated code, both in terms of compilability and match with ground truth. Even very small models (1.1B) are able to generate more compilable code than much larger models (175B) while also improving on match with ground truth.

No. You need to hook into the LLM at a lower level. One API call typically triggers a generation of a sequence of tokens and this library has to poke into things between each generated token.