Exercise Bank — Agent Architectures and Reasoning
The printed Chapter 3 keeps Exercises 1–6; the bank continues from Exercise 7.
Exercise 7. A team resolves to give its coder agent a hand-authored symbolic model of the repository: one boolean fluent per observable fact — this file compiles, that test passes, the working tree is clean — with F = 60 fluents and A = 25 STRIPS-style operators whose add and delete lists mention exactly four distinct fluents each. In a naive logical axiomatisation of change, every operator requires one frame axiom for each fluent it leaves untouched. (a) How many frame axioms must the team author, and what is the growth law in A and F? (b) Next quarter’s enriched model has F = 200 and A = 80, each operator still touching four fluents; how many now? (c) STRIPS dispenses with the axioms by fiat: any fluent absent from an operator’s delete list is assumed to persist. Exhibit one operator–fluent pair in this repository world for which the assumption is false, and state what the agent would then believe, wrongly, after acting. (d) In one sentence: which of the three costs of deliberation catalogued in Section 3.3 does this arithmetic make concrete, and why does a foundation model lighten it without abolishing it?
Exercise 8. A coder agent’s harness assembles the model’s context afresh each turn: a fixed preamble giving the agent’s role and tools — with no mention of the current task — followed by the most recent w = 6 transcript entries. The transcript opens with a single entry, the user’s instruction “Fix the flaky retry test, and do not touch the public API”, and each completed turn appends exactly two entries: the action the model chose and the observation the tool returned. (a) On which model call is the agent first invoked with no trace of its instruction anywhere in its context? Derive the general formula for a window of w entries. (b) Say, in the chapter’s vocabulary, what the architecture has silently become from that call onward, and predict the fate of the constraint on the public API. (c) Give the minimal repair, stating exactly where the instruction should now live, and name the classical concept of Section 3.5 that your repair implements.
Exercise 9. A coder agent’s edit–test loop costs c = 2{,}000 tokens per iteration, and each iteration makes the failing test pass with probability p = 0.4, independently of every other. The harness stops at the first success or after B iterations, whichever comes first. (a) Compute the probability that the loop succeeds within budget for B = 4. (b) Show that the expected number of iterations consumed is \mathbb{E}[N] = \bigl(1 - (1 - p)^{B}\bigr)/p, and evaluate the expected token spend for B = 4. (c) Find the smallest B for which the loop succeeds with probability at least 0.95. (d) A passing fix is worth V = 10{,}000 tokens of engineer time. Show that, under the model exactly as stated, a rational harness would never stop at all — and identify the assumption whose failure in practice restores the budget’s good sense, taking as your witness the agent of Section 3.6 that retries a broken edit until the budget is exhausted.
Exercise 10. A repository watchdog receives, once a minute, a percept with two fields: build_red (a boolean) and disk_free_gb (a number). It is to be built as a subsumption stack (Section 3.2) of three behaviours, bottom layer first: idle, always applicable, action sleep; rerun-build, applicable when build_red, action rerun; free-disk, applicable when disk_free_gb is below 5, action prune. A higher layer, when applicable, subsumes every layer beneath it. (a) Implement the stack in standard-library Python: a behaviour pairs an applicability predicate with an action, and the agent acts as its highest applicable layer directs. (b) Run it on the six percepts (build_red, disk_free_gb) = (False, 20), (True, 20), (True, 3), (False, 3), (False, 9), (True, 4), in that order, and record the six actions. (c) Delete the free-disk layer and rerun: confirm the agent still acts on every percept, and name the advertised virtue of the reactive family this exhibits. (d) The team now asks that, after any prune, the watchdog verify on its next tick that pruning actually worked — freed space the disk did not already have, which no single reading of disk_free_gb can attest — before it permits a rerun. Prove that no stack over this percept can comply — exhibit two situations that demand different actions yet are indistinguishable to the architecture — then name the minimal thing that must be added, and the architectural family the addition quietly leaves behind.
Exercise 11. DocBot handles every issue labelled docs in the team’s tracker with one pipeline: a flagship-model call drafts a plan (nine steps on average), a second call critiques the plan, an execution loop then makes one edit per step with a model call each and replans after every step with another call each, and a final call reflects on the outcome — 21 model calls and roughly 45,000 tokens per issue. The issue history shows that 90% of docs issues are single-file wording or typo fixes. Continuous integration runs the documentation build and link checker on every pull request, and nothing DocBot produces merges without a green check and a human approval. (a) Place DocBot on the two knobs of Section 3.6, and say which classical family its designers have, perhaps unknowingly, committed to. (b) Dismantle it: propose the cheapest architecture that still serves the remaining 10%, state the escalation trigger you would rely on, and justify each part you remove by naming the external safeguard that makes its removal safe. (c) Your reflex path costs one call and 2,000 tokens, succeeds on 90% of the single-file issues, and escalates its failures — caught by the CI build — to the unchanged full pipeline; multi-file issues go straight there, and the tracker’s labels make the trigger free. Compute the expected calls and tokens per issue under the redesign, and the saving over DocBot. (d) Which single safeguard in the scenario, were it removed, would forbid your dismantling, and why?
Exercise 12 (lab). Choose a model family that ships a flagship and a small fast sibling (Section 3.4). Assemble forty short tasks in two strata you can score automatically: twenty easy and twenty hard instances of one kind of problem — single-step against multi-step code fixes, say, or one-hop against multi-hop questions over a repository you know well (the companion repository’s setup guide describes the setup for labs of this kind). (a) Measure each tier’s success rate and cost per task on each stratum. (b) Feed the measurements into the analysis of Exercise 2 — your own hard fraction, success rates, and costs — and determine which of its three policies your numbers favour, under both the reliable-detection and the leaky-detection assumptions. (c) Report which stratum shows the wider gap between the tiers, and test the chapter’s claim that the model menu is System 1 and System 2 ready-made: near parity on the easy stratum, a widening gap with depth. Record the model identifier and the date beside your results.
Exercise 13. In one afternoon of the software-engineering team’s life, three agents each record a thought and act on it. The first coder: “The nightly build is red because commit 4f2a renamed parse_row without updating its callers; reverting that commit will make the build green. I will revert it.” (In fact the build is red because a CI credential has expired; the rename is harmless.) The second coder: “The linter reports four style warnings in utils.py; clean code is easier to review; I will spend my remaining budget on the warnings.” (The release-blocking test failure it was assigned sits untouched.) The third coder: “Users cannot log in; the logs show the auth worker has crashed; restarting the web front-end will restore login. I will restart the front-end.” (The logs are right, and the front-end is healthy.) (a) Cast each thought as a practical syllogism, identifying the major premise, the minor premise, and the concluded act. (b) One agent holds a false belief, one fails at deliberation, and one fails at means–ends reasoning; say which is which, justifying each in a sentence. (c) For each agent, name the cheapest run-time check that would expose the failure. (d) An auditor examines only whether each stated belief is true. Which of the three failures does the audit miss, and what does that say about grading practical reasoning as though it were theoretical?
Exercise 14. An agent attacks a hard question by sampling m chains of thought independently at nonzero temperature and returning the majority answer, with m odd. Each chain yields the correct answer with probability p; assume, pessimistically, that every incorrect chain lands on the same wrong answer, so that the vote is between two candidates and the majority is correct with probability
P_m \;=\; \sum_{k=(m+1)/2}^{m} \binom{m}{k}\, p^{k} (1-p)^{m-k}.
(a) For p = 0.7, compute P_5. (b) Find the smallest odd m for which P_m \ge 0.9. (c) Compute P_5 for p = 0.4, and state — justifying it from the behaviour of P_m as m grows — what majority voting does for a model systematically inclined towards one wrong answer. (d) An engineer proposes an adaptive spend: sample three chains; if they agree unanimously, return their answer; otherwise sample six more and take the majority of all nine. For p = 0.7, compute the expected number of chains consumed per question and the resulting accuracy, and compare both figures with the fixed m = 9 scheme. What signal is the adaptive rule reading, and which faculty of this chapter is it a first, crude implementation of? (e) Name the assumption every part above leans on, and explain why chains sampled from a single model are exactly where it fails — a hazard Chapter 10 returns to.
Exercise 15. A coder agent’s first draft of a patch is correct with probability q. A critic reviews the draft: a correct draft it nevertheless declares wrong with probability a; an incorrect draft it catches with probability b. Whenever the critic declares the draft wrong, the agent revises: a revised correct draft remains correct with probability r_c, and a revised incorrect draft becomes correct with probability r_w. Drafts the critic passes are left alone. (a) Derive the probability q' that the patch is correct after one critique-and-revise round, and the exact condition under which the round helps (q' > q). (b) The team’s tester is a deterministic suite with total coverage — a = 0, b = 1. Compute q' for q = 0.5 and r_w = 0.4. (c) Now remove the tester and let the model grade its own work: a = 0.25, b = 0.35, r_c = 0.6, r_w = 0.4. Compute q' for q = 0.5 and for q = 0.8; derive the threshold value of q above which this critic is a net harm; and say in one sentence what this implies for bolting intrinsic self-correction onto ever more capable models. (d) With the deterministic suite of (b), the loop now runs up to k rounds, revising after every red run. Derive the probability that the patch is correct after k rounds, and find the smallest k for which it exceeds 0.95.
Exercise 16. The team’s reviewer agent is shown two candidate patches for the same ticket, each preceded by an author line, and emits a chain of reasoning followed by a verdict on which to merge. An engineer suspects the verdict is driven by the author line — “authored by: staff engineer” against “authored by: intern” — rather than by the code. (a) Design the controlled experiment: what is varied, what is held fixed, how the author labels are counterbalanced across pairs, what ground truth is needed for each pair, and the two measurements to record. (b) The experiment is run on 100 pairs in which a hidden test suite judges the intern-labelled patch strictly better. The reviewer selects the staff-labelled patch 68 times; across the 100 chains the author line is mentioned three times; the chains otherwise discuss correctness, style, and coverage, fluently and in detail. State exactly what these numbers establish, and give the correct name for the relation the chains bear to the verdicts. (c) A colleague proposes asking the reviewer, in a follow-up turn, “Did the author line influence your decision?” Explain why the answer settles nothing, whichever way it comes out. (d) Propose the remedy, and say whether it works by improving the reviewer’s reasoning or by removing something from its world.
Exercise 17. Implement the verifier half of a generate-and-test loop for the domain of Exercise 4. Represent an action as a frozen dataclass carrying its name and its precondition, add, and delete sets, and write a function validate(state, plan, goal) returning one of three verdicts: the plan is valid; some step is inapplicable — report the first such step and the facts its precondition lacks; or the plan runs to completion but leaves the goal unmet — report the missing facts. (a) Implement it, standard library only. (b) Run it on three plans the language model has proposed: P_1, the five-step plan of Exercise 4(c); P_2, which skips review — write_patch, run_tests, merge, deploy; and P_3, which is P_1 followed by a second write_patch, because the model helpfully started on the next ticket. Report each verdict. (c) In two sentences: which classical guarantee does this verifier restore to the loop, which can it not restore, and on what does the restored one remain conditional?
Exercise 18. Build a perturbation harness in the manner of GSM-Symbolic (Mirzadeh et al., 2024) for one template problem from the team’s world: “{name} maintains a CI pipeline that runs {n} test suites, each containing {m} tests. Tonight {k} tests were flaky, and each flaky test was executed one extra time. How many test executions did tonight’s run perform?” — ground truth n \cdot m + k. (a) Write a seeded generator, standard library only, that emits matched instances in three conditions: (i) the base instance with constants (n, m, k) = (4, 25, 6); (ii) the same structure with fresh name and numbers; (iii) as (ii), plus one numerically flavoured but irrelevant sentence, such as “Each retry also used 3 extra minutes of runner time.” The answer must be computed programmatically, and the same seed must reproduce the same triple. (b) State the evaluation protocol for a model under test, and the two contrasting accuracy signatures — the pattern that would indict matching on the problem’s surface, and the pattern a method reasoning from its structure would show. (c) Explain why the ground truth must come from the formula rather than from the strongest available model’s answers, naming the finding of this chapter that the shortcut would collide with.
Exercise 19. A vendor pitches DeepPlan, an autonomy upgrade for the orchestrator, as five stages: (i) the model produces a step-by-step plan for the ticket; (ii) the model re-reads and revises its own plan twice, with no external input (“double reflection”); (iii) five whole plans are sampled and the majority plan is adopted (“plan-level self-consistency”); (iv) the adopted plan’s steps are executed end to end, with nothing inspected until all steps have run (“uninterrupted execution”); (v) the model appends a paragraph certifying the run’s success (“metacognitive audit”). No test, validator, or other external check appears anywhere. (a) For each stage, say whether the chapter’s evidence supports it as specified, naming the specific finding or argument that bears on it. (b) Two of the stages are not merely unsupported but defective in their very mechanics; identify them and say precisely why. (c) Redesign the pipeline under the same token budget: give your stages and, for each, the external signal that grounds it.
Exercise 20 (lab). Couple a live model to the verifier of Exercise 17, LLM-Modulo fashion. Describe the domain of Exercise 4 to the model in natural language — facts, actions with preconditions and effects, initial state, and goal — and ask it for a plan; validate the reply; if invalid, allow up to five revision rounds under one of two feedback regimes: bare — “the plan is invalid; try again” — or grounded — the validator’s verdict verbatim, for example “step 2, request_review: precondition tests_pass not satisfied”. A strong model may well solve this five-action domain at the first attempt; if it does so in more than about half your trials, enlarge the domain — add staging, migration, and rollback facts and actions — until first-try validity falls below one half, then run at least twenty attempts per regime. Record, per regime, the distribution of rounds to a valid plan, and, throughout, every case in which an invalid plan arrives wrapped in an assertion of confidence. (a) Report the comparison between regimes and relate it to the chapter’s account of what makes reflection work. (b) Relate the confident-but-invalid cases to the chapter’s account of self-assessment. (c) Quote the transcript moment, if it occurs, where the model repairs precisely the fault the validator named, and say what this shows the model can do with a true error signal that it could not do for itself. Record the model identifier and the date beside your results.