{"id":"cbfce849-5033-4b65-8608-f5b435b8c585","arxiv_id":"2607.13642","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A Cube-and-Conquer framework compiles CNF formulas into a virtual d-DNNF distributed across workers, enabling counting, direct access, and uniform sampling under conditioning.","lead":"dkc and dreasoner compile large logical formulas into a distributed d-DNNF circuit by splitting the problem into independent pieces, then answer counting, sampling, and access queries across a cluster. The work matters because knowledge compilation is a memory bottleneck in AI configuration and verification, and this is a first distributed design for that target.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Query evaluation never tests the memory-exceeding regime that the headline 'beyond reach of sequential compilers' claim requires; uniform-sampling contiguity is not the real weak point.","rationale":"The reader's weakest_assumption focuses on lexicographic contiguity for uniform sampling. That assumption is too strong: an arbitrary fixed total order over the fragments is sufficient for uniformity, and the paper's routing protocol can be read as defining exactly such an order. However, the paper's own experimental scope in Section 5.3 ('instances that are tractable for compilation') avoids the very case where the distributed circuit is too large for a single node. Since the abstract claims querying of complex formulas beyond sequential reach, this is the load-bearing gap. It is addressable by running the reasoner on the MC 2025 instances only dkc can compile. The verdict should remain CONDITIONAL: the architecture and algorithms are plausible, but the central querying claim lacks direct empirical support. No change from the reader's conditional verdict.","tokens_in":15890,"tokens_out":25031,"duration_ms":234204,"concrete_test":"Run the Section 5.3 query workload (1,000 queries, same evidence schedule) on the instances in the MC 2025 benchmark that dkc_128 compiles within 900 s but d4_seq does not (or a sample stratified by d4 failure reason). Record the cumulative tq and per-worker memory; if tq exceeds 900 s or workers exhaust 32 GiB on a substantial fraction, the 'querying beyond reach' claim is unsupported. This directly targets the missing memory-exceeding regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central value proposition is that dkc compiles formulas too large for a single node and dreasoner then serves queries on the distributed circuit. Yet Section 5.3 explicitly restricts the query benchmark to 'instances that are tractable for compilation' and to the subset solved by both d4 and dkc; 116 of 200 compile in under one second. No query measurement is reported for the 37 MC 2025 instances dkc_128 solves but d4_seq does not, i.e., the regime where the distributed circuit actually exceeds sequential reach. Without that experiment, the claim in the abstract that the architecture enables 'compilation and querying of complex formulas that remain beyond the reach of state-of-the-art sequential compilers' is only demonstrated for the compilation half. The reader's contiguity objection to uniform sampling is not, as stated, a correctness bug: any fixed enumeration of the per-worker/per-fragment model sets gives a bijection between {1..C} and models, so a uniform random s remains uniformly distributed even when workers hold non-contiguous lexicographic intervals. The unaddressed gap is empirical support for the querying-beyond-memory scenario.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"dkc is presented as the first distributed d-DNNF compiler. It uses Cube-and-Conquer to partition the input CNF into disjoint cubes; each worker compiles its assigned cube with d4, stores the fragment locally in an ordered list, and never ships the circuit to the Master. The global circuit is virtualized as a deterministic OR of the local fragments (Eq. 3). dreasoner then supports satisfiability, model counting, direct access, and uniform sampling, with or without conditioning, by broadcasting queries and aggregating scalar results; sampling routes a random global index to a worker via per-worker counts. Experiments on MC 2025 show that dkc with 127 workers solves 113 instances versus 76 for sequential d4. Query experiments on a subset of 200 tractable instances compare the 128-core reasoner with d4 and show mixed results, with communication overhead dominating small queries.","tokens_in":16124,"tokens_out":20789,"duration_ms":212725,"significance":"If the correctness and scope issues below are addressed, this is a valuable contribution. Extending Cube-and-Conquer from transient #SAT to persistent compilation avoids the circuit-fragment communication bottleneck, and the distributed query algorithms (especially counting and routing-based sampling) are natural and potentially impactful. The reported compilation scalability is substantial, and the release of code and logs is a concrete reproducibility strength. The main scientific claim about querying formulas beyond sequential reach, however, is not yet supported by the experiments as designed.","major_comments":[{"comment":"The equivalence ∆≡Ψ is asserted but not established for the fragment representation as described. If a worker compiles the §2.1-style conditioned formula, the literals of cube τ are replaced/simplified away, and the fragment does not entail τ. Then the OR of local fragments is generally not equivalent to Ψ over Var(Ψ). Example: Ψ=(a∨d)∧(¬b∨c), cubes {a} and {¬a}; the residual fragments are (¬b∨c) and d∧(¬b∨c), whose OR is (¬b∨c), which is not Ψ. To validate Eq. (3), each stored fragment must be compiled from the un-simplified conjunction Ψ∧τ over all variables, or each fragment must be paired/conjoined with its cube. The reasoner must also handle variables that are absent from a fragment but appear in a conditioning set γ. This issue is load-bearing for §4.","section":"§3.2, Eq. (3)"},{"comment":"The query evaluation is restricted to instances 'tractable for compilation' and to those solved by both d4 and dkc; 116 of 200 compile in under one second. No query timings or memory data are given for the MC 2025 instances that dkc_128 solves but d4_seq does not (37 instances). The abstract's claim that the architecture enables 'compilation and querying of complex formulas that remain beyond the reach of state-of-the-art sequential compilers' is therefore supported only for compilation. Add query experiments on at least a few dkc-only instances, with per-worker circuit sizes and peak memory, or narrow the claim.","section":"§5.3, Figure 4"},{"comment":"No memory measurements are reported. The motivation for the distributed representation is overcoming the single-node memory wall, yet the paper gives no per-worker fragment sizes, no aggregate virtual-circuit size, and no instance where d4_seq hits the 32 GiB limit while dkc completes. Without these, the 'beyond the reach' narrative rests on solve counts alone. Report memory data for the solved instances, particularly the dkc-only ones.","section":"§5.2, Figures 1–3"}],"minor_comments":[{"comment":"The uniform-sampling routing is correct without assuming global lexicographic contiguity of a worker's models; a uniform global index s mapped to a local index in any fixed local enumeration is uniform because each model occurs exactly once in the union of local enumerations. Please state this argument and remove the misleading emphasis on 'owns' the s-th solution and on strict order being 'crucial' for direct access.","section":"§4.2 / Algorithm 2"},{"comment":"The random selection of 200 instances needs a seed and a precise procedure for reproducibility.","section":"§5.3"},{"comment":"#SAT(∆∧γ) is defined as a scalar in Eq. (5); the sampling path also needs per-worker partial counts {c_j}. Specify that workers return these counts.","section":"Algorithm 2, line 25"},{"comment":"Formatting artifacts such as 'proposedkc' and 'introducedreasoner' should be fixed.","section":"Abstract, passim"}],"recommendation":"major_revision","confidential_remarks":"Please double-check the novelty claim 'first distributed knowledge compiler'; the related-work discussion covers only distributed model counters. Also, the Eq. (3)/fragment-representation issue should be clarified before revision; if the implementation stores simplified residual fragments, the correctness of all reported counts may be affected, and the authors should be asked to verify counts on a few instances."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the core idea is good: dkc uses Cube-and-Conquer to compile a d-DNNF across workers that keep their fragments locally, and treats the collection as a virtual deterministic OR. The correctness argument (disjoint cubes imply a valid global d-DNNF) is straightforward, and the compilation experiments are convincing — 113 MC 2025 instances solved with 127 workers versus 76 for d4, with a consistent scaling trend and near-linear speedups on hard instances. The code and logs are linked, so this part is reproducible.\n\nSecond, the reasoner section does not deliver what the abstract promises. The query experiments are explicitly restricted to instances that are tractable for sequential compilation; 116 of 200 compile in under a second. No query times are reported for the 37 instances that dkc_128 solves but d4 does not — i.e., the case where the distributed circuit actually exceeds sequential reach. So the claim about 'compilation and querying of complex formulas beyond the reach of sequential compilers' is only supported for compilation.\n\nNow, the sampling concern the review flagged is a false alarm. The routing scheme maps a global index to a worker via prefix sums of counts, then to a local index within that worker's fragments. That defines a perfectly good enumeration of all models (worker by worker, fragment by fragment). A uniform random global index gives a uniform model regardless of whether a worker's models form a contiguous interval in the global lexicographic order. So the algorithm is correct as a sampler, though it won't produce lexicographic order for direct access unless the fragment order aligns, which is not required.\n\nWeaker spots worth noting: the 'first distributed knowledge compiler' claim is not backed by a survey of prior parallel KC work, so it's easy to overclaim. The reasoner evaluation on small instances is mostly an overhead study, and the paper's own discussion admits the distributed approach loses on easy queries. None of this is fatal. The algebraic machinery is simple but correct, the experimental design is appropriate for the compilation phase, and the persistent-circuit idea is genuinely reusable.\n\nIn short: this is a solid systems paper for the KC community. It deserves a serious referee, but I'd ask the authors to either run the query benchmark on the instances only dkc can compile or clearly state that the memory-exceeding query scenario remains open. I'd cite it for the distributed compilation design, and probably bring it to a reading group if the focus is on compilation systems.","headline":"The distributed compilation half is a solid, reproducible advance; the querying half is not actually tested in the regime that matters, so the abstract oversells.","tokens_in":16583,"tokens_out":5420,"would_cite":true,"duration_ms":49495,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A Boolean formula can be compiled into a d-DNNF circuit that exists across a cluster—each worker keeps its own fragments—and the same distributed circuit answers counting, sampling, and direct-access queries without ever being assembled in","keywords":["knowledge compilation","d-DNNF","distributed reasoning","Cube-and-Conquer","model counting","uniform sampling","direct access","conditioning"],"falsifier":"Compile a small formula with a known model set, deliberately dispatch cubes so one worker receives two non-adjacent cubes, then request a large batch of samples and compare the empirical distribution to the true uniform distribution; a significant mismatch would show the sampling guarantee fails.","tokens_in":15762,"feed_emoji":"🌐","tokens_out":9315,"duration_ms":83187,"temperature":0.7,"pith_summary":"Knowledge compilation turns a propositional formula into a circuit that supports fast counting and sampling, but building that circuit is expensive and often demands more memory than one machine has. The paper argues that a Cube-and-Conquer split—dividing the formula into disjoint subproblems—lets the compilation run across a cluster while each worker keeps its circuit pieces local. The global circuit is then an implicit deterministic OR over those pieces, and a companion reasoner answers satisfiability, model counting, direct access, and uniform sampling queries on it, even after conditioning on partial assignments. On the 2025 Model Counting Competition benchmarks, the distributed setup with 127 workers solves 113 instances, whereas a strong sequential compiler solves 76.","feed_headline":"Distributed compiler solves 113 hard benchmarks vs 76 on one node","feed_subtitle":"Fragments stay local, so the cluster answers counting, sampling, and direct-access queries beyond single-node memory.","key_machinery":"The key mechanism is the virtual circuit Δ = ∨_j ∨_{Σ∈L_j} Σ, a deterministic OR gate over ordered lists of local d-DNNF fragments. The Cube-and-Conquer decomposition of the formula into disjoint, exhaustive cubes is what makes this OR deterministic and correctness-preserving: every model belongs to exactly one fragment. This decomposition turns distributed compilation into a set of independent sequential compilations and reduces global reasoning to sums (counting), disjunctions (satisfiability), and index routing (direct access and uniform sampling) over the local lists.","core_discovery":"The paper's central claim is that the communication overhead that has kept knowledge compilation single-node can be avoided by never moving circuit fragments. Each worker compiles its assigned cubes into d-DNNF fragments and persists them in a locally ordered list; the global circuit exists virtually as a deterministic OR gate over all those lists (Eq. 3). Because the cubes are pairwise inconsistent and cover the entire solution space, the reconstruction is correct, and because fragments remain local, the circuit can exceed the memory of any single node. The companion reasoner answers counting, direct access, and uniform sampling by broadcasting scalar questions, aggregating scalar answers,","pith_inferences":["The uniform-sampling router assumes the models of each worker form a contiguous interval in the global order; making this assumption explicit and enforcing contiguity at cube-assignment time would turn a heuristic into a provable guarantee.","The same virtual-circuit design—a deterministic root OR over locally stored fragments—should transplant to other compilation targets that support deterministic disjunction, such as BDDs or SDDs, giving them distributed query engines too.","The direct-access price of one broadcast count per variable suggests a speculative prefetching protocol could cut the round-trip count; the paper lists this as future work, but a concrete bound on the resulting speedup is a natural next test."],"forward_implications":["Knowledge compilation can be scaled beyond the memory of any single machine by persisting fragments locally and never gathering the full circuit.","The same distributed circuit supports the four standard queries—satisfiability, model counting, direct access, uniform sampling—in polynomial time, including under arbitrary conditioning.","With as few as two active workers, the distributed compiler overtakes the sequential baseline on the MC 2025 benchmark set, and with 127 workers it solves 113 instances versus 76.","Query overhead dominates for lightweight, sub-second queries; the distributed reasoner is most beneficial when the compiled circuit is too large for one machine."],"fun_headline_variants":["Fragments stay, queries fly: distributed d-DNNF scales","Split and keep: cluster compiles past single-node memory","No circuit sharing: dkc handles 113 benchmarks on cluster","Lazy OR gate: distributed d-DNNF beats single-node limits","Distributed d-DNNF: local fragments, global reasoning at scale"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"Uniform sampling relies on each worker's fragments covering a contiguous interval of the global model ordering; with dynamic dispatch, workers can receive non-contiguous cubes, so the routing step may not yield a uniform sample.","fun_headline_variants_meta":{"raw":{"variants":["Fragments stay, queries fly: distributed d-DNNF scales","Split and keep: cluster compiles past single-node memory","No circuit sharing: dkc handles 113 benchmarks on cluster","Lazy OR gate: distributed d-DNNF beats single-node limits","Distributed d-DNNF: local fragments, global reasoning at scale"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00016,"raw_usage":{"total_tokens":1077,"prompt_tokens":761,"completion_tokens":316,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":505,"completion_tokens_details":{"reasoning_tokens":225}},"tokens_in":505,"tokens_out":316,"duration_ms":4862,"temperature":1.0,"reasoning_tokens":225,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T04:35:45.829012+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compile a small formula with a known model set, deliberately dispatch cubes so one worker receives two non-adjacent cubes, then request a large batch of samples and compare the empirical distribution to the true uniform distribution; a significant mismatch would show the sampling guarantee fails.","supporting_citations":[],"review_version":1}