Summary
This paper focuses on the constrained decoding scenario where LLMs are expected to produce high-quality and grammatically correct outputs. It presents the adaptive sampling with approximate expected futures (ASAp) method, which is designed to enhance the quality of the output by adjusting the conditional probability to align with the model’s original output distribution while ensuring grammaticality. Central to ASAp is the development of effective approximations to the expected future grammaticality (EFG). More specifically, ASAp involves an extra sampling process, where the estimates of EFG are iteratively refined after each sampling and will eventually converge to exact EFG in the limit of infinite iterations. Experimental results show that the output probability distribution of ASAp is closer to the original one than that of GCD methods.
Strengths
Advantages of ASAp include facilitating more accurate grammatical predictions. ASAp approximates the desired distribution by considering the potential future grammaticality of sequences, whereas GCD typically samples greedily based on current probabilities without considering the future development of the sequence. This approach allows ASAp to more accurately predict and generate text sequences that comply with grammatical rules.
Weaknesses
The algorithm heavily relies on prior samples to estimate grammatical probabilities, which can be computationally expensive and difficult to manage, especially in cases where the dataset is large or the environment is dynamically changing. Moreover, a fair comparison of decoding speed between ASAp and GCD methods is required, as ASAp needs this sampling process to produce high-quality outputs, but conducting sampling on LLMs is very time-consuming.
Only evaluating the quality of the output by KL divergence and expectations is limited because the decoding sampling algorithm, except for the greedy search, does not always obey the probability distribution. For example, when the decoding temperature is set to 1, models may not output tokens with the highest probability. To conduct a more intuitive evaluation, one can choose some constrained decoding tasks with explicit quality scores, such as constrained translation [1] with BLEU and Exact Match, and code generation, which can be evaluated by the passing rate.
Since the experiments in this paper are based on prompt-motivated LLMs, a natural step is to fine-tune LLMs and see if they can produce grammatically correct output with high quality. On the other hand, the authors can also try ASAp based on fine-tuned LLMs, which may further boost the performance of ASAp.
To enhance the readability of the article, the following suggestions can be considered.
1. It’s more intuitive to give specific input and output examples for SLIA and INV-BV tasks.
2. The names GCD and GAD are too similar to easily differentiate, even after reading the paper.
3. Other typos: In line 289, the word “both” is typed as “bot”.
[1] Wang, S., Li, P., Tan, Z., Tu, Z., Sun, M., & Liu, Y. (2022). A Template-based Method for Constrained Neural Machine Translation. arXiv preprint arXiv:2205.11255.
Questions
Given previous samples with the prefix $w_{1:i}$, there exist abundant future tokens beyond just the next token. However, ASAp only uses the next token likelihoods to facilitate a better estimate of EFG. Why not use other future tokens?