S*: Test Time Scaling for Code Generation

1 Introduction

• GPT-4o-mini + S* surpasses o1-preview by 3.7%, while DeepSeek-R1-Distill-Qwen-32B + S* reaches 85.7% on LiveCodeBench, approaching o1-high at 88.7%.Figure 1 summarizes performance improvements across models of different sizes and types.Source: Figure 1 · p. 1, §1 · p. 2
• Code-generation scaling is underexplored because functional correctness requires executing test cases, but interpreters provide precise outputs and error messages for grounding.This execution dependence complicates validation and reward-model design compared with rule-based answer matching in mathematics.Source: §1 · pp. 1–2
• S* combines parallel sampling with sequential iterative debugging, using public-test outputs or error messages to refine generated code.For selection, an LLM synthesizes distinguishing inputs for each pair of samples; execution results then ground its choice of the best sample.Source: §1 · p. 2, Figure 2 · p. 2
• On LiveCodeBench, Qwen2.5-7B-Instruct + S* outperforms Qwen2.5-32B-Instruct by 10.7%.The evaluation covers 12 models spanning different sizes, open and closed models, and instruction-based and reasoning models; it also evaluates on CodeContests.Source: §1 · p. 2

Test Time Scaling for LLMs

• Parallel sampling expands coverage as N grows, but majority voting and reward-model scoring often fail to identify the correct sample (Brown et al., 2024; Hassid et al., 2024; Stroebl et al., 2024).Sequential scaling instead refines reasoning through chain-of-thought and iterative revision; long-CoT systems including o1, DeepSeek R1, Qwen QwQ, and Kimi use revision and backtracking.Source: §2 · p. 3

Test Time Scaling for Code Generation

• Code-generation methods use self-consistency over generated code and tests but can hallucinate test outputs; AlphaCode filters with generated tests, while AlphaCodium revises against public and model-generated tests.Saad-Falcon et al. (2024) finds parallel sampling with model-generated tests effective for CodeContests problems (Li et al., 2022).Source: §2 · p. 3

Hybrid Test-Time Scaling

• Hybrid test-time scaling in mathematics often uses reward-model-guided tree search, while S1 adds parallel voting and search after observing diminishing returns from sequential scaling.The cited examples include Monte-Carlo Tree Search and S1 (Muennighoff et al., 2025).Source: §2 · p. 3
• S* applies hybrid scaling to code generation without tree search because effective reward models remain challenging, combining parallel scaling with sequential, execution-grounded iterative debugging for coverage and adaptive input synthesis for selection accuracy (Zeng et al., 2025).Source: §2 · p. 3

Concurrent Work

• CodeMonkeys also samples and revises in parallel but targets SWE-Bench software engineering, whereas S* targets competition-level code generation and uses public-test feedback instead of generated tests across iterations.CodeMonkeys addresses file-identification challenges; the paper notes ablated variants of its public-test approach in §5.3.Source: §2 · pp. 3–4

3 Method

• Given a coding problem, the model generates a program mapping inputs to outputs; correctness is determined by private tests inaccessible during generation.Public tests clarify the problem and are typically included in the prompt.Source: §3 · p. 4

3.1 The S∗Framework

• S∗ combines parallel and sequential generation with adaptive input synthesis and execution-grounded verification in a two-stage framework.The stages are Generation and Selection.Source: §3.1 · p. 4
• Generation starts with N independent samples, then revises each for up to R rounds using public-test execution feedback, stopping when all public tests pass or revisions run out.Source: §3.1 · p. 4
• Adaptive selection addresses weaknesses of LLM judging and generated tests by executing synthesized distinguishing inputs and comparing candidate outputs.Samples are initially clustered by execution outputs, then compared pairwise across clusters; execution feedback grounds the LLM’s evaluations.Source: §3.1 · pp. 4–5

4.1 Experimental Setup

• S* is evaluated on 12 instruction-based and reasoning-based models, using LiveCodeBench as the primary benchmark and CodeContests for additional evaluation.Final LiveCodeBench evaluation uses non-overlapping v2 (511 problems); Pass@1 is the primary metric, with o1-series models and majority voting and self-debugging as baselines.Source: §4.1 · p. 5

4.2 S∗Main Results

• 10.1%: S* lets Qwen2.5-7B-Coder-Instruct outperform unscaled Qwen2.5-32B-Coder-Instruct; GPT-4o mini with S* beats o1-Preview.DeepSeek-R1-Distill-Qwen-32B with S* surpasses o1-mini and achieves results comparable to o1 (high reasoning efforts).Source: §4.2 · pp. 5–6, Table 1 · p. 6

4.3 Comparison to Other Test-Time Methods

• 8.4% to 18.2%: S* improves the Qwen-2.5-Coder series over baselines; on DeepSeek-R1-Distill-Qwen-32B, it beats majority voting by 9.9% and self-debugging by 15.6%.Majority voting clusters parallel samples by execution results, while self-debugging iteratively revises code using public tests; comparisons use 16 parallel samples and two debugging rounds.Source: Table 1 · p. 6, §4.3 · p. 6

4.4 Results on Other Benchmark

• 9.1%: S* raises Qwen-2.5-Coder-7B-Instruct from its zero-shot performance of 1.8% on CodeContests and outperforms GPT-4o mini without S* by 1.8%.The reported improvement extends to both instruction-based and reasoning models on this benchmark.Source: Table 2 · p. 6, §4.4 · p. 6

5.1 Parallel Sampling Hyper-Parameters

• >35%: Qwen2.5-Coder-7B-Instruct improves at N = 64; moderate temperatures (0.2–0.7) help, while higher temperatures plateau or reduce performance.QwQ-32B-Preview rises from 50% at N = 1 to 80% at N = 32, with gains plateauing beyond N = 32.Source: §5.1 · p. 7, Figure 4 · p. 7

5.2 Impact of In-Context Examples

• At n ≥8, ICL (Pattern) outperforms zero-shot for Qwen2.5-Coder-7B-Instruct, and at n ≥4 for Qwen2.5-Coder-32B-Instruct; it is comparable for GPT-4o mini.ICL (BM25) usually performs similarly to or worse than zero-shot; results use medium-difficulty LiveCodeBench (v4) problems with oracle selection. Pattern retrieval groups problems by technique, while BM25 retrieves similar prompts; performance is sensitive to example quality.Source: §5.2 · pp. 7–8

5.3 Impact of Iterative Debugging Variants

• 72.6 to 74.2: QwQ-32B-Preview improves with two rounds of test-feedback debugging, but benefits typically plateau after 2–3 rounds.Using only the last round of context or adding generated tests does not improve performance consistently; the chosen approach uses two rounds with public tests only, including for reasoning models.Source: §5.3 · p. 8, Figure 6 · p. 8

5.4 Impact of Different Selection Policies

• Adaptive Input Synthesis improves selection accuracy over alternatives, while Generated Tests do not improve on Public Only.It selects an input to distinguish candidate samples and uses real execution outputs rather than predicted outputs.Source: §5 · p. 7, §5.4 · p. 8, Table 3 · p. 8

6 Conclusion

• S∗ is the first hybrid test-time scaling framework for code generation, extending parallel scaling with sequential iterative debugging and adaptive synthesis of distinguishing tests validated through execution.The framework substantially improves both coverage and selection accuracy, using synthesized inputs to differentiate candidate solutions and identify correct ones via execution results.Source: §6 · p. 9
• A 3B model outperforms GPT-4o mini, GPT-4o mini surpasses o1-preview by 3.7% on LiveCodeBench, and DeepSeek-R1-Distill-Qwen-32B reaches 86.7% on LiveCodeBench, approaching o1-high at 88.5%.S∗ consistently improves code generation performance across benchmarks, including LiveCodeBench and CodeContests.Source: §6 · p. 9

• The study excludes software-engineering tasks such as SWE-BENCH and focuses on improving accuracy rather than minimizing costs.Source: §7 · p. 9

A.1 Example of Coding Problem

• The example comes from LiveCodeBench’s hard subset and illustrates the paper’s coding-problem setup with a small number of demonstrations.The method section describes the setup as unambiguous and using a small amount of demonstrations.Source: §A.1 · p. 11
• Given a string word and an array forbidden, a substring is valid when none of its substrings appears in forbidden.A substring is a contiguous sequence of characters, possibly empty.Source: §A.1 · p. 12
• The task is to return the length of the longest valid substring of word.Source: §A.1 · p. 12
• For word = "cbaaaabc" and forbidden = ["aaa","cb"], the longest valid substring has length 4.The passage lists 11 valid substrings and explains that every other substring contains "aaa" or "cb".Source: §A.1 · p. 12
• For word = "leetcode" and forbidden = ["de","le","e"], the longest valid substring has length 4.The passage lists 11 valid substrings and explains that every other substring contains "de", "le", or "e".Source: §A.1 · p. 12
• The constraints allow word and forbidden to have lengths up to 10^5, with each forbidden string between 1 and 10 characters.word and forbidden strings contain only lowercase English letters.Source: §A.1 · p. 12

A.2 Prompt templates

• The prompt set includes templates for iterative debugging, generating test cases, and code generation.Figures 7, 8, and 9 show the respective prompts.Source: §A.2 · p. 12, Figure 7 · p. 13, Figure 9 · p. 15
• The test-generation prompt requests JSON input-output examples that cover edge cases, difficult but not very long inputs, and other bug-catching cases.It asks for reasoning and a complete set of potential tests, with inputs and outputs matching the problem’s expected types and structure.Source: §A.2 · p. 14, Figure 8