ML: Batching

Machine-learning ideas tagged Batching in the ML taxonomy of the Math2NN corpus.

△ Mechanism confirmed, baseline not beaten 2026

Log-Depth Chunked Linear-Attention Scan

Implement causal linear attention in chunks and combine chunk summaries with an associative scan instead of carrying the recurrent state through all chunks sequentially. This preserves the exact causal computation while reducing inter-chunk dependency depth from the number of chunks to its logarithm, enabling substantially more GPU parallelism for long-context training and prefill.

Useful8/10
Difficulty6/10
Novelty6/10
Paper: Kernelized Linear Attention: Breaking the Capacity Wall with Symmetric Cones arXiv:2607.17419
△ Mechanism confirmed, baseline not beaten 2026

Tau-leaped parallel discrete Hamiltonian sampler

Approximate the exact event-by-event lifted sampler by drawing independent Poisson jump counts over a short interval and applying compatible discrete moves in parallel. This converts sequential neighbor events into batched GPU-friendly updates while retaining the Hamiltonian rate structure; the step size controls the error-versus-throughput tradeoff.

Useful7/10
Difficulty5/10
Novelty8/10
Paper: Hamiltonian dynamics for sampling on discrete spaces arXiv:2608.17961
✗ Failed on benchmark 2026

Scrambled Sobol Diffusion Ensembles

Use Owen-scrambled Sobol points instead of independent Gaussian seeds for batched diffusion sampling, mapping each cube point through the component-wise inverse Gaussian CDF and the model's probability-flow ODE. Estimate ensemble expectations with importance weights computed from the target-to-proposal density ratio, so the estimator remains valid despite finite-step and learned-score transport errors.

Useful7/10
Difficulty6/10
Novelty7/10
Paper: Diffusion Quasi-Monte Carlo arXiv:2608.11055
✗ Failed on benchmark 2026

Fairness-Budgeted Short-Job Insertion

Replace unrestricted continuous batching with a fairness-constrained scheduler that only inserts a waiting request when its predicted decode footprint remains within a normalized distance of the longest request already in the batch. The fairness budget should be tuned away from the mathematically worst midpoint and validated against real arrival distributions, with the goal of reducing wasted max-driven decode work without falling back to inefficient one-request-at-a-time serving.

Useful7/10
Difficulty4/10
Novelty6/10
Paper: Efficiency and Cost Alignment in Batched LLM Serving via Resource-Fair Scheduling arXiv:2608.02244
✗ Failed on benchmark 2026

Tail-Weighted Optimal Batch Scheduling

Replace a static batch size with a schedule optimized for a prescribed learning-rate schedule and a fixed total number of processed examples. Steps whose stochastic-gradient noise has a large effect on the paper's loss bound receive larger batches, with the weighting determined by the future learning-rate tail rather than by a hand-designed warmup or cooldown rule.

Useful7/10
Difficulty5/10
Novelty5/10
Paper: Towards joint scaling laws with optimal batch size schedules arXiv:2607.27731
△ Mechanism confirmed, baseline not beaten 2026

Pipelined bounded-staleness gradient coding

Replace synchronous replicated-gradient computation with a bounded-staleness stream: at optimizer step t, aggregate one gradient for each data partition, using the newest completed evaluation even if it was computed at an earlier model version. Replicated partition placement makes the aggregate robust to stragglers, while pipelining ensures that each worker computes only one partition gradient per step.

Useful7/10
Difficulty6/10
Novelty6/10
Paper: Pipelined Gradient Coding arXiv:2607.20739
△ Mechanism confirmed, baseline not beaten 2026

Support-Graph Parallel Scheduler

Convert a sequential modular network into parallel execution layers by placing mutually commuting operators in the same layer. The resulting circuit preserves all noncommuting precedence constraints while exposing safe concurrency and fusion opportunities for inference or training.

Useful7/10
Difficulty5/10
Novelty5/10
Paper: Partially-Commutative Polynomial Optimization arXiv:2607.08841
✗ Mechanism failed 2026

UCB Drift Router for Cheap-or-Expert Inference

Replace a fixed confidence threshold in cascaded inference or mixture-of-experts routing with a queue-aware UCB-DPP controller. The controller sends an input to a cheap model when its optimistic estimated success is sufficiently high and the expert backlog is large, while escalating uncertain or high-value inputs when the penalty for an error dominates congestion. This should reduce expensive-model utilization without allowing latency or escalation queues to diverge.

Useful7/10
Difficulty4/10
Novelty6/10
Paper: Learning When to Automate: Queue Control in Human-AI Service Systems arXiv:2607.06017
Unverified 2026

Spectral Control Variates for Minibatch Gradients

Replace a raw minibatch gradient with an unbiased control-variate estimator that subtracts predictable components of per-example gradients and adds back their exactly or cheaply known population mean. Select the control-variate directions using leading eigenvectors of an online covariance operator, rather than using arbitrary scalar baselines. This should reduce gradient variance at fixed batch size and permit fewer examples per optimization step.

Useful6/10
Difficulty6/10
Novelty6/10
Paper: Optimal Control Variates for Survey Sampling and Causal Inference arXiv:2608.15333
Unverified 2026

Submodular Max-Delay Batch Timer

Replace a fixed maximum-wait timeout in dynamic neural inference batching with a service-aware timer. The timer estimates the marginal reduction in computation or communication cost from adding another request and delays service only while that saving justifies the additional oldest-request delay.

Useful6/10
Difficulty4/10
Novelty6/10
Paper: Online Multi-Level Aggregation with Per-Batch Maximum Delay arXiv:2608.06796
Unverified 2026

Chromatic Collision-Free Pairwise Batches

Represent every pairwise training interaction as a directed edge and edge-color the interaction graph. Use one color class, or a small set of colors, as a microbatch: because a color class is a matching, no data example participates in two pairwise terms within that microbatch. This removes within-batch gradient collisions and provides a graph-dependent estimate of how many dependent strata are being combined.

Useful6/10
Difficulty5/10
Novelty7/10
Paper: Concentration Inequalities for Incomplete U-statistics over Arbitrary Sampling Graphs arXiv:2607.17048
Unverified 2026

Orthogonal Latin Expert Router

Use mutually orthogonal Latin labels as deterministic expert assignments for token batches. Each routing family is individually balanced, and pairs of families avoid repeated co-assignment patterns, enabling multiple routing rounds or auxiliary experts without the severe load collisions caused by independent random hashing.

Useful6/10
Difficulty5/10
Novelty6/10
Paper: Generalizations of nets and Latin squares arXiv:2607.10890
✗ Mechanism failed 2026

Unassembled Adaptive Cell Neural Network

Represent every mesh interface degree of freedom by one feature copy per incident cell, and apply local neural blocks directly to these cell tensors. Enforce inter-cell consistency with valence-weighted averaging only after selected layers or hierarchy transitions, avoiding repeated construction of a global sparse graph or assembled feature vector. This is suited to adaptive quadtrees, octrees, and finite-element neural operators.

Useful6/10
Difficulty5/10
Novelty7/10
Paper: Coalesced Matrix-Free Geometric Multigrid on Persistent Cell-Wise Storage arXiv:2607.03413
Unverified 2026

Global-Shift Randomized Batching

Sample one batching aggressiveness parameter once per serving epoch and use it for all busy periods, instead of independently randomizing every batch. This globally coupled randomness preserves nested batching behavior while preventing a fixed traffic pattern from repeatedly aligning with a deterministic timeout.

Useful5/10
Difficulty3/10
Novelty7/10
Paper: Online Multi-Level Aggregation with Per-Batch Maximum Delay arXiv:2608.06796
Unverified 2026

Masked Universal Host Layer

Represent many related sparse graph or attention patterns inside one fixed host connectivity pattern and activate each target instance with binary directional masks. The learned edge transformation and sparse-kernel layout are shared across instances, while the mask selects the target graph, enabling one compiled operator to process heterogeneous structures.

Useful5/10
Difficulty5/10
Novelty5/10
Paper: A universal emulator for planar Ising lattices arXiv:2607.05308