- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes Path-Consistency, a training-free test-time scaling framework that reduces the token generation cost of Self-Consistency by progressively sharing and extending a validated reasoning prefix across sequential sampling windows. The key observation is that independently sampling full trajectories repeatedly generates similar early reasoning steps, which can be amortized through controlled prefix reuse. Specifically, Path-Consistency combines an incomplete-Beta answer agreement gate to trigger prefix extension, a local confidence selection rule that ranks candidate prefixes by their minimum sliding-window token log-probability, and a trial-and-recovery mechanism that rolls back prefixes upon consecutive agreement failures. The authors also provide a theoretical decomposition of voting accuracy and an error bound under conditional-margin assumptions. Experiments across three models and five reasoning benchmarks show that Path-Consistency reduces generated tokens by 25.8% to 42.0% while largely preserving voting accuracy, and achieves an additional 20% token reduction when combined with early-stopping methods.
Critical strengths
-
The paper identifies substantial early-step redundancy across independently sampled reasoning trajectories and proposes a training-free progressive prefix reuse mechanism with rollback protection. By combining an answer agreement gate, local sliding-window confidence selection, and a trial-and-recovery controller, the method amortizes early reasoning computation while preventing the irreversible lock-in of misleading prefixes.
-
The proposed approach achieves consistent token reductions on long-chain reasoning models and composes effectively with existing early-stopping techniques. Across three model scales and five benchmarks, Path-Consistency reduces generated tokens by 25.8% to 42.0% with minimal impact on majority-voting accuracy, and provides an additional 20% token saving when integrated with early-stopping methods.
Critical weaknesses
1.The core propose-trial-rollback mechanism closely resembles existing Tree-of-Thoughts and Monte Carlo Tree Search paradigms, yet the paper lacks both conceptual discussion and empirical comparisons against tree-search baselines. Extending a shared high-confidence prefix, evaluating it via multi-path rollouts, and backtracking upon poor outcomes is structurally equivalent to a single-branch depth-first tree search, especially in the sentence-level variant presented in the appendix. However, the authors neither cite foundational Tree-of-Thoughts literature nor compare their method against step-level beam search or MCTS under matched token budgets.
- Partitioning a parallel sampling budget into sequential windows reduces generation concurrency and may degrade end-to-end latency in realistic serving environments. While standard Self-Consistency can generate all 32 trajectories in a single parallel batch, Path-Consistency enforces 8 sequential rounds of 4 trajectories where each window must wait for the previous one to finish before updating the prefix. The evaluation only reports single-GPU timing under small batch constraints and does not analyze how this serialization bottleneck affects wall-clock latency and hardware utilization on high-capacity GPUs where 32 trajectories can be decoded concurrently without throughput saturation.
Questions for authors
How does Path-Consistency conceptually and empirically compare against Tree-of-Thoughts, step-level beam search, or rollout-based MCTS methods under an equal token or compute budget? [1][2]
[1] Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models.
[2] Tree of Thoughts: Deliberate Problem Solving with Large Language Models.
2 comments
Thank you for the response and the additional experiments.
However, my two main concerns remain largely unresolved. First, regarding W1 and Q1, the added tree-search comparison is not well matched in actual compute. Both ToT-BFS and step-level beam search use less than half of PC's actual tokens, and the self-evaluation adapters with an 8B model are much weaker than standard PRM-guided search methods such as REBASE. Thus, the conceptual novelty over restricted prefix tree search and the empirical advantage under equal realized compute remain unconvincing.
Second, regarding W2, the new A40 serving results directly confirm my concern about serialization latency. Even with 40.9% fewer tokens, isolated-request latency becomes 1.79× slower than SC, and the interleaved serving schedule increases average per-question latency from 397.6 s to 1,925 s while disabling the proposed local confidence selection. This shows that the method trades substantial per-request latency for batch throughput rather than providing general inference acceleration.
Given these remaining limitations, I will maintain my rating of 2.
Response to Reviewer zwLH
W1. Relationship to tree search
Thank you for highlighting the connection to Tree of Thoughts and rollout-based search. PC shares proposal, evaluation, and recovery ideas with search and can be interpreted as a restricted prefix-search process. The ToT and Inference Scaling Laws works identified in the review provide the relevant search context.
PC organizes these operations around multi-trajectory voting. Each window uses one committed shared prefix; continuation agreement determines whether an extension is retained or rolled back. All valid answers, including those from unsuccessful trial windows, enter the final majority vote. PC does not maintain a competing frontier or use visit-count-based selection. The search adapters evaluated below maintain explicit candidate states and select a solution using path likelihood or self-evaluation rewards. This locates the contribution in controlled prefix reuse for voting, rather than in proposal or rollback alone.
W2. Sequential windows and serving concurrency
We measured Qwen3-30B-A3B, thinking on, BF16, on two A40s with TP=2 using MATH-500. SC keeps all 32 trajectories of a question resident without OOM. PC uses the same 32-sequence capacity by interleaving up to eight independent questions, four trajectories each; its within-question window dependencies are preserved.
The 41.3% generation reduction yields 1.64x question throughput with an accuracy difference of 0.20 percentage points. This serving run uses logprobs=0 and length/source-ID fallback selection; it is distinct from the main-table BLC-ranking configuration. Both arms enable prefix caching, and PC generates its own roots.
SC timing sums decoding-loop wall times (194,837.5 s), excluding loading, prompt construction, and inter-question overhead; PC uses engine-ready-to-completion makespan (118,838.7 s), including scheduling. These scopes are explicitly reported. Mean per-question timed duration is 397.6 s for SC and 1,925 s for interleaved PC. In a separate 32-question isolated schedule, PC takes 1.79x SC's wall time despite 40.9% token savings. The measured benefit is workload throughput when independent requests fill decoding capacity; it does not imply lower isolated-request latency.
Q1. Empirical comparison with ToT, beam search, and MCTS
We completed a comparison on all 1,319 GSM8K test questions with Llama-3.1-8B-Instruct. For each question, the search methods receive a generation-token cap equal to PC's measured usage. Proposed and discarded candidates, evaluator outputs, rollouts, and final completions are all charged.
PC has the highest observed accuracy among these configurations, while the search adapters use fewer actual tokens. These are accuracy-cost operating points under equal per-question generation caps; early termination means actual consumption differs. We report both quantities rather than interpret the comparison as equal-realized-token or equal-FLOP dominance.
ToT uses breadth-first expansion with same-model evaluation; beam ranks paths by average cumulative token log-probability; MCTS uses UCT, rollouts, and same-model rewards. The MCTS adapter is not a reproduction of the cited PRM-based system. Sampling uses seed 0, T=0.6, top-p=0.9, and a 2,048-token path limit; reference answers enter alignment and final grading, not search rewards. ToT/beam's 7/6 answer-parsing failures remain incorrect; ToT/MCTS's 49/6 invalid evaluations receive zero reward. All questions are retained. This comparison complements W1 by measuring the outcomes of allocating a bounded generation allowance to prefix-sharing voting or explicit search.