Authors: Zhou, et al.
LATS combines Monte Carlo Tree Search (MCTS) with LLMs to enable systematic exploration of solution spaces. By using LLMs for node expansion and reflection-based evaluation, LATS finds optimal solutions to complex reasoning tasks through intelligent search rather than greedy generation.
Awareness implements LATS for complex planning:
**1. Selection (UCB1)** ``` UCB1 = (Q/N) + C × √(ln(Parent_N) / N) ``` - Q: total value accumulated - N: visit count - C: exploration weight (default 1.41 = √2) - Balances trying promising paths vs exploring new ones
**2. Expansion** - LLM generates 3 candidate actions (branching factor) - Each action becomes a child node - Actions are contextually appropriate next steps
**3. Simulation** - ReAct-style rollout from new node - Execute actions and observe results - Limited to max steps (default 20)
**4. Evaluation (Reflection)** - LLM reflects: "Is this a good solution?" - Scores trajectory 0.0-1.0 - Compare to solution threshold (default 0.8)
**5. Backpropagation** - Update all ancestor nodes with result - Propagate best values upward - Inform future selection decisions
// LATS implementation in Awareness
async function planWithLATS(problem: string): Promise<Solution> {
const tree = new MCTSTree(problem);
for (let i = 0; i < maxIterations; i++) {
// Phase 1: Select best node using UCB1
const node = tree.select();
// Phase 2: Expand with LLM-generated actions
const actions = await llm.generateActions({
state: node.state,
branchingFactor: 3
});
for (const action of actions) {
tree.expand(node, action);
}
// Phase 3: Simulate from new node
const trajectory = await simulate(node);
// Phase 4: Evaluate with reflection
const value = await llm.reflect({
prompt: "Rate this solution (0-1)",
trajectory
});
// Phase 5: Backpropagate value
tree.backpropagate(node, value);
if (value >= solutionThreshold) break;
}
return tree.getBestPath();
}Planning algorithm implementation for complex multi-step reasoning