REVIEW 3 major objections 4 minor 30 references
Parallel and Mini-Batch Stable Matching for Large-Scale Reciprocal Recommender Systems
T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read By recomputing preference blocks on the fly from factor vectors, the paper reduces stable-matching memory from quadratic to linear and runs up to a million users on a single GPU with the same match count.
desk verdict The parallel/batched IPFP idea is sound and the 10^6-user demo is real, but Eq. (11) has a factor-of-2 error that breaks the compact output's claim to reproduce the equilibrium match probabilities. 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 load-bearing object is the iterative proportional fitting procedure (IPFP) recast as two matrix-vector products, $s = Av/2$ and $s = A^T u/2$, with $A = \exp((P+Q)/(2\beta))$, followed by the elementwise update $u = \sqrt{s^2 + m} - s$ (and symmetrically for $v$). Equation (8) -- the assumption that $p_{x,y} = \langle f_x,g_y\rangle$ and $q_{y,x} = \langle k_x,l_y\rangle$ -- lets Algorithm 2 recompute only the needed block $A_j$ from factor matrices, cutting space from $O(|\mathcal{X}||\mathcal{Y}|)$ to $O(|\mathcal{X}|D + |\mathcal{Y}|D)$. This is what makes online mini-batch updates of the scaling vectors possible while keeping the fixed-point equations algebraically identical to batch IPFP.
What would settle it
Take a synthetic market whose true joint utility matrix has high numerical rank, run batch IPFP and mini-batch IPFP at the same $D$, and measure the gap in the final expected number of matches; a nonzero gap that shrinks only as $D$ grows shows that the 'without losing the match count' claim depends on exact low-rank structure.
Extended reading notes
Core claim
The paper's central claim is that the entropy-regularized transferable-utility matching equilibrium of Eq. (2) can be computed by a parallel matrix-vector IPFP, and that a mini-batch version, Algorithm 2, computes the same equilibrium without ever materializing the $|\mathcal{X}||\mathcal{Y}|$ preference matrix. The identity that carries this is that each block $A_j = \exp((F_jG^T + K_jL^T)/(2\beta))$ equals the corresponding block of the full matrix $A = \exp((P+Q)/(2\beta))$ whenever the unilateral preferences are exactly $\langle f_x,g_y\rangle$ and $\langle k_x,l_y\rangle$ as in Eq. (8). Because the IPFP updates in Eq. (7) only access $A$ through matrix-vector products, recomputing blocks on the fly in Eqs. (9)--(10) yields the same $u,v$ scaling vectors and therefore the same match probabilities $\mu$. The paper reports that batch IPFP runs out of memory beyond $10^5$ users, while mini-batch IPFP with batch size 100 processes $10^6$ users, and that in the exactly factored case the match count is preserved.
Load-bearing premise
The reduction in memory relies on real preferences being exactly representable as inner products of short factor vectors, so that each mini-batch recomputes the very same preference matrix the batch algorithm would have used.
Editorial extensions
If this is right
- Stable-matching recommendations can be served at real platform scale of millions of users on a single GPU, replacing heuristic score aggregators that lack stability guarantees.
- The theoretical guarantees of TU stable matching -- stability and welfare maximization -- become available at scales where they were previously confined to datasets of a few thousand users.
- Memory now scales with the rank of the preference representation, so larger markets cost roughly linearly in the number of users plus the factor dimension, not in the number of user pairs.
- In crowded markets, where naive and reciprocal ranking degrade, the IPFP policy keeps expected total matches high while still being computationally feasible.
- An early-stopping rule based on ranking stability could shorten runtime further, since the goal is the converged match pattern, not the raw iteration count.
Reading between the lines
- A natural stress test the paper does not run is to sweep the factor dimension $D$ on data with full-rank preference structure; the match-count gap between batch and mini-batch IPFP should track the factorization error, giving practitioners a principled way to choose $D$.
- The block-recomputation trick should transfer to plain Sinkhorn scaling for entropy-regularized optimal transport whenever the cost matrix is a factored product, yielding linear-memory Sinkhorn; the paper only applies the idea to the stable-matching IPFP.
- Equation (11) writes match probabilities as inner products of $(2D+2)$-dimensional vectors, which suggests approximate nearest-neighbor search could generate candidate matches without ever building the full matrix; the paper does not explore this.
- The exact-factorization assumption also implies the method could be coupled with the training of the factor model itself, so the matching step and the learned preferences are jointly consistent; the paper leaves this coupling for future work.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes two computational improvements to the iterative proportional fitting procedure (IPFP) for transferable-utility (TU) stable matching in reciprocal recommender systems: a parallel matrix-vector formulation (batch IPFP) and a mini-batch version that assumes unilateral preferences are inner products of low-dimensional factor vectors (Eq. 8). The mini-batch version recomputes the exponential preference blocks on the fly, reducing memory from O(|X||Y|) to O((|X|+|Y|)D), and is claimed to achieve the same match count as the original IPFP. Experiments on Libimseti and synthetic data report speedups on GPU and scalability to 10^6 users, with a slight decrease in match count attributed to factorization approximation.
Significance. If the technical details are correct, this is a practically valuable contribution: it makes entropy-regularized stable matching applicable to large two-sided platforms, where previous methods were limited to roughly 10^4 users. The parallel matrix-vector update is a natural and sound reformulation, and the mini-batch idea is compelling because it leverages the factorized structure already used in recommender systems. The paper provides a public code link and experiments that demonstrate real scalability. However, the central output formula for the mini-batch representation contains an algebraic error that undermines the claim that the compact output represents the equilibrium, so the significance is contingent on that fix.
major comments (3)
- [Section 3.3, Eq. (11) and Algorithm 2 (lines 18–19)] Equation (11) is internally inconsistent with Eq. (4) and with the definition of u and v in Eq. (5). In Eq. (4), μ_xy = exp(φ_xy/(2β)) sqrt(μ_x0 μ_0y), and Eq. (5) sets u_x = sqrt(μ_x0), v_y = sqrt(μ_0y), so log μ_xy = φ_xy/(2β) + log u_x + log v_y. Substituting the concatenations ψ_x = Concat(f_x, k_x, β log(u_x), 1) and ξ_y = Concat(g_y, l_y, 1, β log(v_y)) into log μ = (1/(2β))<ψ_x, ξ_y> gives log μ = φ_xy/(2β) + (log u_x + log v_y)/2, which is off by a factor of 2 in the u/v terms. Consequently, the Ψ and Ξ returned by Algorithm 2 encode μ'_xy = sqrt(u_x v_y) exp(φ_xy/(2β)), not the equilibrium matching probabilities. This is a load-bearing error because the compact representation is the basis for the claimed memory efficiency and for the statement that the algorithm 'achieves the same matching probabilities as the conventional IPFP'. The fix is to use 2β log u and 2β log v in the concatenations (or to define u and v as the full row/column masses rather than their square roots).
- [Section 4.1.3 and Figure 4 caption] The Figure 4 caption states that mini-batch IPFP's number of matches 'slightly decreases because the preference matrix is approximated using the product of factor vectors', but the experimental setup in Section 4.1.1 says that for both batch and mini-batch the preference information comes from the same factor vectors: batch IPFP uses the imputed preference matrix which is the product of the factor vectors, and mini-batch directly uses those factor vectors. If the factorization is identical, the two methods should compute the same equilibrium (up to numeric tolerance). The observed decrease is therefore unexplained, and it may in fact be a consequence of the Eq. (11) encoding error. The manuscript should either reconcile this discrepancy or present the corrected formula and remeasure the match counts.
- [Abstract and Section 5] The abstract and conclusion claim that the method works 'without losing the match count' without qualification, but the experiments in Section 4.1 show a slight decrease for mini-batch IPFP, and the mathematical equivalence holds only when the preference matrix is exactly the product of the given factor vectors (Eq. 8). When factor vectors are estimated from data, they are an approximation of true preferences, so the 'without losing the match count' claim should be explicitly conditioned on exact factorization. As written, the claim overstates the empirical finding.
minor comments (4)
- [Section 3.1 vs. Algorithm 1] The notation for the capacity vectors is inconsistent: in Section 3.1 and Eq. (6), n_x denotes the candidate capacity and m_y the employer capacity, while Algorithm 1 uses m for |X|-sized vector and n for |Y|-sized vector. This swapping is likely to confuse readers; please align the notation.
- [Abstract, line 2 of the paper] The phrase 'graphics processing unit graphics board' is redundant and seems to contain a typo; it should be 'graphics processing unit' or 'graphics card'.
- [Figure 4] The legend entry 'Mini-batch' should read 'Mini-batch IPFP' to match the other labels such as 'Batch IPFP'.
- [Section 4.2.2] The statement that the mini-batch IPFP 'does not require approximation' (also in Contributions) should be more precise: the optimization itself does not approximate the IPFP iterations, but the input preference matrix is assumed to be exactly the factorized product (Eq. 8). Abundant real-data preferences will not satisfy this exactly, so calling the method 'approximation-free' without this caveat is misleading.
Circularity Check
No circularity: mini-batch IPFP is an exact block recomputation of the same matrix A under the stated low-rank assumption; the Eq. (11) issue is an algebraic inconsistency, not circularity.
full rationale
The claimed reduction is an algorithmic identity, not a hidden tautology. Section 3.2 defines batch IPFP with A = exp(Phi/(2 beta)) (Eq. 7). Section 3.3 assumes p_xy = <f_x,g_y> and q_yx = <k_x,l_y> (Eq. 8), so Phi_xy = <f_x,g_y> + <k_x,l_y>. The mini-batch update (Eqs. 9-10) computes A_j = exp((F_j G^T + K_j L^T)/(2 beta)), which is exactly the submatrix of A restricted to batch j; when Eq. (8) holds, no approximation is introduced, and mini-batch and batch solve the same fixed-point equations. This equivalence is by construction, and that is the content of the claim, not circularity. Beta and D are hand-set rather than fitted to match-count targets, so there is no fitted-input-called-prediction step. The citations to Galichon and Salanié [9] and Tomita et al. [6] are external works with no author overlap, so no self-citation is load-bearing. Two caveats belong to correctness and validation, not circularity: Eq. (11) as printed appears algebraically inconsistent with Eq. (4) (it gives log mu = phi/(2 beta) + (log u + log v)/2 rather than phi/(2 beta) + log u + log v), and the evaluation is in-sample on the imputed preference matrix, with Figure 4's caption conceding that match count slightly decreases when the factor-product approximation is used. Neither caveat makes the derivation equivalent to its own inputs.
Assumptions & free parameters
free parameters (2)
- beta (entropy scale parameter) =
1.0 in all experiments
- factor vector dimension D =
50 in efficiency experiments
assumptions (4)
- domain assumption Unobserved random utilities are i.i.d. type-I extreme value with scale beta (logit model), Eq. (1).
- standard math Galichon-Salanie duality: the TU matching equilibrium is characterized by the convex program (2) and the IPFP updates (6).
- domain assumption Preferences are exactly low-rank: p_xy = <f_x, g_y> and q_yx = <k_x, l_y>, Eq. (8).
- standard math An equilibrium-matching solution to (2) exists and is unique under the normalized capacity constraints (footnote 1, Decker et al. [22]).
Cite this review
Pith. "Pith review of Parallel and Mini-Batch Stable Matching for Large-Scale Reciprocal Recommender Systems." pith.science (2026). https://pith.science/paper/L7RKJKJP
@misc{pith2026241119214,
author = {Pith},
title = {Pith review of: Parallel and Mini-Batch Stable Matching for Large-Scale Reciprocal Recommender Systems},
year = {2026},
howpublished = {\url{https://pith.science/paper/L7RKJKJP}},
note = {Machine review of arXiv:2411.19214}
}
read the original abstract
Reciprocal recommender systems (RRSs) are crucial in online two-sided matching platforms, such as online job or dating markets, as they need to consider the preferences of both sides of the match. The concentration of recommendations to a subset of users on these platforms undermines their match opportunities and reduces the total number of matches. To maximize the total number of expected matches among market participants, stable matching theory with transferable utility has been applied to RRSs. However, computational complexity and memory efficiency quadratically increase with the number of users, making it difficult to implement stable matching algorithms for several users. In this study, we propose novel methods using parallel and mini-batch computations for reciprocal recommendation models to improve the computational time and space efficiency of the optimization process for stable matching. Experiments on both real and synthetic data confirmed that our stable matching theory-based RRS increased the computation speed and enabled tractable large-scale data processing of up to one million samples with a single graphics processing unit graphics board, without losing the match count.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
I. Palomares, C. Porcel, L. Pizzato, I. Guy, E. Herrera- Viedma, Reciprocal recommender systems: Analysis of state-of-art literature, challenges and opportunities towards social recommendation, 2021. doi:10.1016/ j.inffus.2020.12.001
work page 2021
-
[2]
L. Pizzato, T. Rej, T. Chung, I. Koprinska, J. Kay, Re- con: A reciprocal recommender for online dating, in: RecSys, New York, NY, USA, 2010, p. 207–214. doi:10.1145/1864708.1864747
arXiv 2010
-
[3]
L. S. Shapley, M. Shubik, The Assignment Game I: The Core, volume 1, Physica-Verlag GmbH, DEU, 1971. doi:10.1007/BF01753437
- [4]
-
[5]
E. Choo, A. Siow, Who marries whom and why, Jour- nal of Political Economy 114 (2006) 175–201. URL: http://www.jstor.org/stable/10.1086/498585
- [6]
-
[7]
K.-M. Chen, Y.-W. Hsieh, M.-J. Lin, Reducing rec- ommendation inequality via two-sided matching: a field experiment of online dating, International Eco- nomic Review 64 (2023) 1201–1221. doi: 10.1111/ iere.12631
work page 2023
-
[8]
A. Saini, F. Rusu, A. Johnston, Privatejobmatch: A privacy-oriented deferred multi-match recommender system for stable employment, In: RecSys, New York, NY, USA, 2019, p. 87–95. doi: 10.1145/3298689. 3346983
doi:10.1145/3298689 2019
Show all 30 references
-
[9]
Galichon, B
A. Galichon, B. Salanié, Cupid’s invisible hand: So- cial surplus and identification in matching models, The Review of Economic Studies 89 (2021) 2600–2629. doi:10.1093/restud/rdab090
2021 doi
-
[10]
Knopp, R
P. Knopp, R. Sinkhorn, Concerning nonnegative ma- trices and doubly stochastic matrices., Pacific Journal of Mathematics 21 (1967) 343–348
1967
-
[11]
Koren, R
Y. Koren, R. Bell, C. Volinsky, Matrix factorization techniques for recommender systems, Computer 42 (2009) 30–37. doi:10.1109/MC.2009.263
2009 doi
-
[12]
Özcan, S
G. Özcan, S. G. Ögüdücü, Applying different classifica- tion techniques in reciprocal job recommender system for considering job candidate preferences, in: 2016 11th International Conference for Internet Technology and Secured Transactions (ICITST), 2016, pp. 235–240. doi:10.1...
2016
-
[13]
P. Xia, B. Liu, Y. Sun, C. Chen, Reciprocal recom- mendation system for online dating, in: ASONAM, New York, NY, USA, 2015, p. 234–241. doi:10.1145/ 2808797.2809282
2015
-
[14]
Kleinerman, A
A. Kleinerman, A. Rosenfeld, F. Ricci, S. Kraus, Op- timally balancing receiver and recommended users’ importance in reciprocal recommender systems, in: RecSys, ACM, New York, NY, USA, 2018, p. 131–139. doi:10.1145/3240323.3240349
2018
-
[15]
Ramanathan, N
R. Ramanathan, N. K. Shinada, M. Shimatani, Y. Yam- aguchi, J. Tanaka, Y. Iizuka, S. K. Palaniappan, A re- ciprocal embedding framework for modelling mutual preferences, in: AAAI, volume 35, 2021, pp. 15385– 15392. doi:10.1609/aaai.v35i17.17807
2021 doi
-
[16]
Borisyuk, L
F. Borisyuk, L. Zhang, K. Kenthapadi, Lijar: A system for job application redistribution towards efficient ca- reer marketplace, in: KDD, New York, NY, USA, 2017, p. 1397–1406. doi:10.1145/3097983.3098028
2017
- [17]
-
[18]
Y. Su, M. Bayoumi, T. Joachims, Optimizing rankings for recommendation in matching markets, in: WWW,
-
[19]
G. Bied, E. Perennes, V. A. Naya, P. Caillou, B. Crépon, C. Gaillac, M. Sebag, Congestion-avoiding job recom- mendation with optimal transport, in: FEAST work- shop ECML-PKDD 2021, Bilbao, Spain, 2021
2021
-
[20]
Mashayekhi, B
Y. Mashayekhi, B. Kang, J. Lijffijt, T. De Bie, Recon: Reducing congestion in job recommendation using op- timal transport, in: RecSys, ACM, New York, NY, USA, 2023, p. 696–701. doi:10.1145/3604915.3608817
2023
-
[21]
Cuturi, Sinkhorn distances: Lightspeed computa- tion of optimal transport, in: NIPS, Curran Associates Inc., Red Hook, NY, USA, 2013, p
M. Cuturi, Sinkhorn distances: Lightspeed computa- tion of optimal transport, in: NIPS, Curran Associates Inc., Red Hook, NY, USA, 2013, p. 2292–2300
2013
-
[22]
Decker, E
C. Decker, E. H. Lieb, R. J. McCann, B. K. Stephens, Unique equilibria and substitution effects in a stochas- tic model of the marriage market, Journal of Eco- nomic Theory 148 (2013) 778–792. doi: 10.1016/j. jet.2012.12.005
2013 doi
-
[23]
A. Mnih, R. R. Salakhutdinov, Probabilistic matrix factorization, in: J. Platt, D. Koller, Y. Singer, S. Roweis (Eds.), Advances in Neu- ral Information Processing Systems, volume 20, Curran Associates, Inc., 2007. URL: https: //proceedings.neurips.cc/paper_files/paper/2007/fi...
2007
-
[24]
Paterek, Improving regularized singular value de- composition for collaborative filtering, Proceedings of KDD Cup and Workshop (2007)
A. Paterek, Improving regularized singular value de- composition for collaborative filtering, Proceedings of KDD Cup and Workshop (2007)
2007
-
[25]
J. Neve, I. Palomares, Latent factor models and aggregation operators for collaborative filtering in reciprocal recommender systems, in: Proceedings of the 13th ACM Conference on Recommender Sys- tems, RecSys ’19, Association for Computing Ma- chinery, New York, NY, USA, 2019,...
2019
- [26]
-
[27]
Bradbury, R
J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. Van- derPlas, S. Wanderman-Milne, Q. Zhang, JAX: com- posable transformations of Python+NumPy programs,
-
[28]
Scetbon, M
M. Scetbon, M. Cuturi, G. Peyré, Low-rank sinkhorn factorization, in: M. Meila, T. Zhang (Eds.), Proceed- ings of the 38th International Conference on Machine Learning, volume 139 of PMLR, PMLR, 2021, pp. 9344– 9354. Algorithm 1 Solving Equilibrium Matching by Batch IPFP Requi...
2021
-
[2018]
URL: http://github.com/google/jax
-
[2022]
doi:10.1145/3485447.3511961
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.