CodeWalk: Generating Coding Benchmarks by Walking a Problem Graph

Jiaxin Fang; Runyuan He; Arnav Gupta; Sahil Kumawat; Huanzhi Mao; Alvin Cheung

cs.LGOct 11, 2026

CodeWalk: Generating Coding Benchmarks by Walking a Problem Graph

Authors: Jiaxin Fang, Runyuan He, Arnav Gupta, Sahil Kumawat, Huanzhi Mao, Alvin Cheung

Organizations: University of California, Berkeley

Abstract

High-quality coding problems are expensive to collect. Benchmarks such as SWE-bench rely on substantial human curation, while synthetic alternatives typically rely on costly model generation and validation. In this work, we show that new coding problems can be created at almost no cost by composing existing ones. We formulate problem generation as code composition: verified atomic problems are combined into level- $N$ tasks, and a task is kept only if every atomic problem remains unsolved and a joint reference solution passes the same check used at evaluation time. The entire task-construction process is programmatic and requires no language-model generation or validation. We instantiate this approach in four coding settings: multi-bug repair, proof completion, complexity analysis, and clone equivalence. The generated tasks are challenging for frontier models, which all degrade as compositional depth increases. The generated tasks are also useful as training data: rejection-sampling fine-tuning on them improves Qwen3.5-9B at every composition level.

Figures & tables

Figure 1: Task generation pipeline. Atoms are extracted from a source;

N

interacting atoms grown on the problem graph are composed into a single task

(x_{G},V_{G})

with reference

\mathrm{Ref}(G)

. Groups that fail admission are discarded and resampled.

	Multi-bug repair	Proof completion	Complexity	Clone equivalence
Source $\mathcal{S}$	repository with commit history	Verus-Bench programs	CodeComplex snippets	labeled Java method pairs
Atom $a$	$(c_{b},g_{b},t_{b},F_{b})$	$(f,S_{a})$	$(s,f,\tau_{\mathrm{in}},\tau_{\mathrm{out}},\ell)$	$(p_{1},p_{2},T,\lambda)$
Interaction ${\sim}$	patches share a file	$\tau_{\mathrm{out}}(a_{i})\preceq\tau_{\mathrm{in},k}(a_{j})$	$\tau_{\mathrm{out}}(c_{i})\preceq\tau_{\mathrm{in}}(c_{j})$	$\tau_{\mathrm{out}}(e_{i})=\tau_{\mathrm{in}}(e_{j})$
Composition $\mathrm{Cmp}$	locate $c_{\star}$ , apply test patches	chain under driver; remove annotations	chain under driver	chain each side under driver
Reference $\mathrm{Ref}$	union of gold patches	annotations $y_{G}^{\star}$	label derived from atomic labels	eq unless one neq atom
Verifier $V_{G}$	$\mathcal{F}$ passes	Verus accepts restored program	predicted label matches	composites match label

Table 1: Applying CodeWalk to four coding domains. Each column gives one domain’s source, relation, composition, reference and verifier.

Figure 2: A level-

2

repair task in python-tabulate , with simplified code and inputs. Hiding a named index shifts column headers, while empty input with headers="firstrow" creates spurious headers. Both bugs coexist at

c_{\star}

; their test patches form one task, and the reference combines the two source fixes.

Table 4

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Model	Class	$N{=}1$	$N{=}2$	$N{=}3$	$N{=}10$
GPT-5.6-Sol	eq	97.7	80.5	78.6	45.8
	neq	100.0	100.0	100.0	98.8
Kimi-K3	eq	97.7	82.9	85.7	51.3
	neq	93.0	92.7	95.2	94.0

Appendix

Table 4: Clone equivalence accuracy (%) by composition level, split by class. A positive composition chains

N

equivalent pairs; a negative one injects a single non-equivalent pair at a random position.

Synthetic Benchmark Generation

Synthetic benchmark generation creates controlled, verifiable evaluation tasks and datasets to test models across diverse settings.

See all 287 papers

AlgoBench: Benchmarking Algorithmic Adaptation in Code Generation
Jun 30, 2026Xinyuan Song, Zekun Cai, Liang ZhaoSynthetic Benchmark Generation Code Generation Evaluation
Emory University, Atlanta, GA, USA · The University of Tokyo, Tokyo, Japan · LocationMind, Tokyo, Japan
FrontierSmith: Synthesizing Open-Ended Coding Problems at Scale
May 14, 2026Runyuan He, Qiuyang Mang, Shang Zhou +14Synthetic Benchmark Generation Synthetic Data Generation for Language Models
UC Berkeley · UC San Diego · University of Washington +4
BenchEvolver: Frontier Task Synthesis via Solution-Centric Evolution
May 31, 2026Yangzhen Wu, Aaron J. Li, Wenjie Ma +10Synthetic Benchmark Generation Code Generation Evaluation
University of California, Berkeley · Institute for Interdisciplinary Information Sciences, Tsinghua University

Jun 30, 2026J/K move · Enter open · S save

AlgoBench: Benchmarking Algorithmic Adaptation in Code Generation

Xinyuan Song, Zekun Cai, Liang Zhao

Emory University, Atlanta, GA, USA · The University of Tokyo, Tokyo, Japan · LocationMind, Tokyo, Japan

Synthetic Benchmark Generation Code Generation Evaluation Algorithmic Reasoning Code Generation Benchmarks Algorithmic Generalization

Open paper AskPDF arXiv

High pass rates on established programming benchmarks such as HumanEval and LiveCodeBench do not always show whether a model can reason about algorithms. Many fixed benchmarks eventually become part of the public training ecosystem through released problem statements, editorials, and generated solutions, allowing later models to improve partly by exposure rather than by stronger algorithmic ability. We introduce ALGOBENCH, a framework that automatically builds novel algorithmic problems from known competitive-programming problems through structured constraint-shifting transformations. Each accepted ALGOBENCH variant is traceable to a source problem, but must make the original reference algorithm fail. Beyond pass@

k

, we introduce complexity-aware metrics -- including OPTT, OPTS, TRAPRATE, GAPT, and CONSENS -- to test whether a solution is not only functionally correct but also asymptotically suitable for the generated problem. Experiments across multiple LLMs and prompting strategies show that performance drops sharply on ALGOBENCH variants, retrieval can increase reuse of the old algorithm, and many correct-looking solutions fail to meet the required complexity. Error analysis shows that failures are mainly algorithmic rather than implementation-level, suggesting that ALGOBENCH evaluates adaptation beyond functional correctness.

Abstract

Synthetic Benchmark Generation

Explore similar work

AlgoBench: Benchmarking Algorithmic Adaptation in Code Generation

FrontierSmith: Synthesizing Open-Ended Coding Problems at Scale

BenchEvolver: Frontier Task Synthesis via Solution-Centric Evolution