Skip to main content

← HomOps Reference

HomRunningSum

Turn values into running totals: each position becomes the sum of itself and everything before it.

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​

HomRunningSum computes a prefix sum over encrypted data: after it runs, each position holds the cumulative total of all positions up to and including itself. The slot-tree path takes k (slot span; default full n_slots) plus stage_sizes / stages_per_level. The axis-based path uses cumsum_axis and blocks_axis_external.
Where HomAxisSum collapses an axis to a single total, HomRunningSum keeps every intermediate total. That is what selection logic needs: in the cosine-similarity pipeline, it runs on the 0/1 selector produced by the threshold polynomial, turning match flags into match positions.
The accumulation across slots is built from rotations, so HomRunningSum takes a stage plan, the same stage_sizes / stages_per_level pair as HomExpand. If stages, offsets, and rounds are new to you, read Slots, rotations & stages first; this page only states how the rules land on this operator.

Signature​

HomRunningSum(
    cumsum_axis=None,
    blocks_axis_external=None,
    k=None,
    stage_sizes=None,
    stages_per_level=None,
    rows_budget=None,
)
HomRunningSum takes no weights, so there is no set_data call. The slot-tree path uses k=None (full slot count) by default; axis-based cumsum is selected with cumsum_axis.

Parameters​

ParameterTypeDefaultDescription
cumsum_axisint | NoneNoneAxis to cumulatively sum. When set, enables the axis-based cumsum path.
blocks_axis_externalint | NoneNoneAxis that describes block structure for the axis-based cumsum path.
kint | NoneNoneSlot span to accumulate. None means the full slot count (n_slots). When set, 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 the full slot count.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​

  • 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. The chain must have len(stage_sizes) / stages_per_level levels left when the operator runs. See Level budget.
These surface as compilation errors; see Compilation errors.

Shape effect - no​

The output shape equals the input shape. The values are redistributed into running totals; the layout stays as it was.
pt_shape: (num_blocks * n_slots,)
HomRunningSum(k, stage_sizes, stages_per_level)
pt_shape: (num_blocks * n_slots,)same shape, values now cumulative

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 to accumulate over the full slot count; pass an explicit span to run the prefix sum within groups of width k.
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, 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) - one per stage
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