dorsal/arxiv
View SchemaSparsity Is Necessary: Polynomial-Time Stability for Agentic LLMs in Large Action Spaces
| Authors | Angshul Majumdar |
|---|---|
| Categories | |
| ArXiv ID | 2601.08271vv1 |
| URL | https://arxiv.org/abs/2601.08271 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
Tool-augmented LLM systems expose a control regime that learning theory has largely ignored: sequential decision-making with a massive discrete action universe (tools, APIs, documents) in which only a small, unknown subset is relevant for any fixed task distribution. We formalize this setting as Sparse Agentic Control (SAC), where policies admit block-sparse representations over M >> 1 actions and rewards depend on sparse main effects and (optionally) sparse synergies. We study ell_{1,2}-regularized policy learning through a convex surrogate and establish sharp, compressed-sensing-style results: (i) estimation and value suboptimality scale as k (log M / T)^{1/2} under a Policy-RSC condition; (ii) exact tool-support recovery holds via primal-dual witness arguments when T > k log M under incoherence and beta-min; and (iii) any dense policy class requires Omega(M) samples, explaining the instability of prompt-only controllers. We further show that under partial observability, LLMs matter only through a belief/representation error epsilon_b, yielding an additive O(epsilon_b) degradation while preserving logarithmic dependence on M. Extensions cover tuning-free, online, robust, group-sparse, and interaction-aware SAC.
{
"annotation_id": "7535e2ae-f320-4789-8a25-d7d86c5d2434",
"date_created": "2026-02-17T05:53:15.438000Z",
"date_modified": "2026-02-17T05:53:15.438000Z",
"file_hash": "990cca412c206efaf07f7bd60907475d32afb6b4240bc8c037f11bc86d5f1667",
"private": false,
"record": {
"abstract": "Tool-augmented LLM systems expose a control regime that learning theory has largely ignored: sequential decision-making with a massive discrete action universe (tools, APIs, documents) in which only a small, unknown subset is relevant for any fixed task distribution. We formalize this setting as Sparse Agentic Control (SAC), where policies admit block-sparse representations over M \u003e\u003e 1 actions and rewards depend on sparse main effects and (optionally) sparse synergies. We study ell_{1,2}-regularized policy learning through a convex surrogate and establish sharp, compressed-sensing-style results: (i) estimation and value suboptimality scale as k (log M / T)^{1/2} under a Policy-RSC condition; (ii) exact tool-support recovery holds via primal-dual witness arguments when T \u003e k log M under incoherence and beta-min; and (iii) any dense policy class requires Omega(M) samples, explaining the instability of prompt-only controllers. We further show that under partial observability, LLMs matter only through a belief/representation error epsilon_b, yielding an additive O(epsilon_b) degradation while preserving logarithmic dependence on M. Extensions cover tuning-free, online, robust, group-sparse, and interaction-aware SAC.",
"arxiv_id": "2601.08271",
"authors": [
"Angshul Majumdar"
],
"categories": [
"cs.AI"
],
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "Sparsity Is Necessary: Polynomial-Time Stability for Agentic LLMs in Large Action Spaces",
"url": "https://arxiv.org/abs/2601.08271",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "7906ed53-a699-4c4d-82e0-d74f1a27fdf5",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}