acceptodds
Under review as a conference paper at ICLR 2027

Testing Hypotheses with Knowledge Networks

Abstract

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 failed rules, the verification cost at a supplied legal ideal is at every confidence level , uniformly in the graph, where is a fractional cover of the low cut missing sets inside . When the mastered witness is unknown and is located through a diagnostic table , the cost is , where is the cost of hitting a witness without recognizing it: discovery and confidence add. Over all tables, diagnostic pairs for witnesses leave a discovery cost of order , while a constant factor surplus of pairs lowers it to order , even against unbalanced tables and adaptive proposals. The laws survive two relaxations. With redundant witnesses and at most failed rules, only the confidence term grows, by . 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.

Primary area:
learning theory
Keywords:
sequential hypothesis testing, knowledge space theory, prerequisite graphs

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_4cnKOpenReview ↗
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
  1. 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.

  1. 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
  1. 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.

  2. 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
  1. 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.
  2. 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.
  3. 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.
  4. 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?
  5. 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?
Reviewer_78yFOpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies the following problem: how to determine whether a specified set of binary variables are all true when each observation can be wrong? It assumes that implications between the variables are supplied as a directed acyclic graph, so establishing truth of one variable can sometimes establish the truth of several others. The goal is to characterize the number of observations needed to reach a decision with a prescribed error probability, including the cost of finding which variables are useful to query.

The paper gives matching upper and lower bounds on the number of observations needed when a reference assignment of the variables is supplied. For a particular class of implication graphs, it also characterizes the cost of finding a variable whose value establishes the entire claim, and shows how additional variables encoding its location can reduce this cost. It extends these results to some violations of the implications and uncertainty about observation noise, and illustrates them with simulations and controlled language-model experiments. The efficiency bounds concern specified favorable assignments, while correctness is required for every allowed assignment.

Critical strengths

I am not from the area, but apparently the presented results are novel and so is the proof technique used for the diagnostic-budget lower bound, which covers arbitrary diagnostic tables and adaptive procedures that need only query the useful variable without identifying it.

Critical weaknesses

The paper is written in a very cryptic way and, to this reviewer, close to impenetrable. This starts in the abstract and introduction, which states technical conclusions right away before adequately explaining the context, the problem, the terminology, or any underlying assumptions. In my opinion, with such a writing style only very few experts will be able to comprehend and benefit from the paper and I am strongly opposed to accepting it for ICLR.

Let me also say that the paper looks LLM-generated to me, from the writing style. I am not claiming it is because this is obviously impossible to prove, I am only saying that's what it looks like to this reviewer.

Which brings me to the author's AI declaration. They say that AI was used intensely to develop the proofs, to carry out the experiments, and to write the paper. What they do not say clearly, in contrast, is to which extend they actually checked the proofs and the writing. They only state that they take responsibility. In my opinion, this is not enough. The AI declaration is just as cryptic as the rest of the paper. For me, this is another reason for rejection.

Questions for authors

Please describe very clearly and in full detail what your (human!) contributions were to carrying out the research and to writing the paper.

Please also say whether you would be willing to rewrite the paper to make it more accessible. As a proof, you might want to include in your rebuttal (part of) a rewritten introduction accessible to a more general ICLR audience.

Reviewer_G8UpOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
1(−1)
Soundness
3
Read review
Paper summary

The paper studies the noisy query complexity of testing whether a system masters every capability in a specified target set, given a supplied prerequisite graph. Correctness is required at every legal state, while efficiency is evaluated at specified favorable states.

For a supplied legal reference profile, the paper characterizes verification cost through a fractional cover of admissible missing sets, including robustness to a bounded number of failed prerequisite rules. Its central discovery result concerns private witnesses and a diagnostic table: the optimal testing cost is, up to noise-dependent constants, the minimum of direct target testing and an additive combination of unrecognized witness-discovery cost and confidence cost.

The paper then optimizes over diagnostic tables for 2h2^h witnesses and proves a matching resource tradeoff. Exactly hh diagnostic pairs require order hlog⁡(h+1)h\log(h+1) observations, while a constant-factor surplus permits order hh. The converse covers arbitrary tables and adaptive witness proposals. Further results address redundant witnesses, failed rules, and channels with a known error margin.

The theory is supported by controlled simulations and experiments using stored, exactly graded language-model outputs. These illustrate the mechanisms and some limitations of the assumptions.

Critical strengths
  1. Theorem 5.1 is the strongest technical contribution. It characterizes the optimal discovery cost over arbitrary diagnostic tables, including duplicate rows, unbalanced signatures, and adaptive queries and proposals. The lower bound applies even when success only requires hitting the correct witness without recognizing it.

  2. Theorem 4.1 shows that unrecognized discovery and high-confidence confirmation contribute additively, while the resulting evaluator remains valid beyond the favorable profiles. The reduction through witness-deleted baselines and the asymmetric checking construction handle this distinction convincingly. The robustness and known-margin extensions are developed with appropriate qualifications.

Critical weaknesses
  1. In the sampled-output experiments, a witness checker evaluates all target conditions and additional conditions, yet its invocation is counted as one grade, just like an individual target check. Consequently, fewer grades need not imply less underlying checking work. The distinction also matters when one generated output can be graded against several targets, as the paper’s batch-grading experiment demonstrates. The query model is mathematically consistent, but an intended evaluation setting in which composite witness queries and individual target queries have comparable cost would make the application claims more compelling.

  2. The HumanEval examples largely eliminate witness discovery, the successful private-witness language-model examples have noiseless diagnostics, and the noisy coding experiment does not establish the asymptotic growth-rate comparison. Much of the sequential evaluation also uses replay from finite stored grade banks. These are useful illustrations, and the manuscript acknowledges many of their limitations, but the main text should distinguish more clearly between validating algorithms on the assumed channel, illustrating diagnostic benefits on empirical channels, and demonstrating savings in practical model evaluation. The dense presentation makes these distinctions harder to assess than necessary.

Questions for authors
  1. In the sampled-output setting, a witness check includes all target conditions and additional conditions. In which intended applications is such a composite check comparable in cost to an individual target check? How should the reported savings be interpreted when target-check computations or generated samples can be shared? Clarifying the resource captured by the query budget would materially affect my assessment of the practical contribution.

  2. Can you describe a concrete intended evaluation setting in which the private-witness structure and informative diagnostic capabilities are available before testing, and explain which evidence in the current study supports this connection? This would help assess how broadly the sharp results apply beyond the constructed knowledge-base examples. The request is for clarification of the present application claim, rather than an additional experimental study.

Reviewer_g8XmOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper tackles an interesting problem intersecting query complexity, knowledge spaces, and active testing, but the presentation is exceptionally dense, convoluted, and difficult to follow. It assumes a massive amount of background knowledge and heavy technical fluency from the reader, frequently burying core intuitions under a barrage of formal definitions, unmotivated notation, and abrupt theorem-proof structures.

Critical strengths

This manuscript studies the noisy query complexity of testing conjunctive hypotheses under prerequisite knowledge networks, introducing various structural and resource bounds such as fractional covers and diagnostic resource laws.

Critical weaknesses
  • Impenetrable Presentation and Organization: The manuscript is currently inaccessible to a general conference audience. The narrative flow repeatedly sacrifices clarity for brevity, packing multiple complex concepts (e.g., fractional certificates, high-cut/low-cut alternatives, martingale concentration under unknown margins) into breathless paragraphs without adequate preamble or high-level takeaways.
  • The paper demands that the reader independently bridge wide conceptual gaps. It often relies on implicit reductions and dense algebraic formulations without providing concrete running examples or intuitive walkthroughs of why a particular bound behaves the way it does.
  • Key definitions and theorems are presented without sufficient grounding in practical or conceptual intuition. The transition between static graph structures (Section 3), dynamic discovery (Section 4), and diagnostic table design (Section 5) feels disjointed because the overarching narrative thread is obscured by notation.

The manuscript requires a major, end-to-end rewrite by a human author focused on pedagogical clarity. Every major theorem should be preceded by a plain-language explanation and a concrete, small-scale running example (such as a simple 2-layer graph or minor diagnostic table) before diving into the formal linear programs or asymptotic bounds. Condense or better organize the heavy notation table and decouple auxiliary technical lemmas from the main flow of ideas to improve readability.

Questions for authors

NA

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.