Staff AI Engineer Interview Preparation Guide - Lyft

Direct answer
Favor simple heuristics or manual tuning when interpretability of the tuning process itself matters (regulatory or team-trust reasons), when time-to-production is tight and a well-known reasonable default is likely close enough, when the model or dataset is cheap and small enough that a quick manual pass is genuinely faster than setting up an automated search, or when the team lacks the maintenance capacity to own an AutoML pipeline long-term.

Structured elaboration
Interpretability: a manually-chosen, well-understood set of hyperparameters is easier to defend and explain (to auditors, to a new team member, to yourself six months later) than "whatever an automated Bayesian search happened to converge on," which matters more in regulated or high-stakes settings. Time-to-production: for a first version of a model under real deadline pressure, a few well-chosen manual configurations informed by domain experience or a quick heuristic (a known-good default learning rate, a standard tree depth for this kind of tabular problem) often gets you 90% of the way there in a fraction of the time an automated search would take. Compute cost: automated search, especially Bayesian optimization or multi-fidelity methods, has real setup and infrastructure overhead; for a one-off, small model, that overhead can exceed the time a knowledgeable person would spend manually trying 3-4 sensible configurations. Long-term maintainability: an AutoML pipeline itself needs to be maintained, monitored, and occasionally debugged; a team without the capacity to own that infrastructure may be better served by simpler, more transparent manual tuning, at least until the model's importance justifies the investment.

Worked example
A small internal reporting model needed within a week, with a modest dataset and low stakes if it's not perfectly tuned: a manual pass over 3-4 sensible configurations based on known defaults for this model family is likely the right call, versus standing up a Bayesian-optimization pipeline whose setup time alone could exceed the entire project's timeline.

Trade-offs & pitfalls
The risk of defaulting to manual tuning out of habit, even once a model becomes important enough (high business value, frequent retraining, many hyperparameters) that automated search's efficiency gains clearly outweigh its setup cost, is leaving real performance on the table; revisit this choice as the model's stakes and retraining frequency grow, rather than treating the initial "manual is fine for now" decision as permanent.

OKRs are goal-setting outcomes: ambitious, time-bound objectives with measurable key results that describe success. KPIs are ongoing metrics that track business or product health (e.g., retention, latency, conversion). OKRs drive change; KPIs measure sustained performance.

How I’d align an AI team’s quarterly OKRs with product KPIs:

• Clarify product priority (e.g., increase engagement or reduce churn).
• Map AI levers to product KPIs (e.g., model relevance → retention, latency → engagement).
• Define an OKR that advances the product priority and pick KRs that are leading indicators plus implementation milestones.
• Coordinate with PM/analytics to ensure metric definitions, instrumentation, and ownership.
• Run weekly checkpoints, A/B tests, and a post-quarter review tying changes to KPI movement.

Example (AI Engineer, quarter):
Objective: Improve the virtual assistant’s helpfulness to increase user engagement and satisfaction.
Key Results / KPIs:

1. Increase task completion rate (end-to-end success rate) from 62% → 75% (product KPI showing feature effectiveness).
2. Raise weekly active users (WAU) for the assistant by 15% (engagement KPI).
3. Reduce median inference latency from 420ms → 250ms and keep cost per 1k requests ≤ budget threshold (performance/cost KPIs).

Why these work: KR1 is the direct quality signal from model improvements, KR2 shows product-level impact, KR3 ensures the solution is performant and scalable so gains are deployable.

I prefer high decision-making autonomy for day-to-day experimental choices (hyperparameters, small architecture tweaks, feature engineering) as long as goals, constraints, and risk boundaries are agreed upfront with my manager. I escalate only when decisions affect product requirements, budget, or release timelines.

Situation: On a text-classification proof-of-concept, our baseline fine-tuned BERT reached 78% F1, but training was slow and inference latency was too high for the target app.

Task: Improve latency and maintain or improve F1 without delaying the sprint.

Action:

• I evaluated two options: distillation to DistilBERT vs pruning the full model. I chose knowledge distillation because it promised quicker inference with minimal retraining overhead.
• I implemented a distillation pipeline (teacher: original BERT, student: smaller transformer with 6 layers), tuned temperature and student learning rate, and used a combined loss (CE + KL).
• Trained overnight, validated on holdout set, and ran latency benchmarks on target hardware.

Result: Student model achieved 76.5% F1 (small drop) but reduced inference latency by 3.5x and memory by 60%, meeting product constraints. I documented the experiment, pushed code and checkpoints to the repo, and sent a concise summary to my manager and stakeholders with: motivation, methods, metric table, and trade-offs. In the follow-up meeting I proposed next steps (further distillation or quantization). The team approved deploying the student model for a pilot.

This approach balances speed, ownership, and transparency: I act independently within agreed boundaries and communicate results and risks promptly.

Direct answer

NVIDIA Tensor Cores are specialized hardware units, distinct from a GPU's general-purpose CUDA cores, built specifically to accelerate matrix multiply-accumulate operations (the dominant computation in deep learning) at much higher throughput than general-purpose cores achieve, generally requiring reduced-precision numeric formats (fp16, bf16, tf32, or int8) to reach their full speed advantage.

Structured elaboration

• What Tensor Cores do: they perform small matrix multiply-and-accumulate operations (e.g. multiplying two small matrix tiles and adding the result to an accumulator) as a single hardware operation, far more efficiently than performing the equivalent sequence of individual multiply-and-add instructions on general-purpose CUDA cores.
• Why they need specific precisions: Tensor Cores' hardware design is built around specific input/accumulation precision combinations (e.g. fp16 or bf16 inputs, accumulating in fp32 for numerical stability); using standard fp32 for both inputs and accumulation generally doesn't engage the fastest Tensor Core paths (some GPU generations support a reduced-precision fp32 variant, tf32, specifically to get partial Tensor Core benefit without fully switching to fp16/bf16), which is a large part of why mixed-precision training (discussed extensively elsewhere in this topic) is so tightly linked to actually realizing a modern GPU's advertised peak performance.
• What changes in model implementation and numerics: using Tensor Cores effectively generally means adopting mixed-precision training (autocast-style automatic casting, or explicit dtype management) so that the matrix-multiplication-heavy operations (linear layers, convolutions, attention) actually run in a Tensor-Core-compatible precision, while numerically sensitive operations may still need to stay in fp32; this is not automatic just from having Tensor-Core-capable hardware, it requires the software (and specifically the numeric-precision choices in the code) to actually engage them.
• Practical magnitude: Tensor Cores can offer several times (often cited around 4-8x, generation- and precision-dependent) the throughput of the same GPU's general-purpose CUDA cores for the specific matrix-multiply-accumulate operations they accelerate, which is why nearly all large-scale deep learning training today deliberately uses mixed precision specifically to capture this hardware advantage, not merely for the memory savings mixed precision also happens to provide.
• Tile shapes: Tensor Cores compute fixed-size small matrix-multiply tiles per instruction (e.g. a 16x16x16 fp16 multiply-accumulate as the classic WMMA fragment shape, with newer generations supporting additional shapes and precisions including sparsity-aware tiles); matrix dimensions that aren't already multiples of the relevant tile size get padded up to the next multiple internally (or by the framework/library), so choosing model dimensions (hidden size, head dimension, vocabulary size) as multiples of 8 (fp16/bf16) or 16 (int8) avoids wasted padding compute and keeps the kernel on the fastest Tensor Core path.
• Preferred data layouts: Tensor Core kernels generally prefer a channels-last-style memory layout (e.g. NHWC for convolutions, or contiguous inner dimensions matching the tile's fastest-varying axis for matmuls) over the classic channels-first NCHW layout, since it lets the hardware read a tile's worth of contiguous, tile-aligned memory in fewer, more efficient transactions; using a suboptimal layout can silently fall back to a slower, non-Tensor-Core or poorly-tiled path even when the precision is otherwise correct.
• Fused matmul+epilogue ops benefit most: the operations that gain the most from Tensor Cores are large matrix multiplies immediately followed by a small "epilogue" op (bias add, activation function, or residual accumulation) fused into the same kernel, since fusing avoids writing the raw matmul output to HBM and reading it back just to apply the epilogue in a second kernel; libraries like cuBLASLt and CUTLASS expose these fused matmul+epilogue kernels directly, and it's this combination (large tiled matmul plus fused elementwise epilogue), more than an unfused matmul alone, that captures the largest share of Tensor Cores' theoretical throughput advantage in practice.

Worked example

A transformer's linear layers (the majority of its FLOPs) run as large matrix multiplications; training the same model in full fp32 (not engaging Tensor Cores' fastest paths on many GPU generations) versus in fp16/bf16 with autocast (engaging Tensor Cores fully) can show a measured multi-fold difference in training throughput on the same hardware, a difference attributable specifically to Tensor Core engagement, distinct from (though it compounds with) the separate memory-bandwidth benefit of moving smaller, lower-precision tensors.

Trade-offs & pitfalls

A common misconception is assuming a GPU with Tensor Cores automatically gets their speed benefit regardless of the precision used in the code; without deliberately using a Tensor-Core-compatible precision (via mixed precision training or explicit dtype choices), a model trained entirely in fp32 on Tensor-Core-capable hardware may leave a substantial fraction of that hardware's actual throughput potential unused.

Direct answer

The fix is not to write three separate explanations from scratch, it is to layer one explanation: a headline takeaway for anyone who only reads the first line, a short rationale for someone who needs to act on it, and full technical detail for someone who needs to verify it. Each layer has to be consistent with the ones below it, so a reader who goes deeper never finds something that contradicts what the headline told them.

Structured elaboration

I build the layers in this order, from the inside out, so the technical detail is always the source of truth the other layers are compressed from:

1. Technical layer (data scientists, engineers). Full detail: what changed, how it was measured, calibration, known limitations, and how to reproduce it. This layer is written first because everything above it has to be a faithful compression of it, not a separate narrative.
2. Operational layer (product managers). What the finding means for specific user segments, why it happened in terms they can act on (plain-language feature drivers, not raw importance scores), and what to actually do about it. This layer names the same limitations as the technical layer, just without the statistical vocabulary.
3. Headline layer (executives). One sentence stating the business-relevant result, one sentence stating the main risk or limitation, and a clear recommendation. No new claims appear here that are not traceable back to the technical layer.

The trust problem in the original feedback usually is not that the technical layer was wrong, it is that only the technical layer existed, so a PM had to either decode it themselves or discard it. Building the other two layers on top of the same underlying analysis, rather than writing a separate simplified story, is what keeps the versions correct and consistent with each other.

Worked example

After an A/B test, my model-explanation report was flagged as too technical to act on. I kept the full technical write-up (feature importance detail, calibration plot, data lineage) as the base layer, then built two more layers from it rather than writing something new:

• PM brief: "The model is now flagging a specific group of recently inactive users as higher churn risk than before. The main signal driving that is a drop in weekly logins over the last two weeks, translated from the underlying feature importance rather than shown as a raw score. Recommended action: route this group into the existing win-back flow and watch weekly login rate as the leading indicator that it is working."
• Executive headline: "The updated model identifies at-risk users earlier based on login activity. Main risk: it has not yet been validated on users outside our two largest markets. Recommendation: route flagged users to the existing win-back flow and re-check performance in other markets before wider rollout."

Before sending either version, I checked it with one PM and one exec, not to soften the content, but to catch any place where my compression had accidentally introduced a claim the technical layer did not support.

Trade-offs and pitfalls

• The biggest risk in layering is drift: if the headline layer is edited later without updating the technical layer underneath it (or vice versa), the versions stop agreeing, and that inconsistency is exactly what destroys trust once someone notices it. Whoever owns the technical layer should own regenerating the layers above it.
• Compressing too aggressively for executives can turn a real, bounded limitation into something that reads as fully resolved. The one-sentence risk statement has to survive contact with the technical detail, not just sound reassuring.
• Different audiences sometimes genuinely need different actions recommended, not just different levels of detail; if the PM-layer action and the executive-layer recommendation would actually differ, that has to be reconciled explicitly rather than papered over by omission in one of the layers.
• This is about presenting the same underlying finding at different levels of detail, not about persuading anyone toward a particular business decision; if a layer starts emphasizing certain facts specifically to win support for a preferred outcome, it has stopped being a clarity tool.

Situation: Our production classifier is susceptible to targeted adversarial perturbations causing wrong, potentially harmful predictions.

Mitigation plan (detection, runtime defenses, training, operations):

1. Detection of adversarial inputs

• Ensemble anomaly detector: monitor input-level statistics (L1/L2 distance to training manifold via autoencoder or feature MD from penultimate layer). Flag inputs with high reconstruction error or low likelihood.
• Model-internal consistency checks: compare logits/confidence vs. calibrated thresholds; detect sharp gradients via input-gradient norm.
• Deploy a lightweight detector model trained on adversarial vs. benign examples (use FGSM/PGD/CW) as a binary signal.
• Metrics: false positive rate < X%, detection latency < Y ms. Log all flagged inputs for forensics.

2. Runtime defenses

• Input preprocessing: apply randomized input transformations (bit-depth reduction, JPEG compression, small Gaussian blur) and use majority voting across transforms to reduce perturbation effectiveness. Balance with accuracy loss.
• Randomized smoothing: wrap base classifier with Gaussian/noise smoothing to provide certified L2-robustness radius for each prediction. Use randomized smoothing for critical classes where certification matters.
• Test-time ensembling: average predictions across stochastic augmentations; if high variance, mark as suspicious.

3. Adversarial training

• Integrate adversarial examples into training with Projected Gradient Descent (PGD) or TRADES to trade off robustness and accuracy. Use curriculum: start with small eps, increase.
• Class-conditional and targeted-attack augmentation to cover real-world threat models; include physically-realistic transforms (print-and-scan).
• Regularly retrain with new adversarial examples harvested from production detector logs.

4. Operational practices

• Monitoring: dashboards for detection rates, sudden spikes in flagged inputs, drift in input distribution, changes in certified radii (for smoothing).
• Alerting & playbook: automated throttling of flagged inputs, route suspicious requests to fallback model or human review, escalate alerts on correlated anomalies.
• Canarying: roll-out defenses in canary traffic; A/B measure clean accuracy, robustness, latency.
• Logging & privacy: store salted embeddings and minimal metadata for incident analysis; ensure compliance.
• Red-team & continuous evaluation: scheduled adversary simulations, automated adversarial test-suite in CI (with metrics: robust accuracy at eps).
• Governance: define threat model, acceptable risk, and response SLA.

Trade-offs:

• Randomized smoothing increases latency and requires many samples for certification; adversarial training can reduce clean accuracy. Tune based on criticality.

Outcome: layered (detect + harden + monitor + respond) defenses reduce attack surface, enable quick detection and recovery, and maintain measurable robustness guarantees.

Situation: At a previous company, launching a content-recommendation model for a high-traffic consumer app surfaced a real disagreement: engineering and product wanted the reward model optimized purely for engagement and retention, while the safety team flagged that the same objective was amplifying borderline and harmful content, risking a launch delay and real user harm.

Task: As the ML engineer leading the model, I needed to resolve this disagreement and land on a single reward objective that balanced business value, safety, and engineering constraints, with genuine stakeholder buy-in, not just a compromise handed down from one side.

Action: I convened a working session with product, two safety leads, two engineers, and a legal/privacy representative to agree explicit success criteria and non-negotiables up front (no amplification of harmful content, a measurable engagement uplift target, and hard latency and infrastructure limits). I proposed a multi-objective reward combining predicted engagement with a safety penalty from a content-risk classifier, and backed the proposal with data rather than opinion: I trained three variants (utility-heavy, balanced, safety-heavy), evaluated them offline on engagement and safety-score distributions plus an estimated business impact via counterfactual policy evaluation, and made sure the safety penalty itself was cheap enough (a simple risk-bucket lookup) to fit our latency budget. I then facilitated a decision matrix mapping the concrete trade-offs (product KPIs, an explicit maximum acceptable share of high-risk impressions, operational cost) so the group was choosing among quantified options rather than debating in the abstract, and recommended the balanced weighting with one adaptive twist, increasing the safety weight automatically whenever the safety classifier's own confidence was low. We agreed a staged rollout with strict monitoring, a kill switch, and weekly cross-team reviews before committing to the decision.

Result: The balanced model delivered a 6% retention lift over the baseline while cutting high-risk content impressions by 70% relative to the utility-first variant, and the staged rollout with an automated kill switch meant no user-facing harm occurred during the transition. Every stakeholder group got something concrete: safety got hard constraints and ongoing monitoring, product got a measurable engagement gain, and engineering had a design that fit within the latency and compute budget.

Trade-offs I would flag: A quantitative Pareto comparison across the three variants was what actually resolved the disagreement, not further discussion of principles in the abstract, having concrete offline numbers for each candidate objective converted an ethically-charged debate into a decision among clearly quantified options. The adaptive safety-weight mechanism (raising the safety weight when the classifier's confidence dropped) was a deliberate hedge against exactly the failure mode the safety team was worried about, an over-confident but wrong safety classifier silently approving harmful content, and building that hedge in up front was part of why the safety team accepted the compromise.

Direct answer: A production feature-store architecture at real scale needs a dual-store design (a batch-optimized offline store and a latency-optimized online store) fed by both batch and streaming ingestion, unified behind a serving API and a shared metadata/lineage layer, with the hardest engineering constraint being keeping the two stores consistent, not building either one in isolation.

Structured elaboration:

• Ingestion: batch jobs for slow-changing, high-volume sources (a nightly warehouse ETL); streaming jobs (a framework like Flink or Spark Structured Streaming) for features that need near-real-time updates.
• Offline store: a columnar warehouse or data lake table, optimized for large scans over history for training-set construction; this is where point-in-time-correct joins between features and labels happen.
• Online store: a low-latency key-value store (in-memory or a fast KV database), optimized for single-entity lookups under sub-50ms targets at high query volume.
• Materialization: the job(s) that populate both stores from the same underlying transformation logic, so the two stores are two VIEWS of one computation, not two independent implementations.
• Serving API: the client-facing interface (see the client-library-API question elsewhere in this topic) that abstracts which store is being read.
• Versioning and lineage: every feature value traceable to the code and data version that produced it.
• Access control: role-based restrictions, particularly for personally-identifiable-information (PII)-adjacent features.

Worked example: A recommendation model needs both batch-computed features (a user's lifetime purchase history, updated daily and used heavily in training) and low-latency online features (what the user clicked in the last 5 minutes, needed for real-time re-ranking). The architecture computes both from the same event stream: the streaming path continuously updates the online store for the fast-moving signals, while a batch job periodically materializes the offline store's historical snapshots for training, and both derive from the same underlying transformation definitions so a change to the feature's logic updates both paths together rather than requiring two separate code changes.

Trade-offs and pitfalls: The single most consequential design decision is technology choice at each layer (which key-value store, which warehouse format), and the trade-offs are genuinely workload-specific: a KV store optimized for point lookups is a poor fit for the offline store's scan-heavy access pattern, and vice versa, which is exactly why the dual-store split exists rather than one store trying to serve both needs.

Layer normalization placement, before the sublayer (pre-norm) or after the residual add (post-norm), materially changes how gradients flow through a deep stack, and the difference gets more important the deeper the model.

Core difference

• Post-norm (the original Transformer): LayerNorm is applied AFTER adding the sublayer's output to the residual stream, so the value going into the next layer is norm(x + sublayer(x)).
• Pre-norm: LayerNorm is applied BEFORE the sublayer, and the raw (unnormalized) sublayer output is added directly to the residual stream: x + sublayer(norm(x)).
  This placement changes whether the residual "highway" that carries information (and gradients) across layers ever gets rescaled by a normalization step.

Gradient flow and why it matters at depth

• In pre-norm, the residual path itself is never passed through LayerNorm, only what feeds INTO each sublayer is normalized. That keeps the gradient path close to an identity map through many layers, so gradients neither vanish nor explode even at very large depth (100+ layers).
• In post-norm, the residual sum is passed through LayerNorm at every layer, so gradients get repeatedly rescaled on their way back through the network. At shallow-to-moderate depth this is fine (it's the original design), but as depth grows, that repeated rescaling makes gradients harder to control, and post-norm models become much more prone to unstable or exploding gradients without careful warmup.

Convergence behavior and practical training

• Pre-norm models tend to converge faster and more reliably at depth, and tolerate larger learning rates and shorter (or no) warmup.
• Post-norm can sometimes reach slightly better final metrics at shallow-to-moderate depth (the extra normalization after the residual add keeps activation statistics well-behaved for the next layer), but it is far more sensitive to how training is set up: without careful learning-rate warmup and initialization scale, a deep post-norm model can simply fail to train.

Optimizer interactions: Adam vs LAMB

• Adam's per-parameter adaptive scaling reduces (but does not remove) sensitivity to how normalization is placed. With pre-norm, a standard AdamW plus a moderate learning rate and short warmup is usually robust out of the box.
• LAMB was built for large-batch training and applies layer-wise adaptive scaling to updates. That extra scaling can make post-norm more workable at scale than Adam alone would, but it doesn't replace the structural gradient-flow advantage pre-norm has: pre-norm combined with LAMB is generally the more stable combination for very large-batch, large-depth training.
• Weight decay handling (decoupled, as in AdamW), epsilon choice, and bias-correction timing all interact with normalization placement too. In practice, AdamW plus pre-norm is the more forgiving default; post-norm asks a lot more of your hyperparameter tuning.

Initialization sensitivity

• Pre-norm is comparatively forgiving of initialization: standard Xavier/He initialization plus a modest warmup is usually enough, even at large depth.
• Post-norm is much more sensitive to the initial weight scale. Get it wrong and, in a deep stack, the model can diverge in the first few hundred steps before warmup has a chance to help. This is why post-norm setups at scale typically pair it with specific initialization schemes (e.g., scaling initial weights down by a depth-dependent factor) rather than vanilla initialization.

Practical recommendation

• Default to pre-norm for very deep models: it needs less hyperparameter babysitting and is more robust across optimizer choices.
• Only choose post-norm (e.g., for compatibility with an existing checkpoint, or a specific claimed final-performance edge) if you're willing to invest in longer LR warmup, smaller initial learning rates, careful initialization scaling, and probably LAMB or a similarly adaptive optimizer.

Experiments to validate these claims at scale

1. Depth sweep: train identical encoder stacks at depths like {6, 12, 24, 48, 96, 192} with both placements under matched hyperparameters; track training loss, per-layer gradient norms, and whether/when training diverges.
2. Initialization and warmup ablation: at a large depth (e.g., 96+ layers), grid over learning rate, warmup length (0, 1k, 10k, 50k steps), and a couple of initialization schemes; compare convergence and final validation metric between pre- and post-norm.
3. Optimizer comparison: at the same large depth, compare AdamW vs LAMB (and plain SGD-momentum as a baseline) under both norm placements, measuring throughput, peak memory, and final task performance.
4. Gradient diagnostics: log per-layer gradient norms (and, if feasible, an estimate of the Jacobian's singular values) throughout training to directly connect observed stability or instability back to the gradient-flow argument above.

Together, these experiments would confirm whether the depth at which post-norm starts to struggle matches what the gradient-flow argument predicts, and whether LAMB genuinely closes the gap with pre-norm or only delays the same failure mode to a larger depth.

Approach summary

• Model tiling by column profiles (3 rows → 2^3=8 states). Build an 8×8 transfer matrix T where T[s→t]=1 if you can legally place dominoes in the next column(s) to move profile s to t.
• Count ways for n columns by computing (T^n)[start, end]. Start=end=empty profile (0). Because odd n yields 0, T connects parity; you can also restrict to even steps.
• The 8×8 matrix has minimal characteristic polynomial reducing to an order-4 recurrence for a_n (a_n = number of tilings of width n): a_n = 4 a_{n-2} − a_{n-4} for even n, with a_0=1, a_2=3, a_4=11, a_6=41. Use this 4-term linear recurrence to compute in O(k^3 log n) with k=4 or O(k^2 log n) with Kitamasa.

How to build transfer matrix

• Enumerate profiles as 3-bit masks (0..7), where bit=1 means cell is occupied from previous column.
• For every mask s, DFS fill current column with vertical dominoes and horizontal placements that extend to next column, producing resulting mask t. Each successful tile placement increments T[s][t].

Compute answer

1. Matrix exponentiation (simple): compute T^n mod M by binary exponentiation. Answer = (T^n)[0][0]. Complexity O(8^3 log n) ≈ O(512 log n).
2. Linear recurrence (faster): derive recurrence coefficients (from characteristic polynomial or by computing first 8 terms and using Berlekamp–Massey). Here we get order-4: a_n = 4 a_{n-2} − a_{n-4}. Reduce to even-indexed sequence b_m = a_{2m}, recurrence b_m = 4 b_{m-1} − b_{m-2}. Use 2×2 matrix or Kitamasa to get b_{n/2} in O(log n). Complexity O(k^3 log n) with k=2 here.

Fast exponentiation example (recurrence 2×2)

• For b_m = 4 b_{m-1} − b_{m-2}, state vector [b_m, b_{m-1}]^T = R * [b_{m-1}, b_{m-2}]^T with R = [[4, -1],[1,0]] mod M. Compute R^(n/2) by binary exponentiation and multiply by base [b_1,b_0]=[3,1].

Mod details & edge cases

• Work modulo M=1_000_000_007; ensure negative coefficients handled by adding M.
• If n is odd, return 0.
• For n up to 1e6, log n ~ 20 so exponentiation is trivial. For very large n (1e18+), same methods apply.

Why minimal state 4

• The full profile transfer is 8 states, but parity and symmetry reduce independent degrees to 4; characteristic polynomial factorization or Berlekamp–Massey on first terms yields order-4 (and for even-indexed b_m order-2), allowing smaller matrices and faster exponentiation.

This gives an O(log n) algorithm either via 8×8 matrix exponentiation or via the reduced 2×2/4×4 recurrence exponentiation (preferred: use the 2×2 recurrence on b_m for best speed and simplicity).