Retrieving Math Problems by the Programs That Solve Them

When a language model solves a math problem, it helps a great deal to show it a few worked examples of problems that are solved the same way. Today those examples are picked by text similarity: find past problems whose wording looks like the new one. This fails badly exactly where it matters. Two problems can share every keyword and need entirely different mathematics. The same problem written in Mongolian, or drawn as a diagram, can look nothing like its English twin. On the MathNet benchmark, leading embedding models find the true mathematical equivalent of an Olympiad problem only about 5% of the time at rank one. Examples retrieved that way actually lower solving accuracy, while hand-picked equivalents raise it by up to 12 points (MathNet).

We propose to index and retrieve problems by a short executable program that solves them, not by their words. The model first drafts a Python program for the new problem, whatever the language or modality of the input. Every numeric constant in the program is lifted out as an argument, and the program's structure and its input-output behavior on fixed probe inputs become the retrieval key. Corpus problems get keys from programs checked against their known answers. Program-of-Thought prompting, where the model writes code and an interpreter does the arithmetic, is usually used only to stop arithmetic mistakes (PAL). We use the same code a second time, as a representation of the problem that no longer depends on the language it was written in or on the exact numbers read off a diagram. The claim to test is concrete. Program-keyed retrieval should find structurally equivalent problems far more often than text or multimodal embeddings. Its accuracy should stay nearly flat across languages. And the demonstrations it retrieves should close part of the gap between embedding-based retrieval and expert-chosen examples.

Core Claim

The four problem areas meet at one object. Surface wording misleads retrievers, which is the semantic-logical misalignment problem. Models guess arithmetic tokens instead of computing them, which is the arithmetic hallucination problem. Vision-language models see diagram parts correctly but fail to chain them into a derivation, which is the multimodal reasoning gap. Reasoning degrades outside English even when translation is fluent, which is the cross-lingual reasoning gap.

A program with lifted constants addresses all four at once, in different roles. Arithmetic goes to the interpreter. The key ignores wording, so it does not care what language the question came in. The key ignores constant values, so a misread tick label or bar height in a chart changes the program's arguments but not its structure, and retrieval survives perception errors that would still break a direct answer. Retrieval is therefore the core mechanism of the proposal. Code execution is the representation. Multilingual and multimodal inputs are the stress conditions under which the method has to hold.

What would be new is judging equivalence between problems by executing and comparing programs, across languages and between text and diagrams. Prior retrievers compare natural-language descriptions, and prior multilingual Program-of-Thought work retrieves nothing.

Relation to Prior Work

Two retrieval methods motivate this design and supply its closest competitors. SKILL-KNN prompts an LLM to rewrite each query as a description of the operations it needs, then embeds that text. It improved Spider execution accuracy from 74.6% to 78.3%. SALA parses problems into operation sequences and aligns them with dynamic time warping, a method for matching sequences of different lengths. It reached 85.23% average accuracy on Qwen2.5-7B, against 83.09% for the prior logic-based selector. Both still compare English text, and SALA assumes a linear chain of steps. We replace the text with code: the key is a syntax tree and an execution trace rather than a description, so it can represent branching structure, and it can be checked against gold answers when the corpus is built. Text-to-SQL work showing that question similarity does not track the structure of the required query (Shen et al.) points the same way. We carry that intuition from SQL to general math programs.

Three papers connect subsets of the four directions. We build on each and differ from each. MathNet provides the multilingual, multimodal retrieval benchmark and the diagnosis that embeddings fail, but proposes no retrieval method and uses no code execution. Payoungkhamdee et al. show that Program-of-Thought helps in multilingual MGSM: soft self-consistency raised Llama 2-7B cross-lingual accuracy from 31.6% to 56.6%, and code-pretrained models transfer better across languages. Their work is text-only and uses fixed prompts. XRICL retrieves cross-lingual demonstrations for SQL generation, but it pivots through English translation and still retrieves by embedded text. TinyChart shows that code generation removes numeric errors in chart question answering, but in English only and with no retrieval.

Several results constrain the design. DCoT found that retrieving multimodal demonstrations with image features adds noise compared with text-only keys. MRMR found that text retrieval over generated captions beat native multimodal retrievers by 6 nDCG@10 points, yet still fell below 25% accuracy on negation and contradiction tasks. Together these tell us not to embed pixels, and not to assume that turning images into text is enough. Actions Speak Louder than Words reports that model reasoning is about 99% ASCII even when the prompt is in Devanagari, and that policy retention across languages collapses toward chance below 10B parameters. We read this as support for code as a pivot the model already uses. It also warns that small drafting models may produce language-dependent programs, so we test drafting-model size directly.

Research Program

The system has three parts.

The first is a corpus builder. For every corpus problem with a closed-form answer, a strong code model writes several candidate programs from the expert solution. We keep only programs whose execution reproduces the gold answer. These verified programs are then normalized. Variables are renamed in order of first use. Literal constants become function arguments, with a record of the constants' original values. Library calls are mapped to a small canonical set, so that sympy and hand-written loops for the same operation look alike where that is feasible.

The second is the key. Each normalized program yields two signals. One is its abstract syntax tree, the tree representation of the code's structure, which we compare with a tree kernel. The other is a behavioral fingerprint: the program's outputs on a fixed set of random probe arguments, compared up to reordering of the arguments.

The third is query drafting. A new query arrives as text in any language, possibly with a diagram. A vision-language model reads it and writes $n$ draft programs without running them. Each draft is normalized in the same way.

The similarity between query $q$ and corpus problem $d$ is

$$s(q,d) = \max_{i \le n} \big[\lambda\, K(t_i, t_d) + (1-\lambda)\, F(f_i, f_d)\big],$$

where $t_i$ and $f_i$ are the syntax tree and fingerprint of the $i$-th draft, $t_d$ and $f_d$ those of the corpus program, $K$ is a normalized tree kernel, $F$ is the fraction of probe inputs on which the two programs' outputs agree, and $\lambda \in [0,1]$ is tuned on a development split. Taking the maximum over drafts makes the key robust to a single bad draft. It also means a key can be wrong only if every draft is wrong.

The top $k$ retrieved problems, each shown with its verified program, become demonstrations. The solver then writes and runs code in the usual Program-of-Thought loop.

The analysis side has one central measurement. For every input language and modality, we split the failures of the full pipeline into three parts. Drafting failure means no draft is structurally close to the gold program. Retrieval failure means the drafts are fine but the neighbors are wrong. Solving failure means the neighbors are right but the answer is still wrong. This split lets us say, for the first time, how much of the cross-lingual gap and the multimodal gap comes from reading the problem and how much comes from what happens after reading.

The scope is limited. Proof-only Olympiad problems have no executable answer, and we exclude them from the program-keyed evaluation. We report that exclusion rate openly as a coverage limit of the method.

Baselines

The do-nothing reference is zero-shot Program-of-Thought with the same solver and no demonstrations, alongside zero-shot direct answering. MathNet reports 84.8% zero-shot accuracy for DeepSeek-V3.2-Speciale on test-small. For smaller open solvers we will measure this ourselves. The ceiling is MathNet's Expert-RAG setting, which uses ground-truth equivalent problems and reached 97.3% for the same model. Any retriever is scored by how much of the distance between zero-shot and Expert-RAG it recovers.

The strongest off-the-shelf retrievers are the dense embedders MathNet evaluates, Gemini-embedding-001 and Qwen3-embedding-4B. Both reach about 5% Recall@1 on MathNet problem retrieval. For MGSM we add Multilingual E5, which XAMPLER reports at 74.61% on SIB200 against XAMPLER's own 75.91%. For diagram queries we add MRMR's strongest recipe, text embeddings over LLM-generated captions (54.1 nDCG@10 on MRMR). All of these are run on the same corpus, the same queries, the same $k$, and the same solver prompt.

The strongest method-level competitor is SKILL-KNN run on the same drafting model. We give it $n$ skill-description rewrites per query, the same number of LLM calls as our $n$ drafts, and take the maximum similarity across rewrites. Beating it means higher Recall@1 on MathNet at matched call budget, together with a smaller recall drop from English to low-resource languages. We will also run SALA's sequence alignment as a second structural competitor.

The ablation that isolates the key ingredient keeps our drafts and changes only the representation. Each draft is paraphrased into an English operation description and embedded with the same text encoder SKILL-KNN uses. If code keys do not beat their own English paraphrase, the benefit comes from drafting, not from execution-based keys. We also ablate the fingerprint term ($\lambda=1$) against the syntax-tree term ($\lambda=0$). Finally, we swap in gold programs for the query drafts, which gives an oracle upper bound on retrieval with perfect drafting.

Why not just…?

Why not just translate to English, caption the image, and use SKILL-KNN? This is the most serious threat, and the experiments are designed to settle it rather than argue it away. The evidence against it is indirect. LLaMAX finds that translation quality decouples from reasoning. M3Kang needed quality filtering because translated problems carried artifacts and labels that refer into images. MRMR shows that caption-based retrieval still fails on logically demanding queries. We run exactly this pipeline, with the same translator budget, as a baseline in every condition. If it matches program keys on MathNet and M3Kang, we will report that code adds nothing beyond structured paraphrase.

Why not just fine-tune a dense retriever on MathNet's synthetic equivalent pairs? MathNet releases about 39,000 synthetic pairs, and contrastive fine-tuning on them may teach embeddings to ignore wording. We train such a retriever, initialized from Qwen3-embedding-4B with a matched tuning budget, and treat it as a full baseline. Our expectation is that it will improve on in-distribution languages but will not carry structure to languages and diagram types rare in its training pairs. Program keys need no training data per language, which is the advantage we expect to see. If the fine-tuned retriever wins on held-out languages too, the idea should give way to it.

Why not skip retrieval and use a tool-trained reasoning model? ReTool reaches 67.0% on AIME 2024 versus 40.0% for text-only RL, and ZeroTIR shows that models learn to call code on their own. This removes arithmetic errors, but MathNet's Expert-RAG result shows that even very strong solvers gain up to 12 points from the right examples. We include a tool-trained solver both with no retrieval and with each retrieval method. Retrieval should matter only if its gains persist on top of such a solver, and that is what we test.

Proposed Experiments

Retrieval is evaluated on MathNet's retrieval task, restricted to problems with closed-form answers, and reported per language and separately for problems with and without diagrams, as Recall@1 and Recall@5.

Downstream solving is evaluated on four benchmarks. The first is MathNet test-large and test-small in the Math RAG setting. The second is M3Kang across a spread of high- and low-resource languages; no per-model accuracy numbers are reported for it on Lacuna, so all numbers there are our own. The third is MGSM, for comparison against the 56.6% soft self-consistency result. The fourth is MATH-Vision, where GPT-4o reaches 30.39% and 42.2% of GPT-4V's errors are reasoning errors despite correct perception.

For MGSM and M3Kang, the demonstration corpus is the English training data only. This makes every non-English query a cross-lingual retrieval.

Four checks decide the outcome. First, program keys must beat both SKILL-KNN at matched call budget and the fine-tuned dense retriever on MathNet Recall@1 in held-out languages. Second, the drop in recall from English to low-resource languages must be smaller for program keys than for every text-based retriever. Third, on diagram problems, recall with program keys should barely change when we deliberately perturb numbers the drafter extracts from charts. Text keys should change more under the same perturbation. This is the direct test of the claim that lifting constants makes retrieval robust to perception errors. Fourth, the failure decomposition should show whether the remaining cross-lingual gap lives in drafting. If it does, the next target is the reading step, not retrieval.

We also sweep drafting-model size across the 10B threshold found in the Actions Speak paper, to test whether code keys stay stable across languages for small drafting models.

Two outcomes would count against the proposal. One is the translate-and-caption pipeline or the fine-tuned embedder matching program keys on held-out languages. The other is the English-paraphrase ablation matching them. Either result would falsify the core claim, and we would report it as such.