Stanford CS329A Part 5 — Planning and Multi-Step Reasoning

Planning in an AI agent is not just writing a list before work begins. The agent chooses an action, observes what happened, and changes its next choice. Stanford CS329A Part 5 is useful because it separates three different engineering problems that are often collapsed into one word: searching over trajectories, exposing dependency-safe parallel work, and learning a better next-action policy.

This page is a teaching companion to the complete 1:14:55 lecture session from October 6, 2025. The front-matter date is this wiki entry’s publication date. The page combines the full manual-caption transcript, 28 inspected visual cues, and the primary papers. This page and its companion deck focus on the three methods substantively covered in the recording: LATS, SPRINT, and SWiRL. ADaPT and Wider or Deeper / AB-MCTS are listed separately as official readings that the video does not develop.

Download the Slides

The Core Idea

An agent trajectory is a feedback loop:

goal + current state
         |
         v
 choose next action
         |
         v
 environment response
         |
         v
 update state and plan
         |
         +----------> repeat until stop

Part 5 provides three levers for improving that loop:

These methods can be combined, but they do not solve the same problem.

1. Planning Means Choosing Under Feedback

A checklist says what should happen in advance. A trajectory records how action and observation change the next decision.

checklist:   A -> B -> C -> D

trajectory: A -> observation
                  |
                  +-> B or repair or stop

This difference matters because multi-step agents change the environment. An early tool error, missing result, or unsafe action can alter every later state.

The engineering question is therefore not only, “Can the model produce a plan?” It is, “How does the system choose and revise actions after evidence arrives?”

2. LATS Searches Over Agent Behavior

Language Agent Tree Search combines language-model reasoning, environment feedback, self-reflection, and an MCTS-style search loop.

The lecture presents a search loop and highlights reflection as an additional LATS mechanism:

selection -> expansion -> evaluation -> simulation
    ^                                      |
    |                                      v
    +---------- backpropagation <----------+

failed or weak trajectory -> textual reflection -> later context

The tree is not only a reasoning tree. Actions produce environment observations, so a branch represents agent behavior.

3. Value Is Estimated, Not Known

LATS uses a UCT-style rule to balance exploitation and exploration. The score may depend on language-model judgment and self-consistency.

LM judgment --------+
                    |
self-consistency ---+--> estimated branch value --> UCT routing

estimated branch value != correctness guarantee

This boundary is critical. UCT can allocate search coherently around a bad estimate. If the judge rewards fluent mistakes, or many samples share one misconception, search can repeatedly expand the wrong region.

Self-consistency measures agreement among samples. It does not establish truth.

4. Search Has a Feasibility Boundary

The lecture explicitly identifies compute cost and irreversible actions as limitations.

Tree search assumes that alternative actions can be evaluated. Real-world side effects make that assumption an engineering and governance problem.

5. SPRINT Finds a Dependency Graph Inside a Trace

SPRINT starts from a simple observation: a reasoning trace is written in token order, but token order is not always dependency order.

linear trace

S1 -> S2 -> S3 -> S4 -> S5 -> S6

dependency structure

       +-> S2 -> S4 -+
S1 ----|             +-> S6
       +-> S3 -> S5 -+

The two middle branches can execute concurrently if neither depends on the other. The longest dependency-constrained chain is the critical path.

Dependency labeling is load-bearing. A false claim of independence can launch an action before its required evidence exists.

6. SPRINT Compiles Demonstrations Into Stages

The training-data pipeline transforms a sequential demonstration:

trace
  -> decompose into steps
  -> label planning versus execution
  -> infer dependency DAG
  -> pack independent work into stages
  -> supervised fine-tuning

This is best understood as a compiler from one representation of reasoning to another. The model is taught to emit plans and groups of independent execution work rather than one undifferentiated chain.

The dependency inference step may use another model. Its errors become training errors.

7. Parallel Execution Needs a Runtime

The base language model remains autoregressive. Parallelism appears because an external runtime interprets the model’s output.

planner emits tagged branches
          |
          +-> executor A --+
          +-> executor B --+-> synchronization barrier
          +-> executor C --+          |
                                      v
                               merged result
                                      |
                                      +-> replan

The runtime must own:

• launch and cancellation;
• timeouts and retries;
• dependency barriers;
• executor failure;
• result merging;
• context returned for replanning.

The method is therefore not only a prompt or a fine-tuned model. It is a model-runtime contract.

8. Critical Path Is Not Total Work

SPRINT reports reductions in sequential tokens for selected long reasoning problems. That metric approximates the critical path. It is not automatically equivalent to lower total tokens or measured latency.

The paper reports up to 39% fewer sequential tokens for long math problems in its setup and larger sequential-token reductions on selected out-of-distribution GPQA and Countdown evaluations. These are benchmark- and system-specific results, not a universal speed guarantee.

Short tasks may become slower because orchestration overhead exceeds the saved critical path.

9. SWiRL Learns at the Step Level

Synthetic Data Generation & Multi-Step RL for Reasoning & Tool Use, referred to as SWiRL in the course, addresses weak intermediate tool decisions.

Its two stages are:

Stage 1: offline collection
  synthetic tool trajectories
      -> process and outcome labels
      -> filtered training data

Stage 2: step-wise RL
  state + stored observation
      -> proposed next action/query
      -> process judgment
      -> policy update

The model does not need to call a live tool during every RL rollout. Stored responses stabilize training and control cost.

The tradeoff is distribution shift. The current policy or deployment tool may reach states not represented in the stored observations.

10. Process and Outcome Signals Fail Differently

Process feedback asks whether an intermediate action appears sound. Outcome feedback asks whether the final result is correct.

In the reported SWiRL setup, process-only filtering was the strongest filtering choice for the RL stage, while successful complete demonstrations played a different role in supervised fine-tuning. The process labels were themselves model-judged, so this result depends on that judge, the tasks, and the data pipeline.

11. Choose the Bottleneck Before the Method

Use this diagnostic:

uncertain trajectory?
  -> search, if evaluation and reversibility are adequate

independent subproblems?
  -> parallelize, if dependencies and runtime are reliable

weak next-action policy?
  -> step-wise learning, if process feedback is trustworthy

unsafe actions or weak verifier?
  -> no added autonomy yet

“No added autonomy yet” is not a failure. It is the correct engineering choice when the system cannot evaluate candidate behavior or reverse harmful actions.

The Lecture in 12 Teaching Moves

Teaching Questions

1. What changes between a checklist and an agent trajectory?
2. Which LATS operations require a model, and which require an environment?
3. Why can UCT allocate search well while the final choice remains wrong?
4. What makes an action unsuitable for speculative search?
5. Why is token order different from dependency order?
6. Which component creates concurrency in SPRINT?
7. What does a sequential-token reduction fail to measure?
8. What does the SWiRL process judge score during step-wise RL?
9. Give one outcome false positive and one process false positive.
10. When is “no added autonomy” the strongest design decision?

Homework: Audit a University Research Agent

Choose a task such as creating a literature comparison, checking student code, or assembling evidence for a course policy.

Produce the following:

Defend the decision using expected quality, total work, latency, evaluator reliability, and reversibility. State what evidence would cause you to reverse it.

Official Reading Set

Substantively taught in the recording and deck

1. Andy Zhou et al., Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models, arXiv:2310.04406.
2. Emil Biju et al., SPRINT: Enabling Interleaved Planning and Parallelized Execution in Reasoning Models, arXiv:2506.05745.
3. Anna Goldie et al., Synthetic Data Generation & Multi-Step RL for Reasoning & Tool Use, arXiv:2504.04736.

Official assigned readings not substantively taught in this recording

1. Archiki Prasad et al., ADaPT: As-Needed Decomposition and Planning with Language Models, arXiv:2311.05772.
2. Yuichi Inoue et al., Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search, arXiv:2503.04412.

ADaPT and Wider or Deeper provide useful surrounding context. They are not presented here as methods taught by this video or explained by the 12-slide deck.

Source Versus Teaching Synthesis

Directly sourced from the lecture and the three taught papers:

• the LATS search loop, UCT-style allocation, reflection, and limitations;
• SPRINT trace decomposition, dependency staging, orchestrated execution, and reported sequential-token results;
• SWiRL offline trajectory collection, process/outcome filtering, step-wise RL, transfer, and scaling observations.

Teaching synthesis in this page:

• the three-lever comparison;
• the phrase “planning is choosing a trajectory, not writing a list”;
• the bottleneck diagnostic;
• university classroom and research examples;
• the homework and “no added autonomy yet” decision branch.

Related Reading

• Stanford CS329A — Self-Improving AI Agents: Public Lecture Learning Path
• Stanford CS329A Part 4 — Learning from Feedback with Tools and Code
• Stanford CS329A Part 6 — Train-Time Scaling and Scaling RL
• CS329A Agent-System Literacy — The Next Layer of AI Education
• Harness / Loop / Graph Engineering — Environment, Feedback, Flow
• Stanford CS329A Part 2 — Test-Time Compute Scaling