LATS-RCA: Tree Search for Microservice Root Cause Analysis

Summary

LATS-RCA는 microservice 장애 분석을 하나의 긴 추론 경로로 처리하지 않고, 여러 root cause 가설을 동시에 유지하는 reflection-guided tree search로 모델링한다.

Incident
   │
   ├── Log Agent
   │     └── Log evidence를 탐색하는 search tree
   │
   ├── Metrics Agent
   │     └── Metric evidence를 탐색하는 search tree
   │
   └── Supervisor
         └── 두 결과의 상관관계를 검토하고 최종 진단

핵심은 더 많은 telemetry를 무조건 수집하는 것이 아니다. 같은 evidence를 두고 여러 설명을 생성하고, 각 설명의 품질을 평가하며, 가능성이 높은 경로에 탐색 예산을 배분한다.

논문은 이 구조가 통제된 LO2 benchmark에서 높은 정확도를 달성했지만, 실제 production에서는 정확도가 낮아지고 비용이 커졌다는 결과도 함께 보여준다. 따라서 LATS-RCA는 “LLM이 RCA를 해결했다”는 결론보다 RCA에서 hypothesis search가 왜 필요한지를 보여주는 연구로 보는 편이 정확하다.

Why Linear RCA Is Not Enough

일반적인 ReAct agent는 다음 과정을 반복한다.

Thought
  → Action
  → Tool
  → Observation
  → Next Thought

Roy et al., Exploring LLM-based Agents for Root Cause Analysis, Figure 2.

이 방식은 새로운 정보를 얻을 때마다 다음 행동을 결정할 수 있다는 장점이 있다. 제공된 Exploring LLM-based Agents for Root Cause Analysis 논문도 ReAct agent에 incident detail과 historical incident retrieval 도구를 연결해 RCA 가능성을 평가했다.

하지만 하나의 경로를 따라가는 linear reasoning에는 문제가 있다.

• 초기에 잘못 선택한 가설이 이후 추론을 지배할 수 있다.
• 유사한 증상을 만드는 여러 원인을 충분히 비교하지 못할 수 있다.
• 새로운 evidence가 기존 가설과 모순되어도 이전 단계로 돌아가기 어렵다.
• Log와 metric이 서로 다른 원인을 가리킬 때 하나의 context에서 섞일 수 있다.

예를 들어 API latency 증가가 발생했을 때 가능한 원인은 하나가 아니다.

High latency
   ├── Database connection pool exhaustion
   ├── Upstream API timeout
   ├── CPU throttling
   ├── Retry storm
   └── Bad deployment

LATS-RCA는 이 후보들을 하나의 추론 문장 안에 나열하는 데서 끝나지 않고, 각각을 별도의 탐색 상태로 유지한다.

Architecture

LATS-RCA는 두 diagnostic agent와 하나의 supervisor로 구성된다.

각 agent는 자신에게 할당된 modality만 다룬다. Log Agent는 file listing, content retrieval, pattern search 도구를 사용하고, Metrics Agent는 time-series loading, comparison, visualization 도구를 사용한다.

이 구분은 agent 수를 늘리기 위한 형식적인 분리가 아니다. Log의 원문과 metric time series를 서로 다른 context에 격리해 한쪽의 긴 탐색 과정이 다른 쪽 판단을 오염시키는 것을 줄이려는 설계다.

Diagnostic Search Tree

각 agent의 RCA 과정은 유한한 sequential decision process로 표현된다.

State
  = observations
  + active hypotheses
  + collected evidence
  + service dependencies
  + current search depth

Action
  = reasoning step
  or tool invocation

Search tree에서 node는 현재 diagnostic state, edge는 다음 investigative action을 나타낸다.

Naakka, Wang, Mäntylä, LATS-RCA, Figure 1.

Initial incident
   ├── Hypothesis A: database issue
   │      ├── Query DB error logs
   │      └── Compare connection metrics
   │
   ├── Hypothesis B: upstream timeout
   │      ├── Search timeout pattern
   │      └── Compare dependency latency
   │
   └── Hypothesis C: resource exhaustion
          ├── Inspect CPU throttling
          └── Inspect memory pressure

한 번의 search iteration은 네 단계로 진행된다.

Selection

이미 방문한 결과와 아직 충분히 조사하지 않은 경로 사이에서 다음 node를 고른다. 이때 Monte Carlo Tree Search에서 사용하는 UCT 개념으로 exploitation과 exploration의 균형을 맞춘다.

High estimated value
  → 이미 유망한 가설을 더 조사

Low visit count
  → 아직 덜 본 가설도 탐색

Expansion

선택된 leaf node에서 여러 candidate action을 생성한다. 논문 구현은 한 번에 다섯 개의 action을 sampling하고, 중복을 제외하면 보통 2~3개의 서로 다른 다음 행동이 생긴다고 설명한다.

Reflection

각 candidate는 LLM reflection module로 평가된다.

각 항목은 0~10점으로 평가되고 정규화된 reflection score가 된다. 여기에 여러 sampling에서 비슷한 tool action이 반복됐는지를 나타내는 self-consistency를 결합해 reward를 계산한다.

Backpropagation

계산된 reward를 현재 node에서 root 방향으로 전파한다. 이후 iteration은 누적된 평가를 이용해 더 유망한 diagnostic path에 탐색 예산을 배정한다.

Search는 다음 조건 중 하나를 만족하면 종료된다.

• Candidate solution이 충분히 확인됨
• 최대 depth에 도달함
• 정해진 iteration budget을 소진함

Cross-Modal Handoff

Log Agent가 항상 Metrics Agent를 호출하는 것은 아니다. Log Agent의 terminal reflection score나 diagnostic completeness가 기준보다 낮을 때 supervisor가 metric 분석으로 escalation한다.

Log Agent result
   │
   ├── Sufficient evidence
   │      └── Final correlation으로 진행
   │
   └── Weak or incomplete evidence
          └── Metrics Agent에 summary 전달

전달되는 것은 전체 search tree가 아니라 다음과 같은 압축 정보다.

• 핵심 조사 결과
• Reflection score
• Evidence item 수
• Escalation 여부

Metrics Agent는 Log Agent의 긴 reasoning trajectory를 그대로 받지 않는다. 요약된 evidence만 전달받아 독립적으로 탐색하고, supervisor는 마지막에 두 결과를 비교한다.

상관관계는 다음 네 단계로 구분된다.

Strong correlation
Weak correlation
No correlation
Contradictory

이 결과와 두 agent의 진단 요약을 바탕으로 최종 root cause를 생성한다.

What the ReAct Study Adds

제공된 2024년 ReAct RCA 논문은 LATS-RCA 논문 자체는 아니지만 중요한 배경을 제공한다.

이 연구는 Microsoft production incident dataset에서 ReAct agent가 다음 도구를 사용하는 구조를 평가했다.

• Incident 원문에 대한 question answering
• Historical incident retrieval
• Team-specific knowledge base
• Monitoring database query
• Engineer에게 정보를 요청하는 human interaction

Static dataset 실험에서 ReAct는 강한 retrieval·reasoning baseline과 비슷한 수준의 성능을 보이면서 factual error를 줄였다. 반면 historical incident의 discussion comment를 추가하는 것만으로는 유의미한 개선이 나타나지 않았다.

이 결과가 주는 중요한 교훈은 다음과 같다.

RCA agent의 성능은 prompt 길이보다 실제 diagnostic service에 접근할 수 있는 tool과 evidence에 더 크게 좌우될 수 있다.

LATS-RCA는 여기서 한 단계 더 나아가, tool을 사용하는 linear ReAct loop를 여러 가설을 비교하는 tree search로 확장한다.

Evaluation

LO2 Benchmark

LO2는 OAuth 2.0 protocol을 구현한 7개 microservice와 MySQL database로 구성된다. 평가에 사용된 sample은 53개 failure type에 걸친 100개 anomaly case를 포함한다.

논문은 동일한 log·metric 도구를 사용하는 single-agent ReAct와 sequential multi-agent ReAct를 baseline으로 구성했다.

이 수치는 LATS-RCA가 동일한 조건의 linear baseline보다 높은 정확도를 보였다는 의미다. 다른 dataset이나 서로 다른 RCA task의 결과와 직접 비교할 수 있는 보편적인 정확도는 아니다.

Why Accuracy Improved

LATS-RCA는 한 incident에서 평균 18.9개의 가설을 탐색했다. Single-agent ReAct는 5.1개, multi-agent ReAct는 8.5개였다.

Naakka, Wang, Mäntylä, LATS-RCA, Figure 2.

반면 선택된 evidence item 수는 세 방법 모두 약 7개로 비슷했다.

Similar evidence amount
        +
Broader hypothesis exploration
        +
Reflection-guided selection
        =
Higher benchmark accuracy

즉 정확도 향상은 단순히 telemetry를 더 많이 읽었기 때문이 아니라, 같은 evidence를 여러 설명과 대조했기 때문이라는 것이 논문의 해석이다.

Ablation

가장 큰 하락은 candidate batching을 제거했을 때 발생했다. 이 실험에서는 여러 가설을 동시에 유지하는 구조가 가장 큰 기여를 했고, backpropagation과 reflection도 각각 추가적인 효과를 보였다.

Cost and Production Gap

높은 benchmark 정확도에는 명확한 비용이 있었다.

• Single-agent ReAct보다 약 3.8배 많은 token
• Multi-agent ReAct보다 약 2.1배 많은 token
• 평균 53.1회 API call
• Incident당 평균 9.1분

Production 평가는 더 현실적인 한계를 보여준다. 연구진은 유럽에서 30만 개 이상의 website를 서비스하는 production microservice 환경에서 6개월간 수집한 37개 incident를 평가했다.

Production 정확도는 여러 실행에서 62~70% 범위였고 평균은 65.1%였다. 논문은 다음 원인을 지적한다.

• 하나의 incident에 여러 원인이 동시에 작용함
• Service dependency와 telemetry 규모가 커짐
• Service마다 log 형식과 metric 이름이 다름
• 일부 metric과 dependency가 관측되지 않음
• Single-label exact match가 부분적으로 맞는 진단을 표현하지 못함

따라서 LO2의 91.3%만 떼어내 실제 운영 정확도로 해석하면 안 된다.

Applying the Idea

실제 환경에서 비슷한 RCA system을 설계한다면 tree search보다 먼저 다음 기반을 준비해야 한다.

Normalized logs
Prometheus metrics
Service ownership
Dependency information
Incident time window
Safe read-only diagnostic tools

Agent에게 직접적인 remediation 권한을 주기 전에는 조사와 실행을 분리하는 것이 안전하다.

Agent
  → Evidence collection
  → Hypothesis ranking
  → Diagnostic report

Engineer
  → Evidence verification
  → Remediation approval

또한 search budget을 incident severity에 따라 조절할 수 있다.

• 낮은 severity: Linear ReAct 또는 제한된 hypothesis 수
• 높은 severity: 더 넓은 tree search와 cross-modal validation
• 불완전한 observability: 자동 결론 대신 추가 계측 요청

Key Takeaways

• LATS-RCA는 RCA를 하나의 reasoning chain이 아니라 여러 root cause 가설의 tree search로 다룬다.
• Log Agent와 Metrics Agent는 독립적인 search tree를 사용하고 supervisor가 결과를 연결한다.
• Reflection은 evidence quality, completeness, consistency를 기준으로 다음 탐색을 평가한다.
• LO2에서는 91.3% accuracy를 기록했지만 평균 156K token과 9.1분이 필요했다.
• Production에서는 평균 accuracy가 65.1%로 낮아지고 비용은 220K token과 13분으로 증가했다.
• 실제 적용의 핵심은 agent 수보다 observability 품질, 안전한 tool, search budget과 human verification이다.

Review Questions

1. Linear ReAct reasoning이 초기의 잘못된 가설에서 벗어나기 어려운 이유는 무엇인가?
2. UCT는 이미 유망한 가설과 아직 덜 탐색한 가설 사이에서 어떤 역할을 하는가?
3. LATS-RCA의 accuracy 향상이 evidence 수 증가만으로 설명되지 않는 이유는 무엇인가?
4. Supervisor가 전체 search tree 대신 요약만 전달하는 이유는 무엇인가?
5. LO2와 production의 accuracy를 동일한 의미로 해석하면 안 되는 이유는 무엇인가?

References

• LATS-RCA: Language Agent Tree Search for Root Cause Analysis in Microservices
• LATS-RCA Replication Package
• Exploring LLM-based Agents for Root Cause Analysis
• Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models