Large language model requests are increasingly answered by a hierarchy of machines: a small model on the phone, a larger one at a nearby edge server, and a strong "oracle" model in the cloud. A system that learns online where to send each request has a feedback problem. It only learns how good the cloud answer would have been if the request actually travelled to the cloud and the cloud's score made it back. Recent work handles this for strict layer-by-layer hierarchies. Real edge deployments differ in two ways. First, peers can hand requests sideways to each other, so the network is a mesh with cycles rather than a tree. Second, wireless links are lopsided: the strong uplink that carried a request to the cloud is often not matched by an equally reliable return path to a battery-limited device, and the link from node A to B can differ from B to A. A mesh offers many ways to reach the cloud, and lopsided links mean that reaching the cloud is not the same as hearing back from it.
We propose to treat "the probability that the learner observes the oracle's verdict" as a quantity defined on the network graph. It is computed exactly by solving a small linear system over the routing policy and the directional link reliabilities, and it is plugged into a variance-reduced bandit learner. The objective is not a weighted sum of accuracy and delay. It is a deadline-gated utility: an answer that arrives late is worth nothing, however accurate it is. The result is an online router that keeps its estimates unbiased on cyclic meshes with asymmetric links. Because a mesh has many paths to the cloud, it should also suffer far less of the "vanishing feedback" variance that cripples deep hierarchies.
Core Claim
Online Learning for Multi-Layer Hierarchical Inference under Partial and Policy-Dependent Feedback introduced VR-Ly-EXP4. That method is an expert-mixing contextual bandit (EXP4) combined with Lyapunov queues that enforce long-run bandwidth budgets. It divides observed loss by the product of per-layer offload probabilities, and it subtracts a task-type baseline first so the estimate does not blow up when that product falls below 0.02% at depth five. The authors explicitly leave two things open: lateral mesh routing, and any physical channel model beyond average bandwidth. Our claim is that both gaps are one problem.
The routing policy turns the network into a Markov chain in which requests are absorbed when answered. The correct importance weight is the probability that a request is absorbed at the oracle within the deadline, multiplied by the probability that the verdict survives the return link. Concretely, let $Q$ be the matrix of probabilities that the current policy forwards a request from one non-oracle node to another. Let $r$ be the vector of per-node probabilities of forwarding directly to the oracle, $H$ the hop budget implied by the deadline, and $\rho_i$ the success probability of the oracle-to-$i$ return path, which may differ from the forward path. The observation propensity for a request originating at node $i$ is then
$$\pi_i = \rho_i \, e_i^\top \sum_{h=0}^{H-1} Q^h r .$$
The loss estimate becomes $\hat\ell = b(\tau) + (\ell - b(\tau))\,\mathbf{1}[\text{observed}]/\pi_i$, where $b(\tau)$ is the task-conditioned baseline from VR-Ly-EXP4 and $\ell$ is the observed oracle loss. In a strict hierarchy with symmetric, lossless returns this reduces exactly to the layered product. On a mesh, $\pi_i$ sums over paths, so it is bounded below by the best single path rather than by the product along one chain. This is where we expect the variance gain. If the symmetric-link assumption is used instead, the learner implicitly sets $\rho_i$ equal to the forward reliability. The resulting bias then grows with the uplink/downlink gap, so ignoring asymmetry is not just suboptimal but systematically wrong.
Research Program
The work has three parts.
The first part is the estimator and its analysis. We derive an unbiasedness statement and a variance bound in terms of $\min_i \pi_i$. The key step is showing that on meshes this minimum depends on the number of node-disjoint deadline-feasible paths to the oracle rather than on depth.
The second part handles low-propensity devices with graph smoothing. Devices at the periphery with poor return links will still have tiny $\pi_i$. Rather than clipping, we borrow the device used by Graph-Preference Learning. That work showed that feedback sampled through a network over-represents central nodes, and it corrected this with a quadratic program whose graph-smoothness penalty prevents the variance explosion of naive inverse-degree weighting. We adapt the same idea to shrink low-propensity nodes' baselines toward their channel-graph neighbours. This is the closest analogue in the file. Their inclusion bias comes from social centrality on a static offline dataset; ours comes from channel position and is induced by the learner's own policy, online.
The third part is the deadline-gated objective. The utility is accuracy multiplied by an indicator that the answer is back before the deadline, minus resource cost. Bandwidth and energy remain Lyapunov constraints, as in VR-Ly-EXP4. The case for the non-linear gate comes from Zhou et al., who show that real preferences are not constant-ratio trade-offs, and from the digital-twin scheduling study. That study needed hard-deadline and capability-matching rewards across heterogeneous devices, and it names asymmetric channels as its open problem while evaluating only single-hop star topologies.
One constraint shapes the design. Adversarial Combinatorial Bandits with General Non-linear Reward Functions proves that a non-linear reward over subsets forces regret of order $\sqrt{N^K T}$, where $N$ is the number of items, $K$ the subset size, and $T$ the horizon. That rate arises because every combination must be treated as its own arm. We therefore do not put the non-linearity on combinatorial path choices. Instead, the learner mixes a finite set of routing experts (threshold policies per node), so regret scales with the logarithm of the number of experts. The non-linear gate lives inside each expert's evaluated loss.
Unimodal Thompson Sampling restricts exploration to a graph neighbourhood. Its known failure on scale-free graphs, where uneven node degrees create large variance, is a warning that local exploration rules will not save us on heavy-tailed meshes. We test exactly those topologies.
Baselines
The naive reference point is standard importance-weighted Ly-EXP4 without a task baseline, plus static threshold heuristics. VR-Ly-EXP4 reports that such static heuristics routed none of the difficult tasks to the oracle at depth five.
The strongest existing method is VR-Ly-EXP4 itself. The best number on record for it in the file is that it "successfully routed ~44% of difficult tasks to the oracle" in a 5-layer hierarchy, and that it achieved the lowest inference error at depths 3 to 5. No reported numerical error values were found on Lacuna for VR-Ly-EXP4. To apply it on a mesh, it must see a tree, so we run it on the shortest-path spanning tree to the oracle with the symmetric (forward-equals-return) propensity.
A third baseline is a permutation-equivariant graph neural network policy trained offline by primal-dual updates, following the free-space-optical fronthaul allocator. That method handles arbitrary node labelings, but it optimizes weighted sum-capacity with full-information training. It tests whether learning a topology-aware policy offline makes online propensity correction unnecessary.
All methods share the same expert set, the same Lyapunov bandwidth budget (40% average, matching VR-Ly-EXP4), the same request stream and seeds, and an equal hyperparameter search budget.
Two ablations isolate the key ingredients. The first keeps the mesh path-sum propensity but removes the return-link factor $\rho_i$. The second keeps $\rho_i$ but forbids lateral moves.
Beating VR-Ly-EXP4 means higher deadline-gated utility and a higher oracle hit rate on difficult tasks at equal bandwidth on asymmetric meshes. It also means not losing on the layered symmetric setting, where the two methods should coincide.
Why not just…?
Why not just run VR-Ly-EXP4 on a spanning tree of the mesh? This is the main threat. If lateral paths rarely raise propensity, the tree version captures almost everything. Our first ablation answers it directly. We sweep topology from layered to Watts-Strogatz to Barabási-Albert and report the gap as a function of the number of disjoint deadline-feasible paths. If the gap stays small at realistic path counts, the mesh contribution is weak, and we would report the return-link correction as the main result.
Why not just symmetrize the channels, using average or worst-case link quality? The information-theory side of the file shows that symmetric approximations loosen bounds and mislead strategy design when gains differ. Function-alignment converse results and half-duplex relaying analysis are two examples. For a learner the damage is concrete: a mis-specified $\rho$ biases the loss estimates. We measure this bias against simulator ground truth while sweeping the uplink/downlink gap. Under worst-case symmetrization the bias should become conservatism rather than error, so we compare on utility as well as bias.
Why not just reserve a fixed slice of traffic to send directly to the oracle? Forced exploration gives a propensity bounded away from zero by construction, and it is a strong, simple competitor. It falls short when direct paths are expensive or unreliable for peripheral devices, and it spends bandwidth uniformly rather than where routes are cheap. We test it at matched total bandwidth, with the exploration rate tuned on held-out streams.
Why not just use a weighted sum of accuracy and latency, or put deadlines in a Lyapunov queue? A deadline-violation queue enforces an average violation rate, not per-request worthlessness, so it can trade many late correct answers for on-time wrong ones. We run both formulations and report per-request deadline satisfaction alongside average utility.
Proposed Experiments
The workload is the combined RouterBench/VL-RouterBench stream used by VR-Ly-EXP4: nearly 80,000 jobs across 114 task types served by 23 open-source models, with the benchmark itself described in RouterBench. Model placement on nodes follows that paper's greedy memory-constrained allocation.
Topologies are layered hierarchies at $L\in\{3,4,5\}$, which reproduce the original setting, and meshes generated as stochastic block, Barabási-Albert, and Watts-Strogatz graphs at 20 to 100 nodes, as in Graph-Preference Learning. Each directed link gets independent forward and return outage probabilities, with a controllable asymmetry ratio.
Metrics are deadline-gated utility, oracle hit rate on difficult tasks, empirical variance and bias of the loss estimator against simulator ground truth, regret against the best expert in hindsight, and bandwidth violation.
Two checks decide whether the idea holds. The first is a sanity test: on layered symmetric topologies our method must match VR-Ly-EXP4 to within seed noise, because the estimator reduces to theirs. The second is the core test. As return-link asymmetry grows, the symmetric-propensity baseline's estimator bias should grow roughly in proportion to the gap between assumed and true $\rho$, and its utility should fall, while ours stays flat. If the bias does not appear, the channel-asymmetry part of the claim is wrong.
A third check tests the variance prediction. Estimator variance, plotted against the number of disjoint feasible paths, should fall on meshes and stay at depth-driven levels on trees. Barabási-Albert graphs, where neighbourhood-local methods are known to struggle, are the stress case.
References
- Online Learning for Multi-Layer Hierarchical Inference under Partial and Policy-Dependent Feedback
- Graph-Preference Learning: Debiasing Network-Sampled Human Feedback for Target Welfare Estimation
- Beyond One-Preference-Fits-All Alignment: Multi-Objective Direct Preference Optimization
- Digital Twin-Driven Collaborative Scheduling for Heterogeneous Task and Edge-End Resource via Multi-Agent Deep Reinforcement Learning
- Adversarial Combinatorial Bandits with General Non-linear Reward Functions
- Unimodal Thompson Sampling for Graph-Structured Arms
- Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul Networks
- Computation in multicast networks: Function alignment and converse theorems
- When Are Dynamic Relaying Strategies Necessary in Half-Duplex Wireless Networks?
- MARS: A Benchmark for Multi-LLM Algorithmic Routing System