Step-by-Step Reasoning for Math Problems via Twisted Sequential Monte Carlo

We sincerely appreciate your recognition of the significance and novelty of our work. Here we mainly address your concern in terms of the MATH500 dataset.

How were the 500 problems selected from the 12.5K problems in the MATH dataset? Is performance expected to remain consistent across the complete dataset?

Following [1], we utilize the 500 problems (the same split in [1]) uniformly sampled from the whole dataset as the test set. This is a common practice employed in existing works [1][2][3].

Since we have already trained our model on most remaining problems, we verify the performance of our method on our on-hold validation dataset (500 samples). The result is presented in Appendix G Table 6, which is consistent with our result on the testing set.

[1] Lightman et al. Let’s verify step by step. ICLR 2024.

[2] Wang et al. Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations. ACL 2024.

[3] Sun et al. Easy-to-hard generalization: Scalable alignment beyond human supervision. NeurIPS 2024.

We would like to thank you for your positive feedback and constructive suggestions on our work. Please see below for the detailed responses to each of your concerns.

What are the computational costs associated with TSMC in terms of training and inference time compared to existing methods?

Thank you for your insightful question. Since TSMC needs to load two models simultaneously, its inference computational cost is around 2 times of the existing methods. We use a batch size 80 and the average time usage (in seconds) for each batch is shown below. For verification methods, there would be an additional 2 seconds atop the cost from parallel decoding.

However, this additional cost from the value network could be easily resolved by using a shared backbone for the generator and the value network, as in the classical actor-critic models.

Another source of computational latency comes from the asynchronous decoding of the steps across sequences, where the sequence with a shorter step needs to stop and wait for the sequence with a longer step. One potential solution is to define the step as a fixed number of tokens for a better parallelism, whose performance (denoted as TSMC-block) on MATH500 (Llemma) is shown below.

Overall, TSMC does not involve additional generation since the resampling step simply copies the promising sequences to replace the low-quality ones, without generating more candidate steps such as the backtracking. This ensures the potential of TSMC to be further accelerated in real-time applications. While the acceleration involves more infra optimizations to reduce the memory and inference costs, .e.g quantization, kv-cache, dynamic-batching, which are out of the scope of this work

In terms of the training time, we have no data about existing methods. In our case, we generate 80 samples for each problem on 8000 problems using the parallel decoding method. The cost is around $10s*8000=80000s=22.2h$. But what we observe is that only 2000~3000 problems (25% to 40%) are enough to saturate the training of the value network.

Thank you for your detailed and insightful questions on our work. Basically, we understand the concerns in some of the designs in our method, but we would like to remind the reviewer that all our designs have been verified through our empirical results. Here we provide a more intuitive explanation in why these designs work.

the proposal distribution $q(x_t|x_{1:t−1})$ is simplified to $p(x_t|x_{1:t−1})$. It may cause samples to deviate from the target distribution, introducing sampling bias

Our method is primarily an inference-time search algorithm and that is why we assume we only have access to a poor generator $p(x_t|x_{1:t-1})$. Similar assumption is also used in other verification methods such as [1].

However, this does not mean that we shall always stick to $q=p$. A better generator (e.g., via finetuning) would definitely improve the final performance of any verification method.

[1] Lightman et al. Let’s verify step by step. ICLR 2024.

Using a greedy strategy to iteratively optimize the intermediate target distribution can lead to a local optimum problem Do the authors consider further improvements, such as global optimization strategies?

We would like to kindly point out that TSMC is a sampling process rather than an optimization process, so the local optimum in the variance reduction would not lead to the “local optimum” in the generated samples.

In standard verification methods, there is no optimization of the variance, and in TSMC, we reduce the variance via informative intermediate targets. Although they are not globally optimal, they already take effect compared with standard verification methods.

When applying the Lagrange multiplier (Section A.2) to find the global optimum by zeroing the derivatives, it ends up with solving an ordinary differential equation with two boundary conditions at $t=1$ and $t=T$ and turns out to be unsolvable. Therefore, the globally optimal intermediate targets are not in a clean formulation and it is hard to approximate them in practice. But even with the global optimum, the variance would not be reduced to 0 unless the generative distribution is the same as the marginal target. So our locally optimal targets have already been a practically good choice under our problem setting.

However, learning the value function can often be unstable or divergent in many cases. Do the authors make any improvements or additional designs here?

We acknowledge that the value estimation could be unstable, but we would also like to point out this is exactly the advantage of TSMC against the greedy decoding method (concentrating all explorations on the partial sequence with the highest value).

In TSMC, if the value function is uninformative (not trained), say a constant, the stratified sampling strategy we used would simply make TSMC the same as the standard verification method without resampling. We also skip the first few tokens since the value estimation there could be inaccurate. We summarize these strategies in Section 4.1 TSMC details. In a nutshell, TSMC takes effect if the value estimation is informative and and brings no adverse effect if it is not.

Thank you for your recognition of the novelty and theoretical foundation of our work. Here we have included a detailed response with additional experimental results to address your concerns.

whether it can achieve similar results on relatively simpler mathematical datasets(without causing adverse effects), such as Addsub, MultiArith, and SVAMP.

Thank you for your insightful question. Following your suggestion, we have added a comparative experiment on the MultiArith dataset. Please see Table 4 in Appendix G for the details.

The results show that TSMC outperforms the baselines under all scenarios without bringing any adverse effects. All the inference-time parameters are kept the same over the three datasets (MATH500, GSM8K, Multiarith).

adding a comparison for w/o MV （zero-shot performance）in Table 1

Thank you for your suggestion, we have added the comparison in Table 1. The method is denoted as “Greedy” , using the greedy decoding strategy.

In Figure 4, why does the solving rate via TSMC show continuous and significant improvement with an increasing number of solutions for the same batch size (e.g., M=10)

We would like to first clarify that the batch size here refers to the resampling batch size of the TSMC rather than the number of voting samples $N$, where the latter is kept as a constant as 240 in this paper. $M$ is a TSMC-specific parameter not present in other methods.

The resampling batch size of TSMC refers to the number of samples used to form the categorical distribution for resampling in Equation 5. For example, when M=10, we would have 24 distributions and each distribution contains 10 categories.

The optimal number we find in Figure 4 is actually $M=20$. We hypothesize this is related to the weight degeneracy issue of importance sampling. When having a large resampling batch size, one sample with a large probability would dominate the distribution and lead to a bad diversity after resampling. So there is a tradeoff between the diversity and the variance. We treat the understanding of this phenomenon as a part of our future work as stated in Section 6.

In the algorithm pseudocode, is there any difference between 'concat' and 'cat' (Appendix B)?

Yes. ‘Cat’ is initially defined in Equation 5, whose meaning is the categorical distribution. ‘Concat’ simply means the concatenation. We have added one more comment in the pseudocode to clarify this.

Could you provide a more detailed comparison with Zhao's work (line 524)

Both works follow the classical framework of TSMC, while Zhao’s work is more focused on a general alignment framework while our method is primarily an inference-time search algorithm.

The major difference lies in our assumption that the generator is not powerful enough and refining the distribution of the generator is expensive (intractable step-level guidance), this is in line with the motivation of recently popular inference-time searching algorithms like MCTS, backtracking or o1 model. With this constraint, we can only use a suboptimal generator $q=p$ and need to address the potential large variance via more informative intermediate targets (Section 3.2).

In Zhao’s work, they allow the refinement of the generator via a tractable token-level guidance, but this token-level guidance would be expensive in case of long outputs since it needs the estimation of the twist objective at each token. This makes our work more significant under this setting (long output), for example, the multi-step reasoning task.

Thank you for your recognition in our effort to deal with the low-sampling efficiency problem (Problem I) in existing verification methods. Here we would like to clarify our approach in resolving the need for process supervision (Problem II) and the concern of using MATH500.

How does your method address problem II?

We have declared our solution to Problem II in Section 3.4, “Estimating the value function through independently sampled data from policy (generator) is a well-studied topic (Bertsekas, 2012). It therefore eliminates the need for explicit process supervision during training, as outlined in Problem II.”

Our TSMC method is based on the guidance from the value network. While the training of the value network only requires the data sampled from the generator and the correctness of the solution, without need of the process supervision. Notably, we only need to sample the data from the generator independently using the standard parallel decoding, meaning there is no roll-out from an intermediate step of a sequence as in tree search. So our method exhibits a high training efficiency as well (Problem II).

How math500 is being selected. How it works on the whole dataset.

Following [1], we utilize the 500 problems (the same split in [1]) uniformly sampled from the whole dataset as the test set. This is a common practice employed in existing works [1][2][3].

Since we have already trained our model on most remaining problems, we verify the performance of our method on our on-hold validation dataset (500 samples). The result is presented in Appendix G Table 6, which is consistent with the result on our testing set.

[1] Lightman et al. Let’s verify step by step. ICLR 2024.

[2] Wang et al. Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations. ACL 2024.

[3] Sun et al. Easy-to-hard generalization: Scalable alignment beyond human supervision. NeurIPS 2024.