Optimal Self-Consistency for Efficient Reasoning with Large Language Models

Self-consistency (SC) is a widely-used test-time inference technique for improving performance in chain-of-thought reasoning. It consists of generating multiple responses, or "samples," from a large language model (LLM) and selecting the most frequent answer. This procedure can naturally be viewed as a majority vote or empirical mode estimation. Despite its effectiveness, self-consistency is prohibitively expensive at scale when naively applied to datasets, and it lacks a unified theoretical treatment of sample efficiency and scaling behavior. In this paper, we provide the first comprehensive analysis of SC's scaling behavior and its variants, drawing on mode estimation and voting theory. We derive and empirically validate power law scaling for self-consistency across datasets, and analyze the sample efficiency for fixed-allocation and dynamic-allocation sampling schemes. From these insights, we introduce Blend-ASC, a novel variant of self-consistency that dynamically allocates samples to questions during inference, achieving state-of-the-art sample efficiency. Our approach uses $4.8\times$ fewer samples than vanilla SC on average, outperforming both fixed- and dynamic-allocation SC baselines, thereby demonstrating the superiority of our approach in terms of efficiency. In contrast to existing variants, we note that Blend-ASC is hyperparameter-free and can fit any budget of samples, ensuring it can be easily applied to any self-consistency application.

One approach to increasing LLM performance is to generate many answers per user prompt and aggregate them. Self-Consistency (SC), a popular instance of this idea, samples n responses per question and returns the most frequent answer. While effective, SC is notoriously expensive, multiplying inference costs many times over. Until now, there was also no clear theory explaining how SC accuracy on datasets improves with more answers. This paper draws on ideas from voting theory and statistics to show that Self-Consistency error follows power-law patterns. We explore the theory of several variants of SC and prove how to spend limited budgets more efficiently by investing more attempts on difficult questions. From these insights, we introduce Blend-ASC, a method that determines on the fly how much each question needs. Unlike other variants of SC, our method requires no tuning and fits any user budget.