Skip to main content

← HomOps Reference

HomRunningSum

Turn values into running totals, inside each period of slots.

RsSlots
RunsServer
Changes shapeNo
Changes scaleYes - managed per mod-switch group
Levels spentlen(stage_sizes) / stages_per_level
RotatesYes - stage plan via stage_sizes
KeysRotation key

What it does​

On the slot axis, the running total stays inside each period of n_slots. It does not run across the whole ring. A smaller period uses fewer levels, because the default depth follows the period.
k is the number of rows in the period. It defaults to n_slots, so the default is one column: a prefix sum of the period. The period is k rows of n_slots / k columns. The sum goes down those rows. Every repeat of the period gets the same totals. The output keeps the input shape and the same n_slots.
If cumsum_axis is a different axis, this is an ordinary cumulative sum on that axis. That path spends no levels.
A padded slot axis is rejected. The axis must hold exactly n_slots values, or whole rings when n_slots is internal_n. HomAxisSum collapses an axis to one total. This operator keeps every intermediate total. Stage plans are on Slots, rotations & stages.

Signature​

HomRunningSum(
    cumsum_axis=None,
    blocks_axis_external=None,
    k=None,
    stage_sizes=None,
    stages_per_level=None,
    rows_budget=None,
)
No set_data. Omit k to sum each full period. Set cumsum_axis to a different axis for a plain cumulative sum.

Parameters​

ParameterTypeDefaultDescription
cumsum_axisint | NoneNoneAxis to sum. None, or the slot axis, sums inside each period. Another axis is a plain cumulative sum and spends no levels.
blocks_axis_externalint | NoneNoneUse this axis as the blocks, instead of separate rings. The slot axis must then fit in one ring, and this axis must not be the slot axis.
kint | NoneNoneNumber of rows in each period. None means n_slots. Must be a power of two that divides n_slots. prod(stage_sizes) must equal k.
stage_sizessequenceNoneThe stage plan: one entry per stage, each entry the stage's group size. Unset means (2,) × log₂(k), the smallest-key plan.
stages_per_levelintNoneHow many stages share one mod-switch. Unset means 1: a mod-switch after every stage.
rows_budgetSequence[int] | NoneNoneAbsolute rows allowed for the internal mod-switches.

Rules that depend on the value​

SettingRuleIf you break it
stage_sizesThe entries must multiply out to k: prod(stage_sizes) == k. When k is omitted, that product must equal input.n_slots.Compilation fails: Product of stage_sizes must be equal to k.
stage_sizes unsetThe default plan (2,) × log₂(k) only exists when k is a power of two.For any other k, write the plan yourself.
stages_per_levelMust divide the number of stages exactly: len(stage_sizes) % stages_per_level == 0. And when you set it, set stage_sizes explicitly too; the default plan is not filled in early enough to divide against.Compilation fails: stages_per_level must divide len(stage_sizes).

Requirements​

  • No padded slot axis. The slot axis must be exactly n_slots long, or a whole number of rings when n_slots is internal_n.
  • Rotation key entries. Every rotation offset in the stage plan must be present in the evaluation key. The compiler derives the exact set; you don't list them yourself.
  • Level headroom. On the slot axis, the chain must have len(stage_sizes) / stages_per_level levels left. See Level budget.
These surface as compilation errors; see Compilation errors.

Shape effect - no​

The output shape equals the input shape. On the slot axis, each period keeps its own running totals.
tensor shape: (num_blocks * n_slots,)
HomRunningSum(k, stage_sizes, stages_per_level)
tensor shape: (num_blocks * n_slots,)same shape; each period has its own totals

Scale effect - yes​

Rule: scale is managed per mod-switch group, exactly as on HomExpand. A group is stages_per_level consecutive stages: the mask multiplies inside a group grow the scale by one prime's worth in total, and the mod-switch at the group boundary brings it back down. The net effect is one mod-switch worth of scale movement per group.
How scale moves through a pipeline is on Ciphertext state - Scale.

Stages & rotations​

The general rules live on Slots, rotations & stages; here is how they apply to HomRunningSum:
QuestionAnswer for HomRunningSum
Where does k come fromConstructor argument. Omit it and k is n_slots: one column, a prefix sum of the period.
Default planstage_sizes unset gives (2,) × log₂(k). Requires k to be a power of two.
Plan constraintprod(stage_sizes) == k
Distinct rotation offsetsΣ (entry − 1) over the plan. Sets the rotation key size.
Roundslen(stage_sizes). Fewer rounds means a faster query.
Levels spentlen(stage_sizes) / stages_per_level, controlled by stages_per_level.
plans.pyPYTHON
# Two stages, one mod-switch: k = 64 rows, plan 8 × 8
HomRunningSum(k=64, stage_sizes=[8, 8], stages_per_level=2)
# 14 offsets, 2 rounds, 1 level

# One group over the whole plan: spend a single level regardless of depth
HomRunningSum(k=k, stage_sizes=plan, stages_per_level=len(plan))

Level budget​

ConfigurationLevels spent
stage_sizes and stages_per_level unsetlog₂(k) on the slot axis. k defaults to n_slots, so a smaller period spends fewer levels. A sum on another axis spends 0.
Explicit planlen(stage_sizes) / stages_per_level
The rotations and mask multiplies spend nothing; only the mod-switch at the end of each group does. How primes are organized in the chain is explained on Level budget - The chain.

Keys​

Rotation key. Every offset in the stage plan needs an entry in the rotation key, derived at compile time from the plan and generated for you during key generation. Wider stages mean more offsets and a bigger key. No square key: the only multiplies are by plaintext masks.

Example​

Standalone running sum​

pipeline.pyPYTHON
from lattica_build.operators import HomRunningSum
from lattica_build.base_classes.hom_pipeline import HomomorphicPipeline
from lattica_build.operators.composite.sequential import SequentialHomOp

K = 64
STAGE_SIZES = [8, 8]        # 8 * 8 = 64 = k
STAGES_PER_LEVEL = 2        # one mod-switch for both stages

pipeline = HomomorphicPipeline(
    hom=SequentialHomOp(
        HomRunningSum(k=K, stage_sizes=STAGE_SIZES, stages_per_level=STAGES_PER_LEVEL),
    ),
    input_shape=(5120,),
)
The plan [8, 8] costs 7 + 7 = 14 rotation offsets over two rounds, and with stages_per_level=2 spends one level.

See also​

  • HomExpand - the other stage-plan operator, same knobs, opposite job (replicate instead of accumulate)
  • HomAxisSum - a full reduction when you only need the total
  • HomSumSlots - sum across slots without keeping prefixes
  • Slots, rotations & stages - stage plans, offsets, and the key-size trade