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

• URL: http://arxiv.org/abs/2609.12757v1
• Date: Fri, 11 Sep 2026 12:08:55 GMT
• Title: GraphAHA: Graph-Based Adaptive Search with Heterogeneous Actions for Test-Time Code Generation
• Abstract summary: 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.<n>We propose an adaptive graph search method with heterogeneous actions (GraphAHA)<n>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.
• Score: 19.00432566076247
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Harness-G: A Graph-Structured Harness for Search Agents [17.554676400013424]
  Reinforcement learning (RL) search agents commonly model retrieval as free-form natural-language query generation.<n>We propose Harness-G, a graph-structured retrieval framework that redesigns this interface.<n>It reformulates free-form query generation as finite action selection, while the environment constructs the menu, tracks retrieval state, and validates and executes each choice.<n>It achieves the highest average F1 at both evaluated model scales, outperforming the strongest baseline, Graph-R1, by 10.74 points at 1.5B and 3.98 points at 3B.
  arXiv  Detail & Related papers  (2026-07-30T04:05:05Z)
• Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A* [0.324890820102255]
  This paper introduces a reformulation of alignment-based conformance checking as a totally unimodular linear program (LP)<n>By exploiting the underlying network-flow structure, the proposed formulation guarantees an optimal extreme-point solution through LP relaxation.<n>We derive simple algorithm-selection guidelines that combine both approaches, achieving average runtime savings of 38.6% with 96% selection accuracy compared to always using A*.
  arXiv  Detail & Related papers  (2026-05-26T12:30:23Z)
• An Embarrassingly Simple Graph Heuristic Reveals Shortcut-Solvable Benchmarks for Sequential Recommendation [50.09718257952108]
  Sequentialsolv has increasingly shifted toward generative recommenders that combine sequential patterns with semantic item information.<n>These methods are often evaluated on a small set of widely used benchmarks, raising a key question: do these benchmarks actually require the advanced modeling capabilities that modern generative recommenders claim to provide?<n>We conduct a benchmark audit with an intentionally simple graph. Starting from only the last one or two items, it retrieves candidates from a few-hop item-transition graph and ranks them by item-feature similarity.
  arXiv  Detail & Related papers  (2026-05-08T02:00:11Z)
• $V_1$: Unifying Generation and Self-Verification for Parallel Reasoners [69.66089681814013]
  $V_$ is a framework that unifies generation and verification through efficient pairwise ranking.<n>$V_$-Infer improves Pass@1 by up to $10%$ over pointwise verification.<n>$V_$-PairRL achieves $7$--$9%$ test-time scaling gains over standard RL and pointwise joint training.
  arXiv  Detail & Related papers  (2026-03-04T17:22:16Z)
• Covariate-assisted graph matching [1.4466802614938332]
  We propose two novel graph matching methods, where a partial alignment for a set of nodes, called seeds, is known.<n>The effectiveness of our methods is demonstrated through numerical experiments and in an application to matching the statistics academic genealogy and the collaboration networks.
  arXiv  Detail & Related papers  (2025-12-12T18:12:56Z)
• Chain-of-Retrieval Augmented Generation [91.02950964802454]
  This paper introduces an approach for training o1-like RAG models that retrieve and reason over relevant information step by step before generating the final answer.<n>Our proposed method, CoRAG, allows the model to dynamically reformulate the query based on the evolving state.
  arXiv  Detail & Related papers  (2025-01-24T09:12:52Z)
• A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization [12.016449555335976]
  We propose an open-source benchmark suite MaxCut-Bench dedicated to the NP-hard Maximum Cut problem in both its weighted and unweighted variants. We use the benchmark in an attempt to systematically corroborate or reproduce the results of several, popular learning-based approaches. Our results show that several of the learneds fail to outperform a naive greedy algorithm, and that only one of them consistently outperforms Tabu Search.
  arXiv  Detail & Related papers  (2024-06-14T19:44:23Z)
• Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking [66.83273589348758]
  Link prediction attempts to predict whether an unseen edge exists based on only a portion of edges of a graph. A flurry of methods have been introduced in recent years that attempt to make use of graph neural networks (GNNs) for this task. New and diverse datasets have also been created to better evaluate the effectiveness of these new models.
  arXiv  Detail & Related papers  (2023-06-18T01:58:59Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
  Graph outlier detection is an emerging but crucial machine learning task with numerous applications. We present the first comprehensive unsupervised node outlier detection benchmark for graphs called UNOD.
  arXiv  Detail & Related papers  (2022-06-21T01:46:38Z)
• Provable Training Set Debugging for Linear Regression [17.138864028618276]
  We first formulate a general statistical algorithm for identifying buggy points and provide rigorous theoretical guarantees. We then present two case studies to illustrate the results of our general theory and the dependence of our estimator on clean versus buggy points.
  arXiv  Detail & Related papers  (2020-06-16T09:14:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.