sublinear

Definition

Growing more slowly than the input size — cost that scales as, say, log n or sqrt(n) rather than n. The term shows up wherever long context is at stake, since standard self-attention is quadratic in sequence length and approximate or retrieval-based alternatives advertise sublinear cost. Asymptotics hide constants, though, so a sublinear method can still lose to the dense baseline at practical sequence lengths.

Explainers using this term

• Surviving GPU Out-of-Memory — Every Cause, Every FixTraining Deep Nets with Sublinear Memory Cost