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

The Path from Prediction to Action

An agent can describe an action without having a route to perform it. Check the route before reading the success rate.

These four demonstrations follow the chapter's controller graph. The first shows how a permission deletes a move and everything beyond it, on the document workflow and on the notebook's transfer workflow. The next three separate numbers that are easy to confuse: what a finite drawing of a random tree can and cannot show about a threshold, whether a path exists, is expected or is completed in a small tree, and how a product of four rates makes a missing path look like a rare one.

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

A permission deletes a move, and the path with it

If one permission is removed, which states can the controller still reach, and does the goal survive?

Each state lists what the model might do next; the grant rule keeps a subset, and the kept moves are the only edges of the graph. The reachable set grows one move at a time from the start state, so a denied move removes the state behind it unless another permitted route leads there. The right panel counts how many states are reached within each step budget, so a controller allowed too few moves loses a state even when a path exists. The notebook's transfer workflow shows the sharpest case: the permitted move into sent cannot help, because the state it leaves is never reached.

Equation (4.1), written in LaTeX: \operatorname{Reach}_G(V_0)=\bigcup_{t\geq0}\operatorname{step}^{t}(V_0).

Equation (4.2), written in LaTeX: \operatorname{Allowed}_{\mathcal G}(v)=\mathcal{G}(\operatorname{Act}(v)).

Scroll sideways for the whole equation

V_0 is the set of starting states (here one state). step^t(V_0) is the set of states reached after exactly t allowed moves, with step^0(V_0) = V_0, and Reach is the union over every t, so a state counts if at least one allowed path reaches it. Act(v) is the set of actions the model might emit at state v, G is the permission system, and Allowed(v) is what survives it. A step number below a state is the fewest moves needed to reach it. The step budget is the most moves the controller may make.

Predict first. Deny the move from review to release. Can the controller still reach release, and which states remain reachable?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: A permission deletes a move, and the path with it. Left: the document workflow with reached states filled and unreached states hatched; no move is denied. Reached: draft, review, release, archive. Right: the number of states reachable within each step budget, with and without the grants.
Workflow and denied move: Document: every move granted
Constructed example: the laboratory's four-state document workflow (draft, review, release, archive), whose denied review to release case is the notebook's changed case, and the notebook's transfer workflow (queued, approved, sent). Counts come from the laboratory's reachability function.

Calculated values

Release reachable with every grant
yes
Release reachable with these grants
yes
States reached
4 of 4
Shortest permitted path to release
draft, review, release
Reached states with no way out
release, archive

step 0 holds {draft}; step 1 adds {review, archive}; step 2 adds {release}. Reach = 1 + 2 + 1 = 4 of 4 states, so states with no permitted path = 4 - 4 = 0. Within 1 move the controller reaches 3 of 4 states. Every grant is given, so Allowed(v) equals Act(v) at every state. Release is reached by draft to review to release, 2 moves, so a controller allowed fewer than 2 moves cannot reach it. The permitted loop review to draft leads to a state already reached, so it adds no state and the search still ends.

Worked steps

  1. Step 0 holds {draft}.
  2. Step 1 adds {review, archive}.
  3. Step 2 adds {release}.
  4. Reach = 1 + 2 + 1 = 4 of 4 states, so states with no permitted path = 4 - 4 = 0.
  5. Every grant is given, so Allowed(v) equals Act(v) at every state.
  6. Release is reached by draft to review to release, 2 moves, so a controller allowed fewer than 2 moves cannot reach it.

Use the idea

When a task fails every time, list the states and moves, mark which moves the controller has a grant for, and search from the real start state before tuning prompts. A missing grant shows up in the list of states and moves; a prompt cannot add it.

Where the conclusion applies

Grants are frozen at analysis time, each arrow stands for a mechanism that really exists, and states are coarse labels. Reachable does not mean likely, cheap or safe, and it does not show that an action happened. If a label hides a distinction the system depends on, such as which evidence a draft holds, the drawn path can be one the real controller does not have.

Common wrong turn: A zero score means a weak model
A model that succeeds 2 percent of the time and a controller that cannot attempt the task both report as failing. The first is a probability problem that more sampling or a stronger model may fix; the second is a reachability problem that nothing of that kind touches. Check the graph before reading the score.
What this does not settle

A path existing means a path exists: it carries no claim that the path is likely, cheap, safe or correct. The graph is also a chosen abstraction, so a label that hides a distinction the system depends on can draw a route the real system does not have.

Chapter 4 source: "What the graph cannot say".

Check your understanding: Suppose a new state, audit, can only be entered from release. With the move from review to release denied, is audit reachable, and how many states does the controller reach in all?
No. Audit sits behind release, and release has no permitted path, so audit is unreachable too. The reached states are draft, review and archive, so 1 + 2 = 3 of the 5 states.

Chapter 4 source: section "Permission is a filter, not an opinion". Demonstration C04-D01.

Demonstration 2 of 4

A finite drawing is not the threshold

At edge probabilities below, at and above the threshold, what does one sampled tree show, and how does that differ from the infinite tree?

Each open vertex has d x p open children on average, so the expected count at depth T is (dp)^T, which is smooth in p. The chance that a depth-4 path exists is also smooth in p, built one level at a time. Only the infinite tree has a sharp change: its survival is zero up to p = 1/2 and positive above. The four draws use the same underlying random numbers at every p, so raising p only opens more edges, yet different draws disagree at the same p.

Equation (4.3), written in LaTeX: \begin{gathered}\Pi_{G,v}(p)=\Pr_p\{|C_p(v)|=\infty\},\\p_c(G,v)=\inf\{p:\Pi_{G,v}(p)>0\}.\end{gathered}

Equation (4.4), written in LaTeX: p_c=\frac{1}{d}.

Scroll sideways for the whole equation

Each vertex of the binary tree has d = 2 possible children, and an edge to a child is open with probability p, independently. The root's open cluster is the set of vertices joined to the root by open edges; Pi(p) is the chance that this cluster is infinite and p_c = 1/d is the smallest p at which that chance is positive. The drawn tree has depth 4, so it has 16 vertices in its bottom row. r_k is the chance that some open path from the root reaches depth k. The expected number of open vertices at depth 4 is (dp)^4.

Predict first. At p = 0.30, below the threshold of 1/2, can a sampled depth-4 tree show an open path from the root to the bottom row?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: A finite drawing is not the threshold. Left: a binary tree of depth 4 drawn with edge probability 0.50 (draw 1); 0 paths of open edges reach the bottom row. Right: two curves against edge probability, the infinite-tree survival that is zero up to one half and the smooth chance of a depth-4 path, with this probability marked.
Edge probability p: 0.50 (at 1/2), Random draw: 1
Constructed example: the chapter's finite samples of an independent binary tree below, at and above the branching threshold (Figure 4.3), here with edge probabilities 0.3, 0.5 and 0.7 and four fixed draws defined for this reader.

Calculated values

Open paths to the bottom row in this draw
0
Expected open paths at depth 4, (dp)^4
1.000
Chance a path to depth 4 exists
0.450
Chance one committed run finishes, p^4
0.0625
Chance the root's cluster is infinite
0.000
Edge probability against 1/2
at the threshold

Expected open paths at depth 4 = (d x p)^4 = (2 x 0.5)^4 = 1.000. The chance that at least one exists follows r0 = 1 and r_k = 1 - (1 - p x r_(k-1))^2: r1 = 1 - (1 - 0.5 x 1)^2 = 0.75; r2 = 1 - (1 - 0.5 x 0.75)^2 = 0.609375; r3 = 1 - (1 - 0.5 x 0.609375)^2 = 0.516541; r4 = 1 - (1 - 0.5 x 0.516541)^2 = 0.449837. This draw shows 0 paths; draws differ, so one drawing is not the regime. The four drawings offered were chosen to differ, so how many of them show a path is not the chance r4 = 0.450. The infinite tree has d x p = 2 x 0.5 = 1, not above 1, so its survival is 0 although this finite tree can still show a path.

Worked steps

  1. Each open vertex has d = 2 possible children; an edge is open with p = 0.5.
  2. Expected open vertices at depth 4 = (2 x 0.5)^4 = 1.000.
  3. Chance one branch gives a depth-k path: p x r_(k-1); two independent branches give r_k = 1 - (1 - p x r_(k-1))^2.
  4. Starting at r0 = 1: r1 = 0.750, r2 = 0.609, r3 = 0.517, r4 = 0.450.
  5. A committed run needs four particular edges open: p^4 = 0.5^4 = 0.0625.
  6. This draw shows 0 open paths to the bottom row.
  7. Infinite survival is 0.000: zero at or below 1/2.

Use the idea

When someone shows one picture of a small random graph as evidence of a regime, ask for the probability law and the depth. A drawing can look connected below a threshold and broken above it; the threshold describes the law, not the drawing.

Where the conclusion applies

A binary tree with independent open edges and a depth of 4. The four draws are fixed random draws, picked from seeds 0 to 59 so that they differ; they are not a measurement. The threshold 1/2 belongs to this graph shape, and real tool failures often share causes, which breaks independence.

Common wrong turn: Reading one drawing as the regime
The number of displayed paths is random in every panel, and finite trees do not deterministically depict infinite-survival regimes. A drawing below the threshold can show a path and a drawing above it can show none.
What this does not settle

The threshold 1/d belongs to a regular tree; other graph families have their own thresholds, and this value does not carry over. The independence assumption is a simplification real systems violate.

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

Check your understanding: In a binary tree with p = 0.5, what is the expected number of open vertices at depth 4, and is the infinite tree's survival positive?
(2 x 0.5)^4 = 1^4 = 1.000 open vertex on average, and survival is 0 because d x p = 1 is not above 1.

Chapter 4 source: section "How many edges are enough". Demonstration C04-D02.

Demonstration 3 of 4

Possible, expected and completed are three numbers

In a small tree, how different are the chance that a path exists, the expected number of open descendants and the chance that a committed controller finishes?

A branch supplies a path when its first edge is open and at least one of its d children edges is open. The d branches are independent, so a path exists unless all of them fail. A committed run needs two particular edges open, which has probability p x p. The expected count multiplies the d x d possible depth-two vertices by p^2. The three quantities answer different questions.

Equation, written in LaTeX: 1-[1-0.6(1-0.4^2)]^2=0.753984.

Equation, written in LaTeX: (dp)^T

Scroll sideways for the whole equation

p is the chance that each edge is open, independently, and d is the number of children per vertex; the tree has depth two. A path exists when at least one chain of open edges runs from the root to depth two. A committed run picks one branch at each level before learning whether its edge is open and stops at the first closed edge. The expected count is a mean number of open depth-two descendants, not a probability. The tree has depth two, so (dp)^T with T = 2 is (dp)^2 = d^2 x p^2. The displayed existence equation is the chapter's instance (d = 2, p = 0.6); the general formula the demonstration computes is 1 - [1 - p(1 - (1 - p)^d)]^d.

Predict first. Set p to 0.4 with 2 children. Is the expected number of open depth-two descendants above or below 1, and is a path then impossible?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: Possible, expected and completed are three numbers. Left: the chance that a path to depth two exists and the chance that a committed run finishes, both against edge probability, with p = 0.6 marked (0.754 and 0.36). Right: the expected number of open depth-two descendants (1.44 at this p) against edge probability, with a reference line at 1.
Children per vertex d: 2, Edge probability p: 0.6
Constructed example: the chapter's binary tree of depth two with p = 0.6 (expected count 1.44, existence 0.753984, committed run 0.36), with p and the child count varied by the same formulas.

Calculated values

Expected open depth-two descendants (d^2 x p^2)
1.44
A path to depth two exists
0.753984
Committed run finishes (p^2)
0.36
Existence minus committed run
0.393984

Each root branch supplies a path with probability p x (1 - (1 - p)^2) = 0.6 x (1 - 0.4^2) = 0.6 x 0.84 = 0.504. The 2 branches are independent, so a path exists with probability 1 - (1 - 0.504)^2 = 1 - 0.246016 = 0.753984. A controller that commits to one branch per level succeeds with p^2 = 0.6 x 0.6 = 0.36. Expected open depth-two descendants = d^2 x p^2 = 4 x 0.36 = 1.44. The expected count 1.44 is a count, not a probability: it can exceed 1 while the chance of a path stays at 0.753984. This is the chapter's constructed example.

Worked steps

  1. A branch needs its first edge open (0.6) and at least one of 2 lower edges open: 1 - 0.4^2 = 0.84.
  2. One branch supplies a path with probability 0.6 x 0.84 = 0.504.
  3. The 2 branches are independent: a path exists with probability 1 - (1 - 0.504)^2 = 0.753984.
  4. A committed run needs two particular edges open: 0.6 x 0.6 = 0.36.
  5. Expected open depth-two descendants = 4 x 0.36 = 1.44.

Use the idea

When someone reports that a search or a tool graph has many possible paths, ask which number they mean: that a route exists, how many are open on average, or how often the actual controller completes one. Each needs different information.

Where the conclusion applies

Independent open edges and depth two. An exhaustive search can realize the existence probability only if it can test every needed edge, revisit branching states and afford the budget; those are extra assumptions. The three-child case applies the chapter's reasoning to a new child count; it is not a number from the book.

Common wrong turn: Treating the expected count as a chance of finishing
The number of open descendants at depth T has expectation (dp)^T. That count is neither the probability that a path exists nor the controller's completion probability, and it is not a grant of free exploration.
What this does not settle

A controller's completion probability depends on which branches it explores, what it observes and its budget; the existence probability is realized only if the controller can test all necessary edges, revisit branching states and afford the search.

Chapter 4 source: "Reachability, expected descendants, and completion".

Check your understanding: In the binary tree with p = 0.5, what is the committed-run probability, the expected number of open depth-two descendants, and the chance that a path exists?
Committed: 0.5^2 = 0.25. Expected count: 4 x 0.25 = 1.00. Existence: each branch gives 0.5 x (1 - 0.5^2) = 0.375, so 1 - (1 - 0.375)^2 = 1 - 0.390625 = 0.609375.

Chapter 4 source: section "Reachability, expected descendants, and completion". Demonstration C04-D03.

Demonstration 4 of 4

Four rates make one edge, and failure logs cannot tell rare from missing

How does tightening one stage, the grant, change the edge probability, the threshold test, the growth of descendants and what a long run of identical failures shows?

Because each rate is conditional on the stages before it, the chain rule multiplies them without assuming independence. Lowering the grant rate scales p by the same factor, so p falls from 0.67032 to 0.29792 when the grant drops from 0.90 to 0.40, and d x p crosses from above 1 to below 1. A grant rate of 0 removes the edge outright. Over a chain of T steps the success probability p^T is tiny whenever p is modest, so many failures in a row look the same whether the chain is rare or absent.

Equation, written in LaTeX: p = p_{\text{format}}\times p_{\text{parse}}\times p_{\text{grant}}\times p_{\text{tool}}.

Equation (4.4), written in LaTeX: p_c=\frac{1}{d}.

Equation, written in LaTeX: (dp)^T

Scroll sideways for the whole equation

p is the chance that one attempted call produces a usable next state. p_format is the chance the call is well formed, p_parse that the parser accepts it given that, p_grant that the permission system grants it given the earlier stages, and p_tool that the tool returns a usable response given all earlier stages. d x p compares p with the binary-tree threshold 1/d = 0.5. (dp)^T is the expected number of open descendants at depth T, while p^T is the chance that one chosen chain of T steps succeeds. A run here is one such chain; the right panel is the chance that n runs in a row all fail.

Predict first. The book lowers the grant rate from 0.90 to 0.40. By roughly what factor does the edge probability p fall, and does d x p stay above 1?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: Four rates make one edge, and failure logs cannot tell rare from missing. Left: horizontal bars for the chance a call has passed the format, parse, grant and tool stages, ending at 0.670. Right: the chance that a growing number of runs all fail, from 1 to 10,000 runs, against a dashed line at 1 for a missing path; for a chain of 3 steps the values at 10 and 10,000 runs are 0.0278 and about 3.7e-1557.
Grant rate p_grant: 0.9, Steps T in one chain: 3
Constructed example: the chapter's rates (0.95, 0.98, 0.80), its grant rates of 0.90 and 0.40 and its depth-twenty ratio (0.90 / 0.40)^20, about 11.057 million; the grant rates 0.70 and 0 and the chain lengths 3 and 10 are values defined for this reader.

Calculated values

Edge success p
0.67032
Open children per vertex (d x p, d = 2)
1.34064
Against the threshold 1/d = 0.5
above the threshold
Expected open descendants at depth 3 ((dp)^3)
2.410
One chain of 3 steps (p^3)
0.30119
Chance 10 runs in a row all fail
0.0278
Chance 10,000 runs in a row all fail
about 3.7e-1557
Grant rate that gives d x p = 1
0.6713

p = 0.95 x 0.98 x 0.90 x 0.80 = 0.67032, so d x p = 2 x 0.67032 = 1.34064, which is above 1, above the threshold in the binary-tree model. The expected open descendants at depth 3 are 1.34064^3 = 2.410, while one chain of 3 steps succeeds with probability p^3 = 0.67032^3 = 0.30119. If each run is such a chain, 10 failures in a row have probability (1 - 0.30119)^10 = 0.0278 and 10,000 have about 3.7e-1557: here a long run of identical failures would be strong evidence against this model. The grant rate that puts d x p at exactly 1 is 0.5 / (0.95 x 0.98 x 0.80) = 0.5 / 0.7448 = 0.6713; a stricter review that lowers the grant rate below that value moves the model below the threshold.

Worked steps

  1. Stage rates: format 0.95, parse 0.98, grant 0.90, tool 0.80, each given the earlier stages.
  2. Edge success p = 0.95 x 0.98 x 0.90 x 0.80 = 0.67032.
  3. Open children per vertex d x p = 2 x 0.67032 = 1.34064, compared with 1.
  4. Expected open descendants at depth 3 = 1.34064^3 = 2.410.
  5. One chain of 3 steps: p^3 = 0.30119.
  6. Ten failures in a row: (1 - 0.30119)^10 = 0.0278; a missing path gives exactly 1.

Use the idea

Before a safety review tightens a grant, write the four rates and compute where d x p lands against the threshold. A change that looks like a modest percentage can move the model across 1/d, and repeating a chain of steps multiplies the loss. When the logs show only failures, inspect the grants and the transition rules: the pattern of failures alone cannot establish that no path exists.

Where the conclusion applies

Constructed rates, an idealized binary tree with independent edges, and a controller that follows one chain. The product gives smooth finite-horizon sensitivity, not a discontinuity; the threshold concerns the infinite-depth model only. Real tools may share failure causes, and real graphs merge or loop. Treating each run as an independent chain with success p^T is a constructed simplification.

Common wrong turn: Identical failures prove the edge is missing
Identical failures can reflect a poor policy, a rare event or a missing route, and a finite run of identical failures does not establish that no path exists. Inspect the actual grants and transitions before concluding that a route is absent.
What this does not settle

The worked permission numbers are constructed, and their independence assumption is a simplification real systems violate. Products of conditional success rates create strong finite-horizon sensitivity without a discontinuity or a universal threshold.

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

Check your understanding: With the grant rate at 0.60 and the other rates as shown, is d x p above or below 1?
p = 0.95 x 0.98 x 0.60 x 0.80 = 0.44688 and d x p = 2 x 0.44688 = 0.89376, which is below 1. This matches 0.60 being under the break-even grant rate of 0.6713.

Chapter 4 source: section "The permission graph, with numbers". Demonstration C04-D04.