Hephaestus: Mixture Generative Modeling with Energy Guidance for Large-scale QoS Degradation

We thank the reviewer for pointing out potential tension between VAEs and EBMs in generative modeling. First, we clarify that our approach does not train VAEs adversarially via a minimax objective. Instead, the minimax formulation is used solely to derive a principled training objective for the EBM, allowing us to train it independently without requiring explicit sampling from the model distribution or estimating the partition function $Z_\theta$, which is typically expensive (e.g., via MCMC or Langevin dynamics). Specifically, as shown in Equation (4), our approach starts from the following minimax objective:

This formulation seeks a latent density $q$ that is simultaneously close to the true data distribution $p$ and exposes gaps in the current generator $\Omega$. From this equation we can derive the objective function for EBM (shown in Appendix 2.3: Proof of Theorem 3) that the inner maximization over $\Omega$ yields a variational bound which leads to the following energy‐based training objective for the EBM (we also defined in main paper):

This objective encourages the EBM to assign low energy to real (feasible) samples (from $p(\mathbf{x})$) and higher energy to generated samples (from $\Omega(\mathbf{x})$), effectively learning a density discrepancy signal. On the other hand, each VAE expert $\Omega _i$ is then trained independently using an energy‐guided ELBO (we also defined in main paper):

In the above, samples generated by the VAE that are assigned high energy by the EBM are penalized. This encourages each expert to specialize in generating samples within low-energy regions, i.e., those aligned with the real distribution. Whenever an expert can no longer effectively minimize its energy penalty (i.e., it fails to cover a high-$\chi(x)$ region where $\chi(\mathbf{x}) = \log q(\mathbf{x}) - \log \Omega(\mathbf{x}) > \delta$), a new VAE expert is added to capture that region. This process is repeated until the overall mixture model covers the high-quality regions of the data distribution, driving the total EBM energy loss toward zero. As a consequence, adding more experts in the Mix-CVAEs progressively reduces density discrepancy, ensuring better coverage of the data manifold and effectively avoiding mode collapse, without requiring the VAE to be inherently mode-covering or mode-seeking.

Second, although this does not affect how the VAE is trained—nor does it require the VAE to be explicitly mode-covering or mode-seeking—for completeness, we note that the VAE training objective is derived from the reversed KL divergence $\mathrm{KL}\left(q _\phi(\mathbf{z} \mid \mathbf{x}) | p _\theta(\mathbf{z} \mid \mathbf{x})\right)$, not $KL(p|q)$. We recall briefly the derivation from original VAE paper [1] here:

As $\log p _\theta(\mathbf{x})$ is constant, maximizing $\mathrm{ELBO}=\mathbb{E} _{q _\phi(\mathbf{z} \mid \mathbf{x})}\left[\log p _\theta(\mathbf{x} \mid \mathbf{z})\right]-\mathrm{KL}\left(q _\phi(\mathbf{z} \mid \mathbf{x}) | p _\theta(\mathbf{z})\right)$ indirectly minimizes the reverse KL(q|p). Recent work [2] instead studies the “forward” KL divergence for Variational inference by leveraging MCMC.

[1] Original VAE paper: Auto-Encoding Variational Bayes. Conference: ICLR 2014

[2] Transport Score Climbing: Variational Inference Using Forward KL and Adaptive Neural Transport. Journal: Transactions on Machine Learning Research 2023

Dear Reviewer,

We’re very glad that our clarifications have addressed your concern regarding the combination of Conditional VAEs and Energy-Based Models. Given your initial assessment that our paper introduces a novel generative modeling + reinforcement learning approach for the important QoSD problem—along with the fact that each component in our framework is supported by theoretical guarantees—we hope the overall potential of our work is clearer now.

In addition to the theoretical motivation, our experiments show that Hephaestus not only outperforms prior SOTA methods under linear edge-weight functions, but is also the first method that successfully handles nonlinear QoSD, which prior methods cannot solve.

Since your remaining concern has now been resolved and you found the paper to be of good quality and originality, we were wondering if you would consider re-evaluating your initial evaluation to see if our work can have a stronger rating based on its theoritical contributions and experimental results.

Thank you very much again for your time and engagement.

Best regards, Authors

Q1 and W1. How robust is the PPS algorithm when SPAGAN is trained on distributions that differ from the test graph topology?

We thank the reviewer for this insightful question. While SPAGAN exhibits strong generalization on graphs with similar topology (as illustrated in Appendix 3.3), we also take care of the out-of-distribution (OOD) case. In particular, we include a robust safeguard—PPS-I, as described in Section 3.3 (Inference Process) of the main paper. PPS-I is capable of taking any intermediate solution (including those produced by the RL refinement phase) and further refining it using exact shortest-path computation (via Dijkstra’s algorithm), thereby guaranteeing 100% feasibility of the final perturbation vector, regardless of SPAGAN’s prediction quality.

To empirically evaluate robustness under distributional shift, we conducted additional experiments in which we injected controlled levels of random noise into SPAGAN’s predictions—simulating degraded generalization. With number of pairs is 50, we report both feasibility (percentage of source–target pairs successfully disconnected, i.e., shortest path > T) and total cost across varying noise levels (30%, 10%, 5%, and 0% of real value) on three real-world datasets used in the main paper (excluding Skitter due to time constraints during the rebuttal). We also assess the ability of both RL and PPS-I to recover from noisy predictions. Results are summarized below:

From the table above, we observe the following:

• PPS performance degrades as SPAGAN’s prediction noise increases, leading to reduced feasibility and inflated cost due to budget being allocated to non-critical edges.

• RL refinement helps recover both feasibility and cost, but does not fully guarantee constraint satisfaction.

• PPS-I consistently restores 100% feasibility, correcting violations through exact computation regardless of prior noise levels.

• Even in the worst-case scenario (RoadCA with 30% noise), PPS-I incurs only a modest cost increase of approximately 19% compared to the ideal, noise-free case (11,061 vs. 9,277), while still maintaining full feasibility.

These findings highlight the robustness of our three-phase pipeline: even when the learned SPAGAN model fails to generalize, PPS-I ensures feasibility recovery, while RL contributes to cost efficiency along the way. We will include these findings and discussion in the final version of the paper.

Q2. Has the RL refinement phase been compared with alternative latent optimization strategies like Bayesian Optimization or ES?

Based on the reviewer’s suggestion, we conducted a comprehensive comparison between our RL-based refinement phase and alternative latent space optimization strategies, including Bayesian Optimization (BO) and Evolutionary Strategies (ES). As summarized in Table 4 below, we evaluate each method on the Gnutella dataset under varying latent dimensionalities, reporting the final cost (lower is better) and feasibility rate. We note that BO does not scale well to high-dimensional latent spaces (e.g., $d>30$) due to its sample inefficiency and surrogate modeling limitations. Therefore, we restrict BO to low-dimensional latent settings ($d=16$ and $d=28$), while allowing higher dimensions for RL and ES. Furthermore, all evaluations are conducted under clean SPAGAN predictions (i.e., without additional noise), to ensure consistent comparison of refinement strategies.

From these results, we can see that our RL-based refinement consistently achieves the best final cost and full constraint satisfaction (100% feasibility) across both latent dimensions. We will also incorporate this discussion in the final version.

Q3 and W2. How is the number of CVAE experts in Morph determined? Is there a risk of redundancy or overfitting?

Thank you for raising this important question. The number of CVAE experts is dynamically determined during training based on a density discrepancy criterion, which quantifies how well the current set of experts captures the latent distribution (we let max expert = 9 in our paper). Specifically, we compute a score $\chi(\mathbf{x}) = \log q(\mathbf{x}) - \log \Omega(\mathbf{x})$ that identifies regions where the mixture model fails to match the energy-guided latent distribution. New experts are only added when this discrepancy exceeds a threshold, ensuring that expansion is data-driven and targeted toward unexplained modes.

Regarding the potential risks of redundancy or overfitting, we would like to highlight several theoretical justifications and empirical safeguards that guide our expert expansion strategy as demonstrated in prior works, including:

[1] Towards Understanding Mixture of Experts in Deep Learning, NeurIPS 2020

[2] A Statistical Perspective of Sparse Top-k Softmax Gating in MoE, ICLR 2023

[3] SwiftHydra: Self-Reinforcing Generative Framework for Anomaly Detection with Multiple Mamba Models, ICLR 2025

there are two key theoretical insights:

(i) MoE models are more expressive than single-expert models [1,3], especially in modeling multi-modal or structured solution spaces like those in the QoSD setting. While increased model capacity could raise overfitting concerns, in practice, top-$k$ sparse gating acts as an implicit regularizer, activating only the most relevant subset of experts per input. This input-dependent sparsity limits the effective model capacity seen by any given sample, thereby reducing the chance of overfitting despite the large total number of experts [2].

(ii) Even when the number of experts $N \to \infty$ (overspecified setting), our use of top-$k$ sparse softmax gating ensures that: Only $k \ll N$ experts are active per input, keeping inference cost bounded and efficient; The convergence rates of parameter and density estimation remain unchanged compared to dense gating, as proven in [2,3]. This decouples model capacity from inference cost and training stability, eliminating the typical trade-off between expressiveness and generalization. Thus, adding more experts improves coverage of target distribution without harming generalization or causing significant computational overhead.

W4. The paper does not compare with recent powerful generative optimization methods (e.g., diffusion-based solvers or large-scale neural MIP solvers)

We would like to clarify that our baseline set already includes two recent and powerful optimization methods with different scale (1) DiffiLO (ICLR 2025 Spotlight), a differentiable ILP solver that performs well on small to medium-sized graphs and (2) Light-MILPopt (ICLR 2024), a neural MILP solver designed for large-scale graphs.

We believe this combination already represents state-of-the-art in combinatorial optimization across graph sizes, and our method consistently outperforms both on multiple datasets, especially in handling nonlinear cost structures and enforcing feasibility via latent-space control

We appreciate your suggestion. Indeed, we’d like to clarify that to highlight the generalizability of SPAGAN, we added up to 30% of noise (which is very unlikely in practice), of which you see the worst-case cost increase approaches 20% (in large network like RoadCA). However, even under this stress testing scenario, our worst-case cost is still less than that of the SOTA methods. Please see Table 1, RoadCA, threshold T=140% (that is the threshold setting used in our rebuttal) in the main manuscript. Note that in Table 1, no noise was added to stress-test SPAGAN. We will mention this discussion in the final version of the paper.

Thank you for your suggestion to include the testing RL vs. ES under noisy predictions. We conducted additional experiments comparing our RL-based refinement with Evolution Strategies (ES) on the Gnutella dataset under varying levels of SPAGAN noise (5%, 10%, and 30%). Results are summarized in the table below:

From experiment, we found that Evolution Strategies are more sensitive to SPAGAN prediction noise, especially due to their strong reliance on the quality of the pretrained solution set $D^{sol}$ generated during the Forge phase. In contrast, our RL-based method maintains better feasibility and lower cost under noise, demonstrating stronger robustness. We will include this experiment and analysis in the Appendix of the final version.

We have provided the answers to this similar suggestion in our rebuttal to reviewer GFJA. For your convenience, we list here again:

We analyzed the learning dynamics of the RL policy across training episodes (to standardize comparisons across graph sizes). The training process follows three distinct stages:

• Stage 1 (Episodes 0–5K for Email, 0–10K for RoadCA): The policy quickly learns to satisfy constraints, increasing feasibility from 80% to 100% on Email and from 40% to 100% on RoadCA. This demonstrates the policy’s capacity to recover feasibility from scratch by optimizing the first term of the reward function.

• Stage 2 (Episodes 5K-15K for Email, 10k-35k for RoadCA): The focus shifts to minimizing cost (the second reward term). During this phase, total cost drops significantly—from 15,147.21 to 2,697.84 on Email, and from 64,453.49 to 9,265.72 on RoadCA—while feasibility remains above ~98%.

• Stage 3 (the remaining episodes): The training stabilizes, with both reward and cost showing low variance. For example, on RoadCA, reward converges to 3975.03 ± 37 and cost to 9265.72 ± 49, confirming efficient and stable convergence even on large-scale graphs.

These results highlight both the efficiency and scalability of the proposed RL refinement loop. We will include this new experiment, along with runtime analysis, in the final version of the paper.

Dear reviewer AUQg

We’re reaching out to kindly follow up on our rebuttal for submission #17634. We’ve done our best to address your comments carefully, and we truly appreciate the valuable feedback you provided. If you’ve had a chance to review our responses, we’d be grateful to know whether they have addressed your concerns, or if there’s anything we can further clarify.

Warm regards,

The Authors

Dear Reviewer,

As a quick follow-up, we’ve done our best to address all the points raised and are glad that most of your concerns have been resolved. Given these clarifications and enhancements, and that the core contribution—a modular, theoretically grounded, and scalable generative framework for QoSD—is now more clearly supported both empirically and theoritically, we would kindly ask whether you might be open to re-evaluating your initial assessment to see if our work may warrant a stronger rating.

we truly appreciate your time and engagement in this review process.

Warm regards, Authors

Q1, also W1. It’s unclear how errors in SPAGAN approximation affect the feasibility or optimality of generated solutions. Has the robustness of the pipeline been evaluated under noisy SPAGAN outputs?

Thank you for raising this important question. While SPAGAN shows strong generalization on graphs with similar topology (as illustrated in Appendix 3.3), we also address the out-of-distribution (OOD) setting through a robust safeguard—PPS-I, introduced in Section 3.3 (Inference Process) of the main paper. PPS-I is designed to refine any intermediate solution—including those from the RL refinement phase or PPS—using exact shortest-path computation via Dijkstra’s algorithm, thereby guaranteeing 100% feasibility of the final perturbation vector regardless of SPAGAN’s prediction accuracy.

To evaluate the pipeline’s robustness under degraded SPAGAN predictions, we conducted a controlled noise injection study. Specifically, we perturb SPAGAN’s predicted shortest-path values with varying levels of random noise (30%, 10%, 5%) and assess the downstream effects on PPS, RL, and PPS-I across two real-world datasets.

From the table, with number of pairs is 50, we observe four following keys:

1. PPS degrades under noisy predictions: feasibility drops by up to 22% (e.g., RoadCA with 30% noise), and cost increases (~20%) as perturbation budgets are allocated to irrelevant edges.

2. RL refinement recovers performance: RL improves feasibility and reduces cost over PPS by leveraging gradient signals in the latent space. For instance, in the RoadCA dataset at 30% noise, RL improves feasibility from 78% to 86%, and reduces cost from 13730 to 10985.

3. PPS-I ensures 100% feasibility in all cases: Regardless of SPAGAN noise level, PPS-I consistently restores feasibility via exact Dijkstra-based correction. This confirms the pipeline’s correctness guarantee.

4. Cost penalty of PPS-I is modest: Even in the worst-case (RoadCA, 30% noise), the PPS-I cost only increases by ~19% relative to the ideal (0% noise) case—i.e., 11061 vs. 9277—while feasibility remains perfect.

We will include this analysis to the main manuscript

Q2, also Limitation 2. It is not clear how well the RL-based refinement policy performs when topology or distribution shifts occur. Would retraining be needed for significantly different domains?

Since our RL policy operates in the latent space, its generalization ability depends on three main factors:

1. Robustness of SPAGAN’s predictions: As SPAGAN provides shortest-path approximations that guide the construction of initial solutions, any degradation here may propagate downstream. However, we have shown in Question 1 that even under significant prediction noise, the RL policy still improves feasibility and cost-effectiveness, demonstrating strong tolerance to upstream approximation error.

2. Generalization of Mix-CVAE: Since the latent space is shaped by a Mix-CVAE trained over solution trajectories, its ability to encode meaningful structures for unseen graphs is critical. Fortunately, generalization of VAE-style models across structurally similar data distributions is well-established in the literature [1,2], especially when trained on diverse samples.

3. Generalization of the policy network: The learned RL policy receives a latent vector as input and refines it toward better solution quality. Its ability to generalize to out-of-distribution (OOD) domains depends on whether the latent embeddings of unseen graphs lie within the training support. Prior works [3,4] in reinforcement learning (e.g., in offline RL and model-based control) show that policies can generalize across tasks when the representation space is sufficiently expressive—which applies here due to the modularity of our pipeline.

However, we also believe that if the target domain exhibits significantly different structural characteristics, retraining or fine-tuning the RL policy may indeed be beneficial to fully capture domain-specific latent dynamics. To our best knowledge, few-shot learning for domain adaptation of generative models is a rapidly advancing field [5,6,7], and such techniques can theoretically be incorporated into our framework to enhance transferability with minimal overhead.

[1] Abstract representations emerge naturally in neural networks trained to perform multiple tasks. Nature Communication 2023

[2] Beta-VAE: Learning Basic Visual Concepts with a Constrained Variational Framework. ICLR 2017

[3] Planning to Explore. ICML 2020

[4] Reinforcement Learning with Prototypical Representations. ICML 2021

[5] One-Shot Generative Domain Adaptation. ICCV 2023

[6] Make Your One-step Diffusion Model Better Than Its Teacher. ECCV 2024

[7] The Superposition Using the Itô Density Estimator. ICLR 2025

W2. Analysis of RL convergence behavior under different problem scales.

To address this, we provide detailed training statistics on real datasets with different scale: Email (1005 nodes 25571 edges) and RoadCA (1.96M nodes, 2.77M edges), both with clean SPAGAN's prediction.

As shown in the table, training proceeds in three stages based on episode count. In Stage 1 (Episodes 0–5K / 0–10K), the policy rapidly improves feasibility (maximizing term 1 of reward function) from 80% to 100% (Email) and from 40% to 100% (RoadCA), demonstrating its ability to learn constraint satisfaction from scratch. In Stage 2, the focus shifts to cost optimization (term 2 of reward function): total budget drops significantly from 15147.21 to 2697.84 on Email, and from 64453.49 to 9265.72 on RoadCA, while feasibility remains approximately 98%. Finally, in Stage 3, the reward and cost metrics converge with low variance, e.g., on RoadCA, reward stabilizes at 3975.03 ± 37 and budget at 9265.72 ± 49, confirming stable convergence even in large-scale settings.

Limitation 1. If the initial PPS-based solutions are suboptimal, the entire pipeline may converge to poor regions of the solution space

Our framework is specifically designed to reduce the impact of low-quality initial data by employing a latent-space refinement loop. Importantly, instead of discarding the highest-reward solutions generated by the RL phase, we incorporate them back into the pretrained solution set (as illustrated in Figure 1). This feedback loop serves two main purposes: (1) it enhances the training distribution for the Mix-CVAE in the next iteration, enabling the model to better capture informative solution patterns; and (2) it provides the RL policy with a richer and more structured latent space, allowing it to generate higher-quality solutions in subsequent cycles.

Dear reviewer GFJA,

We’re writing to kindly follow up regarding our rebuttal for our submission #17634. We’ve carefully addressed your comments and would be truly grateful to know whether our responses have helped resolve your concerns, or if there are any remaining questions we could further clarify.

Sincerely,

Q1. How do SPAGAN errors impact final outcomes? Have you conducted sensitivity analysis or exact-path verification to ensure constraint satisfaction? perhaps integrating a safeguard ?

We thank reviewer for a pointing that. Despite that SPAGAN demonstrates generalization on graphs with similar topology (Appendix 3.3), we still explicitly address the failure scenario where SPAGAN's predictions degrade under out-of-distribution (OOD) graphs—by incorporating a robustness safeguard: PPS-I, described in Section 3.3. PPS-I can refine any intermediate solution (including those from PPS or RL) using exact shortest-path computations via Dijkstra, thereby guaranteeing 100% feasibility of the final perturbation.

In response to the suggestion for a worst-case check using exact computation to verify that no path constraints are violated, we note that our framework already includes such a mechanism. Specifically, we define a feasibility check function that applies Dijkstra to compute the true shortest-path distances after perturbation. We then report the feasibility rate (%), measured as the percentage of source–target pairs whose shortest-path lengths exceed a given threshold $T$ (i.e., successfully disconnected). To further quantify robustness, we also conducted a sensitivity analysis by injecting controlled levels of random noise (30%, 10%, 5%) into SPAGAN’s predicted shortest-path values. This simulates various degrees of degraded model performance. We then evaluated the impact of this noise on feasibility (out of 50 pairs) and cost across all stages of our pipeline—PPS, RL, and PPS-I—on two benchmark datasets.

From the table, we observe:

• PPS degrades under noise: Higher SPAGAN noise reduces feasibility (up to –22%) and increases cost due to misallocated budget (e.g., RoadCA, 30% noise).

• RL improves robustness: RL boosts both feasibility and cost-efficiency over PPS by optimizing in latent space (e.g., RoadCA: 78% → 86%, cost drops from 13,730 → 10,985).

• PPS-I ensures 100% feasibility: It always restores feasibility via exact Dijkstra correction, regardless of noise level.

• PPS-I cost overhead is modest: Worst-case cost increase is ~19% (RoadCA: 11,061 vs. 9,277) while preserving perfect feasibility.

These show that Hephaestus is still robust to significant errors in SPAGAN’s predictions. We will include this analysis to the main paper

W1. Having a bad data in the first phase will likely have influence on the other phases

This is insightful point. Our framework is explicitly designed to mitigate the influence of poor-quality initial data through a latent-space refinement loop. In particular, our RL operates entirely in the latent space, where it learns to generate high-quality perturbation vectors that improve feasibility and cost-efficiency, as directly reflected by the differentiable reward function. Crucially, the best-performing solutions—i.e., those with the highest rewards—are not discarded after refinement. Instead, they are added back into the pretrained solution dataset (as shown in Figure 1) to enrich the diversity and quality of training data. This feedback mechanism has two key effects:

1. Mix-CVAE retraining in the next cycle benefits from improved latent samples, allowing it to better capture useful solution modes.

2. The RL policy, in turn, receives a more informative and structured latent space, enabling it to produce even better solutions in future cycles.

We empirically validate this self-reinforcing effect through the following table, which shows the cost reduction (%) achieved across successive refinement cycles. Specifically, we measure the relative improvement in cost (budget savings) after each cycle where the top‑$k$ highest-reward samples are added back to the solution set. Results on three benchmark datasets under four different feasibility thresholds $T$ clearly demonstrate monotonic improvement with more cycles:

• On Email with $T=260$, improvement saturates after 5 cycles, yielding up to ~18.5% cost reduction.

• On the large-scale RoadCA dataset with $T=260$, cost reductions continue to rise even after 8 cycles, peaking at over ~26% under high thresholds.

These results show that our pipeline is resilient to weak initial data.

W2, also Q2. Though generally well written, the paper’s readability occasionally suffers from density.

Thank you for the valuable suggestion. We agree that the Morph phase and latent-space RL refinement are technically dense components, and we appreciate the need for improved clarity. We will revise these sections to enhance readability by summarizing key math intuitively, e.g., describing how Mix-CVAE captures multimodal solution structures from PPS, and how the RL policy operates in latent space to improve feasibility and cost via a differentiable reward function. We will also highlight modularity in the pipeline.

Q3, also W3: Dynamic/Adaptive Scenario as Future Work for Hephaestus

Thank you for the suggestion. Although Hephaestus currently focuses on the static QoSD setting, its modular design naturally supports extensions to dynamic scenarios. For example, SPAGAN can be retrained incrementally as the network topology evolves, Mix-CVAE and RL can adapt via continual or meta-learning, and our add-back mechanism already forms a feedback loop for iterative refinement. As future work, we plan to explore online variants of Hephaestus that adapt strategies in response to changing network conditions or defenses, potentially framing the problem as a repeated game or adaptive attack.

Suitability. The reviewer questions whether the paper is better suited for networking venues (e.g., SIGCOMM, INFOCOM) rather than ML conferences.

While our work intersects with networking, its core contributions also lie in generative mixture modeling, latent-space RL, and structured optimization—central topics in the ML community. Furthermore, our framework is generalizable and can be applied to other challenging CO problems, as long as a reasonably good approximation method exists for the Forge phase. We believe this brings meaningful value to the ML community beyond the original QoSD problem.

Dear reviewer Tyqx,

We wanted to kindly follow up on our rebuttal for submission #17634. We’ve done our best to address your comments in detail, and we truly appreciate the time you took to raise them. If you’ve had a chance to review our responses, we would be grateful to know whether our clarifications have resolved your concerns, or if there are any remaining questions or points you’d like us to elaborate on.

Warm regards,