The Mathematics of AI Agents, laboratory reader ยท Chapter 9

Searching the Future

A search needs a number for every branch it has not explored. What that number must satisfy, and what it costs to produce, decides what the search can promise.

These four demonstrations follow the chapter's A* search. First the chapter's own traces, one selection at a time. Then the condition that keeps the best route, tested on the chapter's graph and the notebook's graphs, then the condition that keeps the estimate consistent with itself, and finally what an estimate buys and what it costs. Each one changes a declared value and shows which part of the result moves.

Every example in these readers is a constructed teaching example. The probabilities, utilities and cases are declared inputs chosen to make the mathematics visible. They are not measurements of any deployed agent, product or team.

Demonstration 1 of 4

Following the search one selection at a time

What does the search record, select and update at each step, and where does a recorded cost get corrected?

Each step removes the cheapest queue entry and either stops at a goal or generates successors. The recorded cost only ever moves down toward the true cheapest cost, so that half of Equation (9.2) is bookkeeping; the estimate is the half that needs knowledge from outside. In the research workflow every action taken at the wrong stage is a self-loop with a higher cost for the same state, and the strict improvement rule discards it, so the frontier holds one useful state at a time.

Equation (9.2), written in LaTeX: \hat f(v) = \hat g(v) + \hat h(v)

Scroll sideways for the whole equation

g-hat(v) is the cost of the cheapest path to vertex v that the search has found so far (navy), h-hat(v) is the estimate of the cost still to come (hatched), and f-hat(v) their sum, the queue score. A selection removes the entry with the smallest score (ties: smaller g-hat, then label); an expansion generates its successors. A successor is updated only when an edge gives it a strictly lower cost. The three traces are the chapter's: four vertices with edge costs 3, 7, 2 and 3 (vertex B taken as the goal); the two-route graph with a zero estimate; and the research workflow with estimates 2, 1, 1, 0 (search 1 s, fetch 2 s, verify 4 s).

Predict first. In the four-vertex trace, after A is expanded, does B's recorded cost stay at 7?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: Following the search one selection at a time. Step 1 of 4 of the bookkeeping graph (figure 9.1), goal b. Left: stacked bars of recorded cost and estimate for each generated vertex; right: the queue after selecting s.
Trace: Four-vertex bookkeeping graph, Selection: 1st
Constructed example: the chapter's four-vertex trace (edge costs 3, 7, 2 and 3, where 7 becomes 6), its two-route zero-estimate table and its research workflow (costs 1, 2, 4; estimates 2, 1, 1, 0), each checked against the laboratory's A* function.

Calculated values

Selected
s
Recorded cost g, score f
0, 0
Expanded so far
s
Edges examined so far
2
Frontier, next first
A (3), B (7)

Select s: f = 0 + 0 = 0. A gets g = 0 + 3 = 3 and f = 3 + 0 = 3. B gets g = 0 + 7 = 7 and f = 7 + 0 = 7.

Worked steps

  1. Select s: f = 0 + 0 = 0.
  2. A gets g = 0 + 3 = 3 and f = 3 + 0 = 3.
  3. B gets g = 0 + 7 = 7 and f = 7 + 0 = 7.
  4. Frontier, next first: A 3, B 7.

Use the idea

When an agent reaches the same state by two sequences of tool calls, keep one best cost for that state and update it only when a strictly cheaper sequence appears. The record is then a trustworthy upper bound.

Where the conclusion applies

Edge costs are fixed, known and positive, and a repeated vertex is the same state however it was reached. That fails when the cost of a step depends on the history, for example a deadline or a tool whose price changes with use. The bookkeeping graph names no goal in the chapter; B is taken as the goal here so that the trace ends.

Common wrong turn: The recorded cost is a guess
The chapter separates the two halves. The recorded cost is a record of work done: it can only be too high, and it falls when a cheaper route turns up (7 becomes 6). The guess about what remains lives in the estimate.
What this does not settle

The worked guarantees here assume fixed, known positive edge costs. An agent can sometimes construct such a model, but uncertain latency or history-dependent costs require additional modeling.

Chapter 9 source: "What this does not settle".

Check your understanding: If the edge from A to B cost 2 and the direct edge from s to B cost 7, what would B's record become after A is expanded?
3 + 2 = 5, which is strictly below 7, so the record falls to 5 and A becomes B's parent.

Chapter 9 source: section "The trace, worked". Demonstration C09-D01.

Demonstration 2 of 4

One overestimate can hide the cheaper route

How far can the estimate at one vertex exceed its true remaining cost before the search returns the dearer route, and which vertices does the exact f single out?

A vertex is expanded only while its score is at or below the rival route's score. An estimate at or below the true remaining cost keeps it well inside that limit; one far above pushes it past, the rival goal is selected first and the cheap route is never examined. Between the two the condition is broken yet the best route can still come back, so the condition is a guarantee, not a symptom detector. The right panel shows Equation (9.1): f equals the optimal cost on every vertex of an optimal path and exceeds it everywhere else.

Equation (9.1), written in LaTeX: f(v) = g(v) + h(v)

Equation (9.3), written in LaTeX: \hat h(v) \le h(v) \text{for every vertex } v

Scroll sideways for the whole equation

g(v) is the cost of the best path from the start to v and h(v) the cost of the best path from v onward to a goal, so f(v) = g(v) + h(v) is the cost of the best route forced through v. h-hat(v) is the estimate. A queue score is cost so far plus estimate and the search removes the smallest first. The cases: the chapter's two-route graph (costs 1, 9, 1, 24; true remaining costs 9 at a and 24 at b), the notebook graph (S to A 1, A to G 4, S to B 2, B to G 1; true remaining cost 1 at B), and the notebook's transfer graph (2, 2 and a direct 7; true remaining cost 2 at the middle vertex). The estimate level is applied to the cheap route's first vertex.

Predict first. In the chapter's two-route graph the true remaining cost at a is 9. Set the estimate at a to its largest level, 25. Does the search return the cost-25 route?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: One overestimate can hide the cheaper route. Left: queue score of a against its estimate with the rival route's score as a dashed line and the expansion region hatched. Right: exact f for each vertex, teal on an optimal path. With estimate 9 the route returned costs 10.
Graph: Chapter two-route graph, Estimate at the cheap route's first vertex: Exact
Constructed example: the chapter's two-route graph (costs 1, 9, 1, 24), the laboratory notebook's default and changed graph (heuristic at B 1 and 10) and transfer graph (zero estimates), with other estimate levels defined for this reader; every search is also run through the laboratory's A* function.

Calculated values

Score of a: g + estimate
10
Equation (9.3) holds everywhere
yes
Vertices expanded
s, a
Generated but unexpanded
b
Route returned
cost 10 (optimal, best is 10)

Exact f: s = 0 + 10 = 10, a = 1 + 9 = 10, b = 1 + 24 = 25, goal_a = 10 + 0 = 10, goal_b = 25 + 0 = 25. Vertices with f = C* = 10 (on an optimal path): s, a, goal_a. Score of a = 1 + 9 = 10 against the rival route's 25. The estimate at a is at or below its true remaining cost 9, so Equation (9.3) holds and the search returns cost 10, the best. Admissible estimates can save expansions but cannot lose the best route.

Worked steps

  1. True remaining cost at a is h(a) = 9; the estimate is 9.
  2. Equation (9.3): 9 <= 9 is true.
  3. Score of a = 1 + 9 = 10; the rival route scores 25.
  4. a is expanded (it is expanded only when its score is at most 25).
  5. Route returned costs 10; the best costs 10.
  6. Exact f = g + h equals C* = 10 on s, a, goal_a.

Use the idea

Before describing a search as optimal, ask whether any estimate in it can exceed the true remaining cost. One high estimate on the wrong branch is enough to lose the best route. The notebook's changed case and transfer case are the third and fourth levels of the notebook graph and the first level of the transfer graph.

Where the conclusion applies

The graphs, costs and queue rules are fixed as stated. A broken Equation (9.3) can still return the best route, as the middle levels show, and on other graphs the threshold would differ. Ties in score are broken by smaller cost so far, then by label. Only one vertex's estimate is varied; the others keep the case's values.

Common wrong turn: An overestimate always loses the best route
The chapter says an overestimate need not cause a wrong answer on every graph; it removes the general guarantee. In the two-route graph an estimate of 20 at a still returns the cost-10 route, and only 25 loses it.
What this does not settle

A learned predictor needs a certified uniform error bound over the relevant domain to justify claiming admissibility everywhere. Subtracting the largest overshoot in a test set bounds those observed errors only; an unseen state can exceed it.

Chapter 9 source: "What the two conditions are really asking of a designer".

Check your understanding: In the notebook graph the rival route through A reaches G at cost 5 and B has recorded cost 2. What is the largest estimate at B that still lets B be expanded before that goal is selected?
B scores 2 + h-hat(B) and the goal scores 5, so h-hat(B) <= 3. At 3 the scores tie at 5 and B wins on smaller recorded cost (2 against 5). Above 3, the cost-5 route is returned although 3 was available.

Chapter 9 source: section "The condition that makes it correct". Demonstration C09-D02.

Demonstration 3 of 4

An estimate must not contradict itself

How far may the estimate fall across an edge before it breaks the consistency condition?

Consistency says the estimate may not fall by more than the edge costs. Across the upper edge the start's estimate of 8 meets an edge cost of 6, so the upper vertex needs an estimate of at least 2. At 1 the estimate falls by 7 across a cost of 6, and the vertex's score of 7 dips below the start's own 8. The estimate may also stay unchanged across an edge: consistency limits the drop and does not require progress. The fragment shows the contradiction and nothing more.

Equation (9.4), written in LaTeX: h(u,v) + \hat h(v) \ge \hat h(u)

Equation, written in LaTeX: \hat h(u) \le \operatorname{cost}(u,v)+\hat h(v)

Scroll sideways for the whole equation

u and v are neighbouring vertices joined by an edge. h-hat(u) and h-hat(v) are the estimates at each end, cost(u,v) is the edge cost, and h(u,v) is the true cheapest cost from u to v. In this fragment u is the start and each edge is the cheapest way across, so the two coincide. The drop is h-hat(u) minus h-hat(v). The lower vertex's estimate is fixed at 5.

Predict first. Set the start's estimate to 8 and the estimate at the upper vertex to 1. Which vertex is selected first, and is its score below the start's estimate of 8?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: An estimate must not contradict itself. Left: for each edge out of the start, the drop in the estimate against the edge cost; the upper edge is consistent. Right: queue scores 7 and 8 against the start's estimate 7.
Estimate at the upper vertex: 1, Estimate at the start: 7
Constructed example: the chapter's consistency fragment (start estimate 8, edges costing 6 and 3, estimates 1 and 5), with the start's estimate and the upper estimate varied; the consistency flag is also checked with the laboratory's A* function.

Calculated values

Upper edge: drop, cost
6, 6
Lower edge: drop, cost
2, 3
Consistent on both edges
yes
Scores: upper, lower
7, 8
Selected first
upper vertex

Upper edge: 7 <= 6 + 1 = 7 is true, because the estimate drops by 7 - 1 = 6 across an edge costing 6. Lower edge: 7 <= 3 + 5 = 8 is true. The estimate never falls by more than an edge costs, so the fragment is consistent. The upper edge is exactly tight: the estimate drops by as much as the edge costs. Selected first: upper vertex, with scores 7 (upper) and 8 (lower). No selected score is below the start's estimate of 7.

Worked steps

  1. Upper edge: the estimate goes from 7 to 1, a drop of 6; the edge costs 6.
  2. Equation (9.4) in edge form: 7 <= 6 + 1 = 7 is true.
  3. Lower edge: 7 <= 3 + 5 = 8 is true.
  4. Scores: upper 6 + 1 = 7, lower 3 + 5 = 8.
  5. Selected first: upper vertex.

Use the idea

When two estimates are produced separately for neighbouring states, compare their difference with the cost of the step between them. A difference larger than the step is a sign that the estimator disagrees with itself.

Where the conclusion applies

Only the local fragment is drawn: no goal routes are shown, so it cannot tell you whether either estimate is admissible, which route is best, or whether a vertex will be reopened. A consistent estimate can still be wrong about the remaining cost; it only cannot be wrong in a self-contradicting way.

Common wrong turn: An inconsistent estimate means the route is wrong
The chapter says the fragment shows a score decrease, not a suboptimal route or an actual reopening: selecting the first successor can still be the right choice. Consistency prevents a kind of score reversal; it does not prove that an action advances the task.
What this does not settle

Without the onward paths to goals, it does not establish which route is optimal, whether the estimates are admissible, or whether any vertex will need reopening.

Chapter 9 source: "The condition that makes it efficient".

Check your understanding: If the start's estimate is 8 and the upper edge costs 4 instead of 6, what is the smallest estimate at the upper vertex that satisfies consistency?
8 <= 4 + h-hat(upper) requires h-hat(upper) >= 8 - 4 = 4.

Chapter 9 source: section "The condition that makes it efficient". Demonstration C09-D03.

Demonstration 4 of 4

What an estimate buys and what it costs

How many expansions does an estimate save compared with guessing zero, and does that pay once computing the estimate costs time?

Time is expansions times 200 ms plus estimates computed times the price. An admissible estimate always returns the same route cost as the zero estimate, and under Theorem 2's conditions it expands a subset of what the zero estimate expands; the saving is the difference. The estimate pays only while that saving, 200 ms per expansion avoided, exceeds what the estimates cost, so the search that expands the fewest vertices can be the slowest to finish.

Equation (9.2), written in LaTeX: \hat f(v) = \hat g(v) + \hat h(v)

Equation (9.4), written in LaTeX: h(u,v) + \hat h(v) \ge \hat h(u)

Scroll sideways for the whole equation

f-hat(v) = g-hat(v) + h-hat(v) must be computed for every vertex the search generates, and computing h-hat is not free. An expansion is one tool call and costs 200 milliseconds (ms); one estimate costs the chosen price. The zero estimate guesses 0 everywhere, costs nothing to compute and is admissible, so it turns A* into uniform-cost search. The informed estimate is the notebook's (3, 4, 1, 0), the two-route graph's exact values at a and b, or the research workflow's structural values (2, 1, 1, 0). Estimates computed is one at the start plus one each time a cheaper route to a vertex is queued.

Predict first. In the research workflow, how many expansions does the structural estimate save compared with the zero estimate?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: What an estimate buys and what it costs. Left: a grid showing which vertices each search expands and in what order. Right: total time of the two searches; with the estimate 4000 ms against 600 ms for zero.
Graph and informed estimate: Notebook graph, exact estimate, Time to compute one estimate (ms): 900
Constructed example: the chapter's constructed agent latencies (a 200 ms tool call, a 900 ms estimate) applied to the notebook graph, the chapter's two-route graph and its research workflow, with expansions counted by the chapter's queue rules and checked against the laboratory's A* function.

Calculated values

Expansions, with and without
2 and 3
Estimates computed
4
Total time, with and without
4000 ms and 600 ms
Break-even price per estimate
50 ms
Verdict
estimate loses

Time with the estimate = 2 x 200 + 4 x 900 = 4000 ms; with the zero estimate (free to compute) = 3 x 200 = 600 ms. The estimate loses 3400 ms: the search that expands fewest vertices (2) is not the one that finishes soonest, which is the chapter's point that fewest expansions need not mean least total resources. Break-even price = 1 x 200 / 4 = 50 ms per estimate. Every vertex expanded with the estimate is also expanded by the zero-estimate search (S, B inside S, A, B), as Theorem 2's corollary says when the estimate is consistent and there are no ties. Both return the same route cost, 3.

Worked steps

  1. Expansions: 2 with the notebook estimate (exact) (S, B) and 3 with zero (S, A, B).
  2. Estimates computed with the estimate: 4 (one at the start, one each time a cheaper route is queued).
  3. Time with the estimate = 2 x 200 + 4 x 900 = 4000 ms.
  4. Time with zero = 3 x 200 = 600 ms.
  5. Expansions saved = 1; break-even price = 1 x 200 / 4 = 50 ms.
  6. The estimate loses 3400 ms: the search that expands fewest vertices (2) is not the one that finishes soonest, which is the chapter's point that fewest expansions need not mean least total resources.

Use the idea

Price the estimate in the same unit as the step it is meant to avoid. If scoring a candidate takes a model call, compare it with the tool call, and consider scoring candidates in batches or only when the choice is close.

Where the conclusion applies

Constant costs per call, and expansion counts that come from these small graphs, not from measurement. Queue work, storage and batching are left out. The 200 ms figure and the 900 ms estimate are the chapter's constructed example; 100 and 400 ms are values chosen for this reader. Theorem 2 compares algorithms with the same information, no ties and a consistent estimate.

Common wrong turn: The search that expands the fewest vertices finishes soonest
The chapter quotes the paper: the procedure that is optimal in minimum vertices expanded might not be optimal in minimum total resources expended, because the estimate has to be computed whenever a vertex is generated.
What this does not settle

Theorem 2 holds only against algorithms with the same information, no ties, and a consistent estimate, which is a narrower class than the phrase optimal search suggests.

Chapter 9 source: "What this does not settle".

Check your understanding: In the notebook graph the estimate saves one expansion and needs 4 estimates. What is the most one estimate may cost for the estimate to break even?
1 x 200 / 4 = 50 ms per estimate. Above 50 ms the zero-estimate search is faster; below it the estimate pays.

Chapter 9 source: section "When the estimate costs more than the vertex". Demonstration C09-D04.