S *: Test Time Scaling for Code Generation (2025)

Abstract: Increasing test-time compute for LLMs shows promise across domains but remains underexplored in code generation, despite extensive study in math. In this paper, we propose S*, the first hybrid test-time scaling framework that substantially improves the coverage and selection accuracy of generated code. S* augments the existing parallel scaling approach with sequential scaling to further increase the performance. It further leverages a novel selection mechanism that adaptively generates distinguishing inputs for pairwise comparison, combined with execution-grounded information to robustly identify correct solutions.We evaluate S* across 12 Large Language Models and Large Reasoning Models and show that: (1) S* consistently improves performance across model families and sizes, enabling a 3B model to outperform GPT-4o-mini; (2) S* enables non-reasoning models to surpass reasoning models—GPT-4o-mini with S* outperforms o1-preview by 3.7% on LiveCodeBench; (3) S* further boosts state-of-the-art reasoning models—DeepSeek-R1-Distill-Qwen-32B with S* achieves 85.7% on LiveCodeBench, approaching o1 (high) at 88.5%. Codes, model generations and intermediate experiments results are available under Codes, model generations and intermediate ex-periments results are available under https://github.com/NovaSky-AI/SkyThought.

## introduction increasing test-time compute has emerged as a powerful approach for improving the performance of large language models (llms) across diverse tasks @xcite @xcite @xcite @xcite . in particular, test-time scaling has been extensively explored in mathematical reasoning, where parallel sampling increases solution coverage, sequential refinement improves figure 1 : performance improvement with s * in live-codebench (v2) @xcite . s * consistently improves models across different sizes, allowing nonreasoning models to surpass reasoning models and open models to be competitive with o1 (high reasoning effort). "qwen-coder" denotes "qwen2.5-coder-instruct," @xcite and "r1-distill" denotes "deepseek-r1-distill-qwen." @xcite . despite these advancements in the math domain, the potential of test-time scaling for code generation-a domain with both fundamental importance and widespread practical applicationsremains under-explored. code generation introduces unique challenges compared to math reasoning. correctness in math can often be verified through rule-based string matching with reference answers @xcite , whereas validating code requires executing a large set of test cases to accurately check functional correctness @xcite . this dependence on execution increases the complexity of test-time scaling and complicates the design of reward models @xcite . however, code generation also offers a distinct advantage: the ability to execute in this paper, we propose s * , the first hybrid test-time scaling framework for code generation, which substantially improves both coverage 1 and selection accuracy. the framework operates in two key stages (fig. 2 ): (1) solution generation, which aimes to generate at least one correct solution, and (2) solution selection, which aimes to select a correct solution from generated ones. first, in the generation stage, s * augments parallel sampling @xcite , which samples multiple solutions independently, with sequential scaling via iterative debugging. each generated sample is executed on public test cases to obtain outputs and/or error messages, which are fed back into the model to iteratively refine the code. second, in the selection stage, existing methods often rely on generating test inputs indiscriminately, which can fail to effectively differentiate between candidate solutions @xcite . to overcome this limitation, s * introduces adaptive input synthesis: for each pair of samples, an llm is prompted to generate distinguishing test inputs. these inputs are executed, where the outputs are further provided to ground the llm to select the best sample. this adaptive, execution-grounded approach ensures robust identification of correct solutions ( §5.4). s * is a general approach that outperforms zeroshot generation and existing test-time scaling meth1 the fraction of problems that are solved by any generated sample @xcite ). ods. we evaluate s * on 12 models, spanning a wide range of sizes, both open and closed, instruction-based and reasoning models. s * consistently enhances performance across these diverse settings. notably, s * (1) enables small models to surpass larger models within the same family: qwen2.5-7b-instruct + s * outperforms qwen2.5-32b-instruct on livecodebench by 10.7%; (2) enables instruction-based models to outperform reasoning models: gpt-4o-mini + s * surpasses o1-preview by 3.7%; and (3) enables open reasoning models to achieve performance competitive with state-of-the-art closed models: deepseek-r1-distill-qwen-32b + s * achieves 85.7% on live-codebench, approaching the state-of-the-art performance of o1-high at 88.7%. fig. 3 provides an overview of the performance improvements enabled by our techniques. in summary, our contributions are: 1. we present the first hybrid test-time scaling framework for code generation, combining the strengths of parallel and sequential scaling to improve the overall effectiveness of test-time scaling in code generation. 2. we introduce adaptive input synthesis, that employs llms to generate test cases capable of distinguishing between code samples to ground sample selections. 3. we conduct extensive evaluations on live-codebench and codecontests, demonstrating that s * consistently improves performance across diverse model families and sizes. 4. we released all software artifacts, model gen-82.8 66.2 63.2 64.6 51.5 44.8 20 30 40 50 60 70 80 90 + s* selection + s* generation r1-distill-14b +s* selection + s* generation qwen-coder-14b o1-preview o1-high +6.7 +13.1 +3.0 +16.6 o1-mini figure 3: ablation of s * performance benefits: qwen2.5-coder-14b-instruct (denoted as qwen-coder-14b) (hui et al., 2024) with s * can surpass o1-preview without s * . deepseek-r1-distill-qwen-14b (denoted as r1-distill-14b) (guo et al., 2025) with s * outperforms o1-mini without s * . +s* generation denotes the setting where we perform parallel sampling and iterative debugging, where the additional +s* selection denotes to additionally apply the selection method (i.e., the full s* method). the accuracy is from livecodebench v2. erations, and intermediate results to support and accelerate future research in this area. ## related work test time scaling for llms. existing approaches to increase test-time compute can be broadly categorized into two paradigms: parallel scaling and sequential scaling @xcite . parallel scaling (also known as repeated sampling) involves generating multiple solutions simultaneously and selecting the best one, a strategy commonly known as best-of-n. coverage-the fraction of problems solved by any of these n samples-continues to improve as n increases @xcite , even at the scale of 10 4 to 10 6 @xcite . however, common selection strategies, such as (weighted) majority voting @xcite and reward model scoring @xcite @xcite @xcite , often struggle to select the best sample in parallel scaling @xcite @xcite . we propose a novel method that improves selection for coding tasks. sequential scaling, on the other hand, encourages the model to refine its reasoning over multiple steps. this includes methods like chain-ofthought (cot) prompting @xcite , and iterative rethinking and revision @xcite @xcite @xcite @xcite @xcite . noticeably, openai o1, deepseek r1, qwen qwq, and kimi employ incontext long cot with revision and backtracking to find the best solution @xcite @xcite . in this paper, we leverage iterative debugging from test execution feedback for sequential scaling code generation performance @xcite . test time scaling for code generation. chen et al. (2022); huang et al. (2023); jiao et al. (2024) use models to generate code samples and test cases, selecting the final sample in a self-consistency manner @xcite . however, these approaches often suffer from model hallucination, where the model fails to accurately predict the output of a test input @xcite @xcite . alphacode explores large-scale parallel sampling with a trained model to generate test cases for filtering and selection @xcite . alphacodium uses a series of selfrevision on both public demonstration and modelgenerated tests to improve solutions @xcite . @xcite searches over various inference techniques and finds that parallel sampling with model-generated tests works well for codecontests problems @xcite . unlike methods relying solely on parallel sampling or sequential scaling, we use a hybrid approach that combines their advantages. hybrid test-time scaling. many works in the math domain study hybrid approaches that combine parallel and sequential scaling, often leveraging reward-model-guided tree search algorithms, such as monte-carlo tree search (mcts), to effectively navigate the solution space @xcite @xcite @xcite . s1 @xcite primarily focuses on sequential scaling but observes diminishing returns and thus incorporates parallel-based approaches like majority voting and tree search to further enhance performance. in contrast, our work applies hybrid scaling to code generation tasks without relying on tree search methods, as developing a general and effective reward model for the code generation domain remains challenging @xcite . instead, s * augments parallel scaling with sequential scaling via execution-grounded iterative debugging to improve coverage and introduces adaptive input synthesis to enhance selection accuracy. @xcite generates parallel samples and revises samples, but it focuses on a different domain (soft-ware engineering @xcite ). we adopt the standard setup widely used in existing coding benchmarks @xcite @xcite @xcite . each coding problem p consists of a natural language description and a set of public and private test cases, each represented as input-output pairs. private tests evaluate the correctness of x but remain inaccessible to m during code generation. a solution is considered correct if it passes all private tests. in contrast, public tests are provided to clarify the problem's intent and are typically included in the prompt. public tests are usually far fewer than private tests; for instance, in codecontests @xcite , there are, on average, 2.0 public tests and 202.1 private tests per problem. this contrasts with mathematical reasoning tasks, where evaluation typically relies on exact string matching of the final solution without additional test information @xcite . ## evaluation in this section, we evaluate s * across a diverse set of instruction-based and reasoning models, various model families, sizes, and access types (open and closed), as well as multiple benchmarks @xcite . our key findings demonstrate the generality and effectiveness of s * : ## ablation studies we conduct further ablation studies to analyze the key components of s * on livecodebench v4: parallel scaling we analyze the impact of different hyper-parameter choices, such as the temperature setting and the number of samples, on parallel sampling performance ( §5.1), and incorporating incontext example retrieval into the parallel sampling process ( §5.2). we find that moderate temperatures improve performance, and adding icl example can potential further improve performance. sequential scaling we explore variations of the iterative debugging process, e.g. with modelgenerated test cases ( §5.3). we find that iteratively debugging from test execution feedback improve performance, even for reasoning models. we find that simply appending execution results from public tests for every iteration works the best. selection policy we assess the performance of different selection policies, comparing our adaptive input synthesis approach with alternative selection strategies ( §5.4). we find that adaptive input synthesis selection is consistently more reliable than the generated tests and the llm judge method. we examine the impact of two key factors in parallel sampling: temperature and the number of parallel samples. understanding their influence is essential for optimizing test-time scaling strategies. moderate temperatures improve performance, but high temperatures degrade it. fig. 4 (left) shows that moderate temperatures (0.2-0.7) enhance performance by balancing exploration and sample diversity. however, beyond 0.7, performance plateaus or declines, likely due to excessive randomness introducing noise. qwen2.5-coder-7b-instruct exhibit performance regression at higher temperatures, emphasizing the trade-off between diversity and solution consistency. repeated sampling improves performance, even for reasoning models. as shown in fig. 4 (right), increasing the number of parallel samples significantly improves performance across all models. notably, qwen2.5-coder-7b-instruct, the weakest performer at @xmath0, shows the largest gain, exceeding 35% at @xmath1. similarly, the more capable reasoning-model (qwq-32b-preview) follows the same trend, though its gains plateau beyond @xmath2. nevertheless, it improves substantially, rising from 50% at @xmath3. these results confirm that increasing the number of parallel samples is a simple yet effective strategy for enhancing performance in both instructionfollowing and reasoning-based models. 1 2 4 8 163264 # samples (log) 20 40 60 pass@n qwen2.5-coder-7b-inst. no icl icl (bm25) icl (patterns) 1 2 4 8 163264 # samples (log) pass@n qwen2.5-coder-32b-inst. 1 2 4 8 163264 # samples (log) pass@n gpt-4o mini while s * primarily focuses on repeated sampling for parallel scaling, it can be integrated with more advanced parallel scaling techniques. for instance, varying input prompts can create more diverse responses @xcite , which lead to better coverage. thus, we investigate whether augmenting prompts with in-context examples can further improve parallel scaling performance. ## limitations this work primarily focuses on competition-level code generation, where it does not studies tasks such as software engineering tasks, e.g., swe-bench @xcite . the method primarily focuses on improving accuracy, while it does not aim for minimizing costs. judging llm-as-a-judge with mt-bench and chatbot arena. advances in neural information processing systems, 36:46595-46623.