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

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

Saturation-Adaptive Prefill Chunking

Replace fixed chunked-prefill settings in an LLM serving engine with a feedback controller that decreases the number of prompt tokens processed per scheduling quantum as GPU saturation or long-context load increases. The controller targets a high-quantile bound on the absolute GPU-power ramp while preserving the existing peak-power ceiling and measuring the resulting latency-throughput tradeoff.

Useful7/10
Difficulty5/10
Novelty6/10
Paper: Smoothing the Ramp, Not the Peak: Scheduling-Induced Power Dynamics of LLM Inference and Their Grid-Scale Consequences arXiv:2608.01250
✓✓ Beats tuned baseline 2026

Laplacian-Coherence Graph Minibatches

Replace uniform node minibatches in a GNN with a coreset selected from a small random candidate set using local Laplacian-column coherence. Select nodes whose connectivity signatures are least redundant with already selected nodes, while retaining inverse-probability weights for unbiased loss estimates. This should improve coverage of weakly connected graph clusters and preserve smooth graph signals at the same batch size.

Useful7/10
Difficulty5/10
Novelty7/10
Paper: Scalable Graph Coreset Selection via Greedy Sampling arXiv:2607.27602
△ 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

Graph Quotient Minibatch Coupling

Use a minibatch-level transport plan that jointly decides which source graph should be paired with which target graph and how each target should be node-aligned. This can reduce total flow-matching displacement beyond per-example matching, producing shorter and less conflicting training trajectories without modifying the architecture.

Useful7/10
Difficulty7/10
Novelty7/10
Paper: Gromov-Monge Flow Matching for Equivariant Graph Generation arXiv:2608.26961
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

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

Coset-aware MoE routing repair

Add an integer-lattice feasibility layer after ordinary top-1 or top-2 MoE routing. The router first produces its usual expert assignments, then minimally changes a small number of low-confidence assignments so the batch count vector lies in a prescribed lattice or desired coset, eliminating persistent modular load imbalance that ordinary auxiliary losses may not detect.

Useful5/10
Difficulty5/10
Novelty7/10
Paper: On the number of factorable induced subgraphs arXiv:2607.27870
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