21 ms·
Show HN: LLMs can generate valid JSON 100% of the time
Outlines is a Python library that focuses on text generation with large language models. Brandon and I are not LLM experts and started the project a few months ago because we wanted to understand better how the generation process works. Our original background is probabilistic, relational and symbolic programming.
Recently we came up with a fast way to generate text that matches a regex (https://blog.normalcomputing.ai/posts/2023-07-27-regex-guided-generation/regex-guided-generation.html https://blog.normalcomputing.ai/posts/2023-07-27-regex-guide...). The basic idea is simple: regular expressions have an equivalent Deterministic-Finite Automaton (DFA) representation. We can transform this DFA into a generative model: in each state we get a list of symbols which correspond to completions that partially match the regular expression. We mask the other symbols in the logits returned by a large language model, sample a new symbol and move to the next state. The subtelty is that language models work with tokens, not symbols, so we derive a new FSM whose alphabet is the model's vocabulary. We can do this in only one pass over the vocabulary.
Generating the token masks thus only requires a dictionary lookup at each state. Our method blows other libraries like Microsoft's guidance out of the water.
From there it was only a small leap to be able to generate text that follows a JSON schema (https://json-schema.org/ https://json-schema.org/), or is parseable into a Pydantic model (https://docs.pydantic.dev/latest/usage/models/ https://docs.pydantic.dev/latest/usage/models/). The method works with union types, optional types, nested schemas, arrays, everything. It is guaranteed that the output is parseable.
I think it's cool, and I've spent a lot of time watching even tiny models output valid JSON over the weekend. Hope you will too.
I look forward to feedback, bug reports, feature requests and discussions!
Edit: Link to our pre-print explaining the method and how this can be extended to generate text that follows a Context-Free Grammar https://arxiv.org/abs/2307.09702 https://arxiv.org/abs/2307.09702
- gsuuon 3y agoGenerating an FSM over the vocabulary is a really interesting approach to guided sampling! I'm hacking on a structured inference library (https://github.com/gsuuon/ad-llama https://github.com/gsuuon/ad-llama) - I also tried to add a vocab preprocessing step to generate a valid tokens mask (just with regex or static strings initially) but discovered that doing so would cause unlikely / unnatural tokens to be masked rather than the token which represents the natural encoding given the existing sampled tokens. Given the stateful nature of tokenizers, I decided that trying to preprocess the individual token ids was a losing battle. Even in the simple case of whitespace - tokenizer merges can really screw up generating a static mask, e.g. we expect a space next, but a token decodes to 'foo', but is actually a '_foo' and would've decoded with a whitespace if it were following a valid pair. When I go to construct the static vocab mask, it would then end up matching against 'foo' instead of ' foo'. How did you work around this for the FSM approach? Does it somehow include information about merges / whitespace / tokenizer statefulness?
- IanCal 3y agoI tried slight modifications from the example pydantic model and it's incredibly slow. Maybe I'm doing something wrong but I've a hefty box and a 3090, an example using gpt-2 doesn't seem like it should be that taxing.
- remilouf 3y agoIt is currently limited by the time it takes to build the index. There are obvious optimizations we can apply to this, however in a production setting it does not matter much since you only need to build the index once for each (schema, vocabulary) pair.
- IanCal 3y agoIs there a rough guide as to how long to wait? I think it's definitely an important thing if building takes 10+ minutes (or hours?) for even very basic models, that's a fundamentally different production architecture (as launching from a blank slate is now not feasible). It's also a big devx issue. I'd highlight this somewhere on the readme as I wasn't sure if it was just broken or how long to wait.
- Cholical 3y agoThis looks great!
- sneedchucker 3y agoRelevant; LLama.cpp implemented grammar-based sampling last month. https://news.ycombinator.com/item?id=36819906 https://news.ycombinator.com/item?id=36819906 https://github.com/ggerganov/llama.cpp/pull/1773 https://github.com/ggerganov/llama.cpp/pull/1773
- remilouf 3y agoWe 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 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.
- popinman322 3y agoIt should hopefully be a quick change to llama.cpp to add a mask per grammar state to bring it in line with your generation method; I don't think the two are incompatible, thankfully. I do wonder how much you win here by masking the tokens? You still need to iterate along the output vector to apply the mask. Masking on the accelerator still requires filtering on the CPU side? Compared to running the language model, the cost of iterating over the edges in the grammar seems small.
- burke 3y agoYes! This is closer to the approach I took in my port of llama.cpp's grammar support to PyTorch: https://github.com/Shopify/torch-grammar/blob/main/torch_grammar/grammar_sampler.py#L203-L212 https://github.com/Shopify/torch-grammar/blob/main/torch_gra... ... it generates a tensor mapping each PDA stack to a map of which tokens are acceptable from that state. It seems like a much better way to do it than looping over the sampled tokens on each turn.
- btwillard 3y agoWe also had an implementation of grammar-driven guidance around the same time: https://github.com/normal-computing/outlines/pull/131 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.
- Deukhoofd 3y agoLooks interesting! How would you say it compares to Microsoft's TypeChat (beyond the obvious Python/TypeScript difference)? https://microsoft.github.io/TypeChat/blog/introducing-typechat/ https://microsoft.github.io/TypeChat/blog/introducing-typech...
- remilouf 3y agoThanks 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.
- 1wheel 3y agoThere's also https://lmql.ai/ https://lmql.ai/
- remilouf 3y agoLQML (and guidance https://github.com/guidance-ai/guidance https://github.com/guidance-ai/guidance) are much more inefficient. They loop over the entire vocabulary at each step, we only do it once at initialization.
- potatoman22 3y agoDoes looping over the vocabulary add much overhead to the tok/s? I imagine they're just checking if the input is in a set, and usually there's only ~30k tokens. That's somewhat intensive, but inference on the neural net feels like it'd take longer.
- remilouf 3y agoThey’re checking regex partial matches for each possible completion, which is intensive indeed. You can look at the Figure 2 in our paper (link in original post) for a simple comparison with MS guidance which shows the difference.
- Havoc 3y agoThat looks intriguing. Managing that interface has proven challenging - especially on data cleaning tasks where the model ends up talking rather than doing. Bit more guiderails would be helpful on that
- remilouf 3y agoThat'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.
- spott 3y agoHow does this relate to ggmls bnf sampling?
- remilouf 3y agoTwo 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.
- spott 3y agoRegex-guided gen is slick… is it arbitrary? Or are you custom building it for json? If arbitrary, how are you pre-defining a set of masks? I would expect that splitting an arbitrary regex into a bunch of contexts for a masking dictionary to be non-trivial.
- remilouf 3y agoRegex-Gen is implemented in all generality in the library (minus some constructs that we still have to add). JSON is merely an application. You can read https://blog.normalcomputing.ai/posts/2023-07-27-regex-guided-generation/regex-guided-generation.html https://blog.normalcomputing.ai/posts/2023-07-27-regex-guide... for a more detailed explanation of how it works. Should answer your question :)
- panarky 3y agoI can make GPT4 return valid JSON simply by providing examples in the system message. This works nine times out of ten. But it's still probabilistic, and nine times out of ten isn't good enough. Occasionally it will hallucinate responses like this: {"key1": "value1", "key2": "value2" for i in range(n)} Re-prompting with the parsing error message is usually enough to get it on the second try. But escaping double-quotes and newline characters is less reliable. Even after giving it multiple examples, it correctly escapes only about half the time. Re-prompting for escaping errors still yields a ~50% success rate.
- keiferwiseman 3y agoIt 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.
- padolsey 3y agoI'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.
- gowld 3y agoHow do you imbue XML with meaning?
- padolsey 3y agoXML Elements themselves: their naming, their attributes, comments, indentation. There's more opportunity at every level of the hierarchy to demarkate and establish meaning. Having closing-tags as well, I've found, is a massive boon; LLMs can better understand what "finishing" looks like if its delimited in a semantic way - with a name.
- xigency 3y agoThanks for building this. The mechanics are such an obvious idea that it's astounding that the first-party platforms haven't done this yet. I would be interested to see how this could be used for other tasks outside of JSON that require structured input.
- remilouf 3y agoThanks! 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 https://github.com/normal-computing/outlines/pull/178
- Lerc 3y agoCould this same approach be applied at training? If the guidance does a lot of the syntactical heavy lifting, would that create the opportunity for a model to use the weights for something else. Essentially not bothering to reduce the error of things that the guidance will stomp on anyway.
- umvi 3y ago> 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.
- winwang 3y agoI think they meant that you'd expect simpler/more obvious ideas to be implemented first.
- LakshyAAAgrawal 3y agoHi, the paper at https://arxiv.org/abs/2306.10763 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.
- J_Shelby_J 3y agoSo to explain this another way: After each token generated by the LLM you update the logit bias “mask” to only allow the next token to be a valid json token? Very slick!
- remilouf 3y agoIndeed. And we're able to update the mask with a dictionary lookup instead of looping over the entire vocabulary (slow!).
- deleted 3y ago[deleted]
- behnamoh 3y agoIt’s actually a very old trick. Lots of libraries do this. idk what’s the big deal about this one.
- remilouf 3y agoPerhaps I didn’t explain clearly enough in the original post?
- dontreact 3y agoYou 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%
- orlp 3y ago> And what if it gets caught in a loop? Not sure how this can really guarantee 100% It's not great but after some timeout you can just set the mask to only include closing brackets.
- aassddffasdf 3y agoYou would still have to ensure balancing somehow. Both "]" and "}" are valid "closing brackets" and the correct one to choose is context-dependent.
- thatcherthorn 3y agoThis is awesome. I have a vision to build self-managed software. This will be a great tool.
- BoorishBears 3y agoI'm not sure how this is different than: https://github.com/1rgs/jsonformer https://github.com/1rgs/jsonformer or https://github.com/newhouseb/clownfish https://github.com/newhouseb/clownfish or https://github.com/mkuchnik/relm https://github.com/mkuchnik/relm or https://github.com/ggerganov/llama.cpp/pull/1773 https://github.com/ggerganov/llama.cpp/pull/1773 or https://github.com/Shopify/torch-grammar https://github.com/Shopify/torch-grammar Overall there are a ton of these logit based guidance systems, the reason they don't get tons of traction is the SOTA models are behind REST APIs that don't enable this fine-grained approach. Those models perform so much better that people generally settle for just re-requesting until they get the correct format (and with GPT-4 that ends up being a fairly rare occurrence in my experience)
- remilouf 3y agoThanks 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.
- burke 3y agotorch-grammar generates a mask per PDA stack... we don't try to compute all the possible stacks. I'm sure there's something smarter that could be done here and you've probably figured it out (though IIRC regular languages don't have the arbitrarily recursive stack problem that you get when you get to context-free languages?) anyway, in practice we spend a few milliseconds on the first few requests building caches and then just apply masks from caches after that.
- remilouf 3y agoSorry for misrepresenting your work. Thank you for correcting me and the explanation. Will take a closer look.
- mkuchnik 3y agoHi, author of ReLM here. We use automata as well, like you describe, if I understand correctly.
- Ilasky 3y agoOpenAI has this capability built in with functions[0], I believe! Building my own project[1] I have implemented functions in combination with guidance[2] and haven’t had a hiccup yet! I have a JSON parser function there, just in case, but it seems to be working reliably. Here’s a bit more of a description of using the functions API for JSON returns: https://yonom.substack.com/p/native-json-output-from-gpt-4 https://yonom.substack.com/p/native-json-output-from-gpt-4 [0] https://openai.com/blog/function-calling-and-other-api-updates https://openai.com/blog/function-calling-and-other-api-updat... [1] https://resgen.app https://resgen.app [2] https://github.com/guidance-ai/guidance https://github.com/guidance-ai/guidance
- londons_explore 3y ago>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!
- Ilasky 3y agoGood catch! It really is a combination of guidance guaranteeing JSON output and OpenAI getting it right a good majority of the time[0]. But yeah, I can see how it can be frustrating that the JSON output is not guaranteed by the docs. [0] >>99% in my experience
- Ilasky 3y agoThat said, I am definitely going to look into this library and compare its results to guidance, since they claim it blows it out of the water (which is very enticing!)
- remilouf 3y agoFigure 2 in our paper (https://arxiv.org/abs/2307.09702 https://arxiv.org/abs/2307.09702) shows the difference for a single regex.
- 3y ago
- Scene_Cast2 3y agoOne potential drawback I can see is if the viable tokens are far down the list of predictions. In that case, filtering down to just those tokens is a distribution shift with resulting output being less stable / less sensible.
- remilouf 3y agoIndeed, this remains an empirical question.
- Scarblac 3y agoIt can't be less sensible JSON than syntactically invalid JSON. All the tokens higher on the list are syntax errors.
- skybrian 3y agoIt seems unlikely for JSON, but this might indicate that the model has somehow painted itself into a corner and the best thing to do is backtrack? Regenerating the entire response could be seen as an extreme form of backtracking.
- haswell 3y agoThat depends highly on the values contained within the JSON. Syntactically correct is only useful if the rest of the content is useful.
- pshc 3y agoExactly 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.
- potatoman22 3y agoWhat are characteristics of a "hallucinatory idea-space"? If you're enforcing the model outputting a closing bracket instead of a random string of numbers, that seems like a win for JSON formatting.
- coding123 3y agoCan someone re-explain all of this. If I got to GPT3.5 and ask it to give me some information in json, vs whatever this library is doing?
- odyssey7 3y agoEach 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.
- Animats 3y agoOK, you get syntactically valid JSON, but does it contain the correct info? This is effectively a polisher, like spell check, which gives the output superficially correct form but doesn't understand the content. Right?
- coder543 3y agoThis 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.
- chipsrafferty 3y agoWhy isn't it possible to design LLMs that say "I don't know"?
- coder543 3y agoIt is possible… ChatGPT4 says that all the time. It’s just not guaranteed that an LLM will recognize that it doesn’t know a particular answer every time. I had even already mentioned in the comment you’re replying to that you should leave room in the sampler to allow the LLM to provide error responses. I never said it wasn’t possible. Not to anthropomorphize LLMs too much, but humans will also sometimes respond confidently with a wrong answer too. Both LLMs and humans will sometimes say the wrong thing when they don’t actually know an answer, but sometimes (hopefully most of the time) they will instead say that they don’t know the answer. Contrary to another response here, I do not believe it's a good mental model to say that LLMs only respond "I don't know" only when they have specifically memorized that they don't know a fact. When you're dealing with tens or hundreds of billions of parameters, the "why" is often elusive and complicated. It's also probabilistic; it may respond that it doesn't know one time, but the next time, it may unfortunately claim to know an answer it doesn't know -- which is a form of hallucination. If it was just about memorization, then it wouldn't be probabilistic. Reducing hallucinations is one of the major goals of LLM research today, and ChatGPT4 performs much better in this area than ChatGPT3.5 did. Here is a quick example of ChatGPT4 saying it doesn’t know: https://chat.openai.com/share/7b72b109-fb84-4988-891b-f2eecc4ce582 https://chat.openai.com/share/7b72b109-fb84-4988-891b-f2eecc... I'm sure no one at OpenAI specifically trained ChatGPT4 to recognize a question about the Stanley Cup and respond that it doesn't know the answer, but it still said that it didn't know. It absolutely did not start a sentence with "the winner of the 2023 Stanley Cup was..." and then wander its way into a bad answer. That's not a good representation of how this stuff works, even though it does sample one token at a time.
- 2bitencryption 3y agoit still blows my mind that OpenAI exposes an API with Functions calling, and yet does not guarantee the model will call your function correctly, in fact, it does not even guarantee the output will be valid JSON. When this is, really, a solved problem. I've been using github.com/microsoft/guidance for weeks, and it genuinely, truly guarantees correct output, because it simply does not sample from tokens that would be invalid. It just seems so obvious, I still have no clue why OpenAI does not do this. Like, why fuss around with validating JSON after the fact, when you can simply guarantee it is correct in the first place, by only sampling tokens if they conform to the grammar you are trying to emit?
- BoorishBears 3y agoI 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)
- 2bitencryption 3y ago> maybe running a schema validator against the output and re-requesting on your behalf this is the part that blows my mind. You don't have to do this! You don't have to sample the entire output, and then validate after the fact. You're not required to greedily pick the token with the highest score. You get the scores of all tokens, on every forward pass! So why even waste time picking invalid tokens if you're just going to validate and retry later on?? (note: when I say "you" here, I mean whoever is hosting the model. It is true that OpenAI does not expose all token scores, it only gives you back the highest-scoring one. So a client-side library is not able to perform this grammar-based sampling. BUT, OpenAI themselves host host the model, and they see all token outputs, with all scores. And in the same API request, they allow you to pass the "function definition" as a JSON schema. So why not simply apply that function definition as a mask on the token outputs? They could do this without exposing all token scores to you, which they seem very opposed to for some reason.)
- huevosabio 3y agoVery cool! How much latency does it add?
- btwillard 3y agoWith our indexing approach, it only costs a dictionary lookup to get the next valid tokens during each sampling step, so very little latency.
- popinman322 3y agoDoes this work in tandem with beam search or does it do greedy sampling?
- btwillard 3y agoThe 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.
- tantalor 3y ago"Generating valid JSON" is not impressive. Here's some valid JSON: [] The tricky part is generating useful JSON.
- ape4 3y agoOr JSON that correctly answers what the prompt is asking.
- notpushkin 3y agoGenerating 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.
- AtNightWeCode 3y ago"" valid!
- travisjungroth 3y agoThere 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.
- leetharris 3y agoHow does this compare in terms of latency, cost, and effectiveness to jsonformer? https://github.com/1rgs/jsonformer https://github.com/1rgs/jsonformer
- bhickey 3y agojsonformer uses a template rather than a DFA. The logit masking seems to be identical, though.
- remilouf 3y agoFigure 2 in our paper (https://arxiv.org/abs/2307.09702 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.
- Der_Einzige 3y agoSad to see that my related work on token-level constrained text generation is not cited in the paper: https://github.com/Hellisotherpeople/Constrained-Text-Generation-Studio https://github.com/Hellisotherpeople/Constrained-Text-Genera... https://aclanthology.org/2022.cai-1.2/ https://aclanthology.org/2022.cai-1.2/
- remilouf 3y agoWe're unfortunately only human and didn't catch every single paper on the topic while writing the draft. Thanks for bringing it to our attention.
- aduffy 3y agoThis is exciting, we built a similar tool[1] recently specifically targeted at constraining llama output to match a TypeScript interface. I firmly believe that output format guarantees are going to be important for real (non-toy) decades for LLMs [1] https://github.com/ggerganov/llama.cpp/discussions/2494 https://github.com/ggerganov/llama.cpp/discussions/2494
- ianbutler 3y agohttps://github.com/newhouseb/clownfish https://github.com/newhouseb/clownfish Which I've been using for a while now, also restricts the sampling space to force correct generation, but does so as the result of a different process than yours.
- Q6T46nT668w6i3m 3y agoIs this Brandon Willard the breakdancer from Detroit Brandon Willard? Edit: It is! https://brandonwillard.github.io/ https://brandonwillard.github.io/
- btwillard 3y agoHa, yeah, in a distant, but really fun, past!
- rckrd 3y agoI also released a hosted version of my open-source libraries ReLLM and ParserLLM that already supports APIs for * Regex completion for LLMs * Context-free Grammar completion for LLMs https://thiggle.com/ https://thiggle.com/ [0] https://github.com/r2d4/rellm https://github.com/r2d4/rellm [1] https://github.com/r2d4/parserllm https://github.com/r2d4/parserllm [2] https://github.com/thiggle/api https://github.com/thiggle/api There's also another API on Thiggle that I've build that supports classification via a similar logit-based strategy.
- deleted 3y ago[deleted]
- btbuildem 3y agoI feel like I'm missing something very basic here, but is this library intended to be used with an existing model? If so, could you point to an example?
- remilouf 3y agoIt 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-generation-following-a-pydantic-model https://github.com/normal-computing/outlines#efficient-json-... We plan on adding more model integrations, but it is completely decoupled from the method implementation.
- activatedgeek 3y agoMechanistically, I think this library takes the simple idea of masking part of the vocabulary space and steps in time efficiently. Great! I am curious, however, for the ones who have played around with such libraries wrapping base LLMs with output structure: do base models like Llama2 work very well? My experience says "hell no!" and you do need a fair bit of instruction-tuning for specific use cases to actually get things to work. And even then, it seems very counter-intuitive to me that given an instruction-tuned model, post-hoc masking of the state-space during generation then amounts to just changing the generation distribution, and potentially detrimental to instruction-tuning?
- make3 3y agoI'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_leaderboard 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.
- nabakin 3y agoDon't rely too much on automated benchmarks for LLMs. They are often gamed, made to overfit, and result in worse performance in the general case. Human evaluation is the gold standard and the Llama 2 paper gave significant evidence that Llama 2 70b chat is on-par, if not, better than ChatGPT for that metric so I tend to stick to it unless there is good reason not to.
- huevosabio 3y agoThe problem with Llama 2 chat versions is that they have been RLHF-ed to death. You can't ask questions without getting a sermon of how your question may be inappropriate for this or that reason. I think it's worse on the smaller models, but still present in the 70B one.
- Kiro 3y agoDoes this mean that I need to call the LLM API once for each token?
- baobabKoodaa 3y agoNo. 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.
- Kiro 3y agoCan't I use the max_tokens (set to 1) and logit_bias parameters? Not saying I want to do this. I just want to understand how this works.
- baobabKoodaa 3y agoNot sure exactly what is logit_bias, but after Googling for 5 seconds it seems to be an OpenAI parameter that's not available in HuggingFace transformers? Anyway, if your idea is to make one API call per token, the biggest problem with that approach is that it would be really slow to do that.
- deleted 3y ago[deleted]
- nikcheerla 3y agoDoes this work with GPT-4?
- lettergram 3y agoFew thoughts, you're effectively creating representations that can convert to JSON (kudos!) Can't mention how we did it (there are a lot of public patents, if interested), but back in 2018 we had a way to generate synthetic data (statistically, structurally similar) off any dataset - https://medium.com/capital-one-tech/why-you-dont-necessarily-need-data-for-data-science-48d7bf503074 https://medium.com/capital-one-tech/why-you-dont-necessarily... You could also design datasets if you wanted. It'd keep similar relations and worked pretty darn well. Not the exact same, but always produced valid JSON.
- remilouf 3y agoThank you for the pointer. The best part of posting on HN is the long list of related work you get in response.
- simonw 3y agoI really hope OpenAI add something like this to their endpoints soon. Being able to pass up some kind of grammar (a regular expression, or a JSON schema, or some other format) and have this trick run during their token sampling process to ensure the output was compliant would be incredibly useful.
- joshuanapoli 3y agoIsn't the Function Calling feature meant for this purpose? It guides the LLM to output according to the given schema. The name of the feature is a little misleading. https://platform.openai.com/docs/guides/gpt/function-calling https://platform.openai.com/docs/guides/gpt/function-calling
- simonw 3y agoSurprisingly the function calling mechanism doesn't appear to use this trick - apparently it's still possible to get the wrong JSON structure back from it occasionally.
- tornato7 3y agoFunction Calling is fine-tuned to a certain output format, but it very often strays from that format. My function-calling-handling code has a mess of edge case handlers that catch when GPT-4 is calling functions incorrectly.
- M4v3R 3y agoIt’s not though, they even say it in their docs that sending a schema does not guarantee that the model will actually adhere to the scheme or even produce valid JSON
- potatoman22 3y agoThey recently added logit biases, so that's a start.
- remilouf 3y agoIt's limited to 300 logit biases at a time. Knowing GPT4's vocabulary is ~100k tokens it's not nearly enough to get reliable guided generation. Although it could work in some cases, and another advantage of this work is that we can determine that before generating.
- visarga 3y agoEnforcing JSON schema, regex and grammars is very useful. But how can we enforce decoding spans from a document? decoded text should be copied from a list of spans in the input document. It would be useful for extractive tasks.
- lefttoreader 3y agoThe “trick” seems to blatantly rip off FlashText without citing it? https://arxiv.org/pdf/1711.00046.pdf https://arxiv.org/pdf/1711.00046.pdf I’m a fan of the approach. I normally wouldn’t care if this was just another LLM library taking inspiration, but if you’re going to go out of your way to put a paper on the ArXiv, feels like doing a literature review is a good step?
- deleted 3y ago[deleted]
- verdverm 3y agoCare to explain how a string replacement algorithm relates to nudging the logits of a ML model? I don't see the "rip off", the paper you cite requires a complete document to work on while this work is for guiding the generation of tokens
- lefttoreader 3y agoSure! So it’s hopefully clear that the notion of constrained grammar is not novel (see every comment on here of people name-dropping their implementation from two months ago). The novelty here is “instead of checking whether every token is allowed” to create a finite state machine that defines which tokens are allowable at each generation step. This lets them not check every token at every step. The trick of creating an FSM to efficiently check next-token grammar is what allowed FlashText to run circles around standard regex stuff. Even FlashText guy acknowledged the shoulders he stood on, etc. Let’s be super clear here, none of these standards apply when you’re building good ole libraries. But putting out a paper really elevates what you’re on the hook for. Most folks that write papers are dying to acknowledge the shoulders they stand on - it’s part of the toxic humility we all engage in. Again - shill OSS all day - I’ll upvote it.
- _flux 3y agoBy "standard regex" stuff I take it you mean the standard regex stuff Python standard library comes with? I mean going from standard regex to NFA to DFA is already more sophisticated than that one, it's _quite_ oldschool and gives you linear time matching: https://en.wikipedia.org/wiki/Thompson%27s_construction https://en.wikipedia.org/wiki/Thompson%27s_construction https://en.wikipedia.org/wiki/Powerset_construction https://en.wikipedia.org/wiki/Powerset_construction And what I mean to say by this as they could have easily have had this idea and never had discovered the whitepaper you referenced.
- dvt 3y ago[flagged]
- swyx 3y ago> Imagine thinking that adding regex on top of an LLM is worth $8.5M you should be downvoted for being this reductionist and uncharitable. this is a side project of a larger company effort.
- kristjansson 3y agoI think you might be over-simplifying. This (and llama.cpp's grammar-based sampling, which this is moving towards[1]) doesn't say "no, not like that, give me another token". It excludes impossible tokens at each step, but otherwise samples like normal. Is this a revolutionary trick? Not really, since llama.cpp and guidance, and probably others have already done it. But it's a good trick, and hopefully one of many to justify the valuation :). [1]: https://github.com/normal-computing/outlines/pull/178 https://github.com/normal-computing/outlines/pull/178
- remilouf 3y agoI’m sorry that our software made you so angry. It was a side project led by two people independently from the rest of the company.
- deleted 3y ago[deleted]
- coder543 3y agoAs a more general comment, the repo README provides examples that all use gpt2. It would be nice to see at least one example that invokes llama2, since I feel like that would make sure the reader knows that this library can use models that are more modern and interesting.
- Havoc 3y agoInclined to disagree - gpt2 is far more likely to produce gibberish. So if you can force specific outputs on that then it is a good demo that higher quality models will be even better
- coder543 3y agoMaybe... but then if I want to use something better, I have to figure out how by myself. I said "at least one example", not "please change all the examples to llama2." I agree with your general point. It would be nice if there were an example of how to use a better model. Models often have different shapes and requirements, so is it really as simple as changing the string "gpt2" to "llama2-13B-Chat" and it will magically work? If so, that's great, and I wish that was made clear. Unfortunately, that hasn't always been my experience with other libraries.
- swyx 3y agoit would also be nice to see one example that uses gpt4.
- 3y ago
- quickthrower2 3y ago> LLMs can generate valid JSON 100% of the time If that seems surprising, it is worth doing a course like Karpathy's zero to hero NN, and have all the magic peeled away a layer at a time. The reason you can do this is because LLMs don't just generate the next word or token, it produces a probability distribution over all tokens. A JSON parser can give you a list of next valid tokens. The tokens in each case might be from a different set, e.g LLM thinks of " The" whereas the JSON parser might think of "{", so you need some conversion there. But if you sample randomly from only the valid tokens, the output must be valid JSON. What you can't build a parser for though is ... the truth! You may still be told lies or made up stuff.
- mattigames 3y agoIt's not like humans are particularly good at distinguishing truth from lies.
- quickthrower2 3y agoThe word "lie" is probably too anthropic here. I should have just said "made up". There is no intent to lie. And the model isn't try to self-fact-check anyway. (Maybe some do). But if they do they are probably bad at it at the moment, at least from my experience of GPT3.5 (not used 4 much).
- coder543 3y ago> at least from my experience of GPT3.5 (not used 4 much). And 4 is tremendously better than 3.5, in my own experience. Not perfect, but actually useful.
- quickthrower2 3y agoCan anyone recommend a good, and trusted UI so I can use it via the API? I don't want to pay monthly for it, but would be nice to use occasionally. I keep meaning to do this!
- anotherpaulg 3y agoFor complex tasks like coding, my experience is that asking for a complex output format hurts performance on the underlying task. This showed up clearly in code editing benchmarks of GPT-3.5 and GPT-4: https://aider.chat/docs/benchmarks.html https://aider.chat/docs/benchmarks.html I’m curious if you have measured whether the “constrained generation” that you’re doing suffers from similar downsides?
- infecto 3y ago100% have observed the same over many tests. No loss in fidelity when responding in spoken language style of formatting but using json is disastrous.
- nouri 3y agoUsing OpenAI Function Calls or asking for JSON in the prompt?
- infecto 3y agoI have noticed it in both but have been working with json output before function calling was introduced so I have more evidence on that side. The times I have tried to implement it in a function call I was equally unimpressed with it.
- speedgoose 3y agoWhile not ideal, could a workaround be to ask in spoken language first, and then ask to format it in JSON?
- infecto 3y agoThat’s what we have been doing. Two passes. The task and then the format.
- darkteflon 3y agoWe’ve seen this too. We run them as two separate stages - “reason”, log the intermediate output, then parse.
- itissid 3y agoI have noob thought on the potential of these in Formal path planning. Specifically given a set of functions that basically map {State -> Actions} given preconditions, transition functions (heavily paraphrasing STRIPS[1]) can a correct and optionally "realistic" plan be generated[2]? I am quite interested in this. It seems clear that the issue is that there is no "guidance" like DFA on what is the correct next symbol for a Plan, but perhaps the AI can generate some kind of a probability or order on what is the best step and one can go from there... Are you guys thinking about this direction? [1] https://en.wikipedia.org/wiki/Stanford_Research_Institute_Problem_Solver#Complexity https://en.wikipedia.org/wiki/Stanford_Research_Institute_Pr... [2] Formal Planning decision problem(plan exists) given STRIPS spec is at least NP-Complete[1]. There are several mathematical, logical and statistical "tricks"(e.g. [3]) that are used to bring down the complexity and try find a plan using heuristics(thinking MDPs, POMDPs here). This is not new, everyone in LLM research knows this. [3] "Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning": https://www.sciencedirect.com/science/article/pii/S0004370299000521?ref=pdf_download https://www.sciencedirect.com/science/article/pii/S000437029...
- deleted 3y ago[deleted]
- YeGoblynQueenne 3y ago>> Specifically given a set of functions that basically map {State -> Actions} given preconditions, transition functions (heavily paraphrasing STRIPS[1]) can a correct and optionally "realistic" plan be generated[2]? Maybe, but the results would be unreliable. And if there's one thing that Good, Old-Fashioned, automated planning and scheduling is good at, that is reliability.
- oars 3y agoExcited to incorporate this into my developer workflow.
- Scaevolus 3y agoAre there temperature or sampling parameters for generate.regex? I'm poking around trying to generate password mnemonics (https://rmmh.github.io/abbrase/ https://rmmh.github.io/abbrase/), and it really doesn't like actually giving me proper words: >> model = models.transformers("gpt2-medium") >> generate.regex(model, r"Rea[a-z']{,10} lik[a-z']{,10} acr[a-z']{,10} ene[a-z']{,10} sta[a-z']{,10}\.", max_tokens=30)("A memorable phrase is:") 'Rearmingandme like acrowetteanda eneatubootank stackfishkies.'
- dvasdekis 3y agoWould love to have a tutorial on how to install and run this locally with a nice model, for those of us who are behind the 8-ball with torch, transformers, diffusers, llama2 etc.
- jmcminis 3y agoAre there edge cases here due to context length? 1. I have a json schema with required fields. I complete the json, but do not include the required fields. 2. I run out of token from the model before I finish the json object because I'm in the middle of some deep, nested structure. These seem solvable, just edge cases to control for by either reserving tokens, randomly generating required tokens until completing the json, or something more sophisticated.
- sandkoan 3y agoThis is what we did at Trex (https://github.com/automorphic-ai/trex https://github.com/automorphic-ai/trex). The tricky part is doing it quickly and efficiently.
- sberens 3y agoWhat happens if max_tokens cuts the model off from generating valid JSON?
- dsrtslnd23 3y agoIt says "Outlines 〰 is compatible with all models.". But does this actually work with gpt3.5-turbo or gpt4? I was using guidance before and you only get value when using davinci due to the constraints of chat api based models.
- AtlasBarfed 3y agoOk so: - for what energy/processing cost per validation? - how much of the input space was tested (unicode chars, escaped chars, newlines, etc)? - are you doing this as a service? We've seen LLMs already evolve negatively in some capabilities over time, so do you have a constant "ping" test suite validating the LLM's performance?
- haolez 3y agoCan I use this locally with models that run on my CPU? Like llama.cpp
- remilouf 3y agoWe can add an integration to llama.cpp, please open an issue on the repo if you’re interested!
- Ycros 3y agoHaving played around with this sort of thing in the llama.cpp ecosystem when they added it a few weeks ago, I will say that it also helps if your models a) are tuned to output json and b) you prompt them to do so. Anything you can do to help the output fit the grammar helps.
- faangiq 3y agoIs generating valid json nontrivial?
- vlovich123 3y agoHow is this different from generating such things without an LLM? In other words picking random valid tokens from the grammar via fuzzing or similar techniques.
- vlovich123 3y agoInstead of downvoting, I’d appreciate an answer. I’m genuinely curious to learn what the value add of the LLM is.
- lexandstuff 3y agoLLMS allows for building systems that take user requests in text: "book the next flight to Egpyt" and convert them into a system message: `{"action": "book_flight", "destination": "Egypt", ... }` However, anyone who's tried to build a system like this on GPT or other LLM soon learns that they don't always do as they're told, and it can be hard to get them to return valid JSON or correct instructions translation reliably. Sometimes, they make stuff up that has nothing to do with your system. OpenAI has a solution to this with their new function calling API, by introducing models fine-tuned to return JSON, but they still can't make guarantees. Outlines seems to be a neat approach to constrain an LLM to return JSON, or any grammar, reliably.
- vlovich123 3y agoWhy bother with conversion to JSON directly from the LLM instead of a simpler format (eg line separated) that you then convert into JSON normally?
- malft 3y agoRegex-constrained GPT, what is a mnemonic for pi? > It's a word, a short statement or phrase which you learn. Can you make a good one? > Man, I wish I could recommend an answer. You're not gonna remember something, because, obviously, pi's so big. Actually, let's forget pi. There's only one way: Googling for it. (count the letters)
- deleted 3y ago[deleted]
- SethTro 3y agoprint(guided) # What is the IP address of the Google DNS servers? # 2.2.6.1 correctly formatted wrong answers are still wrong answers.
- aiunboxed 3y agoOpen AI has released this as a feature, is this news ? what am i missing ?
- calderwoodra 3y agoHave you found a solution to output exceeding the context window? That's been our only issue with generating json output.
- remilouf 3y agoThe Finite-State Machine we walk on during the generation process does not suffer from this problem so we can still output correct JSON, if that’s what you’re asking.
- kristjansson 3y agoIt does seem inapt to claim this “eliminates” hallucinations in your blog post. Sort of like unnamed FP languages claiming to eliminate bugs. Both eliminate a subclass of failures, but don’t preclude failure categorically.
- TeeWEE 3y agoAs it describes it does eliminate non JSON outputs by masking the tokens while the LLM is generating. Its quite smart if you ask me.
- kristjansson 3y agoIt’s very clever. I wouldn’t want it to be oversold.
- hansvm 3y agoA major part of the power of an LLM is the calibrated probability distribution in its responses, and this technique probably throws that ability away. Why is it good enough? As a brief example, suppose the only possible LLM outputs were "hello world", "food", "hello", and "good day" (and that they're all equally probable with no prompting). Suppose your grammar requires a space in the output somewhere and has no other constraints. If you sampled LLM outputs till something passed the grammer you'd receive "hello world" and "good day" with equal probability. If you apply the website's technique you'll receive "hello world" twice as frequently as "good day". The core problem is that an answer prefix might have been extremely unlikely to yield a valid response, but the technique (probably -- assuming it succeeds -- my example assumed retries would eventually succeed) constructs a valid response from it regardless. Assuming enough independence in the right places everything is fine and dandy still, but correlated errors compound quickly in autoregressive models. As a brief JSON-specific question, is an LLM more or less likely to make factual errors (hallucinations, truncated strings, missing main characters, ...) when it produces a response failing to adhere to a schema? If factual error rate relates nontrivially to schema error rate then this path is more perilous than it seems. Given the outsized impact certain words or schmooshed together word-phrases seem to have on LLM output, I'd be surprised if details like schema adherence didn't bleed into other characteristics of the output.
- druskacik 3y agoIn this case (multiple choice generation), if one of the possible outputs does no match the regex, you can just exclude it from generation. I am trying to think of an example where "answer prefix might have been extremely unlikely to yield a valid response, but the technique ( ... ) constructs a valid response from it regardless", which might really cause a problem. But to no luck. Anyone has any idea? This could potentially be an interesting research question.
- newhouseb 3y agoAn example from an earlier comment of mine on a different thread (assuming I've understood correctly): > let's say we had a grammar that had a key "healthy" with values "very_unhealthy" or "moderately_healthy." For broccoli, the LLM might intend to say "very_healthy" and choose "very" but then be pigeonholed into saying "very_unhealthy" because it's the only valid completion according to the grammar. That said, you can use beam search to more or less solve this problem by evaluating the joint probability of all tokens in each branch of the grammar and picking the one with the highest probability (you might need some more nuance for free-form strings where the LLM can do whatever it wants and be "valid").
- cztomsik 3y agoFYI llama.cpp can do that for a "while" https://github.com/ggerganov/llama.cpp/pull/1773 https://github.com/ggerganov/llama.cpp/pull/1773 Somebody is also working on a whisper.cpp version, which is maybe even more interesting because if you have grammar you can speak not only JSON but also a code (or anything)
- kevinlu1248 3y agoThis is amazing! I think for production and rapid development use-cases though we just use XML for information extraction. It's extremely easy to parse with regex and rarely do the models make mistakes since the start and end tokens are uncommon. At least this is just for the OpenAI model which are different from the use cases in this ShowHN.
- YeGoblynQueenne 3y agoHi, remilouf. You say that your background is in "probabilistic, relational and symbolic programming". In that case I suspect you understand that it is no problem to generate text from a regular or context-free grammar, or really any level of grammar. For example, you can do that very easily in Prolog (a relational language) given a grammar in Definite Clause Grammars notation. As far as I can tell your approach requires a grammar to be given by a user. In that case, what is the advantage of using an LLM to generate text? Why can't you just run your grammar as a generator and generate the text you want? That would save you the considerable trouble and cost of training an LLM in the first place. And why would you need an LLM, a model of natural language, if all you want is to generate structured text, anyway?
- IanCal 3y agoWouldn't that generate an entirely random but valid output? Here you want a valid output related to the request. > And why would you need an LLM, a model of natural language, if all you want is to generate structured text, anyway? So that you can parse unstructured text from a person and return structured data for a machine.
- YeGoblynQueenne 3y ago>> Wouldn't that generate an entirely random but valid output? No. Grammars don't generate entirely random output. Even Probabilistic Context Free Grammars can generate deterministic output, depending on how they are sampled. The output can be related to some input, if desired, for example one can give a string with "holes" (variables) as input and have the holes filled-in by the grammar. >> So that you can parse unstructured text from a person and return structured data for a machine. If you are willing to spend the effort to write a grammar, you can do that without an LLM.
- IanCal 3y agoI wasn't talking about deterministic Vs nondeterministic. > If you are willing to spend the effort to write a grammar, you can do that without an LLM. How are you taking, for example, a request to make a "fun but not over the top character from the middle ages, with relevant weapons and a backstory. Game theme is a world populated by anthropomorphic vegetables." And get back a character for the game in a specific JSON format without the LLM in your design here? That's not encodable in the grammar.
- rmonvfer 3y agoYou should probably look into Guidance [1](previously Microsoft Guidance but looks like it’s been separated from their main organization), which is a language for controlling the output of LLMs (so you can, among many other things, output JSON in a deterministic way) [1]: https://github.com/guidance-ai/guidance https://github.com/guidance-ai/guidance
- civilitty 3y agoFrom the OP: > Our method blows other libraries like Microsoft's guidance out of the water. Come on man, it was just a few paragraphs.
- jhhgzgft 3y ago+hacker:com:de.wegt8wfcvd
- taeric 3y agoNotable that you can't seem to use this trick to have an LLM create JSON that has JSON embedded in it. Which... happens far more often than it probably should. :(
- remilouf 3y agoYou mean nested JSON? It's totally possible.
- demarq 3y agoI've spent two days trying to make this work with anything other than gpt2 and I just can't get it to work. GPT2 doesn't seem to take instruction well. I've tried llama gpt-medium etc etc. They all either pick up a different language, or freeze. EDIT: I see tons of activity and work in the github issues, so ignore this for now. Super excited when I'll be able to have this working for myself!