Rotation hoisting

Example source: examples/07_rotation_hoisting_benchmark.py

This example benchmarks independent rotations against a grouped request over the same source and exact keys. The tutorial explains which decomposition and preparation work can be shared and how to interpret the timings.

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.

Run the benchmark

python examples/07_rotation_hoisting_benchmark.py \
  --preset slots32768-scale40-levels34-int64 \
  --counts 4,8,16 \
  --warmup 5 \
  --runs 20

Start with fewer runs when checking a new environment:

python examples/07_rotation_hoisting_benchmark.py \
  --preset slots8192-scale40-levels7-int64 \
  --counts 2,4 \
  --warmup 1 \
  --runs 3

1. Provision every exact 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)

Both request the same set of rotated ciphertexts. The sequence-form API gives the engine a direct opportunity to hoist input-dependent work shared by all requested steps.

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 exact 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.

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.

Do not mix unrelated optimizations into a scaling comparison

When comparing devices, ranks, or partition strategies, keep hoisting, NTT backend, key residency, warmup, and synchronization policy fixed. A faster result is otherwise not attributable to one variable.

Complete runnable source

#!/usr/bin/env python3

"""Benchmark grouped rotation hoisting against independent rotations.

Example:
    python examples/07_rotation_hoisting_benchmark.py --preset slots32768-scale40-levels34-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-levels34-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("--level", 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, level=args.level)
    sync_if_cuda(engine.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=engine.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}, level={args.level}, 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 a workload correctly