One post tagged with "multi-step-planning"

Welcome to the fifth installment of our deep-dive engineering breakdown of Stanford University's CS329A: Self-Improving AI Agents (Autumn 2025).

In Lecture 4, we witnessed how agents step outside their closed rooms to interact with external tools and debug code via compiler feedback loops. However, fixing local syntax bugs or querying an API is a far cry from architecting a complex 100,000-line distributed software system or resolving long-horizon scientific problems.

Standard ReAct and Chain-of-Thought approaches are fundamentally greedy, single-path searchers: they inspect the immediate next step and march forward irreversibly. Like an amateur chess player who only evaluates the next move and falls into a checkmate three turns later, a greedy language model that commits to a suboptimal early derivation becomes hopelessly trapped in a dead end, unable to recover.

Today's Lecture 5 serves as the grand finale of Part 1 (Foundation) of the Stanford curriculum: Multi-Step Planning and Tree Search.

By transplanting the mathematical engine of DeepMind's AlphaGo—Monte Carlo Tree Search (MCTS)—into autoregressive language models, we transform reactive text predictors into strategic chess grandmasters. We explore systems that anticipate consequences dozens of steps ahead, dynamically prune dead ends, backtrack across history branches, and parallelize reasoning pipelines:

1. Unifying Reasoning, Acting, and Planning: Language Agent Tree Search (LATS, Zhou et al., 2023).
2. As-Needed Recursive Decomposition: Breaking down complex objectives only upon failure via ADaPT (Allen AI, 2023).
3. Parallel Dependency DAG Packing: Slashing multi-step inference latency by 53.5% via SPRINT (Stanford Future Data, 2025).
4. Adaptive Branching via Thompson Sampling: Solving the Wider vs. Deeper dilemma with AB-MCTS (Sakana AI, 2025).
5. Internalizing Planning into Synaptic Weights: SWiRL (Step-Wise RL, 2025).

flowchart TD
    subgraph MCTS_Loop ["The LATS Language Agent MCTS Engine"]
        direction TB
        Root["Root State: User Goal / PRD"]
        --> Select["1. Selection: Traverse via UCT Metric"]
        --> Expand["2. Expansion: Sample n Candidate Actions"]
        --> Eval["3. Evaluation: Dual LM Score + Self-Consistency"]
        --> Backprop["4. Backpropagation: Propagate Scalar Values Up Tree"]
        --> Reflect["5. Semantic Reflection: Store Linguistic Critique in Memory"]
    end

    subgraph PlanningParadigms ["The Spectrum of Advanced Agentic Planning"]
        direction TB
        P1["LATS (Tree Search)<br/>• Exploits prompt history reversibility for zero-overhead backtracking<br/>• HumanEval: 92.7% Pass@1; HotpotQA: 32% jumps to 71%"]
        --> P2["ADaPT (As-Needed Decomposition)<br/>• Avoids brittle upfront plans; attempts single-shot execution first<br/>• Recursive AND/OR sub-task expansion triggered only on failure"]
        --> P3["SPRINT (Dependency DAG Packing)<br/>• Identifies mutually independent reasoning sub-steps<br/>• Parallelizes execution across GPU clusters; cuts latency by 53.5%"]
        --> P4["SWiRL (Step-Wise RL)<br/>• Internalizes MCTS rollout wisdom directly into model weights<br/>• Single-pass inference with grandmaster strategic foresight"]
    end

    MCTS_Loop ==> PlanningParadigms