Greedy reicht: Sparse Action Discovery in Agentic LLMs

Moderne agentische Systeme arbeiten in Umgebungen mit extrem großen Aktionsräumen – etwa Sprachmodelle, die tausende APIs oder Abrufoperationen zur Verfügung haben. Trotz dieser Größe zeigen empirische Befunde, dass nur ein winziges Teil dieser Aktionen tatsächlich die Leistung in einer konkreten Anwendung beeinflusst.

Die Autoren untersuchen ein kontextuelles lineares Belohnungsmodell, bei dem die Relevanz der Aktionen durch eine strukturiert-sparse Annahme bestimmt wird: Nur wenige Aktionen haben über die latenten Zustände hinweg nicht‑null Effekte. Sie formulieren die Entdeckung relevanter Aktionen als ein Block‑Sparse‑Recovery‑Problem und analysieren einen Greedy‑Algorithmus, der sich an der Orthogonal Matching Pursuit orientiert.

Unter üblichen Voraussetzungen zu Inkoherence, Signalstärke und Aktionsabdeckung zeigen sie, dass der Greedy‑Ansatz mit hoher Wahrscheinlichkeit genau die relevanten Aktionsmenge rekonstruiert. Die benötigte Stichprobengröße skaliert polynomial in der Sparsitätsstufe und der latenten Dimension, aber nur logarithmisch in der Gesamtzahl der Aktionen. Zusätzlich liefern sie Schätzfehler‑Garantien für die nachgerechneten Parameter und zeigen, dass die daraus resultierende Entscheidungsregel für neue latente Zustände nahezu optimal ist.

Die Arbeit ergänzt diese Resultate durch informationstheoretische Untergrenzen, die belegen, dass sowohl Sparsität als auch ausreichende Abdeckung für die Trächtlichkeit der Problemstellung notwendig sind. Zusammen unterstreichen die Ergebnisse, dass die Entdeckung sparsamer Aktionen ein grundlegendes Prinzip im Entscheidungsprozess großer Aktionsräume darstellt und eine theoretische Basis für Aktionspruning in agentischen Systemen bietet.