2025/12/08 by Tzachristas, Georgios, Deng, Lei, Tzachristas, Ioannis +2 · 1 citation
Computer Science · Mathematics · #Adversarial Robustness in Machine Learning #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Markov Chains and Monte Carlo Methods #Stochastic Gradient Optimization Techniques
paper · doi:10.48550/arxiv.2512.07647
openalex publication_date 2025/12/08 · openalex created_date 2025/12/10 · openalex updated_date 2026/07/28
We develop a unified mathematical framework for certified Top-k attention truncation that quantifies approximation error at both the distribution and output levels. For a single attention distribution P and its Top-k truncation P, we show that the total-variation distance coincides with the discarded softmax tail mass and satisfies TV(P, P)=1-e-KL( P\Vert P), yielding sharp Top-k-specific bounds in place of generic inequalities. From this we derive non-asymptotic deterministic bounds -- from a single boundary gap through multi-gap and blockwise variants -- that control TV(P, P) using only the ordered logits. Using an exact head-tail decomposition, we prove that the output error factorizes as ‖Attn(q,K,V)-Attnk(q,K,V)‖2=τ‖μtail-μhead‖2 with τ=TV(P, P), yielding a new head-tail diameter bound ‖Attn(q,K,V)-Attnk(q,K,V)‖2≤τ diamH,T and refinements linking the error to VarP(V). Under an i.i.d. Gaussian score model si∼\mathcal N(μ,σ2) we derive closed-form tail masses and an asymptotic rule for the minimal kε ensuring TV(P, P)≤ε, namely kε/n≈Φc(σ+Φ-1(ε)). Experiments on bert-base-uncased and synthetic logits confirm the predicted scaling of kε/n and show that certified Top-k can reduce scored keys by 2-4× on average while meeting the prescribed total-variation budget.