For Question 1

The verification model $\mathcal{V}$ is the original s1.1-32B model (reported in the Training Details paragraph of Section 4.1, line 178).

For Question 2

We have already explained the meaning of the circles and their color intensity (reported in the description of Figure 1).

To be precise, all circles are of a consistent size, with each representing a thought step.

The color of each circle indicates its importance, a value quantified by the Bidirectional Importance Score (BIS) from Section 3.1. Consequently, a darker shade signifies a higher importance score.

For Question 3

Following prior works such as Retro-Search, ThinkPrune, Length-filtered Vote, and SEAL, we split reasoning steps using "\n\n".

Building on this, we are the first to propose a "thinking span" strategy. When an individual thought step $\mathbf{t}^{(n)}$ is to be explored, we instead select a span centered around it:$\mathbf{r}^{(n)}=\langle \mathbf{t}^{(n-1)}, \mathbf{t}^{(n)}, \mathbf{t}^{(n+1)}\rangle,$where $\mathbf{t}^{(n-1)}$ and $\mathbf{t}^{(n+1)}$ are the immediately preceding and succeeding steps of $\mathbf{t}^{(n)}$. This method allows the A* search process to simultaneously consider both the physical order of the original thought path and the logical, importance-based order of the BIS queue.

For Question 4

We are grateful to the reviewer for this insightful suggestion. We reran the A*-Thought evaluation on MATH-500 and LiveCodeBench, this time using a best-of-N strategy (with N=8) to calculate pass@k. The findings indicate that A*-Thought and test-time-scaling strategies can be used in combination. These results will be integrated into the final version of the paper.

For Weakness 1

Our training data is independent of the test sets (reported in the Training Data and Verification Model paragraph of Section 4.1, lines 177-178).

A*-Thought was run on the 1K training data, this involved a 5.2-minute BIS scoring stage and a 7.43-hour A* search stage. For different benchmarks, the computational cost of our method is then proportional to the length of the output tokens required at inference time.

Crucially, A*-Thought also demonstrates remarkable generalization. Though trained only on math, our supplementary evaluations on LiveCodeBench and MMLU confirm that it successfully applies the A*-Thought pattern to non-math tasks (e.g., coding, history, computer science, law).

For Weakness 2

We are grateful for the reviewer's insightful suggestion. We conducted new experiments by training the Qwen2.5-7B-Instruct and Qwen2.5-14B-Instruct on data compressed by A*-Thought and benchmarking their performance against the TokenSkip baseline. The results affirm that A*-Thought is robust and maintains its effectiveness across different model sizes. These new results will be incorporated into the final manuscript.

For Q1

Each thought step $\mathbf{t}^{(n)}$ is a complete sentence (reported in Section 3.1, line 105).

Following prior works such as Retro-Search, ThinkPrune, Length-filtered Vote, and SEAL, we split reasoning steps using \n\n. Our process begins by extracting the content between the model-specific identifiers, <think> and </think>. This content is then segmented by \n\n to generate a set of thought-step sentences. Following the subsequent bidirectional importance scoring and A* search phases, we identify a minimal subset of these steps, which forms the compressed reasoning output.

For Q 2

$\mathrm{NLL}(\mathbf{y} | \mathbf{x})$ reflects the probability of obtaining $\mathbf{y}$ under the condition of $\mathbf{x}$, where $\mathbf{x}$ and $\mathbf{y}$ are distinct sentences.

Given that each thought step $\mathbf{t}^{(n)}$ is a complete sentence, we can easily calculate Negative Log-Likelihood (NLL) using language models (e.g., GPT-2):

For Question 1 / Weakness 1

We thank the reviewer for their valuable suggestion. We tested A*-Thought's generalization on the out-domain benchmarks LiveCodeBench and MMLU across diverse domains such as coding, history, computer science, law.

The results demonstrate that the model successfully learned the A*-Thought pattern, achieving higher efficiency and performance on non-mathematical tasks. We will incorporate these findings into the final version of the paper.

For Question 2

Verification model $\mathcal{V}$ is the original model of s1.1-32B, which was fine-tuned on the original s1K-1.1 dataset to preserve its long reasoning abilities. It is worth noting that the verification model was not fine-tuned on the compressed data.

For Limitation (a)

We are grateful for the reviewer's insightful suggestion. Accordingly, we have performed a sensitivity analysis to explore the impact of varying the hyperparameters  $\alpha$, $\beta$, $k_{\mathrm{max}}$. This was done by evaluating the A*-Thought-QwQ-32B model on the ARC and LiveCodeBench benchmarks with 512 tokens budget. We will update the final version of our paper with these experimental results.

For Limitation (b)

Theoretically, Bidirectional Importance Score (BIS) is designed to find the most important reasoning steps. However, some key steps, like formulas, may get low scores when they're isolated.

To address this, we propose the "thinking span" strategy. Instead of picking just one step $\mathbf{t}^{(n)}$ in A* search, we grab it along with its immediate neighbors: $\mathbf{r}^{(n)}=\langle \mathbf{t}^{(n-1)}, \mathbf{t}^{(n)}, \mathbf{t}^{(n+1)}\rangle,$ where $\mathbf{t}^{(n-1)}$ and $\mathbf{t}^{(n+1)}$ are the immediately preceding and succeeding steps of $\mathbf{t}^{(n)}$. This method preserves local context, counteracting the effects of information fragmentation and reducing potential semantic drift.

For Limitation (c)

Since the validation model is fine-tuned from the safety-aligned Qwen2.5-32B-Instruct, it also provides a degree of filtering for potentially harmful content during the A* search process.

For Weakness 2

We thank the reviewer for their valuable suggestion. To make the experimental results more robust, we conducted multiple-runs and reasoned 5 times, taking the average as the final result, and attaching the overall standard deviation after the result.

For Weakness 3

To our knowledge, A*-Thought is the first work to adapt the principles of A* search for this task.

Our method is fundamentally different from these predecessors.

• vs. Retro-Search: A*-Thought performs a systematic, global search based on importance. Retro-Search does a local, sequential exploration.
• vs. TokenSkip: Our BIS metric is both question and solution aware, whereas TokenSkip's is agnostic to global context information. We compress at the sentence level to preserve meaning, while TokenSkip works at the token level. Thus, despite a shared objective, our methodology is unique.

Beyond just guiding A* search, BIS metric also serves as a novel metric for analyzing the intrinsic importance mechanisms within long CoT. This aligns with a growing body of recent work (e.g., Token Entropy, Thought Anchors). We hope it provides a solid foundation for future research in this area.

For Weakness 4

Following DeepSeek-R1-Distill-Qwen, s1, SkyThought, Bespoke-Stratos, 32B size is strong mid-scale model that is sufficient for long CoT. Based on this, we have centered our efforts on the 32B model scale.

For Weakness 5

On our 8 A100 GPUs, training the s1-32B on its original 1K dataset took 3.84 hours, training Bespoke-Stratos-32B on its 17K dataset required 27 hours.

In contrast, after using A*-Thought to compress the 1K-row dataset, reducing the average data length by 68.69%. We trained our model for 3 epochs in 2.91 hours. reducing the training time by 24.25%, demonstrating a significant decrease in computational cost.

For Question 1 / Weakness 2

Based on the supplementary experiment ($k_{\mathrm{min}}=15$) and the original experiment ($k_{\mathrm{min}}=5$), it can be concluded that: The trade-off is that a smaller $k_{\mathrm{min}}$ is more effective for low-budget reasoning, while a larger $k_{\mathrm{min}}$ is more effective for high-budget reasoning.

Due to the historical difficulties associated with achieving lossless compression at the text level, the trade-off between performance and efficiency is generally regarded as inevitable. The A*-Thought algorithm employs a minimum search depth,  $k_{\mathrm{min}}$ , to mitigate the negative semantic impact of overly short thought sequences. Verification of a thought path only occurs when its depth, $k$, meets the condition  $k \ge k_{\mathrm{min}}$.

However, using an excessively low $k_{\mathrm{min}}$ value will result in the overall length of CoT data being too short, leading to performance degradation in high-budget scenarios. To address this, we explored increasing the value of $k_{\mathrm{min}}$​. The experiment results are shown in the following table. Notably, with $k_{\mathrm{min}}=15$ in 4K budget, the A*-Thought model surpassed the performance of the strongest baseline, QwQ-32B fine-tuned with s1K-1.1, across all benchmarks. Furthermore, this best result was achieved with fewer inference tokens. We will update the final version of our paper with these findings.

For Question 2

For $\alpha$, which is used to balance between question and solution information within BIS, systematic hyperparameter tuning has been reported in Figure 9 of Appendix D, varying $\alpha$ across the discrete set of values [0, 0.25, 0.5, 0.75, 1]. Experiments show that the best model performance can be achieved when BIS effectively integrates problems and solutions.

For $\beta$, it is used to adjust the weight of the current cost function $g(\cdot)$ in the overall cost function $f(\cdot)$. In the following supplementary experiments, we discussed its discrete values in [0.1, 0.5, 0.9] on the AI2 Reasoning Challenge (ARC) and LiveCodeBench. We will add these experimental results to the final version of the paper.

For Question 3

We thank the reviewer for their valuable suggestion. To validate the generalization capabilities of the A*-Thought algorithm across diverse domains such as coding, history, computer science, and law, we conducted supplementary evaluations on the LiveCodeBench and MMLU benchmarks. It is important to note that our model was trained exclusively on mathematical tasks, making these benchmarks entirely out-domain.

The results demonstrate that the model successfully learned the A*-Thought pattern, achieving higher inference efficiency and performance on non-mathematical tasks. We will incorporate these findings into the final version of the paper.

For Weakness 1

We provide a deeper theoretical analysis of A*-Thought. The rationality of "BIS + A* Search" can be explained by using importance sampling. The theoretical explanation is as follows:

Given an LRM $\mathcal{M}$, it can generate an extended thinking trajectory comprising $N$ reasoning steps, denoted as $\mathbf{t} = { \mathbf{t}^{(1)}, \mathbf{t}^{(2)}, \dots, \mathbf{t}^{(N)}}$, and the corresponding solution $\mathbf{s}$ for a given question $\mathbf{q}$. This process can be represented as: $( \mathbf{t}, \mathbf{s} ) := \mathcal{M}( \mathbf{q} ).$ We denote $\mathbf{s}$ as expectation $\mathbb{E}$ of $\mathcal{M}$ about $\mathbf{q}$ over the distribution $\mathbf{t}$: $\mathbf{s} = \mathbb{E}_ {\mathbf{t}}^{\mathcal{M}}[\mathbf{q}] = \sum ( \mathbf{q} \mathbf{t} ).$ Standard LRM using uniform sampling of the thinking trajectories to approximate the expectation: $\mathbb{E}_ {\mathbf{t}}^{\mathcal{M}} [ \mathbf{q} ] \approx \frac{1}{N} \sum_{i=1}^{N} \mathbf{q} \mathbf{t}^{(i)},$ if the final solution $\mathbf{s}$ is correct, we can call it an unbiased estimate. When $N$ is large enough, the variance of $\mathbf{s}$ sampled on $\mathbf{t}$ can be scaled by a factor of $N$ by the variance of $\mathbf{q}$ sampled uniformly on $\mathbf{t}$: $\mathbb{V}_ {\mathbf{t}} [ \mathbf{s} ] = \frac{1}{N} \mathbb{V}_ {\mathbf{t}} [ \mathbf{q} ].$ However, as the number of thought steps $N$ keeps increasing, the model will frequently switch thought modes, leading to an increase in the variance of the thought trajectory. If such thought trajectories are sampled, it tends to reduce the convergence speed of the solution estimation and increase the chance of biased estimation.

BIS + A* Search provides an approximate method for importance sampling, which will introduce a new distribution $\mathbf{t}^{\prime}$, the new expectation can be derived from $\mathbb{E}_ {\mathbf{t}}^{\mathcal{M}} [ \mathbf{q} ]$: $\mathbb{E}_ {\mathbf{t}}^{\mathcal{M}} [ \mathbf{q} ] = \sum ( \mathbf{t}^{\prime} \frac{\mathbf{t}}{\mathbf{t}^{\prime}} \mathbf{q} ) = \mathbb{E}_ {\mathbf{t}^{\prime}}^{\mathcal{M}} [ \frac{\mathbf{t}}{\mathbf{t}^{\prime}} \mathbf{q} ],$ the expectation of $\mathcal{M}$ about $\mathbf{q}$ over the distribution $\mathbf{t}^{\prime}$ can be further transformed as: $\mathbb{E}_ {\mathbf{t}^{\prime}}^{\mathcal{M}} [ \frac{\mathbf{t}}{\mathbf{t}^{\prime}} \mathbf{q} ] \approx \frac{1}{N} \sum_{i=1}^{N} \mathbf{q} \frac{\mathbf{t}^{(i)}}{\mathbf{t}^{\prime(i)}}.$ At this point an improvable variance about $\mathbf{s}$ is obtained: $\mathbb{V}_ {\mathbf{t}^{\prime}} [ \mathbf{s} ] = \frac{1}{N} \mathbb{V}_ {\mathbf{t}^{\prime}} [ \frac{\mathbf{t}}{\mathbf{t}^{\prime}} \mathbf{q} ],$ making $\mathbb{V}_ {\mathbf{t}^{\prime}} [ \mathbf{s} ] < \mathbb{V}_ {\mathbf{t}} [ \mathbf{s} ]$. Given that $\mathbf{s}$ is sampled on $\mathbf{t}^{\prime}$, thus it can be achieved by minimizing the variance of $\mathbf{t}^{\prime}$: $\mathbf{t}^{\prime} = \arg\min_{\mathbf{t}^{\prime}} \mathbb{V}_ {\mathbf{t}^{\prime}} [ \mathbf{s} ] = \arg\min_{\mathbf{t}^{\prime}} \frac{1}{N} \mathbb{V}_{\mathbf{t}^{\prime}} [ \frac{\mathbf{t}}{\mathbf{t}^{\prime}} \mathbf{q} ]$ Therefore, the ultimate goal is to find a proposal BIS distribution for the thought steps that minimizes this variance. By using the quality and information density of thought steps as heuristic information, the A* Search algorithm dynamically searches for the most important intermediate thought steps. This improves the quality of the final estimate while speeding up its convergence.