Learning Task Decomposition to Assist Humans in Competitive Programming
Jiaxin Wen, Ruiqi Zhong, Pei Ke, Zhihong Shao, Hongning Wang, Minlie Huang
2024-08-09
Summary
This paper discusses a method for helping people solve complex programming problems by breaking down solutions into simpler parts, making it easier for them to understand and fix mistakes.
What's the problem?
When using language models to generate solutions for programming challenges, humans often find it difficult to understand these solutions and correct any errors. This is especially true for complex problems where the generated answers can be hard to follow, leading to frustration and inefficiency, particularly in competitive programming settings where time is limited.
What's the solution?
To address this issue, the authors propose a technique called task decomposition, which automatically breaks down complex programming solutions into smaller, more manageable subtasks. They introduce a new measurement called assistive value (AssistV) that evaluates how easy and quick it is for humans to repair these decomposed solutions. By collecting data on how humans interact with these subtasks, the researchers train their system to improve the quality of the decompositions. Their experiments show that this method allows non-experts to solve 33.3% more problems and work 3.3 times faster than before, helping them perform at levels comparable to experienced programmers.
Why it matters?
This research is important because it enhances the ability of everyday programmers to tackle difficult coding challenges more effectively. By providing clearer guidance through task decomposition, this approach can improve learning and performance in programming competitions and other scenarios where quick problem-solving is essential.
Abstract
When using language models (LMs) to solve complex problems, humans might struggle to understand the LM-generated solutions and repair the flawed ones. To assist humans in repairing them, we propose to automatically decompose complex solutions into multiple simpler pieces that correspond to specific subtasks. We introduce a novel objective for learning task decomposition, termed assistive value (AssistV), which measures the feasibility and speed for humans to repair the decomposed solution. We collect a dataset of human repair experiences on different decomposed solutions. Utilizing the collected data as in-context examples, we then learn to critique, refine, and rank decomposed solutions to improve AssistV. We validate our method under competitive programming problems: under 177 hours of human study, our method enables non-experts to solve 33.3\% more problems, speeds them up by 3.3x, and empowers them to match unassisted experts.