{"id":"abe08a88-6b29-46f0-b0f4-bd5af99d2d52","arxiv_id":"2608.13268","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper introduces a multiobjective preexpectation transformer that exactly captures the almost-achievable Pareto front of nondeterministic probabilistic programs, with loop invariant rules and strategy synthesis.","lead":"A new program-level calculus, called mop, computes the set of outcomes a nondeterministic probabilistic program can achieve when several objectives are optimized at once, including the trade-offs on the Pareto front. It extends standard weakest preexpectation reasoning and is shown to match the strategy semantics of infinite-state Markov decision processes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main soundness theorem (10.6) is asserted, not proved; Corollary 10.7 rests on an unverified induction over the convex Hoare powerdomain.","rationale":"The reader's verdict is CONDITIONAL, and I agree with that verdict, but for a different reason than the stated weakest assumption. The reader identifies compactness of H-elements as the load-bearing assumption. I checked the relevant claim: the footnote in Theorem 7.1 gives a valid directed-set argument that downward closed plus Scott closed implies topological closedness in R-bar^n≥0, and the subsequent compactness arguments in Theorems 6.7 and 7.3 appear to go through. So I do not think the compactness assumption is the actual weak point. The real soft spot is Theorem 10.6, the operational soundness theorem, which is the direct support for the paper's headline result Corollary 10.7. Its proof is a sketch that defers to a scalar theorem in a different paper and mentions an unstated compositionality lemma. The multiobjective setting introduces operations—Scott-closed convex suprema, Minkowski sums with probability weights, least fixed points in two different function lattices—that are absent from the scalar analogy, and the induction over program structure must handle intermediate configurations and loop unfoldings in the operational MDP. Without a full proof, the central claim is not established. This is consistent with the reader's CONDITIONAL verdict: the paper is promising, the geometric and fixed-point machinery is coherent, and the compactness concern appears resolvable, but the main correspondence needs to be proved or formalized before the result can be accepted as demonstrated.","tokens_in":51277,"tokens_out":23377,"duration_ms":255663,"concrete_test":"Write out a complete proof of Theorem 10.6. Specifically: (1) state and prove the compositionality lemma mopJ𝐶1#𝐶2K(F) = λσ.(lfp Φ^{rewJFK}_O)((C1#C2,σ)) by relating the Bellman operator on the configuration (C1#C2,σ) to the value after one small step; (2) for the loop case, prove by induction on the Kleene iterates that the syntactic iterate (Φmop)^n(0) equals the Bellman iterate (Φ^{rewJFK}_O)^n(0) evaluated at (while φ C', σ), for every σ, using the Hoare-powerdomain supremum property (Lemma 5.2) at each step; (3) verify that scalar multiplication distributes over the Scott-closed convex suprema used in the Bellman operator, since this is the step where the 0·∞ convention and the extended orthant could break the induction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central equivalence, Corollary 10.7, is derived from Theorem 10.6 ('Operational Soundness of mop'), but Theorem 10.6 is not actually proved. Its proof consists of two sentences: the ⊒ direction is claimed by 'essentially showing' that mopJ𝐶K(F)(σ) is a fixed point of the Bellman operator, and the converse is 'proven via induction on the program structure, using a compositionality lemma for sequential composition' that is never stated. The cited analogy, [Batz et al. 2024b, Theorem 6], is a scalar weakest-preexpectation soundness theorem; it does not involve suprema in the convex Hoare powerdomain, Minkowski sums with probabilities, or Scott-closed convex closures. These are exactly the operations that make the multiobjective Bellman operator nontrivial: its least fixed point lives in MV = S→H, while the mop least fixed point lives in MultExp = Σ→H, and the operational state space includes intermediate configurations (C1#C2, σ) and loop unfoldings whose values must be shown to satisfy the structural mop equations. The loop case requires commuting Hoare-powerdomain suprema with the operational unfolding, and the guarded-choice rule must match the MDP's action-enabledness at every state. None of this is demonstrated. The compactness assumption flagged by the reader is, on inspection, supported: for downward-closed sets in R-bar^n≥0, Scott closedness does imply product-topological closedness via the directed-set argument in the footnote to Theorem 7.1, and the bounded/compact reductions in Theorems 6.7 and 7.3 are plausible. The genuine soft spot is therefore the missing derivation of Theorem 10.6, which is load-bearing for the headline claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a multiobjective preexpectation transformer, mop, for probabilistic programs with nondeterminism. mop maps a tuple of postexpectations to an element of the convex Hoare powerdomain: the set of simultaneously achievable value vectors, downward closed, convex, and Scott closed. The authors prove basic healthiness properties, invariant-based loop rules for upper and lower bounds, a scalarization theorem relating mop to classical weakest preexpectations via weighted sums, and conditions for synthesizing mixed determinizations that realize Pareto-optimal trade-offs. They then relate mop to a generalized Bellman operator on the operational MDP semantics of pGCL and claim an exact correspondence for countable-state, finite-action MDPs without finite-state restrictions. Three case studies (robot, casino, queue) illustrate the calculus with closed-form Pareto fronts.","tokens_in":51574,"tokens_out":6394,"duration_ms":69522,"significance":"If the main soundness theorem is fully established, the paper would be a substantial contribution: it provides a program-level, deductive calculus for multiobjective strategy synthesis over infinite-state MDPs, conservatively extending classic weakest preexpectations and connecting to the finite-state multiobjective MDP literature. The scalarization result (Theorem 7.1) and the halfspace characterization (Theorem 7.3) are elegant and well developed, and the case studies give explicit, checkable closed forms. The paper is also honest about its limitations in Section 12. However, the headline equivalence between mop and almost-achievable values, Corollary 10.7, rests on Theorem 10.6, which is currently asserted rather than proved; this gap is load-bearing and must be closed before the central claim can be accepted. The compactness concern raised in the stress-test note is, on inspection, addressed by the footnote to Theorem 7.1: the directed-set argument there does establish topological closedness of downward-closed Scott-closed sets in Rbar^n, so I do not base my recommendation on that point.","major_comments":[{"comment":"The central operational soundness theorem is not actually proved. The proof consists of two sentences: the direction mopJ C K(F)(σ) ⊒ (lfp Φ_O)((C,σ)) is claimed by 'essentially showing' that mopJ C K(F) is a fixed point of the Bellman operator, and the converse is said to follow 'via induction on the program structure, using a compositionality lemma for sequential composition' that is never stated. This is not a presentation issue: Corollary 10.7 and Lemma 10.8, which are the paper's main characterization of the achievable set, are direct consequences of Theorem 10.6. The cited scalar analogue [Batz et al. 2024b, Theorem 6] does not cover Minkowski sums with probabilities, convex and Scott closures in the Hoare powerdomain, or intermediate configurations such as (C1#C2, σ) and loop unfoldings. Please supply the full proof, including an explicit compositionality lemma, the loop case, and the verification that the Bellman operator's action-enabledness matches the guarded-choice semantics at every state.","section":"Section 10.3, Theorem 10.6"},{"comment":"The descending fixpoint iteration theorem for molp is not established. The proof itself states that the required ω-co-continuity 'is not routine', defers nested loops to 'a Park-style argument', and claims that closure points involving ∞-components are handled by 'reduc[ing] to the bounded sublattices via finite caps' without giving that reduction. Since Lemma 6.8, and consequently Lemmas 6.9 and 6.10 and the lower-bound rules Theorems 6.11 and 6.12, all depend on Theorem 6.7, the lower-bound loop reasoning is currently conditional. Either provide a complete proof of ω-co-continuity, or explicitly mark these rules as relying on an unproved conjecture and adjust the claims in Section 6 accordingly.","section":"Section 6, Theorem 6.7"},{"comment":"The reductions between memoryful and memoryless schedulers and between mixed determinizations and schedulers are only sketched. The proof of Theorem 9.3 lists four high-level steps but does not define the schedulers ρ_k, the finite-state fragments M_k^⊥, or the precise reward preservation argument when passing from the finite fragment back to the full countable MDP. Lemma 10.3 similarly asserts the correspondence 'by induction on the program structure' and 'by the reverse construction' without giving the construction. These results feed directly into Corollary 10.5 and hence into Corollary 10.7, so they need to be written out in enough detail to be checked.","section":"Section 9, Theorem 9.3 and Section 10.2, Lemma 10.3"}],"minor_comments":[{"comment":"The headings 'Eqivalence of Fixpoints I/II' contain a typo; both should read 'Equivalence'.","section":"Section 6, Lemmas 6.9 and 6.10"},{"comment":"The claim that the invariant was 'proposed by Anthropic's Claude Fable 5 and subsequently verified in Lean' is unsupported and irrelevant to the mathematical content; either provide a reproducible artifact or remove the claim.","section":"Section 8.1, footnote 4"},{"comment":"The displayed formula for L_k(t,g) ends with a stray '.𝑠' that appears to be a typographical artifact.","section":"Section 8.1, formula for L_k(t,g)"},{"comment":"The proof of basic healthiness is very brief; in particular, the well-definedness of the least fixed point for loops in the convex Hoare powerdomain deserves a few more sentences, since it is not entirely routine.","section":"Section 5.3, Theorem 5.8"},{"comment":"The proof of Lemma 4.4 is omitted. A short argument showing that dwc(Pareto) = cl(Ach) would be helpful, as the lemma is used in Lemma 7.7.","section":"Section 4, Lemma 4.4"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within the scope of the journal and the main idea is attractive. The decisive issue is completeness of the proof of Theorem 10.6 and its supporting operational lemmas; these are load-bearing for the paper's central claim. I recommend major revision rather than rejection because the missing arguments appear obtainable by adapting existing scalar proofs, but the authors should not be permitted to defer them to future work. The Section 6 descending-iteration theorem also needs either a full proof or an explicit caveat."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nShort version: this is a real contribution to probabilistic program verification. The mop transformer, the scalarization equality (Theorem 7.1), the halfspace characterization (Theorem 7.3), and the lower-bound loop rules based on dAST/dCT are new and well motivated. The case studies are illuminating, especially the robot and casino, and the paper is honest about the gap between almost-achievability and exact synthesis.\n\nThe body of the theory is mostly in good shape. The reader's worry about Scott closed plus downward closed implying topological closedness is, on inspection, supported by the footnote to Theorem 7.1; that part holds. The halfspace separation in Theorem 7.3 is intricate but reasonable, and the compactness reductions in Theorems 6.7 and 7.3 are sound.\n\nThe real soft spot is Theorem 10.6, operational soundness of mop, which is the load-bearing step for Corollary 10.7 (mop equals the Scott closure of the achievable value vectors). Its proof is two sentences. The ⊒ direction 'essentially shows' that mop is a fixed point of the Bellman operator; the converse is 'proven via induction on the program structure' using a compositionality lemma that is never stated. The cited analogy, Batz et al. 2024b Theorem 6, is a scalar weakest-preexpectation theorem; it does not cover the convex Hoare powerdomain, Minkowski sums, or operational configurations with intermediate program stacks. This is a genuine, load-bearing gap. It is not obviously wrong—the result may well be true—but a referee should demand a complete proof or a machine-checked version.\n\nLesser issues: the Lean footnote in Section 8.1 is unverifiable from the text; a link or artifact would settle it. Some case-study invariants are asserted with 'we omit the calculations' (e.g., the robot). These are minor if the main theorem is fixed.\n\nWho this is for: anyone working on weakest preexpectations, programmatic strategy synthesis, or multiobjective MDPs. It deserves a serious referee, so I would send it out. But I would not accept it as is. The missing proof of Theorem 10.6 should be supplied, and the Lean claim substantiated.\n\nRecommendation: major revision, with the operational soundness proof as the required change.","headline":"A serious multiobjective preexpectation calculus that is mostly sound, but the operational soundness theorem is a sketch rather than a proof, and the whole paper leans on it.","tokens_in":52149,"tokens_out":3284,"would_cite":true,"duration_ms":30483,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q55","68Q60","68Q87","90C29"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper shows that the almost-achievable trade-offs of a probabilistic program form exactly the least fixed point of a Bellman operator on convex value sets, computed by a syntactic transformer.","keywords":["multiobjective preexpectation","Pareto front","probabilistic programs","weakest preexpectation","convex Hoare powerdomain","strategy synthesis","scalarization","Markov decision processes"],"falsifier":"Take the program that in round $i$ either terminates with reward vector $(1-2^{-i}, 2^i)$ or continues. Compute $\\mathrm{mop}[\\![C]\\!](\\mathrm{dwc}(\\{(x,y)\\}))$ and compare it with the halfspace intersection $\\bigcap_{w\\in W}\\{x \\mid w\\cdot x \\le \\mathrm{wp}[\\![C]\\!](w\\cdot f)(\\sigma)\\}$. If the two sets differ at the point $(1,\\infty)$, or if $\\max\\{w\\cdot x \\mid x\\in \\mathrm{mop}[\\![C]\\!](\\mathrm{dwc}(\\{f\\}))(\\sigma)\\}$ differs from $\\mathrm{wp}[\\![C]\\!](w\\cdot f)(\\sigma)$ for a single weight $w$, the compactness foundation behind the scalarization theorems is refuted.","tokens_in":51084,"feed_emoji":"🎯","tokens_out":21440,"duration_ms":186194,"temperature":0.7,"pith_summary":"Probabilistic programs with nondeterministic choices model planning problems where a strategy resolves the nondeterminism to optimize expected outcomes. This paper asks not for the best value of a single objective but for the whole set of value vectors simultaneously achievable by randomizing over program refinements, and it proves that this set is computable by a program-level transformer, the multiobjective preexpectation transformer $\\mathrm{mop}$, a conservative extension of weakest preexpectations. $\\mathrm{mop}$ maps a tuple of postexpectations to an element of the convex Hoare powerdomain, supports invariant-based loop proofs, and for $n=1$ collapses to the classical weakest preexpectation. The load-bearing result is that $\\mathrm{mop}$ coincides with the Scott closure of the achievable vectors and, operationally, with the least fixed point of a generalized Bellman operator on the induced countable-state MDP. A sympathetic reader should care because this gives a deductive, syntax-directed calculus for Pareto-front reasoning over infinite-state MDPs, together with rules for synthesizing the witnessing mixed determinizations.","feed_headline":"A transformer maps probabilistic programs to their Pareto fronts","feed_subtitle":"A program-level calculus handles infinite-state MDPs symbolically, replacing finite-state enumeration with proof rules.","key_machinery":"The central object is the convex Hoare powerdomain $\\mathbb{H}$: nonempty, downward-closed, convex-closed, and Scott-closed subsets of $\\mathbb{R}^n_{\\ge 0}$, used to represent the region under the Pareto front. The multiobjective preexpectation transformer $\\mathrm{mop}$ lifts each weakest-preexpectation rule to this domain; for loops it takes the least fixed point of the characteristic function $\\Phi_{\\mathrm{mop}}(X) = [\\neg\\varphi]\\cdot F \\oplus [\\varphi]\\cdot \\mathrm{mop}[\\![C']\\!](X)$. Two identities carry the argument: scalarization ($\\mathrm{wp}$ of the weighted sum $w\\cdot f$ is the maximum of $w\\cdot x$ over the $\\mathrm{mop}$ set) and halfspace reconstruction (the $\\mathrm{mop}$ set is the intersection of the supporting halfspaces over all weight vectors). Its operational counterpart is the generalized Bellman operator $\\Phi_M^{\\mathrm{Pareto}}$ on multivalue functions, whose least fixed point over the program's MDP coincides with $\\mathrm{mop}$.","core_discovery":"The paper's own formulation of the central claim is Corollary 10.7: for every program $C$, tuple of postexpectations $f$, and state $\\sigma$, $\\mathrm{mop}[\\![C]\\!](\\mathrm{dwc}(\\{f\\}))(\\sigma) = \\mathrm{cl}(\\mathrm{Ach}^{C,f}_\\sigma)$, i.e. the transformer returns exactly the Scott closure of the set of value vectors achievable by mixed determinizations, and the maximal elements of this set are the Pareto front. This is obtained through operational soundness (Theorem 10.6): $\\mathrm{mop}$ is the least fixed point of a generalized Bellman operator on convex sets of reward vectors over the countable-state, finite-action MDP induced by the program, with no finite-state assumption. The companion identities are scalarization (Theorem 7.1), $\\mathrm{wp}[\\![C]\\!](w\\cdot f)(\\sigma)=\\max\\{w\\cdot x \\mid x\\in \\mathrm{mop}[\\![C]\\!](\\mathrm{dwc}(\\{f\\}))(\\sigma)\\}$, and halfspace reconstruction (Theorem 7.3), $\\mathrm{mop}[\\![C]\\!](\\mathrm{dwc}(\\{f\\}))(\\sigma)=\\bigcap_{w\\in W}\\{x \\mid w\\cdot x\\le \\mathrm{wp}[\\![C]\\!](w\\cdot f)(\\sigma)\\}$. From these the paper derives sufficient conditions for exact synthesis of Pareto-optimal mixed determinizations and a Straszewicz-style guarantee that every extreme point can be approximated arbitrarily closely by synthesized witnesses.","pith_inferences":["Multiobjective refutation could be reduced to single-objective proof obligations: to show a point is not achievable it suffices to find one weight vector whose supporting halfspace excludes it, and each such obligation is a standard wp query.","The paper reports that key invariants were machine-proposed and machine-checked while some loop calculations are delegated as straightforward; this points to invariant discovery, not the calculus, as the practical bottleneck, and automation of convex-Hoare invariant search is the natural next step.","Because mixed determinizations use only finitely supported distributions, synthesized strategies remain executable as initial coin flips; moving to infinite mixtures would need a continuity result outside the current rules.","The framework is built around reachability-style expectations, so translating discounted or long-run average objectives into bounded reachability rewards over an expanded state space is a plausible route to extend the calculus."],"forward_implications":["For any point in the multiobjective preexpectation, some mixed determinization realizes the point up to arbitrarily small error; if the set of determinization values is Scott closed, exact realization follows.","Weighted-sum optimization is complete for exposed Pareto points, and every non-exposed extreme point can be approached arbitrarily closely by synthesized determinizations.","The calculus conservatively extends weakest preexpectations: with a single objective, mop returns the downward closure of the ordinary wp value.","Multiobjective invariants give sound loop proofs: superinvariants bound the least fixed point from above; subinvariants bound it from below under demonic almost-sure termination with bounded objectives or demonic certain termination; and lower omega-invariants give lower bounds without side conditions.","The equality with the Bellman operator transfers multiobjective MDP verification to countable-state, finite-action MDPs at program level, bypassing the finite-state restriction of earlier multiobjective MDP work."],"supporting_citations":[{"why":"Supplies the weakest-preexpectation calculus for probabilistic programs that mop conservatively extends.","marker":"[McIver and Morgan 2005]"},{"why":"Introduces probabilistic predicate transformers, the single-objective calculus whose rules mop lifts.","marker":"[Morgan et al. 1996]"},{"why":"Gives programmatic strategy synthesis, the determinization relation and optimal pure determinizations used to build witnessing mixed determinizations.","marker":"[Batz et al. 2024a]"},{"why":"Provides the convex Hoare powerdomain in which multiobjective preexpectations live.","marker":"[Abramsky and Jung 1995]"},{"why":"Supplies the generalized Bellman operator on convex sets of reward vectors whose least fixed point mop matches.","marker":"[Chen et al. 2013a]"},{"why":"Establishes that memoryless schedulers suffice for closed achievable rewards, used to connect program determinizations with MDP schedulers.","marker":"[Forejt et al. 2011]"},{"why":"Provides the template for operational soundness of wp against MDP semantics that Theorem 10.6 follows.","marker":"[Batz et al. 2024b]"},{"why":"Supports the separating hyperplane theorem and Straszewicz's theorem used in halfspace reconstruction and approximate synthesis.","marker":"[Rockafellar 1970]"}],"fun_headline_variants":["Probabilistic program transformer finds Pareto fronts symbolically","Infinite-state MDPs: symbolic Pareto front synthesis","Multiobjective strategy synthesis without finite-state limitation","Program calculus yields Pareto-optimal mixed strategies"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every element of the convex Hoare powerdomain is compact in the extended nonnegative orthant with the convention $0\\cdot\\infty=0$, so along any weight direction a maximum is attained and any point outside the set can be separated by a supporting halfspace; if that compactness fails, the scalarization equality, the halfspace characterization, and the descending fixpoint iteration lose their foundation.","fun_headline_variants_meta":{"raw":{"variants":["Probabilistic program transformer finds Pareto fronts symbolically","Infinite-state MDPs: symbolic Pareto front synthesis","Multiobjective strategy synthesis without finite-state limitation","Program calculus yields Pareto-optimal mixed strategies"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000284,"raw_usage":{"total_tokens":1716,"prompt_tokens":1027,"completion_tokens":689,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":643,"completion_tokens_details":{"reasoning_tokens":629}},"tokens_in":643,"tokens_out":689,"duration_ms":6770,"temperature":1.0,"reasoning_tokens":629,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:01:11.808809+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the program that in round $i$ either terminates with reward vector $(1-2^{-i}, 2^i)$ or continues. Compute $\\mathrm{mop}[\\![C]\\!](\\mathrm{dwc}(\\{(x,y)\\}))$ and compare it with the halfspace intersection $\\bigcap_{w\\in W}\\{x \\mid w\\cdot x \\le \\mathrm{wp}[\\![C]\\!](w\\cdot f)(\\sigma)\\}$. If the two sets differ at the point $(1,\\infty)$, or if $\\max\\{w\\cdot x \\mid x\\in \\mathrm{mop}[\\![C]\\!](\\mathrm{dwc}(\\{f\\}))(\\sigma)\\}$ differs from $\\mathrm{wp}[\\![C]\\!](w\\cdot f)(\\sigma)$ for a single weight $w$, the compactness foundation behind the scalarization theorems is refuted.","supporting_citations":[{"cited_title":"1995.Domain theory","cited_arxiv_id":null,"evidence_quote":"Provides the convex Hoare powerdomain in which multiobjective preexpectations live."}],"review_version":1}