# Submodular Max-Delay Batch Timer - ID: 1910 - Canonical URL: https://synthcore.org/idea/1910/submodular-max-delay-batch-timer - API JSON: https://synthcore.org/api/idea/1910.json - API Markdown: https://synthcore.org/api/idea/1910.md - Verification status: unverified - Source: [arXiv:2608.06796](https://arxiv.org/abs/2608.06796) - Category: architecture - Solves: speedup, stability, scalability - ML areas: batching, inference-speedup, moe-routing - Math tags: combinatorics, optimization, graph-theory - Ratings: usefulness 6/10; difficulty 4/10; novelty 6/10 ## Idea description 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. ## Mathematical statement The paper charges a service batch B cleared at time t by C(S,B,t)=w(S)+max_{r\in B}(t-a(r)), where S is the selected rooted service subtree, w(S) is its service cost, a(r) is request arrival time, and the maximum is the oldest-request delay. Its parameterized potential is h^L_ heta(i,j)=D_L(i,j)-(1- heta)M(i,j), where D_L(i,j) is the optimized cost of serving interval [i,j], M(i,j) is the service-only cost, and heta\in[0,1]. The key structural inequality is M(i,p-1)+M(k,j)\ge M(i,j)+M(k,p-1) for i\le k\le p\le j, expressing diminishing marginal service cost. The adaptation uses the same principle: keep a batch open when the estimated service-cost saving from merging the next request exceeds (1- heta) times its added maximum delay. ## Key formulas - $$C(S,B,t)=w(S)+\max_{r\in B}(t-a(r)).$$ - $$h^{L}_{\theta}(i,j)=D_{L}(i,j)-(1-\theta)M(i,j).$$ - $$M(i,p-1)+M(k,j)\geq M(i,j)+M(k,p-1)\qquad(i\leq k\leq p\leq j).$$ - $$\text{flush at time }t\text{ if }\Delta M_{\mathrm{next}}<(1-\theta)\Delta d_{\mathrm{oldest}},\qquad \Delta d_{\mathrm{oldest}}=t-a(r_{\mathrm{oldest}}).$$ ## Implementation notes Integrate this at the dynamic batching queue immediately before a Transformer forward pass or a batched MoE dispatch. Each queued request r has arrival time a(r), token count, sequence length, and routing or device metadata. For a candidate batch B, estimate M(B) as the predicted service cost: for inference this can be measured FLOPs plus padding overhead, while for MoE it can be the number of expert-token transfers and active expert kernels. Maintain the current batch B and periodically inspect the oldest not-yet-served request r_next. Pseudocode: initialize B empty; on arrival append r; at every scheduler tick compute M(B), M(B union {r_next}), and the merging saving DeltaM=M(B)+M({r_next})-M(B union {r_next}); compute the current oldest-request delay DeltaD=t-a(r_oldest); if DeltaM < (1-theta)*DeltaD, flush B, otherwise keep waiting until the next tick or a hard deadline. Use a short-horizon dynamic program over the last K arrivals when several possible boundaries are available: F[j]=min_{i