Assessing the Impact of Retrieval-Augmented Generation on Algorithmic Problem-Solving
Authors: Gabriel Souza Baggio, Gabriel Machado Lunardi, Guilherme Medeiros Machado, Subhankar Maity, Faiza Belbachir, José Palazzo Moreira de Oliveira
Organizations: Federal University of Santa Maria, Roraima Avenue, 1000, Santa Maria, 97105-800, Rio Grande do Sul, Brazil · LyRIDS lab, ECE Engineering School, 10 Rue Sextius Michel, Paris, 75015, Île-de-France, France · Federal University of Rio Grande do Sul, Informatics Institute, Bento Gonçalves Avenue, 9500, Porto Alegre, 91501-970, Rio Grande do Sul, Brazil
Competitive programming problems pose distinctive challenges for Large Language Models, as they demand not only proficient code generation but also advanced algorithmic reasoning. This study presents a Retrieval-Augmented Generation approach specifically designed to enhance the capacity of Large Language Models to address such problems. Our approach integrates an embedding-based retrieval mechanism and a similarity search algorithm to identify analogous problems within a knowledge database, employing a dynamically adjusted threshold to mitigate retrieval noise. We conducted an evaluation using the CodeContests dataset, focusing on the test split problems that exhibit similarity to instances from the training split. The experimental framework considered three conditions: (i) problems provided solely with their original descriptions, (ii) problems supplemented with randomly selected examples from the training split, and (iii) problems augmented with similar examples retrieved through the proposed method. In addition, we incorporated a Min-K membership inference analysis to examine whether the generated code solutions were influenced by potential memorization of training data within the evaluated Large Language Models. This complementary perspective enables a deeper understanding of model behavior by distinguishing genuine generalization through retrieval from implicit recall of pretraining samples. Performance was assessed using both pass rates and the CodeForces Elo rating of the problems. The results provide empirical evidence that similarity-based retrieval substantially enhances Large Language Models performance in competitive programming scenarios, offering an scalable framework for improving code generation in algorithmic problem-solving contexts.
Figures & tables
Figure 1: System Architecture and Execution Pipeline
Dataset
# Problems
Problems’ Year(s)
USACO [ 33 ]
307
2011-2024
CodeElo [ 32 ]
408
2024
LiveCodeBench [ 19 ]
442
2023-2024
LiveCodeBench Pro [ 43 ]
∼ 584
Updated Lively
CodeContests [ 23 ]
13,493
2021
Table 1: Summary of competitive programming datasets used for LLM evaluation
Full Model Name
Org.
Context Tokens
Cut-off Date
DeepSeek-R1 [ 1 ]
DeepSeek
131K
Not specified
Gemini 2.0 Flash [ 14 ]
Google
1 million
June 2024
Claude 3.7 Sonnet [ 4 ]
Anthropic
200K
October 2024
Qwen2.5-Coder-32B [ 2 ]
Alibaba
128K
End of 2023
GPT-4-omni [ 28 ]
OpenAI
128K
September 2023
GPT-3.5 Turbo [ 29 ]
OpenAI
16K
September 2021
Table 2: Overview of models with organization, context window and cut-off date.
Figure 2: Categories of the Problems from the Knowledge and Test Datasets
Knowledge Dataset
Test Dataset
Difficulty
Count
Proportion (%)
Count
Proportion (%)
Easy
901
11.70
18
22.22
Medium
3759
48.81
31
38.27
Hard
3041
39.49
32
39.51
Table 3: Distribution of Problem Difficulty in the Knowledge and Test Datasets
Figure 3: Correctness analysis
Model
Easy
Medium
Hard
Rating
Pct.
Zero-shot
DeepSeek R1
100.0%
80.6%
21.9%
2080
2.9%
Gemini 2.0
61.1%
12.9%
0.0%
983
54.3%
Claude 3.7 Sonnet
50.0%
16.1%
0.0%
955
57.0%
GPT 4o
27.8%
3.2%
0.0%
706
79.8%
GPT-3.5
5.6%
0.0%
0.0%
412
90.3%
Table 4: Performance Based on Difficulty and Community Percentile Rating
Category
Zero-shot
Random-retrieval
RAG
math
2177 (1.7%)
2042 (3.2%)
2177 (1.7%)
dp
2066 (3.0%)
1852 (5.4%)
2066 (3.0%)
implementation
1832 (5.7%)
1832 (5.7%)
1832 (5.7%)
greedy
1963 (3.9%)
1806 (6.1%)
2052 (3.1%)
brute force
1967 (3.8%)
1967 (3.8%)
1967 (3.8%)
data structures
2063 (3.0%)
1957 (3.9%)
1851 (5.5%)
Table 5: DeepSeek-R1 Elo Rating and Rank by Problem Category
Large language models (LLMs) still struggle with the rigorous reasoning demands of hard competitive programming. While recent multi-agent frameworks attempt to bridge this reliability gap, they remain fundamentally stateless: they rely on static retrieval and discard the valuable problem-solving and debugging experience gained from previous tasks. To address this, we present Solvita, an agentic evolution framework that enables continuous learning without requiring weight updates to the underlying LLM. Solvita reorganizes problem-solving into a closed-loop system of strategy selection, program synthesis, certified supervision, and targeted hacking, executed by four specialized agents: Planner, Solver, Oracle, and Hacker. Crucially, each agent is paired with a trainable, graph-structured knowledge network. As the system operates, outcome signals, such as pass/fail verdicts, test certification quality, and adversarial vulnerabilities discovered by the Hacker, are recast as reinforcement learning updates to these network weights. This allows the agents to dynamically route future queries based on past successes and failures, effectively accumulating transferable reasoning experience over time. Evaluated across CodeContests, APPS, AetherCode, and live Codeforces rounds, Solvita establishes a new state-of-the-art among code-generation agents, outperforming existing multi-agent pipelines and nearly doubling the accuracy of single-pass baselines.
Han Li, Jinyu Tian, Rili Feng +10
Nanjing University · Independent Researcher · Tsinghua University
Large language models (LLMs) have demonstrated strong performance in code generation, where success depends on both recalling relevant algorithmic knowledge and reasoning about how to apply it. However, existing LLM pipelines are opaque, with no explicit separation between these two components. We argue that for well-known algorithms whose canonical implementations are widely accessible in pretraining corpora, code generation is better measured as parametric code retrieval: reproducing a named algorithm from internalised knowledge rather than synthesizing a novel one. We introduce AlgoREval, a benchmark of 599 problems spanning classical 77 algorithms across 14 domains, 7 programming languages, and 4 graph-input representations to evaluate this capability in isolation, and assess 15 models (7B--34B parameters) in a zero-shot setting. We find substantial variation in retrieval accuracy across languages and input representations, even for widely documented algorithms and show that prompt augmentation with retrieved code snippets or structured algorithmic hints improve accuracy on complex algorithms, while SFT achieves broader language gains and GRPO achieves larger per-language gains on specific languages. Together, our results establish parametric code retrieval as a distinct, measurable capability and caution against deploying AI-generated algorithmic code without systematic validation.\footnote{Code and dataset are available at https://github.com/Nickil21/AlgoREval
Nickil Maveli, Antonio Vergari, Shay B. Cohen
School of Informatics, University of Edinburgh 10 Crichton Street, Edinburgh, EH8 9AB
Recent studies have shown that Large Language Models can effectively solve problems and fix bugs in diverse programming environments, including competitive programming. Existing approaches primarily evaluate LLM performance in problem solving or bug fixing independently, but do not explore the relationship between these two capabilities. This work focuses on determining how much the LLM deviates from a buggy solution to fix the bug compared to a human-written patch, and if there is a bias towards generating entirely new solutions. We construct a dataset with all the submissions (∼ 3000) from a couple of users from Codeforces, and we match each buggy submission with its corresponding human fix. By using the similarity between the buggy solution and the human fix as a baseline, we evaluate the quality of LLM-generated bug fixes on 3 OpenAI GPT models (gpt-5-nano, gpt-5-mini, gpt-5.1). We check if the generated solutions solve the problem by using the Codeforces-R1 dataset, an openly available dataset that has tests generated with the DeepSeek-R1 model. Our findings suggest that LLMs tend to modify more lines than necessary compared to human fixes and, in some cases, generate entirely new solutions. We also observe that LLMs solve more problems correctly when allowed to generate solutions from scratch rather than patch buggy submissions, even when those submissions are close to the human patch. This has important implications for the design of AI-assisted programming tools, particularly in supporting user debugging processes and promoting incremental problem-solving strategies rather than solution replacement.
Alexandru Stefan Stoica, Traian Rebedea, Marian Cristian Mihaescu
University Politehnica of Bucharest Bucharest, Romania · University of Craiova Craiova, Romania