LLM生成JSON格式不对容易解析失败
- Rachel____Zhang
- 2024-11-30 07:49:47
解决【LLM生成JSON格式不对容易解析失败】的问题：Constraint decoding
背景：大模型在执行NL2Code、NL2SQL、Function calling这种任务中，经常需要生成结构化的代码、JSON或SQL。然而生成过程容易出现格式问题，如遗漏括号或逗号，导致生成的内容无法被正确解析而失败。Constraint decoding是个常规解决方案，它通过在每一个decoding step，规定这一步 允许/禁止 出现vocab中的哪些token，确保输出符合预期的格式。 这些约束通常基于上下文无关语法（context-free grammar, CFG）来定义（如图1）。
动机：如果直接将CFG应用于受限解码，可能存在效率问题，比如一种方法是在每一步解码中，都对vocab中的每个token，run一下CFG解析，但infer-time当场解析的话，计算消耗非常大。换个方法，如果想要提前算好所有符合规则的待匹配候选，又会由于组合爆炸难以实现。那怎么才能高效地结合CFG进行constraint decoding呢？
思路：由于上下文无关语法可以由一些有限状态机(finite state machines, FSM)来表示（如图2），本文提出了一种新颖的方法。针对状态机中的每个状态，提前计算好该状态下能够 允许和禁止哪些token，从而实现高效constraint decoding。这样只要在decoding时，用一个下推状态机（专门解释CFG的）来跟踪当前状态了，就能马上调用提前计算好的kv对（key:状态，value:当前状态下 允许/不允许 解码出的token），快速判断每个token是否应该被允许或禁止了。
方案：idea很美好。但实际上到一个状态的时候，不一定能完全确定某个token 能被允许/禁止，因为有时候一个state下能不能允许某个token的出现，取决于之后走到哪个state（继续在这个规则里，还是走完了这个规则的状态机然后返回父节点了）。于是，可以对于每个state，将vocab分成三类（如图3），可接受的（绿）、不可接受的（红）、依赖上下文才能知道的（黄）。比如图中解码走到状态l的时候，根据规则能够确定这时候出 \ 肯定是不行的，但是"a能不能出，就不太确定。因为str这条状态机走完，还会解析到其 父规则，其父规则能不能接受就不是这个节点好确定的事情了。不过不要紧，vocab中的大部分token都是上下文无关的（红、绿），这部分计算量几乎为零了，之后只需要针对 依赖上下文才能知道的（黄）tokens进行推理验证就行了。
对于每个上下文相关token，下推自动机需要执行完整的匹配过程，即从当前节点开始，一直匹配字符，同时更新栈状态。如果匹配过程到达当前规则的末尾并返回到父规则，则需要从栈中弹出相应的元素。这个过程会一直持续到整个token被完全匹配，或者确定该token无效。
哔哔一下：时光匆匆过，美女变成老太婆。大学毕业这么多年了，一下子看到状态机，想到数字逻辑课，应该是我为数不多的满分科目，久远又美好，艾玛太带劲了，一口气读完论文，真爽，真make sense。然后那啥，说回来，其实对齐训练后，代码生成好像没那么多格式问题，所以解决的其实是长长长尾case，只是万一偶然的解析失败导致用户等半天又没拿到结果，体验确实不好。
文章：《XGrammar: Flexible and Efficient Structured Generation Engine For Large Language Models》
网页链接 作者：CMU，NV，上交，UC伯克利
背景：大模型在执行NL2Code、NL2SQL、Function calling这种任务中，经常需要生成结构化的代码、JSON或SQL。然而生成过程容易出现格式问题，如遗漏括号或逗号，导致生成的内容无法被正确解析而失败。Constraint decoding是个常规解决方案，它通过在每一个decoding step，规定这一步 允许/禁止 出现vocab中的哪些token，确保输出符合预期的格式。 这些约束通常基于上下文无关语法（context-free grammar, CFG）来定义（如图1）。
动机：如果直接将CFG应用于受限解码，可能存在效率问题，比如一种方法是在每一步解码中，都对vocab中的每个token，run一下CFG解析，但infer-time当场解析的话，计算消耗非常大。换个方法，如果想要提前算好所有符合规则的待匹配候选，又会由于组合爆炸难以实现。那怎么才能高效地结合CFG进行constraint decoding呢？
思路：由于上下文无关语法可以由一些有限状态机(finite state machines, FSM)来表示（如图2），本文提出了一种新颖的方法。针对状态机中的每个状态，提前计算好该状态下能够 允许和禁止哪些token，从而实现高效constraint decoding。这样只要在decoding时，用一个下推状态机（专门解释CFG的）来跟踪当前状态了，就能马上调用提前计算好的kv对（key:状态，value:当前状态下 允许/不允许 解码出的token），快速判断每个token是否应该被允许或禁止了。
方案：idea很美好。但实际上到一个状态的时候，不一定能完全确定某个token 能被允许/禁止，因为有时候一个state下能不能允许某个token的出现，取决于之后走到哪个state（继续在这个规则里，还是走完了这个规则的状态机然后返回父节点了）。于是，可以对于每个state，将vocab分成三类（如图3），可接受的（绿）、不可接受的（红）、依赖上下文才能知道的（黄）。比如图中解码走到状态l的时候，根据规则能够确定这时候出 \ 肯定是不行的，但是"a能不能出，就不太确定。因为str这条状态机走完，还会解析到其 父规则，其父规则能不能接受就不是这个节点好确定的事情了。不过不要紧，vocab中的大部分token都是上下文无关的（红、绿），这部分计算量几乎为零了，之后只需要针对 依赖上下文才能知道的（黄）tokens进行推理验证就行了。
对于每个上下文相关token，下推自动机需要执行完整的匹配过程，即从当前节点开始，一直匹配字符，同时更新栈状态。如果匹配过程到达当前规则的末尾并返回到父规则，则需要从栈中弹出相应的元素。这个过程会一直持续到整个token被完全匹配，或者确定该token无效。
哔哔一下：时光匆匆过，美女变成老太婆。大学毕业这么多年了，一下子看到状态机，想到数字逻辑课，应该是我为数不多的满分科目，久远又美好，艾玛太带劲了，一口气读完论文，真爽，真make sense。然后那啥，说回来，其实对齐训练后，代码生成好像没那么多格式问题，所以解决的其实是长长长尾case，只是万一偶然的解析失败导致用户等半天又没拿到结果，体验确实不好。
文章：《XGrammar: Flexible and Efficient Structured Generation Engine For Large Language Models》
网页链接 作者：CMU，NV，上交，UC伯克利
