[Program Synthesis #5] Search Prioritization: 어떤 프로그램부터 볼 것인가?
Program Synthesis 시리즈 5편 – Enumerative Synthesis의 한계를 극복하기 위한 Search Prioritization과 확률 기반 탐색 전략 이해하기
Search Prioritization — 탐색 순서를 바꾸는 순간 문제가 달라진다
Enumerative synthesis의 핵심 문제는 단순히 search space가 크다는 데 있지 않다.
더 본질적인 문제는 다음이다.
탐색 순서가 완전히 무작위에 가깝다는 점
Enumerative 방식은 보통 프로그램을 크기 기준으로 나열한다.
\[e_1, e_2, e_3, \dots\]여기서 순서는 대략 다음과 같은 기준을 따른다.
- AST 크기
- depth
- grammar expansion 순서
이 방식은 “완전성”은 보장한다.
하지만 “좋은 후보를 빨리 찾는다”는 보장은 전혀 없다.
탐색 순서가 왜 중요한가
다음 두 경우를 비교해보자.
- 정답이 100번째 프로그램에 있는 경우
- 정답이 $10^{12}$번째 프로그램에 있는 경우
알고리즘은 동일하다.
하지만 실제 실행 시간은 완전히 다르다.
이 차이는 오직 하나에서 발생한다.
정답이 어디에 위치하느냐
즉 synthesis 문제는 단순한 탐색 문제가 아니라
\[\text{“좋은 해를 얼마나 앞쪽에 배치할 수 있는가”}\]라는 문제로 바뀐다.
naive enumeration의 구조적 한계
단순 enumeration이 실패하는 이유는 단순히 “많아서”가 아니다.
더 중요한 이유는 다음이다.
1. 프로그램 분포가 균등하지 않다
모든 프로그램이 동일한 확률로 정답이 될 가능성을 가지지 않는다.
실제로는 다음과 같은 편향이 존재한다.
- 특정 연산 조합이 훨씬 자주 등장한다
- 특정 구조는 거의 등장하지 않는다
- 사람이 작성하는 코드에는 강한 패턴이 있다
하지만 naive enumeration은 이걸 완전히 무시한다.
2. “작은 프로그램 = 좋은 프로그램”은 항상 성립하지 않는다
Occam’s razor 때문에 보통 작은 프로그램부터 탐색한다.
하지만 synthesis에서는 다음 문제가 발생한다.
- 작은 프로그램은 너무 일반적이라서
- 예제를 우연히 맞추는 경우가 많다
즉,
작은 프로그램이 더 빨리 나오지만, 더 자주 틀린다
3. 탐색 비용의 대부분이 “쓸데없는 후보”에 쓰인다
실제로 탐색 공간의 대부분은 다음과 같은 프로그램들이다.
- 의미 없는 조합
- 동일한 동작의 변형
- specification과 전혀 관계없는 구조
즉,
계산 자원의 대부분이 “정답과 무관한 프로그램”에 소비된다
핵심 전환: 탐색을 “정렬 문제”로 본다
이 시점에서 관점을 바꿔야 한다.
기존 관점:
가능한 프로그램을 생성한다
이제의 관점:
프로그램 집합에 순서를 부여한다
즉 우리는 사실 다음 문제를 풀고 있다.
\[\text{Find } e \in L(G) \text{ with minimal search cost}\]이걸 바꿔 쓰면:
\[\text{Sort } L(G) \text{ by likelihood of being correct}\]여기서 등장하는 개념이 바로 확률 모델이다.
확률 기반 탐색의 도입
각 프로그램 \(e\)에 대해 다음 값을 정의한다고 하자.
\[P(e) = \text{e가 정답일 가능성}\]이 값이 정확할 필요는 없다.
중요한 것은 상대적인 순서다.
이제 탐색은 다음처럼 바뀐다.
- 기존: arbitrary order
- 변경: \(P(e)\) 기준 정렬
이 변화는 매우 크다.
이제 탐색은 단순한 enumeration이 아니라
“확률적으로 가이드된 탐색”
이 된다.
왜 이게 효과적인가
이 접근이 잘 작동하는 이유는 경험적이다.
실제 프로그램들은 다음 특성을 가진다.
- 반복적인 패턴을 가진다
- 특정 idiom을 자주 사용한다
- 문법적으로 균등하지 않다
이걸 모델링하면:
정답은 search space의 “특정 영역”에 몰려 있다
Search prioritization은 이 영역을 먼저 탐색하려는 시도다.
PCFG — Grammar에 확률을 넣는 방법
앞에서 프로그램마다 “정답일 가능성”이 다르다는 걸 봤다.
문제는 그걸 어떻게 실제 탐색에 반영하느냐이다.
가장 직접적인 방법은 프로그램 자체에 확률을 붙이는 것이다.
하지만 프로그램은 구조가 복잡해서 확률을 직접 정의하기 어렵다.
그래서 대신 사용하는 접근이 있다.
프로그램이 아니라, grammar에 확률을 붙인다
Probabilistic Context-Free Grammar
기존의 grammar는 단순히 “가능한 프로그램의 집합”만 정의했다.
1
E ::= x | E + E | E * E
이건 모든 규칙이 동일하게 취급된다.
여기에 확률을 추가하면 다음과 같이 바뀐다.
1
2
3
E ::= x (0.5)
| E + E (0.3)
| E * E (0.2)
이제 각 production rule은 선택될 확률을 가진다.
프로그램의 확률
이제 하나의 프로그램 \(e\)의 확률은
그 프로그램을 생성하는 규칙들의 확률을 곱해서 정의한다.
예를 들어:
\[e = x + x\]라면,
\[P(e) = P(E \rightarrow E + E) \cdot P(E \rightarrow x)^2\]이 방식은 매우 중요한 의미를 가진다.
- 자주 쓰이는 규칙 → 높은 확률
- 덜 자연스러운 조합 → 낮은 확률
즉, grammar 자체가 “코드의 통계적 구조”를 반영하게 된다.
탐색 방식의 변화
이제 enumeration은 단순 순회가 아니라
확률 기반 정렬된 탐색으로 바뀐다.
기존:
- size 순서
- arbitrary order
변경:
- \(P(e)\)가 높은 순서
이걸 구현하면 다음과 같은 형태가 된다.
1
2
3
4
5
6
priority queue ← 프로그램 후보들 (확률 기준)
while queue not empty:
e = pop highest probability program
if e satisfies spec:
return e
왜 효과적인가
이 접근이 잘 작동하는 이유는 간단하다.
실제 프로그램은 무작위로 생성되지 않는다.
- 특정 연산 패턴이 반복되고
- 특정 구조가 자주 등장하며
- 일부 조합은 거의 사용되지 않는다
PCFG는 이 편향을 모델링한다.
결과적으로 탐색은 다음처럼 바뀐다.
- “모든 프로그램을 보는 과정”
→ “가능성 높은 영역부터 훑는 과정”
중요한 한계
이 방식에도 한계는 있다.
- 확률 모델이 부정확하면 오히려 탐색이 느려질 수 있다
- 높은 확률이 항상 정답을 의미하지는 않는다
- 여전히 search space 자체는 크다
그래서 실제 시스템에서는
- PCFG
- pruning
- constraint solving
이 모두 결합된다.
이제 탐색은 더 이상 단순한 enumeration이 아니라
구조 + 확률 + 제약이 결합된 문제
로 바뀐다.
확률 모델은 어디서 오는가 — 코드의 통계적 구조
앞에서 PCFG를 통해 grammar에 확률을 부여하는 방법을 봤다.
이제 자연스럽게 이런 질문이 나온다.
그 확률은 어떻게 정하는가?
수동으로 정하는 것은 어렵다
가장 단순한 방법은 사람이 직접 확률을 정하는 것이다.
예를 들어:
- 변수 사용 → 높게
- 복잡한 연산 → 낮게
하지만 이 방식에는 한계가 있다.
- 프로그램 구조는 생각보다 훨씬 복잡하다
- 어떤 패턴이 “좋은지” 사람이 일일이 정의하기 어렵다
- 도메인이 바뀌면 다시 설계해야 한다
그래서 실제로는 다음과 같은 접근을 사용한다.
데이터로부터 확률을 학습한다
코드에도 “통계적 패턴”이 있다
흥미로운 사실은 이것이다.
프로그램은 완전히 자유롭게 작성되지 않는다
실제 코드에서는 다음과 같은 패턴이 반복된다.
- 특정 연산 조합이 자주 등장한다
- 특정 문법 구조가 더 자연스럽다
- 일부 표현은 거의 사용되지 않는다
예를 들어:
1
for (i = 0; i < n; i++)
이 패턴은 매우 흔하다.
반면:
1
for (i = 0; i < n; i--)
이건 훨씬 드물다.
이 차이는 단순한 스타일 문제가 아니라
통계적 분포의 차이다.
n-gram 기반 모델
가장 기본적인 방법은 n-gram 모델이다.
아이디어는 단순하다.
앞에 나온 토큰을 기반으로 다음 토큰의 확률을 계산한다
예:
\[P(\text{next token} \mid \text{previous tokens})\]이걸 코드에 적용하면:
- 연산자 순서
- 변수 사용 패턴
- API 호출 구조
같은 것들을 확률적으로 모델링할 수 있다.
Grammar 기반 확률 모델
PCFG 자체도 데이터로부터 학습할 수 있다.
예를 들어:
- \(E \rightarrow E + E\) 는 자주 등장
- \(E \rightarrow E * E\) 는 덜 등장
이라면,
\[P(E \rightarrow E + E) > P(E \rightarrow E * E)\]이렇게 rule 확률을 실제 코드 빈도로부터 추정한다.
Neural 모델
최근에는 더 강력한 방법이 사용된다.
신경망 기반 프로그램 모델
이 모델들은:
- 코드 전체 구조를 고려하고
- 더 복잡한 패턴을 학습하며
- long-range dependency까지 반영한다
대표적으로:
- LSTM 기반 모델
- Transformer 기반 코드 모델
이들은 단순한 grammar 확률보다 훨씬 정교한 분포를 학습한다.
중요한 관점
이 모든 방법의 공통점은 하나다.
프로그램을 “확률 분포”로 본다
즉 synthesis는 더 이상 단순 탐색이 아니라
확률 공간에서의 탐색 문제
로 바뀐다.
이 시점에서 탐색은 다음과 같이 재해석된다.
- search space = 프로그램 집합
- probability = 우선순위
- goal = 높은 확률 영역에서 정답 찾기
정리 — 탐색은 이제 “확률 문제”다
지금까지 우리는 Enumerative Synthesis의 한계를 출발점으로,
탐색을 개선하는 여러 방법을 살펴봤다.
- 단순 enumeration은 search space 폭발로 인해 비현실적이다
- pruning은 불필요한 후보를 제거한다
- prioritization은 탐색 순서를 바꾼다
이 과정에서 가장 중요한 변화는 이것이다.
프로그램을 더 이상 “동등한 후보들의 집합”으로 보지 않는다
대신 우리는 다음과 같이 생각하게 된다.
- 어떤 프로그램은 더 자연스럽고
- 어떤 프로그램은 거의 나오지 않으며
- 정답은 특정한 구조를 가진 영역에 집중된다
이걸 반영하면 탐색은 이렇게 바뀐다.
- search space = 프로그램 집합
- probability = 각 프로그램의 “자연스러움”
- search = 높은 확률 영역을 먼저 탐색하는 과정
즉 Program Synthesis는 더 이상 단순한 generate-and-test가 아니라
확률 분포 위에서의 탐색 문제
로 재해석된다.
이 관점은 이후의 모든 기법에 영향을 준다.
- 더 좋은 search strategy
- 더 강력한 pruning
- 더 정교한 representation
지금까지는 “어떻게 탐색할 것인가”에 집중했다.
하지만 여전히 한 가지 문제가 남아 있다.
프로그램을 여전히 하나씩 다루고 있다
다음 글에서는 이 문제를 해결하기 위해,
탐색 공간 자체를 압축하는 방법
을 다룬다.