🤖 machine learning

LLM Program Optimization via Retrieval Augmented Search

이 논문은 LLM이 생성한 자연어 설명과 원자적 편집(atomic edits)을 활용하여 C++ 및 Python 프로그램을 최적화하는 데 있어 기존의 최첨단 전략들을 크게 능가하면서도 해석 가능성을 높이고 코드 변경을 최소화하는 새로운 블랙박스 적응 방법론인 Retrieval Augmented Search (RAS)와 AEGIS를 소개한다.

원저자: Sagnik Anupam, Alexander Shypula, Osbert Bastani

게시일 2026-06-25

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Sagnik Anupam, Alexander Shypula, Osbert Bastani

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

당신에게 아주 재능 있지만 경험은 부족한 요리사(대규모 언어 모델, 즉 LLM)가 요리를 하려고 한다고 상상해 보세요. 목표는 단순히 음식을 맛있게 만드는 것이 아니라, 맛은 바꾸지 않으면서 더 빨리 요리하는 것입니다.

이 논문은 이 요리사가 더 똑똑하게 일할 수 있도록 돕는 두 가지 새로운 방법(이전의 '느린 코드'와 '빠른 코드'로 구성된 '과거 레시피 라이브러리'를 사용하여 가이드하는 방식)을 제시합니다.

문제점: 요리사가 막혔습니다

보통 이 요리사에게 레시피를 빠르게 만들라고 요청하면, 요리사는 무작위로 추측하거나 한꺼번에 전체를 다시 쓰려고 할 수 있습니다. 그들은 어떻게 하면 더 빠르게 만들 수 있는지에 대한 충분한 사례를 보지 못했기 때문에 자주 실패합니다. 그들에게는 구체적인 기술을 보여줄 코치가 필요합니다.

방법 1: RAS (검색 증강 탐색, Retrieval Augmented Search)

비유: "키워드 검색"이 아닌 "스마트한 사서"

요리사가 영감을 얻기 위해 거대한 도서관에서 유사한 레시피를 찾아야 한다고 상상해 보세요.

기존 방식 (코드 검색): 요리사는 현재 요리의 재료 목록(실제 코드)을 보고 도서관에서 비슷한 재료를 가진 레시피를 찾습니다. 이것은 "밀가루와 달걀"을 검색해서 실제로는 수프 레시피가 필요한데도 불구하고 밀가루와 달걀을 사용하는 케이크 레시피를 가져오는 것과 같습니다. 너무 문자 그대로만 해석하는 방식입니다.
새로운 방식 (문맥적 검색): 요리사는 먼저 요리에 대한 요약(예: "이것은 풍미를 추출하기 위해 채소를 뭉근하게 끓이는 수프이다")을 작성하도록 사서에게 요청합니다. 그러면 사서는 특정 재료가 무엇인지와 상관없이, 동일한 기능을 수행하는 다른 요리들을 찾아냅니다.
- 작동 원리: 이는 단순히 종이 위에 적힌 모습이 닮은 것이 아니라, 동일한 문제를 해결하는 레시피를 찾아냅니다.

탐색 과정 (빔 서치, Beam Search):
레시피를 한 번에 거대한 도약으로 고치라고 요구하는 대신, RAS는 이를 단계별로 나눕니다.

요리사가 작은 개선을 수행합니다.
사서는 이 새로운 버전을 바탕으로 관련성 높은 새로운 사례를 찾습니다.
요리사는 그 새로운 사례를 사용하여 다시 시도합니다.
이 과정을 반복하며, 마치 산을 오르듯 항상 가장 빠르게 올라가는 경로를 선택합니다.

결과: 이 방법은 C++ 프로그램을 이전 최고 방식보다 최대 2배 더 빠르게 만들었으며, 파이썬 프로그램의 속도도 크게 향상시켰습니다.

방법 2: AEGIS (원자적 편집 가이드 탐색, Atomic Edit Guided Search)

비유: "철거 팀"이 아닌 "레고 마스터"

스마트한 사서가 있더라도, 요리사는 여전히 레시피에 대해 크고 혼란스러운 변화(예: 전체 조리법을 통째로 바꾸는 것)를 줄 수 있습니다. 이는 이해하기 어렵고 위험합니다.

AEGIS는 라이브러리 자체를 바꿉니다. "느린 레시피"와 "빠른 레시피" 쌍을 통째로 저장하는 대신, 이를 원자적 편집(Atomic Edits) 단위로 쪼갭니다.

과정: 시스템은 느린 레시피와 빠른 레시피를 가져와 전문가에게 아주 작은, 단일 단계의 차이점을 설명해 달라고 요청합니다.
- 1단계: "나무 숟가락 대신 금속 숟가락으로 교체 (열 전달이 더 빠름)."
- 2단계: "양파를 더 잘게 다짐 (더 빨리 익음)."
- 3단계: "뚜껑을 사용하여 증기를 가둠."
일반화: 그런 다음 이러한 단계들을 일반적인 규칙(예: "높은 열에는 금속 도구를 사용하라")으로 다시 작성하여, 특정 요리에만 국한되지 않고 어떤 레시피에도 적용할 수 있도록 합니다.

도움이 되는 방식: 요리사가 새로운 요리를 최적화해야 할 때, 시스템은 "여기 새로운 레시피 전체가 있습니다"라고 말하지 않습니다. 대신 "여기 구체적이고 작은 기술이 있습니다: '금속 숟가락으로 교체하세요.' 이것을 시도해 보세요"라고 말합니다. 요리사는 이 작은 기술 하나를 적용하고, 결과를 확인한 뒤, 다음 기술을 시도합니다.

결과:

변경 사항을 더 작고 이해하기 쉽게 만듭니다 (성 전체를 다시 짓는 대신 레고 블록 하나를 교체하는 것과 같습니다).
첫 번째 방법과 비교했을 때 변경 규모를 17%에서 30%까지 줄였습니다.
첫 번째 방법보다는 약간 덜하지만, 여로 더 빠른 속도를 구현하면서도 훨씬 더 많은 제어력과 명확성을 제공했습니다.

결과 요 সারamm (요약)

RAS는 당신에게 일련의 작고 정보가 담긴 단계들을 통해 안내하며, 더 빠른 프로그램을 위한 최선의 경로를 찾는 스마트한 코치와 같습니다. 이는 C++에서 이전 최고 방식을 2배 능가했으며, 파이썬 속도를 평균 10% 향상시켰습니다.
AEGIS는 문제를 아주 작고 관리 가능한 레고 블록으로 나누어 주는 코치와 같습니다. 이는 효율성 측면에서 1.37배 더 나은 결과를 만들며, 변경 사항을 훨씬 더 작고 안전하게 만들어, 프로그램을 더 빠르게 만들려는 과정에서 프로그램이 망가지지 않도록 보장합니다.

요컨대, 이 논문은 AI의 코드를 빠르게 만들기 위해서 단순히 "추측"하게 해서는 안 된다는 것을 가르쳐 줍니다. 대신 코드의 이야기를 이해하는 사서(문맥적 검색)와, 하나씩 작고 안전한 개선을 할 수 있는 아주 구체적인 도구 세트(원자적 편집)를 제공해야 합니다.

기술 요약: 검색 증강 탐색(Retrieval Augmented Search)을 통한 LLM 프로그램 최적화

문제 정의

대규모 언어 모델(LLM)은 코드 생성 분야에서 상당한 잠재력을 보여주었으나, 별도의 학습 없이 '프로그램 최적화'를 수행하는 데에는 어려움을 겪고 있다. 전통적인 학습 데이터셋은 프로그램 성능에 관한 데이터가 부족하여 직접적인 적응이 어렵다. 최근 연구(Shypula et al., 2024)는 "성능 개선 편집(Performance Improving Edits, PIE)" 벤치마크를 도입하고, 동적 코드 검색(코드 임베딩 유사도에 기반하여 느린 프로그램과 빠른 프로그램 쌍을 검색)이 성능을 향상시킨다는 것을 입증했으나, 기존 방식들은 여전히 "엔드 투 엔드(end-to-end)" 방식에 머물러 있다. 즉, 몇 가지 예시를 바탕으로 LLM에게 최적화된 버전을 직접 출력하도록 요구한다. 이는 일련의 점진적인 패스(pass)를 통해 체계적으로 프로그램을 수정하는 현대적 컴파일러와 대조된다. 또한, 엔드 투 엔드 방식은 종종 크고 해석하기 어려운 변화를 만들어낸다.

방법론

본 논문은 이러한 한계를 해결하기 위해 두 가지 주요 방법인 **검색 증강 탐색(Retrieval Augmented Search, RAS)**과 **원자적 편집 유도 탐색(Atomic Edit GuIded Search, AEGIS)**을 제안한다.

1. 검색 증강 탐색 (RAS)

RAS는 후보 최적화에 대해 빔 서치(beam search)를 수행하며, 동적 검색을 개선하기 위해 두 가지 핵심 통찰을 통합한 블랙박스 적응 방법이다.

문맥적 검색 (Contextual Retrieval): RAS는 원시 소스 코드를 기반으로 예시를 검색하는 대신, LLM( $F_{context}$ )을 사용하여 프로그램의 핵심 알고리즘과 데이터 구조에 대한 자연어 설명을 생성한다. 이 설명은 임베딩( $\psi$ )되어 가장 관련성이 높은 느린-빠른 훈련 쌍을 검색한다. 저자들은 이러한 추상화가 시스템이 표면적인 구문적 유사성이 아닌 의도와 로직을 바탕으로 예시를 검색할 수 있게 한다고 가설을 세웠다.
반복적 빔 서치 (Iterative Beam Search): 고정된 예시 세트를 한 번만 검색하는 것이 아니라, RAS는 '검색-최적화-평가' 루프를 수행한다. 각 단계 $i$ 에서 현재 프로그램 $p_{i-1}$ 이 주어지면, 시스템은 (문맥적 임베딩을 기반으로) $p_{i-1}$ 과 가장 유사한 상위- $k$ 개의 훈련 쌍을 검색한다. 그 후 LLM( $F_{opt}$ )은 $k$ 개의 후보 최적화안을 생성한다. 시스템은 가장 빠른 올바른 프로그램을 $p_i$ 로 선택하고 이 과정을 $m$ 단계 동안 반복한다.

2. 원자적 편집 유도 탐색 (AEGIS)

크고 단일한 변화의 해석 가능성 문제를 해결하기 위해, AEGIS는 훈련 예시를 "원자적 편집(atomic edits)"으로 분해하는 전처리 단계를 도입한다.

분해 (Decomposition): LLM( $F_{decomp}$ )은 느린-빠른 프로그램 쌍 $(p, p')$ 을 분석하여, 변환 과정을 특정 점진적 변화와 그 성능 근거를 설명하는 일련의 자연어 기술 $[s_1, ..., s_r]$ 로 분해한다.
생성 및 일반화 (Generation and Generalization): 시스템은 LLM( $F_{edit}$ )을 사용하여 각 기술 $s_i$ 를 느린 프로그램에 순차적으로 적용하여 중간 프로그램들을 생성한다. 그 다음, 일반화 LLM( $F_{gen}$ )은 각 구체적인 편집 기술을 다양한 프로그램에 적용 가능한 일반적인 "원자적 편집" $e_i$ 로 재작성한다.
원자적 편집을 통한 탐색 (Search with Atomic Edits): 결과물인 데이터셋 $\Pi_{atomic}$ 은 튜플 $(e_i, (p_{i-1}, p_i))$ 로 구성된다. 이후 RAS가 이 데이터셋에서 실행되며, 검색 단계에서는 가장 관련 있는 원자적 편집을 찾고, LLM은 해당 구체적인 점진적 편집을 현재 프로그램에 적용하도록 프롬프트가 제공된다. 이는 최적화 과정이 더 점진적이고 해석 가능하도록 강제한다.

주요 기여

문맥적 검색의 우수성: 본 논문은 LLM이 생성한 자연어 설명을 기반으로 예시를 검색하는 것이 원시 소스 코드 임베딩을 기반으로 하는 것보다 성능이 훨씬 뛰어나다는 것을 입증했다. 이는 알고리즘적 의도를 추상화하는 것이 효과적인 퓨샷 학습(few-shot learning)에 결정적임을 시사한다.
RAS 프레ка임워크: 저자들은 문맥적 검색과 반복적 빔 서치를 결합한 RAS를 제안한다. 이 접근 방식은 최적화를 단일 단계 생성 작업이 아닌 순차적 탐색 문제로 취급한다.
해석 가능성을 위한 AEGIS: AEGIS는 훈련 데이터를 원자적이고 일반화 가능한 편집으로 정제하는 방법을 소개한다. 이를 통해 시스템은 상당한 성능 저하 없이 더 작고 해석 가능한 단계로 최적화를 수행할 수 있다.
포괄적 평가: 제안된 방법들은 동적 검색, 지시문 전용 프롬프팅, 인간의 성능을 포함한 최첨단 베이스라인과 함께 PIE 벤치마크(C++) 및 Mercury 벤치마크(Python)에서 평가되었다.

결과

C++ 최적화 (PIE 벤치마크)

RAS 성능: Qwen3-Coder를 사용했을 때, RAS는 이전의 최첨단 동적 검색 베이스라인인 **4.23×**에 비해 평균 **8.70×**의 속도 향상을 달려냈다. 이는 베이스라인 대비 2.06× 개선된 수치이다.
AEGIS 성능: GPT-4o를 사용한 AEGIS는 **6.08×**의 평균 속도 향상을 달성했다. 특정 모델을 사용한 전체 RAS보다는 약간 낮았지만, AEGIS는 현저히 작은 규모의 편집을 생성했다.
편집 크기: AEGIS는 RAS(GPT-4o 사용 시)와 비교하여 평균 편집 크기(문자열 편집 거리로 측정)를 17% 줄였으며, 탐색 과정의 첫 번째 편집만을 고려했을 때는 **30%**를 줄였다.
정확도: GPT-4o 실험에서 RAS는 **99.5%**의 정확도(모든 테스트 케이스를 통과하는 프로그램)를 유지한 반면, AEGIS는 **100%**를 달성했다. 10개의 DeepSeek 3.2 출력물 중 일부에 대해 CBMC를 이용한 형식 검증(formal verification)을 실시한 결과, 8개 사례에서 의미론적 동등성이 확인되었으며 나머지 2개는 미세한 포맷팅(줄바꿈) 차이만 있었다.

Python 최적화 (Mercury 벤치마크)

Qwen2.5-7B-Instruct와 함께 RAS를 사용했을 때, 평균 실행 시간 백분위 지표(Beyond@1)가 베이스라인 대비 10.27 개선되어, 이 모델과 더 큰 추론 모델 간의 성능 격차를 크게 좁혔다.

의의 및 주장

본 논문은 프로그램 최적화를 점진적인 단계로 나누는 것이 LLM의 코드 최적화 능력을 크게 향상시킨다고 주장한다. 저자들은 문맥적 검색(자연어 설명을 사용함)이 코드 기반 검색보다 우수한 성능을 내는 데 있어 핵심적인 요소임을 강조한다. 또한, AEGIS가 상당한 성능 손실 없이도 점진적인 변화를 강제함으로써 LLM 기반 최적화를 더 해석 가능하고 안전하게 만드는 실행 가능한 경로를 제공한다고 주장한다. 이 연구는 이러한 블랙박스 적응 전략을 파인튜닝(fine-tuning)의 실질적인 대안으로 위치시키며, 느린-빠른 프로그램 쌍의 기존 훈련 데이터셋을 활용하여 프로그램 최적화에서 최첨단 결과를 달성할 수 있음을 보여준다.