CMU AI Agents 2026: 5. Planning, Task Decomposition, and Multi-Agent Coordination

0:01 Okay. Yeah, let's go ahead and get started. So, today is going to be about planning and task decomposition. And planning is kind of an interesting topic because it's a little bit of a a moving target. it's about well, we we'll see. It's about like how agents kind of produce a representation of what they plan to do in the future. and it builds on some ideas from chain of thought, for example. but in agentive settings it's more interesting and challenging because the agent is going to reveal some information from the environment that is going to change what it should do. So plan should always be revisable and there's a question of like you know how much should the agent be committing to one course of action which could help make things like understandable and overseeable by a person versus how much should the agent be flexible and be able to deal with things that come up along the way. And we'll see some different points in the design space that that trade off between these. This is going to touch a little bit on multi-agent just because, you know, if you have a plan and you try to carry out parts of it in parallel, that's sort of naturally a multi- aent system. But we'll be getting more into multi- aent and the way that agents communicate with each other in a later lecture.

1:18 But just as a motivating example, let's think about a task which you could ask an agent to carry out now. And you can think about whether you would trust the agent to do this task or do all of this task. But maybe you want maybe you want the agent to do some research on GPUs for a research lab that you're running and you need to compare different configurations from different vendors and but you also have some constraints. You need to check whether they're compatible with the existing cluster that you have and there's some documentation for that and then if things go well the agent should actually buy the the GPUs. So, an agent carrying this out using like a standard React loop, it's probably going to take it like hundreds of steps, right? it's going to need to go to the first vendor, navigate their website, and, you know, find a particular configuration, get some of the details of that and then come back to a wiki which has the constraints and compare the available options against that. And then you need to repeat this process for like some number of other vendors as well. And you know, how do you figure out how many vendors to look at? do you change that up on the fly? At some point, you're going to probably need to compact the context, right? And we've talked about compaction before, but you can think of it as a way of kind of like producing an artifact which summarizes the things that you've done in the past. Planning is going to be a little bit like that. It's going to be an artifact which the model can refer to. But the plan is also going to need to specify what should be done in the future that can help you know inform the agents actions. So somewhere after like hundreds of steps maybe the agent has like searched four different vendors but it hasn't found something that's a great fit. There's only one vendor that meets the specifications but it's going to take 20 weeks for the GPUs to arrive. This is a real example that we ran into a few weeks ago. so now what do you do? Does the agent like go ahead and just buy that? Does it ask a person? Does it look for additional vendors? so the plan, the actions that the agent needs to take probably need to change based on what it comes across in the environment. So there's a few things to notice here. you don't have to carry all of this out linearly, right? There's four different vendors and you could do separate independent investigations on each one and none of the four you know vendor sites that it chose were a particularly good fit. So you need to change and react to this feedback that you get from the environment.

4:05 And at some point along the way there's also probably a good opportunity to ask a person for feedback. is this should I go ahead with this thing that's suboptimal? Should I do something else? And if so, what would be the right thing to do? So, plans and task decomposition will give us a general way to address some of these challenges but with some trade-offs as we'll see. So, one way to think about this particular example is there's some underlying structure of the task that the agent needs to carry out and you can think of this as being sort of like a dependency graph. We'll see this come up in one of the papers we talk about towards the end of the lecture. But vendor A, B, C, and D, the search on each of their sites could be done independently from each other. If you just have some specification of the task, you could carry out each of those in parallel and then you can take the information you get from each of those and check it against the list of specifications that you have. So there's a dependence of doing this compatibility check on the information from the vendors, but each of those vendors does not depend on each other.

5:15 And then after you've done this compatibility check, you would ideally want to do a requisition, right? Maybe you start the task and you think, I'm just going to look at those four vendors, do the compatibility check, then do the requisition. But if none of them actually matches then maybe we need to add in some new subtasks which we could represent as new nodes in say a graph based on some feedback that we got from the environment along the way.

5:40 So this is called replplanning like you have this plan this structured representation of what you want to do and then you make changes to it based on observations from the environment. So yeah, some of the questions that we'll ask today are is planning like having an agent commit to what it intends to do in the future, is that useful? when can it be useful? When might it not be worth the additional cost or the additional kind of rigidity that it places on the agent? What are some ways to represent plans? Is it just text? Is it a structured graph like this? code is also a way that you can represent plans.

6:22 And if you make a plan, when should you change it? Like should you in this example add in another vendor to search? And also like how and when should a person weigh in? So how many of you would be comfortable like having the agent actually like buy GPUs for you? yeah, you probably would ask for input from the person. and you would probably ask towards the end of this right after you've collected more information. But for lower risk tasks, maybe you're okay with the person, you're okay with the agent just carrying out a plan and adapting where you've only signed off on the initial plan or maybe you don't even need to sign off on the plan at all.

7:04 So, how many folks have used planning mode in a in a coding agent? These became Okay. Yeah. So, a number of folks have these became pretty popular I think about about a year ago. and they're they exist in in cursor. I think cursor was maybe one of the first ones. And it's also pretty interesting and fully featured. We'll we'll see a demo of it later on in the lecture. Cloud code and codecs do too. But the idea between all of them is you prompt the agent with a complex task. It produces a natural language description of the steps that it's going to do.

7:41 sometimes after doing some initial kind of nondestructive actions like exploring your codebase or taking other information gathering actions that don't actually change things but just get the information that would be helpful to let you weigh in on whether the plan is good. so the human verifies it or maybe makes some edits to it by editing the plan directly or by giving some you know feedback messages that let the agent update the plan. And then after the plan's confirmed you would do something like click build and then the agent carries it out. And this is also a chance for parallelizing the execution of the plan like using sub aents to carry out individual items in it. And we'll see some research papers later on that show methods for for doing this.

8:32 So why might this be helpful? Does anybody can anybody suggest some reasons that you might want an agent to plan? Any hands? >> Yeah. >> Yeah. Definitely. Yeah, you for tasks where it's hard to trust the agent, the plan can help like build that trust help you know that it's likely to do the right thing.

9:07 >> Yeah. Yeah. So, this is like it's in cloud code, this is actually phrased as a permission mode, right? in the same way that like the agent would either carry out all actions or ask on every action. There's like plan where you carry out the information gathering actions and then you can act more permissively afterwards. >> Yeah, >> maybe the plan out like a lower global cost than like >> Yeah, planning and then executing could have a lower total cost than greedily executing. Yeah, that's true. And that's a big motivation for for planning.

9:47 there's a few ways that could play out. Like one could be maybe these tasks are simpler, these, you know, items in the plan are simpler and so you could have like a weaker agent carry them out. but you need a stronger agent which is more expensive to run to actually generate a good plan. it could also be faster if you can parallelize the agent, you know, the sub agent calls. So it might even if you're using kind of the same size agent for everything maybe you're not spending less compute but maybe it is like more time efficient but also like a plan could potentially avoid the agent make it easier for the agent to not make mistakes that would like send it into you know loops and cause more actions. yeah >> sometimes like when you have class you don't have a very structured how to explain it so you might just learn about all the whatever ideas you have you might structure it out and plan both you agent and yourself >> right yeah so a plan can kind of be like a scratch pad for thinking about how to solve a problem that's shared by the person and the agent together. Yeah, that's right.

11:01 Cool. Yeah, maybe one more. Go ahead. >> A very long task which needs to be divided into multiple subtasks. So like visibly split it into multiple task that structured present itself. >> Yeah, that's right. So having kind of like a structured artifact of what was done and what still needs to be done in the future can help the agent keep track of its progress through the task.

11:34 Yeah. And so like this is also you know that that motivation is kind of similar to the ones that we talked about for like context management. yeah but it's doing it in a human interpretable human editable way. Yeah. Great. These are all great arguments for planning and yeah, I think we I think we covered all of those. Cool. So yeah, so we've gotten at this already, but our working definition for a plan for the sake of this lecture is some representation of what the agent is likely to do in the future. So the actions are the sub goals that it will attempt with any ordering or dependencies between them like you know the dependency edges that we saw in that graph or just kind of like a linear ordering of steps.

12:20 So skills which we talked about last time were about reusable guidance that applies across tasks things that are common for different distinct tasks whereas a plan is just for this particular task. and doesn't deal with generality as much. so plans can be more specific than skills and can be you know tied to a particular repo. for example, so yeah, like we said, a plan is sort of an organization of future work and it's just a proposal, right? the agent may need to deviate from that plan depending on some things that it finds in the environment. So it might need to replan, but that is also the ability to replan is also going to make the agents behavior less predictable or less specifiable by a person. So that'll be a trade-off that we'll we'll deal with a little bit later.

13:21 Yeah. And I like this quote, everybody has a plan until they get punched in the mouth, which was from the boxer Mike Tyson. so it's good to have a plan, but it's also good to adapt your plan your plan on the fly. So we will talk about planning a few different times in this course. So mostly today but in the coding agents lecture I think Graham is going to talk about agent lists which is sort of a structured plan that the the agent will stick to when solving code like when implementing pull requests when solving coding issues. We'll also talk a little bit about multi- aent.

14:01 Well, we'll talk a lot about multi-agent which has connections to planning in one of the interaction lectures. we will talk a lot more about how humans can provide supervision to agents with plans is one mechanism for that in the second interaction lecture and also in the search lecture we'll we'll talk about search applied to multi- aent systems including the the MACU and the the row systems that we'll talk about today. Yeah. Any questions before we get started?

14:34 Okay. So, planning has has a history and the first part of this history is the more recent one. It's from LLMs and chain of thought. So, I think folks should be people have seen chain of thought, right? people are familiar with reasoning models. Quick. Yeah, we'll do just a very very quick recap of those. but chain of thought is kind of exemplified by these two papers that had prompts for even before models were trained to produce chains of thought explicitly. They were, you know, before models were trained to produce chains of thought that the model could condition on to produce an answer, which would be a reasoning model like R1 or 01, people were having models produce chains of thought just by prompting them. and they found that prompting the models to produce chains of thought, made them better at producing answers. And here were some of the prompts that people explored. So this paper from Kojima at all they had a pretty fun table in the paper where they like listed out the prompt that they used and then the accuracy of the model when prompted in that way and they found the most successful one was let's think step by step. U so this kind of became famous for a little bit like let's think step by step is all you need. and you know then models later on were trained to produce chains of thought in a way that was more robust to the prompt. but the basic idea in these works was the chain of thought will provide a way for the model to use extra compute. So it's taking in these tokens in the chain of thought that it produces and that's allowing it to do extra operations before predicting the answer. And it also provides like a scratch pad for the model to refer back to. So for complex problems it's useful to write down some intermediate results that you get and sort of like externalize the process of solving the complex problem. And that's the same kind of motivation that we'll have for agents planning.

16:52 so in these works the model was doing the chain of thought generation and the solution just in one generation pass from the model generating the tokens of the chain of thought one at a time then producing the answer. And we'll also see some planning approaches for agents that look like this. But you could also imagine something like explicitly you know modifying the chain of thought or inspecting the chain of thought and then using that controlled chain of thought as conditioning context for the answer. There's analogies of that for agent planning too.

17:27 And so I think kind of right now for agents we're sort of here like after these you know we're we're sort of like after these two approaches and starting to do work that is like training an agentive system to produce a plan that's also useful for the answer. but that has been more thoroughly explored for reasoning models. with like star and and deepseek being some of the first papers to do that. We will see some papers toward the end of this lecture like Ralph for example that train models to produce a plan that's also useful for producing a verifiable answer.

18:06 So building on kind of the foundation of chain of thought people developed approaches for decomposing complex reasoning problems into subtasks and showing that that could improve performance. So a couple papers that did this, one was called least tomost prompting from iClar a few years ago. And a more recent one that I also think of as being sort of like this is the recursive language models paper. but the idea here is you will have you will call your reasoning model once you will call your LLM once to take a complex problem and decompose it into parts. So for like this paper, the least to most paper was validating on math problems and they have the language model taken a more complex problem and then predict some sub questions from it and the idea is those sub questions will be easier for the language model to solve than the initial problem. So the model can take you can then make successive calls to the language model on the simpler problems and solve each one in turn where some of the calls can also depend on the answers to earlier questions. So like we might first start by solving how long does each trip take and we'll get a solution to that. Each trip takes five minutes and then you'll move on to the next question generated by the language model and as an input to that question you'll also feed in you know the full complex question and the answers to the previous ones. And for the models at the time this was really helpful because the models were not as good at answering questions that involved multiple reasoning steps in one shot. and you also don't need as much context to answer the sub questions in compared to the full question. Right? So maybe to answer this you just need some parts of the initial question and the answers to some of the tasks that you're depending on. So these motivations will be the same for for the agents that we have now. like it's potentially easier for an agent to solve a subtask because it doesn't need all of the context that you need for the full task. if you're you know searching for one particular vendor's GPUs, you don't need to reason about like the information from the other vendors. You can just bring that back and then aggregate it afterwards.

20:46 And another advantage of decomposing a complex task into subp parts is that you can use different models to solve some of the subp parts. Can anybody think of of motivation for for doing this? Why might it be useful to use different models to solve different like types of questions? >> Yeah. That's right. Yeah, you could find or develop a model that's sort of specialized to that particular type.

21:21 we'll see some examples of that. another motivation is what we had earlier that like it might be more efficient. like you may not need a model that's as expensive to run to solve like a simpler question. So a paper that did this was called decompose prompting. The idea was kind of similar to the ones that we just saw where you like take a complex question and you have a decomposition model generate sub questions from it and each of those questions also has a type predicted for it. So they were focused on question answering. So they had different types of questionans answering tasks like one was just general QA like who were born in the year 910 1910 and others involved some relational information about people and their jobs like which movies was this would be a reference back to the answers of previous questions. for which movies was argument number one the producer and that would be predicted as this particular type of QA problem.

22:33 So in this work I think they were using different prompts for a language model to implement these different types of questionans answering models where the model had some few shot examples that made it better at general QA or made it better at this sort of positional QA. But you could also imagine some of these models having access to like specialized knowledge or in a language model context like specialized tools that the others do not. And this paper also had a simple form of programmatic control where you basically like specified an ordering over the subtasks that you would be doing in the future and you allowed passing some information from the answers of one subtask to the next. Like this would refer to this would allow using the answer from a previous subtask as an argument here. and they had a pretty structured representation for this. But just like in the skills lecture, we went from sort of templates to code. You can also imagine going from a kind of structured domain specific language to just generally using code to control this sort of orchestration of subtasks and we'll see that later on when we talk about route.

23:52 Okay. So some brief motivation from kind of the OLM chain of thought side, but I also want to talk about what breaks down when you move to agentive settings that actually need to act in the world. So a chain of thought, reasoning step, it's just producing text, right? it's not making changes in the environment like an agent could. And it's usually not revealing more information either, right? everything that's being generated in the chain of thought kind of came from the language model. we're not using tool calls. and the model can sort of undo you know the reasoning steps by just saying something like never mind and then saying you know the change which then ideally it would be able to condition on. So if we're actually acting in the world we have a lot of challenges. so the agent is going to be taking actions that reveal information like finding out what GPUs are available from a vendor. Actions could fail. So you might have a really great plan, but then it turns out, you know, the thing that you need to carry it out is just not available to you.

25:03 and you can also make like actions that irrevocably change the state of the environment, like deleting all of your files. and those are challenges that don't exist for reasoning models. So there's been a long tradition of work in AI on planning and the plans in classical AI have some important differences from the ways that we use plans to you know describe LLM agents. But kind of a core of classical planning is you have a structured grounded in logic representation of the world.

25:42 You have states which are a set of predicates. So like you know functions that can be true about particular arguments. So this is from like a robotics domain where you have objects which instantiate these X and Y arguments and you have predicates which are true or false about these arguments like an object could be on a table. One object could be on another object Y and so on. And you also have actions that your AI system can take in the world which will update the states.

26:17 So these are also these are basically functions that are applied to two arguments and to be able to represent like changes in states you will define preconditions and effects for each of your action functions. So a precondition is basically like when is it when are you allowed to apply that action. So like you can pick up an object if an object is on a table and there's nothing on top of the object and your robot hand is empty and then after you apply that action then you have a new state which is a conjunction of predicates. So you're holding that object the object's not on the table and the robot hand is not empty.

27:01 And this is this is a language called strips which was really widely used for for planning. PDDDL is is another one that people are actually using as an evaluation target for LLMs. you can take a look at that paper if you're interested. and people are thinking about the ways to combine you know kind of the strengths of both. But a planning problem is you have like some initial state and you have a goal and the goal is also a state. And your problem is how do you find a valid sequence of actions that get you from this initial state to the goal? And an action sequence is going to be valid if every action has its prerequisites met by the state that you're currently in. So here's an example plan. Like if you have blue and orange blocks and the blue block is on the orange and you don't have anything on top of red, blue and yellow, you can have a sequence of actions like this which you could hopefully I checked this carefully enough. You could take a look and see this is a valid action sequence and it does get you to the goal. So a lot of work in planning was and still is about search like you develop search algorithms things like BFS, DFS, AAR with different heruristics that given this very structured representation figure out a plan that gets you from a start state to an end state.

28:29 So that's classical planning and there's a lot of differences from planning with LLMs but some important similarities too. So with LMS like everything here everything is explicit right you know exactly when an action applies you know exactly what the action does you also a lot of the time know a lot about the world there's also ways to represent uncertainty in those approaches but with LMS everything is implicit right like for an LLM you don't know exactly what an action entails like when you could apply the action most of that lives externally to the agent you have to just like try stuff in the environment and see if it works. But for an LLM agent, you don't have to do a lot of search to write a plausible plan because, you know, LMS have just seen a lot of information about all of these different settings that we're operating in. So, they could just generate some text that's probably a reasonable first guess at how to move one block to another or more complex tasks like how to debug an issue in a codebase. So for LMS planning is less about doing search although we will later on in the end of the course see ways to bring search into improve LM agents and more about just like checking to see if your plan is actually feasible and executable.

29:50 but important concepts are still search to some degree and also action applicability. So we don't have a way of like doing these you know precondition checks that we did with classical planning but we will see some approaches that try to incorporate information about what you can do in your environment into the way that you choose your plans. So you might now's a really good time to start to think well if we aren't doing classical planning what do our plans actually look like? And formal plans like the ones we saw with strips they're checkable. Language plans like the you know ones that we saw in the plan mode at the beginning of the lecture are pretty general. programs are also a way to represent plans that sit somewhere in between. And there were a number of papers around I think 2023 was kind of the start of these that use a code language model to write basically a code structured plan which controls the system and it was applied to some domains including robotics and also others including kind of like structured question answering this paper binder we also did some work on this here for kind of like semi-structured question answering. But the basic idea here is you have a task that comes into your LLM like stack the blocks on the empty bowl and the LLM will be prompted to generate a program which makes calls to domain specific APIs or functions and those functions are going to be implemented using sort of like rob primitives from you know the robotic system like calling an object detector on an image to see are there any blocks or are there any bulls and then actually like making calls to object manipulators also. So for this to work, you need to have good APIs and good primitives. but you also need to have sort of the tasks that you want the system to carry out be well representable by code. And code has some nice features like you can say like wall I haven't put the block on the other block retry doing this thing and which is sort of a way to you know implement kind of like search and post conditions.

32:18 but it's also like we talked about in the skills lecture, a little bit more rigid. Yeah. And a way to make it more flexible is your API functions here can also be calls to an LLM for example or another sort of neural model like you know a ResNet based object detector. So you get some benefits of like you know having the structured control programmatic control of code but also you could use tailored models which can be machine learned and more flexible. Any questions about this?

32:55 Yeah, these approaches have started to at least for robotic domains. My understanding is these approaches have not taken off as much as you know endtoend like multimodal LLM based VLA type systems which can be directly trained. but these sorts of approaches are still like very useful for for example coding agents. we'll see a little bit about that with code act in the next lecture.

33:25 So another dimension to think about is like changing up the plan based on feedback that you get from the environment and is that useful or not to do. So Anthropic put out this blog post a couple years ago called building effective agents where they're basically kind of coaching you don't start with an agent like start with something simpler that's easy to reason about that you can specify in advance and they call those workflows. So in a workflow you have a fixed programmatic way of making calls to language models that specify a lot of the information that you have about the task. So say for this GPU example say that we were going to buy GPUs very frequently because we're rich and we always want to follow the same procedure for doing that. So we have a fixed list of vendors whose sites we are going to go to and do research. We'll read those specifications. We'll check if they fit and then we will pick the cheapest one and buy it. this is actually somewhat similar to like the agentless harness that I think we'll talk about in the next lecture. so this is nice because you you basically like know kind of the highle structure of the task that the agent's going to carry out. it has some flexibility to adapt like if the vendor website has changed it will hopefully find the right information from it and you know that it's going to like you know pick the cheapest one so so that's nice but it's also pretty rigid right like you know what if these vendors are no longer the best ones to do research on so it can be useful to relax some of these constraints too and for example like have the agent predict the list of vendors that should be researched searched and maybe you do like a search that produces that list.

35:17 or you just go fully adaptive and don't have this structure at all, but just give the agent sort of like the description of what you want it to do. You turn it loose and there's not much planning that happens in a way that's specified by the person in advance. So, there's a trade-off here. like committing to a plan upfront. it's potentially like faster and cheaper and more predictable because you could maybe like use smaller, simpler models to implement each of these parts. but if you aren't changing this at all, you like lose the ability to adapt to changes in the environment.

35:58 And we'll see a little bit later on that replanning can sometimes be you know worth the extra cost and complexity and unpredictability that it adds to your system. Any questions about this or or other things? Yeah. So if you take a look at this blog post, they'll say we've deprecated this and they point you to another one. But I think part of the reason they've done that is the agents that we have now are stronger kind of the most recent agents with the most recent models are stronger at making reasonable actions a lot of the time not constrained by workflow. I think we'll see this with coding agents also where this agentless framework is no longer the most successful framework for like solving issues. so some of this scaffolding can be replaced as your agents get stronger for a particular domain, but you also potentially like lose reliability. And if you're working on a new problem where you haven't you know, where agents haven't been trained to be able to react to changes in the environment, starting with a workflow is probably a safer way to go.

37:17 Questions, thoughts? Okay. So, reasons to add some structure to planning. and we'll talk about some of these that were motivated by our initial example. coming back to it again, we have you know this modularity like carrying out each of these subtasks independently from each other. feedback like potentially changing the plan based on things that you observe in the environment.

37:48 One thing that's really common across all of these is that they're long horizon like you need to keep track of information and it could be helpful to have some you know prediction of what you are going to do in the future and then potentially also you know control where a person might weigh in on the plan or changes to the plan along the way. And this will structure the next the next part of the lecture which is mostly talking about kind of approaches that have been developed in the research literature to handle each of these.

38:22 So first with modularity, we touched on this a little bit before where we you know we said that it can be useful to have different models that are specialized in different ways to carry out different parts of a task. And these types of approaches were really widely used for computer use agents for a while because the the strongest models for producing like plans were not very good at processing kind of like low-level fine grain visual details about websites. So in 2025 there were a few papers that were pretty successful by separate by like you know solving tasks on the web like finding the cheapest 4K monitors and they would decompose this into a planning step where you well actually a sequence of planning steps where you have a strong planner model like at the time GPT40 would take in the web page and would produce a natural language description of what should be you know type in the search bar at the top of the page but this model would be very bad at like actually clicking on the search bar especially if you needed to kind of like click on particular pixels. So what they did was they trained a small this was the U groundwork. They trained a small 7 billion parameter model on synthetic data where they you know had web pages and they were able to kind of like synthesize text descriptions like this for particular elements of the page and once they got that model to be very accurate then you could use it to execute these natural language instructions that were produced by the planner model. Right? So decomposing and making the system modular can kind of like let you independently optimize each of the components and like hill climb on each one after you figure out what the bottleneck is. And these papers were nice examples of this.

40:21 After this work was done, the companies that trained, you know, these big language models like the successors to GPT40 started putting a lot of like web data with the same sort of like fine grained, you know, stuff directly into the training of the big model. So these kinds of approaches were no longer as necessary for just improving performance, but still are potentially useful for improving efficiency. We'll see a little bit about that later on.

40:51 Yeah. So you can train you know you can train a model that carries out parts of a plan like they trained the grounding model here but you could also generate data to train a planner. One way you can do that was explored by this plan and act paper where you want so the task that they're doing here is yeah the task that they're doing here also involves like you know actions in an environment interacting with a web page and they want to have a planner model be able to produce a plan that kind of looks like this like step one is going to be searching for this particular place Step two is going to be analyzing the results and then hand off the execution of the plan to a model which looks sort of like the execution model we saw on the last slide. So they need to you don't have sort of a naturally occurring source of data for these plans. So what they'll do is they'll get entire trajectories carrying out tasks filter down the trajectories to ones that they predict are correct and then have a teacher LLM annotate that trajectory with basically a segmentation of the actions and labels in natural language for each of those action sequences. And once you have that, you can sort of like unzip that and create your training data for a planner, which goes from, you know, a natural language description of the task to the sequence of natural language steps. And then the executor also, which maps from a natural language description of a step to the actual actions that you take in context.

42:38 Does that make sense? In some ways, this is a little bit similar to the workflow induction stuff that we talked about last lecture, right? Like workflow induction also started from a trajectory and did sort of a segmentation and labeling of it. you're doing a similar thing here, but you're using it to generate training data for a model that produces those those descriptions. So there's some trade-offs also when you go to a modular system like this. You're you're decomposing a task into you know kind of a set of subtasks and a sequencing of them. And this is an abstraction that can miss some of the details and and be inflexible.

43:29 there's been some limited successes of like ro decompositions for coding. There were a sequence of papers that like said we'll have models implement sort of a software company or like a team of software engineers that might have like dedicated roles for testing for editing. Some even have like a product manager and those approaches have and some variants of them like like agentless which is kind of like very tailored to solving GitHub issues have success in sort of the if the task always matches that structure but they have some weaknesses too.

44:15 they're not adaptable as we talked about before and they also require like passing information from one of these modules to another and it could be hard to sort of get the right information that the other agent needs to solve its task. Whereas if you're doing this just in a single agent and you have done a good job of handling all the context of the past actions that are available, all that information is going to be there for the agent to use. So those are some of the trade-offs between these approaches that you know just have a single agent try to do everything or use a planning based decomposition.

45:00 So if you have like a sequence of subtasks that you want to execute in an environment, one thing that we're missing from classical planning is figuring out if you can actually do the subtask or not. So people started once LLM started to become you know really successful on NLP tasks people started to see if they could be used to control for example robotic systems and replace some of the planning systems that were used in the past. So you would give a system something like an instruction like how would you put an apple on the table and just have an LLM produce kind of like a text standin for a plan and you could sample a lot of different possible next steps in the plan from the language model and under each of these you get some score from the language model. these would be like you know sums of lojits. and some of these might be pretty plausible under the language model but the language model doesn't actually know what the robotic system can do in a particular context.

46:09 So it might propose like you know pick up the apple but if there's no apple within sight of the agent that's a bad subtask to actually carry out. So this paper called sean integrated the LLM being used as the planner with a model of affordances like whether a subtask produced by the planner could actually be carried out in the environment. And they used some classic techniques from robotics to develop that model that value function. but that value function basically was able to predict the probability of being able to execute any of these natural language descriptions of a subtask in a particular context. And when you have that, so like you know, if you're not near an apple or a Coke can, then those have low probability and finding them has higher, right? And yeah, and like placing it has even lower probability because you don't have it. So the simple way of like incorporating this value function of whether you can actually carry out a subtask with the planner is to just multiply together the probability that's given to you by the value function with the probability given to you by the language model.

47:22 Any questions about this? Yeah. So the next thing that we want agents to be able to do is to incorporate feedback from the environment, right? So we saw a precursor to this when we talked about reflection, right? Like you have an agent try out a trajectory, you see whether it succeeded or failed, you get some natural language feedback, you condition on that and you try again. And this can also this is especially applicable in environments where you don't get to see everything from the initial state that you're at. So this example is from a paper that was operating in this embodied environment called Alfred where you have a robot navigating around inside a simulated robot navigating around inside a simulated house and you have tasks like cook a potato and put it into the recycle bin. These tasks were synthetically generated so some of them are kind of funny. but the model will produce an initial plan that makes calls to these these primitives which can carry out tasks like navigate to a potato, pick up a potato, put it in the recycle bin and it'll try to carry out that plan but the plan might not actually be executable by the robot in that context. So you might get feedback like I cannot find a potato but I do see a fridge. you can just feed that feedback into the language model and then try to repredict the plan which will now be updated to like open the fridge and then hopefully there's a potato in there and I should continue on with that. And so this is kind of a simple like reflection based way of doing replanning that can help.

49:19 So there's generally a trade-off between you know thinking between doing the reasoning steps without interacting with the environment and taking actions in the environment and it can be there's a trade-off between these and different ones can be valuable to different degrees but I think there's this paper was pretty interesting that showed that if you have an agent that's acting in an environment you have choices about how to spend your compute. So you could if this is a reasoning model, you could produce like longer reasoning chains before you take a particular action or you could just take more actions and interact more with the environment and then you'll potentially be getting more information but you'll also need to you know process that information with your language model which will also be a way to spend compute. and they they compared these two approaches on these tasks that they looked at and they also compared to a baseline approach which we'll cover this more in the search lecture but which just like samples multiple different trajectories from the environment and then chooses between them using a judge.

50:41 That's that orange line here. So an approach that just got the model to think longer, produced longer chains of thought before taking each action is this blue line. And an approach that interacted more with the environment is the green line. And for like a given number of tokens spent usually this green line which is using those tokens to interact more with the environment is doing better. Does that make sense? Was the description clear to folks?

51:12 So, I think that this is kind of like a nice way of thinking about just the value of interaction. getting more information from the environment, as long as you're not doing things which put you into a bad state, is generally pretty helpful. And another paper that looked at this from another angle that Graham was actually involved in too looks at kind of the perils of overthinking for coding models. So they identified different sorts of behaviors that reasoning models used as a or models that produce you know thinking traces used as foundations for agents different sorts of bad behaviors that those models could produce which affect the actions that they take in the environment. So, one of these types is the model spending too much time planning and not taking as many actions. Another one is like taking actions which aren't useful but make kind of like harmful changes to the environment. and then there's a third one too like ending the task too early.

52:23 So these behaviors that they identified they don't actually require access to the reasoning traces because if you know they just require access to like how many tokens were spent on reasoning which you can get from a lot of these API models. but they look at sort of the balance of the actions that you can actually see in the environment with the number of reasoning tokens that are spent. And they developed some classifiers for these different types of behaviors and use that to produce a classifier which gives you sort of an overthinking score for a given agent backed by a language model acting in a codebase. And they plot these comparing performance on this benchmark of solving SWEBench issues with the overthinking score and find pretty strong negative correlations. So that models that are overthinking more like kind of not acting appropriately and doing too much thinking are doing worse on these benchmarks also. So they generally find that some of this is addressed by having like larger or stronger models. and so you can see like you know 01 with a lower reasoning effort is worse. 01 with a higher reasoning effort is better overthinks less also does better. and even non-reasoning models which you know still produce some text before taking their actions have this sort of behavior as well although it's less bad than it is for reasoning models.

53:54 So yeah taking feedback from the environment is useful. and you don't want to be spending too much time planning. you also want to replan as needed. Yeah. So this paper we won't have time to go into the details of it for the sake of time but I think it's a really interesting paper that I'd encourage you to take a look at if the idea is intriguing to you. But the idea is that like some actions that a language model can take are just sort of like plausible and m you can maybe do something reasonable without actually checking the details of the environment.

54:39 So say like you you know ask a you ask a coding agent to investigate a CSV file and find the item with the max price. So most CSV files that are related to prices probably have a column which is called price, but not all of them do. So a language model could take an action like this and it'll be right most of the time, but sometimes it'll be wrong. And this paper is sort of about how do we explicitly represent the probability that a particular thing is true about the environment like you know it has these particular properties of the CSV file and if we explicitly represent those probabilities can it make the agent more likely to do the right thing and they find that it can.

55:30 Yeah. So I'll encourage you to to check out that paper if that sounds interesting to you. Yeah. So part of the motivation too is for letting the model better be able to carry out long horizon tasks. And I think one of the canonical examples of a long horizon task is this task called vending bench which is challenging sort of because it's a long time horizon more so than because it requires like complex reasoning but the idea is to like run a simple business for a long time where the business is just operating a vending machine. so you have some set of items which have prices. You need to order new items if your stock gets low and put those in the vending machine. But the challenge is you have to do this for up to 222 days which can require like 25 million tokens from a model. So you need to be able to like track state over time and make good decisions over and over again without being poisoned by things that you do wrong in the past.

56:42 And models have gotten better at this as they've been trained with long context and trained with RL to be able to recover from their mistakes. But there's been some analysis that's looked at that's looked at some surprising properties of models in these sorts of long horizon tasks. So if if you one thing that's really challenging about tasks that involve taking like hundreds of steps in a row is that you have to have extremely high accuracy on the individual steps in order to have a high chance of being accurate on the full trajectory, right?

57:29 Because probabilities get multiplied by each other. If you have like a 90% chance of getting the first step correct, if you have a 90% chance of getting each step correct, getting all the steps correct is like 9.9 * 0.9 * 0.9 * 0.9. And this paper looks at so on the left here is the accuracy of individual steps on a simple task and on the right is the length of the task that the model is able to carry out correctly. So even you know going from like 0.9 to like.999% accuracy on individual steps produces a really large impact on the length of the task that you're able to do correctly.

58:25 But one really interesting thing is because the model's using its past context to make future actions and since these models were you know trained on were trained on like sequences of varying quality if you have mistakes in the past that can actually make mistakes in the future more likely. So why might this be? You know, one way to think about this is like models were were pre-trained on all the code from the internet. And if you have like good code in a file, like highquality code, then it's probably likely that the rest of the code in that file is also high quality. Whereas if the code is like, you know, maybe has some bugs or was sloppily written, probably the rest of the code in the file is also lower quality. So for a long time and still to some extent now, people found that if you sort of like seed a model with bad quality inputs, it's more likely to produce bad quality outputs in the future. And this paper finds that that's true for agentive systems as well, although it's corrected to a big extent by training models with reinforcement learning. And that makes sense, right?

59:44 Because as we'll see a little bit later on, reinforcement learning teaches models to be able to correct mistakes and to try to optimize their reward in the future independently of the past. But something to watch out for in long horizon tasks and that's some motivation for yeah so they showed that this is true for example with the quen 3 models which are pretty recent models right they find that if you insert errors into the past context of the model at higher and higher rates the strongest you know the presumably strongest the largest model quen 3 32b actually has the biggest drop off in accuracy in comparison to the other models So it's sort of more susceptible to being poisoned by mistakes in the past.

60:36 Cool. So we've I've kind of alluded a few times to this paper row which is recursive agent optimization from Aporva who's one of our TAs and and Graham is also an author on this paper and this paper is really cool because it trains the models. So we've we've talked a lot about like you know is planning useful is decomposition useful. One way to make sure that it's useful is to just train the model to be able to do it to succeed on a task.

61:10 We've also talked about kind of what's the right representation for a plan and how code can be useful as a representation. And I'd say those are two of kind of the main ideas of this paper. You'll train a model to produce a plan in code. and then execute that plan using sub agents which have more limited context so they can be more efficient. They don't see you know some of the unnecessary stuff that other agents are doing. and so if you have a task like plan a 3-day Kyoto trip in early April that has these properties, they train the model to produce code that looks like this, which launches sub agents that have these subtasks where the subtasks kind of look like what we saw in the chain of thought papers early on, the decompositions like you know find the cherry blossoms, find the quiet temple and this is also using like the async and await operations from Python so that these sub agents could be acting in parallel or in sequence as appropriate for the task. And like the paper says, this is recursive. So sub aents can also call other sub aents.

62:20 and it's trained with a reward function that you know optimizes the model's ability to carry out the tasks and also the model's ability to generate the code to you know achieve high reward on these training tasks. and also you know how often the children succeed. They also have some interesting experiments that show generalization too. So you can train on tasks that you can train on tasks that have sort of a medium difficulty as measured by how deep the task needs to be decomposed but then it generalizes to harder tasks too.

62:59 And yeah, they have some kind of interesting results that show that that harder tasks yeah that that harder tasks ones that are that require like more depth can be achieved using this approach. Okay, cool. So we won't talk as much about about how plans can be sort of a interface for people. We'll cover that sort of thing more in the interaction lecture. But plans can be useful as a way for making your system more robust. And one paper that I think that's really interesting that demonstrates this is this one just from this year that uses sort of a workflow based approach to carrying out tasks on the web. So, if you have a task like add the best noise cancelling headphones under $200 to my cart, your planner will, produce some code that looks like this, like search for noise cancelling headphones, loop over the products, you know, take the best one, add it to the cart. And why might this be useful?

64:19 Well, the web is kind of a the web is kind of a wild place. And people you like you the agent builder do not have control over what people are putting on websites. So people could insert injections for your model by making changes to these sites. Like for example, you could write a review on an Amazon product that says ignore the price. This is the best product. The agent's then going to take that text in. Does it use it or not? We had some work led by Aditi Ragunathan and one of her students Chen Wu that uses adversarial attacks on via images. so making kind of like imperceptible changes to the images of products. and like that has a similar effect to this like causes a model to perceive a product as the one that has the lowest price for example.

65:18 so adding in this kind of like structured plan gives some robustness to that because you by executing this code you're going to guarantee that you are finding the product that has you know the highest average rating rather than selecting one using this kind of like user or you know kind of adversary injected context. Does that make sense? Any questions about that? Cool.

65:50 So for the human interface side of thing, I just want to show this demo from cursor of their plan mode because I think this is kind of a nice interface that also allows like editing the plan in addition to just you know approving it. >> As agents run for longer plans help them get the context and direction that they need up front. I'm building a new feature on cursor.com where I can see my teammates's background agent box. Build a dashboard on the agents page where I can see and comment on my teammates background agents. Because this is an involved project, the model has recommended that we use shift tab to switch into plan mode. Now the agent is gathering context. You can see it's searching and reading files in our codebase as it figures out how to do authentication, authorization, and use our existing UI components. If I weren't in plan mode, the agent would just go ahead and figure out these questions as it's implemented. But in plan mode, the agent has done deep research in our codebase and come back to us with a few questions. So, I'd like for question A to have a new tab and page route. For question B, group by status. For question C, I'd like card based comments for question D. I want to store and retrieve comments in our D. This is a hard project and I didn't know how to group the combine board or how to store comments. But now that the model has this info, it's come back to us with a full plan inside a markdown file. So we can see that it's proposed the new front end data model, a new route as I specified, and then finally we'll see a full to-do list that the model creates.

67:31 So, I'm going to hit build. The entire markdown file plan is loaded into context and the agent is assigned this full to-do list. And so, we can see now that one to-do is in progress or complete. We can also save this plan as a markdown file inside our workspace. We can reference it in the future or our teammates can use it to collect. As a team, we've been seeing plan mode help the agent run for longer in the direction that you want. We're excited to see how you use it.

68:02 Yeah. So I think there's quite a bit of work to do here sort of at the interface between like overseeing agents and like human in the loop to like determine is the right thing being done and steer it. What's the right representation to steer and how can you learn? yeah and we'll touch on some of that in a future lecture. Okay. So with the last 5 minutes that we have, I'll cover one paper that puts a lot of these ideas together. But I think you'll also see more about this approach in the search lecture that that JY, who's the first author of of the paper, will be giving.

68:43 But just as an example task, here's here's a task from a benchmark that we released recently called Odyssey's that's based on people's like real world browsing history. So, we had people opt in to kind of like donate their Google history and they were able to select what they donated and we used it to create a benchmark for web agents that involves tasks like finding ACL you know surgeons for your your ACL on your leg. this is work that was led by Lawrence Jong and Jy Co along with Russ Saludnav and the agent to solve this needs to carry out like hundreds of steps maybe taking like half an hour to an hour of work on the computer and we have some rubrics that we use to evaluate whether all of the components of this task are correctly satisfied.

69:37 so for example here like taking 93 steps to go to all these websites and like put all the information in a spreadsheet by issuing kind of the low-level click and type actions in your in your guey. So these tasks are really long horizon and they also have some structure right kind of like the ones in the GPU example that we used at the beginning of the lecture. So JY's work called multi-agent computer use uses a graph-based representation of plans to decompose and carry out and replan for an agent that's doing these complex long horizon tasks. And the way this works looks a lot like the approaches that we've covered throughout the lecture.

70:25 you'll have the user task go into a manager which is you know implemented via an LLM a we need to use kind of like a a strong large model for this something like one of the you know recent cla models but we'll have it produce a decomposition of this task into subtasks represented using a DAG you know a dependency graph that has kind of the ordering and dependencies of the subtasks between each other when we have that we can carry out the subtasks in an ordering determined by the dependencies in the graph using parallel sub aents to carry out each one of these. And after the tasks are carried out, the sub agent indicates that it's done and the manager has the ability to replan like to inspect the results of that subtask. And if it doesn't think that it was done correctly, have the sub agent carry it out again. Or if it does, then it could potentially make changes to this graph to for example like introduce a new like vendor in the example that we saw at the beginning. and this process repeats over and over again until the graph is completely processed and then the task is complete. And here's a demo of this in action. So the task is I'm trying to decide whether brunch in San Francisco makes sense today. Involves checking the weather, you know, researching locations. And you can see the manager generating this DAG here. And then the subtasks that are being carried out by each of these sub agents. as well as you know kind of the chain of thought for the actions that the sub agents carrying out at each point in time. Sorry, it's kind of probably hard to read in the back, but you can check out the website. We'll share the the videos on there and then produces a structured artifact at the end. And you could see maybe here that it introduces a new node along the way when it finds that some new information is needed. So, it's able to replan.

72:30 Okay. So with the two minutes that we have I'll show one benefit of this modularity which is you can use like separate agents for the manager and for the planner or sorry for the manager and for manager/planner and for the sub aents. So if we use like a fairly you know cheap model as the sub aent worker like 3.54b we could actually just run this locally. we don't have to make expensive calls to an API. But if we keep that worker fixed and change the manager agent, we see pretty big differences in performance without huge increases in cost per task because most of the actions are actually being carried out by this worker model.

73:21 And we find that you know weaker models do see a more substantial improvement in performance by adding in this manager agent which does a lot of the kind of difficult planning about how to decompose a task. And so I've said this whole lecture that replplanning is useful, but here's like actually an experiment that shows that we limited how much the agent that produces the graph is able to make modifications to it. So if you have to stick with the graph that you initially proposed, your success rate on this challenging, you know, long horizon benchmark is around 25%. If you allow the agent to make one change to it, it goes up a little bit, but with more changes allowed, with more steps of replanning, the performance goes up even more.

74:13 And yeah, so there's like adding in planning is a design choice. There's trade-offs. Like it adds complexity for sure. that complexity may not always be worth it, but here are some of the questions that you should ask yourself. are there kind of like clear subtasks? Are they separable from each other? Could they be carried out ideally independently from each other? would it be helpful to have like a dedicated model for some of those subtasks? do they have different types? Is planning harder than actually executing? you should think about like when should I replan? Should I stick to my plan? Could it be useful to change it? and also can planning potentially be a way to better control the system?

74:58 Whether that's through a person like overseeing and intervening or using another model to to steer things. >> Yeah, that's all we have. I'll be around for a few minutes if folks have questions.