The gist of HyCO
HyCO — Hybrid Neural Solver for Combinatorial Optimization. The method builds a solution prefix using an RL solver. It then adaptively switches to a conditional diffusion model, which completes the remaining decisions. This hybrid solves neural combinatorial optimization problems. Its goal is to combine the strengths of two classes of solvers.
The paper is available as arXiv:2609.07990. Authors: Yuheng Li, Di Yang, Haipeng Chen, Yanhai Xiong. The preprint is categorized under cs.LG and cs.AI. The authors submitted version v1 on 7 Sep 2026. This information helps locate the original source and verify the details.
Practical takeaway: HyCO does not replace one solver with another; it manages the transition between them.
Where standalone strategies fail
Sequential RL solvers and global DM solvers exhibit complementary failure modes. This is reflected in optimization regret.
| Solver class | Strength | Weakness |
|---|---|---|
| Sequential RL | Low marginal regret in the early stages of solution construction | Errors accumulate over the horizon; regret grows superlinearly |
| Global DM | Avoids accumulation over the horizon | Linear or sublinear regret with respect to the dimensionality of the remaining unsolved subspace |
Takeaway: the failure modes do not coincide. RL performs well early on but suffers from horizon effects. DM does not accumulate horizon-related errors, but pays a price for the size of the remaining problem. Hybridization takes advantage of this gap.
Theoretical framework for switching
The authors build a unified theoretical framework for error scaling. Under explicit assumptions about how errors scale, the framework proves two results.
- The hybrid structure yields strictly lower expected regret than either of the two baseline approaches on its own.
- There is a unique optimal switching step that minimizes the hybrid's regret.
The authors define the optimal step in terms of expected regret. It cannot be computed directly for individual trajectories. A practical trigger is therefore needed.
Takeaway: the theory explains why the hybrid helps and when to initiate the handoff. It does not provide a ready-made formula for every trajectory.
How the adaptive trigger works
HyCO uses a lightweight adaptive trigger. The trigger combines policy entropy and RL-DM divergence. These signals detect a regime shift at the trajectory level. They serve as a practical proxy, which is needed because the optimal switching step cannot be computed for an individual trajectory.
The trigger ends the RL prefix. The conditional DM completes the remaining decisions. The practical criterion is to monitor policy entropy and RL-DM divergence. These signals indicate a regime shift and the handoff point. The trigger remains lightweight and adaptive.
Experiments and selection criteria
In experiments across diverse benchmarks, HyCO delivers consistent improvements over both baseline solvers. The results also confirm the empirical effectiveness of the adaptive trigger.
Practical selection criterion: you need an inference algorithm for combinatorial optimization that uses RL for the early prefix and DM for the remaining decisions. The hybrid reduces expected regret relative to each baseline approach. HyCO is suitable as a switching layer on top of RL search and diffusion-based completion. It manages the transition between them.
