CS Paper Radar

What Must Survive? Exact Task-Information--State Frontiers Under Partial Task Revelation

Ronald Katende

cs.LG cs.IT ·submitted 2026-09-18 09:12 UTC · v2

Abstract

A state may need to be compressed before its exact downstream task is known. For a finite family of linear task operators $\{T_u\}_{u\in\U}$, we characterize exactly how much state must survive when only one of $K$ coarse task messages is available at compression time: $$p^*(K)= \min_{\substack{\Pcal\text{ partition of }\U\\|\Pcal|\le K}} \max_{C\in\Pcal}\rank(T_C),$$ where $T_C$ stacks the tasks that remain unresolved within cell $C$. Thus task information reduces retained state precisely by separating tasks whose joint task-visible subspace is expensive. We derive the dual bit frontier, an irreducible common-core floor, and a sharp singular-value characterization for nonzero tolerance. For overlapping task families, a cumulative overlap deficit places the exact frontier within an additive $Δ$ of weighted load balancing. Optimal partitioning is strongly NP-hard, yet direct-sum families admit classical approximation guarantees and a PTAS. We stress-test the theory on learned task operators from CIFAR-10, Fashion-MNIST, SVHN, and Burgers observables. For Burgers with $K=2$ and $\eps=0.35$, a constructive partition attains $p=4$, while balanced random partitions require median $p=6$, with held-out worst standardized RMSE $0.0368$. The results distinguish uniform task sufficiency from distributional and decision-level performance.

Comment
12 pages, 2 figures, 1 table. Substantially expanded version: added sharp approximate bounds, overlap-deficit theory, approximation guarantees, and empirical stress tests on learned representations and Burgers observables

Closest papers

Nearest neighbours by meaning across the whole index.

Deterministic Distributed Linearly Separable Computation via Nested Cyclic Codes

cs.IT ·2026-10-13 ·Anu Mathew, M. Nikhil Krishnan
similarity 0.59
Abstract · 13 pages, 1 figure

We study the $(K,N,S,M,K_c)$ distributed linearly separable computation (DLSC) setting, where a master employs $N$ workers with a per-worker computation load of $M$ to recover $K_c$ deterministic linear combinations of $K$ messages in the presence of up to $S$ stragglers. We propose a DLSC framework based on nested cyclic codes that achieves $M=\frac{K}{N}(S+K_c)$. For sufficiently large $K$, we establish the matching converse $M\geq\frac{K}{N}(S+K_c)$, proving the asymptotic computation load optimality of the proposed framework. By instantiating cyclic locally recoverable codes (LRCs) as base codes in the framework, the master can recover the desired $K_c$ linear combinations by contacting fewer than $N-S$ workers under many straggler scenarios. This essentially softens the straggler threshold without increasing the computation load or communication cost. Finally, we extend the construction to reduce the per-worker communication load by a factor of $m$, while achieving an asymptotically optimal computation load of $M=\frac{K}{N}(S+mK_c)$.

0.20

Task-Sufficient Contraction: Source Selection for Machine Information Interfaces

cs.IT cs.LG ·2026-10-06 ·Joss Armstrong
similarity 0.58
Abstract · 19 pages, 1 figure, 1 table. An earlier version was first posted on Zenodo in September 2026 (v1: doi:10.5281/zenodo.22834532; all versions:…

A declared task can sometimes certify a reduced source before a downstream encoder, codebook, rate, distortion target, or optimizer is chosen. This paper studies when one such reduction preserves the complete downstream problem family, a property termed Task-Sufficient Contraction. The reduced source is fixed by the task before the later operating point is selected. An exact contraction allows the later problem to be solved on that source with the same result as if the full source had been retained. For a machine with a fixed set of possible actions and a fixed loss, the paper identifies a consumer-specific source by merging states only when every available action has the same regret in both. For finite action sets, replacing the richer source by this reduced source preserves the complete one-step rate-regret curve, even though the reduction is fixed before the distortion target is chosen. A second result gives an exact characterization for quadratic loss on affine feasible-action sets: the canonical reduced source is the projection onto the directions in which feasible actions can differ. Under a fixed energy budget, this becomes centered load, while retaining only the optimal water-filled action is too coarse. Earlier Information Bottleneck, semantic rate-distortion, and goal-oriented quantization results are then used to distinguish exact, architecture-conditioned, approximate, failed, and corrected contractions. The framework suggests a way for heterogeneous machines to exchange what a receiving task needs without first aligning their full internal representations.

0.32

The Bell Boundary of Shared Representations

cs.LG cs.CL ·2026-10-12 ·Yang Wu, Hanyu Zhao, Yazhou Zhang, Yuexian Hou
theory similarity 0.58
Abstract

When does a shared representation become insufficient for jointly supporting multiple tasks? This question lies at the heart of multi-task learning models. Although task interference in shared representations has been widely observed, its onset, measurable form, and capacity boundary remain poorly understood. In this paper, we revisit this problem through the lens of Bell's theorem. We show that if four binary task outcomes can be jointly represented by a common shared representation, their correlations must satisfy the classical CHSH bound $|S|\leq2$. We introduce NCnet, a controlled multi-task model for studying how representational capacity affects task compatibility. Experiments reveal a clear capacity-dependent transition. Once nontrivial task fitting emerges, constrained capacity can yield $|S|>2$. As capacity further increases, these exceedances progressively disappear and $S$ returns to the bounded region. This systematic pattern provides evidence that limited representational capacity is an important source of the observed incompatibility. We observe similar transitions across CNNs, PLMs, and LLMs, suggesting that the phenomenon extends beyond the controlled NCnet setting. We refer to this capacity-dependent transition as the Bell Boundary, providing a measurable diagnostic for representation bottlenecks, task incompatibility, and capacity allocation in multi-task models.

0.24

MoRE: Scaling mixture of experts with hardware-aware low-rank routing

cs.LG cs.AIcs.CLstat.ML ·2026-09-28 ·Honam Wong, Surbhi Goel, Enric Boix-Adserà
theorycode/data similarity 0.57
Abstract

Mixture-of-Experts (MoE) layers are central to frontier language models, and recent architectures push toward more and smaller experts. In this regime, the standard linear router becomes a bottleneck: with $M$ experts and hidden dimension $h$, its per-token cost $Θ(Mh)$ dominates the MoE layer once $M$ is large. We introduce MoRE (Mixture of Rank-reduced-routed Experts), which factorizes the router weight matrix at rank $r$ and reduces the routing cost to $O((h + M)r)$. We prove that rank logarithmic in $M$ suffices for routing expressivity when the number of active experts is fixed, and is necessary up to precision factors. We also prove that logarithmic rank preserves load balance in a Gaussian memorization model, and training on a synthetic phonebook task shows that low rank does not hurt memorization. At matched active FLOPs, the factorization allows a factor of $Θ(h/r)$ more experts. To realize this gain in wall-clock time, we design a fused Triton kernel at inference that avoids expensive memory operations on HBM. Empirically, MoRE improves memorization on the phonebook task and performance on knowledge-intensive Q\&A benchmarks after pretraining, while matching reasoning ability. Code available at https://github.com/Matheart/MoRE_code.

0.33

Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More

cs.LG ·2026-10-07 ·Zhaohua Chen
benchmark similarity 0.57
Abstract

We study finite-horizon online resource allocation with i.i.d. requests and an endogenous Markov state on a finite state space: each action affects the transition of the state that governs future rewards and resource consumption. In this problem, a transient fluid LP benchmark upper bounds the expected reward of every nonanticipating policy, while a stationary LP supplies randomized state-dependent controls. We assume that the stationary LP has a unique optimum and identify primal nondegeneracy and irreducibility of the optimal induced kernel as important regularity conditions in this framework. With a known request prior, we show that, under nondegeneracy and irreducibility, both frequent and infrequent re-solving attain $O(1)$ regret. However, under a degenerate optimum, irreducibility yields the sharp worst-case $Θ(\sqrt{T})$ rate for infrequent re-solving, while frequent re-solving can incur $Ω(T)$ regret. Thus, more frequent optimization can perform asymptotically worse. With an unknown request prior, we develop a three-phase U-shaped infrequent re-solving policy that coordinates learning and inventory correction with $O(\log\log T)$ LP solves. When the optimal induced kernel is irreducible and the algorithm is given the optimal target state class and a constant-cost entrance policy, it attains $O(1)$ regret under nondegeneracy and $O(\sqrt{T})$ regret under degeneracy. Without the target-class information, linear minimax regret is unavoidable. Numerical experiments further illustrate the instability of round-by-round re-solving relative to epoch-wise infrequent re-solving, show that thresholding greatly mitigates its loss, and find that infrequent schemes remain dominant under both known and estimated priors.

0.19

When Does Less Information Pay? An Exact Finite Atlas of Representation, Payoff, and Cost

cs.AI ·2026-11-12 ·Aleksandr M. Shtraukh-Adamsky, Vladimir M. Adamsky, Irina G. Voloshina, Artemiy D. Spitsyn
similarity 0.57
Abstract · 40 pages, 5 figures; supplementary material included. Code, data and Russian translation: https://doi.org/10.5281/zenodo.23868864

A representation that retains one bit about a four-state world can solve a task perfectly, while another that retains 1.5 bits on average reaches only 75% accuracy. The difference lies in which distinctions each representation preserves. We examine this relationship in a uniform four-state world by enumerating all admissible representations and binary action rules. Constructions are compared both by replacing one component while holding the others fixed and by choosing the best action rule separately for each module. We consider three tasks, their mixtures, and four separate hypothetical cost tariffs. In some comparisons, the representation retaining less world information has the higher payoff; in others, the more informative representation does. There are also pairs with different information amounts but equal payoff--that is, equal task accuracy. If a representation preserves all existing distinctions and adds new ones, its best zero-cost payoff cannot decrease. Lower-information advantages therefore depend on which distinctions are retained. Equal counts of opposing advantages under representation replacement follow from coding symmetry. In broader comparisons, the shares depend on how repeated realizations are counted. A different task set or resource price can change which member of a fixed pair performs better. These results are exact, complete censuses of the specified finite sets of constructions and comparisons. The atlas provides a reproducible worked model for examining how action constraints, counting rules, and cost assumptions affect comparisons. It illustrates established distinctions between information quantity and decision value rather than proposing a new general law of their relation. $I(W;R)$ measures retained world information, and payoff measures task accuracy.

0.31

Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation

cs.AI cs.IT ·2026-09-24 ·Yezhou Cheng, Runjia Du, Zeming Liu, Qibai Chen, Hang Lyu +3 more
benchmarkhot direction similarity 0.57
Abstract

Repeated evaluation can estimate a benchmark score accurately while still requiring replication to certify narrow uncertainty. We characterize that requirement on a fixed grid of $M$ tasks with $L$ binary paths per task under the hard budget $(M+t)K$, where each path costs at most $K$ responses or episodes. For fixed $L \ge 3$ and $0 < α\le 1/12$, the optimal expected width on the worst pure cohort is $Θ_{α,L}([M(t+1)]^{-1/2})$ when every task is observed and $Θ_{α,L}([M(t+\sqrt{M})]^{-1/2})$ when omission is allowed. The lower bounds cover adaptive hard-budget policies, and fixed random-subset designs attain both rates through disagreement certificates. A joint mean/disagreement interval turns the task-covering law into practical finite-budget inference. In an equal-budget LiveCodeBench replay with 16 models, 880 tasks, and five outputs per task, the task-covering design reduces median point-estimation MSE by 87.0\% relative to pooled uniform sampling, while the Joint certificate produces narrower confidence intervals in 15/16 panels and reduces median interval width by 30.6\%. Finite-regime analyses identify task coverage as the effective choice at the evaluated scale and characterize how cohort size and within-task agreement determine the useful operating region. Together, the sharp laws and fixed-budget evidence make replication and task coverage explicit design variables for information-efficient repeated evaluation.

0.57

Scheduling to Maximize Weighted Throughput with an Active-Time Budget

cs.DS ·2026-08-29 ·Susanne Albers, G. Wessel van der Heijden
publishedtheory similarity 0.57
Abstract · 16 pages, 5 figures, To appear at WAOA 2026

We study the active-time scheduling problem with weighted throughput maximization. In this setting, a set of $n$ jobs $J$ arrive at integer release times, each with an integer processing time and integer deadline. Jobs may be preempted at integer time slot boundaries. A schedule assigns jobs to time slots, with at most $m$ jobs assigned to the same time slot. A slot is called \emph{active} if at least one job is scheduled in it. Instead of scheduling all jobs to minimize the number of active time slots, we consider the more general variant of \emph{weighted throughput} with an active-time budget $K$, where each job $j\in J$ has a weight $w_j$. The objective is to maximize the total weight of \emph{completed} jobs using at most $K$ active time slots. This means that partially scheduled jobs do not count towards the objective. The classical active-time minimization problem is recovered by asking whether all jobs can be completed within a given active-time budget. We give hardness, approximation, and exact algorithmic results. For general intervals with unbounded parallelism, we prove NP-hardness, rule out an FPTAS unless $\mathrm{P}=\mathrm{NP}$, and give a pseudo-polynomial time $Ω(1/\log K)$-approximation. For proper intervals, we prove a canonical structural lemma and obtain an exact $(nK)^{O(m)}$-time algorithm. For laminar intervals, we give an exact $f(K,m)\cdot n^{O(1)}$-time algorithm.

0.25