acceptodds
Under review as a conference paper at ICLR 2027

Same Marginals, Different Query Probabilities: Diagnosing Why Relational Predictors Fail

Abstract

Low-order marginals do not determine the probability of a Boolean query over uncertain relational data: even- and odd-parity laws on four edges agree on every marginal of up to three edges, yet assign different probabilities to the same query. When a relational predictor errs on such a query, a single error number cannot say why. We propose an information-sufficiency audit that separates three failure sources: query-interface loss, the information discarded by the query representation; finite-context uncertainty, the Bayes risk left by finitely many partially observed worlds; and estimator excess, the risk a predictor adds beyond that Bayes risk. We prove that, under exchangeable dependence on a group of any size, two monotone queries have equal probability under every such law exactly when their union-size signatures agree. The signature predicts which query representations lose information: encoding only the edges a query names imposes an error floor of 0.028 on a four-edge conjunction and a two-pair disjunction, while clause counts and sizes fail on four edges only for a class containing star and path queries, a failure that becomes common on larger groups. On a factorial benchmark we compute Bayes risks from exact posteriors and bracket the excess of each learned predictor. On star and path queries, the network given full incidence does not resolve an improvement beyond the shape-only Bayes risk, so its apparent gain from incidence is explained by excess. With ten times more training data, ensembles are no longer resolved above the query-edge Bayes risk; with thirty times more, the ensemble falls below the query-edge Bayes risk by using edges outside the query, on the benchmark and on independent confirmation tasks, whereas the mean single run is not resolved below that risk.

Primary area:
datasets and benchmarks
Keywords:
relational data, distribution shift, information sufficiency, Bayes risk, exchangeability, benchmark

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_qwYCOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies statistical analysis in a situation where we receive sampled truth assignments and a Boolean query over the variables, and we wish to predict the probability that the query is true. This is the case, for example, in query evaluation over probabilistic databases. Using a synthetic benchmark with 16 binary variables divided into four dependency groups of four variables, the paper examines how much prediction error is unavoidable because of limitations in the information supplied to the model, and how well different prediction models learn true dependencies among variables from the sampled assignments. The authors derive error bounds and compare neural models with statistical methods.

Critical strengths
  1. The paper seems to study a fundamental problem in statistical analysis.
  2. The paper includes a thorough set of experimental results.
Critical weaknesses
  1. The paper studies a very narrow problem: the probability of a monotone DNF over four variables, in the context of the specific benchmark that consists of a total of 16 variables. The theoretical propositions are, in fact, specific to this setting.

  2. I found the presentation quite misleading. The paper presents itself as discussing Boolean queries over relational data, and references Dalvi and Suciu, who coined the term and opened a rich line of research. This reference appears in the introduction, and the terminology is already apparent in the title. Yet, the paper has very little to do with probabilistic databases. It applies to DNF inference, which is used in probabilistic databases, but it analyzes the case of 16 variables (corresponding to databases with 16 tuples).

  3. The theoretical analysis is very basic and provides little insight. These are essentially short calculations within the chosen sampling mechanism.

  4. The paper is very hard to read. Even the abstract is very difficult to grasp. It uses very technical terms and does not seem to address the ICLR audience.

Questions for authors

None.

2 comments

The theoretical scope must be distinguished from the experimental dimensions. The two-point bound applies to task pairs with equal input laws and different targets, independent of the number of variables (§3.1; Appendix A). The exchangeable-law characterization is stated for arbitrary finite n (§3.3). Consequently, the assertion that the theoretical propositions are specific to four query variables and a 16-variable benchmark is not a valid restriction on those results as now stated. The standard four-variable parity construction and the finite experimental design do not impose that restriction. This establishes scope, not theoretical novelty or computational tractability.

The task is probability estimation from sampled binary worlds. Possible-world databases provide related semantics; they are not a database-engine evaluation in this paper (§§1–2, 7). The revised abstract and introduction state the actual task explicitly. The appropriate remaining question is whether this task and its diagnostic findings have sufficient significance, rather than whether the paper delivers general database inference.

Standard ingredients do not settle the contribution assessment. We do not claim to invent the squared-loss identity, parity construction or reliability polynomial. Section 2 and Table 23 also credit usable information, PVI and OpenRFM. The specific contribution to assess is the protocol: establish equal available inputs, confirm a target gap, and obtain a risk floor for every predictor restricted to that input. A loss comparison between fitted candidates alone does not establish such a floor.

The revision tests this beyond exact synthetic targets: held-out query outcomes from a school recording confirm 88 of 160 selected encoding-collision pairs (§6.1; Table 5). This is a finite recorded population with generated queries and deliberate encodings, not proof of a deployed model bottleneck. The public-model intervention and audit-inspired selector both have adverse results (§§6.2–6.3; Figure 3); neither is presented as an improvement. Broad practical utility remains open.

Readability has been revised at the entry point. Figure 1 explains probabilities 1/4 and 3/4, their forced common prediction 1/2, and equal-pair MSE 1/16. Figure 2 sets out discovery and confirmation. Proposition 2 and Appendix A.1 specify the extra workload weights and partial-outcome assumptions. The more complex construction moves to the appendix.

We ask that the scope restriction be reconsidered against the stated results, and that any remaining rejection rationale identify which contribution is insufficient after these clarifications and additions. A judgment of limited novelty is distinct from a claim that the results only apply to four variables.

A concrete accuracy decision. For aligned/crossed queries under common shock, Set-shape has probability MSE 0.02105 against an analytic floor of 0.020625. Thus, an MSE target of 0.01 is unattainable for every predictor restricted to that shape interface on this balanced task population, regardless of further training. Set-full with named incidence reaches 0.004814, with a paired difference of -0.01624 and 95% interval [-0.01841, -0.01413] (§5.1, Table 3). The certificate identifies a constraint on attaining a specified accuracy.

An empirical insight about model evaluation. On the support-collision pair, adding incidence increases fitted-model risk by 0.000234, with 95% interval [0.000124, 0.000378], although richer information cannot increase Bayes risk (§5.1). This reversal shows how learner excess can obscure the value of input refinement. The controlled benchmark makes that discrepancy quantitatively checkable.

A procedure when exact targets are unavailable. After fixing the interface and selecting pairs on discovery data, independent confirmation draws supply query-outcome gap bounds. On the school recording, the strongest confirmed gap is at least 0.2284, yielding an equal-pair MSE floor of at least 0.01304 (§6.1, Table 5). The recorded queries use 4-12 variables and connected supports, extending the test beyond the original seven templates. The target population is uniform sampling from the finite recorded bins. This supplies a certificate from observed outcomes under explicit sampling assumptions.

A precise workload-level output. Proposition 2 converts within-class gaps into a weighted catalog-risk certificate using the declared query weights and full encoding-class masses, including overlapping pairs. Proposition 4 extends confirmation to incomplete outcomes through sound truth bounds. These results make the required inputs, scope and confidence explicit. The mathematical tools are established. The contribution claim concerns their specified diagnostic use, controlled calibration and recorded-outcome confirmation. We ask that the significance assessment address these outputs and findings.

Reviewer_qwYCOpenReview ↗

Thank you for the feedback

I received your feedback and plan to consult the other referees about the implications for the recommendation.

Reviewer_AfNQOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies whether a relational predictor has enough information to estimate Boolean-query probabilities. The authors construct a synthetic benchmark where even- and odd-parity mechanisms agree on all marginals through order three but give different probabilities for some queries. They compare query representations based on support, clause shape, and named incidence, and derive error floors for task pairs that each representation cannot distinguish. Experiments with learned models, statistical references, and oracles examine whether the remaining errors come from missing information or from a model failing to use the available signal. In particular, a fourth-moment MLP learns the parity signal under parity-only training, while the set model does not. The paper also shows that detecting a mechanism shift does not necessarily help identify queries with large prediction errors.

Critical strengths

The study is reasonably thorough. The exact query probabilities and the information available to each estimator are clearly specified. The experimental reporting is also detailed, with multiple training runs and paired confidence intervals for the main comparisons.

Critical weaknesses

The theoretical contribution is limited. Proposition 1 follows directly from the squared-loss identity for two indistinguishable tasks, Proposition 2 uses the standard parity construction, and Equation 3 is a conditional-expectation decomposition. The novelty therefore rests mainly on how these ingredients are assembled into an audit. The first two query collisions are also largely determined by construction: support alone cannot distinguish conjunction from disjunction, and clause sizes do not determine clause–edge membership. The experiments are restricted to sixteen edges, four latent groups, and seven query templates. This allows exact references, but provides limited evidence about the relational prediction models that motivate the paper. No existing pretrained relational foundation model is evaluated. It remains unclear whether the audit would reveal comparable failures beyond these examples, or how it would be applied when the mechanism families and exact targets are unavailable. The comparison between the moment MLP and Set-full needs more investigation. The MLP receives explicitly computed moments up to fourth order, and its learning rate and training schedule differ from those of Set-full. The result establishes that the signal is learnable from the observations, but leaves open whether Set-full’s failure persists with further tuning, greater capacity, or a different training schedule under the matched parity prior. The attribution to prior mismatch in Section 5.3 is not cleanly isolated. Cohort T adds odd parity while also adding star/path templates and changing the number of training tasks allocated to each family. The reported reduction of approximately 1.3×10−31.3\times10^{-3} therefore cannot be attributed solely to correcting the mechanism prior. The lower endpoint of the Bayes bracket in Section 5.3 also needs justification. The bracket is reported on the even/odd pool, but the value 0.0001160.000116 comes from an oracle computed under the three-family benchmark prior. More information guarantees a lower Bayes risk when the predictors are optimal under the same evaluation distribution; this argument does not directly apply to an oracle using a different prior. Table 5 reports 0.0000650.000065 for the parity-only oracle. The paper should establish the lower bound under the evaluation distribution used for the bracket.

Questions for authors

Please see the weaknesses above for my main questions and concerns. Several additional points also need clarification.

Section 5.3 attributes the mixed-prior failure to common-shock errors dominating the squared-error objective, whereas Section 4.3 states that the networks are trained with soft-target cross-entropy. What evidence supports this explanation under the actual training objective?

Is there a non-oracle statistical reference that uses all sixteen edges? Partition BMA reads only the query edges, so the comparison with Set-full does not isolate the effect of the estimator from the benefit of additional observations.

Appendix B states that comparisons against deterministic references resample tasks only. Are these confidence intervals intended to be conditional on the fitted ensemble? Would the reported differences remain statistically resolved if training runs were also resampled?

1 comment

We thank the reviewer for this critical prior‑mismatch objection. We acknowledge our original Bayes lower‑endpoint was incorrectly justified under the evaluation prior. We have fixed this error and added matched controlled experiments to address training‑confound concerns. Key revisions are summarized below, with full details moved to the revised main text and appendices.

  1. Corrected Bayes lower endpoint We no longer use a mis‑matched‑prior oracle as a lower bound for the even/odd population. The valid lower reference uses the matching even/odd evaluation prior (estimated risk = 0.00006477). Parity‑prior query‑edge BMA serves as upper reference (0.000346). The three‑family posterior parity risk (0.000116) is now labelled reference risk only, not a lower bound. Similarly, crossed‑query posterior risks under broader priors are marked as upper references, not pool‑specific Bayes optima. (§3.1, §5.2; Appendix D.1; Table 16)
  2. Moment‑MLP vs Set‑full matched comparison We ran ten‑seed matched controls (9,216 tasks, 16 epochs, batch‑128, identical AdamW/BCE). Under parity‑only training (lr=0.0003): Moment‑MLP risk = 0.00028477; Set32 risk = 0.00065436; difference = −0.00036959, 95% CI [−0.00041857, −0.00032508]. At lr=0.001: difference = −0.00039607, 95% CI [−0.00044769, −0.00034527]. Set64 (lr 0.0003): 0.00065631. These results show moment‑feature advantage in our tested fits; we explicitly note this does not prove the Set architecture cannot learn this signal. We preserved 21 original prediction arrays and added 49 new replicated fits. (§6.4; Table 4; Appendix B.2)
  3. Matched prior‑allocation intervention We avoid interpreting results as an additive “prior‑mismatch component”. In our matched intervention we keep common/one‑even slots fixed and replace half of even‑parity tasks with odd parity (1/3 of total tasks). Odd‑parity ensemble risk drops from 0.00211442 to 0.00102267; difference −0.00109175, 95% CI [−0.00126072, −0.00092357]. The older T‑prior comparison is retained only as descriptive. (§6.4; Appendix B.2)
  4. Removed unsupported training‑failure claim Our models use soft‑target cross‑entropy loss. We delete the claim attributing mixed‑prior training failure to larger common‑shock squared errors, since MSE alone cannot provide gradient‑level evidence for that mechanism. (§5.2)
  5. Non‑oracle all‑edge Chow‑Liu reference We compare Chow‑Liu trees fit either only on query edges or on all 16 edges (no true group labels). Deployment MSE decreases from 0.01111 to 0.00967; difference −0.00144, 95% CI [−0.00189, −0.00099]. Both tree variants perform poorly on parity tasks. This isolates the effect of extra input observations for this algorithm; it cannot separate finite‑sample estimation error from model misspecification. (§6.4; Appendix B.3)
  6. Updated resampled confidence intervals All key model contrasts now use crossed bootstrap: resample training runs + shared task‑design blocks, recomputing ensemble predictions within every replicate, including comparisons against deterministic references. Example: cohort‑C crossed/common: Set‑shape 0.02105 vs Set‑full 0.00481; difference 95% CI [−0.01840909, −0.01412575]. We explicitly separate ensemble risk / mean single‑run risk, and task‑only intervals / crossed resampled intervals. A caption conflating the two risk summaries in cohort‑A is fixed; original mean‑run intervals reproduce exactly (Table 21). No missing historical budget arrays were recovered; we supply 150 fresh protocol‑compliant reruns, document hardware/PyTorch/dropout differences and clarify reused test tasks are not independent confirmation samples. (§4.3; Appendices B.2, C, F)
  7. Practical utility on real‑world recorded‑contact data Our audit certificate works with observed query outcomes instead of exact ground‑truth targets, yet it cannot quantify absolute excess for arbitrary learned models. We evaluate a fixed audit‑informed selection rule against simple validation‑based selection over the same model/bin portfolio across school + workplace contact recordings (48 trial clusters, 384 query episodes). Outer Brier difference (audit − validation): +0.00021215, 95% CI [+0.00002560, +0.00051849]. The audit‑driven rule performs worse on both datasets. Computational budgets are matched; conditional intervals do not generalize to unseen days or venues. This negative result is fully retained; it disproves automatic repair but does not invalidate the information‑certificate concept itself. (§6.3; Figure 3b; Appendix E.3; Table 10)

With these technical corrections and new matched‑control experiments addressing lower‑bound, prior‑confound and statistical‑uncertainty concerns, we kindly ask the reviewer to identify which technical objections remain outstanding, and to separate them from broader open questions about practical real‑world utility and pretrained‑model evaluation.

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

The paper studies whether the information available to a relational predictor is sufficient to determine the probability of a Boolean query in monotone DNF, based on the observation that different joint distributions can have the same low-order marginals but give different query probabilities. The authors propose an information-sufficiency auditing framework that constructs pairs of query templates that are indistinguishable under a given interface and derives lower bounds on the achievable risk. They evaluate this on a 16-edge typed graph benchmark with common shock and even/odd parity mechanisms and three levels of query information (support, shape, and incidence). The experiments show that the risk can decrease when additional query information is provided, in several cases approaching the derived bounds, while the parity experiment is useful for showing that models can differ in their ability to exploit the fourth-order interaction that distinguishes the even and odd-parity distributions.

Critical strengths
  1. The paper makes a useful point that the same low-order marginals can result in different query probabilities, and the "information-sufficiency auditing" framework provides a way to separate the limitation of the available information from the learning limitation of the model.
  2. In a controlled setting, the constructions are useful for isolating different sources of information loss. In particular, the support, shape, and incidence collisions make it possible to study how much additional query information is needed to reduce the Bayes risk.
  3. The paper also shows that having the relevant information available does not necessarily mean that the neural model can use it. The parity experiment, where the moment MLP given fourth-moment features can exploit the higher-order information when trained on parity tasks while Set-full does not use it, is a useful demonstration of this distinction.
Critical weaknesses

The first one is my main concerns about conducting the experiments for the proposed setting only on a toy dataset

  1. The authors provide a useful way to separate the learnability of Boolean query probabilities from the information available to the predictor. However, the experiments are conducted on a highly constructed 16-edge benchmark where the ground-truth query probabilities can be computed exactly by enumeration. The paper does not demonstrate whether similar information-sufficiency issues arise in realistic relational prediction settings, nor does it provide concrete guidance on how practitioners could use the proposed information-sufficiency framework to diagnose or improve existing relational predictors.

  2. The support/shape/incidence hierarchy provides clean controlled collisions, but the support and shape representations are themselves synthetic coarsenings designed to induce the proposed failures. So the experiments mainly confirm that trained models respect the computed floors, and provide limited evidence that the same information bottlenecks arise in realistic relational query representations or existing relational predictors.

The third one is a relatively minor concern but the presentation can be substantially improved

  1. The paper introduces several terms (“query-information ladder,” “Bayes bracket,” “collision”) that are used in the contributions before they are defined, and some are only described informally. This makes the experimental setup difficult to fully understand from the paper alone.
Questions for authors

The main question is also related to my main concerns about extending the method to realistic settings beyond the one constructed toy dataset of 16 edge graph in the paper. How to use the infomation sufficiency framework where the ground truth is not computable exactly and the query templates do not follow the paper's constructed templates?

5 comments

The audit does not require supplied exact probabilities or known mechanism families for every use. Exact posterior references are needed for the controlled risk decomposition; a confirmed input-collision certificate has different requirements. For the latter, §6.1 and Appendix B.1 give the following procedure:

  1. Fix the predictor's actual deterministic query encoding and its world-side observation protocol.
  2. On discovery data, find two queries with exactly the same encoding and the same world-side input distribution.
  3. On separate confirmation draws, evaluate the paired binary outcomes and obtain a simultaneous lower bound δ on their probability gap.
  4. A positive bound certifies an equal-pair probability-MSE floor δ²/4 for every predictor restricted to that interface.

For a full catalog, Proposition 2 weights gaps by the query sampling weights and encoding-class masses; a selected pair alone supplies no overall deployment guarantee. Proposition 4 and Appendix A.1 also allow sound lower/upper query outcomes from partial worlds. Monotone zero/one completions need no missingness model, although their certificate may be zero.

This requires correctly observed outcomes or valid truth bounds, but neither known mechanism families nor supplied exact probabilities. It does not recover all three risk components without suitable references. Approximate embedding similarity is insufficient, and failure to find a collision does not prove sufficiency. Thus, sample-based certification and full risk decomposition should be assessed separately.

Evidence beyond the controlled templates. We apply this procedure to a school recording with 327 people and 5,818 observed contact edges. Generated connected-support DNFs use 4–12 variables. The first two days select candidate pairs; the final three provide a separate confirmation population. Simultaneous 95% bounds certify nonzero gaps for 88 of 160 selected pairs, with the strongest pair-specific MSE floor lower bound 0.01304 (Table 5).

The target here is uniform sampling from the finite recorded bins. This demonstrates a sample-based certificate, not identification of an unknown physical process: repeated index draws are not additional physical observations, and selected-pair counts do not estimate natural-query prevalence. Support/shape remain deliberate coarsenings; these findings do not establish that a deployed encoder has the same bottleneck.

What improvement has actually been demonstrated? Appendix B.1 contains a limited query-interface example: on the selected two-query catalogs, revealing named incidence permits the query's context frequency rather than the midpoint forced by the shared shape encoding. At context size 128, paired Brier changes are −0.0002357 and −0.0006205 at the two resolutions. This is a constructed encoding comparison within the fixed recording, not a repair of an existing deployed model.

We separately evaluate native pomegranate 1.1.2 models on 64 topology-generated 16/17-variable reachability query draws, retaining all draws without outcome screening (§6.2; Appendix E; Table 9). Replacing independence by Chow–Liu improves 11 and worsens 53. Both models receive full named incidence and identical raw worlds, so this tests a model-family intervention rather than an input-information floor. It supplies no positive repair result. Table 9 now also displays the already saved direct query-frequency reference on the same fitting bins, without a new significance claim.

Appendix I additionally inspects the actual interfaces of native pomegranate, official BetaE, and the author-linked RT-v1 source. The 12-encoding BetaE smoke test uses initialized models, and RT is source-only. No compatible input-law collision with distinct probability targets was established; these checks neither evaluate pretrained performance nor prove sufficiency.

We agree that external relevance remains limited: this is a published probabilistic-modeling package, not a pretrained relational foundation model or a deployed natural workload. The revision therefore separates a valid diagnosis from an effective intervention and states those limits in the abstract and §7.

I received your feedback and will keep my score.

AuthorsOpenReview ↗

Follow-up on the Revised Manuscript

Thank you for replying. Could you please clarify which concerns from your original review, if any, our latest response and the revised manuscript have addressed, even partially? For the most important concern that remains, could you explain why the correction or evidence we provided was insufficient and what would address it?

A substantive assessment of the revisions would help us improve the paper regardless of the final decision.

BTW, our comments are under reviewer NjXw, however, I found the newest reply is from AfNQ. I hope this would not bother the clear comments.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Clear statement

The central question is specific: when a predictor receives sampled binary worlds and a Boolean query, which errors can be certified as consequences of its available information, and which require evidence about the fitted learner?

The revision adds three kinds of evidence. First, query-outcome samples from a school contact recording confirm representation collisions without supplying exact probabilities to the audit (§6.1; Table 5). Second, ten-seed matched controls address the prior, optimization and capacity confounds (§6.4; Table 4). Third, we test a public probabilistic-modeling implementation and a fixed audit-inspired selection rule on recorded contacts (§§6.2–6.3; Figure 3). Both operational tests are adverse; we do not claim successful repair or better selection.

We also correct the evaluation-prior requirement for Bayes lower references (§§3.1, 5.2), remove the unsupported training-gradient explanation, and distinguish ensemble risk from mean single-run risk. Missing historical budget predictions could not be recovered; central comparisons now use released predictions from 150 new protocol reruns, with execution differences and reused evaluation tasks disclosed (Appendix F).

Proposition 2 additionally states how certified gaps contribute to a specified weighted query catalog, including overlapping pairs. Proposition 4 and Appendix A.1 give a confirmation-sample certificate with incomplete outcomes using sound truth bounds. Both are consequences of standard variance and concentration arguments, require no exchangeability, and do not determine an unspecified deployment workload.

What the certificate adds to validation is a statement about every predictor restricted to the declared input, rather than just the fitted candidates. With its stated assumptions and confidence, it can rule out reaching a smaller error by further training on unchanged inputs. This is a diagnosis of an accuracy constraint; choosing a successful intervention still needs separate evaluation.

The revised related work now directly credits usable information (Xu et al., ICLR 2020), PVI (Ethayarajh et al., ICML 2022), and OpenRFM (Chen et al., 2026). These already study restricted-model information or relational identifiability. Our claim is the specified query-probability certificate and calibrated protocol, rather than originating that distinction (§2; Appendix I; Table 23). A bounded implementation audit establishes no admissible native input-law witness, so it triggers no new repair experiment.

The contribution to assess is the specified diagnostic protocol and its empirical calibration. The two-point, parity and conditional-variance ingredients are standard. We ask that the remaining assessment distinguish the corrected technical issues from the separate questions of significance and external validity. No general database inference engine or pretrained relational foundation model is evaluated.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.