A*-Thought: Efficient Reasoning via Bidirectional Compression for Low-Resource Settings
Authors: Xiaoang Xu
Shuo Wang
Xu Han
Zhenghao Liu
Huijia Wu
Pei Pei Li
Zhiyuan Liu
Maosong Sun
Zhaofeng He
Venue: NeurIPS 2025 poster ()
Keywords: long-to-short
thought compression
reasoning
efficient CoT
Primary area: deep_learning

Abstract: Large Reasoning Models (LRMs) achieve superior performance by extending the thought length. However, a lengthy thinking trajectory leads to reduced efficiency. Most of the existing methods are stuck in the assumption of overthinking and attempt to reason efficiently by compressing the Chain-of-Thought, but this often leads to performance degradation. To address this problem, we introduce A*-Thought, an efficient tree search-based unified framework designed to identify and isolate the most essential thoughts from the extensive reasoning chains produced by these models. It formulates the reasoning process of LRMs as a search tree, where each node represents a reasoning span in the giant reasoning space. By combining the A* search algorithm with a cost function specific to the reasoning path, it can efficiently compress the chain of thought and determine a reasoning path with high information density and low cost. In addition, we also propose a bidirectional importance estimation mechanism, which further refines this search process and enhances its efficiency beyond uniform sampling. Extensive experiments on several advanced math tasks show that A*-Thought effectively balances performance and efficiency over a huge search space. Specifically, A*-Thought can improve the performance of QwQ-32B by 2.39$\times$ with low-budget and reduce the length of the output token by nearly 50\% with high-budget. The proposed method is also compatible with several other LRMs, demonstrating its generalization capability. The code can be accessed at: https://github.com/AI9Stars/AStar-Thought.

- -hTTought: Efficient Reasoning via Bidirectional Compression for Low-Resource Settings
Xiaoang Xu Shuo Wang2* Xu Han 2.4.5 Zhenghao Liu Huijia Wu Peipei Li Zhiyuan L Maosong Sun Zhaofeng He** Beijing University of Posts and Telecommunications Dept. of Comp. Sci. & Tech., Tsinghua University, Beijing, China Northeastern University *Institute for AI, Tsinghua University, Beijing, China Beijing National Research Center for Information Science and Technology
Abstract
Large Reasoning Models (LRMs) achieve superior performance by extending the thought length. However, lengthy thinking trajectory leads to reduced efficiency. Most of the existing methods are stuck in the assumption of overthinking and attempt to reason efficiently by compressing the Shain-of-TThouhh but this often leads to performance degradation. To address this problem, we introduce * Thought, an efficient tree search- based unified framework designed to identify and isolate the most essential thoughts from the extensive reasoning chains produced by these models. It formulates the reasoning process of LRMs search tree, where each node represents a reasoning span the giant reasoning space. By combining the A search algorithm with cost function specific to the reasoning path, it can efficiently compress the chain of thought and determine a reasoning path with high information density and low cost. In addition, we also propose bidirectional importance estimation mechanism, which further refines this search process and enhances its efficiency heyond uniform sampling. Extensive experiments several advanced math tasks show that A --TThough effectively balances performance and efficiency
huge search space. Specifically, A *-Thought performance of QwQ-32B by 2.39x with low-budget and reduce the length of the output token by nearly 50% with high-budget. The proposed method is also com- patible with several other LRMs, demonstrating its generalization capability. The code can be accessed at: https: //gith/ www/AI9Staaaaaee. AStar- AStar-Thouggt
improve the
Question
Question
Solution
Thought Steps
Thought Steps with BES (b) A-Thuuthh
(a) Chain-of- Though
Figure 1: Illustration of the comparison between the standard CoT and the proposed * --Thhuught. In A A-Thuugh,, each thinking step assigned bidirectional importance score (BIS), represented by varying color shades. Guided by the carefully-designed cost functions, A A*-Thought efficiently arrives at the solution using fewer steps, reducing the redundancy inherent in the original CoT.
Corresponding authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Introduction
Large Reasoning Models (LRMs), such ol (OpenAl 2024). RI DDeepSeek-A] 2025)
and QwQ (Qwen Team 2025). have demonstrated remarkable advancements in performance on variety complex tasks. These significant leaps are largely attributable to their capacity for sophisticated long-form reasoning, often operationalized through the generation of extended chain- of-thought (CoT) sequences. However, this enhanced reasoning capability introduces a substantial trade-off in terms of computational overhead during inference (Xia et al.) [025 Aggarwal & Welleck 2025). The generation and processing of these lengthy CoTs inherently demand greater storage and computational resources. Consequently, the escalating costs associated with these long CoTss pose a considerable barrier to the practical application and widespread adoption of LRMs, particularly in desource-constraince environments such as on-device or end-point deployments (Hu al. 2024 Allal et al., 2025) where computational budgets and memory footprints are strictly limited.
To address these efficiency concerns, a growing body of recent research has begun to investigate long-to-short methodologies. These approaches aim to significantly condense the reasoning processes
inherent in LRMs. thereby enhancing their inference efficiency (Lee et al. 20256 Han et al. 2025
Aytes et al. 2025 Xia al.] 2025] Qu et al., 2025 Hao al., 2024). For example, Chen al. (2025)
identify and conceptualize the overthinking phenomenon in LRMs, where models may engage in unnecessarily verbose or circuitous reasoning. They propose to mitigate this by specifically training the models to favor more concise responses. In complementary effort, Xiang et al. (2025) introduce a prompting strategy that guides LRMs to articulate their reasoning in shorter, more atomic steps, which cumulatively leads to a reduction in the total length of the generated thought process.
Rather than addressing a singular, narrowly defined issue within LRMs, this work introduces a unified framework designed to identify and isolate the most essential thoughts from the extensive reasoning chains produced by these models. An effective intermediate thinking step should ideally possess two core properties: (1) High-quality: The step's logical progression and substantive content must be accurate, sound, and directly relevant to the specific context and boundaries of the question. (2) Informativenes:: The step must make a demonstrable contribution towards the target solution by furnishing critical information. This characteristic holds even an intermediate conclusion, while perhaps imperfect or erroneous in isolation, ultimately facilitates the derivation of the correct final answer. The main challenges are two-fold:
1. How to identify high-quality and informative steps at the step-level
2. How to effectively assemble individual reasoning steps into concise and effective reasoning path at the path-level?
We propose A * A*-Thhught, a novel framework for automatically discovering compact and effective reasoning paths by leveraging signals at both step and path levels. At the step level, bidirectional importance estimation mechanism quantifies the significance of each thinking step based on its relevance both the question and the prospective solution. At the path level, A search is employed to efficiently navigate the exponential search space. This search utilizes cost functions that assess two key aspects: the quality of the current path and the conditional self-information of the solution given this path. These assessments collectively inform the estimated current and future cost to reach desirable final solution. Experimental results demonstrate that A * **Thhuthh successfully learns effective LRMs across diverse inference budgets, surpassing several representative baselines.
The primary contributions of this research are delineated follows:
We design a step-level bidirectional importance score (BIS) to evaluate the criticality of individual sentences. This scoring mechanism serves to significantly enhance effectiveness of the A search procedure compared to standard sampling techniques.
We introduce path-level A search algorithm tailored for compressing lengthy CoTs from LRMs. This algorithm strategically considers both current path quality and estimated future costs optimize LRM performance under stringent output length constraints.
The proposed algorithm demonstrates substantial empirical gains several representative baselines. For instance, for QwQ-32B in concise output scenarios, achieves a 3.53x improvement in accuracy.

---

Step Level
QuesTion
solution
Emprotence
Empretorce
Bidinectional Imprrttance Store (8I5)
Dequoue & Spon
Thought Step Queue Sorted By RTS
Iteration-1 Verification
Iteration-1 Exploration
Iteration-2 Venficatiion
Iteration-2
Exploration
question
question
Ourrent Patth
Dequeue Span
Current Path
Dequest
Cost Ceculation
output
f f 9
putput
Cust Colculetion
Path
X
= Current Path
f f=
Path Level
Figure 2: Illustration of A Thought, long- CoT compression method. A*-Thought leverages signals both the step and path levels. At the step-level, bidirectional importance score assesses relevance to both the question and the solution. At the path-level, an A search algorithm is employed, with cost functions designed to consider both current path quality and estimated future cost.
2 Problem Setup
Given an LRM M, can generate an extended thinking trajectory comprising reasoning steps, denoted (t(1), t(2), ...., t()), and the corresponding solution for a given question q. This process can be represented as:
(t, (q).
(1)
However, as the number of reasoning steps N increases, the model may frequently switch its thinking modes. Sampling complete thinking trajectory can hinder convergence of the solution estimation, thereby increasing the inference cost.
Our objective is to identify subset t' that preserves the LRM's reasoning performance to the greatest extent possible. A more compact thinking trajectory t' is expected to exhibit higher knowledge density across various computational budgets.
3
Method
In this section, we first introduce the bidirectional importance score each local thinking step, which employed in the subsequent A search process for thought compression.
3.1 Step-Level Bidirectional Importance Score
As mentioned Scction 2 it is prohibitively costly to explore all potential subsets of the long CoT. We therefore propose importance score to improve sampling efficiency for thought selection. A related approach is LongLL.Minngu (Jiang et al.) (024). which employs conditional probabilities to estimate the question-aware importance of each token in long document. In complex tasks that require long CoTs, the importance of an intermediate thought not only related to the question but also to the final solution. Relevance to the solution may provide important information for identifying useful thoughts. We therefore propose bidirectional importance score that considers both the question and the final solution when estimating the importance of each thinking step.

---

where a is a hyper-parameter to control the relative weighting of relevance to the question versus the solution. Figure presents the distribution of BIS for a sequence of thought steps, where the thought steps are divided by "An'n". The figure illustrates that not all steps hold high importance concerning both the question and the solution. Only limited subset offers significant contributions. Specifically, we assess importance at two levels, including the attention and model levels. At the attention level, we use attention weights to represent the importance of for y:
H y
ATTN(y|x)
ΣΣΣ an (gy, 24),
(2)
Hy h=1j=l==
where (U,, denotes the attention score of the query Yj to the key zt for the h-th head. H represents the number of heads. A higher importance score indicates more significant effect of x on y. At the model level, we use the negative log- oog-likelihood to assess the importance score of for y:
y
1 y
Ny
log (y)(x,yej).
To assess the contribution of each thinking step t(x) in the overall thought t, we analyze its influence on both the question q and the solution s. Each thought is concatenated with the question and the solution, forming the sequences (t(m), q) and (t(mm, s), respectively. Subsequently, we utilize compact language model, specificallyy GPT- to quantify attention scores and NLL values. The selection of a smaller model enhances the efficiency of this importance estimation procedure.
Specifically, the bidirectional importance score of ((()) is denoted as
(1 a) ATTN (qlt(") + QATTN (s)t(")) (1 - a NLL (q (*)) + aNLL (s)t(*))
BIS
(m)
Subsequently, these BIS values will be leveraged in conjunction with the A search algorithm to determine the pruned thought t'.
25
23
98
Thinking Steps
Figure 3: Distribution of BIS values for individual thinking steps in Long CoT.
3.2 Path-Level A Search
Our objective to extract an alternative thought trajectory t' from an original trajectory t. For trajectory t with N thinking steps, the 2 candidate trajectories render exhaustive exploration computationally intractable for extended We therefore employ the A search algorithm for efficient traversal of this space. Following an initialization phase, the algorithm iteratively conducts verification the k-th iteration, a verification model V ascertains if the current candidate path ti can lead to the correct solution. During exploration, each path t. is evaluated using cost functions. The algorithm detailed in the following subsections.
and exploration.
3.2.1 Overview
To enhance search efficiency, the thinking steps within the original long CoT t = (t(), (,),,..,, {())) are first sorted in descending order based on their BIS values, yielding

---

t Subsequently, the A search algorithm iteratively expands a search tree, denoted as T, according to defined cost functions. In this tree, each node corresponds to a span centered on a specific thinking step, encompassing its immediately preceding and succeeding steps. Formally, a node associated with the thinking step (()) is represented as r(()) = (t(x-1), t(m), ((=+1)). This approach aims mitigate the adverse effects of fragmented information that can arise from thought segmentation.
torrt {(t(m)), t(m=)).............).
Initialization By leveraging the bidirectional importance estimation mechanism detailed in Sec- tion 3.1] A*-Thought identifies a logical starting point within the potentially redundant thinking trajectory, thereby enhancing both efficiency and performance. Initially, thought queue, denoted as Q, is constructed using the sorted thought sequence tsort. Subsequently, the first thought is dequeued from 2 form the root node of the search tree T. This selection ensures the implementation of best-first sampling strategy throughout the subsequent search iterations.
Verification To assess the efficacy of the current thinking path, denoted t.g which encompasses the thinking spans from the root node to the current active leaf node within the search tree T, a validation model V is introduced. This model is employed determine whether the current path t/g successfully leads to the solution s:
Fs, s, expand T V Va
(5)
=ss,
return t'= t/2
It has been observed that verification tends to be ineffective for extremely short thought sequences, thereby offering limited guidance for the search process. Consequently, a lower boundary, denoted as kmin, is established for verification. Verification is performed exclusively when the depth of the search tree, k, satisfies the condition k 2 kmin-
Exploration If the current active leaf node does not pass verification, the first W thoughts are dequeued from Q to function next-level leaf nodes, denoted {r...... rw]: }. Each of these nodes is then appended to the current thinking path t/ to construct a set of candidate thinking paths, we assign a cost function f-) to each candidate thinking path, where
f (t/ + rw) = 9 (t/- + rw)) + (t/2 + r..)
(6)
The design our cost function, f(-), informed by the A* search algorithm. Specifically, g(.) denotes the cumulative cost incurred from the root node to the current node. Concurrently, h(()) functions as a heuristic, providing an estimate of the prospective cost from the current node to the target solution. We select the node that with the minimal cost the new active Icaf node:
Pw
argmin f (t/ + rw)-
wE(L,--.W)
The newly formed active thinking path, tz+1 = (t/., fw). subsequently proceeds to the next iteration of the process. Figure shows an example for the search process. To prevent an excessively deep search tree, an upper bound, kmaxx is imposed on its depth. The search process is terminated, and t is directly returned when the current depth, k reaches or exceeds this limit, i.e., k 2 kmax- The resulting compact responses can be leveraged to distill LRMs, fostering enhanced thinking efficiency.
3.2.2 Design of Cost Functions
To identify an effective and compact thought, denoted as t', the quality of each intermediate thought th is assessed from two perspectives: (1) the quality of the current intermediate thought, which is quantified by g()); and (2) the estimated future cost associated with extending the current intermediate thought t to the final thought sequence t'.
Current Cost Function The function g(-) measures the quality of the current intermediate thought t.. A verification model leveraging its reasoning capabilities is employed estimate this quality:
/
(t))
=
|t
log Py (t'.l)),
(8)
where 3 is the weight controlling the effect of the current cost.
5

---

The function h(n) estimates the cost from the current node to the goal, thereby influencing the efficiency of the search path. A higher estimated future cost suggests that more extensive sequence of future thoughts will be required to reach the final solution from the current state. To quantify this, we employ the conditional self-information of the correct solution s, given the current thought i/ and the input question q. Formally, it can be represented as:
Future Cost Function
h((()) (s|q, 11))
Larger values of the conditional self-information 2(-) indicate a lower likelihood of generating the solution We quantify Z(-) as follows:
I (s|q. t = log Pv (s)q.t%))
(10)
In particular, Ah-Tuughht enhances reasoning efficiency by compressing the thought trajectory. This is achieved through the systematic reduction of redundant steps, thereby streamlining the path from the initial query to the final solution. Such targeted compression significantly improves the performance of LRMs, enabling them deliver robust outcomes across diverse budgets.
4 Experiments
4.1 Setup
Backbones To evaluate the performance of A *--thought for compressing long CoT sequences for modern LRMs, we apply several compression methods to representative reasoning models, including QwQ-32B DeepSeek-R1-Distiee Swllll-weenn2220 and -1.1-32B
Training Data and Verification Model We utilize the long CoT data released by Muennighoff as the original CoT data and employ the corresponding distilled model, s1.1-32B, as the verification model, following the approach detailed in Section 3.2
et al. (2025 6
Benchmarks We employ the following mathematical reasoning tasks in our experiments, all of which demand complex reasoning capabilities from LRMs: MATH500 (Lightman et al.. (023).
AMC23 (AMC) OlympiadBench (He et al.) 2024). and GSM8K (Cobbe et al. (021). Model performance evaluated using the following metris::
Accuracy: The proportion of model outputs that match the ground-truth answers, measuring the model's correctness.
Length: The average length (i.e., number of tokens) of the model's response; longer responses typically incur higher inference costs.
Accuracy per Computation Unit (ACU) (Ma et al. between performance and efficiency, calculated as ACU AccuracyyTTaaa /Lenghh.
2025b : A metric assessing the trade-off
Baselines
We compare method against the following baselines:
Chain-of-Draft (CoD) (Xu et al. 2025 A prompt-hased method designed to guide LRMs in generating compact reasoning steps, each typically comprising fewer than five words.
Bheak-the- (BtC) (Ding et al. 2024): ; A prompt-based method employing specialized prompting strategies to encourage LRMs to utilize shortcuts, thereby enabling them to rapidly explore reasoning clues while bypassing detailed intermediate steps.
TokenSkip (Xia et al. 2025): A training-basee method that first employs prompt compres- sion (Jiang 2024) to shorten long CoT data, and then uses this compressed data to train an efficient reasoning model.
For comparison, we also report the performance of the QwQ-32B model directly fine-tuned on the s1K-1. 1. dataset.

---

Training Details We trained all models, including training-based baselines and our proposed method, for epochs with a peak learning rate of 10 and a warm-up ratio of 0.1. Training was conducted on 8 NVIDIA A100 80G GPUs, using a per-GPU batch size of and 8 gradient accumulation steps. For our proposed method, the default hyperparameters were set as a = 0.5 (Eq.E) 4 and 3 = 0.1 (Eq. [8. The lower bound for the verification depth, kmin= is set to 5, while the upper bound for the search tree depth, kmax. is set to 20, The exploration size W was set to 2.
Table I: Experimental results of different long-to-short methods across several benchmarks. The best
results shown in bold, and the second-best results are underlined.
Methods
MATH500
AMC23
OlympiudBench
GSM8K
Averuge
ACU
Acc.
Lon NE
Acc.
Lon.
Ace:
Len
Acc.
Len.
Acc.
Lon.
Budget: 512 Tokens
QwQ-328
10.8
512,00
512.00
3.3
512,00
27.6
511.97
11.1
511.99
2.16
QwQ-32B w/ s.K-
9.5
512,00
7.5
512.00
3.4
$12.00
28.8
512.00
12.3
$12.00
2.41
Col)
10.6
512.00
512.00
4.2
512.00
29.0
511.96
12.2
$11.99
2.38
B:C Effecciive Shortcut
10.2
512.00
12.5
512.00
4.2
$12.00
26.7
511.95
13.4
511.99
2.62
HrC. Skip Steps
9.6
512.00
5.0
$12.00
5.6
512.00
28.9
511.95
12.3
$11.99
2.40
ToocnSkip A Thought
10.8
511.05
3.9
512.00
508.1
33.2
491.92
15.0
508.60
12.0
509.74
57.4
451.76
29.4
490.51
5,99
Budget: 1024 Tokens
QwQ-32B
1024.00
951.96
1004.19
Q=QQ32H w/ sIK-1.1
24.8
1023.52
17.5
1024.00
8.9
1023.90 949
60.1
999.80
27.8
1017.85
2.73
CoD
24.8
1023.37
5.0
1024.00
7.3
1023.64
60.1
996.84
24.3
1016.96
2.39
BrC Effeetiive Shorteut
23.4
1022.00
1024.00
7.7
1023.92
61.3
1000.44
25.0
1017.81
2.45
BBC Skip Steps
23.4
1023.25
5.0
1024.00
7.6
1024.00
59.9
1000.93
24.0
1018.05
2.36
TokenSkip A Thoughhh
22.4
995.96
12.5
1024.00
6.4
1019.61
49.7
934.74
22.8
993.58
2.29
50.8
858.28
37.5
954.74
688.69
48.1
Budget: 2048 Tokens
QwQ332H
51.2
1844.96
25.0
1978
2021.995
80.4
1245.68
43.8
1772.880
2.47
QwQ-32B w/ s1K-1.1
60.0
1887.15
35.0
2000.95
23.3
2012.14
88.7
1474.00
51.8
1843.56
2.8L
CoD
60.2
1894.54
30.0
2012 35
25.5
2018.02
89.5
1490.23
51.3
1856.29
2.76
BcC Edfectivve Sbortcut
2004.65
89.8
52.3
75
BrC. Skip Steps
58.8
1884.96
35.0
2005.67 67
23.2
2013.00
89.2
1490.39
$1.6
1848. 52
2.79
TokenSkip Thoughh
53.6
1685.34
35.0
1923 25
19.7
1943.68
86.7
1272.03
48.8
1706.00 08
2.86
1540.30
1320.41
Budget: 4096 Tokens
QwQ:32B
75.4
2798.67
55.0
3456.05
36.5
3645.22
85.8
1348.24
63.2
2812.05
2.25
QwQ-32R w/
79.6
65.9
3485.95
95.2
1624.11
2836.00
CoD
80.2
2719.00
60.0
3354.28
42.0
3488.67
95.0
1655 80
69.3
2804.44
2.47
B&C Effective Shortcut
79.6
2696.72
57.5
3355.43
42.4
3493.28
94.3
1636.45
68.6
2795.47
2.45
BiC Skip Stops
80.2
2710.83
57.5
3399.93
41.8
3494,41
94.9
1651.37
68.6
2814.14
2.44
TokenSkip
74.4
2336.20 29
52.5
3156.68
37.8
3289 44
94.8
1412.87
64.9
2548. 82
2.55
-hoogghh
78.8
1699.78
65.0
2385.85
2546.45
874.34
69.3
1876.66
3.69
4.2 Main Results
The detailed experimental results, presented in Table T yield the following key insights:
Up to 2.39x accuracy and 2.49 ACU improvements in low-budget scenarios. Specifically, across all examined benchmarks, A Ah-Tuought improve the average accuracy of QwQ-32B from 12.3 to 29.4 when the inference budget is constrained 512 tokens. Concurrently, the ACU score improves from 2.41 to 5.99. Furthermore, in experiments with inference budgets of 1024 and 2048 tokens, Thougtt consistently attained superior accuracy and the shortest response lengths.
Up to 33.59% length reduction without substantial accuracy drop in the 4096-token setting. For instance, for the QwQ-32B model, A+-Thought decreased the average response length from 2826.00 to 1876.66 tokens. This significant length reduction resulted in only a slight decrease in average accuracy (from 70.6% 69.3%). Importantly, A *-Thutthh also attained the highest ACU score in this setting, outperforming both the prompt-based and the training based baselines.
Compatible with several models, A * demonstrates generalizability. Figure and Figure display the ACU and performance curves on three distinct backbone models: QwQ R1 R1-Distill-32B, and sl. 1-33B The results demonstrate A *-Thhughhts effectiveness across these LRMs, where it achieves the highest efficiency and accuracy under various budget conditions.
Detailed results provided in Appendix D
7

---

130 6320
4-
On Shonce
2
4096
2048
1024
512
4096
2048
1024
512
4096
2048
1024
Tokens
(a) QwQ-32B
(b) RI-Distill-32B
(c) s1.1-32B
Figure 4: ACU on different methods, which reflects performance-o--effccinee ratio of LRMs.
70
70-
60
60-
Accurscy 05
50
30
20
60-
20
30-
20-
512
1024
20488
4096
512
1024
2048
4096
512
1024
2048
4096
Tokens
Tokons
Tokers
(a) AMC23
(b) Olympiadbench
(c) Average
Figure 5: Performance of RI-Distill-32B augmented using TokenSkip and A Thought.. "Average" denotes the average accuracy of the model in MATH500, AMC23, OlympiadBench, and GSM8K.
5 Analysis
5.1
Performance on More Benchmarks
To verify the generalization capabilities A-TTuuggh, we conducted supplementary evaluations on the out-of-domain benchmarks LiveCodeBench and MMLU, as shown in Table 2 Although our model was trained exclusively on mathematical tasks, the results demonstrate that it effectively learned the A A*TThough reasoning pattern. This led to improved performance and higher inference efficiency, even on these non-mathematical tasks.
Table 2: Results of A A*TThought on out-of-domain benchmarks.
LiveCodeBench
MMLU
Average
Methods
ACU
Acc. (t)
Len. (4)
Acc,
Len (L)
Acc.(t) (t)
Len
Budget: 512 Tokens
QwQ-32B A A--Thought
0.0
512.00
37.6
511.94
18.8
511.97
3.67
4.5
509.53
56.7
398.57
30.6
454.05
6.74
Budget: 1024 Tokens
QwQ-32B
0.0
1021.94
57.4
956.90
28.7
989.42
2.90
+ A A>*TThought
11.8
986.02
71.9
573.30
41.9
779.66
5.37
Budget: 2048 Tokens
QwQ-32B
3.5
1977.58
75.2
1323.26
39.4
1650.42
2.38
+ +A* A--Thhught
24.5
1734.28
79.0
671.41
51.8
1202.85
4.30
Budget: 4096 Tokens
QwQ-32B + A--Thought
12.0
3586.93
79.5
1584.05
45.8
2585.49
1.77
39.0
3044.51
80.3
733.90
59.7
1889.21
3.16

---

5.2 Analysis on the Effect of A Search
Table 3 presents an ablation study on the value kmin in the A A*-search process. The results show that with Kmin = 15 and 4K-token budget, the A A model consistently outperformed the strongest baseline across all benchmarks. Importantly, this performance was also achieved with higher token efficiency during inference.
Table 3: Effect of the exploration step limit Kmin model performance.
Methods
MATH500
AMC23
OlympiaiBench
GSMSK
Average
Acc. (7)
Loa.
Acc.
Lea.
Aoc.
Lon. (3)
Acc.
Len.
Ace:
Len.
Budget: 409 Tokens
QwQ-328
73.4
2798.67
$5.0
3456.05
36.5
3645.22
85.8
1348.24
63.2
2812.00
2.25
QwQ:32B w/ s1K-1.1
79.6
2693.27
65.0
3485
42.4
3500.66
95.2
1624.11
70.6
2826.00
2.50
A*"TThoght Rain
A Thoughhh Kain 15
80.8
2184.34
67.5
2891.68
44.2
3063.96
95.5
1229.40
72.0
2342.85
3.07
5.3 Training Loss and Training Time
Figure 6 illustrates the training loss for various training-based methods, demonstrating that A Thought achieves the lowest loss. This potential advantage may be attributed A A+-Thought' utilization of the span around individual thoughts, thereby reducing the negative impact of interrupting the complete thinking process. Furthermore, by considering the quality of the intermediate path during the A search process, we ensure the learnability of the compressed data.
0.90
0.85
0.85
1.0
0.75
0.80
0.70
0.9
0.75
0.8
0.80
10
20
40
10
20
40
10
20
40
Stop
Stop
Stop
(a) Fine-TTune Tuning
(b) TokenSkip
(c) A A--Thought
Figure 6: Training loss of the training-bast based methods discussed, using the QwQ-32B backbone.
Table 4 presents a comparison compressed data sizes and their corresponding training times. No- tably, A A+-Thought exhibits significantly higher compression ratio than TokenSkip. while achieving a lower training loss. These results further corroborate the efficacy of the proposed A *-Thouuht method. A more detailed ablation study on the components of A A*TThought, along with analysis of the effect of hyperparameters, is presented in the Appendix.
Table 4: Amount of the training data and the corresponding time. denotes the compression rate.
Training Time (s)
Training Set
QwQ-32B
R1-Distill-32B
s1.1-32B
s1K-1.1
100.00% 85.41% (114.59%)
13819.60
13784.32
13638.07
TokenSkip
12846.1 14 (17.04%)
12700.96 (17.86%)
12679.52 (47.03%)
+ AhoTTht
31.31% (J68.691))
10468.20 (124.25%)
10809.50 (121.58%)
10550.03 ((22.645)
5.4
Case Study
Figure 7 showcases representative example of outputs from models trained with and without A * Thought, given an identical question. While both models arrive at the correct solution, A*-Thought fosters more streamlined and focused thinking path. Appendix C provides further comprehensive examples. These examples demonstrate that A **-Thought can train models to adopt more concise thinking process. We believe this approach, with additional effort and integration with advanced training techniques, holds the potential to break through the current bottlenecks in LRMs.

---

Mikka wants to order pizza with two toppings. He has & different toppings to choose from. How many different pizzas could he order?
teni ii onder thee taik
hupping
hopp
Mikka wamts order pizza with two differens toppings from available toppungs, is:
cboal aalee of Cillinal contkarien parvill Skoee the ondic of the happlags place daise cockiim Rus, plica will puppora cal wad- pres
problem, the
cambina-
the vole, yae surien
C(n, A)
R- (m kyl
C15%
where 8 (the lotal number of toppingo) and (the number toppings choose). Plugging values, get
Wat
cocpua in lo 26, 2 ia driccl by diteeer comti onn romet the post dos hes loom ITE
whetee
A oa tiikk If Mikk dteaiieg Bed and then hepping the tins de scow crpping
they wolld
coenct
siroe
pooken
rndo ton't speictty way
centes thn Thus, the number of different pizzas Mikka could ooder is 28
confesaives
C18, 3)
21-61
2x
7 28
chelcy So, lew
ho the oach par teke beqeur dheetigg vagiing and heo cpppin de Soy
Wes, just is feoneegh lats mesilry moceple with frece hepplags happone fire sew only Kipppigs & wid Wive mwny cidleee rou loppl prose wodl natort Feel theer AK aC) That's deowiiing
S. Owoedt Ao
warts if etcit te oiter nichet. Als pertos So the hemals wats het.
septiop
24Alk vanta to bi patts DMiig the ond Sconda
C(
28 (8 23}
xx1
(10.2)
Therefore, Mikka can order diffcrent pizzas.
Final Answer The number of different pizzas Mikia could order
28
place
Figure 7: Responses generated by QwQ-32B models trained with and without A Thought, Red box represents the question, purple box represents the thinking process, blue box represents the solution.
Related Works
Recent LRMs achieve complex reasoning capabilities, often described as "deep thinking", through significant computational effort during inference, a process sometimes referred to test-time scaling. However, studies indicate that models utilizing long CoT processes can be susceptible to excessive computation, leading to inefficiencies often termed "overthinking". Consequently, considerable research has aimed to improve reasoning efficiency. Primary strategies include the development of
refined prompting techniques (Renze & Guven 2024 [Ding et al.) 2024 [an et al. 2025 Lee et al.
2025a
Aytes et al. 2025; Xu et al. 2025| et al. 2025a) and methods for CoT compression (Hao
al.
2024
Cheng & Durme 2024 Shen et al. 2025 ZZhng et al. 2025 Su al. 2025).
Specific approaches have targeted token-level or path-level optimizations. For example, Token-
Skip (Xia et al. (025) attempts to focus computation by selectively processing tokens deemed most relevant to the input query while omitting less pertinent ones. Another method, Retro-Search (Lu et al. 2025), inspired by Monte Carlo Tree Search, explores numerous potential reasoning paths within long CoT structures. Its goal is to mitigate redundancy across multiple paths (overthinking) while ensuring adequate exploration within individual paths (avoiding underthinking), issues potentially exacerbated by frequent shifts in reasoning strategy.
In contrast to methods focusing on specific causes of redundancy within long COT, this paper proposes a heuristic approach. We employ a bidirectional importance score to guide the A search algorithm. The objective is to identify computationally efficient yet effective reasoning pathway, thereby contributing to the development of more resource-efficient LRMs.
7 Conclusion
We introduce A A*-Thought, an innovative CoT compression algorithm designed to enhance the reasoning efficiency of contemporary LRMs. Our approach meticulously crafts concise reasoning pathways. This is achieved by first evaluating the necessity of individual reasoning steps using a novel bidirectional importance score. Subsequently, the thinking steps are assembled into a compact and coherent reasoning chain by employing a path-level A search algorithm. A key aspect of our A+ search process is the design of specialized cost functions. These functions assess not only the quality of the current partial reasoning path but also estimate the potential cost to complete the thought process, thereby providing helpful guidance for selecting the most promising reasoning trajectories. Experimental results demonstrate that * *TThought can outperform several representative baselines.
10

---

Acknowledgments and Disclosure of Funding
This study is sponsored by CAAI-Lenovo Blue Sky Research Fund. This work is also supported by the AI9Stars community.
References
Aggarwal, and Welleck, S. Ll: Controlling how long reasoning model thinks with reinforcement learning, March 2025.
Allal, L. B., Lozhkov, A., Bakouch, E., Blázquez, G. M., Penedo, G., Tunstall, L., Marafioti, A., Kydlfček, H., Lajarín, A. P., Srivastav, V., Lochner, J., Fahlgren, C., Nguyen, X.-S., Fourrier, C., Burtenshaw. B., Larcher, H., Zhao, H., Zakka, C., Morlon, M., Raffel, C., von Werra. L., and Wolf, T. Smollm2: When smol goes big data-centric training of a small language model, 2025. URL https://arxia: org abs//bb2. 02737
AMC. American mathematics competitions (amc), 2025.
URL https://man org/
student-proye patpsttt-porggaamaaaaaaa
Aytes, S. A., Baek, J., and Hwang, S. J. Sketch-of-thought: Efficient Ilm reasoning with adaptive cognitive-inspired sketching, March 2025.
Chen, X., Xu, J., Liang, T., He, Z., Pang, J., Yu, D., Song, L., Liu, Q. Zhou, M., Zhang, Z., Wang, R., Tu, Z., Mi, H., and Yu, Do not think that much for 2+3=? on the overthinking of ol-like lims, 2025. URL
/ aaxii org/ h/////////// abs//412.... 21187
Cheng, J. and Durme, B. V. Compressed chain of thought: Efficient reasoning through dense representations, December 2024.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C.. and Schulman, J. Training verifiers to solve math word problems, 2021. URL httph::///// h arwiv..iivvv///.v org/ www./////////e.eeooooo/eee// abs//110....................../b 11166
DeepSeck-AL. Deepseek-rl: Incentivizing reasoning capability in ilms via reinforcement lcarning, January 2025.
Ding, M., Liu, H., Fu, Z., Song, J., Xie, W., and Zhang, Y. Break the chain: Large language models can be shorteut reasoners, June 2024.
Han, T., Wang, Z.,, Fang, C., Zhao, S., Ma, S., and Chen, Z. Token-budget-aware Ilm reasoning, February 2025.
Hao, S., Sukhbaatar, S., Su, D., Li, X., Hu, Z., Weston, J., and Tian, Y. Training large language models to reason a continuous latent space, December 2024.
He, C., Luo, R., Bai, Y., Hu, S., Thai, Z., Shen, J., Hu, J., Han, X., Huang, Y., Zhang, Y., Liu, J., Qi, L.,, Liu, Z., and Sun, M. Olympiadbench: A challenging benchmark for promoting agi with olympiad- level bilingual multimodal scientific problems. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 3828-3850, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 00.118653/v1/ 1/200///1///22aalllllooo 1211.211.
Hu, S., Tu, Y., Han, X., He, C., Cui, G., Long, X., Zheng, Z., Fang, Y., Huang, Y., Zhao, W., et al. Minicpm: Unveiling the potential of small language models with scalable training strategies. arXiv preprint arXiv:2404.0 240.:2444450 2024.
Jang, H., Wu. Q., Luo, X., Li, D., Lin, C.-Y,, Yang, Y., and Qiu, L. Longllmlingua: Accelerating and enhancing 1lms in long context scenarios via prompt compression. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1658-1677, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 18.18653/v 1/2024.ac1-long..11
11

---

Lee, A., Che, E., and Peng, T. How well do Ilms compress their own chain-of- thought? token complexity approach, March 2025a.
Lee, A., Che, E., and Peng, T. How well do Ilms compress their own chain-of tf-thughhht token complexity approach, 2025b. https://aaaax wttp:/orrgaaaaaaaaae 01141
Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let's verify step by step, 2023. URL /tatpps//arxiv, org/ abs/
Lu, X., Han, S., Acuna, D., Kim, H., Jung, J., Prabhumoye, S., Muennighoff, N., Patwary, M., Shoeybi, M., Catanzaro, B., and Choi, Y. Retro-search: Exploring untaken paths for deeper and efficient reasoning, April 2025.
Ma, W., He, J., Snell, C., Griggs, T., Min, S., and Zaharia, M. Reasoning models can be effective without thinking. https//aaxivvrrraa22554...8888
April 2025a.
Ma, X., Wan, G., Yu, R., Fang, G., and Wang, X. Cot-valve: compth--ompressiblle chain-of saain-of-in tin--fff-thoe thought tuning, February 2025b.
Muennighoff, N., Yang. Z., Shi, W., Li, L., Fei-Fei, L.., Hajishirzi, H., Zettlemoyer, L.., Liang, P., Candès, E., and Hashimoto, T. S1: Simple test-time scaling, February 2025.
OpenAL, i, Jaech, A., Kalai, A., Lerer, A., Richardson, A., El-Kishky, A., Low, A., Helyar, A., Madry, A., Beutel, A., Carney, A., Iftimie, A., Karpenko, A., Passos, A. T., Neitz, A., Prokofiev, A., Wei, A., Tam, A., Bennett, A., Kumar, A., Saraiva, A., Vallone, A., Duberstein, A., Kondrich, A., Mishchenko, A., Applebaum, A., Jiang, A., Nair, A., Zoph, B., Ghorbani, B., Rossen, B., Sokolowsky, B., Barak, B., McGGrew B., Minaiev, B., Hao, B., Baker, B., Houghton, B., McKinzie, B., Eastman, B., Lugaresi, C., Bassin, C., Hudson, C., Li, C. M., de Bourcy, C., Voss, C., Shen, C., Zhang. C., Koch, C., Orsinger, C., Hesse, C., Fischer, C., Chan, C., Roberts, D., Kappler, D., Levy, D., Selsam, D., Dohan, D., Farhi, D., Mely. D., Robinson, D., Tsipras, D., Li, D., Oprica, D., Freeman, F.,, Zhang, F., Wong, F.,, Proehl, F., Cheung, E., Mitchell, E.,, Wallace, E., Ritter, E., Mays. E., Wang, F., Such, F. P.. Raso, F., Lconi, F., Tsimpourlas, F., Song. F., von Lohmann, F., Sulit, F. Salmon, G., Parascandolo. G., Chabot, G., Zhao, G., Brockman, G., Leclere, G., Salman, H. Bao, H., Sheng, H., Andrin, H., Bagherinezhad, H., Ren, H., Lightman, H., Chung, H. W., Kivlichan, O' Connel,, I., Osband, I., Gilaberte, C., Akkaya, I., Kostrikov, I., Sutskever, I., Kofman, I., Pachocki, J., Lennon, J., Wei, J., Harb, J., Twore, J., Feng, J., Yu, J., Weng. J., Tang, J.. Yu, J., Candela, J. Q. Palermo, J., Parish, J., Heidecke, J., Hallman, J., Rizzo, J., Gordon. J., Uesato, J., Ward, J.. Huizinga. J., Wang, J., Chen, K., Xiao, K., Singhal, K., Nguyen, K., Cobbe, Shi, K., Wood, K., Rimbach, K., Gu-Lemberg, K., Liu, K., Lu, K., Stone, K., Yu, K., Ahmad, L., Yang, I.., Liu, I.., Maksin, I.., Ho, I.,, Fedus, I.., Weng, L.., Li, I.., McCallum, I.., Held, I.., Kuhn, I.,, Kondraciuk, I.., Kaiser, I.., Metz, I.., Boyd, M., Trebacz, M., Joglekar, M., Chen, M., Tintor, M., Meyer, M., Jones, M. Kaufer, M., Schwarzer, M., Shah, M.. Yatbzz M., Guan, M. Y., Xu, M., Yan, M., Glaese, M., Chen, M., Lampe, M., Malek, M., Wang. M., Fradin, M., McClay, M., Pavlov, M., Wang, M., Wang, M., Murati, M., Bavarian, M., Rohaninejad, M., McAleese, N., Chowdhury, N., Chowdhury, N., Ryder, N., Tezak, N., Brown, N., Nachum, O., Boiko, O., Murk, O., Watkins, O., Chao, P., Ashbourne, P., Izmailov, P., Zhokhov, P., Dias, R., Arora. R., Lin, R., Lopes, R. G., Gaon, R. Miyara, R., Leike, R., Hwang, R.. Garg, R., Brown, R., James, R., Shu, R., Cheu, R., Greene, R., Jain, S., Altman, S., Toizer, S.. Toyer, S., Miserendino, S., Agarwal, S., Hernande7, S., Baker, S., McKinney, S., Yan, S., Zhao, S., Hu, S., Santurkar, S., Chaudhuri, S. R., Zhang, S., Fu, S., Papay, S., Lin, S., Balaji, S., Sanjeev, S., Sidor, S., Broda, T., Clark, A., Wang, T., Gordon, T., Sanders, T., Patwardhan, T., Sottiaux, T., Degry. T., Dimson, T., Zheng, T., Garipov, T., Stasi, T., Bansal, T., Creech, T., Peterson, T., Eloundou, T., Qi, V., Kosaraju, V., Monaco, V., Pong, V., Fomenko, V., Zheng, W., Zhou, W., McCabe, W., Zaremba, W., Dubois, Y., Lu, Y., Chen, Y., Cha, Y., Bai, Y., He, Y., Zhang, Y. Wang, Y., Shao, Z., and Li, Z. Openai ol system card, 2024. URL https: http///xxvvvv. www.riii.....oo....oo 2412. 16720
Qu, Y., Yang, M. Y. R., Setlur, A., Tunstall, L.., Beeching, E. E., Salakhutdinov, R., and Kumar, A. Optimizing test-time compute via meta reinforcement fine-tuning, March 2025.
Qwen Team. Qwq-32b: Embracing the power of reinforcement learning, March 2025. URL https: h//ppnll///ennmmm.mm github..tt io blog///g 32b/
12

---

Renze, M. and Guven, E. The benefits of a concise chain of thought on problem-solvine in large language models. In 2024 2nd International Conference on Foundation and Large Language Models (FILM), pp. 476 483, November 2024, doi: 10.1 1099HLLLN631122.22211022222
Shen, Z., Yan, H., Zhang, L., Hu, Z., Du, Y., and He. Y. Codi: Compressing chain-of-thought into continuous space via ooff-distillation, February 2025.
Su. D., Zhu, H., Xu, Y., Jiao, J., Tian, Y., and Zheng. Q. Token assorted: Mixing latent and text tokens for improved language model reasoning. February 2025.
Xia, H., Li. Y.. Leong, C. I., Wang, W., and Li, W. Tokenskip: Controllable chain-of-thought compression in 1lms, February 2025.
Xiang, K., Liu, Z., Jiang, Z., Nie, Y., Cai, K., Yin, Y., Huang, R., Fan, H., Li, H., Huang, W., Zeng, Y., Yuan, Y.J.,, Han, J., Hong, I.., Xu, H., and Liang, X. Can atomic step decomposition enhance the self-structured reasoning of multimodal large models?, March 2025.
Xu, S., Xie, W., Zhao, L., and He, P. Chain of draft: Thinking faster by writing less, March 2025.
Zhang. J., Zhu, Y., Sun, M., Luo, Y., Qiao, S., Du, L., Zheng, D., Chen, H.,, and Zhang, N. Lightthinker: Thinking step-by-stey compression, February 2025.
13

---

A A*-Thought Algorithm Detail
Algorithm
D shows the details of the A search algorithm to compress lengthy CoTs.
Algorithm Thooughh algorithm for compressing lengthy CoTs
Input:
2:
question; t: original CoT; tsort: thought list sorted by BIS; S. solution; V: verification
model; Amin: min verification depth; mmax: max search depth; W: number of observable nodes
3: Output:
4: t' t'C t: compressed thought path
5: procedure * SEARCH
(1) Initialization
6:
Q taort
7:
to Q.pop()
8:
==1
9:
while Q not empty do if le 2 kmax then return t' end if
10:
11:
b (2) Verification
13:
if k 2 kiiin and V2q t()) = then return t'' = t/
14:
end
D (3) Exploration
[r rI....., Tw] +- first W elements in Q for Tw in (TI..... rw } do
17:
(tz, + +w)) = 9 (t/ rw) (t/ + rw)
19:
end for Fw argmin (1,- W) (t/ + rw.)
21:
t = (w)
Q.pop(fw)) k= k++
23:
end while
25:
return ti
26:
end procedure
14

---

B Test- Dest-Time-Scaling Strategies
We the A A+-Thought evaluation on MATH500 and LiveCodeBench, this time using best-of-N strategy (with N=8) to calculate pass@k. k. The findings indicate that A -hoouhtt and test-time test-time-scaue sast--ii--clling strategies can be used combination, the experiment results are shown Table 5
Table 5: Experimental results A A AhTuhhttt with test-time-schi scaling strategies.
MATH500
LiveCodeBench
Methods
pass @
pass @
pass
pass@8
pass@1
pass
pass@4
pass
Budget:
512 Tokens
QwQ-32B
10.8
17.2
25.9
34.4
0.0
0.0
0.0
0.0
A ThTThhhhh
33.2
47.4
60.7
70.2
4.5
7.0
12.5
20.8
Budget: 1024 Tokens
QwQ-32B 16.6
29.6
42.1
53.2
0.1
0.1
0.3
+ A A-TThutthh
50.8
65.4
75.8
81.8
11.8
20.4
31.9
44.8
Budget: 2048 Tokens
QwQQ32B
51.2
59.8
67.8 8
74.8
2.1
3.4
5.1
7.0
+ Thought
69.2
79.2
85.4
89.0
24.5
34.0
45.2
56.5
Budget: 4096 Tokens
QwQ-32B
75.4
80.2
84.0
86.8
12.4
17.7
23.0
28.0
A Thougttt
78.8
86.8
91.1
93.2
39.0
50.9
60.9
68.8
C Performance of Models of Varying Sizes
This section reports experiments Qwen2.5-7B-Instreee and Bwen2.5-14B-Insttuue in Table
Table 6: Experimental results on models of varying sizes.
Methods
MATH500
AMC23
OlympiadBench
GSMBK
Average
ACU
ftc. (t)
Len.
Acc. (t)
Len.
Acc. (f)
Len.
Acc. (t)
Len.
Acc. (
Len.
Budget: Tokens
TokenSkip-7B
9.4
511.41
2.5
512.00
4.0
512.00
25.5
508.40
10.4
511.0
2.03
Ar-Though--BB
30.8
499.12
5.0
508.70
6.7
509.36
59.2
447.22
25.4
491.10
5.18
TokenSkip-11e 14B
9.2
$10.89
29.0
511.52
A= Thought 14B
30.4
497.54
10.0
512.00
10.4
508.77
50.9
475.30
25.4
498.40
5.10
Budget: 1024 Tokens
IokenSkip-7B
24.8
986.62
1021.33
1019.11
907.40 047.40
983 62
A= Thoughht 7B
48.2
866.93
25.0
991.42
19.3
961.42
74.3
661.99
41.7
870.44
4.79
TokenSkip- 14B
1020.22
960.13
T--Thought-1ee 14B
49.2
873.53
22.5
997.33
18.8
966.55
78.3
738.61
42.2
894.01
4.72
Budget: 2048 Tokens
TokenSkip-7B
35.4
1776.50
20.0
1968.47
14.7
1959.13
55.6
1534.37
31.4
1809.62
1.74
A Ah-Thrugh-7B
59.2
1352.54
30.0
1715.22
25.4
1677_38
77.6
874.11
48.1
1404.81
3.42
TokenSkip-Iee 14B
55.8
1678.03
20.0
1934.05
20.8
1940.58
73.8
1453.71
42.6
1751.59
2.43
Ar-Thought-14B
64.2
1308.18
1650.40
28.3
1610.04
86.1
930.89
54.7
1374.88
3.97
Budget: 4096 Tokens
TokenSkip- 7B
39.8
3201 90
27.5
3593.93
20.9
3566.00
63.4
2651.40
37.9
3253.31
1.16
1999_10
2840.70
34448.73
1271.18
2289.93
TokenSkip 14B
68.4
2406. 16
40.0
3338.80
32.5
3334.73
81.2
2054.78
55.5
2783.62
1.99
Thonhghht-
1677.00
2350.32
2494.24
1100.52
1905.52
15

---

D Detailed Results of R1-Distill-32B and s1.1-32B
This section reports experiments on RI-Distill-32B and s1.1-32B in Table and Table respectively. reports
Table 7: Experimental results DeepSeek-RI-De -i-isssi-----sssi-----ee
Methods
MAT
AMC23
OlympiadBench
GSM8K
Average
ACU
Acc.
Len
Acc.
Len.
Acc.
Len.
Acc.ft:
Lea.tt
Acc.!!1
Len
Budget: 512 Tokens
RI-Disrill-228 CoD
512.00
12.1
2.36
10.0
512,00
7.5
512.00
4,0
512.00
35.0
512.00
14.1
512.00
2.76
BrC Effective Shortcut
9.6
512,00
3.0
512.00
4.0
$12.00
30.3
512.00
12.2
512.00
2.39
Skip Steps
13.1
+ TokcnSkip
12.2
$12,00
2.5
$12.00
4.5
512.00
28.4
512.00
11.9
512.00
2.32
Thooghh
24.0
512.00
10.0
7.0
512.00
$12.00
23.0
$12.00
4.49
Budget: 1024 Tokenss
R1 RI-Disrill-228 32B w'stk-L11
24.2
1024.00)
17.5
1024.00
7.0
1024.00
60.5
1024.00
27.3
1034.00
2.67
1024.00
1024.00
+ BBC Elfective Shortcut
24.4
1024.00
10.9
1024.00
8.8
1024.00
63.5
1024.00
26.7
1024.00
2.60
BIC Skip Steps TToeeSkiip
19.4
1024.00
7.5
1024,00
7.3
1024.00
60.2
1024.00
23.6
1024,00
2.30
Thoaghe
39.6
1024.00
20.0
1024.00
16.0
1024.00
69.8
1024.00
36.4
1024.00
3.55
Budget: 2048 Tokens
Distill-3BB w/s w.s1K-1.1
54.2
2048.00
35.0
2048.
19.9
2048.00
85.8
2048. 00
48.7
2048.00
2.38
Coll
57.8
2048.000
35.0
20488.00 00
22.4
2048.00
88.4
2048.00
50.9
2048.00 00
2.49
BIC Effective Shorieut
37.5
2048.00
+ BIC Skip Steps Tokennkiip
56.2
2048.00
37.5
2048.00
21.4
2048.00
87.9
2048.00 00
50.8
2048.00
2.48
40.8
2048.00
37.5
2048.00
19.7
2048.00
59.1
2048.00
39.3
2048.00
1.92
Thoogl
45.0
2048.00
2048.00
89.4
55.7
2048.00
Budget: 4096 Tokens
R1-Distill-32D 3B w/l1-1111
77.4
4096.00
52.5
4096.00
37.8
4095.00
90.9
4096.00
64.7
4096.00
1.58
75.4
60.0
4096.00
4096.00
67.0
4096.00
1.64
+ BIC Effective Shortcut
75.8
#096.00
$5.0
4096.00
39.8
4096.00
91.7
4096.00
63.6
4096.00
1.60
DiC Skip Steps
73.2
4096.00
52.5
4096.00
38.6
3099.00
92.1
4096.00
64,1
4096.00
1,56
TokenSkipp
4096.00
57.8
A.A.Ti Thought
75.4
4096.00
70.0
4096.00
40.9
4096.00
91.7
4096.00
69.5
4096.00
1.70
Table 8: Experimental results on s1.1-32B.
Methods
MATH500
AMC23
OlympiadBench
GSM8K
Acc.
Len.
Acc.
Len
Acc. (1)
Len.
Acc. IT)
Lea.
Acc
Len.
Budget: 512 Tokens
s1.1-328
9.8
512.001
5.0
512.00
5.5
512.00
28.3
511.85
12.2
$11.96
2.37
CoD
12.6
511.86
7.5
512.00
5.3
512.00
32.8
511.21
14.6
511.77
2.84
BrC
RiC Skip Steps
12.2
512.00
2.5
512.00
4.5
512.00
31.2
511.95
12.6
$11.99
2.45
TokenSkip
14.0
511.25
7.5
512.00
3.9
512.00
29.4
509.62
13.7
511.21
2.68
Thought
Budget: 1024 Tokens
s1.1-328
25.6
1014,866
10.0
1024.00
8.8
1023.93
47.5
997.19
23.0
1015.00
2.26
CoD
37.8
1006.51
20.0
1019:02
1021.62
58.7
957.21
32.0
1001
3.20
BiC Effecttive Shortcut
42.8
1001.81
25.0
1024.00
13.8
1020 92
61.3
950.63
35.7
999.34
3.57
RiC Skip Steps
32.8
1011.61
15.0
1022
13.4
1022.07
58.5
975.83
29.9
1008.04 04
2.97
TokcnSkip
28.4
983.36
15.0
1020.08
9.8
1019.31
45.4
955.1
24.7
994
2.48
A Thought
55.4
862.14
32.5
969.05
22.3
960.90
80.9
738.52
47.8
882.65
5.41
Budget:
s1.1-328
63.2
1765.50
35.0
1986.60 60
26.6
1978.44
80.9
1518. 36
51.4
1812.23
2.84
CoD
69.6
1661.55
10.0
1906 22
31.9
1933.45
84.9
1339.1
56.6
1710.08
3.31
BOC Effective Shoreeu
70.2
1634.15
42.5
1926.
34.4
1928.26
85.0
1313.87
58.0
1700.60
3.41
BiC Skip Steps
67.4
1699.65
40.0
1929. 10
32.5
1954.23
84.5
1383.99
56.1
1741.74
3.22
TokenSkip
59.2
1636.53
37.5
1903.90
27.3
1916.75
70.1
1586.98
48.5
1761.
2.76
1229.54
37.5
1676.65
913.33
58.7
1363369
Budget: 4096 Tukens
x1.1.320
Coll
74.4
2701.37
55.0
3041 .45
47.9
3228.24
90.8
1.582.5 40
67.0
2638,
2.54
BtC Elfective Shortcut
80.0
2209.99
60.0
3132.45
49.3
3161..9
88.8
1609.22
69.5
2528. 24
2.75
DrC Skip Steps
3169.82
3222.67
TTkenSkkp
69.2
2404..5
37.5
3057.28
41.5
3230.59
77.7
2:755. 19
61.5
2766 91
2.22
Thougi
77.8
1629.87
52.5
2744.00
42.4
2611.72
91.9
1055.83
66.2
2010.36
3.29
16

---

E
Additional Ablation Analysis
By default, we report the average accuracy using QwQ-32B over all the examined benchmarks.
E.1
Analysis on BIS
The design of BIS significantly influences the quality of assessing the importance of individual thought steps. ATTN (attention level importance) and NLL (model level importance) represent distinct measures of reasoning step significance. As demonstrated in Figure 8 manipulating their individual and combined effects on BIS reveals that their joint application is superior for improving the model performance across various budgets.
20
Accuracy (%)
15
5
Random
NLL
Attn NLLGAttn
Figure 8: Effect of ATTN and NLL on BIS under the 512-token budget.
The parameter a modulates the balance between question and solution information within BIS. We conducted an ablation analysis, varying across the discrete set of values [0, 0.25, 0.5, 0.75, 11, to determine its effect on reasoning data quality and, consequently, model performance. Specifically, with a = 0, the score is determined only by the information related to the question. In contrast, setting a 1 results in score based entirely on information pertaining the solution. As Figure illustrates, optimal model performance is achieved when the BIS effectively integrates both question and solution perspectives, guided by an appropriate setting of a that ensures judicious allocation of their respective contributions.
23
22
Accuracy
21
35
34
0.25
0.5
0.75
1.0
0.25
0.5
0.75
1.0
(a) 512 Takens
1024 Tokens
61
51
5.9
Acturary
49
AccurO
56
47
54--
53.
0.25
0.5
0.75
1.0
0.25
0.5
0.75
1.0
(c) 2048 Tokens
(d) 4096 Tokens
Figure 9; Effect of the hyperparameter a on model performance.
17

---

E.2
Analysis on A Search
Appropriately setting the maximum exploration steps kmax are keys to optimizing the trade-off between performance and efficiency.
effective for low-budge scenarios (51 (512-2048 tokens). In contrast, for a 4096-token budget, performance benefits from greater number of exploration steps. This is likely because extensive exploration (i.e., deep search) can lead to more concise overall reasoning paths or solutions. Based on these observations,
Figure I0 highlights distinct trends: moderate exploration steps
kmax 20 our main experiments by default.
60
15
50
Kraa 20
Accuracy (%)
40
30
10
0
512
1024
2048
4096
Tokens
Figure 10: Relationship between the exploration step limit kmax and model performance.
The parameter is used to adjust the weight of the current cost function g(-) in the overall cost function f(.). In the following supplementary experiments, discussed its discrete values in [0.1, 0.5, 0.9] on the ARC and LiveCodeBench, the experiment results are shown in Table 9
Table Effect of the hyperparameter on model performance.
ARC
LiveCodeBench
Average
Methods
ACU
Acc. (1)
Len. (4)
Acc.() (t)
Len. (4)
Acc. (1)
Len. (4)
Budget: 512 Tokens
8 0.1
63.5
381.02
4.5
509.53
34.00
445.28
7.64
3 0.5
52.5
438.03
4.0
510.73
28.25
474.38
5.96
0.9
48.2
469.22
5.8
506.15
27.00
487.69
5.54
18

---

The Prompt used in this Work
This section details the prompts utilized in this work, including the system prompts presented in Table and the specific CoD (Chain-of-Draft) prompts along with two variants of BtC (Break-the- Chain) baseline prompts, which are shown in Table I1
Table 10: System prompt
System Prompt
Your role as an assistant involves thoroughly exploring questions through systematic long thinking process before providing the final precise and accurate solutions. This requires engaging a comprehensive cycle of analysis, summarizing, exploration, reassessment, reflection,
backtracing, and iteration to develop well-considered thinking process.
Please structure your response into two main sections: Thought and Solution. In the Thought section, detail your reasoning process using the specified format:
< <lbegin_of of _fttofft_thhhhttt >>
[thought with steps separated with "Inln') <I elndd_ of_ughghtt >
Each step should include detailed considerations such as analisying questions, summarizing relevant findings, brainstorming new ideas, verifying the accuracy of the current steps, refining any errors, and revisiting previous steps.
In the Solution section, based various attempts, explorations, and reflections from the Thought section, systematically present the final solution that you deem correct. The solution should remain a logical, accurate, concise expression style and detail necessary step needed reach the conclusion, formatted as follows:
<
(final formatted, precise, and clear solution)
< <|end_of solution|>>
Now, try to solve the following question through the above guidelines:
Table 11: Specific prompt for CoD and two variants of BtC
Methods
Prompt
CoD
Think step by step, but only keep minimum draft for each thinking step, with words at most.
BtC Effective
Rapidly evaluate and use the most effective reasoning shortcut to answer the question.
Shortcut
BtC Skip Steps
Let's 's skip as much as possible.
G Example of the A A*.Thought Trajectories
This section provides two comparative examples that illustrate the CoT produced by A Thouuhthh versus the original CoT QwQ-32B and 11.1-32B. Figures and demonstrate that A *TTTuughh successfully reduces redundant thought trajectories while preserving reasoning ability.
19

---

Convert the point (0,3) 3) in rectangular coordinates to polar coerdinates. Enter your answer in the form (r. where r > 0nd 0 s < 2tt.
QwQ-32B
A A--Thought-QwQ--222
Okay, sa need to convert the rectangular coordinates (0. 3; to polar coordinates. Hmm, let me remember how to do this. coordinates are given (r,0), from the origin to the point, and is the angle made with the positive r-axis.
So, in this case, is 3. Then / is the angle made with the positive 2-axis, The point (0.3), which the positive y-axis. So, the angle 9 here radians, becmuse that's 90 degrees, pointing straight along the y-axis.
distance
let verify. The formulas converting from rectan- gular to polar coordinates are var 5² which gives vO' + 3 v9 3. Then 0 is uretan (2). But wait, here. So, arctan (2) would he arctan (g). However, division zeto undelined, but in the context of polar coor- dinates, when 0, either 5
First, to find r. the formula is v + ya. In this case. is O and 3. Plugging those the formula, get vIP 4:33 = V0+F9 = vBI 3. Okay, so r is 3. That seems straightorward. Now, for the angle 0. The formulu for is usuilly
-.. depending sign of Since positive (3), 8 is 5. So, that checks out. But let make
arttan (e). Rut wait, here a is O. That would make the de- nominator zero, which would
tangent undetined. arctan (E) would he arctan (H), which is undefined. But arctangent of infinity 2. right? Because as approaches from positive side, approaches positive infinity, so arctan approaches 5- But since is esactly 0, we have to consider the direction. If a and y is positive, the point is on the positive graxis, which is 8 f. If a is o and is 2. this case, y is 3, which posätive, so should be 5.
there isn't another angle that could represent the same point. For crample, sometimes adding 27 to il gives the same direction, but since the problem re- quires to be between and 2n, $ already within that range. So, the unswer should be (3. 2)-
Final Answer: The polar coordinates are
(3. 2
negutive,
But let me double-check. Sometimes when converting ordinates, especially when
angle can be tricky. Let me visualize the point (). In roctangular coordinates, that's units up allong the y-axis. So imugine the polur coordinatic system, the angle 6 is measured from the posi- tive a-axis. If I rotate radians (which is 90 degrees) from positive a-axis, end pointing straight up along positive y-axis. That's exactly where the point (0. 3) is. So
To convert the point (0,3) from rectongular coordinates to polar coordinates, we use the formulas v1² + 8 and arctan (2).
Calculate r:
F= V 100+3
d = f makes sense here. Therefore, combining
Determine 9:
polar coordinates should be (3, G). But lot me make sure there's 's not another way to represent this. Since polar coordinates
Since x O and 3, the point lies on the positive y-uxis.
have negative values and ungles adjusted by n. but the problem specifies that r and (1 s g < 2rr. So we need positive and i within that interval. Since is already 7. which between o and 2a, and r is 3, which is positive, this should be the correct answer.
The angle for the positive graxis 2-
Thus, the polar conrdinates
to confirm, what tried angle? For example, could d be ig But up equivalent to when you subtract 2n. so it's the same direction, But since d is roquized to be less than 2x. 30 is out of range. So 5 the correct angle here. Also, if tried
Walt,
another
negative y, like e - -3, then 0 would be 4 x 4F. But must be greater than 0, so that's not allowed. Therefore, (3, 5) is the only valid polar coordinate representation for the point (0,3) under the given constraints.
think that's all. Let recap: the point angle is Yep, that seems right. can't think of any mistakes here. The formulas for and both lend to these values, and considering the position the final answer should be (3, } Final Answer: The polar coordinates of the point (0.3)
the positive
y-axis, so the
3,
the point confirms
(3. x
To convert the rectangular coordinates (0,3) to polar coordi- nates, start by calculating the radius using the foruula /=r + y² Here, x 0 and
r= 1 vē=3
Next, we determine the angle 6. Since = O and 3 is positive, the point lies the positive graxis. The angle d for a point on the positive g-axis f.
We verify that @ = is within the required interval 0 5 0 2n and that
positive. Thus, the polar coordinates
Figure 11: A specific example comparing QwQ-32B and A Th-Thugght-QWQ-B (Ours). which red box represents the question, purple box represents the thought path, blue box represents the solution.
20

---

What the value of a such that logg (logy(2r 23) 2?
s1.1-32B
A Thw.hghhhsss11131
Okay, so I need to find the value of that sutisfies the equa- tion log, (log,(2r 2)) 2. Hmm, nested logurithms, that could hit tricky. Let
Sot
logy(2s: 2)
take step by step.
Thercfore: 2x 2 16
First, let me socall that I have log,,log,. (ww.lll.ppssssioooo..oooo (cxpression) es then I need to solve the inner logarithm first. But maybe can work from the outside in. Since the
Solving for x:
logarithm
2x 16 + 2 18
means the argument outer log must be 2P, Because loga(as) 2 implies y
base and equals
== 18/22 m 9
4. So, the inner logarillun must equal 4, Wait, let confirm that something must
But let's check
satistlis the original equation.
(smmeiiii))
Original equation:
which is 4. So, the equation simpliifee to logg (2z 2) 4. Then, solving for the imner logarithmm, logg (2r 2) 4 implies
(ogg(log,(2r
Plug in a 9:
that 2r 2
25, which is 16, Therefore, 2r = 16.
log, (log, (2 9 2) (ogg(1
2]) - logg((ogg (16).
Solving x, add
sides: 2 18, then divide by 2:
(16) bocause 2 =
= 9. So, x = U.
So:
But wait. need to check if this value of actually satis- the original equation. Let's plug original equation and see.
(4g;(4) which correct.
back into
Therefore, x = is the correct solution.
*"Final Answer*
Original equarion: (oga/logaa(2r 21] 2 2
First, compute the inner expression:
18 -2
because 16. Then. (1g,(4) = 2. since 2 = 4. Therefore, the original equation becomes logy(4) 2. which is correct. So, wait, should
Then (16)
works. check there any domain restrictions. The argument of the inner logarithm, 2r 2. must be positive bocause you can't take the loganithm of net- positive number. So, 2 2- Solving for so i 1. Since a argument of the outer logarithm is logy (2r 2). which most he positive because the logurithm only defined for positive numbers. Wait, the equation log, (2r 2)1
To salve the equation log, (2gga 22) 2. we start by isolating the
loganthm. know then y = 22 1. Therefore. we can rewrite the equation as: log, (2n -2) 2) = 4. Next, we salve for 2r 2 by converting the exponemial form. Since long(2r Solving a, we
logg(s) 2.
> greater than I, it's valid. Also, the
lnganitmiic ergarion
4, follows
2
add 2 to both sidks: 2r- = 18. Then, divide by 2: 9, To verify, we substitute
9 back the original equation:
For (ngyloo, 2) to he defined, (2r 2) must be positive. Because the logarithm function only defined for positive arguments. So, 12g
log, (ogg(log((: (2-9-- - 2)) logg (166) = luga (1)
The solution satisfies the original equation, confirming that the value of is [s
Since (o)
when v > I. this implics that 2 2 1. So, 2x > 3. hence 3/2, So, the domain than 3/2, it's valid.
3/2. Since a 9 is greater
Therefore, the solution is = B. But let's verify once again. Let's computc the inner expression: 21- -2 2 = 2 x 2 = 16, Then, (10) Then, (og.(4)
which matches the
original eguation.
it's correct. Wait, just to make sure, let me check if there's 's any other possible solution. The equation log, (log,(2 (2r 2) 2. Let think. The fonction logg strictly increasing function. so the equation loga(s)
has only one solution i 4. Then, the equation log, (2r - 2) 4 has only one solution 2r 16, leading check
B. So, there's only solution. any extrancous solutions. When solving equations with logaritims, sometimes you get extrancous solutions if you squared both sides someihing. But in case, we just used definition of logarithms and solved linear equations. So, 9 is the only solution and it satisfies the domain restrictions. Therefore, the answer
Walt, but
*xFinal Answar
To solve the equation log, (logg(2r 2)) 2, we start by recognizing that the plies the argument the outer logarithi must he
logarithm must equal 2, which im-
4.
Thcrefore, we set up the aguation: log, (2x 2) = 4 Nest, we solve for the inner logaritlin. The equation logg(2r (2r- - 2) Solving for 2
implies that 2
16 - 2r 18 _ x =- 9 We verify the solution by sub- stittiig
back into the original equation: Compute the inner expression:
logarithm: The is indeed the solution. Additionally we check the domain restrictions to ensure the arguments The inner argument 27 2 must he positive, which requires 1. and the argument of the outer logarithu, log, (2r- 2), must be positive, requiring both conditions. it is valid. Thus, the value of is
2- 16, compute the
(1g]]66) = 1. compute the outer logarithm: logg (4) original equation is sutisfied, confirming that
logurithms positive.
g. Since satisties
A specific example comparing 31.1-32B and A* (Ours), which red box represents the question, purple box represents the thought path, blue box represents the solution.
Figure 12:
21

---

H Limitation and Future Works
At present, the application of A-TThought is confined to supervised fine-tuning (SFT). However, in light of recent studies showcasing the efficacy of reinforcement learning (RL) in advancing the reasoning capacities of LRMs, intend to investigate the extension of our methodology to an RL-based approach.
I Impact Statement
The profound thinking abilities of LRMs allow them to master complex scenarios, but at the cost of significant computing resource consumption. Our work focuses developing more efficient and green AI, which promises to decrease the energy footprint of LRM deployment and, crucially, enable their application in more resource-scarce environments like endpoint devices.
22

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
The abstract and introduction clearly provide the main contribution and key
results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
23

---

Justification:
Limitations are discussed in Appendix G.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [NA]
Justification:
This work does not contain theoretical assumptions and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Experimental details can be found in Section 4 and Appendices C, D. and
Guidelines:
The answer NA means that the paper does not include experiments.

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Links to the involved resources (e.g., data and model) are listed in Section and 4.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips.cc/publcc/eee.c wttpg//ddd//ooeeutiiieeeeeeeeeee ssi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
25

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The related experimental settings are detailed in Section 4 and Appendices D and E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: In light of the proposed method's substantial improvement and the high computational cost, we did not undertake repeated experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computation devices and training time are explained in Section 4 and 5.
Guidelines:
The answer NA means that the paper does not include experiments.
26

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: This paper conform the mentioned Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please refer to Appendix H for broader impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks.
27

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Citations for all related original papers are provided, and adherence their respective licenses has been ensured.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pww.::s...aaseiiiia...... thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not create new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
28

---

Answer:
[NA]
Justification:
This paper does not involve such efforts.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [Yes]
Justification: Section 2, 3, and detail the usage of LLM in the study.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non ntn-standard components.
Please refer to LLM policy for what should or should not be described.
cc. http::/pss..eeooeeeeeenn///////s
29


Reviews:
[{"review_id": "Jjes20pmyf", "reviewer": "Reviewer_j7zW", "summary": "This paper introduces A-Thought*, a framework that compresses lengthy Chain-of-Thought (CoT) outputs from large reasoning models using an A* search guided by a bidirectional importance score (BIS). The method addresses the efficiency challenges posed by verbose CoT reasoning, aiming to retain performance while significantly reducing token output.", "questions": "1. Can you explain why A*-Thought underperforms in high-budget scenarios? Is there an inherent trade-off in the compression strategy that degrades solution completeness?\n\n2. How sensitive is the method to the selection of $\\alpha$ (in BIS) and $\\beta$ (in the cost function)? Have you performed any systematic hyperparameter tuning?\n\n3. Have you tested A*-Thought on non-mathematical reasoning tasks (e.g., commonsense QA, multi-hop QA)? If not, what are the anticipated limitations?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. **Clear Motivation and Relevance**: The problem of excessive reasoning length in LRMs is well-known, and addressing it aligns with growing interest in cost-efficient inference.\n\n2. **Methodological Innovation**: The integration of a bidirectional importance score with A* search to identify high-value reasoning steps is novel.\n\n3. **Empirical Performance**: Substantial gains are reported in accuracy and accuracy per computation unit (ACU), especially under constrained budgets (e.g., 2.39× improvement for QwQ-32B).\n\n## Weaknesses\n\n1. **Lack of Theoretical Analysis**: There is no rigorous theoretical justification for why BIS + A* would yield better CoT compression than alternatives.\n\n2. **Limited Performance Gains in High-Budget Scenarios**: While A*-Thought shows impressive improvements under strict token constraints, its advantages diminish—and even reverse—when larger token budgets are available. In high-budget settings (e.g., 4096 tokens), A*-Thought underperforms compared to several baselines in terms of raw accuracy. This suggests that the proposed method may overly prioritize brevity at the cost of completeness.", "was_revised": true, "final_justification": "Thanks for the authors' detailed response. I appreciate the results from the response and believe that it would make the paper more solid if the final version could include these results. However, I believe that my initial evaluation is accurate, as this paper is upper the borderline, therefore I decided to keep my original score.", "rebuttal": "# For Question 1 / Weakness 2\n\nBased 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.**\n\nDue 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}}$.\n\nHowever, 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.\n\n|              Methods               | MATH500  |             |   AMC23  |             | OlympiadBench |             |   GSM8K  |            |  Average |             |    ACU   |\n| :--------------------------------: | :------: | :---------: | :------: | :---------: | :-----------: | :---------: | :------: | :--------: | :------: | :---------: | :------: |\n|           **Budget: 4K**           |   Acc.   |     Len.    |   Acc.   |     Len.    |      Acc.     |     Len.    |   Acc.   |    Len.    |   Acc.   |     Len.    |          |\n|              QwQ-32B               |   75.4   |     2798.67 |     55.0 |     3456.05 |          36.5 |     3645.22 |     85.8 |    1348.24 |     63.2 |     2812.05 |     2.25 |\n|         QwQ-32B w/ s1K-1.1         |   79.6   |     2693.27 |     65.0 |     3485.95 |          42.4 |     3500.66 |     95.2 |    1624.11 |     70.6 |     2826.00 |     2.50 |\n| + A*-Thought $k_{\\mathrm{min}}=5$  |   78.8   | **1699.78** |     65.0 | **2385.85** |          40.1 | **2546.45** |     93.1 | **874.54** |     69.3 | **1876.66** | **3.69** |\n| + A*-Thought $k_{\\mathrm{min}}=15$ | **80.8** |     2184.34 | **67.5** |     2893.68 |      **44.2** |     3063.96 | **95.5** |    1229.40 | **72.0** |     2342.85 |     3.07 |\n\n# For Question 2\n\nFor $\\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.\n\nFor $\\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.\n\n|   Methods   | ARC  |        | LiveCodeBench |        | Average |        | ACU  |\n| :---------: | :--: | :----: | :-----------: | :----: | :-----: | :----: | :--: |\n|             | Acc. |  Len.  |     Acc.      |  Len.  |  Acc.   |  Len.  |      |\n| $\\beta=0.1$ | 63.5 | 381.02 |      4.5      | 509.53 |  34.00  | 445.28 | 7.64 |\n| $\\beta=0.5$ | 52.5 | 438.03 |      4.0      | 510.73 |  28.25  | 474.38 | 5.96 |\n| $\\beta=0.9$ | 48.2 | 469.22 |      5.8      | 506.15 |  27.00  | 487.69 | 5.54 |\n\n# For Question 3\n\nWe 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.\n\nThe 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.\n\n|   Methods    |   MMLU   |            |  LiveCodeBench  |             | Average  |             |   ACU    |\n| :----------: | :------: | :--------: | :-------------: | :---------: | :------: | :---------: | :------: |\n|              |   Acc.   |    Len.    |      Acc.       |    Len.     |   Acc.   |    Len.     |          |\n|              |          |            | **Budget: 512** |             |          |             |          |\n|   QwQ-32B    |   37.6   |   511.94   |       0.0       |   512.00    |   18.8   |   511.97    |   3.67   |\n| + A*-Thought | **56.7** | **398.57** |     **4.5**     | **509.53**  | **30.6** | **454.05**  | **6.74** |\n|              |          |            | **Budget: 1K**  |             |          |             |          |\n|   QwQ-32B    |   57.4   |   956.90   |       0.0       |   1021.94   |   28.7   |   989.42    |   2.90   |\n| + A*-Thought | **71.9** | **573.30** |    **11.8**     | **986.02**  | **41.9** | **779.66**  | **5.37** |\n|              |          |            | **Budget: 2K**  |             |          |             |          |\n|   QwQ-32B    |   75.2   |  1323.26   |       3.5       |   1977.58   |   39.4   |   1650.42   |   2.38   |\n| + A*-Thought | **79.0** | **671.41** |    **24.5**     | **1734.28** | **51.8** | **1202.85** | **4.30** |\n|              |          |            | **Budget: 4K**  |             |          |             |          |\n|   QwQ-32B    |   79.5   |  1584.05   |      12.0       |   3586.93   |   45.8   |   2585.49   |   1.77   |\n| + A*-Thought |   **80.3**   |   **733.90**   |      **39.0**       |   **3044.51**   |   **59.7**   |   **1889.21**   |   **3.16**   |\n\n# For Weakness 1\n\nWe 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:\n\nGiven 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:\n$$( \\mathbf{t}, \\mathbf{s} ) := \\mathcal{M}( \\mathbf{q} ).$$\nWe denote $\\mathbf{s}$ as expectation $\\mathbb{E}$ of $\\mathcal{M}$ about $\\mathbf{q}$ over the distribution $\\mathbf{t}$:\n$$\\mathbf{s} = \\mathbb{E}_ {\\mathbf{t}}^{\\mathcal{M}}[\\mathbf{q}] = \\sum ( \\mathbf{q} \\mathbf{t} ).$$\n**Standard LRM using uniform sampling** of the thinking trajectories to approximate the expectation:\n$$\\mathbb{E}_ {\\mathbf{t}}^{\\mathcal{M}} [ \\mathbf{q} ] \\approx \\frac{1}{N} \\sum_{i=1}^{N} \\mathbf{q} \\mathbf{t}^{(i)},$$\nif 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}$:\n$$\\mathbb{V}_ {\\mathbf{t}} [ \\mathbf{s} ] = \\frac{1}{N} \\mathbb{V}_ {\\mathbf{t}} [ \\mathbf{q} ].$$\nHowever, 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.\n\n**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} ]$:\n$$\\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} ],$$\nthe expectation of $\\mathcal{M}$ about $\\mathbf{q}$ over the distribution $\\mathbf{t}^{\\prime}$ can be further transformed as:\n$$\\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)}}.$$\nAt this point an improvable variance about $\\mathbf{s}$ is obtained:\n$$\\mathbb{V}_ {\\mathbf{t}^{\\prime}} [ \\mathbf{s} ] = \\frac{1}{N} \\mathbb{V}_ {\\mathbf{t}^{\\prime}} [ \\frac{\\mathbf{t}}{\\mathbf{t}^{\\prime}} \\mathbf{q} ],$$\nmaking $\\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}$:\n$$\\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} ]$$\nTherefore, 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."}, {"review_id": "KJ7Nrujs3Z", "reviewer": "Reviewer_hAiS", "summary": "The paper proposes A*-Thought, an inference-time framework that prunes large language models’ long chain-of-thought (CoT) traces. Each step receives a bidirectional importance score (BIS) derived from attention statistics and token-level NLL with respect to both the question and the predicted answer. An A* search then selects a compact subset of spans that minimises a cost combining current-path verification loss and a heuristic future cost. Experiments on four math-reasoning benchmarks with three 32 B models show accuracy gains (up to +18 pp) and shorter outputs (≈50 % fewer tokens) under fixed token budgets compared with prompt- and training-based baselines.", "questions": "Q1: Have you tried GSM-like natural-language tasks, code reasoning, or commonsense QA to demonstrate domain robustness?\n\nQ2: The verifier V is distilled from the same dataset used for pruning; could this inflate acceptance probability? \n\nWhile the idea is interesting and results promising, the narrow evaluation scope, missing robustness analyses, and incomplete limitation discussion prevent a confident acceptance at this stage.", "limitations": "They do not discuss: (a) sensitivity to α, β, k_max across tasks; (b) potential semantic drift when critical but low-BIS steps are pruned; (c) ethical risks of deploying compressed reasoning that may omit safety checks. Hence the limitations section is insufficient.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n- Potential to lower inference cost of LRMs, an important problem.\n\n- Empirical improvements on math tasks under tight budgets (Table 1). \n\nWeaknesses\n\n- Evaluation limited to synthetic math datasets; no evidence on open-domain, multimodal or non-numeric reasoning.\n\n- Variance/error bars omitted despite stochastic search; single-run results may be fragile. \n\n- Conceptually close to Retro-Search and TokenSkip; contribution may be incremental (reuse of A* and attention/NLL saliency).\n\n- Gains are shown only for already-compressed 32 B distillations; unclear impact on frontier ( >70 B) models or real latency on hardware.\n\n- Training still demands multi-epoch passes over the entire CoT corpus (8 × A100 80 G, 3 epochs) — energy savings may be overstated.", "was_revised": true, "final_justification": "A*-Thought presents an interesting approach. The paper is well-written, demonstrating promising performance across datasets in different domains and achieving SOTA results.", "rebuttal": "# For Question 1 / Weakness 1\n\nWe 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.**\n\nThe 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.\n\n|   Methods    |   MMLU   |            |  LiveCodeBench  |             | Average  |             |   ACU    |\n| :----------: | :------: | :--------: | :-------------: | :---------: | :------: | :---------: | :------: |\n|              |   Acc.   |    Len.    |      Acc.       |    Len.     |   Acc.   |    Len.     |          |\n|              |          |            | **Budget: 512** |             |          |             |          |\n|   QwQ-32B    |   37.6   |   511.94   |       0.0       |   512.00    |   18.8   |   511.97    |   3.67   |\n| + A*-Thought | **56.7** | **398.57** |     **4.5**     | **509.53**  | **30.6** | **454.05**  | **6.74** |\n|              |          |            | **Budget: 1K**  |             |          |             |          |\n|   QwQ-32B    |   57.4   |   956.90   |       0.0       |   1021.94   |   28.7   |   989.42    |   2.90   |\n| + A*-Thought | **71.9** | **573.30** |    **11.8**     | **986.02**  | **41.9** | **779.66**  | **5.37** |\n|              |          |            | **Budget: 2K**  |             |          |             |          |\n|   QwQ-32B    |   75.2   |  1323.26   |       3.5       |   1977.58   |   39.4   |   1650.42   |   2.38   |\n| + A*-Thought | **79.0** | **671.41** |    **24.5**     | **1734.28** | **51.8** | **1202.85** | **4.30** |\n|              |          |            | **Budget: 4K**  |             |          |             |          |\n|   QwQ-32B    |   79.5   |  1584.05   |      12.0       |   3586.93   |   45.8   |   2585.49   |   1.77   |\n| + A*-Thought |   **80.3**   |   **733.90**   |      **39.0**       |   **3044.51**   |   **59.7**   |   **1889.21**   |   **3.16**   |\n\n# For Question 2\n\nVerification 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`**.\n\n# For Limitation (a)\n\nWe 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.\n\n|        Methods        | ARC  |        | LiveCodeBench |        | Average |        | ACU  |\n| :-------------------: | :--: | :----: | :-----------: | :----: | :-----: | :----: | :--: |\n|                       | Acc. |  Len.  |     Acc.      |  Len.  |  Acc.   |  Len.  |      |\n|     $\\alpha=0.0$      | 65.9 | 405.31 |      5.5      | 509.31 |  35.70  | 457.31 | 7.81 |\n|     $\\alpha=0.5$      | 63.5 | 381.02 |      4.5      | 509.53 |  34.00  | 445.28 | 7.64 |\n|     $\\alpha=1.0$      | 65.0 | 393.20 |      8.5      | 505.59 |  36.75  | 449.40 | 8.18 |\n|      $\\beta=0.1$      | 63.5 | 381.02 |      4.5      | 509.53 |  34.00  | 445.28 | 7.64 |\n|      $\\beta=0.5$      | 52.5 | 438.03 |      4.0      | 510.73 |  28.25  | 474.38 | 5.96 |\n|      $\\beta=0.9$      | 48.2 | 469.22 |      5.8      | 506.15 |  27.00  | 487.69 | 5.54 |\n| $k_{\\mathrm{max}}=10$ | 35.3 | 476.90 |      2.2      | 506.68 |  18.75  | 491.79 | 3.81 |\n| $k_{\\mathrm{max}}=15$ | 54.2 | 436.41 |      3.8      | 510.25 |  29.00  | 473.33 | 6.13 |\n| $k_{\\mathrm{max}}=20$ | 63.5 | 381.02 |      4.5      | 509.53 |  34.00  | 445.28 | 7.64 |\n\n# For Limitation (b)\n\nTheoretically, 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.\n\nTo 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:\n$$\\mathbf{r}^{(n)}=\\langle \\mathbf{t}^{(n-1)}, \\mathbf{t}^{(n)}, \\mathbf{t}^{(n+1)}\\rangle,$$\nwhere $\\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**.\n\n# For Limitation (c)\n\nSince 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.\n\n# For Weakness 2\n\nWe 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.**\n\n|   Methods    |   MATH500    |                  |    AMC23     |                  |  OlympiadBench  |                  |    GSM8K     |                 |   Average    |                  |     ACU      |\n| :----------: | :----------: | :--------------: | :----------: | :--------------: | :-------------: | :--------------: | :----------: | :-------------: | :----------: | :--------------: | :----------: |\n|              |     Acc.     |       Len.       |     Acc.     |       Len.       |      Acc.       |       Len.       |     Acc.     |      Len.       |     Acc.     |       Len.       |              |\n|              |              |                  |              |                  | **Budget: 512** |                  |              |                 |              |                  |              |\n|   QwQ-32B    | $10.8\\pm0.7$ |  $512.00\\pm0.0$  | $2.5\\pm0.0$  |  $512.00\\pm0.0$  |   $3.8\\pm0.3$   |  $512.00\\pm0.0$  | $28.7\\pm1.4$ | $511.90\\pm0.1$  | $11.5\\pm0.5$ |  $511.98\\pm0.0$  | $2.24\\pm0.1$ |\n| + A*-Thought | $33.5\\pm0.9$ |  $492.46\\pm1.0$  | $18.5\\pm2.0$ |  $509.00\\pm2.9$  |  $11.4\\pm0.6$   |  $509.00\\pm0.7$  | $58.3\\pm0.7$ | $453.84\\pm2.0$  | $30.4\\pm0.7$ |  $491.08\\pm0.5$  | $6.19\\pm0.1$ |\n|              |              |                  |              |                  | **Budget: 1K**  |                  |              |                 |              |                  |              |\n|   QwQ-32B    | $17.0\\pm0.9$ | $1018.39\\pm1.1$  | $11.0\\pm4.9$ | $1024.00\\pm0.0$  |   $6.4\\pm0.2$   | $1023.97\\pm0.0$  | $50.0\\pm1.2$ | $950.39\\pm2.4$  | $21.1\\pm1.5$ | $1004.19\\pm0.4$  | $2.10\\pm0.2$ |\n| + A*-Thought | $50.3\\pm2.1$ |  $853.22\\pm4.3$  | $31.5\\pm4.9$ | $944.83\\pm14.7$  |  $20.3\\pm1.1$   |  $962.95\\pm6.3$  | $81.6\\pm0.5$ | $696.85\\pm4.6$  | $45.9\\pm1.8$ |  $864.47\\pm5.1$  | $5.31\\pm0.2$ |\n|              |              |                  |              |                  | **Budget: 2K**  |                  |              |                 |              |                  |              |\n|   QwQ-32B    | $50.6\\pm1.1$ | $1845.24\\pm3.2$  | $26.0\\pm1.2$ | $1970.87\\pm9.5$  |  $18.0\\pm1.0$   | $2020.94\\pm2.3$  | $80.3\\pm0.6$ | $1239.78\\pm4.0$ | $43.7\\pm0.5$ | $1769.21\\pm3.9$  | $2.47\\pm0.0$ |\n| + A*-Thought | $69.2\\pm0.8$ | $1282.09\\pm30.4$ | $44.0\\pm5.6$ | $1509.43\\pm40.0$ |  $31.1\\pm1.1$   | $1640.21\\pm8.0$  | $91.6\\pm0.4$ | $835.68\\pm5.6$  | $59.0\\pm1.3$ | $1316.85\\pm12.8$ | $4.48\\pm0.1$ |\n|              |              |                  |              |                  | **Budget: 4K**  |                  |              |                 |              |                  |              |\n|   QwQ-32B    | $75.3\\pm0.4$ | $2776.35\\pm15.6$ | $50.0\\pm6.3$ | $3485.04\\pm39.6$ |  $35.8\\pm0.8$   | $3634.92\\pm9.4$  | $84.8\\pm0.6$ | $1362.99\\pm8.7$ | $61.5\\pm1.6$ | $2814.83\\pm11.8$ | $2.18\\pm0.1$ |\n| + A*-Thought | $77.8\\pm1.7$ | $1717.41\\pm17.1$ | $60.0\\pm4.5$ | $2286.07\\pm49.9$ |  $41.4\\pm1.9$   | $2535.87\\pm28.0$ | $93.4\\pm0.3$ | $883.02\\pm17.6$ | $68.1\\pm1.6$ | $1855.59\\pm12.5$ | $3.67\\pm0.1$ |\n\n# For Weakness 3\n\nTo our knowledge, **`A*-Thought is the first work to adapt the principles of A* search for this task.`**\n\nOur method is fundamentally different from these predecessors.\n - vs. Retro-Search: A*-Thought performs a **systematic, global search** based on importance. Retro-Search does a **local, sequential exploration**.\n - 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**. \n Thus, despite a shared objective, our methodology is unique.\n\nBeyond 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.\n\n# For Weakness 4\n\nFollowing 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.\n\n# For Weakness 5\n\nOn 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.\n\nIn 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."}, {"review_id": "GYuHBmJpTu", "reviewer": "Reviewer_jq25", "summary": "This paper presents an approach for decreasing the length of chain-of-thought reasoning traces while maintaining accuracy. To do so, they design an algorithm that searches for subtraces that can still reach the final answer, and then conduct supervised fine-tuning (I think?) on those subtraces. Evaluated on mathematical reasoning benchmarks, the resulting models are much more accurate for a given token budget, and maintain accuracy when answering without a budget too. The algorithm for discovering subtraces is said to be a form of A* search that sorts tokens based on their importance in determining the solution, then chooses which tokens to in an expand-then-greedily-select step until the current subtrace is verified to produce a correct solution.", "questions": "Q1. Is a reasoning step $t^(n)$ a single token? Or is it like a sentence? If it's not a token, is the splitting of an answer into thoughts given by your dataset? For the rest of my answer, I'll assume it's a single token..\nQ1. For the NLL part of the BIS, it looks like $NLL(s | t^(n))$ is the probability of generating the solution given the single reasoning step? Isn't that going to be very hard for the model? Similarly, it seems odd to calculate the $NLL(t^(n) | q)$. But I guess even though it's weird, there's enough signal there to be useful?\nQ3. I don't understand the $A^*$ search algorithm. Is this even A^*? Here is my understanding:\n    1. sort tokens by BIS score. start with empty trace T.\n    2. take the top W tokens. For each one, score using cost function f. Take the best scoring token and add it to the trace.\n    3. check if current trace leads to solution using verifier. If it does, return current trace. Otherwise, repeat step 2.\n\nQuestions about this algorithm:\nQ3.1: why are there two different scoring functions, BIS and the cost function? It seems like BIS more efficient to evaluate, and f more expensive? Why not just use the same exact function for the two, but use a cheap model for the initial sorting function and then the full model for the cost function? \nQ3.2: what is the value of W? is this stated somewhere?\nQ3.3: the tokens after being sorted by BIS are out of order, right? when added to the trace, they are put back into their order, right?\nQ3.4: after expanding W options, are the ones that aren't finally selected put back into the queue, or discarded?\nQ4. how does the verifier work? You just say which model it is, but I don't understand what the model is doing.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Strengths\nThe approach works really well compared to baselines.\nThe paper is well-written. Most of it is easy to understand and clear. \nThe approach is interesting and novel. At first when I read the paper, I was skeptical that such an approach would lead to useful results, so it's surprising to see that it works.\nThe interesting part of the approach is the fine-grained importance score as the basis of discovering useful traces. It's based on attention weights and the likelihood of the model producing the solution given the tokens up to that point, but using GPT-2 instead of whatever model is generating the reasoning traces.\nI find it quite surprising that GPT-2 could yield useful scores this way, given how weak of a model it is.\n\n## Weaknesses\nThe A* algorithm and the bidirectional score could be explained more clearly. See questions section.\nThere are some other confusing parts of the paper, see questions section.\nThe baselines the approach is being compared to seem quite weak — see appendix E for prompts.", "was_revised": true, "final_justification": "The authors did a good job explaining details of the approach that I was confused about. I will update my score to a 5.", "rebuttal": "# For Q1\n\nEach thought step $\\mathbf{t}^{(n)}$ is a **`complete sentence`** (reported in Section 3.1, line 105). \n\nFollowing 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.\n\n# For Q 2\n\n**$\\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.\n\nGiven 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):\n$$\\mathrm{NLL}(\\mathbf{y} | \\mathbf{x}) = -\\frac{1}{|\\mathbf{y}|} \\sum_{j=1}^{|\\mathbf{y}|} \\mathrm{log} P \\left ( \ny_j | \\mathbf{x}, \\mathbf{y}_{<j} \\right ).$$\nA more informative context $\\mathbf{x}$ increases the likelihood of generating the target $\\mathbf{y}$. We apply this by treating each thought step $\\mathbf{t}^{(n)}$  as the context $\\mathbf{x}$ and calculating its relevance to both the question $\\mathbf{q}$ and the solution $\\mathbf{s}$ (as the target $\\mathbf{y}$). This results in two key scores: $\\mathrm{NLL}\\left( \\mathbf{q} | \\mathbf{t}^{(n)} \\right)$ and $\\mathrm{NLL}\\left( \\mathbf{s} | \\mathbf{t}^{(n)} \\right)$.\n\nTo improve scoring and enhance the distinctiveness of the results, we follow LongLLMLingua by inserting a template phrase to explicitly prompt the causal connection. Specifically, we use:\n- For $\\mathrm{NLL}\\left( \\mathbf{q} | \\mathbf{t}^{(n)} \\right)$: \"We can get the solution to this question in the given thought step.\"\n- For $\\mathrm{NLL}\\left( \\mathbf{s} | \\mathbf{t}^{(n)} \\right)$: \"We can get this solution in the given thought step.\"\n\n# For Q 3\n\nA* search is a canonical heuristic algorithm in computer science, which was jointly proposed by Peter Hart, Nils Nilsson and Bertram Raphael in 1968. It is widely applied in the fields of path planning and map navigation in AI systems. It uniquely combines search efficiency with the guarantee of discovering the shortest possible path. The algorithm progresses by calculating a total cost function, $F(n)=G(n)+H(n)$, for every node n it considers. Within this function, $G(n)$ represents the exact cost incurred to travel from the origin to node n, while $H(n)$ represents the future cost—a heuristic estimation of the cost from node n to the final destination. It is by virtue of this heuristic information, $H(n)$, that the A* algorithm can intelligently navigate a vast search space without resorting to an exhaustive exploration, thus ensuring computational efficiency.\n\nDrawing an analogy, we can view the standard Chain-of-Thought (CoT) method, shown in Figure 1(a), as an unguided traversal of all intermediate nodes, which is often a convoluted and verbose approach. Inspired by the principles of A* search, our A*-Thought method (Figure 1(b)) introduces a heuristic to this process. Here, the importance of each node—visualized by its color depth—serves as the heuristic. By integrating this information, A*-Thought efficiently searches for the most concise thought trajectory required to solve a problem, which in turn leads to highly efficient reasoning and inference.\n\nTherefore, the overall pipeline is:\n1. sort **`sentences`** by BIS score. start with empty trace T.\n2. take the top W **`sentences`**, and respectively obtain the **`thinking span`** centered on the sentence and carrying the preceding and following sentences. For each one, score using cost function F. Take the best scoring **`thinking span`** and add it to the trace.\n3. check if current trace leads to solution using verifier. If it does, return current trace. Otherwise, repeat step 2.\n\n# For Q 3.1\n\nBoth the Bidirectional Importance Score (BIS) and the Cost Function serve to guide the expansion of the search tree, but at different granularities: BIS determines the **coarse-grained global direction**, while the Cost Function determines the **fine-grained local direction**.\n- **Global Direction (BIS)**: In classic pathfinding, the positions of all nodes between the start and end points are fixed, which allows for a straightforward determination of candidate node priority at each search depth. In contrast, for the many thought steps in a Chain-of-Thought, we must first assess the intrinsic importance of each sentence based on its quality and informational content. This assessment establishes a priority order for expanding candidate steps into the search tree. Therefore, the role of BIS is to guide the global direction of the search.\n- **Local Direction (Cost Function):** At each step of the search, we examine only the top $W$ candidates from the BIS queue. We form a \"thinking span\" around each candidate and apply the cost function $f(\\cdot)$ to select the single best span to advance the search path, returning the other candidates to the queue. This makes the Cost Function a local, step-by-step decision-maker.\n\nA key distinction lies in their nature: **`BIS scores are static`**, calculated once to reflect the intrinsic merit of each step. In contrast, the **`Cost Function is dynamic`**. Navigating a non-enumerable search space efficiently requires a dynamic function that can accurately assess a path's current cost and future value at every step.\n\nThis conceptual separation informs our choice of models. For the global ranking task performed by BIS, we use the efficient and cost-effective GPT-2 model. For the critical, dynamic, and fine-grained local evaluation managed by the Cost Function, we leverage the more powerful and precise s1.1-32B model to achieve superior performance.\n\n# For Q 3.2\n\nThe exploration size $W$ was set to 2 (already reported in the Training Details paragraph of the original Section 4.1, line 206).\n\n# For Q 3.3\n\nWe use the Bidirectional Importance Score (BIS) to sort the sentences in **`descending order`**, forming a priority queue. In this queue, the sentences are intentionally out of sequence compared to their order in the original CoT.\n\nHowever, when they are selected and added to the compressed path, they are arranged to maintain their **`original order`**.\n\n# For Q 3.4\n\nAfter expanding the $W$ options, candidates that are not selected are **`put back into the queue`**.\n\n# For Q 4\n\nGiven the current compressed thinking path  $\\mathbf{t}^{\\prime}_k$, question $\\mathbf{q}$ and solution $\\mathbf{s}$, the validation model $\\mathcal{V}$ plays a dual role during the A* search phase: **generating a candidate solution $\\mathbf{s}^{\\prime}_k$ for verification and calculating the Cost Function $f(\\cdot)$ for exploration** (reported in Section 3.1, lines 132-139 and 158-167).\n\n## 1. Verification Phase\n\nFirst, the validation model $\\mathcal{V}$, is prompted to perform sequence completion on the following input:\n$$\\mathbf{q} \\langle think \\rangle \\mathbf{t}_k^{\\prime} \\langle/think\\rangle \\langle solution \\rangle$$\nThis generates a candidate solution $\\mathbf{s}^{\\prime}_k$, resulting in the complete sequence:\n$$\\mathbf{q} \\langle think \\rangle \\mathbf{t}^{\\prime}_k \\langle /think \\rangle \\langle solution \\rangle \\mathbf{s}^{\\prime}_k \\langle /solution \\rangle$$\nIf the generated solution matches the ground truth ($\\mathbf{s}^{\\prime}_k==\\mathbf{s}$), it indicates that the current path $\\mathbf{t}^{\\prime}_k$​ is of high quality and contains sufficient information. The algorithm then terminates and returns $\\mathbf{t}^{\\prime}_k$​ as the final output. If they do not match ($\\mathbf{s}^{\\prime}_k\\neq\\mathbf{s}$), the algorithm proceeds to the exploration phase.\n\n## 2. Exploration Phase\n\nIn this phase, the top $W$ \"thinking spans\" from the priority queue, denoted as $\\lbrace \\mathbf{r}_1, \\dots, \\mathbf{r}_W \\rbrace$, are selected as candidates for expansion. For each candidate $\\mathbf{r}_w$, the validation model $\\mathcal{V}$ is used to evaluate the cost function $f\\left (\\mathbf{t}_k^{\\prime}+\\mathbf{r}_w\\right) = g\\left (\\mathbf{t}_k^{\\prime}+\\mathbf{r}_w\\right) + h\\left (\\mathbf{t}_k^{\\prime}+\\mathbf{r}_w\\right)$. This is done by providing the model with the following input, which includes the ground-truth solution:\n$$\\mathbf{q} \\langle think \\rangle \\mathbf{t}^{\\prime}_k+\\mathbf{r}_w \\langle /think \\rangle \\langle solution \\rangle \\mathbf{s} \\langle /solution \\rangle$$\nThe candidate with the minimum cost function value is then chosen to expand the search tree, and the process moves to the next iteration. Further details on the algorithm and the validation model's operation are provided in Algorithm 1 in Appendix A, lines 382-383.\n\n# For Weakness\n\nTo comprehensively evaluate its performance, in addition to the prompt-based baselines (Chain-of-Draft and Break-the-Chain in Appendix E), we also compared A*-Thought against a training-based baseline and the backbone model.\n- **Training-based baseline:** We compared against **`TokenSkip`**, a method that involves a two-stage process: first, shortening long CoT datasets with LLMLingua-2 compression, and second, using the resulting data to train an efficient model.\n- **Backbone model baseline:** We also included the QwQ-32B model as a fundamental point of comparison."}, {"review_id": "O8PKHLXFDl", "reviewer": "Reviewer_JDQU", "summary": "The paper introduces A*-Thought, a novel framework designed to enhance the reasoning efficiency of Large Reasoning Models (LRMs) by compressing their lengthy reasoning chains. The authors propose a bidirectional importance estimation mechanism to evaluate the significance of each reasoning step based on its relevance to both the question and the solution. This mechanism assigns a bidirectional importance score (BIS) to each step, which is then used in conjunction with the A* search algorithm to identify and isolate the most essential thoughts from the extensive reasoning chains. The A* search algorithm employs cost functions that assess the quality of the current path and estimate the future cost to reach a desirable final solution, thereby efficiently compressing the chain of thought and determining a reasoning path with high information density and low cost. Extensive experiments on various advanced math tasks demonstrate that A*-Thought effectively balances performance and efficiency over a huge search space. For instance, it can improve the performance of QwQ-32B by 2.39× with low-budget and reduce the length of the output token by nearly 50% with high-budget. The proposed method is also compatible with several other LRMs, showcasing its generalization capability.", "questions": "### Questions\n\n1. What validation model is used during the A* search process? The paper does not seem to specify this, which raises concerns about reproducibility and implementation clarity.\n\n2. The teaser figure is difficult to interpret. What do the circles of different sizes and depths represent? A legend or further explanation would greatly improve readability.\n\n3. Does using `\\n\\n` as a delimiter for segmenting thought steps risk omitting essential intermediate reasoning steps, especially in multi-line or complex CoT outputs?\n\n4. Have the authors explored **test-time scaling strategies**, such as self-consistency or diverse sampling? Such evaluations would help better understand the upper-bound performance of the method.", "limitations": "No.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. The paper is novel and presents a well-defined problem formulation. Both the **Step-Level Bidirectional Importance Score** and the **Path-Level A\\* Search** are intuitively motivated and thoroughly described.  \n2. The proposed method achieves strong empirical performance, demonstrating a **2.39× speedup** over the 32B model.  \n3. The overall structure of the paper is clear and easy to follow.\n\n### Weaknesses\n\n1. It would be helpful to include a more detailed analysis of the **computational cost** incurred by the A* search process when selecting training samples across benchmarks.  \n2. The paper would benefit from a broader evaluation across **different model scales** to better assess robustness.", "was_revised": true, "final_justification": "All of my concerns have been addressed. I have updated my score based the rebuttal.", "rebuttal": "# For Question 1\n\nThe verification model $\\mathcal{V}$ is the **`original s1.1-32B model`** (reported in the Training Details paragraph of Section 4.1, line 178). \n\n# For Question 2\n\nWe have already explained the meaning of the circles and their color intensity (reported in the description of Figure 1).\n\nTo be precise, **`all circles are of a consistent size`**, with each representing a thought step.\n\n**`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.\n\n# For Question 3\n\nFollowing prior works such as Retro-Search, ThinkPrune, Length-filtered Vote, and SEAL, we split reasoning steps using \"\\n\\n\".\n\nBuilding 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.\n\n# For Question 4\n\nWe 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.\n\n|       Methods       | MATH-500 |        |        |                 | LiveCodeBench |        |        |        |\n| :-----------------: | -------- | ------ | ------ | --------------- | ------------- | ------ | ------ | ------ |\n|                     | pass@1   | pass@2 | pass@4 | pass@8          | pass@1        | pass@2 | pass@4 | pass@8 |\n|                     |          |        |        | **Budget: 512** |               |        |        |        |\n|       QwQ-32B       | 10.8     | 17.2   | 25.9   | 34.4            | 0.0           | 0.0    | 0.0    | 0.0    |\n| + A*-Thought (Ours) | 33.2     | 47.4   | 60.7   | 70.2            | 4.5           | 7.0    | 12.5   | 20.8   |\n|                     |          |        |        | **Budget: 1K**  |               |        |        |        |\n|       QwQ-32B       | 16.6     | 29.6   | 42.1   | 53.2            | 0.0           | 0.1    | 0.1    | 0.3    |\n| + A*-Thought (Ours) | 50.8     | 65.4   | 75.8   | 81.8            | 11.8          | 20.4   | 31.9   | 44.8   |\n|                     |          |        |        | **Budget: 2K**  |               |        |        |        |\n|       QwQ-32B       | 51.2     | 59.8   | 67.8   | 74.8            | 2.1           | 3.4    | 5.1    | 7.0    |\n| + A*-Thought (Ours) | 69.2     | 79.2   | 85.4   | 89.0            | 24.5          | 34.0   | 45.2   | 56.5   |\n|                     |          |        |        | **Budget: 4K**  |               |        |        |        |\n|       QwQ-32B       | 75.4     | 80.2   | 84.0   | 86.8            | 12.4          | 17.7   | 23.0   | 28.0   |\n| + A*-Thought (Ours) | 78.8     | 86.8   | 91.1   | 93.2            | 39.0          | 50.9   | 60.9   | 68.8   |\n\n# For Weakness 1\n\nOur training data is **`independent of the test sets`** (reported in the Training Data and Verification Model paragraph of Section 4.1, lines 177-178).\n\nA*-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.\n\nCrucially, 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).\n\n|   Methods    | LiveCodeBench |         |      MMLU       |         | Average |         | ACU  |\n| :----------: | :-----------: | :-----: | :-------------: | :-----: | :-----: | :-----: | :--: |\n|              |     Acc.      |  Len.   |      Acc.       |  Len.   |  Acc.   |  Len.   |      |\n|              |               |         | **Budget: 512** |         |         |         |      |\n|   QwQ-32B    |      0.0      | 512.00  |      37.6       | 511.94  |  18.8   | 511.97  | 3.67 |\n| + A*-Thought |      4.5      | 509.53  |      56.7       | 398.57  |  30.6   | 454.05  | 6.74 |\n|              |               |         | **Budget: 1K**  |         |         |         |      |\n|   QwQ-32B    |      0.0      | 1021.94 |      57.4       | 956.90  |  28.7   | 989.42  | 2.90 |\n| + A*-Thought |     11.8      | 986.02  |      71.9       | 573.30  |  41.9   | 779.66  | 5.37 |\n|              |               |         | **Budget: 2K**  |         |         |         |      |\n|   QwQ-32B    |      3.5      | 1977.58 |      75.2       | 1323.26 |  39.4   | 1650.42 | 2.38 |\n| + A*-Thought |     24.5      | 1734.28 |      79.0       | 671.41  |  51.8   | 1202.85 | 4.30 |\n|              |               |         | **Budget: 4K**  |         |         |         |      |\n|   QwQ-32B    |     12.0      | 3586.93 |      79.5       | 1584.05 |  45.8   | 2585.49 | 1.77 |\n| + A*-Thought |     39.0      | 3044.51 |      80.3       | 733.90  |  59.7   | 1889.21 | 3.16 |\n\n# For Weakness 2\n\nWe 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.\n\n|        Methods        |  MATH500 |             |   AMC23  |             |  OlympiadBench  |             |   GSM8K  |             |  Average |             |    ACU   |\n| :-------------------: | :------: | :---------: | :------: | :---------: | :-------------: | :---------: | :------: | :---------: | :------: | :---------: | :------: |\n|                       |   Acc.   |     Len.    |   Acc.   |     Len.    |      Acc.       |     Len.    |   Acc.   |     Len.    |   Acc.   |     Len.    |          |\n|                       |          |             |          |             | **Budget: 512** |             |          |             |          |             |          |\n|     TokenSkip-7B      |      9.4 |      511.41 |      2.5 |      512.00 |       4.0       |      512.00 |     25.5 |      508.40 |     10.4 |       511.0 |     2.03 |\n| A*-Thought-7B (Ours)  | **30.8** |  **499.12** |  **5.0** |  **508.70** |     **6.7**     |  **509.36** | **59.2** |  **447.22** | **25.4** |  **491.10** | **5.18** |\n|     TokenSkip-14B     |      9.2 |      510.89 |      7.5 |      512.00 |       4.8       |      512.00 |     29.0 |      511.17 |     12.6 |      511.52 |     2.47 |\n| A*-Thought-14B (Ours) | **30.4** |  **497.54** | **10.0** |  **512.00** |    **10.4**     |  **508.77** | **50.9** |  **475.30** | **25.4** |  **498.40** | **5.10** |\n|                       |          |             |          |             | **Budget: 1K**  |             |          |             |          |             |          |\n|     TokenSkip-7B      |     24.8 |      986.62 |     10.0 |     1021.33 |       7.9       |     1019.11 |     51.0 |      907.40 |     23.4 |      983.62 |     2.38 |\n| A*-Thought-7B (Ours)  | **48.2** |  **866.93** | **25.0** |  **991.42** |    **19.3**     |  **961.42** | **74.3** |  **661.99** | **41.7** |  **870.44** | **4.79** |\n|     TokenSkip-14B     |     23.6 |      991.65 |     10.0 |     1024.00 |       7.4       |     1020.22 |     47.8 |      960.13 |     22.2 |      999.00 |     2.22 |\n| A*-Thought-14B (Ours) | **49.2** |  **873.53** | **22.5** |  **997.33** |    **18.8**     |  **966.55** | **78.3** |  **738.61** | **42.2** |  **894.01** | **4.72** |\n|                       |          |             |          |             | **Budget: 2K**  |             |          |             |          |             |          |\n|     TokenSkip-7B      |     35.4 |     1776.50 |     20.0 |     1968.47 |      14.7       |     1959.13 |     55.6 |     1534.37 |     31.4 |     1809.62 |     1.74 |\n| A*-Thought-7B (Ours)  | **59.2** | **1352.54** | **30.0** | **1715.22** |    **25.4**     | **1677.38** | **77.6** |  **874.11** | **48.1** | **1404.81** | **3.42** |\n|     TokenSkip-14B     |     55.8 |     1678.03 |     20.0 |     1934.05 |      20.8       |     1940.58 |     73.8 |     1453.71 |     42.6 |     1751.59 |     2.43 |\n| A*-Thought-14B (Ours) | **64.2** | **1308.18** | **40.0** | **1650.40** |    **28.3**     | **1610.04** | **86.1** |  **930.89** | **54.7** | **1374.88** | **3.97** |\n|                       |          |             |          |             | **Budget: 4K**  |             |          |             |          |             |          |\n|     TokenSkip-7B      |     39.8 |     3201.90 |     27.5 |     3593.93 |      20.9       |     3566.00 |     63.4 |     2651.40 |     37.9 |     3253.31 |     1.16 |\n| A*-Thought-7B (Ours)  | **61.8** | **1999.10** | **30.0** | **2840.70** |    **29.6**     | **3048.73** | **78.0** | **1271.18** | **49.9** | **2289.93** | **2.18** |\n|     TokenSkip-14B     |     68.4 |     2406.16 |     40.0 |     3338.80 |      32.5       |     3334.73 |     81.2 |     2054.78 |     55.5 |     2783.62 |     1.99 |\n| A*-Thought-14B (Ours) | **70.8** | **1677.00** | **42.5** | **2350.32** |    **34.6**     | **2494.24** | **88.8** | **1100.52** | **59.2** | **1905.52** | **3.11** |"}]

Author rebuttal:

Meta-review: This paper introduces A*-Thought, a framework that compresses lengthy Chain-of-Thought (CoT) outputs from large reasoning models using A* search guided by a bidirectional importance score (BIS). The method addresses efficiency challenges in verbose CoT reasoning by identifying high-value reasoning steps through attention statistics and token-level negative log-likelihood, aiming to retain performance while significantly reducing token output length.

The paper addresses a highly relevant problem of excessive reasoning length in large reasoning models, which aligns with growing interest in cost-efficient inference. The methodological innovation of integrating bidirectional importance scoring with A* search to identify essential reasoning steps is novel and well-motivated. Experimental results demonstrate substantial performance gains, with up to 2.39× improvement for QwQ-32B under constrained budgets and approximately 50% reduction in output tokens. The approach shows strong empirical performance across multiple mathematical reasoning benchmarks and demonstrates generalization capability across different large reasoning models. Thus I recommend to accept this paper.

Following the discussion phase, all major reviewer concerns have been adequately addressed. The authors successfully clarified the theoretical foundations, provided additional analysis of computational costs, and demonstrated broader applicability across different model scales. The novel combination of bidirectional importance scoring with A* search represents a valuable contribution to efficient reasoning in large language models, with strong empirical validation supporting its practical utility.
Decision: Accept (poster)