Stanford CS221 | Lecture 5： Search I — Annotated Lecture Notes & Key Takeaways

Course Information

Institution: Stanford

Original Course: Stanford CS221 | Autumn 2025 | Lecture 5: Search I

Instructor Bio: This lecture is delivered by Percy Liang, Associate Professor of Computer Science at Stanford University and core faculty of the Stanford Institute for Human-Centered Artificial Intelligence (HAI). Percy Liang leads the Stanford Natural Language Processing Group and the Center for Research on Foundation Models (CRFM). His research spans the theoretical foundations and practical systems of artificial intelligence, including machine learning, natural language processing, AI alignment, and rigorous model evaluation. He received his PhD in Computer Science from the University of California, Berkeley and his BA in Mathematics from Harvard University. His work has been recognized with the NSF CAREER Award, Google Faculty Research Award, and multiple best paper awards at top-tier AI conferences. He has taught CS 221 at Stanford for over a decade, shaping foundational AI education for thousands of students.

Course Description: This lecture opens the search and planning module, introducing the core problem of finding optimal solution paths through discrete state spaces. It covers uninformed search strategies including breadth-first search, depth-first search, and uniform-cost search, systematically analyzing each algorithm for completeness, optimality, time complexity, and space complexity. The lecture also formalizes the state-space search framework and explains how it applies to a wide range of AI planning and problem-solving tasks.

The lecture opens with a small act of repositioning. Last week was machine learning: a learning algorithm eats input-output pairs and hands back a predictor, and that predictor is what you take out into the world. For regression it emits a number, for classification one of K labels. The lecturer's point is that this whole apparatus sits low in the stack of things intelligence needs — perception, reasoning, action, learning — because a predictor is basically a reflex. It maps what you sense straight to what you do, and even a deep net does it in one fast forward pass. Search is the unit for everything that doesn't work that way, at least in worlds where nothing is random.
 

Rubik's cubes get name-checked here, with the aside that if you're a speedcuber the problem has collapsed back into reflex for you. Finding a driving route gets the harder sell, since it's the homework problem: you commit to a plan and then walk it, rather than standing at each corner improvising. The framing I'd underline is narrow on purpose — search is reasoning under determinism. Randomness and adversaries come later.
 

Why Search Again, in 2025

 

The lecturer stages the obvious objection rather than dodging it. Symbolic AI started in the 1950s, it was all about search, it solved checkers and general problem solving, and it didn't pan out. So why not go all in on deep learning and skip this?
 

The answer is Rich Sutton's "Bitter Lesson," which he describes as having hardened into folklore and recommends reading directly (2:52). The thesis, as relayed: general methods that ride on raw computation beat hand-built priors, and not narrowly — by a large margin, once compute is cheap enough to wash the priors away. Then comes the line the whole lecture hangs on. Sutton names exactly two things that seem to scale without bound this way, and they are search and learning.
 

I appreciated that he immediately puts a thumb on the scale against himself. This is true "in some limit," he says, and there is still a time and a place for prior knowledge. Then he moves on within about five seconds, and I think that brush-off is the most interesting crack in the lecture's foundation, because everything after it is a demonstration of hand-built structure. Choosing what goes into a state is as hand-crafted as AI gets. If the bitter lesson is right that priors get washed away, the state design he spends twenty minutes teaching is a prior too. He never reconciles those two commitments.
 

The modern hook is test-time compute: models that spend real cycles at inference instead of answering in one pass, and where that spending has to be organized by something. He's careful not to romanticize the 1950s, though — search alone failed then, and learning alone isn't enough now. The pitch is the coupling.
 

Turning a Word Problem Into a Search Problem

 

The running example is a street of numbered blocks. Walking from block i to i+1 costs one minute; a magic tram takes you from i to 2i and costs two (5:36). Get from 1 to n in the least time.
 

Then a genuinely good teaching moment. He watches people start solving it, tells them to stop, and explains why: the exercise isn't the answer, it's the translation of a paragraph of English into code that a general solver can eat. This is the bitter lesson re-applied at the level of the assignment. There's a small class poll on whether a cost-6 route for n=10 is optimal, the room splits evenly, and he declines to settle it — the algorithm will, and the skill worth having is writing the problem down correctly.
 

The formal object has three parts. A start state. A successors function that, given a state, returns the steps available from it, where each step is an action label, a cost, and the state you land in. And an isEnd predicate that says when you're done. The goal is a sequence of actions with minimum total cost.
 

The interesting half of this section is what counts as a state. Add a rule that the tram needs tickets and the state has to grow a ticket counter, which means states are composite objects — structs, strings, anything hashable. Add a rule that you can't ride the tram twice in a row and the state has to grow another field recording whether your last move was a tram, because with only location and tickets there's no way to even evaluate the constraint.
 

His warning about getting this wrong landed harder than the formalism. If you forget to check that the ticket count is nonzero before offering the tram as a successor, the solver will happily decrement into negative tickets and keep riding.
 

He calls this reward hacking, and the general lesson is that a search algorithm will find the seam in your specification.
 

There's a natural question lurking: why not just shove the entire history into the state and never worry again? His answer is that it's technically sufficient and practically fatal, since some of the algorithms scale in the number of states. Keep states as small as honesty allows. A student pushed on whether this modeling step can be trusted, and the reply was refreshingly unglamorous — the translation from a real problem into a formal one is lossy, you won't get every constraint right, and you do it anyway because the algorithms can't run on a vague description.
 

Exact Answers: Future Cost, Exhaustive Search, and Caching

 

Exhaustive search is introduced the plain way first: try everything, keep the best (21:09). What he actually builds has a bit more machinery, and he flags that it's deliberate overkill meant to pay off in later weeks on MDPs and games.
 

The central definition is future cost (21:56): a function on a state giving the cost of the cheapest route from that state to an end state. Once you have it, the answer to the whole problem is just its value at the start state. And it has a one-line recurrence, because any solution has to begin with some first action, after which you're at a successor state with the same problem one size smaller. So future cost is the minimum over successors of the immediate action cost plus the future cost of wherever you landed. End states cost zero, since being finished is free.
 

The code returns full solutions rather than bare numbers, which is the right instinct — "42" as a cost is useless without the actions that achieve it. Tracing the toy problem by hand, he reports nine states explored to cover four distinct states. That gap is the whole motivation for what comes next.
 

Two honest limitations get stated up front. Time is exponential in the number of states in the worst case, which he demonstrates by watching the explored count balloon as he grows the problem. Memory is gentler, just linear in the length of the solution, carried implicitly by the recursion stack. And then the nasty one: if the graph has cycles, this recurrence doesn't terminate. It's not merely slow, it's ill-defined.
 

The fix offered for now is a hack, and he owns the word. Fold the step count into the state, which kills cycles because time only moves forward; then declare isEnd true once the step count passes a threshold, and hand out infinite cost to anything that overruns, so the minimum never selects it. A student asked how to pick that threshold without accidentally excluding the optimal solution, and the answer was that there's no general rule — look at your problem. With positive costs the number of states is a loose upper bound; with negative costs you can get a negative cycle where looping forever keeps driving cost down, and that's degenerate enough to just return minus infinity. Real handling of cycles is deferred: uniform cost search on Wednesday, value iteration for MDPs next week.
 

Dynamic programming arrives as the punchline to a student's suggestion (38:37): keep a lookup table. The definition he gives is the cleanest I've heard — dynamic programming is exhaustive search plus caching, nothing more. Three lines change: a dictionary, an early return on a cache hit, and a store before returning. He even mentions you could wrap it in a Python decorator, and explains why he didn't: transparency beats elegance in a first exposure.
 

The terminology detour is worth keeping. Richard Bellman coined it in the 1950s while formalizing Markov decision processes. "Dynamic" means sequential decision-making over time, and "programming" means optimization, not writing Python.
 

The payoff is immediate. Explored states now equals the number of distinct states, and problems that were hopeless a minute ago — n of 100 — solve instantly. A side benefit I'd have missed: the cache ends up holding the best continuation from every state, not just the start, so you get a whole policy's worth of answers for free.
 

Then the brakes (45:12). Memory is more precious than time, because you can always let a program run longer but you can't grow your RAM. Dynamic programming costs memory proportional to the number of states, and if that number is a trillion you simply cannot run it. The second caveat is sharper: caching only helps when many paths converge on the same state. He draws two pictures — a tree where every action reaches fresh territory, where the cache misses every time and you've paid for nothing, versus a lattice with lots of merge points, where the number of paths is exponential but the number of states is linear and caching is transformative.
 

Cheating on Exactness: Best-of-n and Beam Search

 

The pivot to approximation is motivated by state spaces that are too big to enumerate at all: a state that has to remember the whole set of visited locations, or the entire prefix of words generated so far. When exact is unavailable, you look at a subset of actions and accept that you may miss the good stuff.
 

Best-of-n is almost embarrassing in its simplicity (51:33). Roll out a policy — a function from state to action, borrowed from reinforcement learning vocabulary — from start to end, repeat n times, keep the cheapest. The demo uses a uniform policy that picks randomly among successors; a student's word for the cost spread across rollouts was right, you get lucky sometimes and unlucky other times. The stated guarantee is asymptotic: as n goes to infinity you do converge on the optimal solution, provided the policy puts positive probability on every action. He follows it immediately with the bad news, which is that the n required might as well be a centillion.
 

I'd push on that a little. A convergence guarantee that needs exponentially many samples is doing rhetorical work rather than mathematical work, and he seems to know it. What actually saves the method is different: it's embarrassingly parallel. A thousand machines roll out independently with zero communication, and a worker that finishes early just starts another rollout. Simplicity plus parallelism is the real argument. The other real argument is that a uniform policy is the worst case — swap in an informed policy and the whole thing becomes a legitimate baseline.
 

Beam search is the second approximation (58:02). Maintain K partial solutions, expand every action from every one of them, sort by cost, keep the top K, repeat. The analogy is driving at night with headlights: a narrow cone advancing with you, versus exhaustive search as broad daylight where you see the whole landscape.
 

The parameter notes are the useful part. Beam width 1 is just greedy search. Letting the width go to infinity gives you exhaustive search, which is a terrible idea because now you're paying exhaustive search's time and exponential memory. Asked for a good width, he declines to give a number and then gives a soft one: it depends on problem and budget, he's seen anywhere from two or three up to a thousand, and on the order of ten is reasonable for language work. Beam search is deterministic where best-of-n is stochastic; the stochastic cousin is particle filtering, which can run thousands of particles and, like best-of-n, lets a policy act as a prior.
 

The student questions here were better than the algorithm. What happens when one candidate reaches an end state while others are still mid-flight? In his implementation the finished one is carried along in the candidate list without being expanded further, and he points out you probably want that, because finishing first doesn't mean finishing best. And can you kill a partial path whose cost already exceeds a completed solution's? Yes, if all costs are nonnegative — with negative costs you can't, since it might later drop.
 

Language Models as Search Problems, and the Bits That Bugged Me

 

The closing application (1:11:41) reframes a language model as the multiclass classifier from last week, just with something like a hundred thousand classes: input is a prompt, output is a distribution over the next token. Add an optional verifier that scores a finished response as pass or fail — a math problem and a checker for the answer, say — and the goal is a response that passes the verifier while staying likely under the model. Spending compute at inference to get there is what test-time compute means, and he credits the o1 series with popularizing it publicly. He notes that best-of-n sampling is a real technique here, not a toy: there's work showing a small model sampled many times can compete with a much larger one.
 

Casting it into the framework is neat. The state is the prompt plus the response prefix so far. The action is emitting the next token. The cost is the negative log probability of that token, so minimizing cost means maximizing likelihood. And the verifier is smuggled in as a large negative cost bonus for a valid completion — the same trick as the infinite-cost threshold from earlier, which makes for a nice circularity. The demo runs a 0.6-billion-parameter open model locally with top-k truncation over the token distribution, and he's explicit that production systems do all sorts of inference tricks he's skipping; this is for the conceptual link.
 

The summary (1:19:57) is compact enough to memorize: exhaustive search is exact but exponential; caching buys you dynamic programming and dramatic speedups provided the states fit in memory; best-of-n and beam search are heuristics that usually find good solutions and sometimes fail. Then the synthesis he clearly cares about — costs come from learning, search optimizes against those costs, and that combination is a decent recipe for robust AI systems.
 

Three things left me unsatisfied. The threshold question got a shrug, and while I believe the shrug is honest, it means the exact algorithms as presented have a tuning knob the lecture doesn't help you set. The best-of-n convergence claim is formally true and practically close to empty. And the deepest one is the tension I flagged at the start: twenty minutes on how to hand-design state representations, sitting inside a justification built on an essay arguing that hand-designed knowledge loses to general methods. He'd probably say the general method is the search algorithm and the state is just the interface you're required to supply, which is defensible, but it's a distinction the lecture never draws out.
 

Worth saying plainly, though: the arc works. Watch a solver blow up exponentially, notice it's revisiting states, add a dictionary, watch the same problem solve at n=100. That's a good hour, and the fact that the next lecture picks up cycles means the thread continues rather than getting tied off.
 

Content Disclaimer:

This article is for general reference only and does not constitute professional R&D guidance, production process advice or quality certification. All material performance data has specific test premises; readers should verify parameters against actual equipment and working conditions.