acceptodds
Under review as a conference paper at ICLR 2027

One Trajectory Can Be Enough with Wise Step Selection for Semantic Uncertainty Quantification in Large Language Diffusion Models

20 views

Abstract

This paper deals with the high inference cost of sampling-based semantic un- certainty quantification (UQ) for Large Language Diffusion Models (LLDMs). We ask whether multiple independent generations can be replaced by informa- tive states from a single denoising trajectory. To this end, we introduce DIMS (Distribution-Matched Step Selection), which learns which diffusion steps best reproduce the semantic variability of independent generations. We show that the single-trajectory approximation error decomposes into distribution mismatch and within-trajectory redundancy, leading to a simple convex MMD-based objective. DIMS requires only a small unlabeled calibration set and no correctness labels. Across three LLDMs, six datasets, and eight semantic UQ estimators, DIMS is best or tied for best among single-trajectory strategies in 34/40 settings. Overall, our results show that sampling itself can be optimized for efficient UQ. Code will be released upon publication.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Uncertainty Quantification, Large Language Diffusion Models

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_NMG2OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper asks whether intermediate states along a single denoising trajectory of a masked large language diffusion model (LLDM) can replace the M independent generations that sample-based semantic UQ needs. It proposes DIMS, which learns a distribution over diffusion steps by minimizing the expected squared RKHS error between the kernel mean embedding of selected intermediate answers and that of final answers; Prop. 1 decomposes this error into an MMD distribution-mismatch term and a within-trajectory redundancy term, giving a convex QP with a per-step cap, calibrated offline on a small unlabeled set (Ncal=100 prompts, R=20 trajectories by default). At test time one trajectory suffices: M=20 steps are kept (top-M or 75% coverage) and fed to any of eight semantic estimators. On three LLDMs (five variants) and six datasets, DIMS is best or tied-best single-trajectory strategy in 34/40 (estimator, model) blocks, at 66.81 s vs 3.50 s overhead per prompt against 20 i.i.d. generations (Table 1a).

Critical strengths

Clean and genuinely useful formulation: treating the sampling strategy itself as a learnable component of semantic UQ is a novel angle, and the exact decomposition (Prop. 1) plus equivalence to the M-sample target up to a constant (Cor. 1) yield a convex, label-free objective that plugs into any existing semantic estimator unchanged.

Broad and candid evaluation: 5 model variants x 6 datasets x 8 estimators, with ablations on lambda, kernel, encoder, selection rule and calibration budget (stable down to Ncal=10, R=5), transfer experiments, and overhead accounting that includes similarity-model and estimator cost (App. D.4). The paper honestly reports where one trajectory is not enough (EigenVal prefers Full; CoCoA still trails 20 i.i.d. generations by 0.021-0.044 AUROC).

Critical weaknesses

Statistical support for the headline win count is thin: many per-block margins over Full/Random are of the same order as the reported +/-1.96 SE intervals in Table E.1 (+/-0.016-0.020 per cell), and no paired test is provided; averaged over variants, top-M reaches 0.653 vs 0.643 for Full and 0.636 for Random (Table 1a). Together with the large residual gap to the 20-i.i.d. reference for six of eight estimators (0.709 avg vs 0.653/0.655 for DIMS), the "one trajectory is enough" message is really carried by CoCoA and AD.

The headline efficiency claim assumes sequential decoding: App. D.4 charges the reference as 20 sequential decodes and notes batched decoding still costs more than 6x a single trajectory, yet the abstract and intro quote ~66.8 s to 3.5 s without that caveat. The overhead figures are also slightly inconsistent across the paper (intro 66.8/3.5 s; Sec. 5.2 66.7/3.4 s; Table 1a 66.81/3.50 s; Table E.1 66.78 s).

Questions for authors

Could you add paired significance tests (or SEs of the per-block differences) for DIMS vs Full and vs Random? How many of the 34/40 wins survive?

Which overhead figure do you consider deployment-realistic — the sequential ~66.8 s or the batched (>6x single trajectory) number in App. D.4? Would you state this caveat in the abstract?

Why does EigenVal prefer Full (0.621) over top-M (0.616)? Is the redundancy term w^T C w mis-specified for eigenvalue-based scores?

All results use M=20. How sensitive are w* and the selected step sets to M, given the cap set W_M; do weights calibrated at M=20 transfer to, say, M=10?

2 comments

Dear Reviewer,

First of all, we truly thank you for the thorough and precise review. We thank you for your advice. Your questions pointed to concrete improvements, and we have addressed each one.

1. Statistical support for the win count (Q1).

We agree that the statistical support was thin. In the paper, we only gave a separate confidence interval for each method (Tables E.1 and E.2). This does not show directly whether DiMS beats a baseline on the same prompts, so we ran paired tests as you suggested.

What we did. We used a paired bootstrap over prompts (2,000 resamples). In each resample, we draw a set of test prompts and score all methods on it. We then compute the average difference in AUROC (Δ\DeltaAUROC) between DiMS and each baseline, with its 95% confidence interval (CI). A block counts as a significant win if the CI is entirely above 0.

We consider 4 cases:

  • Blocks won by DiMS (CI higher than 0): The whole CI is above 0, so we are confident DiMS is better in this block.
  • Tie (and Δ\DeltaAUROC> 0): The CI includes 0, so we cannot be sure. DiMS is slightly ahead on average, but this could be luck.
  • Tie (and Δ\DeltaAUROC < 0): The CI includes 0, but DiMS is slightly behind on average. Again, we cannot be sure.
  • Blocks lost by DiMS (CI lower than 0): The whole CI is below 0, so the baseline is clearly better in this block.
Baseline compared withvs. Randomvs. Full
Blocks won by DiMS (CI higher than 0)3022
Tie (and Δ\DeltaAUROC > 0)913
Tie (and Δ\DeltaAUROC < 0)13
Blocks lost by DiMS (CI lower than 0)02
  • vs. Random: most wins are significant (30 of 39), and DiMS is never significantly worse.
  • vs. Full: about two-thirds of the wins (22 of 35) are significant. DiMS is significantly worse in only 2 blocks. Full uses every denoising step, so it costs about 2.2–2.5× more than DiMS for the NLI-graph and semantic-entropy estimators (7.9–8.6 s vs. 3.5–3.9 s, Table E.1). Matching or beating it at less than half the cost is useful in itself.

We also computed DeLong's paired significance tests for each block, with small modifications since each block’s AUROC is an average of 6 datasets and 4 LLM judges (for robustness). DeLong’s test confirms the wins obtained with paired prompt bootstrap (29 significant wins against Random, and 22 against Full). We will include the paired significance tests and the CIs of the differences in the revised version of the paper by the end of the week.

2. Deployment-realistic overhead (Q2).

We thank the reviewer for raising this question that is critical to analyse the accuracy-speed trade-off that DiMS offers, as well as for spotting the slight inconsistencies in our figures that were the result of different reruns of the same time measurement experiment. We’ll take care of harmonizing them in a corrected version and send it by the end of the week.

In our opinion, in deployment-realistic scenarios, we may need to assess the uncertainty of a model on several different prompts. Batching these different prompts would be a natural way of optimizing inference and uncertainty computation, especially since our step selection is prompt-independent, so it requires memory writing at a simultaneous time for all prompts in the batch. For i.i.d. sampling, if the M=20 samples for a given prompt are already batched, further batching across different prompts may be limited by memory depending on the GPU.

For this reason, it seems more relevant to us to compute reference independent sampling with sequential decoding rather than batched, as it is more revealing of the deployment setup. But we will reformulate the abstract to highlight that point.

3. Why EigenVal prefers Full (Q3).

We thank the reviewer for highlighting this interesting point that deserves deeper investigation. Our current hypothesis is that the redundancy term is not mis-specified for eigenvalue-based scores, and the cause of EigenVal preferring Full is its sensitivity to the late, converged steps.

First, the redundancy term is not specific to any estimator. The estimator only influences which λ\lambda is selected. EigenVal's λ∗\lambda^*, and the resulting selected steps, are typical:

EigenValEccentricityDegMatKLE-HeatKLE-Matérn
median λ∗\lambda^*20.851.521.5
mean position of the selected steps, t/(T−1)t/(T-1)0.420.500.430.400.42

and a quick ablation on shows that the redundancy term helps EigenVal:

EigenVal with DiMS top-MAUROCvs Full (0.621)
λ\lambda=0 (no redundancy term)0.590-0.031
λ∗\lambda^* (label-free on validation split, like in the paper)0.616-0.005
Oracle: best λ\lambda on test split0.629+0.008

Second, EigenVal’s behavior is not an eigenvalue problem, but rather the consequence of its sensitivity to late steps. Eccentricity is another method that uses the eigenvectors of the same graph Laplacian and does gain from DiMS. Moreover, we notice that the Pearson correlation between AUROC differences Last - Full and DiMS(top-M) - Full is 0.87 over the 8 estimators. EigenVal has the worst Last - Full gap among the 8 uncertainty estimators (-0.058). Our current hypothesis to explain this is that EigenVal acts as a soft count of semantic clusters, but ignores how many steps fall into each cluster, thus suffering from selecting late, converged steps. We acknowledge that we only exhibit a correlation, which may not fully explain EigenVal’s behavior.

Finally, we would like to mention that the statistical support of the claim “EigenVal prefers Full” is also thin. Over the 30 EigenVal runs (5 models, 6 datasets), we have the following table using the same procedure as in our answer to Q1:

MetricAUROCAUROCPRRPRR
DiMS ruleTop-M vs FullCov75 vs FullTop-M vs FullCov75 vs Full
Blocks won by DiMS (CI higher than 0)2311
Tie (and Δ\DeltaAUROC/PRR > 0)10141217
Tie (and Δ\DeltaAUROC/PRR < 0)14121711
Blocks lost by DiMS (CI lower than 0)4101

Conclusion. The redundancy term is not mis-specified for eigenvalue-based scores. It is computed without reference to the estimator; it improves EigenVal by +0.026, and Eccentricity, which also uses the Laplacian's spectrum, gains from DiMS. EigenVal's slight preference for Full reflects its strong reliance on early-trajectory diversity (Last − Full = −0.058, the largest drop of all estimators). We will add this analysis to the appendix by the end of the week.

4. Sensitivity to M (Q4).

We agree that a sensitivity analysis on MM would be valuable to complete our work. We thank the reviewer for pointing this out and giving us the opportunity to disentangle the two roles of the parameter MM. On the one hand, at calibration time, it defines a cap 1M\tfrac{1}{M} for the simplex in the quadratic program we solve. On the other hand, at test time, through the top-MM rule, it defines how many steps we extract from the optimal vector w∗\mathbf{w}^*. We therefore study the sensitivity to MM at these two levels, as well as the transferability across values of M∈5,10,20,40M\in\\{5,10,20,40\\} used at calibration and test. We report the average AUROC obtained in the following table. Since we evaluate top-MM with MM up to 40, we exclude the TriviaQA dataset from the average, as it has only 32 steps, while the other datasets have 128.

MM at calibration (rows ↓\downarrow) — MM at test (columns →\rightarrow)5102040
50.6200.6280.6350.634
100.6200.6280.6340.633
200.6180.6290.6360.634
400.6200.6300.6340.636

It appears that Top-MM decides the results; the cap 1M\tfrac{1}{M} during calibration has very little effect on the downstream AUROC. The weights w∗\mathbf{w}^* then transfer well to any other MM at test time. We will add this sensitivity and transfer analysis to the revised version of the paper by the end of the week.

Thank you again. We believe these additions make the statistical claims more rigorous and the efficiency claims more transparent, and we would be glad to continue the discussion.

Reviewer_9Z6zOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes DiMS to reduce the computational cost of semantic uncertainty quantification in Diffusion LLMs. DiMS uses MMD to match the semantic distribution of independently generated answers while accounting for dependencies between intermediate states within a single denoising trajectory, formulating step selection as a convex optimization problem. Experiments on three Diffusion LLMs, six datasets, and eight semantic UQ estimators demonstrate that DiMS generally outperforms existing single-trajectory sampling strategies while significantly reducing online inference costs.

Critical strengths
  1. This paper leverages intermediate answers naturally produced during the denoising process of Diffusion LLMs and optimizes step selection to reduce the need for independent sampling. This provides a valuable direction for improving the efficiency of uncertainty quantification in Diffusion LLMs.

  2. DiMS does not require modifications to the underlying Diffusion LLM and is independent of specific semantic UQ estimators, allowing it to be directly integrated with various existing uncertainty estimation methods.

  3. The authors conduct comprehensive experiments across three Diffusion LLMs, six datasets, and eight semantic UQ estimators.

Critical weaknesses
  1. In Table 1, DiMS achieves an average AUROC of 0.655, compared to 0.643 for Full and 0.636 for Random, indicating relatively modest improvements. Moreover, a noticeable gap remains compared to the AUROC of 0.709 achieved by 20 independent generations.

  2. Figure 2 shows that DiMS tends to select steps concentrated in the early and late stages of the denoising trajectory. However, the paper lacks comparisons with simpler baselines, such as Uniformly Spaced Sampling and Early-Late Stratified Sampling. It is therefore unclear whether the more complex MMD-based optimization provides substantial benefits over directly exploiting these temporal patterns.

  3. The default setting requires 20 trajectories for each of 100 calibration prompts, while selecting λ\lambda additionally relies on 20 independent generations for each of 200 validation prompts. Consequently, the computational cost of offline calibration and hyperparameter selection is not negligible.

  4. The experiments mainly adopt single-block decoding with one token committed per step. The paper lacks evaluations under more efficient decoding configurations, such as committing multiple tokens per step or using block-wise diffusion.

Questions for authors
  1. Could the authors include simpler baselines, such as Uniformly Spaced Sampling and Early-Late Stratified Sampling, to further validate the advantages of MMD-based optimization over fixed step-selection strategies?

  2. How would the performance of DiMS and the distribution of selected steps change under more efficient decoding configurations, such as committing multiple tokens per step or using block-wise diffusion?

4 comments

Dear Reviewer,

First of all, we sincerely thank you for the time and effort you put into reviewing our work. We fully acknowledge the importance of your comments and your requests for additional experiments. They are extremely valuable to us because they provide an opportunity to demonstrate our method’s performance and limitations, and they suggest new, interesting directions for future work.

We hope the following detailed clarifications address your concerns and make the method, its motivation, and its empirical support clear.

1. Gain over Full/Random and the gap to 20 i.i.d. generations (W1).

We fully agree with the reviewer that the average AUROC can suggest modest improvements over baselines. Yet, the closest baseline to us is the Full variant which suffers from a higher computational overhead, as computing pairwise similarity scores between a set of 128 intermediate answers is significantly more costly than doing it with a selection of 20 intermediate answers. Against other 20-intermediate-answers subset baselines (Random, Last, Centroid), the performance gap is more pronounced, given that the performance ceiling set by reference i.i.d. sampling is at 0.709.

We also completely agree with the reviewer that the performance gap to i.i.d. is noticeable. However, the AUROC gap should be put in perspective with the computational cost gain. Our method allows us to divide the number of generations needed by 20 compared to the reference 20 independent generations. And Fig. 1 in the paper shows that as we take fewer than 20 independent generations, the performance gap closes in favor of DiMS. We summarize Fig. 1 in the following table:

Methodoverhead per prompt (s)AUROC
DiMS Top-M3.500.653
i.i.d. M = 26.680.621
i.i.d. M = 310.020.647
i.i.d. M = 516.690.670
i.i.d. M = 2066.810.709

showing that, on average, DiMS sits between M=3 and M=5 independent sampling, at much lower cost.

Finally, the gap is much smaller for CoCoA (i.i.d. : 0.763 ; DiMS Top-M : 0.732), the only estimator considered that includes a token-based signal: CommitNLL. We find that DiMS’ performance can be systematically improved by applying CoCoA’s philosophy to the other purely semantic uncertainty estimators, by multiplying them with CommitNLL. The following table details AUROC with and without CommitNLL product, as well as the gap to i.i.d. sampling. We do not include CoCoA explicitly in this table as it is already defined as AD × CommitNLL. This explains why the averages differ slightly from Tab. 1.

Estimatori.i.d. (alone)DiMS Top-M (alone)DiMS cov75 (alone)i.i.d. (× CommitNLL)DiMS Top-M (× CommitNLL)DiMS cov75 (× CommitNLL)
SE0.7000.6230.6280.7270.6800.683
DegMat0.7010.6430.6430.7220.7090.708
Ecc0.6790.6270.6280.7070.6840.685
EigenVal0.6570.6160.6200.7110.6920.694
KLE-H0.7050.6460.6440.7210.7090.707
KLE-M0.7040.6440.6450.7110.7060.707
AD0.7620.6940.6960.7630.7320.732
Average0.7010.6420.6430.7230.7020.702
Gap to i.i.d.–−0.059−0.058–−0.021−0.021

Even though independent sampling also benefits from CommitNLL, DiMS becomes even more valuable on the Pareto frontier.

2. Missing simple baselines (W2/Q1).

We thank the reviewer for suggesting interesting baselines to compare DiMS with. Following your suggestions, we define two baselines:

  • Uniformly Spaced Sampling (USS): we select MM evenly spaced positions that always include the first and last steps;
  • Early-Late Sampling (ELS-mm): we select the first M−mM-m steps plus the last mm steps, m∈0,…,M−1m\in\\{0, …, M-1\\}. With m=Mm=M, we recover Last. This baseline introduces a hyperparameter m.

In the following results, we always keep M=20M=20. We first try ELS-mm for every value of m∈0,…,19m\in\\{0, …, 19\\}, on all the models and datasets and report the average AUROC and PRR (we only report even values for m):

Late: mm stepsEarly: 20 - mm stepsAUROCPRR
0200.6310.253
2180.6360.266
4160.6380.273
6140.6400.277
8120.6410.279
10100.6400.277
1280.6400.277
1460.6390.275
1640.6370.272
1820.6340.264

Setting mm to 8 provides the best results, and performance is very stable around m=10m=10. Below is a table reporting the average AUROC and PRR for these new baselines:

RuleAUROCPRR
i.i.d. (M=20)0.7090.415
Full0.6430.278
Random0.6360.264
USS0.6400.277
ELS-80.6410.279
DiMS Top-M0.6530.299
DiMS cov750.6550.303

We will add detailed per-estimator and per-model tables in the revised paper.

3. Offline calibration and hyperparameter-selection cost (W3).

We fully agree with the reviewer that the computational cost of offline calibration and hyperparameter selection is a legitimate concern in addition to test-time performance and computational cost. We kindly point out to the reviewer that we perform ablations (Tab. 1, Tab. E.13 and Tab. E.14 in the paper) that demonstrate that performance stays stable even when reducing NcalN_{\textrm{cal}}, the number of calibration prompts, to 10 or RcalR_{\textrm{cal}}, the number of trajectories per calibration prompt, to 5.

However, we acknowledge that we did not try to go further: setting NcalN_{\textrm{cal}} to 10 and RcalR_{\textrm{cal}} to 5 at the same time; reducing NvalN_{\textrm{val}}, the size of the validation set, below 200 and RvalR_{\textrm{val}}, the number of trajectories per validation prompt, below 20. We ran additional ablations to answer these questions and report the average AUROC in the following table.

Rulereference (Ncal=100N_{\textrm{cal}}=100, Rcal=20R_{\textrm{cal}}=20, Nval=200N_{\textrm{val}}=200, Rval=20R_{\textrm{val}}=20)(Ncal=10N_{\textrm{cal}} = 10, Rcal=5R_{\textrm{cal}}=5)(Nval=50N_{\textrm{val}} = 50, Rval=20R_{\textrm{val}}= 20)(Ncal=10N_{\textrm{cal}} = 10, Rcal=5R_{\textrm{cal}} = 5, Nval=50N_{\textrm{val}} = 50)(Nval=50N_{\textrm{val}} = 50, Rval=5R_{\textrm{val}}= 5)
DiMS Top-M0.6530.6500.6500.6490.648
DiMS cov750.6550.6520.6520.6500.650

This table highlights the stability of DiMS performance under smaller calibration and validation sets, showing that we can even lower the computational cost of offline calibration and hyperparameter selection compared to what we did initially in our paper. We thank the reviewer again for pushing us to explore this direction even further.

4. More efficient decoding configurations (W4/Q2).

We agree with the reviewer that single-token-per-step decoding is not the only practical setting, and that exploring more efficient decoding configurations would contribute to assessing the practicality of DiMS. Therefore, we ran experiments on two-tokens-per-step and four-tokens-per-step decodings. We keep the same generation length as in our previous experiments. We exclude the TriviaQA dataset from this new experiment, as its generation length is 32 tokens, so fewer than 20 steps to work with, making all baselines and DiMS collapse into a single one. The other datasets have a 128-token generation length, so 64 and 32 steps in two-tokens-per-step and four-tokens-per-step decodings, respectively.

We report the average AUROC and PRR achieved by DiMS and other competitors in the following table, and will add detailed per-estimator and per-model tables (similar to Tab. 1) in the revised paper. For easier comparison, we report the single-token-per-step results for the same experimental scope (TriviaQA excluded).

Method1 token per step2 tokens per step4 tokens per step
Mean accuracy0.5550.5340.478
MetricsAUROCPRRAUROCPRRAUROCPRR
i.i.d. sampling0.6880.3720.6890.3770.6870.387
Full0.6250.2420.6200.2430.6140.237
Random0.6180.2250.6160.2340.6110.232
Last0.6020.2170.6010.2130.6030.219
Centroid0.6150.2270.6140.2300.6100.230
USS0.6230.2400.6180.2360.6130.234
ELS-80.6220.2390.6240.2510.6150.236
DiMS Top-M0.6360.2640.6260.2540.6190.246
DiMS cov750.6380.2680.6270.2570.6200.248

DiMS still beats the single-trajectory baselines. We are currently running similar experiments with block-wise diffusion. We cannot include them at the moment, as they are expensive to run, but we will provide them by the end of the week.

Thank you again. We believe these additions address the main concerns, and we would welcome further discussion.

Dear Reviewer,

Please find in this comment additional results to complete our answer to your question about more efficient decoding configurations.

We re-ran LLaDA-1.5 and Dream with LLaDA's semi-autoregressive block-wise decoding (the 128-token answer is split into 4 blocks of 32 tokens, decoded left to right, one token per step, T=128). We exclude the TriviaQA dataset as it would only use one block. The table compares it with standard single-block decoding on the same 20 (model, dataset, remasking) runs, giving test AUROC and PRR averaged over the eight UQ estimators.

StrategySingle block AUROCSingle block PRRBlock-wise AUROCBlock-wise PRR
Greedy-answer accuracy0.5520.644
i.i.d. (M=20)0.7040.4090.6950.363
Full0.6400.2750.6170.203
Random0.6310.2560.6020.178
Last0.6080.2340.5740.150
Centroid0.6300.2610.6080.191
USS0.6370.2700.6140.202
ELS-100.6320.2620.6090.191
DiMS top-M0.6480.2900.6180.211
DiMS cov. 75%0.6510.2970.6180.210

Thank you again.

Dear Authors,

Apologies for my late response, and thank you for your detailed responses and additional experiments.

The new baseline comparisons, calibration ablations, and experiments under different decoding configurations have addressed most of my concerns. Although the improvements under block-wise decoding remain limited, I believe the additional results have strengthened the paper.

I am therefore willing to raise my rating from 2 to 3.

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

in this work, the authors propose an efficient way to estimate the uncertainty in the answer distribution given a prompt from a diffusion based language model (though, i suspect it can apply to any type of a diffusion based generative model.) the idea is to avoid repeatedly drawing samples from the answer distribution (which would be the most exact approach, as it is really nothing but Monte Carlo) but instead checking how much changes we see over a single trajectory of sampling. in other words , the authors claim (and empirically verify) that it is possible to closely approximate the target uncertainty metric (E_{y|x}[U_sem(y)]) with E_{t|x} [U_sem(y_t)] given a single y_1, …, y_T | x trajectory.)

this is a nice idea, and i like the motivation. unfortunately it is taking me more time and effort than (i think) is needed to understand their mathematical derivations of the objective function and calibration (it is just a presentation style issue, and probably a subjective opinion.) with a moderate number of calibration samples (100), their approach, called DiMS, works better than other trivial baselines (e.g. randomly select a subset of temperatures.) though, it is unclear whether the AUC (for detecting the correctness) is close enough to the reference approach (that uses many independent samples).

it is interesting to see Fig 2, which demonstrates that the proposed approach essentially relies on the stability of the sampling trajectory (in terms of how much changes were introduced during the sampling steps) as a proxy to the uncertainty. i think this is a nice observation, and this probably even tells us potentially other ways to approximate the reference uncertainty even better (perhaps we can think of “length” of a trajectory w.r.t. some reference trajectory length ?)

i’m not too familiar with recent advances in diffusion-based LM nor semantic uncertainty estimation, but i think this paper adds a nice contribution on top of our existing understanding.

Critical strengths

see my summary above.

Critical weaknesses

see my summary above.

Questions for authors

see my summary above.

3 comments

Dear Reviewer,

Thank you for your careful and encouraging review. We're glad you found the motivation compelling and the trajectory-stability observation in Fig. 2 interesting. We address your points below.

1. Gap to the multi-sample reference

This is a fair point, and we explicitly acknowledge this in our paper. The gap in terms of AUROC is clear but also expected, as independent sampling is the ideal regime. However, the AUROC gap should be put in perspective with the computational cost gain. Our method allows us to divide the number of generations needed by 20 compared to the reference 20 independent generations. To make this trade-off explicit, we provide Fig. 1 in the paper, which shows that as we take fewer than 20 independent generations, closes and then reverses in favor of DiMS. We summarize Fig. 1 in the following table:

MethodOverhead per prompt (s)AUROC
DiMS Top-M3.500.653
i.i.d. M=26.680.621
i.i.d. M=310.020.647
i.i.d. M=516.690.670
i.i.d. M=2066.810.709

showing that, on average, DiMS sits between M=3 and M=5 independent sampling, at much lower cost.

Finally, the gap is much lower for CoCoA (i.i.d.: 0.763; DiMS (Top-M): 0.732), the only estimator considered that includes a token-based signal: CommitNLL. We find that DiMS' performance can be systematically improved by applying CoCoA's philosophy to the other purely semantic uncertainty estimators, by multiplying them with CommitNLL. The following table details AUROC with and without CommitNLL product, as well as the gap to i.i.d. sampling. We do not include CoCoA explicitly in this table as it is already defined as AD × CommitNLL. This explains why the averages differ slightly from Tab. 1.

Estimatori.i.d. (alone)DiMS Top-M (alone)DiMS cov75 (alone)i.i.d. (× CommitNLL)DiMS Top-M (× CommitNLL)DiMS cov75 (× CommitNLL)
SE0.7000.6230.6280.7270.6800.683
DegMat0.7010.6430.6430.7220.7090.708
Ecc0.6790.6270.6280.7070.6840.685
EigenVal0.6570.6160.6200.7110.6920.694
KLE-H0.7050.6460.6440.7210.7090.707
KLE-M0.7040.6440.6450.7110.7060.707
AD0.7620.6940.6960.7630.7320.732
Average0.7010.6420.6430.7230.7020.702
Gap to i.i.d.–−0.059−0.058–−0.021−0.021

"Alone" columns: published results; "× CommitNLL" columns: new results with product by CommitNLL.

Even though independent sampling also benefits from CommitNLL, the gap closes and DiMS becomes even more valuable on the Pareto frontier.

2. Clarity of the derivations (objective and calibration)

We appreciate this feedback. We agree that the derivation can be made easier to follow, and we will revise the paper accordingly by the end of the week.

3. Trajectory "length" as an alternative signal

We completely agree with the reviewer that Fig. 2 of the paper, and more generally the profile of the optimal step weights w∗\mathbf{w}^* deserves deeper investigation toward a better understanding of the diffusion trajectory geometry.

RKHS path length. We tested the reviewer's suggestion directly: the RKHS path length L=∑t=1Td(yt,yt+1)L=\sum_{t=1}^Td(\mathbf{y}_t,\mathbf{y}_{t+1}), with d(yt,yt+1)=∥∣ϕ(yt)−ϕ(yt+1)∥∣Hk2d(\mathbf{y}_t,\mathbf{y}_{t+1})=\||\phi(\mathbf{y}_t)-\phi(\mathbf{y}_{t+1})\||^2_{\mathcal{H}_k}, as a standalone uncertainty score on the scored trajectory. We tried three sentence embedders E5-large-v2, all-MiniLM-L6-v2 and BGE-M3 with RBF kernel and under hard and soft NLI microsoft/deberta-v2-xlarge-mnli (note that NLI is not a RKHS distance, but we try it in place of d). It is a weak uncertainty signal. The embedder makes no difference (test AUROC 0.54–0.55), and NLI helps (0.61). The best variant, soft NLI on the last 20 steps, reaches 0.62, against 0.73 for DiMS + CoCoA. Our hypothesis is that raw path length is dominated by the early, noisy steps, where every trajectory moves a lot while masks are filled, whatever the model's uncertainty. It measures how much the trajectory moves, not where it moves relative to the answer distribution. We acknowledge that we only tried a simple implementation of the reviewer's intuition, and that future work could investigate this direction further.

Trajectory "size". Building on the reviewer's intuition, we could also define the "length" or "size" of a trajectory as the number of independent samples this trajectory is worth. This definition is very loose, but we try to define a more rigorous object to study, using Corollary 1 from the paper:

Let y(1),…,y(M)∼i.i.d.pθDiff(⋅∣x)\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(M)} \overset{\text{i.i.d.}}{\sim} p^{\mathrm{Diff}}_{\theta}(\cdot\mid x) be independent of Y, and μ^iid=1M∑mϕ(y(m))\hat{\mu}_{\mathrm{iid}}=\tfrac{1}{M}\sum_{m}\phi(\mathbf{y}^{(m)}) . Then, for every w(T),

E∥∣μ^w(Y~)−μ^iid∥∣Hk2=Ex(w)+1−cxM.\mathbb{E}\big\||\hat{\mu}_{\mathbf{w}}(\tilde{Y})-\hat{\mu}_{\mathrm{iid}}\big\||_{\mathcal{H}_k}^{2}=\mathcal{E}_{\mathbf{x}}(\mathbf{w})+\frac{1-c_{\mathbf{x}}}{M}.

If for a given MM, the expected RKHS distance (left-hand side of the previous equation) is zero, it means that DiMS with weights w\mathbf{w} is equivalent, in the RKHS, to MM independent sampling. Then, zeroing this left-hand side provides an equation for MM, interpreted as the number of independent samples DiMS is equivalent to. Recall the QP objective Ex(w)\mathcal{E}_\mathbf{x}(\mathbf{w}) is defined as Ex(w)=∥∣μw−μref∥∣Hk2+w⊤Cw\mathcal{E}_\mathbf{x}(\mathbf{w})=\||\mu_\mathbf{w}-\mu_{\mathrm{ref}}\||^2_{\mathcal{H}_k}+\mathbf{w}^\top C \mathbf{w}. We then identify two trajectory "sizes" given a step weighting w\mathbf{w}:

Mvar=1−cxw⊤Cw,,Mtot=1−cxEx(w).M_{\textrm{var}}=\frac{1-c_{\mathbf{x}}}{\mathbf{w}^{\top}C\mathbf{w}}\\, , \qquad M_{\mathrm{tot}}=\frac{1-c_{\mathbf{x}}}{\mathcal{E}_x(\mathbf{w})}.

MvarM_{\textrm{var}} only accounts for the redundancy between steps (assuming the distributions match), while MtotM_{\textrm{tot}} accounts for the total error: redundancy and distributions mismatch. We also add a simpler geometric number that is trajectory-independent, and only a function of the vector w\mathbf{w}: Mgeo=1/∣w∣22M_{\mathrm{geo}}=1/\\|\mathbf{w}\\|_2^2 (Hill numbers of order 2) that can be interpreted as the number of steps the weights are spread over. We report what these numbers give on the test sets, on average:

ScopeMgeoM_{\textrm{geo}}MvarM_{\textrm{var}}MtotM_{\textrm{tot}} (all models)MtotM_{\textrm{tot}} (lc)MtotM_{\textrm{tot}} (rd)
Last201.91.291.401.13
Full1126.71.471.022.13
Random203.31.390.962.02
DiMS Top-20204.01.811.292.59
DiMS continuous w∗\mathbf{w}^*575.81.861.252.78

For the deployed scopes (first 4 rows), w\mathbf{w} is uniform over the selected steps.

Please see the next comment for discussion and limitations.

Discussion of trajectory "size":

  • MtotM_{\textrm{tot}} ranks the methods in the same order as AUROC. It helps explain which step selection works.
  • MtotM_{\textrm{tot}} and MvarM_{\textrm{var}} are useful to understand where each method loses performance. Full has the highest value of MvarM_{\textrm{var}}, meaning it is able to capture more variability than other methods, even when accounting for redundancy. However, the gap between MvarM_{\textrm{var}} and MtotM_{\textrm{tot}} indicates that it struggles to match the distributions.
  • The remasking schedules matter a lot for the "size" of the trajectory, as rd probably exposes more variability than lc.
  • It is interesting to look at the last row (DiMS continuous w∗\mathbf{w}^*) to see what is lost when keeping only the top-20 steps. Moreover, MvarM_{\textrm{var}} increases with and MtotM_{\textrm{tot}} is maximal at =1 (not shown in the table), as predicted by our objective design.

Limitations of trajectory "size":

  • MtotM_{\textrm{tot}} is based on kernel mean embeddings, and does not fully determine the downstream AUROC. These numbers should serve as complementary analysis rather than pure performance indicators.
  • Interpreting MtotM_{\textrm{tot}} as the equivalent number of independent samples needs to be tempered. For DiMS, while MtotM_{\textrm{tot}} is below 2, the table given in the answer to the previous point shows that DiMS' AUROC sits between 3 and 5 independent samples.

Thank you again. We believe these additions address the main concerns, and we would welcome further discussion.

Comments on the paper

2 comments

Dear Reviewers and Area Chair,

Thank you for serving as the Area Chair and reviewer for our submission.  We thank you and the reviewers for the detailed comments and suggestions.  For our revised manuscript, we make the following significant changes:

  • Paired significance of the per-block differences (E.2)
  • Additional discussion on the gap to multi-sample reference (E.3)
  • Comparison with other fixed step selection baselines (E.4)
  • Investigation on why EigenVal prefer Full (E.5)
  • Additional ablations on the offline calibration and hyperparameter selection costs (E.8.7) and on the step budget MM (E.8.8)
  • Additional experiments on more efficient decoding configurations (E.10)
  • Discussion on the deployment-realistic overhead for multiple samples methods (Abstract and D.4)

All the changes in the revision are highlighted in red.

We would be delighted if we could discuss any remaining concerns or points that the reviewers would like us to improve before the rebuttal period ends, if there are still areas that need improvement.

Best regards,

The corresponding Authors

Dear Area Chair and Reviewers,

As the Author-Reviewer discussion ends on November 18 (AoE), we would like to kindly remind that we would greatly appreciate the opportunity to discuss our work with all of you.

If any reviewer has specific questions, requests for clarification, or points they would like us to elaborate on, we would be very happy to provide additional explanations.

Thank you again for your time and consideration.

Best regards,

The corresponding Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.