Bits Beat Tokens: A Regret Rate Distortion Theory for Large Language Model Agents

A language model agent acts on a context assembled by retrieval, summarisation, prompt templates, and memory. How many decision-relevant bits must this context carry before the agent can act with low regret? We give an answer that does not depend on the model, decoder, or scaffold. Modelling the agent as a Markov chain H→C→A and treating Bayes regret (the value gap between the chosen and the optimal action) as the distortion measure, we define a regret rate-distortion (RRD) function Rℓ(ε) whose converse is a one-line consequence of the data-processing inequality (DPI). A context that carries fewer than Rℓ(ε) bits cannot drive expected regret below ε, regardless of decoder, scaffold, scale, or chain-of-thought. For finite M-ary decisions under zero-one loss the bound reduces to the Fano floor in closed form, requiring ≈3.14 bits at (M=16, ε=0.1) and ≈6.73 bits at (M=256, ε=0.1). We instantiate the theory on 441 controlled single-step tool-selection cells, a balanced 16-way classification proxy spanning three open-source large language models (Qwen3-32B, Gemma3-27B, GLM-4-32B) and three public benchmarks (API-BANK, τ-bench, ToolBench). Because the gold tool index X=f(H) is a deterministic function of the history, the action-side rate IMM(X; A) lower-bounds the context capacity by data processing, so an action-side test of the converse is strictly tighter than a context-side one. Every cell respects the predicted floor (median margin +1.07 bits). Across 629 matched-rate pairs, 97.5% share overlapping regret confidence intervals (CIs), and a chain-of-thought supplement slides cells along the frontier rather than across it. The same data exposes a tokens-versus-bits gap reaching ∼1.7×10⁶:1, with the model extracting fewer than 0.05 bits about the gold action on a 32,768-token ToolBench prompt. In the single-step regime, the framework supplies a falsifiable, model-agnostic stopping criterion at IMM=Rℓ(ε) and reframes context engineering as an information-allocation problem.