{"id":"887b26c0-f063-4007-9f20-20f0caf6b8e7","arxiv_id":"2502.01416","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The paper proves that discrete-time iterative Markovian fitting converges to the Schrödinger Bridge on finite discrete spaces and introduces CSBM, a practical matching algorithm for categorical data.","lead":"CSBM extends the Schrödinger Bridge framework for generative modeling to discrete data such as text tokens and vector-quantized image codes, with a convergence proof for the discrete-time iterative Markovian fitting. It gives a grounded algorithm for unpaired domain translation on categorical spaces, a setting earlier SB methods did not cover.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 3.2's D-IMF convergence is asserted via (Shi et al., 2023, Thm 8) without a proof specific to finite spaces and general Markov qref; the characterization theorem alone does not establish that the alternating KL projections in Eq. (6) converge to q*.","rationale":"The reader identifies the same load-bearing weak point: Corollary 3.2 is invoked via an external theorem rather than proved, and the convergence of exact D-IMF in the discrete setting with a general Markov reference is precisely what must hold for the paper's central algorithmic claim. My read agrees with this assessment. The characterization theorem itself appears sound: the proof of Theorem 3.1 correctly derives a static Schrödinger bridge plan of the form ψ(x0) qref(x1|x0) φ(x1) and then uses reciprocity to lift it to the dynamic solution. The gap is in the corollary, not the theorem. I do not think the concern is necessarily fatal: in finite state spaces, the alternating projections in Eq. (6) are block coordinate descent on the jointly convex KL objective, and a proof may be available, but the paper does not provide it. Therefore the appropriate verdict remains CONDITIONAL rather than ACCEPT; no change from the reader's verdict is needed. The proposed concrete test is to write out this missing proof, with a numerical cross-check on a non-symmetric reference to ensure the claim is not merely an artifact of the symmetric references tested in Figure 1.","tokens_in":23966,"tokens_out":13987,"duration_ms":139125,"concrete_test":"Attempt a self-contained proof of Corollary 3.2 for finite X: verify that proj_R and proj_M in Eq. (6) are exact minimizers of KL(r||m_l) over R and KL(r_{l+1}||m) over M, respectively; show that F(r,m)=KL(r||m) is jointly convex and differentiable on the positive simplex; and show that every limit point of the alternating scheme is a coordinate-wise minimum, hence a global minimum, forcing convergence to the unique Markov-reciprocal q*. If this proof requires an assumption not stated in the paper, state it explicitly. As a numerical cross-check, run exact matrix-based D-IMF with a randomly generated, full-support, non-reversible Markov qref (e.g., S=3, N=2) and compare KL(q_l||q*) against a Sinkhorn ground truth over at least 10^4 iterations.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central convergence claim splits into Theorem 3.1, which characterizes the unique Markov-reciprocal process q*, and Corollary 3.2, which asserts that the D-IMF iteration in Eq. (6) converges to q* in KL. Theorem 3.1 is argued directly, but Corollary 3.2 is not proved in the paper. The text says convergence 'easily follows from the generic proof argument in (Shi et al., 2023, Theorem 8)' and gives no verification that this transfer is valid for a finite state space and an arbitrary full-support Markov reference qref. Shi et al.'s Theorem 8 is a continuous-time result and its proof may rely on Brownian or continuous-time machinery; even if the characterization theorem holds, the alternating KL projections in Eq. (6) could in principle fail to converge, or converge to a point that is not the unique Markov-reciprocal process. A direct proof would view Eq. (6) as block coordinate descent on the jointly convex function F(r,m)=KL(r||m) over the convex sets R (reciprocal processes) and M (Markov processes); no such proof is supplied. Figure 1 tests only the symmetric qunif and qgauss references, so it does not support the claim for general Markov qref. Thus, as written, the algorithmic convergence guarantee is an unverified transfer from a different setting.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Schrödinger Bridge (SB) problem on finite discrete spaces X = S^D with a general full-support Markov reference process. Its main theoretical contribution is Theorem 3.1, which states that in this setting the dynamic SB solution q* is the unique process that is both Markov and reciprocal with respect to the reference. Based on this characterization, Corollary 3.2 claims that the discrete-time Iterative Markovian Fitting (D-IMF) procedure converges to q* in KL divergence. The paper then proposes a practical algorithm, Categorical Schrödinger Bridge Matching (CSBM), which implements the reciprocal and Markov projections using neural networks with a factorized parameterization, and reports experiments on synthetic data, colored MNIST, CelebA (via VQ-GAN latent codebooks), and Amazon Reviews sentiment transfer. The paper includes code and extensive appendices.","tokens_in":24278,"tokens_out":4201,"duration_ms":39265,"significance":"If the main claims hold, the paper fills a genuine gap in the Schrödinger Bridge literature: the discrete-state, discrete-time setting with a general Markov reference was listed as an open case in the authors' Table 1, whereas continuous-space analogues were covered by prior work (Shi et al. 2023; Gushchin et al. 2024b). The characterization theorem is clean and its proof is mostly self-contained, citing Leonard's standard result for the static SB. The proposed CSBM algorithm is a natural extension of D3PM-style discrete diffusion to a Schrödinger bridge setting, and the authors provide code and a range of experiments. However, the algorithmic convergence guarantee—the paper's central practical claim—is not actually proved, and the experimental comparison against continuous-space baselines is confounded by operating in different data spaces. These issues are load-bearing for the paper's core narrative, but they are fixable within the manuscript's scope.","major_comments":[{"comment":"The convergence of D-IMF is asserted with the sentence 'the convergence easily follows from the generic proof argument in (Shi et al., 2023, Theorem 8)' and no proof is provided. Shi et al.'s Theorem 8 is a continuous-time result, and its proof relies on continuous-time machinery (Brownian bridges, Girsanov-type arguments) that does not automatically transfer to the finite discrete state space and arbitrary full-support Markov reference qref considered here. Theorem 3.1 characterizes q* but does not by itself establish that the alternating KL projections in Eq. (6) converge, or that the limit is q* rather than some other fixed point. Since Corollary 3.2 is the paper's core algorithmic guarantee, this is not a local omission: the authors should either give a self-contained proof for finite spaces (e.g., by viewing Eq. (6) as cyclic KL projections and invoking a finite-state alternating minimization theorem, or by adapting the argument of Shi et al. explicitly to this setting) or state a precise theorem with conditions under which convergence is guaranteed and defer to a complete proof.","section":"Section 4.4, Table 2"},{"comment":"The quantitative comparison with ASBM and DSBM is not apples-to-apples: CSBM operates on discrete VQ-GAN latent tokens (S=1024, D=256), whereas ASBM and DSBM operate in continuous pixel space, and the comparison numbers are taken from (Gushchin et al., 2024b) rather than re-evaluated in a shared protocol. The better FID/CMMD/LPIPS values for CSBM could partly reflect the information already lost or organized in the VQ-GAN latent space, not a superiority of the SB solver. In addition, the CSBM metrics in Table 2 are reported without error bars or multiple seeds, so the claim that 'our approach achieves better results' is not statistically substantiated. I recommend reframing these results as an illustration rather than a head-to-head win, or providing a same-space comparison (e.g., decoding both methods' outputs to pixels and then computing metrics on the same decoded images).","section":"Section 4.1"},{"comment":"The numerical verification of D-IMF convergence is restricted to the symmetric qunif and qgauss reference processes. Corollary 3.2 claims convergence for any full-support Markov qref. Please add at least one asymmetric, non-reversible reference process (e.g., a Markov chain with a drift) to the synthetic convergence study, or explicitly state that the general case is not empirically tested. Without such a test, the paper's evidence for the broad claim in Corollary 3.2 is incomplete.","section":"Section 4.1"}],"minor_comments":[{"comment":"The word 'stochastisity' should be 'stochasticity'.","section":"Figure 1 caption"},{"comment":"'additional immages' should be 'additional images'.","section":"Section 4, first paragraph"},{"comment":"The displayed L(m) has a minus sign before the term E_{qref(x_{t_N}|x_0,x_1)}[log m(x_1|x_{t_N})] that follows from the KL decomposition; the formatting makes it look like a separate term, so please clarify the derivation or restructure the equation.","section":"Eq. (10)"},{"comment":"In the forward step, sampling n ~ U[1, N+1] and then sampling x_{t_{n-1}} ~ qref(x_{t_{n-1}}|x_0,x_1) is ambiguous when n = N+1 because x_{t_N} is not defined as a state before x_1 in the forward chain; please clarify the indexing (e.g., define x_{t_0}=x_0, x_{t_{N+1}}=x_1, or restrict n to 1..N).","section":"Algorithm 1"},{"comment":"The rows 'D-IMF=1 grad updates' and 'D-IMF grad updates' are confusing; consider renaming them 'gradient updates per D-IMF sweep' and 'total gradient updates per outer iteration'.","section":"Table 5"},{"comment":"The statement 'manual inspection of the samples in Table 4 suggests that most generations convey the correct polarity' is subjective; reporting a quantitative polarity score on the generated samples would be more convincing.","section":"Appendix C.4"}],"recommendation":"major_revision","confidential_remarks":"The characterization theorem (Theorem 3.1) appears correct and is a worthwhile contribution. The main risk is Corollary 3.2, which is the algorithmic payoff of the paper but is currently an unproven transfer of a continuous-time result. If the authors can supply a rigorous convergence proof (or a precise citation to a finite-state alternating-projection theorem), the paper would be acceptable. The experimental comparison to continuous-space baselines should be reframed to avoid overclaiming, and the lack of error bars should be addressed. I would not reject the paper on the current evidence, but I would insist on the convergence proof before accepting."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe headline: this paper closes a genuine theoretical gap—characterization of dynamic Schrödinger bridges on finite discrete spaces with general Markov reference—and ships a practical algorithm, CSBM, with experiments across synthetic data, MNIST, VQ-CelebA, and Amazon reviews. The theory is the real contribution; the algorithm's convergence guarantee is the soft spot.\n\nThe genuinely new thing is Theorem 3.1: for finite X and full-support Markov qref, the dynamic SB solution is the unique process that is both Markovian and reciprocal with respect to qref. The proof is short, uses Leonard's static theorem, and checks out. This fills an actual row in their Table 1 and gives a theoretical grounding for D-IMF in discrete spaces.\n\nThe practical side borrows D3PM-style posterior sampling and ASBM's bidirectional matching, so it is not deeply novel, but it is a working method for discrete SB. Code is out. Experiments are adequate for a first demonstration: the 2D and MNIST results show clear qualitative dependence on α and N, and the convergence plot in Figure 1 supports the theory empirically for two references.\n\nThe soft spots, roughly in order:\n\n- Corollary 3.2 is asserted, not proved. The paper says convergence 'easily follows' from Shi et al. (2023, Theorem 8), a continuous-time result. No argument is given that the alternating KL projections converge in finite state spaces for arbitrary Markov qref. This is load-bearing: if the transfer fails, the algorithm is not guaranteed to solve the SB. The fix is likely a Bregman alternating projection argument, but as written it's an unverified cite. A referee should push on this.\n- The CelebA comparison is not apples-to-apples: CSBM works in a VQ-GAN latent space while ASBM/DSBM run in continuous pixels. The better FID/LPIPS may largely reflect the representation.\n- Single-run metrics, no error bars. For FID and CMMD this is a real omission.\n- The factorization of the learnable transition (9) is a known limitation, acknowledged in Appendix A; the MNIST pixelation shows the effect.\n\nWho is this for: SB researchers and anyone applying discrete generative models (text, graphs, VQ latents). The characterization theorem is worth knowing even if the algorithm details are tuned to their specific setup.\n\nRecommendation: send it to peer review. The theory deserves referee time, and the convergence gap is addressable. I would ask for a proof of Corollary 3.2 or an explicit conjecture, and for error bars on the headline metrics.","headline":"A genuinely new characterization theorem for Schrödinger bridges on discrete spaces, paired with an algorithm whose convergence guarantee is cited rather than proved.","tokens_in":24780,"tokens_out":5904,"would_cite":true,"duration_ms":50527,"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":"In finite discrete spaces with full-support marginals and a Markov reference, the dynamic Schrödinger bridge is the unique process that is both Markovian and reciprocal, and the D-IMF alternating-projection scheme provably converges to it…","keywords":["Schrödinger bridge","discrete state spaces","iterative Markovian fitting","unpaired domain translation","categorical generative modeling","vector quantization","entropic optimal transport"],"falsifier":"Run D-IMF analytically on a small finite state space with a full-support Markov reference and compute the exact Sinkhorn bridge $q^*$. If the iterates' $\\mathrm{KL}(q^l\\,\\|\\,q^*)$ does not approach zero, or if two different processes are simultaneously Markovian and reciprocal with the same endpoint marginals, Theorem 3.1 and Corollary 3.2 would be refuted.","tokens_in":1844,"feed_emoji":"🧩","tokens_out":9225,"duration_ms":121705,"temperature":0.7,"pith_summary":"The paper establishes that Schrödinger bridge problems on finite discrete state spaces are solvable by a specific alternating-projection scheme with a convergence guarantee. Its main theorem shows that, for full-support marginals and a full-support Markov reference process, the unique solution of the dynamic Schrödinger bridge is the only process that is simultaneously Markovian and reciprocal with respect to the reference. A corollary gives that discrete-time Iterative Markovian Fitting (D-IMF), which alternates reciprocal and Markovian projections, converges to this solution in Kullback–Leibler divergence. The authors then turn this guarantee into a practical algorithm, Categorical Schrödinger Bridge Matching (CSBM), and demonstrate it on synthetic data, vector-quantized images, and text sentiment transfer.","feed_headline":"Discrete Schrödinger bridges get a provable convergence result","feed_subtitle":"The new CSBM algorithm turns the proof into working translations for tokens, codebooks, and image categories.","key_machinery":"The central object is a finite-state discrete-time process that is simultaneously Markovian and reciprocal. Reciprocity means that, conditionally on the two endpoints, the interior path follows the same bridge as the reference process, while Markovianity means transitions factor one step at a time. The load-bearing identity is equation (11): for any intermediate time $t_n$, $\\log q(x_1|x_0)-\\log q_{\\mathrm{ref}}(x_0,x_1)$ splits as $f_0(x_0,x_{t_n})+f_1(x_{t_n},x_1)$, which forces the endpoint coupling to have the Schrödinger-bridge form $\\psi(x_0)\\,q_{\\mathrm{ref}}(x_1|x_0)\\,\\phi(x_1)$. The algorithmic machinery is D-IMF, the alternating reciprocal and Markovian projections, implemented with a neural network that samples an endpoint from a factorized learned distribution and then uses the reference bridge to move between states.","core_discovery":"The central discovery is a characterization theorem for the dynamic Schrödinger bridge in finite discrete spaces with a general Markov reference process. Theorem 3.1 says: if $q^*$ has the prescribed endpoint marginals $p_0$ and $p_1$, is Markovian, and is reciprocal with respect to $q_{\\mathrm{ref}}$ (meaning its bridges between endpoints coincide with $q_{\\mathrm{ref}}$'s), then $q^*$ is the unique minimizer of $\\mathrm{KL}(q\\,\\|\\,q_{\\mathrm{ref}})$ over all processes with those endpoint marginals. The proof rewrites the joint density of a Markov-reciprocal process as $q(x_0,x_1)=\\psi(x_0)\\,q_{\\mathrm{ref}}(x_1|x_0)\\,\\phi(x_1)$, the canonical form of the static entropic optimal transport plan, and then invokes the standard identification of that plan as the Schrödinger bridge. Corollary 3.2 then states that D-IMF iterates converge in KL to $q^*$, which is the theoretical foundation the D-IMF procedure previously lacked for discrete spaces.","pith_inferences":["An inference beyond the paper: the proof argument is stated to apply to general state spaces, which suggests the same characterization could yield a discrete-free variant of D-IMF for continuous spaces with arbitrary Markov references, not just the Wiener-process case.","An inference beyond the paper: the full-support assumption on $p_0$, $p_1$, and $q_{\\mathrm{ref}}$ is load-bearing, because the proof takes logarithms of strictly positive densities; extending the result to sparse or degenerate marginals may require a limiting argument or an explicit support-conditioned formulation.","An inference beyond the paper: the algorithmic factorization over dimensions is not covered by the theorem, so the visual pixelation reported in the paper likely reflects this implementation gap rather than the convergence result; a testable extension would compare factorized transitions against copula-based or energy-based joint transitions on the same tasks.","An inference beyond the paper: the paper observes that convergence behavior depends on the number of time steps $N$, so a quantitative convergence-rate analysis as a function of $N$, $\\alpha$, and the reference process would be a natural next step."],"forward_implications":["D-IMF now has a convergence guarantee on finite discrete spaces with a general Markov reference, not just continuous Euclidean setups.","CSBM can be applied to discrete data such as vector-quantized codebooks, text tokens, and categorical variables, as demonstrated on colored MNIST, CelebA latent spaces, and Amazon reviews.","The theory requires only a finite number of time steps, and the paper notes that even $N=1$ intermediate step is enough for the characterization to hold.","The practical algorithm works with both uniform and Gaussian-like categorical reference processes and inherits the diffusion-style training objective from discrete diffusion models.","The paper's experiments indicate that CSBM attains competitive generative quality on unpaired image translation while operating directly on discrete tokens rather than continuous pixel space."],"supporting_citations":[{"why":"Introduces the Schrödinger bridge problem that this paper solves in discrete spaces.","marker":"(Schrödinger, 1931)"},{"why":"Supplies the static Schrödinger bridge characterization used at the end of the proof of Theorem 3.1.","marker":"(Léonard, 2013)"},{"why":"Provides the generic IMF convergence argument (Theorem 8) that Corollary 3.2 relies on.","marker":"(Shi et al., 2023)"},{"why":"Defines the D-IMF procedure and the Markovian-projection equivalence that Proposition 3.3 extends.","marker":"(Gushchin et al., 2024b)"},{"why":"Introduces the IMF framework that D-IMF is a discrete-time instance of.","marker":"(Peluchetti, 2023)"},{"why":"Supplies the D3PM parameterization and loss that CSBM adapts for its Markovian projection.","marker":"(Austin et al., 2021)"},{"why":"Defines Sinkhorn, used in the paper's convergence experiments to compute the ground-truth bridge and to identify entropic optimal transport.","marker":"(Cuturi, 2013)"}],"fun_headline_variants":["Discrete Schrödinger bridge: convergence proof","CSBM: provable discrete Schrödinger bridge","Categorical Schrödinger bridge matching: proof","Provable convergence for discrete Schrödinger bridges"],"cache_read_input_tokens":26880,"weakest_assumption_plain":"The claim leans on the assumption that the D-IMF alternating projection scheme converges in KL to the unique Markovian-reciprocal process in finite discrete spaces, a transfer from a generic existing proof rather than a proof worked out in this paper.","fun_headline_variants_meta":{"raw":{"variants":["Discrete Schrödinger bridge: convergence proof","CSBM: provable discrete Schrödinger bridge","Categorical Schrödinger bridge matching: proof","Provable convergence for discrete Schrödinger bridges"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000215,"raw_usage":{"total_tokens":1442,"prompt_tokens":974,"completion_tokens":468,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":590,"completion_tokens_details":{"reasoning_tokens":412}},"tokens_in":590,"tokens_out":468,"duration_ms":4522,"temperature":1.0,"reasoning_tokens":412,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T15:22:41.095262+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run D-IMF analytically on a small finite state space with a full-support Markov reference and compute the exact Sinkhorn bridge $q^*$. If the iterates' $\\mathrm{KL}(q^l\\,\\|\\,q^*)$ does not approach zero, or if two different processes are simultaneously Markovian and reciprocal with the same endpoint marginals, Theorem 3.1 and Corollary 3.2 would be refuted.","supporting_citations":[{"cited_title":"D., Campbell, A., and Doucet, A","cited_arxiv_id":null,"evidence_quote":"Provides the generic IMF convergence argument (Theorem 8) that Corollary 3.2 relies on."},{"cited_title":"Diffusion bridge mixture transports, Schr \\\"o dinger bridge problems and generative modeling","cited_arxiv_id":null,"evidence_quote":"Introduces the IMF framework that D-IMF is a discrete-time instance of."}],"review_version":1}