Validated Intent Compilation for Constrained Routing in LEO Mega-Constellations

Yuanhang Li

cs.CRApr 8, 2026

Validated Intent Compilation for Constrained Routing in LEO Mega-Constellations

Authors: Yuanhang Li

Abstract

Operating LEO mega-constellations requires translating high-level operator intents ("reroute financial traffic away from polar links under 80 ms") into low-level routing constraints -- a task that demands both natural language understanding and network-domain expertise. We present an end-to-end system comprising three components: (1) a GNN cost-to-go router that distills Dijkstra-quality routing into a 152K-parameter graph attention network achieving 99.8% packet delivery ratio with 17x inference speedup; (2) an LLM intent compiler that converts natural language to a typed constraint intermediate representation using few-shot prompting with a verifier-feedback repair loop, achieving 98.4% compilation rate and 87.6% full semantic match on feasible intents in a 240-intent benchmark (193 feasible, 47 infeasible); and (3) an 8-pass deterministic validator with constructive feasibility certification that achieves 0% unsafe acceptance on all 47 infeasible intents (30 labeled + 17 discovered by Pass 8), with 100% corruption detection across 240 structural corruption tests and 100% on 15 targeted adversarial attacks. End-to-end evaluation across four constrained routing scenarios confirms zero constraint violations with both routers. We further demonstrate that apparent performance gaps in polar-avoidance scenarios are largely explained by topological reachability ceilings rather than routing quality, and that the LLM compiler outperforms a rule-based baseline by 46.2 percentage points on compositional intents. Our system bridges the semantic gap between operator intent and network configuration while maintaining the safety guarantees required for operational deployment.

Figures & tables

Panel of Figure 1 — Fig. 1: End-to-end system architecture. Operator intents are compiled to typed ConstraintPrograms and verified by the 8-pass validator. Accept (solid) proceeds to grounding and GNN routing; Reject (dashed) triggers repair; Abstain (dotted) defers to Dijkstra.

Type	Target	Grounding
disable_node	node: $n$	$M_{V}[n]\leftarrow 0$
disable_plane	plane: $p$	$M_{V}[pS{:}(p{+}1)S]\leftarrow 0$
disable_edge	edge: $(u,v)$	$M_{E}[(u,v)]\leftarrow 0$
avoid_latitude	edges	$M_{E}\leftarrow 0$ if $\|\phi\|>\theta$
avoid_region	region: $r$	$M_{E}\leftarrow 0$ if $u{\in}\mathcal{N}_{r}{\lor}v{\in}\mathcal{N}_{r}$
reroute_away	node: $n$	$M_{V}[n]\leftarrow 0$ (transit)

TABLE I: ConstraintProgram hard constraint types and their grounding semantics.

Panel of Figure 3 — Fig. 2: 8-pass validation pipeline. Passes 1–4 check structural validity; 5–7 check semantic consistency; Pass 8 constructs routing witnesses (BFS, Dijkstra, Edmonds-Karp). Solid/dashed/dotted arrows indicate Accept/Reject/Abstain outcomes.

Scenario	GNN PDR	Dijkstra PDR	Random PDR
Uniform	99.75%	99.75%	0.90%
Hotspot	99.99%	99.99%	2.36%
Regional	99.94%	99.94%	5.49%
Polar	100.0%	100.0%	1.88%
Flash	99.77%	99.77%	0.89%

TABLE II: GNN cost-to-go routing vs. Dijkstra baseline (unconstrained).

Config	Compiled	Types	Full Match	Latency
Full pipeline	97.9%	91.7%	86.2%	15.7s
No verifier	100.0%	93.8%	91.7%	13.8s
No repair	92.9%	86.7%	84.6%	13.8s
Zero-shot	92.5%	71.7%	15.4%	34.2s

TABLE III: Compiler ablation study on 240-intent benchmark (uniform random edge delays; distance-based re-run yields 98.4%/87.6% for the full pipeline—see Table VI ).

Safety (unsafe = infeasible ACCEPT ):
	Accept	Reject	Abstain
Single ( $n$ =80)	10	5	65
Compositional ( $n$ =100)	40	25	35
Conditional ( $n$ =30)	8	2	20
Infeasible ( $n$ =30)	0	22	8
Total ( $n$ =240)	58	54	128

TABLE IV: Three-way validator confusion matrix (240-intent benchmark, 8-pass pipeline). 0% unsafe acceptance across all categories.

Scenario	Reach.	Raw PDR		Reachable PDR
		GNN	Dijkstra	GNN	Dijkstra
Baseline	100%	99.8%	—	99.8%	—
Node failure	100%	98.7%	97.8%	98.7%	97.8%
Plane maint.	100%	70.5%	70.2%	70.5%	70.2%
Polar avoid.	24.0%	34.6%	47.9%	100%	100%
Compositional	24.0%	34.3%	47.1%	100%	100%

TABLE V: Reachability separation analysis. Both GNN and Dijkstra achieve 100% delivery on reachable pairs; raw PDR gaps reflect topology reachability, not routing quality.

Full match by category:
Metric	Rule-Based	LLM 4B	LLM 9B
Compiled	100.0%	59.6%	98.4%
Types Match	67.1%	55.4%	91.7%
Full Match	56.7%	54.2%	87.6%
Avg Latency	0.05ms	204s	15.7s
Single	76.2%	—	89.5%

TABLE VI: Intent compiler comparison (193 feasible intents; 17 routing-infeasible excluded). LLM 9B outperforms rule-based by 46.2pp on compositional intents.

Category	N	Compiled	Full Match
Single	20	100%	95.0% (19/20)
Compositional	5	100%	40.0% (2/5)
Conditional	8	100%	75.0% (6/8)
Ambiguous	5	100%	qualitative: 5/5
Scorable total	33	100%	81.8% (27/33)

TABLE VII: Out-of-distribution generalization on paraphrased intents (38 total: 33 scorable + 5 ambiguous). The compiler maintains 81.8% full match accuracy with only 4.4pp degradation from template intents, demonstrating robust generalization to novel phrasings.

Metric	Qwen 4B	Qwen 9B
Compiled	59.6%	98.4%
Types Match	55.4%	91.7%
Full Match	54.2%	87.6%
First-try Rate	47.1%	77.9%
Avg Latency	204.4s	15.7s

TABLE VIII: Cross-model scaling: 4B vs 9B parameter LLM on the full 240-intent benchmark. The 9B model substantially outperforms the 4B model across all metrics.

Planes Off	Capacity	GNN PDR	Dijkstra PDR	$\Delta$
1	5%	81.1%	80.9%	+0.22
2	10%	41.1%	41.1%	0.00
3	15%	36.8%	36.8%	0.00
5	25%	45.3%	45.3%	0.00
7	35%	42.5%	42.5%	0.00
10	50%	11.4%	11.4%	0.00

TABLE IX: GNN vs Dijkstra PDR across plane-removal severity (20 sats/plane, 3-seed avg). GNN matches Dijkstra within 0.22pp at all levels.

Configuration	GNN PDR	Dijkstra PDR	$\Delta$
550 km / 53 ∘ (training)	99.75%	99.75%	0.00
1200 km / 53 ∘ (OOD)	99.75%	99.75%	0.00
550 km / 97 ∘ SSO (OOD)	45.18%	99.09%	$-$ 53.91

TABLE X: Zero-shot cross-constellation GNN generalization. GNN generalizes to altitude changes but collapses on SSO 97 ∘ where inclination alters ISL geometry.

Threshold	Edges Removed	GNN PDR	Dijkstra PDR	$\Delta$
30 ∘	28.8%	38.17%	99.75%	$-$ 61.58
40 ∘	20.5%	54.08%	99.75%	$-$ 45.67
45 ∘	15.8%	65.20%	99.75%	$-$ 34.55
50 ∘	9.8%	80.37%	99.75%	$-$ 19.38

TABLE XI: GNN robustness under polar exclusion zones. GNN degrades proportionally to edge removal while Dijkstra maintains 99.75% PDR, confirming topology-specific learned shortcuts.

By certification status:
Category	$n$	Median	P95	Max
All programs	240	0.720 ms	1.580 ms	1.898 ms
With flow selectors	98	1.059 ms	1.738 ms	1.898 ms
Topology-only	142	0.437 ms	1.501 ms	1.629 ms
Accepted	58	1.044 ms	1.738 ms	1.812 ms
Rejected	32	1.135 ms	1.757 ms	1.898 ms

TABLE XII: 8-pass validator runtime (240-intent benchmark). Median under 1 ms; worst case below 2 ms, confirming negligible overhead for real-time deployment. Certification status counts Pass 8 outcomes only (22 early-pass rejects excluded).

Scenario	GNN PDR	Dijkstra PDR
Node failure	98.69%	97.83%
Plane maintenance	70.51%	70.22%
Polar avoidance	34.63%	47.86%
Compositional	34.27%	47.07%

TABLE XIII: End-to-end constrained routing (3 seeds

\times

20 steps).

Explore similar work

Aug 23, 2026

Advanced LLM-Enhanced Intent-Based 5G Network Management using Dynamic Semantic Routes

As the use of Artificial Intelligence (AI) and Large Language Models (LLMs) is becoming common in everyday applications, their ability to interpret natural language has increased significantly. An emerging application of AI is integration with network management and orchestration practices. An instance of this integration is LLM-enhanced intent-based networking, where network operators will control a network using natural language. This work presents the use of dynamic routes with a semantic router to identify an intent from a network operator's prompt and extract necessary details for intent fulfillment in intent-based 5G+ core networks. Furthermore, the performance of static route selection is assessed by evaluating multiple encoders and dynamic route detail extraction accuracy against a series of realistic operator prompts. The presented results show that static and dynamic routes are successful in detail extraction and schema formatting.

Thomas Benton Townsend, Dimitrios Michael Manias

The Department of Computer Science and Engineering, Mississippi State University

Intent-Based Networking LLM Routing Wireless Communications

Ask PDF

Jul 22, 2026

AlphaRoute: Large Language Models as Semantic Optimizers for Multi-Objective Routing

Very Large Scale Integration (VLSI) global routing is an NP-hard combinatorial optimization problem requiring signal net assignment across capacity-constrained 3D grids while minimizing congestion, wirelength, and via transitions. Because traditional heuristics rely on static penalty schedules that fail on complex congestion topologies, we present AlphaRoute: a multi-objective adaptive search framework reformulating rip-up and reroute (R&R) into a dynamic optimization system. We introduce SHAP-based overflow decomposition to isolate per-net congestion, driving targeted subgraph extraction via 3D Dijkstra maze routing and an adaptive PathFinder policy. Crucially, AlphaRoute employs Large Language Models (LLMs) as semantic policy optimizers. Bounded by a deterministic knowledge graph, the LLMs interpret congestion metrics to dynamically adjust penalty parameters. Evaluated on ISPD 2025 benchmarks, AlphaRoute reduces overflow by 98.6% on MEMPOOL. On the constrained ARIANE design, we achieve an overflow of 146,109 (a 29.8x reduction in overflow over the state of the art), yielding a penalized score of S_orig = 0.0538 versus the State-of-the-art (SOTA) 1.780. These results demonstrate that superior algorithmic search geometry can overcome the latency of interpreted Python implementations.

Kabir Murjani, Mishri Bhavsar, Manish I. Patel +1

Department of Electrical Engineering, Institute of Technology, Nirma University, Ahmedabad, India · Department of Electronics and Communication Engineering, Institute of Technology, Nirma University, Ahmedabad, India · Center for Semiconductor Microelectronics, Arizona State University, Tempe, Arizona, USA

Automated Heuristic Design Large Language Model-Guided Optimization Electronic Design Automation Combinatorial Optimization Multi-Objective Optimization

Ask PDF

Mar 28, 2026

From Inference Routing to Agent Orchestration: Declarative Policy Compilation with Cross-Layer Verification

The Semantic Router DSL is a non-Turing-complete policy language deployed in production for per-request LLM inference routing: content signals (embedding similarity, PII detection, jailbreak scoring) feed into weighted projections and priority-ordered decision trees that select a model, enforce privacy policies, and produce structured audit traces -- all from a single declarative source file. Prior work established conflict-free compilation for probabilistic predicates and positioned the DSL within the Workload-Router-Pool inference architecture. This paper extends the same language from stateless, per-request routing to multi-step agent workflows -- the full path from inference gateway to agent orchestration to infrastructure deployment. The DSL compiler emits verified decision nodes for orchestration frameworks (LangGraph, OpenClaw), Kubernetes artifacts (NetworkPolicy, Sandbox CRD, ConfigMap), YANG/NETCONF payloads, and protocol-boundary gates (MCP, A2A) -- all from the same source. Because the language is non-Turing-complete, the compiler guarantees exhaustive routing, conflict-free branching, referential integrity, and audit traces structurally coupled to the decision logic. Because signal definitions are shared across targets, a threshold change propagates from inference gateway to agent gate to infrastructure artifact in one compilation step -- eliminating cross-team coordination as the primary source of policy drift. We ground the approach in four pillars -- auditability, cost efficiency, verifiability, and tunability -- and identify the verification boundary at each layer.

Huamin Chen, Xunzhuo Liu, Bowei He +1

vLLM Semantic Router Project · MBZUAI · McGill University +1

LLM Routing LLM Agent Orchestration AI Agent Governance Formal Verification AI Agent Auditing

Ask PDF