Elamur Research⌕
☰
home / papers / 2026 / Confidence-Weighted Token Set Cover for Early Hypothesis Pruning in Self-Consistency

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

Paper · 2026 · Md Arafat Sultan and Ramón Fernandez Astudillo

Summary

Self-consistency (majority voting over many sampled solutions) is strong but costly in tokens. Earlier efficiency methods generate samples in sequential batches, which gives up parallelism and adds latency. This paper keeps every hypothesis decoding in parallel but stops the unpromising ones partway through long chain-of-thought generation. At each step, a retained subset is chosen with a fast greedy weighted set cover. Each partial hypothesis is represented by its set of unique tokens, and its weight comes from the model's own length-normalized confidence. The result favours candidates that are both confident and lexically diverse, and the selection runs in O(N log N).

The authors tested five LLMs from 1.5B to 14B parameters on MATH500 and a merged AIME24/AIME25 set. In most configurations, CWSC matched the accuracy of unpruned self-consistency with fewer tokens, often saving 10–35%. Unlike Adaptive-Consistency, it does so without lengthening the sequential generation chain. This makes early pruning a practical way to cut test-time compute in GPU-parallel serving.

Key points

  • Models and benchmarks: Qwen2.5-Math-Instruct (1.5B, 7B), Granite3.3-Instruct (2B, 8B) and Phi4 (14B) were evaluated with exact match on MATH500 and merged AIME24+AIME25 (60 problems).
  • Sampling setup:
    • Sample budgets were N = 8, 16, 32 and 64.
    • Each problem received 256 samples (temperature 1.0, top-p 0.95, 16 seeds).
    • The dynamic step-size schedule starts at 64–512 tokens, halves after each step and stops at a floor of 8.
  • Comparison with Adaptive-Consistency (AC): AC spends fewer total tokens, but its longest sequential chain can reach several times, up to roughly 22×, that of standard self-consistency. CWSC keeps the sequential length near the baseline.
  • Ablation over 40 settings:
    • Full CWSC beats unweighted set cover in 82.5% of settings.
    • Full CWSC beats confidence-only pruning in 65.0%.
    • Confidence weighting proved the more important component.
  • Effect of lexical diversity: Pruning is heaviest in early steps and levels off after about 6 steps. Qwen and Phi4 are pruned more aggressively than Granite because each of their hypotheses covers more of the group's tokens. A 256-token Phi4 prefix covers 26.5% of the group's unique tokens, compared with 15.2% for Granite3.3-8B.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢IBMArmonk · United States139 works · 70,691 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 1Research subjects and languages the work is about.Efficient models & compression · 242 works

Cite

Cite as Md Arafat Sultan and Ramón Fernandez Astudillo. 2026. Confidence-Weighted Token Set Cover for Early Hypothesis Pruning in Self-Consistency. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.2046

@inproceedings{sultan2026confidence,
  title = {{Confidence-Weighted Token Set Cover for Early Hypothesis Pruning in Self-Consistency}},
  author = {Md Arafat Sultan and Ramón Fernandez Astudillo},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.2046},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.2046}
}

References

16 references, 7 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Marah Abdin, Jyoti Aneja, and 1 others. 2024. Phi-4 Technical Report. Preprint, arXiv:2412.08905.
  2. Pranjal Aggarwal, Aman Madaan, Yiming Yang, and Mausam. 2023. Let’s Sample Step by Step: Adaptive-Consistency for Efficient Reasoning and Coding with LLMs. In EMNLP. find
  3. Ramón Fernandez Astudillo, Md Arafat Sultan, Aashka Trivedi, Yousef El-Kurdi, Tahira Naseem, Radu Florian, and Salim Roukos. 2025. Optimal Policy Minimum Bayesian Risk. Preprint, arXiv:2505.17242. — [arXiv:2505.17242](https://arxiv.org/abs/2505.17242) find
  4. DeepSeek-AI. 2025. DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning. Preprint, arXiv:2501.12948.
  5. Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. 2021. Measuring Mathematical Problem Solving With the MATH Dataset. In NeurIPS Track on Datasets and Benchmarks (Round 2).
  6. Chengsong Huang, Langlin Huang, Jixuan Leng, Jiacheng Liu, and Jiaxin Huang. 2025. Efficient Test-Time Scaling via Self-Calibration. Preprint, arXiv:2503.00031. — [arXiv:2503.00031](https://arxiv.org/abs/2503.00031) find
  7. Gregory Kang Ruey Lau, Wenyang Hu, Liu Diwen, Chen Jizhuo, See-Kiong Ng, and Bryan Kian Hsiang Low. 2024. Dipper: Diversity in Prompts for Producing Large Language Model Ensembles in Reasoning tasks. In NeurIPS Workshop on Foundation Model Interventions. find
  8. Yiwei Li, Peiwen Yuan, Shaoxiong Feng, Boyuan Pan, Xinglin Wang, Bin Sun, Heda Wang, and Kan Li. 2024. Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning. In ICLR. find
  9. Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. 2024. Let’s Verify Step by Step. In ICLR.
  10. Magistral. Preprint, Hanshi Sun, Momin Haider, Ruiqi Zhang, Huitao Yang, Jiahao Qiu, Ming Yin, Mengdi Wang, Peter Bartlett, and Andrea Zanette. 2024. Fast Best-of-N Decoding via Speculative Rejection. In NeurIPS. find
  11. Hugo Touvron, Thibaut Lavril, and 1 others. 2023. LLaMA: Open and Efficient Foundation Language Models. Preprint, arXiv:2302.13971.
  12. Guangya Wan, Yuqi Wu, Jie Chen, and Sheng Li. 2025. Reasoning Aware Self-Consistency: Leveraging Reasoning Paths for Efficient LLM Sampling. In NAACL.
  13. Han Wang, Archiki Prasad, Elias Stengel-Eskin, and Mohit Bansal. 2024. Soft Self-Consistency Improves Language Models Agents. In ACL. find
  14. Tianchun Wang, Zichuan Liu, Yuanzhou Chen, Jonathan Light, Haifeng Chen, Xiang Zhang, and Wei Cheng. 2025a. Diversified Sampling Improves Scaling LLM inference. Preprint, arXiv:2502.11027. — [arXiv:2502.11027](https://arxiv.org/abs/2502.11027) find
  15. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023. Self-Consistency Improves Chain of Thought Reasoning in Language Models. In ICLR.
  16. Yiming Wang, Pei Zhang, Siyuan Huang, Baosong Yang, Zhuosheng Zhang, Fei Huang, and Rui Wang. 2025b. Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decoding. Preprint, arXiv:2503.01422. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sultan-2026-confidence-weighted-token-set-cover/