In-Context Learning Characterization of Navigation and GNSS Foundation Models: A Theoretical Framework for Safety-Critical Positioning

Foundation models for navigation and Global Navigation Satellite Systems (GNSS) exhibit a striking empirical dichotomy: transformer-based architectures achieve remarkable performance on trajectory prediction and state estimation, yet consistently struggle with fault detection, cycle slip identification, and integrity monitoring. Despite the proliferation of navigation transformers, no theoretical framework explains which navigation tasks admit efficient in-context learning (ICL) and which are fundamentally intractable. This gap has critical implications for safety-critical applications including aviation, autonomous vehicles, and maritime navigation, where theoretical guarantees are essential for certification. We address this gap by extending the ICL characterization framework to navigation and GNSS domains. Our main result is the Navigation Dichotomy Theorem: every natural navigation function class falls into exactly one of two categories. Type A (ICL-Easy) tasks—including position estimation, velocity estimation, atmospheric delay modeling, and trajectory prediction—possess additive sufficient statistics computable by attention mechanisms, achieving sample complexity matching the statistical optimum. Type C (ICL-Hard) tasks—including satellite fault detection, cycle slip detection, spoofing detection, and integrity monitoring—require combinatorial sufficient statistics over C(M,J) fault hypotheses, rendering them intractable for standard ICL when the number of faults J exceeds the threshold J* ≈ 2–3 (for navigation; J* ≈ 2–4 across GeoAI domains). Building on recent advances in chain-of-thought (CoT) reasoning, we prove that CoT prompting provides a mechanism to overcome ICL-Hard barriers in navigation. We establish that T = Ω(J) tokens are necessary and sufficient for J-fault detection, with a navigation-specific token multiplier κnav ≈ 3.5. The effective hardness threshold shifts to J*CoT(T) ≈ J* + T/κnav, enabling detection of up to 7 simultaneous faults with 20 reasoning tokens. We provide complete classification of 32 navigation tasks across six categories (Table 6), derive seven testable predictions for navigation transformer behavior, and analyze implications for safety certification under aviation (DO-229D/DO-253D), automotive (ISO 26262), and maritime (IMO) standards. Our results establish that hybrid architectures—combining ICL for state estimation with explicit algorithms for integrity monitoring—are not merely practical conveniences but fundamental computational necessities. This work completes a seven-paper theoretical program characterizing ICL across all major geospatial AI domains, establishing a unified science of when and why foundation models succeed or fail on Earth observation and navigation tasks.