{"id":"0dc21166-ffcb-496c-b68d-0d0d722f3371","arxiv_id":"2506.10803","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A hypergraph formalism with three edge types encodes package dependencies, conflicts, and optional deps, and a SAT-based solve can in principle span many package ecosystems in one pass.","lead":"This paper defines HyperRes, a hypergraph-based formal model of software dependency resolution, and shows how package managers from many language and OS ecosystems can be translated into it. If the approach matures, a single resolver could handle dependencies across ecosystems that today are managed separately.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Cross-ecosystem resolution is only as valid as the unverified metadata translations; the one resolved example uses ad-hoc unversioned Debian dependencies, so the claimed mechanical .deb deployment is not established.","rationale":"The reader's weakest assumption is the same one I regard as load-bearing: the ecosystem-to-hypergraph translations must preserve exactly the native package managers' semantics. HyperRes's own definitions make this premise external: versions are uninterpreted, so the conversion of version ranges into hyperedge sets is not justified within the formalism. The paper gives no evidence—no artifact, no comparison—that this conversion is correct. Figure 11, the only cross-ecosystem resolution, explicitly relies on unversioned Debian dependencies for the core system packages, so it does not exercise the version-faithfulness required by the headline claim. A differential test across the three ecosystems would settle the matter. I agree with the CONDITIONAL verdict: the formal core is credible (the NP-completeness proof and SAT reduction in §3 are sound), but the central empirical claim is unverified. The acyclicity definition in §4.2.2 is also defective, but it is secondary to the translation-faithfulness question and can be fixed without touching the main architecture.","tokens_in":25531,"tokens_out":7555,"duration_ms":86192,"concrete_test":"Differential fidelity test: for a random sample of 1,000 packages from opam, Cargo, and Debian, translate each package's dependency formula with the §5.2 tool, resolve with the SAT encoder, and independently resolve the same query with the native package manager (opam, cargo, apt on a Debian 10 container); the translation is faithful only if the HyperRes-selected versions are a subset of the native resolver's accepted versions and the resolved graph is deployable with the native tooling. Run this on the Figure 11 polars.1.0.0 query first, and include the generated hypergraph and resolver output as an artifact.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Sec. 5.2 reports implemented translators for ~1.7M packages but ships no code or data and gives no fidelity check against native resolvers. The formalism deliberately attaches no semantics or ordering to versions (§3.1), so every version-range expansion such as 'ocaml >= 4.14.0 & < 5.0.0' (§1.1.1) into an explicit hyperedge codomain is an external, unverified step. If that expansion does not exactly match the set of versions a native package manager (opam, apt, cargo) would consider valid for the same formula, then a HyperRes solution can select packages the native resolver would reject, and the abstract's promise to 'solve dependency constraints across' ecosystems is void. The sole cross-ecosystem demonstration, Figure 11, resolves a query for opam's polars.1.0.0 and the authors state that in that project 'Debian dependencies are ad-hoc and unversioned' (Sec. 5.2), so this example cannot support the claimed binary-compatible .deb deployment.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces HyperRes, a hypergraph-based formalism for dependency resolution in which vertices are package name-version pairs and labelled hyperedges represent strong dependencies, optional dependencies, and conflicts. It defines the DependencyResolution decision problem, proves it NP-complete via a reduction from SAT, gives a CNF-SAT encoding for solving it, and sketches encodings of APT, opam, Cargo, and Nix features. It then claims to bridge ecosystems by translating metadata from many package managers into HyperRes and resolving dependencies across ecosystems in one pass, supported by a prototype covering roughly 1.7 million packages and one cross-ecosystem resolved example involving opam, Cargo, and Debian. The paper also outlines a vision for bidirectional metadata translation between ecosystems.","tokens_in":25639,"tokens_out":7618,"duration_ms":90466,"significance":"If the formal core is correct, HyperRes offers a clean and useful common abstraction for comparing and combining package managers, and the NP-completeness proof and SAT encoding are straightforward but serviceable. The survey of 36 package managers and the classification of their properties into a common pipeline is a useful contribution. However, the central cross-ecosystem claim currently rests on unverified translations and a single example whose Debian dependencies are admitted to be ad-hoc and unversioned. The paper ships no code, data, or fidelity checks against native resolvers, so the empirical part is a demonstration sketch rather than a validated system. The formalization of opam's acyclic-resolved-graph requirement in §4.2.2 is also incorrect as written, which weakens the claim that HyperRes can faithfully model opam. The paper is honest about some of these limitations, but they are load-bearing for the main claims.","major_comments":[{"comment":"The formal condition for opam's acyclic resolved graph is not acyclicity. The text states that for any sequence of edges e1,...,en in G where ei = (pi, ei), it holds that pi != p_{i+1}; even if we charitably read this as edges (pi, e_i) with e_i the head, a two-edge cycle (A,B),(B,A) satisfies p1=A != p2=B and yet is cyclic. The condition is also ill-formed because ei is used both as an edge and as a package. Moreover, the SAT encoding in §3.3 contains no acyclicity constraint at all, so the paper does not establish that HyperRes, as formally defined and encoded, can enforce the opam resolved-graph requirement or the 'post' exception mentioned in the same section.","section":"§4.2.2"},{"comment":"The claim in the abstract that HyperRes can 'solve dependency constraints across' ecosystems is supported only by one resolved graph (Figure 11). The authors state that in this example the Debian dependencies are 'ad-hoc and unversioned', and no comparison against native resolvers (opam, cargo, apt) is reported, no translator code or data are released, and no fidelity measurement is given for the claimed 1.7-million-package translation corpus. As it stands, the cross-ecosystem resolution result is not reproducible and cannot substantiate the asserted ability to produce binary-compatible, deployable package sets. The authors should provide the translators, a validation protocol that compares HyperRes solutions with native resolver outputs on a meaningful sample, or at minimum a precise statement of which translations were actually exercised.","section":"§5.2"},{"comment":"HyperRes deliberately attaches no semantics or ordering to versions, but the translation of a version formula such as 'ocaml >= 4.14.0 & < 5.0.0' into an explicit set of version vertices is an external, unverified step. If that expansion does not exactly match the version-comparison and range semantics of the native package manager, a HyperRes solution may select packages the native resolver would reject, or miss valid ones. The paper does not specify the expansion algorithm for any ecosystem or provide evidence that its expansions agree with native behavior. Since the faithfulness of these translations is the premise for the cross-ecosystem validity claim, this gap needs to be addressed either by formal proofs of translation equivalence or by empirical validation against native resolvers.","section":"§1.1.1 and §3.1"}],"minor_comments":[{"comment":"The clause '∀(p,d)∈D, ∀e∈d, ∃X_(p,e)' uses an undefined symbol D; it should range over the dependency relation, e.g., over all pairs (p,d) with d∈deps(p).","section":"§3.3"},{"comment":"In the at-most-one clause for optional dependencies, the quantifier ranges over e1,e2∈d; it should range over e1,e2∈o, since o is the optional dependency set.","section":"§3.3"},{"comment":"The text says both openssh-server and dropbear-bin provide the virtual package openssh-server, but the running example in §1.1.6 uses the virtual package ssh-server. The example is inconsistent and should be corrected.","section":"§4.1.4"},{"comment":"The definition of FV_n uses an undefined variable s: 'FV_n = {(v,s) | f∈F(n,v), v∈V_n}' should presumably be '{(v,f) | f∈F(n,v), v∈V_n}'.","section":"§4.3.2"},{"comment":"The sentence 'Not that we omit separators between versions and features for the sake of brevity' should be 'Note that we omit separators...'.","section":"§4.3.2"},{"comment":"The word 'Similarity' appears where 'Similarly' is intended.","section":"§3.1"}],"recommendation":"major_revision","confidential_remarks":"The opam acyclicity issue is a specific, fixable formal error, but it is load-bearing for the modelling claim. The larger concern is the lack of evidence for translation fidelity: for a paper whose central claim is cross-ecosystem resolution, the absence of released translators and validation against native package managers is a significant gap. I would encourage the editor to require the authors to either supply a reproducible artifact or substantially scale back the empirical claims to a 'prototype demonstration' framed as future work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: treat HyperRes as a formal proposal with a good survey, not as a demonstrated cross-ecosystem resolver. The hypergraph formalism is clean, the NP-completeness reduction and SAT encoding are essentially correct, and the modelling sections for APT, opam, Cargo, and Nix are genuinely instructive. The paper earns a serious referee.\n\nWhat's actually new: the labelled-hyperedge presentation of dependency/optional/conflict relationships, the cross-ecosystem labelling in Sec. 5.1, and the survey table. Prior SAT/CUDF work stays inside one ecosystem. The paper also gives a fairly honest inventory of package-manager features.\n\nSoft spots, in order:\n\n1. Sec. 4.2.2's formalization of opam's acyclic-resolved-graph requirement is wrong. The condition 'p_i != p_{i+1}' on consecutive edge sources does not forbid a cycle like A→B→A; it only requires that consecutive edges start from different vertices. The prose describes what opam needs, but the formula doesn't capture it. This is a genuine bug in a modelling section, though fixable.\n\n2. The empirical claims outrun the evidence. The abstract says 'dozens' of translators and 'comprehensively demonstrate'; the body lists ten translators, ships no code or data, and gives one resolved example whose Debian dependencies the authors themselves call 'ad-hoc and unversioned' (Sec. 5.2). The stress-test note is right about that. The claimed mechanical .deb deployment is not established by this paper.\n\n3. The cross-ecosystem labelling (Sec. 5.1) is under-specified for packages with the same name and version in different ecosystems; P_t is defined with N not N_t, making the labelling ambiguous. Minor but should be fixed.\n\n4. The SAT encoding has small typos in the optional-dependency clauses: the at-most-one clauses range over e1,e2 in d instead of o, and the structure of the first optional clause is odd. Not load-bearing, but a referee should ask for a cleaner presentation.\n\nThe version-expansion issue is real but not disqualifying: the paper is explicit that HyperRes attaches no semantics to versions, so the translators are external, unverified components. A formal proposal can leave that as future work, but the paper should not present the demonstration as comprehensive.\n\nWho should read it: people working on multi-ecosystem build tooling, SBOMs, or SAT-based resolvers. The survey alone is useful. Recommend: send to peer review, with a request for artifacts and a fidelity check against native resolvers. CONDITIONAL, not reject.","headline":"HyperRes is a sound formal proposal with a genuinely useful survey, but its cross-ecosystem demonstration and its acyclicity encoding do not yet hold up; send it to review with requests for artifacts and fixes.","tokens_in":26402,"tokens_out":2190,"would_cite":true,"duration_ms":25200,"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":"The paper claims that all versioned dependency resolution can be captured in one hypergraph formalism, and that a single SAT pass over that hypergraph can resolve projects spanning OCaml, Rust, Python, and Debian together.","keywords":["package management","dependency resolution","hypergraph","SAT solving","cross-ecosystem interoperability","version constraints","package metadata translation","software supply chain"],"falsifier":"Resolve a specific real multi-ecosystem project, such as the paper's polars example, twice: once with HyperRes and once with the native package managers (opam, Cargo, APT) running separately; if the HyperRes result contains a version the native tools reject, omits a version the native tools require, or fails to find a solution when the native tools succeed, the faithfulness claim is falsified. A sharper check is to translate a known opam package with a complex version formula into HyperRes and verify that the set of satisfying assignments equals the set of native-resolver selections.","tokens_in":25141,"feed_emoji":"📦","tokens_out":8408,"duration_ms":85809,"temperature":0.7,"pith_summary":"The paper sets out to prove that versioned dependency resolution, across operating-system and language package managers alike, has a single common core: a directed hypergraph whose vertices are package name-version pairs and whose hyperedges are labelled as strong dependencies, optional dependencies, or conflicts. It claims this HyperRes formalism is expressive enough to model real managers such as APT, opam, Cargo, and Nix, and that resolution over the hypergraph is a mechanically solvable SAT instance even though the decision problem is NP-complete. From there it argues that ecosystems can be joined in one hypergraph, so a project mixing OCaml, Rust, Python, and system libraries resolves in a single pass, and that package metadata can be translated bidirectionally between ecosystems—for instance, mechanically producing a Debian binary package from a multi-language source project. The reason a reader should care is that, if true, the manual per-distribution, per-architecture, per-language packaging labour collapses into one semantic core plus faithful translations.","feed_headline":"One hypergraph resolves dependencies across all major package managers","feed_subtitle":"HyperRes turns every package manager into one SAT-solvable hypergraph, so mixed-language projects resolve in one pass.","key_machinery":"The central object is the resolution hypergraph: a directed hypergraph whose vertices are package name-version pairs, with hyperedges labelled $\\delta$ (dependency), $\\sigma$ (optional dependency), or $\\gamma$ (conflict), together with the SAT encoding that turns any such hypergraph and query set into a CNF instance. The hypergraph carries the whole argument because it gives a single place where versioned constraints from different ecosystems can coexist, and the SAT encoding is what makes resolution mechanical; the paper also shows how to absorb features into versions, architecture into packages, and boolean package formulae into virtual packages, so the one mechanism covers APT, opam, Cargo, and Nix semantics.","core_discovery":"The central discovery is that the shared essence of package managers is a hyperedge-labelled directed hypergraph. Vertices are packages as name-version pairs; hyperedges carry one of three labels—dependency (one package needs at least one of a set), optional dependency (used only if already present), or conflict (cannot coexist). Dependency resolution is defined as mapping a query set and hypergraph to a resolved graph satisfying four conditions: the query packages are present, every dependency is satisfied by exactly one chosen package, optional dependencies are honoured when their partner is present, and no conflicts are included. The paper proves the DependencyResolution decision problem is NP-complete by a polynomial reduction from SAT, and also supplies the reverse encoding, showing any instance can be handed to a SAT solver. Adding an ecosystem labelling to the hypergraph lets one resolution span multiple package ecosystems, with translations 'on-ramping' metadata into the graph and 'off-ramping' selected packages to native installers; the paper reports translations covering just over 1.7 million packages across APK, Cabal, Cargo, CentOS, Debian, Fedora, Homebrew, opam, OpenSUSE, and Pacman, and demonstrates a resolved subgraph for opam's polars library pulling in Cargo and Debian packages.","pith_inferences":["The paper's deliberate decision to attach no ordering or semantics to versions pushes all faithfulness onto the translation layer; a natural testable extension is to fuzz-compare HyperRes resolutions against native resolvers on random dependency cones to check that the expanded version sets exactly match native selections.","If the 1.7-million-package translation were released and validated, HyperRes would effectively be a common interchange format for package metadata, which could push package managers toward a shared 'protocol'—the paper sketches this possibility but does not implement it.","Encoding features as extra versioned packages (Section 4.3.2) may create a combinatorial explosion for packages with many feature combinations; the paper does not analyze this blow-up, so a practical extension would be to measure vertex growth on real Cargo packages.","The cross-ecosystem resolution idea suggests a benchmark for reproducibility: take the same multi-language project, resolve it with HyperRes and with the union of native managers, and check whether the resulting filesystem trees are binary-compatible; the paper's Debian-dependencies note admits these are currently ad-hoc and unversioned."],"forward_implications":["If HyperRes is correct, one SAT-based resolution over a cross-ecosystem hypergraph yields a consistent, deployable package set for a mixed-language project, without switching users away from their existing package managers.","Package metadata becomes bidirectionally translatable between ecosystems, so a Debian binary package could be produced mechanically from OCaml, Rust, or Python metadata, reusing packaging knowledge instead of repeating per-distribution labour.","System and hardware dependencies—kernel versions, GPU drivers, CPU architectures—can be expressed as versioned cross-ecosystem packages, making deployments reproducible instead of relying on ad-hoc and unversioned assumptions.","The same hypergraph can serve as a common layer for generating software bills of materials and reasoning about supply-chain security across language and OS ecosystems.","Because DependencyResolution is NP-complete yet solvable by the given SAT encoding, solver performance is the practical bottleneck, and the paper reports that it scales with the dependency cone rather than the full repository."],"supporting_citations":[{"why":"The earlier Opium result that package installation can be modelled as SAT, which HyperRes explicitly lifts to hypergraphs.","marker":"[58]"},{"why":"Supplies the NP-completeness of SAT that the reduction relies on when proving DependencyResolution is NP-hard.","marker":"[24]"},{"why":"Supplies the directed-hypergraph terminology and theory the formalism builds on.","marker":"[20]"},{"why":"The opam manual defines the package and version formulae and external dependency syntax that the opam translation must preserve.","marker":"[2]"},{"why":"Debian policy's relationship rules justify the encoding of virtual packages and conflict semantics in the hypergraph.","marker":"[7]"},{"why":"The Cargo resolver's semantic-versioning constraint, allowing concurrent major versions, is the basis for the Cargo model.","marker":"[5]"},{"why":"The Nix store derivation model is the exact-dependency special case that HyperRes reduces to when hyperedge codomains are singletons.","marker":"[28]"}],"fun_headline_variants":["Hypergraph model unifies package managers across ecosystems","SAT-solvable hypergraph handles dependencies across package managers","Package resolution becomes one hypergraph, NP-complete but solvable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that translating each ecosystem's metadata into HyperRes—especially expanding version formulas such as 'ocaml >= 4.14.0 & < 5.0.0' into explicit version sets—preserves exactly the set of valid package selections the native package manager would compute, since HyperRes itself attaches no semantics or ordering to versions.","fun_headline_variants_meta":{"raw":{"variants":["Hypergraph model unifies package managers across ecosystems","SAT-solvable hypergraph handles dependencies across package managers","Package resolution becomes one hypergraph, NP-complete but solvable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00039,"raw_usage":{"total_tokens":2043,"prompt_tokens":926,"completion_tokens":1117,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":542,"completion_tokens_details":{"reasoning_tokens":1064}},"tokens_in":542,"tokens_out":1117,"duration_ms":10771,"temperature":1.0,"reasoning_tokens":1064,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:22:05.829429+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Resolve a specific real multi-ecosystem project, such as the paper's polars example, twice: once with HyperRes and once with the native package managers (opam, Cargo, APT) running separately; if the HyperRes result contains a version the native tools reject, omits a version the native tools require, or fails to find a solution when the native tools succeed, the faithfulness claim is falsified. A sharper check is to translate a known opam package with a complex version formula into HyperRes and verify that the set of satisfying assignments equals the set of native-resolver selections.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The earlier Opium result that package installation can be modelled as SAT, which HyperRes explicitly lifts to hypergraphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the directed-hypergraph terminology and theory the formalism builds on."},{"cited_title":"OCaml Package Manager, The opam manual","cited_arxiv_id":null,"evidence_quote":"The opam manual defines the package and version formulae and external dependency syntax that the opam translation must preserve."},{"cited_title":"Debian Policy Manual: Chapter 7 - Declaring relationships between packages","cited_arxiv_id":null,"evidence_quote":"Debian policy's relationship rules justify the encoding of virtual packages and conflict semantics in the hypergraph."},{"cited_title":"Cargo Resolver","cited_arxiv_id":null,"evidence_quote":"The Cargo resolver's semantic-versioning constraint, allowing concurrent major versions, is the basis for the Cargo model."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Nix store derivation model is the exact-dependency special case that HyperRes reduces to when hyperedge codomains are singletons."}],"review_version":1}