יום שני, 16 בנובמבר 2026 LIVE
AI־INFO

כתבה arXiv cs.CL ·

ייצור שפה באמצעות NFA עם HMMs

Provably Tractable NFA-Constrained Language Generation via HMMs
חוקרים הציגו NFA-LM, מנוע ייצור שפה חדש שמאפשר ייצור מותנה על ידי אוטומט סופי לא דטרמיניסטי (NFA). המנוע מבטיח ייצור יעיל ואיכותי עם שגיאת קירוב מוגבלת. המחקר מראה כי NFA-LM יכול לייצר פלטים איכותיים עם שגיאת קירוב תאורטית.
תקציר מקורי באנגליתarXiv:2609.40185v2 Announce Type: replace Abstract: 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 work has shown that #NFA admits a fully polynomial randomized approximation scheme (FPRAS). Inspired by this result, we propose NFA-LM, a polynomial-time engine for NFA-constrained generation with theoretical guarantees under mild assumptions. Experiments show that NFA-LM efficiently generates high-quality outputs with theoretically bounded appr
קרא במקור המקורי