何以存续？资源充足学习中精确的任务信息-状态前沿

# What Must Survive?Exact Task-Information–State Frontiers for Resource-Sufficient Learning
Source: [https://arxiv.org/html/2609.21523](https://arxiv.org/html/2609.21523)
Ronald KatendeAddress:Department of Mathematics, Kabale University, Kabale, UgandaEmail address:[rkatende@kab\.ac\.ug](mailto:[email protected])

###### 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 sizeKK, the exact frontier is

p∗​\(K\)=min𝒫​partition of​𝒰\|𝒫\|≤K⁡maxC∈𝒫​rank⁡\(TC\),p^\{\*\}\(K\)=\\min\_\{\\begin\{subarray\}\{c\}\\mathcal\{P\}\\text\{ partition of \}\\mathcal\{U\}\\\\ \|\\mathcal\{P\}\|\\leq K\\end\{subarray\}\}\\max\_\{C\\in\\mathcal\{P\}\}\\operatorname\{rank\}\(T\_\{C\}\),with thebb\-bit frontier obtained by settingK=min⁡\(2b,\|𝒰\|\)K=\\min\(2^\{b\},\|\\mathcal\{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 exact524,288→1,024524\{,\}288\\to 1\{,\}024coordinate frontier when nine bits resolve one of512512continuations\. 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 from31363136to448448coordinates, with further task information approaching the irreducible328328\-coordinate single\-task floor\.

###### Key words and phrases:

task\-relative sufficiency, retained state, task side information, task partition, predictive state, attention memory, reduced\-order models, multi\-task representations

###### 2020 Mathematics Subject Classification

68Q32, 68T07, 65Y20, 94A15

## 1\.Problem setup

Task\-aware compression, predictive\-state representations, functional compression, and long\-context memory distinguish information needed for a future operation from information merely present in the current state\[[6](https://arxiv.org/html/2609.21523#bib.bib6),[2](https://arxiv.org/html/2609.21523#bib.bib2),[7](https://arxiv.org/html/2609.21523#bib.bib7),[11](https://arxiv.org/html/2609.21523#bib.bib11),[4](https://arxiv.org/html/2609.21523#bib.bib4)\]\. We study a specific worst\-case question: how many retained coordinates can limited information about a future task save?

Let

𝒰=\{1,…,m\}\\mathcal\{U\}=\\\{1,\\dots,m\\\}be a finite family of tasks with linear operators

Tu:ℝn→ℝru,u∈𝒰\.T\_\{u\}:\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}^\{r\_\{u\}\},\\qquad u\\in\\mathcal\{U\}\.The source state is

x∈𝔹2n:=\{x:‖x‖2≤1\}\.x\\in\\mathbb\{B\}\_\{2\}^\{n\}:=\\\{x:\\left\\lVert x\\right\\rVert\_\{2\}\\leq 1\\\}\.
Before a retained state is formed, an oracle reveals a deterministic advice symbol

a⁡\(u\)∈\[K\],K≤2b\.a\(u\)\\in\[K\],\\qquad K\\leq 2^\{b\}\.The encoder knowsa⁡\(u\)a\(u\)but not the exact taskuu\. After compression,uuis revealed\.

For each advice cell

a continuous encoder

ϕC:𝔹2n→ℝp\\phi\_\{C\}:\\mathbb\{B\}\_\{2\}^\{n\}\\to\\mathbb\{R\}^\{p\}is used\. Onceu∈Cu\\in Cis known, a continuous decoder

ψu:ℝp→ℝru\\psi\_\{u\}:\\mathbb\{R\}^\{p\}\\to\\mathbb\{R\}^\{r\_\{u\}\}must recoverTu​xT\_\{u\}x\. The common dimensionppis the retained\-state budget\.

ForC⊆𝒰C\\subseteq\\mathcal\{U\}, define the stacked operator

TC​x:=\(Tu​x\)u∈CT\_\{C\}x:=\\bigl\(T\_\{u\}x\\bigr\)\_\{u\\in C\}with Euclidean product norm\.

For

K∈\{1,…,m\},K\\in\\\{1,\\dots,m\\\},letp∗​\(K\)p^\{\*\}\(K\)be the least retained dimension allowing exact recovery for all tasks\. The correspondingbb\-bit quantity is

pb∗=p∗​\(min⁡\{2b,m\}\)\.p\_\{b\}^\{\*\}=p^\{\*\}\(\\min\\\{2^\{b\},m\\\}\)\.
For a linear operatorLL, write

rτ​\(L\):=\#⁡\{j:σj​\(L\)\>τ\},r\_\{\\tau\}\(L\):=\\\#\\\{j:\\sigma\_\{j\}\(L\)\>\\tau\\\},with singular values zero\-padded\.

## 2\.Exact and approximate frontiers

We first recall the continuous\-width identity used below\.

###### Lemma 2\.1\(Euclidean continuous width\)\.

Let

L:ℝn→ℝqL:\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}^\{q\}be linear\. Among continuous encoders

ϕ:𝔹2n→ℝp\\phi:\\mathbb\{B\}\_\{2\}^\{n\}\\to\\mathbb\{R\}^\{p\}and continuous decoders

ψ:ℝp→ℝq,\\psi:\\mathbb\{R\}^\{p\}\\to\\mathbb\{R\}^\{q\},infϕ,ψsup‖x‖2≤1‖L​x−ψ⁡\(ϕ⁡\(x\)\)‖2=σp\+1​\(L\)\.\\inf\_\{\\phi,\\psi\}\\sup\_\{\\left\\lVert x\\right\\rVert\_\{2\}\\leq 1\}\\left\\lVert Lx\-\\psi\(\\phi\(x\)\)\\right\\rVert\_\{2\}=\\sigma\_\{p\+1\}\(L\)\.In particular, exact recovery is possible if and only if

p≥rank⁡\(L\)\.p\\geq\\operatorname\{rank\}\(L\)\.

###### Proof\.

The truncated singular\-value decomposition gives the upper bound\.

For the lower bound, restrict to the unit sphere in the span of the firstp\+1p\+1right singular vectors\. Borsuk–Ulam givesxxsuch that

ϕ⁡\(x\)=ϕ⁡\(−x\)\.\\phi\(x\)=\\phi\(\-x\)\.A common decoded value cannot be within distance less than‖L​x‖2\\left\\lVert Lx\\right\\rVert\_\{2\}of bothL​xLxand−L​x\-Lx, while

‖L​x‖2≥σp\+1​\(L\)\.\\left\\lVert Lx\\right\\rVert\_\{2\}\\geq\\sigma\_\{p\+1\}\(L\)\.The exact statement follows by setting the error to zero\.

This is also the linear\-image specialization of the nonlinear\-width lower bound of DeVore–Howard–Micchelli\[[1](https://arxiv.org/html/2609.21523#bib.bib1), Theorem 3\.1\]\. In Hilbert space, the corresponding widths are determined by singular values\[[8](https://arxiv.org/html/2609.21523#bib.bib8), Chapter IV\]\. ∎

###### Theorem 2\.2\(Exact task\-information–state frontier\)\.

For every advice alphabet size

\(1\)p∗​\(K\)=min𝒫​partition of​𝒰\|𝒫\|≤K⁡maxC∈𝒫​rank⁡\(TC\)\.\\boxed\{p^\{\*\}\(K\)=\\min\_\{\\begin\{subarray\}\{c\}\\mathcal\{P\}\\text\{ partition of \}\\mathcal\{U\}\\\\ \|\\mathcal\{P\}\|\\leq K\\end\{subarray\}\}\\max\_\{C\\in\\mathcal\{P\}\}\\operatorname\{rank\}\(T\_\{C\}\)\.\}Consequently,

pb∗=p∗​\(min⁡\{2b,m\}\)\.p\_\{b\}^\{\*\}=p^\{\*\}\(\\min\\\{2^\{b\},m\\\}\)\.
Equivalently, define

κ\(p\):=min\{\|𝒫\|:𝒫partitions𝒰,maxC∈𝒫rank\(TC\)≤p\}\.\\kappa\(p\):=\\min\\Bigl\\\{\|\\mathcal\{P\}\|:\\mathcal\{P\}\\text\{ partitions \}\\mathcal\{U\},\\ \\max\_\{C\\in\\mathcal\{P\}\}\\operatorname\{rank\}\(T\_\{C\}\)\\leq p\\Bigr\\\}\.Then the minimum number of advice bits required for app\-dimensional exact state is

\(2\)b∗​\(p\)=⌈log2⁡κ⁡\(p\)⌉\.\\boxed\{b^\{\*\}\(p\)=\\left\\lceil\\log\_\{2\}\\kappa\(p\)\\right\\rceil\.\}

###### Proof\.

An advice map with at mostKKvalues is a partition𝒫\\mathcal\{P\}of𝒰\\mathcal\{U\}into at mostKKcells\.

Fix one cellCC\. If everyTuT\_\{u\},u∈Cu\\in C, factors through the samepp\-dimensional state, then the stacked mapTCT\_\{C\}also factors through that state\. By[lemma2\.1](https://arxiv.org/html/2609.21523#S2.Thmtheorem1),

p≥rank⁡\(TC\)\.p\\geq\\operatorname\{rank\}\(T\_\{C\}\)\.Hence every advice partition requires

p≥maxC∈𝒫⁡rank⁡\(TC\)\.p\\geq\\max\_\{C\\in\\mathcal\{P\}\}\\operatorname\{rank\}\(T\_\{C\}\)\.
Conversely, for each cellCC, choose a rank factorization

with

EC:ℝn→ℝrank⁡\(TC\)\.E\_\{C\}:\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}^\{\\operatorname\{rank\}\(T\_\{C\}\)\}\.StoreEC​xE\_\{C\}x\. Afteruuis revealed, select the corresponding output block ofDC​EC​xD\_\{C\}E\_\{C\}x\. Zero\-padding gives a common dimension

maxC∈𝒫⁡rank⁡\(TC\)\.\\max\_\{C\\in\\mathcal\{P\}\}\\operatorname\{rank\}\(T\_\{C\}\)\.Minimizing over partitions proves \([1](https://arxiv.org/html/2609.21523#S2.E1)\)\. Thebb\-bit statement follows from

K=min⁡\(2b,m\),K=\\min\(2^\{b\},m\),and \([2](https://arxiv.org/html/2609.21523#S2.E2)\) is the inverse form of the same frontier\. ∎

The frontier depends on joint row\-space geometry, not only on task count or individual task ranks\.

###### Corollary 2\.3\(Common\-core law\)\.

Let

Wu=row⁡\(Tu\),c:=dim\(⋂u∈𝒰Wu\),W\_\{u\}=\\operatorname\{row\}\(T\_\{u\}\),\\qquad c:=\\dim\\Bigl\(\\bigcap\_\{u\\in\\mathcal\{U\}\}W\_\{u\}\\Bigr\),and define

R:=rank⁡\(T𝒰\),rmax:=maxu⁡rank⁡\(Tu\)\.R:=\\operatorname\{rank\}\(T\_\{\\mathcal\{U\}\}\),\\qquad r\_\{\\max\}:=\\max\_\{u\}\\operatorname\{rank\}\(T\_\{u\}\)\.Then for every

\(3\)p∗​\(K\)≥max⁡\{rmax,c\+⌈R−cK⌉\}\.p^\{\*\}\(K\)\\geq\\max\\left\\\{r\_\{\\max\},\\,c\+\\left\\lceil\\frac\{R\-c\}\{K\}\\right\\rceil\\right\\\}\.
Suppose further that

Wu=W0⊕Vu,dimW0=c,dimVu=g,W\_\{u\}=W\_\{0\}\\oplus V\_\{u\},\\qquad\\dim W\_\{0\}=c,\\qquad\\dim V\_\{u\}=g,and

W0⊕⨁u∈𝒰VuW\_\{0\}\\oplus\\bigoplus\_\{u\\in\\mathcal\{U\}\}V\_\{u\}is a direct sum\. Then

\(4\)p∗​\(K\)=c\+g⁡⌈mK⌉\.\\boxed\{p^\{\*\}\(K\)=c\+g\\left\\lceil\\frac\{m\}\{K\}\\right\\rceil\.\}

###### Proof\.

Every cell span contains the common core\. After quotienting by that core,R−cR\-cis at most the sum of the quotient dimensions of the cells\. Hence at least one cell has quotient dimension at least

⌈R−cK⌉\.\\left\\lceil\\frac\{R\-c\}\{K\}\\right\\rceil\.Together with the single\-task lower bound, this proves \([3](https://arxiv.org/html/2609.21523#S2.E3)\)\.

Under the direct\-sum hypothesis,

rank⁡\(TC\)=c\+g​\|C\|\.\\operatorname\{rank\}\(T\_\{C\}\)=c\+g\|C\|\.Every partition into at mostKKcells contains a cell of size at least

⌈mK⌉,\\left\\lceil\\frac\{m\}\{K\}\\right\\rceil,and a balanced partition attains this value\. ∎

###### Corollary 2\.4\(Strong NP\-hardness of optimal advice partition\)\.

Given an explicitly represented linear task family and an advice budgetKK, deciding whether

is strongly NP\-complete, even when the task row spaces are pairwise disjoint coordinate subspaces and have no common core\.

###### Proof\.

Membership in NP follows by supplying a partition and computing the ranks of its stacked operators\.

For hardness, reduce from strongly NP\-complete3\-Partition\[[3](https://arxiv.org/html/2609.21523#bib.bib3)\]\. Given integers

a1,…,a3​Ja\_\{1\},\\ldots,a\_\{3J\}satisfying

∑iai=J​B,B4<ai<B2,\\sum\_\{i\}a\_\{i\}=JB,\\qquad\\frac\{B\}\{4\}<a\_\{i\}<\\frac\{B\}\{2\},create3​J3Jtasks whose row spaces are mutually disjoint coordinate subspacesViV\_\{i\}with

dimVi=ai,\\dim V\_\{i\}=a\_\{i\},and set

For every cellCC,

rank⁡\(TC\)=∑i∈Cai\.\\operatorname\{rank\}\(T\_\{C\}\)=\\sum\_\{i\\in C\}a\_\{i\}\.Therefore

if and only if the tasks can be partitioned intoJJtriples of sumBB\.

Strong NP\-hardness ensures that the explicit ambient dimension

is polynomially bounded in the restricted instances\. ∎

We next allow nonzero recovery error\.

###### Theorem 2\.5\(Robust approximate frontier\)\.

For a cellCC, define

Epmax​\(C\):=infϕC,\{ψu\}sup‖x‖2≤1maxu∈C⁡‖Tu​x−ψu​\(ϕC​\(x\)\)‖2\.E\_\{p\}^\{\\max\}\(C\):=\\inf\_\{\\phi\_\{C\},\\\{\\psi\_\{u\}\\\}\}\\sup\_\{\\left\\lVert x\\right\\rVert\_\{2\}\\leq 1\}\\max\_\{u\\in C\}\\left\\lVert T\_\{u\}x\-\\psi\_\{u\}\(\\phi\_\{C\}\(x\)\)\\right\\rVert\_\{2\}\.Then

\(5\)σp\+1​\(TC\)\|C\|≤Epmax​\(C\)≤σp\+1​\(TC\)\.\\frac\{\\sigma\_\{p\+1\}\(T\_\{C\}\)\}\{\\sqrt\{\|C\|\}\}\\leq E\_\{p\}^\{\\max\}\(C\)\\leq\\sigma\_\{p\+1\}\(T\_\{C\}\)\.
LetpK,ε∗p^\{\*\}\_\{K,\\varepsilon\}be the least retained dimension achieving branchwise error at mostε\\varepsilonwith at mostKKadvice symbols\. Then

\(6\)min\|𝒫\|≤K⁡maxC∈𝒫​r\|C\|​ε​\(TC\)≤pK,ε∗≤min\|𝒫\|≤K⁡maxC∈𝒫​rε​\(TC\)\.\\boxed\{\\min\_\{\\begin\{subarray\}\{c\}\|\\mathcal\{P\}\|\\leq K\\end\{subarray\}\}\\max\_\{C\\in\\mathcal\{P\}\}r\_\{\\sqrt\{\|C\|\}\\varepsilon\}\(T\_\{C\}\)\\leq p^\{\*\}\_\{K,\\varepsilon\}\\leq\\min\_\{\\begin\{subarray\}\{c\}\|\\mathcal\{P\}\|\\leq K\\end\{subarray\}\}\\max\_\{C\\in\\mathcal\{P\}\}r\_\{\\varepsilon\}\(T\_\{C\}\)\.\}Thebb\-bit quantity is

pmin⁡\(2b,m\),ε∗,p^\{\*\}\_\{\\min\(2^\{b\},m\),\\varepsilon\},and the exact frontier is recovered at

###### Proof\.

A decoder for the stacked operator controls every branch, so[lemma2\.1](https://arxiv.org/html/2609.21523#S2.Thmtheorem1)gives

Epmax​\(C\)≤σp\+1​\(TC\)\.E\_\{p\}^\{\\max\}\(C\)\\leq\\sigma\_\{p\+1\}\(T\_\{C\}\)\.
Conversely, branchwise error at mosteegives stacked Euclidean error at most

Hence

σp\+1​\(TC\)≤\|C\|​Epmax​\(C\)\.\\sigma\_\{p\+1\}\(T\_\{C\}\)\\leq\\sqrt\{\|C\|\}\\,E\_\{p\}^\{\\max\}\(C\)\.Thresholding these inequalities and optimizing over partitions with at mostKKcells proves \([6](https://arxiv.org/html/2609.21523#S2.E6)\)\. ∎

###### Corollary 2\.6\(Positive\-tolerance partition design is strongly NP\-hard\)\.

Fix any constant

Given an explicitly represented linear task family and advice budgetKK, deciding whether

pK,ε∗≤Bp^\{\*\}\_\{K,\\varepsilon\}\\leq Bis strongly NP\-hard\.

###### Proof\.

Use the disjoint\-coordinate reduction from[corollary2\.4](https://arxiv.org/html/2609.21523#S2.Thmtheorem4), with3​J3Jtasks and

and multiply every task operator by

λ=\(⌈ε⌉\+1\)​3​J\.\\lambda=\(\\lceil\\varepsilon\\rceil\+1\)3J\.Every nonzero singular value of every stacked operator is thenλ\\lambda\.

If

p<rank⁡\(TC\),p<\\operatorname\{rank\}\(T\_\{C\}\),then \([5](https://arxiv.org/html/2609.21523#S2.E5)\) gives

Epmax​\(C\)≥λ\|C\|≥λ3​J\>ε\.E\_\{p\}^\{\\max\}\(C\)\\geq\\frac\{\\lambda\}\{\\sqrt\{\|C\|\}\}\\geq\\frac\{\\lambda\}\{\\sqrt\{3J\}\}\>\\varepsilon\.Thus error at mostε\\varepsilonis possible on a cell exactly when its retained dimension is at least its rank\.

The approximate instance therefore has the same feasible advice partitions as the exact3\-Partitionreduction\. The scaling is polynomial in the strongly bounded instance size\. ∎

## 3\.Examples

### 3\.1\.Long\-context attention

A useful rank separation should remain visible numerically\. Consider the following softmax construction\.

Let

s=m​g,dk=s,s=mg,\\qquad d\_\{k\}=s,take keys

kj=ej∈ℝs,k\_\{j\}=e\_\{j\}\\in\\mathbb\{R\}^\{s\},and queries

qi=s​α​ei,α=log⁡\(s\+1\)\.q\_\{i\}=\\sqrt\{s\}\\,\\alpha e\_\{i\},\\qquad\\alpha=\\log\(s\+1\)\.Scaled dot\-product attention then has logitsα​Is\\alpha I\_\{s\}, giving

\(7\)A=softmax⁡\(α​Is\)=12​Is\+12​s​𝟏𝟏⊤\.A=\\operatorname\{softmax\}\(\\alpha I\_\{s\}\)=\\frac\{1\}\{2\}I\_\{s\}\+\\frac\{1\}\{2s\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\.Its singular values are11once and1/21/2with multiplicitys−1s\-1, so

κ2​\(A\)=2\.\\kappa\_\{2\}\(A\)=2\.
Partition thessrows intommdisjoint blocksIuI\_\{u\}ofggrows, and letRuR\_\{u\}select blockIuI\_\{u\}\. For value widthdvd\_\{v\}, define

T~u=Idv⊗\(Ru​A\)\.\\widetilde\{T\}\_\{u\}=I\_\{d\_\{v\}\}\\otimes\(R\_\{u\}A\)\.SinceAAis invertible, a stacked set of\|C\|\|C\|distinct row blocks has rank

Therefore[theorem2\.2](https://arxiv.org/html/2609.21523#S2.Thmtheorem2)gives

\(8\)p∗\(K\)=dvg⌈mK⌉,1≤K≤m\.\\boxed\{p^\{\*\}\(K\)=d\_\{v\}g\\left\\lceil\\frac\{m\}\{K\}\\right\\rceil,\\qquad 1\\leq K\\leq m\.\}Forbbadvice bits,

K=min⁡\(2b,m\)\.K=\\min\(2^\{b\},m\)\.
Moreover,

A2⪰14​I\.A^\{2\}\\succeq\\tfrac\{1\}\{4\}I\.Hence every row\-selected Gram matrix

RC​A2​RC⊤R\_\{C\}A^\{2\}R\_\{C\}^\{\\top\}has eigenvalues in\[1/4,1\]\[1/4,1\], so every nonzero singular value ofRC​AR\_\{C\}Alies in

Thus the rank in \([8](https://arxiv.org/html/2609.21523#S3.E8)\) is stable at every threshold

For

m=512,g=8,dv=128,m=512,\\qquad g=8,\\qquad d\_\{v\}=128,the exact frontier is

advance task bitsbb01369required coordinatespb∗p\_\{b\}^\{\*\}5242882621446553681921024
Nine bits identify one of512512continuation blocks and reduce the retained state by a factor of512512while the attention operator remains uniformly well conditioned\. This differs from task\-aware KV methods such as DynamicKV\[[11](https://arxiv.org/html/2609.21523#bib.bib11)\], which address token selection rather than the exact pre\-continuation state dimension studied here\.

### 3\.2\.Domain\-decomposed digital twins

Consider a finite\-element or reduced\-order state

x=\(xΓ,x1,…,xm\),xΓ∈ℝrΓ,xu∈ℝgu\.x=\(x\_\{\\Gamma\},x\_\{1\},\\dots,x\_\{m\}\),\\qquad x\_\{\\Gamma\}\\in\\mathbb\{R\}^\{r\_\{\\Gamma\}\},\\qquad x\_\{u\}\\in\\mathbb\{R\}^\{g\_\{u\}\}\.HerexΓx\_\{\\Gamma\}contains globally coupled interface coordinates andxux\_\{u\}contains interior reduced coordinates for subdomainuu\.

Suppose the state is compressed before the region of interest is known, and taskuurequires

Tu​x=\(xΓ,xu\)\.T\_\{u\}x=\(x\_\{\\Gamma\},x\_\{u\}\)\.This is the coordinate structure produced by interface/interior decompositions such as static condensation and domain decomposition\[[9](https://arxiv.org/html/2609.21523#bib.bib9)\]\.

If

then[corollary2\.3](https://arxiv.org/html/2609.21523#S2.Thmtheorem3)gives

\(9\)p∗\(K\)=rΓ\+g⌈mK⌉,1≤K≤m\.\\boxed\{p^\{\*\}\(K\)=r\_\{\\Gamma\}\+g\\left\\lceil\\frac\{m\}\{K\}\\right\\rceil,\\qquad 1\\leq K\\leq m\.\}
For

m=64,rΓ=256,g=128,m=64,\\qquad r\_\{\\Gamma\}=256,\\qquad g=128,the required state is

8448\(b=0\),1280\(b=3\),384\(b=6\)\.8448\\quad\(b=0\),\\qquad 1280\\quad\(b=3\),\\qquad 384\\quad\(b=6\)\.The final

coordinates consist of the common interface state and the selected region’s local state\.

If the local dimensions are heterogeneous,

g1,…,gm,g\_\{1\},\\dots,g\_\{m\},then[theorem2\.2](https://arxiv.org/html/2609.21523#S2.Thmtheorem2)gives

\(10\)p∗​\(K\)=rΓ\+min𝒫​partition of​\[m\]\|𝒫\|≤K⁡max⁡∑u∈CC∈𝒫⁡gu\.p^\{\*\}\(K\)=r\_\{\\Gamma\}\+\\min\_\{\\begin\{subarray\}\{c\}\\mathcal\{P\}\\text\{ partition of \}\[m\]\\\\ \|\\mathcal\{P\}\|\\leq K\\end\{subarray\}\}\\max\_\{C\\in\\mathcal\{P\}\}\\sum\_\{u\\in C\}g\_\{u\}\.Thus an optimal region code balances reduced state dimension rather than the number of regions\.

### 3\.3\.Hierarchical multi\-task representations

Multi\-task compression can exploit structure shared across downstream tasks\[[4](https://arxiv.org/html/2609.21523#bib.bib4),[7](https://arxiv.org/html/2609.21523#bib.bib7)\]\. The frontier makes the effect of that structure explicit\.

Index tasks by

\(j,ℓ\),j∈\[q\],ℓ∈\[L\]\.\(j,\\ell\),\\qquad j\\in\[q\],\\qquad\\ell\\in\[L\]\.Assume their row spaces have the direct\-sum structure

\(11\)Wj,ℓ=W0⊕Gj⊕Vj,ℓ,dimW0=c,dimGj=h,dimVj,ℓ=g,W\_\{j,\\ell\}=W\_\{0\}\\oplus G\_\{j\}\\oplus V\_\{j,\\ell\},\\qquad\\dim W\_\{0\}=c,\\quad\\dim G\_\{j\}=h,\\quad\\dim V\_\{j,\\ell\}=g,where theGjG\_\{j\}are mutually independent and theVj,ℓV\_\{j,\\ell\}are mutually independent of each other and of the common and group spaces\.

HereW0W\_\{0\}is shared by all tasks,GjG\_\{j\}is shared within familyjj, andVj,ℓV\_\{j,\\ell\}is task\-specific\.

###### Proposition 3\.1\(Exact two\-level task\-information frontier\)\.

Assume

For every advice alphabet size

let

kK:=min⁡\{L,⌊Kq⌋\}\.k\_\{K\}:=\\min\\left\\\{L,\\left\\lfloor\\frac\{K\}\{q\}\\right\\rfloor\\right\\\}\.Then

\(12\)p∗​\(K\)=c\+h\+g⁡⌈LkK⌉\.\\boxed\{p^\{\*\}\(K\)=c\+h\+g\\left\\lceil\\frac\{L\}\{k\_\{K\}\}\\right\\rceil\.\}For

the frontier remains exactly characterized by[theorem2\.2](https://arxiv.org/html/2609.21523#S2.Thmtheorem2)\.

###### Proof\.

Because

there is a feasible partition that does not mix task families and assigns at least one cell to each family\. The coarsest such partition has maximum rank at most

c\+h\+g​L≤c\+2​h\.c\+h\+gL\\leq c\+2h\.
A cell containing tasks from two distinct families contains two independent group spaces and at least two independent task\-specific spaces\. Its rank is therefore at least

c\+2​h\+2​g\>c\+2​h\.c\+2h\+2g\>c\+2h\.Hence no optimal partition mixes families\.

Suppose familyjjreceives

cells\. Balanced partitioning within that family gives maximum rank

c\+h\+g​⌈Lkj⌉\.c\+h\+g\\left\\lceil\\frac\{L\}\{k\_\{j\}\}\\right\\rceil\.Since

∑jkj≤K,\\sum\_\{j\}k\_\{j\}\\leq K,some family satisfies

kj≤⌊Kq⌋=kK\.k\_\{j\}\\leq\\left\\lfloor\\frac\{K\}\{q\}\\right\\rfloor=k\_\{K\}\.This gives the lower bound in \([12](https://arxiv.org/html/2609.21523#S3.E12)\)\.

Assigning at leastkKk\_\{K\}cells to every family and balancing tasks within each family attains the same value\. ∎

Take

q=8,L=16,c=64,h=256,g=8\.q=8,\\qquad L=16,\\qquad c=64,\\qquad h=256,\\qquad g=8\.With no advice, the joint state has rank

64\+8​\(256\)\+128​\(8\)=3136\.64\+8\(256\)\+128\(8\)=3136\.At

bits, the advice can identify the task family, and[proposition3\.1](https://arxiv.org/html/2609.21523#S3.Thmtheorem1)gives

coordinates\. Further advice resolves tasks within each family\.

The floor

is the exact single\-task requirement\. The first three bits have the largest effect because they resolve the high\-dimensional family component\. The cases

remain exactly covered by[theorem2\.2](https://arxiv.org/html/2609.21523#S2.Thmtheorem2), but lie outside the closed\-form regime

of[proposition3\.1](https://arxiv.org/html/2609.21523#S3.Thmtheorem1)\.

## 4\.Relation to prior work

Several neighboring theories contain ingredients used here\.

Predictive\-state representations characterize state through predictions of future tests and relate linear state dimension to rank\[[6](https://arxiv.org/html/2609.21523#bib.bib6)\]\. Functional and multi\-functional source coding study communication needed to compute one or more functions, often with decoder side information and stochastic sources\[[2](https://arxiv.org/html/2609.21523#bib.bib2)\]\. Task\-aware co\-design shows in a linear single\-task setting that a representation of dimensionrank⁡\(K\)\\operatorname\{rank\}\(K\)can suffice for a task operatorKK\[[7](https://arxiv.org/html/2609.21523#bib.bib7)\]\. Linear sketching and workload\-aware query mechanisms construct compressed representations that support a declared workload\[[10](https://arxiv.org/html/2609.21523#bib.bib10),[5](https://arxiv.org/html/2609.21523#bib.bib5)\]\. Nonlinear\-width theory supplies the single\-operator identity in[lemma2\.1](https://arxiv.org/html/2609.21523#S2.Thmtheorem1)\[[1](https://arxiv.org/html/2609.21523#bib.bib1),[8](https://arxiv.org/html/2609.21523#bib.bib8)\]\. Recent systems work also adapts compression to downstream tasks in KV memory and multi\-task representation coding\[[11](https://arxiv.org/html/2609.21523#bib.bib11),[4](https://arxiv.org/html/2609.21523#bib.bib4)\]\.

The information ordering here is different\. The source statexxis available in full, but only a bounded message about the future task is known when the retained state is formed\. The exact task is revealed only afterwards\. The retained resource is continuous coordinate dimension under worst\-case exact or uniform approximate recovery\.

Within this model,[theorem2\.2](https://arxiv.org/html/2609.21523#S2.Thmtheorem2)reduces the task\-information–state tradeoff to a partition problem over stacked ranks, while[theorem2\.5](https://arxiv.org/html/2609.21523#S2.Thmtheorem5)gives the corresponding singular\-value bounds\. The hardness results show that the resulting advice partition need not be computationally easy to find\.

## 5\.Limitations

The results concern continuous retained coordinates rather than finite\-precision bits\. They also assume linear task operators\. Nonlinear tasks would require a different complexity measure, such as nonlinear widths or task\-conditioned local linearizations\.

The exact frontier \([1](https://arxiv.org/html/2609.21523#S2.E1)\) is variational rather than algorithmic\. By[corollaries2\.4](https://arxiv.org/html/2609.21523#S2.Thmtheorem4)and[2\.6](https://arxiv.org/html/2609.21523#S2.Thmtheorem6), finding an optimal partition is strongly NP\-hard in general, both exactly and at fixed positive tolerance\.

When the task operators or their geometry must themselves be estimated from data, statistical uncertainty enters in addition to the state and partitioning costs considered here\.

## References

- \[1\]R\. A\. DeVore, R\. Howard, and C\. Micchelli,Optimal nonlinear approximation,*Manuscripta Math\.*63\(1989\), 469–478\.
- \[2\]S\. Feizi and M\. Médard,Multi\-functional compression with side information,*IEEE Global Telecommunications Conference \(GLOBECOM\)*, 2009, 1–6\.
- \[3\]M\. R\. Garey and D\. S\. Johnson,*Computers and Intractability: A Guide to the Theory of NP\-Completeness*,W\. H\. Freeman, 1979\.
- \[4\]Z\. Huang, R\. Yuan, J\. Gao, Q\. Mao, S\. Ma, W\. Gao, and C\. Jia,Discovering adaptive task dependencies for efficient multi\-task representation compression,*Proc\. IEEE/CVF Conf\. Computer Vision and Pattern Recognition*, 2026, 5326–5336\.
- \[5\]C\. Li, M\. Hay, V\. Rastogi, G\. Miklau, and A\. McGregor,Optimizing linear counting queries under differential privacy,*Proc\. 29th ACM SIGMOD\-SIGACT\-SIGART Symp\. Principles of Database Systems \(PODS\)*, 2010, 123–134\.
- \[6\]M\. L\. Littman, R\. S\. Sutton, and S\. Singh,Predictive representations of state,*Advances in Neural Information Processing Systems*14\(2001\), 1555–1561\.
- \[7\]M\. Nakanoya, S\. Chinchali, A\. Anemogiannis, A\. Datta, S\. Katti, and M\. Pavone,Co\-design of communication and machine inference for cloud robotics,*Robotics: Science and Systems XVII*, 2021, DOI:10\.15607/RSS\.2021\.XVII\.046\.
- \[8\]A\. Pinkus,*nn\-Widths in Approximation Theory*,Springer, 1985\.
- \[9\]A\. Toselli and O\. Widlund,*Domain Decomposition Methods—Algorithms and Theory*,Springer, 2005\.
- \[10\]D\. P\. Woodruff,Sketching as a tool for numerical linear algebra,*Foundations and Trends in Theoretical Computer Science*10\(2014\), no\. 1–2, 1–157\.
- \[11\]X\. Zhou, W\. Wang, M\. Zeng, J\. Guo, X\. Liu, L\. Shen, M\. Zhang, and L\. Ding,DynamicKV: Task\-aware adaptive KV cache compression for long context LLMs,*Findings of EMNLP*, 2025, 8042–8057\.