降低图算法空间开销及其在语言模型约束生成中的应用

语言模型越来越多地被要求提供结构化输出：遵循模式的 JSON，或带有类型参数的工具调用。一台小型机器，一个自动机，通过禁止破坏格式的Token来强制执行格式。我们观察到这台机器有一个罕见的特性：从它的任何状态来看，每个Token都沿着一条路径前进。只有少数路径连接任意两点的图是复杂性理论的经典对象，我们的理论结果解决了关于它们的一个悬而未决的问题：人们可以决定这样的图是否连接两点，同时验证它确实只有很少的路径，并且内存很少。准确地说，问题在于类 ReachUL、LOGDCFL、C=L 和 SC2，并且只需要 O(log2 n/ log log n) 空间，低于 Savitch 定理的经典 O(log2 n)。证明背后的结构成为一个推理引擎：在不运行模型的情况下写入格式强制的文本，在没有任何表的情况下在 GPU 上重新计算掩码，递归格式使用小堆栈，每个输出在Token限制下保持有效，并且独立字段被并行解码和验证。在配备 Qwen3.5-2B 和 4B 的 16 GB Apple M2 Pro 上，与具有 llguidance 的 MLX（该硬件的标准设置）相比，模式约束提取在相同答案下完成速度快 1.2-1.3 倍，语法成本为 3 MB 而不是最多 1.5 GB，一台服务器保存 16 个语法，其中表耗尽内存，16 个工具调用Agent完成速度快 2.5 倍。