CS Paper Radar

A Theory of Information Architecture for Networked Decisions: Freshness, Locality, and Coordination

Scott Moeller, Bhaskar Krishnamachari

eess.SY cs.NImath.OC ·submitted 2026-09-06 03:04 UTC · v1
code/data

Abstract

Networked systems face a tradeoff between the scope of the information behind a decision and its freshness: a broader view of the system supports better coordination, but assembling and communicating it takes time, so it arrives older. We study this tradeoff for a team of agents that repeatedly choose actions to minimize a shared quadratic cost driven by an environment that evolves on its own, unaffected by the agents' actions. An information architecture specifies what each agent observes, from where, and with what delay; we measure an architecture by the cost it loses relative to a decision made with complete, current information. We first compare fresh local observations with a complete but delayed global view. When every component of the environment decorrelates at a common exponential rate, this comparison reduces to a closed-form threshold on the ratio of delay to coherence time. We then study intermediate architectures in which each agent acts on a time-aligned, and therefore older, snapshot of a wider neighborhood. The optimal neighborhood radius occurs where the marginal value of added scope equals the marginal cost of lost freshness. In a canonical spatial model, this radius is set by the spatial-correlation, decision-relevance, and temporal-propagation lengths. Throughout, architecture performance is governed by the predictability of the optimal decision rather than of the raw state.

Comment
44 pages, 6 figures. Manuscript source and complete reproduction materials are available at https://github.com/ANRGUSC/TINA

Closest papers

Nearest neighbours by meaning across the whole index.

Steering Emergent Behavior in Multi-Agent LLM Systems via Information Networks

cs.MA cs.AIcs.GTcs.SI ·2026-11-09 ·Sepehr Ilami, Babak Heydari
similarity 0.60
Abstract · It is preliminary and is not suitable for public release yet

Large language model (LLM) agents increasingly operate in groups, each pursuing an individual objective while jointly determining system performance. If an operator controls which agent observes which other agent, but not their payoffs or messages, how should observations be structured to raise collective welfare? We make the information network (who observes whom) a design object, decoupled from the fixed interaction network over which agents act. Ten identical LLM agents play repeated group-decision games; by default each observes only an anonymous summary of the group's previous-round outcome, and a manager with a fixed budget adds directed observation links that reveal peers' past actions. Across 1,080 episodes and six games spanning coordination, anti-coordination, social dilemmas, and discovery, we ask how much information to share and, at a fixed budget, who should observe whom. Disclosure creates behavioral coupling: observation acts as a contagion channel whose welfare effect depends on the alignment between individually attractive behavior and the collective objective. First, the value of information is alignment-contingent: more peer information tends to help or be neutral when individual behavior is aligned with the collective goal, but under free-riding or congestion externalities it amplifies collectively harmful behavior; in a public-goods game the group does best with no information at all. We read this sign separation as a cross-game regularity within one controlled LLM population, not a model-invariant law. Second, at a fixed budget, who observes whom matters primarily when coupling is harmful: a modular "barbell" that lets sub-populations entrench harmful behavior is reliably the worst wiring, reversing the network-reciprocity intuition from human evolutionary game theory. These results argue against a default of full transparency for agent collectives.

0.05

Emergence, Not Bandwidth: Physical Coupling and the Limits of Learned Multi-Agent Communication

cs.LG cs.MAcs.RO ·2026-09-28 ·Mihir Chauhan, Aniket Bera
similarity 0.59
Abstract

Rate-limited multi-agent teams raise three questions the emergent-communication literature has answered only empirically: what an optimal message should encode, what compression costs over a horizon, and when a learned protocol is unique enough for a teammate to read. We answer them for rate-limited Dec-POMDPs, then measure how far reinforcement learning falls short of the optimum. Our theorems fix what is achievable independently of any learner, so a gap between an engineered and a learned sender at the same bit budget is an optimization fact, not an information-theoretic one. We instantiate this on three MuJoCo arenas spanning zero, partial and rigid physical coupling, charging every condition exactly 2 bits per decision, and create the discriminating regime by closing a physical side channel within one arena, holding bodies, task and reward fixed. Communication value is governed by coupling: under rigid coupling through a shared object, no channel beats silence (+0.001 +/- 0.001, p = 0.982, n = 25), since proprioception already carries that information; without coupling, every condition solves the task; under partial coupling, the engineered 2-bit sender reaches an interquartile mean of 1.000 but the learned one reaches 0.482, indistinguishable from silence (p = 0.400, n = 25). With a shared alphabet, bandwidth cannot explain the gap. Warm-starting from an engineered receiver localizes the failure: the same channel reaches 0.857 versus 0.562 cold-started (p < 0.001), so it is neither representational nor one of maintenance; reinforcement learning fails to discover the protocol. Cross-play shows learned protocols are individually meaningful but mutually unintelligible: self-play 0.980 collapses to 0.144 across seeds, and our best constructed alignment leaves at least 77% of that gap. All headline results use 25 seeds per arena and seven published baselines at matched rate.

0.15

When Agents Coordinate: Measuring Coordination in Multi-Agent AI Coding

cs.AI cs.SE ·2026-08-17 ·Giuseppe Destefanis, Tomaso Aste
highly cited similarity 0.58
Abstract

We study how teams of AI coding agents coordinate while solving programming tasks. Current evaluations usually report whether the agents complete the task and how much the run costs, leaving the coordination inside the team largely unmeasured. We introduce an instrument to measure this coordination. Each run is represented as a temporal network in which agents and files are nodes, and messages, file writes, and file reads are timestamped directed edges with an associated cost. We apply this instrument to 1902 runs, each evaluated with a fixed test suite, across configurations that vary the team size, the team structure, and the file policy. The resulting networks show how coordination changes as teams grow and as the work changes. Direct messaging initially increases close to quadratically with the number of agents, with much of this growth coming from an early round of introductions. As the teams grow further, this increase levels off in the largest teams we study, where agents increasingly communicate through broadcast messages. The task also shapes the network that emerges. Work built around a shared specification produces dense, highly connected teams, while pipeline tasks produce sparse networks organised around local interfaces. Shared files can replace repeated 1-to-1 communication, cutting output tokens by about 42% at eight agents on message-heavy work, while adding overhead when files already carry the coordination. Naming one agent as coordinator creates no communication hub and provides no reliable improvement in success. We also observe an unprompted tendency for agents to seek out hidden grading material. We repeat the key experimental conditions in a sealed environment, replacing the hidden material with marked placeholder files. Across 244 additional runs, agents still reach for it in four fifths of runs, while the coordinator and file-channel findings reproduce.

0.40

When Should AI Agents Ask? Clarification Requests Under Limited Human Attention

cs.AI cs.HC ·2026-10-30 ·Hanzhao Wang, Shengjie Liu, Zhengchao Wang
benchmark similarity 0.57
Abstract

AI agents increasingly carry out delegated tasks in parallel, with one person overseeing several of them at once. In practice, an agent often lacks information its task requires, such as an unstated preference, constraint, or specification. It can ask the human to clarify, or it can search for the information itself, for example in past records, which takes time and effort and may fail. In this paper, we study how to coordinate these decisions across several agents that share one human with limited attention. We build a stylized model in which each agent can search, ask, or continue the parts of its task that do not depend on the missing information, and we formulate the problem as a dynamic program. We first show that whether an agent should ask depends on more than its own uncertainty: an agent with other work to do can be better off asking earlier, and which question the human should answer first depends on all waiting questions, so no ranking computed agent by agent is optimal. We then propose the Pairwise Coordination Policy (PCP), which uses exact one- and two-task problems to estimate how pairs of tasks delay each other when they share the human. Theoretically, PCP is exactly optimal when at most two requirements remain unresolved and costs at most twice the optimum when every unresolved requirement must be resolved by the human. We evaluate PCP on 864 synthetic cases and in a case study with LLM agents. On the synthetic benchmark, PCP's mean gap to optimal cost is 0.07%, and it reduces cost by an average of 18-31% relative to three standard rules for when to ask. In the LLM case study, agents completed every task correctly, and PCP achieved the lowest mean cost in all tested settings.

0.21

Pathwise Information Certificates for Decentralized Adaptive Sensing

cs.IT cs.LG ·2026-10-07 ·Theodoros Tsiligkaridis
similarity 0.57
Abstract · 26 pages, preprint

We study decentralized adaptive sensing, where multiple agents choose measurements from evolving local beliefs while exchanging information over a communication graph. We ask whether the measurements actually selected by an adaptive policy have collected enough evidence to distinguish the true target from every plausible alternative. We develop a pathwise certificate based on the Rényi--Chernoff information accumulated along the realized sensing trajectory. It yields nonasymptotic MAP-error bounds and an anytime, network-wide stopping rule for arbitrary history-dependent sensing policies, while separating accumulated statistical information from a bounded network-mixing transient. Linear growth of the information against the least-resolved competitor implies exponential decay of MAP and squared-localization error. A classical pairwise KL converse, specialized to the adaptive decentralized transcript, shows that insufficient information on any pair prevents a positive uniform error exponent, confirming the hardest competitor as a fundamental bottleneck. Across policies, graph topologies, sensor profiles, and seeds, the worst-competitor score correlates more strongly with localization speed than an average-pair proxy in both 1D ($r=0.89$ versus $0.40$) and structured 2D sensing ($r=0.77$ versus $0.48$). Our results provide a practical way to certify and diagnose adaptive multi-agent sensing systems using the evidence they actually collect.

0.24

Network Intervention by Polling Strategic Agents

cs.GT cs.MAcs.SImath.OC+1 ·2026-10-06 ·Chenyu Zhang, Rohit Parasnis, Saurabh Amin
published similarity 0.57
Abstract · Published as a conference paper at NeurIPS 2026

A planner in a network of strategic agents faces three entangled challenges: the optimum depends on agents' private information, queried agents may misreport to steer the outcome, and exact computation does not scale. We study these challenges in multi-activity network games with heterogeneous private technologies, in which the planner sets non-discriminatory prices. We show that the optimal prices admit a centrality-based decomposition of the welfare kernel: each agent's contribution scales with its squared centrality in a network reweighted by agents' preferences across activities. This decomposition motivates Poll, a polling algorithm in which the planner samples one agent per round, walks briefly through the agent's neighborhood, and updates the price from a local report. From the same decomposition flow three forms of efficiency: computationally, Poll uses significantly fewer operations than exact computation and other distributed methods, requiring up to three orders of magnitude less communication on a real-world network with over 300,000 agents; statistically, its query complexity scales with topology and preference heterogeneity rather than explicitly with population size; and economically, it converges to welfare-maximizing prices while admitting behavior-specific implementations that induce truthful reports and detect adversarial deviations.

0.29

Optimal Sampling and Transmission Policy for Information Freshness in Gossip Networks

cs.IT cs.NIeess.SP ·2026-11-07 ·Irtiza Hasan, Ahmed Arafa
theory similarity 0.57
Abstract · Potential IEEE journal publication

We study the optimal sampling and transmission policies for a transmitter communicating with n gossiping receivers with the objective of tracking a source's status over time using a semantic freshness metric: Version Age of Information (VAoI). The transmitter observes the version changes in the source, and can acquire a new information version by paying a sampling cost. The receivers gossip, allowing information exchange among each other without direct transmission. Gossiping can save on transmission cost, but it may propagate stale version information, necessitating transmitter intervention. With imperfect communication links, we formulate an infinite horizon average cost Markov Decision Process (MDP) in order to jointly optimize receivers' VAoIs, sampling and transmission costs in a time slotted fully connected (FC) gossip network. We first solve the MDP using Relative Value Iteration (RVI) algorithm. Then, we prove that the sampling decision has a threshold structure in the transmitter VAoI. Further, under reliable gossiping links, we show that transmission and idling has an VAoI-difference threshold structure with minimum VAoI activation. Numerical results obtained using RVI show that the optimal policy consistently outperforms natural baselines. These results characterize how source sampling, direct transmission, and receiver gossip should be jointly coordinated for cost-aware semantic freshness in gossip networks.

0.13

Memory Is Communication: The Frontier Between Remembering and Signaling

cs.AI cs.CLcs.ITcs.MA ·2026-08-17 ·Yashar Talebirad, Eden Redman, Ali Parsaee, Osmar R. Zaiane
similarity 0.57
Abstract

A bounded agent may obtain information for a decision from its own past, from peers, or from both sources. Retaining task-relevant history can reduce later communication, while a peer message can supply what memory lacks. Under limits on both resources, how should an agent allocate its information budget? Given a fixed task and decision rule, the memory and message rate pairs attaining a performance threshold form an achievable region under specified rules for using history and peer observations. We call its efficient boundary the remembering--signaling frontier. Across conditions where history permits the same maximum reduction in task loss, we hypothesize that a bounded agent will need less peer communication when it obtains a larger loss reduction from history. In preliminary referential games, target repetition coincided with shorter successful messages, while predictability from a hidden cyclic rule did not shorten them. Experiments varying memory and message rates can estimate the frontier and test this prediction across cooperative tasks.

0.10