<story><title>Show HN: LLMs can generate valid JSON 100% of the time</title><url>https://github.com/normal-computing/outlines</url><text>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.&lt;p&gt;Recently we came up with a fast way to generate text that matches a regex (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;blog.normalcomputing.ai&amp;#x2F;posts&amp;#x2F;2023-07-27-regex-guided-generation&amp;#x2F;regex-guided-generation.html&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;blog.normalcomputing.ai&amp;#x2F;posts&amp;#x2F;2023-07-27-regex-guide...&lt;/a&gt;). 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&amp;#x27;s vocabulary. We can do this in only one pass over the vocabulary.&lt;p&gt;Generating the token masks thus only requires a dictionary lookup at each state. Our method blows other libraries like Microsoft&amp;#x27;s guidance out of the water.&lt;p&gt;From there it was only a small leap to be able to generate text that follows a JSON schema (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;json-schema.org&amp;#x2F;&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;json-schema.org&amp;#x2F;&lt;/a&gt;), or is parseable into a Pydantic model (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;docs.pydantic.dev&amp;#x2F;latest&amp;#x2F;usage&amp;#x2F;models&amp;#x2F;&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;docs.pydantic.dev&amp;#x2F;latest&amp;#x2F;usage&amp;#x2F;models&amp;#x2F;&lt;/a&gt;). The method works with union types, optional types, nested schemas, arrays, everything. It is guaranteed that the output is parseable.&lt;p&gt;I think it&amp;#x27;s cool, and I&amp;#x27;ve spent a lot of time watching even tiny models output valid JSON over the weekend. Hope you will too.&lt;p&gt;I look forward to feedback, bug reports, feature requests and discussions!&lt;p&gt;Edit: Link to our pre-print explaining the method and how this can be extended to generate text that follows a Context-Free Grammar &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;arxiv.org&amp;#x2F;abs&amp;#x2F;2307.09702&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;arxiv.org&amp;#x2F;abs&amp;#x2F;2307.09702&lt;/a&gt;</text></story><parent_chain><item><author>panarky</author><text>I can make GPT4 return valid JSON simply by providing examples in the system message. This works nine times out of ten.&lt;p&gt;But it&amp;#x27;s still probabilistic, and nine times out of ten isn&amp;#x27;t good enough.&lt;p&gt;Occasionally it will hallucinate responses like this:&lt;p&gt;{&amp;quot;key1&amp;quot;: &amp;quot;value1&amp;quot;, &amp;quot;key2&amp;quot;: &amp;quot;value2&amp;quot; for i in range(n)}&lt;p&gt;Re-prompting with the parsing error message is usually enough to get it on the second try.&lt;p&gt;But escaping double-quotes and newline characters is less reliable. Even after giving it multiple examples, it correctly escapes only about half the time.&lt;p&gt;Re-prompting for escaping errors still yields a ~50% success rate.</text></item></parent_chain><comment><author>simonw</author><text>That re-prompting on error trick is what this new Microsoft library does, too: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;microsoft&amp;#x2F;TypeChat&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;microsoft&amp;#x2F;TypeChat&lt;/a&gt;&lt;p&gt;Here&amp;#x27;s their prompt for that: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;microsoft&amp;#x2F;TypeChat&amp;#x2F;blob&amp;#x2F;c45460f4030938da39629d882c3e0e2c718f8680&amp;#x2F;src&amp;#x2F;program.ts#L212-L216&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;microsoft&amp;#x2F;TypeChat&amp;#x2F;blob&amp;#x2F;c45460f4030938da3...&lt;/a&gt;&lt;p&gt;I think the approach using grammars (seen here, but also in things like &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;ggerganov&amp;#x2F;llama.cpp&amp;#x2F;pull&amp;#x2F;1773&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;ggerganov&amp;#x2F;llama.cpp&amp;#x2F;pull&amp;#x2F;1773&lt;/a&gt; ) is a much more elegant solution.</text></comment>
<story><title>Show HN: LLMs can generate valid JSON 100% of the time</title><url>https://github.com/normal-computing/outlines</url><text>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.&lt;p&gt;Recently we came up with a fast way to generate text that matches a regex (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;blog.normalcomputing.ai&amp;#x2F;posts&amp;#x2F;2023-07-27-regex-guided-generation&amp;#x2F;regex-guided-generation.html&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;blog.normalcomputing.ai&amp;#x2F;posts&amp;#x2F;2023-07-27-regex-guide...&lt;/a&gt;). 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&amp;#x27;s vocabulary. We can do this in only one pass over the vocabulary.&lt;p&gt;Generating the token masks thus only requires a dictionary lookup at each state. Our method blows other libraries like Microsoft&amp;#x27;s guidance out of the water.&lt;p&gt;From there it was only a small leap to be able to generate text that follows a JSON schema (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;json-schema.org&amp;#x2F;&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;json-schema.org&amp;#x2F;&lt;/a&gt;), or is parseable into a Pydantic model (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;docs.pydantic.dev&amp;#x2F;latest&amp;#x2F;usage&amp;#x2F;models&amp;#x2F;&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;docs.pydantic.dev&amp;#x2F;latest&amp;#x2F;usage&amp;#x2F;models&amp;#x2F;&lt;/a&gt;). The method works with union types, optional types, nested schemas, arrays, everything. It is guaranteed that the output is parseable.&lt;p&gt;I think it&amp;#x27;s cool, and I&amp;#x27;ve spent a lot of time watching even tiny models output valid JSON over the weekend. Hope you will too.&lt;p&gt;I look forward to feedback, bug reports, feature requests and discussions!&lt;p&gt;Edit: Link to our pre-print explaining the method and how this can be extended to generate text that follows a Context-Free Grammar &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;arxiv.org&amp;#x2F;abs&amp;#x2F;2307.09702&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;arxiv.org&amp;#x2F;abs&amp;#x2F;2307.09702&lt;/a&gt;</text></story><parent_chain><item><author>panarky</author><text>I can make GPT4 return valid JSON simply by providing examples in the system message. This works nine times out of ten.&lt;p&gt;But it&amp;#x27;s still probabilistic, and nine times out of ten isn&amp;#x27;t good enough.&lt;p&gt;Occasionally it will hallucinate responses like this:&lt;p&gt;{&amp;quot;key1&amp;quot;: &amp;quot;value1&amp;quot;, &amp;quot;key2&amp;quot;: &amp;quot;value2&amp;quot; for i in range(n)}&lt;p&gt;Re-prompting with the parsing error message is usually enough to get it on the second try.&lt;p&gt;But escaping double-quotes and newline characters is less reliable. Even after giving it multiple examples, it correctly escapes only about half the time.&lt;p&gt;Re-prompting for escaping errors still yields a ~50% success rate.</text></item></parent_chain><comment><author>padolsey</author><text>I&amp;#x27;ve had more luck with getting it to output XML as (1) You can imbue XML with actual language&amp;#x2F;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&amp;#x27;s a bit like trying to get a cat to swim - you might eventually succeed, but it&amp;#x27;s not their natural inclination.</text></comment>