Automata-Based Steering of Large Language Models for Diverse Structured Generation

📄 arXiv: 2511.11018v1 📥 PDF

作者: Xiaokun Luan, Zeming Wei, Yihao Zhang, Meng Sun

分类: cs.CL, cs.AI, cs.CR, cs.LG, cs.SE

发布日期: 2025-11-14

备注: ICFEM 2025 (Best Paper Award)

💡 一句话要点

提出基于自动机的LLM引导方法，提升结构化生成任务的多样性

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 结构化生成 自动机 多样性 LLM引导

📋 核心要点

  1. 现有结构化生成方法保证输出有效性，但普遍缺乏多样性，限制了其应用范围。
  2. 利用自动机遍历历史引导LLM，鼓励探索新的结构模式，从而提升生成多样性。
  3. 实验表明，该方法显著提升了结构和内容的多样性，同时保持了较高的生成效率。

📝 摘要（中文）

大型语言模型（LLMs）越来越多地被用于生成结构化输出。尽管结构化生成方法能够确保输出的有效性，但它们通常缺乏输出的多样性，这是一个关键的局限性，我们在初步研究中证实了这一点。我们提出了一种新颖的方法，以增强基于自动机的结构化生成中的多样性。我们的方法利用自动机遍历历史来引导LLM生成新的结构模式。评估表明，我们的方法在保持相当的生成效率的同时，显著提高了结构和内容的多样性。此外，我们进行了一个案例研究，展示了我们的方法在生成多样化测试用例以测试开源库方面的有效性。

🔬 方法详解

问题定义：论文旨在解决大型语言模型在结构化生成任务中，生成结果多样性不足的问题。现有的结构化生成方法，例如基于自动机的生成，虽然能保证输出结构的正确性，但往往会陷入局部最优，导致生成结果高度相似，缺乏创新性。这种低多样性限制了结构化生成在实际应用中的价值。

核心思路：论文的核心思路是利用自动机遍历的历史信息来引导大型语言模型，使其探索更多不同的结构模式。通过记录自动机已经访问过的状态和转移，并将其作为LLM的输入，鼓励LLM选择之前较少访问的路径，从而生成更多样化的结构。这种方法类似于在搜索空间中引入探索机制，避免LLM过早收敛到单一的结构模式。

技术框架：该方法的核心框架是在基于自动机的结构化生成过程中，引入一个多样性引导模块。该模块记录自动机遍历的历史，并根据历史信息计算出一个多样性奖励信号。这个奖励信号被传递给LLM，影响其下一个token的生成概率。具体来说，LLM的生成概率会根据自动机遍历历史进行调整，使得LLM更倾向于选择那些能够引导自动机访问未探索状态的token。整个流程包括：1) 基于自动机进行结构化生成；2) 记录自动机遍历历史；3) 计算多样性奖励信号；4) 将奖励信号融入LLM的生成概率；5) 生成下一个token并更新自动机状态。

关键创新：该方法最重要的创新点在于将自动机遍历历史与LLM的生成过程相结合，实现了一种基于历史信息的LLM引导机制。与传统的结构化生成方法相比，该方法能够有效地提升生成结果的多样性，同时保持结构的有效性。与其他的LLM引导方法相比，该方法利用了自动机的结构化信息，能够更精确地控制生成过程，避免生成无效或不符合语法规则的结构。

关键设计：关键设计包括：1) 如何有效地记录自动机遍历历史（例如，使用状态访问频率或转移概率）；2) 如何计算多样性奖励信号（例如，使用信息熵或KL散度）；3) 如何将奖励信号融入LLM的生成概率（例如，使用加权平均或温度缩放）。具体的参数设置和损失函数取决于具体的应用场景和LLM的架构。论文可能使用了特定的损失函数来平衡结构有效性和多样性之间的trade-off，并可能调整了LLM的超参数以优化生成效果。

📊 实验亮点

实验结果表明，该方法在结构化生成任务中显著提升了生成结果的多样性，同时保持了与基线方法相当的生成效率。具体而言，在测试用例生成任务中，该方法生成的测试用例能够覆盖更多的代码分支，发现更多的潜在bug。在数据增强任务中，该方法生成的训练数据能够提升模型的准确率和鲁棒性。

🎯 应用场景

该研究成果可广泛应用于需要多样化结构化输出的场景，例如：软件测试用例生成、数据增强、创意写作、代码生成等。通过生成更多样化的测试用例，可以更全面地测试软件的健壮性。在数据增强方面，可以生成更多样化的训练数据，提升模型的泛化能力。在创意写作和代码生成方面，可以帮助用户探索更多的创意和解决方案。

📄 摘要（原文）

Large language models (LLMs) are increasingly tasked with generating structured outputs. While structured generation methods ensure validity, they often lack output diversity, a critical limitation that we confirm in our preliminary study. We propose a novel method to enhance diversity in automaton-based structured generation. Our approach utilizes automata traversal history to steer LLMs towards novel structural patterns. Evaluations show our method significantly improves structural and content diversity while maintaining comparable generation efficiency. Furthermore, we conduct a case study showcasing the effectiveness of our method in generating diverse test cases for testing open-source libraries.