Research map / Large language models / Agents, code and math

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

NeurIPS 2026 · Large language models › Agents, code and math · approach: Long-horizon LLM agents

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a rate-distortion theory for LLM agents that lower-bounds the decision-relevant bits a context must carry to achieve low Bayes regret, independent of model, decoder, or scaffold.

Problem

How many decision-relevant bits must the context assembled for a language model agent (via retrieval, summarisation, prompts, memory) carry before the agent can act with low regret?

Approach

Models the agent as a Markov chain H→C→A and treats Bayes regret (value gap between chosen and optimal action) as the distortion in a rate-distortion framework, yielding a model-, decoder-, and scaffold-independent bound on the context bits needed for low regret.

Experimental setup

Builds on: rate-distortion theory

Closest papers by meaning

• Remember the Decision, Not the Description: A Rate-Distortion Framework for Agent Memory (NeurIPS 2026 · similarity 0.90)
• On Bits and Bandits: Quantifying the Regret-Information Trade-off (ICLR 2025 · similarity 0.89)
• Evaluating Memory in LLM Agents via Incremental Multi-Turn Interactions (ICLR 2026 · similarity 0.88)
• AMA-Bench: Evaluating Long-Horizon Memory for Agentic Applications (ICML 2026 · similarity 0.88)
• Do LLM Agents Have Regret? A Case Study in Online Learning and Games (ICLR 2025 · similarity 0.87)
• Inference-Time Reward Hacking in Large Language Models (NeurIPS 2025 · similarity 0.87)