잠재 프로그램 격자를 이용한 합성 프로그램 귀납

읽기 판단

skim · confidence: high — 아이디어의 밀도는 높지만 실험 결과가 단 하나도 없다. 저자들이 Discussion에서 “the method has not yet been empirically validated”라고 명시한다(Sec 4). “이 접근이 통하는가”를 알고 싶다면 지금 읽을 이유가 없다. 반대로 compositional reasoning / ARC 계열 program induction의 표현 설계 아이디어가 필요하다면 Section 2(2쪽)와 Appendix A만으로 핵심을 전부 가져갈 수 있다.

1분 요약

Compositional reasoning은 (i) 합성 구조 학습, (ii) 예제로부터 프로그램 추론, (iii) primitive 추상화 발견의 세 능력을 요구하는데, 기존 방법은 명시적 분해 메커니즘이 없거나 손으로 만든 primitive에 의존한다(Abstract). 저자들은 Program Lattice Auto Encoder(PLAE) 를 제안한다. 핵심은 encoder를 “합성 구조를 보존하는 functor를 흉내 내도록” 학습시켜, 프로그램의 효과를 잠재공간에서 program basis의 정수 선형결합 = 이산 격자(lattice) 위의 점으로 표현하는 것이다. 그러면 program induction은 관측된 평균 program effect에 가장 가까운 격자점을 찾는 Closest Vector Problem(CVP) 으로 환원되고, 같은 격자에서 System-1(한 번에 CVP 풀고 적용)과 System-2(정수 좌표로 분해해 단계별 lattice walk + 중간 검증)가 자연스럽게 갈라진다. 여기에 lattice reduction(LLL) 을 붙이면 재학습 없이 더 짧고 직교적인 basis, 즉 더 근본적인 primitive를 발견할 수 있다. source-coverage: fulltext (7쪽 extended abstract 전문).

핵심 아이디어

“프로그램 합성 = 벡터 덧셈”으로 만들되, 연속 공간이 아니라 이산 격자로 제한한다는 것이 전부다. 이 하나의 설계에서 세 가지가 파생된다.

1. 강한 귀납 편향: 격자점만이 “primitive들의 유효한 이산 합성”에 대응하므로, 잡음 섞인 평균 effect $\bar{\Delta }$를 가장 가까운 격자점으로 스냅하는 것 자체가 프로그램 추론이 된다.
2. 이중 처리(dual-process)의 통일: System-1과 System-2가 서로 다른 모듈이 아니라 같은 격자 구조를 읽는 두 방식이다. System-2가 lattice reduction으로 basis를 개선하면 이후의 System-1이 함께 빨라진다.
3. 추상화 = 기저 변환: 라이브러리 학습을 휴리스틱 리팩토링이 아니라 “같은 격자를 span하는 더 짧고 직교적인 정수 기저 $B^{\prime }$ 찾기”라는 정의된 수학 문제로 치환한다.

교환법칙 문제(벡터 덧셈은 가환, 프로그램 합성은 비가환)는 각 basis $p_k$의 위치 $t$마다 격자 packing radius 이내의 작은 섭동 ${\epsilon }_{k,t}$ 를 더해 처리한다 — CVP 해는 바뀌지 않으면서 연산 순서를 격자점으로부터의 편차 $\delta$에 인코딩하는 방식이다.

무엇을 했나

• 문제 설정 (Sec 2): 태스크 $T_i$는 동일 프로그램 $f_i$를 따르는 입출력 쌍 $m$개이고 $f_i$는 $d$개 primitive의 합성. 새 입력 $x_{m+1}$의 출력을 예측한다(ARC류 few-shot 세팅).
• 구조 학습: encoder $E$로 입출력을 임베딩하고 차이의 평균 ${\bar{\Delta }}_i=\frac{1}{m}{\sum }_k\{E(y_k)-E(x_k)\}$ 을 latent program effect로 둔다(쌍 순열 불변 집계). 앞선 $d$개 태스크의 effect를 초기 basis 행렬 $B$로 삼아 격자 $L=\{Bz:z\in {\mathbb{Z}}^d\}$ 를 정의하고, $p_j\circ p_i\Rightarrow p_i+p_j\approx p$ 라는 가법 구조 편차를 최소화하도록 학습한다.
• 손실 설계 (Appendix B): 같은 프로그램의 effect들을 평균 방향으로 모으는 consistency loss $L_{consist}={\sum }_i({\Delta }_i-\bar{\Delta }{)}^2$ 와, effect를 정확한 격자점 $Bz$로 끌어당기는 composition loss $L_{comp}={\sum }_i\{(E(y_i)-E(x_i))-Bz{\}}^2$ 두 개.
• 추론 2모드 (Sec 2, Appendix A): System-1은 $p=\arg {\min }_{v\in L}\Vert v-\bar{\Delta }\Vert$ 를 풀고 ${\hat{y}}_{m+1}=D(E(x_{m+1})+p)$ 로 한 번에 디코딩. System-2는 $p=Bz$ 의 정수 좌표 $z$로 어떤 primitive를 몇 번 쓰는지, 편차 $\delta =\bar{\Delta }-p$ 를 디코딩해 순서를 복원한 뒤, 매 스텝 디코딩→재인코딩으로 중간 상태를 검증하며 격자 위를 걷는다.
• 추상화 발견: LLL 등 lattice reduction으로 $L=\{Bz\}=\{B^{\prime }z\}$ 를 만족하는 더 짧고 직교적인 $B^{\prime }$ 를 찾아 CVP solver 효율을 높인다.
• 실험 설계만 제시 (Sec 3): (1) 가환 도메인에서 격자 구조가 보존되는지, (2) 비가환 도메인에서 섭동 인코딩이 순서를 복원하는지, (3) System-1 vs System-2의 효율–충실도 trade-off. 셋 다 계획 서술이며 결과·수치·데이터셋은 논문에 없다.

핵심 근거

claim	위치	관측	조건·유의사항	claim_origin
program induction을 CVP로 환원할 수 있다	Sec 2, Alg 1	$p=\arg {\min }_{v\in L}\Vert v-\bar{\Delta }\Vert$ 로 정식화	수학적 정식화일 뿐 정확도·성공률 등 실증 근거 없음	author-stated
격자 표현이 System-1/System-2를 하나의 구조에서 파생시킨다	Sec 2, Alg 1–2	동일 basis $B$에서 one-step CVP와 단계별 lattice walk가 모두 도출	두 모드의 실제 성능 차이는 미측정	author-stated
lattice reduction이 추상화 발견 알고리즘 역할을 한다	Sec 2 (Library Building)	$B^{\prime }$ 는 같은 격자를 span하며 더 짧고 직교적 → CVP 효율 개선	저자 스스로 “계산 효율은 보장되나 의미적으로 유의미하다는 보장은 없다”고 명시(Sec 4)	author-stated
섭동으로 비가환 합성 순서를 인코딩할 수 있다	Sec 2	packing radius로 bound된 ${\epsilon }_{k,t}$ 가 CVP 해를 보존하며 순서를 담음	bounded sequence length에서만 성립(Sec 4)	author-stated
방법 전체가 아직 실증 검증되지 않았다	Sec 4 (Discussion)	“the method has not yet been empirically validated”	논문에 Results 섹션 자체가 부재	author-stated

어디까지 믿을까

• 실험 0건: 정확도·베이스라인·데이터셋·ablation이 하나도 없다. Section 3은 “Experiment Design”이지 결과가 아니다. 현 시점에서 이 논문의 주장은 전부 설계 수준의 가설이다.
• 가환성 가정의 한계: 격자 표현은 본질적으로 abelian인데 실제 프로그램 도메인 다수는 비가환이다. 섭동 인코딩은 길이가 bound된 시퀀스에서만 순서를 복원한다(Sec 4).
• 입력 비의존 translation 가정: latent program effect를 “입력과 무관한 평행이동”으로 모델링하는데, 저자도 이것이 항상 성립하지는 않는다고 인정한다. 조건부 변환이 필요한 프로그램에는 구조적으로 맞지 않는다.
• CVP의 난이도: CVP는 최악의 경우 hard 문제라 실용성이 근사 solver 품질과 basis 품질에 좌우된다(Sec 4). 격자 차원 $d$(= primitive 수)가 커질 때의 확장성은 미논의.
• 명칭 불일치: PDF 본문은 PLAE(Program Lattice Auto Encoder) 를 쓰지만, NeurIPS 가상 발표 페이지 요약에는 PLT(Program Lattice Transformer) 로 표기되어 있다. 인용 시 PDF 표기(PLAE)를 따르는 편이 안전하다.

원문 읽기 지도

목적	읽을 위치
격자 정식화 자체만 가져가고 싶다	Section 2의 “Learning the Compositional Structure” ~ “Program Induction on the Learned Structure” (약 2쪽)
구현하려면	Appendix A (Algorithm 1: System-1, Algorithm 2: System-2 lattice walk) + Appendix B (consistency / composition loss)
한계를 냉정하게 보고 싶다	Section 4 Discussion 후반 5개 문장 (가환성·섭동 bound·의미성·입력 비의존·CVP 난이도)
배경 개념	Micciancio & Goldwasser (2002) CVP, Nguyen & Vallée (2010) LLL

읽기 전 용어

용어	정의
Lattice (격자)	기저 벡터들의 정수 선형결합으로 만들어지는 이산 점 집합 $L=\{Bz:z\in {\mathbb{Z}}^d\}$. 여기서는 “primitive들의 유효한 이산 합성” 전체를 뜻한다.
Closest Vector Problem (CVP)	임의의 타깃 벡터 $t$에 대해 $\Vert v-t\Vert$ 를 최소화하는 격자점 $v\in L$ 을 찾는 문제. 본 논문에서 program induction이 이 문제로 환원된다.
Lattice reduction (LLL)	같은 격자를 span하되 더 짧고 직교적인 새 정수 기저 $B^{\prime }$ 를 찾는 알고리즘. 정수 조합으로 제한된 Gram-Schmidt에 비유된다. 여기서는 추상화(라이브러리 학습) 메커니즘 역할.

Wiki 연결

• ARC-AGI - Abstraction and Reasoning Corpus ⭐ — 이 논문이 인용하는 Chollet의 Kaleidoscope Hypothesis가 나온 문제 설정. PLAE가 겨냥하는 few-shot 합성 도메인.
• Program Synthesis with Large Language Models — 프로그램 귀납을 LLM 생성으로 푸는 대안 계열. PLAE의 “손으로 만든 primitive에 의존” 비판과 대조해 볼 지점.
• Looped Transformers as Programmable Computers — 신경망 잠재 상태를 프로그램 실행으로 해석하는 또 다른 노선. System-2 lattice walk의 반복 디코딩과 비교 가능.

태그

paper #2025 compositional-reasoning program-induction lattice ARC NeurIPS-workshop DS-Lab

---

BibTeX

@inproceedings{park2025composedprogram,
  title={Composed-Program Induction with Latent Program Lattice},
  author={Park, Jumyung and Park, Jiwon and Shim, Jinseo and Kim, Sejin and Vennemann, Paulina and Kim, Sundong},
  booktitle={NeurIPS 2025 Workshop on Symmetry and Geometry in Neural Representations (NeurReps), Extended Abstract Track},
  year={2025},
  organization={Gwangju Institute of Science and Technology (GIST)},
  url={https://intrig.vercel.app/research/composed-program-induction-with-latent-program-lattice}
}