Vertical Computation Overhead

The core privacy guarantee in VFL relies heavily on cryptographic protocols, which introduce significant computational cost. Key operations include:

• Homomorphic Encryption (HE): Enables computations on encrypted data. Performing additions and multiplications on ciphertexts is orders of magnitude slower than on plaintext.
• Secure Multi-Party Computation (MPC): Protocols for jointly computing a function over private inputs. The communication rounds and secret-sharing schemes add substantial latency.
• Private Set Intersection (PSI): Used for the initial entity alignment phase. Cryptographic PSI, while secure, is computationally intensive compared to plaintext matching. This cryptographic layer is the primary differentiator from centralized training and a major source of overhead.

In the split neural network architecture, each feature owner executes only a portion of the full model, up to the cut layer. This creates inefficiencies:

• Underutilized Hardware: The local model segment is often smaller than the device's full computational capacity (e.g., GPU), leading to poor resource utilization.
• Idle Time: After sending its intermediate output, a feature owner must wait for the label owner to complete the forward pass, compute the loss, and propagate gradients back before it can resume computation. This synchronous dependency creates bubbles of idle time.
• Memory Overhead: Despite a smaller model, the system must maintain context and gradients for the distributed training process, adding memory management complexity.

The vertical training protocol requires secure coordination for gradient calculation and aggregation.

• Vertical Gradient Computation: Gradients must be computed and passed securely backwards through the split network. This often involves masking or encrypting gradient values before transmission.
• Vertical Secure Aggregation: Protocols like Secure Aggregation from horizontal FL are adapted for VFL to combine updates from multiple feature owners without revealing individual contributions. This aggregation phase involves additional cryptographic masking and summation steps.
• Multi-Round Protocols: A single training step may require multiple communication rounds between parties to complete securely, multiplying the base computational cost.

Before training begins, parties must identify overlapping entities using secure entity resolution, typically via Private Set Intersection (PSI). While often a one-time cost, it is a non-trivial source of pre-training overhead.

• Cryptographic PSI for large datasets (millions of records) can require significant compute time and memory.
• Ongoing Alignment: In dynamic systems where entity sets change, alignment may need to be re-run periodically, incurring recurring overhead. This foundational step ensures samples are matched correctly but adds a substantial computational preamble to the VFL workflow.

VFL tightly interweaves communication and computation, creating overhead that doesn't exist in local training.

• Encryption/Decryption Cycles: Every exchanged intermediate output or gradient must be encrypted by the sender and decrypted by the receiver (or computed on under HE). These cycles are CPU-intensive.
• Synchronization Points: The protocol mandates strict synchronization between parties at the cut layer. Devices must pause computation to send/receive data, and faster devices wait for slower ones, reducing overall system efficiency.
• Protocol Overhead: The vertical inference protocol for prediction requires a similar secure, multi-step process, meaning overhead persists into the production deployment phase.

Vertical computation overhead differs fundamentally from Horizontal Federated Learning.

• Horizontal FL: Overhead is primarily from training full models on many devices and communicating complete model updates. Computation is high but standard forward/backward passes.
• Vertical FL: Overhead is primarily from cryptographic operations and coordinated execution of partial models. The raw training computation per device may be lower, but the cryptographic and coordination costs are uniquely high.
• Asymmetry: In VFL, the label owner often bears the highest load, performing the majority of the model's forward/backward pass and managing the cryptographic protocol for all feature owners.

Designing the split neural network to minimize the complexity of the portion computed by each party directly reduces local computation. Key techniques include:

• Strategic Cut Layer Placement: Placing the cut layer earlier in the network reduces the depth (and thus computational load) of the local model segment each feature owner must run.
• Lightweight Local Sub-models: Replacing standard layers (e.g., large transformers) with efficient alternatives like MobileNet blocks or distilled models for the feature owner's segment.
• Asymmetric Architecture Design: Allocating more complex layers to the party with greater computational resources (often the label owner).

The cryptographic protocols for secure aggregation and homomorphic encryption are primary sources of overhead. Mitigation involves:

• Hardware Acceleration: Utilizing GPUs, Tensor Cores, or dedicated cryptographic hardware (e.g., Intel SGX, AMD SEV) to offload encryption/decryption operations.
• Efficient Cryptosystem Selection: Choosing partial homomorphic encryption (e.g., Paillier) over fully homomorphic encryption when possible, as it is orders of magnitude faster for specific operations like gradient addition.
• Hybrid Privacy Approaches: Combining lightweight secure multi-party computation (MPC) protocols for most steps with heavier encryption only for the most sensitive data exchanges.

Dynamically managing where computations occur can balance the load. This includes:

• Server-Assisted Computation: The central coordinator (or label owner) can pre-compute and distribute certain non-sensitive components or handle the more intensive parts of cryptographic operations.
• Selective Participation: In each training round, only a subset of feature owners with sufficient available compute resources are selected to participate, preventing stragglers from bottlenecking the system.
• Pipeline Parallelism: Overlapping the computation of one party's local forward pass with the cryptographic operations or gradient computation of another party to hide latency.

Reducing the size and precision of the values communicated also reduces the computational cost of processing them. Techniques include:

• Quantization: Converting 32-bit floating-point gradients or intermediate outputs to lower precision (e.g., 8-bit integers) before encryption and transmission, which speeds up subsequent cryptographic operations.
• Top-k Gradient Sparsification: Only transmitting the largest k% of gradient values, setting the rest to zero. This creates sparse matrices that are faster to encrypt and aggregate.
• Error Feedback: Compensating for the information loss from compression by adding the compression error from the previous step to the current gradient, maintaining model convergence.

Reducing the dimensionality of the problem at its source lowers perpetual computation costs. This involves:

• Privacy-Preserving Importance Scoring: Using federated algorithms to calculate feature importance (e.g., via federated SHAP values or correlation with labels) without exposing raw data.
• Iterative Pruning: Collaboratively identifying and removing non-informative or redundant features from the training process over several VFL rounds.
• Projection to Lower Dimensions: Applying federated Principal Component Analysis (PCA) or autoencoders to project high-dimensional feature sets onto a lower-dimensional, more computationally manageable subspace.

Relaxing strict synchronization requirements avoids idle waiting, which is a waste of compute cycles.

• Asynchronous VFL: Allowing feature owners to submit updates as soon as they are ready, without waiting for others. The aggregator applies updates immediately, though this can introduce stability challenges.
• Stale-Synchronous Parallel (SSP): A bounded-asynchrony model where a server proceeds with aggregation once it has received updates from a defined majority of parties, tolerating stragglers up to a pre-set staleness threshold.
• Adaptive Learning Rates: Dynamically adjusting the learning rate for updates based on their staleness to mitigate the negative effects of asynchrony on model convergence.

A split neural network is the core model architecture enabling VFL, where the network is partitioned across parties. The cut layer defines the division point. This architectural choice is the primary source of computation overhead, as it mandates:

• Local forward passes on partial features.
• Secure transmission of intermediate outputs.
• Coordinated backpropagation across network segments.

Homomorphic Encryption (HE) is a cryptographic technique that allows computations to be performed directly on encrypted data. In VFL, HE is often applied to protect intermediate outputs or gradients, but it introduces significant computation overhead due to:

• The mathematical complexity of encryption/decryption operations.
• The ciphertext expansion, which increases data size.
• The computational intensity of arithmetic on encrypted values, which can be orders of magnitude slower than plaintext operations.

Vertical Multi-Party Computation refers to the use of secure MPC protocols to jointly compute model updates over vertically partitioned data. While providing strong privacy guarantees, MPC protocols are a major contributor to computation overhead through:

• The use of secret sharing, which splits data into random shares.
• Interactive protocols requiring multiple communication rounds per operation.
• Complex cryptographic primitives for each arithmetic or comparison gate in the computation graph.

The vertical training protocol defines the exact sequence of steps for a VFL training round. Its design directly dictates computation overhead. A typical protocol involves:

1. Entity Alignment (e.g., using PSI) to find common samples.
2. Vertical Forward Propagation: Feature owners compute to the cut layer.
3. Secure Transmission of encrypted/sanitized intermediate results.
4. Label Owner Computation of loss and initial gradients.
5. Vertical Backpropagation: Gradients are passed back securely.
6. Local Model Update by each party. Each step adds latency and compute cost beyond centralized training.

Private Set Intersection is a cryptographic protocol used for the initial entity alignment phase of VFL. It allows parties to discover their common users (e.g., customer IDs) without revealing their full datasets. PSI contributes to pre-training overhead through:

• Computationally intensive operations like oblivious transfers or public-key cryptography.
• Multiple communication rounds between all participating parties.
• Scaling challenges with large dataset sizes, though modern PSI protocols (e.g., based on cuckoo hashing) have improved efficiency.

Vertical Communication Overhead is the bandwidth and latency cost of exchanging messages between parties. It is intrinsically linked to computation overhead, as many cryptographic operations (e.g., HE, MPC) are performed to enable secure communication. Key factors include:

• The size and frequency of transmitted intermediate outputs and gradients.
• The expansion factor of ciphertexts in encrypted exchanges.
• The number of synchronous communication rounds required per training iteration, which can idle compute resources while waiting for network transfers.