Earley-Driven Dynamic Pruning for Efficient Structured Decoding

Q1: Although cache optimization is proposed in XGrammar (2024) a detailed comparison to compare the two is missing.

We appreciate the reviewer's concern. Section 4.3 addresses this comparison. Both methods categorize tokens into Context-Independent and Context-Dependent types, but we don't use suffix strings to identify invalid context-dependent tokens. For example, XGrammar precomputes all possible suffixes of { to reject tokens like {//ABC without the parser, while we don't. We omit this optimization because:

1. There's no theoretical guarantee that it significantly reduces context-dependent tokens across all grammars and vocabularies,
2. Precomputation overhead scales with grammar size.
3. Formatron already matches or exceeds XGrammar's throughput without it.

That said, this optimization is orthogonal to ours, so it is possible to include the optimization if needed.

Q2: Do you have a concrete example in the dataset where you can show techniques in 4.4 helps?

Thank you for your insightful question. When a context-dependent token is rejected by the parser, the bytes from the first to the byte that is rejected by the parser become a rejected prefix. For each unprocessed context-dependent token, if it shares a prefix with rejected prefixes, then it can be immediately rejected. This allows us to reject tokens with common prefixes faster. We collected following examples from experiments:

• prefix: "., token: "..\..\..\
• prefix: ="", token: =""></
• prefix: ="<, token: ="<?=$

Q3: From this viewpoint, a baseline is missing where only 4.5 is present

We agree with your suggestion. Here's the baseline with 4.5 only.

Q4: How do you explain the decrease about 3 times run?

Thank you for your careful review. Reviewer YX9o had the same question. To allow more space for addressing your other concerns in detail, please refer to our response to Reviewer YX9o: Q3.

Q5: No. However, I think it would be nice to mention that the NLP community has examined neural constrained decoding from 2016

We appreciate the reviewer's suggestion. We will incorporate Xiao et al. (2016) and Yin et al. (2017) in our revised manuscript as important references to this field's early work. We did not include them as baselines because:

1. Adapting these methods to transformer architecture would require significant engineering modifications and LLM continual pretraining.
2. The grammar state maintenance in these approaches would consume excessive memory when applied to LLM.

Q6: Sections 4.2.1 and 4.2.2 introduce the format and the associated graph, however, it is not clearly stated how such representations help the pruning. Adding this would enhance the paper's readability.

Thank you for requesting clarification on how the representations facilitate pruning. You're right that sections 4.2.1 and 4.2.2 would benefit from a more explicit connection to the pruning mechanism.

4.2.1 defines inter-item dependencies and lays the foundation for pruning: for independent items, removing one will not affect Earley actions on others. The enhanced Earley item representation emphasizes that while the same Earley item often spans multiple sets, its dependencies are only affected by its starting and end position. Thus, we need not search all Earley sets in between to find all its dependencies.

4.2.2 defines the dependency graph directly enables pruning since reachability closure is defined on this graph. A path from x to a is a dependency chain from a to x. If a (indirectly) depends on x, then x is reachable from a. That's why reachable items must be kept; removing them would disrupt the dependency chains required for correctness.

Q7: It is also important to know the throughput without constrained decoding

We appreciate your insightful question. The throughput metric in our manuscript is only applicable when constrained decoding component is present in the pipeline since it only measures the throughput of the constrained decoding component only. To answer your question, we conducted additional experiments on throughput for the entire pipeline, including the throughput without contrained decoding (w/o CD).

All constrained decoding methods require additional computation, of which our Formatron remains the fastest, almost approaching the speed of w/o CD.

Q1: In order to enhance clarity of Section 4, it would be useful to also include pseudocode.

We appreciate the reviewer's valuable suggestion regarding Section 4. We agree that including pseudocode would enhance the clarity of this section. We will incorporate pseudocode in the revised manuscript.

Q2: It would be nice to also report on some metric of the output such as accuracy or perplexity.

Thank you for your insightful suggestion. We have evaluated output quality using accuracy metrics. Our experiments show that the proposed method achieves competitive performance compared to previous methods. We will incorporate this additional analysis in the revised manuscript.

Q3: The Formatron algorithm's throughput degrades at 3 runs as seen in Table 2. Why is this the case? Is there anything different occurring in these different runs?

Thank you for your insightful question. The throughput variation in our initial 3 runs was likely due to resource contention on the shared server where we conducted experiments. After re-running tests on an idle server, we observed consistent improvements (see updated table). These new results confirm Formatron's throughput are stable. We will ensure all results in our revised paper are free from resource contention.

Q4: Due to the claims of reduction in memory consumption, it would be insightful to share empirical details or other analysis regarding this claim.

Thank you for your important question regarding memory usage. We conducted additional experiments on max memory usage(unit: MB) of the process during constrained decoding. We note that pruning does help reducing memory usage. We will include these results in the revised manuscript.

Q1: I think the background necessary for understanding this paper, as well as the core method, could be better explained, I had a hard time understanding it.

Thank you for this important feedback about the paper's accessibility. We acknowledge that the background and core methodology of our paper could be more clearly presented. Due to the 8-page limit, we had to balance background explanation with results. In our revision, we will carefully enrich the background section and methodology description, taking full advantage of the additional space available in the camera-ready version. Additionally, we will invite colleagues from diverse technical backgrounds to review our revised manuscript to ensure our explanations are accessible and clear.

Q2: I'm not sure how much algorithmic novelty there is here. Is this just an efficient implementation of an existing algorithm?

Thank you for this important question regarding the novelty of our approach.

Our work builds upon the Earley algorithm, which is fundamentally a theoretical framework. Our contribution lies in the innovative adaptations required to transform this theoretical construct originally designed for languages parsing into a practical solution for language model applications, which required developing both theoretical observations and theory-backed algorithm modifications rather than simply optimizing an existing implementation through engineering.

We have made several adaptations to bridge theory and practice:

1. We noted that constrained decoding only requires format recognition rather than obtaining complete parsing trees, implying the potential to prune states in a modified Earley algorithm.
2. We formalized the idea of high-level regular grammars, allowing us to show what kinds of substructures will lead to repetitive states in the context of format recognition and hence can be effectively pruned.
3. Based on these theoretical constructs, we developed a domain-specific pruning strategy to manage Earley states efficiently in the context of language model generation.

Q3: It would be helpful to provide a bit more of a primer for the key ideas/notation used in the paper.

We appreciate the reviewer's suggestion on how to improve readability. We will enhance the paper by:

1. Adding a comprehensive notation table for reference. The following table is a partial example.

2. Providing a more accessible introduction to key concepts before diving into technical details
3. Including intuitive examples for complex ideas

These improvements will make the paper more accessible.

Q4: Does this method have any important limitations?

We thank the reviewer for this important question on our method's applicability.

Our method has no fundamental algorithmic limitations. However, the primary challenge lies in the nature of constrained decoding approaches generally - can only be applied during inference time and cannot be directly integrated into the model training process. Integrating constraint-decoding directly into supervised and RL training represents a promising direction for future research.

Q5: Does it work for batched inference as well?

We thank the reviewer for this important question about our method's efficiency in large-scale inference settings.

Yes, Formatron fully supports batched inference. Our dynamic pruning and state caching mechanisms operate efficiently across multiple concurrent requests:

1. Our state caching system maintains separate pruned state sets for each sequence in the batch, allowing independent parsing paths from different grammars while sharing the same underlying algorithmic optimizations.
2. When processing multiple inputs simultaneously, Formatron's memory efficiency benefits become even more significant, as the dynamic pruning reduces the aggregate memory footprint across all batch elements.
3. The context-independent token mask cache is particularly effective in batched scenarios, as the precomputed masks can be efficiently applied across multiple sequences that share the same grammar constraints.

Q: I wonder if they are just the throughput of parsing & masking

Thanks for raising this important point on result presentation. We clarify that the throughput results in our paper indeed only reflect the parsing and mask generation stages, not the entire pipeline. We isolated these components to provide precise performance analysis of our key technical innovations.

You're right that entire pipeline performance measurement would be valuable. we conducted additional experiments on throughput for the entire pipeline, including the throughput without contrained decoding (w/o CD).

Since the entire pipeline result includes LLM calls and generation, the throughput will be much lower. As can be seen from the new experimental results, our Formatron is still the most efficient among all constrained decoding methods, almost close to of w/o CD.

Q: The style of subsubsection titles such as 4.2.1 seems mismatching with the other section titles.

Thank you for highlighting this formatting inconsistency. We appreciate your meticulous review of the document structure. We will ensure all section and subsection titles follow a consistent style throughout the paper in our revision.

Q: The 4.3 4.4 and 4.5 sections seem irrelevant to ZapFormat. Maybe you should describe them elsewhere.

Thank you for your valuable feedback on paper organization. We agree that these sections may not directly contribute to the ZapFormat. We will restructure the paper to place these sections in a more appropriate location that better serves the overall narrative flow of our work.

Q: How much do you think the speed of constrained decoding matters for reasoning models which have a really long output (thought) before calling some function?

Thank you for this excellent question regarding constrained decoding for reasoning models.

Our approach is flexible: for reasoning models with extensive thought processes, we can selectively apply constraints only to the function call portions, thereby maintaining efficiency comparable to non-reasoning models since the long reasoning output does not matter in this case. Alternatively, constrained decoding ensures that for ensuring thinking tags match, particularly for smaller models (7B parameters or fewer) or when processing out-of-distribution inputs. This helps maintain the paired tag structure required for proper reasoning format. For this case, the speed of constrained decoding is even more important since the number of constrained tokens could be enormous, much larger than non-reasoning models. This specific area is relatively unexplored though.

Hence, your question identifies an important research direction worthy of further exploration, especially when reasoning processes require specific formatting constraints and maintaining generation efficiency is necessary.