A*-Decoding: Token-Efficient Inference Scaling
Giannis Chatziveroglou · 2025
Read A*-Decoding: Token-Efficient Inference Scaling by Giannis Chatziveroglou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13672.txt.
Introduction
Giannis Chatziveroglou adapts a classic pathfinding algorithm to make language model reasoning cheaper in a 2025 study. Spending more compute at inference time improves hard reasoning, but most methods use a fixed budget bluntly, sampling many chains alike. The A-star search from route planning spends effort where promise is highest, guided by costs paid and estimates ahead.
Framing decoding as structured search lets that guidance rank partial reasoning paths during generation. The goal is the same answer quality for fewer tokens. Token efficiency matters because inference cost, not training, dominates the lifetime bill of a widely used reasoning service.
Catalog record
| CREATOR | Giannis Chatziveroglou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-13672
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A*-Decoding: Token-Efficient Inference Scaling Giannis Chatziveroglou Abstract 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. Figure 1: Top: Results with Llama models. Bottom: Results with Qwen models. Left: Token cost-performance frontier on MATH500. A*-decoding (ours) consistently achieves higher or equal accuracy compared to alternatives with lower token usage. Right: PRM cost-performance frontier on MATH500. A*-decoding optimally allocates PRM inference budget by focusing compute on promising partial trajectories. Points show results for 4–64 sampled generations; A*-decoding uses up to 16 for Llama, and 32 for Qwen. 1 Introduction Large language models (LLMs) have historically achieved improved performance primarily by increasing model size and training data. Empirical scaling laws show predictable loss reductions with increases in model size, dataset size, and training FLOPs [ 12 ] , driving the development of trillion-parameter models [ 18 , 5 , 20 ] . However, training and deploying such models requires massive specialized hardware, introducing significant capital and operational complexity. In response, recent work has shifted toward reallocating training compute to inference-time reasoning [ 1 ] . Chain-of-thought (CoT) prompting [ 28 ] spurred structured approaches like tree-of-thoughts and self-consistency [ 30 , 27 ] , and models like OpenAI’s o1 show how computational effort at inference can boost reasoning [ 19 ] . This shift reframes inference as an active reasoning process, closer to search and planning than to passive next - token prediction, enabling algorithms that strategically allocate compute. Prior work on inference-time strategies has shown that small language models (SLMs) can rival larger models in reasoning accuracy, but such methods often overlook token-level efficiency. Snell et al. [ 24 ] demonstrate that SLMs can outperform significantly larger counterparts when inference-time compute is allocated optimally under fixed FLOPs budgets. While existing research highlights the potential of inference-time strategies to improve predictive accuracy [ 23 , 31 , 11 , 21 , 35 , 7 , 32 ] , they primarily optimize for correctness, often by increasing the number or diversity of samples. In contrast, token efficiency, defined in terms of utility per generated token, has received comparatively limited attention in the literature, despite being a critical dimension of scaling with significant implications for latency and cost, particularly when deploying SLMs in resource-constrained settings. In this work, we focus on inference-time strategies that explicitly optimize the tradeoff between efficiency and performance, aiming to close the gap between small and large models through strategic computation rather than increased scale. To address this gap, we propose A*-decoding. We posit that reframing autoregressive decoding as a state-space traversal guided by the A* search algorithm can deliver similar exact - match accuracy as larger CoT models and inference-time scaling methods, while generating substantially fewer tokens under the same budget. This hypothesis is motivated by the algorithmic design of A* as a best-first, optimal shortest-path algorithm, which enables it to prioritize the most promising partial generations while efficiently pruning costly, less relevant candidates. Grounded in this hypothesis, we design a decoding framework that operationalizes A* search over a dynamically constructed graph of candidate next thoughts. At each generation step, our method samples a fixed number of candidate continuations from the policy, evaluates each using a composite score that combines a process-supervised heuristic with an inferred progress-based cost term, and expands the most promising state based the A* transition model until a complete output sequence is generated. To validate this framework, we conduct experiments on the MATH500 and AIME 2024 benchmarks using a range of SLMs including Llama3 and Qwen3 variants between 1-8B parameters. We evaluate A*-decoding against strong inference-time baselines such as best-of-N, self-consistency, and particle filtering. Our main contributions are: 1. A novel framework for autoregressive generation. We propose A*-decoding, a search-based decoding strategy that reimagines autoregressive inference as a best-first graph traversal, combining a learned heuristic and cost estimate to guide generation toward high-quality outputs with minimal token usage. 2. Improved token efficiency without accuracy loss. We demonstrate that A*-decoding achieves competitive exact-match accuracy compared to established inference-time baselines, including best-of-N, self-consistency, and particle filtering, while generating up to 3x fewer overall tokens and 30% fewer inference passes. 3. Strong empirical results on math reasoning. Through extensive experiments on the MATH500 and AIME 2024, we show that SLMs (1–8B parameters) using A*-decoding can match or exceed the performance of much larger CoT-based models (up to 70B) and thinking models like OpenAI’s o1. 2 Related Work Decoding strategies in language modeling have largely focused on maximizing likelihood during inference. While greedy decoding offers efficiency, its lack of exploration makes it vulnerable to early errors. Sampling-based methods, such as temperature and nucleus sampling, promote diversity by drawing from the full token distribution, though often at the cost of coherence and quality [ 10 , 22 ] . Beam search introduces parallel hypotheses to improve over greedy decoding but frequently converges on high-probability yet suboptimal sequences [ 29 , 4 ] . More recently, self-consistency decoding has improved reliability by aggregating answers across multiple CoT rollouts, treating each as an independent sample [ 27 ] . However, these methods all generate text as flat sequences, lacking the ability to evaluate intermediate reasoning steps thus limiting their capacity to discard faulty paths or reuse promising ones. This motivates more strategic, inference-time approaches that reason over partial trajectories. Process supervision promotes logical correctness by evaluating intermediate reasoning steps, guiding models toward more coherent outputs. Process Reward Models (PRMs) implement this principle through lightweight classifiers trained on step-labeled traces to provide fine-grained feedback. Lightman et al. [ 15 ] introduce a human-in-the-loop approach for creating such data via manual annotation, while recent work explores automated methods using Monte Carlo rollouts and tree search to mine supervision signals [ 16 , 26 , 33 ] . Alternatively, LLM-as-a-judge approaches bypass training by prompting generalist models to assess step correctness directly [ 17 , 2 ] . While PRMs offer task-specific feedback, LLM-as-a-judge methods provide label-free, generalized supervision [ 14 ] . Together, these approaches reflect a shift toward scalable, fine-grained guidance