Papers for

distributed system architects

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Improved bound for partitioning graphs into independent transversals

An asymptotic bound for Yuster's independent transversal factor conjecture

Abstract: An $[r,n,1]$-graph has $r$ independent parts of size $n$, with a matching between each pair of parts. Yuster conjectured in 2021 that every such graph has a partition into independent transversals whenever $n\ge 2\lceil r/2\rceil$. We prove that there is an absolute constant $A>0$ such that, for all sufficiently large $r$, this partition exists whenever $n\ge\lceil r+A r^{20/21}\rceil$. Thus $f(r)\le r+O(r^{20/21})$, where $f(r)$ is the least $n_0$ such that every $[r,n,1]$-graph has such a partition whenever $n\ge n_0$. In particular, $f(r)/r\to1$, giving an asymptotic form of the conjecture.

Thu 19 NovDiscrete Mathematics
The gist
There is a special kind of graph with multiple groups of points where connections exist between groups, and a question about how to break these graphs into neat parts was posed by Yuster. The authors proved that for large enough groups, such a partition always exists with a size that is very close to the number of groups. Their work provides a near-final answer to Yuster's conjecture by showing the size needed grows almost exactly with the number of groups.
Open → 2611.26259v1

Local updates speed federated optimization but can cause bias

Faster to the Wrong Answer: The Price of Local Updates in Federated Optimization

Abstract: Local computation can improve the conditioning of federated updates but may also introduce bias, causing their fixed point to differ from the global minimizer. We characterize the minimum worst-case bias achievable under a prescribed conditioning bound. We consider strongly convex quadratic client objectives with Hessian eigenvalues in $[μ,L]$ and local updates represented by a shared positive spectral filter. Client heterogeneity is measured by the root-mean-square gradient at the global minimizer. For a uniform surrogate condition number bounded by $χ\in[1,L/μ]$, we establish the exact worst-case bias per unit heterogeneity, $(L-μχ)/(2μL\sqrtχ)$, and show that local gradient descent with sufficiently small step sizes and proximal updates attain this bound. Our analysis reduces populations of arbitrary dimension, including noncommuting Hessians, to distributions over scalar curvatures. This reduction provides optimality certificates and worst-case constructions involving at most three scalar clients. We further extend the sharp proximal bias bound to smooth strongly convex objectives beyond quadratics and quantify the error introduced by inexact local solves.

Wed 18 NovMachine Learning
The gist
Federated optimization means training models using data held on many different devices without sharing the data itself. Doing more work locally on each device can make training updates better conditioned and faster, but it can also cause the final combined model to be biased, meaning it may not find the true best solution. The authors analyze how big this bias can get in the worst case, offering precise formulas and examples. They also show when local algorithms reach this minimum bias and extend their results beyond simple quadratic cases.
Open → 2611.24057v1

Distributed algorithms face high round complexity for graph degeneracy estimation

Lower Bounds for the Distributed Computation of Degeneracy and k-Core

Abstract: The degeneracy of a graph $G$ is the maximum integer $k$ such that $G$ has a non-empty $k$-core, where the $k$-core is the largest induced subgraph with minimum degree $k$. Computing the $k$-core of a graph $G$ is P-complete. In the decentralized setting, the sequential peeling algorithm can be distributed so that the core value of every node, i.e., the largest integer $k$ for which the node belongs to the $k$-core, is computed in $O(n)$ rounds in $n$-node networks, where adjacent nodes exchange only $O(\log n)$ bits at each round, i.e., in the standard CONGEST model. However, while $Ω(D)$ rounds is a trivial lower bound for these problems in networks of diameter $D$, this does not rule out the existence of an algorithm running in $O(D)+o(n)$ rounds in CONGEST, as it is the case for many very important graph problems, including MST. We show that it is unlikely that such an algorithm exists, or, if it does exist, then it requires $\tildeΩ(\sqrt{n})$ rounds. Specifically, our first main result states that, for any $ε>0$, approximating the degeneracy up to a multiplicative factor $2-ε$ requires $\tildeΩ(\sqrt{n})$ rounds in CONGEST even in networks of diameter $O(\log n)$, and still $\tildeΩ(n^{1/3})$ rounds in networks of constant diameter. We also show that improving this lower bound seems challenging, as we demonstrate that the newer frameworks cannot be used as black boxes to obtain a better lower bound for degeneracy. Our second main result provides a better bound, albeit conditional. It states that, unless the well-known circuit value problem (CVP) admits a parallel polynomial speedup -- an outcome considered unlikely -- it holds that, for every $ε>δ>0$, deciding whether a graph is 2-degenerate cannot be solved in $O(D+ n^{1-ε})$ rounds with $O(n^δ)$-time parallel local computation per round at each node.

Mon 16 NovDistributed, Parallel, and Cluster Computing
The gist
Degeneracy measures how densely connected parts of a network are, found by peeling away less connected nodes. The authors study how quickly computers in a distributed network can find this measure when only limited information is shared each step. They show it takes a surprisingly long time—much longer than for many other network tasks—even on networks with small diameter. This means fast distributed algorithms for approximating or deciding degeneracy likely need many communication rounds or rely on unlikely breakthroughs in computing theory.
Open → 2611.21511v1

Parallel convolution method improves multi-agent system learning efficiency

From Recursion to Convolution: Parallel Self-Improvement for Multi-Agent Systems

Abstract: Multi-agent self-improvement enables agents to improve through interaction and feedback. However, sequential dependencies across agents and refinement rounds can propagate errors, increase computational costs, and limit parallelism. Moreover, refining individual features or agents in isolation can overlook their dependencies and restrict collective coordination. To address these challenges, we propose ConvRSI, a framework for parallelizing multi-agent self-improvement through convolution. ConvRSI couples intra-agent convolution, which jointly refines related agent features, with inter-agent graph convolution, which aggregates messages according to the collaboration topology. Both stages operate in latent space, enabling parallel updates without repeatedly decoding and re-encoding intermediate messages. Experiments on MATH-500 show that ConvRSI achieves 5.04% performance improvement while reducing 17.27% inference cost, and 45.11% latency compared with RecursiveMAS. It also supports diverse collaboration patterns by representing their topologies as adjacency matrices. These results demonstrate the potential of convolutional co-evolution for efficient multi-agent self-improvement. Our code and datasets are provided in https://github.com/LYA2333/ConvRSI.

Mon 16 NovArtificial IntelligenceComputation and LanguageMachine Learning
The gist
Many computer programs use groups of agents that learn and improve by working together. Usually, improving these agents step by step takes a lot of time and can cause errors that slow things down. The authors propose a new way to let these agents learn and improve all at once using a technique called convolution, which helps them share information better and faster. They tested their approach on a math problem dataset and found it improved performance while making the process quicker and cheaper. This method also works for different kinds of teamwork setups among agents.
Open → 2611.20891v1

Self evolving AI agents modeled and predicted using gas dynamics

A Self-Evolving Agent Runs Like a Gas: Describing and Predicting Its Evolution with Fluid Dynamics

Abstract: A self-evolving LLM agent improves in service by rewriting its own plugin library under a validation gate. Agent engineering is converging on exactly such agents: single systems in continuous operation, carrying populations of runtime instances (plugins, skills, tools) past the point where anyone can read the library and still predict what the system will do. Yet the run itself, the aggregate motion of that population across hundreds of edit rounds, is unstudied: no theory says whether it relaxes, oscillates, or freezes. A recent kinetic theory supplies the missing level: under four architectural properties, the plugin instances of one agent behave as identical hard spheres whose density obeys a master equation, and the theory is candid that its gate injects and drains credit, momentum is not conserved, and waves are excluded by construction. We argue the boundary is architectural; keeping the four safety theorems, we stack conservation axioms on top. A closed-credit ledger makes credit a collision invariant and unlocks acoustic waves at a measurable, engineerable speed; a zero-sum projection gate conserves centroid momentum unconditionally, for any proposal stream. Both layers are proven and executed: the axis total is conserved to the digit over 66 interventions under a live gate, and the pre-registered decisive probe returns the theory's directional verdict: linear wavefronts where the ledger holds, dissipation where it does not, replicated across two population sizes. For agents that must never stop, the gas description is not a metaphor: it is the measurement interface through which their future becomes readable.

Mon 16 NovGraphics
The gist
The paper looks at AI agents that improve themselves by changing their own programs over time. The authors use ideas from how gases behave to describe and predict how these agents change and evolve continuously. They create mathematical rules that track how the agents' internal parts interact and conserve certain quantities like credit and momentum. Their experiments show patterns like waves or energy loss depending on these rules, helping people understand and control these evolving AI systems better.
Open → 2611.20584v1

Optimal strong connectivity preservers found with efficient two-edge failure handling

Optimal-Size Strong Connectivity Preservers under Two Edge Failures in Subcubic Time

Abstract: A $k$-edge-failure strong connectivity preserver of a directed graph on $N$ vertices is a spanning subgraph that has the same strongly connected components as the input after each set of at most $k$ edge deletions. The lower-bound construction of Baswana, Choudhary, and Roditty [BCR18], adapted to strong connectivity in [CC20], gives the previous best bound of $Ω(2^kN)$ necessary edges. Hoppenworth, Saranurak, and Wang [HSW25] prove an $O(k4^kN\log N)$ upper bound, leaving a logarithmic gap for fixed $k$. We close this gap by giving an explicit strongly connected graph on $N=2^d$ vertices with $N-1+(N/2)\log_2N$ edges, every one of which is necessary in a two-failure preserver. Together with the upper bound of [HSW25], this proves that the optimal size in the worst case is $Θ_k(N\log N)$ for every fixed $k\geq2$, whereas it is $Θ(N)$ for $k=1$ [GIP20]. The same graph has a one-failure preserver with at most $3(N-1)$ edges. We also give a randomized algorithm that either returns a spanning subgraph or reports failure. For every fixed $c,\varepsilon>0$, with probability at least $1-N^{-c}$ it returns a correct preserver for $k=2$ with $O(N\log N)$ edges, in $\widetilde O(N^{(ω+3)/2+\varepsilon})$ time and $\widetilde O(N^2)$ space. Here $ω$ is the matrix multiplication exponent over a fixed finite field.

Thu 12 NovData Structures and Algorithms
The gist
Strong connectivity preservers are smaller graphs that keep the important connection structure of the original graph even if some connections fail. The authors found the smallest possible size of these preservers when up to two connections fail, proving it grows like N times log N for large graphs. They also developed a randomized algorithm that quickly builds these preservers in subcubic time. This work closes previous gaps in understanding how large these preservers need to be and how fast they can be computed.
Open → 2611.16313v1

Chromatic number stays stable when removing few graph edges

Impropriety and resilience of the chromatic number

Abstract: We show that, for $p$ bounded away from $1$ and $np\to\infty$, the chromatic number of the binomial random graph $G_{n,p}$ is resilient to removal of a subgraph $H$ with $o(n \log(np))$ edges. It follows that the same assertion holds with $H$ being a subgraph of maximum degree $o(\log(np))$; and both these results are best possible up to a constant factor. We also prove corresponding results for the random $r$-regular graph $G_{n,r}$, when $r\to\infty$ and $r/n$ is bounded away from $1$, where $H$ has $o(n\log r)$ edges or maximum degree $o(\log r)$. Our results rely on a natural connection between chromatic resilience to edge removal and improper graph colouring. This work provides counterpoint to the work of Sudakov and Vu (2008) and Alon and Sudakov (2010), which treated chromatic resilience for $G_{n,p}$ subject to the addition, rather than removal, of edges.

Sun 8 NovDiscrete Mathematics
The gist
This paper studies how the minimum number of colors needed to color a random graph, called the chromatic number, changes when some edges are removed. The authors found that as long as the removed edges are relatively few, the chromatic number remains almost the same, showing the coloring is resilient. They also link this stability to a related idea called improper coloring, where some coloring rules are relaxed. Their results match known cases where edges are added, providing a fuller picture of how robust graph coloring is against changes.
Open → 2611.11280v1

Self-stabilising approximate clock synchronisation needs linear time

Self-stabilising approximate clock synchronisation requires linear time

Abstract: Synchronising the clocks of processes is a fundamental problem in distributed computing. We consider message-passing systems in which processes start in an arbitrary initial state (self-stabilisation) and up to $f$ processes may be non-transiently faulty. It is well known that synchronising clocks \emph{exactly} is at least as hard as consensus and requires $Θ(f)$ time. In contrast, without self-stabilisation, clocks can be synchronised \emph{approximately} much faster, in time independent of the number of non-transient faults [Srikanth and Toueg, JACM 1987; Welch and Lynch, Inf. Comput. 1988]. In this work, we show that deterministic self-stabilising approximate clock synchronisation tasks require $Ω(f)$ time to stabilise. This gives the first non-trivial time lower bound for these tasks, whose time complexity has remained open for over two decades [Dolev and Welch, JACM 2004; Dolev, Függer, Schmid and Lenzen, JACM 2014]. In particular, this answers the open question whether self-stabilising approximate clock synchronisation tasks are as hard as consensus or as easy as approximate agreement [Lenzen and Rybicki, JACM 2019]. The results show that guaranteeing \emph{both} transient and non-transient fault-tolerance simultaneously is expensive even for approximate synchronisation tasks. The lower bounds hold in a very strong model: the faulty processes can only crash, the local clocks of processes have no clock drift, and the message delay is bounded and known to all processes. The proof is based on a combinatorial topological argument showing that no fast finite-state protocol can ensure that the clocks behave consistently across all executions. To our knowledge, this is the first use of topological arguments to prove time lower bounds in the self-stabilising setting.

Tue 3 NovDistributed, Parallel, and Cluster Computing
The gist
Synchronising clocks in distributed computer systems is challenging, especially when processes can start in any state and some may be faulty. The authors show that even to synchronise clocks approximately, it takes time proportional to the number of faulty processes when ensuring the system self-recovers from any initial errors. This means that making clock synchronisation tolerant of both transient and persistent faults is fundamentally slow. Their proof relies on a new method using topological arguments in the self-stabilising setting.
Open → 2611.04725v1

Communication oblivious algorithms achieve tight bounds for sorting and permutation

Communication-Oblivious Permutation and Sorting

Abstract: With the help of secure hardware such as trusted execution environments (TEEs), private data can be uploaded and computed in untrusted cloud clusters, so that an adversary controlling the cloud can only see the data in encrypted form. However, the communication pattern between the processors may still reveal sensitive information about the data, so it is important to develop parallel algorithms in the BSP model whose communication pattern is independent of the input data, a property known as \textit{communication obliviousness}. In this paper, we study such algorithms for three fundamental problems: permutation, sorting, and 0-1 sorting. For the first two problems, we prove a tight (up to lower-order terms) communication complexity of $(2-2/p)n\pm o(n)$. Here, $p$ is the number of processors and $n$ is the input size, assuming $2\le p$ and $p=o(n^{1/3})$. Our lower bound holds regardless of the number of rounds and local memory size, while for balanced permutation and sorting the upper bound is achieved in a constant number of rounds with load at most $n/p+o(n/p)$. For 0-1 sorting, we also derive a tight communication complexity of $C_{\mathrm{cut}}(p) \cdot n \pm o(n)$, where $C_{\mathrm{cut}}(p)$ is the optimal value of a linear program parameterized by $p$. Although there appears to be no closed-form for $C_{\mathrm{cut}}(p)$, we show that it is strictly smaller than $2-2/p$ for all $p\ge 3$, thus separating 0-1 sorting from general sorting in terms of their communication complexity.

Thu 29 OctData Structures and Algorithms
The gist
When computers process secret data on cloud servers, the way they communicate can unintentionally leak information. The authors study how to perform fundamental tasks like rearranging or sorting data so that the communication patterns do not depend on the data itself, keeping it more secure. They establish exact minimum communication amounts needed to do this across multiple processors and show differences between sorting just zeros and ones versus general sorting. This helps improve privacy when running computations on untrusted hardware.
Open → 2610.39922v1

Quantum-resistant blockchain consensus with multiple proposers and no signatures

Quantum Cadence: Post-Quantum Consensus with Multiple Concurrent Proposers

Abstract: The consensus protocols of most high-performance blockchains use quorum certificates, which bundle the signatures of a quorum of validators. Signature schemes such as BLS can aggregate the signatures of a whole quorum into a single short signature, which keeps these certificates small. A large-scale quantum computer would break these schemes, and no post-quantum scheme with comparable aggregate size and aggregation time is known. Without aggregation, a certificate holds one large post-quantum signature per member of the quorum, so it becomes infeasible for each validator to broadcast certificates, as modern consensus protocols often require. We present Quantum Cadence, a post-quantum consensus protocol with multiple concurrent proposers that avoids certificates altogether: every validator counts quorums among the messages it has received itself. Its safety and liveness do not even depend on signatures, although we add signatures to obtain accountability. Quantum Cadence builds on Cadence and replaces its slot consensus, Chorus, with Quantum Chorus, which keeps the optimal fast-path latency of Chorus: dissemination followed by two rounds of votes. When its fast path fails, Quantum Chorus runs Coda, our signature-free Byzantine agreement for multiple proposers. We also outline how the Conductor, which schedules the slots of Cadence, can be adapted to Quantum Cadence. In simulations with 200 validators, Quantum Chorus has a latency comparable to that of Chorus and scales better with the number of proposers.

Fri 23 OctDistributed, Parallel, and Cluster ComputingCryptography and Security
The gist
Most blockchains rely on special cryptographic signatures that could be broken by future quantum computers, making secure agreement difficult. The authors present Quantum Cadence, a new blockchain consensus design that avoids using these risky signatures altogether by having validators count votes themselves. This approach keeps the system both safe and fast, even with many validators proposing blocks at once. Their tests show Quantum Cadence works well with hundreds of participants, maintaining low delays and good scaling.
Open → 2610.32803v1

Blockchain clients become active to ensure transaction inclusion safety

How Not to Be Censored: Inclusion Safety in Client-Led Consensus

Abstract: Blockchain consensus protocols implicitly follow a client-server architecture: validators are the only active participants, while clients (i.e., users) merely submit transactions and rely on validators to include them. This abstraction obscures a fundamental question: what should a client do to guarantee the timely inclusion of its own transaction? We study this question by introducing a leaderless consensus protocol in which clients are active. We define inclusion safety: the guarantee that a client's transaction enters some of the blocks produced for an epoch, and that every block omitting it belongs to a fork that is eventually abandoned. Because every transaction carries a reference to a block of the previous epoch, clients help select the surviving fork. This yields two paths to inclusion: reaching sufficiently many honest replicas within an epoch, or relaying a block containing the transaction across epochs until the corresponding fork becomes canonical. In a generalized model spanning synchrony and asynchrony, the client's and the replicas' connectivity are substitutes for inclusion safety: it is achieved either if the client is well connected, or if the client is poorly connected but honest replicas communicate reliably, provided the client reaches at least one of them. However, the substitution is imperfect: when inclusion safety rests on the replicas' connectivity, it requires a longer epoch compared to when the client is well connected.

Wed 21 OctDistributed, Parallel, and Cluster Computing
The gist
Most blockchain systems give validators control over which transactions get recorded, leaving users uncertain if their transactions will be included quickly. The authors study a new system where users actively help decide which transactions are accepted, improving the chances their transactions will be included in the blockchain securely. They define a guarantee called inclusion safety, meaning if a transaction is excluded from some blocks, those blocks will eventually be discarded. Their approach allows transactions to be safely included either through direct contact with honest nodes or by relaying the transaction over time across blockchain versions. This work provides a way for users to better ensure their transactions are not censored, even in complex network conditions.
Open → 2610.29497v1

Navigable graphs enable efficient paths in low dimensional hyperbolic spaces

Navigable Graphs for Low-Dimensional Hyperbolic Spaces

Abstract: A directed graph on a point set $P$ in a metric space $(X,d)$ is navigable if for every ordered pair of distinct points $s,t \in P$, $s$ has an out-neighbor $v$ with $d(v,t) < d(s,t)$, so greedy routing always reaches the destination. Existing work on sparse navigable graphs mostly assumes bounded doubling dimensions. In this paper, we show that constant-dimensional hyperbolic spaces that do not have bounded doubling dimension also admit sparse navigable graphs. Specifically, for an $n$-point set in $\mathbb H^k$ with a constant $k$, we construct a navigable graph of size $O_k(n)$ with Steiner points, where each node has constant out-degree. We also show that Steiner points can be removed: every $n$-point set in $\mathbb H^k$ admits a navigable graph on the input points alone with $O_k(n)$ edges, though a single vertex may have out-degree $Ω(n)$. Furthermore, with a refined construction with $O_k(n\log n)$ edges and an accompanying greedy routing algorithm, we can obtain routing paths of expected $O(\log ^2 n)$ in both settings with or without Steiner points. With Steiner points, the maximum out-degree is bounded by $O_k(\log n)$. We complement these upper bounds with matching lower bound results. In the hyperbolic plane, there are point sets for which every navigable graph requires maximum out-degree $Ω(n)$, so the maximum linear out-degree above is unavoidable and constant out-degree is only possible with Steiner points. Next, we show that for every constant $α>1$, an $α$-navigable graph may require $Ω(n^2)$ edges, which rules out the standard route of using $α$-navigability to obtain greedy paths of bounded hops. Last, once the dimension $k$ reaches $Ω(\log n)$, there are point sets for which every navigable graph may require $n^{3/2-o(1)}$ edges, matching the upper bounds for general metrics.

Sat 17 OctData Structures and AlgorithmsComputational Geometry
The gist
Navigating networks or maps efficiently means always moving closer to your destination at each step. The authors show how to build simple, easy-to-use directed graphs that guarantee this kind of navigation in particular curved spaces called hyperbolic spaces, even when these spaces have challenging properties. Sometimes extra points (called Steiner points) help keep the connections simple, but they also show ways to do it without those points. The work clarifies how complex these graphs must be, including limits on how many connections a point can have and the number of edges needed.
Open → 2610.24874v1

Delegation challenges in group governance balance cost and control

The Delegation Dilemma: Economies of Scale, Accountability, and Polycentric Governance

Abstract: Many collective-action systems are neither fully decentralized nor fully centralized: agents voluntarily organize into institutions that share organizational costs and delegate decisions to representatives. Delegation can reduce individual costs, but it also transfers control to representatives whose private objectives need not align with those of their constituents. We study this tension in a repeated game with endogenous delegation to self-interested centers. A simple reduced-form model yields a scale--accountability tradeoff: larger constituencies offer greater cost-sharing benefits to members, yet the marginal value to a center of retaining any one constituent decreases as group size grows. Consequently, the prospect of individual exit can sustain non-exploitative delegation only up to an endogenous accountable constituency size. Additionally, we identify parameter regions in which fully delegated, accountable governance, when feasible, must be polycentric. We investigate these predictions through simulations with large language model (LLM) agents. Across five matched pairs of 30-agent simulations, polycentric structures repeatedly emerge but remain fluid, exhibiting cycles of concentration, exploitation, exit, and re-formation. We further find that models of different capacity exhibit similar willingness to assume leadership but differ substantially in their exercise of authority, with Sol initiating exploitation more frequently than Luna in matched decision states.

Thu 15 OctMultiagent SystemsArtificial IntelligenceMachine Learning
The gist
Groups often share decision-making by choosing representatives to reduce costs, but this can cause leaders to act in their own interest rather than the group's. The paper studies how bigger groups benefit from shared costs but make it harder to keep leaders accountable. It shows that groups need to be just the right size to avoid leaders exploiting members and that multiple centers of power often emerge. Simulations with AI agents confirmed these patterns, showing cycles where leadership shifts between cooperation and exploitation.
Open → 2610.21746v1

Stability and generalization explained for biased gradient minimax methods

Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems

Abstract: Minimax optimization refers to a class of optimization problems with some variables to minimize and other variables to maximize. Biased stochastic gradient methods have shown practical success in solving minimax problems to either improve robustness, enhance communication efficiency, or decrease computational costs. These successes motivate a lot of theoretical works to study the convergence of biased stochastic gradient methods, while their generalization analysis remains untouched. In this paper, we present the first framework to study the stability and generalization of biased stochastic gradient methods for minimax problems. We establish a connection between stability and generalization for minimax problems by relaxing the existing bounded gradient assumption to a bounded second moment condition. We then introduce a generalized Lipschitz-type condition on bias and gradient estimators, and derive a general stability bound to clarify the connection among bias, gradient estimators, and stability. We apply our general analysis to Zeroth-order and Clipped stochastic gradient descent ascent (SGDA), and derive stability bounds that match those of SGDA under appropriate smoothing/clipping parameters. We combine stability and convergence analyses together, and derive optimal excess risk bounds of order $1/\sqrt{n}$, where $n$ is the sample size.

Wed 14 OctArtificial Intelligence
The gist
Minimax problems involve two opposing goals, one trying to reduce a value and the other trying to increase it. The paper explains how certain biased methods for solving these problems can still perform well when tested on new data. The authors introduce new ways to measure the stability and quality of these methods without making overly strict assumptions. They prove that these biased approaches can be as reliable as unbiased ones under the right conditions and give theoretical guarantees about their accuracy based on sample size.
Open → 2610.19322v1

Industrial short video ranking improves with chain dimension scaling

Chain Dimension Scaling: Communication-Efficient Loop-Style Scaling for Industrial Short-Video Ranking

Abstract: Industrial recommendation rankers keep scaling in width and depth to billions of parameters, but this increasingly incurs costs in parameter growth, distributed communication overhead, and training inefficiency. We introduce \underline{C}hain \underline{D}imension \underline{S}caling (CDS), a scaling strategy orthogonal to width and depth. CDS repeatedly applies a single feature-interaction block with parameters shared across iterations, so the number of iterations (the chain length) becomes a new scaling dimension that adds no parameters. A lightweight intra-chain residual connection stabilizes optimization and improves quality. CDS enables two regimes. In the \emph{compression regime}, shallow blocks with a longer chain match deeper baselines with fewer parameters and faster training; in the \emph{quality-scaling regime}, increasing chain length under a fixed parameter budget yields consistent offline and online gains, suggesting the chain dimension adds modeling capacity beyond parameter reuse. We evaluate CDS in a large-scale multi-task short-video ranking system in production. In the compression regime, CDS stays within $0.03\%$ of baseline offline quality while reducing trainable parameters by 26.6\% and improving training throughput by 6.4\%, with neutral-to-positive online participation. In the quality-scaling regime, quality improves monotonically with chain length. Wall-clock analysis shows the efficiency gain comes mainly not from reduced FLOPs but from lower cross-device synchronization overhead and reduced optimizer update cost. These results position parameter-shared iterative computation as a practical, communication-efficient scaling axis for industrial ranking systems.

Mon 12 OctArtificial Intelligence
The gist
Recommender systems for short videos have grown very large, making them slow and expensive to train. The authors propose a new way to scale these models by repeatedly using the same part many times, which doesn’t add more parameters but helps the model get better. They show this approach can either reduce the size and speed up training without losing accuracy or improve quality with the same number of parameters. This method also reduces communication costs between devices during training, making it more efficient in real-world systems.
Open → 2610.16415v1

Team strategies without shared randomness have distinct complexity limits

Limit-sure Winning in Team Games without Shared Randomness

Abstract: We study concurrent stochastic games in which a team of agents plays against an adversarial environment. If the agents could access a shared source of randomness, then these games reduce to two-player games. Despite being common in the literature on coalition games, this assumption does not accurately model real-world systems. In this paper, we consider the setting where the agents only have access to individual sources of randomness, and must satisfy a given reachability or safety objective. The limit-sure problem asks whether the team can ensure that the objective is satisfied with probability at least $1-λ$ for every $λ>0$. For reachability objectives, we show that this problem is $\mathsf{NP}$-complete. For safety objectives, we show that limit-sure winning coincides with almost-sure winning, which is known to lie in $\mathsf{P}$. As a corollary of these results, we conclude that model checking of the qualitative fragment of the logic Individually Randomised ATL -- introduced in the recent work of Brice et al. -- is $\mathsf{P}^{\mathsf{NP}}$-complete.

Fri 9 OctComputer Science and Game TheoryFormal Languages and Automata TheoryMultiagent Systems
The gist
The paper looks at games where a team tries to achieve goals while playing against an opponent, but the team members can only use their own random choices, not a shared one. The researchers find that for games where the team wants to reach a goal, it's tough (NP-complete) to decide if they can almost always win. For games focused on avoiding bad outcomes, this decision is easier (in P). They also link these findings to the difficulty of checking certain logical properties about such games.
Open → 2610.13569v1

Balance-aware tree routing improves large model expert use and communication

BRANCH-MoE: Balance-Aware Tree Routing for Large Embedding Models

Abstract: Mixture-of-experts (MoE) layers increase model capacity without a proportional increase in per-example computation. However, conventional flat routers can yield imbalanced expert utilization and treat experts as an unstructured collection, whose indices carry no topological meaning. We introduce {\bf BRANCH-MoE}, a routing architecture that places \(E\) experts at the leaves of a binary decision tree of depth \(\log_2 E\). At each internal node the branching probability is centered on the arrival-weighted mean score of the traffic reaching that node. This mean is estimated using an exponential moving average, which promotes utilization of both child subtrees without an auxiliary load-balancing loss. We show that this moving-average estimate admits an explicit noise-lag trade-off. We prove that for linear node maps and log-concave arrival distributions, this mechanism prevents routing-mass collapse. We further establish that, under a frozen router, an expert's execution frequency controls its stochastic-gradient convergence rate, and that confident decisions near the root bound cross-device communication when experts are assigned to devices by tree prefix. We evaluate BRANCH-MoE against Switch softmax, DeepSeek-V3 dynamic-bias, Skywork logit-normalized, and deterministic hash routing on Criteo click-through-rate prediction, Forest Covertype, HIGGS, and YearPredictionMSD, using \(E=16\), top-\(4\) routing, and five random seeds. Our results show that hierarchical routing can preserve task quality and balanced utilization while inducing a topology that supports localized expert co-activation and reduced communication.

Mon 5 OctMachine LearningArtificial Intelligence
The gist
Large machine learning models use multiple smaller parts called experts to handle different tasks. The authors found that common ways to decide which expert to use can overload some experts while underusing others. They designed a new method called BRANCH-MoE, which organizes experts in a tree and balances the usage by adjusting routing as data flows through the tree. Their approach keeps experts evenly busy, reduces cross-device communication, and works well on tasks like predicting clicks and other datasets.
Open → 2610.06725v1

Directed densest subgraph approximations made efficient with sparsification

Sparsification Framework for Directed Densest Subgraph

Abstract: We develop a new approach for computing approximate directed densest subgraphs (DDS). Our main result is a sparsification procedure that reduces a directed graph $G$ on $n$ vertices to a graph with $n \cdot \text{poly} \log n$ edges while preserving enough structure to recover an approximate DDS of $G$. Instantiating this framework in several memory-constrained settings, we obtain the following improvements over the state of the art: In semi-streaming, we obtain a single-pass algorithm that computes a $(1-\varepsilon)$-approximate DDS. Previously, the only semi-streaming algorithm that computed a constant approximation of DDS was by Bahmani, Kumar, and Vassilvitskii (2012), providing a $0.5-\varepsilon$ approximation in $O(\log n)$ passes. Hence, our work completely closes the approximation gap between undirected and directed DS in the semi-streaming setting, matching the $(1-\varepsilon)$-approximate undirected DS algorithm by Esfandiari, Hajiaghayi, and Woodruff (2016). In the near-linear-memory MPC regime, we obtain an $O(1)$-round algorithm for $(1-\varepsilon)$-approximate DDS, improving over the $O(\sqrt{\log n})$-round $(0.5-\varepsilon)$-approximation algorithm of Mitrović and Pan (2024). In the sublinear-time setting, we obtain an algorithm using $\tilde{O}(n)$ time, space, and oracle queries to compute a $(1-\varepsilon)$-approximate DDS, improving over the $\tilde{O}(n^{1.5})$ time, space, and query algorithm of Esfandiari, Hajiaghayi, and Woodruff (2016).

Thu 1 OctData Structures and Algorithms
The gist
Finding the densest subgraph in a directed graph is a way to identify tightly connected groups, but it is computationally challenging for big graphs. The authors present a new method to shrink the graph while keeping enough information to find nearly optimal densest subgraphs. This faster approach works well even when memory or time is limited, improving on older methods in single-pass streaming, parallel computing, and sublinear time algorithms. Their work helps close gaps between directed and undirected graphs in these settings.
Open → 2610.00846v1

Exact rates found for sharing and communicating correlated data

Exact Common Information and Exact Channel Synthesis for Correlated Discrete Sources

Abstract: In this paper, we provide a single-letter characterization of the exact common information for a pair of correlated discrete sources, as well as a single-letter characterization of the admissible region for the shared randomness rate and the communication rate in exact channel synthesis.

Mon 21 SeptInformation Theory
The gist
The paper identifies exact formulas to understand how two connected pieces of data share information and how much communication is needed to perfectly recreate one data source from the other. The authors focus on discrete sources, which are data points that come from specific categories or values. Their work provides a clear way to calculate the minimal amount of shared randomness and communication required. This helps in tasks where precise reproduction of data is important.
Open → 2609.24120v1