We greatly appreciate your positive feedback and are delighted that you consider our work to be "an excellent and well-executed effort." In response to your questions and suggestions:

1. Thank you for the great suggestion! We will make sure to include a reference to the textbook “A Course in Metric Geometry” and include appropriate discussion in the final version of the paper.
2. You are absolutely correct to imply that LID is not a perfect measure of complexity. They are related, correlated concepts as per our observations (the correlation between PNG compression and LID, as well as the images presented in the main figure and our appendix), but there is no reason to expect them to be interchangeable. We will ensure that the distinction between the two is made more explicit in the main text.

We appreciate your positive review and are pleased that you find our paper well-organized and clearly written. In response to the identified weaknesses and questions, we have addressed them as follows:

Weakness: Including time-complexity comparisons

In the general rebuttal section, we provided a time comparison between our method and other baselines, showing that our method delivers 10x faster LID estimates on grayscale 28x28 images and 100x faster on RGB 32x32 images compared to the best baseline, and most importantly, it is the only method capable of scaling up to high-resolution images in a tractable manner. Given that computational efficiency is one of the most critical practical aspects of our work, we believe the added content will further solidify our claims and provide greater clarity. We will also include these details in the final version of the paper.

Questions:

1. That is a great observation! These curves roughly indicate the rate of change in the Gaussian convolved density $\varrho(x, \delta)$. The observed "spike" in the mentioned curves is likely due to a sudden increase in the Gaussian convolution at that point, potentially caused by mixing distributions from different manifolds. For example, in Figure 6-c where the dataset is a Lollipop (a mixture of 0, 1, and 2-dimensional components), Gaussian noise added to another submanifold may cause datapoints from the 2D or 1D submanifold to mix with the isolated 0D point. A similar situation occurs in the "string within a doughnut" experiment of Figure 2-b. These artifacts are irrelevant for LID estimation with FLIPD, however, as the theory behind our LID estimates holds when we let $\delta \to -\infty$, or equivalently, $t_0 \to 0$. In these regimes, $t_0$ is small and such mixings do not occur.
2. You are correct that the orderings are not sensitive to $t_0$, but only in a certain range. Note that for extremely high $t_0$ we see that the ordering does not correspond to the data complexity anymore; this is evident in Figures 17-d, 19-d, 21-d, and 23-d. We also see that in Figure 16, when $t_0 \to 1$ the correlation between FLIPD estimates and PNG compression size significantly reduces. We would also like to refer you to our synthetic experiment "string within a doughnut" illustrated in Figure 3, and the multivariate Gaussian in Figure 8 of the appendix, where the choice of $t_0$ has a significant impact on the overall estimate.
3. The regularity conditions mentioned in line 130 are those used by Tempczyk et al. [61]. Here, the support of the data-generating distribution being a disjoint union of manifolds means that this measure can be thought of as a mixture of measures on each individual manifold. The regularity condition is that each of these measures is smooth, that is, that for every chart on the manifold, the pushforward of the corresponding measure through the chart is absolutely continuous with respect to the Lebesgue measure, and that the density of this pushforward is locally bounded away from 0. While these conditions are indeed mild, they involve charts and measure-theoretic terms, which we explicitly wanted to avoid to keep the paper as accessible as possible.

We highly appreciate your comprehensive review, and we are grateful that you recognize the significant achievements of our work despite some concerns. Before addressing your points in detail, we would like to clarify a potential misunderstanding regarding the UNet vs. MLP issue. While certain patterns observed with MLPs, like knees, may not carry over to UNets, we firmly maintain that FLIPD estimates remain useful measures of relative complexity, as evidenced by our image rankings with a UNet backbone. Most importantly, the results in Table 2 use a UNet backbone and show a high correlation with PNG compression size. Interestingly, we often observe an even greater correlation with PNG compression size when using a UNet backbone compared to MLPs, as shown in Figure 16 of the Appendix.

With that in mind, we propose FLIPD as a strong LID estimator on structured manifolds and a relevant measure of complexity for images. Once again, we thank you for bringing this up, and will ensure that the introduction and abstract are updated to more accurately reflect our contributions in the final version of the paper.

We will now provide detailed responses to the individual concerns:

Technical Issue (L211)

Thank you for the astute observation. Indeed, these terms tend to be related to curvature, and studying the effect of curvature in this setting seems an extremely appropriate future direction. However, our conjecture is not that this term does not depend on curvature nor that its derivative wrt $\delta$ is exactly $0$; rather, it’s simply that its derivative goes to $0$ as $\delta \rightarrow -\infty$. We indeed expect the speed of convergence to depend on the curvature. Additionally, we would like to emphasize that L211 is merely a conjecture, and it is based on the strong synthetic results we obtained, as detailed in Appendix D. For this we refer you to our experimental results, particularly those involving non-linear manifolds generated by normalizing flows denoted with $\mathcal{F}$. It is also worth mentioning that LIDL, our baseline, also relies on the curvature-related O(1) term being well-behaved.

Furthermore, the limit $\delta \to -\infty$ is not related to the manifold being detached. It suggests that as $\delta \to -\infty$, $\varrho(x, \delta)$ becomes increasingly local, and the dependence on the global characteristics of the manifold diminishes. Our intuition is that as $\delta \to -\infty$, $\log \varrho(x, \delta)$ becomes as local as possible and, after a certain point, the local approximation to the manifold given by its tangent space can be considered “good enough”.

Technical Issue (L309)

We would like to clarify that using knees is not necessarily the best way to obtain accurate LID estimates and is not a crucial part of our method. In fact, choosing a sufficiently small $t_0$ still produces very reasonable results (see Table 5 of the Appendix). Therefore, the absence of knees does not render the estimator useless. Moreover, we firmly believe that even without the knees, the FLIPD estimators with UNets are useful measures of complexity, as evidenced by the high correlation with PNG compression size shown in Table 2. We acknowledge that the differences between UNets and MLPs are counterintuitive and warrant further exploration in future work. Our explanation for why this issue may arise is included in Appendix E.1. We will add more context and move some of that explanation to the main text in the final version of the paper.

Technical Issue (FLIPD on high resolution images)

This is an excellent point and might indeed contribute to the more semantically meaningful orderings we observe. However, we would like to mention that the encoder/decoder of Stable Diffusion is designed not just to encode semantic information; the latent space remains image-shaped and high-dimensional. Additionally, we refer you to our results in Figures 17 through 24, where the model does not use a latent space and still aligns with semantic complexity. That said, we acknowledge that using a latent space for Stable Diffusion might lead to misinterpretation of the claims in the introduction. We will ensure that these claims are made more explicit in the final version of the paper.

Technical Comment (L190)

Your latter interpretation is correct: $\hat{\varrho}$ is simply defined using $\nu$ and the ODE in Eq. (13). It is important to note that $\hat{\varrho}$ and $\varrho$ are not the same, and $\hat{\varrho}$ is the solution to the ODE in (12) where the initial value is artificially set to zero, and thus $\varrho$ and $\hat{\varrho}$ differ by a constant. In Section 3.2, we demonstrate that the constant difference between $\hat{\varrho}$ and $\varrho$ is unimportant because, when a linear regression is employed (similar to LIDL), this constant only affects the intercept and not the slope; with the slope being the term that is important for computing LID. We will reword this section in the final version of the paper for better clarity.

Technical Comment (L284)

This is yet another excellent point! Indeed, if certain factors are not controlled, normalizing flows can distort the manifold, causing numerical changes in the LID. For example, a square stretched in one direction and squeezed in another can numerically deceive an LID estimator to consider it a line with LID=1 rather than a rectangle with LID=2. We incorporate activation normalizations and use at most 10 rational quadratic transforms in our flow-induced manifolds. This ensures the overall transformation is not ill-conditioned.

We thank you once again for your excellent review! Your insightful comments have improved our work. Finally, if you find that our explanation satisfactorily addresses your concerns, we kindly request that you consider raising the score!

Thanks for addressing my comments. I revised the language for my confusion about what carries over from MLPs to UNets. Since this was my main reservation, I have increased my score. It would have been nice to see the revised draft, but I trust the authors to reflect discussions with reviewers in the final version.

Follow up technical remarks

L211 - Regarding curvature terms, I didn't find any mention of those in the paper. It would be nice to briefly discuss that highlighting how they show up in the formulation of LIDL. And thanks for resolving the simplistic counter-argument I posed, though it was probably triggered by the comment on approaching point-mass. Speaking of the tangent space seems more helpful.

L309 - I encourage the authors to reflect on how to best smooth out the abandonment of knees upon switching to UNets. (I can see that knee analysis helped demonstrate how the MLP approach captures the true ID for the synthetic dataset, and better aligns with the theory - see also next block.) More concretely, it may help to break up the experiment section, e.g., into two subsections, in order to allow for a more proper anticipation of the added complications of image experiments. That is, those complications appear to be more than just nuance with the specific experiments and their setup, but rather stem from remaining gaps in the development.

Beyond revising the experiments section, I would also recommend tuning down the claimed contributions, as early as the abstract/introduction/summary, to be based more heavily on MLPs and the synthetic evaluations against true IDs, while suitably positioning contributions related to image datasets and the adaptations needed for them as more of an empirical contribution or an extension of the core contributions. I trust the authors to make the right call there, and to further identify and discuss the remaining gaps in the limitations section.

L787-788: FLIPD curves with MLPs, which have clearly-discernible knees as predicted by the theory

• Please clarify explicitly which parts of the theory predict those clearly-discernible knees.

L792-793: surprisingly poor FLIPD estimates of UNets

• It would help to reflect on this language in light of the authors' assertion*. It would help to tune down the more subjective language and refer to specific qualitative/quantitative empirical results. (*) From the rebuttal: we firmly believe that even without the knees, the FLIPD estimators with UNets are useful measures of complexity, as evidenced by the high correlation with PNG compression size shown in Table 2

Overall recommendation: Given the remaining gaps in analysis - theoretical (i.e. non-linear manifolds) and empirical (i.e. MLP to UNets), I strongly recommend to tune down further hypotheses and conjectures, and instead utilize the space to better present the known facts and available evidence.

Thanks for the updates. I appreciate the authors reflecting on the core claims in light of the discussion. To be clear, it is not my intention to diminish the contributions, but to present exactly what has been achieved and what's left.

TL;DR: please (1) tune down the Momentum adequately positioning the theoretical contributions separately from their practical implementations, (2) Surface and discuss Issue#1 and Issue#2 early on in the introduction, all through the experiments section. (3) Consider reducing focus on knees a little bit, and instead paying more attention to how to best use the estimates across multiple settings of the hyperparameters as commonly done in robust estimation, (4) Revisit the wording in "addresses all the aforementioned deficiencies" in the abstract, noting remaining gaps applying the estimators in the absence of knees.

Taking a step back after yet another reading, I think I can identify the main underlying gap here. Please feel free to clarify any of those points:

• The paper builds momentum based off the theoretical derivations [Momentum] culminating in the proposed estimator as encoded in Theorem 3.1 (Equation 15). This is a great theoretical result with lots of merit towards publication.
• However, applying this neat result in practice immediately hits a couple issues as recounted across a number of pages:
  • [Issue#1] L230-232: The effect of $t_0$ FLIPD requires setting $t_0$ close to 0 (since all the theory holds in the $\delta \to -\infty$ regime). It is important to note that DMs fitted to low-dimensional manifolds are known to exhibit numerically unstable scores $s(·, t_0)$ as $t_0 \to 0$.
  • [Issue#2] L319-320: As long as the DM accurately fits the data manifold, our theory should hold, regardless of the choice of backbone. Yet, we see that UNets do not produce a clear knee in the FLIPD curves
  • [Issue#2] L792-795: To explain the surprisingly poor FLIPD estimates of UNets, we hypothesize that the convolutional layers in the UNet provide some inductive biases which, while helpful to produce visually pleasing images, might also encourage the network to over-fixate on high-frequency features which are not visually perceptible.
  • (Note that those last two remarks seem to contradict each other)
• To cope with the challenges of applying the theory in practice, the authors adopted a number of accommodations
  • First, the notion of knees, which seem to be partly motivated by related work on normalizing flows
    • L269-270: As mentioned, we persistently see knees in FLIPD curves. Not only is this in line with the observations of LIDL on normalizing flows
  • From there, attention shifts heavily to knees overshadowing Issue#1].
    • I really did not appreciate conflating the observation of knees with possible implications of Theorem 3.1 (L787-788), which follows the general sense of overshooting the Momentum.
    • The multiscale interpretation was appreciated though (L249)
  • Upon transitioning to UNets, the focus is still on knees and their sudden disappearance, which further dilutes Issue#1 which is now mixed in non-trivial ways with Issue#2.
  • There's clearly more work to be done on how to best utilize the resulting estimates for various hyperparameters, whereas the experiments section mainly focuses on validating the estimates to demonstrate the theory despite the accommodations needed to make it work.

Looking at the revised summaries, I note the following elements of the abstract:

• [..] current methods based on generative models produce inaccurate estimates, require more than a single pre-trained model, are computationally intensive, or do not exploit the best available deep generative models, i.e. diffusion models (DMs)
  • In this work, we show that the Fokker-Planck equation associated with a DM can provide a LID estimator which addresses all the aforementioned deficiencies
  • I don't think the work addresses all the aforementioned deficiencies. There are still major questions regarding the accuracy of the resulting estimates in practice.
• Other changes were more favorable
  • (before) outperforms existing baselines on LID estimation benchmarks
    • (after) outperforms existing baselines on synthetic LID estimation benchmarks while staying robust to the choice of hyperparameter <<<
  • (after) Despite the resulting LID estimates being less stable over the choice of hyperparameter, FLIPD remains a valid measure of relative image complexity <<<
  • (before) FLIPD exhibits higher correlation with non-LID measures of complexity
    • (after) FLIPD exhibits a consistently higher correlation [..]
  • (before) remain tractable with high-resolution images at the scale of Stable Diffusion
    • (after) first one to be tractable at the scale of Stable Diffusion

We thank you for the positive feedback and the insightful comments. If the following responses satisfactorily address your concerns, we kindly request you consider raising your score!

Weakness 1

Thank you for bringing this concern to our attention. We have provided a clarification for Section 3.2 and how it relates to the Fokker-Planck equation, along with some additional intuition. This will be included in the final version of the paper.

The Fokker-Planck equation is a partial differential equation (PDE) that describes how the marginal probabilities of an SDE evolve over time $t$. Formally, it states that for the given SDE in Eq. (1), we have the following:

$

\frac{\partial}{\partial t} p(x, t) = - \frac{\partial}{\partial x} \left[ f(x, t) p(x, t)\right] + \frac{\partial^2}{\partial x^2} \left[ g^2(t) p(x, t) /2\right]

$

Given this, it is straightforward to derive the PDE for $\log p(x, t)$ too. While Section 3.1 explores the connections between $\varrho(x, \delta)$ and $\log p(x, t)$, Section 3.2 utilizes the PDE for the evolution of $\log p(x, t)$ to develop an ODE that describes how $\varrho(x, \delta)$ evolves as a function of $\delta$. Consequently, the entire trajectory of $\varrho(x, \delta_1)$ through $\varrho(x, \delta_m)$ can be determined using a single ODE solver.

Let us begin by explaining how Eq. (12) relates to the Fokker-Planck equation. This derivation involves two main steps: (i) rewriting the $\log \varrho(x, \delta)$ term on the LHS using the log marginal probabilities from Eq. (11), and (ii) transforming the differentiation with respect to the log-standard deviation $\delta$ into the time domain using the mapping $t(\delta)$. The following derivation formally connects the LHS of Eq. (12) to the Fokker-Planck equation:

$

\frac{\partial}{\partial \delta} \varrho(x, \delta) = \frac{\partial}{\partial \delta} D \log \gamma(\delta) + \frac{\partial}{\partial \delta} \log p(\gamma(\delta) x, t(\delta)) \quad \text{Using (11)}

$

$

= \frac{\partial}{\partial \delta} D \log \gamma(\delta) + \frac{\partial t(\delta)}{\partial \delta} \underset{\text{Rewrite using Fokker-Planck}}{\underbrace{\frac{\partial}{\partial t(\delta)} \log p(\psi(t(\delta)) x, t(\delta))}}

$

$\frac{\partial}{\partial t(\delta)} \log p(\cdot, t)$ can be rewritten in terms of $s(x, t)$ (Eq. (41) of Appendix C.2) and replacing the Fokker-Planck term above will yield $\nu$ in Eq. (12). By solving the entailed ODE, we can evaluate $\varrho(x, \delta)$ at multiple $\delta$s and use the linear regression in LIDL to estimate LID.

Furthermore, while a general solution for Eq. (12) can be obtained, it will always differ by a constant from the true $\varrho(x, \delta)$ due to the unspecified and difficult-to-determine initial value $\varrho(x, \delta_1)$. Eq. (13) introduces an initial value problem where this constant is artificially set to zero, defining its solution as $\hat{\varrho}(x, \delta)$. Notably, although $\hat{\varrho}(x, \delta)$ and $\varrho(x, \delta)$ differ by a constant, we perform a linear regression on $m$ sampled points from these functions, and this constant only affects the intercept in the regression, not the slope. LIDL focuses solely on the slope and not the intercept; thus, regression on $\hat{\varrho}$ instead of $\varrho$ yields the same result. Finally, we derive an LID estimator that directly extends LIDL, requiring only a single pre-trained diffusion model and a single ODE solve.

Weakness 2

The computational benefits are one of the main advantages of our method, and we will substantiate this further in the final version of the paper. We have included a dedicated section with time comparisons to the NB method from [58] in the general rebuttal to address this concern.

Question 1

Both [10] and [48] use the model-free, KNN-based MLE estimator. As outlined in Table 7 of Appendix D, MLE severely underestimates the true LID on synthetic data where the ground truth is known. We note that all the experiments in [10] and [48] are conducted on images, where the ground truth LID is unknown. Thus, in the image context, it is impossible to concretely say whether FLIPD overestimates LID, or MLE underestimates it. However, the fact that MLE underestimates LID in synthetic scenarios suggests that the estimated values on high-dimensional images are likely too low as well. Additionally, we point out that our estimate of average LID for MNIST closely aligns with that of [58], which is a more recent paper.

Question 2

We are not sure we entirely understand the question - please respond back with clarification so that we can better address your concerns and continue the discussion. Regardless, we would like to emphasize that the Fokker-Planck equation itself does not inherently provide better LID estimates; rather, it is a tool for efficiently extracting LID from a diffusion model trained to fit the data manifold. Our estimates are more accurate than prior methods because we use diffusion models, whereas many baseline methods are either model-free or use normalizing flows. Normalizing flows are known to struggle with data coming from low-dimensional manifolds embedded in high-dimensional space [38, A], whereas diffusion models do not exhibit these limitations [B]. In fact, we further study the NB estimator, which also uses a pretrained diffusion model, in Appendix D. We find that enhancements to the NB estimator could yield a highly accurate estimator, despite remaining intractable for high-dimensional data. This supports the notion that the high quality of our LID estimator is mainly due to the superior performance of diffusion models, rather than the Fokker-Planck equation.

References

[A] Behrmann et al. "Understanding and mitigating exploding inverses in invertible neural networks." ICML 2021.

[B] Pidstrigach. "Score-based generative models detect manifolds." NeurIPS 2022.