Skip to main content
Loading Explore guides…
Search Algorithms · Acedra
Home
Explore
Computer Science
Search Algorithms
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
149 segments
Copy
Hide video
0:05
All right. Let's begin. So last week, we talked about machine learning. And just recall, the learning algorithm is something that takes training data, which is input/output pairs and returns a predictor. And the predictor is the thing you go out into the real world, which takes inputs' and outputs' outputs. And for regression, that output is a number. For classification, that output is one of k options or a class, or a label. So that's what we did in machine learning.
0:37
Now, if you go back to the first lecture, recall the ingredients of intelligence. We have perception, reasoning, action, and learning. So a predictor really covers this latter bottom part. So it's basically reflexively mapping percepts to actions. And we're learning this mapping directly. So if you think about the neural nets that we were learning, even if it's deep, it's probably-- it's feedforward and it's fast. Now many problems in the real world
1:16
do require reasoning thinking, problem solving, planning. These are all related concepts. If you want to solve a hard math problem or solve a big, hard programming challenge, these clearly are not reflexive operations you should look at it, and then you output the answer. So this week's lecture is going to be about search. Search is one form of this type of reasoning when the world is deterministic. So as a few concrete examples, finding a sequence of moves to solve a Rubik's cube.
1:51
I guess, if you're a Rubik's cube expert, maybe this is reflex for you, but for most people, this requires a fair amount of search and problem solving, or finding the shortest path from point A to point B. This is going to be something that you explore in your homework. This is something that requires planning. You have to figure out your route, and then you go down the route, rather than just looking at where you are and just making a spontaneous decision.
2:19
So now you might wonder, OK, it's 2025, why are we talking about search? Because wasn't the point that symbolic AI actually started in 1950s and they were all about search, how you can solve checkers, general problem solving, and so on. And that didn't really pan out. So why are we bothering with this? Shouldn't we just go all in on deep learning? So is it relevant today? So I want to pull a quote from this famous essay by Rich Sutton, which is a Turing Award winner, developed
2:50
a lot of the foundations of reinforcement learning called the Bitter lesson, which I think has become a little bit of a folklore. It's a short essay. You guys should go read it. It has some, I think, useful per perspectives. And in the essay, basically it says that "general methods that leverage computation are ultimately the most effective, and by a large margin." So a really rich is pushing back against doing a lot of handcrafting priors, because once you
3:24
have general methods and you have compute, then it sort of washes away any sort of prior knowledge. Now, I mean, that's true in some limit. There's obviously a time and place for prior knowledge as well. But putting that aside, he also says that the two methods that seem to scale arbitrarily in this way are search and learning. OK. So he calls out search and learning are really these pillars that if you believe in the bitter lesson, are the things that you should pay attention to.
3:59
And that's why we're talking about search. So search is increasingly important. Think about test time compute and language models, which we'll touch on in a bit later. These are cases where you actually just need to do a bunch of compute at test time. And you need to organize that compute somehow. The only thing is that search alone, the point from the '50s, that search alone cannot do this. You also need to learn learning. But now, the last decade has told us how to do learning
4:31
and now we have really powerful models. And if you can couple them with search, which people are starting to do more, then you have a really powerful combination. And you can tackle some of the most challenging problems. OK. So that's the motivation. Feel free to interrupt or ask questions.
5:01
Yeah. What is search? Great question. I'm going to define it more narrowly. The rest of this lecture is going to be about more of the nuts and bolts and how you do search. And hopefully, it'll become clear. So let's formalize search using this abstraction called a search problem. So we'll do this through example. So these are going to be fairly toy simple examples. And so the first example is this. So imagine, you have a street with blocks numbered 1 through n. So n is 6 here.
5:41
So each of these is a grid lines as a block. And walking from block i to block i plus 1 takes one minute. Or you have this magic tram that you can take from-- that goes from i to 2 times i, and it takes two minutes. So the question is, how do you travel from 1 to n, which is 6 in the least amount of time? Now some of you are probably already solving this and thinking about strategies. I want you to actually stop doing that. Because that's not the point of a search problem.
6:19
The point of a search problem is to formalize, convert this natural language description into code so that you can have a general method that can solve these problems. Again, remember, the Bitter lesson. We want general techniques that can solve any search problem that you kind of have it. OK. I mean, if you solve it too, that's great for you. But we're going to have algorithms that solve this. And we'll see if you're right. OK. So we're going to define a search problem.
6:52
This is going to be parameterized by the number of locations, n. And the problem is going to have a start state. So the start state is this member of the search problem that tells you what state you start at. So the state that you start out is 1. And the problem also has a function called successors, which you pass in any given state. And it tells you where you can go, essentially. And so let's look at this. OK. So one thing you can do is you can walk. OK. So you're at a particular state, 1.
7:37
So you can take the action which is walk. It cost 1. So one minute, I'm translating cost to be time here. And then where do you end up, you get dumped into state plus 1. So you go from i to i plus 1. And this check is just to make sure you don't walk off the face of the Earth. It's you. The world stops at some locations. OK. So you can also take a tram. So here, the action is tram. The cost is 2. It takes two minutes to take this tram. And you end up in state 2 times state. OK.
8:20
So successors is the list of possible steps. So a step consists-- each step consists of the action, which is just a label, the cost of that action, and where do you get dumped into, the next state. So in this case, both walking and tram takes you to stay 2. But in general, they obviously will do different things.
8:46
So we have start state. We have successors. And the final function that is part of the problem formulation is the function is end. So the is end takes arbitrary state and returns whether you've reached the destination and the search is done. So here, we're just checking, did you get to the number of locations or not? And in this case, the answer is obviously false because we just started. OK. So in general search problem has the following components. You have a start state, that returns
9:22
initial state, successors, that specifies what you can do, which includes the actions, their costs, the resulting states that you end up in. And finally, we have is end, which takes a state and returns whether state is an end state. Any questions about what a search problem is?
9:51
OK. So now, given a search problem, what are we trying to do? The objective is to find a solution, which is a sequence of actions that minimizes the total cost. So here's a possible solution for n equals 10. So you walk to state 2, you take the transit state 4. You walk to state 5, you take the tram to state 10. OK. And this solution has cost 6 because that's 1 plus 2 plus 1 plus 2 is 6. OK. So this is one possible solution. There are many other solutions. You can walk all the way to 10.
10:35
That would be a cost of 10. And is this the best solution? How many of you think this is the best solution? How many of you don't think this is not the best solution? OK. Well, evenly split. So we will see. OK. So remember, it doesn't matter. We're going to be lazy and have the algorithm solve it for us. So you don't have to work that hard. The thing you have to get is make sure that your search problem is defined properly. And then you're good to go. OK.
11:15
So let's do a slightly more complicated example to just show you what states are really about. So suppose the magic tram requires tickets. And we only have a fixed number of tickets. And of course, this tram is probably in high demand. So we're not going to let anyone just get on the tram. So how do we change the search problem to incorporate this constraint? So let's see, what can we do here? So the state so far just captures where we are, the current location. OK.
11:52
But we also need to keep track of the number of tickets we have. So what we're going to do is we're going to define another search problem, limited travel search problem, which is going to be parameterized by the number of locations and the number of tickets you start out with. And now the start state is this going to be the structure travel state that has a location with one. And tickets equals the number of tickets that you started with. OK. So states can be composite things.
12:27
They don't have to be integers. They can be strings. In general, in the implementation, states are going to be any sort of hashable object.
12:37
So what are successors look like now? So now, the successors takes the travel state and has to return a list of things to do. So there's only two things you can do. You can walk or you can take the tram. You can always walk because you don't need tickets to walk. And this is walk, has cost 1. And the new state is this travel state where the location has bumped up by one. And still have the same number of tickets because walking doesn't take tickets.
13:10
And now the second part of this is you can take the tram, and the tram cost 2, you end up in the location 2 times the location. And then oops, this wrapped. OK.
13:27
Hopefully, is that-- OK. It looks like it's not going to unwrap. OK. There we go. But that's probably too small. Is that too small? OK. Let me make it bigger. So anyway, this is tickets minus 1. So we expanded one ticket to take the tram. But as a result, we're in location 2 times location. Now, there's one thing that we need to do here. And what is that?
14:06
So there is a check here that we need to make sure that we actually have tickets. You can only add the successor if you have non-zero number of tickets. Otherwise, it's the same problem. You just end up decrementing this counter and you can have minus 3 tickets and you go on. So this is what I mean by get your search problem definition correct. Because if you don't, then the algorithm is going to find a way to cheat sort of game your system. You can call this reward hacking if you want. OK.
14:46
So successors are walk to location 2. And you still have one ticket, or take the tram to location 2 and you have zero tickets.
14:58
OK. And is end is just, have you reach the destination? And notice that it doesn't look at the number of tickets, which means that there are possibly more than one end state. Because you can have zero tickets left, location equals to unlock with zero tickets, one ticket, two tickets, and so on.
15:28
OK. So in general, the state is a really important notion when we talk about search problems and also MDPs and then games. The state contains any information that's needed to evaluate future actions, costs, and successors. OK. So as another example, suppose we put another constraint. There are a lot of rules in this city here. If you can't take the tram twice in a row. If you want to enforce this constraint, the state needs to contain enough information so you can even properly assess it.
16:13
The current state that we don't-- only know our current location and the number of tickets we have. And that's not enough. What we have to do is we have to add to the state, which is another field in the state structure, whether the last action was taking the tram. Because if we know that, then if we last took the tram, we can't take the tram. And if we don't, we didn't take the tram, then we can take the tram. OK. So there's just going to be this game, you have to play,
16:49
where you take essentially like word problems, and you have to map them onto this type of structure. What is the state? What are the successors cost, and actions? So now you can ask, well, why do I have to think about it? I thought the whole idea is I don't have to think. Why don't we just include everything into the state, the entire history of where we've been? And surely, that's enough information to evaluate the validity of actions and states and successors. You could do that.
17:21
But as we'll see later, some algorithms such as dynamic programming, scaling the number of states. So if you have a million states or an exponential number of states, then your algorithm is going to be really, really slow. So in general, you want to keep the number of states small.
17:44
OK. So far, we focus on modeling. So what modeling means here is representing the problem formally. So there's no doubt in our mind what a solution looks like. And that solution in code should refer to correspond to your intuitive idea of what a good solution is. Now, the thing is that as you build up these search problems with more and more constraints, maybe you were clever and solve the first transportation problem. But now if I tell you, well, how do I go to 1 to 100,
18:21
and you can't use-- take the tram twice, and you also have three tickets. I would be very shocked if someone immediately came up with the answer in their head. But the point is, who cares? We have written it down formally, and now we're just going to pass it off to a learning-- not a learning, an algorithm. OK. Any questions about modeling, search problems, trains, magic trams?
19:02
Yeah. Do you use some protocols for [INAUDIBLE] the problems for [INAUDIBLE] problems. For example, if you use generally the easiest one, we have the problem just to reach with walking or train. And we add something. How we understand this can be useful for [INAUDIBLE] So I think the question is if you look at the easiest problem and you add constraints, how do you know this is useful? I mean, generally, when you're trying to solve a problem, whether it be a machine learning or search,
19:49
either you or someone comes to you with a description of a problem. And you have to translate it into something that's more formal. That process of modeling is often lossy. Sometimes you don't get all the constraints right. And of course, this is a sort of idealized setting. But you have to basically make some sort of lossy modeling assumptions to get it into a tractable form there that the algorithms can operate on. You can't really have your search algorithms operate on,
20:22
just like a kind of vague description.
20:27
OK. So we said, w don't care. But OK, now we have to care about it because we actually do want to solve these search problems. And who's going to do it, except for us? So let's start by solving this problem exactly. OK. We really want the minimum cost solution. Later, I'll show you how you can cut corners if you're short on time. So remember the goal, given a search problem, which defines states, actions, costs, and is end, I want to find a sequence of actions that minimizes the total cost. OK.
21:06
So exhaustive search just says, simply try all the possibilities, all possible sequence of actions, and take the one that's best. OK. This should work. Now there are many ways to enumerate all solutions. We're going to choose one particular formulation that will allow us to effortlessly generalize to dynamic programming. And this will be also the formulation that generalizes to Markov decision processes, reinforcement learning games, and so on. So bear with me while I introduce
21:40
what might seem a little bit more machinery than we need. It's because we're trying to think a little bit farther ahead.
21:49
So the key definition here is future cost. So a future cost is a function that takes a state and is the cost of the minimum cost solution from that state to the end state. OK. So here's a picture. Let me actually draw this on the board. So in general, you have a start state. And just for now, I'll assume that there's one end state. There could be multiple end states. And in general, from the starting state, there might be multiple actions. The best way to I think, understand
22:32
this is in terms of a graph, where these actions could lead to other states and so on and so forth. And here's a random state here. So let's call it S. And the future cost is-- there could be millions of states here. The future cost is if I started here, what is the total cost, the best total cost of getting to the end? OK. And future cost is something that you can apply to any given function. You can apply it to the start. If you apply it to the start, that gives you
23:09
the solution to the problem. OK.
23:16
So how do you compute this future cost? Well, let's take it step by step. So in life, if you have to solve a really hard problem, what do you do? You have to take a first step. No matter what solution, there has to be a first step. OK. So let's start here. Well, there's actually-- OK. Many potential first steps here that you could take. Let me just do this. So I'm going to use S prime to denote the successors.
24:01
And then what I'm going to do is I'm going to say this is someone else's problem. Like if I've computed the future cost from S prime to end, then I can just piggyback off of that and say, well, I could have gone here with some cost. And then over here, I'm going to put maybe some squiggly thing. And this is the future cost of S prime. OK. So one particular route is take this action, end up here, and then do the optimal thing to the end. Or I can take this action, do the optimal thing to the end,
24:48
or I can take this action and do the optimal thing to the end.
24:57
Which one is the optimal one? Well, it's whatever one minimizes the cost over all possible future successors. So the cost of this is cost plus future cost. The cost of this cost plus this. The cost of this action is this one plus that. And what we're going to do is we're simply going to take the minimum over that. So just writing out the pseudocode for this recurrence. The future cost of a state is the minimum over all possible successors. And for each successor I look at,
25:36
it's the immediate cost of that, taking that action, plus the future cost from wherever I ended up to an end state. OK. Let me pause there to address any questions.
26:04
OK. How many of you are good with this? OK good. So let's go through an example here. We're going to look at our familiar travel search problem. And we're going to implement this exhaustive search function here. I'm going to implement four algorithms today. And for each one, I'm going to keep track of number explored. So this is the number of states that we've looked at. And that'll give us idea of time complexity. So we're going to define this helper function called future solution.
26:40
It's essentially the future cost function. But instead of just returning a number, it returns a solution which remember also contains the cost. And that's because we don't just care about solving the problem and returning a number, oh, 42 is a cost. Well, what do I do? What actions do I take? You also need the sequence of actions and that's encompassed in the solution. OK. So I'm going to start at the start state. And I'm going to call this future solution function.
27:13
And what I'm going to do, I've explored a state. I'm going to check. Did I get to the end. So I haven't gotten to the end yet. So then, I'm going to look at the possible successors, walk or tram. And then I'm going to consider, for each of the successor, there's a-- which is taking the first step, which is walk. And then I'm going to recurse, if you call future solution on first step.state, which is 2. So I'm going to recurse. That's going to take me to state 2 in this recurrence.
27:53
And then I'm going to look at the successors. I can walk a tram. And then are you going to consider walk? And I'm going to recurse. And then I'm going to do this again. And eventually, I reach-- arrive at an end state. And at the end state, the solution is-- what's the future cost of end?
28:22
Zero. Because I'm at the end. I don't need to do anything. It doesn't cost me anything. And the steps is zero. I don't need to do anything. So that's the base case. Now I pop back up and I-- here, I'm just going to-- it's going to be hard to follow all the details, but I just want to give you the kind of rough shape of this.
28:50
Actually, let me just skip out of this because this is probably not-- you can follow this to trace through this when you study this afterwards. But hopefully the recurrence is clear. So let me just quickly go through this. At each state, if you're not at the end state, you look at all the possible successors. So these are these things coming out. And then for each successor, you recursively call future solution, which gives you these. And then what I'm doing is I'm going to just choose
29:28
the best solution, which is the one that has the smallest cost at each state.
29:36
So in the end, I got walk, walk, walk, which has a cost of 3 as the best solution here. And I explored nine states as a result. OK. OK. These numbers are out of date. I had five states before, but now nonetheless, the number of states explored, nine, is larger than the total number of states, which is four. OK. Which means that we are exploring some states more than once. So we'll come back to this later. Any questions about exhaustive search? Yeah. I don't know how big the recursion is.
30:23
So that would be-- does that become an issue with Stack Overflow. Yeah. Yeah. So the question is, how long is the recursion going to be? So it is basically the length of your solution. And in the worst case, it's infinite. Because if you have cycles, then you can go around. I'll come back to that point a little bit later. But for now, let's just assume that's not that bad.
30:55
So let's try some larger problems here. So let's try 10 locations if I do exhaustive search. So remember, this is a question I asked like that is walk, tram, walk, tram the optimal solution? And it turns out to be yes. And that it got a cost of 6, which is optimal. It turns out to be multiple optimal solutions. You could also walk, walk, walk, walk, tram.
31:31
The minimum cost solution doesn't have to be unique. But the minimum cost, obviously, is unique. So here's another one, 17 locations now. Now you see the number explored states is growing quite fast right. And in fact, it is going to grow in general exponentially with the number of locations you have. Which means that the time complexity of doing exhaustive search is, worst case, exponential in the number of states. So this is a pretty bad news.
32:11
Because even if you have, let's just say, 100 states, 100 locations, it's going to take, I don't know, the exact number, but it's going to be it's probably not going to terminate anytime soon. OK. So that's kind of rough. What about the memory complexity? So the good news is that the memory is linear in the length of the solution. And it's basically what you have to keep track of is, this is done sort of implicitly through the stack in the recurrence is where basically the stack represents
32:53
the path that you took to a particular state. OK. So now, coming back to this earlier question. We are assuming that we can't have cycles, because what happens if you can go from state A to B to C and back to A is that you'll notice that this function, as I've written, won't actually terminate. Because eventually, when you go back to A and then you go to B, C, A. B, C, A, B, C, A, and it just never ends. Well, it ends when you run out of memory, but mathematically, it doesn't end.
33:32
And it's also not well defined. So next week, we'll see how value iteration for Markov decision processes actually gets around this and allows for cycles. Actually, I'll show you better. I'll show you Wednesday how you can get around this as well with uniform cost search. But in the meantime, what you can do is we can-- here's a trick. You can add the number of steps into the state. OK. So this eliminates all cycles. Because you're always moving forward in time.
34:11
So if you go A to B to C to A, now that A is going to be different because you've taken a number of different number of steps. So that's how one way you can break cycles. Now you have to-- still doesn't prevent the infinite looping. You have to separately define is n to be true when the number of steps exceeds some threshold. So now you're counting steps. You can say like after 100 steps, that's it. No more. And then you can define in let's say infinite cost
34:45
if you're exceeding the threshold just to say that those states are essentially no good. Yeah. The first solution that you're supposed to get to is also beyond this threshold. Is there a way to set that threshold so that we know that we might arrive at a better solution? Yeah. So the question is basically how do you set this threshold because it's possible that the optimal solution might be beyond this threshold. There's no general answer to this except for just look at the problem
35:17
and figure out what you need to do. Generally, when the costs are all positive, you can have-- essentially, if you look at the number of states, I think that should be a pretty good upper bound. I mean, it's probably can be very loose. Sometimes, if you have negative costs, the optimal answer is actually-- technically, if you find a negative cycle, you just keep on going around and your cost goes down and down and down. But that's degenerate.
35:51
If you detect that, then you just return minus infinity. Yeah. Is that function necessarily have to define success?
36:04
So yeah. So the question is the n function have to also now determine whether it's successful or failure? Yes morally. The way I implemented this, again, is a little bit of a trick, where you say is n is just going to return Boolean. Is it true or false? And then I'm going to put it on the successors function to say like if I'm entering an n that state that is bad, meaning that I'm exceeding the threshold, then I'm going to give a cost of infinite there. Now when you're doing the min--
36:39
we're always trying to find-- remember, find the minimum cost solution. So infinity is not going to be the minimum cost solution if there's another solution.
36:51
So I'm sort of like hacking the framework to incorporate all these constraints. But this is part of the game here is that the states cost framework is fairly flexible. It's a kind of a game to figure out how to pack various constraints into this.
37:12
OK. So this 237 is not great. And it's going to get worse. So how can we improve on the efficiency of exhaustive search? Any ideas? Yeah. Make comparisons for the best results. And [INAUDIBLE] now [INAUDIBLE] this could result in the best result. The suggestion is to compare the current result with the previous result. Well, I mean, the current approach-- let's see. I mean, do that comparison went through this minimum? So I am trying to find the cost.
38:02
So there's a solution that minimizes the cost. This min is doing a comparison. So any ideas? Any other ideas? Yeah. Like a lookup table. So before you compute the feature cost, you look at the table to see if it's computed before. And if it is, then-- Yeah. Yeah. So the suggestion here is you make a lookup table and you see if you've computed the future cost for a given state. And if you have, then don't do it again. Yeah. So that's exactly what we're going to do.
38:36
And the term for this is called dynamic programming. And the term, you might find it strange, but it comes from actually the '50s, Richard Bellman, who pioneered, defined Markov decision processes, which we'll look at next week, introduced this term. And the word dynamic means that it's sequential decision making, multiple actions over time. It's dynamic. There's a temporal aspect to it. And programming just means optimization. You're trying to find the minimum cost solution, for example. OK.
39:12
Programming doesn't mean you're Python.
39:18
There's many ways to talk about dynamic programming the way I'm going to introduce it, which is to have the minimum change from what we've already done, is essentially I think about as just exhaustive search plus caching. And this is also known in some circles, it's called memoization. And recall that backtracking search or exhaustive search explores some states more than once. And dynamic programming says, well, if you already saw a state, don't do it again. OK.
39:48
So here's what we're going to do. It's going to be-- the dynamic program function is going to be identical to exhaustive search, except for I'm going to introduce three lines of code, I think. OK. They're going to be marked new. So the first thing is we're going to cache solutions for each state. So for each state, I'm going to cache the solution that we've computed so far. And then in this recurrence, the first thing I'm going to do is check if the state is already in the cache.
40:20
And if it's already in the cache, then I just return it. And the second thing or the, I guess, the third change is down here is after I computed the best solution, I'm just going to cache it. Everything else, all of this is identical. If you don't believe me, you can do a diff yourself.
40:48
OK. So again, the three changes, introduce the cache, check if there's a cache.
40:58
If there's a state is on a cache, and then at the end, put it in the cache if it's not there. OK. Actually, this design pattern is so prevalent that you can even write Python decorator that says at memoize, and it will wrap your function and memoize it. But we didn't do that just to make it more transparent. OK. So I ran this. And at the end, you can see what the cache looks like. It has, for every state, the future action. So this is actually kind of nice because not only did you
41:36
solve the problem for the start state, but you can look at all the solutions, the future solutions from every state. So for one, remember the cost is six. From two, it's five. From three, you walk, walk, tram. From five, it's just taking the tram. Even from six, it's walk, walk, walk. And I guess, the rest of the way, it's walking because otherwise, you overshoot. OK.
42:11
Yeah. So it's best solution. Yes. The cache store is the best solution from each state. Where does it make that comparison? So the question is where did it make the comparison to know that it's the best solution? So if you remember, this is inherited from the exhaustive search. So here, I'm looking at all possible successors. And I'm accumulating all the solutions. And here, I do the minimum by key. So here, for every solution, I'm taking its cost and just taking the minimum.
42:56
So this is one way to write it, I think, which is a bit more functional. You could have also written it. You loop over, and you do the explicit like less-- if cost is less than the best so far, then update that, which is a bit more procedural way of doing this. This I find a little bit more elegant, but it's the same thing.
43:19
OK. Are we good with dynamic programming? So let's try some larger problems now. So now, I have 17. Now the number explored states should be identical to the number of actual states here. Because I'm not exploring a state more than once, I can go up to 100 now and I can compute it for 100. So let's just look at the solution. So it's walk, walk, tram, tram, tram, walk, tram, tram. OK. So it kind of makes sense. One thing that's actually kind of fun about these search
44:02
problems is that you can define these problems. And then you look at the solution. And intuitively, you can see what you're supposed to do. Like you kind of want to get in position to take these trams so that you hop by powers of 2, but you don't want to overshoot. So then you have to line up exactly where it is. But in general, you can think about this as a fairly difficult reasoning problem, and you have to think through all the different possibilities.
44:34
So one of the things actually is nice is that you can just solve these problems and you look at the solution and you look at it, it's like, oh, that's kind of clever because it might not be as obvious as just like doing a bunch of walks and then taking the tram.
44:52
OK. So let's discuss when would you want to use dynamic programming. Hopefully, I've solved the dynamic programming is like, oh, wow, exponential improvement in time complexity. That's great. So not quite so fast. There's some caveats here. One fact about life is that memory is more precious than time. Well, life meaning computer life, I guess. You can always run a program for longer, but memory doesn't grow. So if you want to run dynamic programming,
45:29
it's going to take memory a total number of states. And your computer is only has so much memory in it. And once you fill it up, then you just can't run dynamic programming at all. I mean, you can do things write to disk, but that gets really slow and you don't want to do that. OK. So that's when you can then use dynamic programming is when the number of states is actually fits. So if your number of states is like a trillion, probably it's not going to shouldn't do dynamic programming. OK.
46:02
Now the question is that you can do dynamic programming, when does it actually provide speedups over exhaustive search? And the intuition here is that it's useful when essentially there's a lot of ways to reach a given state. If every action takes you to a new state, then you might as well do exhaustive search, because essentially, the cache is always you're going to have a cache miss. So maybe I'll just draw two pictures here.
46:42
If your situation looks like that, where you have your start state, and then basically all your solutions look like this. They're all independent.
46:55
Then should you do dynamic programming here? No. right? Whereas if you have your-- let's say you have your state and then--
47:13
so typically, you might see these kind of lattice patterns, where at each state, you can essentially go like this, then you should use dynamic programming here because the total number of states is essentially linear. But the number of paths through this is exponential. OK. So there are many ways to reach a state. That means dynamic programming is going to have leverage.
47:48
So unfortunately, a lot of problems actually do look like this. Later, we'll see that if you generate from a language model, essentially it kind of looks like that because every sequence is kind of unique. We'll come back to that later. OK. So dynamic programming is just exhaustive search plus caching. And remember, exhaustive search, the key idea is future cost, which defines its recurrence and allows you to break down a problem into subproblems. And then you should use dynamic programming
48:25
when the number of states fits in memory. And there's a lot of ways to go between states.
48:33
Yeah. So [INAUDIBLE] the memory complexity like exhaustive search was linear to [INAUDIBLE] the solution. [INAUDIBLE] program is linear to the size of the state. Then, if those two are both linear, how much efficiency is there? So just to repeat. So the memory complexity of exhaustive search is essentially the length of the longest solution. And the memory complexity of dynamic programming is the number of states. And so the question is if both are linear, then what is the speed advantage?
49:16
If both are linear, you probably should-- which is the case I think in these cases, then you should use dynamic programming because linear in memory means that dynamic programming is essentially going to be linear or maybe quadratic time. Whereas exhaustive search can be exponential time still.
49:44
So let's move on. So, so far, we've computed the exact minimum cost solution. And the time complexity is at least the number of states. If you're doing dynamic programming, it's the number of states. If you're doing exhaustive search, it could be exponential in that. So large number. So what if the state contains the set of locations? So remember, the state is the information you need to be able to assess the validity of the solution or even determine what the cost and actions are.
50:20
And sometimes you need to store the set of location. If you need to remember all the places you've been so far, so you don't repeat the location or something. There's also, what if this was a sequence of words generated so far? There's a lot of sequences of words. So you're not going to cache all of them. So in that case, exact search is going to be intractable. And so now, we have to move to approximate search. And the key idea is that we're just going to heuristically look
50:58
at a subset of the actions. And as a result, we might miss something. But oh, well, we can't do anything about it. There's no guarantees here. So this is now we're entering the realm of just heuristics. But often, these heuristics can work well in practice. Your mileage will depend on your exact problem setting. So I'm going to look at two algorithms, best of n and beam search. OK. So these are going to be fairly simple ideas here. So the simplest idea is to just choose random actions
51:34
until we reach the end state. Do this n times and take the best solution. That's best of n. You might have heard best of n somewhere and it's like, oh, what is that fancy algorithm. No, that's it. OK. So let's do this example here. Travel problem with 10 locations. I'm going to take this opportunity to define some forward looking terminology. So a policy is a function that maps a state to an action. It can be deterministic. It can be random. OK. We usually see policies in reinforcement learning.
52:16
But we can actually talk about policies in search as well. Because search is actually going to be a special case of Markov decision processes, which are the thing that you do in reinforcement learning. OK. So a policy map states to action. So let's start at say one. And let's define a uniform policy, which is one particular policy. What it does is given a state, it looks at the possible successors. And it just chooses one uniformly at random. OK. Pretty simple. And so every time you call it, you
52:55
might get a different answer. So sometimes you get walk, sometimes you get tram. Hopefully, you get roughly half and half. So that's a policy. Now we can apply a policy from the start state to an end state to get a solution. And that's what I'm going to call a rollout. Again, borrowing terminology from reinforcement learning. OK. So a rollout, you start at state while we're not at the end. And I also have this capped so that it just in case you infinite loop or something.
53:33
I'm going to take a step according to the policy. And I'm going to just keep track of the steps. And I'm going to advance the state. So I took this step. Now state is going to be 2. And so as I go through this, I'm going to take the tram, take the tram, take walk, walk. OK. So now I'm at the end. And now I have this solution which is that has sampled, which is tram, tram, tram, walk, walk, has cost of 8. OK. I'm going to roll it out again. Now, it has 6. OK.
54:15
I guess, I got lucky and it got the minimum cost solution. Roll out again. Less lucky, I get a 9. OK. So you get the idea. I just roll out a bunch of solutions randomly trying actions, and then I'm just going to take the best one. And this is captured in this best of n function, which essentially just roll, does a bunch of rollouts.
54:45
Just roll out, roll out, roll out, roll out, roll out. Let's jump here. And then I'm going to just choose the best solution, which has cost 6. OK.
55:07
OK. So the guarantee here is that as n goes to infinity, so the number of rollouts you do, the solution will actually converge to the minimum cost solution, assuming your policy tries has positive probability on all the actions. So this is kind of nice because it says there is a way to get to the minimum cost solution. Now, the bad news is that this could take exponentially long. So n might have to be like centillion or something.
55:44
OK. The other nice thing about best of n is that it is embarrassingly parallel. So if you have 1,000 machines, you can just go farm out your search to each of the 1,000 machines. They don't have to talk to each other, they just explore independently. And at the end of the day, you gather all the-- you see which one has found the best solution. So it's simplicity, and the parallelism is actually why we actually talk about it. And it's not as bad as it might seem.
56:17
Also, if the policy is informed, then it actually can be pretty reasonable. Right now, the policy is just choosing actions at random, which is probably not the best. But later, we'll see, you can define the policy to be a language model, which actually is pretty informed. And then best of n is a pretty good baseline. So because of this, [INAUDIBLE] make it [INAUDIBLE] to make it a parallel. So it is [INAUDIBLE] faster for you. So you cut the length to make it parallels.
56:51
[INAUDIBLE] 15 to 1 in parallel. You can use other tools, but not a lot of time. So yeah. So the idea is of best of n is parallel. From the starting state, you just roll out multiple trajectories to the end and you just take the best. OK. Any other questions about best event? Yeah. What I assume that each of the [INAUDIBLE] different types is complete. So if we try to parallelize it, is there synchronization issues So the observation is that different paths are going to be different lengths.
57:38
And are there any synchronization issues? There's no synchronization issues because a worker that's rolling out if it ends early, it'll just go on to the next one and try it again. They don't have to communicate with each other. Yeah. It's going to be actually-- the point might be more relevant for beam search. So hold on to that thought.
58:02
So let's talk about beam search here. How many of you have seen beam search before? OK. Only a small number of you. OK. So the idea is not too complicated. So the essence of algorithm is I'm going to keep track of a set of beam width, which is a number, let's say, 100 solutions from that come from the starting state. I'm going to consider all possible actions from each of these partial solutions, evaluate their cost, and then keep the beam width. OK. So the term beam comes from--
58:48
well, the analogy is like you have you're in the driving in the dark and you have your beam. And that's basically what you see. So as you advance the car, your beam kind of shifts. But it's only narrow right. Exhaustive search is that-- I guess, I don't know, it's daytime or you have light everywhere and you see everything. But when you're driving in the dark, you only see a little bit in front of you. OK. So let me-- before I go into the code, I want to just maybe draw a picture
59:19
to give you the outlines of what this looks like.
59:30
OK. So the idea is you have your start starting state and then you start by considering, let's say, your beam width is 2. That means you're going to only keep track of two things. If beam width were 1, that would just be the greedy algorithm. So you start, and maybe there's three actions. OK. So you consider these three actions. Well, three is greater than two, so one of them has to go. So maybe this has a cost of 5, 2, and 3. You're trying to find the minimum cost path.
1:00:19
So you say, sorry, we kind of keep track of you. We have a budget. Then you move on to these and you consider possible actions from here. So now, you have six different candidates to choose from. And you're going to evaluate them. And then you're going to choose the best two. Actually, let me just leave this there for concreteness. And let me just X out that. OK. So you're going to take the top two. So maybe it's this one and this one. OK. So then you cross that out.
1:01:01
And then now two survive at every step. And now you're going to try different actions.
1:01:10
Maybe have four this time. And then you take the top two, and then cross out the ones that don't survive and so on and so forth. OK. So this is a schematic of what beam search is doing. And at the end, you basically have two trajectories, paths through this to this graph, which then you take the best one and you return that. Yeah. Now [INAUDIBLE] one reaches the end earlier. OK. So now you bring up the synchronization thing. So suppose that this is an end, this is an end state.
1:01:54
So now but this one hasn't ended. So you're just going to continue marching along. In the implementation I show, we're just going to hold on to that. We just pass this along. We don't expand it anymore, but we just keep it in the candidate list.
1:02:18
So let's look at the code for this. Oh yeah. What are the nodes that do that for a [INAUDIBLE] So a question is, what happens when nodes loop back or you end up in infinite cycles? You can. What we're going to do is we're going to have a max steps that allows you to essentially-- you can start looping, but you we're only allowing you to do it for 10 steps.
1:02:52
OK. So beam search, I'm going to start with this variable called candidates. And this is at every iteration of the algorithm, I'm going to keep track of a list of solutions. And these are partial solutions that go from the start state to the current step to some state, I guess. OK. So I'm going to take a number of steps, max steps forward. So every solution has to complete a max steps. Otherwise, we're just not going to consider it. OK. So I'm going to build up a new set of candidates.
1:03:37
So this is suppose I'm here. So candidates. And this is going to be new candidate.
1:03:52
So I'm at a particular point. I want to build the next generation, so to speak. So for each of the existing candidates, I get the last state. And I'm going to check, is it at the end? If it is, then I just keep it there.
1:04:16
Otherwise, I'm going to try all the possible successors. And all I do is just append the current candidate steps with the successor step.
1:04:32
OK.
1:04:38
So I do this for all the candidates. Let's see. This does get a little bit-- OK. So in this case, in the tram problem, new candidates. I have two candidates, one is walk, one is tram. And then I look at this. I sort the candidates by cost, which is going to be walk, tram. And then I'm going to prune. Here, the beam width is, I believe, it was 2. And I had two candidates, so nothing gets chopped off. So I'm going to continue. So now I'm step one. My candidates include these two.
1:05:20
And I'm going to consider new candidates. I'm just going to jump here. So now I have a number, four candidates. And with cost 2, 3, 3, 4. And I'm going to sort and I'm going to prune. So I only keep the two candidates with lowest cost, 2 and 3. And I sort of broken ties a little bit arbitrarily here. OK. So you hopefully, you get the idea. So I step, step, step. And at each point in time, I only have two candidates. And this one has gone to stage 6. This one has gone to stage 10. OK.
1:06:14
So at the end of the day, my candidates, I have one with cost 6, one with cost 9, that make it to the end.
1:06:27
And then I'm just going to return the best. So candidate zero is the best one. So one side effect of beam search is that you not only get the minimum cost path, but you get-- or rather, you get an approximation of a minimum cost path. You also get an approximation of a second best and the third best up to the number of beam. So you can get a little bit of sense of the alternatives here.
1:06:57
Any questions about beam search? Yeah. I guess, also related to the same thing again, when you complete a path, does that count as one of your beams ending, or do you regain that. So say, we had two. One of those threads terminates at the n step. Now does my other thread get two? So the question is this one ended. And suppose, I have two more here. Beam width is 2. So do I keep-- basically, is this one of them and the others? In this implementation, this would get x out.
1:07:37
If you want, yeah, it doesn't really matter that much. I mean, you could give special cases and say, well, let's just put it off to the side. But typically, you can just add it. Because that allows you to automatically compare this with others. Because just because it finished doesn't mean it's better. You might actually still want to throw this out.
1:08:11
OK. Any other questions about beam search? Yeah. What's a good beam width? What's a good beam width? 10. No, I mean, the honest answer, I mean, it depends on your problem, your budget. I mean, I've seen anything from 2 to 3, to 1,000. So it really, I guess, depends. But on the order of 10, I think, is actually reasonable, at least in language settings. Beam search is also related to particle filtering, for tracking and probabilistic models. And there, you can get, thousands of--
1:09:02
equivalently, thousands of particles. Yeah. In the example where we get to an end state with a certain cost, and if the [INAUDIBLE] arrive as an even higher cost, that is intended to just stop, [INAUDIBLE] doing any better. So I think the question is, if you got here and you got like a cost of 6, and this is already 8, so then you just get rid of that. So that's a good question. So if all your costs are non-negative, then you can just stop there. And you can prune early.
1:09:44
In general, you might not have negative-- you might have negative costs, in which case you can't. Because this, you might drop that down to four later. Yeah. So it depends on your problem. OK. Just a few notes about beam search. So like I said before, if beam search is 1, then this is also called greedy search. As beam width goes to infinity, then beam search becomes exhaustive search. You're getting every-- you're basically not throwing anything away. This is a bad idea because not only
1:10:22
are you doing exhaustive search, but you're also scaling the memory, exponentially, as well. Terrible idea. Beam search is deterministic, whereas best of n is not. That's stochastic. There is also alluded to stochastic version called particle filtering, which I'm not sure we'll get to in this class, but feel free to look it up. Best of n incorporates a policy as a prior. Beam search just uses a cost directly. So depending on if you have a good policy to guide the search, you can use best of n.
1:11:06
Otherwise, if you don't, then you can use beam search. Particle filtering also allows you to have a policy as a prior. So best of n is generally simpler and more parallelizable than beam search. So anyway, those are some reasons. Both are used pretty commonly. So it depends on what you're trying to do.
1:11:36
OK. So a final example is I'm going to talk about test time compute in language model. So this is going to be an exercise in showing how much more real world setting can be adapted to the search problems that we've been talking about. There is a bit more complexity here because you have to do some shenanigans to get Hugging Face language models to behave, but hopefully it won't be too bad. So remember, a language model is in the language of multi-class classification.
1:12:14
It's just a multi-class classification probabilistic classifier that takes as input, a prompt, and gives you a distribution over the next token. So you can think about the next token as the set of classes. There just happens to be probably 100,000 classes. But mathematically, it's exactly the same thing that we saw last week.
1:12:37
Sometimes, you have a verifier that takes a response and a prompt, I guess, and returns a Boolean. Does this response is correct or not? So a typical setup here is that the prompt is like a math problem. Your language model is going to generate a solution to that math problem. And then you have a verifier that checks whether that solution was correct or not. OK. And your goal is to produce a response that passes the verifier and also is likely under the language model.
1:13:16
So the idea of test time compute, which I mean, has been around for a while, but I think it really got popularized in the public eye due to OpenAI's o1 series, is instead of just sampling one answer, in general, let's try to expand more compute to get a better answer. So a very simple way to do this is best event sampling. Now I think most people when they think test time compute, they think chain of thought and other things. That's absolutely one way to go. But best of n is actually a pretty--
1:13:56
it's a thing that people actually do a lot. There's this paper of many papers, which shows that best event sampling actually works surprisingly well. So you can use a small model, do best event sampling a lot. And you can then-- that's competitive with a much larger model. OK. So let's cast this as a search problem. So to define a search problem. Remember, we have to define what the states and actions and costs are. So the state is going to be a string, which
1:14:33
is the prompt that was given, plus the prefix of the response that we've generated so far. The action is going to be predict the next token. And the cost is going to be the negative log probability of the next token. So because we want to minimize cost, that's going to be-- we want that to be equivalent to maximizing probability. And then if there's a verifier, I'm going to use this hack and say, well, I get a free minus 100 cost if the verifier succeeds OK.
1:15:10
So this is an example with a very, very small model that runs on my laptop. So we're not going to do anything too crazy here. So I've taken, define a language model search problem. The prompt is parentheses 3 plus 7 times. And all this does is I'm going to use the Qwen3 0.6 billion parameter language model. I'm going to define a tokenizer. And load a model from Hugging Face. So we have to, first, define what a policy is. To use best of n, you need some sort of policy.
1:15:50
We're going to use a language model policy. And the start state is just going to be the prompt. And what the policy does is it generates a bunch of successors. OK. So let's look at what successors looks like. This is inside the problem statement. I'm going to convert that state into a set of tokens. This is because a language model speak in tokens, which are integers, rather than strings. I'm going to compute the probabilities. I'm going to skip all the details here, but you can read.
1:16:37
This is hopefully a connection to the previous lecture. We're used to doing things like softmax. I'm going to just take the top k probability. So these are the probabilities. These are the token indices. And then I'm going to build a successor for each of these tokens. So I have an action with a particular cost minus the logprob. And then the new state is going to be whatever. So this, I think, all this says is out of space. And then if it's a complete sentence,
1:17:20
and it contains a number, then I'm going to give you a plus, minus 100 bonus. So once all is done, I have a bunch of successors. So one successor just added a space. This one added a space paren, x, square root, a. And you see the cost of these. Nothing has produce a valid sentence. So I don't get the minus 100 bonus. OK. So those are the successors. And if I take the cost and I convert them into probabilities, I can sample from this probability distribution,
1:18:11
and I get return a particular successor. So this is a language model policy. It's generated these successors, take the cost, compute the probabilities, and sample according to that probabilities. And I get a particular successor. OK. So that's one step. All right. So now, I can do best of n. And best of n, remember just runs the LLM policy using this rollout. So rollout once. So each step in the rollout is appending a new token. So I have space. I have two. And I have closing parentheses.
1:18:50
And because this is a well-formed expression, I get minus 100. And so remember, low cost is good. So that's one solution. If I look at all the possible solutions, I have this. I have this. They often can be duplicates because again, you're sampling independently. So there's some chance you're going to hit the same high probability solutions. But sometimes, I get a five. Sometimes, I get a five. OK. So in this case, I'm going to choose the best solution which is going to be 3 plus 7 times 2. OK.
1:19:35
So I chose this solution. And that's the result of best of n sampling. OK. So in practice, you wouldn't want to implement things this way. You would do a lot of tricks to speed up inference, but this is just an illustrative example of how I think we're connecting the very classic search with more modern language models. OK. So just to summarize, we've introduced search problems, which formally defines the states actions and costs, where
1:20:06
objective is to find a solution, which is a sequence of actions that minimizes the total cost. We looked at a bunch of different algorithms. If you're really particular and want exact solutions, you can do exhaustive search, but that is generally exponential time. You can do caching, which gives you dynamic programming, which can give you exponential fast speedups, but you have to fit the number of states into memory. And then we also have best of n, which is like throwing darts
1:20:37
in parallel, or beam search, which is like that car beam which allows you to find, hopefully, good solutions. But both of these are heuristic and sometimes they might fail, and you have to just be aware of that. Again, the synergy between search and learning, I think, is rather interesting. So you can think about the cost are learned from data. So the cost in the language model example were the language model probabilities, which is obviously all kind of machine learning,
1:21:05
supervised learning on large amounts of data. And then the idea of search, where it plugs in is you're trying to find the best solution given these costs. And I think this is generally a pretty good recipe for building kind of robust systems in AI. Next time, we're going to revisit what happens when there are cycles. This time, we just said, well, look at a max number of steps and just give up. But there's actually going to be some nice things you can do. And we'll see that on Wednesday. OK.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat