Dear reviewer,

Thank you for your insightful and critical comments. For concerns regarding the narrow language scope and the manual engineering effort, please refer to the Restriction to sLua and its engineering effort section and the Adaptation to other languages section in the common response. For concerns regarding the performance bottleneck, we have improved our regex compilation method with a >3x speedup using a new lazy indexing algorithm, which makes it no longer a bottleneck. Please refer to the New speedup on the regex compilation step section for details.

Comparison with [Agrawal et al.], Monitor-Guided Decoding (MGD)

Thank you for pointing out this reference which we will add in our revision in addition to a proper discussion in the revised paper.

Compared to our approach, [Agrawal et al.] considers a narrower setting of semantic correctness: MGD is only concerned with the correctness on a small subset of language features, instead of on the entire program as in our paper or in [Poesia et al]. Their concrete method only handles derefencing an object and making sure correct identifiers would follow. This is far from making sure the entire program is semantically correct (as evidenced in the sub-80% compilation rate in their reported results). As argued in the common response, achieving 100% semantic correctness requires a revamp of the language design with a tailored parser. Hence, we strongly disagree with the reviewer’s assessment that our “advancement is weak over prior art.”

Moreover, MGD does not guarantee correctness even on dereferencing an object. Here’s a counterexample to their strategy proposed at the end of Section 2: If the LLM has a very long token that starts with a valid identifier and matches $w \cdot E \cdot \Sigma^*$ but ends in an invalid suffix, their algorithm can still accept this token, resulting in an incorrect program. In comparison, our token-healing algorithm is designed for handling such a case, where this last token will be rolled back before starting with the next regex.

Would it be possible to add results on a well-known public code-generation benchmark to demonstrate how the method performs in a setting that readers can readily compare against?

Since we propose a new problem (runtime-correctness guaranteed code generation in a constrained environment), we are not aware of any public benchmark focusing on this aspect, as most are targeted at generic problem solving. Our work introduces a novel problem: runtime-correctness guaranteed code generation within a constrained environment. To our knowledge, existing public benchmarks primarily focus on general problem-solving and do not specifically address this aspect. Therefore, we are unaware of any current benchmarks directly comparable to our proposed problem.

Could you include a brief ablation showing how much each of your three key contributions; non-extensible regex, token-healing, and hybrid fallback; contributes to success rate and latency?

The non-extensible regex and token-healing are essential parts of our algorithm - they cannot be swapped out. Without non-extensible regexes, we do not have a way to make constrained decoding terminate for regexes with wildcards (Ex. 3.1). Without token-healing, tokens cannot cross regex boundaries.

We provided an ablation study on the regex compilation step. We improved our previous hybrid approach (based on [Willard & Louf]) to using a new lazy indexing algorithm, getting a 3.8x speedup. This is also much faster than [Koo et al.] which we previously mentioned might have an improvement over [Willard & Louf] but our experiment shows otherwise.

Dear reviewer,

Thank you for your positive assessment. We will fix the reference problems that you pointed out in the revised version. Please refer to the common response that addresses other reviews’ concerns, and a new table showing a speedup of our new lazy indexing algorithm.

Dear reviewer,

Thank you for your positive review. For concerns about sLua and its engineering effort, please refer to the Restriction to sLua and its engineering effort section and the Adaptation to other languages section in the common response. We provide additional answers to the specific questions you raised below.

How scalable will the approach be to languages that will not satisfy the assumptions made in the paper? Is the idea that we will create a specific language version/parser to leverage this for new languages? Can this also help high resource languages like Java?

As discussed in the common response, sLua is carefully designed to achieve the linear-time parsing guarantee that we have. If we are okay with slower parsing speed, we could include more features into the language design. The framework of ToP—using modular CFGs to represent the language— is still applicable, except the size of the tree can be much bigger.

On the other hand, our target application is for runtime critical scenarios where there is no programmer involved. As such, the exact choice of the programming language is less relevant, as long as we have a compiler/interpreter to execute the program. We think sLua already provides a rich set of features (e.g. conformation to any prescribed API with any user-defined fixed-size types) and is sufficient for a lot of tasks such as in generative game scripting. On the other hand, as discussed in the common response, since the ToP gives us the AST of the program, we can also translate the resulting sLua to another host language like Java/C++. Such translation requires a bit of work compared to translating to Lua (which is what we did in our paper).

Dear reviewer,

Thank you for your positive comments. For a discussion of why we restrict sLua and not consider other languages, please refer to the Restriction to sLua and its engineering effort section and the Adaptation to other languages section in the common response. For ablative results on different strategies of regex compilation step, please refer to the New speedup on the regex compilation step section in the common response. We comment that other components of our algorithm are specially designed (in particular, ToP) and no alternative exists. Moreover, it is not possible to swap out parts of ToP because it essentially defines the sLua language.

Integration to XGrammar or Formatron?

Both XGrammar and Formatron focus on context-free grammars, in particular on JSON outputs. For instance, XGrammar requires a pushdown automaton formulation that is not applicable to the context-sensitive setting that we study. We would like to emphasize that our setting is sufficiently different from these works and requires a careful design of the grammar and a curated selection of language features from ground up.

Is this the best we can do with constrained decoding or are there more properties that we can guarantee with it?

Providing runtime correctness guarantees using constrained decoding is in a sense the ultimate goal from a compiler/static analysis point of view. However, as mentioned in our limitation section, the program being correct does not mean the program is necessarily high quality, as constrained decoding leads to distortion of distribution (App. C.9). It is an interesting future direction to investigate how other techniques, such as post-training, can improve the quality of the generated program in addition to the correctness.

How different is your algorithm from Mündler et al?

Thank you for pointing out this highly relevant concurrent work. We detail the differences below and we will revise our related works section to include this work.

• First, we focus on generating runtime-correct sLua code, whereas their goal is to reduce compilation error for TypeScript without guarantees to compile.
• Their prefix automaton is similar in spirit to our ToP, where every reachable state can lead to an accepting state. Both their prefix automaton and our ToP are built recursively based on the target language’s CFG. Both employ a type reachability algorithm (their Figure 3 vs our Section B.2.7). However, theirs is at a low-level, where the state transitions are on a character level. We operate on a terminal level of context-free grammar. Because of their lower-level design, their method likely requires a significantly higher amount of engineering (they reported >10k lines of Python code compared to our 2k lines of Python code for parsing sLua). Because of this, we expect our framework to be more extendable to other languages.
• We support type declaration in the generated code (e.g. generated effect types can later be used). This is not supported by Mündler. For a predefined type (e.g. Actor), it seems like Mündler’s approach additionally requires manual effort to build a prefix automaton for each of these types, whereas our approach is automatic. While they do support more features such as forOf loops, dynamic data structures (arrays, sets, and maps), these features can also be incorporated into sLua if we are only concerned with semantic correctness. Since our goal is on runtime correctness, we forbid dynamic data structures while providing workarounds such as safe callbacks.