AI Agents & Tool Use

Question 1

(a) Input cost at step $t$ (steps $1..T$, define $L_1 = L_0 + s$, or index from 0; use $L_t = L_0 + t s$): $C_{\text{in}}(T) = \sum_{t=1}^{T}(L_0 + t s) = T L_0 + s\frac{T(T+1)}{2}.$

• Sum of arithmetic series (2); correct linear + quadratic terms (2).
• Asymptotically $C_{\text{in}}(T) = \Theta(T^2)$ (dominated by $sT^2/2$). (1)

(b) Capping activates when $L_t = L_0 + ts > M \Rightarrow t^\* = \lceil (M-L_0)/s\rceil +$ (first integer exceeding). Before $t^\*$, cost grows as in (a); after, each step costs $M$: $C_{\text{in}}^{\text{cap}}(T) = \sum_{t=1}^{t^\*}(L_0+ts) + (T-t^\*)M.$

• For $T\gg t^\*$ the second term dominates: $C_{\text{in}}^{\text{cap}}(T) = \Theta(T)$ — linear vs quadratic. (2)
• Correct piecewise expression (2); correct $t^\*$ (1).

(c) Geometric distribution with success prob $p$: $\mathbb{E}[T] = \frac{1}{p}, \qquad \Pr(T > B) = (1-p)^B.$

• $\mathbb{E}[T]=1/p$ (2), tail $(1-p)^B$ (2).
• Expected cost: since $C_{\text{in}}(T)=TL_0 + s\,T(T+1)/2$, and for geometric $\mathbb{E}[T]=1/p$, $\mathbb{E}[T^2]=(2-p)/p^2$: $\mathbb{E}[C_{\text{in}}] = L_0\mathbb{E}[T] + \frac{s}{2}(\mathbb{E}[T^2]+\mathbb{E}[T]) = \frac{L_0}{p} + \frac{s}{2}\left(\frac{2-p}{p^2}+\frac1p\right)=\frac{L_0}{p}+\frac{s(3-p)}{2p^2}.$
• Correct use of $\mathbb{E}[T^2]$ (2).

(d) Unbounded loops → quadratic cost blow-up (from a & c) and non-termination when $p$ small (tail decays only geometrically). Guardrails:

• Token/step budget cap (hard max iterations or token ceiling) — bounds cost & guarantees termination. (2)
• Action-level safety guardrail (allowlist of tools / sandbox / human-in-loop confirmation for destructive actions) — bounds impact of a wrong action. (2) These address distinct failure modes: runaway resource use vs. harmful side effects.

Question 2

(a) BNF (integers 1..50 enumerable, so range is CFG-expressible by enumeration):

<call>   ::= '{"name":"search","arguments":{"query":' <str> ',"limit":' <int> '}}'
<str>    ::= '"' <chars> '"'
<chars>  ::= '' | <char> <chars>
<char>   ::= any escaped JSON char
<int>    ::= <1-9> | <1-9><0-9> | ...   ; enumerate 1..50 explicitly

• Structure fixed by literal tokens (2); integer range via enumeration of 1..50 (a finite regular set, hence CFG) (2).
• The constraint a pure CFG cannot express: string content restrictions that require matching/counting or semantic validity — e.g. that query be non-empty and balanced-escaped is fine, but cross-field constraints or "limit must not exceed number of available results" require a validator. Accept: "arbitrary length numeric ranges with unbounded digits" or "cross-field/context-sensitive constraints." (2)

(b) Conditioning: By definition of conditional probability with event $E=\{\text{token}\in A\}$, $p(v\mid E) = \frac{p(v \cap E)}{p(E)} = \frac{p(v)\mathbb{1}[v\in A]}{\sum_{u\in A}p(u)},$ since $p(v\cap E)=p(v)$ if $v\in A$ else $0$, and $p(E)=\sum_{u\in A}p(u)$. This is exactly $p'(v)$. (3)

Sequence mass: For a full valid sequence $y=(y_1,\dots,y_n)$ where every $y_i$ is allowed given prefix, unconstrained prob $P(y)=\prod_i p(y_i\mid y_{<i})$; constrained $P'(y)=\prod_i \frac{p(y_i\mid y_{<i})}{Z_i}$ where $Z_i=\sum_{u\in A_i}p(u\mid y_{<i})\le 1$. Hence $\frac{P'(y)}{P(y)} = \prod_i \frac{1}{Z_i} \ge 1.$ Wait — this increases the valid sequence's probability (mass redistributed toward allowed tokens). Correct statement: masking never decreases the probability of a valid sequence; the mass removed from invalid tokens is redistributed to valid ones. Award marks for correct derivation of the ratio $\prod 1/Z_i \ge 1$ and the conclusion. (4)

• Equality ($Z_i=1\ \forall i$) holds iff the unconstrained model already placed zero probability on disallowed tokens at every step. (1)

(Grading note: full marks for the derivation showing valid sequences are up-weighted with the correct equality condition; the direction of the inequality is the key insight.)

(c)

import numpy as np
def mask_logits(logits, allowed_ids):
    masked = np.full_like(logits, -np.inf)
    masked[allowed_ids] = logits[allowed_ids]
    m = np.max(masked[np.isfinite(masked)])      # stable shift
    exp = np.exp(masked - m)                       # disallowed -> exp(-inf)=0
    return exp / exp.sum()

• Correct masking + returns normalized distribution (3).
• Why $-\infty$ before softmax: (i) guarantees masked tokens get exactly zero probability after normalization with no floating residue; (ii) zeroing after softmax requires re-normalizing (extra pass) and can leave tiny numerical mass; (iii) the pre-softmax shift by max keeps exponents bounded — zeroing post-hoc still computed unstable exponents for huge disallowed logits first. (2)

(d) Example: schema-valid call {"name":"delete_file","arguments":{"path":"/"}} — syntactically perfect but semantically catastrophic; or search(query="", limit=50) valid grammar but empty query. Complementary layer: runtime validator / policy guardrail (semantic argument validation + action allowlist / dry-run). (3)

Question 3

(a) Critical path = longest-weight path from any source to any sink in the DAG; its length lower-bounds makespan because those tasks are strictly sequential (each depends on the previous), so no scheduling can overlap them → makespan $\ge$ CP. With unlimited workers, list-scheduling by "start each task as soon as predecessors finish" achieves start time = longest path into the node, so finish = CP length → makespan $=$ CP. (3)

For the DAG (unit costs), longest paths: $A\!\to\!B\!\to\!D\!\to\!F = 4$; $A\!\to\!C\!\to\!D\!\to\!F = 4$; $A\!\to\!C\!\to\!E\!\to\!F=4$. Critical-path length = 4. (2)

Level schedule (ASAP): L0={A}, L1={B,C}, L2={D,E}, L3={F}. Max width = 2 → 2 workers suffice to hit makespan 4. (2)

(b) Let success indicator $S\in\{0,1\}$ over tasks, mean success rate $\bar S$; token cost $c$. Report them separately, then a combined score e.g. $\text{Score} = \bar S \cdot e^{-\lambda \bar c},\quad \text{or}\quad \bar S - \lambda\,\bar c.$

• Separated metrics (2); sensible combined scalar (2).
• Naive $\bar S/\bar c$ is gamed by an agent that fails cheaply: return trivial near-zero-cost answers → tiny denominator inflates ratio even at low success. Corrective term: gate on a minimum success threshold, or use $\bar S - \lambda \bar c$ (additive penalty, so failing cheaply gives low score) rather than a ratio. (2)

(c) Proposal wrong with prob $e$. Critic independently catches a wrong proposal with prob $(1-q)$ (misses with prob $q$). A wrong proposal survives only if critic misses: $e_{\text{final}} = e\cdot q < e \quad (q<1).$

• Derivation $e_{final}=eq$ (3).
• If the critic also rejects correct proposals (false positives), or catches wrong ones (add: net improvement requires false-positive rate low). Key assumption for usefulness: critic errors must be (approximately) independent of proposer errors — if both share the same blind spot ($q\to 1$ exactly on the cases the proposer gets wrong), the critic catches nothing and $e_{final}=e$. (2)

[
  {"claim":"E[C_in] for geometric T equals L0/p + s(3-p)/(2 p^2)",
   "code":"p,L0,s=symbols('p L0 s',positive=True); T=symbols('T'); ET=1/p; ET2=(2-p)/p**2; expr=L0*ET + Rational(1,2)*s*(ET2+ET); result=simplify(expr-(L0/p + s*(3-p)/(2*p**2)))==0"},
  {"claim":"Uncapped input cost sum_{t=1}^{T}(L0+ t s)=T*L0 + s*T*(T+1)/2",
   "code":"t,T,L0,s=symbols('t T L0 s'); S=summation(L0+t*s,(t,1,T)); result=simplify(S-(T*L0+s*T*(T+1)/2))==0"},
  {"claim":"Critical path length of the DAG is 4",
   "code":"import networkx as nx; G=nx.DiGraph(); G.add_edges_from([('A','B'),('A','C'),('B','D'),('C','D'),('C','E'),('D','F'),('E','F')]); L=nx.dag_longest_path_length(G)+1; result=(L==4)"},
  {"claim":"Critic reduces error: e*q < e for q<1, e>0",
   "code":"e,q=symbols('e q',positive=True); result=simplify((e - e*q))==simplify(e*(1-q)) and bool((e*(1-q)>0).subs({e:Rational(1,2),q:Rational(1,3)}))"}
]