기술 요약: 경험적 계산: 프롬프팅 대 프로그래밍

문제 정의

본 논문은 계산 문제를 해결하는 방식의 패러다임 변화를 식별한다: 즉, 프로그래밍(정밀한 알고리즘과 데이터 구조를 명시하는 것)에서 프롬프팅(대규모 언어 모델이나 에이전트에게 비정형적인 자연어 설명을 제공하는 것)으로의 이동이다. 전통적인 계산이 결정론적 절차와 검증 가능한 정확성 및 잘 정의된 복잡도 경계(예: 정렬을 위한 $O(n \log n)$)에 의존하는 반면, "경험적 계산(empirical computation)"은 확률 분포로부터 출력을 샘플링하는 것에 의존한다.

핵심 문제는 이러한 새로운 형태의 계산 능력을 고전적인 컴퓨터 과학의 합리주의적 틀 안에서는 이해할 수 없다는 점이다. 구체적으로는 다음과 같다:

1. 비결정론의 부재: 출력은 절차적으로 생성되는 것이 아니라 "경험적으로 가장 가능성이 높은" 결과물이며, 이로 인해 전통적인 디버깅을 통해 국소화하거나 수정할 수 없는 환각(hallucination)과 오류에 취격될 수 있다.
2. 입력의 모호성: 프로그래밍이 형식적 계약(타입, 포맷)을 요구하는 것과 달리, 프롬프팅은 맥락과 모델의 학습 분포에 따라 해석이 달라지는 비정형 입력을 수용한다.
3. 불분명한 복잡도: 실행 시간 동작이 고전적인 계산 복잡도와는 무관하게 나타나며, 대신 토큰화 및 모델 추론 동작과 상관관계를 갖는다.
4. 검증의 간극: 기존의 소프트웨어 공학(SE) 기술(정적 분석, 형식 검증)은 명시적인 프로그램이 존재하지 않는 시스템을 분석하기에는 부적합하다.

방법론

저자들은 다섯 가지 고전적인 계산 문제를 대상으로 경험적 계산의 효율성과 정확성을 규명하기 위해 예비 실험을 수행하였다:

1. 정렬(Sorting): 무작위 숫자의 오름차순 정렬.
2. 탐색(Searching): 정렬된 리스트 및 정렬되지 않은 리스트에서 인덱스 찾기.
3. 최장 팰린드롬 부분 문자열(Longest Palindromic Substring): 문자열 내에서 가장 긴 팰린드롬 시퀀스 찾기.
4. 부분 집합 합 문제(Subset Sum Problem, SSP): 합계가 목표값과 일치하는 숫자들의 부분 집합 찾기.

실험 설정:

• 모델: 실험에는 로컬 맥북 프로(M5 Pro, 48GB RAM)에서 실행되는 오픈 웨이트 모델인 gemma-4-26b-a4b를 사용하여 네트워크 지연 시간을 제거하였다.
• 구성: 세 가지 모드를 테스트하였다:
  • 기본(Default): Temperature = 1.0.
  • 결정론적(Deterministic): Temperature = 0.0.
  • 사고(Thinking): 추론 모드 활성화.
• 지표:
  • 효율성: 솔루션 도달 시간 및 첫 번째 정답 도달 시간.
  • 정확성: 수학적으로 올바른 답을 반환하는 시행의 비율.
• 변수: 입력 크기($n$), 숫자 정밀도, 그리고 언어 표현(영어, 독일어, 한국어, 일본어 등의 다양한 언어에서의 숫자 표기 방식).
• 정답(Ground Truth): 비자명한 문제들(Substring, SSP)의 경우, 검증을 위해 간단한 파이썬 프로그램을 사용하여 정답을 생성하였다.

주요 결과

1. 효율성 대 고전적 복잡도

고전적 이론과 달리, 경험적 계산의 실행 시간은 문제의 알고리즘 복잡도(예: $O(n)$ 대 $O(n \log n)$)를 엄격히 따르지 않는다.

• 선형 스케일링: 정렬, 탐색, SSP의 경우, 모든 모드에서 솔루션 도달 시간이 입력 크기에 따라 선형적으로 증가하였다($O(n)$). 저자들은 이를 계산 로직보다는 입력/출력 토큰의 선형적 증가 때문이라고 설명한다.
• 토큰 의존성: 숫자를 증가시키는 데 걸리는 시간은 SHA-512 해시로부터 평문(plaintext)을 예측하는 데 걸리는 시간과 유사했는데, 이는 실행 시간이 문제의 난이도가 아닌 토큰화 및 추론 메커니즘에 의해 결정됨을 시사한다.
• 사고 모드의 비용: "사고(thinking)" 기능을 활성화하면 실행 시간이 크게 증가하였으나(예: 150개 요소 정렬 시 최대 275초), 높은 정확도를 유지하였다.

2. 정확성과 입력 크기

• 크기 민감도: 기본(Default) 및 결정론적(Deterministic) 모드에서는 입력 크기가 증가함에 따라 정확도가 급격히 저하되었다.
  • 50개의 정수를 정렬할 때, 정확도는 약 50%(동전 던지기 확률)로 떨어졌다.
  • 150개의 정수를 정렬할 때, (선형적 시간 증가에도 불구하고) 정확도는 약 58%로 하락하였다.
  • Subset Sum 문제의 경우, 리스트 길이가 10에 도달하자 정확도가 0에 수렴하였다.
  • Substring 문제의 경우, 문자열 길이가 5가 되자 정확도가 거의 0으로 떨어졌다.
• 사고 모드의 회복력: 추론 능력이 활성화되었을 때, 토큰/시간 제한 범위 내에서 더 큰 입력에 대해서도 높은 정확도(>90%)를 유지하였다.

3. 자연어 표현의 영향

연구는 숫자를 표현하는 언어가 정확도에 미치는 영향을 조사하였다.

• 데이터 표현 편향: 정확도는 모델의 학습 데이터 내에 존재하는 언어의 표현 방식에 크게 의존한다.
• 높은 표현도 대 낮은 표현도: 영어(잘 표현된 언어)로 작성된 숫자를 정렬하는 것은 크기 20에 대해 95% 이상의 정확도를 보였다. 반면, 독일어(저표현 언어)로 작성된 숫자를 정렬하는 것은 동일한 크기에 대해 1% 미만의 정확도를 보였다.
• 결론: 경험적 계산은 언어 중립적이지 않으며, 학습 코퍼스에 널리 퍼져 있는 언어와 형식에 편향되어 있다.

4. 오류 특성

코드의 특정 라인으로 결함을 국소화할 수 있는 전통적인 프로그램과 달리, 경험적 계산의 오류는 비결정론적이다. LLM은 다음과 같은 오류를 범할 수 있다:

• 입력에 없는 숫자를 더함.
• 입력에 있는 숫자를 누락함.
• 숫자를 중복함.
• 전체 리스트를 정렬하는 데 실패함.
• 큰 입력을 잘라냄(Truncate).

주요 기여

1. 경험적 계산의 정의: 본 논문은 솔루션이 절차적 실행이 아닌 프롬프팅과 샘플링을 통해 생성되는 별도의 분야로서 "경험적 계산"을 공식적으로 도입하였다.
2. 경험적 특성 규명: LLM이 고전적 알고리즘 문제를 해결할 때의 효율성과 정확성을 체계적으로 측정한 최초의 연구로서, 실행 시간이 알고리즘 복잡도가 아닌 토큰화와 상관관계가 있음을 밝혀냈다.
3. 한계 식별: 사고 모드 없이는 경험적 계산이 입력 크기에 따라 안정적으로 확장되지 못하며, 입력의 언어적 표현에 매우 민감하다는 것을 입증하였다.
4. 새로운 SE 기반에 대한 촉구: 저자들은 소프트웨어 공학계가 이러한 시스템을 분석, 추정 및 예측하기 위해 "경험적 프로그램 분석(empirical program analysis)"(통계적, 반사실적 또는 인과적 추론)을 위한 새로운 도구를 개발해야 한다고 주장한다.

의의 및 비전

본 논문은 소프트웨어 공학계가 AI 기반 계산의 신뢰성을 보장하기 위해 고전적인 합리주의 프레임워크나 기존의 프로그램 분석 도구에 의존할 수 없다고 단언한다. LLM과 에이전트가 계산 문제를 해결하는 데 필수적인 요소가 됨에 따라, 다음과 같은 과제를 해결하기 위한 분야의 진화가 필요하다:

• 공식적인 프로그램이 없는 상황에서 정확도를 어떻게 분석할 것인가?
• 경험적 계산의 한계를 어떻게 정의하고 테스트할 것인가?
• 회귀(regression)를 유발하지 않으면서 특정 문제 인스턴스에 대한 정확도를 어떻게 개선할 것인가?

저자들은 이를 시의적절하고 풍부한 연구 분야로 규정하며, LLM의 확률적 본질과 소프트웨어 공학의 엄격한 요구 사항 사이의 간극을 메우기 위해 "경험적 프로그램 분석" 기술의 개발을 촉구하고 있다. 본 논문은 이 문제들을 해결하려는 것이 아니라, 이 분야를 확립하고 새로운 이론적 및 실무적 토대의 시급한 필요성을 강조하는 데 목적이 있다.