2024

Learning Task Decomposition to Assist Humans in Competitive Programming

Wen, Jiaxin, Zhong, Ruiqi, Ke, Pei et al.

Understand

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.

Built on

A complexity measure
Thomas J McCabe. 1976 · 1976
Earlier work this paper cites.
The use of the area under the roc curve in the evaluation of machine learning algorithms
Andrew P Bradley. 1997 · 1997
Earlier work this paper cites.
Decomposed versus holistic estimates of effort required for software writing tasks
Terry Connolly and Doug Dean. 1997 · 1997
Earlier work this paper cites.
Does learning a complex task have to be complex?: A study in learning decomposition
Frank J Lee and John R Anderson. 2001 · 2001
Earlier work this paper cites.
Relationships: computational thinking, pedagogy of programming, and bloom’s taxonomy
Cynthia C Selby. 2015 · 2015
Earlier work this paper cites.
Concrete problems in ai safety
Original
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. 2016 · 2016
Earlier work this paper cites.
Revisit of automatic debugging via human focus-tracking analysis
Xiaoyuan Xie, Zicong Liu, Shuo Song, Zhenyu Chen, Jifeng Xuan, and Baowen Xu. 2016 · 2016
Earlier work this paper cites.
Supervising strong learners by amplifying weak experts
Original
Paul Christiano, Buck Shlegeris, and Dario Amodei. 2018 · 2018
Earlier work this paper cites.
Program synthesis with large language models
Original
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. 2021 · 2021
Earlier work this paper cites.
Evaluating large language models trained on code
Original
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021 · 2021
Earlier work this paper cites.
Introducing github copilot
Github. 2021 · 2021
Earlier work this paper cites.
Measuring coding challenge competence with apps
Original
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, et al. 2021 · 2021
Earlier work this paper cites.

Similar

Recursively summarizing books with human feedback
Original
Jeff Wu, Long Ouyang, Daniel M Ziegler, Nisan Stiennon, Ryan Lowe, Jan Leike, and Paul Christiano. 2021 · 2021
Cited alongside, same era.
Constitutional ai: Harmlessness from ai feedback
Original
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. 2022 · 2022
Cited alongside, same era.
Successive prompting for decomposing complex questions
Original
Dheeru Dua, Shivanshu Gupta, Sameer Singh, and Matt Gardner. 2022 · 2022
Cited alongside, same era.
Decomposed prompting: A modular approach for solving complex tasks
Original
Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. 2022 · 2022
Cited alongside, same era.
Competition-level code generation with alphacode
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. 2022 · 2022
Cited alongside, same era.
Training language models to follow instructions with human feedback
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022 · 2022
Cited alongside, same era.
Two-turn debate doesn’t help humans answer hard reading comprehension questions
Original
Alicia Parrish, Harsh Trivedi, Nikita Nangia, Vishakh Padmakumar, Jason Phang, Amanpreet Singh Saimbhi, and Samuel R Bowman. 2022 · 2022
Cited alongside, same era.
Self-critiquing models for assisting human evaluators
Original
William Saunders, Catherine Yeh, Jeff Wu, Steven Bills, Long Ouyang, Jonathan Ward, and Jan Leike. 2022 · 2022
Cited alongside, same era.
Expectation vs. experience: Evaluating the usability of code generation tools powered by large language models
Priyan Vaithilingam, Tianyi Zhang, and Elena L Glassman. 2022 · 2022
Cited alongside, same era.
React: Synergizing reasoning and acting in language models
Original
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2022 · 2022
Cited alongside, same era.
Detecting the reasons for program decomposition in cs1 and evaluating their impact
Charis Charitsis, Chris Piech, and John C Mitchell. 2023 · 2023
Cited alongside, same era.
Teaching large language models to self-debug
Original
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. 2023 · 2023
Cited alongside, same era.

Then

Humans decompose tasks by trading off utility and computational cost
Carlos G Correa, Mark K Ho, Frederick Callaway, Nathaniel D Daw, and Thomas L Griffiths. 2023 · 2023
Later among the works it cites.
Repair is nearly generation: Multilingual program repair with llms
Harshit Joshi, José Cambronero Sanchez, Sumit Gulwani, Vu Le, Gust Verbruggen, and Ivan Radiček. 2023 · 2023
Later among the works it cites.
Starcoder: may the source be with you!
Original
Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, et al. 2023 · 2023
Later among the works it cites.
Self-refine: Iterative refinement with self-feedback
Original
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. 2023 · 2023
Later among the works it cites.
GPT-4 technical report
Original
OpenAI. 2023 · 2023
Later among the works it cites.
Gpqa: A graduate-level google-proof q&a benchmark
Original
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R Bowman. 2023 · 2023
Later among the works it cites.
Code llama: Open foundation models for code
Original
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al. 2023 · 2023
Later among the works it cites.
Principle-driven self-alignment of language models from scratch with minimal human supervision
Original
Zhiqing Sun, Yikang Shen, Qinhong Zhou, Hongxin Zhang, Zhenfang Chen, David Cox, Yiming Yang, and Chuang Gan. 2023 · 2023
Later among the works it cites.
Parsel: Algorithmic reasoning with language models by composing decompositions
Eric Zelikman, Qian Huang, Gabriel Poesia, Noah Goodman, and Nick Haber. 2023 · 2023
Later among the works it cites.
Non-programmers can label programs indirectly via active examples: A case study with text-to-sql
Ruiqi Zhong, Charlie Snell, Dan Klein, and Jason Eisner. 2023 · 2023
Later among the works it cites.
Solving olympiad geometry without human demonstrations
Trieu H Trinh, Yuhuai Wu, Quoc V Le, He He, and Thang Luong. 2024 · 2024
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…