Divide-and-Conquer Meets Consensus: Unleashing the Power of Functions in Code Generation

Meta info.

• Authors: Jingchang Chen, Hongxuan Tang, Zheng Chu, Qianglong Chen, Zekun Wang, Ming Liu, Bing Qin
• Paper: https://openreview.net/pdf?id=cFqAANINgW
• Affiliation: Harbin Institute of Technology
• Published: September 26, 2024
• Code: https://github.com/cometeme/funcoder
• Conference: NeurIPS2024

TL; DR

Divide-and-Conquer 전략에 기능적 합의(functional consensus)를 접목한 CodeGen framework FUNCODER 제안

Background

LLM 등장으로 codegen 성능이 크게 발전된 건 맞지만, requirements가 복잡한 programming은 여전히 도전 과제

Problem States

codegen 과정에 step을 나누거나 pipeline 방식을 적용하게 되면 복잡성이 증대되고(앞단계 오류 실패시 뒤로 전파), LLM 의존성이 높고 (보통 모델 사이즈에 의존), LLM이 생성한 Testcase를 활용한 self-testing의 신뢰성 저하 등 문제가 산재

• research question: 복잡도 높고 self-testing의 신뢰도를 높이는 방향으로 codegen을 (작은 모델에서 더) 효율적으로 하는 방법 고안

Suggestions

FUNCODER

• Divide-and-Conquer: 복잡성 감소 효과 기대
  • Divide: 복잡한 문제(froot)를 하위 함수(fi)로 재귀적으로 분해, 계층적 의존성 트리 생성(T)
  • Conquer: 각 함수는 독립적으로 풀고 나중에 최종 프로그램으로 합성. T의 leaf부터 bottom up 방식으로 탐색하여 합성을 반복하여 f*cur 구현
• functional consensus: 오류 전파 방지 기대
  • 후보 함수를 여러개 샘플링(n회 생성) > 프로그램 동작 유사성 측정(다양한 입력에 대한 출력 결과 비교) > 유사성 기반 합의 함수(가장 일관된 동작을 보이는 후보) 선택
  • 생성 코드 신뢰성 향상 효과
    • self-testing하면 테스트 케이스 자체의 신뢰성 보장 안 되는 문제에 대해, 테스트 케이스를 명시적으로 만들지 않고 함수를 여러개 만들고 각각의 출력을 직접 비교하는 방식으로 우회
  • LLM 크기에 상관없이 codegen 성능을 향상시키는 데 효과적이라는 결론
  • 토큰 사용량도 기존 방식이랑 비슷하다고.

Effects

FUNCODER가 LLM 기반 코드 생성의 효율성과 품질을 향상시키는 데 크게 기여한다.

• backbone: GPT-3.5-turbo, GPT-4 등
• 코드 생성 (HumanEval, MBPP, xCodeEval) Result:
  • 기존 대비 평균 HumanEval +9.8%, MBPP +3.3%, xCodeEval +10.4% 향상
  • funcoder-StableCode3b: HumanEval 기준 GPT-4 성능의 약 97.7%에 근접 (vanilla GPT-3.5의 약 118.6%의 상대적 성능)
  • 정확성 평가에서 functional consensus가 self-testing보다 우수 (신뢰성 향상)
• 수학 추론 (MATH) Result:
  • funcoder-GPT-4: SOTA Cumulative Reasoning 대비 +(6.0, 8.3%), PoT(vanilla program-aided baseline) 대비 +(10.0, 14.7%)
  • funcoder-GPT-3.5-turbo: SOTA Cumulative Reasoning 대비 +(6.2, 11.1%), PoT 대비 +(13.0, 31.7%)
  • Divide-and-Conquer가 도메인별로 특정돼서 각 MATH 주제에 필요한 특정 지식을 반영하기 때문에 성능 높이는듯

Personal note. 효과가 좋은건 물론이고 작은 모델에서 성능 향상도 인상적이고 그림들이 분명해서 그런지 논문도 되게 깔끔하게 쓰여있네요.