고전 캐시 정책의 실패와 의미 기반 검색 버퍼를 위한 학습 보강 교체 기법

LLM 에이전트가 장기 기억을 위해 검색 버퍼를 활용할 때 어떤 항목을 저장하고 버릴지 결정하는 정책은 실사용 성능에 직결되는 운영 문제이다. 이 논문은 의미 유사도 기반 검색 환경에서 전통적 캐시 휴리스틱들이 시간적 지역성이나 빈도 집중 가정을 충족하지 못해 오히려 성능을 저해함을 밝혔다. SOLAR은 삽입 빈도를 엄격히 제어하고 베이지안 후험을 이용해 퇴거를 판단함으로써 제한된 버퍼 용량에서 실질적 품질 향상을 확보했다.

문제의 출발점은 의미 기반 검색에서 '히트'가 이진 신호가 아니라 연속적 품질 지표라는 사실이다. 임베딩 유사도로 항목을 매칭하므로 단일 항목의 부분적 유사성으로도 질의가 부분 해결될 수 있고, 항목의 유용성은 시간에 따라 변화하여 과거의 접근 빈도나 최근 조회만으로 미래 가치를 예측하기 어렵다. 전통적 LRU/LFU는 이러한 연속성과 비정상성을 반영하지 못해 오히려 오판을 일으킨다. SOLAR의 해결 원리는 두 가지 의사결정으로 분해되는 점에 있다. 첫째, 언제 캐시를 수정할지 판단하는 문제는 교체 비용과 축적된 미스 비용의 비교로 환원되며 이를 누적 후회(cumulative regret)를 기준으로 임계값 검출로 처리하면 불필요한 교체를 줄일 수 있다. 둘째, 어떤 항목을 넣고 뺄지는 관측이 불완전한 상황에서 탐험과 활용의 균형을 요구하므로 베이지안 후험을 유지하고 톰슨 샘플링으로 샘플링된 점수를 기준으로 퇴거를 결정하면 관측 부족 항목을 보존하며 학습 효율이 개선된다. 두 메커니즘의 결합이 핵심적 차별점이다. 선택적 삽입은 캐시로 들어오는 노이즈 항목을 걸러내어 퇴거 후험의 신호대잡음을 높이고, 더 나은 퇴거는 캐시 품질을 유지하여 삽입 임계값을 더욱 엄격하게 만들어 교체 빈도를 추가로 낮춘다. 이 상호 강화 루프는 개별 요소의 단순 합을 초과하는 초가법(super-additive) 이득으로 이어졌다.

전체 접근 방식은 총비용(누적 미스 비용 + λ·교체 횟수)을 최소화하는 온라인 기준에서 출발한다. 실행 시각마다 질의에 대한 검색 품질을 관찰하고 그 손실을 누적하여 임계값을 넘으면 삽입을 허용하는 방식으로 삽입 제어를 수행한다. 임계값은 지수이동평균(EMA)으로 적응하며 관측된 손실률에 따라 갱신되어 비정상성에 대응한다. 삽입이 허용되고 캐시가 가득 찬 경우 각 항목에 대해 Beta(α,β) 후험을 유지하고 톰슨 샘플링으로 각 항목의 유틸리티 샘플을 추출한다. 여기에 연령 기반의 신선도 보너스를 더한 점수를 계산하여 최저 점수 항목을 퇴거 대상으로 선택한다. 미관측 항목은 시간 경과에 따라 β를 증가시키는 감쇠 기작으로 서서히 확률을 낮춰 비정상성에 적응한다. 복잡도와 구현 세부는 실시간 제약을 고려해 설계되었다. 임계값 누적과 관측 업데이트는 O(1) 또는 O(k) 비용이고, 교체가 발생할 때만 K개의 Beta 샘플링이 필요하므로 평균적으로는 O(K) 가산 비용으로 수렴한다. 실측으로는 K=100, d=384 환경에서 정책 계산 오버헤드가 1ms 미만으로 측정되어 LLM 추론 비용에 비해 무시할 수준이었다.

주요 벤치마크 결과에서 SOLAR는 제한된 캐시(K ≤ 50) 환경에서 FIFO 대비 5–75%의 상대 성능 향상을 기록했다. 구체적으로 LoCoMo에서 K=10일 때 상대 개선이 +22.7%였고, K=50에서는 절대 F1 +0.014를 확보했다. DialSim 같은 신호 희박 환경에서는 작은 K에서 상대 이득이 더욱 커져 K=10에서 약 +75% 상대 개선을 보였다. 구성요소 별 실험에서 삽입 제어가 퇴거보다 더 큰 기여를 했고, 두 구성요소를 결합했을 때의 총 이득이 개별 효과의 합을 초과하는 초가법적 시너지가 관찰되었다. 예컨대 K=50에서 삽입만의 효과가 +0.007, 퇴거만의 효과가 +0.003인 반면 결합 효과는 +0.014로서 약 40%의 추가 이득이 발생했다. 합성 실험에서는 FIFO의 쓰레싱(cycling) 현상이 재현되어 작업집합 비율이 1을 넘으면 FIFO의 적중률이 0%로 붕괴하는 것을 확인했다. 또한 후보 풀 크기 변화를 탐색한 실험에서는 풀 크기에 따른 역 U자(hit rate peak around K≈1000) 특성이 나타나 검색 잡음이 용량 제약의 원인임을 실험적으로 확인했다.

전체 아키텍처는 두 모듈로 구성된다: 누적 손실 기반의 삽입 게이트와 베이지안 후험 기반의 퇴거 모듈이다. 삽입 게이트는 시간 t에서 관찰된 누적 손실 c= \sum_{s=t-Δ}^{t}δ_s 를 유지하고 c≥τ 일 때만 삽입을 허용한다. 여기서 δ_s는 해당 시점의 1−retrieval_quality이며 τ는 EMA로 적응되는 임계값이다. 임계값 수식의 핵심은 τ^=\sqrt{2λ/L} 이다. 식(1) τ^=\sqrt{2λ/L}에서 τ^는 최적 임계값, λ는 교체당 페널티, L은 평균 손실률을 의미한다. 계산 흐름은 관측된 단계별 손실 δ_t를 EMA로 갱신하여 L을 추정하고 그로부터 τ_t를 갱신하여 삽입 여부를 결정하는 방식이다. 예를 들어 λ=0.5, 관측 평균 손실 L≈0.02이면 τ^≈\sqrt{2·0.5/0.02}≈\sqrt{50}≈7.07으로, 누적 손실이 약 7을 넘을 때 삽입을 허용하는 기준으로 동작한다. 해석하면 교체 비용이 클수록 더 큰 누적 손실이 쌓여야 교체가 정당화되며, 관측 손실률이 커질수록 임계값은 작아져 교체 빈도가 증가한다. 퇴거 메커니즘의 수학적 기반은 Beta-Bernoulli 베이지안 모델과 톰슨 샘플링에 있다. 각 항목 i는 Beta(α_i,β_i)의 후험을 가지며, 항목이 top-k에 반환되면 α_i를 증가시키고, 비관측 기간에는 β_i를 작게 증가시켜 감쇠를 구현한다. 시간 t에 각 항목에서 μ_i∼Beta(α_i,β_i)를 샘플링하고 연령 기반 보너스 b_i를 더한 s_i=μ_i+b_i로 점수를 계산해 최소 점수 항목을 퇴거한다. 이 절차는 탐험-활용 균형을 자연스럽게 확보하며 비관측 항목의 지나친 고정화를 방지한다. 이론적 분석은 두 축으로 구성된다. 삽입 임계값을 고정했을 때 각 에폭(epoch)은 최대 τ+λ의 비용을 초래하므로 적절한 τ 선택으로 경쟁비 CR≤3을 보장했다. 퇴거 측면은 톰슨 샘플링의 표준 분석을 변형하여 R_T=O(√{K T log T}) 후회 상계를 확보했으며 이는 하한 Ω(√{K T})에 로그 인자 차이로 근접한다.

증명에서 사용한 유효성 조건들 중 하나는 'bounded stale advantage'라는 가정으로, 이 가정은 OPT가 고정 캐시를 유지한 구간에서 SOLAR와의 누적 손실 차이가 제한적일 때 성립한다. 퇴거 분석은 근정적(stationary) 모델이나 슬라이딩 윈도우 상황에서의 적용성을 전제로 하며, 극단적으로 빠르게 변하는 비정상성 환경에서는 로그 인자나 윈도우 크기 의존성이 달라질 수 있다. 또한 논문은 임베딩 품질과 임베더 선택에 의해 실험 결과가 민감하게 좌우될 수 있음을 인정하고 있어 실제 배포에서는 임베더와 파라미터 튜닝이 필요하다.