PaperlayerView exact revision on arXiv

Source-linked AI summary

A*-Thought: Efficient Reasoning via Bidirectional Compression for Low-Resource Settings

Xiaoang Xu, Shuo Wang, Xu Han, Zhenghao Liu, Huijia Wu, Peipei Li, Zhiyuan Liu, Maosong Sun, Zhaofeng He

arXiv:2505.24550v2cs.CL

TL;DR

Long reasoning chains make LRM inference costly, while selecting informative steps and assembling concise paths remain challenges. A*-Thought combines bidirectional step-importance estimation with A* path search; experiments report gains under low budgets and strong results across budgets and backbones.

  • Problem

    Long chain-of-thought reasoning raises inference costs, and the paper frames identifying informative steps and assembling concise paths as open challenges.

    Source: §1 · p. 2

  • Method

    A*-Thought estimates step importance bidirectionally and uses A* search with path-quality and estimated-future-cost functions to find compact reasoning paths.

    Source: §1 · p. 2, §3.1 · p. 4, §3.2.1 · p. 5

  • Results

    Across examined budgets and three backbones, A*-Thought reports strong efficiency and accuracy; low-budget improvements reach 2.39× accuracy and 2.49× ACU.

    Source: §4.2 · p. 7

  • Takeaways & Limitations

    The paper reports that systematically reducing redundant reasoning steps streamlines paths from query to solution and improves LRM performance across diverse budgets.

    Source: §3.2.2 · p. 6

    A*-Thought is currently confined to supervised fine-tuning; extending it to reinforcement learning is future work.

    Source: H Limitation and Future Works · p. 22

Abstract

from arXiv · show

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.

1 Introduction

Long reasoning chains raise inference costs, while compressing them must preserve useful reasoning. The introduction frames this as finding informative steps and assembling them into effective paths, then presents A*-Thought as a step- and path-level search framework.

1 Introduction

  • Long chain-of-thought reasoning increases inference computation, storage, and resource demands, constraining practical use in on-device and end-point settings.The introduction notes that these settings have strictly limited computational budgets and memory footprints.Source: §1 · p. 2
  • Prior long-to-short methods include training models for concise responses and prompting them to use shorter, more atomic reasoning steps.The cited examples are presented as approaches to reducing generated thought length.Source: §1 · p. 2
  • The framework treats an effective intermediate step as both logically sound and relevant, and informative by contributing critical information toward the solution.A step may still be informative if its intermediate conclusion is imperfect or erroneous in isolation but facilitates the correct final answer.Source: §1 · p. 2
  • A*-Thought combines bidirectional step-importance estimation with A* search to find compact reasoning paths, assessing both current path quality and estimated future cost.The search addresses two challenges: identifying high-quality, informative steps and assembling them into a concise path.Source: §1 · p. 2
  • 3.53× improvement in accuracy is reported for QwQ-32B in concise-output scenarios.The contribution summary also describes BIS for evaluating individual sentences and A* search that weighs current path quality and estimated future cost.Source: §1 · p. 2

2 Problem Setup

The setup represents an LRM's response to a question as an extended trajectory of reasoning steps and a corresponding solution. It seeks a smaller subset of those steps that retains reasoning performance and increases knowledge density across computational budgets.

2 Problem Setup

  • An LRM generates a trajectory of N reasoning steps and a corresponding solution for a question.The setup denotes the trajectory by t and the solution by s.Source: §2 · p. 3
  • As the number of steps grows, models may switch thinking modes, and sampling a complete trajectory can hinder solution-estimation convergence and increase inference cost.Source: §2 · p. 3
  • The objective is to select a subset of the trajectory that preserves reasoning performance as much as possible while increasing knowledge density across computational budgets.Source: §2 · p. 3

3 Method

A*-Thought combines step-level importance estimates with path-level A* search to select compact reasoning paths. It uses current-path quality and estimated future cost to guide a search through candidate thought sequences.

3 Method

  • A*-Thought first scores local thinking steps with BIS, then uses those scores in A* search to compress the thought trajectory.The step-level score supports the subsequent path-level search.Source: §3 · p. 3

3.1 Step-Level Bidirectional Importance Score

  • BIS estimates each step’s importance from its relevance to both the question and the final solution, using attention and negative log-likelihood measures.A smaller language model computes the estimates; α controls the relative weighting of question versus solution relevance.Source: §3.1 · pp. 3–4

3.2 Path-Level A* Search

  • Because exhaustive exploration of 2N candidate trajectories is computationally intractable for long CoTs, A* search navigates the candidate space while a verifier checks whether a path leads to the solution.The method frames the reasoning process as a search tree of candidate paths.Source: §3.2 · p. 4

3.2.1 Overview

  • BIS-ranked steps seed a best-first queue; each search node spans neighboring steps, and paths are verified only after kmin before failed leaves expand into W candidates.The search stops and returns the current path at the depth limit kmax.Source: §3.2.1 · pp. 4–5

3.2.2 Design of Cost Functions

  • A* ranks paths using current-path quality g and future-cost heuristic h, with h based on correct-solution conditional self-information; higher values indicate a lower likelihood of generating the solution.A verification model estimates current-path quality, while the future-cost estimate reflects the remaining cost to reach the goal.Source: §3.2.2 · pp. 5–6

4 Experiments

The experiments compare compression methods across three reasoning backbones and four math benchmarks. A*-Thought shows strong low-budget gains, shorter outputs at high budgets, and effectiveness across several LRMs.

4.1 Setup

  • Setup evaluates three backbones on four math benchmarks, measuring accuracy, response length, and ACU against prompt- and training-based baselines.Training data use long CoTs from Muennighoff et al. (2025), with s1.1-32B as the verification model.Source: §4.1 · p. 6

4.2 Main Results

  • 2.39× accuracy and 2.49× ACU improvements for QwQ-32B at 512 tokens raise average accuracy from 12.3 to 29.4 and ACU from 2.41 to 5.99.Table 1 reports experimental results across several benchmarks and methods.Source: §4.2 · p. 7, Table 1 · p. 7
  • At 4096 tokens, A*-Thought reduces QwQ-32B average response length from 2826.00 to 1876.66 tokens, while average accuracy shifts from 70.6% to 69.3%.It also achieves the highest ACU in this setting, outperforming prompt-based and training-based baselines.Source: §4.2 · p. 7
  • A*-Thought achieves the highest efficiency and accuracy across QwQ-32B, R1-Distill-32B, and s1.1-32B under various budget conditions.Figures 4 and 5 show ACU and performance curves across these backbones.Source: §4.2 · p. 7, Figure 4 · p. 8, Figure 5 · p. 8

5 Analysis

The analysis reports out-of-domain results, tests an A* search parameter, compares training outcomes, and illustrates the resulting reasoning style.

5.1 Performance on More Benchmarks

  • A*-Thought improves performance and inference efficiency on LiveCodeBench and MMLU despite training exclusively on mathematical tasks.Table 2 reports results on these out-of-domain benchmarks.Source: §5.1 · p. 8, Table 2 · p. 8

5.2 Analysis on the Effect of A* Search

  • With kmin = 15 and a 4K-token budget, A*-Thought outperforms the strongest baseline across all benchmarks with higher token efficiency.Table 3 analyzes the effect of kmin on model performance.Source: §5.2 · p. 9, Table 3 · p. 9

5.3 Training Loss and Training Time

  • A*-Thought achieves the lowest training loss and a higher compression ratio than TokenSkip.The authors suggest preserving spans around individual thoughts and considering intermediate-path quality may support learnability of the compressed data.Source: §5.3 · p. 9, Table 4 · p. 9, Figure 6 · p. 9

5.4 Case Study

  • For the same question, trained models with and without A*-Thought both solve it correctly, while the A*-Thought model follows a more streamlined, focused thinking path.The examples indicate that A*-Thought can train models to adopt a more concise thinking process.Source: §5.4 · p. 9, Figure 7 · p. 10

6 Related Works

Related efficiency work uses prompting and CoT compression, while other methods optimize tokens or explore reasoning paths. This paper instead guides A* search with bidirectional importance scores.

6 Related Works

  • Prior efficiency strategies include refined prompting (Renze & Guven, 2024; Ma et al., 2025a) and CoT compression.Source: §6 · p. 10
  • TokenSkip selectively processes query-relevant tokens, whereas Retro-Search explores multiple reasoning paths to address redundancy and underexploration.Source: §6 · p. 10
  • This paper uses bidirectional importance scores to guide A* search toward a computationally efficient yet effective reasoning pathway.Source: §6 · p. 10

7 Conclusion

A*-Thought compresses LRM reasoning by estimating step importance bidirectionally and using A* costs to assemble concise paths; the conclusion reports outperformance over representative baselines.

7 Conclusion

  • A*-Thought is reported to outperform several representative baselines through concise reasoning paths guided by step importance and specialized A* costs.The costs assess current partial-path quality and estimated completion cost.Source: §7 · p. 10

A A*-Thought Algorithm Detail

  • The search initializes from a BIS-sorted thought list and selects among explored candidates using the lowest combined current and estimated future cost.The selected thought is appended to the compressed path.Source: A A*-Thought Algorithm Detail · p. 14
  • When the search reaches the maximum exploration depth, the algorithm returns the original reasoning trajectory.Source: A A*-Thought Algorithm Detail · p. 14

B Test-Time-Scaling Strategies

C Performance of Models of Varying Sizes

D Detailed Results of R1-Distill-32B and s1.1-32B

This section covers detailed evaluations of R1-Distill-32B and s1.1-32B, plus an additional-ablation reporting convention for QwQ-32B.

D Detailed Results of R1-Distill-32B and s1.1-32B

E Additional Ablation Analysis

E.1 Analysis on BIS

The BIS ablations favor combining question- and solution-related signals, while the search analysis finds that useful exploration depth varies with token budget.

E.1 Analysis on BIS

  • Jointly applying ATTN and NLL to BIS is reported to improve model performance more than manipulating either signal alone across budgets.Figure 8 presents their effects under a 512-token budget.Source: §E.1 · p. 17, Figure 8 · p. 17
  • BIS performs best when α appropriately balances question and solution information rather than relying entirely on either perspective.The ablation varies α across 0, 0.25, 0.5, 0.75, and 1.Source: §E.1 · p. 17, Figure 9 · p. 17

E.2 Analysis on A* Search

  • Moderate exploration steps work better at 512–2048-token budgets, whereas a 4096-token budget benefits from more exploration; the default is kmax = 20.Source: §E.2 · p. 18, Figure 10 · p. 18
  • The supplementary β ablation tests values 0.1, 0.5, and 0.9 on ARC and LiveCodeBench, with results listed in Table 9.Source: §E.2 · p. 18, Table 9 · p. 18

F The Prompt used in this Work

G Example of the A*-Thought Trajectories

Two examples compare original and A*-Thought trajectories for QwQ-32B and s1.1-32B, illustrating reduced redundancy while preserving reasoning ability.

G Example of the A*-Thought Trajectories

H Limitation and Future Works

A*-Thought is currently confined to supervised fine-tuning, with extension to reinforcement learning left for future investigation. The paper also frames efficiency as a way to reduce LRM deployment’s energy footprint and support resource-scarce settings such as endpoint devices.

H Limitation and Future Works

  • A*-Thought is currently confined to supervised fine-tuning (SFT).The authors intend to investigate extending it to an RL-based approach.Source: H Limitation and Future Works · p. 22
  • The authors identify extension to reinforcement learning as future work, citing recent studies on RL’s efficacy for advancing LRM reasoning.The passage describes this as an intended investigation, not an established application of A*-Thought.Source: H Limitation and Future Works · p. 22

I Impact Statement

  • The impact statement presents more efficient AI as a way to decrease LRM deployment’s energy footprint and enable use in resource-scarce environments such as endpoint devices.Source: I Impact Statement · p. 22

Related papers

Loading 2505.24550v2…