Retrieving Worked Examples by Program Shape from a Verified Synthetic Bank

When a language model solves a math word problem from a few worked examples placed in its prompt, which examples it sees matters a great deal. The usual approach picks examples whose wording is closest to the new question. This often fails, because two problems about bakeries can need entirely different arithmetic, while a problem about rockets and one about crop yields can share the same solution steps. Retrieving by solution structure fixes this in principle, but it hits two practical walls. You cannot see the structure of the answer before you solve the problem. And the pool of examples that come with trustworthy step-by-step solutions is small and expensive to annotate.

We propose to attack both walls at once with a bank of synthetic problems whose solutions are short Python programs that have been checked by running them. Because every example in the bank is a program, its "shape" is exact: the graph of which quantities feed which operations. At test time we sample several cheap program drafts for the new question, run them, and turn each into the same kind of graph. We then retrieve problem templates whose graphs match the drafts as a group, rather than trusting a single draft. Within each matched template, we choose the one instance whose wording is closest to the question. The prompt therefore gets the right logic from structure and the familiar vocabulary from surface similarity, and every example it contains carries a verified solution.

Core Claim

Structure-based example retrieval has so far been bottlenecked by trusting a single draft of the answer. ASTReS drafts one SQL query with a small model and retrieves by its syntax tree. RGER drafts one chain of thought, parses it into a calculation graph, and re-ranks examples with graph kernels, which are similarity measures between graphs. Both papers acknowledge the same weakness: a structurally wrong draft pulls in examples that confirm the error.

Our claim is that this weakness becomes cheap to fix when the example bank is executable. Program drafts can be filtered by whether they run at all. Their graphs can be put into a canonical form with no parsing guesswork. Pooling evidence over several drafts raises the chance that the correct structure is among the retrieved examples, much as sampling several answers raises pass@k over pass@1.

The second part of the claim follows from how the bank is built. In a template-generated corpus, each template fixes one structure and has many instances that vary in wording. That makes a two-level retrieval natural: choose templates by structure, then choose instances by wording. This directly addresses the tension the file documents. Structure-based work treats topical similarity as a distractor. Domain studies such as legal judgment prediction and chemistry find that topical similarity supplies needed vocabulary. In our design, structure and wording each decide one level of the choice, so neither has to win outright.

Research Program

The example bank is TemplateGSM from Template-based Data Generation. It contains over 7.4 million problems drawn from 7,473 GPT-4-authored templates. Each problem comes with a natural-language rationale and a Python solution verified in a sandbox. That paper used the corpus only as training data. We use it as retrieval memory instead.

We compute a canonical dataflow graph once per template from its code solution. Literals become typed placeholders, variable names are removed, and nodes are operators connected by data dependencies. This is the program analogue of the domain masking used in DAIL-SQL. Where a template's control flow depends on its parameters, we store one graph per distinct branch pattern.

At query time, a small code model samples $k$ program drafts, with $k$ between 4 and 8. Drafts that crash are discarded. Each surviving draft is canonicalized into a graph. Each template $t$ is then scored by

$$s(t) = \sum_{i=1}^{k} \mathrm{WL}(g_i, G_t),$$

where $g_i$ is the graph of the $i$-th surviving draft, $G_t$ is the template's graph, and $\mathrm{WL}$ is a Weisfeiler-Lehman graph kernel of the kind RGER uses. Summing over drafts rewards templates that agree with many drafts while still covering minority structures. We take the top templates by this score. From each, we pick the single instance whose sentence embedding is closest to the query. The final model then answers from these examples.

Two analyses accompany the accuracy results. The first measures structural recall directly. GSM8K reference solutions contain inline calculator annotations, from which we can build a gold calculation graph. Structural recall is then the fraction of test questions for which some retrieved template's graph is isomorphic to the gold graph, measured as a function of $k$. This tells us whether multiple drafts actually fix the single-draft failure, rather than inferring it from final accuracy alone.

The second analysis concerns coverage. The template count of 7,473 equals the size of the GSM8K training set, which suggests one template per training problem. We will verify this. If it holds, the synthetic bank has the same structural coverage as the human training pool. Any gain over retrieving from GSM8K-train would then come from verified executable solutions and many wording variants per structure, not from new structures. That is a clean and useful separation, and we will report it as such. It also means that out-of-distribution claims must be tested on SVAMP and on structure-held-out splits, not on GSM8K alone.

Baselines

The naive reference point is a fixed set of eight random GSM8K-train examples in the prompt, together with zero-shot prompting. SALA reports a random-example baseline of 81.78% average accuracy over GSM8K, SVAMP, CommonsenseQA and StrategyQA with Qwen2.5-7B (SALA). We run Qwen2.5-7B on the same benchmarks so that comparison is anchored.

The first semantic baseline is nearest-neighbor retrieval by sentence embedding, in the style of LM-BFF. We run it over two pools: GSM8K-train, and all of TemplateGSM. The TemplateGSM version is the real threat, discussed below. To beat it, our method must win on SVAMP, whose problem variants were built specifically to punish keyword matching (Patel et al.).

The strongest structure-aware competitors are three methods, each re-implemented over both pools with the same final model and the same number of examples in the prompt. RGER drafts one chain of thought and re-ranks by graph kernel; it reports 61.33% on SVAMP. SALA aligns sequences of reasoning operations with dynamic time warping, a method for matching sequences of different lengths; it reports 85.23% average with Qwen2.5-7B, against 83.09% for the earlier logic-based baseline PSL. SKILL-KNN rewrites each question into a description of the skills it needs before embedding it; on Spider it reports 78.3% execution accuracy against 74.6% for plain nearest-neighbor retrieval. We found no standalone GSM8K figure on Lacuna for RGER, SALA or SKILL-KNN, so those numbers come from our own runs.

Fairness rests on matched compute. All methods are compared at an equal total number of generated tokens per query, counting draft generation and any rewriting calls. Each method gets the same budget for tuning the number of retrieved examples and other hyperparameters on a held-out GSM8K-train split. Beating these methods means higher accuracy than the best of them on SVAMP and GSM8K at matched tokens, with non-overlapping bootstrap intervals.

Three ablations isolate the key ingredients. The first uses a single draft ($k=1$) and tests whether pooling over drafts is the source of any gain. The second picks a random instance within each matched template, testing the value of the wording-based second level. The third uses the same graph-based retrieval but over GSM8K-train with its human rationales, testing the value of verified executable solutions under the same structural coverage.

Why not just…?

Why not just retrieve semantically from the huge synthetic bank? With 7.4 million examples, a question's nearest wording neighbor may often belong to the right template, so structure could come along for free. This is a genuine threat. However, RGER's bakery example and SKILL-KNN's embedding visualizations show that wording neighbors cluster by topic rather than by operation. Within TemplateGSM, many instances of different templates share topics. The semantic-over-TemplateGSM baseline, together with the structural-recall measurement, settles the question directly. If wording-based retrieval matches our structural recall, the program-graph machinery is unnecessary and we will say so.

Why not just fine-tune on TemplateGSM? That is what the corpus was built for. DAIL-SQL reports that supervised fine-tuning erodes a model's ability to learn from in-prompt examples, and STAT reports plateaus from fine-tuning on math. Still, fine-tuning has no cost at query time, so we run full fine-tuning of Qwen2.5-7B on a token-matched TemplateGSM subset. If it beats retrieval on SVAMP, our method's value shrinks to settings where fine-tuning is not possible.

Why not just spend the draft budget on self-consistency? Self-consistency means sampling several answers and taking the majority vote. Our method already spends $k$ samples, so the natural rival spends them on voting. RPD found that 58% of problems produced strategically uniform samples, and Cobbe et al. document shared false positives under voting. Both suggest that voting cannot escape a wrong structure the model favors. We compare at matched tokens, and we also run majority voting on top of our own retrieval, to show whether the two effects add.

Proposed Experiments

The main experiment evaluates Qwen2.5-7B and Llama-2-7B-chat on GSM8K and SVAMP. These two models match the settings in which SALA and RGER report results. We sweep $k$ from 1 to 8 and track accuracy, structural recall, and tokens per query.

A structure-held-out split tests out-of-distribution behavior. We cluster GSM8K test problems by gold graph and evaluate on the clusters whose graphs are rarest in the bank, where the trigram-default failures described by Qiu et al. should be worst.

The decisive check is whether gains on SVAMP grow as $k$ grows while the semantic-over-TemplateGSM baseline stays flat. A rising curve means pooling over drafts fixes wrong-structure retrieval. Flat parity means the synthetic bank, not structure, was doing the work. An exploratory extension to MATH is reported separately and expected to be weak, because TemplateGSM covers grade-school structures only.