Sparsity Is Necessary: Polynomial-Time Stability for Agentic LLMs in Large Action Spaces

📄 arXiv: 2601.08271v1 📥 PDF

作者: Angshul Majumdar

分类: cs.AI

发布日期: 2026-01-13

💡 一句话要点

针对大动作空间Agentic LLM，提出稀疏策略学习框架SAC以保证多项式时间稳定性。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: Agentic LLM 稀疏控制 序列决策 工具增强 策略学习 凸优化 压缩感知

📋 核心要点

  1. 现有工具增强LLM在巨大动作空间中进行序列决策时，面临着样本效率和稳定性的挑战，因为只有少量工具是相关的。
  2. 论文提出稀疏Agentic控制（SAC）框架，利用策略的稀疏性，通过ell_{1,2}-正则化学习，提高学习效率和稳定性。
  3. 理论分析表明，SAC框架在特定条件下能够实现精确的工具支持恢复，并且性能优于密集策略，验证了稀疏性的必要性。

📝 摘要（中文）

工具增强的LLM系统展现了一种控制机制，而学习理论在很大程度上忽略了它：即在巨大的离散动作空间（工具、API、文档）中进行序列决策，其中只有一小部分未知的子集与任何固定的任务分布相关。我们将此设置形式化为稀疏Agentic控制（SAC），其中策略允许在M >> 1个动作上进行块稀疏表示，并且奖励取决于稀疏的主效应和（可选的）稀疏协同效应。我们研究了通过凸代理的ell_{1,2}-正则化策略学习，并建立了清晰的、压缩感知风格的结果：（i）在Policy-RSC条件下，估计和价值次优性与k (log M / T)^{1/2}成比例；（ii）当T > k log M时，在不相干性和beta-min条件下，通过原始-对偶见证参数保持精确的工具支持恢复；（iii）任何密集策略类都需要Omega(M)个样本，这解释了仅提示控制器的不稳定性。我们进一步表明，在部分可观察性下，LLM仅通过信念/表示误差epsilon_b起作用，从而产生一个附加的O(epsilon_b)退化，同时保持对M的对数依赖性。扩展包括免调优、在线、鲁棒、组稀疏和交互感知SAC。

🔬 方法详解

问题定义：论文旨在解决工具增强的LLM在巨大离散动作空间中进行序列决策时遇到的样本效率和稳定性问题。现有方法，如直接使用prompt进行控制，由于需要大量的样本来覆盖整个动作空间，因此效率低下且不稳定。核心问题在于如何有效地从大量的候选动作中学习到真正相关的动作子集。

核心思路：论文的核心思路是利用策略的稀疏性。假设在任何给定的任务分布下，只有一小部分工具或动作是真正相关的。通过引入稀疏性约束，可以显著减少需要学习的参数数量，从而提高学习效率和稳定性。具体来说，论文假设策略可以用块稀疏表示来表达，并且奖励函数也具有稀疏的主效应和协同效应。

技术框架：论文提出的SAC框架主要包括以下几个阶段：1) 将工具增强的LLM系统形式化为稀疏Agentic控制问题；2) 引入ell_{1,2}-正则化来约束策略的稀疏性；3) 使用凸代理函数进行策略学习；4) 通过理论分析，证明在特定条件下，该方法能够实现精确的工具支持恢复，并具有良好的样本复杂度。

关键创新：论文最重要的技术创新在于将稀疏性假设引入到Agentic LLM的策略学习中，并提出了相应的SAC框架。与现有方法相比，SAC框架能够显著减少需要学习的参数数量，从而提高学习效率和稳定性。此外，论文还提供了严格的理论分析，证明了SAC框架的有效性。

关键设计：论文的关键设计包括：1) 使用ell_{1,2}-正则化来约束策略的稀疏性，鼓励策略在不同的动作块上具有稀疏性；2) 使用凸代理函数进行策略学习，使得优化问题更容易求解；3) 引入Policy-RSC条件、不相干性和beta-min条件，用于保证理论分析的有效性。这些条件对策略空间和奖励函数进行了合理的约束。

📊 实验亮点

论文通过理论分析证明了SAC框架的有效性。具体来说，在Policy-RSC条件下，估计和价值次优性与k (log M / T)^{1/2}成比例。当T > k log M时，在不相干性和beta-min条件下，能够实现精确的工具支持恢复。此外，论文还证明了任何密集策略类都需要Omega(M)个样本，这解释了仅提示控制器的不稳定性。

🎯 应用场景

该研究成果可应用于各种工具增强的LLM系统，例如智能助手、自动化流程、软件开发等。通过利用稀疏性，可以显著提高这些系统在复杂任务中的性能和效率，降低部署成本，并提升用户体验。未来的研究可以进一步探索如何将该框架应用于更广泛的Agentic LLM场景。

📄 摘要（原文）

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.