Thank you for your thoughtful feedback. We address the raised concerns below:

---

Regarding the practical relevance of SER in reasoning tasks

Thanks — this is an excellent point. We intentionally adopt the correctness — or more precisely, the validity — of the entire trajectory as the evaluation metric for sequence-level assessments, rather than relying solely on the final outcome.

It is widely acknowledged that verifying the correctness of a solution to a mathematical problem requires examining all intermediate steps, not just the final answer (as exemplified by the recent IMO proof verification process). The widespread reliance on final-answer evaluation of LLMs is largely due to the inherent difficulty of automatically assessing the full reasoning chain.

In fact, alongside our work, there has been a surge of recent research revealing the limitations of using only final outcomes. For example, [1] explores how agents can be used to verify reasoning paths, while [2] develops methods for identifying mistakes and correcting outputs. Additionally, a recent survey [3] provides a comprehensive framework for evaluating step-by-step reasoning traces.

We believe that the shift from outcome-based to path-based evaluation will happen soon, and our work will become even more impactful.

[1] Derailer-Rerailer: Adaptive Verification for Efficient and Reliable Language Model Reasoning, arxiv 2408.13940
[2] LLMs cannot find reasoning errors, but can correct them! arxiv 2311.08516v2
[3] Evaluating Step-by-step Reasoning Traces: A Survey, arxiv 2502.12289v1

Regarding the comparison between AR and MDMs

We have made every effort towards a fair comparison, and we believe the conclusion is well-justified.

In the first step, we compare open-sourced MDM and AR models in the left subfigure of Figure 1. However, this comparison inherently favors AR models, which were trained by top-tier industry labs with access to high-quality training data and extensive computational resources. Consequently, the superior performance of AR models in this setting may stem from these advantages rather than from fundamental framework-level differences. We acknowledge and discuss this limitation in Line 163.

To address this concern, we adopt a more controlled setting. As noted in Line 164, we decode the MDMs autoregressively from left to right, token by token, and use this as an "AR" baseline for comparison. Admittedly, this setup inherently favors MDM models, as the "AR" decoding is performed directly using the pre-trained MDMs, without any additional training via next-token prediction. Nonetheless, even under this unfavorable comparison for the AR baseline, MDMs fail to achieve both higher accuracy and greater efficiency.

Given the above discussion, we believe that both results together well support our conclusion: MDMs do not offer a better efficiency–accuracy trade-off compared to autoregressive models.

Regarding the generalization to conditional generation

Yes. These metrics can be extended to conditional generation settings with minor modifications.

---

Thank you once again for your thoughtful feedback. We hope our clarifications have adequately addressed your concerns, and we would be happy to answer any further questions.

Thank you for your feedback and comments. We have carefully considered each point you raised and will address them one by one below.

---

Regarding the soundness of the evaluation metric SER

Our primary motivation for introducing SER is to provide a metric for evaluating the validity of reasoning chains, particularly in tasks that require logically correct sequences, such as mathematics or code generation. These tasks involve highly structured data, where the set of correct sequences, $\mathcal{L}_q$, typically occupies a very small subset of the overall sequence space. Therefore, we believe our proposed metric — measuring the probability of generating a sequence outside the correct set — is reasonable.

This design is novel and has received positive feedback from all other reviewers. For example:

• “Measuring TER and SER on synthetic tasks could be a useful metric for future research on Diffusion LMs” — Reviewer 4VkA
• “...For sequence-level metrics such as correctness of reasoning or complete answers, diffusion models fail to offer benefits...” — Reviewer ZofZ
• “The authors provide insights on the strength of parallel sampling in terms of...sequence-level holistic accuracy metrics” — Reviewer Gs9S

You proposed two scenarios, and we demonstrate below that neither presents a problem for the SER metric:

• Case 1: The model distribution has the same support as the ground truth but a different probability assignment. In this scenario, SER = 0. For verifiable reasoning tasks, which may admit multiple correct solutions, SER = 0 is the ideal outcome, indicating that the model exclusively generates correct sequences.

• Case 2: The model distribution is nearly optimal but assigns a small probability $\delta$ outside the support set. Here, SER = $\delta$, which accurately quantifies the model's risk of producing an incorrect output with probability $\delta$.

From the perspective of reasoning accuracy, the model in Case 1 is superior because it never fails, whereas the model in Case 2 will fail with probability of $\delta$. SER correctly captures this distinction, favoring the model that is guaranteed to be correct.

Regarding the significance of the theorems

You misinterpret the theoretical results of the paper. Our target is not to establish the universal approximation capability of MDMs, but rather to rigorously investigate the efficiency–accuracy trade-off (the trade-off between approximation error and computational cost) in comparison to auto-regressive (AR) models. We have emphasized this point multiple times throughout the paper, including in the abstract (Lines 18–20), the introduction (Lines 35–37, 41–42, 64–66, 72–74), Section 4 (Lines 245–250, 292–297), and the conclusion (Lines 363–366).

We demonstrate that the number of sampling steps required by MDMs to achieve a given approximation error varies significantly depending on the evaluation metric:

• For TER (refer to line 240~250): Theorem 4.2 proves that an MDM requires only a constant number of sampling steps (independent of sequence length L) to achieve near-optimal TER. In contrast, AR models inherently require $L$ sequential steps. This result implies that for tasks prioritizing textual fluency (as captured by TER), MDMs offer a substantial theoretical efficiency advantage over AR models.

• For SER (refer to line 268~284): Theorem 4.4 proves that to achieve a low SER, the number of sampling steps required for the MDM must scale linearly with the sequence length L, indicating that the number of neural network executions is comparable between MDMs and auto-regressive models. Consequently, for tasks requiring strict reasoning correctness (as measured by SER), MDMs lose their efficiency advantage.

Regarding experimental design

We cannot agree that the paper only contains toy settings. Our theory is primarily motivated by experimental evaluations conducted in practical applications. See lines 155-170 for the detailed discussion. We observed that on reasoning benchmarks (GSM8k and MBPP), MDMs typically require more sampling steps to reach competitive performance to either AR models or the AR-style generation of MDMs, which diminishes their efficiency advantage.

To better understand these observations, we begin with a theoretical investigation. It is important to note that any theoretical result must be grounded in explicit assumptions. To bound the approximation error of MDMs and analyze the number of steps required to reach that bound, it is essential to specify the underlying ground-truth distribution. To this end, we focus on Hidden Markov Models (HMMs) and n-gram languages, which capture key characteristics of natural language in practical settings, and the theoretical findings reveal that MDMs may require a significant number of steps to achieve a good approximation, which is consistent with the experimental observations.

Regarding the relationship between SER and the performance on reasoning tasks

As stated in our response to Weakness 1, SER is intrinsically linked to performance on reasoning tasks. In many reasoning benchmarks, especially for the verifiable reasoning tasks, there are correct reasoning paths and answers. By verifying the correctness of the entire sequence, SER provides a much stricter evaluation than accuracy, which only considers the final answer. A model that consistently achieves a low SER demonstrates a reliable reasoning capability.

Regarding the calculation of SER

We have explicitly described how TER and SER are computed in practice. As stated in Line 235, “For robust evaluation, all reported TER and SER values are averages over 2000 generated sequences for each experimental setting.” In fact, we have also tried increasing the number of samples to 20000, and the estimated accuracy shows negligible differences compared to the results with 2000 samples, confirming the reliability and stability of our evaluation.

---

Thank you once again for your time and effort. We hope the clarifications and explanations above have adequately addressed your concerns, and we sincerely look forward to receiving your support.

Regarding the Practical Computation of SER

We have now grasped your message. SER is computed using standard Monte Carlo estimation together with a verifier. Specifically, we first randomly generate a set of sequences using the model, and then apply the verifier to determine their correctness (i.e., whether the sequence belongs to $L_q$). SER is then estimated based on the proportion of correct sequences.

Using Monte Carlo estimation is widely adopted in LLM evaluation. For example, in real-world tasks such as GSM8K, Math, and AIME, the mainstream evaluation protocol involves sampling outputs using $k$ different random seeds and checking whether at least one correct solution exists—commonly referred to as pass@$k$, where $k$ is usually a small number.

Developing the verifier is non-trivial. In our experimental setting for synthetic tasks, the ground-truth language $\mathcal{L}_q$ (an HMM with sparse transitions) is formally defined (construction details in Appendix F.1). We implement a perfect verifier that deterministically checks whether a generated sequence contains invalid transitions using the forward algorithm [1,2], thereby verifying whether the sequence belongs to $\mathcal{L}_q$. The reported TER and SER values are computed by averaging the verification outcomes over 2,000 generated sequences per experimental setting. We further verified the stability of this estimate using 20,000 samples, which showed negligible differences.

For practical reasoning tasks, various verification methods can be employed, such as final-answer checkers or neural network-based verifiers. Each verifier provides a different surrogate for SER. For instance, if correctness is judged solely based on the final answer, the resulting metric serves as a lower bound on the true SER—since a correct final answer may still contain errors in intermediate steps. By incorporating stronger verifiers that evaluate the full reasoning chain, the estimated SER can more closely approximate the true value.

We would like to thank you for highlighting this important writing issue twice. At a minimum, we should have clearly presented the general workflow for estimating SER, as well as the specific algorithm used in our experiments. Since NeurIPS does not allow direct revision of the manuscript, we would like to detail the intended modifications here:

a. In Section 4.1, we will introduce the general methodology for empirically estimating SER using a verifier combined with Monte Carlo sampling.

b. In Appendix F.1, we will provide a detailed description of the SER computation procedure for the target HMM experiment, including the construction of the verifier.

Thank you again for your questions and valuable comments, which have helped us identify key issues in our presentation. We hope this clarifies your concerns, and we greatly appreciate your insightful feedback.

[1] Wikipedia contributors, "Forward algorithm," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Forward_algorithm (accessed August 5, 2025).
[2] Eddy, Sean R. "Hidden markov models." Current opinion in structural biology 6, no. 3 (1996): 361-365.

Thank you for your follow-up question. Your understanding is correct--when evaluating SER, it is not only the correctness of the final answer that is considered. While accuracy considers only the final outcome, SER assesses the validity of the entire reasoning process. For example, consider the solution path to a math problem: $1 + 2 + 3 = 4 + 3 = 6$. As the final answer is correct, accuracy would label it as correct. But SER would mark it as incorrect due to errors in the intermediate steps.

We are also somewhat puzzled by your repeated question regarding how SER was specifically implemented in our experiments. If you are referring to the experiment in Section 5, we have already described the implementation in our previous response. Nevertheless, we would be happy to clarify it once again here.

In the experiment in Section 5, we study a synthetic setting in which sequences are generated by a sparse HMM model. After training the neural network model, we generate a set of sample sequences. To calculate SER, we determine whether each generated sequence has non-zero probability under the ground truth sparse HMM—this is equivalent to checking whether the sequence contains any invalid transitions with respect to the sparse HMM. This evaluation can be efficiently performed using the forward algorithm [1][2].

[1] Wikipedia contributors, "Forward algorithm," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Forward_algorithm (accessed August 5, 2025).
[2] Eddy, Sean R. "Hidden markov models." Current opinion in structural biology 6, no. 3 (1996): 361-365.

In the previous response, we also described how SER can be evaluated in general tasks through the development of strong verifiers, and we plan to make sufficient modifications to the paper regarding this clarification.

If you are referring to the experiment in Figure 1, please note that it serves as a motivating example and is not related to the computation or evaluation of SER. The reported accuracy only concerns the correctness of the final answer, which, as we discussed in our previous response, represents an upper bound on $1-\text{SER}$.

We hope this explanation addresses your concerns. Thank you again for your valuable feedback, and we kindly ask you to reconsider your evaluation.

Thank you for your engagement. We’re glad to have addressed most of your concerns and now arrive at the final—-and perhaps most critical—-one: the significance of the SER metric. To address this, we present a three-stage response.

Regarding whether "SER essentially characterizes the same thing as accuracy"

The potential mismatch between the correctness of the final output and that of the reasoning chain is a well-recognized issue and remains an active area of research in recent studies on large language models (LLMs). For instance, [1][2][3] demonstrate that when solving math problems, a model may apply an incorrect formula or make multiple logical errors that coincidentally cancel out—still yielding the correct final answer. Similarly, [4][5][6] show that a model might guess the correct answer without understanding how to derive it, generating a completely fallacious reasoning process.

Based on these related works, the intuition--"SER essentially characterizes the same thing as accuracy"-- is not correct.

[1] Solving Quantitative Reasoning Problems with Language Models, arxiv 2206.14858.
[2] Unfaithful explanations in chain-of-thought prompting, arxiv 2305.04388.
[3] Chain-of-thought reasoning in the wild is not always faithful, arxiv 2503.08679.
[4] Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting, arxiv 2305.04388.
[5] Measuring Faithfulness in Chain-of-Thought Reasoning, arxiv 2307.13702.
[6] Measuring the Faithfulness of Thinking Drafts in Large Reasoning Models, arxiv 2505.13774.

Regarding the essentials of the developing process-level metric

As SER doesn't equal final accuracy, we next demonstrate that its development is essential. Reviewer Gs9S raised a similar question, and we would like to quote our response to Gs9S here.

It is widely acknowledged that verifying the correctness of a solution to a mathematical problem requires examining all intermediate steps, not just the final answer (as exemplified by the recent IMO proof verification process). The widespread reliance on final-answer evaluation of LLMs is largely due to the inherent difficulty of automatically assessing the full reasoning chain.

In fact, alongside our work, there has been a surge of recent research revealing the limitations of using only final outcomes. For example, [7] explores how agents can be used to verify reasoning paths, while [8] develops methods for identifying mistakes and correcting outputs. Additionally, a recent survey [9] provides a comprehensive framework for evaluating step-by-step reasoning traces.

Although it is challenging, we believe that the shift from outcome-based to path-based evaluation will happen soon, and our work will become even more impactful.

[7] Derailer-Rerailer: Adaptive Verification for Efficient and Reliable Language Model Reasoning, arxiv 2408.13940.
[8] LLMs cannot find reasoning errors, but can correct them! arxiv 2311.08516v2.
[9] Evaluating Step-by-step Reasoning Traces: A Survey, arxiv 2502.12289v1.

Regarding the computation of SER with a verifier.

Regarding the computation of SER. As mentioned in our previous responses, with a sufficiently powerful verifier, we can use the Monte Carlo method to calculate SER. The accuracy of the SER calculation is directly linked to the capability of the verifier; a more powerful verifier yields a more precise result. [10] shows that a strong verifier can help Gemini find the correct reasoning trajectory and solve IMO-level problems, and your concern about detecting $1+2+3=4+3$ should be easily achieved.

[10] Gemini 2.5 Pro Capable of Winning Gold at IMO 2025 https://arxiv.org/pdf/2507.15855

Once again, we sincerely thank you for raising these thoughtful questions. They have helped us clarify our work, and we would be happy to incorporate these discussions into the paper if you believe they would be beneficial to readers.

We sincerely thank you for your insightful feedback and suggestions. Below, we address the listed weaknesses and questions in detail.

---

Regarding the use of HMMs and experimental evaluations

Our theory is primarily motivated by experimental evaluations conducted in practical applications, i.e., on reasoning benchmarks (GSM8k and MBPP), we observed that MDMs typically require more sampling steps to reach competitive performance to either AR models or the AR-style generation of MDMs, which diminishes their efficiency advantage.

To better understand these observations, we begin with a theoretical investigation. It is important to note that any theoretical result must be grounded in explicit assumptions. To bound the approximation error of MDMs and analyze the number of steps required to reach that bound, it is essential to specify the underlying ground-truth distribution. To this end, we focus on Hidden Markov Models (HMMs) and n-gram languages, which capture key characteristics of natural language in practical settings, and the theoretical findings reveal that MDMs may require a significant number of steps to achieve a good approximation, which is consistent with the experimental observations.

As you rightly point out, certain gaps between theory and practice still remain. Moving forward, we plan to follow your suggestion and extend our analysis to more realistic scenarios, including long-range dependency structures, syntactic hierarchies, and distributions derived from large-scale language model pretraining corpora.

Regarding infilling tasks

Specialized tasks, such as bidirectional infilling, can be effectively addressed using dedicated frameworks like BERT (masked language modeling) and diffusion models, which take the entire sequence as input and generate missing tokens conditioned on the surrounding context. In this paper, however, we focus on general NLP tasks. We agree that your suggestion — to compare MDM and AR on more specific tasks — is insightful, and we consider it a valuable direction for future work.

Regarding broader model comparison and benchmarks

In the submitted version, we have already included experiments on MBPP in addition to GSM8K. The observations and conclusions are consistent across both benchmarks. Due to space limitations, the MBPP results are presented in Appendix A.3, as referenced in Line 160.

To further address your concern, during the rebuttal period, we extended our comparison to include LLaMA 8B and conducted additional experiments on the HumanEval benchmark. The results are shown in the table below （* indicates AR baselines）. The conclusions remain consistent: MDMs fail to achieve both higher efficiency and better performance simultaneously in realistic settings.

Regarding the dependency of the number of steps

Thanks for the question. The number of steps in the theorem depends on the order $n$ of the Markov model (See line 238). The "constant" here mainly refers to the dependency on sequence length. We will make it clear in the next version.

Regarding the HMM in Theorem 4.4

Good catch — HMMs and n-gram language models are closely related. It's straightforward to show that all n-gram languages can be represented as HMMs, and HMMs can be transformed into n-gram models under certain conditions (e.g., finite state and finite-memory assumptions; a direct proof can be obtained using GPT).

The SER result in Theorem 4.4 also holds for n-gram languages, as the construction used in the proof of Theorem 4.4 can be viewed as an n-gram language with some modifications (detailed in Appendix E.7 and E.8). However, using the HMM framework offers several advantages, particularly in simplifying the proof construction and making it easy for the reader to understand. We will carefully consider both the unification of the proof and the consistency of the overall framework.

Regarding combining AR and MDM

This is an excellent suggestion — integrating diffusion-based text generation with speculative decoding is a very promising direction.

---

Thank you once again for your time and effort. We hope the clarifications and explanations above have adequately addressed your concerns.

Thank you for your valuable feedback. Here, we address your concerns and questions below:

---

Regarding experiments on additional benchmarks

In the submitted version, we have already included experiments on MBPP in addition to GSM8K. The observations and conclusions are consistent across both benchmarks. Due to space limitations, the MBPP results are presented in Appendix A.3, as referenced in Line 160.

To further address your concern, during the rebuttal period, we extended our comparison to include LLaMA 8B, Qwen2.5-3B and Qwen2.5-1.5B, and conducted additional experiments on the HumanEval benchmark. The results are shown in the table below (* indicates AR baselines). The conclusions remain consistent: MDMs fail to achieve both higher efficiency and better performance simultaneously in realistic settings.

Regarding the performance gap between AR and MDMs

We have made every effort towards a fair comparison, and we believe the conclusion is well-justified.

In the first step, we compare open-sourced MDM and AR models in the left subfigure of Figure 1. As you point out, this comparison inherently favors AR models, which were trained by top-tier industry labs with access to high-quality training data and extensive computational resources. We acknowledge and discuss this limitation in Line 163.

To address this concern, we have already adopted a more controlled setting. As noted in Line 164, we decode the MDMs auto-regressively from left to right, token by token, and use this as an "AR" baseline for comparison. Admittedly, this setup inherently favors MDM models, as the "AR" decoding is performed directly using the pre-trained MDMs, without any additional training via next-token prediction. Nonetheless, even under this unfavorable comparison for the AR baseline, MDMs fail to achieve both higher accuracy and greater efficiency.

Given the above discussion, we believe that both results together well support our conclusion: MDMs do not offer a better efficiency–accuracy trade-off compared to auto-regressive models.

Regarding comparison to smaller AR models

To address your concerns that MDMs with less steps should be compared with AR models with lower number of parameters, we conducted experiments to test the performance of Qwen2.5-3B and Qwen2.5-1.5B on GSM8K, MBPP and HumanEval benchmarks. The results on the HumanEval benchmark are listed in the above table, and results on GSM8K and MBPP are shown below. It is clear that in order to achieve comparable accuracy on the benchmarks, MDMs require much more time during inference, which aligns with our conclusion that MDMs do not offer a better accuracy-efficiency trade-off. For potential concerns on the fairness of comparison, please refer to the previous section.

Regarding continuous diffusion language models

No. Theorem 4.4 is specialized for the discrete masked diffusion model. It cannot be extended to continuous diffusion language models [1].

[1] Likelihood-Based Diffusion Language Models, arxiv 2305.18619

Regarding experiments in Section 5.1

In our experiments, both MDMs and AR models were trained until convergence. While the optimal perplexity in these synthetic datasets can be calculated, our trained MDMs and AR models have achieved the optimal perplexity on the validation sets (refer to line 316). We believe the comparison is fair enough.

---

Thank you again for your thoughtful feedback. We hope that these clarifications and additions will enhance the strength and clarity of the paper’s contributions, and we would be happy to answer any further questions.