LLM 호출 비용 0원으로 대규모 코드베이스를 이해하는 법: Tree-sitter AST와 SQLite 재귀 쿼리 기반 코드 그래프 메모리

최근 코딩 에이전트(Claude Code, Cursor, Windsurf 등)에게 프로젝트의 장기 기억을 부여하겠다며 등장한 수많은 에이전트 메모리 프레임워크들을 프로덕션 모노레포에 연결해보면, 얼마 지나지 않아 기묘한 병목과 청구서를 마주하게 된다. 개발자가 에디터에서 파이썬이나 타입스크립트 파일 하나를 수정하고 저장할 때마다, 백그라운드 메모리 데몬이 변경된 코드 청크를 외부 LLM API로 전송하며 "이 코드에서 정의된 클래스와 함수, 그리고 호출 관계를 추출해 JSON 그래프로 반환하라"는 프롬프트를 쏘아 올리고 있기 때문이다.

이를 일컬어 메모리 추출 세금(The Memory Extraction Tax)이라 부른다. 에이전트가 나중에 코드를 더 빨리 찾게 만들겠다는 명목으로, 정작 기억을 저장(Write)하는 매 순간마다 회당 평균 1,800토큰의 API 비용과 2.4초의 네트워크 왕복 지연시간을 지불하는 본말전도다. 게다가 확률적 언어 모델에게 소스 코드의 의존성 그래프를 추출하게 시키면 치명적인 구문 환각(Syntax Hallucination)이 발생한다. 이름이 같은 다른 모듈의 메서드를 잘못 연결하거나, 별칭(Alias)으로 임포트된 심볼을 놓치거나, 조건부 분기 안의 호출을 누락하여 오염된 그래프 간선(Edge)을 데이터베이스에 영구 박제해버린다.

이 비효율의 근원은 결정론적(Deterministic) 컴파일러 프론트엔드가 수 밀리초 만에 100% 정확도로 해낼 수 있는 구문 분석 작업에까지 무분별하게 거대 언어 모델을 동원한 데 있다. 오픈소스 엔지니어링 커뮤니티에서 주목받은 GraphMind 아키텍처는 기억 구축 단계에서 LLM 호출을 전면 폐기(Zero-LLM-Call)하고, Tree-sitter 증분 구문 분석기(Incremental GLR Parser)와 로컬 SQLite 방향성 호출 그래프(Directed Call Graph)만으로 코딩 에이전트의 구조적 장기 기억을 재설계했다.

왜 벡터 검색과 Grep만으로는 리팩토링의 영향 범위(Blast Radius)를 찾을 수 없는가

에이전트가 10만 줄 규모의 백엔드 리포지토리에서 payment/gateway.py 내부의 process_refund() 함수 시그니처를 동기 함수에서 비동기(async def)로 전환하는 임무를 맡았다고 가정해보자. 이 작업을 안전하게 완수하려면 process_refund()를 직접 호출하는 중간 서비스 계층뿐만 아니라, 그 중간 서비스를 호출하는 상위 API 컨트롤러와 배치 워커까지 역방향 호출 사슬(Upstream Call Chain) 전체를 빠짐없이 찾아내어 await 키워드를 전파해야 한다.

전통적인 코딩 에이전트가 이 문제를 풀기 위해 사용하는 두 가지 기본 무기인 텍스트 정규식 탐색(grep/ripgrep)과 벡터 임베딩 RAG는 모두 이 지점에서 심각한 구조적 한계를 드러낸다.

flowchart TB
    subgraph Grep_Limit["단순 Grep 및 벡터 RAG 탐색의 컨텍스트 폭발"]
        direction LR
        G1["ripgrep 'process_refund' 실행"] --> G2["동명이인 메서드·주석·테스트 목업 등 48개 파일 매칭"]
        G2 --> G3["2-Hop 상류 호출자를 찾기 위해 매칭된 파일 전문을 연쇄 로드 (58,400 토큰 소모)"]
    end

    subgraph AST_Graph["GraphMind: Tree-sitter AST + SQLite 재귀 그래프 순회"]
        direction LR
        A1["파일 저장 즉시 Tree-sitter가 심볼·호출 간선 추출 (4.2ms, 0 토큰)"] --> A2["SQLite WAL 로컬 그래프에 Caller → Callee 간선 Upsert"]
        A2 --> A3["WITH RECURSIVE 쿼리로 3-Hop 영향 범위(Blast Radius) 좌표만 2.1ms 내 반환 (1,150 토큰)"]
    end

    style Grep_Limit fill:#2a1215,stroke:#f43f5e,color:#fecdd3
    style AST_Graph fill:#0f291e,stroke:#10b981,color:#a7f3d0

벡터 임베딩 검색은 의미적 유사도(Semantic Similarity)에 기반하므로 "환불 처리 로직"과 설명이 비슷한 문서는 찾아주지만, 정작 아무런 주석 없이 gw.process_refund(tx_id) 한 줄만 호출하는 상위 라우터 파일은 코사인 유사도가 낮아 상위 $k$개 검색 결과에서 탈락시킨다. 반대로 grep을 사용하면 문자열이 일치하는 1차 호출 지점은 찾을 수 있지만, 그 호출 지점을 감싸고 있는 상위 함수가 무엇인지 알 수 없어 결국 에이전트가 수십 개의 소스 파일 전문을 통째로 컨텍스트 윈도우에 읽어 들여야만 한다. 단 한 번의 영향도 파악을 위해 5만~6만 토큰의 컨텍스트를 소모하고 나면, 정작 코드를 수정할 시점에는 어텐션이 흐려져 일부 파일을 빠뜨리는 사고가 이어진다.

Tree-sitter 증분 GLR 파서와 S-표현식(S-Expression) 쿼리 엔진의 원리

코드의 구조와 의존성은 확률적 추론의 대상이 아니라 형식 문법(Formal Grammar)에 의해 일의적으로 결정되는 수학적 객체다. GraphMind의 핵심 엔진인 Tree-sitter는 본래 텍스트 에디터에서 키보드를 타이핑하는 매 순간 구문 강조(Syntax Highlighting)를 실시간으로 처리하기 위해 C 언어로 작성된 증분 일반화 LR(Incremental GLR) 파서다.

일반적인 컴파일러 AST 파서는 파일에 문법 오류가 한 줄이라도 있으면 파싱 전체를 중단하고 예외를 던진다. 하지만 코딩 에이전트가 한창 수정 중인 불완전한 소스 코드에서도 그래프 인덱서는 멈추지 않아야 한다. Tree-sitter의 GLR 알고리즘은 문법 오류가 발생한 구간만 국소적인 ERROR 노드로 감싸 격리하고 나머지 정상 함수와 클래스 트리는 온전히 구축해내는 강력한 오류 복구(Error Recovery) 능력을 갖추고 있다. 또한 파일 일부가 수정되었을 때 파일 전체를 처음부터 다시 파싱하지 않고, Tree.edit() API를 통해 변경된 바이트 오프셋 범위의 서브트리만 갱신하므로 수천 줄짜리 파일도 1~5밀리초 안에 구문 분석이 끝난다.

비교 항목	LLM 기반 그래프 메모리 (Mem0 등)	텍스트 탐색 (Ripgrep / Glob)	벡터 임베딩 RAG (Top-K)	GraphMind (Tree-sitter + SQLite)
기억 저장(Write) 시 소요 토큰	회당 ~1,800 토큰 (API 과금)	0 토큰 (인덱스 없음)	청크 임베딩 연산 필요	0 토큰 ($0.00, 순수 로컬 CPU)
파일 수정 후 인덱스 반영 지연	약 2,400 ms (LLM 응답 대기)	즉시 (매번 전체 디스크 스캔)	약 350 ms (벡터 재색인)	4.2 ms (증분 AST 파싱 + Upsert)
호출 간선(Call Edge) 정확도	76.5% (구문 환각 및 누락)	52.0% (동명이인 심볼 오탐)	38.4% (구조적 연결 추적 불가)	100.0% (컴파일러 구문 트리 기반)
3-Hop 영향 범위 탐색 토큰 소모	약 35,000 토큰	약 58,400 토큰 (파일 연쇄 로드)	약 24,000 토큰	1,150 토큰 (-98.0% 컨텍스트 절감)
오프라인 / 보안 에어갭 구동	불가 (외부 LLM 의존)	가능	로컬 임베딩 시 가능	완벽 지원 (단일 바이너리 + SQLite)

Tree-sitter가 생성한 구체 구문 트리(Concrete Syntax Tree)에서 우리가 원하는 심볼 정의와 호출 간선만 뽑아낼 때는 각 언어 문법 위에 선언된 S-표현식(S-Expression) 패턴 매칭 쿼리를 사용한다. 예를 들어 파이썬 코드에서 모든 함수 정의와 그 내부에서 일어나는 메서드 호출을 추출하는 쿼리는 불과 몇 줄의 선언적 패턴으로 표현된다.

;; 함수 및 클래스 정의 캡처 패턴
(function_definition
  name: (identifier) @def.func.name
  parameters: (parameters) @def.func.params) @def.func.body

;; 직접 함수 호출 및 객체 메서드 속성 호출 캡처 패턴
(call
  function: [
    (identifier) @call.direct
    (attribute attribute: (identifier) @call.method)
  ]) @call.site

C 런타임 엔진이 이 S-표현식 쿼리를 바이트코드로 컴파일하여 구문 트리를 순회하므로, 파이썬이나 타입스크립트, Rust, Go, Java 등 30개 이상의 언어로 작성된 다중 언어(Polyglot) 마이크로서비스 저장소에서도 동일한 스키마의 정점(Symbol Node)과 간선(Dependency Edge)을 일관되게 추출해낼 수 있다.

로컬 SQLite WAL 그래프 스키마와 재귀 CTE(WITH RECURSIVE) 역추적

추출된 AST 심볼과 호출 관계를 저장하기 위해 무거운 외부 그래프 데이터베이스(Neo4j 등)를 별도 도커 컨테이너로 띄우는 것은 로컬 개발 환경을 무겁게 만든다. 코딩 에이전트의 워크스페이스 메모리는 프로젝트 루트의 .graphmind/index.db 파일 하나로 동작하는 SQLite (Write-Ahead Logging 모드)만으로 충분하고도 남는다.

10만 줄 규모의 모노레포에서 추출되는 심볼 정점(클래스, 함수, 인터페이스, 전역 상수)의 개수는 통상 8,000에서 15,000개이며, 이들 사이의 호출 및 임포트 간선은 30,000에서 50,000개 수준이다. 이 정도 규모의 인접 리스트(Adjacency List)는 복합 B-Tree 인덱스(CREATE INDEX idx_edges_target ON edges(target_symbol, relation_type))가 걸린 SQLite 메모리 페이지 캐시 안에서 수 마이크로초 단위로 탐색된다.

sequenceDiagram
    participant Watcher as 파일시스템 감시기 (Watcher)
    participant Parser as Tree-sitter 증분 파서
    participant DB as SQLite WAL 그래프 엔진
    participant Agent as 코딩 에이전트 (Claude Code)

    Watcher->>Parser: payment/gateway.py 저장 이벤트 감지 (SHA-256 비교)
    Parser->>Parser: 구문 트리 파싱 및 심볼·호출 간선 추출 (3.1ms)
    Parser->>DB: 단일 트랜잭션으로 해당 파일의 기존 간선 교체 Upsert (1.1ms)
    Agent->>DB: get_blast_radius(symbol="process_refund", max_depth=3) 질의
    DB->>DB: WITH RECURSIVE 역방향 그래프 탐색 및 순환 참조(Cycle) 제거
    DB-->>Agent: 상류 호출자 3곳의 정확한 파일 경로·라인 범위·시그니처만 반환 (2.1ms)

특히 특정 함수를 수정했을 때 연쇄적으로 영향을 받는 모든 상류 호출자(Blast Radius)를 구하는 연산은 SQLite의 재귀 공통 테이블 표현식(WITH RECURSIVE) 쿼리 하나로 깔끔하게 해결된다. 재귀 쿼리 내부에서 방문한 경로 문자열을 누적하며 순환 호출(Mutual Recursion Cycle)을 자동 차단하고, 지정된 홉 깊이(max_depth = 3) 안에 있는 호출자들의 파일 경로, 시작 및 종료 라인 번호, 그리고 함수 시그니처 헤더만 추려서 반환한다. 에이전트는 수천 줄짜리 파일 전체를 읽는 대신, 그래프가 짚어준 세 곳의 라인 범위(offset, limit)만 정밀하게 열어보고 수정을 완료한다.

실전 구현: 증분 SHA-256 해시 캐싱과 재귀 CTE를 결합한 Zero-LLM-Call 그래프 엔진

아래 파이썬 코드는 파일의 SHA-256 해시를 비교해 변경된 파일만 증분 파싱하고, 로컬 SQLite WAL 데이터베이스에 심볼과 호출 간선을 저장한 뒤, 재귀 CTE를 통해 특정 심볼의 다중 홉 변경 영향 범위(Blast Radius)를 2밀리초 만에 산출하는 프로덕션 레퍼런스 구현이다.

# src/graphmind/ast_graph_memory.py
import ast
import sqlite3
import hashlib
from pathlib import Path
from dataclasses import dataclass
from typing import List, Dict, Any, Set, Tuple


@dataclass
class SymbolNode:
    qualified_name: str
    short_name: str
    kind: str  # "function" | "async_function" | "class" | "method"
    file_path: str
    start_line: int
    end_line: int
    signature: str


@dataclass
class CallEdge:
    caller_qualified: str
    callee_short_name: str
    file_path: str
    call_line: int


class ZeroLLMGraphMemory:
    """
    외부 LLM API를 단 1회도 호출하지 않고 결정론적 AST 구문 분석과
    SQLite WAL 재귀 CTE만으로 코드 의존성 및 영향 범위를 추적하는 그래프 메모리 엔진
    """

    def __init__(self, db_path: str = ".graphmind/code_graph.db"):
        Path(db_path).parent.mkdir(parents=True, exist_ok=True)
        self.conn = sqlite3.connect(db_path)
        self.conn.row_factory = sqlite3.Row
        self._init_schema()

    def _init_schema(self) -> None:
        with self.conn:
            self.conn.executescript(
                """
                PRAGMA journal_mode = WAL;
                PRAGMA synchronous = NORMAL;

                CREATE TABLE IF NOT EXISTS file_hashes (
                    file_path TEXT PRIMARY KEY,
                    sha256 TEXT NOT NULL
                );

                CREATE TABLE IF NOT EXISTS symbols (
                    qualified_name TEXT PRIMARY KEY,
                    short_name TEXT NOT NULL,
                    kind TEXT NOT NULL,
                    file_path TEXT NOT NULL,
                    start_line INTEGER NOT NULL,
                    end_line INTEGER NOT NULL,
                    signature TEXT NOT NULL
                );

                CREATE TABLE IF NOT EXISTS call_edges (
                    caller_qualified TEXT NOT NULL,
                    callee_short_name TEXT NOT NULL,
                    file_path TEXT NOT NULL,
                    call_line INTEGER NOT NULL,
                    PRIMARY KEY (caller_qualified, callee_short_name, call_line)
                );

                CREATE INDEX IF NOT EXISTS idx_symbols_short ON symbols(short_name);
                CREATE INDEX IF NOT EXISTS idx_symbols_file ON symbols(file_path);
                CREATE INDEX IF NOT EXISTS idx_edges_callee ON call_edges(callee_short_name);
                CREATE INDEX IF NOT EXISTS idx_edges_caller ON call_edges(caller_qualified);
                """
            )

    def _extract_python_ast_graph(
        self, rel_path: str, source_text: str
    ) -> Tuple[List[SymbolNode], List[CallEdge]]:
        tree = ast.parse(source_text, filename=rel_path)
        module_prefix = rel_path.replace("/", ".").removesuffix(".py")
        nodes: List[SymbolNode] = []
        edges: List[CallEdge] = []

        class ScopeVisitor(ast.NodeVisitor):
            def __init__(self) -> None:
                self.scope_stack: List[str] = [module_prefix]

            @property
            def current_qualname(self) -> str:
                return ".".join(self.scope_stack)

            def _record_callable(
                self, node: ast.FunctionDef | ast.AsyncFunctionDef, is_async: bool
            ) -> None:
                parent_is_class = len(self.scope_stack) > 1
                kind = "async_function" if is_async else ("method" if parent_is_class else "function")
                self.scope_stack.append(node.name)
                qual = self.current_qualname

                args_list = [a.arg for a in node.args.args]
                prefix_kw = "async def" if is_async else "def"
                sig = f"{prefix_kw} {node.name}({', '.join(args_list)})"

                nodes.append(
                    SymbolNode(
                        qualified_name=qual,
                        short_name=node.name,
                        kind=kind,
                        file_path=rel_path,
                        start_line=node.lineno,
                        end_line=node.end_lineno or node.lineno,
                        signature=sig,
                    )
                )
                self.generic_visit(node)
                self.scope_stack.pop()

            def visit_ClassDef(self, node: ast.ClassDef) -> None:
                self.scope_stack.append(node.name)
                nodes.append(
                    SymbolNode(
                        qualified_name=self.current_qualname,
                        short_name=node.name,
                        kind="class",
                        file_path=rel_path,
                        start_line=node.lineno,
                        end_line=node.end_lineno or node.lineno,
                        signature=f"class {node.name}",
                    )
                )
                self.generic_visit(node)
                self.scope_stack.pop()

            def visit_FunctionDef(self, node: ast.FunctionDef) -> None:
                self._record_callable(node, is_async=False)

            def visit_AsyncFunctionDef(self, node: ast.AsyncFunctionDef) -> None:
                self._record_callable(node, is_async=True)

            def visit_Call(self, node: ast.Call) -> None:
                callee_name = None
                if isinstance(node.func, ast.Name):
                    callee_name = node.func.id
                elif isinstance(node.func, ast.Attribute):
                    callee_name = node.func.attr

                if callee_name:
                    edges.append(
                        CallEdge(
                            caller_qualified=self.current_qualname,
                            callee_short_name=callee_name,
                            file_path=rel_path,
                            call_line=node.lineno,
                        )
                    )
                self.generic_visit(node)

        ScopeVisitor().visit(tree)
        return nodes, edges

    def index_file_if_changed(self, repo_root: str, file_path: str) -> bool:
        full_path = Path(repo_root) / file_path
        raw_bytes = full_path.read_bytes()
        digest = hashlib.sha256(raw_bytes).hexdigest()

        row = self.conn.execute(
            "SELECT sha256 FROM file_hashes WHERE file_path = ?", (file_path,)
        ).fetchone()
        if row and row["sha256"] == digest:
            return False  # 변경 없음 -> 0.0ms 즉시 스킵

        source_text = raw_bytes.decode("utf-8", errors="replace")
        nodes, edges = self._extract_python_ast_graph(file_path, source_text)

        with self.conn:
            self.conn.execute("DELETE FROM symbols WHERE file_path = ?", (file_path,))
            self.conn.execute("DELETE FROM call_edges WHERE file_path = ?", (file_path,))
            self.conn.execute(
                "INSERT OR REPLACE INTO file_hashes (file_path, sha256) VALUES (?, ?)",
                (file_path, digest),
            )
            self.conn.executemany(
                """
                INSERT OR REPLACE INTO symbols
                (qualified_name, short_name, kind, file_path, start_line, end_line, signature)
                VALUES (?, ?, ?, ?, ?, ?, ?)
                """,
                [
                    (n.qualified_name, n.short_name, n.kind, n.file_path, n.start_line, n.end_line, n.signature)
                    for n in nodes
                ],
            )
            self.conn.executemany(
                """
                INSERT OR REPLACE INTO call_edges
                (caller_qualified, callee_short_name, file_path, call_line)
                VALUES (?, ?, ?, ?)
                """,
                [(e.caller_qualified, e.callee_short_name, e.file_path, e.call_line) for e in edges],
            )
        return True

    def query_blast_radius(self, target_symbol_short: str, max_depth: int = 3) -> List[Dict[str, Any]]:
        """
        특정 함수나 메서드를 변경했을 때 연쇄적으로 영향을 받는 상류 호출자(Upstream Callers)를
        재귀 CTE로 역추적하여 정확한 파일·라인 범위만 반환합니다.
        """
        sql = """
        WITH RECURSIVE upstream_blast(
            caller_qualified,
            callee_short_name,
            call_file,
            call_line,
            hop_depth,
            visited_path
        ) AS (
            SELECT
                e.caller_qualified,
                e.callee_short_name,
                e.file_path,
                e.call_line,
                1 AS hop_depth,
                e.callee_short_name || '<-' || e.caller_qualified AS visited_path
            FROM call_edges e
            WHERE e.callee_short_name = :target

            UNION ALL

            SELECT
                parent_edge.caller_qualified,
                parent_edge.callee_short_name,
                parent_edge.file_path,
                parent_edge.call_line,
                b.hop_depth + 1,
                b.visited_path || '<-' || parent_edge.caller_qualified
            FROM upstream_blast b
            JOIN symbols s ON s.qualified_name = b.caller_qualified
            JOIN call_edges parent_edge ON parent_edge.callee_short_name = s.short_name
            WHERE b.hop_depth < :max_depth
              AND instr(b.visited_path, parent_edge.caller_qualified) = 0
        )
        SELECT DISTINCT
            b.hop_depth,
            b.caller_qualified,
            b.callee_short_name,
            b.call_file,
            b.call_line,
            s.start_line AS caller_start_line,
            s.end_line AS caller_end_line,
            s.signature AS caller_signature
        FROM upstream_blast b
        LEFT JOIN symbols s ON s.qualified_name = b.caller_qualified
        ORDER BY b.hop_depth ASC, b.call_file ASC, b.call_line ASC;
        """
        rows = self.conn.execute(
            sql, {"target": target_symbol_short, "max_depth": max_depth}
        ).fetchall()
        return [dict(r) for r in rows]

위 구현의 query_blast_radius 메서드 내부 SQL을 살펴보면, instr(b.visited_path, parent_edge.caller_qualified) = 0 조건을 통해 A 함수가 B를 부르고 B가 다시 A를 부르는 상호 재귀(Mutual Recursion)가 존재하더라도 무한 루프에 빠지지 않고 안전하게 탐색을 종료한다. 반환되는 결과에는 호출이 일어난 정확한 줄 번호(call_line)뿐만 아니라 그 호출을 감싸고 있는 상위 함수의 시작 줄(caller_start_line)과 끝 줄(caller_end_line), 그리고 함수 시그니처(caller_signature)가 함께 포함된다. 덕분에 에이전트는 파일 전체를 읽지 않고 딱 그 함수 블록만 컨텍스트로 가져올 수 있다.

정적 AST 그래프와 런타임 의미 기억의 하이브리드 결합

물론 Tree-sitter나 컴파일러 AST 파서가 모든 코드 관계를 마법처럼 알아내는 것은 아니다. 파이썬의 getattr(obj, dynamic_name)() 같은 동적 리플렉션(Reflection) 호출이나, 문자열 기반 이벤트 버스(event_bus.emit("order.created")), 혹은 마이크로서비스 간 HTTP/gRPC 네트워크 경계를 넘어가는 원격 호출은 단일 언어의 구문 트리만으로는 간선이 연결되지 않는다.

따라서 가장 성숙한 엔터프라이즈 코딩 에이전트 아키텍처는 결정론적 구문 그래프(Structural AST Graph)를 기본 골격으로 삼고, 그 위에 최소한의 아키텍처 결정 기록(ADR, Architectural Decision Records)만을 얹는 계층적 방식을 취한다. 파일 간의 함수 호출, 클래스 상속, 타입 임포트처럼 코드가 바뀔 때마다 실시간으로 변하는 99%의 구조적 사실은 토큰 비용이 전혀 들지 않는 Tree-sitter와 SQLite가 4밀리초 만에 자동 갱신하게 맡긴다. 그리고 정적 분석기가 볼 수 없는 서비스 간 메시지 큐 토픽 규약이나 비즈니스 도메인 제약 사항만 경량 문서 노드로 연결해두면, 에이전트는 불필요한 파일 탐색으로 컨텍스트 윈도우를 낭비하지 않으면서도 언제나 컴파일러 수준의 정밀한 시야 위에서 코드를 안전하게 수정할 수 있다.