{"id":"c54007a3-dce9-4121-9ab5-9ed284db367e","arxiv_id":"2504.20754","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"PALM encodes a path as a one-hot outgoing edge for every vertex, so any PALM output of the discrete diffusion model decodes to a valid path; DDPS adds reward-gradient guidance to steer sampling toward preferred edges.","lead":"A discrete diffusion model learns to represent paths in layered graphs as a stack of one-hot edge choices, so every generated sample is guaranteed to decode into a valid path. The authors add a reward-gradient guidance step that steers sampled paths toward preferred edges without retraining.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (6) cannot be a pointwise likelihood ratio: the RHS ∇_z R(z) depends only on predicted clean logits z, while the LHS depends on both x_t and x_{t-1}; Algorithm 2 also adds the gradient to a probability vector rather than to log-probabilities, so the posterior-sampling claim is unsupported.","rationale":"The PALM construction is sound: for any full assignment of one outgoing edge per reachable vertex, following from the unique first-layer vertex yields a path, and condition (4) of Definition 1 prevents dead ends before layer L. The many-to-one/onto claim is correct, and the validity guarantee is not in question. The empirical reward curves in Fig. 4 are plausible because the reward is a linear function of edge inclusion, so a gradient step on expected reward will increase preferred-edge frequency. The load-bearing weakness is the theoretical bridge from Eq. (5) to Eq. (6), Eq. (7), and Algorithm 2. The approximation is not merely lacking an error bound; it has the wrong dependency structure (no x_{t-1} in the RHS) and the paper specifies two different update rules, one in log-probability space and one in probability space. Therefore the paper has not shown that DDPS is posterior sampling; at most it has shown a reward-guided heuristic. The conditional verdict remains appropriate rather than reject, because the validity guarantee and the empirical reward improvement are independent of the posterior-sampling justification, and both are credible. The proposed enumeration test on Toy would settle whether the approximation can be salvaged or should be reframed as a heuristic.","tokens_in":13668,"tokens_out":10028,"duration_ms":109670,"concrete_test":"On the Toy graph, enumerate all clean paths and, for a fixed preferred edge y and several timesteps t, compute the exact ratio log(p(y|x_t,x_{t-1})/p(y|x_t)) by marginalizing q(x_{t-1}|x0) p(x0|x_t) over all x0 consistent with x_t and x_{t-1}; compare the result with ∇_z R(z) for the same x_t. If the vectors differ in sign or relative ordering across x_{t-1}, Eq. (6) is not a likelihood-ratio approximation. This check is feasible because Toy is small enough to enumerate all PALM states at a given timestep.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's distinctive contribution beyond PALM is DDPS guidance, so Eq. (6) is the load-bearing step. The Bayes identity in Eq. (5) is exact, but Eq. (6) asserts log(p(y|x_t,x_{t-1})/p(y|x_t)) ≈ ∇_z R(z), where z = \\tilde p_θ(x0|x_t). The left-hand side is a function of both x_t and x_{t-1}; the right-hand side is a vector depending only on x_t through z and on the reward parameters. It has no x_{t-1} dependence, so it cannot be a pointwise approximation of a likelihood ratio. Separately, Eq. (7) states the guidance is added in log-probability space, but Algorithm 2 lines 7-8 compute \\tilde x_{t-1} = (∏ Q_τ) z (a probability vector) and then form \\tilde x'_{t-1} = λ g_t + \\tilde x_{t-1}, adding a gradient to probabilities with no clipping or renormalization. The two descriptions disagree, and neither is derived from Eq. (5). Consequently, Fig. 4 demonstrates reward improvement for a reward-shaping heuristic, but not that the sampler targets the conditional distribution p(x0|y). The Fig. 5 target is the λ=0 distribution filtered to max reward; any interpolation between two distributions can produce the reported non-monotone distance curves, so this does not validate posterior sampling. Path validity itself is untouched: even if Eq. (6) is wrong, every sampled PALM decodes to a valid path.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses constrained generation of paths in layered graphs with discrete diffusion. It introduces the padded adjacency-list matrix (PALM): one one-hot vector per vertex over its outgoing edges, so any assignment decodes to a unique valid path and every path has many PALM encodings. Training follows D3PM with uniform transition matrices, a cosine schedule, and a loss restricted to vertices on the path. For conditional generation, the paper proposes DDPS, which at each reverse step predicts clean logits z, computes the gradient of expected reward R(z), and adds a scaled gradient to the predicted x_{t-1} distribution. Experiments on three graphs compare validity with EDP-GNN and SwinGNN, show reward improvement as the guidance scale grows, and report distributional-distance curves as a function of lambda.","tokens_in":14051,"tokens_out":9376,"duration_ms":96275,"significance":"The PALM representation is a genuinely simple and correct way to enforce path validity: the many-to-one/onto argument in Section 3 is sound, and the 100% valid rate in Table 1 follows by construction. The reward curves in Figure 4 give preliminary evidence that the gradient-based guidance is a useful reward-shaping heuristic, and the paper is honest about the preliminary nature of the results. However, the paper's stronger claim, that DDPS is a form of posterior sampling built on the Bayes identity (5), is not established by the current derivation or experiments. The distinctive contribution beyond PALM is the guidance mechanism, and that mechanism currently rests on an unproved approximation and an underspecified algorithm.","major_comments":[{"comment":"Equation (6) is the load-bearing step: it replaces log(p(y|x_t,x_{t-1})/p(y|x_t)) with nabla_z R(z), where z = tilde p_theta(x0|x_t). This cannot be a pointwise likelihood ratio because the left-hand side is a function of both x_t and x_{t-1}, while the right-hand side depends only on x_t (through z) and the reward. No derivation, error bound, or numerical check is provided, so Algorithm 2 is currently a reward-shaping heuristic rather than a posterior sampler. I recommend a small calibration study (e.g., on the Toy graph, compare DDPS samples against the exact reward-filtered posterior, or estimate both sides of Eq. (6) by Monte Carlo) and, if the approximation remains heuristic, stating that explicitly in the paper.","section":"4.2, Eq. (6)"},{"comment":"Equation (7) states that guidance is added in log-probability space, but Algorithm 2 adds the gradient to a probability vector. In detail, line 7 defines tilde x_{t-1} = (prod_{tau=1}^t Q_tau) z, which as written is a distribution over x_t, not x_{t-1}; the product should run to t-1 if q(x_{t-1}|x_0) is intended. Line 8 then forms tilde x'_{t-1} = lambda g_t + tilde x_{t-1}, which can have negative or non-normalized entries before the categorical sampling in line 9; no clipping or renormalization is specified. The algorithm needs a consistent formulation (e.g., adding the gradient to logits and renormalizing) and a correction of the product index.","section":"Algorithm 2, lines 7-9; Eq. (7)"},{"comment":"The target distribution in Section 5.3 is defined operationally as the lambda = 0 distribution filtered to maximum-reward samples, not as a posterior p(x0|y) under a stated likelihood. Since any guidance mechanism that shifts probability toward high-reward paths will produce distance curves that first decrease and then increase as lambda grows, the non-monotone 'sweet spot' in Figure 5 does not validate Eq. (6) or support the posterior-sampling interpretation. A direct calibration test on a small graph would be needed; otherwise the paper should present DDPS as empirical reward shaping.","section":"5.3, Figure 5"}],"minor_comments":[{"comment":"Footnote 2 acknowledges that guidance scale technically cannot be compared across methods, but Figure 3 plots both methods against the same lambda and uses the comparison to conclude that SwinGNN is brittle; please remove the cross-method comparison or use a method-agnostic measure of guidance strength.","section":"2, footnote 2; Figure 3"},{"comment":"Table 1 reports only validity, which is 100% by construction for PALM; reporting a distributional fidelity metric (e.g., distance to the validation path distribution) would make the comparison with EDP-GNN and SwinGNN more meaningful.","section":"5.1, Table 1"},{"comment":"Definition 3 uses V for both the vertex set and its cardinality; use |V| for the cardinality to avoid ambiguity.","section":"3, Definition 3"},{"comment":"The loss masking in Eq. (4) ('only include losses incurred at vertices on the path') is not specified; please state how the mask is formed when random one-hot rows are assigned to off-path vertices.","section":"3, Eq. (4)"},{"comment":"The paper would benefit from a reproducibility statement: hyperparameters such as learning rate, batch size, UNet width/depth, and the exact sampling schedule are not given, and no code is released.","section":"5, experimental setup"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the representation contribution is sound and the experiments are a reasonable preliminary study, but the guidance derivation is the weak point and would need substantial reworking for a full-venue version. I would encourage the authors to either provide calibration evidence for Eq. (6) or explicitly reframe the method as a reward-shaping heuristic. I do not see any citation or novelty concerns beyond the overclaiming of 'posterior sampling.'"},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe PALM representation is the real contribution here, and it's a good one. Encoding a path as a stack of one-hot outgoing-edge choices, one per vertex, makes the path-validity constraint hold by construction: any full assignment decodes to a valid path, and every path has at least one encoding. That's clean and genuinely useful, and the experiments back it up: DDPS gets 100% valid rate while EDP-GNN gets 0 and SwinGNN gets 99.7% but breaks under guidance. The reward-gradient steering idea is also interesting—it's cheap, retraining-free, and the reward curves in Fig. 4 show clear improvement with guidance strength.\n\nThe soft spots are the ones you'd expect when a workshop paper claims posterior sampling without the math to back it. Eq. (6) equates a scalar log-likelihood ratio to a vector gradient ∇_z R(z). That's not a pointwise approximation; the left side depends on both x_t and x_{t-1}, the right side only on x_t through z. And Algorithm 2 adds λ g_t to a probability vector, not to log-probabilities as Eq. (7) states, with no clipping or renormalization. So the paper doesn't actually show that DDPS samples from p(x_0 | y); it shows that a heuristic reward-shaping step improves reward, which is fine but should be labeled as such. The Fig. 5 target is the λ=0 distribution filtered to max reward, so the non-monotone distance curves are uninformative about posterior sampling. Missing code and hyperparameters also make the empirical claims hard to check, and the closest baseline, Shi et al.'s graph-constrained diffusion with its beam-search post-processing, is cited but never compared. The footnote that guidance scales are not comparable across methods further weakens the SwinGNN comparison.\n\nNone of this touches the PALM validity guarantee, which is the load-bearing result and is sound. The paper is honestly written about the heuristic nature of Eq. (6), but the title and framing overreach.\n\nWho's the audience? Researchers working on discrete diffusion for constrained generation, especially path planning. They'll get value from the PALM encoding and the empirical demonstration that structural priors beat post-hoc rounding. The guidance part needs a proper derivation or an error bound before I'd trust it.\n\nI'd send this to peer review—it deserves careful refereeing—but as a workshop paper or with major revisions, not as-is for a main track. The representation alone is worth a serious look.","headline":"PALM is a genuinely useful path encoding that guarantees validity; the guidance is a plausible heuristic with an unsupported posterior-sampling claim.","tokens_in":14543,"tokens_out":2809,"would_cite":true,"duration_ms":27801,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"New representation makes every diffusion sample a valid graph path.","keywords":["discrete diffusion models","layered graphs","path generation","padded adjacency-list matrix (PALM)","classifier guidance","discrete posterior sampling","graph generation","validity by construction"],"falsifier":"On a layered graph small enough to enumerate every path, compute the exact ratio $\\log(p(y|x_t,x_{t-1})/p(y|x_t))$ by brute force for a preferred-edge reward, then run Algorithm 2 with the same reward. If the empirical distribution of decoded paths does not move toward the exact posterior as $\\lambda$ increases, or if the correlation between $\\nabla_z R(z)$ and the true likelihood ratio is weak or negative, the Eq. (6) approximation is falsified while the PALM validity claim remains untouched.","tokens_in":13419,"feed_emoji":"🛤️","tokens_out":7832,"duration_ms":63357,"temperature":0.7,"pith_summary":"The paper sets out to show that discrete diffusion models can generate paths in layered graphs with a hard validity guarantee: every sample is a path, not merely a subgraph that resembles one. Its device is the padded adjacency-list matrix (PALM), which stores a path as one one-hot vector per vertex, each selecting a single outgoing edge. Because any PALM decodes deterministically into exactly one path and every path has at least one PALM, validity is built into the representation rather than left to the model. The paper also claims that reward guidance can steer samples toward preferred edges without retraining, by approximating the discrete posterior log-likelihood ratio with the gradient of expected reward with respect to PALM logits. Experiments report 100% valid samples on the tested graphs and reward improvement that grows with the guidance scale.","feed_headline":"New representation makes every diffusion sample a valid graph path","feed_subtitle":"One-hot edge matrices decode deterministically into valid paths; gradient guidance biases samples to preferred edges.","key_machinery":"The central object is the padded adjacency-list matrix (PALM): for a layered graph with vertex set $V$, a path is encoded as a collection $\\{x_v\\}_{v \\in V}$, where $x_v \\in \\mathbb{R}^{D_v}$ is a one-hot vector picking one outgoing edge of vertex $v$ (with padding when $D_v = 0$). Following the selected edges from the singleton first layer reconstructs the path, which makes the decoding deterministic. The guiding machinery is Eq. (6)-(7): the log-likelihood ratio $\\log(p(y|x_t,x_{t-1})/p(y|x_t))$ is approximated by $\\nabla_z R(z)$, the gradient of the expected total reward $R$ with respect to the PALM logits $z = \\tilde{p}_\\theta(\\tilde{x}_0|x_t)$, and this gradient is added to the denoising logits with scale $\\lambda$ to produce the posterior sample in Algorithm 2.","core_discovery":"The central claim is stated in Section 3: the PALM-to-path mapping is many-to-one and onto, so (i) one PALM instance represents exactly one path, and (ii) every path is represented by at least one PALM. Consequently, a discrete diffusion model trained to output PALM one-hot vectors can only emit samples that decode to valid layered-graph paths, and the validity guarantee holds regardless of guidance strength. In Section 5 the paper further claims that its DDPS guidance, built on the gradient approximation in Eq. (6), increases the reward of generated paths while maintaining reasonable adherence to the learned distribution, with validity rates that stay at 100% where an adjacency-matrix baseline (SwinGNN) degrades to zero under strong guidance.","pith_inferences":["Because the validity guarantee is representational rather than statistical, the same one-choice-per-item encoding should transfer to other constrained combinatorial objects (e.g., spanning trees or matchings) whenever a deterministic decoder exists; the paper does not test this.","The Eq. (6) approximation is the part most likely to fail generally: on small graphs one can compute the exact likelihood ratio and compare it with $\\nabla_z R(z)$, which would isolate whether the reported reward gains come from correct posterior approximation or from a bias that happens to help.","The sweet-spot location in $\\lambda$ varies with graph and reward sparsity, suggesting guidance scale should be tuned per task; extending DDPS to multi-objective or learned rewards would test whether the gradient signal remains aligned with the true likelihood ratio.","The paper's guidance is classifier-style and requires no retraining, so it could in principle be composed with classifier-free or RL-based discrete guidance, but the paper does not explore such combinations."],"forward_implications":["Every sample drawn from the PALM-based discrete diffusion model decodes to a valid path with no post-processing.","Increasing the guidance scale $\\lambda$ raises average reward and eventually plateaus near the maximum achievable reward under the tested reward configurations.","The valid rate remains 100% under guidance, whereas the SwinGNN adjacency-matrix baseline drops to 0% as $\\lambda$ grows.","Distributional distance between guided samples and the target posterior first falls, then rises after a sweet spot, so guidance scale can be tuned to balance reward against fidelity.","PALM-based training uses only the loss on vertices that lie on the path, which is the natural objective when the data distribution is over paths."],"supporting_citations":[{"why":"Supplies the D3PM discrete diffusion framework, its parametrization, and the combined loss that training and inference over PALM build on.","marker":"Austin et al. (2021)"},{"why":"Provides the multinomial/argmax-flow discrete diffusion with uniform transitions, which the per-vertex PALM transition matrices are constructed from.","marker":"Hoogeboom et al. (2021)"},{"why":"Contributes the cosine noise scheduling used in the forward diffusion process.","marker":"Nichol & Dhariwal (2021)"},{"why":"Establishes classifier guidance, the paradigm DDPS adapts for steering generated paths toward preferred edges.","marker":"Dhariwal & Nichol (2021)"},{"why":"Motivates deriving discrete-diffusion guidance from the Bayesian log-likelihood ratio in Eq. (5), which Eq. (6) approximates.","marker":"Nisonoff et al. (2025)"},{"why":"Provides EDP-GNN, the adjacency-matrix score-based baseline whose valid rate is 0% in the comparison.","marker":"Niu et al. (2020)"},{"why":"Provides SwinGNN, the continuous-adjacency diffusion baseline whose validity degrades under guidance in the comparison.","marker":"Yan et al. (2024)"},{"why":"Supplies the simplified reward-gradient guidance applied to the SwinGNN baseline so the guided comparison is possible.","marker":"Ma et al. (2024)"}],"fun_headline_variants":["Diffusion now generates valid paths every single sample","PALM representation guarantees valid paths in every diffusion sample","Steer diffusion paths to preferred edges without any retraining","Valid paths guaranteed: diffusion sampling with gradient guidance"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that the gradient of expected reward with respect to PALM logits is a faithful proxy for the log-likelihood ratio in Eq. (6); the paper offers no error bound, derivation, or directional check, so if that approximation is poor the guided samples need not follow any well-defined conditional distribution, even though the PALM validity guarantee still holds.","fun_headline_variants_meta":{"raw":{"variants":["Diffusion now generates valid paths every single sample","PALM representation guarantees valid paths in every diffusion sample","Steer diffusion paths to preferred edges without any retraining","Valid paths guaranteed: diffusion sampling with gradient guidance"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00059,"raw_usage":{"total_tokens":2711,"prompt_tokens":831,"completion_tokens":1880,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":447,"completion_tokens_details":{"reasoning_tokens":1817}},"tokens_in":447,"tokens_out":1880,"duration_ms":14162,"temperature":1.0,"reasoning_tokens":1817,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:21:39.235755+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a layered graph small enough to enumerate every path, compute the exact ratio $\\log(p(y|x_t,x_{t-1})/p(y|x_t))$ by brute force for a preferred-edge reward, then run Algorithm 2 with the same reward. If the empirical distribution of decoded paths does not move toward the exact posterior as $\\lambda$ increases, or if the correlation between $\\nabla_z R(z)$ and the true likelihood ratio is weak or negative, the Eq. (6) approximation is falsified while the PALM validity claim remains untouched.","supporting_citations":[{"cited_title":"Argmax flows and multinomial diffusion: Learning categorical distributions","cited_arxiv_id":null,"evidence_quote":"Provides the multinomial/argmax-flow discrete diffusion with uniform transitions, which the per-vertex PALM transition matrices are constructed from."},{"cited_title":"Unlocking guidance for discrete state-space diffusion and flow models","cited_arxiv_id":null,"evidence_quote":"Motivates deriving discrete-diffusion guidance from the Bayesian log-likelihood ratio in Eq. (5), which Eq. (6) approximates."},{"cited_title":"Permutation invariant graph generation via score-based generative modeling","cited_arxiv_id":null,"evidence_quote":"Provides EDP-GNN, the adjacency-matrix score-based baseline whose valid rate is 0% in the comparison."}],"review_version":1}