GraphAHA merges equivalent programs into one node so test-time search statistics are shared, beating the strongest baseline in 18 of 20 cases

arXiv 2609.12757·medium signalXBlueskyLinkedInCopy link

Tree-structured test-time search treats each generation history as a separate state even when trajectories converge on the same program, duplicating evaluation and preventing statistics from being pooled. GraphAHA organizes test-time code generation as a typed directed acyclic graph where equivalent programs merge into a single code node so downstream search statistics are reused across every discovery path, then uses hierarchical Thompson sampling to choose between expanding a new state or following an existing successor, and among sampling, reasoning, implementation and repair operations. On LiveCodeBench and CodeContests with Qwen2.5-Coder and DeepSeek-Coder it takes the best score in 18 of 20 cases and beats the strongest baseline on Pass@1 by 4.1 pp on average under a fixed inference budget.