💻 computer science

Relation Reasoning with LLMs in Expensive Optimization

본 논문은 고비용 최적화 문제에 대해 효율적인 제로샷 관계 기반 추론을 수행하기 위해 강화 학습된 대규모 언어 모델을 활용하는 새로운 대리 모델 지원 진화 알고리즘인 R2SAEA를 소개하며, 이를 통해 전통적인 대리 모델의 재학습 오버헤드를 극복하고 최첨단 성능을 달성합니다.

원저자: Ye Lu, Bingdong Li, Aimin Zhou, Hao Hao

게시일 2026-05-06

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Ye Lu, Bingdong Li, Aimin Zhou, Hao Hao

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

거대한 안개 낀 산맥을 통과하는 최선의 경로를 찾으려 한다고 상상해 보세요. 문제는 어떤 단일 지점의 고도를 확인하는 데 하루 종일 하이킹이 필요하다는 점입니다 (이 논문에서는 이를 **"비싼 평가"**라고 부릅니다). 당신은 제한된 일수 (엄격한 예산) 만 가지고 있으므로, 모든 곳을 하이킹할 수는 없습니다.

전통적으로 과학자들은 저지점이 어디인지 추측하기 위해 "지도" (수학적 모델) 를 사용해 왔습니다. 하지만 이러한 지도는 까다롭습니다. 새로운 지역을 탐험할수록 오래된 지도는 쓸모없게 되고, 처음부터 다시 그리는 데 귀중한 시간을 써야 합니다. 이것이 이 논문이 해결하려는 병목 현상입니다.

다음은 논문의 해결책을 간단한 개념으로 분해한 것입니다:

1. 새로운 "지도": 계산기가 아닌 스마트한 심판

정확한 지점의 높이를 예측하려는 시도 (이는 어렵고 지속적인 재작성이 필요함) 대신, 저자들은 AI 를 권투 경기의 심판처럼 훈련시켰습니다.

옛 방식: AI 는 모든 선수의 정확한 점수를 추측하려 합니다.
새 방식 (R2SAEA): AI 는 두 명의 선수만 한 번에 보고 *"선수 A 가 선수 B 보다 나은가?"*라는 간단한 질문에 답합니다.

이를 **관계 추론 (Relation Reasoning)**이라고 합니다. 진화 알고리즘 (탐색 방법) 은 대개 정확한 숫자보다는 어떤 옵션이 다른 것보다 더 나은지에 더 관심을 가지므로, 이 "심판" 접근 방식이 훨씬 효율적입니다.

2. "앵커" 트릭: 도서관 과부하 피하기

100 명의 하이커가 있고 각자 서로를 비교하고 싶다면, 심판에게 약 10,000 쌍에 대해 물어봐야 합니다. 이는 AI 가 한 번에 처리하기에 너무 많은 질문입니다 (AI 의 "메모리"나 문맥이 부족해질 수 있습니다).

저자들은 "앵커" 전략을 고안했습니다:

한 번에 모두에 대해 묻는 대신, 한 명의 하이커를 "앵커" (기준점) 로 선택합니다.
AI 에게 질문합니다: "하이커 A 는 앵커와 비교해 어떤가? 하이커 B 는 앵커와 비교해 어떤가? 하이커 C 는 앵커와 비교해 어떤가?"
이를 모든 하이커에게 하나씩 반복합니다.
결과: 이는 거대하고 혼란스러운 질문 더미를 작고 관리 가능한 일련의 목록으로 바꿉니다. 마치 모든 학생을 서로 동시에 비교하는 대신, 교사가 "학급 평균"과 비교하여 한 명씩 학생들을 채점하는 것과 같습니다.

3. "투표" 시스템: 의견을 점수로 변환하기

AI 가 모든 쌍을 심판한 후, "더 낫다/더 나쁘다"는 의견들을 얻게 됩니다. 최고의 하이커를 어떻게 선택할까요?

시스템은 투표 메커니즘을 사용합니다.
AI 가 "하이커 X 는 앵커의 90% 보다 낫다"고 말하면, 하이커 X 는 높은 점수를 받습니다.
하이커 X 가 대부분보다 나쁘다면 낮은 점수를 받습니다.
이는 AI 의 "의견"을 명확한 순위로 변환하여, 탐색 알고리즘이 비싸고 현실적인 검사를 위해 어떤 하이커를 보내야 할지 정확히 알 수 있게 합니다.

4. 심판 훈련: 강화 학습 (코치)

저자들은 범용 AI 를 단순히 사용한 것이 아니라, 마스터 심판이 될 수 있도록 특정 AI (Qwen2.5 라는 모델 기반) 를 훈련시켰습니다.

AI 가 추측하는 모습을 지켜보는 "코치" (강화 학습) 를 만들었습니다.
AI 가 관계를 올바르게 추측하면 코치는 보상을 주고, 잘못 추측하면 패널티를 줍니다.
시간이 지남에 따라 AI 는 범용 AI 보다 훨씬 더 정교하게 솔루션 간의 미묘한 차이를 포착하는 법을 배웠습니다.
마법: 일단 훈련되면, 이 AI 는 매일 다시 훈련될 필요가 없습니다. 그 자리에서 "생각" (추론) 할 수 있을 뿐입니다. 이는 엄청난 시간과 비용을 절약해 줍니다.

5. "포켓 사이즈" 심판: 소형 장치에서 실행

일반적으로 강력한 AI 는 거대하고 비싼 슈퍼컴퓨터가 필요합니다. 하지만 저자들은 모델을 축소하고 "뇌"를 압축하는 과정 (양자화라고 함) 을 통해 이 스마트한 심판이 고급 노트북이나 드론 또는 로봇에 사용되는 특수 칩 (에지 장치) 과 같은 작고 휴대 가능한 장치에서 실행될 수 있음을 보여주었습니다.

결론

이 논문은 문제를 일련의 간단한 "A 대 B" 비교로 전환하고, 질문을 관리 가능하게 유지하기 위한 교묘한 "앵커" 방법을 사용하며, 전문화된 AI 심판을 훈련시킴으로써, 이전 방법들보다 훨씬 적은 수의 비싼 테스트로 어려운 문제들의 최선의 솔루션을 찾을 수 있다고 주장합니다.

더 빠릅니다: 지도를 매번 다시 그릴 필요가 없습니다.
더 저렴합니다: AI 는 작고 덜 비싼 하드웨어에서 실행될 수 있습니다.
더 잘 작동합니다: 테스트에서 이 방법은 단일 목표 및 다중 목표 문제 모두에서 다른 최상위 방법들보다 더 나은 솔루션을 찾았습니다.

저자들은 다른 사람들이 사용할 수 있도록 이 "스마트 심판"과 코드를 공개했습니다. 이는 올바른 질문을 던진다면 비싼 최적화 문제를 해결하기 위해 슈퍼컴퓨터가 필요하지 않음을 증명합니다.

기술 요약: R2SAEA – 고비용 최적화에서의 LLM 기반 관계 추론

문제 정의
고비용 최적화 문제 (EOP) 는 평가 비용이 높고 (예: 물리적 실험, 고정밀 시뮬레이션) 기울기 정보를 얻을 수 없는 블랙박스 목적 함수를 특징으로 합니다. EOP 를 해결하는 데 있어 주요 병목 현상은 제한된 평가 예산입니다. 대안 모델 보조 진화 알고리즘 (SAEA) 은 학습된 모델을 사용하여 후보를 선별함으로써 이를 완화하지만, 기존의 대안 모델 (회귀, 분류, 또는 관계 모델) 은 일반적으로 집단이 진화함에 따라 빈번한 재학습을 요구합니다. 이러한 '학습 - 예측' 루프는 상당한 계산 오버헤드를 초래하여, 대안 모델 보조로 인한 효율성 향상을 상쇄할 수 있습니다. 또한, 대규모 언어 모델 (LLM) 이 최적화 분야에서 가능성을 보이지만, 고비용 추론 비용과 지연 시간으로 인해 진화 루프에 최첨단 모델을 직접 배포하는 것은 종종 비현실적이며, 소형 모델은 신뢰할 수 있는 관계 추론에 필요한 구체적인 추론 능력을 부족합니다.

방법론: R2SAEA
본 논문은 전통적인 재학습 루프를 미세 조정된 LLM 이 구동하는 추론 전용 관계 기반 대안 모델로 대체하는 R2SAEA(강화 학습 기반 관계 중심 LLM 대안 보조 진화 알고리즘) 를 제안합니다. 방법론은 세 가지 핵심 구성 요소로 이루어집니다:

맥락 학습으로서의 관계 추론:
매개변수 모델을 학습하는 대신, 본 논문은 관계 대안 모델링을 맥락 내 쌍별 추론 작업으로 재정의합니다. LLM 은 레이블이 지정된 예제 (맥락) 를 기반으로 솔루션 쌍 간의 상대적 우위를 예측하도록 프롬프트됩니다. 두 가지 주요 기준이 지원됩니다:
- 함수 기준 (C1): 목적 함수 값의 우위에 기반한 이진 레이블링 ( $+1/-1$ ).
- 범주 기준 (C2): 클래스 간 (좋음 vs 나쁨) 및 클래스 내 관계를 구분하는 삼진 레이블링 ( $+1/0/-1$ ).
앵커 기반 반복적 맥락 구성:
쌍별 비교의 이차 복잡도 ( $O((n+q)^2)$ ) 가 맥락 제한을 초과하는 문제를 해결하기 위해, 저자들은 앵커 기반 반복 전략을 도입합니다.
- 작업은 $n$ 개의 추론 라운드로 분해되며, 맥락 집합 내의 각 기존 솔루션이 고정된 '앵커'로 작용합니다.
- 각 앵커에 대해 LLM 은 앵커와 다른 맥락 솔루션 간의 레이블이 지정된 관계와 앵커와 후보 솔루션 간의 레이블이 지정되지 않은 관계를 포함하는 프롬프트를 수신합니다.
- 이는 매 라운드별 프롬프트 복잡도를 선형 ( $O(n+q)$ ) 으로 줄여 안정성과 확장성을 보장합니다.
투표 기반 집계:
LLM 은 쌍별 관계의 행렬을 출력합니다. 이를 후보 선정을 위한 절대적 품질 점수로 집계하기 위해 투표 메커니즘이 사용됩니다:
- C1 의 경우, 점수는 예측된 관계의 음수 합 (후보가 몇 개의 앵커를 이겼는지 세는 것) 입니다.
- C2 의 경우, '좋음' 및 '나쁨' 앵커 그룹에 의해 후보가 얼마나 자주 '더 좋음' 또는 '더 나쁨'으로 판단되는지에 기반하여 정규화된 점수가 계산됩니다.
강화 학습 미세 조정 (GRPO):
세대별 재학습 없이 효율적인 제로샷 배포를 가능하게 하기 위해, 저자들은 **그룹 상대 정책 최적화 (GRPO)**를 사용하여 소형 LLM(Qwen2.5-7B) 을 미세 조정합니다.
- 데이터: 벤치마크 함수 (LZG, CEC) 에 대한 진화 실행에서 생성된 학습 궤적을 사용하여, 실제 쌍별 관계가 정답인 지시 쌍을 생성합니다.
- 보상: 규칙 기반 보상 함수는 JSON 출력 형식 준수, 관계 정확도, 그리고 출력 다양성 (퇴화 예측에 대한 패널티) 을 평가합니다.
- 장점: GRPO 는 별도의 비평가를 모델이 필요 없게 하며, 그룹별 보상 정규화를 사용하여 이산적 관계 레이블에 대한 안정적인 학습 신호를 제공합니다.

주요 기여

정식화: 본 논문은 C1 및 C2 기준 하에서 관계 기반 대안 모델링을 맥락 내 LLM 추론 문제로 공식화하고, 맥락 복잡도를 이차에서 선형으로 줄이기 위한 앵커 기반 반복 프롬프트 구성 메커니즘을 도입합니다.
집계 전략: 예측된 쌍별 관계를 후보 순위 매기기를 위한 절대 점수로 변환하기 위한 투표 기반 집계 전략을 설계하여, 표준 SAEA 선택 연산자가 LLM 출력을 활용할 수 있도록 합니다.
RL 파이프라인: 진화 궤적과 GRPO 를 활용한 엔드투엔드 RL 미세 조정 파이프라인을 구축합니다. 결과적으로 생성된 모델 (ReLLM-C1/C2) 은 강력한 범용 LLM 에 비해 우수한 관계 예측 정확도를 보여주며, 재학습 없이 제로샷 배포를 가능하게 합니다.
성능: 이 프레임워크는 단일 목적 (SOP) 및 다목적 (MOP) 고비용 최적화 벤치마크에서 최첨단 (SOTA) 성능을 달성하여, 기존 SAEA(회귀, 분류, 관계 기반) 및 일반 LLM 베이스라인을 능가합니다.

실험 결과

최적화 성능: 단일 목적 벤치마크 (LZG, YLL suites) 에서 R2SAEA-SOP 는 7 개 알고리즘 중 평균 순위 2.69 를 기록하여 최상의 성과를 보였으며, 관계 기반 DRSO 를 45 개 중 22 개, 베이지안 최적화를 45 개 중 23 개에서 능가했습니다. 다목적 테스트 (DTLZ, WFG, MaF) 에서 R2SAEA-MOP 는 평균 순위 2.84 로 1 위를 차지하여 분류 기반 (CPS-MOEA, CSEA) 및 회귀 기반 (K-RVEA) 대안 모델을 크게 능가했습니다.
관계 예측: 오프라인 평가 결과, RL 로 미세 조정된 ReLLM 모델은 미세 조정 전 기본 모델 및 최첨단 범용 LLM(GPT-4o, Gemini-2.5-Pro, Qwen3-235B 포함) 보다 쌍별 관계 정확도와 순위 일관성 (Spearman's $\rho$ ) 에서 현저히 우수한 성능을 보였습니다. 특히 일반 LLM 은 작업별 학습 없이는 의미 있는 순위를 산출하지 못해 거의 0 에 가까운 또는 음의 상관관계를 보였습니다.
확장성 및 견고성: 모델은 결정 공간 차원 ( $D \in \{5, 10, 30\}$ ) 및 맥락 크기의 변화에 대해 견고함을 입증했습니다. 관계 추론을 위해 전역 정규화보다 로컬 (프롬프트 수준) 정규화가 더 우월한 것으로 나타났습니다.
배포: 3B 파라미터 모델의 양자화 변형 (4 비트 및 8 비트) 은 높은 정확도를 유지하면서 엣지 장치 (예: Jetson Orin NX) 에서 효율적인 추론을 가능하게 하여, 실용적인 하드웨어 수준의 대안 모델 패러다임을 지원합니다.

의의 및 주장
본 논문은 R2SAEA 가 LLM 의 높은 추론 잠재력과 고비용 최적화의 엄격한 효율성 요구 사항 사이의 간극을 해소한다고 주장합니다. '학습 - 예측' 패러다임에서 '추론 전용' 패러다임으로 전환함으로써, 이 방법은 빈번한 대안 모델 재학습의 오버헤드를 제거합니다. 저자들은 그들의 접근 방식이 추가 적응 없이 단일 전문 모델을 진화 루프에 내장할 수 있는 제로샷 대안 모델 패러다임을 제공한다고 강조합니다. 이 연구는 대안 보조 진화 최적화를 위해 LLM 을 명시적으로 미세 조정한 최초의 작업으로, 리소스 제약 환경에서 하드웨어 친화적인 실시간 최적화를 향한 실현 가능한 경로를 제시합니다.