Response to Reviewer ZxMG

Thank reviewer for the comments and questions, as well as the time devoted! Please kindly notice that there might be some potential misunderstandings. Below please see our point-by-point responses:

---

C1: "In Figure 5, the authors compare the win rate between Beam Search and Reflection-Window (Greedy). However, since Reflection-Window (Greedy) primarily relies on greedy decoding with occasional (3.5%–5.5%) use of Beam Search, it is essential to include pure greedy decoding as a baseline for comparison. [The reviewer] strongly encourage the authors to add this comparison."

A1: Thanks for considering our experimental results. There might be some potential misinterpretation.

In Figure 5, we present the win rate of beam search against greedy decoding, and that of our approach against greedy decoding. In other words, the win/lose is not calculated between beam search and our approach, but compared against greedy decoding, respectively. We think the brief caption (due to space limit) might be the reason behind this misinterpretation, and we have modified it into "Figure 5: Comparison of win rates of beam search and our reflection-window decoding (both against greedy decoding) on MT-Bench across categories."

---

C2: "In Table 2, the authors compare the performance between Top-K/Top-P and Reflection-Window. The improved performance of Reflection-Window primarily highlights the effectiveness of Beam Search over Top-K/Top-P in this task. [The reviewer] strongly encourage the authors to include a pure Beam Search baseline for comparison."

A2: Thanks for the comment. There might be some potential overlook in our specified setting.

In Table 2, the "regular decoding" in our approach is Top-$k$/Top-$p$, and the difference between our approach and the vanilla Top-$k$/Top-$p$ baseline includes both the sliding-window reflection and the selective refinement mechanisms. Describing Table 2 as primarily highlighting the effectiveness of beam search might oversimplify the results, potentially overlooking the substantial improvements in computational efficiency and performance introduced by these additional mechanisms.

Regarding the pure beam search baseline, we included the evaluation results in Table 11, and the pointer was provided on line 344 (Right).

Response to Reviewer Fghj

We are very grateful for the thoughtful comments, as well as the time and effort devoted! Below please see our point-by-point responses:

---

C1: "There are a few more recent works/commercial practices (such as OpenAI O1/3 and DeepSeek R1) that uses a combination of reflection-aware chain-of-thought SFT and RL to achieve a similar computational goal of the proposed method."

A1: Thanks for the comment. We completely agree that recent works/commercial practices have explored various methods to enhance generated content (Sections 1 and 2). However, the fundamental limitation of autoregressive decoding itself remains under-explored. This gap represents a distinct perspective, different from high-level model behaviors or inference efficiency.

Furthermore, as you kindly pointed out, our method is versatile and provides practitioners additional flexibilities to incorporate different strategies (without the need to retrain or finetune).

---

C2: "[The paper] provides an interesting point of view for the community to rethink between the choice of 'computation through tokens' and 'computation through logits.' In this particular case, it is 'reflection as tokens' and 'reflection as logits' (change in values). This might reveal a deeper, unified story about how reflection in LLM works that could facilitate future research."

A2: Thanks for sharing the insight and the perspective! In light of your comment, we would very much like to include such discussion in the paper, and we sincerely hope that our work can facilitate future research. It would be greatly appreciated if you can kindly share pointers to where these terms were discussed.

---

C3: "[The reviewer] wonder if the authors could combine this with contrastive methods (e.g. before computation of saliency first baselining the likelihood by a smaller proxy model) to achieve more compelling results."

A3: Thanks for the thoughtful question. If we understood the comment correctly, by "contrastive methods" we are discussing the compatibility of our framework with contrastive decoding (CD), e.g., Li et al. (2023), O'Brien and Lewis (2023). CD utilizes a search-based decoding approach that contrasts LMs of different scales, for instance, an expert (larger LM) and an amateur (smaller LM). In principle, our approach is versatile and compatible with contrastive methods, and can be applied in various ways.

For instance, one can apply our reflection-window decoding on expert and amateur LLMs in parallel, and then continue with CD's method of factoring out undesired behaviors of smaller LMs while retaining good behaviors of larger ones. Alternatively, one can also apply CD first, and then design appropriate pausing criterion to incorporate our selective refinement framework. We leave these as interesting directions for future works.

Please kindly let us know if we accidentally misunderstood your comment.

---

Q4: "What's your understanding about the scalability of your proposed method, i.e. to what extent, it could enable the models to do complex tasks that it couldn't without the approach?"

A4: Thanks for the thoughtful question and for trying to go further. As the primary goal of this paper is to address the pitfall of the purely autoregressive way of decoding, we do not claim that our approach can enable high-level behaviors (e.g., complex new tasks) that are otherwise unattainable. However, as you kindly pointed out in C2, we sincerely hope our perspective can provide a distinct point of view for community to rethink about related issues, and facilitate future research.

---

References

Li, Xiang Lisa, Ari Holtzman, Daniel Fried, Percy Liang, Jason Eisner, Tatsunori Hashimoto, Luke Zettlemoyer, and Mike Lewis. "Contrastive Decoding: Open-ended Text Generation as Optimization." The 61st Annual Meeting Of The Association For Computational Linguistics. 2023.

O'Brien, Sean, and Mike Lewis. "Contrastive decoding improves reasoning in large language models." arXiv preprint arXiv:2309.09117 (2023).

Response to Reviewer Lq2Q

Thanks for the thoughtful and detailed comments, as well as the time and effort devoted! Below please see our responses to specific comments and questions:

---

Q1: "[Theorem 3.6] what does the ratio $\epsilon_L$ mean or how does it correlate with the discrepancy between the sequence obtained via greedy decoding and the MAP state? why we want to regenerate the last $d$ tokens when $\epsilon_L$ is 'small'"

A1: Thanks for asking about the $\epsilon_L$ term in our theoretical result. The denominator is the ground-truth joint probability of the length-$(L-1)$ stepwise-optimal response (obtained by greedy decoding), and the numerator is that of the length-$L$ globally-optimal response (obtained by MAP). Theorem 3.6 roughly states that if the model is very uncertain when trying to generate the $L$-th token, then there is an error in the generation history at the $K$-th token, and that $K < L$. Therefore, we need to get back to the token $K$ to start the revision.

In practice, we look back $d$ tokens and regenerate them. We also provide additional discussions on the choice of $d$ in Section 5.4 and Appendix B.1.

---

Q2: "Is it possible to analyze when the proposed approach is guaranteed to generate sequences with probability higher than beam search?"

A2: Thanks for the thoughtful question and for trying to go further. If there is no limit on computation and storage, unconstrained-beam-width beam search could yield the globally optimal output (through actual MAP), i.e., guaranteed to be of the highest probability and to outperform (or at least no worse than) any other approach (including the proposed approach).

With a fixed-beam-width beam search, the theoretical characterization of the generated length-$L$ sequence is highly nontrivial, since the frontier depends on the pruning at all previous steps. Please feel free to let us know if you would like suggest a way to perform such theoretical analysis.

---

C3: "Table 1 [...] the sequences generated from beam search should always have higher probability than that from greedy decoding (correct [the reviewer] if [they were] wrong)"

A3: Thanks for carefully considering our results. The metric in Table 1 is accuracy instead of joint probability.

In benchmark evaluations, it is difficult to precisely control the output length of different decoding methods. Directly setting a hard cutoff of token numbers may yield incomplete/insensible responses. Therefore, in Table 1 we present accuracies on MMLU (consistent with previous works).

---

C4: "Discuss the relation with Shih et al. (2023)"

A4: Thanks for providing the pointer to a related work!

Shih et al. (2023) proposed Long Horizon Temperature Scaling (LHTS), which samples from temperature-scaled joint distributions, to address the myopic temperature scaling in autoregressive models. LHTS optimizes for the long horizon likelihood of samples, and can enable a model to generate with a controllable long horizon temperature parameter through finetuning. In comparison, our work aims to address the pitfall of the purely autoregressive generation itself, and our approach is versatile and compatible with LHTS (Shih et al., 2023).

In light of your comment, we will incorporate the above discussion in the revised paper. Thanks again for providing the pointer.

---

C5: "Sec. 3 the notations used are overly complicated. For example, [the reviewer] don't see why $\mathbf{v}$ and $T$ need to be carried everywhere [..., the reviewer] don't see why something like $\widehat{\mathbf{x}}$ and $\mathbf{x}^*$ are not sufficient"

A5: Thanks for the comment on notation. When presenting the theoretical result, we explicitly keep length indices since lengths play an important role when evaluating the joint probability of a response. The longer the length, the lower the probability tends to be, and this is the case for both $\widehat{\mathbf{x}}$'s and $\mathbf{x}^*$'s.

For instance (we provided this example in lines 165--177), if we were to use 10 words to distinguish between joint and conditional densities, one might say "joint density combines all variables; conditional adjusts for known variables." However, if we can use 15 words, one might say "joint density reflects combined probabilities of all variables; conditional density adjusts probabilities given known variables." A fair comparison between $\widehat{\mathbf{x}}$ and $\mathbf{x}^*$ should be length specific. Therefore, we think $\widehat{\mathbf{x}}$ and $\mathbf{x}^*$ together with length indices help make this subtlety more transparent.

---

Reference

Shih, Andy, Dorsa Sadigh, and Stefano Ermon. "Long horizon temperature scaling." International Conference on Machine Learning. PMLR, 2023.

Response to Reviewer KVvm

We are very grateful for the insightful questions and constructive comments! Below please see our point-by-point response:

---

Q1: "the criterion requires the entropy of all past $d$ tokens to be above the threshold [..., but] would not trigger if the LLM is very uncertain about only one token. Is that a desirable behavior?"

A1: Thanks for carefully considering the pausing criterion. Yes, this is indeed a desirable behavior. Uncertainty can occur when the model does not know how to proceed (due to a previous error) or when there are multiple valid ways to proceed. Therefore, we aim to capture the trend of increasing uncertainty, reducing the false-positive triggerings while maintaining a low computational overhead.

---

C2: "It may be interesting to evaluate and compare difference choices for this pausing criterion."

A2: We totally agree, and this is exactly why we present Table 4 (varying entropy threshold $\sigma$) and Table 5 (varying window size $d$) in Section 5.4, and provide additional discussions and analyses (due to space limit) in Appendix B.1 - B.3, on window size, entropy threshold, and modification rate, respectively.

---

Q3: "How come the proposed algorithm performs better than beam search, when it is supposed to be a cheaper approximation?"

A3: Thanks for the thoughtful question. If there is no limit on the computation and storage, unconstrained-beam-width beam search will yield the globally optimal output through brute force. However in practice, since maintaining a full frontier quickly becomes intractable and a fixed beam width is often introduced as a hyperparameter.

Our algorithm can perform better since it tackles errors as the generation goes on, while vanilla beam search needs a larger beam width to be able to enclose all possible sequences that can be generated by our approach.

---

C4: "Assumption 3.3 about the LLM being an oracle (i.e. computes the exact conditional probabilities) seems farfetched"

A4: Thanks for carefully thinking about our theoretical results. There might be potential misunderstandings, please allow us to clarify in twofold:

(1) Together with Assumption 3.3, our theoretical results indicate that, even if with an oracle LLM, there is still suboptimality in the purely autogressive way of decoding. In other words, even if the LLM itself perfectly decomposes the (conditional) probabilities (which, as you pointed out, is a farfetched benefit to assume in practice), there is still no guarantee in obtaining the globally optimal sequence with purely autoregressive decoding.

(2) The purpose of Assumption 3.3 is to facilitate clear theoretical results, and our empirical evaluation does not rely on or employ this assumption.

In light of your comment, we have included above clarifications in our revised draft.

---

C5: "Overall the authors evaluate their method on a few different models and datasets. It would still be more convincing to see more diverse evaluation."

A5: Thanks for the comment. In our empirical evaluations:

• for models, we utilize models from different families, including Llama-3.1-8B-Instruct, Phi-3-Medium-128K-Instruct, Qwen2.5-14B-Instruct, Qwen2.5-7B-Instruct, Mistral-Nemo-Instruct-2407;
• for benchmarks, we consider MMLU (which include 57 diverse subjects, e.g., humanities, STEM, and social sciences, at varying difficulty levels) for evaluating reasoning performance and factual knowledge, and also MT-Bench for a fine-grained evaluation through multi-turn conversational task, including correctness, coherence, and fluency.

We provide pointers to our empirical results in List of Tables in Page 11. Please just kindly let us know if you have a specific evaluation task in mind.

---

C6: "Since it seems the end algorithm is a faster approximation of beam search, it would be great to measure the actual speedup."

A6: We totally agree, and that's why in Section 5.4 paragraph "Efficiency of Reflection-Window Decoding" we provide regeneration metrics by MMLU categories (humanities, STEM, social sciences, others), and also present additional analysis in Appendix B.3.

---

Q7: "What model is used in the synthetic setting? The setup for these experiments needs to be more detailed."

A7: Thanks for asking about the detail of our synthetic setting.

We use Llama-3.1-8B-Instruct. For each prompt, together with a certain length $\{0, 20, 50, 200\}$ of generation history ($0$ means only the prompt is given), we evaluate whether the joint probability of the sequence generated with greedy decoding is greater than or equal to that produced by (fixed-beam-width, set to $10$) beam search (as proxy of the global optimum). This comparison indicates the extent to which greedy decoding deviates from the globally optimal response.

In light of your comment, we have included above detail in the revised draft.