Abstract
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.
Introduction
Structured generation is essential for deploying LLMs in workflows requiring specific formats like JSON or Regex. Tools such as Outlines or SGLang employ finite automata to mask invalid tokens, ensuring syntactic correctness. However, a significant challenge remains: correctness does not guarantee diversity. LLMs often gravitate toward high-probability "safe" regions of a grammar, repeatedly generating common patterns while ignoring valid edge cases. This "diversity crisis" limits the utility of LLMs in synthetic data generation and automated software testing.
Methods: Diversity-Enhanced Steering
We introduce a steering mechanism that leverages the history of an automaton's traversal to encourage exploration of novel structural paths. The method modifies the model's logits during inference through several key components:
- Global Transition Counter ($C$): Tracks every state transition traversed across all previous generation attempts to identify unexplored regions of the grammar.
- Exploration Reward: Adds a reward to tokens leading to rarely visited transitions, incentivizing the model to take the "road less traveled."
- Local Penalty Counter ($C_{loc}$): Prevents infinite loops within a single generation by penalizing tokens that cause the model to linger in the same state excessively.
- Adaptive Scaling: Dynamically adjusts the steering strength based on the current range of valid logits, ensuring the diversity push is effective without compromising output quality.
Experimental Setup
Our method was evaluated using four complex regular expression grammars: $G_{email}$ (including IPv4 edge cases), $G_{color}$ (CSS color codes), $G_{json}$ (standard JSON objects), and $G_{bomb}$ (negative constraints). We compared our approach against the Outlines baseline, measuring structural coverage, content diversity, and generation efficiency.
Key Insights and Results
A critical finding is that increasing the sampling temperature is insufficient for achieving high diversity. As shown in Table 1, while higher temperatures slightly improve coverage in some cases, the model still fails to explore the vast majority of the grammar's state space and can even see a decrease in distinct n-grams (e.g., Distinct-2 for $G_{email}$).
In contrast, our proposed method achieved:
- Superior Coverage: For $G_{email}$, structural coverage increased from the baseline's 18.6% to 95.35%.
- Enhanced Diversity: Content diversity (measured via Vendi score) improved by an average of 90% across all grammars.
- High Efficiency: The steering logic maintained approximately 88% of the baseline's generation speed.
- Real-world Impact: In a case study on Python libraries
email_validatorandwebcolors, our method improved branch coverage by up to 12.89%.
Conclusion
By treating the grammar's Deterministic Finite Automaton (DFA) as a map, we can mathematically steer LLMs toward unexplored structural territory. While currently optimized for finite automata, this approach holds promise for more complex structures like context-free grammars, potentially revolutionizing automated code generation and bug hunting.
Summary updated