CS Paper Radar

When Does Less Information Pay? An Exact Finite Atlas of Representation, Payoff, and Cost

Aleksandr M. Shtraukh-Adamsky, Vladimir M. Adamsky, Irina G. Voloshina, Artemiy D. Spitsyn

cs.AI ·submitted 2026-11-12 23:07 UTC · v1

Abstract

A representation that retains one bit about a four-state world can solve a task perfectly, while another that retains 1.5 bits on average reaches only 75% accuracy. The difference lies in which distinctions each representation preserves. We examine this relationship in a uniform four-state world by enumerating all admissible representations and binary action rules. Constructions are compared both by replacing one component while holding the others fixed and by choosing the best action rule separately for each module. We consider three tasks, their mixtures, and four separate hypothetical cost tariffs. In some comparisons, the representation retaining less world information has the higher payoff; in others, the more informative representation does. There are also pairs with different information amounts but equal payoff--that is, equal task accuracy. If a representation preserves all existing distinctions and adds new ones, its best zero-cost payoff cannot decrease. Lower-information advantages therefore depend on which distinctions are retained. Equal counts of opposing advantages under representation replacement follow from coding symmetry. In broader comparisons, the shares depend on how repeated realizations are counted. A different task set or resource price can change which member of a fixed pair performs better. These results are exact, complete censuses of the specified finite sets of constructions and comparisons. The atlas provides a reproducible worked model for examining how action constraints, counting rules, and cost assumptions affect comparisons. It illustrates established distinctions between information quantity and decision value rather than proposing a new general law of their relation. $I(W;R)$ measures retained world information, and payoff measures task accuracy.

Comment
40 pages, 5 figures; supplementary material included. Code, data and Russian translation: https://doi.org/10.5281/zenodo.23868864

Closest papers

Nearest neighbours by meaning across the whole index.

Task-Sufficient Contraction: Source Selection for Machine Information Interfaces

cs.IT cs.LG ·2026-10-06 ·Joss Armstrong
similarity 0.63
Abstract · 19 pages, 1 figure, 1 table. An earlier version was first posted on Zenodo in September 2026 (v1: doi:10.5281/zenodo.22834532; all versions:…

A declared task can sometimes certify a reduced source before a downstream encoder, codebook, rate, distortion target, or optimizer is chosen. This paper studies when one such reduction preserves the complete downstream problem family, a property termed Task-Sufficient Contraction. The reduced source is fixed by the task before the later operating point is selected. An exact contraction allows the later problem to be solved on that source with the same result as if the full source had been retained. For a machine with a fixed set of possible actions and a fixed loss, the paper identifies a consumer-specific source by merging states only when every available action has the same regret in both. For finite action sets, replacing the richer source by this reduced source preserves the complete one-step rate-regret curve, even though the reduction is fixed before the distortion target is chosen. A second result gives an exact characterization for quadratic loss on affine feasible-action sets: the canonical reduced source is the projection onto the directions in which feasible actions can differ. Under a fixed energy budget, this becomes centered load, while retaining only the optimal water-filled action is too coarse. Earlier Information Bottleneck, semantic rate-distortion, and goal-oriented quantization results are then used to distinguish exact, architecture-conditioned, approximate, failed, and corrected contractions. The framework suggests a way for heterogeneous machines to exchange what a receiving task needs without first aligning their full internal representations.

0.32

Why Finite Intelligence Works in an Infinite World: A Mathematical Theory

cs.IT cs.LGstat.ML ·2026-11-13 ·Mojtaba Soltanalian
similarity 0.63
Abstract · 56 pages, 5 figures

An information system often has to learn before it knows what it will be asked. A finite representation can succeed without recording an infinite environment in full when those asks share collective structure, rather than demand unrelated facts scattered arbitrarily across it. We formalize this phenomenon through future-task information, the minimum retained information needed to preserve decision value relative to the available evidence. A joint decision-regret state records posterior comparisons among actions for every permitted task. Under compactness assumptions, every retained representation admits a calibrated replacement based on this state, preserving all task regrets without increasing information; the resulting information-regret curve equals an operational coding rate. Two exact boundaries govern finite preservation: weak-star closure for a fixed action count, and the singular mass of the source-evidence law when all finite action menus are admitted. Collective structure determines information requirements beyond individual-question difficulty. Families with identical source laws, pairwise task metrics, and individual-task rates can have different high-resolution exponents. Covariance-identical coordinate and parity families have different exact rate-distortion curves, with optimal parity retention characterized by a sharp Fourier-entropy inequality. For balanced nested task families, refinement sizes and weighted reach determine the rate within an additive constant, attained by prefix coding under explicit decay conditions. Nonlinear learning and computational separations distinguish preservation from efficient discovery and use. The proposed mathematical theory identifies which shared decision requirements allow finite information to remain useful for infinitely many possible purposes.

0.26

Attention Tax, Handoff Tax: A Stylised Model of When Multi-Agent LLM Systems Help

cs.MA cs.AIcs.CLcs.LG ·2026-10-05 ·Akshit Anchan, Nayonika Sen
positioncode/data similarity 0.59
Abstract · 23 pages, 6 figures. Code and data: https://github.com/akshitanchan/attention-handoff-tax

Recent work on multi-agent LLM systems reaches sharply different conclusions: some results show that a single agent with the same information and compute should dominate a delegated system, others that multi-agent gains grow with task depth. We argue that much of the disagreement comes from modelling different bottlenecks, and introduce a stylised reliability model built around two trade-offs. Decomposition reduces the burden of long contexts but incurs a handoff tax when information is compressed or transferred between agents. Redundancy gains from multiple samples, but its benefit depends on how much their failures are shared. With reasoning budget, verification, and task structure added, the model yields two crossover conditions: decomposition becomes preferable once the attention cost avoided by resetting context exceeds the handoff cost, and parallel sampling at equal budget is eventually preferable when its shared-failure floor lies below the error floor of one agent thinking longer. We connect these regimes to recent theoretical and empirical results. On a ledger-reconciliation task we measure the context-degradation curve and the handoff tax from single-agent and handoff runs alone. From these the model places the crossover at depth 10 and predicts decomposition to win at depths 20, 50, and 100. It does, on step-level and final-balance accuracy, and the decomposed system's success, which the prediction never sees, lands within 9 percentage points of the predicted rate at every depth.

0.55

Beyond Task Success: A Theory of Representation Reuse

cs.LG ·2026-10-13 ·Zibo Meng, Andrew C. M. Austin, Alin Achim
similarity 0.58
Abstract · 42 pages, 10 figures

A learned representation is useful beyond its source task only if later tasks can make use of what the encoder has already learned. Source-task performance, however, gives no guarantee that the representation itself will remain useful once the original head is removed. We study representation reuse with respect to a specified family of future tasks. For such a family, we define the task-relevant state as the coarsest deterministic state sufficient for all of its tasks. A larger task family can require a finer state, and losing a required distinction makes at least one future task unrecoverable on a target support containing that conflict. Exact reuse also depends on how the retained information is presented to the downstream rule. We separate this into structural accessibility, which concerns whether the required distinctions remain recoverable, and coordinate consistency, which concerns whether those distinctions can be interpreted by the same downstream rule across samples. Both failure modes appear separately in the experiments. Reuse improves as task-relevant distinctions become more accessible. Reversible sample-dependent coordinate changes can sharply reduce reuse even when the representation remains recoverable, and inverting the applicable coordinate change restores performance. The same accessibility-reuse ordering appears in prospectively specified CIFAR-100 experiments with both ResNet-18 and DenseNet-121. Finally, preserving a candidate state that contains the distinctions needed by the anticipated task family improves reuse on compatible held-out tasks, with the clearest benefit when target supervision is limited. Representation reuse is therefore relative to the tasks that follow source learning: a useful representation must retain the distinctions those tasks need and make them available in a form that a shared downstream rule can use.

0.19

Revisiting EFX and fPO Allocations for Binary Chores

cs.GT ·2026-09-12 ·Zehan Lin, Xiaowei Wu, Shengwei Zhou
similarity 0.58
Abstract · 28 pages, no figure

We study fair and efficient allocations of indivisible chores under binary additive costs, with a focus on unequal entitlements and best-of-both-worlds guarantees. While binary valuations have been extensively studied for goods, their chore counterpart remains much less understood. A notable exception is due to Tao et al. (TCS 2025), who established that EFX and fPO are compatible for binary chores with equal entitlements. We revisit binary chores under unequal entitlements and establish the computation of allocations that satisfy WEFX and fPO. Our key technical contribution is a new lexicographic potential function tailored to chores: any allocation minimizing this potential ensures both WEFX and fPO. This potential further guides a polynomial-time local-search algorithm for computing allocations with such fairness and efficiency guarantees. For best-of-both-worlds guarantees, we show that unequal entitlements create a sharp obstruction: even with two agents and identical binary additive costs, no lottery can simultaneously satisfy ex-ante WEF and ex-post WEF1. In contrast, for equal entitlements, we construct in polynomial time a lottery that is ex-ante EF and fPO, while every realization is both EFX and fPO.

0.41

What Does a Token Cost? A Mixture-of-Agents Measurement of Sufficient Per-Token Compute

cs.AI ·2026-10-01 ·Zhixu Du, Weijia Han, Hai Helen Li, Yiran Chen
similarity 0.57
Abstract

Large language models spend the same amount of computation on every token they generate, regardless of how difficult each token is to produce. Methods such as speculative decoding and model routing are built on the premise that much of this computation is unnecessary, yet the computation an individual token actually requires has not been measured. We measure it through a Mixture-of-Agents (MoA) lens: a panel of fifteen language models of increasing capacity, drawn from three families, in which every agent attempts to reproduce a reference sequence token by token, conditioned on the correct preceding tokens. We define the inference cost of the smallest agent that succeeds as the token's sufficient compute, which upper-bounds what the token requires. On three core benchmarks, a 0.5B agent reproduces 92--95\% of reference tokens. Across Qwen, OLMo, and R1-distilled panels, the most expensive 10\% account for 64--80\% of estimated FLOPs. On all 500 MATH-500 problems, the MoA-derived map helps model routing reduce projected latency from 7.59 to 5.12 seconds while slightly improving accuracy, relative to the best confidence-routing baseline. The MoA-map helps drafting use 32.6\% fewer draft tokens and approximately 20\% lower projected latency than fixed-window drafting at similar accuracy. These comparisons reveal remaining allocation headroom, motivating controllers that exploit sufficient-compute structure.

0.18

What Must Survive? Exact Task-Information--State Frontiers Under Partial Task Revelation

cs.LG cs.IT ·2026-09-18 ·Ronald Katende
similarity 0.57
Abstract · 12 pages, 2 figures, 1 table. Substantially expanded version: added sharp approximate bounds, overlap-deficit theory, approximation guarante…

A state may need to be compressed before its exact downstream task is known. For a finite family of linear task operators $\{T_u\}_{u\in\U}$, we characterize exactly how much state must survive when only one of $K$ coarse task messages is available at compression time: $$p^*(K)= \min_{\substack{\Pcal\text{ partition of }\U\\|\Pcal|\le K}} \max_{C\in\Pcal}\rank(T_C),$$ where $T_C$ stacks the tasks that remain unresolved within cell $C$. Thus task information reduces retained state precisely by separating tasks whose joint task-visible subspace is expensive. We derive the dual bit frontier, an irreducible common-core floor, and a sharp singular-value characterization for nonzero tolerance. For overlapping task families, a cumulative overlap deficit places the exact frontier within an additive $Δ$ of weighted load balancing. Optimal partitioning is strongly NP-hard, yet direct-sum families admit classical approximation guarantees and a PTAS. We stress-test the theory on learned task operators from CIFAR-10, Fashion-MNIST, SVHN, and Burgers observables. For Burgers with $K=2$ and $\eps=0.35$, a constructive partition attains $p=4$, while balanced random partitions require median $p=6$, with held-out worst standardized RMSE $0.0368$. The results distinguish uniform task sufficiency from distributional and decision-level performance.

0.37

Context Has a Price: Adding and Removing Context for LLM Coding Agents under Prefix Caching

cs.AI ·2026-11-17 ·Zerui Yang, Miaomiao Dong, Quan Xue, Chaorui Zhang, Xuanyu Zheng +7 more
similarity 0.57
Abstract

Coding agents repeatedly send their conversation history to a language model. Adding useful code may reduce search, while removing old tool outputs may shorten later prompts. But do these changes reduce the cost of solving a task? We study this as a measurement problem in more than 20,000 runs of open models on SWE-bench Verified, SWE-bench and Loc-Bench. We account separately for uncached input, cached input and output tokens. Three findings emerge. First, in our main evidence-package experiments, retrieved code reduces read and search commands by 18--34%, but increases cost by 33--42% when cached input costs one tenth of uncached input, without a measurable improvement in resolution. Second, removing old observations can either save money or increase cost: the same approach saves 19--36% without a cache discount but increases cost by 38--116% with a tenth-price cache. Third, shorter prompts do not guarantee cheaper runs because agents may respond by taking more steps. We also find that concurrent experiments can share cached prefixes and distort cost comparisons. These results show why context-management methods should be evaluated using both token prices and the agent's subsequent behavior.

0.18