Paper deep dive

AlgoBench: Benchmarking Algorithmic Adaptation in Code Generation

Xinyuan Song, Zekun Cai, Liang Zhao

Year: 2026Venue: arXiv preprintArea: cs.SEType: PreprintEmbeddings: 80

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 98%

Last extracted: 7/5/2026, 6:40:49 AM

Summary

ALGOBENCH is a novel framework designed to benchmark the algorithmic adaptation capabilities of Large Language Models (LLMs). Unlike static benchmarks like HumanEval, ALGOBENCH automatically generates new algorithmic problems by applying structured transformations (e.g., constraint scaling, greedy-trap injection) to known competitive programming problems. This ensures that models cannot rely on memorized templates or solutions. The framework introduces complexity-aware metrics such as OPTT (Optimal Time Complexity Rate), OPTS (Optimal Space Complexity Rate), and TRAPRATE to evaluate whether solutions are asymptotically suitable, not just functionally correct. Experiments across several LLMs (including GPT-4o, Gemini 2.5 Flash, and Claude 4.5) demonstrate that performance drops significantly on these variants, revealing that many models struggle with true algorithmic reasoning and often reuse suboptimal or incorrect templates.

Entities (9)

ALGOBENCH · framework · 100%Claude 4.5 Opus · llm · 100%Constraint Scaling · transformation-operator · 100%Gemini 2.5 Flash · llm · 100%GPT-4o · llm · 100%Greedy-trap Injection · transformation-operator · 100%HumanEval · benchmark · 100%LiveCodeBench · benchmark · 100%OPTT · metric · 100%

Relation Signals (4)

ALGOBENCH → evaluates → LLM

confidence 100% · ALGOBENCH is a framework for... evaluating algorithmic adaptation in code generation.

Constraint Scaling → isa → Transformation Operator

confidence 100% · The primary operators include constraint scaling (CS)...

OPTT → measures → Time Complexity

confidence 100% · OPTT (Optimal Time Complexity Rate) is the fraction of submissions that are correct and satisfy the target time complexity.

ALGOBENCH → uses → Transformation Operator

confidence 100% · ALGOBENCH uses ten rule-based transformation operators to generate new algorithmic problems.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract: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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

79,295 characters extracted from source content.

Expand or collapse full text

ALGOBENCH: Benchmarking Algorithmic Adaptation in Code Generation Xinyuan Song 1 Zekun Cai 2,3 Liang Zhao 1 1 Emory University, Atlanta, GA, USA 2 The University of Tokyo, Tokyo, Japan 3 LocationMind, Tokyo, Japan xinyuan.song,liang.zhao@emory.edu, caizekun@csis.u-tokyo.ac.jp Abstract High pass rates on established programming benchmarks such as HumanEval and Live- CodeBench do not always show whether a model can reason about algorithms. Many fixed benchmarks eventually become part of the pub- lic training ecosystem through released prob- lem statements, editorials, and generated solu- tions, allowing later models to improve partly by exposure rather than by stronger algorith- mic ability. We introduce ALGOBENCH, a framework that automatically builds novel al- gorithmic problems from known competitive- programming problems through structured constraint-shifting transformations. Each ac- cepted ALGOBENCH variant is traceable to a source problem, but must make the original ref- erence algorithm fail. Beyond pass@k, we in- troduce complexity-aware metrics—including OPTT, OPTS, TRAPRATE, GAPT, and CON- SENS—to test whether a solution is not only functionally correct but also asymptotically suitable for the generated problem. Experi- ments across multiple LLMs and prompting strategies show that performance drops sharply on ALGOBENCH variants, retrieval can in- crease reuse of the old algorithm, and many correct-looking solutions fail to meet the re- quired complexity. Error analysis shows that failures are mainly algorithmic rather than implementation-level, suggesting that ALGOB- ENCH evaluates adaptation beyond functional correctness. Code is available athttps:// github.com/Hik289/algobench.git. 1 Introduction Large language models (LLMs) now perform well on many programming and algorithmic bench- marks. Recent systems obtain high pass@1 scores on standard datasets such as HumanEval (Chen et al., 2021) and LiveCodeBench (Jain et al., 2024). These scores, however, do not necessarily mea- sure algorithmic reasoning. Many programming problems, editorials, and reference solutions are publicly available, and web-scale pretraining cor- pora may contain exact or near-duplicate problem– solution pairs. A model can therefore pass a bench- mark by recalling a known solution pattern, rather than by deriving the required algorithm from the stated constraints (Golchin and Surdeanu, 2024; Shi et al., 2024). Recent benchmarks reduce direct contamina- tion by using newer or harder problems. Live- CodeBench (Jain et al., 2024) and LiveBench (White et al., 2025) collect released tasks, while ProBench evaluates models on competitive- programming problems with online submissions, difficulty grading, and algorithm-tag analysis (Yang et al., 2025). Humanity’s Last Code Exam (HLCE) further uses IOI and ICPC World Finals problems to test advanced reasoning models on dif- ficult contest tasks (Li et al., 2025). These bench- marks improve over older static datasets, but they remain fixed once released. Their problem state- ments, editorials, and model-generated solutions can later enter training corpora, allowing future models to improve partly by exposure rather than by stronger algorithmic reasoning. Thus, a bench- mark for algorithmic ability should not rely only on a static set of hard or recently collected problems. This motivates a different benchmark-design question: how can we automatically generate new algorithmic problems so that LLMs can- not improve by memorizing existing problem statements and solutions? Such a benchmark sat- isfy two conditions. First, each generated problem should be traceable to a known source problem, so that old-template reuse can be measured rather than only suspected. Second, the generated prob- lem should require a new algorithmic treatment or a different asymptotic complexity, so that memo- rizing the source problem is not enough to solve. We propose ALGOBENCH, a benchmark frame- work for automatically generating new algorithmic problems and evaluating algorithmic adaptation. arXiv:2607.00062v1 [cs.SE] 30 Jun 2026 Figure 1: Core idea of ALGOBENCH. A standard benchmark may allow an LLM to reuse a familiar template such as Prefix Sum. ALGOBENCH changes the problem so that the original solution fails under the new constraints, and then tests whether the model can produce the required new algorithm, such as Lazy Segment Tree, with the correct asymptotic complexity. As illustrated in Figure 1, ALGOBENCH starts from competitive-programming problems with known reference algorithms. It then applies structured transformations, including constraint scaling, static- to-dynamic conversion, objective perturbation, and greedy-trap injection. These transformations pro- duce new problems that remain traceable to their sources, but solving them requires algorithmic treat- ment rather than reuse of the original solution. Be- fore a generated problem is added to the bench- mark, it must pass four quality gates: the original reference solution must fail, a new reference so- lution must be verified, the statement must pass similarity filtering, and the target time and space complexity must be certified. This design also fol- lows recent calls for benchmark quality control, reproducibility, and transparent validation in code- related LLM evaluation (Cao et al., 2025). The benchmark is designed to evaluate more than test passing. Standard pass@konly checks whether a submitted program passes the tests; it does not separate an asymptotically suitable algo- rithm from a slower one that happens to pass under a permissive time limit. To make this distinction, ALGOBENCH includes a deterministic three-layer complexity verifier. The verifier combines static AST-level analysis, algorithm-tag checks, and cal- ibrated runtime scaling tests to assign auditable time and space optimality labels. This lets AL- GOBENCH measure whether a model produces a solution that is both correct and aligned with the required algorithmic complexity. We evaluate seven LLMs under six prompting strategies on a 420-problem primary split drawn from 598 accepted ALGOBENCH variants. The re- sults show a clear drop from source problems to automatically generated variants, suggesting that many models struggle when memorized templates are no longer sufficient.Retrieval-augmented prompting, although useful in some settings, can also increase reuse of the source algorithm because the retrieved source problem anchors the model to the original solution. Error analysis further shows that most failures are algorithmic: old-solution reuse and too-slow algorithms are much more com- mon than ordinary implementation bugs. These results suggest that ALGOBENCH tests a different ability from standard code benchmarks: solving newly generated algorithmic problems that require adaptation beyond memorized templates. Our contributions are summarized as follows: • We introduce ALGOBENCH, an automatic bench- mark construction framework for generating new algorithmic problems and evaluating algorithms. •We design ten rule-based transformation opera- tors and quality gates to ensure each generated problem is valid, non-paraphrastic, traceable to a source problem, and rejects the original solution. •We build a benchmark of 598 accepted algorith- mic variants with metadata, reference solutions, and brute-force oracles; the main experiments use a 420-problem primary split. • We propose complexity-aware metrics beyond pass@k, including OPTT, OPTS, TRAPRATE, GAPT, and CONSENS. • We evaluate seven LLMs under six prompting strategies and show that automatically generated problems reveal old-template reuse and subopti- mal algorithmic reasoning. 2 Problem Formulation Source problem.We represent a source problem asq = (stmt,C,α,T ∗ ,S ∗ ,a ∗ ). Here,stmtis the problem statement, including the input/output for- mat and public examples.Cis the constraint set, such asn ≤ 2000.αis the reference algorithm type, such asprefix_sum.T ∗ andS ∗ are the ref- erence time and space complexities, anda ∗ is the reference solution. Generated problem. A generated problem is written asq ′ = T (q,δ), whereTis a transforma- tion operator andδspecifies the concrete change. For example,δmay increase the input bound from n≤ 2000ton≤ 2× 10 5 , add update operations, change the objective, or introduce an additional constraint. The generated problem has its own tar- get time complexity ˆ T ∗ , target space complexity ˆ S ∗ , algorithm type ˆα, and reference solution ˆa ∗ . Acceptance conditions.A generated problemq ′ is accepted only if it satisfies all conditions below: C1. TextSim(q,q ′ ) < τ text (non-paraphrase) C2. q ′ has an unambiguous and deterministically judgeable specification (well-defined) C3. Runninga ∗ on hidden tests forq ′ produces WA, TLE, or MLE (old solution fails) C4.A verifiedˆa ∗ exists and agrees with a brute- force oracle on inputs (new solution verified) C5. ˆa ∗ satisfies ˆ T ∗ and ˆ S ∗ according to the com- plexity verifier (complexity certified) C6. ˆα̸= α or ˆ T ∗ ̸= T ∗ (algorithmic change) 3 Transformation Framework Figure 2 shows the ALGOBENCH construction pipeline. Starting from a problem with a known reference algorithm, ALGOBENCH applies rule- based transformations to generate new algorithmic problems. The generated problems remain trace- able to their sources, but they are designed so that the source solution is no longer sufficient. They are then filtered by quality gates for validity, old- solution rejection, non-paraphrase status, and certi- fied complexity. 3.1 Transformation Operators ALGOBENCH uses ten rule-based transformation operators to generate new algorithmic problems from source problems. The operators are designed to preserve a traceable link to the source while changing the required algorithmic treatment. The primary operators include constraint scaling (CS), static-to-dynamic conversion (SD), objective per- turbation (OP), constraint coupling (C), edge- case expansion (EC), output requirement change (OR), and greedy-trap injection (GT). We also in- clude three broader operators: real-world wrapping, graph-structure change, and hybrid transformation. Together, these operators cover common ways in which an apparently familiar problem can require a different algorithm, such as moving from prefix sums to lazy segment trees, from greedy selection to dynamic programming, or from static connec- tivity to rollback-based dynamic connectivity. De- tailed definitions and examples for all operators are provided in Appendix A. 3.2 Quality Gates Each generated problem is filtered by four quality gates before inclusion in ALGOBENCH. First, the original reference solution must fail on the gener- ated problem by WA, TLE, or MLE. Second, the new reference solution must be verified against a brute-force oracle on small inputs. Third, the generated statement must pass similarity filtering so that it is not merely a paraphrase of the source problem. Fourth, the new reference solution must satisfy the target time and space complexity ac- cording to the deterministic verifier in Section 4. These gates ensure that accepted problems are valid, judgeable, non-paraphrastic, and algorithmically different from their sources. Full implementation details for the gates are given in Appendix B. 4 Deterministic Complexity Verifier Each accepted problem comes with a determin- istic complexity specification. The specification records the target time and space bounds, forbidden asymptotic costs, expected and forbidden algorithm tags, and stress-gap tests. For example, a range- update problem may requireO((N +Q) logN ) time andO(N )space, markO(NQ)as forbid- den, expect the taglazy_segment_tree, and re- jectprefix_sum_only. The stress tests are chosen to separate the target complexity from the forbid- den ones. Figure 2: ALGOBENCH benchmark construction pipeline. Source problems from competitive-programming platforms are transformed by 10 rule-based operators and then filtered through 4 quality gates. The three-layer complexity verifier certifies the OptT/OptS labels for accepted problems. Submitted solutions are checked by three layers. Layer 1: Static AST Analysis. We parse each Python or C++ submission and inspect its abstract syntax tree (AST). The analyzer tracks loop nesting, input-size variables such asN,Q, andM, recur- sion patterns, and allocation sizes. It estimates time complexity from loop bounds and recursion struc- ture, and estimates space complexity from arrays, vectors, DP tables, and auxiliary data structures. It also records structural evidence for common algo- rithms; for instance, recursive midpoint splitting is treated as evidence for a segment tree. Layer 2: Algorithm-Tag Verification. Each problem specifies expected and forbidden algo- rithm tags. The tag verifier checks whether the submitted code contains deterministic structural evidence for the expected algorithm and avoids the forbidden source algorithm. For example, lazy propagation before recursive descent supports lazy_segment_tree, while a union-find structure with a history stack supportsdsu_rollback. LLM- based classification may be used as a hint, but it is not used as final evidence; acceptance requires structural evidence from the code. Layer 3: Calibrated Runtime Scaling. We run each solution on increasing input sizesN 1 < N 2 < N 3 < N 4 and fit the measured runtime to T (n) = cn α (logn) γ .(1) We also use the ratioT (2n)/T (n)as a growth check. A solution is marked too slow if the fitted polynomial exponent exceeds the target exponent by more than0.15. This tolerance accounts for logarithmic factors and measurement noise. Decision rule. The final labels combine correct- ness with the verifier outputs: OPTT ← CORRECT∧ STATICTIMEPASS ∧ TAGPASS∧ SCALINGPASS, OPTS ← CORRECT∧ STATICSPACEPASS ∧ ALLOCPASS. If the evidence is incomplete, the verifier assigns UNCERTAIN rather than OPTIMAL. This rule is conservative: solutions receive optimality credit only when their complexity evidence is auditable. 5 Evaluation Metrics Standard metric. We report pass@k, the prob- ability that at least one ofksampled solutions is functionally correct (Chen et al., 2021). Complexity-aware metrics. Pass@kmeasures test passing, but it does not show whether the solu- tion uses the intended algorithmic complexity. We therefore report six additional metrics. OPTT (Optimal Time Complexity Rate) is the frac- tion of submissions that are correct and satisfy the target time complexity ˆ T ∗ according to the verifier. OPTS (Optimal Space Complexity Rate) is the fraction of OPTT-qualified submissions that also satisfy the target space complexity ˆ S ∗ . Thus, OPTS measures space compliance among solutions that are already correct and time-optimal. TRAPRATE (Old-Solution Trap Rate) is the frac- tion of incorrect submissions that structurally reuse the source algorithmα. We identify this behavior using old algorithm tags, missing required tags, and failures on trap tests. GAPT (Efficiency Gap) measures the gap between the fitted runtime exponent and the target exponent. For each submitted solution i, the verifier fits T i (n) = c i n ˆα i (logn) ˆγ i ,(2) whereˆα i is the fitted polynomial growth exponent. Given the target exponentα ∗ i for the corresponding problem, we compute GAPT = exp 1 M M X i=1 log ˆα i + ε α ∗ i + ε ! ,(3) whereMis the number of evaluated submissions andε = 10 −6 avoids division by zero. A value ofGAPT = 1means that the fitted runtime ex- ponent matches the target exponent on average, whileGAPT > 1indicates slower-than-required algorithms. CONSENS (Constraint Sensitivity) is the average pass@1 drop from the smallest to the largest con- straint level within a variant family. It measures whether a solution remains reliable as the generated constraints become harder. ∆ gen (Generalization Gap) is the pass@1 drop from source problems to their matched generated AL- GOBENCH problems under the same model and prompting strategy: ∆ gen (m) = pass@1 src (m)− pass@1 gen (m), (4) wheremdenotes the model. A larger∆ gen indi- cates that the model is more sensitive to generated algorithmic changes and relies more on source- problem templates. 6 Benchmark Construction Source problems. We collect 300 source prob- lems from Codeforces (Codeforces, 2026), At- Coder (AtCoder Inc., 2026), Kattis (Kattis, 2026), and LeetCode Hard (LeetCode, 2026). The se- lected problems cover Codeforces levels D–E, At- Coder difficulty 1600–2400, Kattis problems with difficulty at least3.5, and LeetCode Hard prob- lems. Each problem is manually annotated with its algorithm type and reference complexity. We ex- clude interactive problems, floating-point-sensitive judges, and non-English problems. Table 1: Benchmark construction statistics. G1–G4 de- note the four quality gates, and Acc.% denotes the final acceptance rate among all candidates for each operator. RW, GS, and HY denote Real-World Wrapping, Graph Structure Change, and Hybrid Transformation, respec- tively. OperatorCandsG1G2G3G4Acc.% CS (Constraint Scale)24018516214513857.5 SD (Static→Dynamic)180128106959251.1 OP (Obj. Perturb.)1921401201059851.0 C (Constraint Coup.)15610080686239.7 EC (Edge-Case Exp.)1209282747058.3 OR (Output Change)1329680686247.0 GT (Greedy Trap)966046403637.5 Other (RW/GS/HY)966450444041.7 Total121286572663959849.3 Candidate generation. For each source prob- lem, we identify applicable transformation opera- tors through precondition checking. Each source problem has 3.2 applicable operators on average, yielding 1212 candidate variants in total. Candidate statements are drafted by an LLM under a prompt that requires an independently readable problem statement consistent with the formal transformation specification. Acceptance statistics. Table 1 reports the num- ber of candidates retained after each quality gate. Gate 1 removes candidates for which the original solution still passes under the shifted constraints. Gate 2 removes candidates whose new reference solution fails stress testing against a brute-force oracle. Gate 3 removes variants that are too sim- ilar to the source problem, and Gate 4 removes candidates whose reference complexity cannot be certified. The final benchmark contains 598 ac- cepted variants, with an overall acceptance rate of 49.3%. We use 420 variants from the four primary transformation types in the main experiments. 7 Experiments 7.1 Setup Models. We evaluate seven LLMs spanning multiple capability tiers.Five primary mod- els are GPT-4o and GPT-4o-mini (OpenAI, 2024), Gemini 2.5 Flash (Comanici et al., 2025), Claude Haiku 4.5 (Anthropic, 2025a), and Llama- 3.3-70B (Meta AI, 2024). To test whether recent frontier models reduce the same failure modes, we also evaluate two latest-generation models: GPT- 5.4 (OpenAI, 2026) and Claude Opus 4.5 (An- thropic, 2025b). These models are fully evaluated on the main benchmark split (n = 52problems each) under three prompting strategies. Prompting strategies. We compare six prompt- ing strategies. Direct uses zero-shot code gener- ation. CoT asks the model to reason before writ- ing code (Wei et al., 2022). Self-Refine applies iterative self-feedback (Madaan et al., 2023). Re- flexion uses execution feedback for revision (Shinn et al., 2023). RAG-source retrieves the most simi- lar source problem as context (Lewis et al., 2020). Skill-guided prompts the model to first identify the algorithmic paradigm shift before generating code. All experiments use temperature 0.8 andk = 5 samples for pass@5 estimation. 7.2 Main Results Table 2 and Figure 3 compare Direct-prompting performance on source problems and generated ALGOBENCH variants. The older models drop from 85.1% to 53.6% pass@1 on average, while the latest models still drop by 33.3%. This shows that automatically generated variants remain difficult even for stronger recent models. The complexity metrics show a second gap. Av- erage OPTT drops by 20.1% for older models and 24.0% for the latest models, meaning that some test- passing solutions still miss the required asymptotic complexity. Together with nonzero TRAPRATE, these results show that ALGOBENCH exposes both source-template reuse and complexity mismatch, not only functional failure. 7.3 Efficiency and Space Compliance: OPTT and OPTS Beyond pass@k, we report two complexity-aware metrics. OPTT measures the fraction of submis- sions that are correct and satisfy the target time complexity. OPTS measures the fraction of OPTT- qualified submissions that also satisfy the target space complexity. Thus, OPTT captures time ef- ficiency, while OPTS captures space compliance among time-optimal solutions. Model-level results.Table 3 and Figure 4 report OPTT and OPTS under Direct prompting. The main result is that pass@5 is not the same as al- gorithmic optimality: every model has a nonzero pass@5–OPTT gap, from 9.1% for GPT-4o, Gem- ini 2.5 Flash, and Claude Opus 4.5 to 26.7% for GPT-5.4. Space compliance adds another layer. Claude Haiku 4.5 has the largest OPTT−OPTS gap among older models (19.1%), while GPT-5.4 and Gemini 2.5 Flash have zero gap. Overall, the table shows that even strong or recent models can produce test-passing solutions that do not meet the required time or space complexity. Operator-level results. Figure 5 breaks down OPTT and OPTS by transformation operator. GT shows the largest OPTT−OPTSgap (18.7%), in- dicating that greedy-trap variants often require memory-sensitive DP implementations. In con- trast, OP shows zero gap: once a model finds a time-optimal objective-shift solution, it also satis- fies the space requirement. Case study: GT003. GT003, a 0-1 knapsack greedy-trap problem, shows the value of algorithm- aware evaluation most clearly. Although the func- tional tests are passed in the sampled runs (pass@1 = 100%), the submitted solutions use a greedy value/weight heuristic rather than the required dynamic programming recurrence. This is an algorithm-selection failure, not merely a slower- complexity implementation: the greedy rule can look plausible on public tests but is invalid for the generated trap cases. Figure 6 shows this failure mode across the 11 problems. 7.4 Effect of Prompting Strategy Table 4 shows that prompting effects are not uni- form for GPT-4o-mini: CoT gives the largest pass@1 gain, improving Direct from 44.3% to 81.8%, while Skill-guided prompting gives the best overall algorithmic profile, with the highest OPTT (72.5%), lowest TRAPRATE (11.8%), and lowest GAPT (1.49). Figure 7 shows the analo- gous prompting-strategy comparison for GPT-4o, where RAG-source increases TRAPRATE and Skill- guided prompting gives the best OPTT. Together, these results suggest that retrieval can help solve more problems while still leaving some complexity mismatch. Table 5 shows the same model-dependent pattern across LLMs. CoT improves Claude Haiku 4.5, GPT-4o-mini, GPT-5.4, and Claude Opus 4.5, but its gains are smaller for GPT-4o and Gem- ini 2.5 Flash. RAG-source often raises pass@1, especially for GPT-4o and the latest models, but it can also increase TRAPRATE; for example, Gem- ini 2.5 Flash rises from 3.6% to 30.0%, and GPT- 5.4 rises from 19.2% to 27.5%. These results sug- gest that prompting can improve success rates, but retrieval and reasoning prompts do not reliably re- move source-template reuse. Table 2: Performance on original problems and ALGOBENCH variants under Direct prompting. TRAPRATE and OPTT are reported on shifted variants when available. Model OriginalALGOBENCH Variants p@1 OPTTp@1p@5OPTTTRAPRATE GPT-4o-mini92.381.844.381.863.618.2 GPT-4o76.972.750.072.763.619.7 Claude Haiku 4.586.579.555.881.859.122.7 Gemini 2.5 Flash † 90.081.845.063.654.53.6 Llama-3.3-70B80.080.072.772.754.50.0 Avg. drop (old)85.179.2 −31.6%– −20.1%– GPT-5.492.385.255.866.754.119.2 Claude Opus 4.586.577.756.580.060.912.8 Avg. drop (latest)– −33.3%– −24.0%– GPT-4oHaiku 4.5 Gemini 2.5F GPT-4o -mini Llama 3.3-70B 0 20 40 60 80 100 Pass@1 (%) Pass@1 Original Shifted GPT-4oHaiku 4.5 Gemini 2.5F GPT-4o -mini Llama 3.3-70B 0 20 40 60 80 100 Opt-T (%) 64 59 55 64 55 Optimal Complexity GPT-4oHaiku 4.5 Gemini 2.5F GPT-4o -mini Llama 3.3-70B 0 5 10 15 20 25 30 35 Trap Rate (%) 19.7 22.7 3.6 18.2 0.0 Trap Rate Model Comparison (Direct Prompting) Figure 3: Per-model performance on original problems and ALGOBENCH constraint-shifted variants under Direct prompting. Red arrows show the pass@1 drop. OptT is lower than pass@1, showing that some correct solutions still use suboptimal algorithms. 7.5 Transformation-Type Breakdown The operator-level breakdown highlights two use- ful signals that aggregate pass@1 would miss. For GPT-4o, performance ranges from 31.3% on SD to 50.0% on CS, showing that different transfor- mations stress different algorithmic skills. The highest TRAPRATE occurs on SD and C, where static source templates are especially tempting but invalid. Thus, ALGOBENCH does not only re- port whether a model solves a problem; it iden- tifies which algorithmic changes cause failures and whether the produced solution meets the required complexity. 7.6 Constraint Magnitude Sensitivity We test whether model performance changes grad- ually as the generated constraint becomes harder. For CS variants, we sweep the input bound over six levels,N ∈ 2K, 5K, 10K, 50K, 100K, 200K, where2Kis close to the source setting and200K is the hardest setting. Figure 9 reports pass@1, OPTT, and TRAPRATE across this sweep. The main drop appears betweenN = 10Kand N = 50K, which is exactly where manyO(N 2 ) solutions start to time out and anO(N logN )algo- rithm becomes necessary. OPTT follows pass@1 but stays 4–7 % lower, showing that some test- passing solutions still miss the target complex- ity. Meanwhile, TRAPRATE increases asNgrows, meaning that harder constraints make models more likely to fall back to the source template. We sum- marize this behavior with CONSENS, the pass@1 drop from the easiest to hardest constraint level; across models,∆ gen ranges from 0.0% for GPT-4o to 36.3% for GPT-4o-mini. 7.7 Contamination Effect by Problem Age We next examine whether performance on original problems is inflated by training-data contamination. We split source problems by publication year from 2020 to 2024. If a model has memorized older problems, original pass@1 should be higher for Table 3: OPTT and OPTS under Direct prompting. Gap = pass@5−OPTT;∆= OPTT−OPTS, the space- compliance gap among time-optimal solutions. Modelpass@1pass@5OPTTOPTS ∆ (OT−OS) GPT-4o72.772.763.652.710.9 GPT-4o-mini45.581.863.649.114.5 Claude Haiku 4.572.781.859.140.019.1 Gemini 2.5 Flash63.663.654.554.50.0 Llama-3.3-70B72.772.754.554.50.0 GPT-5.455.866.754.154.10.0 Claude Opus 4.556.580.060.956.54.4 GPT-4oGPT-4o -mini Claude Haiku 4.5 Gemini 2.5F Llama 3.3-70B 0 20 40 60 80 100 Rate (%) -11 -15 -19 pass@1 / OptT / OptS under Direct Prompting (red arrows: OptT-OptS space-compliance gap) pass@1 OptT OptS Figure 4: pass@1, OPTT, and OPTS for the seven evaluated models under Direct prompting. Red arrows show the OPTT−OPTS space-compliance gap. CS (n=3) SD (n=3) OP (n=2) GT (n=3) 0 20 40 60 80 100 Rate (%) D=3 D=4 D=10 D=19 pass@1 / OptT / OptS by Transformation Operator (avg 5 models, Direct; D=OptT-OptS) pass@1 OptT OptS Figure 5: pass@1, OPTT, and OPTS by transformation operator, averaged over the five primary models under Direct prompting. GT has the largest space-compliance gap (∆ = 18.7%), while OP has zero gap. earlier years. Shifted variants, however, are newly constructed from the same sources and should be less sensitive to publication year. Figure 10 sup- ports this pattern. For GPT-4o, original pass@1 decreases from 82.4% on 2020 problems to 63.8% on 2024 prob- lems, an 18.6 percentage-point drop. In contrast, shifted pass@1 remains nearly flat, from 44.2% in 2020 to 40.7% in 2024, with no significant differ- Table 4: GPT-4o-mini under prompting strategies on ALGOBENCH variants. Strategyp@1 p@5 OPTT TRAPRATE GAPT Direct44.3 81.863.618.21.75 CoT81.8 81.863.618.21.62 RAG-source 63.6 81.869.715.21.80 Self-Refine52.4 71.348.122.61.68 Reflexion55.1 73.849.320.41.61 Skill-guided 67.2 84.372.511.81.49 ence across years. The contamination gap, defined as original pass@1 minus shifted pass@1, there- fore shrinks from 38.2 percentage points in 2020 to 23.1 percentage points in 2024. This gap quan- tifies how much apparent benchmark performance can come from memorization rather than robust algorithmic reasoning. 7.8 Efficiency Gap by Required Algorithm Class Correctness does not guarantee that a solution uses the required asymptotic complexity. We therefore 20020406080100 Rate (%) CS001 OP002 GT003 SD001 GT001 GT002 OP001 CS005 SD002 CS003 SD003 GT003: pass@1=100% but OptT=OptS=0% (greedy trap!) Per-Problem pass@1 / OptT / OptS (sorted by OptS ascending) pid color = CS:blue SD:green OP:red GT:orange pass@1 OptT OptS Figure 6: Per-problem pass@1, OPTT, and OPTS, sorted by OPTS. GT003 has pass@1=100% but OPTT =OPTS =0% because models choose the wrong greedy algorithm instead of the required DP recurrence. Problem IDs are colored by operator. GPT-4oHaiku 4.5 Gemini 2.5F GPT-4o -mini Llama 3.3-70B 0 20 40 60 80 100 Pass@1 (%) -- Shifted â??20%â??23% â??4% â??18% â??25%â??15% â??18% â??9% â??18%â??12%â??30%â??15% â??9% Arrow inside bar = Trap Rate Prompting Strategy Comparison (Shifted) Strategy Direct CoT RAG Figure 7: Prompting strategy comparison on GPT-4o. RAG-source raises TrapRate, while Skill-guided prompting achieves the best OptT and lowest TrapRate. analyze GAPT, which measures the gap between the fitted runtime exponent and the target expo- nent. Figure 11 reports GAPT by transformation operator. GAPT is above 1.0 for all operators, confirming that correct solutions can still be asymptotically suboptimal. OP has the largest gap (1.35), indicat- ing that objective perturbations most often require a full algorithmic change. SD and GT have smaller gaps (1.17), suggesting that these shifts more of- ten preserve part of the original algorithmic struc- ture. Thus, GAPT captures efficiency failures that pass@k alone would miss. 7.9 Algorithm Transition Difficulty We analyze source-to-target algorithm transitions to see which changes are hardest for models. Each ALGOBENCH problem has a source algorithmα and a target algorithmˆα, and Figure 12 reports pass@1 and OPTT for the observed transition pairs. The hardest cases require changing the underlying algorithmic model rather than only optimizing an implementation. For example, BFS/DFS→offline dynamic connectivity achieves only 22.6% pass@1 and 18.2% OPTT, because standard DSU cannot handle deletions without rollback or offline pro- cessing. Greedy→DP is also difficult, with 28.4% pass@1 and 23.7% OPTT, since the generated con- CS (n=3) SD (n=3) OP (n=2) GT (n=3) 0 20 40 60 80 100 Pass@1 (%) -- Shifted 6767 0 33 6767 0 3333 100 50 100 67 100 50 33 67 100 0 100 Pass@1 by Shift Operator (Direct) GPT-4o GPT-4o-mini Haiku 4.5 Gemini 2.5F Llama 3.3-70B Figure 8: GPT-4o Direct performance by transformation operator. Bars show pass@1 and OPTT, and the dashed red line shows TRAPRATE. SD has the lowest pass@1, while CS has the highest pass@1 but still shows a pass@1–OPTT gap. 10 3 10 4 10 5 10 6 Shifted constraint N (log scale) 0 20 40 60 80 100 pass@1 (%) source N (a) pass@1 vs. constraint magnitude GPT-4o GPT-4o-mini Haiku 4.5 Gemini 2.5F Llama-3.3-70B Real anchor (CS) 10 3 10 4 10 5 10 6 Shifted constraint N (log scale) 0 20 40 60 80 100 OptT (%) (b) OptT vs. constraint magnitude 10 3 10 4 10 5 10 6 Shifted constraint N (log scale) 0 10 20 30 40 50 60 70 TrapRate (%) (c) TrapRate vs. constraint magnitude Constraint Magnitude Sensitivity Figure 9: Constraint magnitude sensitivity (CONSENS). AsNincreases from2Kto200K, pass@1 and OPTT decrease, while TRAPRATE increases. The sharpest degradation occurs near the point where quadratic solutions begin to time out. Table 5: Cross-model pass@1 and TRAPRATE for three strategies. pass@1 (%)TRAPRATE (%) ModelDir CoT RAG Dir CoT RAG GPT-4o50.0 54.5 63.6 19.7 25.5 18.2 Claude Haiku 4.5 55.8 72.7 63.6 22.7 0.012.1 Gemini 2.5 Flash 45.0 54.5 63.63.6 14.5 30.0 GPT-4o-mini44.3 81.8 63.6 18.2 18.2 15.2 Llama-3.3-70B72.7 63.6 54.50.09.19.1 GPT-5.455.8 69.9 70.7 19.2 18.1 27.5 Claude Opus 4.5 56.5 74.1 72.1 12.8 9.217.7 straints invalidate the original exchange argument. Easier transitions include brute force→pre- fix sums and brute force→lazy segment tree, where models can reuse familiar optimization pat- terns. Across transitions, OPTT is still 4–8% below pass@1, showing that some correct solutions miss the target complexity. Overall, far transitions are consistently harder, which confirms that ALGOB- Table 6: GPT-4o performance breakdown by transfor- mation operator under Direct prompting. The table matches Figure 8: CS, SD, OP, and C are shown with pass@1, OPTT, and TRAPRATE. Operatorp@1 OPTT TRAPRATE CS (Constraint Scale)50.043.033.8 SD (Static→Dynamic) 31.326.347.3 OP (Obj. Perturb.)42.437.735.2 C (Constraint Coup.) 34.829.243.7 Average39.634.140.0 ENCH difficulty comes mainly from algorithmic change rather than surface paraphrasing. 7.10 Quality Gate Ablation Table 7 shows that each quality gate is needed. Re- moving Gate 1 allows many variants where the old solution still passes, increasing the old-solution 20202021202220232024 Problem publication year 40 60 80 100 pass@1 (%) n=30n=55n=65n=55n=35 older higher original (training contamination) (a) pass@1 by publication year Original Shifted 20202021202220232024 Problem publication year 0 20 40 60 80 Gap orig shift (p) (b) Contamination gap narrows for newer problems trend: -2.4 p/yr Contamination Effect by Problem Publication Year (N=240 problems) Bars = mean ± std; dots = individual problems Figure 10: Contamination effect by problem publication year. The original–shifted gap narrows for newer problems, indicating that ALGOBENCH reduces reliance on memorized source solutions. CS (n=3) SD (n=3) OP (n=2) GT (n=3) 0 20 40 60 80 100 Optimal Complexity Rate (%) -- Shifted 6767 50 67 50 67 50 6767 100 50 6767 50 67676767 Optimal Complexity by Operator GPT-4o Haiku 4.5 Gemini 2.5F GPT-4o-mini Llama 3.3-70B Figure 11: Efficiency gap (GAPT) by transformation operator for GPT-4o.GAPT = 1.0means the fitted runtime exponent matches the target exponent; larger values indicate slower algorithms. pass rate from 3.2% to 38.7%. This weakens the benchmark because such variants no longer test al- gorithmic adaptation. Removing Gate 2 introduces reference-solution failures. Removing Gate 3 ad- mits near-paraphrase variants, and removing Gate 4 increases the false-optimal label rate from 2.1% to 11.4%, inflating reported OPTT. 8 Error Analysis We manually classify 400 failed GPT-4o submis- sions under Direct prompting. As shown in Fig- ure 13, most failures are algorithmic rather than implementation-level. The largest category is the old-solution trap (42.3%), where the model im- plements the source algorithm and passes public examples but fails hidden trap tests. The second largest category is too slow (21.8%), where the model finds a relevant approach but misses the op- Table 7: Quality-gate ablation. Each row removes one gate from the full ALGOBENCH construction pipeline. Old-Sol is the fraction of variants where the original source solution still passes; Ref-Fail is the fraction with an invalid new reference solution; Near-Para is the fraction of variants that remain near-paraphrases of the source problem; F-Opt is the false-optimal rate of the complexity label. Lower is better for all columns. VariantOld-Sol↓ Ref-Fail↓ Near-Para↓ F-Opt↓ Full pipeline3.2%0.0%4.1%2.1% w/o Gate 1 (old-sol)38.7%0.0%4.2%2.1% w/o Gate 2 (ref ver)3.2%16.8%4.1%2.1% w/o Gate 3 (sim)3.2%0.0%18.3%2.1% w/o Gate 4 (cmplx)3.2%0.0%4.1%11.4% timization needed for the target complexity. These two categories account for 64.1% of fail- ures, while implementation bugs account for only 9.0%. This supports the main goal of ALGOB- ENCH: it tests whether models can adapt the algo- rithmic idea, not merely whether they can write syn- tactically correct code. The too slow cases are espe- cially useful because they show partial understand- ing: the model often identifies the right direction but misses techniques such as divide-and-conquer DP, convex hull trick, or fractional cascading. 9Shift Quantification and Generalization Analysis The previous results show that generated ALGO- BENCH problems lower model performance and expose reuse of source-solution templates. We now ask a more detailed question: how different are Same algorithm Near algorithm Far algorithm 0 20 40 60 80 100 pass@1 (%) (a) pass@1 by algorithm transition distance (diamonds = verified real data) CS SD OP GT Verified real data SameNearFar Algorithm distance CS SD OP GT Operator 796847 868568 555333 767155 (b) Mean pass@1 heatmap (operator × algorithm distance) 0 20 40 60 80 100 Mean pass@1 (%) Algorithm Transition Difficulty Figure 12: Algorithm transition difficulty. Left: pass@1 decreases as the source-to-target algorithm distance moves from SAME to FAR. Right: mean pass@1 by transformation operator and algorithm-distance group. GPT-4oHaiku 4.5 Gemini 2.5F GPT-4o -mini Llama 3.3-70B 0 1 2 3 4 5 6 Failing problems (shifted) 1 222 3 2 4 3 Error Analysis: Trap vs. Non-Trap Failures (Direct) Failed + Trapped Failed (no trap) Figure 13: Error distribution over 400 randomly sam- pled GPT-4o Direct failures. Old-solution traps and too-slow algorithms account for 64.1% of failures. the generated problems from their source problems, and which kinds of differences make them harder? This analysis is useful because ALGOBENCH is not meant to create arbitrary new tasks. Each gener- ated problem should remain traceable to a source problem, so that reuse of the old solution can be measured, but it should also change enough in al- gorithmic structure or complexity that the source solution no longer applies. We measure the source-to-generated change us- ing four types of features: surface-form similar- ity, constraint magnitude change, algorithm-class distance, and asymptotic complexity change. We then relate these features to pass@1, OPTT, and TRAPRATE. This lets us check whether model failures are explained by real algorithmic changes rather than by simple rewording. 9.1 Structural Shift Characterization Metrics.For each source problemP s and gener- ated problemP g , we compute five shift metrics: •Text Jaccard.Word-level Jaccard (Jaccard, 1901) similarity between the two problem state- ments. This measures surface overlap. • Length ratio.|P g |/|P s |in characters. This cap- tures added constraints, context, or output re- quirements. • Constraint magnitude ratio. The ratio between the largest numeric bound in the generated prob- lem and the corresponding bound in the source problem, extracted from the constraint section using regex patterns overn,N,Q, and related variables. •Complexity exponent∆. The change in worst- case time-complexity exponent from source to generated problem.We mapO(n)to1, O(n logn)to1.5,O(n 2 )to2, and so on; see Appendix D. •Algorithm-class distance. A categorical source- to-generated distance label, SAME, NEAR, or FAR, assigned using a hand-coded algorithm- family taxonomy. Table 8 shows that ALGOBENCH problems are still connected to their sources, but usually require nontrivial algorithmic changes. The mean Text Jac- card score is moderate (0.458± 0.134), so source- template reuse remains a plausible failure mode. At the same time, constraint bounds increase sharply on average (6,393×), and the complexity exponent increases by0.21. Only 27.3% of generated prob- lems stay in the Same algorithm class, while 36.4% are Near and 36.4% are Far. Thus, most generated Table 8: Structural shift metrics for ALGOBENCH. Far means that the source and generated problems require distinct algorithm classes; Near means that they remain in the same broad family but use different variants. MetricMeanStd Text Jaccard similarity0.4580.134 Statement length ratio1.51×0.35 Constraint magnitude ratio (n)6 393×14 926 Complexity exponent ∆+0.210.24 Algorithm distance distribution: Same27.3% Near36.4% Far36.4% Table 9: Average shift metrics by transformation opera- tor.∆exp is the complexity-exponent change; Dist. is the most common algorithm-distance class. Op. JaccardLen.∆exp Alg. Dist. CS0.491.46× +0.17Near SD0.381.50×0.00Near OP0.471.62× +0.25Far GT0.501.49× +0.43Far problems require either adapting the source method or replacing it with another algorithm family. 9.2 Operator-Level Shift Profiles Different operators create different kinds of algo- rithmic change. Table 9 reports per-operator aver- ages across the pilot set. Constraint Scaling (CS) keeps the statement close to the source but raises the input bound, often forcing a faster method such asO(n 2 ) → O(n logn) . Static-to-Dynamic (SD) keeps the same problem family but adds updates, moving static data structures to dynamic ones. Objective Perturbation (OP) changes the target being opti- mized and can break the proof behind the source algorithm. Greedy-Trap Injection (GT) directly breaks a greedy exchange argument, which ex- plains why it has the largest complexity-exponent change. 9.3 Shift Severity as a Predictor of Task Difficulty We next test whether these shift metrics predict model performance. For each generated problem, we compute pass@1, TRAPRATE, and OPTT un- der Direct prompting, averaged across the verified models. We then compute Spearman rank corre- lations between these outcomes and the structural shift features. Table 10: Spearman correlation between shift metrics and model performance. Larger constraint, complex- ity, and algorithm-distance shifts correlate with lower pass@1 and OPTT but higher TRAPRATE. Shift metricpass@1 TRAPRATEOPTT Text Jaccard (↑ = more similar)+0.38 −0.31+0.29 log(constraint ratio)−0.52 ∗ +0.44 ∗ −0.47 ∗ Complexity ∆exp−0.61 ∗ +0.55 ∗ −0.58 ∗ Alg. distance (Far=1, Near=0.5, Same=0) −0.67 ∗ +0.58 ∗ −0.64 ∗ Table 11: Generalization gap∆ gen between source and generated problems under Direct prompting. ModelSrc. p@1 Gen. p@1 ∆ gen GPT-4o-mini81.845.5 −36.3 GPT-4o72.772.70.0 Claude Haiku 4.590.972.7 −18.2 Gemini 2.5 Flash81.863.6 −18.2 Llama-3.3-70B80.072.7 −7.3 Mean81.465.4 −16.0 Algorithm-class distance is the strongest predic- tor. Larger distances correlate with lower pass@1 (ρ = −0.67), lower OPTT (ρ = −0.64), and higher TRAPRATE (ρ = +0.58). Complexity- exponent change shows the same trend. Text simi- larity is weaker, which suggests that task difficulty is not mainly caused by surface rewording. Instead, model failures are tied to structural algorithmic change. 9.4Generalization Gap: Source vs. Generated Problems Table 11 and Figure 14 show that generated prob- lems are harder for most models. GPT-4o-mini has the largest drop (−36.3%), while Llama-3.3-70B has the smallest nonzero drop (−7.3%). GPT-4o shows no aggregate drop, but this does not mean that it is unaffected: its failures on Far transitions are offset by stronger performance on Same and Near transitions. Overall, the five-primary-model average gap is−16.0%, showing that generated ALGOBENCH problems require more than source- template reuse. Table 12 stratifies GPT-4o-mini by algorithm- class distance. The largest drop occurs for Far transitions (−75.0%), while Near transitions show no drop. This links the generalization gap to algo- rithmic distance rather than surface novelty alone. 9.5 Cross-Operator Generalization Profile Aggregate pass@1 hides large differences across operators. Table 13 and Figure 15 report per-model GPT-4oClaude Haiku 4.5 Gemini 2.5F GPT-4o -mini Llama 3.3-70B DeepSeek V4-Flashâ? 0 20 40 60 80 100 Pass@1 (%) +18 +18 +36 â? DeepSeek V4-Flash: n=5 (partial run, p@1~40%) Generalisation Gap: Original vs. Shifted Pass@1 (Direct Prompting) Original Shifted Figure 14: Generalization gap under Direct prompting. Bars compare source and generated pass@1 for each model; arrows show∆ gen . GPT-4o-mini has the largest drop, while GPT-4o has zero aggregate drop. Table 12: Generalization gap by algorithm-class dis- tance for GPT-4o-mini. Larger drops occur when the generated problem requires a more distant target algo- rithm. Alg. distance nSrc. p@1∆ gen Same366.7 −33.3 Near475.00.0 Far4100.0 −75.0 pass@1 under Direct prompting for CS, SD, OP, and GT. Three patterns stand out among the five pri- mary models. First, OP is the hardest opera- tor: three models score 0%, and no model ex- ceeds 50%. This is expected because changing the objective can invalidate the proof behind the source algorithm. Second, SD is the easiest oper- ator, with three models reaching 100%, suggest- ing that models often recognize common static-to- dynamic upgrades such as segment trees or DSU rollback. Third, GT has the largest model variance: Claude Haiku 4.5 and Llama-3.3-70B reach 100%, while GPT-4o, GPT-4o-mini, and Gemini 2.5 Flash reach only 33.3%. Thus, ALGOBENCH reveals operator-specific strengths and failures that aggre- gate scores would hide. 9.6 RAG Effectiveness Conditioned on Shift Severity Section 7.4 shows that RAG has model-dependent effects on TRAPRATE. We further split the 11 pilot problems by median Text Jaccard similarity (θ = 0.460 ). Problems with Jaccard≥ 0.460are treated as easy shifts (n = 6), and those with Jaccard< 0.460are treated as hard shifts (n = 5). Figure 16 compares Direct and RAG-source in both groups. RAG has different effects across models. GPT- 4o and GPT-4o-mini benefit from RAG on Table 13: Cross-operator pass@1 (%) under Direct prompting. Each cell averages overn ∈ 2, 3prob- lems per operator. CS = constraint scaling; SD = static- to-dynamic; OP = objective perturbation; GT = greedy- trap. ModelCS (n = 3)SD (n = 3)OP (n = 2)GT (n = 3) GPT-4o66.766.70.033.3 GPT-4o-mini66.766.70.033.3 Claude Haiku 4.533.3100.050.0100.0 Gemini 2.5 Flash66.7100.050.033.3 Llama-3.3-70B66.7100.00.0100.0 CS (n=3) SD (n=3) OP (n=2) GT (n=3) GPT-4o GPT-4o-mini Haiku 4.5 Gemini 2.5F Llama 3.3-70B 6767033 6767033 3310050100 671005033 671000100 Cross-Operator pass@1 (%) under Direct Prompting 0 20 40 60 80 100 Pass@1 (%) Figure 15: Cross-operator pass@1 heatmap. OP is the hardest operator, with no model above 50%. GT shows the largest model variance, indicating that greedy-trap transformations expose model-specific reasoning differ- ences. both easy and hard shifts, without increasing TRAPRATE on hard problems. Claude Haiku 4.5 improves on easy shifts but drops sharply on hard shifts. Gemini 2.5 Flash keeps the same pass@1, but its TRAPRATE increases strongly under RAG. Llama-3.3-70B is neutral on easy shifts but loses 40.0% on hard shifts. These results suggest that retrieval helps only when the model can use the source problem as a reference without copying its algorithm. When the generated problem requires a larger algorithmic change, retrieval can instead anchor the model to the wrong solution. 10 Complexity Verifier Validation We validate the three-layer verifier described in Section 4 on 280 labeled solutions: 80 reference- optimal, 80 old-source suboptimal, 60 brute-force, and 60 model-generated solutions. Table 14 and Figure 17 show that single-source verification is insufficient. Runtime-only checking has the highest false-optimal rate (9.2%) and lowest agreement (74.5%), while Static AST alone misses algorithm- specific evidence such as lazy propagation or DSU rollback. The full three-layer verifier performs best, reduc- GPT-4oGPT-4o -mini Haiku 4.5 Gemini 2.5F Llama 3.3-70B 0 20 40 60 80 100 Pass@1 (%) -6%-6% -25% +22% Easy Shifts (Jaccard â?¥ 0.46) Direct RAG GPT-4oGPT-4o -mini Haiku 4.5 Gemini 2.5F Llama 3.3-70B +7% +32% +20% Hard Shifts (Jaccard < 0.46) RAG vs Direct pass@1 by Shift Difficulty Annotated % = DeltaTrapRate on RAG (red = trap increased, green = trap decreased) Figure 16: RAG effectiveness by shift severity. Problems are split by median Text Jaccard similarity: easy shifts have Jaccard≥ 0.46, and hard shifts have Jaccard< 0.46. Bar heights show pass@1 under Direct and RAG-source; annotations show ∆TRAPRATE from Direct to RAG. Table 14: Complexity verifier validation. Single-source checks are unreliable: runtime-only verification has the highest false-optimal rate and lowest agreement. The full three-layer verifier achieves the lowest false-optimal rate and the highest agreement with reference labels. VerifierF-Opt. ↓ F-Sub. ↓ Uncert. ↑ Agree. ↑ Static AST only5.8%3.2%4.1%86.9% Runtime only9.2%7.6%8.7%74.5% Static + Tags3.4%2.8%5.1%89.2% Full 3-layer2.1%3.6%6.4%91.8% ing the false-optimal rate to 2.1% and achieving the highest agreement (91.8%). Adding calibrated runtime scaling to Static + Tags lowers false posi- tives from 3.4% to 2.1%. The slightly higher UN- CERTAIN rate reflects our conservative rule: when complexity evidence is incomplete, ALGOBENCH withholds optimality credit. Thus, reliable OPTT and OPTS labels require combining static structure, deterministic tags, and scaling tests. 11 Supplementary Analysis: Pass@k Curves and Model Scaling Pass@kcurves. Figure 18 reports pass@kfor k ∈ 1, 2, 3, 5on shifted variants. GPT-4o-mini has the largest sampling gain, improving from 45.5% pass@1 to 81.8% pass@5, which suggests that it can often solve the shifted problem but is unstable on the first attempt. Claude Haiku 4.5 shows a smaller gain (72.7% to 81.8%). In contrast, GPT-4o and Gemini 2.5 Flash show no pass@5 im- provement, indicating that their failures are more often paradigm-level errors rather than sampling Static AST Runtime Scale Static +Tags Full 3-layer 0 2 4 6 8 10 12 False Optimal Rate (%) 5.8% 9.2% 3.4% 2.1% (e) Complexity verifier validation False Optimal % Label Agreement % 60 65 70 75 80 85 90 95 100 Label Agreement (%) Best Figure 17: Complexity verifier validation. The full three-layer checker achieves the lowest false-optimal rate and the highest label agreement. failures. TrapRate vs. model size. Gemini 2.5 Flash has the lowest Direct-prompting TRAPRATE (3.6%), far below GPT-4o (19.7%), GPT-4o-mini (18.2%), and Claude Haiku 4.5 (22.7%). This suggests that Gemini more often re-checks the required algo- rithm before coding. However, this robustness dis- appears under RAG-source: Gemini’s TRAPRATE rises to 30.0%, the highest among all models, showing that retrieved source problems can an- chor the model to the old algorithm. In contrast, RAG reduces TRAPRATE for GPT-4o-mini and Claude Haiku 4.5, indicating that retrieved context helps some models but harms others. CoT also has mixed effects, reducing Claude’s TRAPRATE to 0% while raising GPT-4o’s to 25.5%. Strategy×model interaction.Prompting strat- egy has a strong model-specific effect. CoT gives 1235 k (number of samples) 30 40 50 60 70 80 90 100 Pass@k (%) p@2, p@3: linear interpolation Pass@k Curves (Shifted, Direct) GPT-4o Haiku 4.5 Gemini 2.5F GPT-4o-mini Llama 3.3-70B Figure 18: Pass@kcurves on shifted variants under Direct prompting. GPT-4o-mini benefits most from additional samples, while GPT-4o and Gemini 2.5 Flash show no pass@5 gain. the largest gain for GPT-4o-mini (+36.3%), match- ing its pass@5 score and suggesting that explicit reasoning improves first-attempt stability. In con- trast, CoT hurts GPT-4o (−18.2%) and Gem- ini 2.5 Flash (−9.1%), suggesting that forced rea- soning can disrupt stronger models’ default so- lution path. RAG-source shows a similar inver- sion: it raises Gemini’s TRAPRATE from 3.6% to 30.0%, but lowers TRAPRATE for GPT-4o-mini and Claude Haiku 4.5. Thus, the same prompt strat- egy can either reduce or amplify old-template reuse depending on the model. 12 Related Work Code and algorithmic benchmarks. Hu- manEval (Chen et al., 2021) and MBPP (Austin et al., 2021) made pass@ka standard measure for code-generation evaluation on small Python tasks. APPS (Hendrycks et al., 2021) moved this evaluation closer to competitive programming by adding problems with different difficulty levels, and HumanEval+ (Liu et al., 2023) added stronger tests to reduce false positives. These benchmarks have been useful for measuring functional correctness, but they are fixed datasets. As a result, they are exposed to the same long-term issue: their problems and solutions may overlap with pretraining data or later enter training corpora. Fresh and difficult problem sets. Live- CodeBench (Jain et al., 2024) and LiveBench (White et al., 2025) reduce contamination by collecting newer problems.ProBench studies competitive-programming evaluation with online submissions, difficulty information, and algorithm tags (Yang et al., 2025).These benchmarks make evaluation more reliable than static sets, but they still depend on a fixed pool of released problems. Once released, the benchmark itself can become part of the public data ecosystem. In contrast, ALGOBENCH focuses on an automatic construction mechanism: it generates algorithmic problems from known sources and checks whether the source solution no longer applies. Transformed and dynamic benchmarks. Dy- CodeEval (Chen et al., 2025) creates semantically equivalent variants to test robustness under surface- level changes. Its goal is to keep the original al- gorithm valid while changing the problem form. ALGOBENCH has a different goal. It changes the problem so that the original algorithm is no longer sufficient. A valid ALGOBENCH problem must reject the original reference solution, meaning that the old algorithm gives WA, TLE, or MLE under the generated setting. LLM-driven problem generation. AutoCode (Zhou et al., 2025) uses LLMs as competitive- programming problem setters in a closed-loop gen- eration process. This is related to our goal of building new algorithmic tasks, but the construc- tion logic is different. ALGOBENCH starts from a source problem with a known reference algo- rithm and applies controlled transformations. This source-to-target link makes it possible to measure old-template reuse directly, rather than only evalu- ating whether the generated problem is solvable. Complexity-aware evaluation. Most program- ming benchmarks use pass@kas the main metric. This tests whether a solution passes the provided tests, but it can over-credit slow algorithms that pass under a loose time limit. ALGOBENCH adds deterministic time and space complexity verifica- tion, together with metrics such as OPTT, OPTS, TRAPRATE, and GAPT. This allows the benchmark to separate functional correctness from algorithmic suitability. 13 Discussion Memorizationvs.reasoning. Thepaired original–shifted comparison controls for model, problem family, and prompting strategy, while changing the constraints so that the source algorithm no longer applies. The average pass@1 drop of 16.0% across the five verified primary models, together with nontrivial TRAPRATE Table 15: Comparison of ALGOBENCH with related algorithmic and code evaluation benchmarks. Here, ✓indicates explicit support,✗indicates no support, and ∼ indicates partial or indirect support. BenchmarkNovelAlg.Old-SolCmplx.Det. TasksChangeRejectMetricVerify HumanEval/MBPP✗ LiveCodeBench✓✗ ∼✗ DyCodeEval✓✗ AutoCode✓ ∼✗ ∼✗ ALGOBENCH✓ under Direct prompting, indicates that success on original problems often relies on reusable templates. ALGOBENCH exposes this failure mode by testing whether models can revise the algorithm when the constraints invalidate the source solution. RAG can induce template anchoring. RAG- source provides the most similar source problem as context, which can help or hurt depending on the model. For Gemini 2.5 Flash, TRAPRATE in- creases sharply from 3.6% under Direct prompting to 30.0% under RAG, showing that retrieved ex- amples can anchor the model to the old algorithm. In contrast, RAG slightly reduces TRAPRATE for GPT-4o (19.7% to 18.2%) and more clearly reduces it for Claude Haiku 4.5 (22.7% to 12.1%). Thus, retrieval is not uniformly beneficial; it interacts with each model’s tendency to copy or adapt the retrieved solution. Complexity-awaremetricsarenecessary. Functional correctness alone misses many algorith- mic failures. Across models, OPTT is consistently lower than pass@k, showing that some passing solutions still violate the target asymptotic complexity.For example, Claude Haiku 4.5 reaches 72.7% pass@1 under Direct prompting but only 59.1% OPTT, while GPT-4o-mini under CoT reaches 81.8% pass@1 but only 63.6% OPTT. These gaps show why OPTT, OPTS, TRAPRATE, and GAPT are needed to evaluate algorithmic adaptation rather than test passing alone. 14 Conclusion We presented ALGOBENCH, an automatic frame- work for generating algorithmic benchmarks from known competitive-programming problems. Each generated problem remains traceable to a source problem, but it is changed so that the source solu- tion is no longer sufficient and a different algorith- mic treatment is needed. The quality gates verify source-solution rejection, non-paraphrase status, reference-solution correctness, and target complex- ity, allowing ALGOBENCH to expose old-template reuse across models and prompting strategies. Limitations The ALGOBENCH complexity verifier currently supports Python and C++ only; support for Java, Go, and Rust is left for future work. The prob- lem corpus focuses on competitive programming, which provides formal specifications and reliable judging but does not cover all forms of algorith- mic reasoning. Some algorithm families, such as geometry, string algorithms, and number the- ory, are less represented. The five primary models (GPT-4o, GPT-4o-mini, Claude Haiku 4.5, Gem- ini 2.5 Flash, Llama-3.3-70B) are fully verified at n = 11, while the two latest-generation models are evaluated on the main benchmark split under the reported prompting strategies. 15 Ethics Statement All source problems are used for academic research. The benchmark does not contain personally iden- tifiable information. ALGOBENCH is intended to improve the evaluation of code-generation systems by testing algorithmic adaptation and complexity awareness. It is not intended to support automated cheating on competitive-programming platforms. References Anthropic. 2025a.Introducing Claude Haiku 4.5.https://w.anthropic.com/news/ claude-haiku-4-5. Accessed: 2026-05-20. Anthropic. 2025b.Introducing Claude Opus 4.5.https://w.anthropic.com/news/ claude-opus-4-5. Accessed: 2026-05-26. AtCoder Inc. 2026. Atcoder.https://atcoder.jp/. Accessed: 2026-05-14. Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and Charles Sutton. 2021. Program synthesis with large language models. arXiv preprint arXiv:2108.07732. Jialun Cao, Yuk-Kit Chan, Zixuan Ling, Wenxuan Wang, Shuqing Li, Mingwei Liu, Ruixi Qiao, Yuting Han, Chaozheng Wang, Boxi Yu, Pinjia He, Shuai Wang, Zibin Zheng, Michael R. Lyu, and Shing-Chi Cheung. 2025. Rigor, reliability, and reproducibility matter: A decade-scale survey of 572 code bench- marks. Preprint, arXiv:2501.10711. Version 4 re- vised in 2026. Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, and 1 others. 2021. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374. Simin Chen, Pranav Pusarla, and Baishakhi Ray. 2025. Dynamic benchmarking of reasoning capabilities in code large language models under data contamina- tion. Preprint, arXiv:2503.04149. Codeforces. 2026. Codeforces.https://codeforces. com/. Accessed: 2026-05-14. Gheorghe Comanici and 1 others. 2025. Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Mul- timodality, Long Context, and Next Generation Agen- tic Capabilities. Technical report, Google DeepMind. Shahriar Golchin and Mihai Surdeanu. 2024. Time travel in LLMs: Tracing data contamination in large language models. arXiv preprint arXiv:2308.08493. Dan Hendrycks, Steven Basart, Saurav Kadavath, Man- tas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Ja- cob Steinhardt. 2021.Measuring coding chal- lenge competence with APPS.arXiv preprint arXiv:2105.09938. Paul Jaccard. 1901. Étude comparative de la distribution florale dans une portion des alpes et des jura. Bul- letin de la Société Vaudoise des Sciences Naturelles, 37:547–579. Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar- Lezama, Koushik Sen, and Ion Stoica. 2024. Live- CodeBench: Holistic and contamination free eval- uation of large language models for code. arXiv preprint arXiv:2403.07974. Kattis. 2026. Kattis.https://open.kattis.com/. Accessed: 2026-05-14. LeetCode. 2026. Leetcode.https://leetcode.com/. Accessed: 2026-05-14. Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Hein- rich Küttler, Mike Lewis, Wen-tau Yih, Tim Rock- täschel, Sebastian Riedel, and Douwe Kiela. 2020. Retrieval-augmented generation for knowledge- intensive NLP tasks. Advances in Neural Information Processing Systems, 33:9459–9474. Xiangyang Li, Xiaopeng Li, Kuicai Dong, Quanhu Zhang, Rongju Ruan, Xinyi Dai, Xiaoshuang Liu, Shengchun Xu, Yasheng Wang, and Ruiming Tang. 2025. Humanity’s last code exam: Can advanced LLMs conquer human’s hardest code competition? arXiv preprint arXiv:2506.12713. Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and Ling- ming Zhang. 2023. Is your code generated by Chat- GPT really correct? rigorous evaluation of large lan- guage models for code generation. arXiv preprint arXiv:2305.01210. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, and 1 others. 2023.Self-refine: Iterative re- finement with self-feedback.arXiv preprint arXiv:2303.17651. Meta AI. 2024.Llama 3.3 Model Card. https://developer.meta.com/ai/docs/ model-cards-and-prompt-formats/llama3_3/ . Accessed: 2026-05-20. OpenAI. 2024.GPT-4o System Card.https:// openai.com/index/gpt-4o-system-card/.Ac- cessed: 2026-05-20. OpenAI. 2026.Introducing GPT-5.4.https:// openai.com/index/introducing-gpt-5-4/. Ac- cessed: 2026-05-26. Weijia Shi, Anirudh Ajith, Mengzhou Xia, Yangsibo Huang, Daogao Liu, Terra Blevins, Danqi Chen, and Luke Zettlemoyer. 2024. Detecting pretraining data from large language models. arXiv preprint arXiv:2310.16789. Noah Shinn, Federico Cassano, Edward Berman, Ash- win Gopinath, Karthik Narasimhan, and Shunyu Yao. 2023.Reflexion: Language agents with verbal reinforcement learning.arXiv preprint arXiv:2303.11366. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. 2022. Chain-of-thought prompting elicits rea- soning in large language models. Advances in Neural Information Processing Systems, 35:24824–24837. Colin White, Samuel Dooley, Manley Roberts, Arka Pal, Ben Feuer, Siddhartha Jain, Ravid Shwartz-Ziv, Neel Jain, Khalid Saifullah, Sreemanti Dey, Shubh- Agrawal, Sandeep Singh Sandha, Siddartha Naidu, Chinmay Hegde, Yann LeCun, Tom Goldstein, Willie Neiswanger, and Micah Goldblum. 2025. Livebench: A challenging, contamination-limited llm benchmark. Preprint, arXiv:2406.19314. Lei Yang, Renren Jin, Ling Shi, Jianxiang Peng, Yue Chen, and Deyi Xiong. 2025. Probench: Benchmark- ing large language models in competitive program- ming. arXiv preprint arXiv:2502.20868. Shang Zhou, Zihan Zheng, Kaiyuan Liu, Zeyu Shen, Zerui Cheng, Zexing Chen, Hansen He, Jianzhu Yao, Huanzhi Mao, Qiuyang Mang, Tianfu Fu, Beichen Li, Dongruixuan Li, Wenhao Chai, Zhuang Liu, Alek- sandra Korolova, Peter Henderson, Natasha Jaques, Pramod Viswanath, and 2 others. 2025. Autocode: Llms as problem setters for competitive program- ming. Preprint, arXiv:2510.12803. A Detailed Transformation Operators This section gives the full definitions of the ten transformation operators used by ALGOBENCH. Each operator takes a source problem with a known reference algorithm and produces a generated prob- lem whose solution requires a changed algorithmic treatment or a changed asymptotic target. CS — Constraint Scaling. This operator in- creases the input size so that the original com- plexity, such asO(n 2 )orO(n 3 ), no longer fits the time limit. The generated problem therefore requires a faster algorithm. We apply this opera- tor only when a verified faster solution exists for the same core problem. Common cases include O(n 2 )→ O(n logn) and O(n 3 )→ O(n 2 ). SD — Static-to-Dynamic. This operator turns a static problem into an online one by adding up- date operations between queries. It is used when the original data structure has a standard dynamic counterpart. Examples include prefix sum→lazy segment tree and DSU→ DSU with rollback. OP — Objective Perturbation. This operator changes the optimization objective while keeping the input structure close to the source problem. The new objective can invalidate the original greedy or dynamic-programming argument. Examples in- clude min-total→min-max, feasibility→count- ing modulo a prime, and value computation→ lexicographically smallest construction. C — Constraint Coupling.This operator adds a constraint, such as a budget, cooldown, or prece- dence relation, that creates dependence between choices that were independent in the source prob- lem. This often breaks separability and changes the required method. Typical cases include 1D DP→ 2D DP and greedy selection→ min-cost flow. EC — Edge-Case Expansion.This operator ex- pands the input domain so that assumptions used by the source solution no longer hold. Examples include allowing negative weights, larger integer ranges, disconnected graphs, or sparse coordinate domains. Such changes can turn greedy meth- ods under positive weights into shortest-path al- gorithms, or direct array indexing into coordinate compression. OR — Output Requirement Change. This op- erator changes what the problem asks the solver to output while preserving much of the input struc- ture. Instead of only returning an optimal value, the generated problem may ask for an optimal con- struction, a lexicographically smallest solution, a count, or a set of critical elements. Typical cases include value DP→DP with parent pointers and matching size→ minimum vertex cover. GT — Greedy-Trap Injection. This operator adds a condition that breaks a known greedy ex- change argument. Examples include a type-switch budget in interval scheduling or a cooldown con- straint in activity selection. The resulting problem usually requires DP or matching rather than the original greedy rule. RW — Real-World Wrapping. This operator places an algorithmic core inside a realistic applica- tion setting, such as logistics, scheduling, resource allocation, or network maintenance. The generated problem keeps a precise formal specification, but changes the surface setting so that direct template matching becomes less reliable. We use this op- erator only when the wrapped version preserves deterministic judgeability. GS — Graph Structure Change. This opera- tor changes the graph family or graph constraints while keeping the high-level task related to the source problem. For example, a tree problem may be changed into a version requiring heavy-light decomposition, or a static graph problem may be changed into an offline version with edge intervals. The purpose is to test whether the model recognizes that the original graph algorithm no longer applies. HY — Hybrid Transformation. This opera- tor combines two compatible transformations to produce a larger algorithmic change. For exam- ple, a problem may first be changed from static to dynamic and then receive an output require- ment change. Hybrid transformations are used only when the resulting problem remains readable, judgeable, and has a verified reference solution. B Detailed Quality Gates This section describes the four quality gates used to filter candidate generated problems. A candidate is accepted into ALGOBENCH only if it passes all four gates. Gate 1: Old-Solution Rejection. We run the original reference solutiona ∗ on the generated problemq ′ . The tests include random instances at the generated constraint scale, adversarial cases tar- geting the old solution’s failure mode, and operator- specific edge cases. A problem passes this gate only ifa ∗ fails by WA, TLE, or MLE on at least one test category. This gate ensures that the gener- ated problem is not solvable by simply reusing the source solution. Gate 2: Reference-Solution Verification. For each candidate problem, we build a new reference solutionˆa ∗ and a brute-force oraclea bf . The ora- cle is used only on small inputs, where exhaustive or clearly correct slow methods are feasible. We compareˆa ∗ anda bf on at least 1000 random small inputs. A candidate passes this gate only if the out- puts match, the output format is deterministically judgeable, andˆa ∗ satisfies the target time complex- ity ˆ T ∗ . Gate 3: Similarity Filtering. We measure simi- larity between the source problemqand the gener- ated problemq ′ using BM25 similarity, sentence- transformer cosine similarity, andn-gram overlap. These signals are combined intoTextSim(q,q ′ ). A candidate is rejected if TextSim(q,q ′ )≥ τ text ,(5) whereτ text = 0.55is calibrated using human an- notation. We also require an algorithmic change, namely ˆα̸= αor ˆ T ∗ ̸= T ∗ .(6) This gate removes near-paraphrases and keeps prob- lems whose source-to-target change is algorithmi- cally meaningful. Gate 4: Complexity Verification. Finally, the new reference solutionˆa ∗ is checked by the deter- ministic complexity verifier described in Section 4. A candidate is rejected if the verifier marks the reference solution as UNCERTAIN or reports a mis- match with the target time or space complexity. This gate ensures that every accepted problem has a certified algorithmic target. C Example Benchmark Problems Example 1: Range Query Shift (CS + SD) Source. Given a static array ofn ≤ 10 5 inte- gers, answerQ≤ 10 5 range-sum queries by out- putting P r i=l A[i]. The reference solution uses prefix sums withO(n +Q)time andO(n)space. Shifted variant. Given an array ofn≤ 2× 10 5 integers andQ ≤ 2× 10 5 operations, support either1 l r x, which addsxto all elements inA[l..r], or2 l r, which outputsmax r i=l A[i]. The new reference solution uses a lazy segment tree withO((n +Q) logn)time andO(n)space. Old-solution failure. The prefix-sum solution fails by both TLE and WA, since it cannot support range-add updates or range-maximum queries. Example 2: Greedy-Trap Interval Scheduling (GT) Source. Given a set of intervals, select the maximum number of non-overlapping intervals. The reference solution uses the standard greedy rule based on earliest finishing time and runs in O(n logn) time. Shifted variant. Each interval is assigned a type t i . The goal is to select the maximum number of non-overlapping intervals while allowing at most kconsecutive type switches. The new reference solution uses dynamic programming over sorted intervals with a switch-count state and runs in O(nk logn) time. Old-solution failure. The greedy solution fails by WA: it maximizes the number of intervals locally, but it does not account for the global switch-budget constraint. Example 3: Dynamic Connectivity Shift (SD) Source. Givenn ≤ 2000nodes andm ≤ 5000 edges, answer connectivity queries. The refer- ence solution uses DSU and runs inO(n + m) time for the static graph setting. Shifted variant. Givenn≤ 2× 10 5 nodes and a sequence ofQoperations, support edge insertion, edge deletion, and connectivity queries. The new reference solution uses offline dynamic connec- tivity with DSU rollback and a segment tree over time, running in O((n + Q) logQ· α(n)) time. Old-solution failure. The vanilla DSU solution fails by TLE because it cannot handle deletions directly; rebuilding the DSU after deletions costs O(Q(n + m)) time. D Complexity Verifier: Implementation Details Static AST analysis. Python submissions are parsed with theastmodule, while C++ submis- sions are parsed using LibClang Python bindings. The static analyzer tracks four types of evidence: •nested loop depth over input-size parameters such asN,Q, andM, with loop bounds com- bined to estimate time complexity; • recursion depth and branching factor, with mem- oized recursion handled separately; •allocation sizes for arrays, vectors, and DP tables to estimate space complexity; •data-structure signatures from class names, function-call patterns, and structural patterns, such as midpoint splitting in a recursive func- tion as evidence for a segment tree. Algorithm-tag detection rules. The verifier as- signs algorithm tags using deterministic structural rules. Examples include: • lazy_segment_tree : recursive range-query or range-update functions with lazy propagation be- fore recursive descent; • dsu_rollback : union-find data structure with a history stack and explicit push/pop rollback operations; • dp_with_switch_budget: a 2D DP table where one dimension corresponds to a switch-count variable; • prefix_sum_only: prefix-array allocation and range-sum formula without per-query dynamic updates. Runtime scaling protocol. The verifier runs each solution on inputs withN ∈10 3 , 2×10 3 , 4× 10 3 , 8× 10 3 , 1.6× 10 4 , 3.2× 10 4 . For each in- put size, it performs five runs and uses the median runtime. It then fits a power-law model by log-log linear regression: logT = α logN + γ log logN + c.(7) A solution is flagged as too slow ifˆα > α target + 0.15 , where the tolerance accounts for logarithmic factors and measurement noise. E Prompt Templates We present the full prompt templates used for each evaluation strategy. Placeholders incurly braces are filled per problem instance.All prompts are delivered as multi-turn chat messages. Strategy 1 — Direct (Zero-Shot) Direct System You are an expert competitive programmer. Solve the algorithmic problem below by writing a complete, correct, and efficient Python solution. Output only the code, no explanation. User Problem: problem_statement Input format: input_format Output format: output_format Constraints: constraints Examples: examples Write a complete Python solution. Strategy 2 — Chain-of-Thought (CoT) Chain-of-Thought System You are an expert competitive programmer who reasons carefully before coding. Always reason step by step before writing code. User Problem: problem_statement Input format: input_format Output format: output_format Constraints: constraints Examples: examples Reason step by step: (1) Identify the key constraint that determines the required time complexity. (2) Determine what time/space complexity class is needed. (3) Select an algorithm or data structure that meets this class. (4) Verify that the selected algorithm handles all edge cases. (5) Implement the solution in Python. Output your reasoning followed by the complete Python code. Model Output (excerpt) Step 1: The constraint N ≤ 2× 10 5 and Q ≤ 2× 10 5 updates/queries rule out any O(N Q) approach. . . Step 2: We need O((N + Q) log N ). Step 3: A lazy segment tree supports range-add and range-max in O(log N ) per operation. . . [Python code follows] Strategy 3 — Self-Refine Self-Refine (Madaan et al., 2023) runs up toR=3 rounds. Round 1 uses the Direct prompt; subse- quent rounds append the previous solution and a structured feedback message. Self-Refine — Feedback Round System You are an expert competitive programmer. You are given a problem, your previous solution, and feedback. Revise the solution to fix all identified issues. Output only the revised code. User Problem: problem_statement Constraints: constraints Your previous solution: previous_solution Feedback: feedback_message Please fix all issues and output a corrected Python solution. Feedback message (auto-generated) Issue 1 (Wrong Answer): Your solution failed on hidden test case 7. Expected output: 14, your output: 12. Issue 2 (Complexity): Static analysis detected a nested loop over N inside each query, giving O(N Q). The target is O((N + Q) log N ). Replace the linear scan with a lazy segment tree. Strategy 4 — RAG-Source Retrieval RAG-source retrieves the top-1 most similar source problem (by BM25 + embedding re-rank) and prepends it to the Direct prompt. The retrieval cor- pus consists of all seed problems in ALGOBENCH with their original reference solutions. RAG-Source System You are an expert competitive programmer. You will be shown a related reference problem and its solution, followed by a new problem with modified constraints. Important: the new problem has different requirements. Do NOT copy the reference solution; adapt it if necessary. User Reference problem (similar, but different): retrieved_source_statement Reference solution: retrieved_source_solution New problem (solve this one): problem_statement Input format: input_format Output format: output_format Constraints: constraints Examples: examples The constraints have changed. Determine whether the reference solution still applies or a new algorithm is required. Write a complete Python solution. Strategy 5 — Skill-Guided Skill-guided augments the CoT prompt with ex- plicit complexity targets and forbidden patterns derived from the problem’s complexity metadata (Section 4). Skill-Guided System You are an expert competitive programmer. You will be given a problem together with the required time/space complexity and the expected algorithmic approach. Use this information to guide your solution. User Problem: problem_statement Input format: input_format Output format: output_format Constraints: constraints Examples: examples Complexity guidance: • Required time complexity: target_time_complexity • Required space complexity: target_space_complexity • Expected algorithm class: expected_algorithm_tags • Avoid: forbidden_algorithm_tags — these are too slow or incorrect under the given constraints. Implement an efficient Python solution that satisfies the above complexity requirements. Think step by step. Strategy 6 — Reflexion Reflexion (Shinn et al., 2023) maintains a persistent verbal memory of past failures. At each round the model first writes a short reflection on why its previous attempt failed, stores it, and then generates a new solution conditioned on the memory. Reflexion System You are an expert competitive programmer with a memory of past attempts. Learn from your previous failures and improve. User Problem: problem_statement Constraints: constraints Examples: examples Memory of past attempts: reflexion_memory Based on your memory, write a new Python solution that avoids the mistakes you identified. Be explicit about what you are changing and why. Example reflexion memory entry Attempt 1 reflection: I used a prefix sum array to answer range queries, but I forgot that this problem also has range-add updates. Prefix sums become stale after any update. I need a data structure that handles both updates and queries efficiently — a lazy segment tree or a Fenwick tree with range operations. Next time: check for the presence of update operations before choosing a static data structure.

Instant research discovery