# A*-Decoding: Token-Efficient Inference Scaling

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

## Key facts

- Cited by 4 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 12 of its 23 references that are in the map.
- First posted on arXiv 19 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, 12 of 12)

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [The Lessons of Developing Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2501.07301/) (2025)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [The Effect of Sampling Temperature on Problem Solving in Large Language Models](https://mlsanity.com/paper/2402.05201/) (2024)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [Probabilistic Inference in Language Models via Twisted Sequential Monte Carlo](https://mlsanity.com/paper/2404.17546/) (2024)
- [KCTS: Knowledge-Constrained Tree Search Decoding with Token-Level Hallucination Detection](https://mlsanity.com/paper/2310.09044/) (2023)

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

- [Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference](https://mlsanity.com/paper/2603.07887/) (2026)
- [Test-time Scaling of LLMs: A Survey from A Subproblem Structure Perspective](https://mlsanity.com/paper/2511.14772/) (2025)
- [LatticeBridge: Rare-Event Sequential Inference for Faithful Structured Sequence Synthesis](https://mlsanity.com/paper/2606.11203/) (2026)
- [Improving reasoning at inference time via uncertainty minimisation](https://mlsanity.com/paper/2603.07159/) (2026)

## Abstract (arXiv)

Inference-time scaling has emerged as a powerful alternative to parameter scaling for improving language model performance on complex reasoning tasks. While existing methods have shown strong performance gains under fixed compute budgets, there has been little focus on optimally utilizing that budget during inference. In this work, we introduce A*-decoding, a search-based inference-time strategy that builds on the A* search algorithm to optimally utilize a fixed compute budget by prioritizing high-quality reasoning paths during generation. We frame language model decoding as a structured search in a state space of partial solutions, applying the A* transition model to identify promising continuations guided by an external process supervision signal. In our experiments, A*-decoding reaches the performance levels of strong inference scaling baselines like best-of-N and particle filtering while using up to 3x fewer tokens and 30% fewer PRM passes under equivalent compute budgets. On the MATH500 and AIME 2024 benchmarks, A*-decoding enables Llama-3.2-1B-Instruct to match the performance of the 70x larger Llama-3.1-70B-Instruct, and allows Qwen3-1.7B to reach o1-like reasoning accuracy. These results highlight the power of structured search in decoding, offering an alternative to brute-force sampling or scale-driven gains. Our work demonstrates how thoughtful inference-time strategies can enhance reasoning in SLMs, pointing toward future advances in more efficient and scalable language model deployment.