Paper recorded by Signals 4 on 2026-09-30 in cs.CL. Abstract reproduced from arXiv; link to the original below.
Published 2026-09-30 on arXiv · recorded by Signals 4 on 2026-10-01
Category: cs.CL · 自然语言处理 · first seen 2026-10-01
Constrained generation aims to sample from language models (LMs) conditioned on hard constraints. Existing constrained-generation techniques for nondeterministic finite automaton (NFA) constraints either distort the distribution or sacrifice efficiency. Theoretically, this task reduces to counting the length-$n$ sequences accepted by an NFA (#NFA), and the exact #NFA problem is #P-complete. Recent