acceptodds
Under review as a conference paper at ICLR 2027

Discrete Bridges for Mutual Information Estimation

Abstract

Diffusion bridge models in both continuous and discrete state spaces have recently become powerful tools in the field of generative modeling. In this work, we leverage the discrete state space formulation of bridge matching models to address another important problem in machine learning and information theory: the estimation of the mutual information (MI) between discrete random variables. By framing MI estimation as a domain transfer problem, we construct a Discrete Bridge Mutual Information (DBMI) estimator suitable for discrete data, that poses difficulties for conventional MI estimators. We showcase the performance of our estimator on three MI estimation benchmarks: low-dimensional, DNA with low-dimensional tags and image-based.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Discrete Diffusion Models, Diffusion Bridge Models, Mutual Information

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_ibgCOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Discrete Bridge Mutual Information estimation (DBMI) for discrete random variables. It constructs two reciprocal processes sharing the same reference bridges but having joint and independent endpoint distributions, respectively. Their path-space KL divergence equals the mutual information and decomposes into expected KL divergences between conditional Markov transitions. The practical estimator learns these transitions through conditional bridge matching, using a shared network and a factorized parameterization. Experiments cover factorized categorical distributions, DNA sequences with correlated synthetic tags, and binary images generated from correlated rectangle parameters.

Critical strengths
  1. A useful bridge-based formulation for discrete MI estimation. The shared-bridge construction provides a clear connection between endpoint mutual information and transition-level KL divergences. Sampling intermediate states directly from reference bridges makes training and estimation possible without simulating complete trajectories. This is a useful extension of bridge-based information estimation to categorical data.
  2. Promising empirical stability on controlled benchmarks. DBMI achieves competitive estimation errors and relatively low variability across training seeds in several settings, including the DNA-tag and image experiments. The known ground-truth MI makes these comparisons interpretable. The use of comparable backbones for DBMI and Info-SEDD also strengthens the experimental evaluation.
Critical weaknesses
  1. The justification of the practical factorized estimator is incomplete.

Proposition 2 concerns exact transition distributions, whereas the implementation uses the factorization in Eq. (14). The claim in lines 482–485 that the resulting bias vanishes as the number of steps increases does not follow under the fixed per-step noise parameter in Eq. (15).

For example, let both endpoint vectors equal (B, B), where B is a uniformly distributed binary variable, and choose two categories with a per-step switching probability of 1/2. The reference process then independently resamples every coordinate at each step. For any number of intermediate steps, the joint and independent bridges have identical intermediate transitions. At the final transition, the joint endpoint is determined by the starting point, while the independent endpoint is uniform over the two vectors (0, 0) and (1, 1). Its optimal coordinate-factorized approximation is uniform over all four binary vectors. Substituting these factorized transitions into Eq. (10) therefore gives twice the true mutual information: approximately 1.386 rather than 0.693 nats, regardless of the number of steps. A suitable vanishing-step-noise regime might address this issue, but that regime and its assumptions need to be stated and justified.

There are also two specific inconsistencies requiring clarification. First, Eq. (5) should generally average over the endpoint posterior conditioned on both the current intermediate state and the starting point, rather than conditioned only on the starting point. Second, Algorithm 2 should use an N+1 multiplier when uniformly sampling the N+1 terms indexed from 0 through N. These issues do not themselves invalidate the exact KL decomposition, but their implications for the implementation are unclear.

  1. The empirical evidence does not yet establish a sufficiently strong advance over the closest prior approaches.

The central construction closely follows InfoBridge, with existing categorical bridge-matching machinery supplying the discrete modeling framework. Consequently, the practical advantage over existing discrete estimators is particularly important. However, the categorical benchmark factorizes across dimensions, the image benchmark has only four informative latent variables, and the DNA dependence comes from synthetic tags at fixed positions. These are useful controlled tests but provide limited evidence about more general dependence structures. The extreme overestimation by InfoSEDD-J on images also warrants diagnosis before attributing the gap to the underlying approaches.

Additionally, Table 8 contains numerical inconsistencies that affect confidence in the reporting. For the two-category setting, the ground truth is 3.63 and the f-DIME-KL mean is 3.97, yet its reported RMSE is 0.10, below the absolute mean error of 0.34. The f-DIME-H entry has the same problem. These entries should be checked against the individual seed results.

Questions for authors

The following are clarification and validation requests that could affect my assessment:

  1. What assumptions on the reference process, particularly how the per-step noise parameter changes with the number of steps, justify vanishing factorization bias? How does the claim accommodate the counterexample above? Evidence separating factorization error from model-fitting error would help establish the practical estimator's reliability.

  2. Are Eq. (5) and the N multiplier in Algorithm 2 manuscript errors only? Please clarify the actual posterior conditioning and normalization used in the implementation, and whether correcting them changes any reported results.

  3. Can the authors reconcile the inconsistent entries in Table 8 with the per-seed estimates and explain the severe failure of InfoSEDD-J on the image benchmark? In particular, what checks were performed on its convergence and numerical estimation procedure?

Related-work suggestion: I recommend considering the following papers on information-theoretic diffusion and mutual information estimation:

4 comments

We thank Reviewer ibgC for the thoughtful and detailed review. We are glad that you found our bridge-based formulation to be a useful extension of mutual information estimation to categorical data, enabling trajectory-free training and estimation, and that you appreciated DBMI's strong empirical accuracy, stability across seeds, and fair evaluation. Below, we address each of your comments and questions in detail. We have also uploaded a revised version of the manuscript with all changes highlighted in blue.

1. Factorizaton transitions and MI estimation vanishing bias clarification

Reviewer quote

The justification of the practical factorized estimator is incomplete.

Proposition 2 concerns exact transition distributions, whereas the implementation uses the factorization in Eq. (14). The claim in lines 482–485 that the resulting bias vanishes as the number of steps increases does not follow under the fixed per-step noise parameter in Eq. (15).

For example, let both endpoint vectors equal (B, B), where B is a uniformly distributed binary variable, and choose two categories with a per-step switching probability of 1/2. The reference process then independently resamples every coordinate at each step. For any number of intermediate steps, the joint and independent bridges have identical intermediate transitions. At the final transition, the joint endpoint is determined by the starting point, while the independent endpoint is uniform over the two vectors (0, 0) and (1, 1). Its optimal coordinate-factorized approximation is uniform over all four binary vectors. Substituting these factorized transitions into Eq. (10) therefore gives twice the true mutual information: approximately 1.386 rather than 0.693 nats, regardless of the number of steps.

A suitable vanishing-step-noise regime might address this issue, but that regime and its assumptions need to be stated and justified.

What assumptions on the reference process, particularly how the per-step noise parameter changes with the number of steps, justify vanishing factorization bias? How does the claim accommodate the counterexample above?

Evidence separating factorization error from model-fitting error would help establish the practical estimator's reliability.

Answer

Thank you for pointing out the gap in our argument. Your counterexample is correct and shows that increasing the number of transitions alone does not guarantee vanishing factorization bias when the per-step stochasticity is fixed. However, our original statement did not specify how the per-step stochasticity should change as the number of transitions increases. The intended setting is temporal refinement with a fixed reference endpoint transition distribution qref(x1∣x0)q^{\rm ref}(x_1\mid x_0):

qref(x1∣x0)=∏d=1D[e−β1{x1d=x0d}+1−e−βS],β>0.q^{\rm ref}(x_1\mid x_0) = \prod_{d=1}^{D}\left[e^{-\beta}\mathbf{1}_{\{x_1^d=x_0^d\}}+\frac{1-e^{-\beta}}{S}\right], \qquad \beta>0.

In this setting, increasing the number of intermediate time points requires decreasing the per-step stochasticity. Specifically, we consider

αN=S−1S(1−e−β/(N+1)),β>0,\alpha_N=\frac{S-1}{S}\left(1-e^{-\beta/(N+1)}\right), \qquad \beta>0,

which preserves the reference endpoint transition distribution for every NN.

To formalize this setting and connect it directly to MI estimation, we have added Proposition 3 in Section 4.3 of the revised manuscript (with its proof in Appendix A.3). Under a strict-positivity assumption on the endpoint distribution, it establishes an O((N+1)−1)O((N+1)^{-1}) bound on the factorization bias when the coordinate transition marginals are known exactly:

Proposition 3 (Vanishing Factorization Bias). Assume that π(x0,x1)>0\pi(x_0,x_1)>0 for all (x0,x1)∈X2(x_0,x_1)\in\mathcal{X}^{2}. Fix β>0\beta>0, and let rπ,Njointr_{\pi,N}^{\mathrm{joint}} and rπ,Nindr_{\pi,N}^{\mathrm{ind}} be the exact reciprocal processes defined in Eqs. (8)–(9), using the reference process with stochasticity parameter αN\alpha_N. For a∈{joint,ind}a\in\{\mathrm{joint},\mathrm{ind}\}, define

rˉπ,Na(xtn+1∣xtn,x0)≜∏d=1Drπ,Na(xtn+1d∣xtn,x0),\bar r_{\pi,N}^{a}(x_{t_{n+1}}\mid x_{t_n},x_0) \triangleq \prod_{d=1}^{D}r_{\pi,N}^{a}(x_{t_{n+1}}^{d}\mid x_{t_n},x_0),

where each factor is the exact coordinate marginal of the corresponding conditional transition. Define the population factorized MI functional by

INfact≜∑n=0NErπ,Njoint(x0,xtn)[KL(rˉπ,Njoint(⋅∣xtn,x0)∥rˉπ,Nind(⋅∣xtn,x0))].I_ N^{\mathrm{fact}} \triangleq \sum_ {n=0}^{N} \mathbb{E}_ {r_ {\pi,N}^{\mathrm{joint}}(x_ 0,x_ {t_ n})}\left[ \mathrm{KL}\left( \bar{r}_ {\pi,N}^{\mathrm{joint}}(\cdot\mid x_ {t_ n},x_ 0) \Vert \bar{r}_ {\pi,N}^{\mathrm{ind}}(\cdot\mid x_ {t_ n},x_ 0) \right)\right].

Then there exists a finite constant C=C(π,β,D,S)C=C(\pi,\beta,D,S), independent of NN, such that

∣INfact−I(X0;X1)∣≤CN+1.\left|I_N^{\mathrm{fact}}-\mathsf{I}(X_0;X_1)\right|\leq\frac{C}{N+1}.

This adressed the counter example, which uses a fixed switching probability α=1/2\alpha = 1/2 (so coordinates are fully resampled at every step rather than refined with αN=O((N+1)−1)\alpha_N = O((N+1)^{-1})) and a degenerate endpoint distribution that violates π(x0,x1)>0\pi(x_0, x_1) > 0.

2. Eq. (5) endpoint posterior

Reviewer quote

Eq. (5) should generally average over the endpoint posterior conditioned on both the current intermediate state and the starting point, rather than conditioned only on the starting point.

Are Eq. (5) and the N multiplier in Algorithm 2 manuscript errors only? Please clarify the actual posterior conditioning and normalization used in the implementation, and whether correcting them changes any reported results.

Answer

We thank the reviewer for catching this mistake. In Eq. (5), the expectation should be taken with respect to the endpoint posterior rπ(x1∣xtn−1,x0)∝π(x1∣x0)qref(xtn−1∣x0,x1)r_ \pi(x_ 1\mid x_ {t_ {n-1}},x_ 0)\propto\pi(x_ 1\mid x_ 0)q^{\mathrm{ref}}(x_ {t_ {n-1}}\mid x_ 0,x_ 1), rather than π(x1∣x0)\pi(x_ 1\mid x_ 0). We have corrected this equation and its accompanying explanation in the revised manuscript.

This correction does not change the optimization objectives in Eqs. (6)–(7). Eq. (7) already samples from π(x0,x1)qref(xtn−1∣x0,x1)\pi(x_ 0,x_ 1)q^{\mathrm{ref}}(x_ {t_ {n-1}}\mid x_ 0,x_ 1), under which x1x_ 1, conditional on xtn−1x_ {t_ {n-1}} and x0x_ 0, follows precisely the endpoint posterior in the corrected Eq. (5). The same argument applies to Eq. (6) for fixed x0x_ 0. Thus, this correction requires no changes to the optimization objectives, training Algorithm 1, or the implementation.

3. Algorithm 2 normalization

Reviewer quote

Algorithm 2 should use an N+1 multiplier when uniformly sampling the N+1 terms indexed from 0 through N. These issues do not themselves invalidate the exact KL decomposition, but their implications for the implementation are unclear.

Are Eq. (5) and the N multiplier in Algorithm 2 manuscript errors only? Please clarify the actual posterior conditioning and normalization used in the implementation, and whether correcting them changes any reported results.

Answer

We thank the reviewer for catching this discrepancy. Indeed, because the estimator uniformly samples N+1N+1 time indices and averages their KL terms, the scaling factor should be N+1N+1 rather than NN. This off-by-one factor was also present in our evaluation code, introducing a small downward bias of ≈1%\approx 1\% on the Low-Dimensional benchmarks and ≈0.5%\approx 0.5\% on the Image benchmark. Since this factor enters purely as a multiplicative constant, we rescaled all affected metrics in closed form and updated the corresponding tables and figures in the revised manuscript (highlighted in blue). Notably, in most cases, applying this correction reduces the discrepancy with the ground truth rather than increasing it.

Importantly, these updates do not change any method rankings across the benchmarks, nor do they affect any of our contributions, conclusions, or experimental discussions.

4. Practical positionining w.r.t. other methods

Reviewer quote

The empirical evidence does not yet establish a sufficiently strong advance over the closest prior approaches.

The central construction closely follows InfoBridge, with existing categorical bridge-matching machinery supplying the discrete modeling framework. Consequently, the practical advantage over existing discrete estimators is particularly important.

Answer

Overall, DBMI achieves leading or shared-leading performance across all evaluated benchmarks, with a substantial margin over competing methods on the DNA Tag benchmark. Because few existing discrete MI benchmarks push estimators to their limits, we introduced the DNA Tag and image-based benchmarks to help fill this gap.

The key advantage of DBMI is that it is stable, robust, and performs reliably across all originally presented settings, making it a versatile MI estimator for discrete data. By contrast, each competing estimator exhibits a distinct weakness: InfoSEDD-J performs well on the synthetic benchmark but deteriorates on the DNA Tag and Image benchmarks, InfoSEDD-C underperforms DBMI across nearly all settings, and ff-DIME struggles in high-MI regimes. Because DBMI remains stable across all of these regimes, it offers the most reliable practical choice for general discrete MI estimation, with its main practical advantage being stability and fewer failure cases.

5. Dependence structure in benchmarks

Reviewer quote

the categorical benchmark factorizes across dimensions, the image benchmark has only four informative latent variables, and the DNA dependence comes from synthetic tags at fixed positions. These are useful controlled tests but provide limited evidence about more general dependence structures.

Answer

Thank you for raising this concern. We agree that our controlled benchmarks have limitations. Reliable comparison of MI estimators benefits from benchmarks with known ground-truth MI, which constrains how the joint distributions can be constructed. Existing benchmarking approaches typically rely on analytically tractable dependence structures or transformations that preserve MI [1, 2].

In addition, benchmarking MI estimation in discrete spaces remains relatively underexplored. In our work we have contributed DNA-tag and discrete rectangle-image benchmarks as two controlled settings that combine known MI with complex observations. In the revised manuscript’s Future Work discussion, we now note that current benchmarks, including ours, cover a limited range of dependence structures and identify developing richer discrete benchmarks with known ground-truth MI as an important research direction.

6. Table 8 statistics

Reviewer quote

Additionally, Table 8 contains numerical inconsistencies that affect confidence in the reporting. For the two-category setting, the ground truth is 3.63 and the f-DIME-KL mean is 3.97, yet its reported RMSE is 0.10, below the absolute mean error of 0.34. The f-DIME-H entry has the same problem. These entries should be checked against the individual seed results.

Answer

Thank you for catching these inconsistencies. At D=10,S=2D=10,S=2, the DBMI entry should agree with Table 2. For f-DIME-KL and f-DIME-H, the errors were in the reported means and standard deviations and we have corrected entries in the revised version.

7. InfoSEDD-J image overestimation

Reviewer quote

The extreme overestimation by InfoSEDD-J on images also warrants diagnosis before attributing the gap to the underlying approaches.

explain the severe failure of InfoSEDD-J on the image benchmark? In particular, what checks were performed on its convergence and numerical estimation procedure?

Answer

Thank you for raising this concern. InfoSEDD [3] is a discrete diffusion counterpart to MINDE [4], and both offer joint formulations. Substantial overestimation by these joint estimators has been reported in prior work. In its text-consistency experiment, InfoSEDD [3, Table 11] reports an InfoSEDD-J estimate of 106.69106.69 versus ground-truth MI 00, and 157.90157.90 versus an approximate reference range of ≈25 to 30\approx 25 \text{ to } 30 nats. InfoBridge [5, Tables 16–19] reports MINDE-J estimates of 450450, 308308, 539539, and 511511, respectively, versus ground-truth MI 8080. It also reports severe overestimation on protein embeddings, with a MINDE-J MAE of 13421342 nats (Section 5.3, Table 14). We observe overestimation by InfoSEDD-J on our DNA-tag benchmark as well.

Our hypothesis is that two factors contribute to the observed overestimation. First, InfoSEDD-J requires learning the joint diffusion process [3], which may be more challenging than learning a conditional or bridge process on the rectangles benchmark. Second, its MI estimator sums two contributions [3, Algorithm 1] corresponding to transitions in each variable, both involving approximate joint and marginal scores, which can accumulate in the final estimate, potentially causing substantial overestimation especially in low GT MI cases.

We used the official implementation with the setup described in our paper, under which InfoSEDD-C performs well. Limited hyperparameter variations did not yield substantial improvements, but we did not conduct an extensive search. We therefore interpret this result as a failure under the evaluated configuration.

We agree that the severe overestimation requires diagnosis before attributing it to the estimator itself. We will qualify the comparison as an observation under the evaluated configuration.

8. Suggested related work

Reviewer quote

Related-work suggestion: I recommend considering the following papers on information-theoretic diffusion and mutual information estimation: ....

Answer

Thank you for suggesting these references. We have incorporated Kong et al., Jeon et al., and Yu et al. into the Related Work section and cited Czyż et al. [1] in the benchmark discussion on MI invariance under bijective mappings.

We hope that our answers, the new theoretical analysis of coordinate-factorized transitions (Section 4.3, Proposition 3), the clarified advancement over competitor methods and the updated manuscript have thoroughly addressed your concerns. Please, in the remaining time let us know if any questions remain, and we kindly ask if you would consider adjusting your score in light of these revisions.

References

[1] Czyż et al., Beyond Normal: On the Evaluation of Mutual Information Estimators, NeurIPS 2023.

[2] Butakov et al., Mutual Information Estimation via Normalizing Flows, NeurIPS 2024.

[3] Foresti et al., Information Estimation with Discrete Diffusion, 2026.

[4] Franzese et al., MINDE: Mutual Information Neural Diffusion Estimation, ICLR 2024.

[5] Kholkin et al., InfoBridge: Mutual Information Estimation via Bridge Matching, 2026.

Thank you for the detailed response. The added factorization-bias analysis under explicit temporal-refinement assumptions, together with the posterior-conditioning clarification and numerical corrections, substantially addresses my main concerns. Some reservations remain about the positivity assumption’s applicability to sparse-support data and the limited diversity of benchmark dependence structures. Overall, I am raising my rating from weak rejection to weak acceptance.

Reviewer_XrZfOpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

In this work, the authors present a new method called DBMI to estimate mutual information (MI) between discrete random variables. As for the continuous case, MI estimation poses significant challenges in the high-dimensional setup.

They cast the estimation as a domain transfer problem in the discrete domain: the goal is to learn how to transport a starting distribution to a target distribution, which is a generalization of the widespread diffusion models that instead sample from a simple starting distribution to arrive at a data distribution.

The mathematical tool underlying DBMI are reciprocal processes, which are viewed as Markov chains. A generic reciprocal process requires a reference process, and it is constrained to have a given marginal distribution at its end-points. Now, fixing the starting state (that is, constructing a conditional reciprocal process on the starting state) makes it possible to summarize the influence of the target through a correction that depends only on the current state. This is how the authors show that a conditional reciprocal process is Markovian. This enables a useful representation of reciprocal processes as a family of Markov processes conditioned on the initial state.

At this point, the authors introduce the conditional bridge matching problem, that transforms the untractable problem of exact evaluation of a Markovian conditional reciprocal process into an optimization problem, which can be viewed as the typical variational boound used in (continuous variables) diffusion models.

The construction above is background material, that the authors expose succinctly but clearly. Then, the key idea of this paper is to show that the mutual information between two discrete r.v.s can be computed as the KL divergence between two reciprocal processes, one representative of the join, and one representative of the product of the marginals. This is translated into a practical algorithm, which first requires learning an approximation to the reciprocal processes through bridge matching. The amortized version of the proposed algorithm borrows from techniques developed in the state of the art (MINDE, and INFO-SEDD). Additionally, the authors propose to impose a factorized structure over the dimensions of the probabilities from which data is sampled from, which reduces the number of outputs required to be produced.

DBMI is validated on scenarios in which ground-truth MI is available: low dimensional settings, including a variant that "simulates" DNA data, and image data, which is high-dimensional. DBMI is shown to outperform competitors in most settings, with a lower variance.

Critical strengths
  • Estimating MI between discrete distributions is an important endeavor, with several downstream tasks benefitting from accurate methods that work with high-dimensional data. The authors proposed a technically sound method, which is simple to implement and that achieves excellent performance in scenarios where MI is available as ground truth.

  • To the best of my knowedlge (and despite it is always possible to ask for more, see below for the "weaknesses") this work has really done a good job in the evaluation part. The benchmarks are sound, the image data scenario is challenging and interesting, and the evaluation is comprehensive, with many alternatives from the literature, including "neural estimators" and classical ones.

  • I agree with the authors: MI estimation is a building block that can unlock many interesting scientific analyses, including temporal variants, and the study of complex systems through the lenses of information decomposition.

Critical weaknesses
  • In general the editorial quality of this paper is very high, even if it requires good effort to reconcile some details from the appendix when reading prepositions in the first part of the paper. Instead, the practical implementation is more terse, and the two algorithms (training and estimation) are quite cryptic, and could enjoy some polishing to ease their parsing and to understand the details.

  • I wonder why the authors stopped at D=50 in their synthetic benchmark. To my knowledge, considered the related work, this is already a quite "high dimensionality" problem for MI estimators. Why didn't you push it further to 100 or more? Similarly, for the image data scenario, or even continuing with synthetic benchmarks, I wonder how robust would be MI estimation in cases of very high MI, given that in general (and again to the best of my knowledge) MI estimators suffer quite a bit with high MI cases.

Questions for authors
  1. In the notation section: why do you use X\mathcal{X} to identify both the state space and the path space?
  2. Line 107: in your definition of a reciprocal process, you state that it is constrained to have marginal distribution π(x0,x1)\pi(x_0,x_1), but this is the joint distribution. It's obviously a typo.
  3. Line 210: the sentence seems broken to me "To tackle this problem the key idea we choose the reference process ..."
  4. Line 372: typo, you refer twice to Algorithm 1, the second reference should be on Algorithm 2.
  5. Discussion: you may want to double check your references, as I think you used \cite instead of \citep, so you're missing parentheses.
  6. In the appendix, I find Figure 6 very interesting. How do you explain the stability of f-DIME (even if it dramatically underestimates MI)? More imporantly, both INFO-SEDD and the proposed method seem to suffer when there only are few samples for training the models. What about the number of samples to be used to estimate MI? It is not easy to find a pattern: it looks like that using only one MC sample produces better average estimates, but costs variance obviously; however, increasing the number of MC samples seems to affect negatively the average estimate. Why?
5 comments

We thank Reviewer XrZf for the thoughtful review and constructive feedback. We are glad that you recognized the importance of discrete mutual information estimation for high-dimensional data and downstream scientific analyses, appreciated the technical soundness, simplicity, and strong performance of our method, and found our benchmarks and experimental evaluation to be sound and comprehensive. Below, we address each of your comments and questions in detail. We have also uploaded a revised version of the manuscript with all changes highlighted in blue.

1. Notation and algorithms

Reviewer quote

In general the editorial quality of this paper is very high, even if it requires good effort to reconcile some details from the appendix when reading prepositions in the first part of the paper.

The practical implementation is more terse, and the two algorithms (training and estimation) are quite cryptic, and could enjoy some polishing to ease their parsing and to understand the details.

Answer

We thank the reviewer for acknowledging the high editorial quality of the paper and pointing towards the possible improvements. We acknowledge that practical implementation, some parts of background and algorithms can be quite had to parse. For the final version of the paper we would consider other notations that could ease the practical implementation, algorithms and related parts. In addition, the extra page would allow us to make integrate the main part of the paper with Appendices in more seamless nature.

In the notation section: why do you use X to identify both the state space and the path space?

Answer

We thank the reviewer for questioning such notation choice. Our initial through was that labeling the state space X\mathcal{X} and the path space by the XN+2\mathcal{X}^{N+2} by the same X\mathcal{X}, we would ease the notation and it would contribute to easier understanding of the methodology. However, in the final version along with other notation rework we could also separate the state space and path space notation.

2. Synthetic dimensions beyond 50 and extremely high MI

Reviewer quote

I wonder why the authors stopped at D=50 in their synthetic benchmark. To my knowledge, considered the related work, this is already a quite "high dimensionality" problem for MI estimators. Why didn't you push it further to 100 or more?

Similarly, for the image data scenario, or even continuing with synthetic benchmarks, I wonder how robust would be MI estimation in cases of very high MI, given that in general (and again to the best of my knowledge) MI estimators suffer quite a bit with high MI cases.

Answer

Following the reviewer's suggestion, we have extended the synthetic benchmark (S=10S=10) to dimensions D∈{100,200,500}D \in \{100, 200, 500\}. Because the ground-truth MI grows with dimension in this setup (reaching approximately 167167, 336336, and 838838 nats), these experiments also directly evaluate the extremely high MI regime raised by the reviewer. We have added these results to Section 5.1 (Table 4) of the revised manuscript.

Specifically for this regime, we also evaluate DBMI-DoubleNN, which parameterizes rπjointr_\pi^{\rm joint} and rπindr_\pi^{\rm ind} using two separate neural networks rather than a single amortized network, following the initial formulation in Section 4 before the introduction of amortization. Because DBMI-DoubleNN doubles the number of parameters, regular single-network DBMI remains more parameter-efficient in standard regimes. We reproduce Table 4 below for convenience:

MItrue\mathrm{MI}_{\mathrm{true}}DBMI (ours)DBMI-DoubleNN (ours)InfoSEDD-JInfoSEDD-CfDIME-G
DimMean ± stdRMSEMean ± stdRMSEMean ± stdRMSEMean ± stdRMSEMean ± stdRMSE
D=100D = 100167.0292.08 ± 64.0794.34156.32 ± 0.4010.71165.27 ± 9.388.57126.19 ± 70.5575.1611.50 ± 0.46155.52
D=200D = 200335.6235.41 ± 2.60300.22314.47 ± 1.0521.18340.33 ± 66.2259.42126.20 ± 172.80260.2813.34 ± 0.88322.28
D=500D = 500838.1750.57 ± 17.06787.74776.30 ± 6.9662.17774.99 ± 272.64251.91163.13 ± 364.71749.7211.90 ± 2.10826.27
OverallrMAErRMSErMAErRMSErMAErRMSErMAErRMSErMAErRMSE
76.09%81.70%6.70%6.73%13.14%20.36%55.79%73.12%95.91%95.93%

As shown in the table, while regular single-network DBMI underestimates MI in this extreme regime, DBMI-DoubleNN achieves the lowest overall error (6.70%6.70\% rMAE and 6.73%6.73\% rRMSE), outperforming InfoSEDD-J (whose variance grows sharply with dimension) as well as InfoSEDD-C and ff-DIME-G (which severely underestimate MI). We attribute this to the fact that higher MI requires larger differences between rπjointr_\pi^{\rm joint} and rπindr_\pi^{\rm ind}, which are easier to model with two separate networks than with a single shared backbone conditioned on a binary task indicator.

We also evaluated DBMI-DoubleNN on the standard low-dimensional benchmark settings (added to Appendix C, Tables 8 and 9, and reproduced below for the DBMI variants):

Table 8 excerpt (varying DD, fixed S=10S=10):

MItrue\mathrm{MI}_{\mathrm{true}}DBMI (ours)DBMI-DoubleNN (ours)
DimMean ± stdRMSEMean ± stdRMSE
D=2D = 23.323.14 ± 0.030.173.165 ± 0.0330.15
D=5D = 58.317.93 ± 0.070.398.111 ± 0.0670.21
D=10D = 1016.3215.80 ± 0.130.5315.935 ± 0.0430.38
D=25D = 2541.4539.32 ± 0.202.1539.708 ± 0.1251.75
D=50D = 5083.6677.55 ± 1.206.2079.158 ± 0.1634.50
OverallrMAErRMSErMAErRMSE
5.10%5.33%3.78%4.00%

Table 9 excerpt (varying SS, fixed D=10D=10):

MItrue\mathrm{MI}_{\mathrm{true}}DBMI (ours)DBMI-DoubleNN (ours)
NumCatMean ± stdRMSEMean ± stdRMSE
S=2S = 23.633.67 ± 0.020.043.589 ± 0.0290.05
S=5S = 59.659.42 ± 0.040.249.611 ± 0.0290.05
S=10S = 1016.3215.80 ± 0.130.5315.935 ± 0.0430.38
S=25S = 2525.6623.50 ± 0.192.1724.142 ± 0.2261.53
S=50S = 5032.4928.53 ± 0.333.9729.957 ± 0.3472.55
OverallrMAErRMSErMAErRMSE
5.44%6.91%3.54%4.58%

In these moderate-MI regimes, DBMI-DoubleNN performs nearly similar to single-network DBMI. Thus, regular DBMI remains a strong, parameter-efficient default for standard settings, whereas DBMI-DoubleNN provides a dedicated, reliable option for extremely high MI regimes. We have updated the revised manuscript to introduce the DBMI-DoubleNN and reflect this positioning.

3. Stable f-DIME underestimation

Reviewer quote

In the appendix, I find Figure 6 very interesting. How do you explain the stability of f-DIME (even if it dramatically underestimates MI)? More imporantly, both INFO-SEDD and the proposed method seem to suffer when there only are few samples for training the models.

Answer

In Figure 6, fDIME [2] severely underestimates the mutual information across the entire range of training set sizes, so its flat curve reflects consistent saturation at a low value rather than accurate estimation (a pattern also visible at high MI in Tables 1, 2, 8, and 9). We hypothesize that this behavior is a characteristic feature of discriminator-based MI estimators in high-MI regimes. Specifically, as shown by McAllester & Stratos [1], variational and density-ratio estimators face fundamental logarithmic sample-complexity limitations when the true MI is large. Such results are applicable for discriminator based fDIME as well.

Regarding the small-sample regime, both DBMI and Info-SEDD indeed underestimate MI when trained on very few samples. However, DBMI exhibits a smooth, predictable progression in which the underestimation steadily diminishes as the training set grows. Moreover both methods still generally remain closer to the ground truth than f-DIME and approach accuracy saturation starting from 5,000 training samples. In addition, these results for both DBMI and Info-SEDD may be an artifact of the experimental hyperparameters, and we cannot rule out that another set of hyperparameters would improve performance at smaller training sample sizes.

4. Number of evaluation samples

Reviewer quote

What about the number of samples to be used to estimate MI? It is not easy to find a pattern: it looks like that using only one MC sample produces better average estimates, but costs variance obviously; however, increasing the number of MC samples seems to affect negatively the average estimate. Why?

Answer

Indeed in the original submission, the estimated MI almost grew with number of MC estimates. However, in theory the MI estimation algorithm doesn't have the bias related to the number of MC samples, they should contribute only the to the variance of estimation, but not its mean. We've reproduced the results and made sure that such an upward with number of MC samples pattern was just a result of chance.

We've conducted more through analysis with 25 independent runs instead of 5 and updated a table in the revised paper version. Here we include the comparison between the original and the revised Tables here within directly comparable settings:

MetricGTM = 1M = 2M = 4M = 8M = 16M = 32M = 64
MI mean (5 runs)6.06.08086.11936.12576.17466.14846.16446.1594
MI std (5 runs)—0.06860.04150.02800.03150.03190.01720.0087
MI mean (25 runs)6.06.15026.15896.15726.15466.15896.15746.1610
MI std (25 runs)—0.10040.06800.04160.03600.01970.01770.0111
Reviewer_DzhQOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents an algorithm for Mutual Information estimation of discrete, high dimensional vectors using reciprocal processes.

Their target is

I(X0;X1)=KL(π(x0,x1)∣∣π(x0)π(x1))I(X_0 ; X_1) = \mathrm{KL}(\pi(x0, x1) || \pi(x0) \pi(x1))

to compute this quantity they consider two reciprocal processes

rjoint=π(x0,x1)qref(xt∣x0,x1)r_{\mathrm{joint}} = \pi(x_0, x_1) q_{\mathrm{ref}}(x_t | x_0, x_1)

and

rind=π(x0)π(x1)qref(xt∣x0,x1)r_{\mathrm{ind}} = \pi(x_0) \pi(x_1) q_{\mathrm{ref}}(x_t | x_0, x_1)

Then they leverage the identity

KL(rjoint∣∣rind)=I(X0;X1)\mathrm{KL}( r_{joint} || r_{ind} ) = I(X_0 ; X_1)

While a reciprocal process is generally not markov, conditional on the starting point the authors show that it is markov. The proof of this is quite straight forward but they use this to leverage the chain rule for the KL divergence. Since

$I(X_0 ; X_1) = \mathrm{KL}(r_{joint} || r_{ind}) WhichisequaltoWhich is equal toE_{x_{0} \sim \pi} \mathrm{KL}(r_{joint | x_0} || r_{ind | x_0})$$

which is equal to the sum of local transitions. Then they construct two reciprocal processes, learn their Markov transition probabilities using neural networks, and then use the difference between those transitions to estimate mutual information.

Critical strengths

The paper is clearly written, the goal is clearly stated, and lays a very clean path from problem to execution.

Critical weaknesses

Overall, I find the paper technically sound, clearly presented, and supported by promising empirical results. However, my main reservation concerns the significance of the methodological contribution. The proposed approach appears to follow naturally from combining the mutual information formulation introduced in InfoBridge with existing categorical bridge matching techniques. While the resulting estimator performs well empirically, I am not convinced that the paper introduces sufficiently new theoretical or algorithmic insights beyond this combinatio. Additionally, the high-dimensional benchmarks primarily involve relatively simple, factorized dependence structures, which limits the extent to which the empirical results establish the broader applicability of the approach. I am therefore leaning toward weak reject, although I consider the paper borderline. I would be happy to reconsider my assessment if the authors can better clarify the technical challenges involved in extending InfoBridge to the discrete setting and articulate what distinguishes their contribution from a direct combination of these existing methods.

Questions for authors

See weaknesses.

2 comments

We thank Reviewer DzhQ for the thoughtful review and constructive feedback. We are glad that you appreciated the clarity of the paper, the well-stated goal and clean progression from problem formulation to execution, and the strong empirical performance of the resulting estimator. Below, we address each of your comments and questions in detail. We have also uploaded a revised version of the manuscript with all changes highlighted in blue.

1. InfoBridge connections clarification

Reviewer quote

my main reservation concerns the significance of the methodological contribution. The proposed approach appears to follow naturally from combining the mutual information formulation introduced in InfoBridge with existing categorical bridge matching techniques. While the resulting estimator performs well empirically, I am not convinced that the paper introduces sufficiently new theoretical or algorithmic insights beyond this combinatio.

articulate what distinguishes their contribution from a direct combination of these existing methods.

I would be happy to reconsider my assessment if the authors can better clarify the technical challenges involved in extending InfoBridge to the discrete setting and articulate what distinguishes their contribution from a direct combination of these existing methods.

Answer

We agree that the shared-bridge representation of mutual information incorporates ideas from InfoBridge [4] and builds on existing categorical bridge-matching machinery [1]. However, extending this paradigm to discrete state spaces introduces several key distinctions and technical challenges that we had to address:

First, we formulate a discrete-time KL estimator, in contrast to the continuous-time path-KL formulation in InfoBridge [4]. This requires different theoretical tools (Markov-chain decompositions of conditioned reciprocal processes rather than Girsanov's theorem), a different estimation procedure, and a different set of hyperparameters. For instance, in Appendix C.3 we study the discrete reference stochasticity parameter α\alpha and find that its behavior differs noticeably from that of the continuous stochasticity parameter ϵ\epsilon in InfoBridge.

Second, operating within Categorical Bridge Matching [1] entails a learning procedure that differs substantially from continuous-state-space bridge matching [2, 4] because it relies on fundamentally different loss functions, namely categorical KL divergence and cross-entropy rather than MSE. This changes both the optimization dynamics and the practical hyperparameter choices.

Third, to remain tractable in SDS^D state spaces, Categorical Bridge Matching relies on coordinate-factorized transitions, as is standard in discrete diffusion models [3]. This factorization requires both a coordinate-factorized neural network parameterization and a coordinate-factorized training objective. More importantly, it directly affects the mutual information estimator and must be analyzed carefully. In Section 4.3 (Proposition 3) of the revised manuscript, we provide a novel theoretical result that directly quantifies the effect of coordinate-wise transition factorization on MI estimation and establishes the exact temporal-refinement conditions under which this factorization bias vanishes at rate O((N+1)−1)O((N+1)^{-1}). This challenge is significant and does not arise in InfoBridge.

We would also like to add that, as you noted, the DBMI estimator performs well empirically, achieving leading or shared-leading performance across all originally presented benchmarks. Furthermore, while competing methods encounter distinct difficulties, such as instability for InfoSEDD-J or an inability to estimate high MI for ff-DIME, our method works reliably across all original settings while maintaining low prediction variance. Thus, we view DBMI as a stable and robust estimator with substantially fewer failure modes than existing discrete MI estimators, making it a strong practical choice for general MI estimation in discrete state spaces. We consider this reliability a significant contribution of our work.

2. Benchmarks

Reviewer quote

Additionally, the high-dimensional benchmarks primarily involve relatively simple, factorized dependence structures, which limits the extent to which the empirical results establish the broader applicability of the approach.

Answer

Thank you for raising this concern. We agree that our controlled benchmarks have limitations. Reliable comparison of MI estimators benefits from benchmarks with known ground-truth MI, which constrains how the joint distributions can be constructed. Existing benchmarking approaches typically rely on analytically tractable dependence structures or transformations that preserve MI [5, 6].

In addition, benchmarking MI estimation in discrete spaces remains relatively underexplored and in our work we have contributed DNA-tag and discrete rectangle-image benchmarks as two controlled settings that combine known MI with complex observations. We would argue that Image Benchmarks involves the relatively simple, factorized dependence structure only in the latent space, which defines the rectangle features and which than is transform by not trivial map into an image. Hence in Image the dependence is not factorized anymore and convoluted by the rectangular coordinates to image transform. While DNA tag benchmark complicates the problem by adding real marginal distributions structure to the random variable, which does not influence the MI content, but complicates the MI estimation.

In the revised manuscript’s Future Work discussion, we now note that current benchmarks, including ours, cover a limited range of dependence structures and identify developing richer discrete benchmarks with known ground-truth MI as an important research direction.


We hope that our clarifications regarding the technical challenges of discrete bridge-based MI estimation and the revised manuscript, address your reservations. Please, in the remaining time let us know if any questions remain, and we kindly ask if you would consider adjusting your score in light of these revisions.

References

[1] Ksenofontov & Korotin, Categorical Schrödinger Bridge Matching, ICML 2025.

[2] Shi et al., Diffusion Schrödinger Bridge Matching, NeurIPS 2023.

[3] Campbell et al., A Continuous Time Framework for Discrete Denoising Models, NeurIPS 2022.

[4] Kholkin et al., InfoBridge: Mutual Information Estimation via Bridge Matching, 2025.

[5] Czyż et al., Beyond Normal: On the Evaluation of Mutual Information Estimators, NeurIPS 2023.

[6] Butakov et al., Mutual Information Estimation via Normalizing Flows, NeurIPS 2024.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We sincerely thank all the reviewers for their valuable feedback and for recognizing the strengths of our work:

  • Sound and practical bridge-based formulation for discrete mutual information estimation, enabling simulation-free training and MI estimation (ibgC, XrZf)
  • Clear presentation and clean progression from problem formulation to practical execution (DzhQ, XrZf)
  • Comprehensive experimental evaluation across controlled benchmarks with known ground-truth MI, including the DNA-tag and high-dimensional image benchmarks (ibgC, XrZf)
  • Strong empirical accuracy and low variance across training seeds (ibgC, DzhQ, XrZf)

In response to the reviewers concerns and suggestions, we have made the following changes, highlighted in blue in the uploaded revised manuscript:

  • Theoretical analysis of transition factorization bias: Added Section 4.3 (Proposition 3) and its proof in Appendix A.3, establishing an O((N+1)−1)O((N+1)^{-1}) bound on the coordinate-wise factorization bias under temporal refinement with a fixed endpoint reference distribution (ibgC)
  • Separate-network parameterization and extremely high MI evaluation:
    • Introduced the two-network alternative (DBMI-DoubleNN) in Section 4.2 (XrZf, ibgC, DzhQ), alongside evaluations of DBMI-DoubleNN on the standard low-dimensional benchmarks in Appendix C, Tables 8 and 9 (XrZf).
    • Added the Extremely High Mutual Information Test in Section 5.1 (Table 4) for D∈{100,200,500}D \in \{100, 200, 500\} and S=10S=10 (ground-truth MI from 167167 to 838838 nats) (XrZf)
  • Methodological and numerical corrections:
    • Clarified the endpoint posterior expectation in Eq. (5) and Section 2.5 (ibgC)
    • Corrected the N+1N+1 time-index normalization factor in Algorithm 2 and updated the affected DBMI tables and figures in Section 5 and Appendix C accordingly (ibgC)
    • Reconciled and corrected the baseline and standard deviation entries in Appendix C, Table 9 (ibgC)
  • Expanded Monte Carlo sample ablation: Extended the evaluation of inner Monte Carlo samples MM in Appendix C, Table 10 from 5 to 25 independent repetitions (XrZf)
  • Related work and benchmark discussion: Added references on information-theoretic diffusion and MI benchmarking in Sections 3 and 5.2, and expanded Section 6 to discuss dependence-structure limitations in current ground-truth MI benchmarks (ibgC, DzhQ)
  • Editorial improvements: Fixed misprints, algorithm cross-references, citation formatting, and minor phrasing issues throughout the text (ibgC, XrZf)

We believe that these additions and clarifications have thoroughly addressed the reviewers concerns and strengthened our manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.