Research map / Large language models / Reasoning and chain of thought

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

NeurIPS 2025 · Large language models › Reasoning and chain of thought · approach: Long CoT dynamics and efficiency · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Compresses long chain-of-thought traces of large reasoning models by using A* tree search over thought spans, guided by a GPT-2 bidirectional importance score and a verifier-based cost, then fine-tunes models on the compressed traces.

Problem

Large reasoning models produce very long chain-of-thought traces, which raise inference cost; existing compression methods often degrade accuracy, so the goal is to find compact reasoning paths that keep performance under tight token budgets.

Approach

Treats CoT compression as A* search over a tree whose nodes are thought spans ordered by a bidirectional importance score (question and solution relevance computed with GPT-2 attention and NLL), with path cost combining verifier log-likelihood of the current path and conditional self-information of the solution as the heuristic.

Key results

• On QwQ-32B at a 512-token budget, A*-Thought raises average accuracy from 12.3 to 29.4 (about 2.39x) and ACU from 2.41 to 5.99.
• At a 4096-token budget on QwQ-32B, average length drops from 2826 to 1877 tokens (about 33.6% reduction) with accuracy 70.6 to 69.3.
• Training on compressed data reduces training time by about 22-24% relative to the full s1K-1.1 set, with 31.31% of the original token count.

Measured effects reported in the paper

Surprising findings

• Compressed A*-Thought data at 4096 tokens yields lower accuracy than the uncompressed s1K-1.1 fine-tuned baseline on some benchmarks (e.g., AMC23 and OlympiadBench), indicating a trade-off rather than uniform gains.

Limitations

• Application limited to supervised fine-tuning; RL extension is future work.
• Relies on a verification model (s1.1-32B) and multiple sampling/verification calls during search, which adds search cost.
• Evaluated mainly on math benchmarks; out-of-domain results are supplementary.

Experimental setup

Datasets: s1K-1.1 MATH500 AMC23 OlympiadBench GSM8K LiveCodeBench MMLU ARC

Benchmarks: MATH500 AMC23 OlympiadBench GSM8K LiveCodeBench MMLU ARC

Metrics: accuracy response length accuracy per computation unit (ACU) pass@k

Baselines: Chain-of-Draft Break-the-Chain TokenSkip QwQ-32B w/ s1K-1.1

Builds on: LongLLMLingua TokenSkip s1 Chain-of-Draft Break-the-Chain

Closest papers by meaning

• Think or Not? Exploring Thinking Efficiency in Large Reasoning Models via an Information-Theoretic Lens (NeurIPS 2025 · similarity 0.90)
• Efficient Reasoning with Hidden Thinking (ICML 2026 · similarity 0.90)
• Towards Efficient Large Language Reasoning Models via Extreme-Ratio Chain-of-Thought Compression (ICML 2026 · similarity 0.90)
• Reasoning Path Compression: Compressing Generation Trajectories for Efficient LLM Reasoning (NeurIPS 2025 · similarity 0.90)
• Think Smarter not Harder: Adaptive Reasoning with Inference Aware Optimization (ICML 2025 · similarity 0.89)
• Efficient Reasoning via Constrained Optimization in Latent Space (NeurIPS 2026 · similarity 0.89)