You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by at...@apache.org on 2025/04/18 10:09:15 UTC

(lucene) 01/09: Initial commit without triggering changes

This is an automated email from the ASF dual-hosted git repository.

atri pushed a commit to branch index_binning_changes
in repository https://gitbox.apache.org/repos/asf/lucene.git

commit 8e6ff8fffa787fa1230f52b6e35471c9ab45d8d4
Author: Atri Sharma <at...@192.168.1.25>
AuthorDate: Fri Apr 18 01:02:37 2025 +0530

    Initial commit without triggering changes
---
 .../apache/lucene/codecs/ApproximateDocBinner.java |  61 ++++++
 .../lucene/codecs/ApproximateDocGraphBuilder.java  | 139 ++++++++++++++
 .../org/apache/lucene/codecs/BinMapReader.java     | 110 +++++++++++
 .../org/apache/lucene/codecs/BinMapWriter.java     | 116 ++++++++++++
 .../apache/lucene/codecs/BinQualityMetrics.java    |  51 +++++
 .../lucene/codecs/DocBinningGraphBuilder.java      | 126 +++++++++++++
 .../org/apache/lucene/codecs/DocGraphBuilder.java  | 185 +++++++++++++++++++
 .../org/apache/lucene/codecs/FieldsLeafReader.java | 172 +++++++++++++++++
 .../lucene/codecs/InMemorySparseEdgeGraph.java     |  79 ++++++++
 .../org/apache/lucene/codecs/SparseEdgeGraph.java  |  52 ++++++
 .../codecs/lucene103/Lucene103PostingsFormat.java  | 138 +++++++++++++-
 .../apache/lucene/index/BinScoreLeafReader.java    |  56 ++++++
 .../org/apache/lucene/index/BinScoreReader.java    |  53 ++++++
 .../java/org/apache/lucene/index/BinScoreUtil.java | 134 ++++++++++++++
 .../lucene/search/AnytimeRankingCollector.java     | 109 +++++++++++
 .../search/AnytimeRankingCollectorManager.java     |  69 +++++++
 .../lucene/search/AnytimeRankingSearcher.java      |  52 ++++++
 .../apache/lucene/search/BinBoostCalculator.java   |  95 ++++++++++
 .../apache/lucene/util/HeuristicSLAEstimator.java  | 205 +++++++++++++++++++++
 .../java/org/apache/lucene/util/SLAEstimator.java  |  27 +++
 20 files changed, 2028 insertions(+), 1 deletion(-)

diff --git a/lucene/core/src/java/org/apache/lucene/codecs/ApproximateDocBinner.java b/lucene/core/src/java/org/apache/lucene/codecs/ApproximateDocBinner.java
new file mode 100644
index 00000000000..ac889998d8c
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/ApproximateDocBinner.java
@@ -0,0 +1,61 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs;
+
+import java.io.IOException;
+
+/** Approximate binning for documents using locality-sensitive hashing over sparse edge graph. */
+public final class ApproximateDocBinner {
+
+  private ApproximateDocBinner() {}
+
+  /**
+   * Assign documents to bins approximately based on edge distribution.
+   *
+   * @param graph sparse edge graph
+   * @param maxDoc number of documents
+   * @param numBins number of bins (must be power of 2)
+   * @return bin assignments for each document
+   */
+  public static int[] assign(SparseEdgeGraph graph, int maxDoc, int numBins) throws IOException {
+    if (Integer.bitCount(numBins) != 1) {
+      throw new IllegalArgumentException("numBins must be a power of 2");
+    }
+
+    final int[] bins = new int[maxDoc];
+    final int mask = numBins - 1;
+
+    for (int docID = 0; docID < maxDoc; docID++) {
+      int[] neighbors = graph.getNeighbors(docID);
+      float[] weights = graph.getWeights(docID);
+      int hash = 0;
+      for (int i = 0; i < neighbors.length; i++) {
+        hash = mix(hash, neighbors[i], weights[i]);
+      }
+      bins[docID] = hash & mask;
+    }
+
+    return bins;
+  }
+
+  private static int mix(int h, int neighbor, float weight) {
+    int x = neighbor * 31 + Float.floatToIntBits(weight);
+    h ^= Integer.rotateLeft(x, 13);
+    h *= 0x5bd1e995;
+    return h;
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/ApproximateDocGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/codecs/ApproximateDocGraphBuilder.java
new file mode 100644
index 00000000000..9ec03df5367
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/ApproximateDocGraphBuilder.java
@@ -0,0 +1,139 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ */
+
+package org.apache.lucene.codecs;
+
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.PostingsEnum;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.BytesRef;
+
+import java.io.IOException;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Approximates a sparse similarity graph from token co-occurrence without exact vector comparison.
+ */
+public final class ApproximateDocGraphBuilder {
+
+  /** Default number of edges retained per document in the similarity graph. */
+  public static final int DEFAULT_MAX_EDGES = 10;
+
+  private final String field;
+  private final int maxEdgesPerDoc;
+
+  /**
+   * Creates a new graph builder for the specified field.
+   *
+   * @param field the indexed field to use for term overlap computation
+   * @param maxEdgesPerDoc maximum number of outgoing edges to retain per document
+   */
+  public ApproximateDocGraphBuilder(String field, int maxEdgesPerDoc) {
+    this.field = field;
+    this.maxEdgesPerDoc = maxEdgesPerDoc;
+  }
+
+  /**
+   * Constructs the similarity graph for documents in the provided reader using term co-occurrence.
+   *
+   * <p>Documents that share terms in the specified field are connected with an edge, with edge
+   * weights based on normalized overlap count. The number of outgoing edges per document is limited
+   * by {@code maxEdgesPerDoc}.
+   *
+   * @param reader a leaf reader over a single Lucene segment
+   * @return a sparse document similarity graph based on token overlap
+   * @throws IOException if an I/O error occurs during term enumeration or postings access
+   */
+  public SparseEdgeGraph build(LeafReader reader) throws IOException {
+    final int maxDoc = reader.maxDoc();
+    final InMemorySparseEdgeGraph graph = new InMemorySparseEdgeGraph();
+    @SuppressWarnings("unchecked")
+    final Set<String>[] docTokens = (Set<String>[]) new Set<?>[maxDoc];
+    final Map<String, BitSet> tokenBitsets = new HashMap<>();
+
+    Terms terms = reader.terms(field);
+    if (terms == null) {
+      return graph;
+    }
+
+    TermsEnum termsEnum = terms.iterator();
+    BytesRef term;
+    while ((term = termsEnum.next()) != null) {
+      PostingsEnum postings = termsEnum.postings(null, PostingsEnum.NONE);
+      if (postings == null) {
+        continue;
+      }
+
+      final BitSet seen = new BitSet(maxDoc);
+      while (postings.nextDoc() != DocIdSetIterator.NO_MORE_DOCS) {
+        int docID = postings.docID();
+        seen.set(docID);
+        Set<String> tokens = docTokens[docID];
+        if (tokens == null) {
+          tokens = new HashSet<>();
+          docTokens[docID] = tokens;
+        }
+        tokens.add(term.utf8ToString());
+      }
+      tokenBitsets.put(term.utf8ToString(), seen);
+    }
+
+    for (int docA = 0; docA < maxDoc; docA++) {
+      Set<String> tokensA = docTokens[docA];
+      if (tokensA == null || tokensA.isEmpty()) {
+        continue;
+      }
+
+      final BitSet candidates = new BitSet(maxDoc);
+      for (String token : tokensA) {
+        BitSet seen = tokenBitsets.get(token);
+        if (seen != null) {
+          candidates.or(seen);
+        }
+      }
+
+      int added = 0;
+      for (int docB = candidates.nextSetBit(0);
+          docB >= 0 && added < maxEdgesPerDoc;
+          docB = candidates.nextSetBit(docB + 1)) {
+        if (docA == docB) {
+          continue;
+        }
+
+        Set<String> tokensB = docTokens[docB];
+        if (tokensB == null || tokensB.isEmpty()) {
+          continue;
+        }
+
+        int overlap = 0;
+        for (String token : tokensA) {
+          if (tokensB.contains(token)) {
+            overlap++;
+          }
+        }
+
+        if (overlap > 0) {
+          float weight = (float) overlap / Math.max(tokensA.size(), tokensB.size());
+          graph.addEdge(docA, docB, weight);
+          added++;
+        }
+      }
+    }
+
+    return graph;
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/BinMapReader.java b/lucene/core/src/java/org/apache/lucene/codecs/BinMapReader.java
new file mode 100644
index 00000000000..d98b44ff874
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/BinMapReader.java
@@ -0,0 +1,110 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ */
+package org.apache.lucene.codecs;
+
+import org.apache.lucene.index.IndexFileNames;
+import org.apache.lucene.index.SegmentReadState;
+import org.apache.lucene.store.ChecksumIndexInput;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.util.IOUtils;
+
+import java.io.Closeable;
+import java.io.IOException;
+
+/**
+ * Reads the binmap file for a segment and exposes per-document bin assignments.
+ *
+ * <p>Each document is assigned to a bin during indexing. The binmap file encodes a mapping from
+ * docID to binID and is used at search time to access bin-specific metadata such as scoring boosts.
+ *
+ * <p>This class validates file integrity using Lucene’s codec header/footer checks.
+ */
+public final class BinMapReader implements Closeable {
+
+  private static final String EXTENSION = "binmap";
+  private static final int VERSION_START = 0;
+  private static final String CODEC_NAME = "BinMap";
+
+  private final int[] bins;
+  private final int binCount;
+
+  /**
+   * Loads the binmap file for the given segment.
+   *
+   * @param dir directory containing the segment files
+   * @param state read state for the segment
+   * @throws IOException if the file cannot be read or fails validation
+   */
+  public BinMapReader(Directory dir, SegmentReadState state) throws IOException {
+    final String fileName =
+        IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, EXTENSION);
+
+    ChecksumIndexInput in = null;
+    boolean success = false;
+    try {
+      in = dir.openChecksumInput(fileName);
+      CodecUtil.checkIndexHeader(
+          in,
+          CODEC_NAME,
+          VERSION_START,
+          VERSION_START,
+          state.segmentInfo.getId(),
+          state.segmentSuffix);
+
+      int maxDoc = in.readInt();
+      this.binCount = in.readInt();
+
+      if (maxDoc != state.segmentInfo.maxDoc()) {
+        throw new IOException(
+            "maxDoc mismatch: expected=" + state.segmentInfo.maxDoc() + " actual=" + maxDoc);
+      }
+
+      this.bins = new int[maxDoc];
+      for (int i = 0; i < maxDoc; i++) {
+        bins[i] = in.readInt();
+      }
+
+      CodecUtil.checkFooter(in);
+      success = true;
+    } finally {
+      if (success) {
+        IOUtils.close(in);
+      } else {
+        IOUtils.closeWhileHandlingException(in);
+      }
+    }
+  }
+
+  /**
+   * Returns the bin ID assigned to the given document.
+   *
+   * @param docID document ID
+   * @return the bin ID
+   */
+  public int getBin(int docID) {
+    return bins[docID];
+  }
+
+  /** Returns the total number of bins used in this segment. */
+  public int getBinCount() {
+    return binCount;
+  }
+
+  /** Returns a copy of the full bin assignment array. */
+  public int[] getBinArrayCopy() {
+    int[] copy = new int[bins.length];
+    System.arraycopy(bins, 0, copy, 0, bins.length);
+    return copy;
+  }
+
+  @Override
+  public void close() {}
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/BinMapWriter.java b/lucene/core/src/java/org/apache/lucene/codecs/BinMapWriter.java
new file mode 100644
index 00000000000..ec20137f571
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/BinMapWriter.java
@@ -0,0 +1,116 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs;
+
+import org.apache.lucene.index.IndexFileNames;
+import org.apache.lucene.index.SegmentWriteState;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.store.IndexOutput;
+import org.apache.lucene.util.IOUtils;
+
+import java.io.IOException;
+
+/**
+ * Writes a binmap file for a segment.
+ *
+ * <p>The binmap assigns each document in the segment to a bin ID, typically used for scoring or
+ * early termination. The output is a binary file storing one integer bin ID per document.
+ */
+public final class BinMapWriter implements AutoCloseable {
+
+  /** File extension for binmap files. */
+  public static final String EXTENSION = "binmap";
+
+  /** Initial file format version. */
+  public static final int VERSION_START = 0;
+
+  private static final String CODEC_NAME = "BinMap";
+
+  private final Directory directory;
+  private final SegmentWriteState state;
+  private final int maxDoc;
+  private final int binCount;
+  private final int[] bins;
+
+  private boolean closed = false;
+
+  /**
+   * Creates a new {@link BinMapWriter} instance.
+   *
+   * @param directory output directory
+   * @param state current segment write state
+   * @param docToBin mapping from docID to bin ID
+   * @param binCount total number of bins
+   */
+  public BinMapWriter(Directory directory, SegmentWriteState state, int[] docToBin, int binCount) {
+    this.directory = directory;
+    this.state = state;
+    this.maxDoc = state.segmentInfo.maxDoc();
+    this.binCount = binCount;
+    this.bins = docToBin;
+  }
+
+  /**
+   * Writes the binmap file to the index output directory.
+   *
+   * <p>The format is:
+   *
+   * <ul>
+   *   <li>Header (versioned with {@link CodecUtil})
+   *   <li>maxDoc (int)
+   *   <li>binCount (int)
+   *   <li>{@code maxDoc} bin IDs, one int per document
+   *   <li>Footer
+   * </ul>
+   */
+  @Override
+  public void close() throws IOException {
+    final String fileName =
+        IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, EXTENSION);
+
+    if (closed) return;
+    closed = true;
+
+    // Prevent double-write in case close() is called multiple times
+    for (String existing : directory.listAll()) {
+      if (existing.equals(fileName)) {
+        return; // already written
+      }
+    }
+    IndexOutput out = null;
+    boolean success = false;
+    try {
+      out = directory.createOutput(fileName, state.context);
+      CodecUtil.writeIndexHeader(
+          out, CODEC_NAME, VERSION_START, state.segmentInfo.getId(), state.segmentSuffix);
+      out.writeInt(maxDoc);
+      out.writeInt(binCount);
+      for (int i = 0; i < maxDoc; i++) {
+        out.writeInt(bins[i]);
+      }
+      CodecUtil.writeFooter(out);
+      success = true;
+    } finally {
+      if (success) {
+        IOUtils.close(out);
+      } else {
+        IOUtils.closeWhileHandlingException(out);
+        IOUtils.deleteFilesIgnoringExceptions(directory, fileName);
+      }
+    }
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/BinQualityMetrics.java b/lucene/core/src/java/org/apache/lucene/codecs/BinQualityMetrics.java
new file mode 100644
index 00000000000..42c3c7eb18b
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/BinQualityMetrics.java
@@ -0,0 +1,51 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs;
+
+import java.util.Arrays;
+
+/** Computes bin quality metrics like balance, skewness, and Gini index. */
+public final class BinQualityMetrics {
+
+  private BinQualityMetrics() {}
+
+  /** Computes standard deviation of document counts across bins. */
+  public static double computeStdDev(int[] docCounts) {
+    double mean = Arrays.stream(docCounts).average().orElse(0.0);
+    double variance = 0.0;
+    for (int count : docCounts) {
+      double delta = count - mean;
+      variance += delta * delta;
+    }
+    return Math.sqrt(variance / docCounts.length);
+  }
+
+  /** Computes the Gini index to measure bin inequality. */
+  public static double computeGiniIndex(int[] docCounts) {
+    int n = docCounts.length;
+    if (n == 0) return 0.0;
+    int[] sorted = docCounts.clone();
+    Arrays.sort(sorted);
+    double cumulative = 0.0;
+    for (int i = 0; i < n; i++) {
+      cumulative += (i + 1L) * sorted[i];
+    }
+    double total = Arrays.stream(sorted).sum();
+    if (total == 0.0) return 0.0;
+    return (2.0 * cumulative) / (n * total) - (n + 1.0) / n;
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/DocBinningGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/codecs/DocBinningGraphBuilder.java
new file mode 100644
index 00000000000..7773f302e99
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/DocBinningGraphBuilder.java
@@ -0,0 +1,126 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs;
+
+import java.io.IOException;
+import java.util.ArrayDeque;
+import java.util.Deque;
+
+/**
+ * Partitions documents into bins using iterative graph bisection.
+ *
+ * <p>This utility approximates a balanced clustering of documents using a sparse similarity graph.
+ * It uses fixed seed points and edge weights to recursively assign documents to bins, ensuring that
+ * similar documents are grouped together.
+ */
+public final class DocBinningGraphBuilder {
+
+  private DocBinningGraphBuilder() {}
+
+  /**
+   * Assigns each document to a bin by performing recursive bisection over a similarity graph.
+   *
+   * @param graph the sparse edge graph of document similarities
+   * @param maxDoc total number of documents
+   * @param numBins number of bins (must be a power of 2)
+   * @return an array mapping docID to bin ID
+   * @throws IOException if an error occurs during graph access
+   */
+  public static int[] computeBins(SparseEdgeGraph graph, int maxDoc, int numBins)
+      throws IOException {
+    if (maxDoc <= 0 || Integer.bitCount(numBins) != 1) {
+      throw new IllegalArgumentException("maxDoc must be > 0 and numBins must be a power of 2");
+    }
+
+    final int[] docToBin = new int[maxDoc];
+    final int[] docIndices = new int[maxDoc];
+    for (int i = 0; i < maxDoc; i++) {
+      docToBin[i] = -1;
+      docIndices[i] = i;
+    }
+
+    final Deque<PartitionTask> queue = new ArrayDeque<>();
+    queue.add(new PartitionTask(0, maxDoc, 0, numBins));
+
+    while (!queue.isEmpty()) {
+      PartitionTask task = queue.removeFirst();
+      final int size = task.end - task.start;
+      if (task.binCount == 1 || size <= 1) {
+        for (int i = task.start; i < task.end; i++) {
+          docToBin[docIndices[i]] = task.binBase;
+        }
+        continue;
+      }
+
+      final int seedA = docIndices[task.start];
+      final int seedB = docIndices[task.end - 1];
+
+      final int[] left = new int[size];
+      final int[] right = new int[size];
+      int leftSize = 0;
+      int rightSize = 0;
+
+      for (int i = 0; i < size; i++) {
+        final int docID = docIndices[task.start + i];
+        final float simA = similarity(graph, docID, seedA);
+        final float simB = similarity(graph, docID, seedB);
+        if (simA >= simB) {
+          left[leftSize++] = docID;
+        } else {
+          right[rightSize++] = docID;
+        }
+      }
+
+      System.arraycopy(left, 0, docIndices, task.start, leftSize);
+      System.arraycopy(right, 0, docIndices, task.start + leftSize, rightSize);
+
+      final int mid = task.start + leftSize;
+      final int nextBin = task.binCount >>> 1;
+
+      queue.add(new PartitionTask(task.start, mid, task.binBase, nextBin));
+      queue.add(new PartitionTask(mid, task.end, task.binBase + nextBin, nextBin));
+    }
+
+    for (int i = 0; i < maxDoc; i++) {
+      if (docToBin[i] == -1) {
+        throw new IllegalStateException("Unassigned docID: " + i);
+      }
+    }
+
+    return docToBin;
+  }
+
+  /**
+   * Computes similarity between two documents using the sparse graph.
+   *
+   * <p>The similarity is computed as the sum of edge weights from docA to docB.
+   */
+  private static float similarity(SparseEdgeGraph graph, int docA, int docB) {
+    int[] neighbors = graph.getNeighbors(docA);
+    float[] weights = graph.getWeights(docA);
+    float score = 0f;
+    for (int i = 0; i < neighbors.length; i++) {
+      if (neighbors[i] == docB) {
+        score += weights[i];
+      }
+    }
+    return score;
+  }
+
+  /** Internal task used to represent a partition step. */
+  private record PartitionTask(int start, int end, int binBase, int binCount) {}
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/DocGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/codecs/DocGraphBuilder.java
new file mode 100644
index 00000000000..f028b67ff50
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/DocGraphBuilder.java
@@ -0,0 +1,185 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs;
+
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.PostingsEnum;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.BytesRef;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.PriorityQueue;
+import java.util.Set;
+
+/** Builds a sparse document similarity graph from postings lists. */
+public final class DocGraphBuilder {
+
+  /** Default maximum outgoing edges per document */
+  public static final int DEFAULT_MAX_EDGES = 10;
+
+  private final String field;
+  private final int maxEdgesPerDoc;
+
+  /** Reusable vector store for term frequencies */
+  private final Map<Integer, IntVector> docTermVectors = new HashMap<>();
+
+  /**
+   * Constructs a new graph builder.
+   *
+   * @param field field to use for binning
+   * @param maxEdgesPerDoc number of outgoing edges to retain per document
+   */
+  public DocGraphBuilder(String field, int maxEdgesPerDoc) {
+    this.field = field;
+    this.maxEdgesPerDoc = maxEdgesPerDoc;
+  }
+
+  /** Constructs the sparse similarity graph using term overlap. */
+  public SparseEdgeGraph build(LeafReader reader) throws IOException {
+    final SparseEdgeGraph graph = new InMemorySparseEdgeGraph();
+    final Map<String, ArrayList<Integer>> termToDocList = new HashMap<>();
+
+    Terms terms = reader.terms(field);
+    if (terms == null) {
+      return graph;
+    }
+
+    TermsEnum termsEnum = terms.iterator();
+    BytesRef term;
+    while ((term = termsEnum.next()) != null) {
+      String termStr = term.utf8ToString();
+      PostingsEnum postings = termsEnum.postings(null, PostingsEnum.FREQS);
+      if (postings == null) {
+        continue;
+      }
+      while (postings.nextDoc() != DocIdSetIterator.NO_MORE_DOCS) {
+        int docID = postings.docID();
+        int freq = postings.freq();
+
+        docTermVectors.computeIfAbsent(docID, _ -> new IntVector()).add(termStr, freq);
+        termToDocList.computeIfAbsent(termStr, _ -> new ArrayList<>()).add(docID);
+      }
+    }
+
+    for (Map.Entry<Integer, IntVector> entryA : docTermVectors.entrySet()) {
+      int docA = entryA.getKey();
+      IntVector vecA = entryA.getValue();
+
+      PriorityQueue<Neighbor> topK = new PriorityQueue<>(maxEdgesPerDoc);
+      final Map<Integer, Float> candidates = new HashMap<>();
+
+      for (String termKey : vecA.keys()) {
+        for (int docB : termToDocList.getOrDefault(termKey, new ArrayList<>())) {
+          if (docA == docB) {
+            continue;
+          }
+          candidates.putIfAbsent(docB, 0f);
+        }
+      }
+
+      for (Map.Entry<Integer, Float> candidate : candidates.entrySet()) {
+        int docB = candidate.getKey();
+        IntVector vecB = docTermVectors.get(docB);
+        if (vecB == null) {
+          continue;
+        }
+        float sim = cosine(vecA, vecB);
+        if (sim > 0) {
+          topK.offer(new Neighbor(docB, sim));
+          if (topK.size() > maxEdgesPerDoc) {
+            topK.poll();
+          }
+        }
+      }
+
+      while (!topK.isEmpty()) {
+        Neighbor neighbor = topK.poll();
+        graph.addEdge(docA, neighbor.docID, neighbor.score);
+      }
+    }
+
+    return graph;
+  }
+
+  private static float cosine(IntVector a, IntVector b) {
+    float dot = 0f, normA = 0f, normB = 0f;
+
+    for (Map.Entry<String, Integer> entry : a.entries()) {
+      int tfA = entry.getValue();
+      normA += tfA * tfA;
+      Integer tfB = b.get(entry.getKey());
+      if (tfB != null) {
+        dot += tfA * tfB;
+      }
+    }
+
+    for (int tfB : b.values()) {
+      normB += tfB * tfB;
+    }
+
+    if (normA == 0f || normB == 0f) {
+      return 0f;
+    }
+
+    return dot / (float) (Math.sqrt(normA) * Math.sqrt(normB));
+  }
+
+  private static final class Neighbor implements Comparable<Neighbor> {
+    final int docID;
+    final float score;
+
+    Neighbor(int docID, float score) {
+      this.docID = docID;
+      this.score = score;
+    }
+
+    @Override
+    public int compareTo(Neighbor other) {
+      return Float.compare(this.score, other.score);
+    }
+  }
+
+  /** Lightweight term frequency vector with string keys and int values. */
+  private static final class IntVector {
+    private final Map<String, Integer> tf = new HashMap<>();
+
+    void add(String key, int freq) {
+      tf.merge(key, freq, Integer::sum);
+    }
+
+    Integer get(String key) {
+      return tf.get(key);
+    }
+
+    Set<String> keys() {
+      return tf.keySet();
+    }
+
+    Iterable<Map.Entry<String, Integer>> entries() {
+      return tf.entrySet();
+    }
+
+    Iterable<Integer> values() {
+      return tf.values();
+    }
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/FieldsLeafReader.java b/lucene/core/src/java/org/apache/lucene/codecs/FieldsLeafReader.java
new file mode 100644
index 00000000000..fd2c9f58c87
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/FieldsLeafReader.java
@@ -0,0 +1,172 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs;
+
+import org.apache.lucene.index.BinaryDocValues;
+import org.apache.lucene.index.ByteVectorValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.FieldInfos;
+import org.apache.lucene.index.FloatVectorValues;
+import org.apache.lucene.index.LeafMetaData;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.NumericDocValues;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.index.SortedDocValues;
+import org.apache.lucene.index.SortedNumericDocValues;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.StoredFields;
+import org.apache.lucene.index.TermVectors;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.search.KnnCollector;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.Version;
+
+import java.io.IOException;
+import java.util.Map;
+
+/** Minimal LeafReader exposing term statistics for one or more fields. */
+public final class FieldsLeafReader extends LeafReader {
+
+  private final Map<String, Terms> fieldTerms;
+  private final int maxDoc;
+
+  /**
+   * Creates a {@code FieldsLeafReader} for the given field terms.
+   *
+   * @param fieldTerms mapping of field names to {@link Terms} enumerations
+   * @param maxDoc total number of documents in this reader
+   */
+  public FieldsLeafReader(Map<String, Terms> fieldTerms, int maxDoc) {
+    this.fieldTerms = fieldTerms;
+    this.maxDoc = maxDoc;
+  }
+
+  @Override
+  public CacheHelper getCoreCacheHelper() {
+    return null;
+  }
+
+  @Override
+  public Terms terms(String field) throws IOException {
+    return fieldTerms.get(field);
+  }
+
+  @Override
+  public int maxDoc() {
+    return maxDoc;
+  }
+
+  @Override
+  public StoredFields storedFields() throws IOException {
+    return null;
+  }
+
+  @Override
+  public TermVectors termVectors() throws IOException {
+    return null;
+  }
+
+  @Override
+  public int numDocs() {
+    return maxDoc;
+  }
+
+  @Override
+  public Bits getLiveDocs() {
+    return null;
+  }
+
+  @Override
+  public FieldInfos getFieldInfos() {
+    throw new UnsupportedOperationException("field infos not supported");
+  }
+
+  @Override
+  public NumericDocValues getNumericDocValues(String field) {
+    return null;
+  }
+
+  @Override
+  public BinaryDocValues getBinaryDocValues(String field) throws IOException {
+    return null;
+  }
+
+  @Override
+  public SortedNumericDocValues getSortedNumericDocValues(String field) {
+    return null;
+  }
+
+  @Override
+  public SortedDocValues getSortedDocValues(String field) {
+    return null;
+  }
+
+  @Override
+  public SortedSetDocValues getSortedSetDocValues(String field) {
+    return null;
+  }
+
+  @Override
+  public NumericDocValues getNormValues(String field) throws IOException {
+    return null;
+  }
+
+  @Override
+  public DocValuesSkipper getDocValuesSkipper(String field) throws IOException {
+    return null;
+  }
+
+  @Override
+  public FloatVectorValues getFloatVectorValues(String field) throws IOException {
+    return null;
+  }
+
+  @Override
+  public ByteVectorValues getByteVectorValues(String field) throws IOException {
+    return null;
+  }
+
+  @Override
+  public void searchNearestVectors(
+      String field, float[] target, KnnCollector knnCollector, Bits acceptDocs)
+      throws IOException {}
+
+  @Override
+  public void searchNearestVectors(
+      String field, byte[] target, KnnCollector knnCollector, Bits acceptDocs) throws IOException {}
+
+  @Override
+  public PointValues getPointValues(String field) {
+    return null;
+  }
+
+  @Override
+  public LeafMetaData getMetaData() {
+    return new LeafMetaData(Version.LATEST.major, Version.LATEST, null, false);
+  }
+
+  @Override
+  public void checkIntegrity() {}
+
+  @Override
+  protected void doClose() {}
+
+  @Override
+  public CacheHelper getReaderCacheHelper() {
+    return null;
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/InMemorySparseEdgeGraph.java b/lucene/core/src/java/org/apache/lucene/codecs/InMemorySparseEdgeGraph.java
new file mode 100644
index 00000000000..f0a26a67682
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/InMemorySparseEdgeGraph.java
@@ -0,0 +1,79 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * Simple in-memory implementation of {@link SparseEdgeGraph}. Intended for unit testing and
+ * non-production use.
+ */
+public final class InMemorySparseEdgeGraph implements SparseEdgeGraph {
+
+  private final Map<Integer, int[]> neighbors = new HashMap<>();
+  private final Map<Integer, float[]> weights = new HashMap<>();
+
+  private void addDirectedEdge(int from, int to, float weight) {
+    int[] existingNeighbors = neighbors.get(from);
+    float[] existingWeights = weights.get(from);
+
+    int len = existingNeighbors == null ? 0 : existingNeighbors.length;
+    int[] newNeighbors = new int[len + 1];
+    float[] newWeights = new float[len + 1];
+
+    if (len > 0) {
+      System.arraycopy(existingNeighbors, 0, newNeighbors, 0, len);
+      System.arraycopy(existingWeights, 0, newWeights, 0, len);
+    }
+
+    newNeighbors[len] = to;
+    newWeights[len] = weight;
+
+    neighbors.put(from, newNeighbors);
+    weights.put(from, newWeights);
+  }
+
+  /** Adds a symmetric edge between two documents with the given weight. */
+  @Override
+  public void addEdge(int docA, int docB, float weight) {
+    addDirectedEdge(docA, docB, weight);
+    addDirectedEdge(docB, docA, weight);
+  }
+
+  @Override
+  public int[] getNeighbors(int docID) {
+    return neighbors.getOrDefault(docID, new int[0]);
+  }
+
+  @Override
+  public float[] getWeights(int docID) {
+    return weights.getOrDefault(docID, new float[0]);
+  }
+
+  @Override
+  public void ensureVertex(int docID) {
+    neighbors.computeIfAbsent(docID, _ -> new int[0]);
+    weights.computeIfAbsent(docID, _ -> new float[0]);
+  }
+
+  /** Returns the number of vertices in the graph with at least one edge. */
+  @Override
+  public int size() {
+    return neighbors.size();
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/SparseEdgeGraph.java b/lucene/core/src/java/org/apache/lucene/codecs/SparseEdgeGraph.java
new file mode 100644
index 00000000000..59f2d71730e
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/SparseEdgeGraph.java
@@ -0,0 +1,52 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ */
+package org.apache.lucene.codecs;
+
+/**
+ * Interface for a sparse directed graph of documents. Used to represent approximate similarity
+ * relationships between documents.
+ */
+public interface SparseEdgeGraph {
+  /**
+   * Adds a directed edge from {@code fromDocID} to {@code toDocID} with the given weight.
+   *
+   * @param fromDocID source document ID
+   * @param toDocID destination document ID
+   * @param weight edge weight representing similarity
+   */
+  void addEdge(int fromDocID, int toDocID, float weight);
+
+  /**
+   * Returns the list of neighboring document IDs for a given source document.
+   *
+   * @param docID source document ID
+   * @return array of neighboring document IDs
+   */
+  int[] getNeighbors(int docID);
+
+  /**
+   * Returns the edge weights associated with the neighbors of the given document.
+   *
+   * @param docID source document ID
+   * @return array of weights corresponding to {@link #getNeighbors(int)}
+   */
+  float[] getWeights(int docID);
+
+  /** Returns the number of vertices in the graph. */
+  int size();
+
+  /**
+   * Ensures internal data structures can accommodate the given document ID.
+   *
+   * @param docID document ID to reserve space for
+   */
+  void ensureVertex(int docID);
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene103/Lucene103PostingsFormat.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene103/Lucene103PostingsFormat.java
index 3c489f9d3ca..b463ddc062e 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene103/Lucene103PostingsFormat.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene103/Lucene103PostingsFormat.java
@@ -17,20 +17,34 @@
 package org.apache.lucene.codecs.lucene103;
 
 import java.io.IOException;
+
+import org.apache.lucene.codecs.ApproximateDocBinner;
+import org.apache.lucene.codecs.ApproximateDocGraphBuilder;
+import org.apache.lucene.codecs.BinMapWriter;
 import org.apache.lucene.codecs.BlockTermState;
 import org.apache.lucene.codecs.CodecUtil;
+import org.apache.lucene.codecs.DocBinningGraphBuilder;
+import org.apache.lucene.codecs.DocGraphBuilder;
 import org.apache.lucene.codecs.FieldsConsumer;
+import org.apache.lucene.codecs.FieldsLeafReader;
 import org.apache.lucene.codecs.FieldsProducer;
+import org.apache.lucene.codecs.NormsProducer;
 import org.apache.lucene.codecs.PostingsFormat;
 import org.apache.lucene.codecs.PostingsReaderBase;
 import org.apache.lucene.codecs.PostingsWriterBase;
+import org.apache.lucene.codecs.SparseEdgeGraph;
 import org.apache.lucene.codecs.lucene103.blocktree.Lucene103BlockTreeTermsReader;
 import org.apache.lucene.codecs.lucene103.blocktree.Lucene103BlockTreeTermsWriter;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.FieldInfos;
+import org.apache.lucene.index.Fields;
 import org.apache.lucene.index.ImpactsEnum;
 import org.apache.lucene.index.IndexOptions;
+import org.apache.lucene.index.LeafReader;
 import org.apache.lucene.index.SegmentReadState;
 import org.apache.lucene.index.SegmentWriteState;
 import org.apache.lucene.index.TermState;
+import org.apache.lucene.index.Terms;
 import org.apache.lucene.store.DataOutput;
 import org.apache.lucene.util.IOUtils;
 import org.apache.lucene.util.packed.PackedInts;
@@ -369,6 +383,7 @@ public final class Lucene103PostingsFormat extends PostingsFormat {
   static final String PAY_CODEC = "Lucene103PostingsWriterPay";
 
   static final int VERSION_START = 0;
+  private static final int MAX_DOC_FOR_EXACT_BINNING = 10;
 
   static final int VERSION_CURRENT = VERSION_START;
 
@@ -406,6 +421,92 @@ public final class Lucene103PostingsFormat extends PostingsFormat {
     this.maxTermBlockSize = maxTermBlockSize;
   }
 
+  static void maybeWriteDocBinning(SegmentWriteState state) throws IOException {
+    final int maxDoc = state.segmentInfo.maxDoc();
+    if (maxDoc == 0) {
+      return;
+    }
+
+    final FieldInfos fieldInfos = state.fieldInfos;
+    String binningField = null;
+    String graphBuilderType = null;
+    int binCount = -1;
+
+    for (FieldInfo fi : fieldInfos) {
+      if ("true".equalsIgnoreCase(fi.getAttribute("doBinning"))) {
+        binningField = fi.name;
+        String binCountAttr = fi.getAttribute("bin.count");
+        binCount =
+            (binCountAttr != null)
+                ? Integer.parseInt(binCountAttr)
+                : Math.max(1, Integer.highestOneBit(maxDoc >>> 4));
+        String graphBuilderAttr = fi.getAttribute("bin.builder");
+        graphBuilderType = (graphBuilderAttr != null) ? graphBuilderAttr : "auto";
+        break;
+      }
+    }
+
+    if (binningField == null || binCount <= 0) {
+      return;
+    }
+
+    final PostingsFormat format = new Lucene103PostingsFormat();
+    try (FieldsProducer fields =
+        format.fieldsProducer(
+            new SegmentReadState(
+                state.directory,
+                state.segmentInfo,
+                state.fieldInfos,
+                state.context,
+                state.segmentSuffix))) {
+
+      Terms terms = fields.terms(binningField);
+      if (terms == null) {
+        return;
+      }
+
+      try (LeafReader reader =
+          new FieldsLeafReader(java.util.Collections.singletonMap(binningField, terms), maxDoc)) {
+
+        final int[] docToBin;
+
+        final SparseEdgeGraph graph;
+
+        if ("approx".equalsIgnoreCase(graphBuilderType)) {
+          ApproximateDocGraphBuilder builder =
+              new ApproximateDocGraphBuilder(
+                  binningField, ApproximateDocGraphBuilder.DEFAULT_MAX_EDGES);
+          graph = builder.build(reader);
+          docToBin = ApproximateDocBinner.assign(graph, maxDoc, binCount);
+        } else if ("exact".equalsIgnoreCase(graphBuilderType)) {
+          DocGraphBuilder builder =
+              new DocGraphBuilder(binningField, DocGraphBuilder.DEFAULT_MAX_EDGES);
+          graph = builder.build(reader);
+          docToBin = DocBinningGraphBuilder.computeBins(graph, maxDoc, binCount);
+        } else {
+          // default: auto fallback based on doc count
+          if (maxDoc > MAX_DOC_FOR_EXACT_BINNING) {
+            ApproximateDocGraphBuilder builder =
+                new ApproximateDocGraphBuilder(
+                    binningField, ApproximateDocGraphBuilder.DEFAULT_MAX_EDGES);
+            graph = builder.build(reader);
+            docToBin = ApproximateDocBinner.assign(graph, maxDoc, binCount);
+          } else {
+            DocGraphBuilder builder =
+                new DocGraphBuilder(binningField, DocGraphBuilder.DEFAULT_MAX_EDGES);
+            graph = builder.build(reader);
+            docToBin = DocBinningGraphBuilder.computeBins(graph, maxDoc, binCount);
+          }
+        }
+
+        try (BinMapWriter writer = new BinMapWriter(state.directory, state, docToBin, binCount)) {
+          // Trigger side-effect and keep compiler happy
+          assert writer != null;
+        }
+      }
+    }
+  }
+
   @Override
   public FieldsConsumer fieldsConsumer(SegmentWriteState state) throws IOException {
     PostingsWriterBase postingsWriter = new Lucene103PostingsWriter(state, version);
@@ -415,7 +516,42 @@ public final class Lucene103PostingsFormat extends PostingsFormat {
           new Lucene103BlockTreeTermsWriter(
               state, postingsWriter, minTermBlockSize, maxTermBlockSize);
       success = true;
-      return ret;
+
+          return new FieldsConsumer() {
+      @Override
+      public void write(Fields fields, NormsProducer normsProducer) throws IOException {
+        ret.write(fields, normsProducer);
+      }
+
+      @Override
+      public void close() throws IOException {
+        IOException prior = null;
+        try {
+          ret.close();
+        } catch (IOException e) {
+          prior = e;
+        }
+
+        /*try {
+          if (prior == null) {
+            // Now that all outputs are flushed, perform binning safely
+            maybeWriteDocBinning(state);
+          }
+        } catch (IOException e) {
+          if (prior != null) {
+            prior.addSuppressed(e);
+            throw prior;
+          } else {
+            throw e;
+          }
+        }*/
+
+        if (prior != null) {
+          throw prior;
+        }
+      }
+    };
+      //return ret;
     } finally {
       if (!success) {
         IOUtils.closeWhileHandlingException(postingsWriter);
diff --git a/lucene/core/src/java/org/apache/lucene/index/BinScoreLeafReader.java b/lucene/core/src/java/org/apache/lucene/index/BinScoreLeafReader.java
new file mode 100644
index 00000000000..a562a88ae4a
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/index/BinScoreLeafReader.java
@@ -0,0 +1,56 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.index;
+
+import org.apache.lucene.util.IOUtils;
+
+import java.io.Closeable;
+import java.io.IOException;
+
+/** Reader wrapper that exposes bin-aware scoring. */
+public class BinScoreLeafReader extends FilterLeafReader {
+
+  private final BinScoreReader binScore;
+  private final Closeable[] resources;
+
+  /** Default constructor */
+  public BinScoreLeafReader(LeafReader in, BinScoreReader binScore, Closeable... resources) {
+    super(in);
+    this.binScore = binScore;
+    this.resources = resources;
+  }
+
+  /** Returns the bin score reader. */
+  public BinScoreReader getBinScoreReader() {
+    return binScore;
+  }
+
+  @Override
+  protected void doClose() throws IOException {
+    IOUtils.close(resources);
+  }
+
+  @Override
+  public CacheHelper getReaderCacheHelper() {
+    return in.getReaderCacheHelper();
+  }
+
+  @Override
+  public CacheHelper getCoreCacheHelper() {
+    return in.getCoreCacheHelper();
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/index/BinScoreReader.java b/lucene/core/src/java/org/apache/lucene/index/BinScoreReader.java
new file mode 100644
index 00000000000..60a55cf7935
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/index/BinScoreReader.java
@@ -0,0 +1,53 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.index;
+
+import org.apache.lucene.codecs.BinMapReader;
+
+import java.io.IOException;
+import java.util.Objects;
+
+/**
+ * Provides per-document bin assignments for scoring adjustments.
+ *
+ * @lucene.experimental
+ */
+public final class BinScoreReader {
+
+  private final BinMapReader binMap;
+
+  /** Creates a new {@link BinScoreReader} from a {@link BinMapReader}. */
+  public BinScoreReader(BinMapReader binMap) {
+    this.binMap = Objects.requireNonNull(binMap, "binMap must not be null");
+  }
+
+  /**
+   * Returns the bin ID for the specified document.
+   *
+   * @param docID doc ID within the segment
+   * @return assigned bin ID
+   * @throws IOException if bin lookup fails
+   */
+  public int getBinForDoc(int docID) throws IOException {
+    return binMap.getBin(docID);
+  }
+
+  /** Returns the total number of bins in this segment. */
+  public int getBinCount() {
+    return binMap.getBinCount();
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/index/BinScoreUtil.java b/lucene/core/src/java/org/apache/lucene/index/BinScoreUtil.java
new file mode 100644
index 00000000000..cd095165565
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/index/BinScoreUtil.java
@@ -0,0 +1,134 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.index;
+
+import org.apache.lucene.codecs.BinMapReader;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.store.IOContext;
+import org.apache.lucene.util.IOUtils;
+
+import java.io.Closeable;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+/** Utilities for wrapping readers with binning support. */
+public final class BinScoreUtil {
+
+  private BinScoreUtil() {}
+
+  /** Wrap an IndexReader with bin support. */
+  public static IndexReader wrap(IndexReader reader) throws IOException {
+    if (reader instanceof LeafReader) {
+      return wrap((LeafReader) reader);
+    }
+    if (reader instanceof CompositeReader) {
+      return wrapComposite((CompositeReader) reader);
+    }
+    return reader;
+  }
+
+  private static CompositeReader wrapComposite(CompositeReader reader) throws IOException {
+    List<LeafReader> wrapped = new ArrayList<>();
+    for (LeafReaderContext ctx : reader.leaves()) {
+      wrapped.add(wrap(ctx.reader()));
+    }
+    // This MultiReader just wraps the readers — responsibility for cleanup is delegated to
+    // individual leaves.
+    return new MultiReader(wrapped.toArray(new LeafReader[0]), true);
+  }
+
+  /** Wrap a LeafReader with bin score logic if binmap file is found. */
+  public static LeafReader wrap(LeafReader reader) throws IOException {
+    SegmentReader sr = getSegmentReader(reader);
+    if (sr == null) {
+      return reader;
+    }
+
+    SegmentCommitInfo commitInfo = sr.getSegmentInfo();
+    SegmentInfo info = commitInfo.info;
+    Directory dir = sr.directory();
+    Closeable compoundReader = null;
+
+    if (info.getUseCompoundFile()) {
+      var format = info.getCodec().compoundFormat();
+      if (format != null) {
+        compoundReader = format.getCompoundReader(dir, info);
+        dir = (Directory) compoundReader;
+      }
+    }
+
+    String name = info.name;
+    String binmapFile = findBinmapFile(dir, name);
+    if (binmapFile == null) {
+      IOUtils.closeWhileHandlingException(compoundReader);
+      return reader;
+    }
+
+    String suffix =
+        binmapFile.substring(name.length() + 1, binmapFile.length() - ".binmap".length());
+    SegmentReadState state =
+        new SegmentReadState(dir, info, sr.getFieldInfos(), IOContext.READONCE, suffix);
+
+    BinMapReader binMap = null;
+    try {
+      binMap = new BinMapReader(dir, state);
+      BinScoreReader binScore = new BinScoreReader(binMap);
+
+      final Closeable closeOnClose = compoundReader;
+      return new BinScoreLeafReader(reader, binScore, binMap) {
+        @Override
+        protected void doClose() throws IOException {
+          IOUtils.close(closeOnClose); // closes compoundReader if present
+          super.doClose(); // closes binMap, etc.
+        }
+      };
+    } catch (Throwable t) {
+      IOUtils.closeWhileHandlingException(binMap, compoundReader);
+      throw t;
+    }
+  }
+
+  private static SegmentReader getSegmentReader(LeafReader reader) {
+    if (reader instanceof SegmentReader) {
+      return (SegmentReader) reader;
+    }
+    LeafReader unwrapped = FilterLeafReader.unwrap(reader);
+    return (unwrapped instanceof SegmentReader) ? (SegmentReader) unwrapped : null;
+  }
+
+  private static String findBinmapFile(Directory dir, String segmentName) throws IOException {
+    for (String file : dir.listAll()) {
+      if (file.startsWith(segmentName + "_") && file.endsWith(".binmap")) {
+        return file;
+      }
+    }
+    return null;
+  }
+
+  /** Return bin score reader if available. */
+  public static BinScoreReader getBinScoreReader(LeafReader reader) {
+    if (reader instanceof BinScoreLeafReader) {
+      return ((BinScoreLeafReader) reader).getBinScoreReader();
+    }
+    LeafReader unwrapped = FilterLeafReader.unwrap(reader);
+    if (unwrapped instanceof BinScoreLeafReader) {
+      return ((BinScoreLeafReader) unwrapped).getBinScoreReader();
+    }
+    return null;
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingCollector.java b/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingCollector.java
new file mode 100644
index 00000000000..a1f614ec50f
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingCollector.java
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search;
+
+import org.apache.lucene.index.BinScoreLeafReader;
+import org.apache.lucene.index.BinScoreReader;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.LeafReaderContext;
+
+import java.io.IOException;
+
+/** SLA-aware collector that boosts score based on bin distribution. */
+public final class AnytimeRankingCollector extends TopDocsCollector<ScoreDoc> {
+
+  private static final int DOCS_PER_CHECK = 100;
+  private static final int MIN_CHECK_INTERVAL = 32;
+  private static final int MAX_CHECK_INTERVAL = 512;
+
+  private final long cutoffNanos;
+  private final long start;
+  private final float[] binBoosts;
+
+  private int count = 0;
+
+  AnytimeRankingCollector(int topK, long cutoffNanos, float[] binBoosts) {
+    super(new HitQueue(topK, false));
+    this.cutoffNanos = cutoffNanos;
+    this.start = System.nanoTime();
+    this.binBoosts = binBoosts;
+  }
+
+  @Override
+  protected int topDocsSize() {
+    return pq.size();
+  }
+
+  @Override
+  protected TopDocs newTopDocs(ScoreDoc[] results, int start) {
+    return new TopDocs(
+        new TotalHits(totalHits, TotalHits.Relation.GREATER_THAN_OR_EQUAL_TO),
+        results != null ? results : EMPTY_TOPDOCS.scoreDocs);
+  }
+
+  @Override
+  public LeafCollector getLeafCollector(LeafReaderContext ctx) throws IOException {
+    final int base = ctx.docBase;
+    final LeafReader reader = ctx.reader();
+    final BinScoreReader binReader =
+        reader instanceof BinScoreLeafReader
+            ? ((BinScoreLeafReader) reader).getBinScoreReader()
+            : null;
+
+    int interval =
+        Math.max(
+            MIN_CHECK_INTERVAL, Math.min(MAX_CHECK_INTERVAL, reader.numDocs() / DOCS_PER_CHECK));
+
+    return new LeafCollector() {
+      private Scorable scorer;
+
+      @Override
+      public void setScorer(Scorable scorer) {
+        this.scorer = scorer;
+      }
+
+      @Override
+      public void collect(int doc) throws IOException {
+        float score = scorer.score();
+        if (score <= 0 || Float.isNaN(score)) {
+          return;
+        }
+
+        int globalDoc = doc + base;
+        if (binReader != null && binBoosts != null) {
+          int bin = binReader.getBinForDoc(doc);
+          if (bin >= 0 && bin < binBoosts.length) {
+            score *= binBoosts[bin];
+          }
+        }
+
+        if (pq.insertWithOverflow(new ScoreDoc(globalDoc, score)) != null) {
+          totalHits++;
+        }
+
+        if (++count % interval == 0 && System.nanoTime() - start > cutoffNanos) {
+          throw new CollectionTerminatedException();
+        }
+      }
+    };
+  }
+
+  @Override
+  public ScoreMode scoreMode() {
+    return ScoreMode.TOP_SCORES;
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingCollectorManager.java b/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingCollectorManager.java
new file mode 100644
index 00000000000..c30dcde6d7a
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingCollectorManager.java
@@ -0,0 +1,69 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search;
+
+import org.apache.lucene.index.IndexReader;
+
+import java.io.IOException;
+import java.util.Collection;
+import java.util.PriorityQueue;
+
+/** CollectorManager that provides bin-aware SLA-constrained collectors. */
+public final class AnytimeRankingCollectorManager
+    implements CollectorManager<AnytimeRankingCollector, TopDocs> {
+
+  private final int topK;
+  private final long slaCutoffNanos;
+  private final float[] binBoosts;
+
+  public AnytimeRankingCollectorManager(int topK, long slaCutoffNanos, IndexReader reader)
+      throws IOException {
+    this.topK = topK;
+    this.slaCutoffNanos = slaCutoffNanos;
+    this.binBoosts = BinBoostCalculator.compute(reader);
+  }
+
+  @Override
+  public AnytimeRankingCollector newCollector() {
+    return new AnytimeRankingCollector(topK, slaCutoffNanos, binBoosts);
+  }
+
+  @Override
+  public TopDocs reduce(Collection<AnytimeRankingCollector> collectors) throws IOException {
+    PriorityQueue<ScoreDoc> queue =
+        new PriorityQueue<>(topK, (a, b) -> Float.compare(a.score, b.score));
+    long totalHits = 0;
+
+    for (AnytimeRankingCollector collector : collectors) {
+      TopDocs shard = collector.topDocs();
+      totalHits += shard.totalHits.value();
+      for (ScoreDoc sd : shard.scoreDocs) {
+        if (queue.size() < topK) {
+          queue.offer(sd);
+        } else if (sd.score > queue.peek().score) {
+          queue.poll();
+          queue.offer(sd);
+        }
+      }
+    }
+
+    ScoreDoc[] results = queue.toArray(new ScoreDoc[0]);
+    java.util.Arrays.sort(results, (a, b) -> Float.compare(b.score, a.score));
+    return new TopDocs(
+        new TotalHits(totalHits, TotalHits.Relation.GREATER_THAN_OR_EQUAL_TO), results);
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingSearcher.java b/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingSearcher.java
new file mode 100644
index 00000000000..981275ed6a5
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingSearcher.java
@@ -0,0 +1,52 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search;
+
+import org.apache.lucene.util.HeuristicSLAEstimator;
+import org.apache.lucene.util.SLAEstimator;
+
+import java.io.IOException;
+
+/** SLA-aware searcher that applies bin-aware boosting and early termination. */
+public final class AnytimeRankingSearcher {
+
+  private final IndexSearcher searcher;
+  private final int topK;
+  private final long baseSlaMs;
+  private final SLAEstimator estimator;
+
+  /** Constructs a searcher with SLA cutoff and bin boosting. */
+  public AnytimeRankingSearcher(IndexSearcher searcher, int topK, long baseSlaMs, String field) {
+    this.searcher = searcher;
+    this.topK = topK;
+    this.baseSlaMs = baseSlaMs;
+    this.estimator = new HeuristicSLAEstimator(field);
+  }
+
+  /** Executes a search with bin-aware scoring and SLA cutoff. */
+  public TopDocs search(Query query) throws IOException {
+    long estimated = (long) estimator.estimate(query, searcher.getIndexReader(), baseSlaMs);
+    AnytimeRankingCollectorManager manager =
+        new AnytimeRankingCollectorManager(topK, estimated, searcher.getIndexReader());
+    return searcher.search(query, manager);
+  }
+
+  /** Returns the wrapped IndexSearcher. */
+  public IndexSearcher getSearcher() {
+    return searcher;
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/search/BinBoostCalculator.java b/lucene/core/src/java/org/apache/lucene/search/BinBoostCalculator.java
new file mode 100644
index 00000000000..50fb399d322
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/search/BinBoostCalculator.java
@@ -0,0 +1,95 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search;
+
+import org.apache.lucene.index.BinScoreLeafReader;
+import org.apache.lucene.index.BinScoreReader;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.util.ArrayUtil;
+
+import java.io.IOException;
+
+/** Computes per-bin score boosts using inverse frequency heuristics. */
+final class BinBoostCalculator {
+
+  private BinBoostCalculator() {}
+
+  /** Computes bin-level boosts using inverse frequency weighting with log scaling. */
+  static float[] compute(IndexReader reader) throws IOException {
+    int[] binCounts = new int[8]; // start small, grow as needed
+    int totalDocs = 0;
+    int maxBin = -1;
+
+    for (LeafReaderContext ctx : reader.leaves()) {
+      LeafReader leaf = ctx.reader();
+      BinScoreReader binReader =
+          (leaf instanceof BinScoreLeafReader)
+              ? ((BinScoreLeafReader) leaf).getBinScoreReader()
+              : null;
+      if (binReader == null) {
+        continue;
+      }
+
+      for (int docID = 0; docID < leaf.maxDoc(); docID++) {
+        int bin = binReader.getBinForDoc(docID);
+        if (bin >= binCounts.length) {
+          int newLength = Math.max(bin + 1, binCounts.length * 2);
+          binCounts = ArrayUtil.growExact(binCounts, newLength);
+        }
+        binCounts[bin]++;
+        totalDocs++;
+        maxBin = Math.max(maxBin, bin);
+      }
+    }
+
+    if (totalDocs == 0 || maxBin < 0) {
+      return new float[0];
+    }
+
+    float[] boosts = new float[maxBin + 1];
+    float maxBoost = 0f;
+
+    for (int bin = 0; bin <= maxBin; bin++) {
+      int count = binCounts[bin];
+      if (count == 0) {
+        boosts[bin] = 0f;
+        continue;
+      }
+
+      // Boost is proportional to inverse frequency
+      float freq = (float) count / totalDocs;
+      float boost = (float) Math.log((1.0f + 1.0f / freq)); // avoid log(0)
+      boosts[bin] = boost;
+      maxBoost = Math.max(maxBoost, boost);
+    }
+
+    // Normalize boosts to the range [1.0, max], where 1.0 is neutral
+    if (maxBoost > 0f) {
+      for (int i = 0; i < boosts.length; i++) {
+        if (boosts[i] == 0f) {
+          continue;
+        }
+        // Scale so the most underrepresented bin gets higher score
+        boosts[i] = 1.0f + (boosts[i] / maxBoost); // final boost ∈ [1.0, 2.0]
+      }
+    }
+
+    return boosts;
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/util/HeuristicSLAEstimator.java b/lucene/core/src/java/org/apache/lucene/util/HeuristicSLAEstimator.java
new file mode 100644
index 00000000000..27b1c1a9968
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/util/HeuristicSLAEstimator.java
@@ -0,0 +1,205 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.util;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanClause;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.BoostQuery;
+import org.apache.lucene.search.ConstantScoreQuery;
+import org.apache.lucene.search.DisjunctionMaxQuery;
+import org.apache.lucene.search.MatchAllDocsQuery;
+import org.apache.lucene.search.MultiTermQuery;
+import org.apache.lucene.search.PhraseQuery;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.SynonymQuery;
+import org.apache.lucene.search.TermQuery;
+
+import java.io.IOException;
+
+/**
+ * Estimate SLA based the number of query terms, query complexity, and average document frequency
+ */
+public class HeuristicSLAEstimator implements SLAEstimator {
+
+  private static final int MAX_SAMPLE_TERMS = 64;
+  private static final double MAX_MULT = 3.0;
+  private static final double TERM_COST = 0.2;
+  private static final double FREQ_COST = 0.0015;
+  private static final double QUERY_COMPLEXITY = 0.15;
+
+  private final String field;
+
+  public HeuristicSLAEstimator(String field) {
+    this.field = field;
+  }
+
+  @Override
+  public double estimate(Query query, IndexReader reader, long baseSlaMs) throws IOException {
+    final int termCount = estimateTermCount(query);
+    final double avgDocFreq = estimateAvgDocFreq(reader);
+    final int queryCost = estimateQueryCost(query);
+
+    double m = 1.0;
+    m += TERM_COST * termCount;
+    m += FREQ_COST * avgDocFreq;
+    m += QUERY_COMPLEXITY * queryCost;
+
+    return baseSlaMs * Math.min(MAX_MULT, m);
+  }
+
+  /** Estimate of number of terms that will participate in the scoring */
+  private int estimateTermCount(Query query) {
+    if (query instanceof MatchAllDocsQuery) {
+      return 0;
+    }
+
+    if (query instanceof TermQuery) {
+      return 1;
+    }
+
+    if (query instanceof PhraseQuery pq) {
+      return pq.getTerms().length;
+    }
+
+    if (query instanceof BooleanQuery bq) {
+      int total = 0;
+      for (BooleanClause clause : bq) {
+        BooleanClause.Occur occur = clause.occur();
+        if (occur == BooleanClause.Occur.MUST || occur == BooleanClause.Occur.SHOULD) {
+          total += estimateTermCount(clause.query());
+        }
+      }
+      return total > 0 ? total : 1;
+    }
+
+    if (query instanceof DisjunctionMaxQuery dmq) {
+      // Take the cost of max cost branch
+      int max = 0;
+      for (Query sub : dmq.getDisjuncts()) {
+        max = Math.max(max, estimateTermCount(sub));
+      }
+      return max > 0 ? max : 1;
+    }
+
+    if (query instanceof SynonymQuery sq) {
+      return sq.getTerms().size();
+    }
+
+    if (query instanceof MultiTermQuery) {
+      // Conservative measure - no way to actually estimate
+      return 2;
+    }
+
+    if (query instanceof BoostQuery bq) {
+      return estimateTermCount(bq.getQuery());
+    }
+
+    if (query instanceof ConstantScoreQuery csq) {
+      return estimateTermCount(csq.getQuery());
+    }
+
+    // Default baseline cost - fallback if unknown query type
+    // Returning 0 will reduce the SLA to impractical values
+
+    return 1;
+  }
+
+  /** Coarse estimate of query execution cost. */
+  private int estimateQueryCost(Query query) {
+    if (query instanceof MatchAllDocsQuery) {
+      return 1;
+    }
+
+    if (query instanceof TermQuery) {
+      return 2;
+    }
+
+    if (query instanceof PhraseQuery pq) {
+      return 3 + pq.getTerms().length;
+    }
+
+    if (query instanceof BooleanQuery bq) {
+      int total = 0;
+      for (BooleanClause clause : bq) {
+        BooleanClause.Occur occur = clause.occur();
+        if (occur == BooleanClause.Occur.MUST || occur == BooleanClause.Occur.SHOULD) {
+          total += estimateQueryCost(clause.query());
+        }
+      }
+      return Math.max(2, total);
+    }
+
+    if (query instanceof DisjunctionMaxQuery dmq) {
+      // Max cost branch
+      int max = 0;
+      for (Query sub : dmq.getDisjuncts()) {
+        max = Math.max(max, estimateQueryCost(sub));
+      }
+      return 2 + max;
+    }
+
+    if (query instanceof SynonymQuery sq) {
+      return 2 + sq.getTerms().size();
+    }
+
+    if (query instanceof MultiTermQuery) {
+      // Conservative estimate - no way to actually measure
+      return 6;
+    }
+
+    if (query instanceof BoostQuery bq) {
+      return estimateQueryCost(bq.getQuery());
+    }
+
+    if (query instanceof ConstantScoreQuery csq) {
+      return estimateQueryCost(csq.getQuery());
+    }
+
+    // Default baseline cost - fallback if unknown query type
+    // Returning 0 will reduce the SLA to impractical values
+    return 4;
+  }
+
+  /** Computes average document frequency across a sample of terms in the field. */
+  private double estimateAvgDocFreq(IndexReader reader) throws IOException {
+    long docFreqSum = 0;
+    int sampled = 0;
+
+    for (LeafReaderContext leaf : reader.leaves()) {
+      Terms terms = leaf.reader().terms(field);
+      if (terms == null) {
+        continue;
+      }
+
+      TermsEnum te = terms.iterator();
+      while (te.next() != null && sampled < MAX_SAMPLE_TERMS) {
+        docFreqSum += te.docFreq();
+        sampled++;
+      }
+
+      if (sampled >= MAX_SAMPLE_TERMS) {
+        break;
+      }
+    }
+
+    return sampled > 0 ? (double) docFreqSum / sampled : 0.0;
+  }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/util/SLAEstimator.java b/lucene/core/src/java/org/apache/lucene/util/SLAEstimator.java
new file mode 100644
index 00000000000..667e4bc111c
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/util/SLAEstimator.java
@@ -0,0 +1,27 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.util;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.search.Query;
+
+import java.io.IOException;
+
+/** Interface to implement SLA Estimator */
+public interface SLAEstimator {
+  double estimate(Query query, IndexReader reader, long baseSlaMs) throws IOException;
+}