Learning Task Decomposition to Assist Humans in Competitive Programming (2024)

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.

## introduction with their increased capabilities, language models (lms) are used to perform increasingly complex and high-impact problems @xcite @xcite . the scalable oversight challenge emerges @xcite : lms might fail to provide reliable solutions for these problems, but it is also difficult for humans to evaluate and improve lms' solutions due to therequired significant time and expertise. one strategy to assist humans is task decomposition: as shown in figure 1 , humans can more easily understand and repair complex solutions after they are decomposed into simpler pieces that correspond to specific subtasks @xcite . however, not all decompositions are helpful, and it is challenging for humans to design an effective one @xcite ; correa † corresponding author @xcite . for example, @xcite shows that improper decomposition designed by novice programmers can impede human debugging performance. to decompose better, we need methods beyond using fixed heuristic rules @xcite or learning from author-crafted demonstrations @xcite . in this paper, we introduce a novel objective for learning task decomposition: assistive value (assistv, equation 1 ), which measures the feasibility and speed of humans to repair a decomposed solution in the actual annotation process (figure 1 right). to improve assistv, we first collect a dataset of decompositions, measure their assistv, and ask human annotators to provide a natural language critique on what makes a decomposition (not) helpful. then we design a three-stage process to generate high-assistv decompositions, where each stage is implemented by an llm that learns from our dataset in context: 1) learn a critique model π critique for predicting human critique on how to improve the initial decomposition for higher assistv, 2) learn a refine model π refine to incorporate the critique to refine the initial decomposition, and 3) learn a rank model π rank to select a decomposition with high assistv. we chose competitive programming as a testbed to validate our method for scalable oversight, since it is a challenging task that both lms and humans alone struggle to solve. we recruit 30 python programmers, including 11 experts foot_0 and 19 nonexperts, to repair model-generated program solutions for competitive coding problems, resulting in a total of 177 worker hours. experiment results show that our method enables humans to solve 33.3% more problems, speeds up non-experts and experts by 3.3 and 2.4 times, and assists nonexperts to match the performance of non-assisted ## conclusion this paper focuses on assisting humans in supervising lms on complex problems by automated task decomposition. we introduce a novel objective for learning task decomposition: assistive value (assistv), which measures the feasibility and speed of humans to repair a decomposed solution. we collect a dataset of decompositions, measure their assistv, and ask human annotators to provide a natural language critique on what makes a decomposition (not) helpful. we then learn to critique, refine, and rank decompositions to generate high-assistv decompositions. experiment results demonstrate that our method can effectively assist humans in providing higher-quality supervision with significantly less time. notably, our method assists non-experts in matching unassisted experts. overall, we show that even when lms cannot solve the problem themselves, they can still learn to assist humans by learning from human repair experiences. these results highlight the potential of learning-based methods to assist humans with scalable oversight.