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

Xiaokun Luan, Zemin Wei, Yihao Zhang, Meng Sun

TL;DR

While current tools can force Large Language Models (LLMs) to follow strict formats like JSON or Regex, they often suffer from a "diversity crisis," repeating the same few patterns over and over. This paper introduces a novel steering mechanism that uses the history of an automaton's traversal to push LLMs toward unexplored structural paths, significantly increasing output variety without sacrificing validity or much speed.

What Problem Does This Paper Address?

Structured generation is a hot topic in LLM deployment. Tools like Outlines or SGLang use finite automata to "mask" invalid tokens, ensuring the model's output perfectly matches a schema (like an email format or a specific JSON structure).

However, the authors discovered a major flaw: Correctness does not equal diversity. Even when forced to follow a grammar, LLMs tend to gravitate toward high-probability "safe" regions of that grammar. For example, if asked for an email address, a model might generate [email protected] a thousand times rather than exploring edge cases like quoted local parts or IPv4 literals, even if the grammar allows them. This lack of diversity is a dealbreaker for applications like synthetic data generation or automated software testing, where you need to hit every possible "corner" of a specification.

Methods

The authors propose a "Diversity-enhanced Structured Generation" method. It builds on top of standard automaton-based masking but adds a dynamic "steering" layer to the model's logits (the raw scores before they become probabilities).

The core components are:

  1. Global Transition Counter ($C$): The system keeps track of every "state pair" (transition) the model has traversed across all previous generation attempts.
  2. Exploration Reward: During the next token selection, the system looks at the paths the automaton would take for each valid token. It adds a "reward" to tokens that lead through transitions that have been rarely visited in the past.
  3. Local Penalty Counter ($C_{loc}$): To prevent the model from getting stuck in infinite loops (a common side effect of forcing exploration), a local counter tracks visits within a single generation and penalizes tokens that stay in the same state too long.
  4. Adaptive Scaling: Because different models have different logit ranges, the authors introduce a scaling factor based on the current range of valid logits. This ensures the "push" toward diversity is strong enough to be felt but not so strong that it produces gibberish.

Datasets

The paper doesn't use traditional training datasets; instead, it evaluates the method at inference time using four complex regular expression grammars ($G$):

  • $G_{email}$: A comprehensive email regex covering edge cases like IPv4 addresses.
  • $G_{color}$: CSS color codes including HSL, HSLA, and lab() functions.
  • $G_{json}$: A standard JSON object with multiple field types.
  • $G_{bomb}$: A "negative constraint" grammar that allows any string except those containing the word "bomb."

For the case study, they used two Python libraries, email_validator and webcolors, to see if the generated strings could trigger different code paths (branch coverage).

Key Insights and Ideas

  • Temperature is a Blunt Instrument: The authors found that simply turning up the "temperature" (randomness) of an LLM doesn't solve the diversity problem in structured generation. The model still misses complex edge cases allowed by the grammar because its underlying training bias is too strong.
  • Automata as a Map: By treating the grammar's DFA (Deterministic Finite Automaton) as a map, the authors can mathematically define "unexplored territory." Steering the model becomes a game of incentivizing it to take the "road less traveled" on that map.
  • The Stability-Exploration Trade-off: Without the local penalty ($C_{loc}$), the model often gets "lost" trying to be diverse and fails to reach an end-of-sequence (EOS) state. The local penalty acts as a tether, ensuring the model eventually finishes its thought.

Key Results

The results are striking. When compared to the industry-standard baseline (Outlines):

  • Structural Coverage: For the email grammar, the baseline only covered about 18.6% of the possible states in the automaton. The proposed method covered 95.35%.
  • Content Diversity: Using the Vendi score (a metric for dataset diversity), the new method improved diversity by 90% on average across all tested grammars.
  • Efficiency: The "steering" logic adds some overhead, but the model still maintains about 88% of the original generation speed (Tokens Per Second).
  • Software Testing: In the case study, test cases generated by this method achieved significantly higher branch coverage in real-world Python libraries (e.g., a 12.89% improvement for email_validator).

Limitations and Future Work

The primary limitation is that the current implementation is optimized for Finite Automata (Regular Expressions). While the authors mention the logic is generalizable to Pushdown Automata (Context-Free Grammars like Python or C++ code), they haven't yet implemented or evaluated it for those more complex structures.

Future work aims to develop more adaptive strategies for the exploration-exploitation trade-off and to integrate the method with "parser combinators" to support general-purpose programming languages, which could revolutionize automated code generation and bug hunting.

Summary updated

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.
BibTeX
@inproceedings{luan2025automata,
  author = {Xiaokun Luan and Zemin Wei and Yihao Zhang and Meng Sun},
  title = {{Automata-Based Steering of Large Language Models for Diverse Structured Generation}},
  booktitle = {ICFEM},
  year = {2025},
  url = {https://openreview.net/forum?id=gQP15rNtvo},
}

Loading related content...

Figure