DiG-Plan: Mitigating Early Commitment for Tool-Graph Planning via Diffusion Guidance

1 Introduction

Tool-augmented large language models (LLMs) have evolved from solving simple queries to addressing complex, multistep problems that require composing explicit executable plans [Yao et al., 2023b; Qin et al., 2024]. Unlike singletool invocation, real-world planning involves selecting an appropriate subset of tools from large libraries and determining their execution order [Shen et al., 2024]. This problem is fundamentally combinatorial: with a library of N tools, the subset-hypothesis space contains 2N possible tool sets. We do not assume exhaustive enumeration; the challenge is effective search in this large discrete space as libraries scale [Shen et al., 2024; Li et al., 2023; Liu et al., 2024].

∗Corresponding author. This work was supported by the National Key R&D Program of China (No. 2024YFC3306500), the National Natural Science Foundation of China (62406188), and the Shanghai Municipal Special Program for Basic Research on General AI Foundation Models (2025SHZDZX025G08).

Despite the combinatorial nature of this task, predominant approaches treat tool planning as a sequential text generation problem, relying on standard autoregressive (AR) decoding [Yao et al., 2023b; Yao et al., 2023a]. While AR models have proven highly effective for text generation, we identify a critical misalignment when applied to combinatorial search: early commitment. Because AR generation proceeds strictly left-to-right, early token choices establish a prefix that constrains all subsequent decisions. Once the model commits to an initial tool selection, the probability distribution over remaining tools becomes conditioned on this prefix, limiting the model's ability to explore alternative tool combinations even under stochastic sampling.

This prefix constraint creates a form of path dependency in the search process. Early choices determine the trajectory through the search space, effectively pruning large regions of the combinatorial space before they can be explored. For instance, we observe cases where AR models initially select generic vision tools for document-understanding tasks, failing to discover plans requiring more specialized document or visual question-answering tools even across multiple samples with varied sampling strategies.

Crucially, we find that this limitation is resistant to simply increasing sampling diversity. Even with extensive stochastic sampling, AR models fail to recover the missed plans, indicating that the constraint is intrinsic to the sequential decoding mechanism itself rather than a lack of randomness.

We designed a synthetic tool-selection task to strictly disentangle the decoding mechanism from other variables, such as model architecture and pretraining data. By fixing the output length and matching model capacity, we find that under identical compute budgets, masked denoising raises Pass@10 solution coverage from 0.320 to 0.943 compared with AR sampling. This provides empirical evidence that the limitation is intrinsic to the sequential decoding strategy itself.

Motivated by this insight, we propose DiG-Plan (Diffusion-Guided Planning), a framework that addresses early commitment by decoupling combinatorial exploration from structural refinement. DiG-Plan operates in three stages: first, a diffusion-based proposer generates diverse tool sets via iterative refinement, leveraging global context to revise early decisions; second, a shared autoregressive refiner predicts dependency structures conditioned on each proposed tool set, eliminating the combinatorial search problem in joint generation; finally, an inference-time judge-free value function selects the best candidate using only deployable features, without calling an external LLM judge.

On TaskBench, DiG-Plan improves over AR baselines by a 10% relative margin, with the largest gains on complex compositional tasks; API-Bank results show that the proposerefine-select design remains effective across domains. Diagnostic analyses show that diffusion proposers improve bestof-K quality from 0.735 to 0.787 and union precision from 0.575 to 0.692 compared with AR proposers under matched compute budgets. Importantly, systematic sweeps over AR sampling parameters confirm that this advantage cannot be replicated by simply increasing sampling randomness, validating that the benefit stems from the iterative refinement mechanism rather than increased stochasticity.

Our main contributions are as follows:

• We identify early commitment in autoregressive tool planning as a key barrier to combinatorial tool-set exploration, and validate this effect with a controlled fixedlength study showing that masked denoising covers substantially more valid tool-set hypotheses under matched compute.
• We introduce DiG-Plan, a propose-refine-select framework that separates tool-set exploration from dependency refinement: diffusion proposal searches over candidate tool subsets, autoregressive refinement predicts edges conditioned on each subset, and an inferencetime judge-free value function selects among candidate graphs using deployable features.
• Through experiments on TaskBench, we show that DiGPlan improves tool-set prediction over AR baselines by 10%, while API-Bank results indicate cross-domain applicability. Candidate-pool diagnostics, AR sampling sweeps, and AR-beam comparisons confirm that the gains come from stronger proposal quality rather than simply increased stochasticity.

2 RelatedWork

2.1 Tool-Augmented LLMs

Tool-augmented systems are typically formulated as reasoning-and-acting pipelines or tool-invocation learners [Yao et al., 2023b; Qin et al., 2024], often employing planner-centric orchestration for error correction [Wei et al., 2025; Ma et al., 2025]. Recent benchmarks like MetaTool and Toolink further diagnose tool choice behaviors [Huang et al., 2024; Qian et al., 2024]. However, these methods predominantly rely on autoregressive decoding, which we show suffers from early commitment when the task requires exploring a combinatorial space of tool subsets.

2.2 Planning Benchmarks

Current benchmarks, including TaskBench, API-Bank, and AgentBench [Shen et al., 2024; Li et al., 2023; Liu et al., 2024], have evolved to evaluate end-to-end planning capabilities. Since these metrics primarily prioritize final execution accuracy, the specific impact of decoding strategies on candidate diversity remains underexplored. We complement these benchmarks by focusing on their compositional subsets, conducting controlled studies to analyze how different decoding mechanisms influence exploration.

2.3 Multi-Sample Reasoning

Search-based prompting methods (e.g., Tree of Thoughts, Self-Consistency) and graph-structured reasoning [Yao et al., 2023a; Wang et al., 2023; Besta et al., 2024; Pandey et al., 2025] explore candidate sets to improve reasoning. These approaches effectively operate as search strategies atop autoregressive models. However, our experiments suggest that their performance is naturally bounded by the underlying proposal distribution. If prefix dependencies limit diversity, increasing the sampling budget offers limited gains. DiG-Plan addresses this limitation at the proposal stage by adopting diffusion models for non-autoregressive candidate generation.

2.4 Diffusion and Denoising Language Models

Diffusion models have introduced iterative refinement to text generation and discrete sequence modeling [Austin et al., 2021; Li et al., 2022; Nie et al., 2025; Ye et al., 2025]. Most prior work has applied this capability to controllable generation or infilling tasks. Here, we extend it to combinatorial tool-set exploration. The global visibility of diffusion models facilitates non-sequential revisions, which is particularly helpful for handling complex inter-tool dependencies that are often challenging for strictly left-to-right generation.

3 Problem Setup

We now formalize the tool-graph planning problem and establish the evaluation framework.

3.1 Tool-Graph Planning

A tool library T contains tools where each tool t ∈ T has a name and a short description. Given a natural-language instruction x, the goal is to predict a tool graph ˆG = (ˆ V , ˆE), where ˆ V ⊆ T is the selected tool set and ˆE ⊆ ˆ V × ˆ V is a set of directed dependency edges. A directed edge (u→v) ∈ ˆE indicates that tool v should be executed after tool u.

Evaluation compares predictions against a ground-truth tool graph G⋆ = (V ⋆ ,E⋆ ) provided by the dataset [Shen et al., 2024]. Three factors make this problem challenging: (i) the tool library can be large, with a combinatorial search space of 2|T | possible subsets; (ii) instructions are often underspecified; and (iii) multiple valid plans may exist, but evaluation uses a single ground-truth reference.

3.2 Metrics

Tool-Set F1

We denote this metric as ToolF1. Given predicted tool set ˆ V (canonicalized against T ) and ground-truth V ⋆ :

where ϵ = 10-8 ensures numerical stability.

Edge Recall

We denote this metric as EdgeRec. Given predicted edge set ˆE (restricted to endpoints in ˆ V ) and ground-truth E⋆ : when |E⋆ | = 0, EdgeRec is 1 if | ˆE| = 0 and 0 otherwise; when |E⋆ | > 0,

Candidate-Pool Metrics

To diagnose candidate diversity and upper-bound quality, we use three complementary metrics. Given a pool of K candidates {( ˜ Vk, ˜Ek)}Kk=1 :

Pass@K quantifies the aggregate coverage of the generated pool by computing the union recall against the ground truth. A high value confirms that the model has effectively explored the relevant search space. Oracle@K establishes the performance upper bound (best-of-K) by selecting the optimal candidate via ground-truth labels. The difference between these two metrics isolates the error source: low Pass@K implies poor exploration, while a large gap to the upper bound indicates poor selection.

Executability

We define a lightweight predicate, ExecOK( ˆG) ∈ {0, 1}, to enforce structural validity using the predicted graph. It returns 1 only if three conditions are met: (i) all edge endpoints lie in the predicted node set, with no self-loops or duplicate edges; (ii) for chain instances, edges form a single path visiting all nodes; and (iii) for DAG tasks, the graph contains at least one sink and no isolated nodes. We apply this strictly as an optional filter during selection to ensure deployability.

3.3 Motivating Evidence: AControlled Study

To validate the early commitment hypothesis, we construct a controlled tool-set prediction task that isolates the combinatorial search component. We define a tool universe T = {t1, . . . , t23} and represent tool subsets as fixed-length 23-bit vectors. Each sample provides a symbolic graph specification (sources, sinks, and a noisy depth hint), and the model predicts which tools are needed. This task has the same combinatorial structure: identifying a sparse subset from 223 possible combinations.

We control three key factors: (i) model capacity by using identical small Transformer backbones with 2 layers, 128 hidden dimensions, and 4 attention heads for both AR and denoising models; (ii) training data by generating a shared synthetic corpus from the same distribution; and (iii) output format by fixing the output length to 23 bits, removing any advantage from variable-length generation. The only manipulated factor is the decoding family: prefix AR through next-token prediction versus masked denoising, which randomly masks 30% of bits and predicts them conditioned on unmasked context.

We generate K=10 candidates per input using temperature sampling for AR and stochastic denoising for masked models, then evaluate Pass@K and Oracle@K.

Table 1 shows that masked denoising raises Pass@10 coverage from 0.320 to 0.943 and Oracle@10 from 0.355 to 0.566, while single-candidate quality remains comparable. With 10 candidates, masked denoising covers 94% of the ground-truth tools on average, while AR covers only 32%. Since model capacity, training data, and output format are controlled, this result provides direct evidence that iterative denoising explores a broader region of the tool-set space than prefix AR decoding.

Implications. This controlled study provides empirical evidence that AR's sequential generation limits exploration in combinatorial search spaces. Motivated by this finding, we propose DiG-Plan (Section 4), which leverages diffusion language models for diverse candidate proposal while using AR for structural refinement.

4 Method: DiG-Plan

4.1 Probabilistic Decomposition

The controlled study in Section 3.3 demonstrates that diffusion-based decoding achieves higher exploration diversity than AR in combinatorial search spaces. Motivated by this finding, DiG-Plan follows a propose-refine-select paradigm that separates tool selection from dependency prediction. Given an instruction x and a tool library T , the framework operates in three stages (Figure 1). First, generate K diverse candidate tool sets { ˜ Vk}Kk=1 through diffusionbased proposal. Second, refine each candidate into a directed tool graph ˜Gk = (˜ Vk, ˜Ek) by predicting dependency edges with autoregressive decoding. Third, select a single plan ˆG using a deployable value function.

DiG-Plan splits tool-graph planning into two stages:

where ϕ denotes the proposer parameters and θ denotes the refiner parameters. The first stage explores diverse tool combinations using diffusion language models. The second stage predicts dependencies using autoregressive decoding, which naturally captures sequential structure. The first stage focuses purely on exploring diverse tool combinations, while the second stage focuses on structured prediction given a fixed tool set. This separation allows using diffusion language models for the first stage and autoregressive decoding for the second stage.

4.2 Diffusion Proposer

As established in Section 1, autoregressive decoding suffers from early commitment in combinatorial search spaces. Diffusion language models [Austin et al., 2021; Li et al., 2022; Nie et al., 2025; Ye et al., 2025] offer an alternative: they iteratively refine a complete output through multiple denoising steps, allowing the model to revise early decisions.

The proposer defines a distribution over tool subsets, instantiated with a diffusion language model. Stochastic sampling draws K candidates { ˜ V1, . . . , ˜ VK} under fixed compute budget. Our controlled experiments (Section 3.3) show that diffusion models maintain higher hypothesis diversity than AR decoding under matched budgets. We compare against AR proposers with temperature and nucleus sampling sweeps in Section 5. Even with top-p=1.0, AR does not match diffusion's exploration quality.

For diffusion proposers exposing per-step token entropies, we derive plan-level confidence by aggregating entropy over the diffusion trajectory. Let H(s) denote mean entropy over masked positions at step s. We discard the first 3 burn-in steps and define ¯H = 1 S-S0 ∑Ss=S0+1 H(s) and c = 1 1+ ¯H ∈ (0, 1] as input to the value function, where S0 = 3.

4.3 Autoregressive Refiner

While diffusion language models excel at exploring discrete combinatorial spaces, autoregressive decoding naturally captures sequential dependencies through its left-to-right generation process. By conditioning on a fixed tool set ˜ Vk, we eliminate the combinatorial search problem that causes early commitment.

For each candidate ˜ Vk, an autoregressive refiner predicts dependency structure ˜Ek conditioned on (x, T , ˜ Vk). The refiner is shared across all proposers to isolate tool-set exploration effects. It takes as input the instruction x, the tool library T , and the proposed tool set ˜ Vk, then generates a structured output specifying dependencies between tools. The output is parsed into tool graph ˜Gk = (˜ Vk, ˜Ek) after canonicalizing tool names and filtering edges.

4.4 Judge-Free Selection via a Value Function

Best-of-K gains require a selector to choose among candidates. Oracle selection is not deployable, as it requires access to ground-truth labels at inference time. External LLM judges introduce both cost and evaluation confounds. We train a lightweight value function sψ( ˜G, x, T ) that scores candidate graphs using only deployable, candidate-observable features.

At inference time, we select the highest-scoring candidate:

Training objective. On a training split where ground-truth graphs are available, the value function is trained to predict a combined target that trades off tool-set accuracy and edge coverage:

with α = 0.7 by default. This weighting prioritizes tool-set accuracy: correct tool selection is required for accurate edge prediction. The predictor sψ is fit by regression to y using only candidate-observable features.

Feature design. The input to sψ concatenates several feature groups:

• Proposer confidence c, derived from diffusion entropy to capture uncertainty.
• Structural heuristic score combining three components with weights 0.3/0.3/0.4: structural validity, coverage, and coherence.
• Predicted counts (number of tools and edges).
• DAG-validity flag computed by topological sorting.
• Candidate index k to capture position bias.
• Multi-hot tool vector over predicted tool names to capture tool-specific patterns.

In the graph feature set, we additionally append a directed edge multi-hot vector over tool pairs. Importantly, no groundtruth-derived quantities are used at inference time, so the selector is fully deployable without oracle access.

4.5 Executability Constraints

When high-scoring candidates are close, exec-filtered selection chooses the highest-scoring candidate satisfying ExecOK( ˜Gk)=1 (as defined in Section 3), falling back to unconstrained top-1 otherwise.

5 Experiments

We evaluate on TaskBench-23 [Shen et al., 2024] and APIBank [Li et al., 2023], reporting end-to-end tool-graph metrics (ToolF1 and EdgeRec) and candidate-pool diagnostics (Pass@K, Oracle@K).

5.1 Benchmarks

TaskBench-23. TaskBench [Shen et al., 2024] provides a tool-graph planning benchmark with diverse dependency structures. We use N=501 instances, with 167 each for single-tool, chain, and DAG tasks. For candidate-pool analyses, we focus on the compositional subset of chain and DAG instances, yielding N=334 instances.

API-Bank. We convert API-Bank [Li et al., 2023] to TaskBench format with tool nodes and dependency edges, serving as an out-of-domain check.

5.2 Baselines

We compare DiG-Plan against several baselines: AR-only, AR two-stage, AR-beam+AR, Retriever+AR (dense retriever with k ∈ {5, 10, 15} combined with AR refiner), and Diffusion+AR. The retriever baseline uses a pre-trained dense retriever (all-MiniLM-L6-v2) without task-specific finetuning, computing cosine similarity between instruction embeddings and tool description embeddings to select top-k tools. All two-stage methods share the same AR refiner to isolate the proposer's effect.

5.3 Implementation Details

Model selection. All two-stagemethods share the sameAR refiner, differing only in the proposer. For end-to-end evaluation we report K=1 in Table 2, while for candidate-pool analyses we generate K ∈ {5, 10} candidates per input. The value function is trained on a disjoint training split with supervision y = α·ToolF1+(1-α) ·EdgeRec where α = 0.7.

Proposer models. Diffusion proposers use Dream 7B [Ye et al., 2025], LLaDA-8B-Instruct [Nie et al., 2025], or LLaDA2.0-mini-preview [Bie et al., 2025]. AR components use Qwen2.5-7B-Instruct [Yang et al., 2024]. The retriever baseline uses all-MiniLM-L6-v2 [Reimers and Gurevych, 2019].

Value function. The value function uses a GradientBoostingRegressor [Pedregosa et al., 2011] with 300 trees, learning rate 0.05, and max depth 4, trained on candidate pools from the training split.

Table 3 presents candidate-pool diagnostics on the held-out chain+DAG subset with N=334 and K=10. Compared with an AR proposer under comparable budgets, Dream raises UnionPrec@10 from 0.575 to 0.692 and Oracle@10 from 0.735 to 0.787, indicating both stronger best-of-K quality and higher-precision coverage.

5.4 Disentangling Proposal Quality from Selection

Table 2 reports end-to-end results on TaskBench-23 with N=501 and K=1. DiG-Plan with Dream proposer achieves ToolF1 of 0.729 and EdgeRec of 0.268, outperforming the AR two-stage baseline with ToolF1 of 0.661 and EdgeRec of 0.242, corresponding to a 10% relative improvement. Since single-tool instances do not require combinatorial search, performance differences mainly arise on chain and DAG instances; we therefore focus additional analyses on the compositional subset of N=334 instances.

Several trends emerge from these results. First, twostage methods outperform single-stage AR-only baseline, which achieves ToolF1 of 0.629. Second, among two-stage methods, diffusion proposers outperform AR proposers and retrieval-based proposers. Third, the Dream DLM-only baseline achieves high EdgeRec of 0.335 but low ToolF1 of 0.128. However, this aggregate EdgeRec is driven by single-tool instances: DLM-only achieves near-perfect EdgeRec of 0.994 on single tasks but fails on chain with 0.006 and DAG with 0.004 structures. This shows that end-to-end diffusion generation struggles with precise tool-name grounding and complex dependency prediction on compositional tasks, motivating our two-stage design where diffusion handles tool-set exploration and AR handles edge prediction.

Figure 2 visualizes this advantage across multiple metrics. On the compositional subset (Figure 2a), Dream improves over AR on K=1 ToolF1, Oracle@10, and EdgeRec, matching the candidate-pool gains in Table 3. Figure 2b further shows that the propose-refine-select interface transfers to API-Bank, where LLaDA achieves the strongest Oracle@10 and competitive value-selected ToolF1.

We further test whether the gap is due to weak AR decoding by evaluating an AR-beam proposer under the same heldout protocol, using N=334, K=10, and the same executionconstrained selector. AR-beam reaches ToolF1/EdgeRec of 0.625/0.294, still below Dream's 0.708/0.398, showing that stronger AR search alone does not close the gap.

Having established the effectiveness of the diffusion proposer, we next investigate the impact of the selection mechanism. To disentangle the contributions of proposal quality from selection strategy, we fix a single Dream-proposed candidate pool with the shared AR refiner at K = 5 and systematically vary only the selection strategy on the held-out compositional test set of N = 334 instances. This experimental design isolates the selector's contribution, allowing us to measure selection quality independently of proposal quality.

Table 4 demonstrates that an inference-time judge-free value function achieves ToolF1 of 0.716 compared to 0.690 for heuristic selection. Measured relative to the K=1 baseline of 0.685, this recovers 0.031/0.083 ≈ 37% of the oracle gap to the best-of-5 value of 0.768.

Figure 3 shows (a) best-of-K scaling and (b) AR sampling sweep results. The value function consistently outperforms heuristic selection across all K values, and AR cannot match Dream's performance even when higher top-p values increase sampling diversity.

5.5 Error Analysis and Complexity Stratification

We analyze failure patterns using an automatic multi-label taxonomy on the held-out compositional subset of N = 334 instances. The taxonomy evaluates the value-functionselected predictions from a Dream proposer pool with K = 10 candidates. Error tags are not mutually exclusive, so each predicted graph can receive multiple labels.

Missing edges are the most frequent error tag, affecting 82.9% of samples; missing tools follow at 76.9%. This indicates that coverage remains the primary challenge. Better tool proposals are still useful: Dream raises exact-tool coverage from 0.234 to 0.296 and exact+full-edge coverage from 0.141 to 0.231 over AR. Since the refiner cannot recover edges between missing tools, proposal and refinement quality are complementary. With ground-truth tools fixed, an oracle-refiner diagnostic raises EdgeRec from 0.398 to 0.675, identifying edge refinement as the remaining bottleneck. Extra tools appear in 50.9% of predictions, and overt cyclicity remains rare at 6.9%.

Using K = 5 selection from the same Dream pool, valuefunction selection typically provides gains over heuristic selection, with notable improvements on instances with 3-4 tools where combinatorial search is non-trivial. For example, on chain instances with 3-4 tools, value-function selection achieves ToolF1 of 0.680 and 0.636 respectively, compared to heuristic's 0.661 and 0.632.

5.6 Qualitative Analysis

Table 5 gives representative chain and DAG examples under the same refiner and value-based selector. Dream identifies all required tools in both cases, while AR makes semantically plausible but task-mismatched substitutions such as Image Classification for Document QA and Image-to-Image for Text-to-Image. These examples illustrate how early prefix choices can steer AR away from better tool combinations.

6 Conclusion

We presented DiG-Plan, a diffusion-guided propose-refineselect framework for tool-graph planning. The central finding is that prefix autoregressive decoding suffers from early commitment in tool-set search: once early tool choices are sampled, subsequent decisions remain conditioned on that prefix, limiting the diversity of candidate tool sets. DiG-Plan addresses this mismatch by using diffusion for global tool-set proposal, AR decoding for dependency refinement, and an inference-time judge-free value function for candidate selection.

Controlled and benchmark evaluations show stronger candidate coverage and a 10% ToolF1 gain over AR baselines. Candidate-pool diagnostics, AR sweeps, and AR-beam comparisons attribute these gains to proposal quality rather than stochasticity. Future work will strengthen edge refinement.