What Must Survive? Exact Task-Information--State Frontiers for Resource-Sufficient Learning

arXiv:2609.21523v1 Announce Type: new Abstract: A system may be compressed before its downstream task is fully known. We ask how much retained state is then necessary and how much can be saved by limited advance task information. For a finite family of linear tasks, a task message is revealed before state formation and the exact task only afterwards. For an advice alphabet of size K, the exact frontier is [ p^*(K)= min_{substack{Pcalext{ partition of }U |Pcal|le K}} max_{CinPcal}rank(T_C), ] with the b-bit frontier obtained by setting K=min(2^b,|U|). Thus advance task information reduces state through partitions whose joint task operators have low rank. We also give an approximate singular-value frontier, a common-core lower bound and exact direct-sum law, and strong NP-hardness of finding an optimal advice partition. The hardness persists at every fixed positive approximation tolerance. Three examples illustrate the result. A well-conditioned softmax attention construction gives an exact 524{,}288o1{,}024 coordinate frontier when nine bits resolve one of 512 continuations. A domain-decomposed digital twin yields an interface-plus-local-state law and a weighted partition problem for heterogeneous regions. A hierarchical multi-task model gives a two-stage frontier in which three bits reduce the required state from 3136 to 448 coordinates, with further task information approaching the irreducible 328-coordinate single-task floor.

Source: arXiv cs.LG | 2026-09-21