💻 computer science

Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing how to Conquer

이 논문은 분해(decomposition)의 품질이 솔버 상대적이며, 정답(ground-truth) 하위 목표와 완벽하게 일치하지 않는 차선책의 분해가 오히려 더 우수한 엔드 투 엔드 성능을 낼 수 있음을 입증함으로써, 엄격한 정답 일치보다는 솔버의 추적 가능성(tractability)을 위해 분해기(decomposer)를 최적화하는 방식인 솔버 인식 분해(Solver-Aware Decomposition, SAD) 학습 프레임워크를 소개한다.

원저자: Janis Zenkner, Tobias Sesterhenn, Tim Grams, Christian Bartelt

게시일 2026-08-05

📖 6 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Janis Zenkner, Tobias Sesterhenn, Tim Grams, Christian Bartelt

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

컴퓨터가 단 몇 개의 예시만 보고도 당신이 원하는 바를 수행하는 코드를 스스로 작성하는 법을 배울 수 있는 세상을 상상해 보세요. 이것이 바로 **프로그래밍 바이 이그잼플(Programming-by-Example, PBE)**이라는 흥미로운 분야입니다. 이것은 로봇에게 케이크 굽는 법을 가르치는 것과 같습니다. 모든 단계에 대한 매뉴얼을 일일이 쓰는 것이 아니라, 그저 "여기 밀가루가 담긴 그릇이 있고, 여기 완성된 케이크가 있어"라고 보여주면 로봇이 스스로 레시피를 알아내는 방식입니다. 이 과정이 복잡한 과업에서도 작동하게 만들기 위해, 똑똑한 연구자들은 "분할 정복(divide-and-conquer)" 전략을 사용합니다. 그들은 크고 무서운 문제(케이크 굽기)를 작고 관리 가능한 하위 문제들(밀가루 섞기, 달걀 넣기, 반죽 굽기)로 나눕니다.

이 설정에는 두 명의 주요 등장인물이 있습니다. 바로 **디콤포저(Decomposer, 분해자)**와 **신세사이저(Synthesizer, 합성자)**입니다. 디콤포저는 계획가입니다. 큰 목표를 보고 "좋아, 먼저 밀가루를 섞어야 해"라고 말합니다. 신세사이저는 일꾼입니다. 그 지침을 받아 실제로 밀가루를 섞는 코드를 작성합니다. 수년 동안 과학자들은 인간 전문가가 만든 '완벽한' 계획(Ground Truth, 정답)을 디콤포저에게 보여주며 훈련시켜 왔습니다. 아이디어는 간단했습니다. 만약 인간 전문가가 "밀가루를 섞으라"고 했다면, 디콤포저도 정확히 그렇게 말하도록 배우는 것입니다. 하지만 이 논문은 까다로운 질문을 던집니다. 만약 인간 전문가의 계획이 인간에게는 완벽할지 몰라도, 로봇 일꾼에게는 악몽이라면 어떻게 될까요? 만약 로봇이 그 "완벽한" 계획 때문에 혼란에 빠져 그냥 포기해 버린다면 어떻게 될까요?

이 논문은 **솔버 어웨어 디콤포지션(Solver-Aware Decomposition, SAD, 해결사 인지적 분해)**이라는 새로운 훈련 방식을 소개합니다. 연구자들은 단순히 인간의 계획을 복사하는 것이 항상 효과적이지 않다는 것을 발견했습니다. 왜냐하면 로봇 일꾼(신세사이저)은 자신만의 강점과 약점을 가지고 있기 때문입니다. 때로는 인간의 버전과 약간 다른 계획이 로봇이 따르기에 훨씬 더 쉬울 수도 있습니다. 디콤포저가 단순히 인간을 복사하는 대신, 로봇의 고군분투와 성공으로부터 직접 배우게 함으로써 시스템은 문제를 훨씬 더 잘 해결하게 됩니다. 실제로 그들은 기묘한 "정확도 역설(accuracy paradox)"을 발견했습니다. 인간을 가장 정확하게 복사한 디콤포저가 오히려 로봇이 과업을 완수하도록 만드는 데 있어서는 최악이었다는 것입니다. 가장 뛰어난 디콤포저는 인간의 원래 대본을 따르는 것을 넘어, 로봇의 언어를 말하는 법을 아는 디콤포저였습니다.

두 계획가의 이야기

이것이 왜 중요한지 이해하기 위해, 여러분이 아주 문자 그대로 행동하고 약간 서투른 로봇에게 블록 탑을 쌓는 법을 가르치고 있다고 상상해 봅시다. 여러분에게는 인간 설계자(전문가)와 로봇 빌더(신세사이저)가 있습니다.

옛날 방식: 설계자를 복사하기
과거에는 연구자들이 로봇의 "계획가"(디콤포저)를 훈련시킬 때 인간 설계자의 청사진을 보여주었습니다. 만약 설계자가 "먼저 정사각형 밑판을 만들어라"라고 했다면, 계획가는 "정사각형 밑판을 만들어라"라고 말하도록 배웠습니다. 논리는 이랬습니다. "인간이 옳다고 한다면, 그것은 옳은 것이다."

하지만 여기 함정이 있습니다. 로봇 빌더는 서투릅니다. 그것은 팔을 움직이는 특정한 방식이 있습니다. 예를 들어, 직선으로 블록을 쌓는 것은 잘할지 몰라도 완벽한 정사각형을 만드는 데는 서툴 수 있습니다. 만약 계획가가 빌더에게 "정사각형을 만들어"라고 명령하면, 빌더는 비록 그 정사각형이 인간의 눈에는 "옳은" 단계일지라도, 제자리에서 뱅글뱅글 돌다가 결국 포기해 버릴 수도 있습니다. 계획가는 인간의 훌륭한 학생이었지만, 로봇에게는 나쁜 선생님이었습니다.

새로운 방식: 빌더의 목소리에 귀 기울이기 (SAD)
논문의 저자들은 계획가가 빌더의 한계를 알아야 한다는 점을 깨달았습니다. 그들은 **솔버 어웨어 디콤포지션(SAD)**이라는 새로운 훈련 방식을 만들었습니다. 단순히 인간을 복사하는 대신, 계획가는 학습하는 동안 빌더로부터 피드백을 받습니다.

계획가가 단계를 제안한다고 상상해 보세요. 빌더가 그것을 실행하려고 시도합니다.

만약 빌더가 성공하면, 계획가는 높은 점수를 받습니다.
만약 빌더가 막히면, 설령 그 단계가 인간의 청사진과 똑같이 생겼더라도 계획가는 낮은 점수를 받습니다.

시간이 흐르면서 계획가는 빌더가 실제로 감당할 수 있는 단계를 제안하는 법을 배웁니다. 인간 설계자는 정사각형을 선호하더라도, 계획가는 빌더가 줄을 잘 세운다는 것을 알기에 "먼저 블록을 긴 줄로 세워보자"라고 말할 수 있습니다. 계획가는 단순히 "인간의 언어"를 말하는 것이 아니라 "빌더의 언어"를 말하는 법을 배웁니다.

거대한 놀라움: 정확도 역설

이 연구에서 가장 매혹적인 부분은 그들이 **정확도 역설(Accuracy Paradox)**이라고 부르는 것입니다.

보통 학교에서는 선생님의 정답지를 완벽하게 베끼면 A를 받습니다. 하지만 이 로봇의 세계에서는 정반대의 현상이 일어났습니다. 연구자들은 두 가지 계획가를 비교했습니다:

복사꾼(The Copycat): 이 계획가는 인간 설계자의 청사진을 최대한 가깝게 맞추려고 노력했습니다. 이 계획가는 인간을 복사하는 데 매우 정확했습니다.
솔버 어웨어 계획가 (SAD): 이 계획가는 로봇 빌더가 실제로 할 수 있는 것에 맞추려고 노력했습니다. 이 계획가는 종종 인간의 청사진과는 다르게 보이는 단계를 제안했습니다.

결과는 충격적이었습니다. 복사꾼은 인간과 일치하는 데는 뛰어났지만(높은 "분해 정확도"), 로봇이 탑을 쌓도록 만드는 데는 대부분 실패했습니다. **솔버 어웨어 계획가(SAD)**는 인간의 단어와 일치하는 정도는 낮았지만(낮은 "분해 정확도"), 로봇이 탑을 쌓도록 만드는 데 훨씬 더 자주 성공했습니다.

결국, 인간에 따라 "정확하다"는 것이 로봇에게 "유용하다"는 것을 의미하지는 않는다는 사실이 드러났습니다. 인간의 계획은 논리적으로는 완벽할 수 있지만, 로봇이 실행할 수 없다면 그 계획은 쓸모가 없습니다. SAD 계획가는 "인간처럼 보이는 것"을 "일을 완수하는 것"과 맞바꾸는 법을 배웠습니다.

이것이 단순한 우연이 아님을 증명하기

연구자들은 이것이 단순히 운 좋은 사고가 아님을 확인하기 위해 세 가지 다른 "세계"(도메인)에서 아이디어를 테스트했습니다:

Deepcoder & Lambdabeam: 이곳은 로봇이 숫자 리스트를 조작해야 하는 세계입니다. 여기서 로봇은 문제를 해결하기 위한 여러 가지 방법이 있으며, 올바른 경로를 선택해야 합니다. 이 세계들에서 SAD는 경이로운 성과를 냈습니다. 특히 과업이 길어지고 어려워질수록, SAD는 복사꾼보다 훨씬 더 많은 과업을 해결했습니다.
Robustfill: 이곳은 문자열 조작(단어 속의 글자를 재배열하는 것과 같은)의 세계입니다. 이 세계에서 단계는 매우 엄격합니다. 즉, 오직 하나의 올바른 방법만 존재하며 로봇에게는 선택권이 없습니다. 여기서 SAD는 아무런 도움이 되지 않았습니다. 복사꾼과 SAD는 똑같이 작동했습니다.

이것은 퍼즐의 매우 중요한 조각입니다. 이는 SAD가 오직 **모호함(ambiguity)**이 있을 때, 즉 로봇이 서로 다른 경로 중 하나를 선택해야 할 때만 도움이 된다는 것을 증명합니다. 경로가 고정되어 있다면 로봇에게 특별한 계획가는 필요하지 않습니다. 하지만 선택지가 있을 때는, 계획가가 로봇이 실제로 걸을 수 있는 경로가 무엇인지 알아야 합니다.

"오라클" 테스트: 인간이 틀렸을 때

연구자들은 한 단계 더 나아갔습니다. 그들은 계획가를 완전히 건너뛰고 인간의 완벽한 청사진을 강제로 따르게 하는 "신 모드(God-mode)" 테스트를 만들었습니다. 그들은 이를 **그라운드 트루스 오라클(Ground Truth Oracle)**이라고 불렀습니다.

그들은 오라클이 가장 뛰어난 성능을 보일 것이라고 예상했습니다. 그리고 보통은 그랬습니다. 하지만 반전이 있었습니다. SAD는 오라클조차 해결하지 못한 일부 과업을 해결했습니다.

어떻게 그럴 수 있을까요? 어떻게 "완벽한" 인간의 계획을 따르는 로봇이, 그 계획을 무시하는 로봇보다 더 잘할 수 있을까요?
그 답은 인간의 "완벽한" 계획이 때때로 로봇을 함정에 빠뜨릴 수 있다는 것입니다. 인간은 논리적으로는 타당하지만 로봇이 탐색 공간에서 찾아내기가 믿기 힘들 정도로 어려운 단계를 제안할 수 있습니다. 로봇의 습성을 학습한 SAD 계획가는 인간이 생각지 못한, 더 짧거나 더 단순한 경로를 찾아냈고, 로봇은 그 경로를 쉽게 따라갈 수 있었습니다.

실제로 SAD 계획가는 인간의 솔루션과 완전히 다른 솔루션을 찾아냈습니다. 어떤 경우에는 SAD의 솔루션이 더 짧고 다른 도구들을 사용했습니다. 인간의 계획은 논리적인 관점에서는 "틀리지" 않았지만, 그들이 사용하는 특정 로봇에게는 "틀린" 계획이었습니다.

이것이 미래에 의미하는 바

이 논문은 우리가 AI를 가르치는 방식에 대한 큰 변화를 시사합니다. 우리는 단순히 AI에게 "인간을 복사하라"고 말해서는 안 됩니다. 우리는 AI가 자신이 사용하는 도구를 이해하도록 가르쳐야 합니다. 만약 도구가 서투른 로봇이라면, 설령 그것이 인간의 화려하고 복잡한 지시를 무시하는 것을 의미하더라도, 지시는 단순하고 직접적이어야 합니다.

연구자들은 로봇의 실제 수행 능력으로부터 계획가가 배우게 함으로써, 이전에 불가능했던 문제들을 해결할 수 있다는 것을 발견했습니다. 그들은 단순히 로봇을 조금 더 낫게 만든 것이 아니라, "완벽한" 인간의 계획이 손댈 수 없었던 완전히 새로운 영역의 과업들을 열어젖혔습니다.

결국, 이 논문은 팀워크에 대한 귀중한 교훈을 줍니다. 최고의 계획은 항상 전문가의 아이디어와 가장 닮은 것이 아닙니다. 최고의 계획은 팀이 실제로 실행할 수 있는 계획입니다. 때로는 문제를 정복하기 위해서, 상대방이 무엇을 해야 한다고 생각하는지가 아니라, 그들이 실제로 어떻게 싸우는지 정확히 알아야 합니다.

기술 요약: 프로그래밍 바이 예제(Programming-by-Example)를 위한 솔버 인식 분해(Solver-Aware Decompositions)

문제 정의

프로그래밍 바이 예제(PBE)는 일련의 입출력(I/O) 예시에 부합하는 도메인 특화 언어(DSL) 프로그램을 합성하는 것을 목표로 한다. 복잡한 과업으로 확장하기 위해, 최근의 접근 방식들은 **분해기-합성기 파이프라인(decomposer-synthesizer pipeline)**을 채택한다. 즉, 학습된 분해기가 중간 하위 목표(subgoals, subtasks)를 예측하면, 학습된 합성기가 이 하위 목표들을 조건으로 하여 프로그램을 생성하는 방식이다.

현재의 최첨단 방법론들(예: Exedec, TIIPS)은 인간 주석가가 제공한 정답(Ground Truth, GT) 하위 목표를 모방하도록 지도 학습을 통해 분해기를 훈련시킨다. 이 방식은 구조적 유사성이 솔버의 유용성을 나타내는 신뢰할 수 있는 대리 지표라는 암묵적인 가정을 전제로 작동한다.

저자들은 이 가정에 의문을 제기하며, 유한한 솔버(고정된 귀납적 편향과 탐색 한계를 가진 학습된 합성기)의 경우, GT 분해가 주석가의 분해 선택을 반영할 뿐 솔버의 탐색 역학을 반영하지는 않는다고 주장한다. 어떤 하위 목표는 논리적으로 타당하고 GT와 구조적으로 유사하더라도, 합성기의 다루기 쉬운 분포(tractable distribution) 밖에 존재하여 합성 실패를 초กว่า할 수 있다. 본 논문은 표준적인 지도 학습이 *주석가에 대한 충실도(annotator fidelity)*를 최적화할 뿐, *솔버의 다루기 쉬움(solver tractability)*을 최적화하지 못한다는 근본적인 불일치를 식별한다.

방법론: 솔버 인식 분해 (Solver-Aware Decomposition, SAD)

저자들은 분해기가 GT를 엄격하게 모방하는 대신, 특정 고정된 합성기에 대해 다루기 쉬운 하위 목표를 제안하도록 최적화하는 훈련 프레임워크인 **솔버 인식 분해(SAD)**를 제안한다.

핵심 구성 요소:

고정된 합성기 (Frozen Synthesizer): 합성기는 표준적인 교사 강요(teacher forcing)를 사용하여 GT 하위 프로그램으로 독립적으로 훈련된 후 고정된다. 합성기의 파라미터는 분해기 훈련 중에 고정되어 있다. 이러한 격리는 성능 향상이 오직 분해기가 합성기의 다루기 쉬운 분포를 학습하는 데서 기인함을 보장한다.
하이브리드 훈련 목적 함수: SAD는 정책이 퇴보적인 출력으로 붕괴하는 것을 방지하기 위한 구조적 스캐폴드로 GT 하위 목표에 대한 지도 학습( $L_{sup}$ )을 유지한다. 그러나 이를 **자기 비판적 시퀀스 훈련(Self-Critical Sequence Training, SCST)**에서 유도된 강화 학습(RL) 목적 함수( $L_{RL}$ )로 보강한다.
보상 신호 (Reward Signal): 보상은 예측된 하위 목표에 의해 유도된 과업을 해결하려고 할 때 발생하는 GT 프로그램에 대한 합성기의 교차 엔트로피(CE) 손실로 정의된다.
- $R(O_{pred}) = -L_{syn}(Synth(O_{pred}))$
- 낮은 합성 손실(높은 보상)은 해당 하위 목표가 타겟 프로그램에 대한 높은 확률 영역 내에 솔버를 위치시켰음을 의미한다.
최적화: 분해기 정책 $\pi_\theta$ 는 이득(advantage) $A = R(O_{sampled}) - R(O_{greedy})$ 를 최대화하도록 업데이트된다. 여기서 $O_{sampled}$ 는 샘플링된 분해이고 $O_{greedy}$ 는 탐욕적(greedy) 예측이다. 이는 분해기가 GT와 다르더라도, 고정된 합성기가 더 효과적으로 해결할 수 있는 하위 목표를 선택하도록 장려한다.

추론 (Inference):
테스트 시에는 전체 분해-합성 궤적에 대해 빔 서치(beam search)를 수행한다. 후보들은 분해기와 합성기의 로그 확률 합계에 의해 점수가 매겨지며, 유효하지 않거나 중복된 경로에 대해서는 가지치기(pruning)가 적용된다.

주요 기여

솔버 인식 분해 (SAD): 직접적인 피드백(합성기 손실)을 사용하여, GT 모방에만 의존하는 대신 학습된 유한한 합성기의 다루기 쉬운 분포에 맞춰 분해 구조를 직접 최적화하는 새로운 훈련 프레임워크이다.
정확도의 역설 (The Accuracy Paradox): 저자들은 GT 분해와의 일치도가 높을수록(높은 분해 정확도) 합성 성공률이 높아지는 것이 아니라는 직관에 반하는 경험적 현상을 입증한다. 실제로, 솔버를 고려하지 않은 베이스라인은 SAD보다 훨씬 높은 분해 정확도를 보이지만, 최종적인 엔드 투 엔드(end-to-end) 과업 정확도는 더 낮다.
솔버 상대적 품질 (Solver-Relative Quality): GT 분해는 보편적으로 최적이 아니라는 증거가 제시된다. SAD는 동일한 합성기에 완벽한 GT 하위 목표를 공급하는 GT 오라클(oracle)조차 해결하지 못하는 일련의 과업들을 해결한다. 이는 GT 하위 목표가 솔버의 귀납적 편향과 어긋나는 탐색 궤적을 강요할 수 있음을 증명한다.
Robustfill을 통한 반증 가능성: 본 논문은 분해 순서가 구조적으로 고정되어 있고 모호함이 최소화된 Robustfill 도메인을 사용하여 "반증 검사"를 포함한다. 이 설정에서 SAD의 이점은 사라지며, 이는 SAD의 성공이 유의미한 분해 모호성과 솔버 선호도가 존재하는 환경에 의존함을 확인시켜 준다.

결과

실험은 세 가지 PBE 도메인인 Deepcoder(정수 리스트), Lambdabeam(동적 람다 및 조건문이 포함된 리스트), Robustfill(문자열 변환)에서 수행되었다.

과업 정확도 (Task Accuracy): SAD는 인-도메인(in-distribution) 및 길이 일반화 설정 모두에서 솔버를 고려하지 않은 베이스라인과 최첨단 모델인 Exedec을 일관되게 능가한다. 성능 격차는 프로그램 길이에 따라 넓어지는데, 이는 솔버 정렬(alignment)이 다단계 파이프라인에서의 오류 누적을 방지함을 시사한다.
분해 정확도 vs 합성 정확도:
- 솔버 무관 (Solver-Blind): 높은 분해 정확도(Deepcoder 테스트에서 약 79%)를 보이지만 낮은 합성 정확도(약 73%)를 기록한다.
- SAD: 낮은 분해 정확도(Deepcoder 테스트에서 약 31%)를 보이지만 훨씬 높은 합성 정확도(약 87%)를 기록한다.
- 이러한 역전 현상은 구조적 충실도가 솔버의 유용성을 나타내는 좋은 대리 지표가 아님을 확인시켜 준다.
오라클 분석 (Oracle Analysis):
- GT 오라클(진정한 GT 하위 목표를 사용하는 경우)은 일반적으로 SAD보다 우수한 성능을 보여 성능 상한선을 설정한다.
- 그러나 SAD는 GT 오라클이 해결하지 못하는 별개의 과업 집합(예: Deepcoder에서 63개, Lambdabeam에서 109개)을 해결한다. 이러한 SAD 솔루션은 진정한 대안적 프로그램(종종 더 짧거나 다른 DSL 프리미티브를 사용함)이며, 이는 GT 경로가 다루기 힘든 탐색 궤적으로 이끄는 반면, SAD는 합성기가 다루기 쉬운 위치로 안내했음을 의미한다.
Robustfill 무효 결과: Robustfill에서는 SAD와 솔버 무관 베이스라인이 동일한 성능(~94%)을 달성하였으며, 이는 SAD의 이점이 분해 모호성이 있는 도메인에 특화되어 있음을 확인해 준다.

의의 및 주장

본 논문은 분해 품질이 고유한 것이 아니라 **솔버 상대적(solver-relative)**이라고 주장한다. GT와 구조적으로 일치하는 하위 목표가 유한한 합성기에게는 탐색 불가능할 수 있는 반면, GT에서 벗어난 하위 목표가 합성기를 정확히 필요한 곳에 위치시킬 수 있다.

저자들은 이러한 불일치가 실행되는 구성 요소(솔버)와 독립적으로 중간 표현을 학습하는 모든 시스템에서 발생하는 구조적 문제라고 주장한다. SAD는 분해기와 합성기 사이의 피드백 루프를 직접 닫음으로써, 실행기가 GT 감독만으로는 볼 수 없는 귀납적 편향을 발달시킬 때 발생하는 "정렬 문제(alignment problem)"를 해결한다.

GT 감독만을 통해 실행기의 귀납적 편향을 파악할 수 없는 상황에서, 솔버의 다루기 쉬운 분포를 최적화하는 것이 합성 성공과 엔드 투 엔드 과업 정확도에서 일관된 이득을 가져온다는 것을 입증하였다. 이는 향후 PBE 시스템이 분해를 하위 솔버의 구체적인 능력에 의존하는 결정 문제로 취급해야 함을 시사한다.