{"id":"925a8852-220f-4df6-ae5e-4ca42ad0805a","arxiv_id":"2411.14879","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"For any data type defined by an equivalence relation over sequences, there is a Random Permutation Code that achieves the optimal lossless compression rate, with explicit codes for multisets, clusterings, and graphs.","lead":"Random Permutation Codes shows that 'non-sequential' data such as sets, multisets, graphs, and cluster assignments can be compressed at their true information content by encoding a random ordering of the items and recovering the order bits via bits-back coding. The work unifies several previously published algorithms into a single combinatorial framework and proves their optimality.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"General RPC optimality for arbitrary equivalence relations depends on an unproven uniform-orbit-sampler premise; the thesis only constructs samplers for three special cases.","rationale":"The reader's verdict is CONDITIONAL, and the weakest assumption they identified is exactly the missing uniform orbit sampler for generic equivalence relations. My stress-test confirms this is the most load-bearing gap in the central claim. The published chapters (ROC, RCC, REC) are well-supported and give explicit samplers for multiset, cycle, and edge-permutation equivalence, so the specialized algorithms are credible. The general theorem, however, is the novel contribution that underpins the abstract's 'fully characterized' and 'achieved within the family of RPCs' assertions. Without the proof of Theorem 7.3.2, we cannot tell whether the theorem merely quantifies over an idealized sampler or actually constructs one. The concrete graph-isomorphism instantiation is the sharpest test because it is a natural equivalence relation where the orbit-size computation is known to be hard, yet the relation fits the CRV definition. If the theorem cannot be instantiated there, the general claim is too strong. The Polya Urn 'parameter-free' inconsistency (beta is a parameter in Equation 6.7) is real but minor and does not affect the central CRV/RPC claim. Therefore I agree with the reader and recommend no change to the CONDITIONAL verdict, with the explicit condition that Chapter 7's proof be inspected for the sampler premise.","tokens_in":59477,"tokens_out":14452,"duration_ms":147688,"concrete_test":"Obtain the full proof of Theorem 7.3.2 in Chapter 7 and check whether it constructs, for an arbitrary equivalence relation, an exact uniform orbit sampler and a method to compute orbit size. Then instantiate the theorem for the relation on vertex sequences of graphs where two sequences correspond to the same unlabeled graph up to vertex permutation. Verify that the proof's achievability step can be carried out without solving graph isomorphism (e.g., without computing |[x^n]|). If the proof invokes the sampler or the orbit size as an unconstructed primitive, the general characterization is not proven for all equivalence relations.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract's central claim is that RPCs achieve optimal rates for all CRVs under an arbitrary equivalence relation. The published algorithms (ROC, RCC, REC) each supply an explicit, efficient sampler for the uniform distribution over the relevant equivalence class. For a generic equivalence relation, however, the bits-back construction requires (a) computing the orbit size |[x^n]| and (b) sampling a representative exactly uniformly over that orbit using ANS integer arithmetic. The thesis provides no such sampler for a generic relation and no proof that one can be implemented. This is more than an efficiency gap: for the equivalence relation 'same unlabeled graph up to vertex relabeling', the orbit size is n!/|Aut(G)|, and computing |Aut(G)| is graph-isomorphism-hard. Thus the RPC scheme cannot be implemented with polynomial resources for that relation. If Theorem 7.3.2 proves achievability only under the assumption that these samplers exist as oracles, then the 'full characterization' is conditional on an unproven computational premise, and the claim that optimal rates are 'achieved within the family of RPCs' is established only for the three specialized relations.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The thesis studies lossless source coding of non-sequential data, modeled as equivalence classes of sequences called Combinatorial Random Variables (CRVs). The central claim is that the achievable rate of a CRV is fully characterized by the data distribution and the equivalence relation, and that the optimal rate is achieved by Random Permutation Codes (RPCs), which use bits-back coding with ANS to sample a representative sequence uniformly from the equivalence class. Chapters 4, 5, and 6 present three instantiations: Random Order Coding (ROC) for multisets, Random Cycle Coding (RCC) for clusterings, and Random Edge Coding (REC) for graphs, with algorithmic pseudo-code, complexity analyses, and experiments. Chapter 7 is supposed to unify these under the general CRV/RPC framework and to prove the central optimality theorem (Theorem 7.3.2). The experimental sections show that the specialized codes approach or reach the stated theoretical rates (e.g., REC gap 0.0 in Table 6.1).","tokens_in":59664,"tokens_out":5841,"duration_ms":67480,"significance":"If the general framework is correct, the thesis would unify three previously published algorithms and give a clean information-theoretic characterization of compressing equivalence classes of sequences, with concrete algorithmic tools. The specialized chapters are a genuine strength: ROC, RCC, and REC are explicit, the bits-back constructions are well specified, the complexity claims are concrete, and the experiments support the theory for those three models. The Polya-urn model used with REC is attractive because it is integer-arithmetic only and gives competitive results on large sparse graphs. However, the significance of the claimed full characterization, as opposed to three special cases, depends entirely on Theorem 7.3.2, whose statement and proof are not present in the reviewed text; the general achievability also relies on an unproven computational premise about uniform orbit sampling for arbitrary equivalence relations. These issues prevent me from verifying the thesis-level claim at this stage.","major_comments":[{"comment":"The central theorem is missing. The list of theorems (p. ix) and the chapter outline promise \"Theorem 7.3.2 (Optimality of CRV Codes)\", and the abstract's claims of a \"full characterization\" and optimal rates \"achieved within the family of RPCs\" rest on it, but the reviewed text contains no statement or proof of this theorem. Please include the complete statement with all assumptions (discrete alphabet, finite support, the role of the equivalence relation, and whether the theorem is asymptotic or finite-block) and a full proof.","section":"Chapter 7 / Theorem 7.3.2"},{"comment":"The general achievability result presumes that for an arbitrary equivalence relation one can compute the orbit size |[x^n]| and sample a representative uniformly from the orbit using ANS integer arithmetic. The manuscript constructs such samplers only for multisets, cycles, and edge permutations. This is not merely an efficiency gap: for an equivalence relation such as unlabeled graph isomorphism, the orbit size is n!/|Aut(G)| and computing |Aut(G)| is graph-isomorphism-hard. The paper should either state that Theorem 7.3.2 treats the orbit sampler as an oracle, or restrict the claimed characterization to equivalence relations admitting efficient uniform orbit samplers. Without one of these moves, \"achieved within the family of RPCs\" is established only for the three specialized relations.","section":"Chapter 7 / Definition 7.1.2 and Section 7.3"},{"comment":"The optimality results for RCC and REC are model-specific: RCC is optimal for the product-of-cluster-sizes model in Eq. (5.13), and REC is optimal for edge-permutation-invariant models in Definition 6.3.1. The general characterization in the abstract appears to claim optimality for arbitrary distributions over arbitrary CRVs, which is a substantially stronger statement. The bridge between these model-specific optimality proofs and the general CRV theorem is not visible in the text; please spell out how an arbitrary distribution over an equivalence-class alphabet is handled by the RPC encoder, or clarify the restricted class of distributions for which optimality is claimed.","section":"Chapters 5-6 versus Chapter 7"},{"comment":"The optimality statements are made in the ANS large-state regime, and Section 2.2.3 explicitly states that there is no known method guaranteed to avoid the initial-bits problem. Theorem 6.3.4 amortizes the initial-bits and log m overheads only as m tends to infinity. If Theorem 7.3.2 is an asymptotic result, this should be stated explicitly in the abstract and theorem; if a finite-length or non-asymptotic claim is intended, a finite-block length bound is needed.","section":"Sections 2.2.3 and 6.3.4"}],"minor_comments":[{"comment":"The text calls Polya's Urn \"parameter-free\" twice, but the model in Eq. (6.6) depends on a positive concentration parameter β. Please clarify whether β is fixed a priori, optimized, or transmitted, and adjust the \"parameter-free\" wording accordingly.","section":"Section 6.3"},{"comment":"The column header \"1 8n log|Π|\" appears to have a formatting error and should read something like \"(1/8n) log |Π|\" with units of bytes per element; this should be corrected for readability.","section":"Table 5.1"},{"comment":"The thesis says it treats \"graphs\" as a CRV, but REC only covers labeled graphs under edge-permutation and within-edge vertex-permutation equivalence; it does not cover vertex-relabeling/isomorphism equivalence. Please make this distinction explicit in the contributions and in the CRV examples of Chapter 7.","section":"Preface and Section 3.6"},{"comment":"There is a spelling error in \"distribtuion\"; the manuscript would benefit from a final proofreading pass for such typos.","section":"Section 4.8.2"}],"recommendation":"major_revision","confidential_remarks":"The decisive issue is that the submitted file appears to omit the entirety of Chapter 7, including Theorem 7.3.2, which is the load-bearing result for the abstract's full-characterization claim. If this is an artifact of the submission, the authors should be asked to provide the complete version. The graph-isomorphism-hardness example is a concrete and useful check: if the authors respond by restricting the general theorem to efficiently samplable equivalence relations, the contribution would still be solid, but the advertised scope must be adjusted accordingly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You asked for a quick read of Severo's thesis. Here's the short version: the three specialized codecs (ROC, RCC, REC) are legitimate, published results, and the thesis does a nice job showing they all fit under one bits-back umbrella. The novel CRV/RPC framework is the part that needs scrutiny, and the proof of the central optimality theorem is not in the text I saw.\n\nWhat's genuinely new is the abstraction: a Combinatorial Random Variable is an equivalence class of sequences, and a Random Permutation Code removes the order information by bits-back sampling a representative uniformly from the orbit. That is a clean way to unify multiset, clustering, and graph compression, and it gives a unified explanation of why the earlier algorithms achieve the rates they do. The early chapters on ANS and bits-back are also competently written and could serve as a useful reference.\n\nThe soft spot is the scope of the general claim. The abstract says achievable rates are 'fully characterized' and achieved by RPCs. That holds for the three relations with explicit samplers. For a generic equivalence relation, the construction requires computing orbit sizes and sampling uniformly from the orbit. For unlabeled graphs, the orbit size is n!/|Aut(G)|, and computing |Aut(G)| is graph-isomorphism-hard. So either the theorem assumes an oracle, or the characterization is really about information-theoretic limits, not algorithmic achievability. The thesis should separate those two statements. This is a real gap, not a nitpick.\n\nOne minor point: Polya's Urn is described as parameter-free, but beta appears in its definition. I assume that means no learned parameters, but as written it's confusing and should be corrected.\n\nBottom line: the published codecs stand on their own, and the framework is worth engaging seriously. Send it to a referee who can check Theorem 7.3.2 and the sampler discussion. I'd accept it for review, with major revision expected.","headline":"Solid compilation of three real compression algorithms plus a general framework whose central theorem I could not verify — referee it, but require the missing proof and an explicit treatment of orbit-sampler complexity.","tokens_in":60207,"tokens_out":2832,"would_cite":false,"duration_ms":30846,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A29","94A17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This thesis proves that the optimal lossless code for any unordered, non-sequential data type is the entropy of its equivalence classes, and gives a coding scheme, Random Permutation Codes, that achieves it.","keywords":["lossless source coding","Combinatorial Random Variables","Random Permutation Codes","bits-back coding","asymmetric numeral systems","equivalence classes","multiset compression","graph compression"],"falsifier":"A concrete test is to implement the RPC sampler for an equivalence relation not covered by the thesis, such as isomorphism classes of unlabeled graphs, and compare the code length against $H(\\mathbf{X})$ on an exchangeable distribution; if for some relation the gap fails to vanish as $n$ grows, Theorem 7.3.2 would be false. A laboratory check on the covered cases is to measure ROC's code length against $nH(P)-\\log(n!/\\prod_x n_x!)$ and verify that the residual overhead goes to zero as the ANS state grows.","tokens_in":59229,"feed_emoji":"🗜️","tokens_out":9905,"duration_ms":93868,"temperature":0.7,"pith_summary":"The thesis asks how many bits it really takes to store data whose order carries no meaning—a collection of files, rows in a database, nodes in a graph, or a dataset of images. It formalizes such an object as a Combinatorial Random Variable (CRV): the equivalence class of all sequences that represent the same non-sequential object, with the data type fixed by an equivalence relation $\\sim$ on sequences. The paper's central claim is that the achievable lossless rate of a CRV is fully characterized by the equivalence relation and the data distribution, and that the optimal rate is the entropy of the equivalence-class random variable. Random Permutation Codes (RPCs) achieve this rate by using bits-back coding with asymmetric numeral systems to pick one of the many equivalent sequences at random, banking the bits saved by not transmitting the order, and recovering them exactly at decoding. If correct, the result unifies and completes earlier algorithms for multisets, clusterings, and graphs, and turns \"ignore the meaningless order\" from a heuristic into an exact information-theoretic limit.","feed_headline":"Random Permutation Codes hit the entropy limit for unordered data","feed_subtitle":"A unified bits-back scheme removes the cost of meaningless order and matches the theoretical bound for each data type.","key_machinery":"The central object is the equivalence class $[x^n]$: the set of all sequences that represent the same non-sequential object, whose size $|[x^n]|$ is the number of orderings being discarded. The load-bearing identity is $H(\\mathbf{X}) = H(X^n) - \\mathbb{E}[\\log |[X^n]|]$ for exchangeable sequence distributions: the class entropy equals the sequence entropy minus the order information. Random Permutation Codes realize this identity with ANS decoding as an invertible sampler, uniformly selecting a representative of the class; the state then rises by the sequence code length and falls by $\\log |[x^n]|$, netting the class entropy. The three published instantiations are ROC for multisets (sampling without replacement via a binary search tree), RCC for clusterings (using Foata's canonical cycle notation so cycles become clusters), and REC for graphs (sampling edges and vertex order under Pólya's urn).","core_discovery":"The discovery, proved as Theorem 7.3.2 (Optimality of CRV Codes), is that for an exchangeable distribution over sequences $X^n$ and any equivalence relation $\\sim$, the combinatorial random variable $\\mathbf{X}=[X^n]_\\sim$ has optimal asymptotic lossless rate $H(\\mathbf{X})$, and this rate is attained by a Random Permutation Code. The code encodes the object by sampling one representative sequence from its equivalence class uniformly at random, encoding that representative with the underlying sequence codec, and using bits-back to subtract the $\\log |[x^n]|$ bits that existed only to specify the order. The decoder reverses the steps, restoring the bits, so no information is lost. The thesis also proves a Markov property and a constructive–destructive decomposition for sequences of CRVs, showing the same rate identity holds when non-sequential objects are encoded one after another.","pith_inferences":["Inference: the practical content of the theorem is that rate-optimality reduces to sampler design: for a new data type, the only nontrivial engineering step is a uniform sampler over the equivalence class.","Inference: for equivalence relations whose orbits are hard to sample, such as isomorphism classes of unlabeled structures, the information-theoretic limit may be unreachable in polynomial time, so the open problem is the computational gap, not the rate.","Inference: because the order-saving term is independent of the symbol codec, the method stacks with any improved sequence compressor; the largest percentage gains appear where each element costs few bits, as with cluster ids, rather than where elements are already expensive, as with images.","Inference: a testable extension is to apply the CRV construction to data types not treated here, such as unlabeled trees or permutations modulo rotation; if a uniform orbit sampler exists, the same optimality proof should hold."],"forward_implications":["Multisets of exchangeable symbols, including collections of files or database rows, compress at the multiset's entropy with runtime independent of alphabet size.","Cluster assignments can be stored without ids or labels: RCC recovers the full $\\log|\\Pi|$ order-information saving, which is optimal for the implied cluster-size product model.","Graphs, including directed, undirected, non-simple, and hypergraph variants, compress at the graph's negative log-likelihood under Pólya's urn in quasi-linear time in the number of edges.","Any future equivalence relation with an efficient uniform orbit sampler inherits the optimality guarantee, so the framework is predictive rather than limited to the three worked examples.","Sequences of non-sequential objects, such as nested multisets or evolving clusterings, also achieve the optimal rate through the constructive–destructive decomposition."],"supporting_citations":[{"why":"Bits-back with ANS: supplies the invertible sampling step that spends and recovers the order bits; the formal BB-ANS rate lemma is built on it.","marker":"[72]"},{"why":"Free-energy/bits-back coding: introduces the general principle that a latent degree of freedom can carry information essentially for free.","marker":"[27]"},{"why":"Asymmetric numeral systems: the stack-like entropy coder whose large-state optimality underpins the rate analysis and the sampling procedure.","marker":"[21]"},{"why":"Information-theoretic source coding results, including entropy, Kraft's inequality, and the method of types, used throughout the optimality proofs.","marker":"[18]"},{"why":"Foata's bijection: the canonical cycle representation that lets RCC store clusterings in permutation cycles.","marker":"[25]"},{"why":"Pólya's urn: the parameter-free exchangeable model over which Random Edge Coding is proven optimal.","marker":"[49]"},{"why":"Random Order Coding for multisets: the first of the three specialized RPC instantiations that Chapter 7 unifies.","marker":"[61]"},{"why":"Edge-exchangeable graph compression with bits-back: the graph instance that Chapter 6 develops into Random Edge Coding.","marker":"[62]"},{"why":"Establishes the order-information term $\\log n! / \\prod_x n_x!$ as the gap between sequence and multiset information content; it is the savings target for ROC.","marker":"[76]"}],"fun_headline_variants":["Random Permutation Codes achieve entropy limit for unordered data","Optimal lossless rate for non-sequential data demonstrated","Bits-back coding eliminates order cost, reaches entropy bound","Random permutation codes hit entropy bound for sets and graphs","Entropy-optimal compression for multisets and partitions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The general achievability theorem assumes that for any equivalence relation one can compute the size of an equivalence class and sample one of its sequences uniformly at random using ANS arithmetic; the thesis supplies such samplers only for multisets, clusterings, and graphs, and treats the large-state initial-bits and dirty-bits overhead as negligible without a general proof.","fun_headline_variants_meta":{"raw":{"variants":["Random Permutation Codes achieve entropy limit for unordered data","Optimal lossless rate for non-sequential data demonstrated","Bits-back coding eliminates order cost, reaches entropy bound","Random permutation codes hit entropy bound for sets and graphs","Entropy-optimal compression for multisets and partitions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000292,"raw_usage":{"total_tokens":1748,"prompt_tokens":1036,"completion_tokens":712,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":652,"completion_tokens_details":{"reasoning_tokens":635}},"tokens_in":652,"tokens_out":712,"duration_ms":6775,"temperature":1.0,"reasoning_tokens":635,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:43:37.138297+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete test is to implement the RPC sampler for an equivalence relation not covered by the thesis, such as isomorphism classes of unlabeled graphs, and compare the code length against $H(\\mathbf{X})$ on an exchangeable distribution; if for some relation the gap fails to vanish as $n$ grows, Theorem 7.3.2 would be false. A laboratory check on the covered cases is to measure ROC's code length against $nH(P)-\\log(n!/\\prod_x n_x!)$ and verify that the residual overhead goes to zero as the ANS state grows.","supporting_citations":[{"cited_title":"Free energy coding","cited_arxiv_id":null,"evidence_quote":"Free-energy/bits-back coding: introduces the general principle that a latent degree of freedom can carry information essentially for free."},{"cited_title":"On the Netto inversion number of a sequence","cited_arxiv_id":null,"evidence_quote":"Foata's bijection: the canonical cycle representation that lets RCC store clusterings in permutation cycles."},{"cited_title":"P´ olya urn models","cited_arxiv_id":null,"evidence_quote":"Pólya's urn: the parameter-free exchangeable model over which Random Edge Coding is proven optimal."},{"cited_title":"Com- pressing multisets with large alphabets","cited_arxiv_id":null,"evidence_quote":"Random Order Coding for multisets: the first of the three specialized RPC instantiations that Chapter 7 unifies."},{"cited_title":"One-Shot Compres- sion of Large Edge-Exchangeable Graphs using Bits-Back Coding","cited_arxiv_id":null,"evidence_quote":"Edge-exchangeable graph compression with bits-back: the graph instance that Chapter 6 develops into Random Edge Coding."}],"review_version":1}