CIPHEUR: LLM-Guided Structural Search Control for Conflict-Graph Optimization
Authors: Yuqing Cheng, Yan Jia, Yanjie Song, Xiaolu Liu, Lining Xing, Feng Yao
Organizations: National University of Defense Technology, Changsha, China · Dalian Maritime University, Dalian, China · Jiangsu University of Technology, Changzhou, China
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.
Figures & tables
Figure 1. CIPHEUR motivation. Conflict evidence guides structural intervention and recovery in satellite–ground scheduling. Satellite–ground contact conflicts form a weighted independent-set problem. Offline and online controllers select structural interventions that redirect an ongoing search, followed by recovery.
Figure 2. CIPHEUR overview. Both LLM modes select from one SIU registry; native search continues during online inference. Four stages link structural observation, SIU construction, alternative policy modes and execution. A separate native-search lane continues during asynchronous online inference.
Figure 3. SIU grounding. (a) One anchor has different blockers across trajectories. (b) Online inference overlaps the old SIU; new feedback starts at installation auk . The same unselected anchor has different selected blockers in two feasible trajectories. A timeline shows old-plan execution during inference and a new feedback interval beginning only at installation.
Figure 4. Offline controller construction and online SIU selection. Both modes share the native executor. The offline LLM turns a design specification into choice and update code. The online LLM takes system instructions and current JSON context and returns snapshot ID, plan ID, hypothesis and evidence. Both outputs lead to shared native execution.
Method
Mean ↑
H340
H680
H1200
H1800
M340/1200
M680/1200
M1200/340
M1200/680
Rank ↓
Ev ( 103 s)
—
1624.295
1246.823
884.035
684.860
1259.316
1064.712
1261.095
1062.766
—
External baselines
CHILS
1,134.943
0.00
0.00
-0.63
-0.41
0.00
0.00
0.00
0.00
5.38
Feasibility Jump ( Luteberget and Sartor, 2023 )
1,131.650
-0.06
-0.25
-1.40
0.00
-0.31
-0.59
-0.27
-0.43
6.12
StableSolver LS ( StableSolver Contributors, 2026 )
Table 1. L002 terminal quality (five runs/view). View entries are gains over Ev (%); Ev and Mean use 103 contact-s. Rank averages within-view ranks; bold marks bests. † GEN was separately frozen; LS/LNS use process repeats.
Figure 5. L002 progress (40 runs). The main axis uses 20:1 compression below 1.05×106 contact-s; inset: 300–900 s. CHILS, FJ and FastWVC are separate reruns. A full-range plot contains an internal 300–900 second enlargement. Solid method-colored diamonds mark terminal-only comparison means; lines show recorded incumbent trajectories.
Late shortfall/AOC (%) and improvement (pp)
Mode
gˉ360↓
gˉ900↓
Δ360:900↑
AOC ↓
Online
0.23746
0.12698
0.11048
0.24065
Off-EXP
0.22471
0.15113
0.07359
0.24177
Off-VAL
0.21849
0.15914
0.05936
0.25226
Table 2. Late progress, attainment, and matched control effects. Control Δ is online minus control.
Figure 6. Matched mechanism screen. Each dot is an online-minus-control difference (12 pairs per control); diamonds mark means and the right column lists positive pairs. All twelve paired differences favor online against SIU-Off. Nine favor online against Fixed-Spread, while the three finer comparisons include both positive and negative differences.
Figure 7. Search progress and attainment. (a) Mean online-minus-programmatic quality at 12 saved checkpoints. (b) Counts across nine terminal thresholds (40 runs); inset: three strictest positive thresholds. Online is slightly behind at the start of the late-search window and ahead at the final checkpoints. At 900 seconds it attains the strictest positive reference-gap target in ten runs, against six for each programmatic comparator. The historical incumbent increases, mean population value initially decreases and then recovers, and population diversity rises after reseeding.
View
CHILS
Off-EXP
Off-VAL
AU-H
1,623.290
1,627.711
1,627.468
AU-M
1,259.639
1,264.050
1,263.209
AP-H
1,690.812
1,692.549
1,692.806
AP-M
1,283.948
1,284.905
1,284.875
Mean ↑
1,464.422
1,467.304
1,467.090
Gain (%)
—
+0.197
+0.182
Table 3. L003 cross-source means ( 103 contact-s; three runs per view). Gains and matched wins are relative to CHILS.
School of Computer Science and Technology, School of Computer Science and Engineering · School of Information Science and Engineering, Sun Yat-sen University · College of Computer Science, College of Computer Science