title: S*: Test Time Scaling for Code Generation
summary: 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.
paper_authors._id: 67b7ed3e58f6b70b18ddb4bc
paper_authors.name: Dacheng Li
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-02-21T14:45:13.558Z
paper_authors._id: 63715b25ffc0489ed7d1f415
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/63715b25ffc0489ed7d1f415/xZJepbs0LRqFbW1knnBKR.jpeg
paper_authors.fullname: Dacheng Li
paper_authors.type: user
paper_authors.user: DachengLi
paper_authors._id: 67b7ed3e58f6b70b18ddb4bd
paper_authors.name: Shiyi Cao
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2025-02-21T09:58:43.358Z
paper_authors._id: 64ebbae6895a36ab28de811a
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/64ebbae6895a36ab28de811a/gBiaQP4paS4L13eu-yRm7.jpeg
paper_authors.fullname: Shiyi Cao
paper_authors.type: user
paper_authors.user: eva98
paper_authors._id: 67b7ed3e58f6b70b18ddb4be
paper_authors.name: Chengkun Cao
paper_authors._id: 67b7ed3e58f6b70b18ddb4bf
paper_authors.name: Xiuyu Li
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-02-21T14:45:28.150Z
paper_authors._id: 644570ba2d91b15b4c7f6311
paper_authors.avatarUrl: /avatars/d5e66012066d0c330b8f23718b1499d8.svg
paper_authors.fullname: Xiuyu Li
paper_authors.type: user
paper_authors.user: xiuyul
paper_authors._id: 67b7ed3e58f6b70b18ddb4c0
paper_authors.name: Shangyin Tan
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-02-21T14:45:33.730Z
paper_authors._id: 663cfbd9b0f659de3db65c1a
paper_authors.avatarUrl: /avatars/b7d82d281026ee04a9932b44a770b840.svg
paper_authors.fullname: Shangyin Tan
paper_authors.type: user
paper_authors.user: shangyint
paper_authors._id: 67b7ed3e58f6b70b18ddb4c1
paper_authors.name: Kurt Keutzer
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-02-21T14:45:39.902Z
paper_authors._id: 6251bf4b183aa4266924ad91
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/1678041834400-6251bf4b183aa4266924ad91.jpeg
paper_authors.fullname: Kurt Keutzer
paper_authors.type: user
paper_authors.user: kurtkeutzer
paper_authors._id: 67b7ed3e58f6b70b18ddb4c2
paper_authors.name: Jiarong Xing
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-02-21T14:45:45.774Z
paper_authors._id: 66ff8aa43a31c499dc48fdd6
paper_authors.avatarUrl: /avatars/060dc90fb13991bd013ce8173f12ae3e.svg
paper_authors.fullname: Jiarong Xing
paper_authors.type: user
paper_authors.user: JerryPotter
paper_authors._id: 67b7ed3e58f6b70b18ddb4c3
paper_authors.name: Joseph E. Gonzalez
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-02-21T14:45:52.578Z
paper_authors._id: 645d2e8401f4eaab2a0878ce
paper_authors.avatarUrl: /avatars/1273c5fb607b4b622a746a42692fa632.svg
paper_authors.fullname: Joseph E. Gonzalez
paper_authors.type: user
paper_authors.user: ProfJoeyG
paper_authors._id: 67b7ed3e58f6b70b18ddb4c4
paper_authors.name: Ion Stoica
paper_title: S*: Test Time Scaling for Code Generation
paper_summary: 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.
paper_ai_keywords: LLMs test-time compute code generations Transformers Segment addressing Segment Mapping parallel scaling sequential scaling performance boundaries selection mechanism distinguishing inputs pairwise comparison execution-grounded information Large Language Models Large Reasoning Models InformationCodeBench LiveCodeBench