ruvector-attn-mincut

Dynamic min-cut gating as an alternative to softmax attention — prune low-value attention edges via graph theory.

Overview

Standard transformer attention applies softmax uniformly across all Q*K^T logits, forcing every token to attend to every other token. This crate replaces that all-to-all pattern with a graph-theoretic approach: attention logits are modelled as a weighted directed graph, and Dinic's max-flow / min-cut algorithm partitions the graph to prune low-value attention edges. Only surviving edges pass through row-softmax before multiplying by V.

The result is a sparse, structure-aware attention mask that can reduce KV-cache pressure, lower memory footprint, and cut energy-per-sample -- while preserving output coherence within configurable bounds.

Concept: How Min-Cut Replaces Softmax

Standard attention:           Min-cut gated attention:

  Q*K^T --> softmax --> W*V     Q*K^T --> graph --> min-cut --> mask
                                                      |
                                              surviving edges only
                                                      |
                                               softmax --> W*V

1. Graph construction -- Positive logits become weighted directed edges. Non-positive entries are discarded.
2. Min-cut gating -- Dinic's algorithm computes an s-t min-cut. Edges whose removal cost falls below lambda * mean_weight are pruned.
3. Masked softmax -- Pruned positions are set to -INF so softmax zeros them out. The remaining edges are normalized per row.
4. Hysteresis -- A temporal tracker prevents gate masks from oscillating between steps; a flip only commits after tau consecutive agreements.
5. Witness logging -- Every gating decision is hashed with SHA-256 for deterministic verification on a second machine.

Modules

Configuration Parameters

pub struct MinCutConfig {
    pub lambda: f32,           // Sparsity budget (0.0 = keep all, 1.0 = aggressive pruning)
    pub tau: usize,            // Temporal hysteresis steps before a gate flip commits
    pub eps: f32,              // Safety floor -- logits below eps are clamped to zero
    pub seed: u64,             // RNG seed for reproducibility
    pub witness_enabled: bool, // Whether to emit witness logs
}

API Highlights

Build a graph and run gating

use ruvector_attn_mincut::{graph_from_logits, dynamic_min_cut};

// Flattened 3x3 logit matrix (seq_len = 3)
let logits = vec![
    1.0, 0.5, 0.0,
    0.0, 1.0, 0.5,
    0.0, 0.0, 1.0,
];

let graph = graph_from_logits(&logits, 3);
println!("Edges: {}", graph.edges.len()); // only positive logits

let result = dynamic_min_cut(&logits, 3, 0.5, 2, 0.01);
println!("Kept {}/{} edges", result.edges_kept, result.edges_total);
println!("Cut cost: {:.3}", result.cut_cost);

End-to-end gated attention

use ruvector_attn_mincut::{attn_softmax, attn_mincut};

let seq_len = 4;
let d = 8;
let q = vec![0.1f32; seq_len * d];
let k = vec![0.1f32; seq_len * d];
let v = vec![1.0f32; seq_len * d];

// Baseline
let baseline = attn_softmax(&q, &k, &v, d, seq_len);

// Min-cut gated (lambda=0.5, tau=2, eps=0.01)
let gated = attn_mincut(&q, &k, &v, d, seq_len, 0.5, 2, 0.01);

println!("Output length: {}", gated.output.len());        // seq_len * d
println!("Edges kept: {}", gated.gating.edges_kept);
println!("Edges total: {}", gated.gating.edges_total);

Temporal hysteresis

use ruvector_attn_mincut::HysteresisTracker;

let mut tracker = HysteresisTracker::new(3); // tau = 3 steps

let mask_a = vec![true, true, false, true];
let stabilized = tracker.apply(&mask_a);     // first call passes through

// Subsequent calls require tau consecutive disagreements to flip
let mask_b = vec![false, true, true, true];
let still_a = tracker.apply(&mask_b);        // not flipped yet (1/3)

Witness logging

use ruvector_attn_mincut::{hash_tensor, witness_log, WitnessEntry};

let q_hash = hash_tensor(&[1.0, 2.0, 3.0]);
let entry = WitnessEntry {
    q_hash,
    k_hash: hash_tensor(&[4.0, 5.0, 6.0]),
    keep_mask: vec![true, false, true, true],
    cut_cost: 1.5,
    lambda: 0.5,
    tau: 2,
    eps: 0.01,
    timestamp: 1700000000,
};
let jsonl_line = witness_log(&entry);

Expected Benefits

Dependencies

• serde / serde_json -- serialization for configs and witness entries
• sha2 -- SHA-256 hashing for deterministic witness chain

Architecture

attn_mincut --> coherence metrics --> profiler CSV --> analysis

All public types implement Debug and Clone. Config and result types implement Serialize / Deserialize for JSON round-tripping.

Step 1: Configure and run gated attention

use ruvector_attn_mincut::{MinCutConfig, attn_softmax, attn_mincut};

let config = MinCutConfig {
    lambda: 0.5,     // moderate pruning
    tau: 2,          // 2-step hysteresis
    eps: 0.01,       // filter near-zero logits
    seed: 42,
    witness_enabled: true,
};

let (seq_len, d) = (64, 128);
let q = vec![0.1f32; seq_len * d];
let k = vec![0.1f32; seq_len * d];
let v = vec![1.0f32; seq_len * d];

let baseline = attn_softmax(&q, &k, &v, d, seq_len);
let gated = attn_mincut(&q, &k, &v, d, seq_len, config.lambda, config.tau, config.eps);

println!("Pruned {}/{} edges",
    gated.gating.edges_total - gated.gating.edges_kept,
    gated.gating.edges_total);

Step 2: Measure coherence

use ruvector_coherence::{quality_check, evaluate_batch};

let result = quality_check(&baseline.output, &gated.output, 0.99);
println!("Cosine sim: {:.4} | Passes: {}", result.cosine_sim, result.passes_threshold);

Step 3: Profile and export

use ruvector_profiler::{compute_latency_stats, write_results_csv};
// ... collect timing data, export CSV

Step 4: Run the benchmark grid

./scripts/run_mincut_bench.sh --samples 1000 --lambda "0.3 0.5 0.7" --tau "0 2"

Related Crates

License

Licensed under the MIT License.