PaperlayerView exact revision on arXiv

Source-linked AI summary

Free Lunch for Pass@$k$? Low Cost Diverse Sampling for Diffusion Language Models

Sean Lamont, Christian Walder, Paul Montague, Amir Dezfouli, Michael Norrish

arXiv:2603.04893v1cs.CLcs.AI

TL;DR

Pass@k reasoning tasks need diverse candidates, but independent sampling in diffusion language models can repeatedly produce similar failure modes. The paper introduces ODD, a training-free inference method that sequentially repels samples in feature space, and reports improved diversity and Pass@k performance across HumanEval and GSM8K. The approach is intended as a low-cost way to make additional sampling contribute more effectively to solution exploration.

  • Problem

    Redundant, correlated samples limit solution-space exploration and waste computation in Pass@k tasks such as coding and mathematics.

  • Method

    ODD sequentially applies a lightweight repulsion loss to intermediate diffusion logits, pushing each sample away from the subspace of previous samples.

  • Results

    ODD produces significant and consistent improvements across HumanEval and a GSM8K subset over varied temperature settings.

  • Takeaways & Limitations

    The inference-time intervention converts larger diffusion sampling batches into more diverse solution exploration with minimal computational overhead.

  • Takeaways & Limitations

    The method’s efficiency and effectiveness may depend on feature-extractor choices, while richer positional or partial-sequence features could increase overhead.

Abstract

from arXiv · show

Diverse outputs in text generation are necessary for effective exploration in complex reasoning tasks, such as code generation and mathematical problem solving. Such Pass@$k$ problems benefit from distinct candidates covering the solution space. However, traditional sampling approaches often waste computational resources on repetitive failure modes. While Diffusion Language Models have emerged as a competitive alternative to the prevailing Autoregressive paradigm, they remain susceptible to this redundancy, with independent samples frequently collapsing into similar modes. To address this, we propose a training free, low cost intervention to enhance generative diversity in Diffusion Language Models. Our approach modifies intermediate samples in a batch sequentially, where each sample is repelled from the feature space of previous samples, actively penalising redundancy. Unlike prior methods that require retraining or beam search, our strategy incurs negligible computational overhead, while ensuring that each sample contributes a unique perspective to the batch. We evaluate our method on the HumanEval and GSM8K benchmarks using the LLaDA-8B-Instruct model. Our results demonstrate significantly improved diversity and Pass@$k$ performance across various temperature settings. As a simple modification to the sampling process, our method offers an immediate, low-cost improvement for current and future Diffusion Language Models in tasks that benefit from diverse solution search. We make our code available at https://github.com/sean-lamont/odd.

1 Introduction

Diffusion language models face redundant sampling that limits Pass@k exploration, motivating ODD, a training-free inference intervention that promotes diverse outputs with minimal overhead. The paper reports consistent improvements across HumanEval and GSM8K and releases the implementation for further evaluation.

  • Motivation: Redundant samples can waste computation and reduce Pass@k effectiveness by repeatedly exploring correlated or incorrect solution modes.This challenge affects coding, mathematics, and sparse-reward settings where discovering a rare correct trajectory matters.
  • Motivation: Inference-time diversity remains complementary to diversity introduced during reinforcement-learning post-training.Prior inference-time diversity work largely targets autoregressive models and can require separate value models or costly beam management.
  • Method: ODD sequentially repels each diffusion sample’s intermediate logits from the subspace spanned by previously generated samples.The method uses a lightweight feature representation and a batch-aware diversity loss during inference rather than retraining.
  • Method: ODD provides a training-free framework for improving diffusion-language-model diversity with minimal time and space overhead.Its diversity loss maximizes the component of the current sample orthogonal to previous samples.
  • Results and resources: Experiments on HumanEval and a GSM8K subset show significant, consistent improvements across varied temperature settings.The paper evaluates the approach alongside prior diffusion diversity methods and standard sampling, while the released code supports further experimentation.

2 Methodology

ODD modifies diffusion sampling at inference time by repelling each sample from the feature-space subspace formed by earlier samples. It uses lightweight features, quality awareness, and timestep-annealed intervention to promote diversity while limiting unnecessary disruption.

  • Diffusion Language Models: DLMs generate sequences through iterative global refinement, enabling inference-time interventions over the remaining sequence.The forward process masks tokens according to a time-dependent schedule, while the reverse process progressively denoises them.
  • Inference-Time Diversity Sampling: ODD applies a differentiable diversity loss to each sample’s logits relative to feature vectors from previous batch samples.The framework computes vi = F(xi) and v<i from earlier samples, then updates the current logits to optimize diversity.
  • Inference-Time Diversity Sampling: The intervention strength α is annealed across diffusion timesteps, emphasizing diversity during early structural formation and reducing intervention during later detail refinement.This schedule is intended to provide higher diversity early while preventing excessive intervention at later steps.
  • Feature Extraction and Quality Scoring: ODD uses a lightweight output-distribution feature extractor that combines masked-token probabilities with committed-token indicators and max-pools across sequence positions.The resulting vector represents a global vocabulary-level confidence profile incorporating both established history and intended future trajectory.
  • Feature Extraction and Quality Scoring: A quality score based on average maximum confidence for unmasked tokens scales diversity pressure to discourage excessive diversity in confident regions.The quality-aware weighting is designed to preserve generation quality while encouraging exploration.
  • Orthogonal Diverse Diffusion: ODD maintains an orthogonal basis of previous feature vectors and pushes current logits toward the null space of that history using lightweight gradient updates.The Gram-Schmidt basis and stop-gradient treatment make the established subspace a fixed target while tracking gradients only with respect to logits.

3 Experiments

The experiments compare standard LLaDA, a global DPP-based diversity objective, and ODD across temperature and step-size settings. ODD improves Pass@k with minimal latency, while its greedy detached-subspace objective outperforms joint diversity optimization.

  • Experimental Setup: The evaluation compares standard LLaDA, a DPP-based global diversity objective, and ODD across temperature and α settings using empirical Pass@16.Experiments use LLaDA-8B-Instruct with 32 diffusion steps, generative length 64, batch size 16, and eight runs per configuration.
  • Results: ODD consistently improves performance across both benchmark tasks, with especially large gains at θ = 0.0 and notable HumanEval gains at θ = 2.On HumanEval, excessive token-level diversity at θ = 2 reduces baseline performance, while ODD balances diversity and quality without tuning.
  • Results: ODD is less temperature-sensitive than baseline, providing improvements with minimal tuning.For GSM8K, increasing α consistently improves performance; for HumanEval, large α values eventually decrease performance.
  • Results: The greedy stop-gradient objective improves Pass@k over DiverseFlow’s globally optimized DPP objective.Joint optimization may repel high-probability samples from the optimal mode, whereas ODD projects onto a detached subspace of previous samples.
  • Results: ODD introduces a batch-aware quality–exploration tradeoff, potentially reducing individual Pass@1 while improving the usefulness of larger batches.Standard independent sampling can repeatedly target likely modes, wasting computation on redundant attempts.
  • Efficiency: ODD adds only a small wall-time overhead because it modifies logits after model computation using lightweight operations.The overhead is independent of base-model size and should become relatively smaller as models grow.

4 Conclusion and Future Work

ODD is presented as a training-free inference intervention that improves diversity and Pass@k in diffusion language models at negligible computational cost. The authors connect this capability to global diffusion intervention and identify feature extraction as an important direction for future work.

  • Conclusion: ODD sequentially projects intermediate logits away from previous samples, reducing redundancy and improving diversity and Pass@k on HumanEval and GSM8K.The intervention is described as enabling more effective exploration where valid solutions are sparse.
  • Conclusion: Diffusion models’ global intervention capability supports low-cost improvements to sample efficiency during inference-time scaling.The paper frames this as a consequence of global sequence optimization rather than independent autoregressive decoding.
  • Future Work: Future work should evaluate alternative feature extractors, including positional or partial-sequence information, while managing possible overhead.Dimensionality reduction is also proposed as a way to reduce overhead.

A Cumulative Results

Cumulative coverage shows that ODD expands HumanEval’s reachable solved-problem set, while GSM8K baseline sampling nearly saturates coverage. On GSM8K, ODD instead emphasizes structured exploration and practical sample efficiency.

  • HumanEval: ODD (α = 16) solves 129 HumanEval problems (78.7%) versus 110 (67.1%) for baseline, a 17.3% relative improvement.Coverage is computed as the union of successfully solved problems across 640 samples per problem.
  • HumanEval: For HumanEval, ODD continues discovering rare valid reasoning paths even with suboptimal α values where Pass@16 declines.The result is reported after combining five temperature settings and eight runs per benchmark.
  • GSM8K: Baseline sampling covers 198 of 200 GSM8K problems (99.0%), while ODD covers 192–197 problems but streamlines the search.ODD’s structured exploration improves practical sample efficiency despite slightly lower absolute cumulative coverage.

B Diversity Dynamics

ODD changes batch diversity according to temperature: it increases diversity when baseline sampling collapses into similar outputs and reduces diversity when high-temperature sampling becomes incoherent. This behavior is presented as an adaptive balance between exploration and quality.

  • Low Temperature: At θ ≤ 1.0, ODD reduces embedding similarity and forces more diverse paths when baseline sampling exhibits mode collapse.Diversity is measured using average cosine similarity between sentence embeddings.
  • High Temperature: At θ ≥ 1.5, ODD reduces diversity relative to baseline, acting as a quality-weighted filter for noisy, incoherent outputs.The caption links this regime to improved Pass@16 and describes ODD as guiding generations toward coherence.
  • Interpretation: ODD adaptively promotes diversity when needed and coherence when baseline diversity is already sufficient.The reported behavior represents a temperature-dependent tradeoff between exploration and quality.

C Pareto Efficiency and Trade-offs

ODD improves batch coverage through a quality–diversity trade-off that differs by task. HumanEval gains coverage without degrading individual quality at moderate repulsion, whereas GSM8K sacrifices some Pass@1 for higher Pass@16.

  • Frontier interpretation: Figure 4 compares average individual correctness, Pass@1, with batch coverage, Pass@16.The frontiers show how ODD changes this quality–coverage balance relative to baseline sampling.
  • HumanEval: HumanEval achieves significantly higher Pass@16 without degrading Pass@1 for moderate repulsion α ≤16.This constitutes a Pareto improvement over standard sampling.
  • GSM8K: GSM8K shifts upward and leftward, trading lower Pass@1 for higher Pass@16.The shift reflects greater batch coverage at the cost of individual sample accuracy.

D Empirical Pass@k

ODD maintains stronger empirical Pass@k scaling than independent baseline sampling on GSM8K and HumanEval. Its batch-size invariance means the observed k ≤16 behavior forms the prefix of larger-batch curves.

  • Cross-benchmark results: ODD shows consistent Pass@k improvement over baseline on GSM8K and HumanEval.Figure 5 reports the empirical probability of finding at least one correct solution among the first k of 16 samples.
  • Baseline behavior: Baseline curves plateau early as independent samples repeatedly enter identical failure modes.Independent sampling therefore exhibits severe diminishing returns as k increases.
  • ODD scaling: ODD retains a significantly steeper trajectory as k increases by penalising redundancy and encouraging novel reasoning paths or syntactic structures.The method is designed so later samples contribute additional exploration rather than repeating earlier failures.
  • Scaling beyond 16: For any larger batch K >16, ODD’s curve for k ≤16 matches the displayed prefix because of batch-size invariance.This property suggests continued expansion of the explored solution space as compute budgets increase.

E DiverseFlow Baseline

The DiverseFlow baseline adapts a global batch-diversity objective from image diffusion to text diffusion. It constructs a quality-weighted feature-similarity kernel and updates all logits simultaneously through full backpropagation.

  • Optimisation procedure: Algorithm 2 updates the entire logit batch simultaneously via full backpropagation.Its inputs include model logits, step size α, diffusion timestep t, a feature extractor F, and numerical jitter ϵ.
  • Baseline setup: DiverseFlow is evaluated as a global optimisation baseline originally proposed for continuous image diffusion.The paper adapts this strategy to text diffusion for comparison with ODD.
  • DPP objective: The baseline builds an L-ensemble Gram matrix by element-wise multiplying feature similarity K = V V^T with the quality outer product Qmat.Quality scores weight pairwise feature similarities in the DPP kernel.
  • Computational context: ODD incurs less than a 10% relative time penalty, contrasting with the overhead profile shown for standard sampling in the computational analysis.The figure also reports scaling across batch size, sequence length, and diffusion steps.

F Computational Overhead

ODD adds limited generation overhead while its memory and time costs scale predictably with generation dimensions. Memory overhead grows quadratically with batch size, while sequence length increases both time and memory linearly.

  • Evaluation scope: The overhead evaluation profiles latency and VRAM across batch size B, sequence length S, and diffusion steps T using LLaDA-8B-Instruct.Measurements cover standard BF16 and 4-bit quantised precision across HumanEval and a 200-problem GSM8K subset.
  • Batch scaling: ODD’s VRAM penalty remains negligible at 5–15%, while time overhead remains flat as batch size increases.The quadratic batch-size memory scaling results from sequentially tracking batch history.
  • Sequence scaling: Increasing generated sequence length S causes linear increases in both time and memory overhead.This follows from maintaining and backpropagating through the B × S × V feature-extraction graph.
Loading 2603.04893v1…