Skip to content

GraphAHA: Graph-Based Adaptive Search with Heterogeneous Actions for Test-Time Code Generation

Sep 2026 · 0 citations · 19 references
Computer Science

TL;DR

GraphAHA is proposed, an adaptive graph search method with heterogeneous actions that organizes the test-time code generation in a typed directed acyclic graph and outperforms the strongest baseline for both models on both benchmarks by 4.1 percentage points on average.

Abstract

Test-time scaling improves code generation by spending additional inference budget (e.g., calls or tokens) on direct sampling, feedback-conditioned repair, and reasoning-guided implementation. Search-based methods can allocate this budget adaptively, but two challenges remain. First, tree-structured search treats each generation history as a separate state even when trajectories converge to the same program, duplicating evaluation and preventing statistics from being shared. Second, sampling, repair, and reasoning have complementary and state-dependent payoffs, making online allocation among them difficult under a finite budget. To address these challenges, we propose an adaptive graph search method with heterogeneous actions (GraphAHA). GraphAHA organizes the test-time code generation in a typed directed acyclic graph. Equivalent programs are merged into a single code node, allowing their downstream search statistics to be reused across all discovery paths. Hierarchical Thompson sampling then selects whether to generate a new state or follow an existing successor and, for generation, chooses among the type-valid sampling, reasoning, implementation, and repair operations. Evaluated on LiveCodeBench and CodeContests with Qwen2.5-Coder and DeepSeek-Coder, GraphAHA achieves the best score in 18 of 20 cases. For Pass@1 measured using visible tests, it outperforms the strongest baseline for both models on both benchmarks by 4.1 percentage points on average, demonstrating more effective use of a fixed inference budget.

View source

Similar papers

#software testing Preprint Aug 2026

Disagree to Explore, Agree to Commit: Routing-Guided Test-Time Scaling for Software Agents

This work introduces Risa (Routing-Informed Steering and Arbitration): within trajectories, routing encourages diverse exploration and controlled convergence during patch commitment; across separately sampled trajectories, agreement at informative patch positions selects a final candidate.

Kang Chen, Junjie Nian, Yi-Xin Cao et al. · 0 citations
#artificial intelligence Preprint Sep 2026

MOSAIC: Query-Aware Exploration Policy Adaptation for GraphRAG

Mosaic is presented, a training-free framework that formulates GraphRAG retrieval as a per-query control problem that converts query-specific evidence requirements into a bounded policy over seed selection, graph traversal, stopping, and evidence selection while the corpus graph, indexes, scoring functions, grounding p...

Eunkyeong Lee, Kyeong-Jin Oh, Jinwon Kim et al. · 0 citations
Preprint Aug 2026

EvoMem: Memory-Augmented Evolution for Code Optimization

EvoMem is introduced, a persistent memory architecture for LLM-based evolutionary program search that captures and reuses candidate mutation knowledge and provides evidence that persistent memory can reduce some redundant exploration and improve the reuse and adaptation of successful strategies in LLM-driven evolutiona...

Viktor Volkov, Valentin Khrulkov, Andrey V. Galichin et al. · 0 citations

Component-Aware Feedback for Self-Evolving Programs

LLM-guided evolutionary search can discover complex programs, but existing methods mostly only save candidate programs and fitness scores while discarding which component edits produced which fitness metric changes. Existing methods force the mutator LLM to infer the effect of prior edits from cluttered histories, maki...

Ethan Lin, Jinming Nian, Yi Fang · 1 citation

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.