Rotation hoisting

Example source: examples/06_eager_rotation_hoisting.py

This example benchmarks caller-selected independent rotations against one caller-selected hoisted group over the same source and direct keys. Rotation hoisting shares decomposition and preparation derived from one ciphertext; it is a scheduling choice rather than an implementation selected invisibly by a backend.

Rotation API

The method name identifies both cardinality and how the operation selects key material:

Method	Rotation selector	Key ownership	Result
rotate_by_step	One signed step	Engine inventory	One ciphertext
rotate_with_key	One self-described key	Caller	One ciphertext
rotate_many_by_steps	Ordered signed steps	Engine inventory	Ordered ciphertexts
rotate_many_with_keys	Ordered self-described keys	Caller	Ordered ciphertexts

The step-based methods may use installed keys, generate direct keys when allowed, or compose an available engine-owned key path. The key-based methods use exactly the supplied direct key objects and do not install them.

Both sequence methods accept use_hoisting. True forms one scheduled group from the direct keys in the supplied sequence. False executes those direct rotations independently. Eager execution preserves the caller's offsets and order; it does not search surrounding operations or regroup them.

Run the benchmark

python examples/06_eager_rotation_hoisting.py \
  --preset slots32768-scale40-depth34-int64 \
  --counts 4,8,16 \
  --warmup 5 \
  --runs 20

Start with fewer runs when checking a new environment:

python examples/06_eager_rotation_hoisting.py \
  --preset slots8192-scale40-depth7-int64 \
  --counts 2,4 \
  --warmup 1 \
  --runs 3

1. Provision every direct key before timing

for rotation_step in rotation_steps_all:
    _ = engine.rotation_key(rotation_step)

Lazy key creation must not appear in a rotation timing. The benchmark creates the public key and all requested rotation keys before warmup.

2. Compare equivalent outputs

Independent path:

[
    engine.rotate_by_step(ciphertext, rotation_step)
    for rotation_step in rotation_steps
]

Grouped path:

engine.rotate_many_by_steps(
    ciphertext,
    rotation_steps,
    use_hoisting=True,
)

Both request the same set of rotated ciphertexts. The sequence-form API gives the caller a way to select one hoisted group containing all direct requested steps. Passing use_hoisting=False selects independent execution through the same Eager API.

Compile-time scheduling

Compile IR represents independent rotations as fhelium_ckks.rotate operations. RotationHoistingPass identifies rotations that read the same ciphertext and preparation tables, then emits fhelium_ckks.hoisted_rotate_many groups. The pattern is a shared preparation in the data-dependency graph, rather than adjacent instructions:

$$y_i=F(c_0,P(c_1;\theta ),k_i;{\varphi }_i)⟶h=P(c_1;\theta ),y_i=F(c_0,h,k_i;{\varphi }_i).$$

Here $P$ prepares the key-switch digits, $\theta$ identifies its numerical parameters and tables, and $F$ completes each rotation using its key $k_i$ and rotation/output attributes ${\varphi }_i$. Pure consumers and rotations of other inputs may appear between members of a group. The existing multi-result operation requires a common output domain and compatible execution attributes.

The pass chooses a position after all computed operands are available and before any grouped result is consumed. It can move operand-free material references within the same pure interval, but does not move their producer computations. When no common position exists, rotations remain in separate groups. Effects, unknown operations, control flow, and caller-assigned implementations delimit intervals. Known nested regions are visited separately; preparation is not moved across branches or loop iterations.

The shared operands are live Tensor dataflow. A possible write ends an interval, so grouping does not assume that repeated reads of one Tensor observe unchanged contents across mutations. The pass does not compare Tensor contents or generate key material. max_group_size bounds the number of outputs produced together. Grouping may extend output lifetimes.

Shared preparation can change key-switch rounding and encryption noise relative to independent rotations. The decoded rotation and value state are preserved; ciphertext residues need not be identical across those schedules. Numerical comparisons between schedules therefore use the decoded-error criterion, while comparisons of the same schedule can additionally check residues modulo Q.

The backend consumes the selected groups without adding offsets, splitting them, or falling back to independent rotation. A caller-selected scheduling pass can instead emit the same operation using a workload-specific memory policy.

3. What can be shared

A rotation applies a Galois automorphism and a key switch. When many rotations use the same source ciphertext, decomposition and extension work derived from that source can be prepared once and reused across direct rotation keys.

Conceptually:

Expanded diagram

100%

The result still contains one ciphertext per requested step. Hoisting reduces repeated preparation; it does not remove the per-key automorphism/key-switch work or output memory. The currently selected group therefore remains visible in the Program rather than existing only inside a native implementation.

4. Benchmark without launch-order bias

The example alternates which path runs first on each measured iteration:

if run_idx % 2 == 0:
    independent()
    hoisted()
else:
    hoisted()
    independent()

It also synchronizes CUDA around each timing interval, performs warmup, and reports mean and median. This reduces bias from asynchronous launches, one-time kernel setup, and temperature drift.

5. Interpret the result

The benchmark reports:

• one-by-one mean and median;
• grouped mean and median;
• speedup ratio;
• percentage mean-time saving.

Hoisting tends to become more valuable as the number of rotations from one source increases. Actual benefit depends on active RNS rows, decomposition shape, backend, GPU, key residency, and whether the surrounding algorithm can consume all produced rotations.

Source

#!/usr/bin/env python3

"""Benchmark grouped rotation hoisting against independent rotations.

Example:
    python examples/06_eager_rotation_hoisting.py --preset slots32768-scale40-depth34-int64 --counts 4,8,16
"""

from __future__ import annotations

import argparse
import gc
import statistics as stats
import time

import torch
from common import add_engine_args, make_engine, print_table, sync_if_cuda


def _time_once(fn, device: torch.device):
    sync_if_cuda(device)
    start = time.perf_counter()
    result = fn()
    sync_if_cuda(device)
    return (time.perf_counter() - start) * 1e3, result


def _summarize(times: list[float]) -> dict[str, float]:
    return {
        "mean_ms": stats.mean(times),
        "median_ms": stats.median(times),
        "min_ms": min(times),
        "max_ms": max(times),
        "std_ms": stats.pstdev(times),
    }


def _alternating_bench(
    independent, hoisted, *, warmup: int, runs: int, device: torch.device
):
    for _ in range(warmup):
        independent()
        hoisted()
        sync_if_cuda(device)

    independent_times = []
    hoisted_times = []
    for run_idx in range(runs):
        if run_idx % 2 == 0:
            timing, result = _time_once(independent, device)
            independent_times.append(timing)
            del result
            timing, result = _time_once(hoisted, device)
            hoisted_times.append(timing)
            del result
        else:
            timing, result = _time_once(hoisted, device)
            hoisted_times.append(timing)
            del result
            timing, result = _time_once(independent, device)
            independent_times.append(timing)
            del result

    return _summarize(independent_times), _summarize(hoisted_times)


def _parse_counts(text: str) -> list[int]:
    counts = [int(item.strip()) for item in text.split(',') if item.strip()]
    if not counts or any(count <= 0 for count in counts):
        raise argparse.ArgumentTypeError("counts must be positive integers")
    return counts


def main() -> None:
    parser = argparse.ArgumentParser(description=__doc__)
    add_engine_args(parser, default_preset="slots32768-scale40-depth34-int64")
    parser.add_argument("--counts", type=_parse_counts, default=[4, 8, 16])
    parser.add_argument("--warmup", type=int, default=5)
    parser.add_argument("--runs", type=int, default=20)
    parser.add_argument("--depth", type=int, default=0)
    args = parser.parse_args()

    engine = make_engine(args)
    max_count = max(args.counts)
    rotation_steps_all = list(range(1, max_count + 1))

    _ = engine.public_key
    for rotation_step in rotation_steps_all:
        _ = engine.rotation_key(rotation_step)

    slots = engine.num_slots
    idx = torch.arange(slots, dtype=torch.float64)
    message = (
        0.01 * torch.sin(idx * 0.001) + 0.005 * torch.cos(idx * 0.003)
    ).to(torch.complex128)
    ct = engine.encrypt_message(message, depth=args.depth)
    sync_if_cuda(torch.get_default_device())

    rows = []
    for count in args.counts:
        rotation_steps = rotation_steps_all[:count]

        def independent():
            return [
                engine.rotate_by_step(ct, rotation_step)
                for rotation_step in rotation_steps
            ]

        def hoisted():
            return engine.rotate_many_by_steps(ct, rotation_steps)

        independent_stats, hoisted_stats = _alternating_bench(
            independent,
            hoisted,
            warmup=args.warmup,
            runs=args.runs,
            device=torch.get_default_device(),
        )
        speedup = independent_stats["mean_ms"] / hoisted_stats["mean_ms"]
        savings = (
            1.0 - hoisted_stats["mean_ms"] / independent_stats["mean_ms"]
        ) * 100.0
        rows.append(
            [
                count,
                f"{independent_stats['mean_ms']:.4f}",
                f"{hoisted_stats['mean_ms']:.4f}",
                f"{speedup:.4f}x",
                f"{savings:.2f}%",
                f"{independent_stats['median_ms']:.4f}",
                f"{hoisted_stats['median_ms']:.4f}",
            ]
        )
        gc.collect()
        torch.cuda.empty_cache()

    print(
        f"Engine: preset={args.preset}, depth={args.depth}, device={args.device}, runs={args.runs}, warmup={args.warmup}"
    )
    print_table(
        [
            "rotations",
            "one-by-one mean ms",
            "hoisted mean ms",
            "speedup",
            "mean savings",
            "one-by-one median ms",
            "hoisted median ms",
        ],
        rows,
    )


if __name__ == "__main__":
    main()

Related concepts and guides

• Evaluator operation transitions
• CKKS workload cost model
• Benchmark methodology