Self-consistency is the workhorse trick for chain-of-thought reasoning: sample 32 complete trajectories, take the majority answer. It works, and it is brutally expensive — every extra candidate answer means generating an entire reasoning chain from scratch, so token cost grows with both the sample count and the trajectory length. Existing efficient variants (Adaptive Consistency, Early-Stopping SC) attack the number of trajectories, never their length.
A new paper from North Carolina State attacks the length directly. StepBack takes a small set of draft trajectories, localises the likely first error position with lightweight signals, keeps the prefix that is still valid, and re-samples only the erroneous step and everything after it — then majority-votes with the same 32-candidate budget as before.
Why It Works
Failed reasoning is not worthless. Most wrong trajectories are right for the first several steps and then go wrong somewhere in the middle. Self-consistency throws all of that away; StepBack salvages it. The signals are cheap: either a step-level negative log-likelihood increase (NLL-signal) or a process reward model score drop (PRM-signal).
Across seven benchmarks (GSM8K, MATH500, AMC2023, AIME24, OlympiadBench, HotpotQA, 2WikiMultiHopQA) and three backbones (Qwen-2.5-3B/7B-Instruct, Llama-3.2-3B-Instruct) over 4,166 questions, PRM-signal beats SC@32 on average by +0.36, +0.17 and +0.82 points while generating 21.07%, 18.66% and 22.80% fewer tokens. The NLL signal saves even more — 27.7%, 27.2% and 33.3% on average — while staying within 0.2 points of SC@32 on the two 3B models.
The best single case: 41.26% fewer tokens on MATH500 with Qwen-7B, and +2.00 points of accuracy. Across all 21 model–dataset pairs, tokens dropped in every one (7.66–41.26%), accuracy improved in 14, tied in 1, and was worse in 6.
The Overhead Is Real But Small
Localisation is not free: scoring the drafts consumes 6.98% to 10.93% of wall-clock time depending on model and signal — less than what the token savings return. Accuracy per 1,000 generated tokens on Llama-3B climbs from 1.392 for SC@32 to 1.769 (PRM) and 1.978 (NLL).
An oracle experiment, using LLM-verified true first-error positions, shows the ceiling: on GSM8K, resampling from annotated error points reaches 92.27% at 42.7% fewer tokens, versus 91.21% for SC@32. The gap between oracle and practical signals is where the next round of work sits.
Thresholds (0.1 for NLL, 0.05 for PRM) are shared across all datasets and models with no per-dataset tuning, and held-out calibration shows every threshold in a wide grid matches or exceeds SC@32 accuracy while saving 20–44% of tokens. StepBack also composes with adaptive methods like Adaptive Consistency, pushing inference-time efficiency further.
The takeaway is unglamorous but useful: test-time compute should be spent on the part of the reasoning that is wrong, not on re-rolling chains that were already fine.
Paper: arXiv:2611.08403