acceptodds
Under review as a conference paper at ICLR 2027

Enhancing LLM Plan Diversity by Training on Multiple Partial-Order Linearizations

Abstract

Plans comprise steps that may be executed in more than one order to reach a goal, since pairs of steps may not necessarily be dependent on each other. LLM planning has become increasingly important, along with models' ability to emit valid sequences of steps and remain robustly invariant to their valid reorderings. However, such invariance requires producing similar likelihoods under different valid orders of steps, which is in general not true of pre-trained LLMs. In this paper, we train LLMs to increase the reliability and diversity of the plans they generate. During training, we feed them fixed or multiple orders of the same plan, either using standard language modeling or a plan-unshuffling objective. Likelihood comparisons and sampled generation on plans in multiple domains show that training on a single linearization of a plan's partial order reduces diversity among generated valid orders. By contrast, using multiple valid orders can vastly increase diversity among generated valid orders, which in turn could improve the ability of LLMs to avoid infeasible execution paths and parallelize independent steps in workflows. Finally, we find that the activations and behavior of the model reflect the underlying structure of the plans, with limited evidence that the likelihoods of step orders can be steered with causal interventions on the activations. Code: https://anonymous.4open.science/r/procedural_dags-1033

Primary area:
foundation or frontier models, including LLMs
Keywords:
procedural text understanding, planning, partial order, invariance, shuffling, probing, steering

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_ogKmOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper's main claim, as framed, is that training an LLM on diverse linearizations of a partial-order plan gives it high entropy over the plans it generates. Framed this way, the finding is trivial.

I personally feel the authors' choice of storyline is a pity. Pls see W4

Critical strengths

Good problem setup and solid experiments, code is provided

Critical weaknesses

W1. The likelihood metrics are relative within the valid set; the paper never measures how much probability mass the valid set actually carries.

Both headline likelihood metrics are defined relative to the valid linearizations. DℓD_\ell renormalizes likelihoods inside T(G)\mathcal{T}(G) before computing entropy, and VℓV_\ell compares a valid order only against an invalid one produced by swapping two adjacent, directly connected nodes. Neither measures the total probability the model assigns to valid sequences as opposed to invalid or malformed ones. The main interpretation of the key result, that increasing kk "mainly redistributes probability among valid alternatives" (Section 5.1), is therefore an inference from relative scores rather than a measurement. A model could assign high, evenly spread likelihood within T(G)\mathcal{T}(G) while placing most of its mass elsewhere, and Table 4 would look exactly the same.

The generation results partially close this gap on Blocks World, where the seven models with high generation validity show invalid-order rates of 0.1% to 4.2% at kk = all (Table 9). But that check is behavioral: two samples per plan, temperature 1, unshuffling format only. On proScript the same check fails outright, with VgenV_{gen} as low as .067 and malformed outputs near 30% (Table 12). So for the natural-language domain, where the paper still claims likelihood-diversity gains and cross-domain transfer, the evidence rests almost entirely on the relative metrics above.

Two additions would make the claim direct. First, score a broader invalid set (multi-edge violations, long-range reorderings) so that VℓV_\ell tests more than single-edge sensitivity. Second, estimate the total mass on valid sequences, either from a larger sampled set with exact validity checking or by summing likelihoods over a bounded candidate set. This matters most for proScript and the recipe-domain transfer, where generation validity is weak and the entropy increase is the main positive result.

W2. The intermediate-kk evidence behind the paper's most actionable claim covers only the two smallest models, and for generation effectively one.

The claim that much of the diversity gain "already appears with only a few valid training orders per plan" is the result a practitioner would act on, since kk = 2 is the cheapest possible intervention. Its support is narrow. Only GPT-2 (124M) and SmolLM-135M cover k∈{2,4}k \in \{2, 4\} (Table 3).

Extending the kk = 2 condition to the remaining seven models, for both likelihood and generation, would either solidify the claim or delineate where it stops. To the authors' credit, the abstract scopes the few-orders claim to the two tested models; the issue is that the paper's practical significance rests on exactly this claim, so its evidence base deserves the same nine-model coverage as the kk = 1 vs kk = all comparison.

W3. The related work misses the closest methodological previous work literature, which changes how the contribution should be framed.

He et al., "Order Doesn't Matter, But Reasoning Does: Training LLMs with Order-Centric Augmentation" (EMNLP 2025). That work constructs a DAG over reasoning steps, generates valid reorderings via topological sorting, and trains LLMs on them as SFT augmentation. This is the same training mechanism the present paper varies with kk, applied to logical reasoning with accuracy rather than diversity as the goal. The introduction's framing, "We do this by varying the number of valid linearizations shown to a model," reads as if the training scheme itself is new. It is not. What is new is the diversity and likelihood-invariance objective, the dose-response analysis over kk, and the probing and steering experiments. The contribution should be framed accordingly, and the two works should be compared directly.

W4. The headline contrast is the least informative result in the paper, and the one genuinely surprising observation is reported without any mechanistic analysis.

The central narrative of the paper is the contrast between collapse at kk = 1 and recovery at kk = all. The first direction is close to a tautology: maximum-likelihood training on a target distribution that places all mass on one order per plan will, given sufficient capacity, reproduce that concentration. The second direction follows from mass covering over the now-broadened target. Both are what standard supervised training predicts given how the data pipeline is constructed, and the paper's framing gives them the abstract, the first table, and the section lead.

The observation that does not follow from these considerations is the saturation at kk = 2 (Table 4b). Fitting a training distribution supported on two orders per plan yields per-plan entropy of at most log⁡2/log⁡∣T(G)∣\log 2 / \log |\mathcal{T}(G)|; for Blocks World, where the median ∣T(G)∣|\mathcal{T}(G)| is 3 (Table 2), that bound is 0.63, yet the measured DℓD_\ell is 0.937. The model therefore assigns substantial likelihood to valid orders it never saw in training, which means the intervention works through generalization of an order-symmetry rather than through coverage of the shown orders. The paper neither performs this ceiling analysis nor offers or tests any mechanism for the saturation. Natural hypotheses are available and testable with the paper's own tools: the incomparable-swap bias in Tables 8 and 11 suggests the model learns local pairwise interchangeability rather than global uniformity, and stratifying the kk sweep by ∣T(G)∣|\mathcal{T}(G)| would show whether saturation requires larger kk on plans with wider partial orders. As written, the most theoretically interesting number in the paper is presented as a side remark.

The missing mechanism question has a sharp edge that the paper is well positioned to address but does not. Wang et al. (2026), cited by the authors, show that policy-gradient training collapses solution diversity on Blocks World even when the reward covers all valid orders, a regime in which the data-degeneracy explanation offered here cannot apply. The supervised collapse studied in this paper and the RL collapse reported there therefore have different sufficient causes, and contrasting the two regimes would isolate what actually drives order concentration: whether a model trained with k>1k \gt 1 resists RL-stage collapse, and whether the same saturation at small kk appears when the objective is mode-seeking rather than maximum likelihood, are questions that would turn this paper's empirical observation into a mechanistic claim about training objectives (see also S1).

Questions for authors

S1. Test whether multi-linearization training protects against diversity collapse under RL. The paper attributes the SFT-stage collapse to the data side: a degenerate per-plan target fitted by maximum likelihood. Wang et al. (2026), cited in the paper, show that policy-gradient training collapses solution diversity on Blocks World even after training accuracy saturates, which is a mode-seeking effect of the RL objective itself and cannot be fixed by data augmentation alone. The natural joint question is whether a model first trained with k>1k \gt 1 retains its entropy over valid orders when subsequently optimized with RL, or whether the RL stage re-collapses the distribution onto a single order. A minimal version needs no new infrastructure: take the kk = 1 and kk = all BW checkpoints and apply the same policy-gradient recipe with validity as the reward, tracking DℓD_\ell and VℓV_\ell over training. The outcome is informative either way: if multi-linearization SFT confers lasting resistance, it becomes a pre-RL intervention worth adopting; if not, the paper's remedy is bounded to supervised stages and that boundary is worth stating.

S2. Ground the mechanism discussion in the forward-KL/reverse-KL framing of post-training. The paper's two collapse regimes map cleanly onto an existing analysis: SFT is maximum likelihood, i.e. forward KL against the empirical target, which is mass-covering over whatever support the data provides, while RL fine-tuning behaves as reverse KL against a reward-defined target, which is mode-seeking. Chen et al., "Retaining by Doing: The Role of On-Policy Data in Mitigating Forgetting" (arXiv:2510.18874), develop exactly this SFT-as-forward-KL / RL-as-reverse-KL model of post-training and would give the discussion section a vocabulary for the contrast raised in W4: the collapse studied here is a property of the data the objective is applied to, whereas the collapse in Wang et al. (2026) is a property of the objective itself. Citing this line of work would also connect the kk = 2 saturation result to a concrete open question that the framing makes precise: why generalization, rather than coverage, does the work once the empirical support contains more than one order.

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

This paper investigates the impact of training on single versus multiple valid linearizations on the diversity of plans generated by language models. The authors compare standard language modeling with a step-reordering objective, and analyze model behavior through probabilistic scoring, generation evaluation, structural probing, and activation intervention. Their results indicate that training on multiple linearizations enhances the diversity of valid sequences in controlled tasks, though its effectiveness is more limited in the context of natural program generation and behavioral interventions.

Critical strengths
  • The research question is valuable. Distinguishing between the validity of a plan and the diversity of valid sequences helps in understanding whether a model preserves the execution flexibility permitted by a given task.

  • The controlled experimental design is clear. By comparing different training sequences, training objectives, and invalid objectives, the study facilitates an analysis of how the supervision method influences sequence preferences. Furthermore, the authors are commendably transparent in reporting inconsistent or negative results.

Critical weaknesses
  • There remains a gap between experimental settings and practical planning scenarios. The primary task focuses on reordering a given set of steps; it has not yet been sufficiently verified whether enhancing diversity can actually improve interactive execution, adaptation to dynamic constraints, or recovery from failure.

  • The models used may not be fully representative. The experiments rely primarily on small-scale foundation models, lacking models that have undergone comprehensive instruction tuning or post-training for agentic tasks. Consequently, it is difficult to gauge the prevalence or severity of the observed issues across current, more advanced models.

  • The practical significance of diversity metrics requires further clarification. Differences in probability among valid sequences do not necessarily imply planning errors; furthermore, when the validity of generated sequences is low, conditional diversity metrics may fail to accurately reflect a model's true, usable capabilities.

Questions for authors
  1. Could you provide a pre-training generative baseline using currently applicable instruction-following models or agent models, and evaluate sequential preferences and the benefits of your proposed method under consistent input and sampling conditions?

  2. Could you incorporate more complex or interactive planning evaluations to verify whether an increase in the diversity of valid sequences translates into tangible gains, such as improved re-planning capabilities, better adaptation to constraints, or higher execution success rates?

  3. When compared against a baseline trained on high-quality trajectories, with the total training budget held constant, does multi-linearized supervision still offer any distinct advantages? Furthermore, how can one determine whether probability discrepancies between different valid sequences constitute a bias that requires correction?

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

The paper studies whether training LMs on multiple linearizations of a partial-order plan increases the diversity of the orders they generate. The authors fine-tune small language models either with standard language modeling on valid linearizations, or with an "unshuffling" objective, where the model receives the steps of a plan in an invalid order and has to output a valid linearization. In practice, the authors show that training on more valid orders spreads the likelihood over the valid orders. They also use a probing mechanism to identify relations between steps, and try to steer the outputs by intervening the activations along the probe directions.

Critical strengths
  • The research question is clear, and the experiments are done carefully.

  • The authors are honest about the negative and inconclusive results (e.g., RQ3 is explicitly left unresolved).

  • The paper is well-written.

Critical weaknesses

My main concern is that I do not think the main contributions and conclusions of the paper are at the expected level for ICLR. If the model is trained with targets sampled uniformly from all valid orders, it is expected that it spreads its likelihood over the valid orders of held-out tasks from the same distribution. Training on a single order concentrating the likelihood on one order is also expected. The other analyses (i.e., probing and steering) don't provide a crisp conclusion either.

Second, I do not think the paper is really about planning. The input contains no initial state and no goal: in the unshuffling setting, the model receives all the steps of the plan and only has to put them in a valid order, and in the language modeling setting there is no input at all. This is linearizing a given partial-order plan, not generating a plan. I might be missing something here (as the paper never provides a concrete example used for training or inference), so please correct me if I am wrong.

The Blocksworld setting is also limited. All problems have six blocks, three initial towers and a single goal tower, the plans have 4 to 8 steps, and the median number of valid orders is 3. The distribution of problems is too narrow to conclude that the method works on other dists.

The diversity metric is a bit weaker than what is desired. You sample only two outputs per plan, so the ratio of distinct valid outputs to valid outputs essentially measures whether the two samples differ. Moreover, in planning, plans that only differ in the order of the same actions are usually not considered different plans. And once the partial order is known (which can be computed symbolically from the plan), sampling valid linearizations uniformly is trivial. It is unclear why one would need an LLM for that, and a simple symbolic baseline is missing.

Last, but not least, the probing part is correlational, and there is no control probe. The pre-trained models already reach an accuracy of about .75 on Blocksworld for incomparable pairs, so the decodability might come from the step text itself rather than from the representations. The steering experiments, which are the causal part, are mostly null.

Questions for authors
  • Could you give a concrete training example (input and output) for each dataset?

  • Why is there no initial state or goal in the input? In which sense is unshuffling a planning task?

  • How do the results change with larger Blocksworld problems or longer plans?

  • What fraction of the valid orders does the model cover if you draw more samples per plan?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.