streaming-attention-space-optimization

name	streaming-attention-space-optimization
description	Space-efficient streaming attention approximation using tight bounds for KV cache compression in transformer architectures.
authors	["Justin Y. Chen","Ying Feng","Piotr Indyk"]
date	2026-06-05T00:00:00.000Z
arxiv	2606.07205v1
tags	["transformer","attention","efficiency","streaming","KV-cache","space-complexity"]

Streaming Attention Space Optimization

Overview

Provides nearly tight bounds on space complexity for streaming attention approximation, achieving KV cache compression through theoretical foundations. Integrates three kernel density estimation methods to minimize memory usage while maintaining attention quality.

Key Innovation

Tight Bounds Achievement:

• Upper bounds: Discrepancy-based coreset + polynomial method + space partitioning
• Lower bounds: INDEX problem with large side information
• Gap between upper/lower bounds significantly reduced vs. prior work (COLT'25, NeurIPS'25)

Space Efficiency: Space usage bounded independent of precision parameter (unlike prior methods)

Methodology

Three-Method Integration

Method 1: Discrepancy-Based Coreset

# Charikar-Kapralov-Waingarten'24 approach
coreset_size = discrepancy_based_construction(streaming_tokens)
# Reduces stored tokens while preserving attention approximation

Method 2: Polynomial Method

# Greengard-Rokhlin'87, Alman-Song'23 approach
polynomial_approximation = kernel_density_estimate(tokens)
# Efficient approximation via polynomial representation

Method 3: Space Partitioning

# Andoni-Laarhoven-Razenshteyn-Waingarten'17
partitions = geometric_space_partition(high_dim_embeddings)
# Locality-sensitive hashing for efficient retrieval

Streaming Attention Approximation Framework

Input: Streaming tokens t1, t2, ..., tn
Memory: Limited space S
Output: Approximate attention for each new token

Process:
1. Maintain coreset C (subset of tokens) in memory
2. For new token ti:
   - Compute approximate attention using C
   - Update C using discrepancy minimization
   - Evict low-importance tokens when S exceeded

Lower Bound Technique

INDEX Problem with Side Information:

• Classic INDEX: Recover specific index from stream
• Extended: Include large amount of side information per index
• Application: Proves fundamental space limits for attention approximation

Reusable Patterns

Pattern 1: Multi-Method Fusion

Use when: Single approximation method insufficient Approach: Combine coreset + polynomial + partitioning methods Result: Tighter bounds than any single method

Pattern 2: Streaming Attention Compression

Use when: Memory-constrained inference Steps:

1. Identify high-importance tokens (coreset selection)
2. Compress attention computation to coreset
3. Evict tokens via discrepancy minimization

Pattern 3: Kernel Density Estimation for Attention

Use when: Approximating attention without storing all tokens Method:

• Polynomial representation of kernel (softmax kernel)
• Efficient updates without full computation

Implementation Considerations

Memory Bounds

• Prior: Space increases with precision parameter
• This: Space bounded regardless of precision
• Benefit: Fixed memory for varying accuracy requirements

Computational Cost

• Coreset construction: O(coreset_size * stream_length)
• Polynomial updates: O(poly_degree * stream_length)
• Space partitioning: O(log stream_length) per query

Accuracy Trade-offs

• Higher precision → smaller approximation error
• Same space bounds regardless of precision
• User chooses precision without memory penalty

Extensions

Long-Context Applications

• Apply to long document processing
• Maintain fixed KV cache regardless of sequence length

Multi-Head Attention Optimization

• Per-head coreset selection
• Head-specific discrepancy bounds

Real-Time Inference

• Streaming attention for real-time generation
• Fixed memory footprint for deployed models

Pitfalls

1. Coreset Quality Degradation: Eviction strategy must preserve attention quality
2. Polynomial Approximation Error: Degree must be chosen carefully for kernel type
3. Partition Granularity: Too fine partitions increase overhead
4. Update Frequency: Over-updating coreset can exceed space bounds

Related Methods

• KV cache eviction (Hugging Face, vLLM)
• Streaming algorithms (classic literature)
• Kernel density estimation (KDE)
• Discrepancy theory (number theory)

Mathematical Foundations

Attention Approximation Problem

Given: tokens T = {t1, ..., tn}, limited space S
Goal: For each ti, compute attention(ti, T) ≈ attention(ti, C)
Where: C ⊆ T, |C| ≤ S

Discrepancy-Based Bounds

Discrepancy D(C, T) = max difference in attention weights
Goal: min D(C, T) subject to |C| ≤ S

Applications

• Long-context transformer inference
• Memory-constrained deployment
• Streaming generation without full cache
• Efficient attention for edge devices

Activation Keywords

streaming attention, KV cache compression, attention approximation, space complexity, coreset, discrepancy theory, kernel density estimation, polynomial method, space partitioning, tight bounds