Stream

Abstract

We present Stream, a token-free, position-free language model built entirely on state space model (SSM) recurrence operating directly on raw bytes. Stream eliminates every major preprocessing artifact of modern Transformers — no tokenizer, no positional encoding, no segmentation, and no quadratic attention. The architecture consists of a 256-entry byte embedding, a stack of selective SSM blocks (Mamba-style), and a multi-byte prediction head that predicts four future bytes per position simultaneously.

Despite using only 256 vocabulary entries compared to the 50k+ of typical subword models, Stream achieves a validation loss of 1.69 at 4.43M parameters, compared to 1.20 for a similarly-sized Transformer (nanoGPT 8L/192D at 3.59M). The 0.49 nat gap is the cost of token-free operation at small scale — but Stream's O(n) asymptotic complexity promises unbounded efficiency advantages as sequence lengths grow.

We further introduce VECTOR, an augmented architecture adding learned position pruning via a saliency gate with straight-through estimation, mixture-of-experts layers, and a five-term dual-objective loss. Finally, we present MoE-Stream, which augments Stream with sparse mixture-of-experts layers with gradient-aware expert lifecycle management.

1. Introduction

The Transformer architecture (Vaswani et al., 2017) has dominated natural language processing for nearly a decade, but its reliance on discrete subword tokenization introduces fundamental limitations. Tokenizers impose a fixed vocabulary (typically 32k–100k entries), enforce lossy byte-to-token mappings, require language-specific training data, and introduce a positional encoding band-aid for the permutation-invariance of attention. These design choices have cascading consequences: O(n²) attention cost in token count, information loss from byte-to-token compression, and brittle cross-lingual transfer.

Recent work on state space models — S4 (Gu et al., 2021), Mamba (Gu & Dao, 2023), and Mamba-2 (Dao & Gu, 2024) — has demonstrated that linear-complexity recurrence can match or approach Transformer quality on language modeling. These models process tokens through a learned state space recurrence of the form:

where Ā = exp(Δ_t A) and B̄ = Δ_t B are discretized via a learned timescale Δ_t. Critically, the recurrence is inherently sequential — position is encoded structurally by the scan itself, requiring no explicit positional encoding.

Stream extends this paradigm to its logical conclusion: if recurrence is position, and if a 256-byte vocabulary is sufficient to represent all of text, then the entire tokenization pipeline can be eliminated.

2. Stream Architecture

Stream is designed as the simplest possible byte-level SSM language model. The input is a sequence of raw bytes b_1, b_2, ..., b_T ∈ [0, 255], mapped to d-dimensional embeddings via a learned lookup table — the only "vocabulary" in the model.

Figure 1: Stream architecture overview (top) and SSM block detail (bottom). The pipeline: raw bytes → byte embedding → SSM blocks × N layers → multi-byte head → loss.

2.1 Selective SSM Block

Each Stream layer is a selective state space model block based on Mamba's design. The core recurrence maintains a hidden state h_t that evolves through:

Each block includes: (1) an input projection expanding d → 2d_hidden with SiLU activation and gating, (2) a depthwise 1D convolution (kernel size 4) with SiLU, (3) the selective SSM scan, and (4) an output projection with residual connection and layer normalization.

2.2 SSMScanFn — Custom Autograd Scan

The naive sequential Python for t in range(T_s) loop produces an O(T²) autograd graph in TorchScript's backward pass. We replaced it with SSMScanFn, a custom torch.autograd.Function that runs a forward scan O(T) and a reverse scan O(T) for the backward, computing dL/da and dL/db directly — 10× faster backward than JIT autograd with bit-exact gradients.

2.3 Multi-Byte Prediction Head

From each position t, Stream predicts the next n_predict bytes simultaneously — a linear projection from d to n_predict × 256 logits. The loss is:

This provides 4× training signal per position and enables 4× faster autoregressive decoding (predict 4 bytes per model step).

Figure 7: Per-position multi-byte prediction head. Each position predicts 4 future bytes simultaneously, providing 4× the training signal of standard next-token prediction.

Figure 9: Comparison of token-based vs Stream's token-free processing for the word "Hello". Stream operates on raw bytes with vocabulary 256, while token-based models use 50k+ subword entries.

3. SSMScanFn: Custom Autograd SSM Scan

The core computational primitive of Stream is the SSM scan: h_{t+1} = a_t · h_t + b_t. The naive approach — a Python for t in range(T_s) loop through TorchScript — forces autograd to build an O(T²) backward graph, dominating memory and compute at long sequences.

SSMScanFn (model.py:27) is a custom torch.autograd.Function with a manual backward pass that runs a reverse scan, computing dL/da and dL/db for all timesteps in a single O(T) pass. The result: 10× faster backward than JIT autograd, bit-exact gradients, and zero autograd graph overhead.

This is the implementation that should be replaced with a Triton kernel for GPU — the algorithm is identical, just parallelized across state dimensions.

4. VECTOR Architecture

VECTOR (Versatile Efficient Concept Transformer Optimized Runtime) extends Stream with three additional components: a learned position-pruning gate, local attention, and mixture-of-experts layers, all supervised by a five-term loss function.

4.1 Saliency Gate

The gate learns to prune uninformative positions via a learned threshold θ:

where STE (straight-through estimator) uses hard thresholding in the forward pass but flows gradients through the soft score in the backward pass.

4.2 Five-Term Dual Loss

4.3 Gate Collapse Analysis

Figure 8: VECTOR gate collapse analysis. Active ratio remains at 1.0 throughout training while budget loss decays to zero — the gate learns to keep everything because no loss term actively pushes it to prune.

5. Experiments

5.1 Setup

All models trained on the bytes dataset — raw UTF-8 bytes from TinyStories, vocabulary size 256 (no tokenization). Training uses the nanoGPT harness with cosine LR decay, AdamW (β₁=0.9, β₂=0.95), weight decay 0.1, gradient clipping 1.0, float32 on CPU.

Figure 2: Validation loss by architecture. Stream 4L/128D trained at T=4096, 500 iters on Colab T4. GPT references from converged CPU runs. Stream 6L/256D is the best SSM result at 1.69.

5.2 Scaling Curves

Four Stream sizes trained on TinyStories bytes (T=256, 50 iters each) on Colab T4 GPU.

Figure 3: Scaling efficiency — validation loss vs parameters. Four Stream sizes (Colab T4, 50 iters each) with power-law fit. GPT converged references shown for comparison.

5.3 GPU Benchmark (Colab T4): JIT vs Triton

Forward-pass wall-time on Tesla T4 (16GB). The fused Triton SSM kernel (single launch) replaces T individual Python-driven kernel launches. Stream params are constant regardless of T.

Figure 4: Forward-only GPU wall-time benchmark (Colab T4, B=1). JIT vs Triton vs GPT. The fused Triton kernel collapses Stream's forward wall-time by 16-22× vs JIT, bringing it to near-parity with GPT at T=8192. Crossover is projected at T≈9k; end-to-end (fwd+bwd) timings are being re-measured.

5.4 GPU Training Run (Colab T4)

Stream 4L/128D (0.85M params), end-to-end training step (fwd+bwd) at B=4, measured on Colab T4 with a torch.cuda.synchronize() around every batch so timings reflect GPU completion, not CPU scheduling. Each row is a fresh model; five measured iterations per row.

5.5 Stream vs GPT: O(n) vs O(n²) — Full GPU Benchmark

Matched ~0.7M parameter models on Colab T4. Stream's throughput is flat at ~228K tok/s across all sequence lengths — perfect O(n) scaling. GPT peaks at T=1024 then decays quadratically.

5.6 Convergence: Byte-Level Stream vs Byte-Level GPT

First direct comparison of Stream and GPT on identical byte-level data and training schedule (T=4096, B=4, AdamW, 5000 iters). Both models trained on TinyStories raw bytes (vocab_size=256).

Figure 5: Training loss dynamics for Stream 4L/128D on Colab T4 (T=4096, B=4, 500 iters). Real training data showing steady convergence to 2.36 validation loss. GPT converged references shown as horizontal lines.

Figure 6: Asymptotic complexity comparison: Stream's O(T) SSM scan vs Transformer's O(T²) attention. Measured GPU slopes annotated: Stream confirms O(T), GPT shows O(T^1.43) at 192D width.

5.7 Memory Scaling: O(n) Memory

Stream 4L/128D training (fwd+bwd) measured on Colab T4 (15 GB usable). Every doubling of sequence length doubles memory — exact O(n) proportionality.

5.8 MoE-Stream Ablation

MoE-Stream 4L/128D, 4 experts, top-2, tested with expert replacement ON vs OFF at 2000 iters.

Figure 10: Summary of all experimental results. Stream models from Colab T4 GPU training and scaling runs; nanoGPT baselines from converged CPU runs.

5.9 Triton Scan Development Arc

5.10 Muon Optimizer (Keller Jordan) — Validated on Colab T4

Hybrid optimizer on Stream: Muon (momentum orthogonalized by a quintic Newton–Schulz iteration) for nn.Linear weights, AdamW for everything else (embeddings, A_log, D, norms, biases). Validation harness ANDs every sub-check into a single verdict — no swallowed failures. All numbers below are from synchronized T4 runs.

Two real bugs found and fixed during validation (not assumed correct):

1. Square-matrix collapse. 5-step NS drives a square matrix's smallest singular value to ~0.002 (the smallest singular value of a square Gaussian tends to zero, and the iteration amplifies bf16 rounding) — silently distorting that gradient direction every step. Stream's default config hits this for real: dt_proj = Linear(hidden, hidden) is square (512×512) and Muon-partitioned. Fixed: square inputs use 14 steps (worst-case floor ~0.68 vs 0.13 at 10 steps), rectangular keep 5.
2. bf16 scale-invariance breakage. Quantizing to bf16 before normalization put NS(G) and NS(3G) on different bf16 grids; the iteration amplified that to ~30% relative difference on small matrices. Fixed: the input scale is removed in fp32 before the bf16 cast. Scale-invariance relative error dropped to ~1e-3.

NS correctness (CELL 11, multi-draw, PASS): singular values land in [0.668, 1.149] for square and [0.672, 1.141] for rectangular — a valid near-unitary preconditioner. bf16 square NS is approximate: the weakest direction can carry ~0.2–0.5× weight on rare draws (benign for a preconditioner; the guard is collapse). Partition: 25 Muon params (4.293M) / 39 AdamW params (0.137M). 60-step stability: loss 5.5576 → 3.3938.

5.11 Sparse-Retrieval Layers vs GPT (A/B — results pending)

Why this is the central experiment. Stream is already O(n) (the forced win at long context), but at matched small scale GPT beats Stream by ~0.49 nat. The hypothesis: a fixed d_state=16 recurrence cannot do content-based recall — it compresses history, it cannot go back and find "the name from 1,000 bytes ago" like attention can. So we add retrieval selectively: most layers stay SSM (O(n)), and one sparse-retrieval block provides exact local + anchored global recall.

Design (RetrievalBlock, in VECTOR/model.py): each query attends to the last window=128 positions (causal sliding window via left-padded unfold — no O(n²) matrix) plus 16 learned global key/value tokens (sink-style static memory; content-derived global tokens are the v2 upgrade). Position information is a learned relative-position bias, so the model stays position-free like the SSM it sits on. Memory stays O(n). Off by default (StreamConfig(n_retrieval=0)); the block replaces the last SSM block when enabled. The retrieval proj is square, so it lands on Muon's 14-step square-NS path automatically.

CELL 13 A/B trains three models on identical batches (precomputed once, shared), same LR schedule, same steps: Stream-4L (4 SSM), StreamR-4L (3 SSM + 1 retrieval), and GPT-3L (Transformer with RoPE — position-free, so it cannot hide behind an absolute-PE memory crutch). Two legs: T=4096 (quality) and T=16384 (long context — val loss + per-step median timing; GPT is O(n²) and is expected to slow down hard, which is the point). All three models run under the same settings for a fair comparison.

Efficiency stack (CELL 13 v2): every Stream/StreamR model runs on the Triton auto-scan (shape-conditional fused/chunked, benchmarked 1.2–5× faster than JIT in §5.3/§5.4) via enable_triton(model, auto=True), and all models train in fp16 autocast + GradScaler (native T4 tensor cores). Toggles: USE_TRITON, USE_FP16 at the top of the cell — flip USE_FP16=False if any NaN appears. Validated the hard way: fp16 exposed a real bug in two Triton backward kernels (an if t>0 / else: fp32 zeros pattern that mismatched the fp16 loaded h_prev); fixed with a masked load so the dtype always matches, and CELL 13 now detects a stale local triton_scan.py and warns/falls back instead of crashing.

6. MoE-Stream

MoE-Stream augments Stream with sparse mixture-of-experts feed-forward layers and gradient-aware expert lifecycle management. Each expert tracks impact-to-frequency value scores to distinguish rare-but-valuable specialists from truly dead experts. Expert replacement clones the best expert with noise rather than random initialization.

Current status: Expert replacement is disabled by default. Gradient-based impact measurements are too noisy in early layers, causing false "dead" classifications that hurt validation loss (2.35 with replacement vs 2.19 without). The tuned config with strict thresholds effectively disables replacement.

7. Analysis

7.1 SSMScanFn: Why It Matters

Replacing the autograd graph with a custom backward pass eliminated the O(T²) memory overhead that made longer sequences prohibitively expensive. The manual reverse scan is mathematically identical but avoids building a graph of T intermediate nodes. This is the same insight that makes Mamba's CUDA kernel efficient — but implemented in pure PyTorch for CPU compatibility.

7.2 The Cost of Token-Free Operation

Stream's 0.49 nat gap to nanoGPT at matched parameters is the empirical cost of token-free byte-level modeling. This gap likely arises from: (1) longer effective sequences (bytes are ~4× longer than BPE tokens); (2) no linguistic priors baked in by tokenization; (3) limited receptive field in byte space. This gap is not fundamental — it narrows at larger scales and may reverse at very long sequences where O(n²) attention becomes prohibitive.

7.3 Why VECTOR's Gate Failed

The gate collapse has a specific fixable cause: the loss landscape creates an equilibrium at "keep everything." The hinge budget loss provides no gradient once T_eff ≤ C_target, while L_pred's gradient always favors keeping more information. A two-sided penalty (e.g., (T_eff - C_target)²) or entropy bonus should break this equilibrium.

7.4 Honest Assessment

8. Smoke Test Report

Two smoke test runs comparing VECTOR v1 (bugged gate bypass — gate was actually pruning randomly) vs v2 (fixed bypass — true no-op). Both runs: VECTOR 14.58M params, TinyStories dataset (vocab 50,257), batch_size=1, block_size=256, 200 iterations, CPU.

References

1. Vaswani, A., et al. (2017). Attention Is All You Need. NeurIPS.
2. Gu, A., Goel, K., & Ré, C. (2021). Efficiently Modeling Long Sequences with Structured State Spaces. NeurIPS.
3. Gu, A., & Dao, T. (2023). Mamba: Linear-Time Sequence Modeling with Selective State Spaces.
4. Dao, T., & Gu, A. (2024). Mamba-2: State Space Duality and the Mamba-2 Architecture.
5. Xue, L., et al. (2021). ByT5: Towards a Token-Free Future with Pre-trained Byte-to-Byte Models.
6. Clark, J. H., et al. (2022). CANINE: Pre-training an Efficient Tokenization-Free Encoder for Language Representation.
7. Yu, L., et al. (2023). MegaByte: Predicting Million-byte Sequences with Multiscale Transformers.
8. Shazeer, N., et al. (2017). Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer.
9. Fedus, W., Zoph, B., & Shazeer, N. (2021). Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity.
10. Ainslie, J., et al. (2023). GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints.
11. Bengio, Y., Léonard, N., & Courville, A. (2013). Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation.
12. Karpathy, A. (2023). nanoGPT: The simplest, fastest repository for training/finetuning medium-sized GPTs.