Late Computation Is All You Need

Or, How Procrastination Became the Hottest Trend in Computing

sometimes too late is just in time

Imagine you’re at a buffet. You pile your plate high with every dish, determined to try them all. Halfway through, you realize you’re full, and half the food goes to waste. Now, what if you only grabbed food when you were actually hungry for it? You’d save space on your plate and reduce waste.

Welcome to the world of late computation — the art of doing things only when you absolutely need to. It’s like the procrastination your high school self perfected, but for computers. And guess what? It’s revolutionizing everything from how we search the internet to how AI models understand language.

The Early Bird vs. The Wise Owl

In the early days of computing, the mantra was simple: Do everything upfront. Compute all possible outcomes, store them, and retrieve them when needed. It was like preparing for every possible conversation you might have at a party — exhausting and inefficient.

But as data grew exponentially, this eager-beaver approach started to crack. Enter late computation, the strategy of deferring computations until they’re absolutely necessary. It’s the wise owl’s approach: why waste energy flapping around when you can wait and swoop in precisely when needed?

ColBERT: Efficient and Effective Information Retrieval

Understanding ColBERT

ColBERT stands for Contextualized Late Interaction over BERT. It’s a retrieval model designed to efficiently search through large document collections while maintaining high relevance in the results.

The Technique Behind ColBERT

Dual Encoder Architecture:

• Document Encoding: Each document in the corpus is processed independently using BERT to produce a set of token embeddings. This encoding is done offline and stored for efficient retrieval.
• Query Encoding: At inference time, the user’s query is encoded using the same BERT model to produce query token embeddings.

Late Interaction Mechanism:

• Similarity Computation: Instead of computing a single vector for documents and queries (as in traditional dense retrieval), ColBERT computes fine-grained interactions between each token in the query and tokens in the document.
• MaxSim Operation: For each query token, ColBERT computes the maximum similarity (e.g., cosine similarity or dot product) with all document token embeddings.
• Aggregation: The similarities are aggregated (typically summed) across all query tokens to produce a final relevance score for the document.

Advantages of ColBERT

• Efficiency: By precomputing document embeddings and storing them, ColBERT avoids re-encoding documents for each query.
• Effectiveness: The late interaction allows for nuanced matching between query and document terms, capturing contextual relevance that simpler models might miss.
• Scalability: ColBERT can handle large-scale retrieval tasks by leveraging efficient indexing structures and parallel computations.

Why Late Computation Matters in ColBERT

• Deferred Computation: The expensive part — calculating interactions between query and document tokens — is deferred until a query is received.
• Resource Optimization: Only relevant computations are performed at inference time, reducing unnecessary processing.
• Dynamic Relevance: The model can adapt to the specific nuances of each query, providing more accurate search results.

Inference-Time Scaling in Large Language Models

The Challenge with LLMs

Large Language Models (LLMs) have billions of parameters and require immense computational resources. Traditionally, enhancing their performance meant increasing model size, leading to:

• Higher Training Costs: Training larger models demands significant computational power and time.
• Inference Inefficiency: Larger models can be slow and resource-intensive during inference, impacting responsiveness and scalability.

The Technique of Inference-Time Scaling

One innovative approach to improving LLM performance without increasing model size is inference-time compute scaling, which dynamically adjusts computational resources during inference based on the model’s uncertainty.

We dont exactly how Open AI did it in O1. But here is one way which is being tried now in the wild —

Entropy-Based Injection of Chain-of-Thought (CoT) Tokens

Monitoring Model Uncertainty:

• Entropy Measurement: The model’s uncertainty is quantified using the entropy of its token probability distribution at each step of generation.
• High Entropy Detection: A high entropy value indicates that the model is uncertain about which token to generate next.

Injecting Chain-of-Thought Tokens:

• Triggering CoT Tokens: When high entropy is detected, the model injects Chain-of-Thought (CoT) tokens into the input sequence.
• Purpose of CoT Tokens: These tokens prompt the model to engage in a more detailed reasoning process, effectively re-evaluating its next steps.

Dynamic Branching and Beam Search:

• Branch Exploration: The model performs a beam search over a dynamically determined set of candidate tokens.
• Candidate Selection: Instead of using a fixed top_k value, candidates are selected using methods like top_p (nucleus sampling) or a minimum probability threshold.
• Multiple Paths: By exploring multiple potential paths, the model increases the likelihood of selecting a more accurate or contextually appropriate token.

Adaptive Computation Resumption:

• Entropy Reduction: As the model generates tokens and the entropy decreases, indicating increased confidence.
• Standard Sampling: Once entropy reaches acceptable levels, the model resumes its standard sampling strategy, conserving computational resources.

This is just one of the techniques. Similar techniques might pop up to utilise and elicit the models generalization knowledge to help in reasoning.

Advantages of Entropy-Based Inference-Time Scaling

• Enhanced Accuracy: By injecting CoT tokens and exploring multiple reasoning paths when uncertainty is high, the model produces more accurate and coherent responses.
• Efficient Resource Utilization: Computational resources are allocated dynamically, focusing effort where it’s most needed.
• No Additional Training Required: This method improves performance without increasing training time or model size.

Why Late Computation Matters in LLMs

• Adaptive Reasoning: Late computation allows the model to perform deeper reasoning only when necessary, improving performance on complex or ambiguous inputs.
• Dynamic Complexity Handling: The model adjusts its computational effort based on the input’s complexity and its own uncertainty.
• Resource Optimization: By deferring and scaling computation during inference, models use resources more effectively, leading to better scalability and user responsiveness.

Procrastination Techniques: The Classics

Late computation isn’t a new kid on the block. It’s been around, wearing different hats, for decades. Let’s take a trip down memory lane.

1. Lazy Evaluation

In languages like Haskell, computations aren’t performed until their results are needed. It’s like deciding not to bake a cake unless someone actually orders a slice.

2. Just-In-Time (JIT) Compilation

Languages like Java and Python use JIT compilation to compile code at runtime. Instead of compiling the entire codebase upfront, they compile parts as they are needed. It’s the software equivalent of assembling IKEA furniture only when guests are about to arrive.

3. Lazy Loading

Web developers know this trick. Images and data are loaded only when they’re about to be viewed. Scroll down a webpage, and images pop up as you go. It’s like not setting the table until someone sits down.

4. Eventual Consistency in Databases

Distributed databases often use eventual consistency, where data updates propagate over time. When you read data, the system may perform extra computations to ensure you get the most recent version. It’s like asking a group of friends what time the movie starts and waiting while they check their messages.

5. Command Query Responsibility Segregation (CQRS)

In software architecture, CQRS separates the methods that read data from those that write data. Writes can be done immediately, but reads might involve computations done at the last moment to present the data in the desired format. It’s the difference between jotting down notes (writes) and crafting a polished essay (reads) when someone asks for it.

Why Late Computation Matters

So why is everyone jumping on the late computation bandwagon? Because it:

• Saves Resources: Don’t compute what you don’t need.
• Enhances Performance: Be faster by doing less upfront and optimizing computations when they matter.
• Improves Scalability: Handle more data and users by spreading out the computational load.
• Adapts Dynamically: Update and respond to new information in real-time.

It’s like being a chef who preps ingredients but cooks dishes to order. Fresh, efficient, and customized.

The Future: Procrastination as a Virtue

As we move into an era of ever-growing data and increasingly complex models, late computation isn’t just a neat trick — it’s a necessity.

Imagine AI models that can:

• Access real-time data: Instead of relying on outdated training data, they fetch the latest information when needed.
• Personalize interactions: Compute user-specific responses on the fly.
• Optimize resource usage: Run efficiently on devices from powerful servers to your smartphone.

Wrapping Up: Embrace Your Inner Sloth

In a world that often glorifies being proactive, late computation teaches us the value of strategic procrastination. It’s not about being lazy; it’s about being smart with our resources and efforts.

So the next time someone chides you for putting things off, just tell them you’re practicing late computation. After all, it’s all you need.