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

arXiv: https://arxiv.org/abs/2505.24550 · HTML: https://mlsanity.com/paper/2505.24550/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 24 of its 30 references that are in the map.
- First posted on arXiv 30 May 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 24 of 24)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [OlympiadBench: A Challenging Benchmark for Promoting AGI with Olympiad-Level Bilingual Multimodal Scientific Problems](https://mlsanity.com/paper/2402.14008/) (2024)
- [Training Large Language Models to Reason in a Continuous Latent Space](https://mlsanity.com/paper/2412.06769/) (2024)
- [MiniCPM: Unveiling the Potential of Small Language Models with Scalable Training Strategies](https://mlsanity.com/paper/2404.06395/) (2024)
- [Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs](https://mlsanity.com/paper/2412.21187/) (2024)
- [LongLLMLingua: Accelerating and Enhancing LLMs in Long Context Scenarios via Prompt Compression](https://mlsanity.com/paper/2310.06839/) (2023)
- [L1: Controlling How Long A Reasoning Model Thinks With Reinforcement Learning](https://mlsanity.com/paper/2503.04697/) (2025)
- [SmolLM2: When Smol Goes Big -- Data-Centric Training of a Small Language Model](https://mlsanity.com/paper/2502.02737/) (2025)
- [Chain of Draft: Thinking Faster by Writing Less](https://mlsanity.com/paper/2502.18600/) (2025)
- [TokenSkip: Controllable Chain-of-Thought Compression in LLMs](https://mlsanity.com/paper/2502.12067/) (2025)
- [Token-Budget-Aware LLM Reasoning](https://mlsanity.com/paper/2412.18547/) (2024)
- [Compressed Chain of Thought: Efficient Reasoning Through Dense Representations](https://mlsanity.com/paper/2412.13171/) (2024)
- [Reasoning Models Can Be Effective Without Thinking](https://mlsanity.com/paper/2504.09858/) (2025)
- [CoT-Valve: Length-Compressible Chain-of-Thought Tuning](https://mlsanity.com/paper/2502.09601/) (2025)
- [Optimizing Test-Time Compute via Meta Reinforcement Fine-Tuning](https://mlsanity.com/paper/2503.07572/) (2025)
- [Sketch-of-Thought: Efficient LLM Reasoning with Adaptive Cognitive-Inspired Sketching](https://mlsanity.com/paper/2503.05179/) (2025)
- [LightThinker: Thinking Step-by-Step Compression](https://mlsanity.com/paper/2502.15589/) (2025)
- [How Well do LLMs Compress Their Own Chain-of-Thought? A Token Complexity Approach](https://mlsanity.com/paper/2503.01141/) (2025)
- [Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoning](https://mlsanity.com/paper/2502.03275/) (2025)
- [The Benefits of a Concise Chain of Thought on Problem-Solving in Large Language Models](https://mlsanity.com/paper/2401.05618/) (2024)
- [Retro-Search: Exploring Untaken Paths for Deeper and Efficient Reasoning](https://mlsanity.com/paper/2504.04383/) (2025)
- [Break the Chain: Large Language Models Can be Shortcut Reasoners](https://mlsanity.com/paper/2406.06580/) (2024)
- [Can Atomic Step Decomposition Enhance the Self-structured Reasoning of Multimodal Large Models?](https://mlsanity.com/paper/2503.06252/) (2025)

## Built on by (most cited first, 9 of 9)

- [Don't Overthink It: A Survey of Efficient R1-style Large Reasoning Models](https://mlsanity.com/paper/2508.02120/) (2025)
- [Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models](https://mlsanity.com/paper/2601.11340/) (2026)
- [Steering Large Reasoning Models towards Concise Reasoning via Flow Matching](https://mlsanity.com/paper/2602.05539/) (2026)
- [SmartThinker: Progressive Chain-of-Thought Length Calibration for Efficient Large Language Model Reasoning](https://mlsanity.com/paper/2603.08000/) (2026)
- [BFS-PO: Best-First Search for Large Reasoning Models](https://mlsanity.com/paper/2602.14917/) (2026)
- [CRISP: Compressing Redundancy in Chain-of-Thought via Intrinsic Saliency Pruning](https://mlsanity.com/paper/2604.17297/) (2026)
- [A*-Thought-V2: Efficient Latent Reasoning via Geometric Dynamics of LLM](https://mlsanity.com/paper/2609.07821/) (2026)
- [Bridging Efficiency and Transparency: Explainable CoT Compression in Multimodal Large Reasoning Models](https://mlsanity.com/paper/2602.09485/) (2026)
- [PathCal: State-Aware Reflection-Marker Calibration for Efficient Reasoning](https://mlsanity.com/paper/2605.23074/) (2026)

## Abstract (arXiv)

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× 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.