---
title: "Grammar-State Aware Beam Search for Enhancing Structural Diversity in LLM Generation"
authors:
  - "Hantao Hua"
  - "Jiming Su"
  - "Yiping Yao"
  - "Feng Zhu"
doi: "10.24963/ijcai.2026/639"
url: "https://ijcai.org/proceedings/2026/639"
pdf: "https://ijcai.org/proceedings/2026/0639.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "5739-5747"
track: "Main Track"
keywords:
  - "Natural Language Processing: Language models"
  - "Natural Language Processing: Applications"
  - "Natural Language Processing: Language generation"
  - "Machine Learning: Generative models"
  - "Machine Learning: Structured prediction"
---

# Grammar-State Aware Beam Search for Enhancing Structural Diversity in LLM Generation

Hantao Hua, Jiming Su, Yiping Yao, Feng Zhu

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 5739-5747. DOI: [10.24963/ijcai.2026/639](https://doi.org/10.24963/ijcai.2026/639)

## Abstract

In many large language model (LLM) applications, generating structurally diverse candidate outputs is crucial for downstream decision-making and reasoning. However, conventional beam search allocates search budget at the token-prefix level, so multiple beam slots may be occupied by lexically different but structurally similar hypotheses. To address these limitations, we propose Grammar-State Aware Beam Search (GSA-Beam). Our method first organizes search at the constraint state level rather than individual prefix level, enabling explicit control over structural diversity. It further incorporates a dynamic state-level beam regulation mechanism that adaptively adjusts beam allocation based on the branching of constraint states, efficiently exploring the feasible structured solution space. Experiments on JSON-schema constrained generation show that GSA-Beam improves explicit state coverage and final structural diversity while preserving schema validity; across several LLM backbones, it reduces reference latency by 22.5% on average compared with standard constrained beam search. Code is available at https://github.com/Paradozile/GSABeam.