{"id":"12c2e967-8784-4cf8-a098-6a1eabe06abb","arxiv_id":"1909.02107","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Complementary partitions let each category be represented by composing entries from several small tables, reducing embedding memory from O(|S|D) to about O(k|S|^(1/k)D) while outperforming the hashing trick.","lead":"This paper shrinks the giant lookup tables that recommendation models use for categorical data by assigning each category a unique combination of a few smaller lookup entries. The approach cuts embedding memory dramatically and, on ad-click data, beats the standard hashing trick in accuracy at similar compression.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Uniqueness is proved for concatenation only; the recommended element-wise multiplication is not injective, so the central uniqueness claim is not supported for the deployed operation.","rationale":"The reader's weakest assumption is exactly the right gap. The paper's formal uniqueness result is essential to distinguish the method from hashing: without a unique final vector, the method is one more collision-prone compression scheme. The proof is honest that it covers concatenation only, but the experimental section and shipped implementation recommend multiplication. Since product collisions are easy to construct, the theorem cannot be silently extended. The practical experiments may still be valid, but the claimed mechanism ('unique embedding for each category without explicit definition') is not established for the recommended configuration. A second concern, that the operation and thresholds were selected on test loss, would matter for the empirical claim, but it is secondary and does not change the conditional verdict. I agree with the reader; no verdict change.","tokens_in":14061,"tokens_out":4715,"duration_ms":52969,"concrete_test":"Run a deterministic synthetic check: with S={0,1,2,3}, k=2, m=2, D=2, initialize W1 rows as (1,1),(2,1) and W2 rows as (2,3),(1,3); apply the quotient-remainder lookup with element-wise multiplication. Print xemb for categories 0 and 3: both equal (2,3), demonstrating a collision under complementary partitions and distinct rows. If the authors instead intend uniqueness only for concatenation, the paper should state so and provide collision analysis or empirical collision rates for multiplication on Criteo.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract's central claim is that complementary partitions define a unique embedding per category. Theorem 1 (Section 4) proves this only for concatenation, and the proof explicitly assumes distinct rows within each table. The experiments then recommend element-wise multiplication (Section 5.3), and the paper states the technique has been incorporated into the DLRM implementation. For multiplication the theorem is false. Concrete counterexample with the quotient-remainder partitions for S={0,1,2,3}, m=2: category 0 uses (quotient row 0, remainder row 0) and category 3 uses (quotient row 1, remainder row 1). Set D=2: table W1 rows a=(1,1), c=(2,1); table W2 rows b=(2,3), d=(1,3). All rows in each table are distinct, and the partitions are complementary, yet a⊙b=(2,3)=c⊙d. More generally, coordinatewise multiplication is a multilinear map from R^{kD} to R^D and is not injective for any k,D>=1; zero divisors and non-invertible entries make collisions constructible even with distinct row vectors. Thus the formal guarantee underlying the 'unique representation' contribution does not hold for the recommended operation. This does not disprove the empirical improvement over hashing, but it means the paper's load-bearing theoretical differentiator is currently unproven and, in the stated generality, false.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes compositional embeddings to compress categorical embedding tables in click-through-rate models. Instead of storing one full table of size |S|×D, it stores k smaller embedding tables, one per set partition of the category set, and composes the selected rows; the partitions are designed to be complementary so that any two categories differ in at least one partition. The paper contributes the quotient-remainder trick as a concrete construction, generalizes it to complementary partitions (including generalized quotient-remainder and Chinese-remainder partitions), proves a uniqueness theorem for concatenation, and reports experiments on the Criteo ad-click dataset with DCN and Facebook DLRM networks. The abstract and the introduction claim that the method yields a unique embedding for every category at memory cost reduced from O(|S|D) to about O(k|S|^{1/k}D), and the experiments recommend element-wise multiplication as the composition operation.","tokens_in":14314,"tokens_out":7186,"duration_ms":78996,"significance":"If the empirical findings hold, the paper offers a simple and practical drop-in compression scheme that improves on the hashing trick at similar parameter counts; the memory-complexity derivation is clean, and the constructive examples of complementary partitions are useful. The use of an external benchmark (Criteo), the comparison of several composition operations, and the release of code in the DLRM repository are concrete strengths. However, the advertised theoretical guarantee is not what is deployed: uniqueness is proved only for concatenation and only under an unenforced row-distinctness assumption, while the recommended element-wise multiplication is not injective. This gap affects the paper's central differentiator, although it does not invalidate the empirical comparison with the hashing trick.","major_comments":[{"comment":"The uniqueness result that supports the abstract is proved only for concatenation (and Appendix C is correct under its assumptions), but the paper's recommended and implemented operation is element-wise multiplication. For multiplication the statement is false even when the complementary-partition condition and the row-distinctness assumption both hold. With S={0,1,2,3}, m=2, D=2 and the quotient-remainder partitions, take W1 rows (1,1),(2,1) and W2 rows (2,3),(1,3); categories 0 and 3 both produce the composed vector (2,3). Thus the central claim 'a unique embedding for each category' does not hold for the deployed operation. The empirical hashing-trick comparison can stand, but the theoretical differentiator must be re-scoped, for example by restricting the uniqueness claim to concatenation or by providing a collision-probability analysis for multiplication.","section":"§4, Theorem 1; §5.3, Algorithm 2"},{"comment":"The theorem assumes that the rows within each embedding table are distinct, but the paper does not state how training preserves this property. Random initialization makes exact duplicates unlikely at initialization, but nothing in the training procedure prevents two rows of a table from becoming equal, and then the proof's 'since the embedding vectors in each embedding table are distinct' step fails even for concatenation. Please either provide a regularizer or projection that maintains the assumption, or report empirical row-collision counts after training for the configurations used in Figures 5-7.","section":"§4, Theorem 1"}],"minor_comments":[{"comment":"The sentence claiming 'an optimal memory complexity of O(k|S|^{1/k}D)' should clarify that the optimum is over balanced choices of the partition sizes |P_j| and that, for concatenation with D_j=D, the final embedding dimension is kD rather than D; if the final dimension must remain D, the per-table dimensions need to be adjusted.","section":"§4, memory complexity discussion"},{"comment":"The phrase 'yielding a unique path of transformations' is informal; without an injectivity statement for the composed maps, uniqueness for path-based embeddings is not established. Please either state the required assumptions on the transformations or soften the wording.","section":"§4.1, path-based compositional embeddings"},{"comment":"The phrase 'We enforce 4 hash collisions' is ambiguous, because the quotient-remainder construction with modulus m places |S|/m categories in each row, which is not the usual hashing-trick collision count. Please define the quantity precisely in the text or in the figure caption.","section":"§5.2, Figure 4"},{"comment":"The number of trials and the definition of the error bars are stated in the text as averages over 5 trials but are not repeated in the captions; adding them to the captions would improve readability.","section":"Figures 5-7 and Table 1"}],"recommendation":"major_revision","confidential_remarks":"The core problem is the distance between the advertised 'unique embedding for each category' and what is actually proved: uniqueness holds for concatenation under an unenforced row-distinctness assumption, while the recommended multiplication operation admits concrete collisions. I would not reject the paper on this basis, because the empirical comparison with the hashing trick is independent of the uniqueness claim. A revision that re-scopes the theoretical claim, adds collision analysis for multiplication, and addresses the row-distinctness issue would make the contribution acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things up front. First, this is a genuinely useful practical paper: the quotient-remainder trick (and its complementary-partitions generalization) is simple, easy to implement, and the Criteo experiments show it beats the hashing trick at similar compression. Second, the paper's headline claim—that compositional embeddings yield a unique vector per category—does not hold for the operation the authors end up recommending. Element-wise multiplication is not injective, and the proof only covers concatenation.\n\nWhat's new: the complementary-partitions formulation is a clean way to think about embedding compression by fixed codes, and the memory-complexity reduction to O(k|S|^(1/k)D) is correct. The experiments are reasonable: external benchmark, five trials, both DCN and DLRM, and the comparisons span parameter counts and thresholds. The paper also honestly shows thresholding and path-based variants. They are not overselling the empirical gains; the gains over hashing are real but modest.\n\nWhere it's soft. Theorem 1 is stated only for concatenation, and the proof assumes distinct rows per table. The experiments, though, settle on multiplication, and the abstract/conclusion claim uniqueness. The concrete counterexample in the stress-test note is valid: with quotient-remainder on {0,1,2,3}, m=2, D=2, two categories can collide under element-wise multiplication even when all rows are distinct. More generally, coordinatewise multiplication from R^{kD} to R^D is multilinear and cannot be injective for the dimensions used. So the theoretical differentiator is currently unproven for the deployed operation. That does not refute the empirical comparison—the method still works well—but it means the paper overstates what it guarantees. A second, milder issue: the best operation and thresholds are selected from test-set numbers, with no clean validation-based protocol. Given the effect sizes (0.3–0.7% from baseline), this is a minor concern.\n\nBottom line: the paper deserves a serious referee, because the method is useful and likely to be adopted. The referees should push the authors to either prove a collision bound for multiplication, switch the recommended operation to one with a guarantee, or rewrite the claims to say 'unique for concatenation; empirically strong for multiplication.' As is, I'd accept with major revisions.","headline":"Useful practical embedding compression, but the uniqueness guarantee is proven only for concatenation while the recommended multiplication operation has no such guarantee.","tokens_in":14855,"tokens_out":3403,"would_cite":true,"duration_ms":37672,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Complementary partitions produce a unique embedding per category with drastically less memory.","keywords":["recommendation systems","embeddings","model compression","complementary partitions","quotient-remainder trick","hashing trick","CTR prediction","embedding memory reduction"],"falsifier":"Train the quotient-remainder trick with element-wise multiplication on a feature with, say, one million categories and then compare the final embedding vectors of all distinct categories; if any two distinct categories produce the same vector, the recommended method has failed to preserve uniqueness despite the complementary partitions.","tokens_in":13852,"feed_emoji":"🧩","tokens_out":5865,"duration_ms":56636,"temperature":0.7,"pith_summary":"The paper claims that the embedding tables behind recommendation systems can be compressed far below their nominal size without losing the one-vector-per-category property. Its method stores several small embedding tables, each defined by a partition of the category set, and combines the rows selected by a category into a single vector. When the partitions are complementary, meaning any two categories differ in at least one partition, the combined vector is unique for every category, at least when rows within each table stay distinct and the combination is concatenation. On Criteo ad-click data, the quotient-remainder version of the method beats the hashing trick at equal parameter counts and, with element-wise multiplication, reaches close to full-table accuracy at roughly 4x compression. If this holds in production, it gives CTR models a drop-in compression scheme that preserves categorical diversity.","feed_headline":"One partition trick cuts embedding memory while keeping unique vectors","feed_subtitle":"Complementary partitions of the category set shrink embedding tables and beat the hashing trick on ad-click models.","key_machinery":"The central object is the complementary partition family: set partitions P1,...,Pk of the category set such that any two categories are placed in different equivalence classes by at least one partition. Each partition indexes a small embedding table, and the compositional embedding operation (concatenation, addition, or element-wise multiplication) fuses the selected rows. Theorem 1 proves uniqueness of the resulting vector under concatenation provided every row in every small table is distinct. The quotient-remainder trick is the paper's concrete construction: two partitions split the category index into remainder and quotient, yielding roughly O($\\sqrt$(|S|)D) memory; generalized quotient-remainder and Chinese-remainder partitions extend this to k tables with O(k|S|^{1/k}D) memory.","core_discovery":"The central claim is that a category's embedding can be defined implicitly by complementary partitions instead of stored explicitly. Given a category set S and a desired number k, the method picks k set partitions such that for every pair of distinct categories, at least one partition separates them into different equivalence classes. Each partition owns a small embedding table whose rows correspond to its equivalence classes; a category's compositional embedding is the combination (e.g., element-wise product or concatenation) of the rows its equivalence classes select. Because the partitions are complementary, no two categories share the same tuple of selected rows, so in the concatenation case the final vector is unique even though the stored tables are far smaller than |S|. The memory cost drops from O(|S|D) to roughly O(k|S|^{1/k}D), and the experiments show the scheme outperforms the hashing trick at similar parameter counts on DCN and DLRM models.","pith_inferences":["If collisions occur under multiplication, the method would still be useful as an improved hashing scheme, so its practical value does not strictly depend on the theorem's uniqueness guarantee.","For categorical features with natural multi-attribute structure (e.g., year, make, and model of a product), complementary partitions could be chosen from domain knowledge rather than artificially, which the paper leaves for future work.","Because each small table is independent, the compositional approach could be stacked with other compression techniques such as quantization or low-rank factorization, a combination not tested in the paper."],"forward_implications":["At equal parameter counts, the quotient-remainder trick achieves lower test loss than the hashing trick on the tested Criteo click-through models.","With thresholding, only the largest tables are compressed, so small tables keep full quality while total parameters fall by roughly a factor of four.","The scheme is end-to-end and requires no post-training processing or stored codebook, making it a practical drop-in for existing CTR pipelines.","Under concatenation the uniqueness guarantee is exact; even without that guarantee, the experiments suggest element-wise multiplication gives a stronger memory/accuracy trade-off than hashing."],"supporting_citations":[{"why":"Defines the hashing trick, the baseline compression method the paper's experiments improve upon.","marker":"[17]"},{"why":"Introduces the Deep & Cross Network (DCN), one of the two model architectures used to test the method.","marker":"[16]"},{"why":"Introduces the DLRM architecture, the second testbed for the compression experiments.","marker":"[11]"},{"why":"Uses tensorized embeddings to compress embedding layers, providing the related compositional interpretation the paper extends.","marker":"[7]"}],"fun_headline_variants":["Complementary partitions shrink embeddings, beat hashing","Cut embedding memory with complementary partitions","Partition-based embeddings slash memory, outperform hash","Unique vectors, small tables: partition trick wins","Complementary partitions define unique embeddings with less memory"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The uniqueness proof assumes each row within every small table is distinct and the combination is concatenation, but the recommended element-wise multiplication is not covered by the proof and can map different categories to the same vector even when the partitions are complementary.","fun_headline_variants_meta":{"raw":{"variants":["Complementary partitions shrink embeddings, beat hashing","Cut embedding memory with complementary partitions","Partition-based embeddings slash memory, outperform hash","Unique vectors, small tables: partition trick wins","Complementary partitions define unique embeddings with less memory"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000462,"raw_usage":{"total_tokens":2293,"prompt_tokens":912,"completion_tokens":1381,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":528,"completion_tokens_details":{"reasoning_tokens":1313}},"tokens_in":528,"tokens_out":1381,"duration_ms":9690,"temperature":1.0,"reasoning_tokens":1313,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:59:54.539948+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train the quotient-remainder trick with element-wise multiplication on a feature with, say, one million categories and then compare the final embedding vectors of all distinct categories; if any two distinct categories produce the same vector, the recommended method has failed to preserve uniqueness despite the complementary partitions.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the Deep & Cross Network (DCN), one of the two model architectures used to test the method."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Uses tensorized embeddings to compress embedding layers, providing the related compositional interpretation the paper extends."}],"review_version":1}