- Rating
- 2
- Confidence
- 3(−1)
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies the noisy query complexity of certifying one conjunctive claim: that all k target nodes of a supplied prerequisite DAG are mastered. Each query returns a fresh BSC-corrupted bit, and validity is required at every legal state, where up to r original edges may fail. Theorem 3.1 shows that verification at a supplied legal ideal costs order Cr log(1/δ), uniformly over graphs, for δ up to 1/4. Here Cr is the fractional certificate complexity of the low cut missing sets. The upper bound samples from the fractional cover and falls back to direct target testing. On two-layer graphs Cr becomes an explicit LP, with the closed form min{k, t/(q minus r)} in the biregular case.
The core of the paper is a private-witness architecture: k targets, t witnesses that each require all targets, and m complementary diagnostic pairs given by a table E. Theorem 4.1 shows the common evaluator cost is order min{ka, Hη(E) + a}, where Hη(E) is the cost of hitting the mastered witness without recognizing it. Theorem 5.1 optimizes over all tables with t equal to 2^h. With m equal to h the hitting cost is order h log(h+1), and a constant-factor surplus of pairs, used as a code, brings it down to order h. The converse holds for every table, including duplicate rows and multiple adaptive proposals.
Extensions cover redundant witnesses with failed rules, where only the confidence term grows, by w/(w minus r). They also cover unknown error rates within a known margin, and contract-graded sampled outputs. Preregistered experiments simulate the procedures on a BSC and replay stored grades from gpt-4o-mini on HumanEval and on 16 synthetic knowledge-configured systems. They test coding against repetition on diagnostic reads of gpt-4o-mini, and they probe two failure modes: persistent errors, and rules read off MATH difficulty labels.
Critical strengths
- The theory is complete and, as far as I can tell, correct. The bounds match, with constants uniform in the graph, the table and δ up to 1/4, and validity holds on the full legal class, not just on the favorable profiles. I redid the key steps myself:
- the stopped change-of-measure lower bound and the block verifier of Algorithm D.3, including the step from (1 minus 1/(2C))^M to δ/2 and the bound kl(1 minus δ, δ) at least L/4;
- the deleted-witness coupling behind Theorem 4.1, with Q at most 10T, success at least 5/8, eleven repetitions and the 110T budget;
- the maximal-leakage envelope and its 0.101 constant;
- the x at least 256 step;
- the Gilbert count;
- the Proposition M.1 reduction.
I also checked Examples C.2 and C.3 and Proposition E.4 directly. This matters because the paper says LLMs drafted its proofs. A paper this long earns trust only if the arithmetic survives an independent pass, and here it does.
- The all-table converse for hitting is the real increment, and the paper says so itself. A fixed table of h noisy diagnostic pairs needs order h log(h+1) queries even to propose the right witness once, while a constant-factor surplus of pairs drops this to order h. The envelope handles duplicate rows, unused signatures and multiple adaptive proposals in a few lines. The coding result also shows up on diagnostic reads of gpt-4o-mini, where rereading cannot repair a persistently misread bit but a code can. The experimental appendix is unusually candid as well: failed predictions are reported as failed, and boundary experiments show where the assumptions break.
Critical weaknesses
-
The practical case for the grade savings rests on a unit cost per query that the paper scopes but does not examine where it matters. To be fair, the paper is explicit that its model excludes batch grading of one sample. Appendix J.1 says the query model "does not cover that batch observation". Section 7 says grading one sample "saves samples, not grades". Appendix K.3 limits the model to evaluations where "each grade is the expensive step or needs its own sample". Table 3 measures the batch alternative. I accept that scoping. My concern is what remains inside it.
Exact rules come from contract inclusion, so the witness checker contains the target checkers. On page 9, around line 434, a witness passes only if the targets and its row's diagnostics all pass on the same output. On HumanEval, page 40 around line 2140, each witness "requires every assert and one HumanEval+ test". In the knowledge systems, page 46 around line 2433, the witness passes "when every target passes". E6a shows the flip side: once the diagnostics are dropped from the witness contract, misread systems fall outside the class.
Yet every query costs one, and the paper never discusses grades whose cost depends on the node. In slow test suites, one of the settings the paper itself names on page 41, a witness grade runs all k asserts plus one more test, so it is at least as costly as the target grades it is meant to save. The knowledge systems answer a 40-item probe in one reply, so they sit in the batch regime the paper excludes. There, Table 3's batch direct test needs 6.4 samples, while the certifier's 32.2 grades each draw a fresh sample.
As my own rough estimate, assume a grade costs as many item checks as it contains. Table 7 then gives 10.9 witness grades of at least 17 items each, plus 5.3 diagnostic reads and 16.3 direct grades, for about 207 item checks against 66.4. The paper reports no such number, and it rests on my assumption.
The upshot is that T1 and E1 confirm the laws in the grade unit, which is what the abstract claims. But no reported instance shows a saving that survives a realistic cost unit. The coding result on diagnostic reads is unaffected, since those reads are atomic. The tension is structural: contract inclusion makes witnesses composite, while atomic witnesses need trusted rules, and the MATH experiment shows those fail.
-
The novelty is moderate relative to known tools, and the significance for an ICLR audience is not established. The paper is candid about this. It calls fractional certificates, sequential information allocation and codes "established ingredients" on page 2, around line 72. It places the m equal to h case next to the order n log n of Feige et al. for reading noisy bits, cites Chung et al. for coding in noisy twenty questions, and names "The all table converse and its testing consequence" as the increment. I agree with that self-assessment. My point is that this increment is a solid but narrow noisy query complexity result.
The constants make it a statement about orders only. The lower constant in H.4, page 33, is 1/(256(1+ℓη)) against K/(1/2 minus η)^2 above. For a fixed table, the margin version leaves a log factor open, page 8 around line 430. Combined with the density of the main text and the small LLM populations, I do not see what an ML practitioner would do differently after reading it. A learning theory venue would weigh the converse more.
Questions for authors
- In what concrete evaluation setting does a witness grade cost about the same as one target grade, while the prerequisite rules still hold exactly? Please report Tables 2 and 4 in atomic checker executions as well as in grades, or state the law under node-dependent query costs. If the certifier still wins under such a unit, my main concern goes away.
- Can you exhibit a natural prerequisite graph where witnesses are atomic items and the rules are exact, or hold up to a modest failure budget r? The MATH difficulty-label experiment suggests the answer may be no, which would narrow the paper's motivation.
- The AI use statement says LLMs drafted the model, claims and proofs, and that the finite checks "are not independent human verification". Did a human author check each proof in Appendices D to J and M line by line? I found no errors in the parts I redid, but ICLR's LLM policy holds authors responsible for LLM-produced content, and the statement does not say this was done.
- In E11 on page 43, the diagnostics certifier at h equal to 4 and δ equal to 0.05 spends 19.4 reads, 4.8 search queries and 7.8 grades on failed checks. Table 7 on page 44 gives 18.2, 4.5 and 7.2. I suspect the E11 figures come from the arm with scanning's boundary, which Table 8 puts at 95.5 against 91.4. But the accepting check is 13.5 in both, and the Table 7 row sums to 87.1 rather than 91.4. Which arm and which runs are these?
- Can the log factor between H^gap and Hη for a fixed table under a known margin be removed, or is there a table where it is necessary?