Source-linked AI summary
S*: Test Time Scaling for Code Generation
Dacheng Li, Shiyi Cao, Chengkun Cao, Xiuyu Li, Shangyin Tan, Kurt Keutzer, Jiarong Xing, Joseph E. Gonzalez, Ion Stoica
TL;DR
Test-time scaling has been extensively studied in mathematics but remains under-explored for code generation, where execution is needed to assess functional correctness. S* combines parallel sampling with execution-grounded iterative debugging and adaptive distinguishing-input synthesis, and consistently improves performance across model families and sizes. Its reported results include GPT-4o-mini + S* surpassing o1-preview by 3.7% on LiveCodeBench and DeepSeek-R1-Distill-Qwen-32B + S* reaching 86.7%.
Problem
Test-time scaling for code generation remains under-explored, despite code correctness requiring execution-based functional validation.
Method
S* combines parallel sampling with sequential scaling through iterative debugging and adaptive input synthesis, using execution results to improve generation and selection.
Results
S* consistently improves code-generation performance across benchmarks, including LiveCodeBench and CodeContests, across diverse model families and sizes.
Takeaways & Limitations
S* enables smaller and instruction-based models to outperform stronger comparison models while also improving open reasoning models’ performance.
Takeaways & Limitations
The work focuses on competition-level code generation and accuracy improvement, not software-engineering tasks such as SWE-Bench or minimizing costs.
Abstract
from arXiv · showhide
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* extends the existing parallel scaling paradigm with sequential scaling to push performance boundaries. 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 across 12 Large Language Models and Large Reasoning Model and show: (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%. Code will be available under https://github.com/NovaSky-AI/SkyThought.
1 Introduction
S* addresses the under-explored problem of test-time scaling for code generation with a hybrid framework that combines iterative debugging, adaptive test-input synthesis, and execution-grounded selection. Across diverse models, it consistently improves performance and enables smaller or instruction-based models to surpass stronger baselines.
- Motivation and contribution: Code generation remains under-explored for test-time scaling because functional correctness requires executing many test cases rather than matching reference strings.Programmatic interpreters nevertheless provide precise outputs and error messages for grounding generation and selection.
- Method: S* iteratively refines parallel samples using public-test execution feedback, then compares paired samples with adaptively synthesized distinguishing inputs and actual execution results.The two-stage pipeline consists of Generation and Selection.
- Results: S* consistently improves performance across 12 models spanning diverse families, sizes, and instruction-based or reasoning-based settings.Evaluations cover LiveCodeBench and CodeContests.
- Results: 10.7%: Qwen2.5-7B-Instruct + S* outperforms Qwen2.5-32B-Instruct on LiveCodeBench.This illustrates that S* can allow smaller models to surpass larger models within the same family.
- Results: 3.7%: GPT-4o-mini + S* surpasses o1-preview on LiveCodeBench, while DeepSeek-R1-Distill-Qwen-32B + S* achieves 85.7%.The latter approaches o1-high at 88.7% on LiveCodeBench.
- Motivation and contribution: S* is a hybrid test-time scaling framework that combines parallel sampling with sequential scaling through iterative debugging and adaptive input synthesis.It improves both generated-code coverage and selection accuracy.
2 Related work
Prior code-generation scaling methods rely mainly on parallel sampling, sequential refinement, or generated tests, each facing selection or reliability challenges. S* combines parallel and sequential scaling for code without tree search, using execution-grounded debugging and adaptive test synthesis.
- Existing test-time scaling: Parallel scaling generates multiple solutions and selects among them, but majority voting and reward-model scoring often struggle to identify the correct sample.Coverage generally increases with the number of samples, while selection remains difficult.
- Existing test-time scaling: Sequential scaling refines reasoning over multiple steps, and S* applies iterative debugging driven by test-execution feedback to code generation.The supplied related-work passage introduces this connection but is truncated.
- Code-generation methods: Earlier code-generation methods generate code samples and test cases for self-consistency, but model hallucination can make predicted test outputs unreliable.AlphaCode instead uses a trained model to generate test cases for filtering and selection.
- Hybrid scaling: Math-focused hybrid scaling often uses reward-model-guided tree search, whereas S* applies hybrid scaling to code generation without relying on tree search.The paper attributes this choice to the difficulty of developing a general, effective code-generation reward model.
- Hybrid scaling: S* augments parallel scaling with execution-grounded iterative debugging for coverage and adaptive input synthesis for selection accuracy.This is the paper’s stated distinction from prior hybrid approaches.
- Concurrent work: CodeMonkeys also combines parallel sampling and revision, but targets software engineering on SWE-Bench, whereas S* targets competition-level code generation.The domain difference influences the algorithmic choice: S* uses public-test feedback rather than repeated model-generated tests.
3 Method
S∗ is a two-stage hybrid framework that combines parallel sampling, sequential iterative debugging, and execution-grounded adaptive selection for code generation.
- S∗ takes a coding problem and generation model as input, producing program candidates that map inputs to outputs.
- Setup: The framework uses public and private test cases, with correctness determined by passing all private tests unavailable during generation.
- Generation: Generation combines parallel sampling with sequential revision, refining each sample through up to R debugging rounds using public-test execution feedback.Revision stops when a sample passes all public tests or reaches the maximum number of attempts.
- Selection: Selection compares candidate solutions after public-test generation because additional evaluation is needed for reliable final choice.The framework considers both LLM-as-a-judge and generated-test baselines.
- Selection: S∗ addresses weaknesses of existing selection approaches, where LLM judging can mispredict program behavior and generated tests may not distinguish candidates reliably.
- Selection: Adaptive input synthesis clusters candidates by execution outputs, then generates distinguishing inputs for pairwise comparisons.The compared samples are executed on synthesized inputs, and the superior candidate is selected from the execution results.
4 Evaluation
Across 12 instruction-based and reasoning models on LiveCodeBench and CodeContests, S∗ consistently improves performance and outperforms common test-time scaling baselines.
- Main findings: S∗ consistently improves performance across model families, sizes, types, and the LiveCodeBench and CodeContests benchmarks.
- Main findings: S∗ outperforms existing test-time scaling methods, including majority voting and self-debugging, by improving coverage and selection accuracy.
- Evaluation setup: The evaluation uses Pass@1 primarily across 12 models, with LiveCodeBench v2 and 165 CodeContests problems as benchmarks.
- Baseline comparison: 9.9% and 15.6%: S∗ outperforms majority voting and self-debugging, respectively, for DeepSeek-R1-Distill-Qwen-32B.
- CodeContests: 9.1%: Qwen2.5-Coder-7B-Instruct with S∗ improves from its zero-shot performance of 1.8% on CodeContests.It also outperforms GPT-4o mini without S∗ by 1.8%.
5 Ablation Studies
The ablations show that moderate-temperature parallel sampling, execution-feedback debugging, and adaptive input synthesis each improve S* components, while gains depend on example quality and plateau after limited debugging rounds.
- 5.1 Parallel Sampling Hyper-Parameters: Moderate temperatures of 0.2–0.7 improve performance, whereas temperatures above 0.7 plateau or decline and may reduce solution consistency.Qwen2.5-Coder-7B-Instruct can regress at higher temperatures, indicating a diversity–quality trade-off.
- 5.1 Parallel Sampling Hyper-Parameters: Increasing parallel samples significantly improves performance across instruction-following and reasoning models.Qwen2.5-Coder-7B-Instruct gains over 35% at N = 64, while QwQ-32B-Preview rises from 50% at N = 1 to 80% at N = 32 before plateauing.
- 5.2 Impact of In-Context Examples: Pattern-based in-context retrieval outperforms zero-shot when n ≥8 for Qwen2.5-Coder-7B-Instruct and n ≥4 for Qwen2.5-Coder-32B-Instruct, while BM25 is usually comparable to or worse than baseline.Performance is sensitive to the quality and retrieval effectiveness of in-context examples.
- 5.3 Impact of Iterative Debugging Variants: Execution-feedback debugging improves reasoning-model performance, with QwQ-32B-Preview increasing from 72.6 to 74.2 after two rounds.Benefits typically plateau after 2–3 rounds; the chosen configuration uses two rounds with public tests only.
- 5.4 Selection Policy: Adaptive input synthesis is more reliable than generated-test and LLM-judge selection policies for distinguishing candidate solutions.Generated tests can introduce noise when model-predicted outputs are erroneous or inputs are poorly chosen.
6 Conclusion
The conclusion presents S* as a hybrid code-generation framework that combines parallel and sequential scaling with execution-grounded adaptive selection. It reports consistent gains across benchmarks, including improvements that narrow gaps between smaller, instruction-based, open, and closed models.
- 6 Conclusion: S* combines parallel scaling with sequential scaling through iterative debugging and adaptive input synthesis using execution results to improve coverage and selection accuracy.The framework uses synthesized distinguishing test inputs to differentiate candidates and identify correct solutions.
- 6 Conclusion: S* consistently improves code-generation performance across LiveCodeBench and CodeContests.The reported improvements span the evaluated benchmark settings.
- 6 Conclusion: 3B models can outperform GPT-4o mini, GPT-4o mini + S* surpasses o1-preview by 3.7% on LiveCodeBench, and DeepSeek-R1-Distill-Qwen-32B reaches 86.7% versus o1-high at 88.5%.These comparisons are reported as examples of S* improving performance across model families and sizes.
7 Limitations
The work is scoped to competition-level code generation and prioritizes accuracy rather than minimizing inference costs.
- 7 Limitations: The study does not evaluate software-engineering tasks such as SWE-BENCH and does not aim to minimize costs.Its primary focus is competition-level code generation and accuracy improvement.
A.1 Example of Coding Problem
The example coding problem asks for the longest substring that contains none of the forbidden strings as a substring. It illustrates the problem statement, examples, and constraints used in the paper's setup.
- A.1 Example of Coding Problem: The task is to return the length of the longest valid substring of word that contains no substring from forbidden.A substring is contiguous and may be empty.
- A.1 Example of Coding Problem: For word = "cbaaaabc" and forbidden = ["aaa","cb"], the reported output is 4.The paper lists valid substrings and explains that longer candidates contain a forbidden substring.
- A.1 Example of Coding Problem: For word = "leetcode" and forbidden = ["de","le","e"], the reported output is 4.The listed valid substrings include "tcod" as a longest valid example.
- A.1 Example of Coding Problem: The constraints allow word and forbidden to each have length up to 10^5, with forbidden strings of length at most 10 and lowercase English letters.These bounds define a large-input string-processing problem.
A.2 Prompt templates
The appendix provides automatically generated DSPy prompts for code generation, iterative debugging, and test-case generation. These templates structure inputs and outputs around reasoning, code, tests, and completion markers.
- Prompt templates: DSPy automatically generates the experiment prompts shown for iterative debugging, test-case generation, and code generation.The appendix identifies Figures 7–9 as the corresponding prompt templates.
- Iterative debugging: The debugging template supplies a prompt, reasoning, and code output while incorporating prior code history and test-case feedback.It instructs the model to diagnose the previous failure and correct the code without adding non-code content to the code field.
- Test-case generation: The test-generation template asks for reasoning and a complete set of potential inputs and outputs in JSON format.It emphasizes edge cases, difficult inputs that are not very long, and inputs likely to expose bugs.