{"id":"1abbaef2-12e7-498a-9ecd-33043c7fe2ee","arxiv_id":"2411.19214","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A mini-batch, parallelized form of the IPFP stable matching algorithm lets reciprocal recommender systems process up to 10^6 users on one GPU while keeping the match count close to the exact algorithm.","lead":"This paper scales a stable matching method for two-sided markets, such as dating and job platforms, to datasets of up to one million users. It does so by rewriting the iterative matching algorithm as matrix-vector operations and splitting the computation into mini-batches that fit in memory.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (11) is internally inconsistent with Eq. (4): the dot-product encoding of log mu is off by a factor of 2 in the u/v terms, so the output of Algorithm 2 does not reproduce the equilibrium matching probabilities.","rationale":"The reader's weakest assumption focuses on the low-rank factorization limit, which is a valid concern and is even acknowledged in the Figure 4 caption. However, the more load-bearing problem is an internal algebraic error in Eq. (11), the formula that defines how the memory-efficient output represents the equilibrium. Even if the preference matrix is exactly factorized as in Eq. (8), the proposed compact representation does not reproduce the match probabilities from Eq. (4). This is a concrete, checkable mistake, not a consequence of approximation or external assumptions. It directly undermines the central claim that mini-batch IPFP computes the same TU stable matching without losing the match count, because the output format returned by Algorithm 2 is wrong. The paper would need a corrected formula, a re-run of the experiments to confirm the reported match counts are not affected, and a reassessment of the abstract's overclaim before it could be accepted. Given that the core contribution's key output equation is incorrect, REJECT is appropriate, though a revision addressing the formula and experimental verification could change that assessment.","tokens_in":11695,"tokens_out":16106,"duration_ms":134145,"concrete_test":"Analytically expand Eq. (11) and compare with Eq. (4) for a 1x1 market with phi=0, beta=1, n=m=1: Eq. (4) gives mu=0.5, while Eq. (11) gives mu approx 0.707, demonstrating the factor-of-2 mismatch. More generally, verify whether <psi_x, xi_y>/(2 beta) equals phi/(2 beta) + log u_x + log v_y for arbitrary u and v; if not, Eq. (11) is wrong. Optionally, run the released code to compute match probabilities from Algorithm 2's Psi and Xi and compare with batch IPFP's mu; any discrepancy confirms the error.","verdict_should_be":"REJECT","load_bearing_attack":"Section 3.3, Eq. (11) defines log mu_xy = 1/(2 beta) <psi_x, xi_y> with psi_x = Concat(f_x, k_x, beta log u, 1) and xi_y = Concat(g_y, l_y, 1, beta log v). Substituting gives log mu = phi/(2 beta) + (log u + log v)/2, where phi = <f,g> + <k,l>. But Eq. (4) states mu_xy = exp(phi/(2 beta)) sqrt(mu_x0 mu_0y) = exp(phi/(2 beta)) u_x v_y, so log mu = phi/(2 beta) + log u + log v. The appended coordinates must be 2 beta log u and 2 beta log v (or the constants must be 2) for the two expressions to agree. As written, the compact output Psi, Xi returned by Algorithm 2 (lines 18-19) encodes match probabilities that are systematically wrong (e.g., mu = sqrt(u v) exp(phi/(2 beta)) instead of u v exp(phi/(2 beta))). This is an internal algebraic inconsistency, not an approximation effect: even under exact factorization, the memory-efficient output does not represent the equilibrium matching pattern. Consequently the central claim that mini-batch IPFP solves the same TU stable matching problem without losing the match count is not supported by the paper's formulas, and the reported match-count results cannot be reproduced from the description.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11822,"tokens_out":8373,"duration_ms":68295,"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":[{"comment":"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":"Section 3.3, Eq. (11) and Algorithm 2 (lines 18–19)"},{"comment":"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.","section":"Section 4.1.3 and Figure 4 caption"},{"comment":"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.","section":"Abstract and Section 5"}],"minor_comments":[{"comment":"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.","section":"Section 3.1 vs. Algorithm 1"},{"comment":"The phrase 'graphics processing unit graphics board' is redundant and seems to contain a typo; it should be 'graphics processing unit' or 'graphics card'.","section":"Abstract, line 2 of the paper"},{"comment":"The legend entry 'Mini-batch' should read 'Mini-batch IPFP' to match the other labels such as 'Batch IPFP'.","section":"Figure 4"},{"comment":"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.","section":"Section 4.2.2"}],"recommendation":"major_revision","confidential_remarks":"The paper appears to be written for the RecSys in HR'24 workshop; the scope is appropriate for that venue. The Eq. (11) error is serious and should be corrected before publication; it is, however, a localized algebraic fix rather than a flaw in the algorithmic idea. I would also encourage the authors to verify the match-count results after the fix, since the unexplained decrease in Figure 4 may be an artifact of the error."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the useful part. The paper gives a clean matrix-vector form of Galichon–Salanié's IPFP (Eq. 7) and a block-coordinate mini-batch version (Eqs. 9–10) that recomputes the preference block on the fly, cutting memory from O(n^2) to O(nD). The GPU experiments up to n=10^6 are a legitimate engineering data point, and the paper is honest about the mini-batch match counts being slightly lower in Figure 4.\n\nThe load-bearing problem is Eq. (11). From Eq. (4), mu_xy = exp(phi/(2 beta)) u_x v_y, so log mu = phi/(2 beta) + log u + log v. But Eq. (11) defines log mu = 1/(2 beta) <psi, xi> with psi = concat(f, k, beta log u, 1) and xi = concat(g, l, 1, beta log v). The inner product is phi + beta(log u + log v), so the result is phi/(2 beta) + (log u + log v)/2 — exactly half the u and v contribution. The appended coordinates need to be 2 beta log u and 2 beta log v. As written, Algorithm 2's returned Psi and Xi do not encode the equilibrium match probabilities even under exact factorization. That contradicts the abstract's \"without losing the match count\" and the conclusion's claim of the same matching probabilities.\n\nThe rest of the paper is weaker in less fatal ways: the standard errors promised in Section 4.1 never appear; beta is fixed at 1.0 with no sensitivity; the examination function's ranking-list construction is unspecified; and the welfare numbers are in-sample, computed from the same factor vectors the algorithm optimizes. None of these would sink the paper on their own. The Eq. (11) error will.\n\nThis isn't a condemnation of the whole approach. With the factor corrected, the mini-batch algorithm would plausibly reproduce batch IPFP, and the 10^6-user result would stand. It's the kind of bug a competent referee should catch and a competent author could fix in a day. I'd send it to review if I were a desk editor, but as submitted it should not be published: the central formal claim about the compact output is false as stated.","headline":"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.","tokens_in":12573,"tokens_out":3748,"would_cite":false,"duration_ms":31027,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["transferable utility matching","stable matching","reciprocal recommender systems","iterative proportional fitting","entropy-regularized optimal transport","mini-batch computation","GPU parallelization","matrix factorization"],"falsifier":"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.","tokens_in":11306,"feed_emoji":"⚖️","tokens_out":7062,"duration_ms":46616,"temperature":0.7,"pith_summary":"The paper tries to show that the iterative proportional fitting procedure (IPFP) that solves transferable-utility stable matching is not stuck at thousands of users: rewritten as matrix-vector products, it runs on a GPU, and rewritten again as mini-batch updates, it recomputes preference blocks from user factor vectors instead of storing the whole preference matrix. The claimed payoff is that memory use drops from quadratic in the number of users to linear, so entropy-regularized stable matching can be run on up to a million users on a single GPU. The paper argues this comes without losing the match count as long as the preference matrix is exactly the product of the given factor vectors, and its experiments on dating and synthetic data show higher expected matches than heuristic reciprocal-recommendation baselines in crowded markets. A sympathetic reader would care because this is the difference between stable matching being a theoretical benchmark and being deployable on real job and dating platforms.","feed_headline":"Stable matching now scales to 1M users","feed_subtitle":"Recomputing preference blocks slashes memory from quadratic to linear and keeps the match count.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Derives the equivalence between transferable-utility matching and entropy-regularized optimal transport, and supplies the IPFP coordinate-descent updates that the paper parallelizes.","marker":"[9]"},{"why":"Shows how the TU matching model is applied as a convex optimization problem in a real online-dating field experiment; the paper adopts this formulation.","marker":"[7]"},{"why":"Provides the memory-efficient inference scheme whose closed form for log match probabilities the mini-batch IPFP reuses via Eq. (11).","marker":"[6]"},{"why":"Sinkhorn's matrix-scaling algorithm is the conceptual basis for the matrix-vector parallel update structure.","marker":"[10]"},{"why":"The matrix factorization model gives the factor-vector representation of preferences used by the mini-batch algorithm.","marker":"[11]"},{"why":"Guarantees existence and uniqueness of the equilibrium-matching solution, so the fixed point IPFP aims at is well defined.","marker":"[22]"},{"why":"Establishes the fast Sinkhorn computation for entropy-regularized optimal transport, the computational background for the parallel matrix-vector form.","marker":"[21]"},{"why":"Provides the implicit alternating least squares method used to estimate factor vectors from observation data in the experiments.","marker":"[24]"}],"fun_headline_variants":["Mini-batch stable matching scales to 1M users","Stable matching goes megascale with mini-batches","1M-user stable matching on a single GPU","Parallel stable matching cuts memory to linear","Mini-batch IPFP keeps matches, scales to 1M"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Mini-batch stable matching scales to 1M users","Stable matching goes megascale with mini-batches","1M-user stable matching on a single GPU","Parallel stable matching cuts memory to linear","Mini-batch IPFP keeps matches, scales to 1M"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000191,"raw_usage":{"total_tokens":1358,"prompt_tokens":976,"completion_tokens":382,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":592,"completion_tokens_details":{"reasoning_tokens":305}},"tokens_in":592,"tokens_out":382,"duration_ms":5903,"temperature":1.0,"reasoning_tokens":305,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:25:27.415449+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Chen, Y.-W","cited_arxiv_id":null,"evidence_quote":"Shows how the TU matching model is applied as a convex optimization problem in a real online-dating field experiment; the paper adopts this formulation."},{"cited_title":"Knopp, R","cited_arxiv_id":null,"evidence_quote":"Sinkhorn's matrix-scaling algorithm is the conceptual basis for the matrix-vector parallel update structure."},{"cited_title":"Cuturi, Sinkhorn distances: Lightspeed computa- tion of optimal transport, in: NIPS, Curran Associates Inc., Red Hook, NY, USA, 2013, p","cited_arxiv_id":null,"evidence_quote":"Establishes the fast Sinkhorn computation for entropy-regularized optimal transport, the computational background for the parallel matrix-vector form."},{"cited_title":"Paterek, Improving regularized singular value de- composition for collaborative filtering, Proceedings of KDD Cup and Workshop (2007)","cited_arxiv_id":null,"evidence_quote":"Provides the implicit alternating least squares method used to estimate factor vectors from observation data in the experiments."}],"review_version":1}