Large language models have substantially advanced automatic code generation, but competitive programming remains a demanding test of their reasoning abilities. Solving these problems requires more than producing syntactically valid code: a model must abstract a narrative specification into its underlying mathematical structure, discover an efficient algorithm, develop the algorithm into a complete plan that accounts for correctness, complexity, and edge cases, and finally translate the plan into an executable program that succeeds on unseen tests under strict resource constraints. This complex process requires strategy exploration and problem-solving skills, and is beyond implementing straightforward functionalities. Human competitors typically develop these skills through algorithmic principles, worked examples, and expert-written editorials rather than through problem–program pairs alone. This thesis proposes to utilize natural language as an intermediate representation between problem understanding and reliable program synthesis.
This thesis investigates how to leverage and improve LLMs’ abilities in natural language reasoning, specifically in the context of solving competitive-level programming problems. It first decomposes competitive programming problem-solving into strategy discovery, specific verbal solution details, and implementation. Across the evaluated settings, large language models can often explain verified human solutions and implement programs from detailed verbal descriptions even when they struggle to solve the same problems directly. These results suggest that the main bottleneck lies less in translating a complete solution into code than in discovering the correct algorithmic strategy and specifying it with sufficient precision.
Building on this diagnosis, the thesis develops an explanation-based distillation framework that first automatically generates editorial-style reasoning from verified human programs and uses these explanations to teach a separate reasoning model to guide code generation on new problems. The findings show that semantically rich natural-language supervision transfers algorithmic knowledge more effectively than directly training in the problem-to-code setting and encourages the use of more efficient strategies rather than superficial or brute-force implementations.
The thesis then introduces CodeTree, which operationalizes the separation of reasoning and implementation through an agent-guided search process: distinct roles propose strategies, implement programs, diagnose failures, and evaluate candidate solutions, while execution evidence and model-generated critique determine whether a search path should be expanded, revised, discarded, or accepted. This study finds that exploring diverse strategies and making informed search decisions are generally more effective than repeatedly refining a single initial solution, although successful role decomposition depends on the underlying model’s ability to follow specialized instructions.
The thesis next examines whether stronger problem-solving performance implies transferable algorithmic understanding. AlgoSimBench evaluates whether models can recognize problems that share an underlying solution method despite differences in wording and narrative context, and demonstrates that solving individual programming tasks and recognizing reusable algorithmic structure are distinct capabilities. The results also show that comparing generated solution attempts can expose algorithmic structure more clearly than comparing raw problem statements, even when the attempted solutions are not fully correct.
Finally, the thesis extends this investigation to code retrieval through InstEmbed, an instruction-sensitive representation-learning framework in which the desired target, definition of similarity, and relevant portion of the query jointly determine what should be retrieved. By contrasting documents that are related to the same query but valid under different instructions, the framework learns to distinguish general semantic relevance from task-specific usefulness and improves both target-aware and noise-robust retrieval.
Together, these studies establish natural language as a practical intermediate representation for learning, exploring, evaluating, and retrieving algorithmic knowledge, bridging the gap between problem and code, while showing that reliable code generation requires explicit attention to both the structure of the reasoning process and the generalizability of the representations it produces.
