Agentic AI 성능 향상, Big O 컨셉 이해

작성자:

Other Language Version: [English] [Japanese]

Big O 표기법은 알고리즘의 성능을 수학적으로 설명하는 표기법입니다. 특히, 알고리즘의 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)를 입력 크기(\(n\))에 대한 함수로 나타내어, 입력 크기가 커질수록 알고리즘의 실행 시간이나 사용 메모리가 어떻게 증가하는지 점근적(asymptotic)으로 분석하는 데 사용됩니다.
쉽게 말해, 알고리즘이 얼마나 효율적인지, 특히 입력 데이터의 양이 엄청나게 많아질 때 얼마나 빨라지거나 느려지는지를 예측하는 방법이라고 생각하시면 됩니다.

1. Big O 표기법(Big O notation) 이란?

1) 왜 Big O 표기법을 사용할까요?

  • 알고리즘 비교: 여러 알고리즘 중에서 어떤 것이 특정 문제에 더 효율적인지 객관적으로 비교할 수 있게 해줍니다.
  • 성능 예측: 입력 데이터의 크기가 커질 때 알고리즘의 성능이 어떻게 변화할지 예측할 수 있습니다.
  • 병목 현상 식별: 성능 저하의 주된 원인이 되는 부분을 식별하고 개선하는 데 도움을 줍니다.
  • 하드웨어 독립성: 특정 컴퓨터의 CPU 속도나 메모리 용량과 같은 하드웨어적인 요소에 의존하지 않고, 순수하게 알고리즘 자체의 효율성을 평가할 수 있습니다.

2) Big O 표기법의 주요 특징

  • 최악의 경우(Worst-Case) 분석: 일반적으로 Big O 표기법은 알고리즘이 가장 비효율적으로 동작할 수 있는 ‘최악의 경우’를 기준으로 성능을 분석합니다. 이는 알고리즘의 성능이 최소한 어느 정도는 보장된다는 것을 의미합니다.
  • 상수항 무시: 알고리즘의 실행 시간에 영향을 미치는 상수 시간(예:\(100n\) 에서 \(100\))은 입력 크기가 매우 커질 때 그 중요성이 미미해지므로 무시합니다. 즉, \(O(2n+5)\)는 \(O(n)\)으로 표기합니다.
  • 최고차항만 고려: 여러 항이 있을 경우, 입력 크기 \(n\)이 커질수록 가장 큰 영향을 미치는 최고차항만 고려합니다. 예를 들어, \(O(n^2 + n)\)은 \(O(n^2)\)으로 표기합니다. 이는 \(n^2\)이 \(n\)보다 훨씬 빠르게 증가하기 때문입니다.

3) 주요 Big O 복잡도 종류 (낮은 복잡도 -> 높은 복잡도)

  • \(O(1)\) – 상수 시간 복잡도 (Constant Time):
    • 입력 크기에 관계없이 항상 일정한 시간이 걸립니다.
    • 예시: 배열에서 특정 인덱스의 요소를 읽는 것, 스택에 push/pop 하는 것.
  • \(O(\log n)\) – 로그 시간 복잡도 (Logarithmic Time):
    • 입력 크기가 커질수록 실행 시간이 매우 느리게 증가합니다. 주로 문제를 절반씩 줄여나가는 알고리즘에서 나타납니다.
    • 예시: 이진 탐색(Binary Search).
  • \(O(n)\) – 선형 시간 복잡도 (Linear Time):
    • 입력 크기에 비례하여 실행 시간이 증가합니다.
    • 예시: 배열의 모든 요소를 한 번씩 순회하는 것, 정렬되지 않은 배열에서 특정 요소를 찾는 것.
  • \(O(n \log n)\) – 선형 로그 시간 복잡도 (Linearithmic Time):
    • \(O(n)\)보다 느리지만 \(O(n^2)\)보다 빠릅니다. 효율적인 정렬 알고리즘에서 자주 볼 수 있습니다.
    • 예시: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort).
  • \(O(n^2)\) – 2차 시간 복잡도 (Quadratic Time):
    • 입력 크기의 제곱에 비례하여 실행 시간이 증가합니다. 중첩된 반복문에서 흔히 나타납니다.
    • 예시: 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort).
  • \(O(2^n)\) – 지수 시간 복잡도 (Exponential Time):
    • 입력 크기가 조금만 커져도 실행 시간이 기하급수적으로 증가합니다. 매우 비효율적인 알고리즘입니다.
    • 예시: 피보나치 수열을 재귀로 계산하는 naive한 방법, 브루트 포스(Brute-force) 방식으로 모든 부분집합을 생성하는 경우.
  • \(O(n!)\) – 팩토리얼 시간 복잡도 (Factorial Time):
    • 입력 크기가 1씩 증가할 때마다 실행 시간이 엄청나게 증가합니다. 가장 비효율적인 복잡도 중 하나입니다.
    • 예시: 외판원 문제(Traveling Salesman Problem)를 Brute Force Algorithm 으로 해결하는 경우.
Code 예시(Python)
  • 예시 1: \(O(1)\)
    • 이 함수는 배열의 크기가 아무리 커져도 항상 첫 번째 요소를 반환하는 데 걸리는 시간은 동일합니다. 따라서 \(O(1)\)입니다.
def get_first_element(arr):
    return arr[0]
  • 예시 2: \(O(n)\)
    • 이 함수는 배열의 모든 요소를 한 번씩 순회합니다. 배열의 크기(\(n\))에 비례하여 실행 시간이 증가하므로 \(O(n)\)입니다.
def sum_elements(arr):
    total = 0
    for element in arr:
        total += element
    return total
  • 예시 3: \(O(n^2)\)
    • 이 함수는 중첩된 두 개의 반복문을 가지고 있습니다. 각 반복문은 배열의 크기(\(n\))만큼 반복되므로, 총 \(n \times n=n^2\)번 연산이 수행됩니다. 따라서 \(O(n^2)\)입니다.
def print_pairs(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i], arr[j])
요약

Big O 표기법은 개발자가 알고리즘의 효율성을 이해하고, 대규모 데이터셋에서 어떤 알고리즘이 더 적합한지 판단하는 데 필수적인 도구입니다. 최적의 성능을 가진 시스템을 설계하고 구현하기 위해서는 빅 O 표기법에 대한 이해가 매우 중요합니다.

2. LLM 시대에 맞는 Big O 이해

Big O 표기법을 LLM, MCP(Model Context Protocol), AI Agent와 같은 최신 기술 개념에 접목하여 설명하는 것은 매우 흥미롭고 시사하는 바가 큽니다. 전통적인 알고리즘 분석을 넘어, 복잡한 인공지능 시스템의 성능을 이해하고 최적화하는 데 중요한 통찰력을 제공할 수 있습니다.

1) Big O 표기법의 새로운 지평: AI 시대의 복잡도 분석

기존 Big O 표기법이 주로 CPU 연산 횟수와 메모리 사용량을 중심으로 알고리즘의 효율성을 평가했다면, LLM, MCP, AI Agent와 같은 최신 기술에서는 ‘연산’의 정의가 확장되고 ‘리소스’의 종류가 다양해지면서 복잡도 분석에도 새로운 관점이 필요합니다.

핵심은 시스템의 ‘입력’이 무엇이고, ‘처리’ 과정에서 어떤 ‘리소스’가 소모되며, 그 ‘리소스’ 소모가 입력 크기에 따라 어떻게 ‘증가’하는가를 정의하는 것입니다.

2) Big O(Token): LLM의 언어 처리 복잡도

LLM(Large Language Models)의 핵심적인 입력 단위는 ‘토큰(Token)’입니다. 토큰은 단어, 구두점, 심지어는 글자의 일부가 될 수도 있습니다. LLM의 추론 시간과 비용은 주로 입력 및 출력 토큰의 수에 의해 결정됩니다.

설명:

정의: Big O(Token)은 LLM이 특정 작업을 수행하는 데 필요한 입력 토큰 수(\(N_{input}\))와 출력 토큰 수(\(N_{output}\))에 따라 연산 시간 및 비용이 어떻게 변화하는지를 나타내는 개념입니다.

주요 고려 사항:
  • 입력 토큰 수 (Context Window): LLM은 제한된 ‘컨텍스트 윈도우(Context Window)’를 가집니다. 이 윈도우 크기(최대 토큰 수)를 넘어서는 입력은 처리할 수 없거나, 내부적으로 요약(summarization) 등의 추가적인 처리가 필요합니다.
  • Self-Attention 메커니즘: LLM의 핵심인 트랜스포머(Transformer) 아키텍처의 Self-Attention 메커니즘은 입력 시퀀스 길이(토큰 수)에 대해 \(O(N_{input}^2)\)의 시간 복잡도를 가집니다. 이는 입력 토큰 수가 늘어날수록 연산량이 기하급수적으로 증가한다는 의미입니다. 이로 인해 컨텍스트 윈도우 크기에 제한이 생기는 주요 원인이 됩니다.
  • 출력 토큰 생성: LLM이 응답을 생성하는 과정은 보통 토큰 하나씩 순차적으로 생성됩니다. 각 토큰을 생성하는 데 걸리는 시간은 일반적으로 상수 시간(\(O(1)\))으로 볼 수 있지만, 전체 출력 길이\((N_{output})\)에 비례하여 총 시간이 소요되므로, 출력 생성 자체는 \(O(N_{output})\)의 복잡도를 가집니다.
  • 프롬프트 엔지니어링의 중요성: 불필요하게 긴 프롬프트는 \(N_{input}\)을 증가시켜 \(O(N_{input}^2)\)의 비용을 유발하고, 불필요한 장황한 출력은 \(N_{output}\)을 증가시켜 \(O(N_{output})\)의 비용을 증가시킵니다. 따라서 효율적인 프롬프트는 Big O(Token)를 최적화하는 핵심입니다.
예시:
  • 단순 질문-답변: 짧은 질문(낮은 \(N_{input}\))과 짧은 답변(낮은 \(N_{output}\))은 낮은 \(O(1)\) 또는 \(O(N_{output})\)에 가까운 복잡도를 가집니다 (Self-Attention이 미미한 영향을 미치는 수준).
  • 긴 문서 요약: 매우 긴 문서(\(N_{input}\)이 큼)를 요약하는 작업은 \(O(N_{input}^2)\)의 Self-Attention 비용이 지배적이며, 요약된 출력 길이(\(N_{output}\))에 따라 \(O(N_{output})\)의 생성 비용이 추가됩니다.
  • 코드 생성: 요구사항 명세(낮은 \(N_{input}\))가 길어지고 생성해야 할 코드의 길이(\(N_{output}\))가 길어질수록 \(O(N_{output})\)의 복잡도가 두드러집니다.

3) Big O(Agent): AI 에이전트 협업 및 의사결정 복잡도

AI Agent 시스템, 특히 MCP(Model Context Protocol)와 같이 여러 에이전트가 협업하여 복잡한 문제를 해결하는 경우, ‘입력’은 단순히 데이터의 양뿐만 아니라 ‘목표의 복잡성’, ‘에이전트 수’, ‘상호작용 횟수’ 등이 될 수 있습니다.

설명:

정의: Big O(Agent)는 목표 달성을 위해 필요한 에이전트 수(\(N_{agent}\)), 상호작용 횟수(\(N_{interaction}\)), 또는 문제 공간의 크기(\(S_{problem}\))에 따라 AI 에이전트 시스템의 전체 실행 시간과 리소스 사용량이 어떻게 변화하는지를 나타내는 개념입니다.

주요 고려 사항:
  • 에이전트 간 통신/협업: 에이전트의 수가 늘어날수록 서로 정보를 주고받거나(통신), 조율하는(협업) 데 필요한 오버헤드가 증가할 수 있습니다. 예를 들어, 모든 에이전트가 모든 다른 에이전트와 통신해야 한다면 \(O(N_{agent}^2)\)의 통신 복잡도가 발생할 수 있습니다.
  • 의사결정 복잡성: 각 에이전트가 다음 행동을 결정하는 데 필요한 추론 과정은 내부적으로 LLM 호출(Big O(Token)에 영향)이나 탐색(Search) 알고리즘을 포함할 수 있습니다. 문제 공간의 크기(\(S_{problem}\))에 따라 이 의사결정의 복잡도가 증가할 수 있습니다 (\(O(\log S_{problem})\), \(O(S_{problem})\) 등).
  • 태스크 분해 및 할당: 복잡한 목표를 에이전트들에게 효율적으로 분해하고 할당하는 과정 자체도 복잡도를 가집니다. 이는 \(O(N_{tasks})\) 또는 \(O(N_{tasks} \log N_{agents})\)와 같이 나타날 수 있습니다.
  • 피드백 루프 및 재시도: 에이전트들이 목표 달성에 실패하여 재시도하거나 피드백 루프를 거치는 횟수(\(N_{retry}\))에 따라 전체 실행 시간이 늘어날 수 있습니다. 이는 \(O(N_{retry})\) 또는 더 복잡한 형태로 나타날 수 있습니다.
예시:
  • 단순 정보 수집: 여러 에이전트가 각각 독립적으로 웹 페이지를 탐색하여 정보를 수집하는 경우, 각 에이전트의 작업은 \(O(1)\) 또는 \(O(N_{page})\)이지만, 전체 시스템은 에이전트 수에 비례하여 병렬적으로 처리되므로, Big O(Agent)는 \(O(N_{page\_per\_agent})\) (가장 긴 작업에 의존)에 가깝습니다.
협력적 문제 해결 (ex: 소프트웨어 개발 에이전트):
  • A 에이전트(기획), B 에이전트(설계), C 에이전트(코딩), D 에이전트(테스트)가 순차적으로 작업하고 서로 피드백을 주고받는다면, 각 단계의 LLM 호출 및 내부 로직 비용의 합이 주된 복잡도가 됩니다.
  • 만약, 설계 단계에서 A와 B 에이전트가 N번의 토론을 통해 합의해야 한다면, 이 상호작용은 \(O(N_{discussion} \times \text{Big O(Token)})\)의 비용을 가질 수 있습니다.
  • 전반적인 개발 목표의 복잡성(Sproblem)이 증가하면, 각 에이전트의 의사결정 및 협업에 필요한 총 시간이 \(O(S_{problem})\) 또는 \(O(S_{problem}^2)\) 형태로 증가할 수 있습니다.
  • 탐색 기반 AI 에이전트: 미로 찾기나 게임 플레이와 같이 상태 공간이 넓은 문제에서 에이전트가 탐색 알고리즘을 사용한다면, 탐색 공간의 크기(\(S_{state\_space}\))에 따라 \(O(S_{state\_space})\) 또는 \(O(S_{state\_space} \log S_{state\_space})\)와 같은 복잡도를 가질수 있습니다.

4) Big O 분석의 실질적 의미와 한계

이러한 새로운 Big O 개념들은 AI 시스템의 설계 및 최적화에 중요한 시사점을 제공합니다.

  • 최적화 방향 제시: 예를 들어, LLM 비용이 너무 높다면 \(O(N_{input}^2)\)를 야기하는 Self-Attention을 줄이기 위해 입력 토큰 길이를 최적화하거나, \(O(N_{output})\)를 줄이기 위해 간결한 응답을 유도하는 방향으로 프롬프트 엔지니어링을 개선해야 함을 시사합니다. AI Agent 시스템에서 \(O(N_{agent}^2)\)의 통신 복잡도가 나타난다면, 에이전트 간의 통신 방식을 최적화(예: 브로드캐스트 대신 라우팅 사용)하거나, 계층적인 에이전트 구조를 도입하여 통신량을 줄이는 방법을 고려할 수 있습니다.
  • 확장성 예측: 특정 AI 시스템이 미래에 더 큰 규모의 문제나 더 많은 에이전트를 처리해야 할 때, 현재의 아키텍처가 얼마나 확장될 수 있을지 예측하는 데 도움을 줍니다.
  • 자원 관리: 클라우드 환경에서 LLM API 호출 비용이나 컴퓨팅 자원(GPU) 사용량을 예측하고 효율적으로 관리하는 데 중요한 지표가 됩니다.
한계:
  • 추상화의 난이도: LLM이나 AI Agent의 내부 로직은 매우 복잡하며, 모든 세부 연산을 Big O로 명확하게 추상화하기 어려울 수 있습니다.
  • 상수 요인의 중요성: Big O는 점근적 분석이므로 상수 요인을 무시하지만, 실제 서비스에서는 이 상수 요인이 중요한 성능 차이를 만들 수 있습니다 (예: 특정 LLM의 기본 추론 속도).
  • 비결정적 특성: AI 에이전트의 행동은 확률적이거나 비결정적일 수 있어, 최악의 경우를 항상 명확히 정의하기 어려울 수 있습니다.
요약

Big O 표기법은 컴퓨터 과학의 고전적인 개념이지만, LLM, MCP, AI Agent와 같은 최신 인공지능 시스템의 복잡성을 이해하고 관리하는 데 여전히 강력하고 필수적인 도구입니다. Big O(Token)과 Big O(Agent)는 이러한 새로운 컴퓨팅 패러다임에 맞춰 기존의 복잡도 분석 프레임워크를 확장하고, AI 시스템의 효율성을 설계하고 최적화하는 데 중요한 개념적 기반을 제공할 것입니다. 이를 통해 우리는 더욱 지능적이고 확장 가능한 AI 시스템을 구축할 수 있게 될 것입니다.

3. 조직내 SLM 구축시 고려 사항

개인 PC나 조직 내 서버에 설치되는 SLM(Small Language Model) 모델의 성능을 평가할 때 Big O 개념을 적용하는 것은 매우 중요합니다. 클라우드 기반 LLM과 달리, 온프레미스(On-premise) 환경에서는 제한된 하드웨어 자원을 최대한 효율적으로 활용해야 하기 때문에 알고리즘의 복잡도 분석이 더욱 부각됩니다.

다음은 SLM 모델의 성능 평가에 Big O 개념을 적용하는 구체적인 아이디어입니다.

1) Big O(Token) for SLM Inference

LLM과 마찬가지로 SLM도 토큰을 기반으로 동작합니다. 하지만 SLM은 LLM보다 파라미터 수가 적고, 종종 특정 도메인에 특화되어 학습되므로, 동일한 토큰 수라도 실제 동작 방식과 최적화 전략이 다를 수 있습니다.

인풋 토큰 길이(\(N_{input}\))에 따른 추론 시간 복잡도 분석:
  • \(O(N_{input})\) (선형): 가장 이상적인 시나리오입니다. 입력 토큰 수가 증가함에 따라 추론 시간이 선형적으로 증가한다면, 해당 SLM은 매우 효율적으로 설계되었거나, 특정 최적화(예: sparse attention, 압축 기법)가 잘 적용되었다고 볼 수 있습니다. 실제로는 트랜스포머 아키텍처의 self-attention 특성상 순수한 \(O(N_{input})\)는 어렵지만, 특정 최적화로 인해 선형에 가깝게 동작하도록 만들 수 있습니다.
  • \(O(N_{input} \log N_{input})\) (선형 로그): 일부 효율적인 트랜스포머 변형(예: Linear attention variants) 또는 특화된 SLM 아키텍처에서 나타날 수 있는 복잡도입니다. LLM의 \(O(N_{input}^2)\)보다 훨씬 효율적입니다.
  • \(O(N_{input}^2)\) (2차): 일반적인 트랜스포머 아키텍처의 self-attention의 본질적인 복잡도입니다. SLM이라 할지라도 이 부분을 최적화하지 않으면 입력 길이가 길어질수록 급격히 느려집니다. 온프레미스 환경에서는 GPU 메모리 부족이나 CPU 병목 현상으로 이어질 수 있습니다.
  • 평가 방법: 다양한 길이(\(N_{input}\))의 입력을 SLM에 주고, 각 입력 길이에 대한 추론 시간(TTFT: Time To First Token, TTPT: Time To Per Token)을 측정하여 그래프로 시각화합니다. 그래프의 기울기나 곡선을 통해 대략적인 Big O를 유추할 수 있습니다.

아웃풋 토큰 길이(\(N_{output}\))에 따른 생성 시간 복잡도 분석:

  • \(O(N_{output})\) (선형): 대부분의 LLM/SLM은 토큰을 순차적으로 생성하므로, 출력 토큰 수에 비례하여 생성 시간이 증가합니다. 이는 일반적인 현상이며, 이 복잡도 자체를 줄이기보다는 토큰 생성 속도(Tokens per second)를 높이는 것이 중요합니다.
  • 평가 방법: 고정된 입력 토큰 길이에 대해 다양한 길이(\(N_{output}\))의 응답을 생성하도록 요청하고, 각 응답 길이에 대한 총 생성 시간을 측정합니다.
토큰 복잡도에 영향을 미치는 요인 분석 (온프레미스 특화):
  • 모델 크기 (파라미터 수): SLM이라 할지라도 수십억 개의 파라미터(≈ 7B, 13B)를 가질 수 있습니다. 이는 GPU 메모리 사용량에 직접적인 영향을 미칩니다. Big O는 파라미터 수에 직접 비례하지 않지만, 파라미터 수가 클수록 단일 연산의 상수 시간이 늘어나고, 메모리 제약으로 인한 병목이 발생할 가능성이 높아집니다.
  • 양자화(Quantization) 수준: INT8, INT4 등 양자화 레벨에 따라 연산 속도와 메모리 사용량이 달라집니다. 양자화는 \(O(1)\)연산의 상수 시간을 줄이는 효과를 가져오지만, 너무 낮게 양자화하면 정확도 손실이 발생할 수 있습니다.
  • 배치 사이즈(Batch Size): 여러 요청을 묶어서 한 번에 처리하는 배치 처리 시, 실제 Big O는 \(O(N_{input}^2 \times \text{Batch Size})\)가 될 수 있습니다. 하지만 하드웨어 활용률을 높여 전체적인 처리량(Throughput)을 개선하므로, 일반적으로 큰 배치 사이즈가 유리합니다. 개인 PC나 서버의 GPU 메모리 제약 하에서 최적의 배치 사이즈를 찾는 것이 중요합니다.
  • 하드웨어 제약: CPU, GPU 종류, RAM, VRAM 등 하드웨어 사양에 따라 동일한 Big O 복잡도라도 실제 실행 시간은 크게 달라집니다. 특히 VRAM은 모델 로딩 및 컨텍스트 유지를 위해 매우 중요합니다.

2) Big O(Concurrent Requests) for SLM Deployment

조직 내 서버 환경에서는 여러 사용자가 동시에 SLM에 요청을 보낼 수 있습니다. 이 경우, 동시 요청 수에 따른 시스템의 처리량(Throughput)과 지연 시간(Latency) 변화를 Big O 개념으로 분석할 수 있습니다.

동시 요청 수(\(N_{requests}\))에 따른 처리량(Queries Per Second, QPS) 복잡도:
  • \(O(1)\) (상수 처리량): 하드웨어 자원이 무한하거나, 시스템이 병렬 처리에 매우 최적화되어 있다면, 동시 요청 수가 증가해도 각 요청당 처리 시간은 일정하고, 총 처리량도 거의 일정하게 유지될 수 있습니다 (실현 불가능에 가까운 이상적 상황).
  • \(O(Batch Size)\) 또는 \(O(N_{requests}/Batch\space Size)\): 현실적으로는 배치 사이즈가 고정되어 있을 때, 처리량은 (동시 요청 수 / 배치 사이즈)에 비례합니다. 즉, 동시 요청 수가 배치 사이즈의 배수가 될 때마다 효율이 상승하고, 그 사이에서는 동일한 자원이 소모될 수 있습니다.
  • \(O(N_{requests})\) (선형 감소): 동시 요청 수가 증가함에 따라 각 요청당 처리 시간이 선형적으로 증가하고, 총 처리량은 포화 상태에 도달하거나 감소하는 경향을 보입니다. 이는 병렬 처리의 한계점이나 자원(CPU 코어, GPU 메모리, IO) 병목 현상을 나타냅니다.
  • 평가 방법: JMeter, Locust 등 부하 테스트 도구를 사용하여 동시 요청 수를 점진적으로 늘려가면서 시스템의 QPS와 각 요청의 평균 지연 시간을 측정합니다. 이를 통해 시스템이 몇 개의 동시 요청까지 효율적으로 처리할 수 있는지, 그리고 이후에 어떤 복잡도로 성능이 저하되는지 파악할 수 있습니다.
동시 요청 수(\(N_{requests}\))에 따른 지연 시간(Latency) 복잡도:
  • \(O(1)\) (상수 지연 시간): 매우 낮은 동시 요청 수에서 나타나는 이상적인 상황.
  • \(O(N_{requests})\) (선형 증가): 동시 요청 수가 많아지면서 큐잉(Queuing) 현상이나 자원 경합(Resource Contention)으로 인해 각 요청의 지연 시간이 선형적으로 증가하는 가장 일반적인 시나리오입니다.
  • \(O(N_{requests}^2)\) (2차 증가): 매우 심각한 병목 현상이나 비효율적인 자원 관리(예: 락(lock) 경쟁 심화)가 있을 때 발생할 수 있습니다.
자원 사용량(CPU,GPU,RAM):
  • 동시 요청 수(\(N_{requests})\)에 따라 CPU 사용량, GPU 사용량, 메모리 사용량이 어떻게 변화하는지 모니터링합니다.
  • 예를 들어, CPU 사용량이 \(O(N_{requests})\)로 선형적으로 증가하며 특정 임계점을 넘어서면 QPS가 더 이상 증가하지 않거나 감소한다면, CPU가 병목 지점임을 알 수 있습니다.
  • GPU 메모리 사용량이 \(O(N_{requests})\)로 증가하여 특정 VRAM 용량을 초과하면, 모델 로딩에 실패하거나 Swap이 발생하여 성능이 급격히 저하될 수 있습니다.

3) Big O 분석을 통한 SLM 최적화 및 배포 전략 제안

  • Big O 분석 결과를 바탕으로 개인 PC 및 조직 서버 환경에 맞는 SLM 최적화 및 배포 전략을 수립할 수 있습니다.
  • 모델 선택: 특정 \(N_{input}\) 범위에서 가장 낮은 Big O 복잡도를 보이는 SLM 모델을 선택합니다. 예를 들어, 짧은 질문 답변이 주 용도라면 \(O(N_{input})\)에 가까운 경량 모델이 유리합니다.
  • 하드웨어 업그레이드 우선순위: 분석 결과 CPU가 병목이라면 CPU 코어 수 확충, GPU 메모리가 부족하다면 더 많은 VRAM을 가진 GPU로 업그레이드하는 등 최적의 하드웨어 투자 방향을 결정합니다.
  • 배치 처리 최적화: \(O(Batch \space Size)\) 또는 \(O(N_{requests}/Batch \space Size)\) 복잡도를 이해하고, 주어진 하드웨어에서 최대 처리량을 얻을 수 있는 최적의 배치 사이즈를 찾아 설정합니다.
  • 서비스 큐 및 스케줄링: \(O(N_{requests})\) 지연 시간 증가를 완화하기 위해, 요청 큐를 사용하여 부하를 조절하거나, 우선순위 기반 스케줄링을 도입하는 등의 방법을 고려합니다.
모델 경량화 기법 적용:
  • 양자화(Quantization): 모델 크기를 줄이고 추론 속도를 높여, \(O(1)\)연산의 상수 시간을 줄이는 효과를 가져옵니다.
  • 프루닝(Pruning): 모델의 불필요한 연결을 제거하여 연산량을 줄입니다.
  • 지식 증류(Knowledge Distillation): 더 큰 LLM의 지식을 SLM으로 “증류”하여 더 작은 모델이 유사한 성능을 내도록 합니다.
  • 이러한 기법들은 본질적인 Big O를 변경하지 않을 수 있지만, 동일한 Big O 내에서 ‘상수 인자’를 크게 줄여 실제 성능을 향상시킵니다.
  • 캐싱 전략: 자주 나오는 질문이나 패턴에 대한 응답을 캐싱하여, 실제 모델 추론 없이 \(O(1)\)으로 응답하도록 함으로써 전체 시스템의 Big O(Request)를 개선할 수 있습니다.
  • RAG (Retrieval Augmented Generation) 도입: 복잡한 질문에 대해 LLM의 방대한 지식 대신, 로컬 DB나 문서에서 관련 정보를 검색(\(O(\log N_{docs})\) 또는 \(O(N_{docs})\))하여 SLM에 제공하는 RAG를 도입함으로써 SLM의 \(N_{input}\) 복잡도를 낮출 수 있습니다. 이는 SLM이 방대한 지식을 학습할 필요 없이 도메인 특화된 정보 처리에 집중하게 하여, 전반적인 성능을 최적화합니다.

이러한 Big O 개념의 적용은 개인 PC나 조직 내 서버와 같은 제한된 환경에서 SLM을 효율적으로 배포하고 관리하는 데 있어 매우 중요한 기준점을 제공할 것입니다.

4. Open SLM 모델 메모리 요구 사항에 대한 Big O 컨셉

1) 시간 복잡도 (Time Complexity)

시간 복잡도는 알고리즘의 연산 시간이 입력 크기(N)에 따라 어떻게 변화하는지를 나타냅니다. 최악의 경우를 기준으로 하며, 하드웨어 성능과 무관하게 알고리즘 자체의 효율성을 측정하는 지표입니다.

주요 고려 사항:
  • 연산 횟수: 알고리즘이 수행하는 핵심 연산(덧셈, 곱셈, 비교, 데이터 접근 등)의 총 횟수를 N에 대한 함수로 표현합니다.
  • GPU 성능 (Floating Point Operations Per Second, FLOPS): GPU는 초당 수행할 수 있는 부동소수점 연산의 수가 많을수록 특정 시간 복잡도를 가진 알고리즘을 더 빠르게 완료할 수 있습니다. 예를 들어, \(O(N^2)\) 알고리즘이 있다면, FLOPS가 높은 GPU는 N이 커질수록 더욱 큰 시간 단축 효과를 가져옵니다. 하지만 Big O 자체는 FLOPS에 비례하여 변하는 것이 아니라, N의 증가에 따른 연산 횟수의 증가 추이를 나타냅니다.
  • 병렬 처리: GPU는 본질적으로 병렬 연산에 최적화되어 있습니다. 특정 알고리즘이 병렬화가 잘 된다면, 동일한 \(Big \space O(N)\)를 가진 알고리즘이라도 순차 처리보다 훨씬 빠르게 실행됩니다.
  • 예: 행렬 곱셈(\(O(N^3)\) 일반적)은 GPU를 사용하면 N이 매우 클 때 병렬 처리 덕분에 실제 실행 시간이 훨씬 짧아집니다. LLM/SLM의 Self-Attention(\(O(N_{token}^2)\))도 GPU의 병렬 처리 덕분에 실제로 가능한 것입니다.
SLM 모델의 추론 시간 복잡도 (Big O(Token) 관점):
  • \(O(N_{token}^2)\) (Self-Attention): 트랜스포머 기반 모델의 가장 큰 시간 복잡도 요인입니다. 입력 토큰 길이(\(N_{token}\))가 길어질수록 연산량이 2차 함수적으로 증가합니다. 이는 GPU의 FLOPS와 VRAM에 가장 큰 부하를 주는 부분입니다. 개인 PC나 서버에서 컨텍스트 윈도우가 짧은 SLM을 사용할 경우, 이 \(N_{token}\) 값이 작아져 \(O(N_{token}^2)\)의 절대적인 연산량이 감소하므로 실제 실행 시간이 매우 짧아집니다.
  • \(O(N_{token})\) (FFN, LayerNorm 등): Feed-Forward Network, Layer Normalization 등은 입력 토큰 길이에 선형적으로 비례하는 연산량을 가집니다.

종합: SLM의 총 추론 시간 복잡도는 주로 Self-Attention(\(O(N_{token}^2)\))과 토큰 생성(\(O(N_{output)}\))에 의해 결정됩니다. 온프레미스 환경에서는 GPU의 FLOPS가 충분하다면, 주로 \(N_{token}\)과 \(N_{output}\)이 실제 추론 시간을 좌우합니다.

2) 공간 복잡도 (Space Complexity)

공간 복잡도는 알고리즘이 실행되는 동안 필요로 하는 메모리 크기가 입력 크기(N)에 따라 어떻게 변화하는지를 나타냅니다.

주요 고려 사항:
  • GPU 메모리 (VRAM): SLM 모델의 가중치(weights)가 로드되는 주된 공간입니다. 또한, 추론 과정에서 활성화 값(activations), K/V 캐시 등이 저장됩니다. VRAM이 부족하면 모델을 로드할 수 없거나, 추론 속도가 현저히 느려집니다(CPU-GPU 간 데이터 전송, 스왑 발생).
  • PC(서버) 메모리 (RAM): 모델의 가중치를 디스크에서 로드하여 VRAM으로 옮기거나, CPU 추론 시 사용됩니다. 여러 모델을 동시에 로드하거나, 매우 큰 데이터셋을 처리할 때 중요합니다. VRAM이 부족할 때 RAM으로 모델 일부를 오프로드하는 기법(CPU offloading, Quantization with Offloading)도 사용될 수 있지만, 이 경우 GPU-RAM 간 데이터 전송으로 인해 속도 저하가 발생합니다.
SLM 모델의 메모리 요구 사항 (Big O(Memory) 관점):
  • 모델 가중치 크기: SLM 모델의 파라미터 수(P)에 따라 결정됩니다.
  • 모델 크기 = P * (각 파라미터의 바이트 수)
  • 예: 7B (70억) 파라미터 모델이 FP16(2바이트)으로 저장되면 \(7 \times 10^9 \times 2 \approx 14 \text{GB}\)의 VRAM이 필요합니다.
  • 이는 \(O(P)\) (또는 \(O(1)\)로 보기도 합니다. 왜냐하면 \(P\)는 입력 크기 N에 독립적인 “모델 자체의 크기”이기 때문입니다. 하지만 여러 SLM을 비교할 때는 \(P\)가 중요한 비교 요소가 됩니다.)
  • 활성화 값 (Activations): 추론 과정에서 각 레이어의 출력 값이 임시로 저장되는 공간입니다. 트랜스포머 모델의 경우, Self-Attention 메커니즘에서 입력 토큰 길이(\(N_{token}\))와 모델의 히든 차원(\(D_{hidden}\))에 비례하여 메모리가 소모됩니다.
    • \(O(N_{token}×D_{hidden})\): 기본 활성화 값 저장.
    • \(O(N_{token}^2×Batch \space Size)\): Self-Attention의 쿼리(Q), 키(K), 값(V) 행렬 계산 시 발생할 수 있는 중간 결과물 저장 (특히 Softmax 어텐션 스코어).
    • 활성화 값은 보통 추론이 완료되면 해제되지만, \(N_{token}\)이 길어질수록 VRAM 사용량이 급증합니다.
  • K/V 캐시 (KV Cache): 토큰을 순차적으로 생성할 때, 이전에 생성된 토큰들의 Key 및 Value 행렬을 저장하여 불필요한 재계산을 피합니다. 입력 토큰 길이(\(N_{input}\))와 출력 토큰 길이(\(N_{output}\))에 비례합니다.
    • \(O((N_{input}+N_{output})×Batch \space Size×D_{head}×N_{layers})\):
      • \(N_{input}+N_{output}\): 컨텍스트 길이
      • \(Batch \space Size\): 동시 처리하는 요청 수
      • \(D_{head}\): 어텐션 헤드의 차원
      • \(N_{layers}\): 모델의 레이어 수
    • 이 캐시는 배치 사이즈가 커지거나 입력/출력 길이가 길어질수록 VRAM을 많이 소모하며, 특히 LLM/SLM의 Long Context 추론에서 VRAM 부족의 주범이 됩니다.

3) 최근 공개되는 Open SLM 모델의 메모리 요구 사항 분석 (Big O 컨셉 적용)

최근 공개되는 Open SLM 모델들은 다양한 크기(파라미터 수)와 아키텍처 최적화를 통해 메모리 요구 사항을 줄이려는 시도가 많습니다. 이를 Big O 컨셉에서 분석할 수 있습니다.

파라미터 수 감소 (모델 크기): \(O(P)\) 개선
  • 예시: Llama 3 8B, Phi-3-mini (3.8B), Gemma 2B/7B
  • 분석: 단순히 파라미터 수를 줄여 VRAM 요구량을 \(O(P)\)적으로 감소시킵니다.
    • Big O: \(P\)가 입력 \(N\)에 직접적인 함수는 아니지만, 모델 자체가 소비하는 공간의 “상수 인자”를 줄이는 가장 직접적인 방법입니다.
    • 의미: 개인 PC나 VRAM이 제한된 서버에서 더 작은 모델을 로드할 수 있게 합니다. 이는 추론 속도에도 긍정적인 영향을 미칩니다 (작은 모델은 연산량이 적으므로).
양자화 (Quantization): \(O(P)\)의 상수 인자 감소
  • 예시: GGUF (llama.cpp) 형식의 Q4_K_M, Q8_0 등 다양한 양자화 레벨 모델
  • 분석: 가중치의 정밀도를 FP16에서 INT8, INT4 등으로 낮춰, 동일한 파라미터 수라도 모델 크기를 2배, 4배 이상 줄입니다.
    • Big O: 모델 로드 시 필요한 VRAM/RAM 크기를 \(O(P)\) 스케일 내에서 크게 줄입니다. 4비트 양자화는 16비트 대비 1/4의 메모리만 필요합니다.
    • 의미: 제한된 VRAM에서도 더 큰 모델(원래는 FP16)을 로드할 수 있게 하거나, 동일한 모델로 더 큰 배치 사이즈를 처리하거나 더 긴 컨텍스트를 유지할 수 있게 합니다.
효율적인 아키텍처 (Long Context Optimization): \(O(N_{token}^2)\)의 상수 인자 또는 차수 감소
  • 예시: Mistral, Mixtral (MoE), RWKV, Long-RoPE, FlashAttention 등
  • 분석:
    • Mixtral (MoE): 모델 자체는 크지만, 특정 토큰에 대해 활성화되는 파라미터 수가 적어(Sparse Activation), 실제 추론 시의 연산량을 줄입니다.
      • \(Big O (Time)\): \(O(N_{token}^2)\)는 여전히 존재하지만, \(O(P_{active})\)와 같이 활성화되는 파라미터 수에 비례하여 연산 상수 인자를 줄입니다.
      • \(Big O (Space)\): 모델 전체는 크지만, 특정 시점에 메모리에 로드되는 활성화 값은 줄일 수 있습니다. 하지만 전체 가중치 로드는 여전히 \(O(P_{total})\)이므로 VRAM 부담은 여전합니다.
    • Long-RoPE, ALiBi 등 Positional Encoding 개선: Long Context를 효율적으로 처리하기 위한 위치 임베딩 개선 기법입니다.
      • \(Big O (Time/Space)\): \(N_{token}\)이 매우 길어질 때 \(O(N_{token}^2)\)의 시간 복잡도와 K/V 캐시의 \(O(N_{token})\) 공간 복잡도를 비교적 더 잘 관리할 수 있도록 돕습니다. Big O 자체를 바꾸기보다는, \(N_{token}\)의 상한선을 늘려 실용적인 사용 가능성을 높입니다.
    • FlashAttention (GPU 최적화): Self-Attention 연산을 GPU에 최적화하여 구현함으로써, VRAM 접근 패턴을 개선하고 중간 결과를 DRAM에 저장하지 않아 VRAM 사용량을 줄입니다.
      • \(Big O (Time)\): \(O(N_{token}^2)\)의 본질적인 복잡도는 동일하지만, ‘실제 실행 상수 시간’을 대폭 감소시켜 더 빠른 추론이 가능하게 합니다.
      • \(Big O (Space)\): \(O(N_{token})\)으로 공간 복잡도를 줄여, 더 긴 컨텍스트를 처리할 수 있게 합니다.
스트리밍/오프로딩 기법 (메모리 활용): \(O(P)\)의 유연한 관리
  • 예시: llama.cpp (CPU 오프로딩, GGML/GGUF), vLLM (PagedAttention)
  • 분석:
    • CPU 오프로딩: GPU VRAM이 부족할 때 모델 가중치의 일부를 PC(서버) RAM으로 옮겨 로드합니다.
      • \(Big O (Space)\): 모델의 총 \(O(P)\) 가중치를 GPU VRAM과 PC RAM에 분산하여 로드하여, 단일 VRAM 용량의 한계를 극복합니다.
      • \(Big O (Time)\): GPU-RAM 간 데이터 전송이 발생하므로 추론 시간의 ‘상수 인자’를 증가시키고, \(O(N_{token})\) 또는 \(O(N_{token}^2)\) 연산에 병목을 유발할 수 있습니다.
    • PagedAttention (vLLM): K/V 캐시 메모리를 페이지 단위로 관리하여, 불필요한 메모리 할당을 줄이고 메모리 단편화를 방지합니다.
      • \(Big O (Space)\): K/V 캐시의 \(O((N_{input}+N_{output})×Batch \space Size)\)공간 복잡도를 더 효율적으로 관리하여, 동일한 VRAM에서 더 많은 동시 요청이나 더 긴 컨텍스트를 처리할 수 있도록 합니다.
요약

개인 PC나 조직 내 서버에 SLM을 배포할 때는, 단순히 모델의 파라미터 크기(P)만 볼 것이 아니라, \(N_{token}\)에 대한 시간 복잡도(\(O(N_{token}^2)\)의 존재 여부 및 상수)와 VRAM/RAM에 대한 공간 복잡도(\(O(P)\) 모델 가중치, \(O(N_{token})\) K/V 캐시, \(O(N_{token}^2)\) 활성화 값)를 종합적으로 분석해야 합니다.

최근 Open SLM 모델들은 파라미터 수를 줄이거나, 양자화를 적용하여 \(O(P)\)의 상수 인자를 줄이고, Long Context 최적화나 FlashAttention을 통해 \(O(N_{token}^2)\)의 시간 복잡도와 \(O(N_{token})\) 공간 복잡도의 효율성을 개선하려는 노력을 하고 있습니다.

따라서, SLM 모델을 평가할 때는:

  1. 모델 파라미터 수를 통해 기본적인 \(O(P)\) 공간 요구사항을 파악하고,
  2. 양자화 지원 여부를 통해 \(O(P)\) 공간을 얼마나 더 줄일 수 있는지 확인하며,
  3. 아키텍처 최적화(Long-RoPE, FlashAttention 등)를 통해 긴 \(N_{token}\)에 대한 \(O(N_{token}^2)\) 시간 복잡도와 \(O(N_{token})\) K/V 캐시 공간 복잡도가 얼마나 효율적으로 관리되는지, 그리고 실제 GPU 성능(FLOPS)을 얼마나 잘 활용하는지 측정해야 합니다.
  4. CPU 오프로딩 등 배포 기법을 통해 PC/서버의 RAM을 활용하여 \(O(P)\) 공간 부족 문제를 우회할 수 있는지 고려해야 합니다.

이러한 Big O 기반의 분석은 제한된 온프레미스 자원에서 SLM의 최대 성능을 끌어내고, 합리적인 하드웨어 투자를 결정하는 데 결정적인 통찰력을 제공합니다.

.끝.

댓글 남기기

AI Work Flow에서 더 알아보기

지금 구독하여 계속 읽고 전체 아카이브에 액세스하세요.

계속 읽기