{"id":"3960e332-26c2-4102-86b3-5e7bd1ee9cea","arxiv_id":"2505.13672","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A*-decoding applies A* search with a PRM heuristic to LLM decoding, improving accuracy per generated token on MATH500 and AIME 2024 compared to best-of-N and particle filtering.","lead":"A new decoding method, A*-decoding, uses A* search guided by a process reward model to select promising reasoning paths during generation, reporting accuracy comparable to larger models at a lower token cost. The work matters because it suggests small language models can narrow the gap to much larger models by spending inference compute more selectively.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Headline efficiency claim is unsupported: Table 1 shows A*-decoding using at most ~30% fewer tokens than one baseline at unmatched accuracy, never 3x, and no PRM-pass counts are reported; budgets are not equivalent (baselines k=64, A* k=16).","rationale":"The paper's central claim is empirical: A*-decoding matches strong inference-scaling baselines while using up to 3x fewer tokens and 30% fewer PRM passes under equivalent compute budgets. That claim, not the A* optimality framing, is what the abstract and title promise. The reader's weakest assumption about the degeneracy of the priority rule in Eqs. 4-5 is a genuine theoretical weakness: along a monotonically decreasing heuristic path f(s') = g(s') + h(s') = h(s0), so the priority queue loses ordering and the search behaves like a PRM-guided, breadth-limited beam rather than A*. Appendix A.2 explicitly admits non-admissible heuristics, so no optimality guarantee survives. However, even if that degeneracy is real, the method could still be a useful heuristic-guided beam search with the reported efficiency properties. The load-bearing question is whether the efficiency result itself is true and fairly measured. Table 1 does not show a 3x token reduction at any reported operating point, no PRM-pass counts are given, and the baselines use k=64 while A* uses k=16, so the budgets are not equivalent. The reader's conditional verdict is therefore appropriate, but the primary reason should be the unverified empirical comparability rather than the theoretical A* framing. A concrete check at matched accuracy with explicit PRM counts would settle whether the advertised efficiency gains exist.","tokens_in":14597,"tokens_out":6773,"duration_ms":64250,"concrete_test":"Re-run the efficiency comparison with a fixed, operational definition of compute budget (e.g., total generated tokens plus PRM/verifier calls), and for each accuracy level on the frontier interpolate the token counts for A*, best-of-N, and particle filtering. Then count PRM calls from the published algorithm (one per expansion) and report the ratio at matched accuracy. If no benchmark/model shows a 3x token reduction and 30% PRM-pass reduction under this equal-budget definition, the abstract's quantitative claims should be revised.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Table 1 is the only systematic comparison, and it does not substantiate the central quantitative claim in the abstract. For Llama-3.2-1B on MATH500, A*-decoding reaches 64.4% with 35,365 tokens, while particle filtering reaches 64.0% with 38,856 tokens: about 9% fewer tokens, not 3x fewer. Best-of-N uses 30,783 tokens at 51.4%, so at comparable budgets A* uses more tokens for higher accuracy. For Qwen3-1.7B on AIME, A* achieves 16.6% with 45,139 tokens while best-of-N achieves 20.0% with 94,086 tokens: the comparison is at different accuracy points, making the 'fewer tokens' claim non-commensurable. No PRM-pass counts appear in the table, although the abstract promises 30% fewer PRM passes. The setup states that baselines are run with k=64 generations and A* with k=16 'optimal' candidates, so the claimed 'equivalent compute budgets' are not actually equal. Section 4.3's 'up to 3x' appears to be derived from interpolating Figure 1, but the figure's operating points, matching procedure, and variance are not specified. Without code, seeds, or error bars, the headline efficiency result is not verifiable from the manuscript.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper introduces A*-decoding, a search-based decoding strategy that casts autoregressive generation as A* search over partial reasoning trajectories, using a process reward model (PRM) as the heuristic h(s)=1-r(s) and a progress-based cost g(s,s')=max(0,h(s)-h(s')). The search is bounded by a candidate count k and a breadth cap bmax. The authors evaluate exact-match accuracy and average generated tokens on MATH500 and AIME 2024 with Llama-3.2-1B/3.1-8B and Qwen3-1.7B/8B, comparing against best-of-N, self-consistency, and particle filtering. They claim up to 3x fewer tokens and 30% fewer PRM passes under equivalent compute budgets, and report that small models can match or exceed much larger CoT models.","tokens_in":14917,"tokens_out":5051,"duration_ms":46426,"significance":"The core idea, using a learned process verifier as a search heuristic to allocate inference compute more selectively, is timely and could be practically valuable if the efficiency claims are correct. The paper evaluates on standard external benchmarks with exact-match scoring, which avoids the circularity of re-predicting fitted constants, and it includes ablations of temperature, PRM choice, and graph breadth. However, the main quantitative claims are not currently supported by the reported experiments: Table 1 does not show a 3x token reduction, no PRM-pass counts are reported, the compared budgets are not matched, and a hyperparameter is tuned on a subset of the test set. The significance as stated is therefore not established, although the underlying direction remains plausible.","major_comments":[{"comment":"The abstract and Section 4.3 claim that A*-decoding uses 'up to 3x fewer tokens' than strong baselines, but Table 1, the only systematic comparison, does not support this. For Llama-3.2-1B on MATH500, A*-decoding uses 35,365 tokens versus 38,856 for particle filtering (about 9% fewer) and more tokens than best-of-N's 30,783; for Qwen3-1.7B on AIME, A* uses 45,139 tokens versus 94,086 for best-of-N but achieves 16.6% accuracy versus 20.0%, so the comparison is at different accuracy points and is not commensurable. The 'up to 3x' figure appears to be derived from interpolating Figure 1, but the operating points, matching procedure, and variance are not specified. Please report per-configuration token counts and PRM-pass counts with error bars and re-derive any efficiency claim directly from those data.","section":"Table 1 and Section 4.3"},{"comment":"The experimental budgets are not equivalent as claimed. Section 4.1 states that all baselines are run with k=64 model generations while A*-decoding uses k=16 'optimal' candidate continuations, and no PRM-pass counts appear anywhere in Table 1 or Section 4.3. Consequently, the abstract's claims of '30% fewer PRM passes' and 'equivalent compute budgets' are unverifiable from the manuscript. Please report the number of PRM queries per method, state the total inference budget in consistent units, and rerun or re-report the efficiency comparisons under matched budgets.","section":"Section 4.1 and Table 1"},{"comment":"The sampling temperature 0.8 is selected using a 100-problem subset of MATH500, and the same temperature is then used for the main MATH500 results in Table 1. Since MATH500 is the evaluation set, tuning on a subset of it is a form of test-set selection that can bias the reported comparison. Please use a validation split disjoint from the reported test set, or show that the main conclusions are insensitive to temperature across seeds and that the selected value does not advantage A*-decoding over baselines.","section":"Section 4.4 and Figure 3"},{"comment":"With the cost function g(s,s')=max(0,h(s)-h(s')), the A* total f(s')=g(s')+h(s') is constant along any path on which h is non-increasing, so selection among such candidates reduces to insertion-order tie-breaking. The algorithm is therefore a PRM-greedy, bounded beam search rather than A* with a meaningful cost-to-go, and Appendix A.2 explicitly permits non-admissible heuristics. Since the paper's framing of 'optimally utilizing' a compute budget relies on the A* transition model, please either provide a cost function that is not defined directly from the heuristic, or present the method as heuristic-guided beam search and adjust the optimality and efficiency claims accordingly.","section":"Section 3.3, Eq. (5)"}],"minor_comments":[{"comment":"There is a typo, 'self-sonsistency' instead of 'self-consistency', and the wording 'up to 3x greater overall efficiency' is inconsistent with the abstract's 'up to 3x fewer tokens'; please align the terminology.","section":"Section 4.3"},{"comment":"The caption says points show results for 4-64 sampled generations and that A*-decoding uses up to 16 for Llama and 32 for Qwen, but it does not define what 'sampled generations' means for A*-decoding or how the PRM cost axis is computed; please clarify.","section":"Figure 1 caption"},{"comment":"No standard errors or confidence intervals are reported for accuracy or token counts; given the modest benchmark sizes and stochastic sampling, please report variance across seeds.","section":"Table 1"},{"comment":"The consistency condition h(s) <= c(s,s')+h(s') is trivially satisfied when c is defined as max(0,h(s)-h(s')), because the cost is constructed from the heuristic; please state explicitly that this is a tautology and explain what, if anything, it guarantees for the search.","section":"Appendix A.2"},{"comment":"Notation is inconsistent between the algorithm (s0) and the text (s_0); please unify.","section":"Algorithm 1"},{"comment":"Reference [1], Beeching et al., lacks a year, venue, and URL; please complete the citation.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The gap between the abstract's headline efficiency claims and the numbers in Table 1 is substantial, and the hyperparameter tuning on a subset of the test set is a concern the editors should keep in mind. If the authors can supply matched-budget comparisons, PRM-pass counts, error bars, and a corrected presentation of the algorithm, the paper could become a plausible contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read: the paper's core empirical finding—that PRM-guided best-first search over partial reasoning paths can be competitive with brute-force sampling on token-accuracy trade-offs for small models—is plausible and worth a look. But the A* framing is mostly cosmetic, and the headline efficiency claims don't survive contact with the paper's own table.\n\nWhat's new: framing decoding as A* search over partial trajectories with an improvement-based cost function is a specific combination I haven't seen exactly before. The experiments span multiple small models on MATH500 and AIME 2024 with strong baselines, and they include ablations on temperature, PRM choice, and breadth. That is a solid base of work.\n\nThe soft spots are real. First, the abstract's 'up to 3x fewer tokens and 30% fewer PRM passes' is not in Table 1. In the table, the best A* token savings versus a comparable-accuracy baseline is about 9% (Llama-1B on MATH500 vs particle filtering), and no PRM pass counts appear anywhere. The '3x' comes from a figure whose operating points and matching procedure are unspecified. Second, the claimed 'equivalent compute budgets' are not actually set up that way: baselines use k=64 candidate generations, A* uses k=16, and the token totals in the table mostly show A* using more tokens than best-of-N at higher accuracy. Third, the cost function g(s,s')=max(0,h(s)-h(s')) is degenerate. When the heuristic improves, the total score f(s') = h(s), so all improved children have identical f-values and the search degenerates to insertion-order tie-breaking. That's PRM-greedy beam expansion, not A* with a meaningful cost-to-go. The paper's own admission of non-admissible heuristics understates this.\n\nThere's also a careless factual inconsistency: the text says Qwen-1.7B with A* surpasses o1 on MATH500, but Table 1 shows 83.0 vs. 88.2. Hyperparameters were tuned on a 100-problem MATH500 subset and then applied to the full MATH500, which is a mild leak. No code, no seeds, no error bars anywhere.\n\nOverall, the practical idea is worth testing by a serious referee, but the paper as written oversells its results. I would send it to peer review with the request that the authors release code and seeds, add variance and properly matched budgets, and either substantiate or soften the 'optimal' and '3x fewer tokens' language. No takeaway from the abstract should be trusted until that is done.","headline":"A useful empirical study of PRM-guided search for test-time scaling, but the A* framing and the headline efficiency numbers are substantially overstated.","tokens_in":15443,"tokens_out":4491,"would_cite":false,"duration_ms":40858,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A*-decoding treats generation as best-first search over partial reasoning paths and claims to match brute-force inference-scaling baselines with up to three times fewer tokens and about 30 percent fewer verifier passes.","keywords":["A*-decoding","inference-time scaling","process reward models","token efficiency","mathematical reasoning","small language models","best-first search","exact match accuracy"],"falsifier":"On a sample of MATH500 problems, record $f(s')$ for every expanded state; if $h$ decreases monotonically along chosen paths, then $g(s,s') = h(s_0) - h(s')$ and $f(s') = h(s_0)$ is constant, so A* selection reduces to insertion-order tie-breaking and a decoder with the $g$ term removed should reproduce the same accuracy and token counts. Equivalently, rerun the main comparison after randomly permuting PRM scores within each depth: if accuracy does not drop, the heuristic signal is not what drives the gains.","tokens_in":14362,"feed_emoji":"🧮","tokens_out":10066,"duration_ms":85033,"temperature":0.7,"pith_summary":"This paper proposes A*-decoding, a decoding strategy that spends a fixed inference budget by treating language-model generation as A* search over partial reasoning paths. At each step the policy samples a small set of candidate continuations, a process-reward model scores each partial trajectory, and the decoder expands the state with the best combined score until a complete answer is produced. The paper reports that on MATH500 and AIME 2024 this reaches the accuracy of best-of-N and particle filtering while generating up to three times fewer tokens and calling the process-reward model about 30 percent less often, and that models of 1-8B parameters match or exceed much larger chain-of-thought models on these benchmarks. The reason to care is that if true, smarter search over partial solutions can substitute for brute-force sampling and for parameter scale in math reasoning.","feed_headline":"A* decoding reaches best-of-N accuracy with 3x fewer tokens","feed_subtitle":"Search-guided decoding lets a 1B model match 70B chain-of-thought accuracy on MATH500.","key_machinery":"The carrying mechanism is the A* selection rule $f(s') = g(s') + h(s')$, with heuristic $h(s) = 1 - r(s)$ built from an external process-reward score and step cost $g(s,s') = \\max(0, h(s)-h(s'))$. A* is a best-first search that always expands the lowest-estimated-total-cost node; here the heuristic tells the decoder how close a partial trajectory looks to a correct solution, and the cost term turns a drop in the heuristic into measurable progress toward the goal. The breadth cap $b_{\\max}$ and candidate count $k$ make the search linear in depth, so the whole mechanism converts a fixed token and verifier budget into focused expansion of promising partial reasoning paths rather than full-length resampling.","core_discovery":"The central claim is that autoregressive decoding can be reframed as a best-first search over partial trajectories, and that doing so is more token-efficient than sampling full answers. Each successor state $s'$ from a sampled continuation gets the score $f(s') = g(s') + h(s')$, where $h(s) = 1 - r(s)$ is the complement of a process-reward score $r(s)$ and the step cost $g(s,s') = \\max(0, h(s)-h(s'))$ counts only positive gains in the heuristic. The lowest-$f$ state is expanded next, and a per-depth breadth cap $b_{\\max}$ bounds the graph to $O(b_{\\max} \\cdot d)$ nodes instead of $O(k^d)$. On MATH500 and AIME 2024 with Llama and Qwen models between 1B and 8B parameters, the paper reports that this reaches the accuracy of best-of-N and particle filtering while using up to three times fewer generated tokens and about 30 percent fewer PRM passes, including a 1B model matching a 70B chain-of-thought model and a 1.7B model reaching o1-class reasoning accuracy.","pith_inferences":["The paper does not isolate what A*'s cost term contributes over a plain PRM-greedy decoder; a head-to-head against greedy depth-limited expansion with the same breadth cap would tell whether the $g$ term is doing work or whether the savings come from the breadth cap and heuristic ranking.","Whenever a cheap process-level reward exists — unit tests for code, execution traces for tool use, protocol checks for planning — the same framework should transfer, and the paper only sketches this possibility rather than testing it.","The reported 1B-versus-70B parity is on exact-match math accuracy; it says nothing about open-ended writing, knowledge grounding, or instruction-following, so the practical claim is narrower than 'small models match large models' in general.","Because the $g$ term collapses to a constant on any path where the PRM score only decreases, the search's behavior in practice may be closer to a PRM-guided beam search than to textbook A*; the effective difference is governed by how noisy and non-monotone the PRM scores are."],"forward_implications":["In math reasoning, a small model can reach the accuracy of a much larger chain-of-thought model by spending more search budget on partial solutions, so inference compute can substitute for parameter scale.","Token efficiency becomes a design axis: the same accuracy as best-of-N can be reached with roughly a third of the generated tokens, lowering latency and serving cost for deployed systems.","PRM passes also drop by about 30 percent, which matters when the verifier is itself a large model and dominates inference cost.","The benefit holds across model families and sizes from 1B to 8B, so the strategy does not depend on one base model's strength."],"supporting_citations":[{"why":"Defines the A* search algorithm and its transition model, which the paper adapts to decoding.","marker":"[8]"},{"why":"Provides the particle-filtering baseline and the PRM scaling analysis that motivates the choice of the Qwen2.5-Math-PRM-7B verifier.","marker":"[21]"},{"why":"Establishes the premise that optimally allocated test-time compute can outperform parameter scaling, the framing the paper builds on.","marker":"[24]"},{"why":"Supports the reward-aggregation choice (final token as the heuristic), which the paper relies on for h(s).","marker":"[33]"},{"why":"Introduces process supervision and step-level PRM labels, the basis for the heuristic signal.","marker":"[15]"},{"why":"Defines self-consistency, one of the baselines A*-decoding is compared against.","marker":"[27]"},{"why":"Provides the open-model test-time scaling setup and temperature findings consistent with the paper's choice of 0.8.","marker":"[1]"}],"fun_headline_variants":["A* decoding matches best-of-N with 3x fewer tokens","Search-guided decoding: 1B model matches 70B accuracy","A* decoding: 3x fewer tokens, same accuracy as brute force","Token-efficient A* search: 1B model rivals 70B","A* inference scaling: 3x token savings, 70B-level reasoning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a decrease in the process-reward score from one partial trajectory to its continuation is an honest measure of progress toward a correct answer; if that score is noisy or biased, the search spends its budget following a false gradient and the claimed efficiency gain collapses.","fun_headline_variants_meta":{"raw":{"variants":["A* decoding matches best-of-N with 3x fewer tokens","Search-guided decoding: 1B model matches 70B accuracy","A* decoding: 3x fewer tokens, same accuracy as brute force","Token-efficient A* search: 1B model rivals 70B","A* inference scaling: 3x token savings, 70B-level reasoning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000302,"raw_usage":{"total_tokens":1794,"prompt_tokens":1054,"completion_tokens":740,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":670,"completion_tokens_details":{"reasoning_tokens":643}},"tokens_in":670,"tokens_out":740,"duration_ms":6604,"temperature":1.0,"reasoning_tokens":643,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:12:10.136929+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a sample of MATH500 problems, record $f(s')$ for every expanded state; if $h$ decreases monotonically along chosen paths, then $g(s,s') = h(s_0) - h(s')$ and $f(s') = h(s_0)$ is constant, so A* selection reduces to insertion-order tie-breaking and a decoder with the $g$ term removed should reproduce the same accuracy and token counts. Equivalently, rerun the main comparison after randomly permuting PRM scores within each depth: if accuracy does not drop, the heuristic signal is not what drives the gains.","supporting_citations":[{"cited_title":"A probabilistic inference approach to inference-time scaling of llms using particle-based monte carlo methods, 2025","cited_arxiv_id":null,"evidence_quote":"Provides the particle-filtering baseline and the PRM scaling analysis that motivates the choice of the Qwen2.5-Math-PRM-7B verifier."},{"cited_title":"Scaling test-time compute with open models","cited_arxiv_id":null,"evidence_quote":"Provides the open-model test-time scaling setup and temperature findings consistent with the paper's choice of 0.8."}],"review_version":1}