# Confidence-Weighted Token Set Cover for Early Hypothesis Pruning in Self-Consistency

arXiv: https://arxiv.org/abs/2508.03979 · HTML: https://mlsanity.com/paper/2508.03979/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 9 of its 18 references that are in the map.
- First posted on arXiv 6 Aug 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 9 of 9)

- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5-Math Technical Report: Toward Mathematical Expert Model via Self-Improvement](https://mlsanity.com/paper/2409.12122/) (2024)
- [Phi-4 Technical Report](https://mlsanity.com/paper/2412.08905/) (2024)
- [Efficient Test-Time Scaling via Self-Calibration](https://mlsanity.com/paper/2503.00031/) (2025)
- [Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decoding](https://mlsanity.com/paper/2503.01422/) (2025)
- [Magistral](https://mlsanity.com/paper/2506.10910/) (2025)
- [On the Effect of Sampling Diversity in Scaling LLM Inference](https://mlsanity.com/paper/2502.11027/) (2025)
- [Optimal Policy Minimum Bayesian Risk](https://mlsanity.com/paper/2505.17242/) (2025)

## Built on by (most cited first, 2 of 2)

- [A Survey on Parallel Reasoning](https://mlsanity.com/paper/2510.12164/) (2025)
- [Frustratingly Easy Majority Voting Using Length Conditioning](https://mlsanity.com/paper/2610.19890/) (2026)

## Abstract (arXiv)

Despite its simplicity and efficacy, the high token expenditure of self-consistency can limit its practical utility. Here we investigate if self-consistency can be made more token-efficient for long chain-of-thought reasoning tasks, while preserving its parallelism, through early hypothesis pruning. Concretely, we generate all solutions in parallel, but periodically prune intermediate hypotheses that are deemed unnecessary based on two lightweight indicators: (a) the model's own confidence in individual hypotheses, and (b) lexical coverage of all current hypotheses by candidate subsets that are under consideration for continued retention. We design a fast weighted set cover algorithm that utilizes the two indicators; our evaluation of five LLMs on three math benchmarks shows that this method can improve token efficiency for all models, by 10-35% in many cases.