1 Introduction↩︎

Federated learning (FL) for LLM-based agents has largely inherited its unit of collaboration from classical settings, and that inheritance is beginning to show its limits in the heterogeneous, frozen-LLM regimes this paper studies. The setting where this matters most is federated tool-routing: collaborative tool selection across organizations running frozen, possibly heterogeneous LLMs under four joint constraints that no prior federated paradigm satisfies simultaneously. Clients cannot share weights or gradients (frozen LLMs); cannot pool raw data (no central corpus); may run different LLM families, so the unit cannot be architecture-specific (model-agnostic clients); and must protect tool-usage patterns and not only raw data, since metadata alone re-identifies individuals [1], [2] and repeated routing exposes case-mix and behavioral patterns that regulated deployments treat as protected [3], [4].

Current federated methods exchange model parameters [5]–[7], adapters (FedLoRA), prompts [8], raw examples [9], split activations [10], or distilled ensembles [11]. Parameter and adapter sharing is communication-heavy (\({\sim}50\) MB/client/round for FedLoRA r16-fp16, lower bound), tightly couples architectures, and is privacy-leaky: gradient inversion [12], [13] and membership inference [14] reconstruct training data from shared updates. Raw-example sharing exposes local behavior and reaches only \(0.61\) on 4-tool routing versus \(0.86\) for Prompt-sharing flattens to a single string and cannot reliably aggregate negative constraints (e.g.”do not use tool \(X\) when condition \(Y\)“) across clients, since text concatenation does not resolve which client’s exclusion rule wins for overlapping conditions, and prompt-extraction attacks [15]–[17] make these leaks operational rather than theoretical. Clinical [3], [4], [18] and financial [19]–[21] consortia have established federated precedents in exactly this regulated-domain setting, but those precedents inherit the same wrong-unit problem. The shared structural cause is that flat units carry no type signature at the federation boundary on which schema-aware aggregation, validation, or per-field privacy can dispatch as well-defined operations.

The right unit is not flat—it is a typed federated artifact: an object \(C\) defined by a schema \(\mathcal{S}\) that gives every field a declared role, type, and validation rule. Typed schemas and structured records are mature ideas in databases and distributed systems, and prior federated systems may use them internally; that is not the distinction. The distinction is whether the exchanged unit carries a type signature on which the federation protocol can dispatch privacy, merging, and transfer as well-defined operations—and no existing federated unit does. Promoting a typed artifact to the role of exchanged unit makes three previously ill-defined operations well-posed: per-field differential privacy, because sensitivity bounds are schema-declared rather than estimated post-hoc; conflict resolution, because contradictory client contributions are resolvable by field-wise dispatch rather than majority vote over opaque strings; and cross-architectural transfer, because the artifact is interpreted at inference rather than baked into parameters. None of these is available when the federated unit is opaque text or vectors—not because those representations lack internal structure, but because they carry no type signature at the boundary on which the aggregation protocol can dispatch.

We instantiate this abstraction as SYNAPSE, a compendium for federated tool routing, and make four contributions: the typed federated artifact abstraction (§3), instantiated as a compendium \(C\!=\!(M,U,P,T,A)\) with schema \(\mathcal{S}\) that enables per-field dispatch of privacy, merging, and validation at the federation boundary; a typed merge operator (Def. 1, Algorithm 2) with field-wise conflict resolution, conflict logging, and schema validation across a client–edge–server hierarchy; artifact-level guarantees (§4) comprising a formal \((\varepsilon,0)\)-DP guarantee on numeric metadata (Theorem 1) and two conditional results on retrieval distortion and routing stability empirically characterized on five distributions, including a LiveBench subset where the contraction premise fails (\(\hat{L}_{\mathcal{R}}^{(99\%)}\!=\!1.018\!>\!1\); Tab. 9), disclosed as a limitation rather than suppressed; and a comprehensive empirical evaluation (§5) showing \(0.92\!\pm\!0.02\) routing accuracy on GSM8k, statistically indistinguishable from centralized routing (\(p\!=\!0.31\), \(5\) seeds) at \(5.3\) KB per client per round (\({\sim}10{,}000\times\) below the FedLoRA r16-fp16 architectural lower bound), \({\approx}2\)-pt cross-model loss across four LLM families, \(0.71\) at \(8\)-step tool chains versus \(0.34\) for prompt-sharing, and generalization to NQ-Open retrieval-policy artifacts (App. 18.2), confirming the abstraction extends beyond tool routing.

2 Related Work↩︎

Federated learning for LLMs. OpenFedLLM [22] and FederatedScope-LLM [6] address communication and heterogeneity in LLM training. FedbiOT [23] and FFA-LoRA [24] target privacy under DP. These all aggregate model parameters or adapters, requiring architectural compatibility and incurring substantial communication.
Federated retrieval-augmented generation. GPT-FedRec [25], FedE4RAG [26], FRAG [27], and C-FedRAG [28] federate retrieval indices via raw examples or encrypted shares. They lack tool-aware structure: routing operates over unstructured retrieved chunks rather than typed routing [29]. We compare directly to C-FedRAG in §5.
Text-centric federation. FedTextGrad [8] federates optimized prompts; Fed-ICL [9] federates exemplars. Both treat the federated unit as flat text without typed structure.
Tool-augmented LLMs. Toolformer [30], ReAct [31], Gorilla [32], ToolLLM [33], and Graph RAG-Tool Fusion [34] use schemas and retrieval to select tools, but in centralized settings without federation.
Privacy. DP foundations [35], [36] and prompt-extraction attacks [15]–[17], [37] formalize the leakage we defend against on the numeric and text paths respectively.
Federated routing and large-scale tool benchmarks. Concurrent work [38] federates model-selection routers (which LLM to call); their unit is router parameters, ours is a typed artifact, and the routing problem is tool-selection rather than model-selection. The two settings are complementary. LiveMCPBench [39] (\(527\) tools, \(70\) MCP servers) and InfoMosaic-Bench [40] (\(621\) tasks, \(77\) MCP tools) characterize the scale at which production tool-routing must operate; extending typed-compendium federation to LiveMCPBench-class catalogs is direct future work (App. 17.1).
SYNAPSE differs from prior work along an orthogonal axis: the type signature of the exchanged object: Weights, adapters, prompts, and raw examples are all untyped from the federation’s perspective. The compendium is typed at every field, which is what enables artifact-level \((\varepsilon, 0)\)-DP, schema-constrained merge, and cross-model transfer to be well-defined operations rather than approximations (Tab. 1).

2pt

3 The Compendium and the Typed Merge Operator↩︎

This section gives a precise definition of the compendium artifact and the typed merge operator that aggregates compendiums across a client–edge–server hierarchy (Fig. 1). We open with the formal definition because the rest of the framework – privacy mechanisms, conflict resolution, cross-model transfer, the formal guarantees in §4 are all dispatch on the schema introduced here.

Numeric sensitivity bounds in \(M\) enable \((\varepsilon, 0)\)-DP (Theorem 1); typed separation of \(U\) and \(P\) enables conflict-log handling (Algorithm 2); \(T\) indexed by \((\mathrm{tool}, \mathrm{signature})\) enables model-agnostic transfer; schema validation enables static rejection of malformed adversarial contributions. Each round, clients update locally; edges merge \(\{C_k^{(r)}\}_{k \in E}\!\to\!C_E^{(r)}\); the server merges \(\{C_E^{(r)}\}\!\to\!C_g^{(r)}\), redistributed. Merges are typed dispatches:

Conflict resolution. Conflicting scenarios for a single tool create a cosine cluster (\(\cos\!\geq\!\tau{=}0.85\)); \(\mathrm{IsConsistent}\) verifies schema-level structured-field agreement along with a consistency probe from an LLM (App. [app:merge95full]). In clusters where inconsistencies are found, the centroid is kept, while dissenting elements are logged in the conflict record \(\mathcal{L}^{(r)}\), which informs the next-round Precautions through \(\mathrm{ConflictsToPrecautions}\) (e.g., “Use Wolfram for symbolic integration” + “Avoid when depth \(>\!4\)” \(\to\) “Use for symbolic integration; do not use when depth \(>\!4\)”). (§5: accuracy holds at \(0.86\) even when \(40\%\) of client scenarios contradict each other, versus \(0.74\) without conflict logging). The server applies the same merge operator one level up, treating edge compendiums as its inputs.
Privacy mechanisms.Two mechanisms with different guarantees: numeric fields in \(M\) receive formal \((\varepsilon,0)\)-DP protection via Laplace noise calibrated to each field’s declared sensitivity (Theorem 1); text fields are protected by adaptive masking that suppresses high-salience tokens, an empirical defence with no formal DP guarantee (Tab. 4). Secure aggregation [41] can be layered on top of either mechanism independently.
Inference-time routing. Given a query \(q\), the system first retrieves the five most similar scenarios from the global compendium \(C_g\) using cosine similarity over Jina embeddings [42]. A lightweight LLM reranker (llama-3.1-8b-instruct [43]) then selects the single best match and identifies its parent tool, which the planner invokes. Retrieval-augmented generation within a tool operates independently of this routing step and does not affect which tool is selected.

3.1 TextGrad and the Federated Training Loop↩︎

TextGrad [44] treats natural-language prompts as differentiable variables, optimizing them via LLM-produced critiques (textual gradients) describing how a prompt should change to improve a downstream loss. Within SYNAPSE, TextGrad operates on three compendium fields (\(U\), \(P\), \(T\)) at the edge layer only and never at clients (which would expose private data to the optimizer’s LLM) and never at the server (which would centralize cost). Tool metadata \(M\) is canonical and bypasses TextGrad entirely.
Per-round update. At each round, the edge takes each cluster of similar scenarios produced by Algorithm 2 and drafts a single summary. It then tests that summary against a small held-out set of public benchmark queries, never client data, and measures how often routing fails. An LLM critique describes what the summary should change to reduce those failures, and the summary is revised over \(S{=}3\) steps. Before any text leaves a client, high-salience tokens are masked under a tunable masking strength \(\lambda\): higher \(\lambda\) suppresses more tokens for stronger empirical privacy at some cost to routing accuracy, while lower \(\lambda\) preserves more content (Tab. 5); the edge LLM therefore never sees raw client scenarios. This refinement runs separately for usage scenarios \(U\), precautions \(P\), and prompt templates \(T\). Scenarios that caused conflicts in the current round are not discarded: they are carried forward as structured precautions in the next round’s compendium \(C_E^{(r+1)}.P\), giving the system a form of memory across rounds without any retraining.
Per-field loss for \(U\), \(P\), \(T\). The TextGrad loss differs by field and by what each field controls. For usage scenarios \(U\) and precautions \(P\), both of which influence the routing decision, \(\ell\) is the routing-failure rate on the held-out probe set. For prompt templates \(T\), which control post-routing API formatting after the tool is already selected, routing-failure is not the appropriate loss; we use task-success-given-correct-routing (the fraction of probe queries that produce a valid downstream API response when routed to the correct tool with template \(u_t^{(s)}\)). Using routing-failure for \(T\) would not provide a useful gradient signal because \(T\) does not influence which tool is selected.

Hence TextGrad is not a global optimization over the full compendium, not a meta-learner, not a substitute for the typed merge operator: merge enforces schema validity and field-wise dispatch, TextGrad refines natural-language content within each typed field. Removing TextGrad and using extractive summarization drops routing accuracy \(0.92\!\to\!0.85\) (Tab. [tab:textgrad95main]); removing merge while keeping TextGrad collapses to \(0.74\) at \(40\%\) contradictory clients (Tab. [tab:component95ablation]). Edge cost: \(\sim\!60\) s/round/aggregator on server, amortized across the edge’s clients.

4 Analytical Properties↩︎

We give three analytical statements: a formal DP guarantee on numeric metadata, and two conditional results (retrieval-distortion under Lipschitz assumption, routing stability under contraction) characterized empirically rather than proved (Tab. 19). These are positioning rather than central contributions.

Scope. Theorem 1 covers the numeric path. The text-field mechanism is heuristic; we do not claim it satisfies formal DP.

Adjacency and trust model. “Single user’s numeric metadata contribution” means user-level adjacency: \(D, D'\) differ in the entire numeric record contributed by one user. The guarantee is enforced in two stages: (i) per-user clipping at the client bounds the user’s \(\ell_1\) contribution at \(\Delta_m\) per field before any client-level aggregation (App. [app:merge95full], stage 1); (ii) clients transmit clipped values to the edge aggregator, which computes the per-field average over \(K\) clients and adds Laplace noise calibrated to the average’s sensitivity \(\Delta_m/K\), releasing \(C_E.M.m^{(j)} \leftarrow \frac{1}{K}\sum_k \mathrm{clip}(\cdot) + \mathrm{Lap}(\Delta_m^{(j)}/(K\varepsilon^{(j)}))\). The edge is semi-honest – it follows Algorithm 2 faithfully but may attempt inference from clipped client values; secure aggregation [45] can be layered on the numeric path to weaken this assumption to ideal-functionality only. Downstream typed-merge operations on the noised release (clustering, redistribution) are post-processing (App. 19, Lemma L.2), so the user-level guarantee carries through unchanged across rounds.

Empirical characterization (not a theorem). The Lipschitz assumption above is a statement about the embedding model rather than about SYNAPSE, and we make no formal claim that the Jina embedding satisfies it globally. We measure the per-sample ratio \(\|e(u) - e(\tilde{u})\|_2 / d_\mathrm{text}(u, \tilde{u})\) on \(1{,}000\) scenario pairs at three masking strengths \(\lambda \in \{0.5, 1.0, 1.5\}\). We define \(d_\mathrm{text}(u, u')\) as token-level Levenshtein distance after lowercasing and whitespace normalization, divided by \(\max(|u|, |u'|)\) tokens to give a bounded \([0, 1]\) ratio (full protocol App. 19). The \(99\%\)-quantile is \(\hat{L}_e^{(99\%)} \approx 1.4\) with variation under \(5\%\) across \(\lambda\) values; the resulting \(\hat{\delta}_\mathrm{priv}\) at \(\lambda{=}1.0\) is \(\approx 0.37\), small relative to typical inter-scenario distances (\(\sim\!1.0\)–\(1.4\)). This is an empirical observation about the deployed embedding model, not a proof that Theorem 2’s assumption holds. A user using a different embedding model should re-measure \(\hat{L}_e\) before relying on the conditional bound.

5 Experiments and Analysis↩︎

We evaluate SYNAPSE in two regimes: a controlled regime designed to verify mechanism via proxy benchmarks, ablations, and theory-grounded measurements, and a realistic regime designed to test routing behavior on real APIs and long-horizon tool chains.

Setup. Proxy: GSM8k [46] and BBH [47]-derived tasks; tool labels correspond to routed solution paths. Real: 4 tool families (MathQA, SearchQA, CodeExec, LogicQA) and 6 ToolBench APIs (SerpAPI, OpenWeatherMap, Wikipedia, Wolfram, REST Countries, GCal). IID partitions sample uniformly; non-IID partitions shard by numeric answer range or question characteristics. Training: batch 3, 3 local steps/round, \(K{=}5\) retrieval. Full hyperparameters in App. 20.

Baselines. Two families: (i) federated text-sharing – Fed-ICL [9] (examples) and FederatedTextGrad [8] (prompts) – both frozen-LLM and weight-free; (ii) routing/retrieval ablations – BM25 [48], Centralized-Retrieval-Only, Static-Global, Local-Only, Unstructured-Pool, Description-Only. Centralized-SYNAPSE, the same typed compendium built without federation, serves as the centralized typed-registry analog (cf.MCP-style registries [49]) and isolates the federation cost from the typed-schema contribution. Adapter-based and federated RAG – FedLoRA, C-FedRAG [28] – are extended baselines; FedAvg full-fp32 is reported only as a communication-cost reference.

5.1 Controlled-regime results↩︎

Statistical significance. SYNAPSE matches centralized performance within statistical noise while every baseline falls significantly short. Across 5 random seeds \(\{42, 123, 456, 789, 1024\}\), SYNAPSE achieves \(0.92\!\pm\!0.02\) on GSM8k (5 IID clients), statistically indistinguishable from Centralized-SYNAPSE (\(p\!=\!0.31\), \(d\!=\!0.2\)), while all non-centralized baselines differ at \(p\!<\!0.05\) (full table App. 20): FedTextGrad \(0.90\), BM25 \(0.83\), Fed-ICL \(0.79\), ReAct \(0.64\), Local-Only \(0.46\).
Component and TextGrad ablations. Every typed schema field contributes measurable, monotonic accuracy gains, and the conflict log is critical under adversarial conditions. Stacking BM25 \(\to\) full SYNAPSE (Tab. [tab:component95ablation], left): \(+0.16\) semantic retrieval, \(+0.06\) schema, \(+0.10\) scenarios, reaching \(0.92\) (\(0.08\) from oracle);retrieval and reranking contribute equally (\(+0.16\) each). Injecting contradictory scenarios (Tab. [tab:component95ablation], right): the conflict log opens a \(12\)-pt protection gap at \(40\%\) rate, confirming that field-wise conflict resolution is not cosmetic. Replacing TextGrad (\(S{=}3\)) at the edge with extractive centroid drops accuracy \(0.92\!\to\!0.85\);with no summarization, \(0.92\!\to\!0.78\) (Tab. [tab:textgrad95main]); full sweep over \(S\!\in\!\{1,3,5\}\) in App. 14.

4pt

Heterogeneity and scalability. SYNAPSE degrades gracefully under distribution shift and scales to \(500\) clients with bounded compendium size and sub-\(500\) ms latency (Tab. 15, App. 20). Under non-IID splits, GSM8k drops only \(0.96\!\to\!0.92\) and BBH benchmarks drop \(\leq\!2\) pts; deduplication saturates at \(70\%\) and \(p_{95}\) stays under \(500\) ms regardless of client count because reranking always processes only the top-\(5\) candidates.

Cross-model transfer. A single compendium built with LLaMA-3.1-8B routes correctly across four LLM families on GSM8k – LLaMA-3.1-8B (\(0.92\), native), LLaMA-3.2-3B (\(0.90\)), Mistral-7B (\(0.91\)), GPT-4o (\(0.92\)) – and a mixed federation (2\(\times\)LLaMA + 2\(\times\)Mistral + 1\(\times\)GPT-4o) reaches \(0.92\) overall. The same property replicates on \(\tau\)-bench retail with the round-3 compendium and embedding model held fixed (Tab. 2): same-family transfer to LLaMA-3.2-3B yields \(\Delta\!=\!-0.022\) (matching the GSM8k same-family gap exactly), cross-family Mistral-7B yields \(\Delta\!=\!-0.009\), and stronger-model GPT-4o yields \(\Delta\!=\!+0.085\) – the typed compendium rides a stronger model upward, reaching \({\sim}90\%\) of \(\tau\)-bench’s published GPT-4o ceiling. All four LLMs preserve the per-category ordering (catalog \(>\) account \(>\) escalation \(>\) orders \(>\) returns), confirming that compendium quality rather than LLM-specific category preference drives the result.Weight-sharing federation cannot offer this: merged adapters or parameters need architectural compatibility and re-baking for each target LLM.

6pt

Benchmark breadth and prompt transfer. The federation cost is task-dependent: modest on structured mathematical reasoning, larger on open-ended language tasks where scenario diversity is hardest to compress. On four LiveBench [50] reasoning tasks, federated underperforms centralized by \(7\)–\(13\) pts on three open-domain reasoning tasks but outperforms by \(4\) pts on AMPS Hard (App. 18); both configurations use GPT-4o, so the gap reflects compendium compression rather than model mismatch. Prompt transfer (LLaMA-3.2-11B \(\to\) 3.2-3B) yields task-dependent \(+0.15\)/\(+0.03\)/\(-0.08\) across BBH-Arithmetic/OC/GSM8k, confirming it is a distinct and non-interchangeable mechanism from compendium transfer (App. 18, Tab. [tab:prompt95transfer]).

Latency and ablation summary. Routing latency stays within production-viable bounds and the LLM reranker is the single highest-value component. End-to-end \(p_{50}/p_{95}\!=\!330/470\) ms; replacing the Llama-3.1-8B edge summarizer with Llama-3.2-3B incurs only \(0.01\) accuracy cost (\(0.91\!\pm\!0.02\)). A logged \(500\)-query GSM8k run isolates four mechanisms: the reranker is the largest single contributor (bypass drops \(0.917\!\to\!0.497\), \(\Delta\!=\!0.42\!\pm\!0.05\), \(3\) seeds; App. 15); federation provides coverage (Local-Only \(0.46\), \(\sim\!54\%\) of queries require scenarios unseen locally); schema validation stabilises at \(6\) types with \(95.2\%\) deduplication; Fed-ICL’s string-proximity matching explains its \(0.61\) vs.\(0.86\) collapse on multi-tool.

5.2 Realistic-regime results↩︎

Multi-tool and real APIs. On real APIs, SYNAPSE substantially outperforms text-sharing baselines and remains within sampling noise of the centralized ceiling across all six API categories. On the \(4\)-tool proxy, SYNAPSE reaches \(0.86\) vs.Fed-ICL \(0.61\) (\(+0.25\)) and Centralized \(0.91\) (gap \(0.05\)). On the ToolBench \(250\)-query test set (App. 16, Tab. [tab:real95api95results]): \(0.728\) vs.\(0.800\) vs.\(0.480\); \(95\%\) bootstrap CIs (Tab. 12) show SYNAPSE–Centralized intervals overlap per category while SYNAPSE–Fed-ICL intervals are disjoint at \(n\!=\!250\) overall. The \(0.148\) gap between routing accuracy (\(0.728\)) and end-to-end success (\(0.580\)) is entirely upstream-API failure (schema drift \(5.2\%\), semantic miss \(4.8\%\), auth/quota \(2.4\%\), timeouts \(1.6\%\), rate limits \(0.8\%\)); routing errors account for \(27.2\%\).

Long-horizon multi-step routing. The typed Precautions field is the decisive advantage over multi-step horizons: Fed-ICL collapses to \(0.34\) at \(8\) steps vs.SYNAPSE’s \(0.71\)—a \(37\)-pt gap that grows with chain length because flat-text baselines lack structured exclusion rules (Tab. [tab:multistep]). SYNAPSE matches Reflexion-\(K{=}3\) statistically at \(1/3\) the inference compute, confirming routing memory and routing planning are complementary mechanisms.

Extended baselines. SYNAPSE outperforms all extended baselines without architectural compatibility or weight sharing. On \(5\)-seed GSM8k: SYNAPSE \(0.92\), FedLoRA \(0.89\), C-FedRAG \(0.84\), Fed-ICL \(0.79\)—at \(5.3\) KB vs.\({\sim}52\) MB/client/round for FedLoRA (\({\sim}10{,}000\times\) gap against the architectural lower bound; App. 17).SYNAPSE tolerates up to \(40\%\) adversarial clients (Fig 3) across three attack modes (cross-source, random corruption, tool-confusion) before sharp degradation at \(60\%\); the boundary aligns with Theorem 3’s empirically measured contraction regime

Long-horizon simulation (illustrative stress-test). At deployment scale, the typed-artifact protocol sustains effective routing over \(30\) rounds, recovers from API schema drift, and generates measurable cross-org transfer gains. Across \(100\) clients, \(5\) orgs, \(32\) APIs, and \(\sim\!21\text{k}\) queries (App. 22): routing reaches \(0.79\) at \(R{=}30\); end-to-end success \(0.67\); the \(96\) KB compendium recovers to within \(0.02\) of pre-drift baseline by \(T{+}10\) after each of \(8\) scheduled drift events; and cross-org federation yields \(\Delta\!=\!{+}0.10\) over within-org federation under category-coherent partitioning and \(\Delta\!=\!{+}0.07\) under random partitioning.At \((\varepsilon{=}0.5, \lambda{=}1.5)\), adversary AUROC drops to chance (\(0.50\)) at a cost of \(5\) routing accuracy pts with \(\varepsilon'\!=\!1.5\) over three rounds; the full privacy–utility sweep is in App. 10, Tab. 5.

5.3 Beyond tool routing: typed retrieval-policy artifacts on NQ-Open↩︎

The typed-artifact abstraction generalizes beyond tool routing with no algorithmic changes: the same merge operator, schema validation, and DP guarantees transfer directly to retrieval-policy federation on NQ-Open, closing \(73\%\) of the local-to-centralized accuracy gap. We instantiate the protocol on Natural Questions Open [51] with hybrid retrieval (BM25 + dense, top-\(k\!=\!5\) Wikipedia passages) and llama-3.1-8b answer generation. \(5{,}000\) NQ-Open dev questions are partitioned across \(5\) non-IID clients by question type; clients exchange typed retrieval-policy artifacts (, , , , ) rather than tool-routing scenarios; Algorithm 2 and Theorem 1 apply unchanged. Full setup in App. 18.2.

8pt

The federation–centralized gap of \(0.032\) on NQ-Open is tighter than the \(0.058\) on \(\tau\)-bench retail, consistent with single-step retrieval policies composing more cleanly under typed merge than multi-turn tool decisions where each step compounds routing uncertainty.

6 Limitations↩︎

Three limitations bound the deployment case. First, formal privacy covers only numeric metadata; text fields rely on heuristic masking with no \((\varepsilon,\delta)\)-LDP guarantee. Second, typed schemas concentrate liability, a malformed or adversarially crafted schema becomes a single point of failure under adaptive adversaries beyond the \(50\%\) Byzantine threshold. Third, the system emits no calibrated confidence score, requiring human-review escalation before high-stakes medical or legal decisions. Additionally, contraction fails on a LiveBench subset (\(\hat{L}_\mathcal{R}^{(99\%)}\!=\!1.018\!>\!1\)), leaving routing stability unverified on that distribution.

7 Conclusion↩︎

Typed federated artifacts enable model-agnostic collaboration without sharing weights, prompts, or raw data, making privacy, conflict resolution, and cross-architectural transfer well-defined operations at the federation boundary. SYNAPSE matches centralized performance at \({\sim}10{,}000\times\) below the FedLoRA bandwidth floor (App. 8).

8 Ethical Considerations↩︎

SYNAPSE is evaluated on tool-routing and NQ-Open retrieval-policy artifacts; the protocol extends to other typed-object settings via schema substitution. Three empirical gaps bound the current results: real-API experiments are limited in scale and duration; LiveMCPBench-class catalogs (\({\sim}500\) tools) are not directly evaluated; and the contraction premise fails on a LiveBench subset (\(\hat{L}_\mathcal{R}^{(99\%)}\!=\!1.018\!>\!1\)), voiding the routing-stability guarantee on that distribution. Three deployment prerequisites remain open before any regulated rollout: (i) calibrated \(\varepsilon\)-LDP for text fields (current masking is heuristic with no formal guarantee); (ii) confidence-gated escalation to human review for low-confidence routing decisions; (iii) a right-to-erasure re-materialization pathway (structurally supported by Algorithm 2 but not implemented). Sybil attacks past the \(40\%\) Byzantine tolerance threshold and adaptive adversaries tuned to the robust operator remain future work; rate-limited registration and cross-edge consistency checks are compatible mitigations but are not yet evaluated. SYNAPSE is not a HIPAA/GDPR-complete stack; the schema \(\mathcal{S}\) provides the dispatch points for each extension but does not fulfil them.

9 Robustness to Noisy and Adversarial Clients↩︎

SYNAPSE is evaluated against three adversarial modes: cross-source contamination (clients inject scenarios from unrelated domains), random scenario corruption (random text replacement), and tool-confusion attacks (deliberate parent_tool_name mislabeling). Headline curves (Fig. 3 in §5.2): all three modes stable through \(40\%\) adversarial clients, sharp collapse at \(60\%\). Random noise is largely absorbed by cosine deduplication; cross-source is partially absorbed by schema validation; tool-confusion is hardest because adversaries produce schema-valid scenarios whose only error is the parent_tool_name field, which clusters with honest scenarios for the same task type. Mitigation: cross-validating clustered parent_tool_name fields against the canonical tool registry \(\mathcal{T}\) at Algorithm 2 line 5 before line 12 – already in released code; without it, tool-confusion at \(40\%\) collapses to \(0.48\) rather than \(0.62\). The \(40\%\) stable boundary aligns with Theorem 3’s empirically measured contraction regime (\(\hat{L}_\mathcal{R}^{(99\%)}\!=\!0.891\), \(\hat{\Delta}^{(5\%)}\!=\!0.138\), App. 19); at \(60\%\) the contraction premise fails empirically.

10 Empirical Prompt-Extraction Attack↩︎

Setup. Following [37]: clients generate responses to server queries using private in-context examples; GPT-4o adversary observes only the responses and reconstructs originals. We report membership-inference AUROC (50/50 balanced), adversary–ground-truth token overlap, and the fraction of clients whose token overlap stays under \(0.10\). Full pipeline = formal DP on numeric metadata + heuristic masking on text; this characterizes empirical privacy of the deployed system, distinct from the formal \((\varepsilon, 0)\)-DP claim of Theorem 1 which applies only to the numeric-metadata mechanism.

4pt

Privacy–utility frontier. To characterize the deployment-relevant operating range rather than a single point, Tab. 5 sweeps the per-round privacy budget \(\varepsilon \in \{0.5, 1.0, 2.0\}\) and the text-masking strength \(\lambda \in \{0.5, 1.0, 1.5\}\). Composed \(\varepsilon'\) uses basic sequential composition \(\varepsilon' = R\varepsilon\) (pure \((\varepsilon', 0)\)-DP); for the small-\(R\) regime (\(R{=}3\)) evaluated here, basic composition is strictly tighter than the advanced composition bound and is what we report.

6pt

11 Planner-Based Agent Baselines: ReWOO and Reflexion↩︎

This appendix documents the comparison protocol for the two planner-based agents in Tab. [tab:multistep]. The motivation is to disentangle two confounded effects: routing-as-memory (SYNAPSE, where the federated compendium provides typed knowledge that the router queries) versus routing-as-planning (ReWOO, Reflexion, where a centralized planner LLM decomposes the task and selects tools without relying on shared memory).

Setup. Both planner-based agents use Llama-3.1-8B-instruct (matching our reranker LLM) for all LLM components, share the per-tool execution wrappers used by SYNAPSE, and operate centralized – they have full access to the \(32\)-tool inventory and benchmark distribution at inference time, a strictly more permissive setting than SYNAPSE’s federated regime. ReWOO [52] uses the standard planner prompt (decompose-then-execute); Reflexion [53] uses \(K{=}3\) trials with verbal-feedback memory. We score multi-step chains as successful only if a single trial completes all steps; we do not cherry-pick best-of-trials across steps, which makes Tab. [tab:multistep]’s entries directly comparable to single-trial methods. Neither planner can be straightforwardly federated without sharing either the planner prompts (which contain the full tool inventory) or the episodic-reflection buffer (which contains private query traces). SYNAPSE’s claim is not that compendium-based routing beats centralized planners in absolute terms; it is that routing memory and routing planning are different mechanisms, and SYNAPSE approaches centralized planner performance under constraints planner-based agents architecturally cannot satisfy.

Results and compute cost. ReWOO single-step (\(0.89\)) sits within \(0.01\) of SYNAPSE (\(0.88\)). ReWOO’s \(12\)-step accuracy (\(0.46\)) sits \(0.19\) below SYNAPSE (\(0.65\)): without replanning, intermediate failures geometrically compound. Reflexion (\(K{=}3\)) leads single-step at \(0.93\) but drops below SYNAPSE at \(12\)-step (\(0.64\) vs.\(0.65\)). Reflexion’s competitiveness costs up to \(3\times\) per-step compute and \(36\times\) total per chain (Tab. 6); SYNAPSE’s per-step cost is independent of chain length.

6pt

12 Byzantine-Robust Aggregation: Empirical Evaluation↩︎

The main paper’s threat model is honest-but-curious. This appendix extends to a Byzantine setting where adversaries submit schema-valid payloads designed to maximize misrouting harm.

Setup. Adversarial fraction is measured over submitted compendium entries (not clients), permitting fractional rates with \(5\) clients. Two attack modes: schema-valid poisoning (entries pass schema validation but contain wrong tool\(\to\)scenario mappings, defeating schema validation by construction) and coordinated targeting (multiple adversarial submissions push the same poisoned scenario past cosine deduplication \(\tau{=}0.85\), defeating dedup by exploiting majority-of-cluster). Three aggregation rules at the edge layer: baseline SYNAPSE (Algorithm 2, cosine-cluster + cluster majority), +Krum [54] (drop entries furthest from cluster centroid before majority vote), and +TrimmedMean [55] (drop top/bottom \(f\) entries before majority). GSM8k, \(5\) clients, \(3\) rounds, \(200\) held-out queries; adversarial fractions \(\{0, 10, 20, 33, 50\}\%\).

6pt

13 Edge Merge Operator: Detailed Specification and Sensitivity Analysis↩︎

Full Algorithm 1 with numeric path and conflict-log specification. The body Algorithm 2 presents a compact form. Below we give the complete specification with the numeric-aggregation block, \(\mathrm{IsConsistent}\) definition, and \(\mathrm{ConflictsToPrecautions}\) mapping.

Numeric subfield aggregation. The numeric path is enforced in two stages, calibrated for user-level adjacency (Theorem 1) under a semi-honest edge trust model.

Stage 1: Per-user clipping at the client. Each end-user’s contribution to client \(k\)’s numeric record is clipped at \(\Delta_m^{(j)}\) per field before being incorporated into \(C_k.M\). Per-field clipping bounds the user’s \(\ell_1\) contribution at \(\Delta_m^{(j)}\) across all numeric subfields. In the single-user-per-client configuration used in our experiments, this reduces to per-client clipping; in multi-user-per-client deployments, the bound must be enforced at user-record granularity before any client-level aggregation (see “Multi-user deployments” below).

Stage 2: Edge-side averaging and noising. Each client \(k\) transmits its clipped record \(\mathrm{clip}(C_k.M.m^{(j)}, \Delta_m^{(j)}) \in [-\Delta_m^{(j)}, \Delta_m^{(j)}]\) to the edge aggregator, which computes the per-field average over \(K\) clients and adds Laplace noise calibrated to the average’s sensitivity: \[C_E.M.m^{(j)} \gets \frac{1}{K}\sum_{k=1}^K \mathrm{clip}\bigl(C_k.M.m^{(j)},\, \Delta_m^{(j)}\bigr) + \mathrm{Lap}\!\left(\frac{\Delta_m^{(j)}}{K \cdot \varepsilon^{(j)}}\right)\] Under user-level adjacency with stage-1 clipping in place, one user’s contribution influences exactly one client’s clipped value, which contributes \(1/K\) to the average; the per-user \(\ell_1\)-sensitivity of the released average is therefore \(\Delta_m^{(j)}/K\). The noise scale \(\Delta_m^{(j)}/(K \cdot \varepsilon^{(j)})\) yields per-field \(\varepsilon^{(j)}\)-DP per round. Per-field budgets \(\varepsilon^{(j)}\) sum to the per-round budget \(\varepsilon\) via sequential composition (Theorem 1 statement; App. 19, §L.2 proof).

Trust model. The edge aggregator is semi-honest: it follows Algorithm 2 faithfully but may attempt inference from the clipped values it receives prior to noising. Secure aggregation [45] can be layered on the numeric path so the edge observes only the noisy aggregate, weakening the trust assumption to the ideal-functionality only; the protocol described above is the configuration used in our experiments and operates without secure aggregation.

Multi-user-per-client deployments. When a single client aggregates contributions from \(U \geq 2\) end-users (e.g., an institution serving multiple users behind one federated client), the user-level guarantee requires two additional safeguards beyond the single-user-per-client configuration:

(a) Per-user clipping at the client. Each end-user’s contribution to client \(k\)’s numeric record is clipped at \(\Delta_m^{(j)}\) per field at user-record granularity, before any client-level aggregation. Concretely: client \(k\) maintains \(U\) per-user buffers \(\{b_{k,u}\}_{u=1}^U\), each clipped to \([-\Delta_m^{(j)}, \Delta_m^{(j)}]\); the client-level record \(C_k.M.m^{(j)}\) is the average \((1/U) \sum_u b_{k,u}\) rather than the sum. This keeps the per-user contribution to the released edge average bounded by \(\Delta_m^{(j)}/(K U)\), recovering user-level \(\ell_1\)-sensitivity \(\Delta_m^{(j)}/(K U)\) at the released average. Equivalently, deployments that prefer to keep the noise scale fixed at \(\Delta_m^{(j)}/(K\varepsilon^{(j)})\) must scale the effective sensitivity input to \(U \cdot \Delta_m^{(j)}\) and increase the noise accordingly to \(U \cdot \Delta_m^{(j)}/(K\varepsilon^{(j)})\) — a utility cost growing linearly in \(U\).

(b) Per-user-per-round field count bound. A single user may contribute to multiple numeric fields per round (e.g., a user who invokes both tool \(t_1\) and tool \(t_2\) affects the per-tool call counts and frequency vectors for both tools). To preserve user-level adjacency under sequential composition across \(K_f\) fields, we bound the number of fields any single user can affect in one round at \(F^* \leq K_f\) via a per-user-per-round field cap enforced at the client: each user’s contribution is restricted to at most \(F^*\) distinct numeric fields per round (chosen as the user’s \(F^*\) most-touched tools by raw frequency), with contributions to other fields zeroed before client-level aggregation. Under this cap, the per-user \(\ell_1\)-sensitivity across the full numeric vector is bounded by \(F^* \cdot \max_j \Delta_m^{(j)}\) rather than \(\sum_j \Delta_m^{(j)}\), and the per-round budget allocation \(\varepsilon^{(j)} = \varepsilon/F^*\) is sufficient to maintain per-round \((\varepsilon, 0)\)-DP. In our single-user-per-client experiments we use \(F^* = K_f\) (no effective cap) since natural per-user activity is bounded; multi-user-per-client deployments should set \(F^* \!<\! K_f\) explicitly.

Combined accounting. A multi-user-per-client deployment with \(U\) users per client and per-user-per-round field cap \(F^*\) achieves per-round \((\varepsilon, 0)\)-DP under user-level adjacency by setting:

• Per-user clipping at the client: \(\Delta_m^{(j)}\) per field per user;

• Field cap per user per round: \(F^*\);

• Per-field budget: \(\varepsilon^{(j)} = \varepsilon/F^*\);

• Edge noise scale: \(\Delta_m^{(j)}/(K U \varepsilon^{(j)})\) if the client averages over its users (option (a)), or \(U \Delta_m^{(j)}/(K \varepsilon^{(j)})\) if the client sums and the edge re-noises (utility-equivalent if \(U/(\varepsilon^{(j)}) = U \cdot 1/\varepsilon^{(j)}\)).

The two accountings give identical released utility; the choice is operational. Both reduce to the single-user case at \(U\!=\!1\), \(F^*\!=\!K_f\).

Canonical fields. Tool identifiers, descriptions, and API signatures in \(M\) are server-controlled and not noised; only client-contributed numeric statistics (per-tool call counts, empirical success rates, per-tool usage frequencies) are clipped and noised before edge aggregation.

\(\mathrm{IsConsistent}(\mathcal{C})\) definition. For a cluster \(\mathcal{C}\) of usage scenarios, \(\mathrm{IsConsistent}(\mathcal{C}) :=\) true iff for every pair \((u_1, u_2) \in \mathcal{C}^2\):

1. Structured-field agreement. Both scenarios reference the same parent_tool identifier and their precondition flag sets are jointly satisfiable (no flag pair \(\{f, \neg f\}\)).

2. LLM semantic consistency. An LLM consistency probe (llama-3.1-8b-instruct, prompt template in App. 20) returns Consistent when shown both natural-language scenarios.

Both checks must pass; either failure marks the cluster conflicted.

Conflict log \(\mathcal{L}^{(r)}\). A stateful edge-side artifact (not exchanged across clients), keyed by \((t, \mathrm{centroid\_id})\). Each entry stores the centroid scenario plus all dissenting scenarios from the current round’s clustering. \(\mathcal{L}^{(r)}\) is the union of conflict entries from round \(r\); \(\mathcal{L}^{(0)} = \emptyset\).

\(\mathrm{ConflictsToPrecautions}(\mathcal{L}^{(r-1)})\) mapping. For each entry \(((t, \mathrm{centroid\_id}), \{u_\text{centroid}, u_1, \ldots, u_d\}) \in \mathcal{L}^{(r-1)}\), emit a structured Precaution: \((\mathrm{tool}: t,\, \mathrm{precaution}: \mathrm{TextGradSummarize}_S(u_\text{centroid} \oplus \{u_i\}))\), where \(\oplus\) denotes a structured concatenation prompt: “Combine the following scenario with each of its dissenting variants into a single precaution rule that captures both the affirmative case and the exception conditions.” This produces composed Precautions of the form “Use \(X\) for \(Y\); do not use \(X\) when \(Z\)”.

Annex \(A\). Schema-validated entity–relation triples from clients are deduplicated via cosine similarity (same \(\tau\)) and passed through. The retrieval pipeline (§3) consults \(A\) to resolve cross-tool dependencies during query routing.

Sensitivity to cosine threshold \(\tau\). Tab. 8 reports routing accuracy and compendium size as \(\tau\) varies. Lower \(\tau\) over-merges semantically distinct scenarios; higher \(\tau\) under-merges. We use \(\tau{=}0.85\).

4pt

Cross-distribution Lipschitz and contraction diagnostics. Body §4 reports \(\hat{L}_e^{(99\%)}\!\approx\!1.4\) and \(\hat{L}_\mathcal{R}^{(99\%)}\!=\!0.891\) on GSM8k scenarios. To verify Theorem 3’s contraction premise generalizes beyond the in-paper benchmark, we re-measure on three additional scenario distributions: ToolBench, \(\tau\)-bench retail, and NQ-Open. Procedure. For each distribution we sample \(1000\) in-distribution scenario pairs, compute (i) embedding distance ratio \(\|e(s_1) - e(s_2)\|_2 / d_{\mathrm{text}}(s_1, s_2)\) and (ii) reranker output distance ratio over those pairs, then take the \(99\)th percentile for both \(\hat{L}_e\) and \(\hat{L}_\mathcal{R}\). The margin \(\hat{\Delta}^{(5\%)}\) is the \(5\)th percentile of top-\(1\) vs.top-\(2\) reranker score gaps; this is the empirical buffer that drives stable selection under stochastic perturbation.

4pt

14 TextGrad Ablation and Sensitivity↩︎

We isolate TextGrad’s contribution by replacing it at the edge layer while keeping Algorithm 2’s clustering and conflict log intact. Setup: GSM8k, \(5\) IID clients, \(5\) seeds. The probe set used in TextGrad’s forward pass is constructed at each edge from public benchmark queries (GSM8k validation, BBH dev), never from client data, and is fixed per edge for the federation – this keeps TextGrad’s optimization at the edge from reflecting client-specific information.

4pt

15 Reranker-Bypass Diagnostic: Multi-Seed Verification↩︎

Body §5.1 reports that bypassing the LLM reranker on the fixed \(500\)-query GSM8k diagnostic log drops routing accuracy \(0.92\!\to\!0.49\). To verify this is a stable component effect rather than a single-seed artifact, we re-ran the bypass at two additional seeds, holding the compendium and embedding model fixed. Setup. “Full pipeline” = retrieve top-\(5\) via Jina embedding \(\to\) llama-3.1-8b-instruct reranker selects the most relevant \(\to\) planning step. “No reranker” = retrieve top-\(5\) \(\to\) select the highest-cosine candidate directly \(\to\) planning step. Only the reranker step is toggled.

6pt

16 Real-API Failure Mode Decomposition↩︎

\(250\) queries across six API categories, classified into: routing error (wrong API), API timeout (\(>10\)s), rate limit (429), schema drift (unexpected response structure), auth/quota (401/403/quota exceeded), semantic miss (correct routing, wrong final answer). Routing errors and semantic misses are attributable to SYNAPSE; the rest are upstream-API properties.

Bootstrap confidence intervals. The point estimates in body Tab. [tab:real95api95results] are single-pass (no seed averaging) on a fixed test set. To characterize the test-set sampling variability, Tab. 12 reports \(95\%\) bootstrap CIs (\(B{=}1000\) resamples per category, drawn with replacement from the per-category routing-decision logs).

4pt

3pt

17 Communication Cost Analysis↩︎

4pt

17.1 Projected scaling to LiveMCPBench-class catalogs↩︎

LiveMCPBench [39] catalogs (\(\sim\!500\) tools across \(\sim\!70\) MCP servers) are not directly evaluated. Using our existing scale measurements (Tab. 15): compendium size grows \(62 \to 70\) KB at \(32\) APIs; structural overhead is \(\sim\!300\) bytes per tool. A \(500\)-tool compendium projects to \(\sim\!200\)–\(250\) KB total – still \(\sim\!200\times\) below FedLoRA r16. Retrieval latency: reranker processes top-\(k\!=\!5\) independent of catalog size; ANN retrieval at \(500\) tools projects to \(\sim\!500\)–\(550\) ms vs.\(484\) ms at \(228\) scenarios, requiring relaxation of the \(500\) ms cap or progressive retrieval (HNSW + top-\(k\)). Where the projection is shaky: \(\hat{L}_e^{(99\%)} \approx 1.4\) was measured on GSM8k; embedding behavior on \(500\)+ heterogeneous MCP tools requires re-measurement. Direct empirical evaluation on LiveMCPBench is the natural next step; the projection identifies bottlenecks rather than asserting they are negligible.

2.8pt

18 Benchmark-Breadth and Prompt-Transfer Results↩︎

This appendix supplies the supporting tables for the Benchmark breadth and Prompt transfer paragraphs in §5.

LiveBench (GPT-4o, \(3\) clients \(\times\) \(3\) rounds). Federated underperforms centralized by \(7\)–\(13\) pts on three reasoning tasks but outperforms by \(4\) pts on AMPS Hard (Tab. [tab:livebench]). The wider gap vs.the \(5\)–\(6\) pt gap at \(32\) APIs (Tab. 23) reflects the smaller federation scale used here. Both configurations use GPT-4o, so this does not establish cross-model transfer beyond GSM8k.

Prompt transfer (LLaMA-3.2-11B \(\to\) 3B, distinct from compendium transfer). Compendium held fixed; only optimized prompt structure migrates. Task-dependent: \(+0.15\) on Multi-step Arithmetic, \(+0.03\) on Object Counting, \(-0.08\) on GSM8k (Tab. [tab:prompt95transfer]). Mixed signs indicate prompt transfer is not interchangeable with compendium transfer; the GSM8k regression does not contradict the \(\leq\!2\)-pt cross-model loss in §5 (which transfers the compendium between LLM families with the federation pipeline held fixed). Treating the two mechanisms as interchangeable would obscure the practical recommendation: use compendium transfer when the federation can be re-run; prompt transfer only as a stop-gap.

18.1 External benchmark: \(\tau\)-bench retail↩︎

Setup. \(\tau\)-bench retail [56]: \(14\) tools, \(250\) tasks averaging \(4\)–\(6\) turns each, GPT-4o user simulator, official database-state grader. We partition the \(14\) tools across \(5\) federated clients into category-coherent subsets (account / orders / returns / catalog / escalation), evaluate SYNAPSE after \(3\) federated rounds, and compare against (i) centralized agent with full tool list, (ii) Fed-ICL with the same partitioning, (iii) local-only baseline. Inference: llama-3.1-8b-instruct; \(3\) seeds.

6pt

Cross-model probe. We test whether the cross-model transfer property documented on GSM8k (§5, \({\approx}\!2\)-pt loss within the LLaMA family, smaller for Mistral, gain for GPT-4o) replicates here. Holding the round-3 compendium and embedding model fixed (jina-embeddings-v2-base-en), we swap the inference LLM (Tab. 17). Same-family LLaMA-3.1\(\to\)​3.2-3B: \(\Delta\!=\!-0.022\), matching the GSM8k gap exactly. Cross-family Mistral-7B: \(\Delta\!=\!-0.009\). GPT-4o: \(\Delta\!=\!+0.085\) – the typed compendium rides a stronger model upward, reaching \(\sim\!90\%\) of \(\tau\)-bench’s published GPT-4o ceiling. All four LLMs preserve the per-category ordering (catalog \(>\) account \(>\) escalation \(>\) orders \(>\) returns).

6pt

18.2 Second instantiation: typed retrieval-policy artifacts on NQ-Open↩︎

Setup. Natural Questions Open [51] with hybrid retrieval (BM25 + dense, top-\(k\!=\!5\) Wikipedia passages) and llama-3.1-8b answer generation. Data and clients: \(5{,}000\) NQ-Open dev questions partitioned across \(5\) non-IID clients (\(1{,}000\) questions/client) by question-type (factoid-entity, factoid-date, list, definitional, multi-hop), inducing distributional skew on retrieval strategy. Federation: \(3\) rounds, batch \(3\), \(3\) local steps/round; same hyperparameters as the tool-routing experiments (App. 20). Wikipedia retrieval corpus: 2018-12-20 dump (KILT-canonical version), shared across clients; clients differ in the policy they learn over it, not the corpus itself. Artifact construction: clients run their local NQ subset, log retrieval-then-answer trajectories, and extract typed retrieval-policy artifacts \((\text{query type}, \text{retrieval strategy}, \text{evidence pattern}, \text{failure mode}, \text{correction})\) from successful and failed trajectories; deduplication and edge merge follow Algorithm 2 unchanged. Faithfulness evaluator: QAGS-style, llama-3.1-8b prompted with answer + retrieved passage to score support; offline against the same evaluator across all conditions. The schema-level merge operator (Algorithm 2) and DP guarantee (Theorem 1) apply unchanged; only the schema fields differ. Three metrics: Accuracy (Exact Match), Faithfulness, Evidence Recall@\(5\).

8pt

19 Proofs↩︎

19.1 Status of analytical claims↩︎

4pt

19.2 Proof of Theorem 1↩︎

Setup. The Laplace mechanism with scale \(b\) satisfies \((\Delta/b, 0)\)-DP for any function with \(\ell_1\)-sensitivity at most \(\Delta\) [36]. Definition 1 declares finite ranges per numeric field, bounding \(\Delta_m\) by construction. We adopt user-level neighboring datasets: \(D, D'\) differ by replacing the entire numeric record contributed by one user in round \(r\). The mechanism (App. [app:merge95full]) operates in two stages: (stage 1) per-user clipping at the client bounds the user’s \(\ell_1\) contribution at \(\Delta_m^{(j)}\) per field; (stage 2) the edge aggregator computes the per-field average over \(K\) clients and adds Laplace noise calibrated to the average’s sensitivity.

Per-field sensitivity under user-level adjacency. With stage-1 clipping in place, replacing one user’s contribution changes exactly one client’s clipped value by at most \(\Delta_m^{(j)}\) in \(\ell_1\) under the single-user-per-client configuration (multi-user-per-client handling in App. [app:merge95full]). Because that client’s clipped value contributes \(1/K\) to the released average, the per-user \(\ell_1\)-sensitivity of \(C_E.M.m^{(j)} = (1/K)\sum_k \mathrm{clip}_k\) is \(\Delta_m^{(j)}/K\). Adding Laplace noise of scale \(\Delta_m^{(j)}/(K\varepsilon^{(j)})\) therefore yields per-field \((\varepsilon^{(j)}, 0)\)-DP per round.

Concrete sensitivity values. Per-scenario tool-usage counts are clipped at \(N_{\max}\) per user-round, giving \(\Delta_m\!=\!N_{\max}\). For per-tool frequency vectors normalized to sum to one, replacing one user’s contribution can shift the distribution by up to \(\ell_1\)-distance \(2\) in the worst case (e.g., a user with all mass on tool \(t\) replaced by a user with all mass on tool \(t'\)); we therefore use \(\Delta_m\!=\!2\) for normalized frequency vectors, not \(\Delta_m\!=\!1\). Schema-declared field types determine which clipping rule applies; clipping occurs at the client before transmission to the edge.

Composition across fields (within a round). A single user’s contribution can influence multiple numeric fields simultaneously (e.g., usage count and frequency of the same tool). Parallel composition therefore does not apply: it requires disjoint partitions of the input dataset, not disjoint output fields. We use sequential composition across the \(K_f\) numeric fields released per round (notation: \(K_f\) for fields, \(K\) for clients). Allocating per-field budget \(\varepsilon^{(j)} = \varepsilon/K_f\) and summing field-wise guarantees yields per-round \((\varepsilon, 0)\)-DP. Equivalently, one may release all \(K_f\) fields under a single mechanism with joint \(\ell_1\)-sensitivity \((\sum_j \Delta_m^{(j)})/K\) and a single per-round budget \(\varepsilon\).

Composition across rounds. Across \(R\) federated rounds, basic sequential composition gives pure \((\varepsilon', 0)\)-DP with \(\varepsilon' = R\varepsilon\); advanced composition gives \((\varepsilon', \delta')\)-DP with \(\varepsilon' = \sqrt{2R \ln(1/\delta')}\,\varepsilon + R\,\varepsilon(e^\varepsilon - 1)\) at target \(\delta'\). For the small-\(R\) regime in this paper (\(R \leq 30\), \(\varepsilon \leq 2\)), basic composition is strictly tighter and is what we report (Tab. 5); advanced composition is a strictly weaker but still valid bound.

Trust model. The mechanism above assumes a semi-honest edge: the edge faithfully executes stages 1–2 but may attempt inference from the clipped client values it receives prior to noising. Theorem 1 is calibrated for this trust model. Secure aggregation [45] can be layered on the numeric path so that the edge observes only the noisy aggregate, weakening the trust assumption to the secure-aggregation ideal functionality. Theorem 1 is restricted to the numeric path; the text-field masking mechanism is heuristic and outside the formal claim.

Post-processing closure. Operations applied to the noised release – typed merge clustering (Algorithm 2), redistribution to clients, and server-side broadcast – do not consume additional privacy budget: by the post-processing property of differential privacy [36], any data-independent function of the \((\varepsilon, 0)\)-DP output remains \((\varepsilon, 0)\)-DP. The per-client averaging in stage 2 is part of the mechanism (it determines the sensitivity of the released statistic), not post-processing; post-processing applies only to operations on the already-noised release. The merge operator’s clustering step uses cosine similarity over text fields (which are not covered by Theorem 1) and noised numeric fields (which are post-processed); the resulting global numeric metadata inherits the per-round \((\varepsilon, 0)\)-DP guarantee, with composition across rounds as stated above.

19.3 Proof sketch of Theorem 2↩︎

By the assumed Lipschitz property of the embedding map, \(\|e(u) - e(\tilde{u})\|_2 \leq L_e \cdot d_\mathrm{text}(u, \tilde{u})\) pointwise; taking expectation over the privacy transformation \(\mathsf{PrivTrans}\) gives \(\mathbb{E}\|e(u) - e(\tilde{u})\|_2 \leq L_e \cdot \mathbb{E}[d_\mathrm{text}(u, \tilde{u})] =: \delta_\mathrm{priv}\). Cosine similarity is \(L_\mathrm{sim}\)-Lipschitz in \(\|\cdot\|_2\) on the unit sphere (with \(L_\mathrm{sim}\!=\!\sqrt{2}\) in the worst case), so \(\bigl|\mathrm{sim}(e(q), e(u)) - \mathrm{sim}(e(q), e(\tilde{u}))\bigr| \leq L_\mathrm{sim} \|e(u) - e(\tilde{u})\|_2\) pointwise, and taking expectation gives \(\mathbb{E}|\Delta\mathrm{sim}| \leq L_\mathrm{sim}\,\delta_\mathrm{priv}\). Markov’s inequality applied to the non-negative random variable \(|\Delta\mathrm{sim}|\) gives \(\Pr(|\Delta\mathrm{sim}| > t) \leq L_\mathrm{sim}\,\delta_\mathrm{priv}/t\), yielding the high-probability statement. Both bounds are conditional on the two Lipschitz assumptions; we measure \(\hat{L}_e^{(99\%)}\) and the corresponding empirical bounds \(\hat{\delta}_\mathrm{priv}\) and \(L_\mathrm{sim}\hat{\delta}_\mathrm{priv}\) in Tab. 20.

4pt

19.4 Proof sketch of Theorem 3↩︎

Existence of stationary distribution under contraction with bounded noise. The iterate \(s_{r+1} = \mathcal{R}(s_r) + \eta_{r+1}\) with \(\mathcal{R}\) an \(L\)-contraction (\(L\!<\!1\)) in \(\ell_2\) and \(\eta_r\) i.i.d.zero-mean with bounded variance \(\sigma^2\) per coordinate forms a Markov process (not a martingale: the previous draft incorrectly invoked martingale convergence). By the standard contractive-random-iteration argument [57], this Markov chain admits a unique stationary distribution \(\pi\) concentrated around the noise-free fixed point \(s^*\) of \(\mathcal{R}\), with stationary variance bounded by \(\sigma^2 / (1 - L^2)\) per coordinate. For nonlinear \(\mathcal{R}\), zero-mean noise does not in general imply \(\mathbb{E}_\pi[s] = s^*\) exactly; we therefore claim concentration around (not exact centering on) the noise-free fixed point. Convergence is in distribution to \(\pi\), not almost-surely to a deterministic point: because the Laplace privacy noise has constant variance per round, \(s_r\) does not collapse to \(s^*\) but fluctuates around it indefinitely.

Top-1 selection is correct with high probability. Let \(t^*\) be the unique noise-free top-scoring tool with margin \(\Delta = s^*(t^*) - \max_{t \neq t^*}s^*(t) > 0\). The top-1 selection \(\arg\max_t s_r(t)\) equals \(t^*\) unless some competitor’s noisy score exceeds \(t^*\)’s noisy score. Under the contraction premise plus the assumption (Theorem 3, condition (iii)) that the propagated stationary score perturbations are sub-exponential, \(s_\infty(t^*) - s_\infty(t)\) is a sub-exponential random variable with mean \(\geq \Delta\) and variance bounded by \(2\sigma^2/(1-L^2)\). By a Chernoff-style concentration bound, \(\Pr\bigl(s_\infty(t) \geq s_\infty(t^*)\bigr) \leq \exp\!\bigl(-\Delta^2(1-L^2)/(2\sigma^2)\bigr)\) for each competitor \(t \neq t^*\). Union bound over the \(K-1\) competitors and the two-sided event gives the stated correctness probability \(1 - 2(K-1)\exp\!\bigl(-\Delta^2(1-L^2)/(2\sigma^2)\bigr)\). The sub-exponential tail assumption is not proved for arbitrary nonlinear \(\mathcal{R}\) but is consistent with score perturbations driven by Laplace numeric noise composed with a Lipschitz reranker; we treat it as an assumption rather than a derived property.

What we revised relative to the earlier draft. The earlier draft claimed almost-sure convergence to a deterministic point \(s^*\) via martingale convergence; this was incorrect because (i) \(s_r - \mathcal{R}(s_{r-1})\) is the noise term, not a martingale-difference of \(s_r\), and (ii) constant-variance noise prevents almost-sure collapse. The corrected statement claims stable selection with high probability under the contraction premise, which is the operationally relevant guarantee and is consistent with the empirical observation that the top-1 selection is correct on \(100\%\) of held-out queries with \(\hat{\Delta}^{(5\%)} = 0.138\) (Tab. 9).

Empirical characterization. On \(100\) perturbation-pair samples (Gaussian \(\sigma{=}0.05\)) over held-out GSM8k queries: \(\hat{L}_\mathcal{R}^{(99\%)}\!=\!0.891\) (median \(0.620\)), \(L<1\) for \(100\%\) of pairs; \(\hat{\Delta}^{(5\%)}\!=\!0.138\) (median \(0.208\)), \(\Delta>0\) for \(100\%\) of \(100\) queries. Tab. 9 (App. 13) extends this to four additional distributions: ToolBench, \(\tau\)-bench retail, NQ-Open all hold (with NQ-Open marginal at \(\hat{L}_\mathcal{R}^{(99\%)}\!=\!0.971\)), while a LiveBench subset returns \(\hat{L}_\mathcal{R}^{(99\%)}\!=\!1.018 > 1\) and the contraction premise fails to certify – routing stability is therefore not claimed for that distribution under the deployed embedding+reranker pair.

20 Experimental Setup↩︎

SYNAPSE runs with three federated rounds and three default clients (adjustable via --client-count). Retrieval: jina-embeddings-v2-base-en with top-\(K{=}5\) and cosine threshold \(\tau{=}0.85\). LLM rerank: llama-3.1-8b-instruct (NVIDIA H200, batch 8–32, mixed precision, \(500\) ms cap). DP budget \(\varepsilon \in \{0.5, 1.0, 2.0\}\); masking \(\lambda \in \{0.5, 1.0, 1.5\}\). TextGrad: edge, batch 3, 3 local optimization steps, summarization-based aggregation. Baselines: BM25 (\(k_1{=}1.5, b{=}0.75\)); Fed-ICL (\(8\) exemplars/client). GSM8k: 5/8 clients with 50/30 examples each. Non-IID splits: shard by numeric answer range (GSM8k) or question length (BBH). Fig. 4 shows the inference pipeline.

Proxy tool-label construction (GSM8k/BBH). The router does not see dataset provenance at inference time – routing decisions depend only on the user query and the retrieved compendium scenarios. Ground-truth tool labels for the proxy benchmarks are derived as follows. GSM8k: every question is mapped to the mathqa tool family; gold answers are the dataset’s standard numeric solutions. BBH Object Counting: mapped to logicqa (counting subroutine); gold answers are dataset labels. BBH Multi-Step Arithmetic: mapped to mathqa (multi-step numeric); gold answers are dataset labels. The mapping is a single static function from dataset \(\to\) tool family, applied uniformly to all examples in that dataset; it is not learned, not query-dependent, and identical across all baselines (SYNAPSE, Fed-ICL, FedTextGrad, BM25, ReAct, Centralized). This makes the proxy benchmark a routing-recall test: given a query, can the system retrieve a scenario whose parent tool matches the dataset’s tool family? Limitation. Because the mapping is dataset-uniform, the proxy benchmark cannot test fine-grained cross-tool routing within a single dataset (e.g., MathQA vs.ScienceQA on a mixed-domain question); the multi-tool proxy reported in §5.2 (4 tool families: MathQA, SearchQA, CodeExec, LogicQA, \(\sim\!250\) queries/family) and ToolBench (Tab. [tab:real95api95results]) test that capability directly.

Sensitivity to \(\tau\) and embedding choice. The cosine threshold \(\tau{=}0.85\) and embedding model (Jina v2) are chosen by inspection of held-out scenario pairs and not separately tuned per benchmark. Across the eight settings tested in Tab. 9, the empirical Lipschitz ratio \(\hat{L}_e\) ranges \(1.36\)–\(1.45\) at \(\lambda{=}1.0\), suggesting modest sensitivity to distribution; cross-distribution Lipschitz exceeds \(1\) on LiveBench, where routing stability is not certified (§4). Systematic ablation of \(\tau\) and embedding choice (e.g., bge-large, e5) on routing accuracy and dedup rate is left as future work; the conditional theorems (Thm. 2, Thm. 3) are stated against these constants and would require re-measurement under different choices.

6pt

6pt

21 Long-Horizon Controlled Simulation: Full Protocol↩︎

This appendix documents the protocol for the long-horizon controlled simulation reported in §5. The protocol was registered before the run; numbers populate App. 22.

Federation topology. \(N{=}100\) clients organized into \(5\) simulated organizations of \(20\) clients each, with non-IID query distributions reflecting enterprise specialization: Org A (search/knowledge, MSMARCO-derived traces), Org B (math/symbolic, GSM8k+MATH), Org C (operations, MultiWOZ-derived dialogue), Org D (commerce, Stripe sandbox + retail Q&A), Org E (mixed, balanced across \(32\) APIs; cross-validation organization). Each client within an organization sees a non-IID slice of its organization’s distribution. \(M{=}5\) edge aggregators (one per org) running Llama-3.1-8B for TextGrad summarization. Single central server applies the typed merge operator (Algorithm 2) over the \(5\) edge compendiums and broadcasts back. One round every \(\sim\!11\) hours; \(30\) rounds over \(14\) days. \(\sim\!21{,}000\) queries total (\(\sim\!1{,}500\)/day; \(\sim\!200\)/client).

Tool inventory. \(32\) APIs across \(8\) categories (Search \(\times 4\), Weather \(\times 3\), Knowledge \(\times 5\), Math/Symbolic \(\times 4\), Data/REST \(\times 6\), Calendar/Files \(\times 4\), Payments \(\times 3\), Communications \(\times 3\)). Real APIs used where free-tier access permits (SerpAPI, OpenWeatherMap, Wikipedia, Wolfram, GitHub, etc.); sandbox or deterministic mocks elsewhere.

Drift schedule. \(8\) drift events at known timestamps spanning \(5\) types: \(1\) schema-rename (Day 3, SerpAPI organic_results\(\to\)web_results), \(2\) schema-add (Day 4 OpenWeatherMap air_quality_index, Day 9 REST Countries regional_blocs), \(1\) schema-restructure (Day 5 GitHub repository.owner flattened), \(2\) rate-limit (Day 7 Wikipedia \(200{\to}50\) req/min, Day 11 Stripe \(100{\to}25\)/sec), \(2\) endpoint-path (Day 8 Wolfram /v1/result\(\to\)/v2/query, Day 12 Notion). Pre-drift accuracy is computed in \(\pm 24\)h windows; post-drift at \(T{+}1\), \(T{+}3\), \(T{+}10\) rounds; “recovered” = within \(0.02\) of pre-drift baseline.

Staleness protocol. At end of round \(20\), save snapshot \(C_g^{(20)}\) and serve queries against the live API surface for \(7\) additional days without aggregation. Cadences run in parallel: every-round (baseline), every-\(5\), every-\(10\), frozen. Accuracy measured at days \(\{1,3,5,7\}\) post-freeze on a held-out \(1{,}000\)-query test set proportional to organizational mix.

Compute and scope. \(4\times\) H200 GPUs; \(\sim\!2\) weeks wall-clock for the run plus \(\sim\!1\) week for analysis. The simulation can demonstrate routing under enlarged tool-list size and longer federation, conflict-log behavior under author-scheduled drift, the cadence-accuracy Pareto, and cross-organizational transfer. It cannot demonstrate production-scale traffic (\(1{,}500\)/day is below enterprise loads), jurisdiction-specific regulatory compliance (HIPAA/GDPR characterization is structural, not certified), or adaptive Byzantine attacks beyond those in App. 12.

22 Long-Horizon Controlled Simulation: Detailed Results↩︎

This appendix reports the full numbers behind the simulation summarized in §5: \(100\) clients across \(5\) simulated organizations, \(32\) APIs, \(30\) federated rounds over \(14\) days, \(\sim\!21{,}000\) total queries. Numbers are reported to two decimal places for accuracy and rounded to whole units for size and latency.

22.1 Headline metrics across rounds↩︎

4pt

22.2 Per-category end to end success at Round \(30\)↩︎

6pt

System metrics across rounds (matching Tab. 23): the compendium grows from \(28\) KB at Round \(1\) to \(96\) KB at Round \(30\) with deduplication rate increasing as scenario count saturates. End-to-end success (\(0.53 \to 0.62 \to 0.67\)) sits below routing accuracy because real-API execution adds additional failure modes; the gap (routing \(-\) E2E) of \(\sim\!12\) pts at Round \(30\) is consistent with the small-scale ToolBench experiment (Tab. [tab:real95api95results]). The federation–centralized gap is stable across rounds at \(+0.053\), \(+0.057\), \(+0.052\) (Rounds \(1\), \(10\), \(30\)), evaluated by rerunning held-out queries under a centralized configuration with full conflict-log access.

Where the \(5\)-pt federation–centralized gap comes from. The gap is stable rather than closing, which is itself diagnostic: it indicates a structural source rather than a convergence-rate effect. We hypothesize three mechanisms each of which the centralized oracle can exploit but federated SYNAPSE cannot, and offer the available evidence for each.

• Cross-cluster reconciliation (likely dominant). The merge operator (Algorithm 2) handles conflicts within a cosine cluster but not across clusters: two scenarios with \(\cos < \tau\) are kept as separate entries even when they describe the same routing decision in different terms. Centralized routing sees both during retrieval and can use whichever fits better. Supporting evidence: per-category accuracy in Tab. 24 is most depressed in categories with high within-category paraphrasing (Communications, Calendar/Files, Knowledge: all \(\leq 0.72\)) and least depressed in categories where scenarios are more lexically distinctive (Math/Symbolic, Weather: both \(\geq 0.81\)). The category-level spread of \(0.13\) tracks paraphrasing density, not tool count.

• Lossy text summarization at edge layer. TextGrad summarization (§3.1) compresses multiple client scenarios into a single summary; the centralized oracle has access to all client scenarios un-summarized. The TextGrad ablation in Tab. 10 shows that summarization choice matters in the controlled regime (\(0.92\) for TextGrad vs.\(0.85\) for extractive concatenation), but does not by itself isolate the deployment-gap component because the controlled-regime baseline is centralized-with-TextGrad rather than centralized-without-summarization. The cleanest test of this hypothesis would be a deployment-scale run with extractive concatenation in place of TextGrad, holding all other factors constant; we have not run that experiment. We list this hypothesis here because TextGrad’s per-cluster compression is a structural lossy step that the centralized oracle skips entirely.

• Cluster-representative selection in conflict cases. When line 13 of Algorithm 2 marks a cluster conflicted, the centroid scenario is retained and the dissenter is logged for next-round Precautions. The centralized oracle evaluates queries against both scenarios directly. The conflict log eventually surfaces dissenters as Precautions, but the within-round opportunity cost is real.

What we do not yet know. We cannot quantitatively partition the \(5\)-pt gap among (i)–(iii) without a second deployment-scale run that systematically ablates each mechanism. Within-paper data is consistent with hypothesis (i) being the largest component (the per-category pattern above), but the available \(\tau\)-sensitivity table (Tab. 8) addresses a different question – it shows that lowering \(\tau\) from \(0.85\) over-merges genuinely-distinct scenarios and hurts routing accuracy (\(0.92 \to 0.87\)) – and so does not by itself isolate the cross-cluster reconciliation effect. A targeted ablation that varies cross-cluster merge behavior while holding within-cluster behavior fixed is required, and is left for follow-up work. We flag this as an open empirical question rather than a closed finding.

22.3 Staleness across aggregation cadences↩︎

4pt

Failure decomposition by Day 7. The shift in failure budget across cadences reveals which mechanism fails as the compendium ages. Tab. 26 decomposes \(1\!-\!\text{accuracy}\) into five sources at Day \(7\).

6pt

22.4 Cross-organizational transfer↩︎

4pt

Robustness of the transfer claim. The result above uses a category-coherent organizational partitioning of the \(32\)-tool inventory. We address whether the \(+0.10\) mean \(\Delta\) depends on this specific partitioning in four ways.

(i) Within-experiment evidence. The per-org \(\Delta\) ranges from \(+0.07\) to \(+0.13\) across the five organizations – a \(0.06\) spread with std.\(0.020\). All five orgs show positive \(\Delta\) with the smallest gain (\(+0.07\)) approximately three standard deviations above zero. If the result were specific to a particular partitioning, we would expect at least one organization to show near-zero \(\Delta\).

(ii) Mechanism-level prediction. Hypothesis (i) of the gap-diagnosis paragraph above predicts that organizations with higher within-category paraphrasing should gain more from cross-org Precautions. The data fit this prediction: Operations (calendar/files/communications, \(\leq 0.72\) within-category accuracy) gains \(+0.13\); Commerce \(+0.11\); Search-and-Knowledge \(+0.07\). A null effect would have \(\Delta\) uncorrelated with the paraphrasing pattern of each org’s native subset.

(iii) Randomized-partitioning robustness check. We re-ran the cross-org evaluation under a random partitioning that deliberately breaks the category-coherent assumption: each of the \(32\) APIs is randomly assigned to one of \(5\) orgs (with overlap), producing organizations with no native-category coherence. Setup: \(50\) clients (\(10\) per org, vs.\(20\) in the main run), \(5\) rounds (vs.\(30\)), \(50\) queries/client, \(3\) seeds; we re-ran the category-coherent regime at the same scale as a paired control. Tab. 28 reports both regimes.

4pt

The cross-organizational transfer effect is real but partitioning-dependent in magnitude. The mechanism story holds: more paraphrasing within native subsets \(\Rightarrow\) larger gain from cross-org Precautions. The transfer claim survives the most direct robustness check available: random partitioning still produces positive \(\Delta\) across all \(5\) orgs, with smallest gain \(+0.04\) (above zero by \({\sim}1.3\sigma\) at this sample size).

(iv) What remains untested. Adversarial-overlap partitionings (where org native subsets deliberately overlap), partitionings with extreme inventory-size skew (one org dominant), and full-scale (\(30\)-round, \(100\)-client) random-partitioning runs are not reported here; the small-scale random run above is the strongest evidence available within the submission’s scope. Conditional on (i)–(iii), we read the cross-org claim as evidence-supported under both category-coherent and random partitionings, with magnitude varying by partitioning regime.

References↩︎

---

1. Equal contribution.↩︎

2. Corresponding author.↩︎