本研究針對硬約束語言模型生成任務中的計算瓶頸問題，提出HCESMA 方法。硬約束生成要求在每個token 生成步驟都呼叫約束評估器（如 SQL 語法解析器、JSON Schema 驗證器、正規表示法引擎），當結合序列蒙地卡羅（SMC）粒子過濾器使用時，約束呼叫次數高達O(d · p · k)（其中d 為輸出token 長度，p 為粒子數量，k 為AWRS 平均拒絕次數），嚴重限制了在固定時間預算內可運行的粒子數量。
HCE-SMA 以AWRS-SMC 框架（Lipkin et al., 2025）為基礎，透過兩項加速機制達成提速：(1) 階層式快取增強（HCE）：在每次約束呼叫前加入兩層快取——全域無效前綴集合（利用前綴單調性）與上下文後綴快取（基於 K-Markov 充分條件）。前者保證與AWRS-SMC 的演算法等價性（在629 個
SQL 實例上以相同random seed 比較，粒子權重在十六位小數精度下完全相同）；後者則屬於有界誤差的近似，我們透過shadow mode 測量其與精確驗證器之間的disagreement 比率：SQL 與PM 為0%（48,387 次快取命中皆一致），JSON Schema 為0.441%；(2) 投機式多token 加速（SMA）：一次生成多個token 的草稿序列，僅進行一次約束驗證，並根據約束後驗分佈的形狀（單峰或多峰）自適應地選擇貪婪或隨機採樣草稿策略；其重要性採樣權重在nrej = 0 條件下與AWRS 等價，繼承無偏性。
在相同的時間預算下，HCE-SMA 可運行兩倍的SMC 粒子。以Llama 3.1 8B Instruct 在三個標準任務上進行評測：Text-to-SQL 準確率較AWRSSMC 提升10.2%，JSON Schema 生成提升2.9%，兩者均通過95% Bootstrap 信賴區間統計顯著性檢驗。在「半粒子預算」的對照實驗中（HCE-SMA p=5 vs. AWRS-SMC p=10），SQL 仍以+6.86 pp 領先並達成3.18× 速度加成，證實準確率提升並非單純來自粒子數加倍。實驗結果亦顯示後驗分佈的形狀會決定最佳草稿策略，此一發現對後續的受限生成研究具有參考價值。

Hard-constrained language model generation—where outputs must strictly satisfy formal constraints such as SQL grammar or JSON Schema—requires tokenlevel constraint verification at every step, creating a significant computational bottleneck. We propose hce-sma, built on top of the awrs-smc framework [9] and
incorporating two acceleration components: Hierarchical Cache Enhancement (hce) and Speculative Multi-token Acceleration (sma). hce introduces a twolayer cache that reduces constraint-evaluation cost by 44–45% on SQL and Pattern Matching (a per-call cost reduction that is, at fixed seed, algorithmically equivalent to awrs-smc). sma batches ddraft tokens into a single constraint call, delivering the end-to-end wall-clock speedup, and uses an adaptive draft strategy matched to the shape of the constrained posterior: greedy drafts for unimodal tasks (Text-to-
SQL, Pattern Matching) and sampled drafts for multimodal tasks (JSON Schema). Layer 2 of hce and the sma weight assignment provably preserve awrs-smc’s importance-sampling guarantees; Layer 3 is a K-Markov approximation whose deviation from the exact constraint we measure empirically (0% on SQL/PM over
48,387 cache hits; 0.44% on JSON over 25,415 hits). The reduced per-particle cost allows running 2× more smc particles within the same wall-clock budget, yielding +10.2% accuracy on Text-to-SQL and +2.9% on JSON Schema over awrs-smc (Bootstrap 95% CI excludes zero in both cases). A fixed-budget evaluation at half the particle count (hce-sma p=5 vs. awrs-smc p=10) further yields +6.86 pp / 3.18× speedup on SQL, confirming that the gains are not an artifact of particle count.

[1] Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling, 2023. URL https://arxiv.org/abs/2302.01318.
[2] Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 11733–11763. PMLR, 21–27 Jul 2024. URL https://proceedings.mlr.press/v235/du24e.html.
[3] Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. Grammar-onstrained decoding for structured NLP tasks without finetuning. In Houda Bouamor, Juan Pino, and Kalika Bali, editors, Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 10932–10952, Singapore, dec 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023.emnlp-main.674. URL https://aclanthology.org/2023.emnlp-main.674/.
[4] Saibo Geng, Hudson Cooper, Michał Moskal, Samuel Jenkins, Julian Berman, Nathan Ranchin, Robert West, Eric Horvitz, and Harsha Nori. JSONSchemaBench: A rigorous benchmark of structured outputs for language models, 2025. URL https://arxiv.org/abs/2501.10868.
[5] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, et al. The Llama 3 herd of models, 2024. URL https://arxiv.org/abs/2407.21783.
[6] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with PagedAttention. In Jason Flinn, Margo I. Seltzer, Peter Druschel, Antoine Kaufmann, and Jonathan Mace, editors, Proceedings of the 29th Symposium on Operating Systems Principles, pages 611–626. ACM, 2023. doi: 10.1145/ 3600006.3613165. URL https://doi.org/10.1145/3600006.3613165.
[7] Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 19274–19286. PMLR, 23–29 Jul 2023. URL https://proceedings.mlr.press/v202/leviathan23a.html.
[8] Alexander K. Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash K. Mansinghka. Sequential monte carlo steering of large language models using probabilistic programs, 2023. URLhttps://arxiv.org/abs/2306.03081.
[9] Ben Lipkin, Benjamin LeBrun, Jacob Hoover Vigly, João Loula, David R. MacIver, Li Du, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Timothy J. O’Donnell, Alexander K. Lew, and Tim Vieira. Fast controlled generation from language models with adaptive
weighted rejection sampling. In Second Conference on Language Modeling, 2025. URL
https://openreview.net/forum?id=3BmPSFAdq3.
[10] Jiayuan Mao, Freda Shi, Jiajun Wu, Roger P. Levy, and Josh Tenenbaum. Grammar-based grounded lexicon learning. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34, pages 7865–7878, 2021. URL https://proceedings.neurips.cc/paper/2021/hash/4158f6d19559955bae372bb00f6204e4-Abstract.html.
[11] Robert McNaughton and Seymour A. Papert. Counter-Free Automata. MIT Research Monograph No. 65. MIT Press, Cambridge, MA, 1971.
[12] Nishanth Sridhar Nakshatri, Shamik Roy, Rajarshi Das, Suthee Chaidaroon, Leonid Boytsov, and Rashmi Gangadharaiah. Constrained decoding with speculative lookaheads. In Luis Chiruzzo, Alan Ritter, and Lu Wang, editors, Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 4681–4700, Albuquerque, New Mexico, apr 2025. Association for Computational Linguistics. doi:10.18653/v1/2025.naacl-long.239. URL https://aclanthology.org/2025.
naacl-long.239/.
[13] Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=KmtVD97J43e.
[14] Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Anselm Levskaya, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference. In D. Song, M. Carbin, and T. Chen, editors, Proceedings of Machine Learning and Systems, volume 5, pages 606–624. Curran, 2023. URL https://proceedings.mlsys.org/paper_files/paper/2023/file/c4be71ab8d24cdfb45e3d06dbfca2780-Paper-mlsys2023.pdf.
[15] Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. PICARD: Parsing incrementally for constrained auto-regressive decoding from language models. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih, editors, Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 9895–9901, Online and Punta Cana, Dominican Republic, nov 2021. Association for Computational Linguistics. doi: 10.18653/v1/2021.emnlp-main.779. URL https://aclanthology.org/2021.emnlp-main.779/.
[16] Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-SQL task. In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun’ichi Tsujii, editors, Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 3911–3921, Brussels, Belgium, oct ”-” nov 2018. Association for Computational Linguistics. doi: 10.18653/v1/D18-1425. URL https://aclanthology.org/D18-1425/.
[17] Stephen Zhao, Rob Brekelmans, Alireza Makhzani, and Roger Baker Grosse. Probabilistic inference in language models via twisted sequential Monte Carlo. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 60704–60748. PMLR, 21–27 Jul 2024. URL https://proceedings.mlr.press/v235/zhao24c.html.