https://www.dropbox.com/scl/fi/ewqqgfashj2x90ox13owc/emnlp24-Ultra_Efficient_ICL_via_LM-DPP.pdf?rlkey=sdcs2fq2qt1xwi0lqwpnzo5ai&dl=0

이 논문은 **ICL(In-Context Learning)에서 어떤 데이터를 먼저 라벨링(annotation)해야 하는가?**를 다룬 연구입니다.

기존 ICL 연구는 보통 다음을 가정합니다.

“이미 큰 labeled support set이 존재한다.”

그러나 실제 환경에서는 수만 개의 데이터에 라벨을 다는 비용이 매우 큽니다.

따라서 저자들은 다음 문제를 제기합니다.

“라벨이 전혀 없는 데이터 풀(unlabeled pool)에서 극소수(16개~100개)만 라벨링할 수 있다면 어떤 샘플을 선택해야 ICL 성능이 가장 좋아질까?”

이를 위해 LM-DPP(Language Model-based Determinantal Point Process) 를 제안합니다. 핵심은

• Uncertainty (LLM이 얼마나 익숙한가)
• Diversity (선택된 예시들이 얼마나 다양한가)

를 동시에 고려하여 annotation할 샘플을 고르는 것입니다.  

---

전체 파이프라인

논문의 구조는 다음 2단계입니다.

기존 방식

Large Labeled Dataset
        ↓
Retriever
        ↓
ICL Prompt
        ↓
LLM

많은 labeled data가 필요.

---

제안 방식

Unlabeled Pool
      ↓
LM-DPP
      ↓
선택된 M개만 Annotation
      ↓
Small Labeled Set
      ↓
Retriever
      ↓
ICL Prompt
      ↓
LLM

즉, Annotation 이전 단계에서 좋은 예시를 먼저 골라내는 Active Learning 문제로 재정의합니다.  

---

방법론

논문의 핵심은 Section 2입니다.

---

Step 1. Uncertainty 측정

왜 uncertainty가 필요한가?

Active Learning에서는 일반적으로 불확실성이 큰 샘플을 선택합니다.

하지만 LLM에서는 문제가 있습니다.

예를 들어 classification task에서

entailment
neutral
contradiction

확률을 모두 얻기 어렵습니다.

GPT-J나 GPT 계열은 classifier가 아니기 때문입니다.

---

해결 방법: Perplexity 사용

논문은 SPELL(Gonen et al., 2022)을 사용합니다.

각 unlabeled sample x에 대해

PPL(x)를 계산합니다.

그리고 $r(x)=\frac{1}{PPL(x)}$를 사용합니다.

즉, $r(x)=\exp\left(\frac1t \sum_{i=1}^{t}\log P(x_i|x_{<i})\right)$

---

의미

PPL ↓

→ LLM이 익숙함

→ Training distribution에 가까움

→ 좋은 demonstration일 가능성 높음

따라서

High r(x) = Low PPL = Low uncertainty

가 됩니다.

---

왜 High Uncertainty를 안 쓰는가?

전통 Active Learning은 가장 헷갈리는 샘플을 선택합니다.

하지만 ICL에서는 목적이 다릅니다.

우리는 classifier를 학습시키는 것이 아니라 좋은 demonstration 만들기가 목적입니다.

실험 결과, High uncertainty example을 넣으면 성능이 크게 감소했습니다.  

---

Step 2. Diversity 측정

이제 중복된 예시를 제거해야 합니다.

예를 들어

A cat is sleeping.
A dog is sleeping.
A horse is sleeping.

만 고르면 coverage가 낮습니다.

따라서 다양성을 측정합니다.

---

Representation

Sentence-BERT embedding 사용

$\phi_i$ 로 표현합니다.

조건:

$||\phi_i||=1$

정규화.  

---

Similarity

$\phi_i^T\phi_j$

즉 cosine similarity.

---

Step 3. DPP 구성

여기가 논문의 핵심입니다.

---

기본 DPP

DPP는 서로 비슷한 샘플을 동시에 선택할 확률을 낮추는 모델입니다.

선택된 subset S의 확률:

$P(S)\propto \det(L_S)$

---

직관

두 벡터가 비슷하면

det ≈ 0 됩니다.

서로 직교할수록

det ↑ 됩니다.

따라서

determinant 최대화 = 다양한 샘플 선택

입니다.

---

LM-DPP의 핵심 아이디어

저자들은 uncertainty까지 포함시킵니다.

각 샘플에 대해

$B_i=r_i\phi_i$

정의.

그러면 $L=B^TB$ 이고

$L_{ij}=r_i r_j \phi_i^T\phi_j$

---

해석

$r_i r_j$

→ 품질(uncertainty)

$\phi_i^T\phi_j$

→ 유사도(diversity)

따라서

$L_{ij}=Quality \times Similarity$

형태가 됩니다.

---

DPP 목적함수

전개하면

$\log \det(L_S)=\sum_{i\in S}\log(r_i^2)+\log\det(\Phi_S)$

---

첫 항:

$\sum \log(r_i^2)$

→ Low PPL 샘플 선호

---

둘째 항:

$\log\det(\Phi_S)$

→ Diverse subset 선호

---

λ로 Trade-off 조절

논문은

$\log \det(L_S)’=\lambda\sum_{i\in S}r_i+(1-\lambda)\log\det(L_S)$

를 사용합니다.  

---

의미:

λ=1

Perplexity만 사용

---

λ=0

DPP만 사용

---

λ≈0.5

품질 + 다양성 균형

---

실험 결과

λ = 0.5 ~ 0.6

이 가장 좋았습니다.  

---

Step 4. MAP Inference

이제 최적 subset을 찾아야 합니다.

문제:

$\arg\max_S \det(L_S)$

는 NP-hard.

---

Fast Greedy MAP

Chen et al., NeurIPS 2018 사용.

선택 규칙:

$j=\arg\max\left[\log\det(L_{S\cup j})-\log\det(L_S)\right]$

---

매 iteration마다

현재 subset에 추가했을 때,
det 증가량이 가장 큰 샘플 선택.

---

복잡도

기존:

O(K^3)

---

Cholesky update 사용:

O(NK^2)

---

Step 5. 실제 ICL 수행

선택된 M개 샘플에 대해서만

Human Annotation

수행.

---

그 후 test query가 들어오면

Sentence-BERT 기반 retrieval 수행.

TopK

유사 예시를 찾아 prompt 구성.  

---

기존 Vote-k와의 차이

방법	Diversity	Uncertainty
KMeans	O	X
Vote-k	O	X
Fast Vote-k	O	X
LM-DPP	O	O

Vote-k는 대표성(representativeness)만 고려합니다.

LM-DPP는 대표성 + LLM 친화성(low PPL)을 동시에 고려합니다.

---

실험 결과

GPT-J, LLaMA-2, GPT-3.5 모두에서 개선.

대표적으로

GPT-J, |L|=100:

Fast Vote-k : 64.68
LM-DPP      : 65.83

평균 +1.15%p 향상.  

---

논문의 핵심 기여

이 논문의 가장 중요한 아이디어는

“좋은 ICL demonstration은 단순히 diverse하면 안 되고, LLM이 이해하기 쉬운(low perplexity) 예시여야 한다.”

를 DPP 안에 통합했다는 점입니다.

수식으로 표현하면

$\text{Good Demo}=\text{Low PPL}+\text{High Diversity}$

이고,

이를

$L_{ij}=r_i r_j \phi_i^T\phi_j$

라는 매우 깔끔한 DPP kernel로 구현한 것이 핵심입니다.  

---

DPP 기반 ICL example selection 관점에서 보면, 이 논문은 다음 계보로 정리할 수 있습니다.

Vote-k (EMNLP 2022)
      ↓
DPP-based Corpus ICL (Yang et al. 2023)
      ↓
LM-DPP (EMNLP 2024)
      ↓
Compositional Exemplars for ICL (ICML 2023에서 DPP 활용)
      ↓
RAG Context Compression (xRAG, PISCO 등)

특히 LM-DPP는 “DPP + LLM uncertainty(PPL)“를 결합한 최초의 annotation selection 연구라는 점이 가장 큰 학술적 기여입니다.