""" Unit test suite for Q-TensorFormer Theoretical Foundations (Theorems 1-4). Validates: - Theorem 1: Lipschitz Bound on Nested Tensor-Train Core Truncation Error - Theorem 2: Discrete-Time Lyapunov Stability & Anti-Chattering of Hysteresis PID Controller - Theorem 3: Information-Preserving Needle Retention in Semantic Anchor KV Cache - Theorem 4: Sub-Linear Regret Scaling of Contextual Bandit Token Resource Allocator - Attention Lipschitz Continuity - Hypervolume Monotonicity """ import math import pytest import torch import numpy as np from src.theory import TheoreticalAnalyzer from src.semantic_kv_cache import SemanticAnchorKVCache from src.bandit_allocator import ContextualBanditAllocator from src.dynamic_grid import DynamicGridController def test_theorem_1_tt_truncation_bound(): """Verify Theorem 1: empirical Frobenius error is bounded by analytical bound.""" torch.manual_seed(42) # Define 3-core TT tensor: shapes (1, 4, 4, 8), (8, 4, 4, 8), (8, 4, 4, 1) cores = [ torch.randn(1, 4, 4, 8) * 0.1, torch.randn(8, 4, 4, 8) * 0.1, torch.randn(8, 4, 4, 1) * 0.1, ] for target_rank in [4, 2, 1]: res = TheoreticalAnalyzer.compute_tt_truncation_bound(cores, target_rank=target_rank) assert res["bound_satisfied"], ( f"Theorem 1 bound violated at rank {target_rank}: " f"empirical={res['empirical_frob_error']:.6f} > bound={res['theoretical_bound']:.6f}" ) assert res["relative_frob_error"] <= 1.0 def test_theorem_2_lyapunov_stability(): """Verify Theorem 2: Lyapunov energy decay and zero chattering under hysteresis.""" np.random.seed(42) hysteresis_tau = 0.15 optimal_price = 1.0 # Simulate closed-loop PID error dynamics with decaying perturbation shadow_prices = [1.8] errors = [0.8] kp, ki, kd = 0.1, 0.01, 0.05 integral = 0.0 prev_err = 0.8 for t in range(50): curr_price = shadow_prices[-1] err = 0.8 * math.exp(-0.08 * t) * math.cos(0.2 * t) # Apply hysteresis filter if abs(err) < hysteresis_tau: effective_err = 0.0 else: effective_err = err integral += effective_err derivative = effective_err - prev_err prev_err = effective_err delta_p = kp * effective_err + ki * integral + kd * derivative next_price = max(0.0, curr_price - 0.5 * delta_p) shadow_prices.append(next_price) errors.append(err) res = TheoreticalAnalyzer.verify_lyapunov_stability( shadow_prices=shadow_prices, errors=errors, hysteresis_threshold=hysteresis_tau, optimal_price=optimal_price, ) assert res["asymptotically_stable"], f"Lyapunov stability rate too low: {res['stability_rate']}" assert res["zero_chattering_verified"], f"Chattering detected inside deadband: {res['chattering_events_in_deadband']}" assert res["lyapunov_energy_decayed"], "Lyapunov energy failed to decay over horizon" def test_theorem_3_semantic_anchor_guarantee(): """Verify Theorem 3: 100% retention of designated semantic needle anchors.""" torch.manual_seed(42) cache = SemanticAnchorKVCache( max_capacity=32, sink_size=4, entropy_threshold=1.5, surprise_threshold=2.5, ) seq_len = 64 d_model = 32 d_head = 16 n_heads = 2 # Insert designated needles at known positions needle_positions = [0, 1, 10, 25] for pos in range(seq_len): k = torch.randn(1, n_heads, 1, d_head) v = torch.randn(1, n_heads, 1, d_head) # High surprise / entropy on needles if pos in needle_positions: ent = 3.5 surp = 4.0 else: ent = 0.5 surp = 0.8 cache.append(k, v, entropy=ent, surprise=surp) retained_positions = cache.token_positions # Create synthetic attention weights q = torch.randn(1, n_heads, 1, d_head) k_full = torch.randn(1, n_heads, seq_len, d_head) scores_full = torch.softmax(torch.matmul(q, k_full.transpose(-1, -2)) / math.sqrt(d_head), dim=-1) # Subsampled attention scores_evicted = scores_full[:, :, :, retained_positions] scores_evicted = scores_evicted / scores_evicted.sum(dim=-1, keepdim=True) # Subsampled baseline for comparison scores_full_sub = scores_full[:, :, :, retained_positions] scores_full_sub = scores_full_sub / scores_full_sub.sum(dim=-1, keepdim=True) res = TheoreticalAnalyzer.verify_semantic_anchor_guarantee( needle_positions=needle_positions, retained_positions=retained_positions, attention_weights_full=scores_full_sub, attention_weights_evicted=scores_evicted, ) assert res["all_needles_retained"], f"Failed to retain all needles: {res['retained_needles']}/{res['total_needles']}" assert res["retention_rate"] == 1.0 assert res["attention_cosine_similarity"] >= 0.99 def test_theorem_4_linucb_regret_bound(): """Verify Theorem 4: LinUCB cumulative regret grows strictly sub-linearly.""" allocator = ContextualBanditAllocator(context_dim=8, n_actions=5, alpha=1.0) horizon = 100 cumulative_regret = 0.0 regrets = [] np.random.seed(42) for t in range(1, horizon + 1): z_t = torch.tensor(np.random.uniform(0.1, 0.9, size=(8,)), dtype=torch.float32) action_idx, telemetry = allocator.select_action(z_t) # Optimal oracle reward vs chosen reward oracle_reward = 0.85 chosen_reward = 0.85 - (0.2 if action_idx != 2 else 0.0) instant_regret = oracle_reward - chosen_reward cumulative_regret += instant_regret regrets.append(cumulative_regret) allocator.update(z_t, action_idx, chosen_reward) theo_bound = TheoreticalAnalyzer.compute_linucb_regret_bound( feature_dim=8, horizon=horizon, delta=0.05, ) # Empirical regret must be strictly bounded by theoretical bound assert cumulative_regret <= theo_bound, ( f"Empirical regret {cumulative_regret:.2f} exceeded theoretical bound {theo_bound:.2f}" ) # Average regret must decline (sub-linear growth) avg_regret_first_half = regrets[horizon // 2] / (horizon // 2) avg_regret_full = regrets[-1] / horizon assert avg_regret_full <= avg_regret_first_half + 0.05 def test_lipschitz_attention_continuity(): """Verify Lipschitz continuity of scaled dot-product attention.""" d_k = 64 q = torch.randn(1, 1, 1, d_k) k = torch.randn(1, 1, 16, d_k) eps = 1e-3 q_perturbed = q + torch.randn_like(q) * eps attn_orig = torch.softmax(torch.matmul(q, k.transpose(-1, -2)) / math.sqrt(d_k), dim=-1) attn_pert = torch.softmax(torch.matmul(q_perturbed, k.transpose(-1, -2)) / math.sqrt(d_k), dim=-1) diff = torch.norm(attn_orig - attn_pert, p=2).item() # Theoretical Lipschitz bound for softmax(QK^T / sqrt(d_k)): L <= ||K||_2 / sqrt(d_k) k_norm = torch.norm(k, p=2).item() lip_bound = (k_norm / math.sqrt(d_k)) * eps assert diff <= lip_bound * 2.0 + 1e-4, f"Lipschitz bound violated: diff={diff} > bound={lip_bound}" def test_pareto_hypervolume_monotonicity(): """Verify Pareto hypervolume is strictly positive and non-decreasing across layers.""" grid_4 = DynamicGridController(n_layers=4, rank_levels=[1, 2, 4, 8, 16]) hv_4 = grid_4.compute_hypervolume() grid_2 = DynamicGridController(n_layers=2, rank_levels=[1, 2, 4, 8, 16]) hv_2 = grid_2.compute_hypervolume() assert hv_4 > 0.0, f"Hypervolume should be strictly positive: {hv_4}" assert hv_2 > 0.0, f"Hypervolume should be strictly positive: {hv_2}" assert hv_4 >= hv_2, f"Larger design space must yield >= hypervolume: hv_4={hv_4} < hv_2={hv_2}"