Agentic System as Compressor: Quantifying System Intelligence in Bits Zihan Qin∗ Peking University
Hongrui Zhang∗ Peking University
arXiv:2606.25960v1 [cs.AI] 24 Jun 2026
Abstract Large language models are turning from isolated predictors into agentic systems: they call tools, retrieve evidence, obey environment constraints, use verifiers, and complete tasks through search and multi-turn interaction. We adopts an analytical viewpoint based on “compression is intelligence”: under a fixed task distribution, interface, and compute budget, a stronger agentic system lets a target object be reconstructed with fewer bits. We operationalize the measure with arithmetic coding, seed coding, and a fallback, and evaluate it in five settings: reversed text, chess moves, protein sequences, retrieval-augmented question answering, and semantic story compression; in all of them agentic components reduce codelength. These small, controlled experiments cover component types typical of real agentic systems, show that codelength can analyze how components, observers, and budgets change residual uncertainty, and offer guidance for evaluating real agent systems.
1
Introduction
Large language models appear less and less as isolated predictors and more and more embedded in agentic systems that can call tools, retrieve evidence, read feedback, and interact with an environment (Lewis et al., 2020; Schick et al., 2023; Shinn et al., 2023; Yang et al., 2024; Yao et al., 2023b). In real deployments, intelligent behavior often arises from the whole workflow. That is, the capability deployed and used today is no longer just “model intelligence” but system intelligence formed jointly by the model, tools, environment interfaces, and interaction process. This creates a tension for evaluation. Standard benchmarks usually report accuracy, success rate, pass rate, or an aggregate score (Liang et al., 2022; Srivastava et al., 2022); these metrics indicate whether the system finally completes the task, but say little about where the capability comes from. When a system grows stronger, is it because the model itself predicts better, or because a retriever supplied evidence, a rule-based environment ruled out illegal actions, a verifier filtered out bad trajectories, or a search process found better candidates? How much does a given component actually contribute? When a task is hard, the success rate can stay near zero for a long time; both systems then “almost fail,” yet their reductions of the residual uncertainty over the target space may already differ enormously. The compression-as-intelligence viewpoint offers a finer analytical framework (Cover and Thomas, 2006; Delétang et al., 2024; Huang et al., 2024; Witten et al., 1987). Classical information theory shows that a predictive distribution can be turned into a lossless compressor and vice versa (Cover and Thomas, 2006; Witten et al., 1987); a language model induces token-level codelengths, making log-loss and bits-per-byte an operational compression rate (Delétang et al., 2024); and cross-model results further show that the compression rate is nearly linearly correlated with downstream capability (Huang et al., 2024). These works, however, mainly measure the bare model itself, without bringing tools, environment, retrieval, and the interaction process into the object of measurement. ∗
Equal contribution.
1
This paper therefore adopts agentic codelength as a system-level working measure. Intuitively, once the task distribution, observation standard, system interface, and coding protocol are fixed, the encoder need not transmit the target object in full; it sends only a per-instance code that lets a decoder sharing the same system conditions reconstruct the target. The more intelligent a system, the fewer residual bits it should require to reconstruct objects from the same distribution. Bare-model compression is just a special case: a system can choose to call no tools, do no retrieval, and no search, degenerating into ordinary model compression; conversely, when environment interaction provides usable structure, the system can turn that structure into a shorter per-instance code. To estimate this system compression ability, we combine the following three schemes into an executable compress–decompress protocol. First, arithmetic coding accumulates the negative log-likelihood (NLL) on a given output, turning model predictions into codelength, for cases where a specific output must be encoded exactly. Second, seed coding targets tasks in deterministic or replayable environments where qualifying outputs are dense enough within the sampling budget: it transmits a latent description plus the rank of the first successful random seed. Third, when seed coding fails within a finite budget, it falls back to arithmetic coding, so that every sample can be encoded successfully. We validate the framework in five settings: reversed text, chess, protein sequences, retrievalaugmented question answering, and semantic story compression. These settings respectively isolate several types of information source typical of agentic systems: deterministic tools, rule-based environments, scientific priors, verifier feedback, retrieval side information, semantic observers, and the sampling budget. Reversed text provides a minimal sanity check, testing whether a shared transform can move per-instance structure into the decoder; chess tests how environment constraints shrink the space of legal candidates; the protein experiments test both whether codelength can read out the value of template priors when the success rate has almost no resolution, and whether verifier feedback can reduce blind-search cost in functionally equivalent generation; RAG and story compression respectively test how external-evidence relevance, the observation standard, and the compute budget change the residual codelength. In short, the goal of this set of experiments is not to show that some agent achieves the highest score on a single task, but to verify that agentic codelength can serve as a unified accounting tool for residual uncertainty across different information sources and different success criteria. Our contributions are as follows. First, we are the first to understand the “compression is intelligence” view from the perspective of agentic systems rather than isolated models. Second, we give a marginal bit value metric for components, quantitatively analyzing the contribution of a specific component in a system via the average codelength reduction. Third, we combine arithmetic coding, seed replay, and fallback coding into an executable compress– decompress protocol. Fourth, we validate the effectiveness of this metric for analyzing system intelligence across five classes of tasks.
2
Related Work
2.1
Compression, intelligence, and “language models as compressors”
“Compression measures understanding” is a classical idea: in an appropriate sense, prediction and compression are interconvertible, and the two are essentially equivalent (Cover and Thomas, 2006; Witten et al., 1987). Recent discussions of large models, including Sutskever’s talk An Observation on Generalization, popularized a sharper operational reading: a predictor that assigns higher probability to a data distribution also induces a shorter code for samples from that distribution (Sutskever, 2023). This idea has a more systematic formalization in MDL (minimum description length) and universal coding. The Kraft–McMillan inequality shows that a uniquely decodable codelength function corresponds to a probability budget; and the log-loss risk − log q(x) of a probabilistic 2
Figure 1: Overview of agentic compression. Tools, constraints, context, search, and verifiers act as shared decoding resources, reducing the per-instance hint, seed/rank, and residual bits needed for a reconstruction accepted by the observer. model q is precisely the ideal description length it induces. Hence, learning within a model class M = {qθ } is not only a search for parameters with low predictive risk, but also a search for a description language that assigns short codes to data. The MDL principle writes this relationship as a two-part code or universal-coding criterion: choose an explanation by the sum of the model description length L(θ) and the residual data description length L(x | θ) ≃ − log qθ (x) (Barron et al., 1998; Grünwald, 2007; Rissanen, 1978). From this perspective, generalization can be understood as structure discovery in the compression sense: reusable regularities enter the shared model description, while sample-specific content remains in the residual codelength. Our most direct predecessor is the “language modeling is compression” line of work: an autoregressive model induces token-level codelengths, so log-loss and bits-per-byte provide an operational compression rate (Delétang et al., 2024). Cross-model measurements further show that the compression rate is nearly linearly correlated with downstream capability—the shorter the code, the stronger the model (Huang et al., 2024)—suggesting that compression ability is a useful measure of intelligence. These works, however, measure the compression rate of the bare model itself. They do not touch one reality: today’s models often do not work in isolation— they are embedded in agentic systems and, through tools, feedback, and multi-turn environment interaction, achieve capabilities well beyond the model proper. This paper aims precisely to extend the compression viewpoint from isolated models to entire agentic systems.
2.2
Agentic systems, tools, retrieval, and feedback
Modern work on agentic systems studies how models call tools, retrieve information, receive feedback, repair their own outputs, and act through multi-turn interaction. ReAct interleaves reasoning and acting (Yao et al., 2023b); Toolformer teaches a model to call APIs (Schick et al., 2023); RAG conditions generation on retrieved documents (Lewis et al., 2020); Reflexion uses verbal feedback to improve subsequent attempts (Shinn et al., 2023). On the reasoning side, chain-of-thought (Wei et al., 2022), self-consistency (Wang et al., 2023), and tree-of-thoughts
3
(Yao et al., 2023a) search over intermediate states. Recently, these techniques have been consolidated into a deliberate engineering practice— harness engineering: beyond strengthening the model proper, it emphasizes polishing the surrounding tools, environment interfaces, feedback loops, and context management, and improving the environment rather than blaming the model when an agent fails (OpenAI and Lopopolo, 2026). The OpenAI team, using the coding agent Codex as the sole executor and continually polishing the harness, produced production code on the order of a million lines within a few months (OpenAI and Lopopolo, 2026); on the open-source side, runtimes such as OpenClaw and Hermes Agent package “model + tools + environment + multi-turn loop” into a directly deployable harness and quickly became among the most watched projects in the community (Hermes Agent, 2026; OpenClaw, 2026).
2.3
Observational equivalence, semantic compression, and perceptual compression
Many compression tasks do not require byte-exact recovery, only that the reconstruction preserve key properties in the eyes of the target observer: perceptual codecs such as JPEG and MP3/AAC exploit the limited sensitivity of human vision and hearing to discard imperceptible detail (Brandenburg, 1999; Wallace, 1991), and perceptual-quality studies likewise point out a trade-off between pointwise distortion and “looking natural” (Blau and Michaeli, 2018). Semantic compression extends this idea to structured content: the reconstruction need not be identical token-by-token or byte-by-byte, only preserve the meaning, entities, events, function, or answer that the task cares about; relevant precedents include semantic compression in databases (Jagadish et al., 1999) and prompt/context compression in the LLM setting (Jiang et al., 2023). This paper further expresses such ideas as compression under observational equivalence; see Section 3.3.
3
Theory
We proceed in four steps. We first define agentic systems (Section 3.1), then give conditional compression (Section 3.2) and observational equivalence (Section 3.3). We then discuss agentic coding and component value within a fixed actual system (Section 3.4).
3.1
Definition of an agentic system
We model an agentic system as a triple A = (P, M, E), where P is a program containing the model interface and the environment interface; M is one or more model interfaces that map text to token distributions; and E is a set of environment interfaces, including retrievers, compilers, external APIs, and other tool-call interfaces. A resource constraint C is given as an external budget index at run and evaluation time, which can limit the total number of execution steps, model calls, tool calls, context length, wall-clock time, memory, cost, or any other constraint we care about. During execution, P may query M and E, update its state according to their return values, and continue computing until the resource constraint is exhausted. Hereafter we write AC for the run of system A under budget C. We stress that, in our setting, the encoder system Ae and the decoder system Ad are in general asymmetric. This differs from ordinary language-model arithmetic coding, in which a single model is bound symmetrically to the encoder and decoder, and coding and decoding are essentially tied to one and the same model distribution.
4
3.2
Conditional compression
Many of the tasks we discuss are naturally modeled as conditional compression tasks: an object does not appear in isolation but is given together with a problem statement, task specification, or other public context. Formally, data are given as condition–target pairs (c, x) ∼ D, where c is distribution-dependent side information shared and fixed by the encoder and decoder before any object is encoded. In our tasks, c is usually the problem statement or task specification. Conditional compression measures codelength given c: the encoder sends a per-instance description d = Enc(x; c), and the decoder computes Dec(d; c) and must recover x in the observational sense defined in Section 3.3. Only d counts toward codelength; c does not. We therefore measure the conditional codelength L(x | c), not the marginal codelength L(x). This cleanly separates the background shared by both sides from the extracted information that must be supplied per instance. It follows the conditional setting of Hsiao–Lu–Reyzin, in which the compressor and decompressor have access to side information (Hsiao et al., 2007), and makes the codelengths of different systems comparable under the same c.
3.3
Observational equivalence
Let O be a family of observations, where each o ∈ O maps an artifact to an observed value. We call y and x observationally equivalent when every observation agrees: y ≈O x ⇐⇒ ∀ o ∈ O, o(y) = o(x). Reconstruction succeeds as long as the decoder outputs any y satisfying y ≈O x. We write the equivalence class as [x]O = {y : y ≈O x}. Exact recovery is the special case where O distinguishes all points, in which the condition reduces to y = x. When O preserves task-relevant observations rather than bytes, the same formalization becomes a form of semantic compression. For example, the protein task (Section 5.1 and Appendix A.3) cares only about functional equivalence. A reconstruction y is accepted if and only if it agrees with the original sequence x (i.e. o(y) = o(x)) on the boolean observations specified by the verifier; residue-by-residue identity is not required. Verifiers as a special case. A verifier that checks whether a reconstruction y agrees with x on properties {oi } is exactly the observational equivalence y ≈O x with O = {oi }, whose acceptance set is the class [x]O . An “absolute” verifier V (y) ∈ {0, 1} independent of x also fits: since the original sequence satisfies V (x) = 1, writing o(y) = V (y) makes the acceptance condition V (y) = 1 equivalent to o(y) = o(x). Hence the codelength definition in Section 3.4 need not treat verifiers as a separate case.
3.4
Agentic coding and component value
We consider a fixed coding protocol in which the encoder and decoder are two agentic systems, Ae = (Pe , Me , Ee ),
Ad = (Pd , Md , Ed ).
Here Ae is the encoding-side system and Ad the decoding-side system; the two may use different programs and interfaces and are constrained by budgets Ce and Cd respectively. The encoder is usually allowed stronger offline search, such as enumerating candidate latents or random seeds; the decoder only replays the protocol given the message, the public condition, and its own budget. To make decoding verifiable, the protocol specifies the public condition c visible to both ends, the observation standard O, the model/tool versions, the randomness convention, and the interaction interfaces. We write the whole protocol as Π = (Ae , Ad , Ce , Cd , O). 5
In the conditional-compression setting, the encoding-side program reads the object x to be encoded and the public condition c, and produces a message m = Pe (x; c, Me , Ee , Ce ). The decoding-side program receives only m and the public condition c, then calls its own model interface, environment interface, and budget to output x̂ = Pd (m; c, Md , Ed , Cd ). If x̂ ≈O x, the message successfully reconstructs x under the observation standard O. Under the fixed protocol, we write the operational codelength of this instance as LΠ (x | c) = |m|. For a data distribution D, the system’s average codelength is L̄Π (D) = E(c,x)∼D LΠ (x | c). The average codelength measures this fixed protocol’s compression ability on the distribution: the shorter the average codelength, the less residual information each instance still needs after the public condition, decoding-side system, observation standard, and budget have all been given. For arithmetic coding realized by a predictive distribution, this quantity also equals the model’s average negative log-likelihood under the protocol; it can therefore be interpreted as a codelength characterization of predictive ability. To measure the value of a component g, we compare the average codelength of the same base protocol with and without g. Let Πg denote the protocol containing component g, and Π\g the baseline protocol with that component removed and the remaining data, observer, model version, and budget kept as fixed as possible; then we define ∆g = E(c,x)∼D LΠ\g (x | c) − E(c,x)∼D LΠg (x | c). ∆g is a marginal quantity: it measures the average codelength reduction from adding component g to a given baseline protocol, and can thus measure that component’s contribution to the system’s prediction and reconstruction ability. Along a fixed order of component additions, the successive marginal values sum to the total reduction; but when components interact, an individual ∆g depends on the baseline and the addition order.
4
Coding Schemes
The core problem in designing a coding scheme is that a model’s output is random. When an agentic system runs as the decoder, how do we pin down the model’s output each time with as short a code as possible? We introduce two methods—arithmetic coding and seed coding—for the cases “a specific output must be encoded exactly” and “there are many qualifying outputs,” respectively, and fall back to arithmetic coding when seed coding fails.
4.1
Arithmetic coding
Arithmetic coding is used to exactly encode a given piece of text: under context c, the model induces token-level distributions PM (· | x<t , c), and arithmetic coding takes their conditional probabilities token-by-token on the reference x, transmitting x unambiguously (we omit the details; see “language modeling as compression” (Delétang et al., 2024)). With the standard prefix-unambiguous termination, its codelength is LLM (x | c)+O(1), concretely dLLM (x | c)e+1, and thus exceeds the true NLL by fewer than 2 bits (Appendix B.1). Hereafter we mainly report NLL; this per-instance constant difference barely affects the conclusions. 6
4.2
Seed coding
If a desired output is dense enough under the LLM’s output distribution—i.e. very likely to be hit within the given sampling budget—then seed coding is usually more bit-efficient than arithmetic coding. The randomness of each model generation is determined by a random seed; given the seed, the output is deterministic. Let the sampling budget be N seeds (numbered 0, 1, . . . , N − 1). The encoder tries them in order from 0, takes a seed within budget whose output y ≈O x, and transmits its index with a fixed-length dlog2 N e-bit code; the decoder replays the same seed and obtains the same qualifying output. Hence the coding cost of this instance is just this fixedlength index of dlog2 N e bits. Because the sampling budget is generally low, this codelength generally does not dominate. The protocol premise of seed coding is replayability: the encoder and decoder must reproduce the same random trajectory under the same system conditions, including a fixed model, sampling algorithm, random seed, tool returns, and environment state. This paper uses seed coding only in deterministic or replayable environments; nondeterministic external services are out of scope. Seed coding is merely one way to operationalize an achievable codelength upper bound under a fixed protocol, and does not affect the theoretical analysis framework.
4.3
Fallback
If no seed within the sampling budget makes the output qualify, seed coding fails for that instance, and we fall back to arithmetic coding—which can always encode the reference x exactly, giving a definite codelength Lfallback,i . The two paths are distinguished by a 1-bit selector: the decoder reads this bit first, then decodes x via seed coding or arithmetic coding accordingly. Thus the codelength of each instance is Li = 1 + min{Lagent,i , Lfallback,i }, where Lagent,i = dlog2 N e (hit within budget), and on a miss we set Lagent,i = ∞, with arithmetic coding as the backstop.
5
Experiments
We use five sets of experiments to argue the following three claims. These experiments cover component types typical of real agentic systems (tools, rule-based environments, scientific templates, retrievers, semantic observers, and the search budget), but are deliberately kept small and controlled, so as to isolate mechanisms and test whether the framework can analyze system components. Accordingly, our experiments should be read as mechanistic arguments and exploratory evidence, not as a large-scale benchmark or a final evaluation of a deployed system. • Claim 1 (main claim: environment interaction improves compression, and the gain is quantifiable). Providing the model with harness components such as tools, rulebased environments, scientific templates, verifier feedback, and retrievers, and allowing the system to interact with these environment resources, can improve the system’s compression ability—fewer residual bits are needed to reconstruct the target; this improvement not only exists but can be quantitatively analyzed via the average bits saved. Jointly argued by A reversed text, B chess, C/C′ protein, and D retrieval. • Claim 2 (observation granularity affects compression). The tightness of the observation standard changes the set of acceptable reconstructions, hence the system’s compression ability, so the evaluation standard must be reported together with compression ability. Argued by the semantic-observer ladder experiment in the E story setting. 7
Table 1: Claims, experiments, and component values. Claim
1 interaction improves compression, quantifiably
Exp.
Setup / change
A reversed text
condition Codelength change / trend
Component value
App.
A0 encode reversed 2.877 → 0.742 bits/byte string directly → A1 shared reverse transform
2.135 bits/byte
A.1
B chess
B0 plain SAN text → 9.828 → 6.545 bits/move B1 legal-move environment
3.283 bits/move
A.2
C protein
C0 plain ESM2 → C2 200.65 → 116.80 bits/seq calibrated template
83.85 bits/seq
A.3
375.41 bits/seq
A.3
relevant 18.29; distractor 2.95
A.4
codelength rises monotonically as observer tightens
A.5
— see §5.3 —
A.5
C′ protein (func- C′ 0 no-feedback sam- 402.99 → 27.58 bits/seq tional eq.) pling → C′ 1 verifierfeedback repair D (RAG)
retrieval D0 retrieval failure 24.46 → 6.17 bits/answer → D1 relevant docs
2 observation E story (semantic granularity ladder) affects compression
observer tight- see Fig. 4 ened weak→strong; E1/E2 replay the same candidate set
3 compression E story (budget summary rollout 292.1 → 127.5 bits/story vs. compute sweep) budget T = 1 → 64 trade-off
• Claim 3 (a trade-off between compression and compute). There is a trade-off between a system’s compression ability and the compute invested. Demonstrated by the rollout–codelength Pareto frontier experiment in the E story setting. Table 1 collects this mapping together with each component’s bit value. Naming convention: letters identify experiments (A–E); digits identify conditions within an experiment; in component-ablation experiments, 0 denotes the baseline without the component under test. The full data, models, and protocols of each experiment are in the corresponding appendix subsection; the main text describes only design and argument. Unless otherwise noted, arithmetic-coding codelengths are reported as NLL (differing from the actual codelength by only a constant, Appendix B.1); the component value in each comparison follows the definition in Section 3.4, i.e. the average codelength reduction before and after adding the component. Lower codelength is always better.
5.1
Claim 1 (main claim): harness interaction improves compression, and the gain is quantifiable
We argue Claim 1 with four controlled comparisons: A and B are minimal mechanism demonstrations, while C and D use real data to analyze the scientific-template and retrieval components, further showing that this codelength reduction stays quantifiable even when the success rate has almost no resolution (C) or when retrieval relevance varies continuously (D). Full experimental designs are in Appendices A.1–A.4. A reversed text (deterministic tool). The target distribution is the first 1 MiB of natural text from enwik8, processed by a deterministic line-wise reversal R, requiring exact byte recovery, with the model SmolLM2-360M. The baseline A0 arithmetic-codes the reversed string directly, 8
(a) Reverse text
(b) Chess moves
(c) Protein sequence
2.88
direct LM
0.74
+ reverse tool
6.55
+ legal env 2.27 saved 2.14 b/B 0.5
1.0
143.8
+ fixed prior
best classical
0.0
200.6
pure ESM 9.83
direct SAN
1.5
2.0
2.5
3.0
116.8
+ calibrated prior saved 3.28 b/move
3.5
0
2
4
6
bits / byte
8
10
saved 83.8 b/seq
12
0
50
bits / move
(d) RAG answer 24.46
2820
33% (3.28 b/move)
446
exact NIL
42% (83.8 b/seq)
Protein 7.34
0
5
10
369
event graph
6.17
gold docs
gold saved 18.3 b 15
20
25
125
summary
30
bits / answer agentic / best component
250
74% (2.14 b/B)
Reverse
Chess
mixed
200
(f) Component value summary
gzip
21.52
distractor
150
bits / sequence
(e) Story semantic
no docs
100
10
summary saved 320.1 b
2
10
3
bits / story (log) agentic alternative
model-only / no-context baseline
RAG
75% (18.3 b/ans)
Story
72% (320.1 b/story) 0
20
40
60
80
relative codelength reduction (%) classical / distractor
Figure 2: Bit value of agentic components across the five experiments (A–E). The first five panels show the absolute codelength before and after adding the component; the last panel summarizes the relative reduction. averaging 2.877 bits/byte. A1 lets the encoder and decoder share R: the encoder first uses R to restore the reversed string to canonical text u, then arithmetic-codes it. The result: A1’s codelength drops to 0.742 bits/byte, far below A0 and even below a general-purpose compressor such as gzip; the bit value of the reverse tool is 2.877−0.742 = 2.135 bits/byte—the deterministic tool reduced the system’s residual codelength. This is the simplest demonstration of Claim 1. B chess (rule-based environment). The data are 100 games, 6,005 half-moves in total, deterministically sampled from the Lichess 2013-01 shard, with moves in standard algebraic notation (SAN). The baseline B0 treats a whole game as ordinary text and arithmetic-codes it token-by-token, averaging 9.828 bits/move. B1 introduces a rule-based environment: at each position it calls python-chess to enumerate the legal-move set Lt , renormalizes the model probability over Lt only to Q(a) = PM (a)/PM (Lt ), and takes the move’s codelength as − log2 Q. The legal-move environment lowers the codelength to 6.545 bits/move, a bit value of 3.283 bits/move. C protein (scientific template). This experiment implements the protein task as a controlled masked conditional reconstruction agent, measuring how much a homologous template lowers the uncertainty of unobserved residues. On 100 real protein sequences (50 each from PF00069, the protein kinase domain, and PF00096, the C2H2 zinc finger), the ESM2 masked language model, and leave-one-out template retrieval (full setup in Appendix A.3), the three systems share the same target sequence, the same visible context, the same mask positions, and the same model, differing only in the conditional distribution Qi used at masked positions, so the codelength difference can be attributed to the homologous-template component itself. We add the “homologous template” component along a three-rung ladder, and the codelength shortens at each rung: • C0 (plain ESM2, no template). Masked positions are encoded directly with ESM2’s distribution pESM conditioned on the visible residues, averaging 200.65 bits/seq. 9
Table 2: Shared-context codelength in functionally equivalent protein generation. System C′ 0 MODEL_ONLY C′ 1 AGENTIC
Success rate
Fallback rate
Mean conditional codelength
68.0% 98.0%
32.0% 2.0%
402.99 27.58
• C1 (fixed homologous template). The system ranks candidate templates from the leave-one-out reference set by visible-site identity, visible 3-mer Jaccard, and a length penalty, locally aligns the best template to the masked target sequence, and forms a perposition residue prior pprior at masked positions. The coding distribution is (1 − α) pESM + α pprior , but the template reliability is fixed and α is capped at 0.50. The codelength drops to 143.83 bits/seq. • C2 (calibrated homologous template). The system still uses the same template retrieval and alignment process, but α is no longer fixed; instead it estimates templatematch reliability using visible residues only, and selects the mixing strength on a small subset of visible validation sites; masked positions are used only at final scoring. This rule can be recomputed by the decoding end from the shared visible context, so no extra transmission of template reliability is needed, and the cap on α is relaxed to 0.95. The codelength further drops to 116.80 bits/seq. Hence the total bit value of the calibrated homologous-template tool is 200.65 − 116.80 = 83.85 bits/seq, of which “upgrading from fixed to calibrated” (C1→C2) alone contributes 27.03 bits/seq—showing that a component’s reliability calibration can itself be quantified in bits. Over 100 sequences, C2 beats C0 with 71 wins, 24 losses, and 5 ties. C′ protein (functional equivalence and verifier feedback). We further organize a functionalequivalence experiment. The data are still PF00069 and PF00096, 50 each, 100 real sequences in total, with leave-one-out to prevent target leakage. The observer requires candidate length in 80–300 aa, satisfaction of family motif constraints, and that the top family hit of an HMMER scan be the target Pfam family with e < 10−5 and coverage > 0.6. We compare two systems that differ only in the verifier-feedback component: C′ 0 MODEL_ONLY samples templates from the same-family leave-one-out reference and generates candidates at mutation rate 0.30, searching within 32 ranks for the first accepted candidate and sending a seed code, but never reading the reason for failure; C′ 1 AGENTIC uses exactly the same initial proposals and random seeds, but reads the missing-motif information returned by the verifier only when a candidate fails the motif check, and performs at most 2 rounds of motif repair before submitting to the same HMMER observer. This setup confines the gain to verifier feedback + repair, rather than changing the model, data, or sampling budget. The results show that verifier feedback significantly shortens the conditional codelength needed for functionally equivalent recovery. C′ 1 raises the success rate from 68.0% to 98.0% and lowers the mean conditional codelength from 402.99 to 27.58 bits/seq, saving 375.41 bits/seq on average. In per-sample paired comparison, C′ 1 achieves 48 wins, 0 losses, and 52 ties. D retrieval-augmented generation (retriever). The component being measured is the retriever; we implement four agentic systems D0–D3 that differ only in the retrieval component: D0 simulates a retrieval failure (no valid documents), D1 a retriever returning relevant documents, D2 a retriever returning distractor documents, and D3 a realistic scenario—a retriever returning a mix of true and distractor documents. We measure the bits the system needs to compress the answer, i.e. the conditional NLL − log2 P (answer | question, documents). Since
10
Table 3: Answer codelength under different retrieval conditions on HotpotQA. Condition
Context
D0 D1 D2 D3
retrieval failure gold relevant docs distractor docs gold + distractor mix
Mean codelength
Median codelength
Savings vs. D0
24.46 6.17 21.52 7.34
22.79 3.65 19.63 5.60
— 18.29 2.95 17.13
the question, answer, and model are all fixed, the difference in answer codelength across the four conditions reflects how document-return quality affects the system’s compression of the answer. Table 3 gives the average effect, but the per-question reference-document effect better illustrates the quantitative-analysis value of the retrieval component. Figure 3a uses D0 as baseline to compare, per question, the codelength change of the same answer under the irrelevant document block D2 and the relevant document block D1. Irrelevant documents are not simply “useless”: codelength drops on 76/100 questions and rises on 24/100, saving only 2.95 bits on average; the maximum help is about 42.6 bits and the maximum harm about 11.6 bits. This shows that irrelevant passages sometimes provide a similar-topic prior and sometimes push the model toward a wrong answer. By contrast, relevant documents lower the codelength on all 100/100 questions, saving 18.29 bits on average; the mixed retrieval D3 also lowers it on all 100/100 questions, showing that as long as relevant evidence is in the context, the model can usually pick out the useful information from distractor passages.
Retrieval information value: relevant docs shift codelength left 70
white dots = mean
answer codelength (bits)
60 50 40 30 21.5
20 10
6.2
24.5
7.3
0 G1 gold
(a) Per-question reference-document effect on HotpotQA. Irrelevant documents sometimes help and sometimes harm; relevant documents lower the answer codelength on all samples. The labels G0–G3 are internal markers in the experiment source, corresponding to D0–D3 in the text.
G3 mixed
G2 distractor
G0 no docs
(b) Distribution of the information value of retrieval. D1 and D3 shift the whole answercodelength distribution left, while D2 still overlaps heavily with D0. White dots are means.
Figure 3: Retrieval value on HotpotQA, priced in bits. (a) Per-question effect of relevant vs. distractor documents; (b) the resulting answer-codelength distributions. Relevant documents compress the answer codelength to about a quarter (D1, saving 18.29 bits), distractors barely help (D2, only 2.95 bits), and the mix retains most of the gain (D3). Figure 3b shows this is not a few samples dragging down the mean: the whole D1 and D3 11
distributions shift left, while D2 overlaps heavily with D0. Thus retrieval value is bits priced continuously by relevance, not an on/off switch.
5.2
Claim 2: observation granularity affects compression
The looser the observation standard, the more reconstructions are acceptable and the fewer bits the system needs to compress the target; the stricter it is, the more bits are needed. Thus compression ability depends on observation granularity and must be reported together with it—an isolated score cannot say to what degree the reconstruction was achieved. We validate this on the story task. The system uses the seed coding of Section 4: it compresses a story into a short latent z (a summary or event graph) plus the index of a successful seed, and the decoder replays that seed to regenerate the story from z, falling back to exact coding (E0) when no seed within budget yields a semantically equivalent reconstruction. As the observer ladder progressively tightens the judge’s standard (from “characters preserved” to “conflict, events, and ending all correct”), the acceptable set can only shrink, so the codelength should be monotonically nondecreasing. Figure 4 confirms this: both the summary and event-graph arms rise monotonically and approach the exact-coding ceiling, with no violations—turning “observation granularity determines compression ability” from an assertion into a verified prediction. This experiment serves to demonstrate the semantic-observer and budget mechanisms; its conclusions are limited by the TinyStories sample size and the reliability of the LLM judge. Observer monotonicity in semantic story compression (n=64) 450
mean bits / story
400 350 300 250 200 150 100 chars
+conflict
+events
+ending
+verdict
exact
observer strength (weak -> strong) event graph
summary
exact NIL = 445.5 bits
Figure 4: Observer monotonicity. The stronger the observer, the higher the mean codelength rises monotonically, approaching the exact-reconstruction ceiling.
5.3
Claim 3: a trade-off between compression and compute
There is a trade-off between a system’s compression ability and the compute invested: an agentic system exchanges search, sampling, or verification for a shorter description. Figure 5a (schematic) gives the compute–codelength Pareto frontier—increasing the budget usually improves compression (shorter codelength) but with diminishing returns; below the frontier is unreachable, and above it lie suboptimal protocols. E story (budget sweep). Using the same seed-coding system as Section 5.2, we fix the seed budget used for reconstruction and sweep a single variable—the number T of summary rollouts 12
Pareto frontier: compute buys shorter codes Codelength-compute Pareto frontier (TinyStories, n=64)
350 450
exact NIL = 445.5 bits
semantic-path rate 1.0
mean bits / story
codelength
dominated systems 250
shorter code
200
20
21
0.9
300 0.8 250 200
Pareto frontier unreachable under budget
150
350
0.7 codelength
150
22
23
24
25
26
semantic-path rate
400
300
21
20
22
23
24
25
26
0.6
summary rollout budget T (log scale)
compute budget
(a) Schematic: a larger budget buys a shorter code, (b) Measured frontier on TinyStories. The larger but with diminishing returns; below the frontier is the rollout budget, the lower the codelength; the unreachable, above it lie suboptimal protocols. semantic-path rate saturates around T = 8.
Figure 5: Compute–codelength Pareto frontier: (a) schematic and (b) measured on TinyStories. Table 4: Summary rollout budget and codelength on TinyStories (system E1). T
1
2
4
6
8
16
32
64 E0 (NIL exact)
Bits/story 292.1 238.9 202.9 185.4 175.3 154.1 137.8 127.5 Semantic-path rate 64.1% 84.4% 95.3% 98.4% 100% 100% 100% 100%
gzip
445.5 2820.2 — —
the encoder may search, i.e. how many candidate latents the encoder tries before taking the one that “produces an accepted reconstruction with the shortest codelength itself.” At each T we measure the codelength and the semantic-path rate (the fraction of instances that succeed via the semantic-compression path, i.e. the summary path, without falling back to E0). Table 4 shows that codelength decreases monotonically as T grows, but increasing the budget from T = 8 to T = 64 (8×) only compresses the codelength from 175.3 to 127.5, with clear diminishing returns; the path rate saturates at 100% around T ≈ 8, after which continued search mainly finds shorter latents rather than raising the acceptance rate. This curve shows that a single static capability number cannot describe how capability varies with budget. This experiment shows that a system’s compression ability is not a single static number but a function curve of compute (Figure 5b). Compared with a one-shot success rate, the codelength–compute curve simultaneously exposes the trade-offs among compression ability, cost, and engineering budget.
6
Discussion
6.1
Marginal bit value vs. traditional ablation and success rate
We measure a component’s value by “the improvement in system compression after providing the component”—i.e. the average codelength reduction. This differs fundamentally from the traditional practice of “ablating a component and observing the change in model success rate,” and is more informative for three reasons. • It remains cheap to measure when the success rate is extremely low or too coarse. Through teacher-forcing-like coding, we can read out component value even in tasks where direct sampling almost never succeeds. Protein masked reconstruction is a clear example: estimating the success rate by sampling would require an enormous number of samples, whereas a single forward pass of arithmetic coding reads out the homologoustemplate value of 83.85 bits/seq. Conversely, in functionally equivalent protein generation
13
the success rate is already measurable, but it only tells us 68% → 98%; the rank codelength under shared context further shows that verifier-feedback repair removes 375.41 bits/seq on average and localizes it to the motif-level constraint search cost. • It can distinguish regions that all look like zero from a success-rate viewpoint. From a success-rate viewpoint, 2−10 and 2−100 are both essentially zero. From a codelength viewpoint, moving from the latter to the former gains 90 bits of information. A component that raises the success probability from 2−100 to 2−10 looks useless on a success-rate plot but is extremely valuable in bits. • It provides a conditional, public accounting unit. Under the same task, the same protocol, the same unit, and a fixed order of component additions, bit values can be summed to track the marginal contribution of different components to the total codelength reduction; for cross-task or cross-protocol comparisons, one must additionally report the distribution, observation standard, budget, and unit.
6.2
The relativity of compression: intelligence cannot be discussed in isolation
Any compression result is relative to a distribution, observation granularity, model, environment interface, and compute constraint. This relativity is a feature, not a nuisance, because deployed intelligence is always exercised under these conditions. Agentic codelength measures residual information: if the model, verifier, retriever, or environment already provides structure, then the per-instance message can be very short. This does not mean the object itself carries little information; it means that, relative to a fixed decoding protocol, the object is easy. In this sense, an agentic workflow is not merely an implementation detail but a change of description language: it moves information from the per-instance message into the public protocol and the decoding-side system. Section 3.4 defines this residual codelength within a fixed protocol and defines component value via the average codelength difference before and after adding the component.
6.3
Limitations
Protocol limitation. Seed coding applies only to deterministic or replayable environments: the encoder and decoder must be able to reproduce the same random trajectory, tool returns, and environment state. Engineering an encoding for non-replayable external services is out of scope; but this does not affect the paper’s theoretical analysis framework, because, without loss of generality, we can in principle abstract the randomness of any environment and uncontrollable external inputs as a pseudorandom sequence pre-generated from a sufficiently long global seed. This idealized replay assumption lets the paper’s analysis framework apply, without modification, to systems in non-replayable environments. Experimental limitation. The five sets of experiments cover several component types typical of real agentic systems and demonstrate the ability of codelength to analyze component value, observation granularity, and the budget trade-off; but the experiments are small in scale and mainly serve to verify the paper’s claims and provide exploratory evidence. These results show that the framework can analyze the mechanisms of real systems and offer methodological inspiration for analyzing larger-scale agentic systems; but this paper has not yet conducted a full, large-scale end-to-end system experiment, and the relevant numbers should not be directly extrapolated to general conclusions for deployed systems.
14
6.4
Agentic pseudo-entropy
The preceding text mainly discusses the average codelength under a fixed protocol; but if our concern is not some already-realized system, but rather “given a model, environment, and resource constraints, how much can any designable agentic program at best compress the distribution,” then we must generalize the measure from a single protocol to a class of constrained systems. Fixing the task distribution D, the model M , and the set of environment interfaces E, and allowing only the program P to vary, we obtain a class A of constrained agentic systems satisfying constraint C. On top of the codelength in Section 3.4, taking the infimum over the system class and the expectation over the distribution, we can define the agentic pseudo-entropy A,C Hagentic (D) = inf E(c,x)∼D LC A (x | c). A∈A
This definition follows the idea of Yao-type pseudo-entropy (Barak et al., 2003; Yao, 1982): complexity is not the absolute Shannon entropy of the object distribution, but incompressibility relative to a class of constrained systems. Its main significance is to give a system-relative data complexity: as seen by the constrained system class induced by a fixed model, environment interface, and resource constraints, how much true complexity of the distribution D remains that cannot be absorbed by any program, tool, retrieval, search, or verifier. In other words, agentic pseudo-entropy asks not “how much information” the data themselves carry, but how hard the data still are to compress within the capability boundary of this class of agentic systems. From a system perspective, the same quantity also characterizes the optimal achievable compression ability of the system class on the distribution D given the model, environment interface, and resource constraints—i.e. the theoretical upper bound on learning or exploiting the structure of the distribution. If the agentic pseudo-entropy of some distribution remains high, it means that under these fixed resources the distribution is indeed hard for this system class; if it is low, much of the distribution’s structure can already be exploited by the existing model, environment interface, and admissible programs. The constraint C here must include limits such as program length and compute, e.g. program length, number of model calls, number of tool calls, or call cost (an engineerable agentic system naturally satisfies these constraints). These constraints are constitutive: without limiting program length, the system could write the complex structure that should be borne by the model directly into the program, even explicitly unrolling the model’s internal computation, making the definition degenerate. Without limiting compute, some tasks could shift description length into unbounded search; as Appendix B.2 shows, in certain public-specification tasks the decoder can find any qualifying artifact by infinite enumeration, making the per-instance codelength degenerate. This paper has not yet fully explored the definition of agentic pseudo-entropy itself or the details of these constraint settings; we present it here only as a heuristic concept, to suggest that data complexity relative to a concrete model/system can be discussed from the perspective of a constrained system class.
7
Conclusion
We introduced a compression-based method for analyzing system capability at the level of agentic systems. The key step is to fix the task distribution, observer, interface, and budget, and then ask: how many residual bits must each instance still supply for reconstruction. This makes tools, environment, retrieval, verifiers, and the search budget part of the system being analyzed, rather than external implementation details. The viewpoint becomes operational through arithmetic coding, seed coding in deterministic or replayable environments, and fallback. Each component is measured by the residual bits it removes—its average codelength reduction (values in Table 1). The results show that treating 15
an agentic system as a shared decoder can explain and quantify part of where system capability comes from. This is not the only definition of intelligence, but a complementary viewpoint for component analysis, observer analysis, and budget analysis; it suggests which shared structures may reduce the residual description length, while the concrete engineering significance still needs to be assessed relative to a specific system.
Acknowledgments This work was supported by the National Natural Science Foundation of China (Grant No. 625B1012).
References Boaz Barak, Ronen Shaltiel, and Avi Wigderson. Computational analogues of entropy. In RANDOM-APPROX, volume 2764 of LNCS, pages 200–215. Springer, 2003. doi: 10.1007/ 978-3-540-45198-3_18. Andrew Barron, Jorma Rissanen, and Bin Yu. The minimum description length principle in coding and modeling. IEEE Transactions on Information Theory, 44(6):2743–2760, 1998. doi: 10.1109/18.720554. Yochai Blau and Tomer Michaeli. The perception–distortion tradeoff. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 6228–6237, 2018. doi: 10.1109/ CVPR.2018.00652. Karlheinz Brandenburg. Mp3 and aac explained. In AES 17th International Conference: HighQuality Audio Coding, 1999. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, 2 edition, 2006. doi: 10.1002/047174882X. Grégoire Delétang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christopher Mattern, Jordi Grau-Moya, Wenliang Kevin Li, Matthew Aitchison, Laurent Orseau, Marcus Hutter, and Joel Veness. Language modeling is compression. In International Conference on Learning Representations (ICLR), 2024. arXiv:2309.10668. Peter D. Grünwald. The Minimum Description Length Principle. MIT Press, 2007. doi: 10. 7551/mitpress/4643.001.0001. Hermes Agent. Hermes agent: An open-source autonomous agent runtime. Nous Research, 2026. https://hermes-agent.org/. Chun-Yuan Hsiao, Chi-Jen Lu, and Leonid Reyzin. Conditional computational entropy, or toward separating pseudoentropy from compressibility. In Advances in Cryptology – EUROCRYPT, volume 4515 of LNCS, pages 169–186. Springer, 2007. doi: 10.1007/ 978-3-540-72540-4_10. Yuzhen Huang, Jinghan Zhang, Zifei Shan, and Junxian He. Compression represents intelligence linearly. In Conference on Language Modeling (COLM), 2024. arXiv:2404.09937. H. V. Jagadish, J. Madar, and Raymond T. Ng. Semantic compression and pattern extraction with fascicles. In International Conference on Very Large Data Bases (VLDB), pages 186–198, 1999.
16
Huiqiang Jiang, Qianhui Wu, Chin-Yew Lin, Yuqing Yang, and Lili Qiu. Llmlingua: Compressing prompts for accelerated inference of large language models. In Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 13358–13376, 2023. doi: 10.18653/v1/2023.emnlp-main.825. arXiv:2310.05736. Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmented generation for knowledge-intensive nlp tasks. In Advances in Neural Information Processing Systems (NeurIPS), 2020. arXiv:2005.11401. Percy Liang, Rishi Bommasani, Tony Lee, et al. Holistic evaluation of language models (helm). 2022. arXiv:2211.09110. OpenAI and R. Lopopolo. Harness engineering: Leveraging codex in an agent-first world. OpenAI engineering blog, 2026. https://openai.com/index/harness-engineering/. OpenClaw. Openclaw: An open-source agent harness. openclaw, 2026.
https://github.com/openclaw/
Jorma Rissanen. Modeling by shortest data description. Automatica, 14(5):465–471, 1978. doi: 10.1016/0005-1098(78)90005-5. Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. In Advances in Neural Information Processing Systems (NeurIPS), 2023. arXiv:2302.04761. Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2023. arXiv:2303.11366. Aarohi Srivastava et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models (big-bench). 2022. arXiv:2206.04615. Ilya Sutskever. An observation on generalization, 2023. Talk at the Simons Institute, Large Language Models and Transformers workshop, 14 Aug 2023. Gregory K. Wallace. The jpeg still picture compression standard. Communications of the ACM, 34(4):30–44, 1991. doi: 10.1145/103085.103089. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain-of-thought reasoning in language models. In International Conference on Learning Representations (ICLR), 2023. arXiv:2203.11171. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems (NeurIPS), 2022. arXiv:2201.11903. Ian H. Witten, Radford M. Neal, and John G. Cleary. Arithmetic coding for data compression. Communications of the ACM, 30(6):520–540, 1987. doi: 10.1145/214762.214771. John Yang, Carlos E. Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofir Press. Swe-agent: Agent–computer interfaces enable automated software engineering. In Advances in Neural Information Processing Systems (NeurIPS), 2024. arXiv:2405.15793. 17
Andrew C. Yao. Theory and application of trapdoor functions. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), pages 80–91. IEEE, 1982. doi: 10.1109/SFCS.1982.95. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Advances in Neural Information Processing Systems (NeurIPS), 2023a. arXiv:2305.10601. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023b. arXiv:2210.03629.
A
Experimental Implementation Details
Below we describe the full design of the five experiments mentioned in Section 5.
A.1
Reversed text (Section 5.1)
Data, model, and sampling scale. The target distribution is the first 1 MiB (1,048,576 bytes) of natural text from enwik8 (the English Wikipedia dump), with a deterministic linewise character reversal R applied: characters within a line are reversed as a whole while line terminators are preserved (e.g. "Hello World\n" 7→ "dlroW olleH\n"). R is an involution (applying it twice restores the original). The model is the SmolLM2-360M base version. The observation family O requires exact byte equality (lossless recovery). This task is a single-sample whole-segment encoding, with no sampling and no fallback. Agentic system construction. The only “tool” the system has is the deterministic reversal operator R, shared by the encoder and decoder. A0 does not use it and encodes the reversed string directly; A1 uses it, hardwiring the per-instance information “this text is reversed” into the shared transform so it need not be carried in the bitstream. Codelength protocol. The two systems share the same model and (in A1) the reverse tool, differing only in where the information is placed. A0 (no tool, encode reversed string directly). Encoder: arithmetic-code the reversed target string x directly. Decoder: arithmetic-decode to obtain x. Stored code: just one arithmetic code of x; no tool, no seed, no fallback. A1 (reverse tool). Encoder: first use the shared tool to compute the canonical text u = R(x), then arithmetic-code u, LA1 (x) = LLM (u) + O(1) LA0 (x). Decoder: first arithmetic-decode u, then apply the same shared tool to output x = R(u)—the reversal step is performed by the decoder and so does not occupy the bitstream. Stored code: just one arithmetic code of u; the reversal rule R and the model weights are shared fixed components and are not stored.
A.2
Chess (Section 5.1)
Data, model, and sampling scale. The target distribution is the January 2013 shard of the Lichess standard game database, deterministically sampled with a fixed seed and keeping only games whose half-move count lies in [20, 120], giving 100 games and 6,005 half-moves in total. Moves are in standard algebraic notation (SAN). The model is SmolLM2-360M-Instruct. The observation family O requires exact trajectory agreement. Agentic system construction. The system’s tool is a legal-move environment (python-chess): at any position it enumerates the full set Lt of legal SAN moves. B0 does not use this tool; B1 uses it at each step to renormalize the model distribution over the legal set, recovering the probability mass that would otherwise leak to illegal moves. The rule engine and the initial board are equally visible to both ends, and the environment calls are shared computation. 18
Codelength protocol. B0 (no tool, encode the whole game directly). Encoder: concatenate the whole game’s SAN into a space-separated text string and arithmetic-code it token-by-token. Decoder: arithmeticdecode the whole SAN text stream token-by-token. Stored code: one arithmetic code of the whole SAN string; no environment call, no fallback. B1 (legal-move environment). Encoder: at each position t, call the environment to get the legal set Lt , score each candidate move’s continuation sa , renormalize over the legal set by logsum-exp, and take the observed move a⋆ ’s codelength as logsumexpa (sa ) − sa⋆ = − log2 Q(a⋆ | ht , Lt ), where Q(a | ht , Lt ) = PM (a | ht )/PM (Lt | ht ) (since Lt is a legal subset, PM (Lt | ht ) ≤ 1, so each step’s codelength does not increase relative to the bare model, i.e. ∆legal ≥ 0). Decoder: replay the whole game step-by-step; at position t, use the same history ht to call the same engine for the same Lt , recompute the same renormalized distribution Q, arithmetic-decode the step’s move from the bitstream, and advance to ht+1 . Stored code: one step-by-step arithmetic bitstream, which is read step-by-step against the legal sets replayed by the decoder to restore the whole trajectory; the rule engine, notation, and weights are shared fixed components and are not stored.
A.3
Protein (Section 5.1, masked ESM)
Data, model, and sampling scale. The target distribution is UniProt sequences with Pfam annotations and length 80−300 aa; the core experiment takes 50 each from PF00069 (protein kinase domain) and PF00096 (C2H2 zinc finger), 100 in total. The model is the masked language model ESM2 (esm2_t33_650M_UR50D). To eliminate leakage, we use leave-one-out: when processing target sequence x, the reference set used for the template library, motif extraction, and verifier checks is always “same-family sequences minus x itself.” The observation family O is functional equivalence: a fixed lightweight verifier accepts only when all three hold—length in [80, 300], the candidate contains the top-3 3-mer motifs counted from the reference set, and a 3-mer Jaccard similarity above 0.2 with some reference—rather than requiring residue-byresidue identity. The actual codelength experiment uses a masked conditional reconstruction proxy, billing only the masked residues. Agentic system construction. Beyond ESM, we add a homologous-template tool: it retrieves and locally aligns a homologous template from the leave-one-out reference set, obtaining a per-position template prior pprior , and at each masked position linearly mixes it with ESM’s own distribution as (1 − α) pESM + α pprior . C0 does not use this tool; the tool has two versions: C1 fixed assumes all templates are equally reliable (constant match probability, α capped at 0.50); C2 calibrated estimates each template’s per-position match reliability from visible (unmasked) sites only, and accordingly relaxes the mixing cap to α ≤ 0.95—the more reliable the template, the more it is mixed in. The mixing coefficient α is selected on held-out visible residues. Codelength protocol. The three systems share the same set of mask positions (selected at a fixed 30% ratio, protecting motif sites), and the codelength is the masked pseudo-NLL on masked positions (mask each position and sum the − log2 P of the corresponding distribution); visible sites are always conditions and not billed, so the difference between systems is a clean causal comparison. The three differ only in the distribution Q used at masked positions. The exact length |x| log2 20 serves only as the denominator of the compression rate and does not enter the component value. This protocol estimates the template’s reduction of conditional residue uncertainty; it is not a full de novo protein generation protocol. C0 (plain ESM, no-tool baseline). Encoder: arithmetic-code masked positions with ESM’s own distribution pESM . Decoder: run the same ESM forward pass conditioned on the same visible sites and mask set, reproduce pESM , and arithmetic-decode position by position. Stored code: the arithmetic code of the masked residues under pESM . C1 (fixed homologous-template tool). Encoder: arithmetic-code each masked position with 19
the mixture (1 − α) pESM + α pprior , with fixed template reliability and α ≤ 0.50. Decoder: re-run the homologous-template tool on the same leave-one-out reference set, reproduce the same mixture, and decode position by position. Stored code: the arithmetic code of the masked residues under this mixture; the reference set and α are shared conditions and not stored. C2 (calibrated homologous-template tool). Same encode/decode skeleton as the fixed version, except the per-position α of the mixture is determined by the template reliability estimated from visible sites, with the cap relaxed to 0.95 (the more reliable the template, the more it is mixed in). Crucially, both ends recompute α from visible sites with the same rule, so no transmission is needed. Stored code: the arithmetic code of the masked residues under the calibrated mixture.
A.4
Retrieval augmentation (Section 5.1, HotpotQA)
Data, model, and sampling scale. Samples are taken from HotpotQA’s distractor configuration, validation split, removing yes/no answers and requiring both gold (supporting) and distractor passages, taking the first 100 (bridge 91, comparison 9); each item has 2 gold and 8 distractor passages. The model is Qwen3.5-0.8B. The observation family O is the exact answer text, held consistent across the four conditions of the same sample. Here the public condition c is the question itself (the problem statement), and the answer is conditionally compressed given the question; the reference documents are not c but the output of the retrieval component being measured—a decoding resource determined by the question and shared by both ends (in the same class as the model weights and the rule engine). The four conditions D0–D3 are controlled oracle document-return conditions and thus constitute four agentic systems differing only in the retrieval component’s returned content, isomorphic to A0/A1 and B0/B1. Agentic system construction. The system has a controlled retriever whose output (reference documents) is injected into the model context to provide information. The four conditions differ only in the relevance of the documents the retriever returns: D0 a retrieval-failure placeholder (no valid documents); D1 only the 2 gold (supporting) passages; D2 2 distractor passages equal in number to gold; D3 all 10 passages in original order. This setup measures how document-return quality affects answer codelength. Codelength protocol. D0–D3 are four instances of the same class of retrieval-augmented system, differing only in the retrieval component; the encoder, decoder, and stored-code skeleton are identical, so the protocol is described once. • Encoder design. The retriever’s output reference documents are placed in the prefix, and the conditional NLL − log2 P (answer | question, documents) is accumulated and arithmeticcoded over the answer tokens only; the prompt (including the question and reference passages) is a shared prefix and is not billed at all, forming a clean causal comparison across conditions. • Decoder design. The decoder obtains the same documents through the same retriever (the same question), constructs the same prefix, runs the same forward pass, and arithmeticdecodes the answer token-by-token—just as the chess decoder in A.2 recomputes the legal set itself. • Stored code. Just one arithmetic code of the answer; the reference documents, like the model weights, are shared components and not transmitted per instance, hence not stored— the retrieval component’s value is precisely how many bits it shortens this answer code by. • Per-question reference-document effect analysis. analyze_per_question.py reads each question’s four-condition answer codelengths from per_sample_metrics.csv and computes ∆irrel = LD2 − LD0 and ∆rel = LD1 − LD0 ; a negative value means the document 20
block lowers the codelength, a positive value means it harms compression. Figure 3a in the main text is plotted sorted by ∆irrel , showing the relevant-document effect under the same question order.
A.5
Story (Sections 5.2 and 5.3, TinyStories)
Data, model, and sampling scale. The target distribution is TinyStories, first filtered to short pieces of 55−160 words, shuffled with a fixed seed, and taking 64 pieces. The generator is Qwen3.5-0.8B. The observation family O is semantic plot equivalence (whether the main characters, main events, conflict, and ending are all preserved), judged via API by a DeepSeek judge (deepseek-v4-flash). The judge returns structured flags characters_preserved, conflict_preserved, main_events_preserved, ending_preserved, and an overall verdict; verdict equal to correct is judged as the strongest semantic acceptance. Observer ladder. To test observation-granularity monotonicity, we construct a weak-tostrong cumulative-AND chain from the judge’s flags: characters preserved; characters + conflict preserved; characters + conflict + main events preserved; characters + conflict + main events + ending preserved; plus the overall verdict=correct. Each rung only adds constraints, so a stronger observer’s acceptable set is contained in that of a weaker observer. This ladder is recomputed offline entirely from the saved per-seed judge results; the DeepSeek judge compares the original story with the candidate reconstruction each time (we acknowledge that the noise of this judge model may have an effect, which is one limitation of our experiments). Agentic system construction. The encoder compresses a whole story into a short latent descriptor, and the decoder regenerates the story from it; seed coding lets the intermediate reconstruction avoid token-by-token coding, and the NIL fallback (baseline E0) guarantees the worst case is no worse than bare coding. Two billed latents: E1 is a free-form summary, and E2 is a structured event graph (flat JSON, incorporated into the decoding protocol via a fixed parser/normalizer). Both latents are billed by arithmetic coding with the empty context (NIL), i.e. − log2 P (latent | NIL prompt). Codelength protocol (seed coding + fallback). E1 and E2 share the same seed-coding + fallback skeleton, differing only in latent type (E1 free-form summary; E2 structured eventgraph JSON, with one extra fixed parse/normalize step on the decoding end), so the skeleton is described once with the two differences noted. • Encoder design. First arithmetic-code the latent z by empty-context NLL (E1’s z is the summary, E2’s z is the event-graph JSON). Then enumerate 8 public seeds (ranks 0−7): each seed deterministically regenerates a candidate story, which is verified by the judge as o(x̂) = o(x), and take the rank of the first accepted seed; for E1, additionally select, among multiple accepted summary candidates, the one with the shortest empty-context NLL. If none of the 8 seeds is accepted → fall back to NIL (E0): bill by the empty-context arithmetic code of the whole story. • Decoder design. First read the 1-bit method selector. Semantic path: arithmetic-decode the latent z (E2 normalized to a canonical latent by the fixed parser), read the 3-bit seed rank, and deterministically regenerate the story with that seed (acceptance was verified at encoding time, and the decoding end reproduces the same reconstruction position-byposition). NIL path: directly arithmetic-decode the whole story. • Stored code. A 1-bit method selector, plus one of: the semantic path stores [latent emptycontext code + seed rank code]; the fallback path stores [whole-story NIL code]. Under the budget-sweep convention of Section 5.3, the reconstruction seed budget is 8 (ranks 0−7), and the rank uses a fixed 3-bit code; if the selector is counted on both paths, the combined code exceeds E0 (NIL) by at most 1 bit, and is below E0 when the semantic path succeeds and is shorter. The seed set, generator weights, and (E2’s) parser are shared fixed 21
components and not stored. The compute–codelength Pareto frontier is obtained under this protocol by sweeping the summary rollout budget T = 1 . . . 64 (replaying only the first T rollouts) (values in Section 5.3).
B
Technical Notes and Proof Sketches
This appendix collects the short technical facts used in the main text. Throughout, L denotes the operational codelength under a fixed protocol.
B.1
Arithmetic coding and the NLL proxy differ by a per-instance constant
Under context c (and side information z), the model induces conditional distributions PM (· | x<t , c) in token order. Arithmetic coding maps the reference x = x1:n to a nested subinterval of the unit interval: starting from [0, 1), after reading xt it subdivides the current interval proportionally according to the current token distribution and takes the segment corresponding to xt ; after n steps it obtains ∏ [ ) Ix = F (x), F (x) + PA (x | c, z) , |Ix | = PA (x | c, z) = PM (xt | x<t , c), t
where F is the cumulative distribution in token order. Write NLL(x) = − log2 PA (x | c, z). To obtain a prefix-unambiguous finite binary codeword, take the interval midpoint mx = F (x) + 21 PA (x | c, z), and send the first
⌈
⌉ 1 ℓ(x) = log2 + 1 = dNLL(x)e + 1 PA (x | c, z)
binary digits of mx . This is exactly the standard length choice in Shannon–Fano–Elias codes and in the termination analysis of arithmetic coding: rounding up ensures the binary codeword is fine enough, and the extra +1 makes the small binary interval determined by this prefix lie entirely within Ix , preserving prefix-unambiguity; Delétang et al. (2024) use the same convention when compressing sequences with a predictive distribution ρ, writing the codelength as d− log2 ρ(x1:n )e + 1. The decoder shares c, z and the same model, recomputes the same nested subdivision for the known length n, and can thus uniquely locate Ix from this prefix and recover x. Hence 1 ≤ ℓ(x) − NLL(x) < 2, where the left end is attained when NLL(x) is an integer; if only an upper bound is of interest, then ℓ(x) ≤ NLL(x) + 2. Therefore, when we use NLL as a codelength proxy, we ignore the prefix-termination constant of fewer than 2 bits per message; all reported component values and average codelength differences are far larger than this per-instance constant, and the conclusions are unaffected (Cover and Thomas, 2006; Delétang et al., 2024; Witten et al., 1987). □
B.2
Resource constraints are a constitutive part of the definition
Agentic codelength measures how many extra bits the encoder must still send for this instance after the public condition c, the shared system components, and the observation standard have all been fixed. This definition is meaningful only when compute is also limited; otherwise, the decoder could offload “finding a qualifying artifact among many candidates” to unbounded enumeration, rather than having the encoder point to that artifact with bits. 22
This is especially crucial in public-specification tasks. Many agentic tasks do not require recovering a unique target x, but rather, given a problem, tests, rules, or specification c, output any y satisfying the specification. For example, a QA task needs only a correct answer, a coding task needs only to pass the tests, and a math problem needs only a correct solution. Here the success judgment is not “restore the properties of this specific x” but an absolute judgment depending only on the public specification c, Vc (y) = 1, where the original target x is merely one example satisfying the specification, not an object that must be matched item-by-item. Thus, for the decoder, the task is not “recover x” but “output any y satisfying Vc .” Suppose the decoder, generator, verifier, and seed-enumeration order are all shared fixed resources. If there exists a seed r such that A(c, r) passes verification, i.e. Vc (A(c, r)) = 1, then under unbounded compute the decoder need not receive any per-instance message; it only enumerates public seeds r = 1, 2, . . . and stops at the first output satisfying Vc (A(c, r)) = 1. Since the acceptance criterion only requires a “qualifying artifact” and not a match to a specific target x, the first qualifying artifact the decoder outputs is already an acceptable reconstruction. Therefore such tasks can exhibit zero-bit reconstruction under unbounded search.
23