A LGO B ENCH: Benchmarking Algorithmic Adaptation in Code Generation Xinyuan Song1 Zekun Cai2,3 Liang Zhao1 Emory University, Atlanta, GA, USA 2 The University of Tokyo, Tokyo, Japan 3 LocationMind, Tokyo, Japan {xinyuan.song,liang.zhao}@emory.edu, [email protected]
1
Abstract
arXiv:2607.00062v1 [cs.SE] 30 Jun 2026
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 A LGO B ENCH, a framework that automatically builds novel algorithmic problems from known competitiveprogramming problems through structured constraint-shifting transformations. Each accepted A LGO B ENCH variant is traceable to a source problem, but must make the original reference algorithm fail. Beyond pass@k, we introduce complexity-aware metrics—including O PT T, O PT S, T RAP R ATE, G AP T, and C ON S ENS—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 A LGO B ENCH 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 A LGO BENCH evaluates adaptation beyond functional correctness. Code is available at https:// github.com/Hik289/algobench.git.
1
Introduction
Large language models (LLMs) now perform well on many programming and algorithmic benchmarks. 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 measure algorithmic reasoning. Many programming problems, editorials, and reference solutions are
publicly available, and web-scale pretraining corpora may contain exact or near-duplicate problem– solution pairs. A model can therefore pass a benchmark 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 contamination by using newer or harder problems. LiveCodeBench (Jain et al., 2024) and LiveBench (White et al., 2025) collect released tasks, while ProBench evaluates models on competitiveprogramming 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 difficult contest tasks (Li et al., 2025). These benchmarks improve over older static datasets, but they remain fixed once released. Their problem statements, 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 benchmark 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 cannot improve by memorizing existing problem statements and solutions? Such a benchmark satisfy 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 problem should require a new algorithmic treatment or a different asymptotic complexity, so that memorizing the source problem is not enough to solve. We propose A LGO B ENCH, a benchmark framework for automatically generating new algorithmic problems and evaluating algorithmic adaptation.
Figure 1: Core idea of A LGO B ENCH. A standard benchmark may allow an LLM to reuse a familiar template such as Prefix Sum. A LGO B ENCH 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, A LGO B ENCH starts from competitive-programming problems with known reference algorithms. It then applies structured transformations, including constraint scaling, staticto-dynamic conversion, objective perturbation, and greedy-trap injection. These transformations produce new problems that remain traceable to their sources, but solving them requires algorithmic treatment rather than reuse of the original solution. Before a generated problem is added to the benchmark, it must pass four quality gates: the original reference solution must fail, a new reference solution must be verified, the statement must pass similarity filtering, and the target time and space complexity must be certified. This design also follows recent calls for benchmark quality control, reproducibility, and transparent validation in coderelated LLM evaluation (Cao et al., 2025). The benchmark is designed to evaluate more than test passing. Standard pass@k only checks whether a submitted program passes the tests; it does not separate an asymptotically suitable algorithm from a slower one that happens to pass under a permissive time limit. To make this distinction, A LGO B ENCH includes a deterministic three-layer complexity verifier. The verifier combines static AST-level analysis, algorithm-tag checks, and calibrated runtime scaling tests to assign auditable time and space optimality labels. This lets A L GO B ENCH 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 A LGO B ENCH variants. The results 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 common than ordinary implementation bugs. These results suggest that A LGO B ENCH 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 A LGO B ENCH, an automatic benchmark construction framework for generating new algorithmic problems and evaluating algorithms. • We design ten rule-based transformation operators 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 algorithmic 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 O PT T, O PT S, T RAP R ATE,
G AP T, and C ON S ENS. • We evaluate seven LLMs under six prompting strategies and show that automatically generated problems reveal old-template reuse and suboptimal algorithmic reasoning.
2
Problem Formulation
Source problem. We represent a source problem as q = (stmt, C, α, T ∗ , S ∗ , a∗ ). Here, stmt is the problem statement, including the input/output format and public examples. C is the constraint set, such as n ≤ 2000. α is the reference algorithm type, such as prefix_sum. T ∗ and S ∗ are the reference time and space complexities, and a∗ is the reference solution. Generated problem. A generated problem is written as q ′ = T (q, δ), where T is a transformation operator and δ specifies the concrete change. For example, δ may increase the input bound from n ≤ 2000 to n ≤ 2 × 105 , add update operations, change the objective, or introduce an additional constraint. The generated problem has its own target time complexity T̂ ∗ , target space complexity Ŝ ∗ , algorithm type α̂, and reference solution â∗ . Acceptance conditions. A generated problem q ′ 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. Running a∗ on hidden tests for q ′ produces WA, TLE, or MLE (old solution fails) C4. A verified â∗ exists and agrees with a bruteforce oracle on inputs (new solution verified) C5. â∗ satisfies T̂ ∗ and Ŝ ∗ according to the complexity verifier (complexity certified) C6. α̂ ̸= α or T̂ ∗ ̸= T ∗ (algorithmic change)
3.1
A LGO B ENCH 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 perturbation (OP), constraint coupling (CC), edgecase expansion (EC), output requirement change (OR), and greedy-trap injection (GT). We also include 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 connectivity to rollback-based dynamic connectivity. Detailed definitions and examples for all operators are provided in Appendix A. 3.2
Transformation Framework
Figure 2 shows the A LGO B ENCH construction pipeline. Starting from a problem with a known reference algorithm, A LGO B ENCH applies rulebased transformations to generate new algorithmic problems. The generated problems remain traceable 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, oldsolution rejection, non-paraphrase status, and certified complexity.
Quality Gates
Each generated problem is filtered by four quality gates before inclusion in A LGO B ENCH. First, the original reference solution must fail on the generated 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 according 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 3
Transformation Operators
Deterministic Complexity Verifier
Each accepted problem comes with a deterministic 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 rangeupdate problem may require O((N +Q) log N ) time and O(N ) space, mark O(N Q) as forbidden, expect the tag lazy_segment_tree, and reject prefix_sum_only. The stress tests are chosen to separate the target complexity from the forbidden ones.
Figure 2: A LGO B ENCH 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 as N , Q, and M , recursion patterns, and allocation sizes. It estimates time complexity from loop bounds and recursion structure, and estimates space complexity from arrays, vectors, DP tables, and auxiliary data structures. It also records structural evidence for common algorithms; for instance, recursive midpoint splitting is treated as evidence for a segment tree. Layer 2: Algorithm-Tag Verification. Each problem specifies expected and forbidden algorithm 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 supports dsu_rollback. LLMbased 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 sizes N1 < N2 < N3 < N4 and fit the measured runtime to T (n) = cnα (log n)γ .
(1)
We also use the ratio T (2n)/T (n) as a growth check. A solution is marked too slow if the fitted
polynomial exponent exceeds the target exponent by more than 0.15. This tolerance accounts for logarithmic factors and measurement noise. Decision rule. The final labels combine correctness with the verifier outputs: O PT T ← C ORRECT ∧ S TATIC T IME PASS ∧ TAG PASS ∧ S CALING PASS, O PT S ← C ORRECT ∧ S TATIC S PACE PASS ∧ A LLOC PASS. If the evidence is incomplete, the verifier assigns U NCERTAIN rather than O PTIMAL. 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 probability that at least one of k sampled solutions is functionally correct (Chen et al., 2021). Complexity-aware metrics. Pass@k measures test passing, but it does not show whether the solution uses the intended algorithmic complexity. We therefore report six additional metrics. O PT T (Optimal Time Complexity Rate) is the fraction of submissions that are correct and satisfy the target time complexity T̂ ∗ according to the verifier. O PT S (Optimal Space Complexity Rate) is the fraction of O PT T-qualified submissions that also satisfy the target space complexity Ŝ ∗ . Thus, O PT S measures space compliance among solutions that are already correct and time-optimal.
T RAP R ATE (Old-Solution Trap Rate) is the fraction 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. G AP T (Efficiency Gap) measures the gap between the fitted runtime exponent and the target exponent. For each submitted solution i, the verifier fits Ti (n) = ci nα̂i (log n)γ̂i ,
(2)
where α̂i is the fitted polynomial growth exponent. Given the target exponent αi∗ for the corresponding problem, we compute ! M 1 X α̂i + ϵ , (3) G AP T = exp log ∗ M αi + ϵ i=1
where M is the number of evaluated submissions and ϵ = 10−6 avoids division by zero. A value of G AP T = 1 means that the fitted runtime exponent matches the target exponent on average, while G AP T > 1 indicates slower-than-required algorithms. C ON S ENS (Constraint Sensitivity) is the average pass@1 drop from the smallest to the largest constraint 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 A L GO B ENCH problems under the same model and prompting strategy: ∆gen (m) = pass@1src (m) − pass@1gen (m), (4) where m denotes the model. A larger ∆gen indicates that the model is more sensitive to generated algorithmic changes and relies more on sourceproblem templates.
6
Benchmark Construction
Source problems. We collect 300 source problems from Codeforces (Codeforces, 2026), AtCoder (AtCoder Inc., 2026), Kattis (Kattis, 2026), and LeetCode Hard (LeetCode, 2026). The selected problems cover Codeforces levels D–E, AtCoder difficulty 1600–2400, Kattis problems with difficulty at least 3.5, and LeetCode Hard problems. Each problem is manually annotated with its algorithm type and reference complexity. We exclude interactive problems, floating-point-sensitive judges, and non-English problems.
Table 1: Benchmark construction statistics. G1–G4 denote 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, respectively. Operator
Cands
G1
G2
G3
G4
Acc.%
CS (Constraint Scale) SD (Static→Dynamic) OP (Obj. Perturb.) CC (Constraint Coup.) EC (Edge-Case Exp.) OR (Output Change) GT (Greedy Trap) Other (RW/GS/HY)
240 180 192 156 120 132 96 96
185 128 140 100 92 96 60 64
162 106 120 80 82 80 46 50
145 95 105 68 74 68 40 44
138 92 98 62 70 62 36 40
57.5 51.1 51.0 39.7 58.3 47.0 37.5 41.7
Total
1212
865
726
639
598
49.3
Candidate generation. For each source problem, we identify applicable transformation operators 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 number 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 similar to the source problem, and Gate 4 removes candidates whose reference complexity cannot be certified. The final benchmark contains 598 accepted 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 models are GPT-4o and GPT-4o-mini (OpenAI, 2024), Gemini 2.5 Flash (Comanici et al., 2025), Claude Haiku 4.5 (Anthropic, 2025a), and Llama3.3-70B (Meta AI, 2024). To test whether recent frontier models reduce the same failure modes, we also evaluate two latest-generation models: GPT5.4 (OpenAI, 2026) and Claude Opus 4.5 (Anthropic, 2025b). These models are fully evaluated on the main benchmark split (n = 52 problems
each) under three prompting strategies. Prompting strategies. We compare six prompting strategies. Direct uses zero-shot code generation. CoT asks the model to reason before writing code (Wei et al., 2022). Self-Refine applies iterative self-feedback (Madaan et al., 2023). Reflexion uses execution feedback for revision (Shinn et al., 2023). RAG-source retrieves the most similar 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 and k = 5 samples for pass@5 estimation. 7.2
Main Results
Table 2 and Figure 3 compare Direct-prompting performance on source problems and generated A LGO B ENCH 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. Average O PT T drops by 20.1% for older models and 24.0% for the latest models, meaning that some testpassing solutions still miss the required asymptotic complexity. Together with nonzero T RAP R ATE, these results show that A LGO B ENCH exposes both source-template reuse and complexity mismatch, not only functional failure. 7.3
Efficiency and Space Compliance: O PT T and O PT S
Beyond pass@k, we report two complexity-aware metrics. O PT T measures the fraction of submissions that are correct and satisfy the target time complexity. O PT S measures the fraction of O PT Tqualified submissions that also satisfy the target space complexity. Thus, O PT T captures time efficiency, while O PT S captures space compliance among time-optimal solutions. Model-level results. Table 3 and Figure 4 report O PT T and O PT S under Direct prompting. The main result is that pass@5 is not the same as algorithmic optimality: every model has a nonzero pass@5–O PT T gap, from 9.1% for GPT-4o, Gemini 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 O PT T −O PT S 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 O PT T and O PT S by transformation operator. GT shows the largest O PT T −O PT S gap (18.7%), indicating that greedy-trap variants often require memory-sensitive DP implementations. In contrast, OP shows zero gap: once a model finds a time-optimal objective-shift solution, it also satisfies the space requirement. Case study: GT003. GT003, a 0-1 knapsack greedy-trap problem, shows the value of algorithmaware evaluation most clearly. Although the functional 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 slowercomplexity 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 uniform 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 O PT T (72.5%), lowest T RAP R ATE (11.8%), and lowest G AP T (1.49). Figure 7 shows the analogous prompting-strategy comparison for GPT-4o, where RAG-source increases T RAP R ATE and Skillguided prompting gives the best O PT T. 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 Gemini 2.5 Flash. RAG-source often raises pass@1, especially for GPT-4o and the latest models, but it can also increase T RAP R ATE; for example, Gemini 2.5 Flash rises from 3.6% to 30.0%, and GPT5.4 rises from 19.2% to 27.5%. These results suggest that prompting can improve success rates, but retrieval and reasoning prompts do not reliably remove source-template reuse.
Table 2: Performance on original problems and A LGO B ENCH variants under Direct prompting. T RAP R ATE and O PT T are reported on shifted variants when available. Original
Model
A LGO B ENCH Variants
p@1 O PT T
p@1
p@5
O PT T
T RAP R ATE
GPT-4o-mini GPT-4o Claude Haiku 4.5 Gemini 2.5 Flash† Llama-3.3-70B
92.3 76.9 86.5 90.0 80.0
81.8 72.7 79.5 81.8 80.0
44.3 50.0 55.8 45.0 72.7
81.8 72.7 81.8 63.6 72.7
63.6 63.6 59.1 54.5 54.5
18.2 19.7 22.7 3.6 0.0
Avg. drop (old)
85.1
79.2
−31.6%
–
−20.1%
–
GPT-5.4 Claude Opus 4.5
92.3 86.5
85.2 77.7
55.8 56.5
66.7 80.0
54.1 60.9
19.2 12.8
Avg. drop (latest)
–
–
−33.3%
–
−24.0%
–
Model Comparison (Direct Prompting) Pass@1
40
0
30 64
59
25
64 55
55
40 20
Original Shifted
GPT-4o Haiku Gemini GPT-4o Llama 4.5 2.5F -mini 3.3-70B
0
Trap Rate (%)
Opt-T (%)
Pass@1 (%)
60
60
Trap Rate
35
80
80
20
Optimal Complexity
100
100
20
18.2
15 10 5
GPT-4o Haiku Gemini GPT-4o Llama 4.5 2.5F -mini 3.3-70B
22.7 19.7
0
3.6 0.0 GPT-4o Haiku Gemini GPT-4o Llama 4.5 2.5F -mini 3.3-70B
Figure 3: Per-model performance on original problems and A LGO B ENCH 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 useful 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 transformations stress different algorithmic skills. The highest T RAP R ATE occurs on SD and CC, where static source templates are especially tempting but invalid. Thus, A LGO B ENCH does not only report whether a model solves a problem; it identifies which algorithmic changes cause failures and whether the produced solution meets the required complexity. 7.6
O PT T, and T RAP R ATE across this sweep. The main drop appears between N = 10K and N = 50K, which is exactly where many O(N 2 ) solutions start to time out and an O(N log N ) algorithm becomes necessary. O PT T follows pass@1 but stays 4–7 % lower, showing that some testpassing solutions still miss the target complexity. Meanwhile, T RAP R ATE increases as N grows, meaning that harder constraints make models more likely to fall back to the source template. We summarize this behavior with C ON S ENS, 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.
Constraint Magnitude Sensitivity
We test whether model performance changes gradually as the generated constraint becomes harder. For CS variants, we sweep the input bound over six levels, N ∈ {2K, 5K, 10K, 50K, 100K, 200K}, where 2K is close to the source setting and 200K is the hardest setting. Figure 9 reports pass@1,
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: O PT T and O PT S under Direct prompting. Gap = pass@5 − O PT T; ∆ = O PT T −O PT S, the spacecompliance gap among time-optimal solutions. pass@1
pass@5
O PT T
O PT S
∆ (OT−OS)
GPT-4o GPT-4o-mini Claude Haiku 4.5 Gemini 2.5 Flash Llama-3.3-70B
72.7 45.5 72.7 63.6 72.7
72.7 81.8 81.8 63.6 72.7
63.6 63.6 59.1 54.5 54.5
52.7 49.1 40.0 54.5 54.5
10.9 14.5 19.1 0.0 0.0
GPT-5.4 Claude Opus 4.5
55.8 56.5
66.7 80.0
54.1 60.9
54.1 56.5
0.0 4.4
Model
pass@1 / OptT / OptS under Direct Prompting (red arrows: OptT-OptS space-compliance gap)
100
Rate (%)
80 60
-11
-15
-19
40 20
pass@1 OptT OptS
0
GPT-4o
GPT-4o -mini
Claude Haiku 4.5
Gemini 2.5F
Llama 3.3-70B
Figure 4: pass@1, O PT T, and O PT S for the seven evaluated models under Direct prompting. Red arrows show the O PT T −O PT S space-compliance gap. pass@1 / OptT / OptS by Transformation Operator (avg 5 models, Direct; D=OptT-OptS) pass@1 OptT OptS
100
Rate (%)
80 60
D=4 D=3
Strategy
p@1 p@5 O PT T T RAP R ATE G AP T
Direct CoT RAG-source Self-Refine Reflexion Skill-guided
44.3 81.8 63.6 52.4 55.1 67.2
D=19 D=10
40 20 0
Table 4: GPT-4o-mini under prompting strategies on A LGO B ENCH variants.
CS (n=3)
SD (n=3)
OP (n=2)
GT (n=3)
Figure 5: pass@1, O PT T, and O PT S 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 supports this pattern. For GPT-4o, original pass@1 decreases from 82.4% on 2020 problems to 63.8% on 2024 problems, 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-
81.8 81.8 81.8 71.3 73.8 84.3
63.6 63.6 69.7 48.1 49.3 72.5
18.2 18.2 15.2 22.6 20.4 11.8
1.75 1.62 1.80 1.68 1.61 1.49
ence across years. The contamination gap, defined as original pass@1 minus shifted pass@1, therefore shrinks from 38.2 percentage points in 2020 to 23.1 percentage points in 2024. This gap quantifies 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
Per-Problem pass@1 / OptT / OptS (sorted by OptS ascending) pid color = CS:blue SD:green OP:red GT:orange
SD003 CS003 SD002 CS005 OP001 GT002 GT001 SD001 GT003 OP002
GT003: pass@1=100% but OptT=OptS=0% (greedy trap!)
CS001
20
0
20
40 Rate (%)
60
80
pass@1 OptT OptS
100
Figure 6: Per-problem pass@1, O PT T, and O PT S, sorted by O PT S. GT003 has pass@1=100% but O PT T =O PT S =0% because models choose the wrong greedy algorithm instead of the required DP recurrence. Problem IDs are colored by operator.
Prompting Strategy Comparison (Shifted) Strategy
â??9%
â??9%
â??15%
â??18%
Direct CoT RAG
â??18%
â??30%
â??4%
â??23%
â??12%
â??15%
40
â??25%
60
â??18%
80 â??20%
Pass@1 (%) -- Shifted
100
20 0
Arrow inside bar = Trap Rate
GPT-4o
Haiku 4.5
Gemini 2.5F
GPT-4o -mini
Llama 3.3-70B
Figure 7: Prompting strategy comparison on GPT-4o. RAG-source raises TrapRate, while Skill-guided prompting achieves the best OptT and lowest TrapRate.
analyze G AP T, which measures the gap between the fitted runtime exponent and the target exponent. Figure 11 reports G AP T by transformation operator.
G AP T is above 1.0 for all operators, confirming that correct solutions can still be asymptotically suboptimal. OP has the largest gap (1.35), indicating that objective perturbations most often require a full algorithmic change. SD and GT have smaller gaps (1.17), suggesting that these shifts more often preserve part of the original algorithmic structure. Thus, G AP T 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 A LGO B ENCH problem has a source algorithm α and a target algorithm α̂, and Figure 12 reports pass@1 and O PT T 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% O PT T, because standard DSU cannot handle deletions without rollback or offline processing. Greedy → DP is also difficult, with 28.4% pass@1 and 23.7% O PT T, since the generated con-
Gemini 2.5F Llama 3.3-70B 100
100
100
GPT-4o GPT-4o-mini Haiku 4.5
67
67
67
67
67
80 67
33
33
33
40
50
50
60 33
Pass@1 (%) -- Shifted
100
100
100
Pass@1 by Shift Operator (Direct)
CS (n=3)
SD (n=3)
0
0
0
0
20 OP (n=2)
GT (n=3)
Figure 8: GPT-4o Direct performance by transformation operator. Bars show pass@1 and O PT T, and the dashed red line shows T RAP R ATE. SD has the lowest pass@1, while CS has the highest pass@1 but still shows a pass@1–O PT T gap. Constraint Magnitude Sensitivity (a) pass@1 vs. constraint magnitude
80 60 40 20
60 50
60 40 20
source N
0 103
105
Shifted constraint N (log scale)
106
40 30 20 10 0
0 104
(c) TrapRate vs. constraint magnitude
70
80 OptT (%)
pass@1 (%)
(b) OptT vs. constraint magnitude
100
GPT-4o GPT-4o-mini Haiku 4.5 Gemini 2.5F Llama-3.3-70B Real anchor (CS)
TrapRate (%)
100
103
104
105
106
Shifted constraint N (log scale)
103
104
105
Shifted constraint N (log scale)
106
Figure 9: Constraint magnitude sensitivity (C ON S ENS). As N increases from 2K to 200K, pass@1 and O PT T decrease, while T RAP R ATE increases. The sharpest degradation occurs near the point where quadratic solutions begin to time out. Table 5: Cross-model pass@1 and T RAP R ATE for three strategies. pass@1 (%) Model
Dir CoT RAG Dir CoT RAG
GPT-4o 50.0 54.5 Claude Haiku 4.5 55.8 72.7 Gemini 2.5 Flash 45.0 54.5 GPT-4o-mini 44.3 81.8 Llama-3.3-70B 72.7 63.6 GPT-5.4 Claude Opus 4.5
T RAP R ATE (%)
Table 6: GPT-4o performance breakdown by transformation operator under Direct prompting. The table matches Figure 8: CS, SD, OP, and CC are shown with pass@1, O PT T, and T RAP R ATE.
63.6 19.7 25.5 63.6 22.7 0.0 63.6 3.6 14.5 63.6 18.2 18.2 54.5 0.0 9.1
18.2 12.1 30.0 15.2 9.1
55.8 69.9 70.7 19.2 18.1 27.5 56.5 74.1 72.1 12.8 9.2 17.7
straints invalidate the original exchange argument. Easier transitions include brute force → prefix sums and brute force → lazy segment tree, where models can reuse familiar optimization patterns. Across transitions, O PT T 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 A LGO B-
Operator
p@1 O PT T T RAP R ATE
CS (Constraint Scale) SD (Static→Dynamic) OP (Obj. Perturb.) CC (Constraint Coup.)
50.0 31.3 42.4 34.8
43.0 26.3 37.7 29.2
33.8 47.3 35.2 43.7
Average
39.6
34.1
40.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. Removing Gate 1 allows many variants where the old solution still passes, increasing the old-solution
Contamination Effect by Problem Publication Year (N=240 problems) Bars = mean ± std; dots = individual problems (a) pass@1 by publication year older higher original (training contamination)
(b) Contamination gap narrows for newer problems trend: -2.4 pp/yr
Original Shifted
80
Gap orig shift (pp)
pass@1 (%)
100 80 60 40
60 40 20 0
n=30
n=55
n=65
n=55
n=35
2020
2021
2022
2023
2024
Problem publication year
2020 2021 2022 2023 2024
Problem publication year
Figure 10: Contamination effect by problem publication year. The original–shifted gap narrows for newer problems, indicating that A LGO B ENCH reduces reliance on memorized source solutions.
100
GPT-4o Haiku 4.5 Gemini 2.5F
100
GPT-4o-mini Llama 3.3-70B
67
67
67
67
67
67
67
67
67
67
67
67
80
50
50
50
50
60 50
Optimal Complexity Rate (%) -- Shifted
Optimal Complexity by Operator
40 20 0
CS (n=3)
SD (n=3)
OP (n=2)
GT (n=3)
Table 7: Quality-gate ablation. Each row removes one gate from the full A LGO B ENCH 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. Variant
Old-Sol↓ Ref-Fail↓ Near-Para↓ F-Opt↓
Figure 11: Efficiency gap (G AP T) by transformation operator for GPT-4o. G AP T = 1.0 means the fitted runtime exponent matches the target exponent; larger values indicate slower algorithms.
Full pipeline w/o Gate 1 (old-sol) w/o Gate 2 (ref ver) w/o Gate 3 (sim) w/o Gate 4 (cmplx)
3.2% 38.7% 3.2% 3.2% 3.2%
pass rate from 3.2% to 38.7%. This weakens the benchmark because such variants no longer test algorithmic adaptation. Removing Gate 2 introduces reference-solution failures. Removing Gate 3 admits near-paraphrase variants, and removing Gate 4 increases the false-optimal label rate from 2.1% to 11.4%, inflating reported O PT T.
timization needed for the target complexity. These two categories account for 64.1% of failures, while implementation bugs account for only 9.0%. This supports the main goal of A LGO BENCH : it tests whether models can adapt the algorithmic idea, not merely whether they can write syntactically correct code. The too slow cases are especially useful because they show partial understanding: the model often identifies the right direction but misses techniques such as divide-and-conquer DP, convex hull trick, or fractional cascading.
8
Error Analysis
We manually classify 400 failed GPT-4o submissions under Direct prompting. As shown in Figure 13, most failures are algorithmic rather than implementation-level. The largest category is the old-solution trap (42.3%), where the model implements 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-
9
0.0% 0.0% 16.8% 0.0% 0.0%
4.1% 4.2% 4.1% 18.3% 4.1%
2.1% 2.1% 2.1% 2.1% 11.4%
Shift Quantification and Generalization Analysis
The previous results show that generated A LGO B ENCH problems lower model performance and expose reuse of source-solution templates. We now ask a more detailed question: how different are
Algorithm Transition Difficulty (b) Mean pass@1 heatmap (operator × algorithm distance)
100
100
CS
79
68
47
SD
86
85
68
60
OP
55
53
33
40
GT
76
71
55
Same
Near Algorithm distance
Far
60
Operator
pass@1 (%)
80
40 20 0
CS SD OP GT Verified real data
Same algorithm
Near algorithm
Far algorithm
80 Mean pass@1 (%)
(a) pass@1 by algorithm transition distance (diamonds = verified real data)
20 0
Figure 12: Algorithm transition difficulty. Left: pass@1 decreases as the source-to-target algorithm distance moves from S AME to FAR. Right: mean pass@1 by transformation operator and algorithm-distance group. Error Analysis: Trap vs. Non-Trap Failures (Direct)
6
Failed + Trapped Failed (no trap)
Failing problems (shifted)
5
4
4
3
3
2
2 1 0
3 2
2
2
1 GPT-4o
Haiku 4.5
Gemini 2.5F
GPT-4o -mini
Llama 3.3-70B
Figure 13: Error distribution over 400 randomly sampled 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 A LGO B ENCH is not meant to create arbitrary new tasks. Each generated 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 algorithmic structure or complexity that the source solution no longer applies. We measure the source-to-generated change using four types of features: surface-form similarity, constraint magnitude change, algorithm-class distance, and asymptotic complexity change. We then relate these features to pass@1, O PT T, and T RAP R ATE. 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 problem Ps and generated problem Pg , we compute five shift metrics: • Text Jaccard. Word-level Jaccard (Jaccard, 1901) similarity between the two problem statements. This measures surface overlap. • Length ratio. |Pg |/|Ps | in characters. This captures added constraints, context, or output requirements. • Constraint magnitude ratio. The ratio between the largest numeric bound in the generated problem and the corresponding bound in the source problem, extracted from the constraint section using regex patterns over n, N , Q, and related variables. • Complexity exponent ∆. The change in worstcase time-complexity exponent from source to generated problem. We map O(n) to 1, O(n log n) to 1.5, O(n2 ) to 2, and so on; see Appendix D. • Algorithm-class distance. A categorical sourceto-generated distance label, S AME, N EAR, or FAR, assigned using a hand-coded algorithmfamily taxonomy. Table 8 shows that A LGO B ENCH problems are still connected to their sources, but usually require nontrivial algorithmic changes. The mean Text Jaccard score is moderate (0.458 ± 0.134), so sourcetemplate reuse remains a plausible failure mode. At the same time, constraint bounds increase sharply on average (6,393×), and the complexity exponent increases by 0.21. Only 27.3% of generated problems 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 A LGO B ENCH. 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. Metric
Mean
Text Jaccard similarity Statement length ratio Constraint magnitude ratio (n) Complexity exponent ∆
0.458 1.51× 6 393× +0.21
Std 0.134 0.35 14 926 0.24
Algorithm distance distribution: Same 27.3% Near 36.4% Far 36.4%
Table 10: Spearman correlation between shift metrics and model performance. Larger constraint, complexity, and algorithm-distance shifts correlate with lower pass@1 and O PT T but higher T RAP R ATE. Shift metric
Model
∆exp Alg. Dist.
Len.
CS SD OP GT
1.46× +0.17 1.50× 0.00 1.62× +0.25 1.49× +0.43
0.49 0.38 0.47 0.50
Near Near Far Far
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 algorithmic change. Table 9 reports per-operator averages 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 as O(n2 ) → O(n log n). 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 optimized and can break the proof behind the source algorithm. Greedy-Trap Injection (GT) directly breaks a greedy exchange argument, which explains 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, T RAP R ATE, and O PT T under Direct prompting, averaged across the verified models. We then compute Spearman rank correlations between these outcomes and the structural shift features.
O PT T
−0.31 +0.29 +0.44∗ −0.47∗ ∗∗ +0.55 −0.58∗∗ +0.58∗∗ −0.64∗∗
Table 11: Generalization gap ∆gen between source and generated problems under Direct prompting.
Table 9: Average shift metrics by transformation operator. ∆exp is the complexity-exponent change; Dist. is the most common algorithm-distance class. Op. Jaccard
pass@1 T RAP R ATE
Text Jaccard (↑ = more similar) +0.38 log(constraint ratio) −0.52∗ Complexity ∆exp −0.61∗∗ Alg. distance (Far=1, Near=0.5, Same=0) −0.67∗∗
Src. p@1 Gen. p@1 ∆gen
GPT-4o-mini GPT-4o Claude Haiku 4.5 Gemini 2.5 Flash Llama-3.3-70B
81.8 72.7 90.9 81.8 80.0
45.5 72.7 72.7 63.6 72.7
−36.3 0.0 −18.2 −18.2 −7.3
Mean
81.4
65.4
−16.0
Algorithm-class distance is the strongest predictor. Larger distances correlate with lower pass@1 (ρ = −0.67), lower O PT T (ρ = −0.64), and higher T RAP R ATE (ρ = +0.58). Complexityexponent change shows the same trend. Text similarity is weaker, which suggests that task difficulty is not mainly caused by surface rewording. Instead, model failures are tied to structural algorithmic change. 9.4 Generalization Gap: Source vs. Generated Problems Table 11 and Figure 14 show that generated problems 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 A LGO B ENCH problems require more than sourcetemplate reuse. Table 12 stratifies GPT-4o-mini by algorithmclass distance. The largest drop occurs for Far transitions (−75.0%), while Near transitions show no drop. This links the generalization gap to algorithmic 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
Generalisation Gap: Original vs. Shifted Pass@1 (Direct Prompting) Original Shifted
100 +18 +18 +36
60 40
Model
20 0
â? DeepSeek V4-Flash: n=5 (partial run, p@1~40%)
GPT-4o
Claude Haiku 4.5
Gemini 2.5F
GPT-4o -mini
Llama 3.3-70B
DeepSeek V4-Flashâ?
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.
GPT-4o GPT-4o-mini Claude Haiku 4.5 Gemini 2.5 Flash Llama-3.3-70B
n
Src. p@1
∆gen
Same Near Far
3 4 4
66.7 75.0 100.0
−33.3 0.0 −75.0
pass@1 under Direct prompting for CS, SD, OP, and GT. Three patterns stand out among the five primary models. First, OP is the hardest operator: three models score 0%, and no model exceeds 50%. This is expected because changing the objective can invalidate the proof behind the source algorithm. Second, SD is the easiest operator, with three models reaching 100%, suggesting that models often recognize common static-todynamic 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, A LGO B ENCH reveals operator-specific strengths and failures that aggregate scores would hide. 9.6
RAG Effectiveness Conditioned on Shift Severity
Section 7.4 shows that RAG has model-dependent effects on T RAP R ATE. We further split the 11 pilot problems by median Text Jaccard similarity (θ = 0.460). Problems with Jaccard ≥ 0.460 are treated as easy shifts (n = 6), and those with Jaccard < 0.460 are treated as hard shifts (n = 5). Figure 16 compares Direct and RAG-source in both groups. RAG has different effects across models. GPT4o and GPT-4o-mini benefit from RAG on
SD (n = 3)
OP (n = 2)
GT (n = 3)
66.7 66.7 33.3 66.7 66.7
66.7 66.7 100.0 100.0 100.0
0.0 0.0 50.0 50.0 0.0
33.3 33.3 100.0 33.3 100.0
Cross-Operator pass@1 (%) under Direct Prompting
Table 12: Generalization gap by algorithm-class distance for GPT-4o-mini. Larger drops occur when the generated problem requires a more distant target algorithm. Alg. distance
CS (n = 3)
GPT-4o
67
67
0
33
GPT-4o-mini
67
67
0
33
Haiku 4.5
33
100
50
100
Gemini 2.5F
67
100
50
33
Llama 3.3-70B
67
100
0
100
CS (n=3)
SD (n=3)
OP (n=2)
GT (n=3)
100 80 60 40
Pass@1 (%)
Pass@1 (%)
80
Table 13: Cross-operator pass@1 (%) under Direct prompting. Each cell averages over n ∈ {2, 3} problems per operator. CS = constraint scaling; SD = staticto-dynamic; OP = objective perturbation; GT = greedytrap.
20 0
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 differences.
both easy and hard shifts, without increasing T RAP R ATE 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 T RAP R ATE 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 referenceoptimal, 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 algorithmspecific evidence such as lazy propagation or DSU rollback. The full three-layer verifier performs best, reduc-
RAG vs Direct pass@1 by Shift Difficulty Easy Shifts (Jaccard â?¥ 0.46)
100
-25%
80 -6%
Pass@1 (%)
Hard Shifts (Jaccard < 0.46)
-6%
+22%
+32%
60 +7%
40 20 0
+20%
Direct RAG GPT-4o
GPT-4o -mini
Haiku 4.5
Gemini 2.5F
Llama 3.3-70B
GPT-4o
GPT-4o -mini
Haiku 4.5
Gemini 2.5F
Llama 3.3-70B
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 ∆T RAP R ATE from Direct to RAG.
Static AST only Runtime only Static + Tags Full 3-layer
F-Opt. ↓ F-Sub. ↓ Uncert. ↑ Agree. ↑ 5.8% 9.2% 3.4% 2.1%
3.2% 7.6% 2.8% 3.6%
4.1% 8.7% 5.1% 6.4%
86.9% 74.5% 89.2% 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 positives from 3.4% to 2.1%. The slightly higher U N CERTAIN rate reflects our conservative rule: when complexity evidence is incomplete, A LGO B ENCH withholds optimality credit. Thus, reliable O PT T and O PT S labels require combining static structure, deterministic tags, and scaling tests.
11
Supplementary Analysis: Pass@k Curves and Model Scaling
Pass@k curves. Figure 18 reports pass@k for k ∈ {1, 2, 3, 5} on 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 improvement, indicating that their failures are more often paradigm-level errors rather than sampling
100
False Optimal % Label Agreement %
10
Best
85
8 6
80
5.8%
75
4
3.4% 2.1%
2 0
95 90
9.2%
Static AST
Runtime Scale
Static +Tags
Full 3-layer
70
Label Agreement (%)
Verifier
(e) Complexity verifier validation 12 False Optimal Rate (%)
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.
65 60
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 T RAP R ATE (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 algorithm before coding. However, this robustness disappears under RAG-source: Gemini’s T RAP R ATE rises to 30.0%, the highest among all models, showing that retrieved source problems can anchor the model to the old algorithm. In contrast, RAG reduces T RAP R ATE 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 T RAP R ATE to 0% while raising GPT-4o’s to 25.5%. Strategy × model interaction. Prompting strategy has a strong model-specific effect. CoT gives
Pass@k Curves (Shifted, Direct)
100 90
Pass@k (%)
80 70 60 50
GPT-4o Haiku 4.5 Gemini 2.5F GPT-4o-mini Llama 3.3-70B
40 30
p@2, p@3: linear interpolation
1
2
3
k (number of samples)
5
Figure 18: Pass@k curves 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%), matching its pass@5 score and suggesting that explicit reasoning improves first-attempt stability. In contrast, CoT hurts GPT-4o (−18.2%) and Gemini 2.5 Flash (−9.1%), suggesting that forced reasoning can disrupt stronger models’ default solution path. RAG-source shows a similar inversion: it raises Gemini’s T RAP R ATE from 3.6% to 30.0%, but lowers T RAP R ATE for GPT-4o-mini and Claude Haiku 4.5. Thus, the same prompt strategy can either reduce or amplify old-template reuse depending on the model.
12
Related Work
Code and algorithmic benchmarks. HumanEval (Chen et al., 2021) and MBPP (Austin et al., 2021) made pass@k a 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. LiveCodeBench (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, A LGO B ENCH 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. DyCodeEval (Chen et al., 2025) creates semantically equivalent variants to test robustness under surfacelevel changes. Its goal is to keep the original algorithm valid while changing the problem form. A LGO B ENCH has a different goal. It changes the problem so that the original algorithm is no longer sufficient. A valid A LGO B ENCH 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 competitiveprogramming problem setters in a closed-loop generation process. This is related to our goal of building new algorithmic tasks, but the construction logic is different. A LGO B ENCH starts from a source problem with a known reference algorithm and applies controlled transformations. This source-to-target link makes it possible to measure old-template reuse directly, rather than only evaluating whether the generated problem is solvable. Complexity-aware evaluation. Most programming benchmarks use pass@k as 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. A LGO B ENCH adds deterministic time and space complexity verification, together with metrics such as O PT T, O PT S, T RAP R ATE, and G AP T. This allows the benchmark to separate functional correctness from algorithmic suitability.
13
Discussion
Memorization vs. reasoning. The paired 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 T RAP R ATE
Table 15: Comparison of A LGO B ENCH with related algorithmic and code evaluation benchmarks. Here, ✓indicates explicit support, ✗indicates no support, and ∼ indicates partial or indirect support. Benchmark HumanEval/MBPP LiveCodeBench DyCodeEval AutoCode A LGO B ENCH
Novel Tasks
Alg. Change
Old-Sol Reject
Cmplx. Metric
Det. Verify
✗ ✓ ✓ ✓ ✓
✗ ✗ ✗ ∼ ✓
✗ ✗ ✗ ✗ ✓
✗ ∼ ✗ ∼ ✓
✗ ✗ ✗ ✗ ✓
under Direct prompting, indicates that success on original problems often relies on reusable templates. A LGO B ENCH exposes this failure mode by testing whether models can revise the algorithm when the constraints invalidate the source solution. RAG can induce template anchoring. RAGsource provides the most similar source problem as context, which can help or hurt depending on the model. For Gemini 2.5 Flash, T RAP R ATE increases sharply from 3.6% under Direct prompting to 30.0% under RAG, showing that retrieved examples can anchor the model to the old algorithm. In contrast, RAG slightly reduces T RAP R ATE 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-aware metrics are necessary. Functional correctness alone misses many algorithmic failures. Across models, O PT T 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% O PT T, while GPT-4o-mini under CoT reaches 81.8% pass@1 but only 63.6% O PT T. These gaps show why O PT T, O PT S, T RAP R ATE, and G AP T are needed to evaluate algorithmic adaptation rather than test passing alone.
14
Conclusion
We presented A LGO B ENCH, an automatic framework 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 solution is no longer sufficient and a different algorithmic treatment is needed. The quality gates verify source-solution rejection, non-paraphrase status,
reference-solution correctness, and target complexity, allowing A LGO B ENCH to expose old-template reuse across models and prompting strategies.
Limitations The A LGO B ENCH complexity verifier currently supports Python and C++ only; support for Java, Go, and Rust is left for future work. The problem corpus focuses on competitive programming, which provides formal specifications and reliable judging but does not cover all forms of algorithmic reasoning. Some algorithm families, such as geometry, string algorithms, and number theory, are less represented. The five primary models (GPT-4o, GPT-4o-mini, Claude Haiku 4.5, Gemini 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 identifiable information. A LGO B ENCH 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://www.anthropic.com/news/ claude-haiku-4-5. Accessed: 2026-05-20. Anthropic. 2025b. Introducing Claude Opus 4.5. https://www.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 benchmarks. Preprint, arXiv:2501.10711. Version 4 revised 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 contamination. 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, Multimodality, Long Context, and Next Generation Agentic 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, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. 2021. Measuring coding challenge 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. Bulletin 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 SolarLezama, Koushik Sen, and Ion Stoica. 2024. LiveCodeBench: Holistic and contamination free evaluation 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, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2020. Retrieval-augmented generation for knowledgeintensive 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 Lingming Zhang. 2023. Is your code generated by ChatGPT really correct? rigorous evaluation of large language 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 refinement 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/. Accessed: 2026-05-20. OpenAI. 2026. Introducing GPT-5.4. https:// openai.com/index/introducing-gpt-5-4/. Accessed: 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, Ashwin 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 reasoning 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, ShubhAgrawal, 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: Benchmarking large language models in competitive programming. 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, Aleksandra Korolova, Peter Henderson, Natasha Jaques, Pramod Viswanath, and 2 others. 2025. Autocode: Llms as problem setters for competitive programming. Preprint, arXiv:2510.12803.
A
Detailed Transformation Operators
This section gives the full definitions of the ten transformation operators used by A LGO B ENCH. Each operator takes a source problem with a known reference algorithm and produces a generated problem whose solution requires a changed algorithmic treatment or a changed asymptotic target. CS — Constraint Scaling. This operator increases the input size so that the original complexity, such as O(n2 ) or O(n3 ), no longer fits the time limit. The generated problem therefore requires a faster algorithm. We apply this operator only when a verified faster solution exists for the same core problem. Common cases include O(n2 ) → O(n log n) and O(n3 ) → O(n2 ). SD — Static-to-Dynamic. This operator turns a static problem into an online one by adding update 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 include min-total → min-max, feasibility → counting modulo a prime, and value computation → lexicographically smallest construction. CC — Constraint Coupling. This operator adds a constraint, such as a budget, cooldown, or precedence relation, that creates dependence between choices that were independent in the source problem. 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 expands 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 methods under positive weights into shortest-path algorithms, or direct array indexing into coordinate compression. OR — Output Requirement Change. This operator changes what the problem asks the solver to
output while preserving much of the input structure. Instead of only returning an optimal value, the generated problem may ask for an optimal construction, 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 exchange argument. Examples include a type-switch budget in interval scheduling or a cooldown constraint 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 application 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 operator only when the wrapped version preserves deterministic judgeability. GS — Graph Structure Change. This operator 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 operator combines two compatible transformations to produce a larger algorithmic change. For example, a problem may first be changed from static to dynamic and then receive an output requirement 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 A LGO B ENCH only if it passes all four gates. Gate 1: Old-Solution Rejection. We run the original reference solution a∗ on the generated problem q ′ . The tests include random instances at
the generated constraint scale, adversarial cases targeting the old solution’s failure mode, and operatorspecific edge cases. A problem passes this gate only if a∗ fails by WA, TLE, or MLE on at least one test category. This gate ensures that the generated 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 â∗ and a brute-force oracle abf . The oracle is used only on small inputs, where exhaustive or clearly correct slow methods are feasible. We compare â∗ and abf on at least 1000 random small inputs. A candidate passes this gate only if the outputs match, the output format is deterministically judgeable, and â∗ satisfies the target time complexity T̂ ∗ . Gate 3: Similarity Filtering. We measure similarity between the source problem q and the generated problem q ′ using BM25 similarity, sentencetransformer cosine similarity, and n-gram overlap. These signals are combined into TextSim(q, q ′ ). A candidate is rejected if TextSim(q, q ′ ) ≥ τtext ,
(5)
Shifted variant. Given an array of n ≤ 2 × 105 integers and Q ≤ 2 × 105 operations, support either 1 l r x, which adds x to all elements in A[l..r], or 2 l r, which outputs maxri=l A[i]. The new reference solution uses a lazy segment tree with O((n + Q) log n) time and O(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 log n) time. Shifted variant. Each interval is assigned a type ti . The goal is to select the maximum number of non-overlapping intervals while allowing at most k consecutive type switches. The new reference solution uses dynamic programming over sorted intervals with a switch-count state and runs in O(nk log n) 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.
where τtext = 0.55 is calibrated using human annotation. We also require an algorithmic change, namely α̂ ̸= α or T̂ ∗ ̸= T ∗ . (6)
Example 3: Dynamic Connectivity Shift (SD)
This gate removes near-paraphrases and keeps problems whose source-to-target change is algorithmically meaningful.
Source. Given n ≤ 2000 nodes and m ≤ 5000 edges, answer connectivity queries. The reference solution uses DSU and runs in O(n + m) time for the static graph setting.
Gate 4: Complexity Verification. Finally, the new reference solution â∗ is checked by the deterministic complexity verifier described in Section 4. A candidate is rejected if the verifier marks the reference solution as U NCERTAIN or reports a mismatch with the target time or space complexity. This gate ensures that every accepted problem has a certified algorithmic target.
C
Example Benchmark Problems
Shifted variant. Given n ≤ 2 × 105 nodes and a sequence of Q operations, support edge insertion, edge deletion, and connectivity queries. The new reference solution uses offline dynamic connectivity with DSU rollback and a segment tree over time, running in O((n + Q) log Q · α(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.
Example 1: Range Query Shift (CS + SD) Source. Given a static array of n ≤ 105 inte5 gers, answer Pr Q ≤ 10 range-sum queries by outputting i=l A[i]. The reference solution uses prefix sums with O(n + Q) time and O(n) space.
D
Complexity Verifier: Implementation Details
Static AST analysis. Python submissions are parsed with the ast module, 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 as N , Q, and M , with loop bounds combined to estimate time complexity; • recursion depth and branching factor, with memoized 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 function as evidence for a segment tree. Algorithm-tag detection rules. The verifier assigns algorithm tags using deterministic structural rules. Examples include:
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.
• lazy_segment_tree: recursive range-query or range-update functions with lazy propagation before 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 with N ∈ {103 , 2×103 , 4× 103 , 8 × 103 , 1.6 × 104 , 3.2 × 104 }. For each input size, it performs five runs and uses the median runtime. It then fits a power-law model by log-log linear regression: log T = α log N + γ log log N + 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 in {curly braces} are filled per problem instance. All prompts are delivered as multi-turn chat messages.
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.
RAG-Source Model Output (excerpt) Step 1: The constraint N ≤ 2 × 105 and Q ≤ 2 × 105 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]
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
Strategy 3 — Self-Refine Self-Refine (Madaan et al., 2023) runs up to R=3 rounds. Round 1 uses the Direct prompt; subsequent 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.
Reference problem (similar, different): {retrieved_source_statement} Reference solution: {retrieved_source_solution}
but
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.
User Problem: {problem_statement} Constraints: {constraints} Your previous solution: {previous_solution} Feedback: {feedback_message} Please fix all issues and corrected Python solution.
output
a
Strategy 5 — Skill-Guided
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 corpus consists of all seed problems in A LGO B ENCH with their original reference solutions.
Skill-guided augments the CoT prompt with explicit 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
Example reflexion memory entry
Problem: {problem_statement} Input format: {input_format} Output format: {output_format} Constraints: {constraints} Examples: {examples}
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.
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.