Approximately Aligned Decoding

We thank reviewer ViLc for their comments.

Lack of related work

Our intention was for Sections 2 and 3 to collectively serve as an extended related work, with more detailed comments on each method in context, rather than a separate related work section. However, if the reviewers collectively agree that an explicit section would help clarify the presentation, we can incorporate a separate related work section.

The contribution is a bit marginal, which is an incremental combination of ASAp and speculative decoding.

We respectfully disagree. The novelty of the proposed method has been acknowledged by the reviewers; one has pointed out that we are underselling the novelty as a combination of ASAp and speculative sampling. We will improve the presentation to address the issue.

It is nontrivial to combine these ideas to solve an important problem, and we are unaware of any similar work in literature. Additionally, part of our contribution is showing that ASAp and constrained decoding exist as two ends of a spectrum, with AprAD in the middle of the two methods.

AprAD may underperform ASAp in certain tasks, while only about 1.4 times efficiency improvement

Our method is intended to serve as a useful midpoint between constrained generation and ASAp---a reasonable default that can be overridden in cases where maximal speed or maximal conformity to the LLM probability distribution is required. Our method is on the Pareto frontier of generation ratio versus accuracy.

Why does ASAp perform so well in Table 3, while being much worse in Figure 2?

Our method performs well relative to ASAp in the lipogram task because if a specific generation is rejected, then it is still likely for any other generation to be a violation. Even after attempting many generations, ASAp can only output a few tokens without the banned letter. Our method is able to overcome this, resulting in a large relative improvement.

In contrast, if a hallucinated method is rejected during code generation for the BigCodeBench task, it is unlikely for the LLM to repeatedly attempt to generate additional hallucinated methods, so ASAp is able to cope with this for a 47-56% overhead for the problems shown in Table 3. Even still, our method achieves near-equivalent accuracy with only a 6-8% overhead. This reduction represents a substantial latency improvement for users of a coding assistant, where user experience is highly sensitive to latency.

Thank you for your kind response.

• Regarding the "related works," I believe there are subtle distinctions between the preliminary section and the related works. The preliminary section is meant to provide the technical foundation, while the related works offer a broader perspective on the field. Experts in the area might skip the related works, but a general audience could gain an initial understanding of the area. You could include studies that are not directly related to your paper, which wouldn't fit in the preliminary section. This is just my personal opinion, but I do believe that most papers accepted by ICLR follow this.
• Regarding "content length," let me elaborate: it is surprising to the reviewer that the paper is not more than 8 pages, while the recommended length for ICLR is 9-10 pages. Although we know that the core idea is what's most important, this might give readers the impression that the paper is not "thoroughly" written. It would be better to polish the introduction, as many people only read that section. For example, you could explicitly list your contributions, intuitively explain your method, or provide more background information.
• For the "performance v.s. ASAp", I appreciate your response . Could you make it clear that which kind of task is more appropriate for AprAD in the revision?
• For the "contribution", I will read other reviewers' comments and reconsider this later.

Hi, after reading other reviewers' comments and checking some details, I have some additional questions:

• After checking the experiment details, I find the metric for lipogram not trustworthy: only 4 human raters (small number), no background introduction (might be biased). Therefore, in the trivial Lipogram tasks, it is not reliable that whether the improvement makes sense at the cost of 4 times computation cost compared with constrained decoding, especially given that AprAD is still biased. A way to resolve this concern is to conduct some systhetic tasks like “no more than $3$ words containing $A$”, then the constrained decoding immediately cannot work, and the advantages can then be presented in a reliable way.
• How is addBadExample implemented for LLM? The renormalization propogation is not trivial for large models. Could you provide some insights?

We thank reviewer WHQc for recognizing the importance and novelty of our work, and for the insightful suggestions on improving the presentation. We will incorporate the changes in the paper.

This work tackles an important task of decoding from language models under constraints…which is an interesting topic in the larger picture.

Thank you very much for the comments and we completely agree with the reviewer's assessment. We will enhance the introduction section accordingly.

Throughout the entire paper, the idea is presented as a combination of ASAp and speculative sampling.

We agree with the reviewer on this. The main commonality between our proposal and speculative sampling is the backtracking algorithm that is able to retain an existing sequence as far as possible, yet conform to a new distribution. There are many differences, as the reviewer pointed out: the "target model" in our method is not a model, but rather cached, modified, and re-normalized probabilities; we start from the beginning rather than working on draft segments; and our focus is not on parallelization-induced efficiency, but rather efficiency from smart backtracking. We will enhance the presentation accordingly.

We can also move Appendix C into the main text and discuss how ASAp and constrained decoding fit the spectrum of the generalized framework.

It would be interesting to have a complete pseudocode of all related techniques.

We agree on the value of including details of how the algorithm is implemented in a larger system. Indeed, the conditional probabilities of each step along the way are pre-computed and saved in our implementation, so there is no need to re-evaluate the LLM as if SpecSample were used without modification. We plan to expand the pseudocode with additional details to distinguish our method compared to conventional speculative sampling, and to include additional information about caching and our data structures in the appendix.

Line 225

Thank you for pointing this out; we will fix this.

The experiments are designed to meet the assumptions of the methods.

While the lipogram experiment is admittedly synthetic to demonstrate the difference between different methods, we believe that the BigCodeBench task represents a real-world use case. The results, albeit less dramatic, represent practical values in an AI application, as every reduction in hallucination translates to developer productivity gain.

In AprAD, are the probability tables that lead to the current decoding cached?

Yes.

Is the caching the main reason why it requires fewer evaluations of the language models?

No. ASAp uses a similar caching mechanism; the reduction in generation ratio is because AprAD reuses part of the already-generated prefix.

Is it possible to introduce hyperparameters to control the behaviors of the proposed approach?

Yes---while we did not run extensive experiments on this, we believe that the best place to introduce such a hyperparameter is likely as an exponent to $r$ in line 3 of Algorithm 2 (SpecSample}). Let's call the hyperparameter $h$, so this line becomes $r \leftarrow (P(\ldots) / S(\ldots))^h$.

Of course $h=1$ gives AprAD unmodified. $h=0$ means that $r$ always equals 1; this procedure yields behavior equivalent to constrained generation. As $h$ approaches infinity, $r$ trends towards $0$, yielding behavior equivalent to ASAp. Any values of $h$ between these two extremes will trade speed and conformance to the distribution.

We will include a discussion of this in the paper or an appendix.

We thank reviewer 92k1 for their insightful review and accurate summary of our contributions. We do believe that this paper represents an effective and principled solution to an important problem in AI applications.

Line 199

Correct, Deterministic Finite Automata. We will clarify this in the paper.

We thank reviewer xsaW for their thoughtful feedback and helpful suggestions. We respond to each of these below, and will incorporate the corresponding changes into the paper.

Regarding posterior estimation approaches

For a task such as lipogram generation, the posterior probability of constraint satisfaction is very close to 0 for almost all prefixes, so estimation techniques generally have difficulty with this estimate. Furthermore, especially for longer generations, the posterior probability may or may not be influenced by anything inherent in the prefix text.

For example, there is nothing inherent about the prefix "Long ago" compared to the prefix "In a galaxy far away" that makes the remainder of the story more or less likely to contain a letter 'e'. In either case, the probability of it doing so is almost exactly 1. In contrast, a misleading comment during code generation can cause the LLM to hallucinate a method in the following line.

We found during preliminary experiments that Lew et al. 2023 and Zhang et al. 2024 likely both suffered from estimation issues on the lipogram task. Additionally, Lew et al. 2023 requires a potentially large number of samples to estimate the posterior---especially when all probabilities are near-zero---negating any overhead benefit, even with the performance optimizations introduced with that method. Zheng et al. 2024 requires a separate training step to obtain the HMM, and is unable to express the constraint of the BigCodeBench task. For these reasons, we chose to focus our comparisons against ASAp and constrained generation. We will add a discussion of the task-dependent pros and cons between sampling-based and posterior estimation-based methods in the paper, and describe factors that a practitioner may consider when deciding on a method.

Differs from examples in ASAp

ASAp excels in tasks where there are a few high-probability errors, but its evaluation tasks don't include cases where there are dense low-probability errors. We chose lipograms due to this factor, as well as its straightforward explanation and intuitive evaluation. We included BigCodeBench as a difficult real-world code generation problem where the solution requires use of libraries, and hence where generation can benefit from hallucination detection and avoidance.

FUDGE

We were unaware of FUDGE; thank you for pointing it out. It is a relevant work, and we will discuss it in our section about posterior estimation methods and tradeoffs between different approaches. While we haven't run experiments on FUDGE, the discriminator would need to learn to distinguish posterior probabilities extremely close to zero for the lipogram task; as discussed above, this probability would largely depend on arbitrary behavior in the language model rather than on the content of the prefix. While FUDGE would likely succeed on the BigCodeBench task, it would require an additional training step to obtain the discriminator, and its performance would be dependent on the discriminator's generalization ability.

Membership in $\mathcal{B}$ must be determinable by any prefix

This is true, but we do not consider this a major limitation. For example, in the Python example where it is impossible to determine whether example(foo.bar is a hallucination (line 367), it is still valid to reject the generation after a close parentheses is generated without defining foo. If the close parentheses are high-probability, AprAD will likely backtrack several tokens, rather than trying to generate a low-probability completion with (for example) a generator expression as constrained generation must do.

It's stated that the main weakness of ASAP… Every generation violating the constraint must be added to $B$

Like with ASAp, when AprAD generates a sample that does not violate the constraint, that sample is accepted and returned, even if $B \neq \mathcal{B}$. AprAD will usually require finding fewer violating samples before finally succeeding, because it usually won't throw away the entire prefix of tokens that has been generated so far.