ForgettingOT: Certified Speculative Batching from Sinkhorn's Projective Forgetting

• URL: http://arxiv.org/abs/2607.24741v2
• Date: Tue, 04 Aug 2026 03:22:28 GMT
• Title: ForgettingOT: Certified Speculative Batching from Sinkhorn's Projective Forgetting
• Abstract summary: We show that the eigenmode of the fixed-point Jacobian $J_tstar=QP=Pstar P$ controls the strict correction tail.<n>ForgettingOT turns this nonlinear Perron--Frobenius fact into a certified executor for streams of related Sinkhorn problems.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Positive two-marginal entropic optimal transport is solved by a nonlinear, positive, order-preserving, homogeneous Sinkhorn map. After quotienting the dual scaling gauge, we show that the active eigenmode of the fixed-point Jacobian $J_t^\star=QP=P^\star P$, generically $λ_2(QP)$, controls the strict correction tail. The projective-residual ratio converges to this mode, and the additional certified cycles required for tolerance $θ_τ$ scale as $\log(ρ/θ_τ)/[-\logλ_2]+O(1)$. ForgettingOT turns this nonlinear Perron--Frobenius fact into a certified executor for streams of related Sinkhorn problems. A computable projective variation $Ω_t$ in the marginals and kernel bounds the carry residual, while a verified contraction $q_t$ gives candidate repair depth. A window theorem converts these depths and the audit grid into bounds on packed work, collective rounds, overshoot, and fallback. Empirical tail estimates allocate work but never authorize release; current-instance certificates or measured marginal residuals do so, with ordinary Sinkhorn as fallback. On 15 FP64 A100/OTT-JAX cells, the observed quotient slow-mode ratio agrees with $λ_2(QP)$ to $9.84\times10^{-6}$. On controlled four-A100 streams, the complete executor is $1.42\times$--$3.55\times$ faster than sequential soft $c$-transform warm starts, with 30/30 paired wins and no violations of the $10^{-3}$ marginal tolerance. Eight-A100 support-4096 streams give $2.584\times$--$2.945\times$ wall-time speedup and $4.285\times$--$4.615\times$ fewer vector-collective rounds. The outer executor composes with target-preserving Sinkhorn accelerators; a changed map or approximate target needs a contraction or error bridge before inheriting the repair-depth bound.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• One Inverse Step is a Convex Program: Bayes-Limit Calibration of Diffusion Inversion [0.0]
  One implicit DDIM inversion step is the cheapest probe of whether a pretrained diffusion model encodes local manifold geometry.<n>The Fermi window conflicts with the model's own training support by $3.6$-$5.6times$, and the trained Hessian-Lipschitz constant is $2$-$12%$ of the curvature the law reads.<n>Finally the unconditional ceiling $_t_max(mathrmsym,J)le1$, from $mathrmCov(x_0mid x_t)succeq0$
  arXiv  Detail & Related papers  (2026-08-24T11:01:54Z)
• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
  We study the nonnegative submodular subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle.<n>Our algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives.<n>As a consequence, the offline-to-online reduction yields single-bandit CMAB algorithms for general matroid-constrained submodular rewards.
  arXiv  Detail & Related papers  (2026-08-12T14:54:15Z)
• Round-Trip Consistency: Bidirectional Diffusion Models Can Predict Their Own Rollout Errors [51.56484100374058]
  Autoregressive models accumulate error over long rollouts, yet at deployment there is no ground truth to measure it against.<n>We train a single conditional latent diffusion model that steps a dynamical system forward or backward in time via a direction flag.<n>We show that this bidirectionality supplies a measurement-free test-time error signal.
  arXiv  Detail & Related papers  (2026-08-01T13:49:46Z)
• When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers [17.78341274611665]
  Weight-tied looped transformer -- one block applied T times -- implement an algorithm?<n>We answer with four findings from controlled populations on group word problems.
  arXiv  Detail & Related papers  (2026-07-22T16:04:31Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  We study horizon-free regret for finite-horizon time-homogeneous Markov decision processes with $A$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$.<n>We prove a regret upper bound [tilde O(sqrtSAK+S8A3)] with failure probability $$, where $K$ is the number of episodes and $tilde O(sqrtSAK+S3K)$ hides $mathsfpoly
  arXiv  Detail & Related papers  (2026-07-22T07:42:19Z)
• Attention as Frustrated Synchronization [0.0]
  We introduce the Frustrated Synchronization Network (FSN), whose token states are phases on a torus and whose entire value pathway is one learned complex coupling kernel over harmonics and a one-step delay.<n>The complex phases are static Kuramoto-Sakaguchi frustration angles, the signed harmonics are repulsive Daido components, and the delay term, which couples each token to the successors of the tokens it attends to, is algebraically identical to Kuramoto-Sakaguchi coupling.
  arXiv  Detail & Related papers  (2026-06-17T05:18:01Z)
• Closed-Form Spectral Regularization for Multi-Task Model Merging [96.82449201305234]
  Model merging combines several independently fine-tuned experts into a single multi-task model without any training data.<n>State-of-the-art merging methods formulate merging as a layer-wise interference problem.<n>We propose SWUDI, a closed-form method that combines a soft exponential filter, which matches the gradient-flow trajectory of iterative descent.
  arXiv  Detail & Related papers  (2026-06-05T14:00:47Z)
• Spectral Anatomy of Quantum Gaussian Process Kernels [38.264196157340216]
  We prove a Cauchy-Schwarz tail bound on Nystrm approximation error, a finite-sample variance-contraction identity, and a characterization of the emphtarget-dependent optimal entropy.<n>The diagnostic is kernel-agnostic: hardware-efficient, matchgate, IQP emphand RBF/Matérn/RFF/deep- kernel families all collapse onto identical $S/log n$ curves.
  arXiv  Detail & Related papers  (2026-05-29T07:41:14Z)
• Hidden-State Privacy Has an Empty Middle [51.56484100374058]
  We prove a complementary Fisher-ball lower bound: every full-rank Gaussian release at $O(1)$ Fisher utility admits a direction whose Mahalanobis signal grows linearly in hidden width.<n>A split-memory transformer trained from scratch reaches $G_mathrmMah in [20, 33]$ at 90M and maintains a $6$--$24times$ advantage over same-budget GPT baselines from 30M to 1B at a fixed-token language loss penalty.
  arXiv  Detail & Related papers  (2026-05-21T20:12:09Z)
• Block-Wise Differentiable Sinkhorn Attention: Tail-Refinement Gradients with a Gap-Aware Dustbin Bridge [0.0]
  We study long-context balanced optimal transport attention on TPU hardware through a stopped-base, fixed-depth tail-refinement surrogate.<n>We provide a local surrogate-bias bound, an a posteriori bias certificate, and a projective contraction certificate for strictly positive active blocks.<n>On synthetic masked problems, the optimized matches exact autodiff of the same centered surrogate to within $10-5$--$10-10$.
  arXiv  Detail & Related papers  (2026-04-28T19:01:11Z)
• Bond-dimension scaling of a local-refinement advantage over hyperoptimized tensor-network contraction on Sycamore like topologies [0.0]
  We identify a missing local-refinement stage in the cotengra tensor-network contraction pipeline.<n>We show that its impact grows monotonically with bond dimension on the emphconnectivity graph of Sycamore-like topologies.
  arXiv  Detail & Related papers  (2026-04-28T11:59:31Z)
• Latent Phase-Shift Rollback: Inference-Time Error Correction via Residual Stream Monitoring and KV-Cache Steering [4.032680910442999]
  Large language models commit unrecoverable reasoning errors mid-generation.<n>We introduce $textbfLatent Phase-Shift Rollback$ (LPSR)<n>At each generation step, we monitor the residual stream at a critical layer lcrit, detect abrupt directional reversals (phase shifts) via a cosine-similarity $+$ entropy dual gate.<n>No fine-tuning, gradient computation, or additional forward passes are required.
  arXiv  Detail & Related papers  (2026-04-20T17:53:33Z)
• Token Coherence: Adapting MESI Cache Protocols to Minimize Synchronization Overhead in Multi-Agent LLM Systems [0.0]
  Multi-agent LLM orchestration incurs synchronization costs scaling as O(n x S x |D|) in agents, steps, and artifact size under naive broadcast.<n>I argue this pathology is a structural residue of full-state rebroadcast, not an inherent property of multi-agent coordination.<n>I construct the Artifact Coherence System (ACS) and prove the Token Coherence Theorem.
  arXiv  Detail & Related papers  (2026-03-16T12:20:06Z)
• INC: An Indirect Neural Corrector for Auto-Regressive Hybrid PDE Solvers [61.84396402100827]
  We propose the Indirect Neural Corrector ($mathrmINC$), which integrates learned corrections into the governing equations.<n>$mathrmINC$ reduces the error amplification on the order of $t-1 + L$, where $t$ is the timestep and $L$ the Lipschitz constant.<n>We test $mathrmINC$ in extensive benchmarks, covering numerous differentiable solvers, neural backbones, and test cases ranging from a 1D chaotic system to 3D turbulence.
  arXiv  Detail & Related papers  (2025-11-16T20:14:28Z)
• ATTS: Asynchronous Test-Time Scaling via Conformal Prediction [112.54016379556073]
  Large language models (LLMs) benefit from test-time scaling but are often hampered by high inference latency.<n>We introduce ATTS (Asynchronous Test-Time Scaling), a statistically guaranteed adaptive scaling framework.<n>We show that ATTS delivers up to 56.7x speedup in test-time scaling and a 4.14x throughput improvement.
  arXiv  Detail & Related papers  (2025-09-18T16:55:09Z)
• Speedy MASt3R [68.47052557089631]
  MASt3R redefines image matching as a 3D task by leveraging DUSt3R and introducing a fast reciprocal matching scheme.<n>Fast MASt3R achieves a 54% reduction in inference time (198 ms to 91 ms per image pair) without sacrificing accuracy.<n>This advancement enables real-time 3D understanding, benefiting applications like mixed reality navigation and large-scale 3D scene reconstruction.
  arXiv  Detail & Related papers  (2025-03-13T03:56:22Z)
• On the $O(\rac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
  This paper considers the RMSProp and its momentum extension and establishes the convergence rate of $frac1Tsum_k=1T.<n>Our convergence rate matches the lower bound with respect to all the coefficients except the dimension $d$.<n>Our convergence rate can be considered to be analogous to the $frac1Tsum_k=1T.
  arXiv  Detail & Related papers  (2024-02-01T07:21:32Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  We propose an algorithm called Mild-OGD for the full-information case, where delayed gradients are available.<n>We show that the dynamic regret of Mild-OGD can be automatically bounded by $O(sqrtbardT(P_T+1))$ under the in-order assumption.<n>We also develop a bandit variant of Mild-OGD for a more challenging case with only delayed loss values.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• Error-robust quantum logic optimization using a cloud quantum computer interface [0.0]
  We describe an experimental effort designing and deploying error-robust single-qubit operations using a cloud-based quantum computer and analog-layer programming access. We design numerically-optimized pulses that implement target operations and exhibit robustness to various error processes including dephasing noise, instabilities in control amplitudes, and crosstalk.
  arXiv  Detail & Related papers  (2020-10-15T22:47:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.