Make Every Penny Count: Difficulty-Adaptive Self-Consistency for Cost-Efficient Reasoning

1 Introduction

• ASC and ESC still pre-sample every problem, wasting resources on easy questions, while repeated resampling can add input costs that outweigh output savings.The passage reports that only 3.8% of GPT-4 questions benefit from SC compared with CoT.Source: §1 · p. 2
• DSC ranks batch-query difficulty, partitions problems into easy and hard groups, and pre-allocates sample sizes for hard problems to reduce inference costs.Easy problems receive one CoT sample; predicted sample sizes for hard problems aim to reduce re-sampling and input costs.Source: §1 · pp. 2–3
• DSC outperforms ASC and ESC on cost across six benchmarks while attaining comparable performance.Experiments cover arithmetic, commonsense, and symbolic reasoning tasks.Source: §1 · p. 2
• The paper presents DSC as the first method to dynamically allocate sampling resources based on query difficulty.Source: §1 · p. 3

2 Methodology

• DSC’s workflow consists of Difficulty Ranking, Problem Partition, and Sample Size Pre-Allocation.The three steps allocate computational resources according to problem difficulty.Source: §2 · p. 3

2.1 Difficulty Ranking

• Repeatedly ranking questions within random batches and averaging their ranks produces a difficulty ordering for the full problem set.Batches are used because LLM context windows are limited and long contexts can create a lost-in-the-middle issue.Source: §2.1 · pp. 3–4

2.2 Problem Partition

• After pre-sampling problems from hard to easy, DSC marks the remaining problems as easy when the latest k entropy values are zero; each receives one CoT sample.The method stops pre-sampling when the latest k items have zero entropy.Source: §2.2 · p. 4

2.3 Sample Size Pre-Allocation

• For hard problems, DSC predicts an initial sample size from the average total samples used for the m nearest easier problems, then expands sampling until its stopping criterion is met or the maximum is reached.Using easier rather than harder neighbors avoids over-allocation when a prediction exceeds the required sample size.Source: §2.3 · p. 4

3.1.1 Benchmarks

• Evaluation covers arithmetic, commonsense, and symbolic reasoning benchmarks; relatively simple arithmetic datasets MultiArith, SVAMP, AddSub, and ASDiv are excluded.The benchmarks are MATH, GSM8K, CommonsenseQA, StrategyQA, Last Letter Concatenation, and Coin Flip.Source: §3.1.1 · p. 5

3.1.2 Baselines

• The baselines are standard majority-vote SC, sequential stopping ASC, and window-based early-stopping ESC.Both ASC and ESC are reproduced according to their original implementations.Source: §3.1.2 · p. 5

3.1.3 Implementation details

• Experiments use GPT-4 and GPT-3.5-Turbo in few-shot settings without training or fine-tuning, average 100 repetitions, and include all DSC steps in reported cost.Unless otherwise specified, the default maximum sample size is 40.Source: §3.1.3 · p. 5

3.2 Main Results

• DSC cuts cost versus SC by 65.29% on GPT-4 and 56.04% on GPT-3.5-Turbo, and versus ESC by 24.81% and 21.86%, with barely affected performance.Table 2 reports accuracy and cost across six reasoning benchmarks.Source: §3.2 · p. 5, Table 2 · p. 6
• Across max sampling sizes, ESC saves cost while maintaining performance, but ASC and ESC can cost more than SC when output-token savings are limited.DSC also shows potential effectiveness on Mistral-7B-Instruct-v0.3 using GSM8K.Source: §3.2 · pp. 5–6, Table 3 · p. 6, Table 4 · p. 6

3.3.1 Difficulty Ranking

• GPT-4 difficulty rankings align highly with human labels on MATH, while GPT-3.5-Turbo shows moderate consistency and both rank Geometry weakly.Difficulty-ranking input cost per problem is below the average single few-shot reasoning input cost.Source: §3.3.1 · pp. 6–7, Table 7 · p. 7

3.3.2 Problem Partition

• Removing Problem Partition increases input and output tokens across six datasets; on GSM8K, accuracy rises with judge window k up to 32 while cost also rises.The easy partition shrinks as k increases.Source: §3.3.2 · pp. 7–8, Figure 4 · p. 8

3.3.3 Sample Size Pre-Allocation

• Removing Sample Size Pre-Allocation raises input tokens except for GPT-4 on Coinflip, while output tokens rise slightly; moderate prediction windows of 8–32 are recommended.As prediction-window size increases, cost first falls rapidly and then rises slightly.Source: §3.3.3 · p. 8, Figure 5 · p. 8

Chain-of-thought Reasoning

• Chain-of-thought methods solve complex problems through stepwise reasoning, explicit subproblem splitting, or iterative answer generation with prior answers as context.The cited examples include few-shot CoT, least-to-most prompting, and iterative answer generation.Source: §4 · p. 8

Self-Consistency

• Self-consistency improves reasoning by sampling alternative reasoning paths, while adaptive stopping and sequential windows aim to reduce its sampling cost.ASC stops when a confidence-based criterion is met; ESC stops when answers in a window agree.Source: §4 · pp. 8–9

Difficulty-adaptive Test-Time Scaling

• Difficulty-adaptive test-time scaling allocates compute by query difficulty, including coarse or fine-grained refinement and extra computation for queries expected to benefit.Other approaches use self-evaluation or lightweight difficulty estimators.Source: §4 · p. 9

5 Conclusion

• DSC allocates computational resources according to problem difficulty to address redundant sampling on simple questions and repeated-sampling limitations of existing cost-efficient methods.The method leverages difficulty information from the given problem set.Source: §5 · p. 9
• DSC significantly outperforms ASC and ESC on cost across six popular benchmarks while attaining comparable accuracy.The evaluation covers arithmetic, commonsense, and symbolic reasoning tasks.Source: §5 · p. 9
• The experiments confirm the effectiveness of DSC’s three-step algorithms.The steps are Difficulty Ranking, Problem Partition, and Sample Size Pre-Allocation.Source: §5 · p. 9

Limitations

• Difficulty ranking declines on mixed-type problems, which may challenge DSC in real-time reasoning scenarios involving such problems.The authors suggest further problem-type classification or optimizing the ranking algorithm could improve applicability.Source: Limitations · p. 9
• Because DSC needs test-set awareness to rank question difficulty, it may be restricted when a user is permitted only one input at a time.The authors identify server-side batches of queries and one-time inference over a user’s batch as application scenarios.Source: Limitations · p. 9

Ethics Statement

• All datasets used in the study were publicly available, and no annotators were employed for data collection.Source: Ethics Statement · p. 9
• The authors report that the datasets contained no harmful content and were consistent with their intended research use.Source: Ethics Statement · p. 9
• The study cites the datasets and relevant works it used.Source: Ethics Statement · p. 9

• The task is to rank the given questions from easiest to hardest by difficulty level.Source: §A.1 · p. 12
• The response should list the corresponding question numbers, separated by commas.Source: §A.1 · p. 12
• The prompt instructs the model not to provide an explanation.Source: §A.1 · p. 12

• On 5,000 MATH test questions with GPT-4, DSC mitigates resampling time by pre-allocating sample sizes, whereas ASC and ESC require significantly more time than SC.For DSC, ranking time comes from step 1 and sampling time from steps 2 and 3.Source: §A.2 · p. 12

A.3 Comparison with ESC under Different Window Size

• DSC consistently surpasses ESC by a large margin; ESC accuracy holds at window sizes ≥5 as cost rises, but drops significantly below 5.Source: §A.3 · p. 12, Table 9 · p. 12

A.4 Performance of Difficulty Ranking under Mixing Types of Questions

• Mixing question types decreases Difficulty Ranking performance compared with ranking seven MATH subsets separately.The authors suggest mixed types challenge the LLM to apply consistent assessment standards.Source: §A.4 · p. 12, Table 10 · p. 13

A.5 Hyperparameter Experiment of Difficulty Ranking

• Difficulty Ranking performance declines with batch sizes ≥16, and ranking approximately converges by round 5 for GPT-3.5-Turbo and GPT-4.The authors select 5 iterations and batch size 8 as defaults.Source: §A.5 · p. 12, Figure 6 · p. 13

A.6 Necessity of Few-Shot Setting in DSC

• Removing demonstrations significantly lowers SC accuracy, and reducing demonstrations lowers performance regardless of question difficulty.The experiment compares zero-shot and few-shot SC settings on MATH500 with GPT-3.5-Turbo.Source: §A.6 · p. 13, Table 11 · p. 13

A.7 Comparison of DSC with Self-Correction and Verifier-Based Methods

• DSC’s efficiency focus is framed as complementary to self-correction and verifier methods, with difficulty-based resource allocation potentially adaptable to their iterations or verification.Source: §A.7 · pp. 13–14

A.8 Background of ESC and ASC

• ESC samples fixed-size windows and stops when a window’s answers match or the maximum is reached; ASC samples individually until its Dirichlet stopping criterion is met.ASC (Aggarwal et al., 2023) compares the probabilities of the two most frequent answers against a threshold.Source: §A.8 · p. 14

A.9 Application Scenarios of DSC

• DSC’s application scenarios include concurrent server requests and batch inference; the authors note that it may be constrained for users limited to one input at a time.Source: §A.9 · p. 14
• The authors describe inference on large volumes of LLM samples as computationally and financially costly in industrial and real-world applications.They cite Cheng et al. (2023), Lin et al. (2024), Son et al. (2024), Liu et al. (2024a), and Cong et al. (2025).Source: §A.9 · p. 14