REVIEW 2 major objections 4 minor 26 references
Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems
T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Complementary partitions produce a unique embedding per category with drastically less memory.
desk verdict Useful practical embedding compression, but the uniqueness guarantee is proven only for concatenation while the recommended multiplication operation has no such guarantee. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (2)
- [§4, Theorem 1; §5.3, Algorithm 2] 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.
- [§4, Theorem 1] 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.
minor comments (4)
- [§4, memory complexity discussion] 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.
- [§4.1, path-based compositional embeddings] 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.
- [§5.2, Figure 4] 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.
- [Figures 5-7 and Table 1] 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.
Circularity Check
No significant circularity: the uniqueness result is derived from the explicit complementary-partition definitions and distinct-row assumption, and the empirical claims rest on an external Criteo benchmark.
full rationale
The paper's derivation chain is self-contained. Complementary partitions are defined directly in set-theoretic terms (Definition 1), and the quotient-remainder, generalized quotient-remainder, and Chinese-remainder partitions are explicitly constructed and proved complementary in Appendix B without invoking the target result. Theorem 1 is then proved from two stated assumptions: the partitions are complementary and the rows within each embedding table are distinct; under concatenation, two different categories must differ in at least one partition, and the corresponding block of the concatenated embedding must therefore differ. The memory bound O(k|S|^{1/k}D) follows by arithmetic from the sizes of the constructed partitions, not from fitting or from any prediction target. The experimental claims are comparisons against the hashing trick on the external Criteo Ad Display dataset, and the paper does not fit parameters to a subset and then relabel that fit as a prediction. The main identified gap, that Theorem 1 is stated only for concatenation while the experiments recommend element-wise multiplication, is a correctness or scope issue rather than a circularity issue: the paper neither defines the theorem in terms of the multiplication operation nor uses multiplication to force the claimed uniqueness. Self-citations, including to the DLRM architecture paper, provide experimental context and are not load-bearing for the mathematical derivation. No circular step can be exhibited from the paper's own equations, so the appropriate score is 0.
Assumptions & free parameters
free parameters (5)
- hash collision count c =
2 to 7 and 60
- number of partitions k and per-partition sizes m_i =
k=2 for the main quotient-remainder experiments; general k in the theory
- feature size threshold =
{1, 20, 200, 2000, 20000}
- composition operation =
element-wise multiplication for DCN; concatenation for DLRM under thresholding
- optimizer =
Adagrad or AMSGrad
assumptions (3)
- domain assumption Rows of each small embedding table are distinct so that concatenation preserves category uniqueness
- standard math The complementary partition constructions (quotient-remainder, generalized QR, Chinese remainder) cover any category set
- domain assumption Jointly trained embeddings are the appropriate representation space for categorical features
Cite this review
Pith. "Pith review of Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems." pith.science (2026). https://pith.science/paper/KPY4OR3Q
@misc{pith2026190902107,
author = {Pith},
title = {Pith review of: Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems},
year = {2026},
howpublished = {\url{https://pith.science/paper/KPY4OR3Q}},
note = {Machine review of arXiv:1909.02107}
}
read the original abstract
Modern deep learning-based recommendation systems exploit hundreds to thousands of different categorical features, each with millions of different categories ranging from clicks to posts. To respect the natural diversity within the categorical data, embeddings map each category to a unique dense representation within an embedded space. Since each categorical feature could take on as many as tens of millions of different possible categories, the embedding tables form the primary memory bottleneck during both training and inference. We propose a novel approach for reducing the embedding size in an end-to-end fashion by exploiting complementary partitions of the category set to produce a unique embedding vector for each category without explicit definition. By storing multiple smaller embedding tables based on each complementary partition and combining embeddings from each table, we define a unique embedding for each category at smaller memory cost. This approach may be interpreted as using a specific fixed codebook to ensure uniqueness of each category's representation. Our experimental results demonstrate the effectiveness of our approach over the hashing trick for reducing the size of the embedding tables in terms of model loss and accuracy, while retaining a similar reduction in the number of parameters.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
Ting Chen, Martin Renqiang Min, and Yizhou Sun. 2018. Learning k-way d-dimensional discrete codes for compact embedding representations. arXiv preprint arXiv:1806.09464 (2018)
arXiv 2018
-
[2]
Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, et al
-
[3]
John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research 12, Jul (2011), 2121–2159
2011
-
[4]
Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. 2017. DeepFM: a factorization-machine based neural network for CTR prediction.arXiv preprint arXiv:1703.04247 (2017)
arXiv 2017
-
[5]
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. 2017. Neural collaborative filtering. In Proceedings of the 26th interna- tional conference on world wide web . International World Wide Web Conferences Steering Committee, 173–182
work page 2017
-
[6]
Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, 1 (2010), 117–128
2010
-
[7]
Valentin Khrulkov, Oleksii Hrinchuk, Leyla Mirvakhabova, and Ivan Oseledets
-
[8]
Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic opti- mization. arXiv preprint arXiv:1412.6980 (2014)
arXiv 2014
Show all 26 references
-
[9]
Jianxun Lian, Xiaohuan Zhou, Fuzheng Zhang, Zhongxia Chen, Xing Xie, and Guangzhong Sun. 2018. xDeepFM: Combining explicit and implicit feature interactions for recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mi...
2018
-
[10]
Maxim Naumov. 2019. On the Dimensionality of Embeddings for Sparse Features and Data. arXiv preprint arXiv:1901.02103 (2019)
2019 arXiv
-
[11]
Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi, Jianyu Huang, Narayanan Sundaraman, Jongsoo Park, Xiaodong Wang, Udit Gupta, Carole-Jean Wu, Alisson G Azzolini, et al. 2019. Deep Learning Recommendation Model for Personalization and Recommendation Systems. arXiv preprin...
2019 arXiv
-
[12]
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. 2019. On the convergence of adam and beyond. arXiv preprint arXiv:1904.09237 (2019)
2019 arXiv
-
[13]
Steffen Rendle. 2010. Factorization machines. In 2010 IEEE International Confer- ence on Data Mining . IEEE, 995–1000
2010
-
[14]
Steffen Rendle. 2012. Factorization machines with LibFM. ACM Transactions on Intelligent Systems and Technology (TIST) 3, 3 (2012), 57
2012
-
[15]
Raphael Shu and Hideki Nakayama. 2017. Compressing word embeddings via deep compositional code learning. arXiv preprint arXiv:1711.01068 (2017)
2017 arXiv
-
[16]
Ruoxi Wang, Bin Fu, Gang Fu, and Mingliang Wang. 2017. Deep & cross network for ad click predictions. In Proceedings of the ADKDD’17 . ACM, 12
2017
-
[17]
Kilian Weinberger, Anirban Dasgupta, Josh Attenberg, John Langford, and Alex Smola. 2009. Feature hashing for large scale multitask learning. arXiv preprint arXiv:0902.2206 (2009)
2009 arXiv
-
[18]
Zi Yin and Yuanyuan Shen. 2018. On the dimensionality of word embedding. In Advances in Neural Information Processing Systems . 887–898
2018
-
[19]
Lei Zheng, Chun-Ta Lu, Lifang He, Sihong Xie, Vahid Noroozi, He Huang, and Philip S Yu. 2018. Mars: Memory attention-aware recommender system. arXiv preprint arXiv:1805.07037 (2018)
2018 arXiv
-
[20]
Chang Zhou, Jinze Bai, Junshuai Song, Xiaofei Liu, Zhengchao Zhao, Xiusi Chen, and Jun Gao. 2018. ATRank: An attention-based user behavior modeling frame- work for recommendation. In Thirty-Second AAAI Conference on Artificial Intelli- gence
2018
-
[21]
Guorui Zhou, Na Mou, Ying Fan, Qi Pi, Weijie Bian, Chang Zhou, Xiaoqiang Zhu, and Kun Gai. 2018. Deep Interest Evolution Network for Click-Through Rate Prediction. arXiv preprint arXiv:1809.03672 (2018)
2018 arXiv
-
[22]
Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. 2018. Deep interest network for click-through rate prediction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining ...
2018
-
[23]
Han Zhu, Xiang Li, Pengye Zhang, Guozheng Li, Jie He, Han Li, and Kun Gai
-
[2016]
In Proceedings of the 1st workshop on deep learning for recommender systems
Wide & deep learning for recommender systems. In Proceedings of the 1st workshop on deep learning for recommender systems . ACM, 7–10
-
[2018]
equivalent
Learning Tree-based Deep Model for Recommender Systems. InProceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 1079–1088. A BACKGROUND ON SET PARTITIONS, EQUIV ALENCE RELATIONS, AND EQUIV ALENCE CLASSES For completeness, we inc...
-
[2019]
arXiv preprint arXiv:1901.10787 (2019)
Tensorized Embedding Layers for Efficient Model Compression. arXiv preprint arXiv:1901.10787 (2019)
2019 arXiv
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.