[RFC / Discussion] Finite-Horizon Reachability Masking (GCLM) for Guaranteed Goal/Syntax Completion in O(1) Time

[uuuugi]

Hi @sgl-project team and maintainers,

First of all, huge thanks for building such an exceptional framework! SGLang's jump-forward decoding and compressed KV cache optimizations have set a great benchmark in structured generation[cite: 1].

I would like to open a discussion on a common edge-case limitation in current constrained decoding engines and propose a lightweight, $\mathcal{O}(1)$ solution called GCLM (Goal-Conditioned Reachability Logit Masker)[cite: 1].

---

🔍 1. Motivation: The Finite-Horizon Truncation Problem

Current grammar/regex-guided decoding engines (Outlines, SGLang, SynCode) enforce forward prefix validity $(\delta(s, v) \ge 0)$ under an infinite-horizon assumption[cite: 1].

However, under strict per-request token budgets ($T_{\max}$) or multi-step agent tool executions:

• The model eagerly enters valid deeper syntactic branches (e.g., nested JSON keys {"meta": {"id": ...) that mathematically cannot reach an accepting/goal state within the remaining budget $T_{\text{rem}}$[cite: 1].
• This results in abrupt truncation with invalid syntax (unclosed braces/brackets) or infinite retry loops in agentic workflows[cite: 1].

---

💡 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}}$:

1. Vectorized Offline BFS Precomputation:
   Precomputes a compact 2D boolean reachability table $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)$$

2. Strict $\mathcal{O}(1)$ Online Logit Masking:
   During autoregressive sampling, the logit processor validates candidate tokens via a single contiguous tensor lookup:

$$\mathrm{valid_tokens}(v) = (\delta(s_{\mathrm{curr}}, v) \ge 0) \wedge R[T_{\mathrm{rem}}-1, \delta(s_{\mathrm{curr}}, v)]$$

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

• 100.0% Valid JSON Parsing: Across tight token limits ($T_{\max} \in [4, 16]$), GCLM achieves a 100.0% valid parse rate where forward DFAs fail up to 54.4% of the time[cite: 1].
• Agent Trap Elimination: Achieves 100.0% goal completion in multi-step tool-use benchmarks (pruning unfinishable subtrees and eliminating retry traps)[cite: 1].
• Latency Reduction: Up to 40% reduction in total generation latency via proactive early structural closure[cite: 1].

---

🔗 4. Resources & Open-Source Artifacts

• Hugging Face Project & PDF Paper: https://huggingface.co/uuugi/gclm-constrained-decoding
• GitHub Repository: https://github.com/uuuugi/Goal-Conditioned-Reachability-Logit-Masker

💬 Discussion & Collaboration

• Would this finite-horizon reachability masking be a valuable optional backend / logit processor mode for SGLang?
• If the community and maintainers find this useful, I would love to contribute and collaborate on a PR!

(PS: I am currently submitting this work to arXiv cs.CL for the first time. If any eligible endorsers here find the work sound, an endorsement via arXiv Endorsement Link or code OEPJVR would be deeply appreciated!)

Looking forward to your thoughts and feedback!