PaperlayerView exact revision on arXiv

Source-linked AI summary

Are you Synthesizing or Recalling? Evaluating LLMs on Algorithmic Code Retrieval

Nickil Maveli, Antonio Vergari, Shay B. Cohen

arXiv:2610.02438v1cs.LGcs.AIcs.CLcs.PL

TL;DR

Code-generation evaluations can conflate synthesis with retrieval, even though reproducing known algorithms is a distinct capability with practical reliability stakes. AlgoREval measures zero-shot retrieval across algorithms, languages, and graph representations; results show surface-form variation and different gains from fine-tuning approaches.

  • Problem

    Code-generation evaluations conflate synthesis and retrieval, although reproducing known algorithms is a distinct failure mode with reliability stakes.

    Source: §1 · p. 2

  • Method

    AlgoREval evaluates zero-shot reproduction across 599 problems, 77 algorithms, seven languages, and four graph-input representations, then tests prompt augmentation and fine-tuning.

    Source: §1 · p. 2

  • Results

    Retrieval accuracy varies with language and input representation; SFT improves overall accuracy by +3.9 pp, while GRPO gains are language-specific.

    Source: §1 · p. 3, §7 · p. 8

  • Takeaways & Limitations

    Parametric code retrieval is a distinct, measurable capability, and understanding its failures informs when AI-generated algorithmic code requires verification.

    Source: §1 · p. 2

    Output behavior alone cannot fully distinguish retrieval from synthesis; causal tracing or behavioral probes would be needed for cleaner separation.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Large language models (LLMs) have demonstrated strong performance in code generation, where success depends on both recalling relevant algorithmic knowledge and reasoning about how to apply it. However, existing LLM pipelines are opaque, with no explicit separation between these two components. We argue that for well-known algorithms whose canonical implementations are widely accessible in pretraining corpora, code generation is better measured as \textit{parametric code retrieval}: reproducing a named algorithm from internalised knowledge rather than synthesizing a novel one. We introduce AlgoREval, a benchmark of 599 problems spanning classical 77 algorithms across 14 domains, 7 programming languages, and 4 graph-input representations to evaluate this capability in isolation, and assess 15 models (7B--34B parameters) in a zero-shot setting. We find substantial variation in retrieval accuracy across languages and input representations, even for widely documented algorithms and show that prompt augmentation with retrieved code snippets or structured algorithmic hints improve accuracy on complex algorithms, while SFT achieves broader language gains and GRPO achieves larger per-language gains on specific languages. Together, our results establish parametric code retrieval as a distinct, measurable capability and caution against deploying AI-generated algorithmic code without systematic validation.\footnote{Code and dataset are available at https://github.com/Nickil21/AlgoREval

1 Introduction

The introduction distinguishes retrieving a known algorithm from synthesizing a new one and motivates measuring retrieval failures separately. It introduces AlgoREval and reports that retrieval varies with surface form, with failures and remediation differing across settings.

1 Introduction

  • Synthesis derives a solution, retrieval reconstructs an implementation from parametric knowledge, and recitation replays a near-verbatim cached sequence.Retrieval failures matter because almost-correct code can silently compute the wrong result, including in agentic pipelines without per-step review.Source: §1 · pp. 1–2
  • For widely documented algorithms, the proposed task is retrieving a correct implementation from internalised knowledge rather than synthesising a novel solution.The paper frames this distinction as important because synthesis and retrieval can fail independently.Source: §1 · p. 2
  • AlgoREval evaluates 15 models zero-shot on 599 problems covering 77 algorithms, seven programming languages, and four graph-input representations.The introduction also describes prompt augmentation with retrieved snippets or structured hints and compares GRPO fine-tuning with an SFT baseline.Source: §1 · p. 2
  • Retrieval accuracy varies with programming language and input representation, not model size or code specialisation.Wrong-output errors are the dominant failure mode; prompt augmentation helps only where parametric knowledge is thin, while SFT and GRPO yield different gains.Source: §1 · pp. 2–3

2 Task Formulation

The task formulation treats parametric code retrieval as producing an executable implementation of a named algorithm from model memory under a specified interface. It scores generated code by execution against a fixed reference output.

2 Task Formulation

  • Parametric code retrieval is recovering an executable implementation of a named algorithm from model memory for a specified language and input representation, without external documents or examples.The task concerns reproducing known algorithms rather than supplying in-context reference code.Source: §2 · p. 3
  • Each problem instance specifies an algorithm, target language, input representation, required signature, fixed test input, and reference output.Multiple instances can hold the algorithm and language constant while varying representation to probe representational robustness.Source: §2 · p. 3
  • Prompts name the algorithm and specify its language, representation, signature, and test input, but provide no reference implementation, pseudocode, or chain-of-thought scaffold.The zero-shot constraint is intended to make correct solutions originate from parametric memory rather than in-context retrieval.Source: §2 · p. 3
  • Retrieval succeeds when sandboxed execution produces the reference output after whitespace normalisation; failures are classified as static, runtime, timeout, or wrong-output errors.Wrong-output failures indicate plausible but incorrect logic despite clean execution.Source: §2 · p. 3

3 Dataset Construction

AlgoREval starts from documented algorithms and builds a multilingual benchmark with graph-input variants, yielding 599 entries across 7 languages and 4 input representations.

3 Dataset Construction

  • The 107 Python problems draw on RosettaCode and GeeksforGeeks and intentionally target extensively documented algorithms, not generalization to unseen problems.Ground truth comes from executing a reference implementation on a fixed test input; a submission passes only when its output matches exactly after whitespace normalization.Source: §3 · p. 3
  • Each algorithm is assigned one primary domain based on its canonical problem family, rather than every technique it may use.For example, an expression parser is labeled parsing even if it uses memoization.Source: §3 · p. 4
  • The same task is adapted across 7 languages by changing the language name, replacing the Python test block with expected output, and rewriting entry-point idioms.This design aims to isolate language-level retrieval differences from differences in problem framing.Source: §3 · p. 4
  • The final benchmark contains 599 entries across 7 languages and 4 input representations, built from 77 algorithms across 14 domains.The 107 Python problems are adapted to six additional languages; graph problems receive representation variants.Source: §3 · pp. 3–4
  • Graph problems use edge lists by default and may add adjacency-list, adjacency-matrix, or incidence-matrix variants, while non-graph entries use edge lists alone.Adjacency-list inputs cover 20 of 24 graph algorithms, adjacency matrices 10, and incidence matrices 2; the remaining 371 entries use edge lists.Source: §3 · p. 4

4 Related Work

The related work distinguishes parametric recall from synthesis and frames retrieval of familiar algorithms as a separate code-generation question. It also contrasts that focus with retrieval-augmented generation, which supplies external examples.

4.1 Parametric Memory in LLMs.

  • Parametric memory stores factual and procedural knowledge in model weights for inference without external retrieval, and code retrieval may degrade under language or input-format shifts.The paper treats such shifts as code-surface changes and wrong output as the corresponding failure mode.Source: §4.1 · p. 4

4.2 Code Generation Benchmarks

  • Existing code-generation benchmarks test synthesis, but do not test whether models reproduce familiar algorithms correctly across languages and input formats.The paper argues that pass rates on well-known algorithms can conflate retrieval from parametric memory with reasoning out a solution.Source: §4.2 · pp. 4–5

4.3 Retrieval-augmented generation (RAG)

  • RAG-based code generation supplies retrieved context to address presumed knowledge deficits, whereas this paper studies recall from model weights alone.The paper notes that retrieved examples can add noise or misaligned patterns that compete with existing parametric knowledge.Source: §4.3 · p. 5

5 Experimental Setup

The experiments evaluate 15 models across model type, scale, and inference regime using execution-based scoring. They examine retrieval failures, prompt augmentation, and execution-reward fine-tuning relative to SFT.

5.1 Models

  • The evaluation covers 15 models varying in general-purpose versus code specialization, 7B–34B scale, and standard versus extended chain-of-thought inference.Pretraining code allocation varies substantially across model types, and the paper notes that this shapes language exposure for retrieval.Source: §5.1 · p. 5

5.2 Evaluation

  • Generated programs run in isolated subprocesses with a 30-second timeout; compiled-language submissions must compile, and output must exactly match the reference after whitespace normalization.Failures are classified as static failure, runtime error, timeout, or wrong output.Source: §5.2 · p. 5
  • Pass rate measures correctness overall and by domain, language, and representation; pairwise lexical similarity across models characterizes solution diversity.The similarity analysis groups predictions by problem label and compares models that produced code for the same problem.Source: §5.2 · p. 5
  • The experiments ask how retrieval fails across languages and representations, whether snippets or structured hints improve it, and whether execution-reward GRPO reduces gaps relative to SFT.Prompt augmentation tests inference-time context, while the fine-tuning comparison separates reward-signal effects from training on correct solutions alone.Source: §5.2 · pp. 5–6

6 Analysis

The analysis measures zero-shot retrieval across languages and graph-input representations, then tests prompt augmentation and fine-tuning as ways to improve it. Results vary across settings; augmentation is conditionally useful, while SFT and GRPO produce complementary gains.

6.1 RQ1: Parametric Code Retrieval Across Languages and Input Representations

  • Across 15 models, aggregate pass rate is 41.2%; gpt-oss-20B leads overall despite having fewer active parameters than larger models.The comparison includes QwQ-32B and GPT-4o-mini.Source: §6.1 · p. 6, Table 2 · p. 6
  • General-purpose models lead in most languages, while code-specialised models show more uneven coverage; Python and JavaScript errors are often wrong outputs, unlike the more frequent static failures in compiled languages.Figure 3 breaks down Pass@1 by model and language; Figure 9 is cited for the failure-category comparison.Source: §6.1 · p. 6, Figure 3 · p. 6
  • For the same model and algorithm, changing graph input from edge list to adjacency matrix can reduce pass rate by over 10 percentage points.Figure 4 compares edge-list, adjacency-list, adjacency-matrix, and incidence-matrix inputs within each language.Source: §6.1 · p. 6, Figure 4 · p. 7
  • Correct solutions are surface-diverse but usually share an algorithmic approach: 80% of analyzed pairs do, despite zero exact matches.Mean SequenceMatcher similarity is 0.21 across 2,625 pairs; AlgoSim analyzed 2,215 pairs spanning 37 algorithms.Source: §6.1 · p. 7

6.2 RQ2: Prompt Augmentation via Retrieved Snippets and Structured Hints

  • Across all problems, hints and snippets do not improve aggregate pass rate: the 41.2% baseline becomes 40.6% with hints and 40.9% with snippets.Snippets outperform hints on 8 of 13 models, hints win on 4, and one model ties.Source: §6.2 · p. 7, Table 3 · p. 7
  • On 219 hard problems, hints raise pooled pass rate by +2.9 pp (12.9% →15.8%) and snippets by +3.9 pp (12.9% →16.9%).The gains are confined to problems where parametric knowledge is sparse; added context can introduce noise when the model already retrieves the algorithm reliably.Source: §6.2 · p. 7
  • On hard graph-algorithm instances, snippets outperform hints: pooled pass rate rises by +1.4 pp versus +0.6 pp, with more consistent snippet gains on complex algorithms.Examples include Hopcroft–Karp, Stoer-Wagner, and Blossom; QwQ-32B gains +5.0 pp from snippets versus +4.0 pp from hints.Source: §6.2 · pp. 7–8

6.3 RQ3: SFT vs. GRPO Fine-Tuning for Closing Language and Representation Gaps

  • SFT raises overall pass rate by +3.9 pp and GRPO by +2.0 pp versus the base model, with SFT gains broader across languages.Across three randomized algorithm-level splits, the same SFT setup averages +0.9 pp (±3.7 pp).Source: §6.3 · p. 8, Table 4 · p. 8

7 Conclusion

The conclusion frames the key question as whether models reliably reproduce algorithms already internalised, rather than synthesize solutions. It highlights silent wrong-output failures and complementary gains from fine-tuning.

  • The authors argue that evaluation should ask whether a model reliably reproduces an algorithm it has internalised, rather than whether it can synthesize a solution.Source: §7 · p. 8
  • SFT delivers broader, more consistent language gains (+3.9 pp overall), while GRPO’s largest single-language gain is JavaScript (+14.3 pp) and it regresses on C++ (−9.5 pp).Source: §7 · pp. 8–9
  • Runnable wrong-output errors can silently produce incorrect results and remain present even in the best-performing models.Without a concrete test case, these errors may be invisible.Source: §7 · p. 8
  • Prompt augmentation helps only where parametric knowledge is genuinely absent, while execution-based fine-tuning adjusts model weights.Source: §7 · p. 8

Limitations

The limitations bound what output-level evaluation can establish about parametric code retrieval. The accompanying appendices document the benchmark contents, models, inference settings, augmentation conditions, fine-tuning setup, and prompts.

Limitations

  • Behavioral evaluation is limited by fixed test cases, an untestable pretraining-coverage assumption, and the inability of outputs alone to separate retrieval from synthesis.A model can pass while failing untested edge cases; low-frequency algorithms in Go or Rust may be absent from pretraining, and distinguishing retrieval from synthesis would require mechanistic tracing or discriminating behavioral probes.Source: Limitations · p. 9

A Algorithms in ALGOREVAL

B Models

  • Table 6 identifies the 15 evaluated models and reports their identifiers, parameter counts, organizations, and licenses.Source: B Models · p. 11

C Zero-Shot Inference Hyperparameters

  • Open-weight models use local greedy decoding, while closed API models use temperature 0.7 and a smaller token budget; thinking models receive a 32,768-token budget.A 30-second execution timeout applies across models and languages.Source: C Zero-Shot Inference Hyperparameters · p. 11

D Prompt-Augmentation Setup

  • Prompt augmentation tests structured, language-agnostic hints and retrieved code snippets; snippets were available for 431 of 599 problems, with 168 reverting to baseline prompts.Hints include pseudocode, data structures, and complexity; snippets are retrieved per algorithm-language pair.Source: D Prompt-Augmentation Setup · p. 11

E Fine-Tuning Hyperparameters

F Prompt Template

  • The prompt template pairs a fixed system message with a per-problem message naming the algorithm and language, specifying an interface, and embedding an executable test case.Source: F Prompt Template · p. 11, Figure 5 · p. 12

G Prompt Augmentation Examples

H Error Analysis

Error patterns range from compile failures in weaker models to wrong-output errors in stronger ones. The section also reports solution diversity and describes how per-language heatmaps encode algorithm difficulty and model pass rates.

H Error Analysis

  • Stronger models fail mostly through wrong outputs, while weaker models are dominated by compile errors, indicating a gradient from syntactic to semantic retrieval failure.Source: H Error Analysis · p. 12

I Solution Diversity by Model and Language

J Per-Language Algorithm Difficulty Heatmaps

  • The heatmaps hold algorithm-row order fixed by global mean pass rate, sort model columns by within-language pass rate, and show each algorithm’s language-level mean on the right axis.Grey cells indicate combinations without collected predictions.Source: J Per-Language Algorithm Difficulty… · pp. 12–13

K Scale Experiment: A Behavioral Probe for Retrieval vs. Synthesis

The scale experiment uses increasing graph sizes to test whether correct fixed-size solutions retain textbook runtime scaling. Across both plotted regimes, fitted runtime curves track theoretical complexity slopes.

  • The experiment samples ten algorithms at five algorithm-specific graph sizes, with eight samples per size, and tests models that passed the fixed-size correctness gate.The eligible set comprises 93 of 156 algorithm-model pairs.Source: K Scale Experiment: A Behavioral Probe… · p. 13
  • The analysis fits a power-law runtime exponent and compares it with textbook complexity using a ±0.4 tolerance; sparse sampling helps distinguish E-dependent complexity from O(V^2).For seven E-dependent algorithms, the sparse regime separates an O(E log V) implementation from a hidden O(V^2) one by a full exponent.Source: K Scale Experiment: A Behavioral Probe… · p. 13
  • Across both plots, fitted runtime-versus-n curves track textbook complexity slopes rather than diverging from them.Most models reproduce the right asymptotic shape, not just fixed-size correctness.Source: K Scale Experiment: A Behavioral Probe… · p. 13

L Name/Spec Ablation for Retrieval vs. Synthesis

The ablation varies algorithm-name cues and specification correctness to distinguish retrieval from following the prompt. Correct specifications sustain high accuracy regardless of the name, while corrupted specifications sharply reduce it.

L Name/Spec Ablation for Retrieval vs. Synthesis

  • The probe tests six known algorithms with or without real names and six novel algorithms under crossed name/spec conditions; fabricated names and unseen identifier fingerprints rule out memorization as an explanation for success.Source: L Name/Spec Ablation for Retrieval vs.… · p. 14
  • gpt-oss-20B scores 85–92% across correct-spec conditions regardless of name, then 13% with moderate and 0% with severe corruption; Qwen2.5-7B-Instruct follows the pattern at 12–22%, then 4%.For gpt-oss-20B, these results hold across all six algorithms, with no exceptions.Source: L Name/Spec Ablation for Retrieval vs.… · p. 14

M Algorithmic-Fidelity Judging: Spec vs. Code on External Benchmarks

The authors estimate algorithmic fidelity on external benchmarks by comparing the algorithm inferred from a problem statement with the algorithm judged to be implemented in generated code. Pair match rates are higher on MBPP/HumanEval than LiveCodeBench, and judge choice changes model rankings.

M Algorithmic-Fidelity Judging: Spec vs. Code on External Benchmarks

  • A judge assigns generated code a category from a closed list and separately predicts the expected category from the problem statement, enabling a per-problem comparison without canonical algorithm labels.The lists contain 18 categories for MBPP/HumanEval and 24 for LiveCodeBench; two models are judged on 150 MBPP/HumanEval and 75 LiveCodeBench problems.Source: M Algorithmic-Fidelity Judging: Spec… · p. 14
  • Pair match rate is 80.6% (358/444) on MBPP/HumanEval and 61.0% (114/187) on LiveCodeBench.Source: M Algorithmic-Fidelity Judging: Spec… · p. 14
  • Under Gemini judging, gemini-2.5-flash scores 82.2% on MBPP and 77.5% on LiveCodeBench, but under GPT-4.1 it scores 69.9% and 53.7%; gpt-4.1-mini scores best under both judges.The passage describes this as a self-preference effect.Source: M Algorithmic-Fidelity Judging: Spec… · p. 14

Related papers

Loading 2610.02438v1…