{"id":"9ac3d983-33db-441c-9bf3-fc94a0e3d9fe","arxiv_id":"2504.20784","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"An approximate version of the Advanced Colour Passing algorithm (ε-ACP) groups factors whose potentials are nearly equal, with a proven but often loose bound on how much query answers change.","lead":"Probabilistic models with repeated objects can be compressed for faster inference, but only when the numbers describing the objects match exactly. This paper introduces a version of the standard compression algorithm that tolerates small mismatches, proves a bound on the resulting error, and shows the error stays tiny in tests.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the multi-group bound proof holds up, and the 'minimal error' phrasing is the only overclaim.","rationale":"The reader's weakest_assumption was that the multi-group product-of-bounds argument is only sketched and may rely on independence of groups. I checked the proof: for each group g, the single-group case establishes pointwise bounds α1_g^{m_g} ≤ R_g(r) ≤ α2_g^{m_g} for every full assignment r. Since the full ratio is the product of the R_g(r), the max is bounded by the product of the per-group maxima and the min by the product of the per-group minima; no probabilistic independence or row-alignment condition beyond Definition 3 is needed. The inequalities in Eq. (88) are directionally correct. Lemma 5's interval argument is valid, and Theorem 9's construction indeed achieves the bound. Thus the central theorem survives scrutiny. The remaining legitimate issue is the 'minimal approximation error' wording in the introduction, since the greedy grouping is not globally optimal; this is a presentation overclaim, not a flaw in the bound. The practical claim is supported only on the tested domains. Therefore I do not change the reader's conditional verdict, though I disagree that the multi-group proof is a load-bearing weakness.","tokens_in":26833,"tokens_out":36951,"duration_ms":346001,"concrete_test":"Exhaustively enumerate all factor graphs with m=3 factors, binary-valued arguments, and ε in {0.01, 0.1}; run ε-ACP, compute the exact distance D(P_M,P_M') by enumerating all full assignments, and verify that it never exceeds the Theorem 7 bound and that the Table 3 construction saturates it. Also independently re-derive the multi-group product bound from the single-group pointwise inequalities to confirm Eqs. (84)-(93).","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The central claim—Theorem 7's strict bound on D(P_M,P_M') and Theorem 9's optimality—is mathematically supported. The multi-group extension (Appendix A, Eqs. 84-93) is valid: it applies the single-group pointwise bounds R_g(r) in [α1_g^{m_g}, α2_g^{m_g}] to each group and multiplies them, which requires no independence assumption; row alignment follows from Definition 3. Lemma 5 and the worst-case constructions for α1 and α2 check out. The only substantive caveat is that the introduction's 'minimal approximation error' overclaims global optimality: the greedy Phase I grouping (Alg. 1, lines 1-11) minimizes per-group squared error when adding a factor, not the overall D over all groupings. This does not affect the theorem. The practical near-zero-error claim rests on synthetic FGs and one MIMIC-IV model, so external validation is limited.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces ε-Advanced Colour Passing (ε-ACP), a modification of the ACP lifted-model-construction algorithm that allows potentials to deviate by a multiplicative factor (1±ε) while still being grouped. The algorithm has three phases: greedy grouping of pairwise ε-equivalent factors (Phase I), colour-based graph-structure refinement via ACP (Phase II), and replacement of each group's potentials by the row-wise arithmetic mean (Phase III). The central theoretical contribution is Theorem 7, which bounds the Chan–Darwiche distance D(P_M,P_M') by ln( ((1+(m−1)/m ε)(1+ε))/(1+ε/m) )^m, and Theorem 9, which gives a tightness construction. The paper also reports experiments on synthetic factor graphs and one MIMIC-IV-learned model showing speedups and query-result quotients near one.","tokens_in":27005,"tokens_out":22352,"duration_ms":204549,"significance":"If the results hold, the paper provides a principled approximate lifted-model-construction method with a provable error bound, which is important for applying lifted inference to potentials learned from noisy data. The analysis is largely self-contained: Lemma 5 shows the mean update preserves ε-equivalence, Theorem 7 is proved with an explicit worst-case argument, and Theorem 9 supplies a matching lower-bound construction. The empirical evaluation is strengthened by released data-set generators and source code, as well as by the MIMIC-IV case study. The main caveats are that the Phase I grouping is a greedy heuristic and the practical near-zero-error claim rests on a limited set of benchmarks.","major_comments":[],"minor_comments":[{"comment":"The phrase 'constructing an approximate lifted representation with a minimal approximation error' overstates the guarantee: Phase I of Algorithm 1 is a greedy, order-dependent grouping heuristic, and the optimality of Theorem 1 applies only to the choice of the representative potential for a fixed group, not to the partition of factors into groups. Please rephrase the contribution statement to say that the per-group update is locally minimal and state explicitly that the grouping in Phase I is heuristic (for example, after Line 11 of Algorithm 1).","section":"Section 1 and Section 3.1 (Eq. 3)"},{"comment":"The sentence claiming that even the outliers 'only deviate at the third decimal place' is contradicted by the plots for ε=0.1 and small domain sizes: for k=2 the quotient p′/p reaches values around 1.02 (second decimal). Please either restrict the statement to the typical or median cases or report the actual extrema.","section":"Section 5 (Fig. 3 and Figs. 7–12)"},{"comment":"The analysis uses the expression (1−ε) and logarithms of it; please state explicitly that the results assume 0<ε<1, and clarify the intended behaviour of Definition 3 when ε≥1.","section":"Section 4 (Theorem 3 and Definition 3)"},{"comment":"Please clarify whether the argmin in Eq. (3) ranges over all potential tables or only over the factors already in G; the surrounding text and Theorem 1 indicate the former, but the subscript ϕ_j invites the latter reading.","section":"Section 3.1 (Eq. (3))"},{"comment":"The multi-group bound would benefit from a one-line justification of the inequality in Eq. (88), for example by noting that the function n ↦ ((1+(n−1)/n ε)(1+ε))/(1+ε/n) is increasing in n for n≥1.","section":"Appendix A (Eqs. (84)–(93))"},{"comment":"The sentence 'The learned FG contains 344 randvars and factors, respectively' is ambiguous; please state explicitly that there are 344 randvars and 344 factors.","section":"Section 5, Table 2"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hey,\n\nThis paper is a solid extension of the ACP line. The new piece is ε-ACP, which lets potentials deviate by a factor of (1±ε) and still be grouped, and the error analysis that comes with it. Theorem 7 gives a strict bound on the distance between the original and approximate distributions, and Theorem 9 shows the bound is tight. I checked the proof of the multi-group case in Appendix A (Eqs. 84-93) because the reader flagged it as sketched; it's actually correct. You apply the single-group pointwise bounds to each group and multiply the ratios. No independence assumption is needed, and row alignment follows from Definition 3. So that concern is cleared.\n\nWhat the paper does well: the worst-case construction in Theorem 9 is elegant, the arithmetic-mean choice is the natural one and is proven optimal for the per-group update, and the experiments show the empirical error is far below the worst-case bound. The MIMIC-IV learned FG is a nice touch, and the amortization analysis in Appendix E is a useful addition.\n\nThe soft spots are real but minor. The phrase 'minimal approximation error' in the abstract and intro overclaims: the optimality is for the potential update given a group, not for the greedy Phase I grouping. The greedy grouping (Alg. 1, lines 1-11) is order-dependent and can produce different groups. The paper never claims the grouping itself is globally optimal, but the phrase could mislead. The experimental evidence is limited to synthetic FGs plus one MIMIC-IV model, so the 'close to zero in practice' claim is not broadly demonstrated yet. That's okay for a paper like this, but a referee should ask for a clearer statement of the scope.\n\nThe citation pattern is fine — heavy self-citation, but it's their own prior ACP work, and the background is appropriately credited. This is an evolution of a program, not a paradigm shift, but it's a useful practical step for lifted inference.\n\nI'd recommend sending this to peer review. It deserves a serious referee. The main fix is terminological: be precise that 'minimal' refers to the potential update, not the grouping. With that, I'd accept it.","headline":"Solid extension of ACP with a provably tight error bound; the theory holds up, and the only overclaim is 'minimal approximation error'.","tokens_in":27525,"tokens_out":3119,"would_cite":true,"duration_ms":28390,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Near-equal potentials can be lifted with a provable bound on query changes","keywords":["lifted inference","parametric factor graphs","colour passing","approximate model construction","epsilon-equivalence","approximation error bound","probabilistic graphical models","symmetry detection"],"falsifier":"Use the paper's Theorem 9 construction to verify that the bound is attained for a single group, then modify the graph so that the factors split into two groups whose extreme quotients are anti-correlated across assignments; enumerate all assignments to compute $D(P_M,P_{M'})$ exactly. If any such graph exceeds the Theorem 7 bound, the multi-group generalisation fails.","tokens_in":26635,"feed_emoji":"🧮","tokens_out":11621,"duration_ms":105132,"temperature":0.7,"pith_summary":"This paper introduces $\\varepsilon$-Advanced Colour Passing ($\\varepsilon$-ACP), an algorithm that constructs a lifted probabilistic factor graph from a ground factor graph even when factor potentials are not exactly equal, only close. It replaces exact equality by $\\varepsilon$-equivalence, in which two potentials may differ by at most a factor of $1\\pm\\varepsilon$, and replaces each group of pairwise $\\varepsilon$-equivalent factors with their row-wise arithmetic mean before running colour passing. The central claim is that this approximate lifting provably changes query answers only within a strict bound: for an input graph with $m$ factors, the distance $D$ between the original and lifted distributions is at most $\\ln\\!\\left(\\frac{(1+\\frac{m-1}{m}\\varepsilon)(1+\\varepsilon)}{1+\\frac{\\varepsilon}{m}}\\right)^{m}$, and Theorem 9 shows this bound is optimal. The paper also reports experiments in which the actual change in query results is close to zero while inference becomes up to a hundred times faster. If correct, this makes lifted inference usable on models whose potentials are learned from data rather than exactly specified.","feed_headline":"Near-equal potentials can still be lifted, error strictly bounded","feed_subtitle":"The ε-ACP algorithm groups near-equal factors and keeps query-answer changes inside a proven bound.","key_machinery":"The central objects are $\\varepsilon$-equivalent factors and the arithmetic-mean update that makes their potentials identical with minimal squared deviation. Two potentials are $\\varepsilon$-equivalent when each lies in $[\\varphi(1-\\varepsilon),\\varphi(1+\\varepsilon)]$ and conversely; two factors are $\\varepsilon$-equivalent when their tables match after a permutation of arguments. $\\varepsilon$-ACP groups factors that are pairwise $\\varepsilon$-equivalent, chooses for each group the arithmetic mean row by row (the optimum of the sum-of-squared-deviations objective), assigns one colour per group, and runs ACP's colour-passing refinement so that the final groups respect both potential proximity and graph symmetry. The error analysis uses the distance $D(P_M,P_{M'}) = \\ln \\max_r \\frac{\\psi'(r)}{\\psi(r)} - \\ln \\min_r \\frac{\\psi'(r)}{\\psi(r)}$, in which the normalisation constants cancel; the key property is that $D \\le d$ implies $e^{-d} \\le O_{M'}(r|e)/O_M(r|e) \\le e^d$ for query odds.","core_discovery":"On the paper's own terms, the discovery is that the approximation error induced by $\\varepsilon$-ACP is tightly controlled. For any factor graph $M$ with $m$ factors and its $\\varepsilon$-ACP output $M'$, the full-joint distributions satisfy $D(P_M,P_{M'}) \\le \\ln\\!\\left(\\frac{(1+\\frac{m-1}{m}\\varepsilon)(1+\\varepsilon)}{1+\\frac{\\varepsilon}{m}}\\right)^{m}$, where $D$ is the log-ratio distance used in Theorem 7, and the paper constructs a factor graph that reaches this boundary, so no tighter bound of this general form exists. Setting $\\varepsilon=0$ reduces $\\varepsilon$-ACP to the exact ACP algorithm. Because a bound on $D$ translates directly into a bound on the odds of any query answer, the theorem gives a worst-case guarantee for approximate query answering in terms of $\\varepsilon$ and the number of factors. The experiments then show that the actual error is far below the guarantee, with most query-result quotients equal to 1 to three decimal places.","pith_inferences":["A practical extension would invert Theorem 7: given a target tolerance on query odds and the factor count $m$, compute the largest $\\varepsilon$ that still satisfies the tolerance, and use that as the algorithm's hyperparameter.","The multi-group step in the appendix assumes that the extreme quotients of different groups align independently; a stress test would construct graphs where one group's maximum quotient coincides with another's minimum across assignments and check whether the Theorem 7 bound still holds.","The mean-replacement idea is not tied to colour passing; the same $\\varepsilon$-grouping plus arithmetic-mean update could be applied to other lifted representations or to parameter tying in learned graphical models.","If the near-zero empirical error persists on more diverse real-world models, the broader conclusion would be that approximate symmetry detection is safe for moderate $\\varepsilon$, making lifted inference the default rather than a special case for exactly symmetric models."],"forward_implications":["For fixed $m$, reducing $\\varepsilon$ tightens the worst-case query bound, and setting $\\varepsilon=0$ recovers the exact ACP output.","The distance bound converts directly into a multiplicative worst-case guarantee on any query's posterior odds, so a user can state an error bar for the lifted model without extra computation.","Grouping is conservative on purpose: a factor joins a group only if it is $\\varepsilon$-equivalent to every current member, which prevents cascading errors from the non-transitivity of $\\varepsilon$-equivalence.","The experiments show a speedup of up to about a factor of 100 over ACP while keeping average query-result quotients within a few tenths of a percent of 1; on a learned MIMIC-IV graph the speedup is smaller but the error quotients are even closer to 1.","The proof notes that mild departures from the worst-case configuration shrink the bound substantially, so the theoretical guarantee is conservative for realistic inputs."],"supporting_citations":[{"why":"Supplies the distance measure $D$ and the sharp bounds linking $D$ to changes in query odds.","marker":"[Chan and Darwiche, 2005]"},{"why":"Introduces the colour-passing CompressFactorGraph algorithm that ACP generalises and $\\varepsilon$-ACP builds on.","marker":"[Kersting et al., 2009; Ahmadi et al., 2013]"},{"why":"Defines the ACP algorithm and the colour-refinement scheme whose initial colour assignment $\\varepsilon$-ACP replaces in Phase II.","marker":"[Luttermann et al., 2024a]"},{"why":"Introduces parametric factor graphs and lifted variable elimination, the representation and inference target.","marker":"[Poole, 2003]"},{"why":"Provides the MIMIC-IV medical dataset from which a learned factor graph is built for the practical evaluation.","marker":"[Johnson et al., 2023]"}],"fun_headline_variants":["Epsilon-ACP: lift near-equal potentials, error provably bounded","Approximate lifting with a tight error bound via epsilon-ACP","Near-equal factors? Epsilon-ACP lifts them with guaranteed error","Bounded-error lifting for nearly indistinguishable objects","Epsilon-ACP: tolerate potential deviations, keep error in check"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument's load-bearing premise is that the worst-case bound proved for the deviations inside a single group of $\\varepsilon$-equivalent factors remains valid when the algorithm produces several interacting groups; the proof of that step assumes the groups' extreme deviations align independently, an assumption that can fail for arbitrary factor graphs.","fun_headline_variants_meta":{"raw":{"variants":["Epsilon-ACP: lift near-equal potentials, error provably bounded","Approximate lifting with a tight error bound via epsilon-ACP","Near-equal factors? Epsilon-ACP lifts them with guaranteed error","Bounded-error lifting for nearly indistinguishable objects","Epsilon-ACP: tolerate potential deviations, keep error in check"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000808,"raw_usage":{"total_tokens":3540,"prompt_tokens":932,"completion_tokens":2608,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":548,"completion_tokens_details":{"reasoning_tokens":2520}},"tokens_in":548,"tokens_out":2608,"duration_ms":17842,"temperature":1.0,"reasoning_tokens":2520,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:21:05.017175+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Use the paper's Theorem 9 construction to verify that the bound is attained for a single group, then modify the graph so that the factors split into two groups whose extreme quotients are anti-correlated across assignments; enumerate all assignments to compute $D(P_M,P_{M'})$ exactly. If any such graph exceeds the Theorem 7 bound, the multi-group generalisation fails.","supporting_citations":[{"cited_title":"A Distance Measure for Bounding Probabilistic Belief Change","cited_arxiv_id":null,"evidence_quote":"Supplies the distance measure $D$ and the sharp bounds linking $D$ to changes in query odds."},{"cited_title":"Counting Belief Propagation","cited_arxiv_id":null,"evidence_quote":"Introduces the colour-passing CompressFactorGraph algorithm that ACP generalises and $\\varepsilon$-ACP builds on."},{"cited_title":"First-Order Probabilistic Inference","cited_arxiv_id":null,"evidence_quote":"Introduces parametric factor graphs and lifted variable elimination, the representation and inference target."}],"review_version":1}