Source-linked AI summary
CIPHEUR: LLM-Guided Structural Search Control for Conflict-Graph Optimization
Yuqing Cheng, Yan Jia, Yanjie Song, Xiaolu Liu, Lining Xing, Feng Yao
TL;DR
Conflict-graph search needs interventions that address blocking conflicts and account for delayed recovery. CIPHEUR uses LLM-guided SIUs to coordinate targeting, intervention, and continuation, with offline and online control modes. In satellite–ground scheduling, it improves on the greedy baseline and CHILS in the reported comparisons.
Problem
Conflict-graph search control must connect observed conflicts to actions, since an intervention’s value depends on what it displaces and what combinations it makes accessible.
Source: §1 · pp. 1–2Method
CIPHEUR uses SIUs to jointly specify a structural target, intervention, and continuation, with LLM-generated offline policies or online contextual choices.
Source: §1 · p. 2Results
14.84% higher mean scheduled contact duration than GWMIN; CIPHEUR-online also outperforms CHILS in all 40 paired runs.
Source: §1 · p. 2Takeaways & Limitations
The completed experiments show terminal competitiveness, stronger late-search progress for the online configuration, and a reconstruction–recovery pattern that motivates interval-level feedback.
Source: §5 · p. 9Evidence covers a few contact sources and a 12-position fine-control screen; synchronous-control and online cross-source tests remain unfinished.
Source: §4.4 · p. 9
Abstract
from arXiv · showhide
Conflict-graph search can stagnate despite effective operators when interventions fail to address the conflicts blocking progress. A disruptive intervention may also require further search before its value emerges. We propose CIPHEUR, a large language model (LLM)-guided framework that connects conflict evidence to coordinated intervention and recovery through Structured Intervention Units (SIUs). The shared control interface supports offline synthesis of executable policies and online contextual decisions. Asynchronous online control sustains native search during inference, while all policies preserve the original objective and feasibility constraints. Across eight satellite-ground scheduling conflict views with five runs per view and a 900-second evaluation cap, CIPHEUR-online achieves the highest mean objective among 11 configurations and increases mean scheduled contact duration by 14.84% over the greedy baseline GWMIN. It exceeds the strongest external per-view mean in seven of eight views and outperforms CHILS in all 40 paired runs. Within the same runs, its normalized objective improvement from 360 to 900 seconds is 1.50 to 1.86 times that of the two programmatic controllers. A separately frozen, one-shot LLM-generated controller also improves the mean objective over CHILS without runtime model calls. Together, these results demonstrate how structural search control translates LLM design knowledge and contextual reasoning into improved solution quality and sustained search progress.
1 Introduction
CIPHEUR treats conflict-graph search control as a joint choice of where to intervene and how search should continue. In satellite–ground scheduling, it improves objective outcomes through offline and online control over a shared SIU interface.
Motivation
- Conflict-graph search control must account for which activities an intervention displaces and which combinations it makes accessible.Reconstruction can reduce immediate trajectory value while creating later opportunities for improvement or exchange.Source: §1 · pp. 1–2
- LLMs can construct executable heuristics from problem descriptions and feedback, or make state-dependent heuristic choices during optimization.CIPHEUR’s common control abstraction connects these capabilities to structural change in conflict-graph search.Source: §1 · p. 2
Approach
- CIPHEUR’s Structured Intervention Units (SIUs) jointly specify a structural target, an intervention, and its continuation, using feedback from executed periods to guide later choices.Candidate SIUs are grounded in conflicts affecting current trajectories.Source: §1 · p. 2
Control modes
- CIPHEUR uses offline LLM synthesis to create executable policies and online LLM reasoning to choose SIUs from current structural evidence and search history.Both modes share an interface that preserves the original objective and feasibility constraints; asynchronous online decisions let native search continue during inference.Source: §1 · p. 2
Results
- 14.84% higher mean scheduled contact duration than GWMIN; CIPHEUR also outperforms CHILS in all 40 paired runs, and a frozen one-shot controller improves mean objective without runtime calls.The evaluation covers eight constraint views, five runs per view, a 900-second cap, and 11 configurations.Source: §1 · p. 2
2 Related Work
CIPHEUR builds on structural guidance, adaptive heuristic selection, and LLM-based algorithm design, while making structurally grounded intervention and recovery a shared control task for generated policies and online LLMs.
2.1 Independent-Set Search and Structural Guidance
- CIPHEUR uses resource-specific blocking evidence to select search interventions, complementing local moves, solution exchange, and vertex-level guidance.Prior examples include METAMIS’s local moves and path relinking and CHILS’s cooperation based on solution differences.Source: §2.1 · p. 2
2.2 Adaptive and Temporally Extended Search Control
- SIUs combine structural targeting with an explicit intervention–recovery sequence and feedback on quality changes over that sequence.This extends adaptive control approaches such as selection hyper-heuristics and temporally extended decisions formalized by the options framework.Source: §2.2 · p. 2
2.3 LLM-Based Algorithm Design and Search Decisions
- CIPHEUR makes target, intervention, and recovery the common decision task for reusable offline controllers and online LLMs.The shared SIU space supports current-context choices while feedback tracks solution-quality changes across intervention–recovery periods.Source: §2.3 · p. 3
3 CIPHEUR
CIPHEUR uses LLMs to guide structural search control through SIUs, which coordinate a target, intervention, and continuation. It links structural evidence and execution feedback to offline or online decisions over a shared search interface.
3 CIPHEUR
- CIPHEUR uses LLM capabilities to construct search controllers offline or choose interventions online through a common loop of structural observation, SIU selection, native execution, and feedback.Source: §3 · p. 3
3.1 Problem and Control State
- CIPHEUR operates on a fixed resource-labelled conflict graph using four persistent trajectories initialized from feasible states.Source: §3.1 · p. 3
3.2 From Conflict Evidence to SIUs
- Target-specific blocker evidence grounds SIUs that jointly bind a trajectory and anchor to an intervention template and continuation actions.The observer records blocker counts, weights, and resource relationships; directed SIUs reconstruct the target once on entry, then continue with Spread or Merge.Source: §3.2 · p. 4
3.3 Feedback over Executed Interventions
- Feedback intervals begin at actual installation and retain the initiating observation, while incumbent gain and population change capture progress, disruption, and recovery.Source: §3.3 · p. 4
3.4 Two LLM Policy Realizations
- Offline LLM synthesis produces local executable control, while online LLM reasoning selects SIUs from current context; both modes share the native executor.Offline construction precedes the timed solve; online decisions use a fixed instruction and current control context.Source: §3.4 · pp. 4–5, Figure 4 · p. 5
3.5 Asynchronous Execution and Complete Procedure
- Online replies are checked before installation while native search advances during inference; feasible incumbents retain nondecreasing original-objective value.Source: §3.5 · pp. 5–6
4 Experiments
Across eight constraint views of one satellite–ground scheduling source, the experiments compare 11 configurations under a 900-second cap. CIPHEUR-online leads the terminal-quality comparison, while additional tests examine late-search progress, control contributions, recovery, and offline synthesis.
4.1 Instances, Comparators and Protocol
- The evaluation uses five runs per view across eight constraint views, four matched trajectories, and a 900-second outer wall cap.Online requests begin at 20 seconds and recur at 40-second opportunities, up to 21 requests; inference overlaps native search.Source: §4.1 · p. 6
4.2 Final Quality and Late-Search Improvement
- CIPHEUR-online records the highest mean, 1,138,760.369 contact-seconds, and best average rank, 1.75; it exceeds the strongest external mean in seven views and wins all 40 CHILS pairs.The strongest external reference is CHILS in six views, LS in H1200, and Feasibility Jump in H1800; online trails Feasibility Jump by 0.148% in H1800.Source: §4.2 · p. 6, Table 1 · p. 7
- Online’s normalized shortfall improvement from 360 to 900 seconds is 1.50 times EXP’s and 1.86 times VAL’s, despite a larger shortfall at 360 seconds.At the strictest positive target, 0.05%, online attains 10/40 runs versus 6/40 for each comparator; whole-run shortfall area against EXP is near-equal.Source: §4.2 · p. 6, Table 2 · p. 7, Figure 7 · p. 8
4.3 Control Contributions and Observed Recovery
- In a fresh 12-pair mechanism screen, full online control gains 4,241.212 contact-seconds over SIU-Off and 1,393.654 over Fixed-Spread.Smaller contrasts against Random-SIU, No-Struct, and Single-Op are seed-dependent and provide limited component-specific evidence.Source: §4.3 · p. 7, Figure 6 · p. 7
- Across 401 directed reseeds, the population mean is 2,417.631 seconds below entry at +5 seconds and 78.8% recovered by +24 seconds, while the incumbent improves by 226.823 seconds.These are observational changes and do not isolate reseeding’s causal effect; all 401 events remain installed through +24 seconds.Source: §4.3 · p. 8, Figure 8 · p. 8
- During 840 online calls, 99.92% of pending intervals overlap native work, sustaining search during inference rather than demonstrating additive time savings.The median request-to-receipt latency is 11.06 seconds; the overlap totals 9,837.360 seconds.Source: §4.3 · p. 8
4.4 Offline Synthesis and Cross-Source Use
- The frozen one-shot GEN controller completes 40 runs with zero deployment model calls and improves the mean over CHILS by 1,404.572 seconds (0.124%).On L003, only EXP, VAL, and CHILS arms are complete; online and GEN cross-source runs remain incomplete.Source: §4.4 · pp. 8–9, Table 3 · p. 9
5 Conclusion
CIPHEUR treats conflict-graph search control as a joint decision over structural targets, interventions, and continuation. Completed experiments show broad terminal competitiveness, stronger late-search progress for the online configuration, and a reconstruction–recovery pattern that motivates interval-level feedback.
5 Conclusion
- Completed experiments show broad terminal competitiveness, stronger late-search progress for the online configuration, and a reconstruction–recovery pattern motivating interval-level feedback.Source: §5 · p. 9
- Structured Intervention Units give generated programs and online LLMs a common executable task while native search preserves the original optimization semantics.Source: §5 · p. 9
- A frozen one-shot controller demonstrates deployment without runtime model calls, and the findings identify structural search control as a practical way to use LLM design knowledge and contextual reasoning in combinatorial optimization.Source: §5 · p. 9