{"id":"c3fcd9da-5b27-43d0-a7cf-fdc36119c30f","arxiv_id":"2611.16815","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Selective chaining of PBESs is a sound transformation that reduces verification time and memory by unfolding only specific predicate variable instances guided by heuristics.","lead":"This paper introduces a technique called selective chaining to simplify Parameterised Boolean Equation Systems (PBESs) used in formal verification of industrial software. The method selectively unfolds predicate variable instances to reduce memory and time when solving model checking problems, with experiments showing up to 25x speedups and 14x memory reductions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"Heuristic effectiveness rests on only one public case study; two of three are confidential, limiting reproducibility and generalizability.","rationale":"The reader's verdict is CONDITIONAL, citing reliance on confidential case studies and lack of reproducibility. My stress-test identifies the same weakest point: the empirical validation is not independently verifiable. The reader's weakest_assumption (heuristics may not generalize) is exactly the concern I articulate. I do not downgrade the verdict because the paper's theoretical contributions (soundness, upper bounds) are solid and the authors are transparent about limitations. However, I emphasize that the central claim of practical effectiveness cannot be fully assessed without public benchmarks. The concrete test I propose is feasible and would directly address the reproducibility gap. I agree with the reader that the verdict should remain CONDITIONAL until broader validation is provided.","tokens_in":26734,"tokens_out":530,"duration_ms":6225,"concrete_test":"Release the models and properties for C-2 and C-3 (or sufficiently detailed anonymized versions) and run the same pbeschain pipeline on a public benchmark, e.g., the mCRL2 example suite or the BEEM benchmark. If the speedup and memory reduction patterns replicate on at least three public models of comparable complexity, the concern is resolved.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central claim—that selective chaining yields up to 25× speedup and 14× memory reduction—is supported by three case studies, but two of them (C-2 Maeslant Barrier, C-3 Pneumatic Cylinder) are confidential. Only C-1 (Prinses Marijke lock complex) is public. The authors acknowledge this indirectly by omitting model details for C-2 and C-3. For a technique whose effectiveness depends on heuristics (H1–H4) that are empirically tuned and whose interaction with PBES structure is not formally characterized, the lack of a public, reproducible benchmark is a load-bearing concern. Without independent verification on a shared benchmark, the reported improvements could be artifacts of the specific (confidential) models or of the particular solver configuration used. The paper's own Section 6 notes that the order of chaining remains unexplored and can change the final PBES, further underscoring that the heuristics are not yet robustly understood. The soundness proof (Theorem 3.11) is not in question; the concern is about the empirical support for the claimed practical benefits.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper introduces selective chaining, a transformation for Parameterised Boolean Equation Systems (PBESs) that unfolds specific predicate variable instances to simplify the system while preserving its solution. The authors prove soundness (Theorem 3.11) and provide theoretical bounds on the size increase of relevancy graphs for PBESs in standard recursive form (Theorem 3.15). They propose four heuristics (H1–H4) to avoid adverse blow-ups and implement the technique in a tool called pbeschain within the mCRL2 toolset. The experimental evaluation on three case studies—one public (Prinses Marijke lock complex) and two confidential (Maeslant Barrier, Pneumatic Cylinder)—shows reductions in solving time (up to 25×) and memory usage (up to 14×).","tokens_in":27116,"tokens_out":1814,"duration_ms":16213,"significance":"If the results hold, selective chaining offers a useful addition to the toolbox for mitigating state explosion in model checking via PBESs. The soundness proof is rigorous, and the theoretical bounds for SRF PBESs are a solid contribution. The heuristics are plausible and the experimental results, though limited in public reproducibility, show consistent improvements across the tested cases. The technique is complementary to existing static analysis methods for PBESs.","major_comments":[{"comment":"Two of the three case studies (C-2 Maeslant Barrier, C-3 Pneumatic Cylinder) are confidential, with model details omitted. The paper's central empirical claim—up to 25× speedup and 14× memory reduction—rests heavily on these confidential cases. While the authors acknowledge this indirectly by omitting details, the lack of a public, reproducible benchmark is a load-bearing concern for the claimed practical benefits. The heuristics (H1–H4) are empirically tuned, and their effectiveness is demonstrated only on these three cases. Without independent verification on a shared benchmark, the reported improvements could be artifacts of the specific (confidential) models or solver configuration. The paper's own Section 6 notes that the order of chaining remains unexplored and can change the final PBES, further underscoring that the heuristics are not yet robustly understood. The soundness proof (Theorem 3.11) is not in question; the concern is about the empirical support for the claimed practical benefits.","section":"§5.1, §5.3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The evaluation of heuristic H2 (Bounded PVI expansion) for C-1 shows that higher bounds (e.g., 50) can lead to faster solving times for the hardest properties, but also increase pbeschain running time, sometimes making the total time worse than not chaining at all. The paper acknowledges a tipping point but does not provide a systematic way to choose the bound. This is a limitation, but it is stated. However, the claim that 'the number of nodes in the relevancy graph is consistently 7-10x lower when the maximum number of PVI increases' (line after [b251]) is not supported by a quantitative comparison in the text; only a qualitative statement is given. The paper should provide concrete numbers or a table to substantiate this claim.","section":"§5.2, Figure 2b","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Theorem 3.15 states that for PBESs in SRF, the relevancy graph after chaining has edges only in E_G ∪ eE_{G,X,i}, and no new vertices are introduced. This is a useful bound. However, the proof relies on Lemma 3.14, which assumes that (Y,w) is not in (X,v)• and that (X, Jarg_i(φ_X)Kδ[v/d_X]) ∈ (X,v)• implies (Y,w) ∉ (X, Jarg_i(φ_X)Kδ[v/d_X])• for all δ. The lemma's statement is conditional on these assumptions, and the proof of Theorem 3.15 uses Lemma 3.14 to handle the case where ( (Z,v),(Y,w) ) ∉ E_G. The reasoning appears sound, but the presentation could be clearer: the proof of Theorem 3.15 is very brief (only a few lines) and relies heavily on Lemma 3.14 without explicitly showing how the conditions of Lemma 3.14 are satisfied. Expanding the proof would improve readability.","section":"§3.2, Theorem 3.15","authors_acknowledge":null,"authors_acknowledge_p":null}],"minor_comments":[{"comment":"The example unfolding in the introduction shows the formula after unfolding but does not explicitly state that the resulting equation is more complex. It would be helpful to note that the number of PVIs increases from 2 to 4, illustrating the blow-up.","section":"§1, Example","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The definition of chain_I(φ_X) uses φ_X⟨arg_i(φ_X)⟩, but it is not immediately clear that this is the right-hand side with the formal parameter d replaced by the actual argument. The notation φ_X⟨e⟩ is defined earlier (after Definition 2.1) as φ_X[(d_1,...,d_n) := (e_1,...,e_n)], but a brief reminder here would aid readability.","section":"§3.1, Definition 3.5","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The algorithm uses 'pick' without specifying the selection strategy. The paper later (Section 6) notes that the order of chaining is unexplored. It would be helpful to state explicitly that the current implementation uses an arbitrary order (e.g., the order in which PVIs appear in the formula).","section":"§4, Algorithm 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Table 1 lists memory limits for each property of C-1. It would be useful to also report the actual memory usage (peak resident set size) for the base and chained cases, as is done for C-2 in Figure 4a. The memory comparison for C-1 in Figure 4b uses log-log scale and shows a clear reduction, but the text does not discuss the absolute values.","section":"§5.1, Table 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The sentence 'We can notice this here since this case study generally contains more complex data expressions' is vague. It would be better to provide a concrete example or quantify the complexity (e.g., size of data expressions).","section":"§5.2, H3 discussion","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The claim 'there is never an increase in relevant nodes after chaining' (based on Theorem 3.15) is stated as empirically confirmed. However, Theorem 3.15 only guarantees no new vertices for SRF PBESs; the paper should clarify whether all case study PBESs are in SRF after preprocessing. The text mentions that SRF transformation is applied for symbolic cases (H3), but for explicit cases (C-3) it is not mentioned. Please clarify.","section":"§5.3, General trends","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The benchmark commands include options like '--cached-rjittyc' and '--groups=used' that are not explained. A brief explanation of these options would help reproducibility.","section":"Appendix B","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Reference [Str25] is a PhD thesis (Stramaglia, 2025). The paper cites it for Lemma A.2, but the lemma is standard (substitution lemma). It would be acceptable to provide a self-contained proof or cite a more accessible source.","section":"References","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"major_revision"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"Jore,\n\nThis paper introduces selective chaining for PBESs—unfolding only specific predicate variable instances instead of all occurrences—and backs it with a soundness proof and a set of heuristics to avoid blow-up. The core idea is sensible and the formal work is the real contribution: Theorem 3.11 (soundness) and Theorem 3.15 (bounds on relevancy graph size for SRF PBESs) are cleanly proved and give the technique a solid foundation. The paper also ships an implementation in the mCRL2 toolset, which is good practice.\n\nThe soft spot is the empirical evaluation. The paper reports up to 25× speedup and 14× memory reduction, but two of the three case studies (Maeslant Barrier, Pneumatic Cylinder) are confidential. Only the Prinses Marijke lock complex is public. For a technique whose effectiveness depends on four heuristics (H1–H4) that are empirically tuned and whose interaction with PBES structure is not formally characterized, this is a real limitation. The authors acknowledge that the order of chaining is unexplored and can change the final PBES (Section 6), which further underscores that the heuristics are not yet robustly understood. The soundness proof is not in question; the concern is about the empirical support for the claimed practical benefits. The paper would be stronger with a public benchmark and a more systematic sensitivity analysis of the heuristic parameters.\n\nWho is this for? Researchers working on PBES-based verification and practitioners using mCRL2 who hit state explosion. The paper deserves a serious referee—the formal contributions are real and the technique is useful—but the referee should push for better empirical transparency.\n\nI'd bring it to a reading group focused on formal verification techniques, but I'd note the reproducibility caveat. I wouldn't cite it for the empirical claims without independent verification, but I might cite it for the soundness proof and the chaining operator definition.\n\nRecommendation: accept with major revision requiring either (a) making at least one more case study public, or (b) adding a synthetic benchmark suite that allows independent reproduction of the main trends.","headline":"Solid incremental technique for PBES simplification; soundness proof is clean, but the empirical case for the heuristics rests heavily on two confidential case studies.","tokens_in":27585,"tokens_out":535,"duration_ms":125157},"pith_extraction":{"msc":["68Q60"],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"Selective chaining, a transformation that unfolds only chosen predicate variable instances when solving a parameterised Boolean equation system, is sound — it preserves the solution — and on industrial control models it solves equations…","keywords":["selective chaining","parameterised boolean equation systems","model checking","proof graphs","relevancy graphs","fixpoint theory","state explosion","heuristics"],"falsifier":"A concrete check: find a PBES in standard recursive form whose chained relevancy graph gains a new vertex, which Theorem 3.15 asserts cannot happen; such an example would refute the bound as stated, and the paper's own Example 3.12 shows the failure mode is real for general (non-SRF) systems.","tokens_in":28181,"feed_emoji":"⚙️","tokens_out":8058,"duration_ms":50008,"temperature":0.7,"pith_summary":"Parameterised Boolean Equation Systems (PBESs) encode model checking problems as sequences of fixpoint equations, and solving them can trigger the state explosion problem. This paper introduces selective chaining, a transformation that unfolds only chosen predicate variable instances when doing so is likely to simplify the system, rather than applying the rolling rule of fixpoint theory to everything at once. The paper proves chaining is sound — it preserves the solution of the original PBES — and bounds how much the search space can grow, for systems in standard recursive form. Four heuristics decide which instances to chain, and on three real-world industrial control models, chained PBESs solve up to 25x faster and use up to 14x less memory. The claim is that these heuristics capture most of the benefit while keeping the adverse blow-ups of wholesale unfolding under control.","feed_headline":"Unfolding just the right equations cuts model-checking time 25x","feed_subtitle":"A sound transformation preserves the model-checking answer while shrinking solve time and memory on industrial software.","key_machinery":"The chaining operator $\\mathrm{chain}_I(\\varphi_X)$ is the central mechanism: given the right-hand side of the equation for $X$, it replaces every selected predicate variable instance $X(\\arg_i(\\varphi_X))$ in the set $I$ with $\\varphi_X\\langle\\arg_i(\\varphi_X)\\rangle$, the right-hand side instantiated at those arguments. This is a local refinement of the rolling rule $\\sigma(f \\circ g) = f(\\sigma(g \\circ f))$ of fixpoint theory, which unfolds all occurrences at once and can blow the system up. Soundness is established by extending a proof graph with shortcut edges — the extended graph $G_{X,i}$ — and showing the result is still a proof graph, so any certificate transfers to the chained system. Four heuristics govern which instances get chained: avoiding quantifier-scoped predicate variable instances, bounding the number of new instances per chaining action, converting to standard recursive form before chaining when the solver requires it, and capping the unfolded formula's size.","core_discovery":"The central claim is that chaining — replacing selected occurrences of a predicate variable instance $X(\\arg_i(\\varphi_X))$ with the instantiated right-hand side $\\varphi_X\\langle\\arg_i(\\varphi_X)\\rangle$ — preserves the solution of the PBES (Theorem 3.11), and that for PBESs in standard recursive form, the relevancy graph of the chained system introduces no new vertices, only edges between existing ones (Theorem 3.15). Because the proof works by extending a proof graph with shortcut edges and checking that infinite paths remain $\\nu$-dominated, the certificate of a solution survives chaining, so a model checker's conclusion is unchanged. The empirical claim is that, on two symbolic and one explicit solver configuration over three control-heavy industrial models, chaining with the proposed heuristics delivers up to 25x shorter solve times and up to 14x lower memory, with the largest absolute gains on the hardest requirements.","pith_inferences":["Because the authors report little benefit on models with substantial parallelism, an inference is that chaining targets control-heavy sequential behaviour; a natural extension is ordering chaining by dependency depth or chain length instead of the current arbitrary pick order.","The sliding optimum of the PVI-expansion bound across solving regimes suggests an adaptive policy that tunes the bound to the expected requirement size could outperform any fixed setting, a testable extension the paper does not pursue.","Since chaining is sound on general PBESs but only bounded in standard recursive form, a conservative practical rule — convert to standard recursive form first, then chain — accepts the small overheads seen in the Maeslant case while buying the tightest size guarantee."],"forward_implications":["For PBESs in standard recursive form, chaining adds no new predicate variable instances to the relevancy graph — only edges among already-relevant instances — so any blow-up is bounded by the original graph's vertex count.","Because chaining preserves the solution, it can be applied as a preprocessing step without changing what the model checker concludes, only how fast and with how much memory it reaches that conclusion.","Allowing more new predicate variable instances per chaining action shrinks the relevancy graph 7–10x even while it increases the syntactic PVI count, and the best bound shifts with the size of the requirement being solved.","Converting to standard recursive form before chaining can dominate the benefit in some cases: one requirement solved in 10 minutes when the conversion preceded chaining but took 28 hours without it."],"supporting_citations":[{"why":"Defines parameterised boolean equation systems and supplies the substitution lemma (Lemma 18/19) that the chaining operator refines from all-occurrence to single-instance replacement.","marker":"[GW05]"},{"why":"Defines proof graphs, the certificate structure that the soundness proof of chaining preserves and extends.","marker":"[CLW13]"},{"why":"Introduces relevancy graphs, the size proxy that Theorem 3.15 uses to bound the growth of the search space after chaining.","marker":"[Lie23]"},{"why":"States the rolling rule of fixpoint theory that unfolding is based on and that chaining refines into a local operation.","marker":"[NP24]"},{"why":"Supplies the local substitution operator $\\varphi[i \\mapsto \\psi]$ that the chaining operator generalizes to arbitrary sets of predicate variable instances.","marker":"[KWW13]"},{"why":"Provides Zielonka's recursive algorithm for parity games, cited as the means to extract a proof graph from a relevancy graph.","marker":"[Zie98]"},{"why":"Hosts the mCRL2 toolset in which the pbeschain implementation and the reported experiments run.","marker":"[Bun+19]"},{"why":"Supplies the Prinses Marijke lock complex model, the largest public case study used to benchmark the heuristics.","marker":"[GV25]"},{"why":"Supplies the Maeslant Storm Surge Barrier model, the second case study, whose PBESs contain the most complex data expressions.","marker":"[Bee+25]"}],"fun_headline_variants":[],"cache_read_input_tokens":0,"weakest_assumption_plain":"The load-bearing premise is that the four heuristics reliably pick chaining steps that simplify rather than enlarge the solving problem; the paper demonstrates this on only three industrial case studies, two of them confidential, and acknowledges that the order of chaining — which can change the final PBES — remains unexplored.","fun_headline_variants_meta":{"raw":{"variants":[]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":9.8e-05,"raw_usage":{"cost":9.8007e-05,"is_byok":false,"cost_details":{"upstream_inference_cost":9.8007e-05,"upstream_inference_prompt_cost":8.3811e-05,"upstream_inference_completions_cost":1.4196e-05},"total_tokens":999,"prompt_tokens":921,"completion_tokens":78,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":0,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":0}},"tokens_in":921,"tokens_out":78,"cost_source":"openrouter_usage","duration_ms":2790,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":0,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-13T12:29:26.094509+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"A concrete check: find a PBES in standard recursive form whose chained relevancy graph gains a new vertex, which Theorem 3.15 asserts cannot happen; such an example would refute the bound as stated, and the paper's own Example 3.12 shows the failure mode is real for general (non-SRF) systems.","supporting_citations":[],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}