Repository navigation
[Show and Tell / RFC] Finite-Horizon Reachability Masking (GCLM) for Guaranteed Goal/Syntax Completion in O(1) Time #2028
uuuugi
started this conversation in
Show and tell
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
Hi @outlines-dev and maintainers,
First of all, huge thanks for building Outlines! It has set the gold standard for grammar-guided and regex-constrained LLM generation.
I would like to share an idea and open an RFC/discussion on a finite-horizon edge case in constrained decoding, along with a lightweight,$\mathcal{O}(1)$ solution called GCLM (Goal-Conditioned Reachability Logit Masker).
🔍 1. Motivation: The Finite-Horizon Truncation Problem
Current grammar/regex-guided decoding engines enforce forward prefix validity$(\delta(s, v) \ge 0)$ under an infinite-horizon assumption.
However, under strict per-request token budgets ($T_{\max}$ ) or multi-step agent tool executions:
{"meta": {"id": ...) that mathematically cannot reach an accepting/goal state within the remaining budget💡 2. Proposed Mechanism: GCLM
Instead of evaluating prefix validity forward only, GCLM integrates backward reachability with respect to the remaining step budget$T_{\text{rem}}$ :
Vectorized Offline BFS Precomputation:$R \in \mathbb{B}^{(T_{\max}+1) \times |S|}$ in a few milliseconds offline:
$$R[t, s] = R[t-1, s] \vee \big(\exists v \in \mathcal{V} \text{ s.t. } \delta(s, v) \ge 0 \wedge R[t-1, \delta(s, v)] = \text{True}\big)$$
Precomputes a compact 2D boolean reachability table
Strict$\mathcal{O}(1)$ Online Logit Masking:
$$\mathrm{valid_tokens}(v) = (\delta(s_{\mathrm{curr}}, v) \ge 0) \wedge R[T_{\mathrm{rem}}-1, \delta(s_{\mathrm{curr}}, v)]$$
During autoregressive sampling, the logit processor validates candidate tokens via a single contiguous tensor lookup:
Runtime latency remains flat and invariant to the state count$|S|$ (<0.4 ms on CPU, <0.05 ms on GPU).
📊 3. Key Benchmark Results
🔗 4. Resources & Open-Source Artifacts
💬 Discussion & Collaboration
CFGLogitsProcessoror the regex FSM index)?(PS: I am currently submitting this work to arXiv
cs.CLfor the first time. If any eligible endorsers here find the work sound, an endorsement via arXiv Endorsement Link or codeOEPJVRwould be deeply appreciated!)Looking forward to your thoughts and feedback!
All reactions