LATS (Language Agent Tree Search)

Monte Carlo Tree Search combined with LLM reasoning. Achieved 92.7% pass@1 on HumanEval (SOTA).

Activation

Use for:

• Complex multi-step planning
• Code generation with tests
• Decision-making with feedback loops
• Tasks where environment provides signals (tests, builds, APIs)

Core Algorithm

while not solved and budget > 0:
    1. SELECT:      Pick best node using UCT formula
    2. EXPAND:      Generate N candidate actions
    3. SIMULATE:    Execute actions, get environment feedback
    4. REFLECT:     Self-evaluate trajectory quality
    5. BACKPROPAGATE: Update scores up the tree

Key Components

Selection (UCT Formula)

UCT(node) = exploitation + C * sqrt(ln(N) / n)
          = avg_score    + exploration_bonus

Where:
- C = exploration constant (typically 1.41)
- N = parent visit count
- n = node visit count

Expansion

Generate top-5 candidate actions in parallel using the Task tool.

Reflection Prompt

"Given this trajectory and outcome:
Trajectory: [actions taken]
Result: [success/failure + details]

Rate this approach 1-10 and explain:
1. What worked well?
2. What went wrong?
3. How could it be improved?"

Backpropagation

python
def backpropagate(node, score):
    while node:
        node.visits += 1
        node.total_score += score
        node = node.parent

Integration with OSA

LATS is activated by @master-orchestrator when:

• Task complexity is "complex" or "critical"
• Multiple valid solution paths exist
• Environment provides feedback (tests, builds)
• High accuracy is more important than speed

Cost Consideration

LATS is compute-intensive (5-10x more LLM calls). Reserve for:

• High-value tasks
• When accuracy > cost
• As escalation from simpler methods

Based on ICML 2024 research - arXiv:2310.04406