Testing Hypotheses with Knowledge Networks

When does a prerequisite network make a hypothesis cheaper to test? We study one conjunction of binary hypothesis under supplied prerequisite rules and fresh noisy queries, with validity required at every legal state. On a directed acyclic graph allowing at most $r$ failed rules, the verification cost at a supplied legal ideal $I$ is ${\Theta }_{\eta }(C_r(G[I],S)\log (1/\delta ))$ at every confidence level $\delta \le 1/4$, uniformly in the graph, where $C_r(G[I],S)$ is a fractional cover of the low cut missing sets inside $I$. When the mastered witness is unknown and is located through a diagnostic table $E$, the cost is ${\Theta }_{\eta }(\min \{k\log (1/\delta ),{\mathcal{H}}_{\eta }(E)+\log (1/\delta )\})$, where ${\mathcal{H}}_{\eta }(E)$ is the cost of hitting a witness without recognizing it: discovery and confidence add. Over all tables, $h$ diagnostic pairs for $2^h$ witnesses leave a discovery cost of order $h\log (h+1)$, while a constant factor surplus of pairs lowers it to order $h$, even against unbalanced tables and adaptive proposals. The laws survive two relaxations. With $w$ redundant witnesses and at most $r<w$ failed rules, only the confidence term grows, by $w/(w-r)$. With error rates unknown but bounded by a known margin, the optimized resource law is unchanged; this covers sampled outputs graded by exact checkers under a pass rate gap. The converse also requires every grade pattern satisfying the witness inclusions and diagnostic pair incompatibility to be realizable. Pairwise implications of a union closed knowledge space preserve full mastery certificates, but not partial profile ones. Preregistered experiments reproduce the additive law and the diagnostic resource law in simulation and on sampled outputs of language models, and locate where they stop: under persistent errors, and under rules read off difficulty labels.